從原理聊JVM（三）：詳解現代垃圾回收器Shenandoah和ZGC
作者：京東科技 康志興
Shenandoah
Shenandoah一詞來自於印第安語，十九世紀四十年代有一首著名的航海歌曲在水手中廣為流傳，講述一位年輕富商愛上印第安酋長Shenandoah的女兒的故事。 後來美國有一條位於Virginia州西部的小河以此命名，所以Shenandoah的中文譯名為「情人渡」。
Shenandoah首次出現在Open JDK12中，是由Red Hat開發，主要為了解決之前各種垃圾回收器處理大堆時停頓較長的問題。
相比較G1將低停頓做到了百毫秒級別，Shenandoah的設計目標是將停頓壓縮到10ms級別，且與堆大小無關。它的設計非常激進，很多設計點在權衡上更傾向於低停頓，而不是高吞吐。
「G1的繼承者」
Shenandoah是OpenJDK中的垃圾處理器，但相比較Oracle JDK中根正苗紅的ZGC，Shenandoah可以說更像是G1的繼承者，很多方面與G1非常相似，甚至共用了一部分程式碼。
總的來說，Shenandoah和G1有三點主要區別：
1.G1的回收是需要STW的，而且這部分停頓佔整體停頓時間的80%以上，Shenandoah則實現了並行回收。
2.Shenandoah不再區分年輕代和年老代。
3.Shenandoah使用連線矩陣替代G1中的卡表。
關於G1的詳細介紹請翻看前一篇：從原理聊JVM（二）：從序列收集器到分割區收集開創者G1
連線矩陣（Connection Matrix）
G1中每個Region都要維護卡表，既耗費計算資源還佔據了非常大的記憶體空間，Shenandoah使用了連線矩陣來優化了這個問題。
連線矩陣可以簡單理解為一個二維表格，如果Region A中有物件指向Region B中的物件，那麼就在表格的第A行第B列打上標記。
比如，Region 1指向Region 3，Region 4指向Region 2，Region 3指向Region 5：
相比G1的記憶集來說，連線矩陣的顆粒度更粗，直接指向了整個Region，所以掃描範圍更大。但由於此時GC是並行進行的，所以這是通過選擇更低資源消耗的連線矩陣而對吞吐進行妥協的一項決策。
轉發指標
轉發指標的效能優勢
想要達到並行回收，就需要在使用者執行緒執行的同時，將存活物件逐步複製到空的Region中，這個過程中就會在堆中同時存在新舊兩個物件。那麼如何讓使用者執行緒存取到新物件呢？
此前，通常是在舊物件原有記憶體上設定保護陷阱（Memory Protection Trap），當存取到這個舊物件時就會發生自陷異常，使程式進入到預設的例外處理器中，再由處理器中的程式碼將存取轉發到複製後的新物件上。
自陷是由執行緒發起來打斷當前執行的程式，進而獲得CPU的使用權。這一操作通常需要作業系統參與，那麼就會發生使用者態到核心態的轉換，代價十分巨大。
所以Rodney A.Brooks提出了使用轉發指標來實現通過舊物件存取新物件的方式：在物件頭前面增加一個新的參照欄位，在非並行移動情況下指向自己，產生新物件後指向新物件。那麼當存取物件的時候，都需要先存取轉發指標看看其指向哪裡。雖然和記憶體自陷方案相比同樣需要多一次存取轉發的開銷，但是前者消耗小了很多。
轉發指標的問題
轉發指標主要存在兩個問題：修改時的執行緒安全問題和高頻存取的效能問題。
1.物件體增加了一個轉發指標，這個指標的修改和物件本身的修改就存在了執行緒安全問題。如果通過被存取就可能發生複製了新物件後，轉發物件修改之前發生了舊物件的修改，這就存在兩個物件不一致的問題了。對於這個問題，Shenandoah是通過CAS操作來保證修改正確性的。
2.轉發指標的加入需要覆蓋所有物件存取的場景，包括讀、寫、加鎖等等，所以需要同時設定讀屏障和寫屏障。尤其讀操作相比單純寫操作出現頻率更高，這樣高頻操作帶來的效能問題影響巨大。所以Shenandoah在JDK13中對此進行了優化，將記憶體屏障模型改為參照存取屏障，也就是說，僅僅在物件中參照型別的讀寫操作增加屏障，而不去管原生物件的操作，這就省去了大量的物件存取操作。
Shenandoah的執行步驟
- 初始標記（Init Mark）[STW] [同G1]
標記與GC Roots直接關聯的物件。
- 並行標記（Concurrent Marking）[同G1]
遍歷物件圖，標記全部可達物件。
- 最終標記（Final Mark）[STW] [同G1]
處理剩餘的SATB掃描，並在這個階段統計出回收價值最高的Region，將這些Region構成一組回收集。
- 並行清理（Concurrent Cleanup）
回收所有不包含任何存活物件的Region（這類Region被稱為Immediate Garbage Region）。
- 並行回收（Concurrent Evacuation）
將回收集裡面的存貨物件複製到一個其他未被使用的Region中。並行複製存活物件，就會在同一時間內，同一物件在堆中存在兩份，那麼就存在該物件的讀寫一致性問題。Shenandoah通過使用轉發指標將舊物件的請求指向新物件解決了這個問題。這也是Shenandoah和其他GC最大的不同。
- 初始參照更新（Init Update References）[STW]
並行回收後，需要將所有指向舊物件的參照修正到新物件上。這個階段實際上並沒有實際操作，只是設定一個阻塞點來保證上述並行操作均已完成。
- 並行參照更新（Concurrent Update References）
順著記憶體實體地址線性遍歷堆空間，更新並行回收階段複製的物件的參照。
- 最終參照更新（Final Update References）[STW]
堆空間中的參照更新完畢後，最後需要修正GC Roots中的參照。
- 並行清理（Concurrent Cleanup）
此時回收集中Region應該全部變成Immediate Garbage Region了，再次執行並行清理，將這些Region全部回收。
ZGC
ZGC是Oracle官方研發並JDK11中引入，並於JDK15中作為生產就緒使用，其設計之初定義了三大目標：
1.支援TB級記憶體
2.停頓控制在10ms以內，且不隨堆大小增加而增加
3.對程式吞吐量影響小於15%
隨著JDK的迭代，目前JDK16及以上版本，ZGC已經可以實現不超過1毫秒的停頓，適用於堆大小在8MB到16TB之間。
ZGC的記憶體佈局
ZGC和G1一樣也採用了分割區域的堆記憶體佈局，不同的是，ZGC的Region（官方稱為Page，概念同G1的Region）可以動態建立和銷燬，容量也可以動態調整。
ZGC的Region分為三種：
1.小型Region容量固定為2MB，用於存放小於256KB的物件。
2.中型Region容量固定為32MB，用於存放大於等於256KB但不足4MB的物件。
3.大型Region容量為2MB的整數倍，存放4MB及以上大小的物件，而且每個大型Region中只存放一個大物件。由於大物件移動代價過大，所以該物件不會被重分配。
重分配集（Relocation Set）
G1中的回收集用來存放所有需要G1掃描的Region，而ZGC為了省去卡表的維護，標記過程會掃描所有Region，如果判定某個Region中的存活物件需要被重分配，那麼就將該Region放入重分配集中。
通俗的說，如果將GC分為標記和回收兩個主要階段，那麼回收集是用來判定標記哪些Region，重分配集用來判定回收哪些Region。
染色指標
和Shenandoah相同，ZGC也實現了並行回收，不同的是前者是使用轉發指標來實現的，後者則是採用染色指標的技術來實現。
三色標記本質上與物件無關，僅僅與參照有關：通過參照關係判定對像存活與否。HotSpot虛擬機器器中不同垃圾回收器有著不同的處理方式，有些是標記在物件頭中，有些是標記在單獨的資料結構中，而ZGC則是直接標記在指標上。
64位元機器指標是64位元，Linux下64位元中高18位元不能用來定址，剩下46位中，ZGC選擇其中4位元用來輔助GC工作，另外42位能夠支援最大記憶體為4T，通常來說，4T的記憶體完全夠用。
具體來說，ZGC在指標中增加了4個標誌位，包括Finalizable、Remapped、Marked 0和Marked 1。
原始碼註釋如下：
6 4 4 4 4 4 0
3 7 6 5 2 1 0
+-------------------+-+----+-----------------------------------------------+
|00000000 00000000 0|0|1111|11 11111111 11111111 11111111 11111111 11111111|
+-------------------+-+----+-----------------------------------------------+
| | | |
| | | * 41-0 Object Offset (42-bits, 4TB address space)
| | |
| | * 45-42 Metadata Bits (4-bits) 0001 = Marked0
| | 0010 = Marked1
| | 0100 = Remapped
| | 1000 = Finalizable
| |
| * 46-46 Unused (1-bit, always zero)
|
* 63-47 Fixed (17-bits, always zero)
Finalizable標識表示物件是否只能通過finalize()方法存取到，Remapped、Marked 0和Marked 1用作三色標記（後面簡稱為M0和M1）。
為什麼既有M0還有M1呢？
因為ZGC標記完成後並不需要等待物件指標重對映就可以進行下一次垃圾回收迴圈，也就是說兩次垃圾回收的全過程是有重疊的，所以使用兩個標記位分別用作兩次相鄰GC過程的標記，M0和M1交替使用。
染色指標的在GC過程中的作用
我們通過紅藍黃三個顏色分別表示三種標記狀態：
1.第一次標記開始時所有的指標都處於Remapped狀態
- 從GC Root開始，順著物件圖遍歷掃描，存活物件標記為
M0
- 標記完成後，開始進行並行重分配。最終目標是將A、B、C三個存活物件都移動到新的Region中去。
整個標記過程中新分配到物件都被直接標記為M0，比如物件D。
複製完成的物件，指標就可以由M0改為Remapped，並將舊物件到新物件到對映關係儲存到轉發表中。
- 如果此時系統存取物件C，會觸發讀屏障，將原參照修正到新的物件C的地址上去，並轉發存取，最後刪除轉發表的記錄。
這個行為稱為指標的「自愈」。
實際上，如果沒有物件D的存在，在上一步所有存貨物件轉移完成後，舊的Page就可以被回收了，依靠指標和轉發表就可以將所有存取轉發到新的Page中去。
- 並行重對映階段會把所有參照修正，並刪除轉發表的記錄。
- 下一次並行標記開始後，由於上一次垃圾回收迴圈並沒有完成，所以
Remapped指標被標記為M1，用來和上一次的存活物件標記作區分。
可以看出，並行標記的過程中，ZGC是通過讀屏障來保證存取的正確轉發，並且由於染色指標採用惰性更新的策略，相比Shenandoah每次都要先存取轉發指標的兩次定址來說快上不少。
染色指標的三大優點
1.由於染色指標提供的「自愈」能力，當某個Page被清除後可以立刻被回收，而無需等待修正全部指向該Page的參照。
2.ZGC完全不需要使用寫屏障，原因有二：由於使用染色指標，無需更新物件體；沒有分代所以無需記錄跨代參照。
3.染色指標並未完全開發使用，剩下的18位元提供了非常大的擴充套件性。
而染色指標有一個天然的問題，就是作業系統和處理器並不完全支援程式對指標的修改。
多種記憶體對映
染色指標只是JVM定義的，作業系統、處理器未必支援。為了解決這個問題，ZGC在Linux/x86-64平臺上採用了虛擬記憶體對映技術。
ZGC為每個物件都建立了三個虛擬記憶體地址，分別對應Remapped、Marked 0和Marked 1，通過指標指向不同的虛擬記憶體地址來表示不同的染色標記。
分代
ZGC沒有分代，這一點並不是技術權衡，而是基於工作量的考慮。所以目前來看，整體的GC效率還有很大提升空間。
讀屏障
ZGC使用了讀屏障來完成指標的「自愈」，由於ZGC目前沒有分代，且ZGC通過掃描所有Region來省去卡表使用，所以ZGC並沒有寫屏障，這成為ZGC一大效能優勢。
NUMA
多核CPU同時操作記憶體就會發生爭搶，現代CPU把記憶體控制系統器整合到處理器核心中，每個CPU核心都有屬於自己的本地記憶體。
在NUMA架構下，ZGC會有現在自己的本地記憶體上分配物件，避免了記憶體使用的競爭。
在ZGC之前，只有Parallet Scavenge支援NUMA記憶體分配。
ZGC的執行步驟
ZGC和Shenadoah一樣，幾乎所有執行階段都和使用者執行緒並行進行。其中同樣包含初始標記、重新標記等STW的過程，作用相同，不再贅述。重點介紹以下四個並行階段：
並行標記
並行標記階段和G1相同，都是遍歷物件圖進行可達性分析，不同的是ZGC的標記在染色指標上。
並行預備重分配
在這個階段，ZGC會掃描所有Region，如果哪些Region裡面的存活物件需要被分配的新的Region中，就將這些Region放入重分配集中。
此外，JDK12後ZGC的類解除安裝和弱參照的處理也在這個階段。
並行重分配
ZGC在這個階段會將重分配集裡面的Region中的存貨物件複製到一個新的Region中，併為重分配集中每一個Region維護一個轉發表，記錄舊物件到新物件的對映關係。
如果在這個階段使用者執行緒並行存取了重分配過程中的物件，並通過指標上的標記發現物件處於重分配集中，就會被讀屏障截獲，通過轉發表的內容轉發該存取，並修改該參照的值。
ZGC將這種行為稱為自愈（Self-Healing），ZGC的這種設計導致只有在存取到該指標時才會觸發一次轉發，比Shenandoah的轉發指標每次都要轉發要好得多。
另一個好處是，如果一個Region中所有物件都複製完畢了，該Region就可以被回收了，只要保留轉發表即可。
並行重對映
最後一個階段的任務就是修正所有的指標並釋放轉發表。
這個階段的迫切性不高，所以ZGC將並行重對映合併到在下一次垃圾回收迴圈中的並行標記階段中，反正他們都需要遍歷所有物件。
總結
現代的垃圾回收器為了低停頓的目標可謂將「並行」二字玩到極致，Shenandoah在G1基礎上做了非常多的優化來使回收階段並行，而ZGC直接採用了染色指標、NUMA等黑科技，目的都是為了讓Java開發者可以更多的將精力放在如何使用物件讓程式更好的執行，剩下的一切交給GC，我們所做的只需享受現代化GC技術帶來的良好體驗。
參考：
1.OpenJDK 17 中的 Shenandoah：亞毫秒級 GC 停頓【譯】 - 知乎 (zhihu.com)
2.https://shipilev.net/talks/devoxx-Nov2017-shenandoah.pdf
3.https://openjdk.java.net/jeps/333