我是一個(gè)著迷于產(chǎn)品和運(yùn)營的技術(shù)人，樂于跨界的終身學(xué)習(xí)者。歡迎關(guān)注我的個(gè)人公眾號(hào)「跨界架構(gòu)師」
每周五11：45 按時(shí)送達(dá)～
我的第「203」篇原創(chuàng)敬上
大家好，我是 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ā)。
第三授滓，從長遠(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ì)你面試啥的有些幫助吁讨。
/01 ?判斷對(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)記法就是其中之一。我們今天主要來聊聊它摇肌。
/02? 三色標(biāo)記法/
在講具體原理之前先了解一個(gè)概念擂红，「Stop The World 」，簡稱「STW」围小。
垃圾回收器的工作流程大體如下：
? ? 1.標(biāo)記出哪些對(duì)象是存活的昵骤，哪些是可回收的。
? ? 2.進(jìn)行回收（清除/復(fù)制/整理）肯适。如果在回收期間有移動(dòng)過的對(duì)象（復(fù)制/整理）变秦，還需要更新引用。
第一步做標(biāo)記的過程又可以分成兩個(gè)步驟框舔。
? ? 1.標(biāo)記 GC ROOT 能關(guān)聯(lián)到的對(duì)象蹦玫。這里會(huì) STW。
? ? 2.從 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è)：
? ? 1.在斷開引用的時(shí)候做額外處理。
? ? 2.在「黑色」對(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句話：
? ? 1.將對(duì)象分為堆上的對(duì)象和棧上的對(duì)象仲智。
? ? 2.GC 開始將棧上的對(duì)象全部掃描并標(biāo)記為黑色买乃，無需 STW。并且之后不再進(jìn)行第二次重復(fù)掃描
? ? 3.在 GC 期間钓辆，任何在棧上創(chuàng)建的新對(duì)象剪验，均為黑色。
? ? 4.在 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ī)制來解決向叉。思路是，
? ? 1.將對(duì)象分為堆上的對(duì)象和棧上的對(duì)象嗦董。
? ? 2.GC 開始將棧上的對(duì)象全部掃描并標(biāo)記為黑色母谎，無需 STW。并且之后不再進(jìn)行第二次重復(fù)掃描
? ? 3.在 GC 期間展懈，任何在棧上創(chuàng)建的新對(duì)象，均為黑色供璧。
? ? 4.在 GC 期間存崖，在堆上被刪除或者添加的對(duì)象都標(biāo)記為灰色。后續(xù)繼續(xù)掃描睡毒。
希望對(duì)你有所幫助来惧。
推薦閱讀：
如果你喜歡這篇文章，可以點(diǎn)一下右下角的「愛心」演顾，支持我的創(chuàng)作～
定期發(fā)表原創(chuàng)內(nèi)容：架構(gòu)設(shè)計(jì)丨分布式系統(tǒng)丨產(chǎn)品丨運(yùn)營丨一些深度思考供搀。
