# [TOC] ## 5、Golang三色標記+混合寫屏障GC模式全分析 > 本節為**重點**章節 > 本章節含視頻版: [](https://www.bilibili.com/video/BV1wz4y1y7Kd) --- 垃圾回收(Garbage Collection，簡稱GC)是編程語言中提供的自動的內存管理機制，自動釋放不需要的內存對象，讓出存儲器資源。GC過程中無需程序員手動執行。GC機制在現代很多編程語言都支持，GC能力的性能與優劣也是不同語言之間對比度指標之一。 Golang在GC的演進過程中也經歷了很多次變革，Go V1.3之前的標記-清除(mark and sweep)算法，Go V1.3之前的標記-清掃(mark and sweep)的缺點 * Go V1.5的三色并發標記法 * Go V1.5的三色標記為什么需要STW * Go V1.5的三色標記為什么需要屏障機制(“強-弱” 三色不變式、插入屏障、刪除屏障 ) * Go V1.8混合寫屏障機制 * Go V1.8混合寫屏障機制的全場景分析 ### 一、Go V1.3之前的標記-清除(mark and sweep)算法 接下來我們來看一下在Golang1.3之前的時候主要用的普通的標記-清除算法，此算法主要有兩個主要的步驟： - 標記(Mark phase) - 清除(Sweep phase) #### 1 標記清除算法的具體步驟 **第一步**，暫停程序業務邏輯, 分類出可達和不可達的對象，然后做上標記。  圖中表示是程序與對象的可達關系，目前程序的可達對象有對象1-2-3，對象4-7等五個對象。 **第二步**, 開始標記，程序找出它所有可達的對象，并做上標記。如下圖所示：  所以對象1-2-3、對象4-7等五個對象被做上標記。 **第三步**, 標記完了之后，然后開始清除未標記的對象. 結果如下。  操作非常簡單，但是有一點需要額外注意：mark and sweep算法在執行的時候，需要程序暫停！即 `STW(stop the world)`，STW的過程中，CPU不執行用戶代碼，全部用于垃圾回收，這個過程的影響很大，所以STW也是一些回收機制最大的難題和希望優化的點。所以在執行第三步的這段時間，程序會暫定停止任何工作，卡在那等待回收執行完畢。 **第四步**, 停止暫停，讓程序繼續跑。然后循環重復這個過程，直到process程序生命周期結束。 以上便是標記-清除（mark and sweep）回收的算法。 #### 2 標記-清除(mark and sweep)的缺點 標記清除算法明了，過程鮮明干脆，但是也有非常嚴重的問題。 - STW，stop the world；讓程序暫停，程序出現卡頓 **(重要問題)**； - 標記需要掃描整個heap； - 清除數據會產生heap碎片。 Go V1.3版本之前就是以上來實施的, 在執行GC的基本流程就是首先啟動STW暫停，然后執行標記，再執行數據回收，最后停止STW，如圖所示。  從上圖來看，全部的GC時間都是包裹在STW范圍之內的，這樣貌似程序暫停的時間過長，影響程序的運行性能。所以Go V1.3 做了簡單的優化,將STW的步驟提前, 減少STW暫停的時間范圍.如下所示  上圖主要是將STW的步驟提前了異步，因為在Sweep清除的時候，可以不需要STW停止，因為這些對象已經是不可達對象了，不會出現回收寫沖突等問題。 但是無論怎么優化，Go V1.3都面臨這個一個重要問題，就是**mark-and-sweep 算法會暫停整個程序** 。 Go是如何面對并這個問題的呢？接下來G V1.5版本 就用**三色并發標記法**來優化這個問題. ### 三、Go V1.5的三色并發標記法 ?Golang中的垃圾回收主要應用三色標記法，GC過程和其他用戶goroutine可并發運行，但需要一定時間的**STW(stop the world)**，所謂**三色標記法**實際上就是通過三個階段的標記來確定清楚的對象都有哪些？我們來看一下具體的過程。 **第一步** , 每次新創建的對象，默認的顏色都是標記為“白色”，如圖所示。  上圖所示，我們的程序可抵達的內存對象關系如左圖所示，右邊的標記表，是用來記錄目前每個對象的標記顏色分類。這里面需要注意的是，所謂“程序”，則是一些對象的跟節點集合。所以我們如果將“程序”展開，會得到類似如下的表現形式，如圖所示。  **第二步**, 每次GC回收開始, 會從根節點開始遍歷所有對象，把遍歷到的對象從白色集合放入“灰色”集合如圖所示。  這里 要注意的是，本次遍歷是一次遍歷，非遞歸形式，是從程序抽次可抵達的對象遍歷一層，如上圖所示，當前可抵達的對象是對象1和對象4，那么自然本輪遍歷結束，對象1和對象4就會被標記為灰色，灰色標記表就會多出這兩個對象。 **第三步**, 遍歷灰色集合，將灰色對象引用的對象從白色集合放入灰色集合，之后將此灰色對象放入黑色集合，如圖所示。  這一次遍歷是只掃描灰色對象，將灰色對象的第一層遍歷可抵達的對象由白色變為灰色，如：對象2、對象7. 而之前的灰色對象1和對象4則會被標記為黑色，同時由灰色標記表移動到黑色標記表中。 **第四步**, 重復**第三步**, 直到灰色中無任何對象，如圖所示。   當我們全部的可達對象都遍歷完后，灰色標記表將不再存在灰色對象，目前全部內存的數據只有兩種顏色，黑色和白色。那么黑色對象就是我們程序邏輯可達（需要的）對象，這些數據是目前支撐程序正常業務運行的，是合法的有用數據，不可刪除，白色的對象是全部不可達對象，目前程序邏輯并不依賴他們，那么白色對象就是內存中目前的垃圾數據，需要被清除。 **第五步**: 回收所有的白色標記表的對象. 也就是回收垃圾，如圖所示。  以上我們將全部的白色對象進行刪除回收，剩下的就是全部依賴的黑色對象。 以上便是`三色并發標記法`，不難看出，我們上面已經清楚的體現`三色`的特性。但是這里面可能會有很多并發流程均會被掃描，執行并發流程的內存可能相互依賴，為了在GC過程中保證數據的安全，我們在開始三色標記之前就會加上STW，在掃描確定黑白對象之后再放開STW。但是很明顯這樣的GC掃描的性能實在是太低了。 那么Go是如何解決標記-清除(mark and sweep)算法中的卡頓(stw，stop the world)問題的呢？ ### 四、沒有STW的三色標記法 先拋磚引玉，我們加入如果沒有STW，那么也就不會再存在性能上的問題，那么接下來我們假設如果三色標記法不加入STW會發生什么事情？ 我們還是基于上述的三色并發標記法來說, 他是一定要依賴STW的. 因為如果不暫停程序, 程序的邏輯改變對象引用關系, 這種動作如果在標記階段做了修改，會影響標記結果的正確性，我們來看看一個場景，如果三色標記法, 標記過程不使用STW將會發生什么事情? 我們把初始狀態設置為已經經歷了第一輪掃描，目前黑色的有對象1和對象4， 灰色的有對象2和對象7，其他的為白色對象，且對象2是通過指針p指向對象3的，如圖所示。  現在如何三色標記過程不啟動STW，那么在GC掃描過程中，任意的對象均可能發生讀寫操作，如圖所示，在還沒有掃描到對象2的時候，已經標記為黑色的對象4，此時創建指針q，并且指向白色的對象3。  與此同時灰色的對象2將指針p移除，那么白色的對象3實則就是被掛在了已經掃描完成的黑色的對象4下，如圖所示。  然后我們正常指向三色標記的算法邏輯，將所有灰色的對象標記為黑色，那么對象2和對象7就被標記成了黑色，如圖所示。  那么就執行了三色標記的最后一步，將所有白色對象當做垃圾進行回收，如圖所示。  但是最后我們才發現，本來是對象4合法引用的對象3，卻被GC給“誤殺”回收掉了。 可以看出，有兩種情況，在三色標記法中，是不希望被發生的。 * 條件1: 一個白色對象被黑色對象引用**(白色被掛在黑色下)** * 條件2: 灰色對象與它之間的可達關系的白色對象遭到破壞**(灰色同時丟了該白色)** 如果當以上兩個條件同時滿足時，就會出現對象丟失現象! 并且，如圖所示的場景中，如果示例中的白色對象3還有很多下游對象的話, 也會一并都清理掉。 為了防止這種現象的發生，最簡單的方式就是STW，直接禁止掉其他用戶程序對對象引用關系的干擾，但是**STW的過程有明顯的資源浪費，對所有的用戶程序都有很大影響**。那么是否可以在保證對象不丟失的情況下合理的盡可能的提高GC效率，減少STW時間呢？答案是可以的，我們只要使用一種機制，嘗試去破壞上面的兩個必要條件就可以了。 ### 五、屏障機制 我們讓GC回收器，滿足下面兩種情況之一時，即可保對象不丟失。 這兩種方式就是“強三色不變式”和“ 式”。 #### (1) “強-弱” 三色不變式 * 強三色不變式 不存在黑色對象引用到白色對象的指針。  弱三色不變色實際上是強制性的不允許黑色對象引用白色對象，這樣就不會出現有白色對象被誤刪的情況。 * 弱三色不變式 所有被黑色對象引用的白色對象都處于灰色保護狀態。  弱三色不變式強調，黑色對象可以引用白色對象，但是這個白色對象必須存在其他灰色對象對它的引用，或者可達它的鏈路上游存在灰色對象。 這樣實則是黑色對象引用白色對象，白色對象處于一個危險被刪除的狀態，但是上游灰色對象的引用，可以保護該白色對象，使其安全。 為了遵循上述的兩個方式，GC算法演進到兩種屏障方式，他們“插入屏障”, “刪除屏障”。 #### (2) 插入屏障 `具體操作`: 在A對象引用B對象的時候，B對象被標記為灰色。(將B掛在A下游，B必須被標記為灰色) `滿足`: **強三色不變式**. (不存在黑色對象引用白色對象的情況了， 因為白色會強制變成灰色) 偽碼如下: ```go 添加下游對象(當前下游對象slot, 新下游對象ptr) { //1 標記灰色(新下游對象ptr) //2 當前下游對象slot = 新下游對象ptr } ``` 場景： ```go A.添加下游對象(nil, B) //A 之前沒有下游， 新添加一個下游對象B， B被標記為灰色 A.添加下游對象(C, B) //A 將下游對象C 更換為B， B被標記為灰色 ``` ? 這段偽碼邏輯就是寫屏障,. 我們知道,黑色對象的內存槽有兩種位置, `棧`和`堆`. 棧空間的特點是容量小,但是要求相應速度快,因為函數調用彈出頻繁使用, 所以“插入屏障”機制,在**棧空間的對象操作中不使用**. 而僅僅使用在堆空間對象的操作中. ? 接下來，我們用幾張圖，來模擬整個一個詳細的過程， 希望您能夠更可觀的看清晰整體流程。 ---  ---  ---  ---  ---  ---  ? 但是如果棧不添加,當全部三色標記掃描之后,棧上有可能依然存在白色對象被引用的情況(如上圖的對象9). 所以要對棧重新進行三色標記掃描, 但這次為了對象不丟失, 要對本次標記掃描啟動STW暫停. 直到棧空間的三色標記結束. ---  ---  ---  --- ? 最后將棧和堆空間 掃描剩余的全部 白色節點清除. 這次STW大約的時間在10~100ms間.  --- #### (3) 刪除屏障 `具體操作`: 被刪除的對象，如果自身為灰色或者白色，那么被標記為灰色。 `滿足`: **弱三色不變式**. (保護灰色對象到白色對象的路徑不會斷) 偽代碼： ```go 添加下游對象(當前下游對象slot， 新下游對象ptr) { //1 if (當前下游對象slot是灰色 || 當前下游對象slot是白色) { 標記灰色(當前下游對象slot) //slot為被刪除對象， 標記為灰色 } //2 當前下游對象slot = 新下游對象ptr } ``` 場景： ```go A.添加下游對象(B, nil) //A對象，刪除B對象的引用。 B被A刪除，被標記為灰(如果B之前為白) A.添加下游對象(B, C) //A對象，更換下游B變成C。 B被A刪除，被標記為灰(如果B之前為白) ``` 接下來，我們用幾張圖，來模擬整個一個詳細的過程， 希望您能夠更可觀的看清晰整體流程。        這種方式的回收精度低，一個對象即使被刪除了最后一個指向它的指針也依舊可以活過這一輪，在下一輪GC中被清理掉。 ### 六、Go V1.8的混合寫屏障(hybrid write barrier)機制 插入寫屏障和刪除寫屏障的短板： * 插入寫屏障：結束時需要STW來重新掃描棧，標記棧上引用的白色對象的存活； * 刪除寫屏障：回收精度低，GC開始時STW掃描堆棧來記錄初始快照，這個過程會保護開始時刻的所有存活對象。 Go V1.8版本引入了混合寫屏障機制（hybrid write barrier），避免了對棧re-scan的過程，極大的減少了STW的時間。結合了兩者的優點。 --- #### (1) 混合寫屏障規則 `具體操作`: 1、GC開始將棧上的對象全部掃描并標記為黑色(之后不再進行第二次重復掃描，無需STW)， 2、GC期間，任何在棧上創建的新對象，均為黑色。 3、被刪除的對象標記為灰色。 4、被添加的對象標記為灰色。 `滿足`: 變形的**弱三色不變式**. 偽代碼： ```go 添加下游對象(當前下游對象slot, 新下游對象ptr) { //1 標記灰色(當前下游對象slot) //只要當前下游對象被移走，就標記灰色 //2 標記灰色(新下游對象ptr) //3 當前下游對象slot = 新下游對象ptr } ``` > 這里我們注意， 屏障技術是不在棧上應用的，因為要保證棧的運行效率。 #### (2) 混合寫屏障的具體場景分析 接下來，我們用幾張圖，來模擬整個一個詳細的過程， 希望您能夠更可觀的看清晰整體流程。 > 注意混合寫屏障是Gc的一種屏障機制，所以只是當程序執行GC的時候，才會觸發這種機制。 ##### GC開始：掃描棧區，將可達對象全部標記為黑   --- ##### 場景一： 對象被一個堆對象刪除引用，成為棧對象的下游 > 偽代碼 ```go //前提：堆對象4->對象7 = 對象7； //對象7 被 對象4引用 棧對象1->對象7 = 堆對象7； //將堆對象7 掛在 棧對象1 下游 堆對象4->對象7 = null； //對象4 刪除引用 對象7 ```   ##### 場景二： 對象被一個棧對象刪除引用，成為另一個棧對象的下游 > 偽代碼 ```go new 棧對象9； 對象8->對象3 = 對象3； //將棧對象3 掛在 棧對象9 下游 對象2->對象3 = null； //對象2 刪除引用 對象3 ```    ##### 場景三：對象被一個堆對象刪除引用，成為另一個堆對象的下游 > 偽代碼 ```go 堆對象10->對象7 = 堆對象7； //將堆對象7 掛在 堆對象10 下游 堆對象4->對象7 = null； //對象4 刪除引用 對象7 ```    ##### 場景四：對象從一個棧對象刪除引用，成為另一個堆對象的下游 > 偽代碼 ```go 堆對象10->對象7 = 堆對象7； //將堆對象7 掛在 堆對象10 下游 堆對象4->對象7 = null； //對象4 刪除引用 對象7 ```    ? Golang中的混合寫屏障滿足`弱三色不變式`，結合了刪除寫屏障和插入寫屏障的優點，只需要在開始時并發掃描各個goroutine的棧，使其變黑并一直保持，這個過程不需要STW，而標記結束后，因為棧在掃描后始終是黑色的，也無需再進行re-scan操作了，減少了STW的時間。 #### 七、總結 ? 以上便是Golang的GC全部的標記-清除邏輯及場景演示全過程。 GoV1.3- 普通標記清除法，整體過程需要啟動STW，效率極低。 GoV1.5- 三色標記法， 堆空間啟動寫屏障，棧空間不啟動，全部掃描之后，需要重新掃描一次棧(需要STW)，效率普通 GoV1.8-三色標記法，混合寫屏障機制， 棧空間不啟動，堆空間啟動。整個過程幾乎不需要STW，效率較高。