Go語言實時GC - 三色標記算法

前言

Go語言能夠支持實時的，高并發的消息系統，在高達百萬級別的消息系統中能夠將延遲降低到100ms以下，很大一部分需要歸功于Go高效的垃圾回收系統。

對于實時系統而言，垃圾回收系統可能是一個極大的隱患，因為在垃圾回收的時候需要將整個應用程序暫停。所以在我們設計消息總線系統的時候，需要小心地選擇我們的語言。Go一直在強調它的低延遲，但是它真的做到了嗎？如果是的，它是怎么做到的呢？

在這篇文章當中，我們將會看到Go語言的GC是如何實現的（tricolor algorithm，三色算法），以及為什么這種方法能夠達到如此之低的GC暫停，以及最重要的是，它是否真的有效（對這些GC暫停進行benchmar測試，以及同其它類型的語言進行比較）。

正文

1. 從Haskell到Go

我們用pub/sub消息總線系統為例說明問題，這些系統在發布消息的時候都是in-memory存儲的。在早期，我們用Haskell實現了第一版的消息系統，但是后面發現GHC的gabage collector存在一些基礎延遲的問題，我們放棄了這個系統轉而用Go進行了實現。

這是有關 Haskell消息系統的一些實現細節，在GHC中最重要的一點是它GC暫停時間同當前的工作集的大小成比例關系（也就是說，GC時間和內存中存儲對象的數目有關）。在我們的例子中，內存中存儲對象的數目往往都非常巨大，這就導致gc時間常常高達數百毫秒。這就會導致在GC的時候整個系統是阻塞的。

而在Go語言中，不同于GHC的全局暫停(stop-the-world)收集器，Go的垃圾收集器是和主程序并行的。這就可以避免程序的長時間暫停。我們則更加關注于Go所承諾的低延遲以及其在每個新版本中所提及的延遲提升是否真的向他們所說的那樣。

2. 并行垃圾回收是如何工作的?

Go的GC是如何實現并行的呢？其中的關鍵在于三色標記清除算法 (tricolor mark-and-sweep algorithm)。該算法能夠讓系統的gc暫停時間成為能夠預測的問題。調度器能夠在很短的時間內實現GC調度，并且對源程序的影響極小。下面我們看看三色標記清除算法是如何工作的：

假設我們有這樣的一段鏈表操作的代碼：

var A LinkedListNode;
var B LinkedListNode;
// ...
B.next = &LinkedListNode{next: nil};
// ...
A.next = &LinkedListNode{next: nil};
*(B.next).next = &LinkedListNode{next: nil};
B.next = *(B.next).next;
B.next = nil;
復制代碼

2.1. 第一步

var A LinkedListNode;
var B LinkedListNode;// ...B.next = &LinkedListNode{next: nil};
復制代碼

剛開始我們假設有三個節點A、B和C，作為根節點，紅色的節點A和B始終都能夠被訪問到，然后進行一次賦值 B.next = &C。初始的時候垃圾收集器有三個集合，分別為黑色，灰色和白色。現在，因為垃圾收集器還沒有運行起來，所以三個節點都在白色集合中。

2.2. 第二步

我們新建一個節點D，并將其賦值給A.next。即：

var D LinkedListNode;
A.next = &D;
復制代碼

需要注意的是，作為一個新的內存對象，需要將其放置在灰色區域中。為什么要將其放在灰色區域中呢？這里有一個規則，如果一個指針域發生了變化，則被指向的對象需要變色。因為所有的新建內存對象都需要將其地址賦值給一個引用，所以他們將會立即變為灰色。（這就需要問了，為什么C不是灰色？）

2.3. 第三步

在開始GC的時候，根節點將會被移入灰色區域。此時A、B、D三個節點都在灰色區域中。由于所有的程序子過程（process，因為不能說是進程，應該算是線程，但是在go中又不完全是線程）要么事程序正常邏輯，要么是GC的過程，而且GC和程序邏輯是并行的，所以程序邏輯和GC過程應該是交替占用CPU資源的。

2.4. 第四步掃描內存對象

在掃描內存對象的時候，GC收集器將會把該內存對象標記為黑色，然后將其子內存對象標記為灰色。在任一階段，我們都能夠計算當前GC收集器需要進行的移動步數：2*|white| + |grey|，在每一次掃描GC收集器都至少進行一次移動，直到達到當前灰色區域內存對象數目為0。

2.5. 第五步

程序此時的邏輯為，新賦值一個內存對象E給C.next，代碼如下：

var E LinkedListNode;
C.next = &E;
復制代碼

按照我們之前的規則，新建的內存對象需要放置在灰色區域，如圖所示：

這樣做，收集器需要做更多的事情，但是這樣做當在新建很多內存對象的時候，可以將最終的清除操作延遲。值得一提的是，這樣處理白色區域的體積將會減小，直到收集器真正清理堆空間時再重新填入移入新的內存對象。

2.6. 第六步指針重新賦值

程序邏輯此時將 B.next.next賦值給了B.next，也就是將E賦值給了B.next。代碼如下：

*(B.next).next = &LinkedListNode{next: nil};
// 指針重新賦值:
B.next = *(B.next).next;
復制代碼

這樣做之后，如圖所示，C將不可達。

這就意味著，收集器需要將C從白色區域移除，然后在GC循環中將其占用的內存空間回收。

2.7. 第七步

將灰色區域中沒有引用依賴的內存對象移動到黑色區域中，此時D在灰色區域中沒有其它依賴，并依賴于它的內存對象A已經在黑色區域了，將其移動到黑色區域中。

2.8. 第八步

在程序邏輯中，將B.next賦值為了nil,此時E將變為不可達。但此時E在灰色區域，將不會被回收，那么這樣會導致內存泄漏嗎？其實不會，E將在下一個GC循環中被回收，三色算法能夠保證這點：如果一個內存對象在一次GC循環開始的時候無法被訪問，則將會被凍結，并在GC的最后將其回收。

2.9. 第九步

在進行第二次GC循環的時候，將E移入到黑色區域，但是C并不會移動，因為是C引用了E，而不是E引用C。

2.10. 第十步

收集器再掃描最后一個灰色區域中的內存對象B，并將其移動到黑色區域中。

2.11. 第十一步回收白色區域

收集器再掃描最后一個灰色區域中的內存對象B，并將其移動到黑色區域中。

2.12. 第十二步區域變色

這一步是最有趣的，在進行下次GC循環的時候，完全不需要將所有的內存對象移動回白色區域，只需要將黑色區域和白色區域的顏色換一下就好了，簡單而且高效。

3. GC三色算法小結

上面就是三色標記清除算法的一些細節，在當前算法下仍舊有兩個階段需要 stop-the-world：一是進行root內存對象的棧掃描；二是標記階段的終止暫停。令人激動的是，標記階段的終止暫停將被去除。在實踐中我們發現，用這種算法實現的GC暫停時間能夠在超大堆空間回收的情況下達到<1ms的表現。

4. 延遲 VS 吞吐

如果一個并行GC收集器在處理超大內存堆時能夠達到極低的延遲，那么為什么還有人在用stop-the-world的GC收集器呢？難道Go的GC收集器還不夠優秀嗎？

這不是絕對的，因為低延遲是有開銷的。最主要的開銷就是，低延遲削減了吞吐量。并發需要額外的同步和賦值操作,而這些操作將會占用程序的處理邏輯的時間。而Haskell的GHC則針對吞吐量進行了優化，Go則專注于延遲，我們在考慮采用哪種語言的時候需要針對我們自己的需求進行選擇，對于推送系統這種實時性要求比較高的系統，選擇Go語言則是權衡之下得到的選擇。

5. 實際表現

目前而言，Go好像已經能夠滿足低延遲系統的要求了，但是在實際中的表現又怎么樣呢？利用相同的benchmark測試邏輯實現進行比較：該基準測試將不斷地向一個限定緩沖區大小的buffer中推送消息，舊的消息將會不斷地過期并成為垃圾需要進行回收，這要求內存堆需要一直保持較大的狀態，這很重要，因為在回收的階段整個內存堆都需要進行掃描以確定是否有內存引用。這也是為什么GC的運行時間和存活的內存對象和指針數目成正比例關系的原因。

這是Go語言版本的基準測試代碼，這里的buffer用數組實現:

package mainimport ("fmt""time"
)const (windowSize = 200000msgCount   = 1000000
)type (message []bytebuffer  [windowSize]message
)var worst time.Durationfunc mkMessage(n int) message {m := make(message, 1024)for i := range m {m[i] = byte(n)}return m
}func pushMsg(b *buffer, highID int) {start := time.Now()m := mkMessage(highID)(*b)[highID%windowSize] = melapsed := time.Since(start)if elapsed > worst {worst = elapsed}
}func main() {var b bufferfor i := 0; i < msgCount; i++ {pushMsg(&b, i)}fmt.Println("Worst push time: ", worst)
}
復制代碼