wPerf: Generic Off-CPU Analysis to Identify Bottleneck Waiting Events

[linxuyalun]

osdi 2018: https://www.usenix.org/conference/osdi18/presentation/zhou

slides: https://www.usenix.org/sites/default/files/conference/protected-files/osdi18_slides_zhou.pdf

[linxuyalun]

性能分析

无论在学术界还是工业界，一个很重要的工作就是做性能优化。性能方面的问题，最常见的就是：

• throughput：系统内部存在的哪些东西使得吞吐量上不去了，比如说 CPU 满了，宽带满了；
• latency：即使是相同的请求，它们处理的时间也是完全不一样的。

想进行上述分析的时候，那么最通用的解决方法就是埋点或者利用一些描述系统状态的工具，那么你就可以找到原因。但是在很多其他的情况下，我们发现这个答案不是特别好找。比如说有的时候你发现系统 CPU 也不高，磁盘空间剩余也很多，网络带宽也没怎么用，但是这个系统就是到瓶颈了，它的速度就再也上不去了。这是什么原因？

举个例子。

比如说写了一个最简单的程序，这个程序只干一件事情，它就做一个这个空的 loop 其他什么事都不干。然后我们就测了一下这个空路的 for loop 它要多长时间。然后我们发现即使对这个不能再简单的程序来说，它的延迟还是不确定的。如下图：

在这个图里你可以看到大概 50% 到 75% 左右的延迟是在 60 微秒。但是还有 25% 左右的这些命令请求下，他的延迟可以高到 95 微秒。那么对于这样一个 empty 的 for loop 说它里面没有什么特殊任务，它也不做内存分配，它又没有 if else。那么对于这样一个程序来说，为什么它的延迟还会不确定，还会有这么高的波动？

论文的研究表明，在很多情况下，它是由这些底层的事件造成的。比如说 OS 层，它可能会把你的线程刮起执行其他线程，可能会有 page fault，那么会要执行中断请求。在 CPU 层比如说 cache miss，现在的 CPU 还可以根据 CPU 的温度或功耗，来动态的调整频率，如果 CPU 的频率变低了，那么你的程序自然就变慢了。比较讨厌的一点，是在应用程序层面来说，这些事件基本都是不可见的，所以会对性能分析造成比较大的影响。

[linxuyalun]

wPerf overview

wPerf 的工作就是识别到底底层的哪些事件造成系统的 throughput 上不去，特别是由底层的等待事件造成的瓶颈。比如说两个线程之间竞争锁，那么一个线程必须要等待另外一个线程，如果用的是常见的这种 pthread 的库的话，那么最终这些等待是由操作系统的底层调度来实现的。那么另外一个典型的例子就是比如说某个线程需要等待 IO 来完成，这些也是通过操作系统底层的调度来实现的。

为了理解，或者为了找到哪些等待事件会造成瓶颈。论文主要需要回答两个问题。

一个是一个很理论的问题，就是说那到底哪些等待事件是比较重要的，一个很 naive 的想法是说是不是比如长的等待时间的事件就是更重要的。

一个是从工程的角度来说的问题，我们怎么样记录这些事件？比如说在 pthread 层记录，或者是在这个系统调度层记录，以得到更准确的信息。

[linxuyalun]

Concrete example

来看一个例子：

假设模拟了一个最简单的 server，A 处理 funcA 需要 2 ms，然后放入一个队列，B 从队列取数据，处理 funcB 需要 5 ms，然后还要做一些 sync 的动作，比如也要 5 ms。假设队列的最大容量就是 1，那么这里的程序瓶颈在哪？

在上图展示的例子中，R1 和 R2 已经被 Thread A 处理完毕了，R1 从 queue 中取出由 Thread B 处理，R2 被放入 queue 中，此时队列满了，A 无法继续放数据，block 住，B 正在处理。

由于 funcB 和 sync 都需要 5 ms，因此这里总共耗费 10 ms。因此，当系统稳定时，其状态图如下：

从这个例子中，我们可以得到几个结论：

1. 等待时间很重要，它可能对吞吐量有巨大的影响；

如果 funB 和 sync 之间可以完全异步，那么吞吐量就可以翻倍。

2. 长等待事件可能没有很重要；

尽管 funcA 一直在等，但其实 A b并不是瓶颈。

3. 竞争并不是等待事件中唯一重要的因素；

在过去，人们可能会认为事件等待长的主要原因是锁争用，这个例子证明只做 contention 是不完备的，还有更多的因素需要考虑。

[linxuyalun]

Key insights of wPerf

1. To improve the throughput, we need to improve all the threads involved in request processing (worker threads).

这里的工作线程指的那些比如 request handling，disk flushing，gc 等；反之那些 background 线程指的是比如心跳处理，死锁检查等。瓶颈事件就应该是那种优化了它就可以提升整体 worker threads 的事件。还是刚刚的例子，如果我们把 flush 全部变成异步了，那么吞吐就会翻倍。因此，这里 sync 是瓶颈。

2. If thread B never waits for A, either directly or indirectly, then optimizing A’s event will not help B.

如果 B 从不等待 A，那么优化 A 对于 B 来说是没有用的。

还是这个例子，不论 A 怎么优化，吞吐量都不会有显著提升。

wPerf 的工作就是结合上述两点，wPerf 不会直接找到瓶颈，而是查找哪些不是瓶颈，然后扔掉，继续查找，逐步缩小范围。

Key idea: narrow down the search space by excluding non‐bottlenecks

[linxuyalun]

Key idea of wPerf

wPerf 的核心思想在于，它把每个工作线程构建成一个图，其中每个线程就是一个节点，如果线程 A 等待线程 B，那么就会存在一个 A 指向 B 的有向 edge。

wPerf 基于的理论是：Each knot with at least one worker contains a bottleneck.

这里的 knot 指的是一个没有 outgoing edge 的强连通图，而优化 knot 之外的 event 没有办法显著提升 throughput。

然而理论和实际往往存在差距，

如右图，每个 node 都几乎存在互相等待，他们整体构成了一个巨大的 knot，在这样的情况下，我们还是没有办法很好的找到瓶颈。那么，我们肯定要想办法缩减这个图的大小，一个直观的解法是给这些 edge 加上一些“影响”。在这里，论文尝试给每个 edge 加上一个等待时间来评估，但是这并不简单，因为我们没法直接通过等待时间确认哪些是影响比较大的 edge，因此，这里的等待事件代表的是优化这条边等待时间的收益上界。即，那些等待时间很短的边，优化意义一定不大，而那些等待时间很长的边，优化它也不一定也用。

然而，即使如此，仍存在一个问题：级联的等待时间怎么办？

举个例子，thread A B C 共用一把锁，B 等待 C，A 等待 B，那么等待时间如下图：

如果是之前的解法那么我们会认为 A 等待 B 的时间是（t2-t0），B 等待 C 的时间是 （t1-t0）:

但是这种方法存在一个很重要的问题，那就是它低估了 B 的重要性 —— 如果我们能够优化 B，那么 A 自然也被优化了。wPerf 采取的办法就是根据级联的次数增加一个倍数，比如在这里 B 存在一个级联 A，那么它的等待时间是 2 倍的（t1-t0）：

结合上述两点，我们得到了 wPerf 的算法流程：

1. 构建 worker threads 的 wait-for graph，每个 edge 带有权重；
2. 通过图算法找到图中最大的 knot；
3. 如果得到的 knot 已经小于阈值，终止算法；
4. 否则移除掉 knot 中 weight 最小的 edge；
5. 回到第 2 步。

这里阈值的设置可以是比如这个 knot 中最小的 weight 已经大于某个值了，说明优化这个边很可能已经可以取到很好效果了。

[linxuyalun]

Implementation

这里还有一些工程上实现的细节，不再次具体展开。主要有以下几点，详细见论文：