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

大家好，我是 Z 哥。

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

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

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

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

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

好了，回到本文的正題。最近正好在學(xué)習(xí) Golang，對(duì)它的里面用到的三色標(biāo)記法的 GC 機(jī)制有些好奇(最開始是因?yàn)槊肿屛衣?lián)想到了三色杯冷飲～)，就稍微多深入了解了一下，在這里分享出來，或許將來對(duì)你面試啥的有些幫助。

一判斷對(duì)象存活的思路

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

01 引用計(jì)數(shù)

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

02 可達(dá)性分析

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

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

目前主流的 GC 機(jī)制大多用的是「可達(dá)性分析」這條路線。Go、Java、.Net等都是如此。為什么引用計(jì)數(shù)不好用呢?因?yàn)樗幸粋€(gè)特別嚴(yán)重的問題：無法處理循環(huán)引用。

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

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

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

二三色標(biāo)記法

在講具體原理之前先了解一個(gè)概念，「Stop The World 」，簡(jiǎn)稱「STW」。

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

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

第一步做標(biāo)記的過程又可以分成兩個(gè)步驟。

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

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

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

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

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

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

它會(huì)導(dǎo)致兩個(gè)問題，「多標(biāo)」和「漏標(biāo)」。

多標(biāo)就是下圖這樣：

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

「漏標(biāo)」就是這樣：

對(duì)象 E/F/G 是“應(yīng)該”被回收的。然而因?yàn)?E 已經(jīng)變?yōu)榛疑?，其仍?huì)被當(dāng)作存活對(duì)象繼續(xù)遍歷下去。最終的結(jié)果是：這部分對(duì)象仍會(huì)被標(biāo)記為存活，即本輪 GC 不會(huì)回收這部分內(nèi)存。

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

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

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

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

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

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

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

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

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

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

這篇呢，Z 哥和你分享了我對(duì) Golang 中的 GC 機(jī)制「三色標(biāo)記法」的了解。

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

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

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

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

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

希望對(duì)你有所幫助。