并發的垃圾回收

golang 語言設計的根本性追求就是高并發，低延遲，所以golang 的垃圾回收也是持續在優化。golang 的垃圾回收是并發垃圾回收設計，業務運行和回收器運行并發，這種設計的初衷是降低垃圾回收停頓時間。

之前提過一個例子，如果你要安全的實現回收垃圾，那么簡單的就是回收垃圾的時候，把所有的業務操作都停止，這個術語是STW（stop the world）。下面用一些術語：

1. 賦值器：這個就是程序的業務代碼
2. 回收器：垃圾回收器

STW 安全的回收

下面畫了一個圖，表示了這種簡單例子的一個演進：

1. 灰色表示一次垃圾回收操作
2. 黑色表示下一次

圖里我們看到：

1. 在單處理器的場景，賦值器和回收器的代碼是交替運行的，回收器回收的時間即為賦值器停頓的時間；
2. 多處理器的時候，多個賦值器線程并行執行，但是每次回收器回收的時候，還是要掛起多個賦值器；
3. 第三種，就是讓多個處理器并行的執行回收器的任務，減少停頓；

這是一個顯而易見的實現和優化演進，其實再進一步，我們可以把完整的一個回收任務拆分成小粒度的，搞成一次次增量的回收，這樣單次的停頓時間就更少了。

并發的垃圾回收

golang 明顯不是這個（哈哈，曾經是），golang 必須要讓賦值器和回收器并發起來，不能有明顯的停頓。golang 當前的垃圾回收特點：

1. 完全消除了明顯的 STW （除了開啟的垃圾回收的時候）
2. 回收器標記、回收過程完全和賦值器并發
1. 但是注意一點，對于單個棧來說，是一個一個掛起掃描的，這種掃描方式叫做 on-the-fly collection，并且是增量式的；

golang 的回收沒有混合屏障之前，一直是插入寫屏障，由于棧賦值沒有 hook 的原因，所以有 STW，混合寫屏障之后，就沒有 STW。

這里有個點要理解：STW 是全局的賦值器掛起，我們一直說 golang 消除了 STW 說的是沒有了全局性的掛起，但是局部的賦值器掛起是一直有的，包括現在也是有的。

插入寫屏障

偽代碼

Write 操作改變特定內存的值。改操作引發內存存儲，需要三個參數：指向源的指針、待修改域的索引、待存儲的值。寫賦值操作用偽代碼表示下：

Write(src, i, val):    src[i] <- val

我們的插入寫屏障就是在這段賦值代碼中，添加一段 hook 代碼，這段 hook 代碼就是所謂的屏障代碼，由編譯器在編譯期生成。寫屏障的實現有多種，golang 使用的是 Dijkstra 算法實現：

atomic Write(src, i, ref)    src[i] <- ref    if isBlack(src)        shade(ref)

這段偽代碼我們非常容易看懂，就是加了后面的一個判讀邏輯，如果 src 已經是黑色的，那么就把指向的新對象置灰色。

對象丟失的必要條件

之前的文章有提到三色標記法，提到，如果要想出現對象丟失（錯誤的回收）那么必須是同時滿足兩個條件：

• 條件1:賦值器把白色對象的引用寫入給黑色對象了（換句話說，黑色對象指向白色對象了）
• 條件2:從灰色對象出發，最終到達該白色對象的所有路徑都被賦值器破壞（換句話說，這個已經被黑色指向的白色對象，還沒有在灰色對象的保護下）

圖示舉例：

1. 賦值器操作一：X -> Z
2. 賦值器操作二：Y -> null
3. 回收器操作一：Scan Y
4. 回收器操作二：回收 Z （這就有問題了）

在這兩個條件同時出現的時候，才會出現對象被錯誤的回收。然后我們回過頭看下寫屏障的實現，就會發現，寫屏障從根本上破壞了第一個條件的出現。

寫屏障是怎么解決問題？

加了屏障的示意圖：

插入寫屏障就是這么簡單。只要你保證時時刻刻沒有黑色對象指向白色對象的條件出現，那么回收的正確性就能保證。但是話又說回來了，這個屏障是配合賦值器回收器并發的場景才需要，如果你允許直接STW執行回收器邏輯，那就不需要這么復雜了，當然啦，這樣的話賦值器的性能肯定就不行啦。

雖然插入寫屏障能解決問題，但是 golang 針對棧上對象的賦值卻沒有捕捉（沒有生成寫屏障），原因自然是性能損耗和實現復雜度的考慮。這就開了一個例外的口子，有一些黑色的棧對象指向了白色的對象，而回收器卻無法感知到。golang 的解決方法是：最后再 STW 重新掃描一把棧。這個自然就會導致整個進程的賦值器卡頓，所以后面 golang 是引用混合寫屏障解決這個問題。