GC回收器演進之路

這篇具有很好參考價值的文章主要介紹了GC回收器演進之路。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

GC回收器演進之路,jvm,開發(fā)語言

未來演進方向

歷經(jīng)之路

引用計數(shù)法

標記清除法

復制法

標記整理

分代式

三色標記法的誕生

三色標記法的基本概念

產(chǎn)生的問題

問題 1：浮動垃圾

問題 2：對象消失

遍歷對象圖不需要 STW 的解決方案

屏障機制

插入屏障（Dijkstra）- 灰色賦值器

刪除屏障（Yuasa）- 黑色賦值器?

混合屏障

引用

未來演進方向

垃圾收集器是實現(xiàn)垃圾回收的具體實現(xiàn)，是GC技術的核心組件。垃圾收集器的演進方向主要包括以下幾個方面：

低延遲：隨著互聯(lián)網(wǎng)和移動設備的普及，對于低延遲的要求越來越高。因此，垃圾收集器需要支持低延遲的回收，以減少GC對程序性能的影響。
高吞吐量：高吞吐量是指垃圾收集器需要在盡可能短的時間內(nèi)回收盡可能多的垃圾。高吞吐量對于大規(guī)模數(shù)據(jù)處理和高性能計算等應用非常重要。
分代收集：分代收集是指將內(nèi)存分為不同的代，每個代有不同的生命周期和回收策略。通過采用不同的回收策略和頻率，可以提高GC效率和程序性能。
并發(fā)收集：并發(fā)收集是指在程序運行過程中，GC線程和應用線程可以同時執(zhí)行，以減少GC對程序性能的影響。并發(fā)收集需要解決線程安全、一致性和可靠性等問題。
分區(qū)收集：分區(qū)收集是指將內(nèi)存分為多個區(qū)域，每個區(qū)域有不同的分配和回收策略。通過采用不同的分區(qū)大小和回收策略，可以提高GC效率和程序性能。
壓縮收集：壓縮收集是指在回收內(nèi)存時，將存活對象移動到一起，以減少內(nèi)存碎片和提高內(nèi)存利用率。壓縮收集需要對程序中的引用進行調(diào)整，并且會對程序性能產(chǎn)生一定影響。

垃圾收集器的演進方向需要根據(jù)具體應用場景和需求進行選擇和優(yōu)化，以提高程序性能和用戶體驗。

歷經(jīng)之路

引用計數(shù)法

根據(jù)對象自身的引用計數(shù)來回收，當引用計數(shù)歸零時進行回收，但是計數(shù)頻繁更新會帶來更多開銷，且無法解決循環(huán)引用的問題。

優(yōu)點：簡單直接，回收速度快
缺點：需要額外的空間存放計數(shù)，無法處理循環(huán)引用的情況；

標記清除法

標記出所有不需要回收的對象，在標記完成后統(tǒng)一回收掉所有未被標記的對象。

GC回收器演進之路,jvm,開發(fā)語言

優(yōu)點：簡單直接，速度快，適合可回收對象不多的場景
缺點：會造成不連續(xù)的內(nèi)存空間（內(nèi)存碎片），導致有大的對象創(chuàng)建的時候，明明內(nèi)存中總內(nèi)存是夠的，但是空間不是連續(xù)的造成對象無法分配；

復制法

復制法將內(nèi)存分為大小相同的兩塊，每次使用其中的一塊，當這一塊的內(nèi)存使用完后，將還存活的對象復制到另一塊去，然后再把使用的空間一次清理掉

GC回收器演進之路,jvm,開發(fā)語言

優(yōu)點：解決了內(nèi)存碎片的問題，每次清除針對的都是整塊內(nèi)存，但是因為移動對象需要耗費時間，效率低于標記清除法；
缺點：有部分內(nèi)存總是利用不到，資源浪費，移動存活對象比較耗時，并且如果存活對象較多的時候，需要擔保機制確保復制區(qū)有足夠的空間可完成復制；

標記整理

標記過程同標記清除法，結(jié)束后將存活對象壓縮至一端，然后清除邊界外的內(nèi)容。

GC回收器演進之路,jvm,開發(fā)語言

優(yōu)點：解決了內(nèi)存碎片的問題，也不像標記復制法那樣需要擔保機制，存活對象較多的場景也使適用；
缺點：性能低，因為在移動對象的時候不僅需要移動對象還要維護對象的引用地址，可能需要對內(nèi)存經(jīng)過幾次掃描才能完成；

分代式

注意！這也是最重要的一種回收思想。eg. g1, c4, zgc, shenandah.

將對象根據(jù)存活時間的長短進行分類，存活時間小于某個值的為年輕代，存活時間大于某個值的為老年代，永遠不會參與回收的對象為永久代。并根據(jù)分代假設（如果一個對象存活時間不長則傾向于被回收，如果一個對象已經(jīng)存活很長時間則傾向于存活更長時間）對對象進行回收。

三色標記法的誕生

事實上，GC Roots 相比起整個 Java 堆中全部的對象畢竟還算是極少數(shù)，且在各種優(yōu)化技巧（比如 OopMap）的加持下，它帶來的停頓已經(jīng)是非常短暫且相對固定的了，也就是說，“根節(jié)點枚舉” 階段的停頓時間不會隨著堆容量的增長而增加。

當我們枚舉完了所有的 GC Roots，就得進入第二階段繼續(xù)往下遍歷對象圖了，這一步驟同樣需要 STW，并且停頓時間與 Java 堆容量直接成正比例關系：堆越大，存儲的對象越多，對象圖結(jié)構(gòu)越復雜，要標記更多對象而產(chǎn)生的停頓時間自然就更長，這是理所當然的事情

也就是說，“從根節(jié)點開始遍歷對象圖” 階段的停頓時間隨著堆容量的增長而增加。

要知道包含“標記”階段（也就是可達性分析）是所有追蹤式垃圾收集算法的共同特征，如果這個階段會隨著堆變大而等比例增加停頓時間，其影響就會波及幾乎所有的垃圾收集器。如果能夠減少這部分停頓時間的話，那收益也將會是巨大的

想降低 STW 時間甚至是避免 STW，我們就要先搞清楚為什么必須在一個能保障一致性的快照上才能進行對象圖的遍歷？

需要注意的是，三色標記法只是輔助我們分析的工具，并不是某個垃圾收集器具體使用的算法?。。。?！更不是降低 STW 時間 or 消除 STW 的方法，

具體解決方法下面還會介紹

在這里，三色標記法可以幫助我們搞清楚在可達性分析的第二階段（也就是遍歷對象圖），如果用戶線程和垃圾收集線程同時進行，會出現(xiàn)什么問題

三色標記法的基本概念

所謂三色標記法，就是把遍歷對象圖過程中遇到的對象，按照 “是否訪問過” 這個條件標記成以下三種顏色：

白色：表示對象尚未被垃圾收集器訪問過。顯然在可達性分析剛剛開始的階段，所有的對象都是白色的，若在分析結(jié)束的階段，仍然是白色的對象，即代表不可達（可達性分析到不了的對象，就是死亡對象，需要被回收）
黑色：表示對象已經(jīng)被垃圾收集器訪問過，且這個對象的所有引用都已經(jīng)掃描過。黑色的對象代表已經(jīng)掃描過，它是安全存活的，如果有其他對象引用指向了黑色對象，無須重新掃描一遍。黑色對象不可能直接（不經(jīng)過灰色對象）指向某個白色對象。
灰色：表示對象已經(jīng)被垃圾收集器訪問過，但這個對象上至少存在一個引用還沒有被掃描過

執(zhí)行步驟：

（1）起初所有的對象都是白色的；

（2）從根對象出發(fā)掃描所有可達對象，標記為灰色，放入待處理隊列；

（3）從待處理隊列中取出灰色對象，將其引用的對象標記為灰色并放入待處理隊列中，自身標記為黑色；

（4）重復步驟（3），直到待處理隊列為空，此時白色對象即為不可達的“垃圾”，回收白色對象；

GC回收器演進之路,jvm,開發(fā)語言

根對象在垃圾回收的術語中又叫做根集合，它是垃圾回收器在標記過程時最先檢查的對象，包括：（1）全局變量：程序在編譯期就能確定的那些存在于程序整個生命周期的變量。

（2）執(zhí)行棧：每個 goroutine 都包含自己的執(zhí)行棧，這些執(zhí)行棧上包含棧上的變量及指向分配的堆內(nèi)存區(qū)塊的指針。

（3）寄存器：寄存器的值可能表示一個指針，參與計算的這些指針可能指向某些賦值器分配的堆內(nèi)存區(qū)塊。

灰色可能不好理解，這里舉個例子：A(GC roots) → B → C，如果 B 已經(jīng)被掃描過，但是 B 的引用 C 還沒有被掃描過，那么 B 就是灰色的，C 由于還沒有被掃描，所以是白色的

所以對象圖遍歷的過程，其實就是由灰色從黑向白推進的過程，灰色是黑和白的分界線。

下面我們就用三色標記法來分析下，如果在對象圖遍歷這個階段用戶線程與收集器并發(fā)工作會出現(xiàn)什么問題

產(chǎn)生的問題

問題 1：浮動垃圾

所謂浮動垃圾，就是由于垃圾收集和用戶線程是并行的，這個對象實際已經(jīng)死亡了，已經(jīng)沒有其他人引用它了，但是被垃圾收集器錯誤地標記成了存活對象

舉個例子，a 引用了 b，此時 b 被掃描為可達，但是用戶線程隨后又執(zhí)行了 a.b = null，這個時候其實 b 已經(jīng)是死亡的垃圾對象了，但是由于黑色對象不會被重新掃描，所以在垃圾收集里 b 依然作為存活對象被標記成黑色，因此就成了浮動垃圾。如下圖所示：

GC回收器演進之路,jvm,開發(fā)語言

浮動垃圾當然不是一件好事，但其實是可以容忍的，因為這只不過產(chǎn)生了一點逃過本次收集的浮動垃圾而已，反正還會有下一次垃圾收集，到時候就會被標記為垃圾被清理掉了

問題 2：對象消失

對象消失和浮動垃圾恰恰相反，對象消失是把原本存活的對象錯誤標記為已消亡，這就是非常致命的后果了，程序肯定會因此發(fā)生錯誤，下面表演示了這樣的致命錯誤具體是如何產(chǎn)生的

GC回收器演進之路,jvm,開發(fā)語言

如上圖所示，b -> c 的引用被切斷，但同時用戶線程建立了一個新的從 a -> c 的引用，由于已經(jīng)遍歷到了 b，不可能再回去遍歷 a（黑色對象不會被重新掃描），再遍歷 c，所以這個 c 實際是存活的對象，但由于沒有被垃圾收集器掃描到，被錯誤地標記成了白色。

總結(jié)下對象消失問題的兩個條件：

插入了一條或多條從黑色對象到白色對象的新引用
刪除了全部從灰色對象到該白色對象的直接或間接引用

Wilson 于 1994 年在理論上證明了，當且僅當以上兩個條件同時滿足時，才會產(chǎn)生 “對象消失” 的問題，即原本應該是黑色的對象被誤標為白色

遍歷對象圖不需要 STW 的解決方案

如上所述，如果遍歷對象圖的過程不 STW 的話，第一個浮動垃圾的問題很好處理，但是第二個對象消失問題就很棘手了。

但是呢，遍歷對象圖的過程又實在太長，設計 JVM 的大佬們不得不想出一些辦法來解決對象消失問題，使得在遍歷對象圖的過程中不用進行 STW（也就是用戶線程和對象線程可以同時工作），從而提升可達性分析的效率

上面總結(jié)了對象消失問題的兩個條件，所以說，如果我們想要解決并發(fā)掃描時的對象消失問題，只需破壞這兩個條件的任意一個即可。由此分別產(chǎn)生了兩種解決方案：

增量更新（Incremental Update）：增量更新破壞的是第一個條件，當黑色對象插入新的指向白色對象的引用關系時（就是上圖中的 a -> c 引用關系），就將這個新插入的引用記錄下來，等并發(fā)掃描結(jié)束之后，再將這些記錄過的引用關系中的黑色對象（a）為根，重新掃描一次。這可以簡化理解為，黑色對象一旦新插入了指向白色對象的引用之后，它就變回灰色對象了。
原始快照（Snapshot At The Beginning，SATB）：原始快照要破壞的是第二個條件，當灰色對象要刪除指向白色對象的引用關系時（上圖中的 b -> c 引用關系），就將這個要刪除的引用記錄下來，在并發(fā)掃描結(jié)束之后，再將這些記錄過的引用關系中的灰色對象（b）為根，重新掃描一次。這也可以簡化理解為，無論引用關系刪除與否，都會按照剛剛開始掃描那一刻的對象圖快照來進行搜索。

屏障機制

把回收器視為對象，把賦值器視為影響回收器這一對象的實際行為（即影響 GC 周期的長短），從而引入賦值器的顏色：

黑色賦值器：已經(jīng)由回收器掃描過，不會再次對其進行掃描。
灰色賦值器：尚未被回收器掃描過或盡管已經(jīng)掃描過，但仍需要重新掃描。

我們來看一下golang中屏障機制是什么做的？

插入屏障（Dijkstra）- 灰色賦值器

寫入前，對指針所要指向的對象進行著色

// 灰色賦值器 Dijkstra 插入屏障
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr) //先將新下游對象 ptr 標記為灰色
    *slot = ptr
}

//說明：
添加下游對象(當前下游對象slot, 新下游對象ptr) {   
  //step 1
  標記灰色(新下游對象ptr)   
  
  //step 2
  當前下游對象slot = 新下游對象ptr                    
}

//場景：
A.添加下游對象(nil, B)   //A 之前沒有下游， 新添加一個下游對象B， B被標記為灰色
A.添加下游對象(C, B)     //A 將下游對象C 更換為B，  B被標記為灰色

避免條件1（賦值器修改對象圖，導致某一黑色對象引用白色對象；）因為在對象A 引用對象B 的時候，B 對象被標記為灰色 Dijkstra 插入屏障的好處在于可以立刻開始并發(fā)標記。

但存在兩個缺點：

由于 Dijkstra 插入屏障的“保守”，在一次回收過程中可能會殘留一部分對象沒有回收成功，只有在下一個回收過程中才會被回收；
在標記階段中，每次進行指針賦值操作時，都需要引入寫屏障，這無疑會增加大量性能開銷；為了避免造成性能問題，Go 團隊在最終實現(xiàn)時，沒有為所有棧上的指針寫操作，啟用寫屏障，而是當發(fā)生棧上的寫操作時，將棧標記為灰色，但此舉產(chǎn)生了灰色賦值器，將會需要標記終止階段 STW 時對這些棧進行重新掃描。

GC回收器演進之路,jvm,開發(fā)語言

GC回收器演進之路,jvm,開發(fā)語言 ?

GC回收器演進之路,jvm,開發(fā)語言

特點：在標記開始時無需STW，可直接開始，并發(fā)進行，但結(jié)束時需要STW來重新掃描棧

刪除屏障（Yuasa）- 黑色賦值器?

寫入前，對指針所在對象進行著色

// 黑色賦值器 Yuasa 屏障
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot) 先將*slot標記為灰色
    *slot = ptr
}

//說明：
添加下游對象(當前下游對象slot， 新下游對象ptr) {
  //step 1
  if (當前下游對象slot是灰色 || 當前下游對象slot是白色) {
          標記灰色(當前下游對象slot)     //slot為被刪除對象， 標記為灰色
  }  
  //step 2
  當前下游對象slot = 新下游對象ptr
}

//場景
A.添加下游對象(B, nil)   //A對象，刪除B對象的引用。B被A刪除，被標記為灰(如果B之前為白)
A.添加下游對象(B, C)     //A對象，更換下游B變成C。B被A刪除，被標記為灰(如果B之前為白)

?避免條件2（從灰色對象出發(fā)，到達白色對象的、未經(jīng)訪問過的路徑被賦值器破壞），因為被刪除對象，如果自身是灰色或者白色，則被標記為灰色

GC回收器演進之路,jvm,開發(fā)語言

? GC回收器演進之路,jvm,開發(fā)語言

GC回收器演進之路,jvm,開發(fā)語言

特點：標記結(jié)束不需要STW，但是回收精度低，GC 開始時STW 掃描堆棧記錄初始快照，保護開始時刻的所有存活對象；且容易產(chǎn)生“冗余”掃描；

混合屏障

大大縮短了 STW 時間

GC 開始將棧上的對象全部掃描并標記為黑色；
GC 期間，任何在棧上創(chuàng)建的新對象，均為黑色；
被刪除的堆對象標記為灰色；
被添加的堆對象標記為灰色；

// 混合寫屏障
func HybridWritePointerSimple(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot)
    shade(ptr)
    *slot = ptr
}

場景一：對象被一個堆對象刪除引用，成為棧對象的下游

由于屏障的作用，對象7不會被誤刪除；

GC回收器演進之路,jvm,開發(fā)語言

場景二：對象被一個棧對象刪除引用，成為棧對象的下游?

GC回收器演進之路,jvm,開發(fā)語言

場景三：對象被一個堆對象刪除引用，成為堆對象的下游?

GC回收器演進之路,jvm,開發(fā)語言

場景四：對象被一個棧對象刪除引用，成為另一個堆對象的下游

GC回收器演進之路,jvm,開發(fā)語言 ?

GC回收器演進之路,jvm,開發(fā)語言

?Golang 中的混合屏障結(jié)合了刪除寫屏障和插入寫屏障的優(yōu)點，只需要在開始時并發(fā)掃描各goroutine的棧，使其變黑并一直保持，標記結(jié)束后，因為?？臻g在掃描后始終是黑色的，無需進行re-scan，減少了STW 的時間。

總結(jié)

你需要知道垃圾收集器在追求并行高效回收過程中產(chǎn)生的問題是什么？

????????遍歷對象圖的過程又實在太長，設計 JVM 的大佬們不得不想出一些辦法來解決對象消失問題，使得在遍歷對象圖的過程中不用進行 STW（也就是用戶線程和對象線程可以同時工作），從而提升可達性分析的效率

又是如何解決的？

????????增量更新

????????增量更新破壞的是第一個條件，當黑色對象插入新的指向白色對象的引用關系時，就將這個新插入的引用記錄下來，等并發(fā)掃描后再將這些記錄過的引用關系中的黑色對象為根重新掃描一次，這樣可以簡化理解為黑色對象一旦插入新的指向白色對象它就變?yōu)榛疑珜ο罅?/p>

CMS就是基于增量更新來實現(xiàn)的

????????原始快照
????????原始快照破壞的是第二個條件，當灰色對象要刪除指向白色對象的引用關系時，就要將這個要刪除的引用記錄下來，在并發(fā)掃描結(jié)束之后，再將這些記錄過的引用關系中的灰色對象為根，重新掃描一次，可以簡化理解為無論引用關系刪除與否都會按照剛剛開始那一刻的對象圖快照來進行搜索