分散式拒絕服務攻擊（DDoS）指的是通過多台機器向一個服務或者網站發送大量看似合法的數據包使其網路阻塞、資源耗盡從而不能為正常用戶提供正常服務的攻擊手段。隨著互聯網帶寬的增加和相關工具的不斷發佈，這種攻擊的實施難度越來越低，有大量IDC托管機房、商業站點、游戲服務商一直飽受DDoS攻擊的困擾，那麼如... ...
原文來自公眾號：猿人谷
在Java中記憶體是由虛擬機自動管理的，虛擬機在記憶體中划出一片區域，作為滿足程式記憶體分配請求的空間。記憶體的創建仍然是由程式猿來顯示指定的，但是對象的釋放卻對程式猿是透明的。就是解放了程式猿手動回收記憶體的工作，交給垃圾回收器來自動回收。
在虛擬機中，釋放哪些不再被使用的對象所占空間的過程稱為垃圾收集（Garbage Collection，GC）。負責垃圾收集的程式模塊，成為垃圾收集器（Garbage Collector）。
既然虛擬機已經幫我們把垃圾自動處理了，為什麼還要去瞭解GC和記憶體分配呢？
當需要排查各種記憶體溢出、記憶體泄漏問題時，當垃圾收集成為系統達到更高併發量的瓶頸時，我們就需要對虛擬機的自動管理技術實施必要的監控和調節了。這也是JVM調優，故障排查，重點需要掌握的知識了。
本篇我們的重點是介紹何謂垃圾及垃圾回收演算法，那我們就要弄清到底什麼是垃圾？能不能設計一種強大的垃圾回收演算法來解決垃圾回收的所有問題？肯定是沒有的，後面介紹的每一種垃圾回收演算法都有它得天獨厚的優點，也有它避之不及的缺點。針對具體的場景，靈活運用方是上策。
希望大家能帶著如下問題進行學習，會收穫更大。
- 什麼是垃圾？
- 如何回收垃圾？
- 有沒有一種垃圾回收演算法能像銀彈一樣解決所有垃圾所有？
- GC的分類是什麼樣的？（Minor GC、Major GC、Full GC）
- Stop-the-world是什麼？
- 如何避免全堆掃描？
1 垃圾回收
在堆裡面存放著Java世界中幾乎所有的對象實例，垃圾收集器在堆進行回收前，第一件事就是要確定這些對象之中哪些還“存活”著，哪些已經“死亡”（即不可能再被任何途徑使用的對象）。垃圾回收，其實就是將已經分配出去的，但不再使用的記憶體回收，以便能夠再次分配。在Java虛擬機的規範中，垃圾指的就是死亡的對象所占據的堆空間。
那怎麼確定一個對象是存活還是死亡呢？
1.1 引用計數演算法
給對象中添加一個引用計數器，每當有一個地方引用它時，計數器值就加1；當引用失效時，計數器值就減1；任何時刻計數器為0的對象就是不可能再被使用的。也就是說，需要截獲所有的引用更新操作，並且相應地增減目標對象的計數器。
題外話：記得研一那段時間對iOS開發感興趣，找個公司去實習，現學現搞iOS開發，當時是做了一個模擬炒股的app。用的就是Objective-C，這門語言起初管理記憶體的方式就是用的這種引用計數演算法，不過後面也有了自動管理記憶體。接觸的對象多了，發現很多東西在本質的原理有非常多的相似之處。
引用計數演算法缺點：
- 需要額外的空間來存儲計數器，以及繁瑣的更新操作。
- 無法處理迴圈引用對象。
其中無法處理迴圈引用對象，算是引用計數法的一個重大漏洞。
1.2 可達性分析演算法
可達性是指，如果一個對象會被至少一個在程式中的變數通過直接或間接的方式被其他可達的對象引用，則稱該對象是可達的（reachable）。更準確的說，一個對象只有滿足下述兩個條件之一，就會被判斷為可達的：
- 本身是根對象。根（Root）是指由堆以外空間訪問的對象。JVM中會將一組對象標記為根，包括全局變數、部分系統類，以及棧中引用的對象，如當前棧幀中的局部變數和參數。
- 被一個可達的對象引用。
這個演算法的基本思路就是通過一系列的成為“GC Roots”的對象作為起始點，從這些節點開始向下搜索，搜索所走過的路徑稱為引用鏈（Reference Chain），當一個對象到GC Roots沒有任何引用鏈相連（即從GC Roots到這個對象不可達），則證明此對象是不可用的。
GC Roots又是什麼呢？可以暫時理解為由堆外指向堆內的引用。
在Java語言中，可以作為GC Roots的對象包括下麵幾種：
- 虛擬機棧（棧幀中的本地變數表）中引用的對象。
- 方法區中類靜態屬性引用的對象。
- 方法區中常量引用的對象。
- 本地方法棧中JNI（即一般說的Native方法）引用的對象。
- 已啟動且未停止的Java線程。
可達性分析演算法可以解決引用計數演算法不能解決的迴圈引用問題。舉個例子，即便對象a和b相互引用，只要從GC Roots出發無法到達a或者b，那麼可達性分析便不會將它們加入存活對象合集之中。
關於Java中的引用的定義及分類（強引用、軟引用、弱引用、虛引用）會在單獨出一篇進行詳細介紹，Java引用的內容雖然有點冷門，但是很多公司面試的常考點。
可達性分析演算法本身雖然很簡明，但是在實踐中還是有不少其他問題需要解決的。比如，在多線程環境下，其他線程可能會更新已經訪問過的對象中的引用，從而造成誤報（將引用設置為null）或者漏報（將引用設置為未被訪問過的對象）。誤殺還可以接受，Java虛擬機至多損失了部分垃圾回收的機會。漏報就問題大了，因為垃圾回收器可能回收事實上仍被引用的對象記憶體。一旦從原引用訪問已經被回收了的對象，則很有可能會直接導致Java虛擬機奔潰。
2 垃圾回收演算法
上面我們介紹什麼是Java中的垃圾，接下來我們就開始介紹如何高效的回收這些垃圾。
2.1 標記-清除演算法
標記-清除（Mark-Sweep）演算法可以分為兩個階段：
- 標記階段：標記出所有可以回收的對象。
- 清除階段：回收所有已被標記的對象，釋放這部分空間。
該演算法存在如下不足：
- 記憶體碎片。由於Java虛擬機的堆中對象必須是連續分佈的，因此可能出現總空閑記憶體足夠，但是無法分配的極端情況。無法找到足夠的連續記憶體，而不得不提前觸發一次垃圾收集動作。
- 分配效率較低。如果是一塊連續的記憶體空間，那麼我們可以通過指針加法（pointer bumping）來做分配。而對於空閑列表，Java虛擬機則需要逐個訪問列表中的項，來查詢能夠放入新建對象的空閑記憶體。
標記-清除演算法的示意圖如下：
2.2 複製演算法
複製演算法的過程如下：
- 劃分區域：將記憶體區域按比例劃分為1個Eden區作為分配對象的“主戰場”和2個幸存區（即Survivor空間，劃分為2個等比例的from區和to區）。
- 複製：收集時，打掃“戰場”，將Eden區中仍存活的對象複製到某一塊幸存區中。
- 清除：由於上一階段已確保仍存活的對象已被妥善安置，現在可以“清理戰場”了，釋放Eden區和另一塊幸存區。
- 晉升：如在“複製”階段，一塊幸存區接納不了所有的“幸存”對象。則直接晉升到老年代。
該演算法解決了記憶體碎片化問題，但堆空間的使用效率極其低下。在對象存活率較高時，需要進行較多的複製操作，效率會變得很低。
2.3 標記-整理演算法
該演算法分為兩個階段：
- 標記階段：標記出所有可以回收的對象。
- 壓縮階段：將標記階段的對象移動到空間的一端，釋放剩餘的空間。
該演算法的標記過程與標記-清除演算法一樣，但後續步驟不是直接對可回收對象進行清理，而是讓所有存活的對象都向一端移動，然後直接清理掉端邊界以外的記憶體。
解決了記憶體碎片的問題，也規避了複製演算法只能利用一半記憶體區域的弊端。看起來很美好，但它對記憶體變動更頻繁，需要整理所有存活對象的引用地址，在效率上比複製演算法要差很多。
標記-整理演算法的示意圖如下：
2.4 分代收集演算法
分代收集演算法倒並沒有什麼新的思想，只是根據對象存活周期的不同將記憶體劃分為幾塊。一般是把Java堆分為新生代和老年代，這樣就可以根據各個年代的特點採用最適當的收集演算法。
在新生代中，每次垃圾收集時都發現有大批對象死去，只有少量存活，那就選用複製演算法，只需要付出少量存活對象的複製成本就可以完成收集。而老年代中因為對象存活率高、沒有額外空間對它進行分配擔保，就必須使用標記-清理演算法或標記-整理演算法來進行回收。
3 HotSpot演算法實現
3.1 枚舉根節點
以可達性分析中從GC Roots節點找引用鏈這個操作為例，可作為GC Roots的節點主要在全局性的引用（例如常量或類靜態屬性）與執行上下文（例如棧幀中的本地變數表）中。上面介紹可達性分析演算法時有詳細介紹GC Roots，可以參看上面。
3.2 安全點（Safepoint）
安全點，即程式執行時並非在所有地方都能停頓下來開始GC，只有在到達安全點時才能暫停。Safepoint的選定既不能太少以至於讓GC等待時間太長，也不能過於頻繁以致於過分增大運行時的負荷。
安全點的初始目的並不是讓其他線程停下，而是找到一個穩定的執行狀態。在這個執行狀態下，Java虛擬機的堆棧不會發生變化。這麼一來，垃圾回收器便能夠“安全”地執行可達性分析。只要不離開這個安全點，Java虛擬機便能夠在垃圾回收的同時，繼續運行這段本地代碼。
程式運行時並非在所有地方都能停頓下來開始GC，只有在到達安全點時才能暫停。安全點的選定基本上是以程式“是否具有讓程式長時間執行的特征”為標準進行選定的。“長時間執行”的最明顯特征就是指令序列復用，例如方法調用、迴圈跳轉、異常跳轉等，所以具有這些功能的指令才會產生Safepoint。
對於安全點，另一個需要考慮的問題就是如何在GC發生時讓所有線程（這裡不包括執行JNI調用的線程）都“跑”到最近的安全點上再停頓下來。
兩種解決方案：
搶先式中斷（Preemptive Suspension）
搶先式中斷不需要線程的執行代碼主動去配合，在GC發生時，首先把所有線程全部中斷，如果發現有線程中斷的地方不在安全點上，就恢複線程，讓它“跑”到安全點上。現在幾乎沒有虛擬機採用這種方式來暫停線程從而響應GC事件。
主動式中斷（Voluntary Suspension）
主動式中斷的思想是當GC需要中斷線程的時候，不直接對線程操作，僅僅簡單地設置一個標誌，各個線程執行時主動去輪詢這個標誌，發現中斷標誌為真時就自己中斷掛起。輪詢標誌地地方和安全點是重合的，另外再加上創建對象需要分配記憶體的地方。
3.3 安全區域
指在一段代碼片段中，引用關係不會發生變化。在這個區域中任意地方開始GC都是安全的。也可以把Safe Region看作是被擴展了的Safepoint。
4 擴展知識
4.1 GC分類
Minor GC：
- 針對新生代。
- 指發生在新生代的垃圾收集動作，因為java對象大多都具備朝生夕死的特性，所以Minor GC非常頻繁，一般回收速度也比較快。
- 觸發條件：Eden空間滿時。
Major GC：
- 針對老年代。
- 指發生在老年代的GC，出現了Major GC，經常會伴隨至少一次的Minor GC（但非絕對的，在Parallel Scavenge 收集器的收集策略里就有直接進行Major GC的策略選擇過程）。Major GC的速度一般會比Minor GC慢10倍以上。
- 觸發條件：Minor GC 會將對象移到老年代中，如果此時老年代空間不夠，那麼觸發 Major GC。
Full GC：
- 清理整個堆空間。一定意義上Full GC 可以說是 Minor GC 和 Major GC 的結合。
- 觸發條件：調用System.gc()；老年代空間不足；空間分配擔保失敗。
4.2 Stop-the-world
GC進行時必須停頓所有Java執行線程，這就是Stop-the-world。
可達性分析時必須在一個能確保一致性的快照中進行，這裡“一致性”的意思是指在整個分析期間整個執行系統看起來就像被凍結在某個時間點上，不可以出現分析過程中對象引用關係還在不斷變化的情況，這一點不滿足的話分析結果準確性就無法得到保證。
Stop-the-world是通過安全點機制來實現的。當Java虛擬機接收到Stop-the-world請求，它便會等待所有的線程都到達安全點，才允許請求Stop-the-world的線程進行獨占的工作。
4.3 卡表
有個場景，老年代的對象可能引用新生代的對象，那標記存活對象的時候，需要掃描老年代中的所有對象。因為該對象擁有對新生代對象的引用，那麼這個引用也會被稱為GC Roots。那不是得又做全堆掃描？成本太高了吧。
HotSpot給出的解決方案是一項叫做卡表（Card Table）的技術。該技術將整個堆劃分為一個個大小為512位元組的卡，並且維護一個卡表，用來存儲每張卡的一個標識位。這個標識位代表對應的卡是否可能存有指向新生代對象的引用。如果可能存在，那麼我們就認為這張卡是髒的。
在進行Minor GC的時候，我們便可以不用掃描整個老年代，而是在卡表中尋找臟卡，並將臟卡中的對象加入到Minor GC的GC Roots里。當完成所有臟卡的掃描之後，Java虛擬機便會將所有臟卡的標識位清零。
想要保證每個可能有指向新生代對象引用的卡都被標記為臟卡，那麼Java虛擬機需要截獲每個引用型實例變數的寫操作，並作出對應的寫標識位操作。
卡表能用於減少老年代的全堆空間掃描，這能很大的提升GC效率。
