圖文結合，白話 Go 的垃圾回收原理

下面首先我們會聊一下什麼是 GC (垃圾回收)，GC 的作用是什麼，然後再結合圖示用每個人都能聽懂的大白話解釋 Go 的 GC 原理。

什麼是 GC？

現代高級編程語言管理內存的方式分爲兩種：自動和手動，像 C、C++ 等編程語言使用手動管理內存的方式，工程師編寫代碼過程中需要主動申請或者釋放內存；而 PHP、Java 和 Go 等語言使用自動的內存管理系統，有內存分配器和垃圾收集器來代爲分配和回收內存，其中垃圾收集器就是我們常說的 GC。

GC 回收的是什麼？

在應用程序中會使用到兩種內存，分別爲堆（Heap）和棧（Stack），GC 負責回收堆內存，而不負責回收棧中的內存。那麼這是爲什麼呢？

主要原因是棧是一塊專用內存，專門爲了函數執行而準備的，存儲着函數中的局部變量以及調用棧。除此以外，棧中的數據都有一個特點——簡單。比如局部變量不能被函數外訪問，所以這塊內存用完就可以直接釋放。正是因爲這個特點，棧中的數據可以通過簡單的編譯器指令自動清理，並不需要通過 GC 來回收。

GC 算法的種類

主流的垃圾回收算法有兩大類，分別是追蹤式垃圾回收算法和引用計數法（ Reference counting ）。而 Go 語言現在用的三色標記法就屬於追蹤式垃圾回收算法的一種。

追蹤式算法的核心思想是判斷一個對象是否可達，一旦這個對象不可達就可以在垃圾回收的控制循環裏被 GC 回收了。那麼我們怎麼判斷一個對象是否可達呢？很簡單，第一步找出所有的全局變量和當前函數棧裏的變量，標記爲可達。第二步，從已經標記的數據開始，進一步標記它們可訪問的變量，以此類推。

Go 的垃圾回收算法

Go 的垃圾收集器從一開始到現在一直在演進，在 v1.5 版本開始三色標記法作爲垃圾回收算法前使用 Mark-And-Sweep（標記清除）算法。從 v1.5 版本 Go 實現了基於三色標記清除的併發垃圾收集器，大幅度降低垃圾收集的延遲從幾百 ms 降低至 10ms 以下。在 v1.8 又使用混合寫屏障將垃圾收集的時間縮短至 0.5ms 以內。

標記清除算法的缺點

Mark-And-Sweep，這個算法就是嚴格按照追蹤式算法的思路來實現的。這個垃圾回收算法的執行流程可以用下面這張圖來表示。

垃圾回收 -- 標記清除

此算法主要有兩個步驟：

• 暫停應用程序的執行, 從根對象出發標記出可達對象。

• 清除未標記的對象，恢復應用程序的執行。

這個算法最大的問題是 GC 執行期間需要把整個程序完全暫停，不能異步地進行垃圾回收，對實時性要求高的系統來說，這種需要長時間掛起的標記清掃法是不可接受的。所以就需要一個算法來解決 GC 運行時程序長時間掛起的問題。

三色標記清除法

從 v1.5 版本 Go 實現了基於三色標記清除的併發垃圾收集器，注意三色標記這個算法不是 Go 的垃圾收集器獨有的。這個算法背後的核心思想是由 Edsger W. Dijkstra，Leslie Lamport，A.J.Martin，C.S.Scholten 和 E.F.M.Steffens 提出的，算法首先於 1978 年發表在論文 On-the-fly Garbage Collection：An Exercise in Cooperation[1] 上面。三色標記清除算法背後的首要原則就是它把堆中的對象根據它們的顏色分到不同集合裏面。

三色標記算法將程序中的對象分成白色、黑色和灰色三類：

• 白色對象 — 潛在的垃圾，其內存可能會被垃圾收集器回收；

• 黑色對象 — 活躍的對象，包括不存在任何引用外部指針的對象以及從根對象可達的對象，垃圾回收器不會掃描這些對象的子對象；

• 灰色對象 — 活躍的對象，因爲存在指向白色對象的外部指針，垃圾收集器會掃描這些對象的子對象；

文字解釋起來不太好理解，我用下面幾張圖演示一下三色標記清除的整個過程：

第一步：在進入 GC 的三色標記階段的一開始，所有對象都是白色的。

第二步, 遍歷根節點集合裏的所有根對象，把根對象引用的對象標記爲灰色，從白色集合放入灰色集合。

第三步, 遍歷灰色集合，將灰色對象引用的對象從白色集合放入灰色集合，之後將此灰色對象放入黑色集合第四步：重複第三步, 直到灰色集合中無任何對象。第五步：回收白色集合裏的所有對象，本次垃圾回收結束。

這裏所說的根節點集合裏的根對象就是棧上的對象或者堆上的全局變量。

寫屏障

Go 在 GC 階段執行三色標記前，還需要先做一個準備工作——打開寫屏障 (Write Barrier)。那麼寫屏障是什麼呢？我們知道三色標記法是一種可以併發執行的算法。所以在 GC 運行過程中程序的函數棧內可能會有新分配的對象，那麼這些對象該怎麼通知到 GC，怎麼給他們着色呢？如果還是按照之前新建的對象標記爲白色就有可能出現下圖中的問題：

在 GC 進行的過程中，應用程序新建了對象I，此時如果已經標記成黑的對象F引用了對象I，那麼在本次 GC 執行過程中因爲黑色對象不會再次掃描，所以如果I着色成白色的話，會被回收掉，這顯然是不允許的。

這個時候就需要我們的寫屏障出馬了。寫屏障主要做一件事情，修改原先的寫邏輯，然後在對象新增的同時給它着色，並且着色爲灰色。因此打開了寫屏障可以保證了三色標記法在併發下安全正確地運行。那麼有人就會問這些寫屏障標記成灰色的對象什麼時候回收呢？答案是後續的 GC 過程中回收，在新的 GC 過程中所有已存對象就又從白色開始逐步被標記啦。

三色不變性

想要在併發或者增量的標記算法中保證正確性，我們需要達成以下兩種三色不變性（Tri-color invariant）中的任意一種：

• 強三色不變性 — 黑色對象不會指向白色對象，只會指向灰色對象或者黑色對象；

• 弱三色不變性 — 黑色對象指向的白色對象必須包含一條從灰色對象經由多個白色對象的可達路徑

屏障技術

垃圾收集中的屏障技術更像是一個鉤子方法，它是在用戶程序讀取對象、創建新對象以及更新對象指針時執行的一段代碼，根據操作類型的不同，我們可以將它們分成讀屏障（Read barrier）和寫屏障（Write barrier）兩種，因爲讀屏障需要在讀操作中加入代碼片段，對用戶程序的性能影響很大，所以編程語言往往都會採用寫屏障保證三色不變性。

Go 的混合寫屏障

在Go 語言 v1.7 版本之前，使用的是Dijkstra插入寫屏障保證強三色不變性，但是運行時並沒有在所有的垃圾收集根對象上開啓插入寫屏障。因爲 Go 語言的應用程序可能包含成百上千的 goroutine，而垃圾收集的根對象一般包括全局變量和棧對象，如果運行時需要在幾百個 goroutine 的棧上都開啓寫屏障，會帶來巨大的額外開銷，所以 Go 團隊在實現上選擇了在標記階段完成時暫停程序、將所有棧對象標記爲灰色並重新掃描，在活躍 goroutine 非常多的程序中，重新掃描的過程需要佔用 10 ~ 100ms 的時間。

Go 語言在 v1.8 組合 Dijkstra 插入寫屏障和 Yuasa 刪除寫屏障構成了如下所示的混合寫屏障，該寫屏障會將被覆蓋的對象標記成灰色並在當前棧沒有掃描時將新對象也標記成灰色：

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

爲了移除棧的重掃描過程，除了引入混合寫屏障之外，在垃圾收集的標記階段，我們還需要將創建的所有新對象都標記成黑色，防止新分配的棧內存和堆內存中的對象被錯誤地回收，因爲棧內存在標記階段最終都會變爲黑色，所以不再需要重新掃描棧空間。

一次完整的 GC 過程

Go 的垃圾回收器在使用了三色標記清除算法和混合寫屏障後大大減少了暫停程序（STW）的時間，主要是在開啓寫屏障前和移除寫屏障前暫停應用程序。

Go 的垃圾收集的整個過程可以分成標記準備、標記、標記終止和清除四個不同階段，每個階段完成的工作如下：

標記準備階段

• 暫停程序，所有的處理器在這時會進入安全點（Safe point）；

標記階段

• 將狀態切換至 _GCmark、開啓寫屏障、用戶程序協助（Mutator Assiste）並將根對象入隊；

• 恢復執行程序，標記進程和用於協助的用戶程序會開始併發標記內存中的對象，標記用的算法就是上面介紹的三色標記清除法。寫屏障會將被覆蓋的指針和新指針都標記成灰色，而所有新創建的對象都會被直接標記成黑色；

• 開始掃描根對象，包括所有 goroutine 的棧、全局對象以及不在堆中的運行時數據結構，掃描 goroutine 棧期間會暫停當前處理器；

• 依次處理灰色隊列中的對象，將對象標記成黑色並將它們指向的對象標記成灰色；

• 使用分佈式的終止算法檢查剩餘的工作，發現標記階段完成後進入標記終止階段；

在標記開始的時候，收集器會默認搶佔 25% 的 CPU 性能，剩下的 75% 會分配給程序執行。但是一旦收集器認爲來不及進行標記任務了，就會改變這個 25% 的性能分配。這個時候收集器會搶佔程序額外的 CPU，這部分被搶佔 goroutine 有個名字叫 Mark Assist。而且因爲搶佔 CPU 的目的主要是 GC 來不及標記新增的內存，那麼搶佔正在分配內存的 goroutine 效果會更加好，所以分配內存速度越快的 goroutine 就會被搶佔越多的資源。

除此以外 GC 還有一個額外的優化，一旦某次 GC 中用到了 Mark Assist，下次 GC 就會提前開始，目的是儘量減少 Mark Assist 的使用，從而避免影響正常的程序執行。

標記終止階段

• 暫停程序、將狀態切換至 _GCmarktermination 並關閉輔助標記的用戶程序；

• 清理處理器上的線程緩存；

清理階段

• 將狀態切換至 _GCoff 開始清理階段，初始化清理狀態並關閉寫屏障；

• 恢復用戶程序，所有新創建的對象會標記成白色；

• 後臺併發清理所有的內存管理單元，當 goroutine 申請新的內存管理單元時就會觸發清理；

清理這個過程是併發進行的。清掃的開銷會增加到分配堆內存的過程中，所以這個時間也是無感知的，不會與垃圾回收的延遲相關聯。

總結

Go 語言的垃圾收集的實現非常複雜，難懂的技術概念和原理也比較多，這篇文章意在用每個人都能看懂的白話文字結合圖示把 Go 的垃圾回收原理解釋清楚，讓讀者能對垃圾回收的大體流程有個概念。

下面用一句話總結概況 Go 的垃圾回收原理：

Go 的 GC 最早期使用的回收算法是標記 - 清除算法，該算法需要在執行期間需要暫停應用程序 (STW)，無法滿足併發程序的實時性。後面 Go 的 GC 轉爲使用三色標記清除算法，並通過混合寫屏障技術保證了 Go 併發執行 GC 時內存中對象的三色一致性（這裏的併發指的是 GC 和應用程序的 goroutine 能同時執行）。

一次完整的垃圾回收會分爲四個階段，分別是標記準備、標記、結束標記以及清理。在標記準備和標記結束階段會需要 STW，標記階段會減少程序的性能，而清理階段是不會對程序有影響的。

參考資料

垃圾收集器 [2]

Go 垃圾回收——三色標記法 [3]

[1]

On-the-fly Garbage Collection：An Exercise in Cooperation: https://www.microsoft.com/en-us/research/publication/fly-garbage-collection-exercise-cooperation/

[2]

垃圾收集器: https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-garbage-collector/

[3]

Go 垃圾回收——三色標記法: https://zhuanlan.zhihu.com/p/105495961

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/IxbJx_m4zRxmc_vcuCoWEQ