聊聊Go的三色標記法

這里是Z哥的個人公眾號

每周五11：45 按時送達

當然了，也會時不時加個餐～

我的第「203」篇原創(chuàng)敬上

大家好，我是 Z 哥。

今天帶來一篇久違的技術型文章。

之前也有不少小伙伴會問，Z 哥你好久沒發(fā)技術性文章了。其實主要原因有以下幾點。

第一，目前的工作偏業(yè)務以及管理，的確在技術上的精力投入不如之前那么多。這也限制了自己在純技術性方面的知識輸出。

第二，雖然自己在工作之余，也會有一部分精力專門用于技術學習，但是大多是以新技術、新框架等的了解、熟悉為主。涉及到的知識 Level 相對比較淺，就算發(fā)出來對大家的幫助也不大，就沒發(fā)。

第三，從長遠來看，自己也不想太把自己局限在技術的圈子里。因為在我看來，技術只是一門手藝，是吃飯的家伙，但是吃飯的家伙從來都不僅僅是技術，還有很多其它的方面。甚至其中很多事情不像具體的技術細節(jié)那樣「標準化」，有很多是通過血汗積累的「非標準化」經驗，我認為這些經驗的價值不亞于技術知識。因此，作為有志與大家交朋友的 Z 哥，自然就不想把自己局限在「技術」這個小圈子里。

好了，回到本文的正題。最近正好在學習 Golang，對它的里面用到的三色標記法的 GC 機制有些好奇（最開始是因為名字讓我聯(lián)想到了三色杯冷飲～），就稍微多深入了解了一下，在這里分享出來，或許將來對你面試啥的有些幫助。

/01  判斷對象存活的思路/

在 GC 領域里，判斷對象存活的主流思路是兩個，「引用計數」和「可達性分析」。

01  引用計數

顧名思義，引用計數的思路就是給每個對象進行計數，每被其它對象引用一次，計數就 +1，引用失效后，計數就 -1。當計數器的數值為 0，就意味著它沒有被使用，可以回收。

02  可達性分析

可達性分析的思路就是通過引用鏈路判斷對象是否可被觸達，如果能觸達說明該對象當前正在被使用，不可回收；反之，沒有觸達到的對象則認為是無使用的，可以回收。

這個引用鏈路的結構類似于有向有環(huán)圖，但是根節(jié)點不止一個，是一個集合，稱之為 GCRoots。

目前主流的 GC 機制大多用的是「可達性分析」這條路線。Go、Java、.Net等都是如此。為什么引用計數不好用呢？因為它有一個特別嚴重的問題：無法處理循環(huán)引用。

像上圖這樣的情況，引用計數永遠不為 0，這些對象就永遠不會被回收，這會嚴重影響回收的效果。

但是它也并不是一無是處，它的回收實時性效果更好，可以配合「可達性分析」一起使用，發(fā)揮各自的優(yōu)點，在不同的場景下使用不同的策略。

由于，「可達性分析」思路是主流，所以后續(xù)發(fā)展出來的很多回收算法都以這個思路為基礎的，三色標記法就是其中之一。我們今天主要來聊聊它。

/02  三色標記法/

在講具體原理之前先了解一個概念，「Stop The World 」，簡稱「STW」。

垃圾回收器的工作流程大體如下：

1. 標記出哪些對象是存活的，哪些是可回收的。

2. 進行回收（清除/復制/整理）。如果在回收期間有移動過的對象（復制/整理），還需要更新引用。

第一步做標記的過程又可以分成兩個步驟。

1. 標記 GC ROOT 能關聯(lián)到的對象。這里會 STW。

2. 從 GCRoots 的直接關聯(lián)對象開始遍歷整個對象圖。這里不會STW。

垃圾回收算法主要做的就是第一步中的第二步，三色標記法也不例外，它將從GC Roots 開始遍歷的對象標記為以下三種顏色：

• 白色，初始值。本次回收沒被掃描過的對象默認都是白色的。而確認不可達的對象也是白色，但是會被標記「不可達」。

• 灰色，中間狀態(tài)。本對象有被外部引用，但是本對象引用的其它對象尚未全部檢測完。

• 黑色，本對象有被其它對象引用，且已檢測完本對象引用的其它對象。

其實這三種顏色是啥不重要的，重要的是它們所表達的狀態(tài)，灰色的中間狀態(tài)，標記過程結束后只會存在白色或者黑色。

整個過程中，這些狀態(tài)是如下圖這樣變化的。

看似很完美的解決方案，其實也存在的一個問題：標記過程中，對象引用發(fā)生了變化。

它會導致兩個問題，「多標」和「漏標」。

多標就是下圖這樣：

由于步驟2不會STW，所以可能存在掃描過A將它標記為黑色后，又重新引用了一個原本已經被標記為白色的D（C斷開了與D的引用）。此時，D就會被回收掉，導致程序出現意料之外的bug。

「漏標」就是這樣：

對象 E/F/G 是“應該”被回收的。然而因為 E 已經變?yōu)榛疑耍淙詴划斪鞔婊顚ο罄^續(xù)遍歷下去。最終的結果是：這部分對象仍會被標記為存活，即本輪 GC 不會回收這部分內存。

傳統(tǒng)的解決這兩個問題的思路有兩個：

1. 在斷開引用的時候做額外處理。

2. 在「黑色」對象重新建立「白色」對象的引用時做額外處理。（回收開始后新建的對象默認為黑色）。

第一個思路專業(yè)叫法是「寫屏障」，第二個是「讀屏障」。其實名字就是噱頭，你可以把它們倆當我們平時編程中用到的 AOP 概念來理解，在修改和讀取之前做一些操作。

基于「寫屏障」，可以延伸出兩個方案：

• 增量更新（Incremental Update）。針對新增的引用，將其記錄下來等待重新遍歷。這個操作在「修改操作后」進行，JVM 中的 CMS 垃圾回收器就是這個思路。

• 原始快照（Snapshot At The Beginning，SATB）。當某個時刻 的 GC Roots 確定后，當時的對象圖就已經確定了。如果期間發(fā)生變化，則可以記錄起來，保證標記依然按照原本的視圖來。這個操作在「修改操作前」進行，JVM中 的 G1 垃圾回收器用的就是這個思路。理論上，配合 「Remembered Set」，SATB 的效率是比增量更新要高的，不過會消耗更多的內存。

基于「讀屏障」的方案是：在「黑色」對象重新建立「白色」對象的引用前，將這個白色對象記錄下來，避免被回收掉。這個動作在「讀取操作前」進行，JVM 中的 ZGC 垃圾回收器就是這個思路。

在 Golang（1.8版本之后）里，用的是一種新的機制，稱之為「混合寫屏障」機制。它的思路總結下來就是4句話：

1. 將對象分為堆上的對象和棧上的對象。

2. GC 開始將棧上的對象全部掃描并標記為黑色，無需 STW。并且之后不再進行第二次重復掃描

3. 在 GC 期間，任何在棧上創(chuàng)建的新對象，均為黑色。

4. 在 GC 期間，在堆上被刪除或者添加的對象都標記為灰色。后續(xù)繼續(xù)掃描。

你看，其實這些原理也沒那么復雜，我相信只要你搞清楚了自己面對的是什么問題，你也能想到這些方案。

好了，總結一下。

這篇呢，Z 哥和你分享了我對 Golang 中的 GC 機制「三色標記法」的了解。

GC 的底層判斷對象存活思路主要是兩個，引用計數和可達性分析。由于引用計數存在循環(huán)引用問題，所以大多數 GC 都是按照后者的思路實現的，Golang 也不例外。

「三色標記法」的原理是，將對象分為了三種狀態(tài)：

• 白色，默認值。本次回收沒被掃描過的對象都是白色的。確認不可達的對象也是白色，但是會被標記「不可達」。

• 灰色，中間狀態(tài)。本對象有被外部引用，但是本對象引用的其它對象尚未全部檢測完。

• 黑色，本對象有被其它對象引用，且已檢測完本對象引用的其它對象。

最終將白色狀態(tài)的對象回收掉。為了解決其中會存在的漏標、多標問題，它通過「混合寫屏障」的機制來解決。思路是，

1. 將對象分為堆上的對象和棧上的對象。

2. GC 開始將棧上的對象全部掃描并標記為黑色，無需 STW。并且之后不再進行第二次重復掃描

3. 在 GC 期間，任何在棧上創(chuàng)建的新對象，均為黑色。

4. 在 GC 期間，在堆上被刪除或者添加的對象都標記為灰色。后續(xù)繼續(xù)掃描。

希望對你有所幫助。

推薦閱讀：

• 如何做好知識管理
  

• 一些微服務拆分的淺見
  

原創(chuàng)不易，如果你覺得這篇文章還不錯，就「點贊」或者「在看」一下吧，鼓勵我的創(chuàng)作 ：）

也可以分享我的公眾號名片給有需要的朋友們。

如果你有關于軟件架構、分布式系統(tǒng)、產品、運營的困惑

可以試試點擊「閱讀原文」