本文轉(zhuǎn)載自微信公眾號「跨界架構(gòu)師」，作者Zachary。轉(zhuǎn)載本文請聯(lián)系跨界架構(gòu)師公眾號。

大家好，我是 Z 哥。

今天帶來一篇久違的技術(shù)型文章。

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

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

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

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

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

一判斷對象存活的思路

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

01 引用計數(shù)

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

02 可達性分析

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

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

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

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

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

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

二三色標記法

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

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

• 標記出哪些對象是存活的，哪些是可回收的。
• 進行回收(清除/復(fù)制/整理)。如果在回收期間有移動過的對象(復(fù)制/整理)，還需要更新引用。

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

• 標記 GC ROOT 能關(guān)聯(lián)到的對象。這里會 STW。
• 從 GCRoots 的直接關(guān)聯(lián)對象開始遍歷整個對象圖。這里不會STW。

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

• 白色，初始值。本次回收沒被掃描過的對象默認都是白色的。而確認不可達的對象也是白色，但是會被標記「不可達」。
• 灰色，中間狀態(tài)。本對象有被外部引用，但是本對象引用的其它對象尚未全部檢測完。
• 黑色，本對象有被其它對象引用，且已檢測完本對象引用的其它對象。

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

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

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

它會導(dǎo)致兩個問題，「多標」和「漏標」。

多標就是下圖這樣：

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

「漏標」就是這樣：

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

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

• 在斷開引用的時候做額外處理。
• 在「黑色」對象重新建立「白色」對象的引用時做額外處理。(回收開始后新建的對象默認為黑色)。

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

• 基于「寫屏障」，可以延伸出兩個方案：
• 增量更新(Incremental Update)。針對新增的引用，將其記錄下來等待重新遍歷。這個操作在「修改操作后」進行，JVM 中的 CMS 垃圾回收器就是這個思路。

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

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

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

• 將對象分為堆上的對象和棧上的對象。
• GC 開始將棧上的對象全部掃描并標記為黑色，無需 STW。并且之后不再進行第二次重復(fù)掃描
• 在 GC 期間，任何在棧上創(chuàng)建的新對象，均為黑色。
• 在 GC 期間，在堆上被刪除或者添加的對象都標記為灰色。后續(xù)繼續(xù)掃描。

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

好了，總結(jié)一下。

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

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

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

• 白色，默認值。本次回收沒被掃描過的對象都是白色的。確認不可達的對象也是白色，但是會被標記「不可達」。
• 灰色，中間狀態(tài)。本對象有被外部引用，但是本對象引用的其它對象尚未全部檢測完。
• 黑色，本對象有被其它對象引用，且已檢測完本對象引用的其它對象。

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

• 將對象分為堆上的對象和棧上的對象。
• GC 開始將棧上的對象全部掃描并標記為黑色，無需 STW。并且之后不再進行第二次重復(fù)掃描
• 在 GC 期間，任何在棧上創(chuàng)建的新對象，均為黑色。
• 在 GC 期間，在堆上被刪除或者添加的對象都標記為灰色。后續(xù)繼續(xù)掃描。

希望對你有所幫助。