原創(chuàng)聲明
作者:劉丹冰Aceld
垃圾回收(Garbage Collection，簡稱GC)是編程語言中提供的自動的內(nèi)存管理機制锡凝，自動釋放不需要的對象粘昨，讓出存儲器資源，無需程序員手動執(zhí)行窜锯。
? Golang中的垃圾回收主要應(yīng)用三色標(biāo)記法张肾，GC過程和其他用戶goroutine可并發(fā)運行，但需要一定時間的STW(stop the world)锚扎，STW的過程中吞瞪，CPU不執(zhí)行用戶代碼，全部用于垃圾回收驾孔，這個過程的影響很大芍秆，Golang進行了多次的迭代優(yōu)化來解決這個問題。
〇翠勉、內(nèi)容提綱
本文將系統(tǒng)的詳細介紹Golang中GC的全分析過程妖啥，包括垃圾回收的方式遞進。
內(nèi)容包括：
- G0 V1.3之前的標(biāo)記-清除(mark and sweep)算法
- Go V1.3之前的標(biāo)記-清掃(mark and sweep)的缺點
- Go V1.5的三色并發(fā)標(biāo)記法
- Go V1.5的三色標(biāo)記為什么需要STW
- Go V1.5的三色標(biāo)記為什么需要屏障機制(“強-弱” 三色不變式眉菱、插入屏障迹栓、刪除屏障 )
- Go V1.8混合寫屏障機制
- Go V1.8混合寫屏障機制的全場景分析
文章約近50張圖文解析、4000+文字俭缓、推薦分階段學(xué)習(xí)及消化
一克伊、Go V1.3之前的標(biāo)記-清除(mark and sweep)算法
此算法主要有兩個主要的步驟：
- 標(biāo)記(Mark phase)
- 清除(Sweep phase)
第一步，暫停程序業(yè)務(wù)邏輯, 找出不可達的對象华坦，然后做上標(biāo)記愿吹。第二步，回收標(biāo)記好的對象惜姐。
操作非常簡單犁跪，但是有一點需要額外注意：mark and sweep算法在執(zhí)行的時候椿息，需要程序暫停！即 STW(stop the world)坷衍。也就是說寝优，這段時間程序會卡在哪兒。
第二步, 開始標(biāo)記枫耳，程序找出它所有可達的對象乏矾，并做上標(biāo)記。如下圖所示：
第三步, 標(biāo)記完了之后迁杨，然后開始清除未標(biāo)記的對象. 結(jié)果如下.
第四步, 停止暫停钻心，讓程序繼續(xù)跑。然后循環(huán)重復(fù)這個過程铅协，直到process程序生命周期結(jié)束捷沸。
二、標(biāo)記-清掃(mark and sweep)的缺點
- STW狐史，stop the world痒给；讓程序暫停，程序出現(xiàn)卡頓 (重要問題)预皇。
- 標(biāo)記需要掃描整個heap
- 清除數(shù)據(jù)會產(chǎn)生heap碎片
所以Go V1.3版本之前就是以上來實施的, 流程是
Go V1.3 做了簡單的優(yōu)化,將STW提前, 減少STW暫停的時間范圍.如下所示
這里面最重要的問題就是：mark-and-sweep 算法會暫停整個程序 侈玄。
Go是如何面對并這個問題的呢？接下來G V1.5版本 就用三色并發(fā)標(biāo)記法來優(yōu)化這個問題.
三吟温、Go V1.5的三色并發(fā)標(biāo)記法
三色標(biāo)記法 實際上就是通過三個階段的標(biāo)記來確定清楚的對象都有哪些. 我們來看一下具體的過程.
第一步 , 就是只要是新創(chuàng)建的對象,默認的顏色都是標(biāo)記為“白色”.
這里面需要注意的是, 所謂“程序”, 則是一些對象的跟節(jié)點集合.
所以上圖,可以轉(zhuǎn)換如下的方式來表示.
第二步, 每次GC回收開始, 然后從根節(jié)點開始遍歷所有對象序仙，把遍歷到的對象從白色集合放入“灰色”集合。
第三步, 遍歷灰色集合鲁豪，將灰色對象引用的對象從白色集合放入灰色集合潘悼，之后將此灰色對象放入黑色集合
第四步, 重復(fù)第三步, 直到灰色中無任何對象.
第五步: 回收所有的白色標(biāo)記表的對象. 也就是回收垃圾.
以上便是三色并發(fā)標(biāo)記法, 不難看出,我們上面已經(jīng)清楚的體現(xiàn)三色的特性, 那么又是如何實現(xiàn)并行的呢?
Go是如何解決標(biāo)記-清除(mark and sweep)算法中的卡頓(stw，stop the world)問題的呢爬橡？
四治唤、沒有STW的三色標(biāo)記法
? 我們還是基于上述的三色并發(fā)標(biāo)記法來說, 他是一定要依賴STW的. 因為如果不暫停程序, 程序的邏輯改變對象引用關(guān)系, 這種動作如果在標(biāo)記階段做了修改，會影響標(biāo)記結(jié)果的正確性糙申。我們舉一個場景.
如果三色標(biāo)記法, 標(biāo)記過程不使用STW將會發(fā)生什么事情?
可以看出宾添，有兩個問題, 在三色標(biāo)記法中,是不希望被發(fā)生的
- 條件1: 一個白色對象被黑色對象引用(白色被掛在黑色下)
- 條件2: 灰色對象與它之間的可達關(guān)系的白色對象遭到破壞(灰色同時丟了該白色)
當(dāng)以上兩個條件同時滿足時, 就會出現(xiàn)對象丟失現(xiàn)象!
?
? 當(dāng)然, 如果上述中的白色對象3, 如果他還有很多下游對象的話, 也會一并都清理掉.
? 為了防止這種現(xiàn)象的發(fā)生，最簡單的方式就是STW柜裸，直接禁止掉其他用戶程序?qū)ο笠藐P(guān)系的干擾缕陕，但是STW的過程有明顯的資源浪費，對所有的用戶程序都有很大影響疙挺，如何能在保證對象不丟失的情況下合理的盡可能的提高GC效率扛邑，減少STW時間呢？
? 答案就是, 那么我們只要使用一個機制,來破壞上面的兩個條件就可以了.
五铐然、屏障機制
? 我們讓GC回收器,滿足下面兩種情況之一時,可保對象不丟失. 所以引出兩種方式.
(1) “強-弱” 三色不變式
- 強三色不變式
不存在黑色對象引用到白色對象的指針蔬崩。
- 弱三色不變式
所有被黑色對象引用的白色對象都處于灰色保護狀態(tài).
為了遵循上述的兩個方式,Golang團隊初步得到了如下具體的兩種屏障方式“插入屏障”, “刪除屏障”.
(2) 插入屏障
具體操作: 在A對象引用B對象的時候恶座，B對象被標(biāo)記為灰色。(將B掛在A下游沥阳，B必須被標(biāo)記為灰色)
滿足: 強三色不變式. (不存在黑色對象引用白色對象的情況了跨琳， 因為白色會強制變成灰色)
偽碼如下:
添加下游對象(當(dāng)前下游對象slot, 新下游對象ptr) {
//1
標(biāo)記灰色(新下游對象ptr)
//2
當(dāng)前下游對象slot = 新下游對象ptr
}
場景：
A.添加下游對象(nil, B) //A 之前沒有下游， 新添加一個下游對象B桐罕， B被標(biāo)記為灰色
A.添加下游對象(C, B) //A 將下游對象C 更換為B湾宙， B被標(biāo)記為灰色
? 這段偽碼邏輯就是寫屏障,. 我們知道,黑色對象的內(nèi)存槽有兩種位置, 棧和堆. 棧空間的特點是容量小,但是要求相應(yīng)速度快,因為函數(shù)調(diào)用彈出頻繁使用, 所以“插入屏障”機制,在椄园恚空間的對象操作中不使用. 而僅僅使用在堆空間對象的操作中.
? 接下來，我們用幾張圖埠啃，來模擬整個一個詳細的過程死宣， 希望您能夠更可觀的看清晰整體流程。
? 但是如果棧不添加,當(dāng)全部三色標(biāo)記掃描之后,棧上有可能依然存在白色對象被引用的情況(如上圖的對象9). 所以要對棧重新進行三色標(biāo)記掃描, 但這次為了對象不丟失, 要對本次標(biāo)記掃描啟動STW暫停. 直到棽昕空間的三色標(biāo)記結(jié)束.
最后將棧和堆空間 掃描剩余的全部 白色節(jié)點清除. 這次STW大約的時間在10~100ms間.
(3) 刪除屏障
具體操作: 被刪除的對象毅该，如果自身為灰色或者白色，那么被標(biāo)記為灰色潦牛。
滿足: 弱三色不變式. (保護灰色對象到白色對象的路徑不會斷)
偽代碼：
添加下游對象(當(dāng)前下游對象slot眶掌， 新下游對象ptr) {
//1
if (當(dāng)前下游對象slot是灰色 || 當(dāng)前下游對象slot是白色) {
標(biāo)記灰色(當(dāng)前下游對象slot) //slot為被刪除對象， 標(biāo)記為灰色
}
//2
當(dāng)前下游對象slot = 新下游對象ptr
}
場景：
A.添加下游對象(B, nil) //A對象巴碗，刪除B對象的引用朴爬。 B被A刪除，被標(biāo)記為灰(如果B之前為白)
A.添加下游對象(B, C) //A對象橡淆，更換下游B變成C召噩。 B被A刪除，被標(biāo)記為灰(如果B之前為白)
接下來逸爵，我們用幾張圖具滴，來模擬整個一個詳細的過程， 希望您能夠更可觀的看清晰整體流程师倔。
這種方式的回收精度低构韵，一個對象即使被刪除了最后一個指向它的指針也依舊可以活過這一輪，在下一輪GC中被清理掉趋艘。
六疲恢、Go V1.8的混合寫屏障(hybrid write barrier)機制
插入寫屏障和刪除寫屏障的短板：
插入寫屏障：結(jié)束時需要STW來重新掃描棧，標(biāo)記棧上引用的白色對象的存活致稀；
刪除寫屏障：回收精度低冈闭，GC開始時STW掃描堆棧來記錄初始快照，這個過程會保護開始時刻的所有存活對象抖单。
Go V1.8版本引入了混合寫屏障機制（hybrid write barrier）萎攒，避免了對棧re-scan的過程遇八，極大的減少了STW的時間。結(jié)合了兩者的優(yōu)點耍休。
(1) 混合寫屏障規(guī)則
具體操作:
1刃永、GC開始將棧上的對象全部掃描并標(biāo)記為黑色(之后不再進行第二次重復(fù)掃描，無需STW)羊精，
2斯够、GC期間，任何在棧上創(chuàng)建的新對象喧锦，均為黑色读规。
3、被刪除的對象標(biāo)記為灰色燃少。
4束亏、被添加的對象標(biāo)記為灰色。
滿足: 變形的弱三色不變式.
偽代碼：
添加下游對象(當(dāng)前下游對象slot, 新下游對象ptr) {
//1
標(biāo)記灰色(當(dāng)前下游對象slot) //只要當(dāng)前下游對象被移走阵具，就標(biāo)記灰色
//2
標(biāo)記灰色(新下游對象ptr)
//3
當(dāng)前下游對象slot = 新下游對象ptr
}
這里我們注意碍遍， 屏障技術(shù)是不在棧上應(yīng)用的，因為要保證棧的運行效率阳液。
(2) 混合寫屏障的具體場景分析
接下來怕敬，我們用幾張圖，來模擬整個一個詳細的過程帘皿， 希望您能夠更可觀的看清晰整體流程东跪。
注意混合寫屏障是Gc的一種屏障機制，所以只是當(dāng)程序執(zhí)行GC的時候鹰溜，才會觸發(fā)這種機制越庇。
GC開始：掃描棧區(qū)，將可達對象全部標(biāo)記為黑
場景一： 對象被一個堆對象刪除引用奉狈，成為棧對象的下游
偽代碼
//前提：堆對象4->對象7 = 對象7卤唉； //對象7 被 對象4引用
棧對象1->對象7 = 堆對象7； //將堆對象7 掛在 棧對象1 下游
堆對象4->對象7 = null仁期； //對象4 刪除引用 對象7
場景二： 對象被一個棧對象刪除引用桑驱，成為另一個棧對象的下游
偽代碼
new 棧對象9；
對象8->對象3 = 對象3跛蛋； //將棧對象3 掛在 棧對象9 下游
對象2->對象3 = null熬的； //對象2 刪除引用 對象3
場景三：對象被一個堆對象刪除引用，成為另一個堆對象的下游
偽代碼
堆對象10->對象7 = 堆對象7赊级； //將堆對象7 掛在 堆對象10 下游
堆對象4->對象7 = null押框； //對象4 刪除引用 對象7
場景四：對象從一個棧對象刪除引用，成為另一個堆對象的下游
偽代碼
堆對象10->對象7 = 堆對象7理逊； //將堆對象7 掛在 堆對象10 下游
堆對象4->對象7 = null橡伞； //對象4 刪除引用 對象7
? Golang中的混合寫屏障滿足弱三色不變式盒揉，結(jié)合了刪除寫屏障和插入寫屏障的優(yōu)點，只需要在開始時并發(fā)掃描各個goroutine的棧兑徘，使其變黑并一直保持刚盈，這個過程不需要STW，而標(biāo)記結(jié)束后挂脑，因為棧在掃描后始終是黑色的藕漱，也無需再進行re-scan操作了，減少了STW的時間崭闲。
七肋联、總結(jié)
? 以上便是Golang的GC全部的標(biāo)記-清除邏輯及場景演示全過程。
GoV1.3- 普通標(biāo)記清除法刁俭，整體過程需要啟動STW牺蹄，效率極低。
GoV1.5- 三色標(biāo)記法薄翅， 堆空間啟動寫屏障，椕ツ危空間不啟動翘魄，全部掃描之后，需要重新掃描一次棧(需要STW)舀奶，效率普通
GoV1.8-三色標(biāo)記法暑竟，混合寫屏障機制， 椨祝空間不啟動但荤，堆空間啟動。整個過程幾乎不需要STW涧至，效率較高腹躁。
參考文獻:
https://www.cnblogs.com/wangyiyang/p/12191591.html
http://www.reibang.com/p/eb6b3aff9ca5
https://zhuanlan.zhihu.com/p/74853110
關(guān)于作者：
劉丹冰Aceld
mail: danbing.at@gmail.com
github: https://github.com/aceld
原創(chuàng)書籍: https://www.kancloud.cn/@aceld
文章推薦
開源軟件作品
(原創(chuàng)開源)Zinx-基于Golang輕量級服務(wù)器并發(fā)框架-完整版(附教程視頻)
(原創(chuàng)開源)Lars-基于C++負載均衡遠程調(diào)度系統(tǒng)-完整版
精選文章
典藏版-Golang調(diào)度器GMP原理與調(diào)度全分析
最常用的調(diào)試 golang 的 bug 以及性能問題的實踐方法？
