Go 垃圾回收原理
目錄
內(nèi)存管理
標(biāo)記清除法——Go1.3
三色標(biāo)記法——Go1.5
三色+混合寫屏障——Go1.8
GC 觸發(fā)的時機(jī)
01 內(nèi)存管理
1）程序里面的垃圾是怎么產(chǎn)生的
程序在內(nèi)存上被分為棧區(qū)、堆區(qū)、數(shù)據(jù)區(qū)、全局?jǐn)?shù)據(jù)區(qū)、代碼段五個部分。
對于 C++ 等底層的編程語言，棧上的內(nèi)存空間由編譯器統(tǒng)一管理，而堆上的內(nèi)存空間需要程序員來手動管理進(jìn)行分配和回收。
在 Go 語言中，棧上的內(nèi)存空間也是由編譯器來統(tǒng)一管理，而堆上的內(nèi)存空間由編譯器和垃圾收集器共同管理進(jìn)行分配和回收，這給我們程序員帶來了極大的便利性。
垃圾其實就是程序向堆棧申請的內(nèi)存空間，隨著程序運(yùn)行已經(jīng)不再使用了。而這些無用的堆棧對象占用了機(jī)器大量的內(nèi)存空間，如果不把它們都回收，那么機(jī)器的內(nèi)存就會越來越小，最終無法提供正常的服務(wù)，這就是內(nèi)存泄漏。
2）內(nèi)存管理
而內(nèi)存的管理，就是管理可用內(nèi)存空間的方式。想要對內(nèi)存空間進(jìn)行合理化使用，一些好的垃圾回收（Garbage Collection，以下統(tǒng)一簡稱 GC）算法是必不可少的。接下來，我們看一下 Go 語言的 GC 是怎么實現(xiàn)的。
02 標(biāo)記清除法
Go 1.3 GC 用的是標(biāo)記清除法，每次 GC 時線程暫停會延遲幾百 ms。
原始的標(biāo)記清除分兩步：
標(biāo)記，先 STW（Stop The World），暫停整個程序的全部運(yùn)行線程，將被引用的對象全部打上標(biāo)記；
清除未打標(biāo)的對象，即回收內(nèi)存資源，然后恢復(fù)運(yùn)行線程。
這樣做有個很大的問題就是，要通過 STW 來保證 GC 期間標(biāo)記對象的狀態(tài)不能發(fā)生變化，整個程序都要暫停幾百 ms，在外部看來程序就會卡頓。
03 三色標(biāo)記法
Go 1.5 GC 用的是三色標(biāo)記法，這種算法實現(xiàn)了并發(fā)清除垃圾，STW 延遲縮短到了10ms 以下。
1）對象顏色分類
三色標(biāo)記法將程序中的對象分為以下三類：
白色對象，表示暫無對象引用的潛在垃圾，其內(nèi)存可能會被垃圾回收器回收；
灰色對象，表示活躍對象，白色到黑色的中間狀態(tài)，因為存在指向白色對象的外部指針，垃圾收集器會掃描這些對象的子對象；
黑色對象，也表示活躍對象，包括不存在引用外部指針的對象和從 root 區(qū)域出發(fā)掃描到的對象。
root 區(qū)域主要是程序運(yùn)行到當(dāng)前時刻的棧和全局?jǐn)?shù)據(jù)區(qū)域。
2）三色標(biāo)記流程
標(biāo)記過程如下：
初始狀態(tài)所有對象為白色；
從 root 根出發(fā)掃描所有對象，將它們引用的對象標(biāo)記為灰色；
分析灰色對象是否引用了其它對象：
如果沒有，則將該灰色對象標(biāo)記為黑色；
如果有引用，則將該灰色變?yōu)楹谏耐瑫r，將它引用的對象變?yōu)榛疑?/p>
重復(fù)步驟3，直到所有灰色對象集合為空時，標(biāo)記階段結(jié)束。此時，對所有白色對象進(jìn)行回收。
結(jié)合如下動圖理解：
可以看出：A、F 為 root 根直接引用的對象，E、G、H 對象為垃圾，需要回收。
3）錯誤回收與三色不變式
由于用戶程序可能在執(zhí)行標(biāo)記的過程中修改對象的指針，所以三色標(biāo)記法可能會出現(xiàn)錯誤回收的情況，例如：
三色標(biāo)記執(zhí)行時產(chǎn)生如下情況：
根集合上的節(jié)點 A 已經(jīng)變成了黑色，它指向的對象 B 變?yōu)榱嘶疑?/p>
A 對象新增指針，指向了對象 D；
持續(xù)掃描所有灰色對象，將其指向?qū)ο笞優(yōu)榛疑?，自身變?yōu)楹谏?，直到灰色集合里沒有對象。
我們發(fā)現(xiàn)，在這個過程中，D 對象一直是白色的，所以掃描結(jié)束后，它會被垃圾收集器錯誤地回收，影響了內(nèi)存的安全性。
因此，想要在標(biāo)記過程中保證安全性，我們需要達(dá)成以下兩種三色不變式（Tri-color invariant）中的任意一種：
強(qiáng)三色不變式：黑色對象不能指向白色對象，只能指向灰色或黑色對象；
弱三色不變式：黑色對象指向的白色對象，必須包含一條從灰色對象經(jīng)由多個白色對象的可達(dá)路徑。
如圖所示：
當(dāng)三色標(biāo)記算法遵循以上兩個不變式中的一種，就能保證垃圾回收時內(nèi)存的安全性。而為了實現(xiàn)這兩種不變式，引入內(nèi)存屏障技術(shù)。
4）屏障技術(shù)
屏障技術(shù)是在用戶程序讀取、創(chuàng)建以及更新對象指針時執(zhí)行的一段代碼，簡單來說，內(nèi)存屏障是一種能夠保證內(nèi)存操作順序的技術(shù)。根據(jù)操作類型的不同，屏障技術(shù)分為讀屏障和寫屏障兩種。
由于讀屏障需要在讀操作時加入代碼片段，對用戶程序的影響較大。因此，Go 語言采用寫屏障來保證三色不變式，寫屏障技術(shù)包括 Dijkstra 在 1978 年提出插入寫屏障和 Yuasa 在 1990 年提出刪除寫屏障兩種。
5）插入寫屏障
插入寫屏障的原理是：當(dāng)有黑色對象 A 指向新對象 D 時，如果被指向?qū)ο?D 為白色，則將 D 對象設(shè)置為灰色，它實現(xiàn)了強(qiáng)三色不變式。
如上圖的標(biāo)記過程：
垃圾收集器將根集合上的 A 對象標(biāo)記為黑色，并將 A 對象指向的 B 對象標(biāo)記成灰色；
用戶程序修改 A 對象的指針，將原本指向 B 對象的指針指向 C 對象，這時，觸發(fā)插入寫屏障將 C 對象標(biāo)記為灰色；
垃圾收集器依次遍歷其它灰色對象，標(biāo)記為黑色。
插入寫屏障將被添加引用的白色對象都標(biāo)記為了灰色，這種方法實現(xiàn)簡單，但也有明顯的缺點：
缺點一：未存活的對象可能需要兩次回收，假設(shè)上述第 2 步到第 3 步之間，A 對象的指針又從指向 C 改為指向 B，那 C 對象就是垃圾，應(yīng)該回收。但是此時灰色的對象 C 會被垃圾收集器認(rèn)為是存活的，這些被錯誤標(biāo)記的對象只有在下一個循環(huán)才會被回收；
缺點二：寫屏障只會對堆上的內(nèi)存對象啟動寫屏障（插入和刪除寫屏障共有的）。而棧上的對象需要保證內(nèi)存安全時，必須在標(biāo)記階段重新對棧上的對象進(jìn)行 STW 掃描。重新掃描時需要暫停程序，影響整體性能。
6）刪除寫屏障
刪除寫屏障的原理是：對象 A 被引用時，如果引用它的對象被刪除了，那么白色的 A 對象將被標(biāo)記為灰色，它實現(xiàn)了弱三色不變式。
如上圖的標(biāo)記過程：
垃圾收集器將根集合上的 A 對象標(biāo)記為黑色，并將 A 對象指向的 B 對象標(biāo)記成灰色；
用戶程序?qū)?A 指向 B 對象的指針，修改為指向 C 對象。這時，觸發(fā)刪除寫屏障，但因為 B 對象不為白色，所以不做改變；
用戶程序?qū)?B 指向 C 對象的指針刪除，觸發(fā)刪除寫屏障，此時，白色的 C 對象被標(biāo)記為灰色；
垃圾收集器依次遍歷程序中的灰色對象，將它們標(biāo)記為黑色。
刪除寫屏障將被刪除引用的白色對象都標(biāo)記為了灰色，但是它也有缺點和局限性：
缺點一：回收精度低，當(dāng)對象 B 已經(jīng)被刪除時，它仍然可以活過這一輪在下一個循環(huán)才被回收；
缺點二：同插入寫屏障，重新 STW 掃描棧對象。
04 三色+混合寫屏障
基于插入寫屏障和刪除寫屏障在結(jié)束時需要 STW 來重新掃描棧上的內(nèi)存對象，考慮其帶來的性能影響，Go 1.8 GC 組合了插入寫屏障和刪除寫屏障構(gòu)成了混合寫屏障以及原本的三色標(biāo)記法，將垃圾收集的時間縮短到 0.5ms 以下，整個流程分為以下四步：
GC 開始時，將棧上所有的可達(dá)對象全部標(biāo)記為黑色（不需要二次掃描，無需 STW）；
GC 期間，任何棧上創(chuàng)建的新對象都標(biāo)記為黑色；
將被刪除引用的對象標(biāo)記為灰色；
將被添加引用的對象標(biāo)記為灰色。
05 GC 觸發(fā)的時機(jī)
觸發(fā) GC 有兩個條件：
Go 語言運(yùn)行時的默認(rèn)配置會在堆內(nèi)存達(dá)到上一次垃圾收集的 2 倍時，觸發(fā)新一輪的垃圾回收，這個行為可以通過 GOGC 變量調(diào)整。它的默認(rèn)值為 100，即增長 100% 的堆內(nèi)存才會觸發(fā) GC；
如果一定時間內(nèi)沒有通過方式 1 觸發(fā)，也會觸發(fā)新的循環(huán)，這個定時時長由 runtime.forcegcperiod 變量控制，默認(rèn)為 2 分鐘。
06 參考文獻(xiàn)
《Go語言設(shè)計與實現(xiàn)》—— Draven
搞懂 Go 垃圾回收，https://juejin.cn/post/6844903917650722829#heading-0
圖解垃圾回收機(jī)制，https://learnku.com/articles/59021
?
更多技術(shù)文章，面試干貨，“xin源意碼”公眾號已經(jīng)準(zhǔn)備好了，關(guān)注后即可免費領(lǐng)取哦~
