Disruptor 全解析(6)：为什么它这么快 (二) - 神奇的 cacheline 补齐

原文地址：http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-why-its-so-fast_22.html​， 作者是 Trisha Gee, LMAX 公司的一位女工程师。

 

我们多次提到了 Mechanical Sympathy (机器协同？) 这个短语，事实上它甚至是Martin 的博客 标题。它的含义与理解底层计算机硬件的操作原理，然后编程让软件用协同的方式，而不是以违背的方式在硬件上工作有关。

 

关于 RingBuffer​ 与神奇的 cacheline（高速缓存行）补齐，我在 上文​ 提到它以后，收到了不少的评论和问题。因为这合适用画出的漂亮图片来演示——我想，这就是我要解决的下一个问题。

 

Comp Sci 101

 

我喜欢在 LMAX​ 工作的原因之一，就是这里让我在大学和 A 级计算机课程里学到的一切东西在实际上产生意义。常见的，作为一个开发，你可以不理解并且完全抛弃 CPU，数据结构或者 大 O 符号 这些​——我花了整整 10 年职业生涯来忘记这些东西。但是结果证明，如果你的确了解这些知识，并且能够应用这些知识，你就能够写出一些非常巧妙，非常快的代码。

 

所以，这里首先会复习我们在学校学过的知识，并且介绍一些从未学过的知识。请注意，这篇文章包含了大量的过度简化。

 

CPU 是机器的心脏，并且最终由它来执行所有的操作。内存（RAM）是放置你的数据的地方（包括你的程序代码）。我们打算忽略硬盘驱动器（hard driver），网络这些东西，因为 Disruptor​ 的目标是尽可能在内存中运行。

 

CPU 与内存之间有好几层高速缓存（cache），因为即使访问内存也太慢了。如果你正在对一块数据做若干次重复的操作，在执行操作的时候把它加载到一个非常靠近 CPU 的地方是很有意义的（想想一个循环计数器——你一定不想在每次循环中都去内存取出值来递增）。

 

 

越靠近 CPU 的高速缓存（cache），速度越快，尺寸也越小。L1 cache 很小而且速度非常快，紧邻着访问它的 CPU 核心。L2 cache 尺寸要大一点也慢一点，并且仍然只能被一个单独的 CPU 核心访问。L3 cache 在现代的多核计算机上更加常见，它尺寸更大，更慢，并且被单个 CPU 插槽（Slot）上的所有 CPU 核心共享。最后，你拥有一大块内存，由全部 CPU 插槽上的所有 CPU 核心共享。

 

当 CPU 在执行操作的时候，它首先去 L1 cache 查找所需要的数据，然后 L2 cache，然后 L3 cache，最后如果任何 cache 里都没有， 数据就需要全部从内存加载。CPU 访问得越远，操作所需要的时间就越长。因此，如果需要做非常频繁的操作，你最好保证数据在 L1 cache。

 

Martin 和 Make 的 QCon 演示​ 提供了一些高速缓存未命中（cache miss）成本的定性数据：

 

CPU 延时	大约的 CPU 周期	大约的时间 （单位纳秒）
主存 Main memory		~60-80ns
QPI 总线传输 (between sockets, not drawn)		~20ns
L3 cache	~40-45 cycles,	~15ns
L2 cache	~10 cycles,	~3ns
L1 cache	~3-4 cycles,	~1ns
寄存器 Register	1 cycle

 

如果你的目标是让端到端（end-to-end）的延迟只有 10ms，用 80ns 去内存里拿一些未命中的数据将成为很重的一块。

 

Cachelines（高速缓存行）

 

现在要注意的有趣事情，是写入高速缓存（cache）的数据不是独立的——比如，不是一个变量，也不是一个指针。cache 是由 cacheline（高速缓存行）组成的，典型的长度是 64 字节，并且高效的对应内存中的一段地址。一个 Java 长整数（long）是 8 字节，因此在一段 cacheline 中最多能放进 8 个长整数（long）的值。

 

（为了简单起见，我忽略了多级缓存）

 

如果你访问的是一个长整数（long）数组，这很不错——数组的一个值被加载到高速缓存（cache）时，会自动的加载另外 7 个。因此你可以非常快速的遍历数组。事实上，你可以非常快速的遍历在连续的内存块上分配的任意数据结构。我做了一个跳转引用从 非常早的一篇 RingBuffer 文章​ 指向这里，它解释了为什么我们在 RingBuffer 中使用数组。

 

相反，如果数据结构的各项不是在内存中相邻的（链表，我盯着你呢），你就得不到自动 cache 加载的优势。当你访问这个数据结构中的每一项时，都有可能遇到 cache miss。

 

不过，所有自动加载都有一个缺陷。想象一下如果长整数（long）不是数组的一部分。假设它只是一个单独的变量。让我们称呼它为“head”，没有特别的理由。然后再假设你的类（Class）里有另外一个变量紧邻着它。让我们任意的称呼它为“tail”。现在，当你加载“head”到高速缓存（cache）时，你也自动的加载了“tail”。

 

 

这听起来不错。除非你意识到“tail”是由生产者（Producer）写入的，而“head”是由消费者（Consumer）写入的。这两个变量在实际使用中是不相关的，并且事实上它们会被可能运行在两个单独的 CPU 核心上的两个独立的线程访问。

 

 

想象一下消费者（Consumer）更新了“head”的值。高速缓存（cache）中的值变化了，内存中的值也变化了，而其他包含“head”的 cacheline 都失效了，因为在这些 cacheline 中没有储存这个“崭新”的值。记住我们只能在整个 cacheline 的层面处理，没办法单独把“head”变量标记成无效。

 

 

现在有一些进程在另外的 CPU 核心上运行，只是想读一下“tail”的值，结果整个 cacheline 都要从内存重新加载。这样，一个与消费者（Consumer）无关的线程想要读一个与“head”无关的值，但是被产生的 cache miss 减慢了。

 

当然，这样更糟糕——如果是两个独立的线程写入同一个 cacheline 上两个不同的变量。每个 CPU 核心都会失效另一个 CPU 核心上的 cacheline，并且不得不在另一个线程每次更新后都重新加载 cacheline。基本上，你已经在这两个线程之间造成了写争用，即使它们访问的是两个不同的变量。

 

这叫做“伪共享​”，因为每次访问“head”你也会拿到“tail”，而每次访问“tail”，你也会同样拿到“head”。所有这一切都发生在幕后，没有编译器警告会告诉你刚刚写的代码在并发访问时会变得非常低效。

 

我们的解决方案——神奇的 cacheline 补齐

 

你会看到 Disruptor 解决了这个问题，至少是在 cacheline 大小为 64 字节或更小的处理器架构下。方法是通过添加补齐来保证 RingBuffer 的序号不会与其他数据共享同一个 cacheline。

 

    public long p1, p2, p3, p4, p5, p6, p7; // cache line padding

    private volatile long cursor = INITIAL_CURSOR_VALUE;

    public long p8, p9, p10, p11, p12, p13, p14; // cache line padding

 

所以这里不会产生伪共享，不会与其他变量意外冲突，也没有不必要的 cache miss。

 

在你的 Entry 对象里这样做也是值得的——如果有不同的消费者（Consumer）写入不同的字段，你也需要保证在每个写入的字段之间没有伪共享。

 

更新：Martin 写了一篇从技术上更加准确和详细的描述 伪共享的文章​，并且发布了性能测试结果。