前言

Go語言能夠支持實時的，高并發(fā)的消息系統(tǒng)，在高達百萬級別的消息系統(tǒng)中能夠?qū)⒀舆t降低到100ms以下，很大一部分需要歸功于Go高效的垃圾回收系統(tǒng)。

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

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

正文

1. 從Haskell到Go

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

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

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

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

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

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

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; 復(fù)制代碼

2.1. 第一步

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

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

2.2. 第二步

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

var D LinkedListNode; A.next = &D; 復(fù)制代碼

需要注意的是，作為一個新的內(nèi)存對象，需要將其放置在灰色區(qū)域中。為什么要將其放在灰色區(qū)域中呢？這里有一個規(guī)則，如果一個指針域發(fā)生了變化，則被指向的對象需要變色。因為所有的新建內(nèi)存對象都需要將其地址賦值給一個引用，所以他們將會立即變?yōu)榛疑?#xff08;這就需要問了，為什么C不是灰色？）

2.3. 第三步

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

2.4. 第四步 掃描內(nèi)存對象

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

2.5. 第五步

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

var E LinkedListNode; C.next = &E; 復(fù)制代碼

按照我們之前的規(guī)則，新建的內(nèi)存對象需要放置在灰色區(qū)域，如圖所示：

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

2.6. 第六步 指針重新賦值

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

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

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

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

2.7. 第七步

將灰色區(qū)域中沒有引用依賴的內(nèi)存對象移動到黑色區(qū)域中，此時D在灰色區(qū)域中沒有其它依賴，并依賴于它的內(nèi)存對象A已經(jīng)在黑色區(qū)域了，將其移動到黑色區(qū)域中。

2.8. 第八步

在程序邏輯中，將B.next賦值為了nil,此時E將變?yōu)椴豢蛇_。但此時E在灰色區(qū)域，將不會被回收，那么這樣會導(dǎo)致內(nèi)存泄漏嗎？其實不會，E將在下一個GC循環(huán)中被回收，三色算法能夠保證這點：如果一個內(nèi)存對象在一次GC循環(huán)開始的時候無法被訪問，則將會被凍結(jié)，并在GC的最后將其回收。

2.9. 第九步

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

2.10. 第十步

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

2.11. 第十一步 回收白色區(qū)域

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

2.12. 第十二步 區(qū)域變色

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

3. GC三色算法小結(jié)

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

4. 延遲 VS 吞吐

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

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

5. 實際表現(xiàn)

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

這是Go語言版本的基準(zhǔn)測試代碼，這里的buffer用數(shù)組實現(xiàn):

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) } 復(fù)制代碼

相同的邏輯，不同語言實現(xiàn)下進行的測試結(jié)果如下：

令人驚訝的是Java,表現(xiàn)得非常一般，而OCaml則非常之好，OCaml語言能夠達到約3ms的GC暫停時間，這是因為OCaml采用的GC算法是 incremental GC algorithm (而在實時系統(tǒng)中不采用OCaml的原因是該語言對多核的支持不好)。

正如表中顯示的,Go的GC暫停時間大約在7ms左右，表現(xiàn)也好，已經(jīng)完全能夠滿足我們的要求。

總結(jié)

這次調(diào)查的重點在于GC要么關(guān)注于低延遲，要么關(guān)注于高吞吐。當(dāng)然這些也都取決于我們的程序是如何使用堆空間的(我們是否有很多內(nèi)存對象？每個對象的生命周期是長還是短？)

理解底層的GC算法對該系統(tǒng)是否適用于你的測試用例是非常重要的。當(dāng)然GC系統(tǒng)的實際實現(xiàn)也至關(guān)重要。你的基準(zhǔn)測試程序的內(nèi)存占用應(yīng)該同你將要實現(xiàn)的真正程序類似，這樣才能夠在實踐中檢驗GC系統(tǒng)對于你的程序而言是否高效。正如前文所說的，Go的GC系統(tǒng)并不完美，但是對于我們的系統(tǒng)而言是可以接受的。

盡管存在一些問題，但是Go的GC表現(xiàn)已經(jīng)優(yōu)于大部分同樣擁有GC系統(tǒng)的語言了，Go的開發(fā)團隊針對GC延遲進行了優(yōu)化，并且還在繼續(xù)。Go的GC確實是有可圈可點之處，無論是理論上還是實踐中。

參考

• Golang’s Real-time GC in Theory and Practice

總結(jié)

以上是生活随笔為你收集整理的Go语言实时GC - 三色标记算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。