减少固定大小缓冲区的最大延迟

最近我在Pusher的博客读到两篇很棒的文章:低延迟、大的工作集和GHC的垃圾收集器:三选二Golang的实时GC的理论与实践 。这两篇文章讲的是Pusher的工程师如何重新实现他们的消息总线的故事。第一篇是发生在Haskell里。在性能测试期间,他们发现在99%那个范围内有一些高延迟。在他们分析代码后,他们能够证明这些延时的尖峰是由GHC的 stop-the-world 垃圾收集器,再加上一个大的工作集(内存中的对象的数目)所造成的。该开发团队随后尝试了GO,得到好得多的结果,这得益于GO的并发垃圾收集器。

我强烈推荐这两篇文章。Pusher的测试是一个很棒的基准测试例子,因为它专注于解决一个真正的挑战,并且基于该项技术是否合适本工作来评估此技术。这是我喜欢的那种评估方式。我发现做一个简单的关键功能的实现非常有用,然后看看它在所需的负荷下的表现,而不是通过一些浅层的模拟基准测试来比较不同的技术,例如在环里传递令牌,或让一个Web服务器返回“200 OK”。这个方法应该能提供“我能用Y有效地解决X吗?”问题的答案。当我第一次评估Erlang的时候,我采用的就是这种方法。10 倍的预期负载模拟真实系统的12个小时测试让我相信这项技术比我所需要的绰绰有余。

接受挑战

阅读Pusher的文章使得我很想知道这个问题的Elixir实现的性能如何。毕竟,底层的Erlang虚拟机(BEAM)一直是给我低的和可预测的延迟的印象,所以加上其他性质,如容错、大规模的并发性、可扩展性、分布式系统的支持,这似乎是一个为该工作令人信服的选择。

所以让我根据Pusher的文章来定义挑战。我将实现一个先进先出(FIFO)缓冲区,它可以处理两种操作:push 和 pull。这个缓冲区由最大尺寸来限定它的大小。如果这个缓冲区满了,push操作将覆盖队列里最老的元素。

目标是为了减少一个非常大的缓冲区(最大20万元素)的push和pull操作的最大延迟。把这最后的目标牢记在心是很重要的。我关心平滑缓冲区操作的延迟尖峰。我不在乎哪种语言给我更好的最坏情况的GC停顿。虽然Pusher的挑战的根本问题是由长GC停顿造成的,那并不意味着我仅仅是换其他的语言就能解决它。正如我将阐述的,依赖于Elixir/Erlang的一些技巧,我们可以完全旁路掉GC,并且将最大延迟带入到微秒区域。

测量

为了测量性能,我决定在一个独立的GenServer进程里运行缓冲区。你可以在这里看到实现代码。

测量利用了Erlang的trace能力。一个独立的进程被启动,它设置了缓冲区进程的trace。它接收push和pull操作以及缓冲区垃圾回收的开始和结束时间。它收集那些时间,并且在被要求的时候生成最终结果。你可以在这里找到它的实现。

trace将导致一些性能损耗。当trace被使用的时候,整个基准测试将是平常花费的两倍时间。我不能说它对报告的时间有多大的影响,但我并不在意它。如果我能够在用trace的情况下获得好的结果,那么在不用trace的情况下,这样的实现足够满足要求了。:-)

如果你不熟悉Erlang,这里的进程指的是Erlang的进程 - 一个运行在同一个操作系统进程里的轻量并发程序,并且和其他Erlang进程没有共享数据。在操作系统层面,我们仍然还是只有一个进程,但是在Erlang虚拟机里,有很多Erlang进程独立地运行着。

这些进程没有共同点,没有共享内存,只能通过发送自己的消息进行通信。特别是,每个进程都有自己独立的堆,并且各自进行自己的垃圾回收。因此,不论tracer进程分配了什么数据都不会给缓冲区进程造成GC压力。只有那些我们确实压入到缓冲区的数据在缓冲区GC期间才被考虑,也因此会影响缓冲区操作的延时。这种方法展示了Erlang非常棒的好处。通过在隔离的进程里运行不同的程序,我们可以在系统中防止在一个进程里的GC压力影响其他进程。我不知道有任何其他轻量级的并发平台提供这样的保证。

测试首先从一个简短的“拉伸”热身开始。我创建了一个最大容量为20万元素(这个数字是Pusher的基准测试里使用的)的缓冲区。然后,我压入20万个元素,接着全部取出来,然后再压入20万个元素。热身结束之际,缓冲区内的数据达到了它的最大容量。

这个时候基准测试开始。我以15个push操作然后跟着5个pull操作为一个周期发起了两百万个请求。因此,缓冲区的大多数操作处于“溢出”模式下。总的来说,1百万个push操作执行在满的缓冲区上,而50万个push操作执行在几乎满的缓冲区上。被压入的元素是1024字节的Erlang二进制数据,而且每一个元素都互不相同,意思就是测试将产生1百50万个不同的元素。

基准测试代码在这里。完整的项目文件在这里。我用 Erlang 19.1 和 Elixir 1.3.4 运行基准测试,我用 asdf 版本管理器来安装它们。测试运行在我的2011年的iMac上(3.4 GHz Intel Core i7)。

函数式实现

首先,我会尝试我所认为的符合Elixir和Erlang习惯的方法 - 基于 :queue 模块的纯函数实现。根据文档所说,这个模块以高效的方式实现双端先进先出(FIFO)队列,它的大多数操作有一个分摊的O(1)运行时间。这个模块的API提供了绝大多数我们所需要的函数。我可以用 :queue.in/2 和 :queue.out/2 来push和pull数据。它没有直接支持设置队列的最大尺寸,但是在 :queue 模块实现这个功能非常简单。你可以在这里找到我的实现。

当我最初读Pusher的文章的时候,我非常肯定,这样的实现会导致较大的延迟尖峰。虽然在Erlang里没有 stop-the-world 的GC,但是依然有 stop-the-process 的GC。一个Erlang进程启动的时候有一个相当小的堆(大约2Kb),如果它需要分配比这个更多的空间,那么进程被GC并且它的堆可能被扩展。要了解GC的更多细节,我推荐这篇文章以及另一篇文章

在我们的测试里,这意味着缓冲区进程将相当快扩展到很大的堆,因为它要容纳20万个元素。那么,当我们压入更多数据并产生更多垃圾,GC将有很多工作要做。因此,我们可以期待有一些显著的GC停顿发生,它们将导致延迟尖峰。让我们核实一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
$ mix buffer.bench -m Buffer.Queue

push/pull (2000000 times, average: 6.9 μs)
99%: 17 μs
99.9%: 32 μs
99.99%: 74 μs
99.999%: 21695 μs
100%: 37381 μs
Longest 10 (μs): 27134 27154 27407 27440 27566 27928 28138 28899 33616 37381

gc (274 times, average: 8514.46 μs)
99%: 22780 μs
99.9%: 23612 μs
99.99%: 23612 μs
99.999%: 23612 μs
100%: 23612 μs
Longest 10 (μs): 21220 21384 21392 21516 21598 21634 21949 22233 22780 23612

Buffer process memory: 35396 KB
Total memory used: 330 MB

这里有大量的数据,所以我将突出一些我发现的最有趣的数字。

我将从缓冲区操作的平均延迟开始。最近平均值这个概念得到一些坏名声,但我仍然觉得它们是有用的度量标准。观察到的平均延迟是6.9微秒,这告诉我,即使缓冲区完全满了,这个实现可以没有延迟地应付大约每秒145000次操作。如果我能容忍一些延迟的变化,而且也不期望更高的请求,那么 :queue 实现应该适合我的需求。

看一下延迟的分布,我们可以看到最大延迟大约37毫秒。这可能是不可接受的,又或者它可能是刚好合适的,这取决于特定的场景。武断地认为这个用 :queue 实现的缓冲区是糟糕的,或者断定它在所有场景下都是可行的,这两种看法都应该是错误的。如果我们知道手头上具体问题的规格和要求,我们就能解释这些数字。

如果你仔细观察push和pull操作的延迟分布,你可以看到在4个9和5个9之间延迟迅速增加,延迟从两位数的微秒区间过度到两位数的毫秒区间。在两百万操作里,意味着我们要经历小于200个延迟尖峰。同样,这是否可以被接受取决于特定问题的约束。

打印出来的GC状态只和缓冲区进程相关。我们可以看到274次GC发生在缓冲区进程里,而且有很高比例的延迟在两位数毫秒区间。不出所料,GC的次数和开始于4个9到5个9的延迟尖峰之间似乎有着很强的相关性。

最后,请注意缓冲区进程的堆大小为何是35MB。你可能期望它大约是200MB,因为缓冲区持有20万元素,每个元素是1024个字节。但是,在这个基准测试里,元素被叫做引用计数二进制数据,它的意思是它们被存储在单独的堆上。缓冲区进程只持有这些二进制数据的引用,而不是数据本身。

当然,缓冲区进程还是有20万引用在它自己的堆上,还和被删除的消息等任何垃圾一起,这些就是引起延迟尖峰的原因。因此如果我只看它和其他语言比较最坏的GC次数的话,Erlang就不够好,并且我可能错误地得到结论,它不适合这项工作。

基于ETS的实现

然而,我可以用ETS表来限制GC。ETS表有很多特色,但是本文我为了简单起见,只讲它们可以当做一个进程内的内存的键值存储来用。当涉及到语义,ETS表没有给表带来什么新的东西(没有双关语义)。你可以用普通的Erlang进程和数据结构来实现同样的功能。

然而,该表有几个有趣的特性,能使他们在某些情况下表现的很好。首先,ETS表的数据被存储在进程堆之外的独立内存空间里。因此,如果我们使用ETS表来存储数据,缓冲区进程就不再需要持有许多引用,这应该会减少它的GC次数。此外,ETS表里的数据在被删除后将立即被释放。这意味着我们可以完全避免在大集合数据上的GC。

我用ETS表来实现的缓冲区是根据Pusher的GO实现来做的。基本上,我用ETS表来模拟一个可变数组,存储 (index, value) 这样的键值对到表中。我维护着两个索引,一个决定我push下一个元素到哪个位置,另一个决定了我从哪个位置pull下一个元素。它们都是从零开始。然后,每次push存储一个(push_index, value)这样的键值对到表中,就将push的索引加一。如果push的索引达到缓冲区最大尺寸,它就被设置为零。同样地,当pull数据的时候,我根据 pull_index 键来读取值,并且增加pull索引的值。如果缓冲区已满,则pull操作将覆盖最老值并增加两个索引,从而确保下一个pull操作将从适当位置读取数据。全部实现代码在这里

让我们看看它的性能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
$ mix buffer.bench -m Buffer.Ets

push/pull (2000000 times, average: 6.53 μs)
99%: 27 μs
99.9%: 37 μs
99.99%: 50 μs
99.999%: 66 μs
100%: 308 μs
Longest 10 (μs): 76 80 83 86 86 96 106 186 233 308

gc (97062 times, average: 5.16 μs)
99%: 10 μs
99.9%: 20 μs
99.99%: 30 μs
99.999%: 44 μs
100%: 44 μs
Longest 10 (μs): 30 30 34 34 34 39 43 44 44 44

Buffer process memory: 30 KB
Total memory used: 312 MB

6.53微秒的平均时间没有比用 :queue 模块实现的更好。不过,延迟尖峰现在小了很多。观测到的最长延迟是308微秒,同时,在5个9的区域,我们已经减到了两位数微秒区域。实际上,在两百万的操作里,只有4个操作的延迟时间大于100微秒。相当不错。:-)

充分披露:这个结果是我运行了几次测试中的最好一次结果。在我的机器上,最大延时有时候略大于1毫秒,而其他数字没有明显的变化。特别是,99.999%总是低于100微秒。

观察一下GC的状态,你可以看到缓冲区进程的GC次数大幅度增加。在用 :queue 模块的实现里,缓冲区进程触发了274次GC,但是这个实现里,我们观察到大约97000次GC。这是为什么呢?记住,缓冲区进程仍然在它自己的堆上管理着一些数据。其中包括了下一次push和pull操作的索引,以及对刚刚被push和pull的元素的临时引用。因此,大量请求到达缓冲区进程,它将产生大量垃圾。但是,给缓冲区的元素被存储在ETS表的单独堆上,缓冲区永远不会维护一个大的活跃的数据集。这与Pusher的结论相符。GC的延迟尖峰与产生的垃圾量无关,而是与活跃的工作数据集的数量有关。在这个实现里,我们减少工作的数据集,保持缓冲区进程的堆很小。因此,虽然我们将触发大量的GC,但是它们耗时都相当短。观察到的缓冲区进程的最长GC时间仅仅44微秒。

最后的思考

因为Erlang的stop-the-process的GC特性,我们可能在一些进程里经历长时间停顿。但是我们有一些选项可以帮我们削减大的延迟尖峰。控制这些停顿的主要技巧就是保持进程的堆很小。一个大的活跃堆加上频繁的传入请求将对GC施加更多的压力,延迟将增加。

在这个特定的例子中,使用ETS帮我减少缓冲区进程的堆大小。虽然GC数量显著增加,但是GC停顿很短使得整体延迟稳定。虽然Erlang肯定不是最快的平台,但是它让我保持我的延迟是可预测的。我构建系统,调优它达到我想要的性能,并且我可以预测到在生产中较少的令人吃惊情况发生。

值得一提的另外两种技术可能会帮助您减少GC延迟尖峰。第一个是将管理一个大堆的进程分割成多个管理更小数据集的进程。这将导致碎片化的GC,并且可能削减GC延迟尖峰。

在某些情况下,你可以充分利用进程终止时立即释放进程内存的事实。如果你需要执行一个分配大量临时内存的一次性工作,你可以考虑使用Process.spawn,它允许你在启动进程时显式地预先分配一个大的堆给这个进程。这可能完全阻止GC在这个进程中发生。你做计算,输出结果,最后终止进程,因此它所有的内存被立即回收而从来没有被GC过。

最后,如果你不能在Erlang里使得你的系统的一些关键部分高效,那么你可以利用进程内的NIF的C编程或者进程外的端口机制,而保持Erlang/Elixir作为你的系统的主平台和“控制面板”。许多选项都在桌面上,这给了我很大的信心,我将能够处理任何我遇到的挑战,无论它可能多么棘手。

原文链接: http://www.theerlangelist.com/article/reducing_maximum_latency