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 main

import (
    "fmt"
    "time"
)

const (
    windowSize = 200000
    msgCount   = 1000000
)

type (
    message []byte
    buffer  [windowSize]message
)

var worst time.Duration

func 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] = m
    elapsed := time.Since(start)
    if elapsed > worst {
        worst = elapsed
    }
}

func main() {
    var b buffer
    for i := 0; i < msgCount; i++ {
        pushMsg(&b, i)
    }
    fmt.Println("Worst push time: ", worst)
}
复制代码

相同的逻辑，不同语言实现下进行的测试结果如下：

令人惊讶的是Java,表现得非常一般，而OCaml则非常之好，OCaml语言能够达到约3ms的GC暂停时间，这是因为OCaml采用的GC算法是 incremental GC algorithm (而在实时系统中不采用OCaml的原因是该语言对多核的支持不好)。

正如表中显示的,Go的GC暂停时间大约在7ms左右，表现也好，已经完全能够满足我们的要求。

总结

这次调查的重点在于GC要么关注于低延迟，要么关注于高吞吐。当然这些也都取决于我们的程序是如何使用堆空间的(我们是否有很多内存对象？每个对象的生命周期是长还是短？)

理解底层的GC算法对该系统是否适用于你的测试用例是非常重要的。当然GC系统的实际实现也至关重要。你的基准测试程序的内存占用应该同你将要实现的真正程序类似，这样才能够在实践中检验GC系统对于你的程序而言是否高效。正如前文所说的，Go的GC系统并不完美，但是对于我们的系统而言是可以接受的。

尽管存在一些问题，但是Go的GC表现已经优于大部分同样拥有GC系统的语言了，Go的开发团队针对GC延迟进行了优化，并且还在继续。Go的GC确实是有可圈可点之处，无论是理论上还是实践中。