0 前言

近期在和大家一起探討 Golang 內存管理機制.

本系列內容分爲兩部分，第一部分談及 Golang 內存模型以及內存分配機制，第二部分和大家討論 Golang 的垃圾回收機制.

本文是其中第二部分. 由於 GC 模塊內容篇幅不小，且筆者近期工作繁忙，因此這部分不得不拆爲上下兩篇.

本文是上篇，在理論層面對 Golang GC 展開介紹，下篇將於下週發出，屆時會基於源碼走讀的方式對理論進行補充論證.

1 垃圾回收算法

1.1 背景介紹

垃圾回收（Garbage Collection，簡稱 GC）是一種內存管理策略，由垃圾收集器以類似守護協程的方式在後臺運作，按照既定的策略爲用戶回收那些不再被使用的對象，釋放對應的內存空間.

（1）GC 帶來的優勢包括：

• 屏蔽內存回收的細節

擁有 GC 能力的語言能夠爲用戶屏蔽複雜的內存管理工作，使用戶更好地聚焦於核心的業務邏輯.

• 以全局視野執行任務

現代軟件工程項目體量與日劇增，一個項目通常由團體協作完成，研發人員負責各自模塊的同時，不可避免會涉及到臨界資源的使用. 此時由於缺乏全局的視野，手動對內存進行管理無疑會增加開發者的心智負擔. 因此，將這部分工作委託給擁有全局視野的垃圾回收模塊來完成，方爲上上之策.

（2）GC 帶來的劣勢：

• 提高了下限但降低了上限

將釋放內存的工作委託給垃圾回收模塊，研發人員得到了減負，但同時也失去了控制主權. 除了運用有限的 GC 調優參數外，更多的自由度都被閹割，需要向系統看齊，服從設定.

• 增加了額外的成本

全局的垃圾回收模塊化零爲整，會需要額外的狀態信息用以存儲全局的內存使用情況. 且部分時間需要中斷整個程序用以支持垃圾回收工作的執行，這些都是 GC 額外產生的成本.

（3）GC 的總體評價

除開少量追求極致速度的特殊小規模項目之外，在絕大多數高併發項目中，GC 模塊都爲我們帶來了極大的裨益，已經成爲一項不可或缺的能力.

下面幾類經典的垃圾回收算法進行介紹，算是一些比較老生常談的內容.

1.2 標記清掃

標記清掃（Mark-Sweep）算法，分爲兩步走：

• 標記：標記出當前還存活的對象

• 清掃：清掃掉未被標記到的垃圾對象

這是一種類似於排除法的間接處理思路，不直接查找垃圾對象，而是標記存活對象，從而取補集推斷出垃圾對象.

至於標記清掃算法的不足之處，通過上圖也得以窺見一二，那就是會產生內存碎片. 經過幾輪標記清掃之後，空閒的內存塊可能零星碎片化分佈，此時倘若有大對象需要分配內存，可能會因爲內存空間無法化零爲整從而導致分配失敗.

1.3 標記壓縮

標記壓縮（Mark-Compact）算法，是在標記清掃算法的基礎上做了升級，在第二步” 清掃 “的同時還會對存活對象進行壓縮整合，使得整體空間更爲緊湊，從而解決內存碎片問題.

標記壓縮算法在功能性上呈現得很出色，而其存在的缺陷也很簡單，就是實現時會有很高的複雜度.

1.4 半空間複製

相信用過 Java 的同學對半空間複製（Semispace Copy）算法並不會感到陌生，它的核心點如下：

• 分配兩片相等大小的空間，稱爲 fromspace 和 tospace

• 每輪只使用 fromspace 空間，以 GC 作爲分水嶺劃分輪次

• GC 時，將 fromspace 存活對象轉移到 tospace 中，並以此爲契機對空間進行壓縮整合

• GC 後，交換 fromspace 和 tospace，開啓新的輪次

顯然，半空間複製算法應用了以空間換取時間的優化策略，解決了內存碎片的問題，也在一定程度上降低了壓縮空間的複雜度. 但其缺點也同樣很明顯——比較浪費空間.

1.5 引用計數

引用計數（Reference Counting）算法是很簡單高效的：

• 對象每被引用一次，計數器加 1

• 對象每被刪除引用一次，計數器減 1

• GC 時，把計數器等於 0 的對象刪除

然而，這個樸素的算法存在一個致命的缺陷：無法解決循環引用或者自引用問題.

本章對垃圾回收算法的背景知識做了補充介紹，下一章我們來看看，在此基礎上，Golang 的 GC 模塊做了怎樣的設計與取捨.

2 Golang 中的垃圾回收

拋開漫長的進化史不談，Golang 在 1.8 版本之後，GC 策略框架已經奠定，就是併發三色標記法 + 混合寫屏障機制，下面我們逐一展開介紹.

2.1 三色標記法

Golang GC 中用到的三色標記法屬於標記清掃 - 算法下的一種實現，由荷蘭的計算機科學家 Dijkstra 提出，下面闡述要點：

• 對象分爲三種顏色標記：黑、灰、白

• 黑對象代表，對象自身存活，且其指向對象都已標記完成

• 灰對象代表，對象自身存活，但其指向對象還未標記完成

• 白對象代表，對象尙未被標記到，可能是垃圾對象

• 標記開始前，將根對象（全局對象、棧上局部變量等）置黑，將其所指向的對象置灰

• 標記規則是，從灰對象出發，將其所指向的對象都置灰. 所有指向對象都置灰後，當前灰對象置黑

• 標記結束後，白色對象就是不可達的垃圾對象，需要進行清掃.

2.2 併發垃圾回收

Golang 1.5 版本是個分水嶺，在此之前，GC 時需要停止全局的用戶協程，專注完成 GC 工作後，再恢復用戶協程，這樣做在實現上簡單直觀，但是會對用戶造成不好的體驗.

自 1.5 版本以來，Golang 引入了併發垃圾回收機制，允許用戶協程和後臺的 GC 協程併發運行，大大地提高了用戶體驗. 但 “併發” 是一個值得大家警惕的字眼. 用戶協程運行時可能對對象間的引用關係進行調整，這會嚴重打亂 GC 三色標記時的標記秩序. 這些問題，我們將在 2.3 小節展開介紹.

2.3 幾個問題

首先在（1）（2）兩個問題中，討論一下併發垃圾回收機制下，可能產生的問題.

（1）Golang 併發垃圾回收可能存在漏標問題

漏標問題指的是在用戶協程與 GC 協程併發執行的場景下，部分存活對象未被標記從而被誤刪的情況. 這一問題產生的過程如下：

• 條件：初始時刻，對象 B 持有對象 C 的引用

• moment1：GC 協程下，對象 A 被掃描完成，置黑；此時對象 B 是灰色，還未完成掃描

• momen2：用戶協程下，對象 A 建立指向對象 C 的引用

• moment3：用戶協程下，對象 B 刪除指向對象 C 的引用

• moment4：GC 協程下，開始執行對對象 B 的掃描

在上述場景中，由於 GC 協程在 B 刪除 C 的引用後纔開始掃描 B，因此無法到達 C. 又因爲 A 已經被置黑，不會再重複掃描，因此從掃描結果上看，C 是不可達的.

然而事實上，C 應該是存活的（被 A 引用），而 GC 結束後會因爲 C 仍爲白色，因此被 GC 誤刪.

漏標問題是無法接受，其引起的誤刪現象可能會導致程序出現致命的錯誤. 針對漏標問題，Golang 給出的解決方案是屏障機制的使用，這部分內容將在本文第 3 章進一步展開.

（2）Golang 併發垃圾回收可能存在多標問題

多標問題指的是在用戶協程與 GC 協程併發執行的場景下，部分垃圾對象被誤標記從而導致 GC 未按時將其回收的問題. 這一問題產生的過程如下：

• 條件：初始時刻，對象 A 持有對象 B 的引用

• moment1：GC 協程下，對象 A 被掃描完成，置黑；對象 B 被對象 A 引用，因此被置灰

• momen2：用戶協程下，對象 A 刪除指向對象 B 的引用

上述場景引發的問題是，在事實上，B 在被 A 刪除引用後，已成爲垃圾對象，但由於其事先已被置灰，因此最終會更新爲黑色，不會被 GC 刪除.

錯標問題對比於漏標問題而言，是相對可以接受的. 其導致本該被刪但仍僥倖存活的對象被稱爲 “浮動垃圾”，至多到下一輪 GC，這部分對象就會被 GC 回收，因此錯誤可以得到彌補.

（3）Golang 垃圾回收如何解決內存碎片問題？

1.2 小節中有提及，標記清掃算法會存在產生 “內存碎片” 的缺陷. 那麼採用標記清掃算法的 Golang GC 模塊要如何化解這一問題呢？

在筆者一週前發佈的文章—— “Golang 內存模型與分配機制” 的介紹中已經能夠給出這一問題的答覆. Golang 採用 TCMalloc 機制，依據對象的大小將其歸屬爲到事先劃分好的 spanClass 當中，這樣能夠消解外部碎片的問題，將問題限制在相對可控的內部碎片當中.

基於此，Golang 選擇採用實現上更爲簡單的標記清掃算法，避免使用複雜度更高的標記壓縮算法，因爲在 TCMalloc 框架下，後者帶來的優勢已經不再明顯.

（4）Golang 爲什麼不選擇分代垃圾回收機制？

分代算法指的是，將對象分爲年輕代和老年代兩部分（或者更多），採用不同的 GC 策略進行分類管理. 分代 GC 算法有效的前提是，絕大多數年輕代對象都是朝生夕死，擁有更高的 GC 回收率，因此適合採用特別的策略進行處理.

然而 Golang 中存在內存逃逸機制，會在編譯過程中將生命週期更長的對象轉移到堆中，將生命週期短的對象分配在棧上，並以棧爲單位對這部分對象進行回收.

綜上，內存逃逸機制減弱了分代算法對 Golang GC 所帶來的優勢，考慮分代算法需要產生額外的成本（如不同年代的規則映射、狀態管理以及額外的寫屏障），Golang 選擇不採用分代 GC 算法.

3 屏障機制

本章介紹屏障有關的內容，主要是爲了解決 2.3 小節中提及的併發 GC 下的漏標問題.

3.1 強弱三色不變式

漏標問題的本質就是，一個已經掃描完成的黑對象指向了一個被灰 \ 白對象刪除引用的白色對象. 構成這一場景的要素拆分如下：

（1）黑色對象指向了白色對象

（2）灰、白對象刪除了白色對象

（3）（1）、（2）步中談及的白色對象是同一個對象

（4）（1）發生在（2）之前

一套用於解決漏標問題的方法論稱之爲強弱三色不變式：

• 強三色不變式：白色對象不能被黑色對象直接引用（直接破壞（1））

• 弱三色不變式：白色對象可以被黑色對象引用，但要從某個灰對象出發仍然可達該白對象（間接破壞了（1）、（2）的聯動）

3.2 插入寫屏障

屏障機制類似於一個回調保護機制，指的是在完成某個特定動作前，會先完成屏障成設置的內容.

插入寫屏障（Dijkstra）的目標是實現強三色不變式，保證當一個黑色對象指向一個白色對象前，會先觸發屏障將白色對象置爲灰色，再建立引用.

如果所有流程都能保證做到這一點，那麼 3.1 小節中的（1）就會被破壞，漏標問題得以解決.

3.3 刪除寫屏障

刪除寫屏障（Yuasa barrier）的目標是實現弱三色不變式，保證當一個白色對象即將被上游刪除引用前，會觸發屏障將其置灰，之後再刪除上游指向其的引用.

這一流程中，3.1 小節的步驟（2）會被破壞，漏標問題得以解決.

3.4 混合寫屏障

結合 3.2 3.3 小節來看，插入寫屏障、刪除寫屏障二者擇其一，即可解決併發 GC 的漏標問題，至於錯標問題，則採用容忍態度，放到下一輪 GC 中進行延後處理即可.

然而真實場景中，需要補充一個新的設定——屏障機制無法作用於棧對象.

這是因爲棧對象可能涉及頻繁的輕量操作，倘若這些高頻度操作都需要一一觸發屏障機制，那麼所帶來的成本將是無法接受的.

在這一背景下，單獨看插入寫屏障或刪除寫屏障，都無法真正解決漏標問題，除非我們引入額外的 Stop the world（STW）階段，對棧對象的處理進行兜底。

爲了消除這個額外的 STW 成本，Golang 1.8 引入了混合寫屏障機制，可以視爲糅合了插入寫屏障 + 刪除寫屏障的加強版本，要點如下：

• GC 開始前，以棧爲單位分批掃描，將棧中所有對象置黑

• GC 期間，棧上新創建對象直接置黑

• 堆對象正常啓用插入寫屏障

• 堆對象正常啓用刪除寫屏障

下面我們通過 3.5 小節的幾個 show case，來論證混合寫屏障機制是否真的能解決併發 GC 下的各種極端場景問題.

3.5 show case

（1）case 1：堆對象刪除引用，棧對象建立引用

• 背景：存在棧上對象 A，黑色（掃描完）；

存在堆上對象 B，白色（未被掃描）；

存在堆上對象 C，被堆上對象 B 引用，白色（未被掃描）

• moment1：A 建立對 C 的引用，由於棧無屏障機制，因此正常建立引用，無額外操作

• moment2：B 嘗試刪除對 C 的引用，刪除寫屏障被觸發，C 被置灰，因此不會漏標

（2）case 2：一個堆對象刪除引用，成爲另一個堆對象下游

• 背景：存在堆上對象 A，白色（未被掃描）；

存在堆上對象 B，黑色（已完成掃描）；

存在堆上對象 C，被堆上對象 B 引用，白色（未被掃描）

• moment1：B 嘗試建立對 C 的引用，插入寫屏障被觸發，C 被置灰

• moment2：A 刪除對 C 的引用，此時 C 已置灰，因此不會漏標

（3）case 3：棧對象刪除引用，成爲堆對象下游

• 背景：存在棧上對象 A，白色（未完成掃描，說明對應的棧未掃描）；

存在堆上對象 B，黑色（已完成掃描）；

存在堆上對象 C，被棧上對象 A 引用，白色（未被掃描）

• moment1：B 嘗試建立對 C 的引用，插入寫屏障被觸發，C 被置灰

• moment2：A 刪除對 C 的引用，此時 C 已置灰，因此不會漏標

（4）case 4：一個棧中對象刪除引用，另一個棧中對象建立引用

• • 背景：存在棧上對象 A，白色（未掃描，這是因爲對應的棧還未開始掃描）；

存在棧上對象 B，黑色（已完成掃描，說明對應的棧均已完成掃描）；

存在堆上對象 C，被棧上對象 A 引用，白色（未被掃描）

• moment1：B 建立對 C 的引用；

• moment2：A 刪除對 C 的引用.

• 結論：這種場景下，C 要麼已然被置灰，要麼從某個灰對象觸發仍然可達 C.

• 原因在於，對象的引用不是從天而降，一定要有個來處. 當前 case 中，對象 B 能建立指向 C 的引用，至少需要滿足如下三個條件之一：

I 棧對象 B 原先就持有 C 的引用，如若如此，C 就必然已處於置灰狀態（因爲 B 已是黑色）

II 棧對象 B 持有 A 的引用，通過 A 間接找到 C. 然而這也是不可能的，因爲倘若 A 能同時被另一個棧上的 B 引用到，那樣 A 必然會升級到堆中，不再滿足作爲一個棧對象的前提；

III B 同棧內存在其他對象 X 可達 C，此時從 X 出發，必然存在一個灰色對象，從其出發存在可達 C 的路線.

綜上，我們得以證明混合寫屏障是能夠勝任併發 GC 場景的解決方案，並且滿足棧無須添加屏障的前提.

4 源碼導讀展望

理論的學習上更加生動、源碼的學習則較爲晦澀. 然而，個人秉持的觀點是 “原理需要被源碼論證”. 因爲理論是抽象的，且言語表達是帶有主觀性的，不同人傳譯分享後，難免存在偏頗和歧義. 再者，網上分享博客中人云亦云、斷章取義的也不在少數. 因此，甄別是非真假的核心點就在於——深挖源碼. 因爲，代碼是不會騙人的.

懷揣着這個信念，下週我會帶來垃圾回收源碼走讀相關的新作，此處我們先摘出走讀代碼的框架，大家如有興趣，可以先作預習鋪墊，這樣下週食用效果更佳~

4.1 源碼文件位置

u5s0cV

4.2 觸發 GC 鏈路

I 定時觸發 GC

hm4Jan

II 對象分配觸發

W0chq9

（2）標記準備

sKecaF

（3）併發標記

I p 調度標記協程

CAxH59

II 併發標記

zy6JaQ

（4）標記清掃

v25f5K

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