互斥锁真的慢吗¶

标题：The Cost of Concurrency Coordination

日期：2026/03/25

作者：Jon Gjengset

链接：https://www.youtube.com/watch?v=tND-wBBZ8RY

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

备注一：中文标题用的是幻灯片内的标题。简单来说，作者的意思是慢不慢跟你的锁没关系。不过他这里提到的 left/right 我总感觉就是常见的双缓冲啊。

备注二：关于这方面的话题，我的观点永远是 perfbook is all you need.

备注三：早在一月份我就打算在主站发一篇文章说下 folly 做的分布式互斥锁，实现比这个有意思。但是 opus 给的神秘命令行，意外把我 jekyll 环境爆破了，有空再更吧。且听🐉吟！

引言：互斥锁（Mutex）真的很慢吗？¶

谢谢大家。大家好，我是 Jon。就像刚刚介绍里用几句优美的话描述的那样，这就是我。我今天来这里是为了深入探讨一些相当极客、底层的内容，希望你们都会喜欢。这次演讲并不是专门针对 Rust 的，尽管我做的很多工作都和 Rust 有关。但碰巧的是，关心 Rust 的人往往也非常关心并发、并行、速度、数据系统和算法等问题。我有一种感觉，在座的各位即使不是因为 Rust 编程语言，也同样关心这些类似的问题。我希望这次演讲的内容能有更广泛的适用性。

你们会在几张幻灯片上看到一点点 Rust 代码，但我相信你们能够认出它们，并在脑海中将其映射为你偏好的任何语言。这次演讲的标题是《互斥锁（Mutexes）很慢吗？》。有一个被称为“顾德里奇新闻标题定律”（注：应为贝特里奇标题定律）的说法指出：任何这类以问号结尾的标题，你都可以用“不”来回答。毫不意外，这个问题的答案也是“不”——但这背后的原因却非常有趣。

因为我们所有人都曾观察到（或者至少大部分人观察到过）互斥锁很慢，程序的运行速度被拖慢了，因为它卡在了获取互斥锁上，或者互斥锁加载的时间长得不可思议。那么，既然我已经观察到它们很慢，我又怎么能声称它们不慢呢？

事实上，如果你深入探究并询问人们互斥锁是用来做什么的，你会听到诸如“互斥锁很慢”之类的说法。你还会听到“你应该使用读写锁（Reader-Writer Locks）作为替代方案。如果你有大量读取的工作负载，只管用读写锁，这样你就可以拥有任意数量的并发读者，整个世界都会很美好，一切都会很快。”你甚至还会听到“无锁（Lock-free）数据结构是最好、最快的”这样的断言。

你可能会想：“无锁数据结构到底是什么意思？”但同时，锁到底是什么？好，锁就是互斥锁，但互斥锁又是什么？在 CPU 层面到底发生了什么？这就是我们今天想要深入挖掘的内容。我希望能给大家建立一种直觉：当你拿到一个特定的并发算法时，它将会有怎样的性能表现？如果它真的慢，为什么会慢？以及“慢”到底意味着什么？

而现实情况（这里先给大家一个小剧透）是：这很复杂，充满着微妙的细节。在更底层的地方有很多因素在影响着它们为什么会变慢。

基准测试：读取共享计数器的性能表现¶

我们在这里要使用的测试其实非常直接。我们将设置一个计数器，然后去读取这个计数器。没有任何操作会去更新它，我们只是单纯地读取。我们将尝试从非常多的线程并发读取它。

虽然这原本是 Rust 代码，但基本思路如下：你有一个共享的计数器，在这里它是一个原子引用计数器（Arc），通过它你可以让许多线程指向同一个计数器。然后在一个循环中，我们对该计数器加锁，接着读取它。

// 伪代码示例：
let counter = Arc::new(Mutex::new(0));

// 在多个线程的循环中：
loop {
    let guard = counter.lock().unwrap();
    let value = *guard; // 执行读取操作
    black_box(value);   // 提示编译器不要优化掉这段代码
}

这里我使用 black_box（黑盒）的原因是为了确保编译器真的会执行这次读取。否则，编译器会把这段代码优化成一个什么都不做的空循环，那样我就根本没有获取锁，也就测不出任何有意义的数据了。

接着，我将并行运行大量这样的线程。并且，因为没有任何写入操作，所以这肯定应该很快对吧？让我们来看看如果我们在这里尝试使用互斥锁会发生什么。

第一张图表非常容易看懂。当只有 1 个线程时，图表的起点非常高。大约达到了每秒 2.5 亿次操作（即每秒 2.5 亿次读取）。如果你有一个 2.5 GHz 的 CPU，这意味着你大约只花了 10 个指令周期来获取锁并完成读取。这非常出色。

但是，当增加到 2 个核心时，性能直接骤降到了原来的十分之一。从每秒 2.5 亿次操作掉到了约 2500 万次。图表呈现出断崖式下跌。而之后随着你添加更多的线程，曲线几乎变平了。它稍微又下降了一点点，然后就停留在非常、非常低的位置。

这可能会让你得出结论：“好吧，互斥锁确实很慢。这可是一段只做读取操作的代码啊！互斥锁到底在干什么？为什么我仅仅是增加了线程，它就变得这么慢？”

你可能会认为，互斥锁顾名思义是“互斥”（Mutual Exclusion）的，它只允许一个线程在同一时间取得进展。所以你本来就不指望它会随着线程数的增加而变快，但你至少期望它能保持不变，对吧？互斥锁应该在任何时候都允许一个操作正在发生。然而图表看起来并非如此。相反，更多的线程给你带来了更糟糕的性能。

那么，如果换成读写锁（RwLock），情况会怎样呢？这里有另一张图表，这张图表也很容易解释，因为图中有两条线重叠在一起。当你依然只获取读锁，且只进行读取操作时，随着线程数的增加，读写锁的初始性能非常好，大约和互斥锁一样。然后，它也变差了约 10 倍。虽然它最终的表现比互斥锁稍微好一点点，但正如你将在图表上看到的，读写锁的性能实际上随着时间的推移（线程数的增加）在持续恶化。随着你添加更多的读者，读写锁最终会变得比互斥锁还要糟糕。互斥锁在骤降后好歹稳定变平了，而读写锁却越来越差。

在这里，我想考考大家，看看你们对这种现象是否有直觉上的解释。我本次演讲的目的或期望就是，大家目前的答案是：“我真的不知道为什么会这样，这太奇怪了。”而我希望能尝试告诉你们为什么它会表现成这样，以及为什么这实际上完全符合我们的预期。

显然，这里面还有其他事情在作祟。为了理解这个潜在的问题，我们需要谈谈 CPU 缓存（CPU Caches）。

揭秘底层原因：CPU缓存与MESI协议¶

正如我所说，那张图表显示性能一开始很高，然后变差，接着保持平稳。随后我们看到一张同时展示互斥锁和读写锁的图表（蓝线代表读写锁）。你会看到它一开始比互斥锁略差，但没有下降得那么猛烈；但随着读取线程的增加，读写锁跌得比互斥锁还要惨，而互斥锁则相对稳定下来了。

这就是我们需要讨论 CPU 缓存的地方。CPU 缓存是内置在 CPU 中的组件，目的是让访问存储在 RAM（主存）中的数据变得更廉价。因为存储在 RAM 中的数据距离 CPU 实在太远了——在物理的铜线距离上非常遥远。访问一次主存可能需要花费你几百个指令周期。对于 CPU 来说，几百个指令周期犹如永恒。

所以，你想把一些内存放在离 CPU 更近的地方。但离 CPU 越近，空间就越小。你无法把太多的内存放在那里，你必须非常精打细算地使用实际的物理空间。因此，CPU 实际上拥有一种缓存层级结构（Cache Hierarchy）。

这在不同的 CPU 上会有些许差异，不同的 CPU 有不同的架构设计。但通常拥有三级缓存是非常常见的：

L1 缓存：离 CPU 非常近，就像是直接焊在 CPU 核心上一样。且 L1 缓存是不共享的。
L3 缓存：距离 RAM 相当近。它不像 RAM 那么远，但比 L1 远。通常，L3 缓存是在你 CPU 的所有核心之间共享的。
L2 缓存：取决于 CPU。它位于 L1 和 L3 之间，延迟也介于两者之间。

随着层级往上（远离核心），它们的大小也会增加。L1 缓存非常小，L2 稍微大一点，L3 相当大。而 RAM 当然是众所周知的庞大。

那么，如果一个 CPU 核心在它的本地缓存中存有一段内存（比如我们正在讨论的那个计数器），而另一个 CPU 核心想要读取那段内存，会发生什么呢？

它们之间需要有一种缓存一致性协议（Cache Coherence Protocol），来协商谁被允许在什么时候写入数据，并确保正确的值最终能回写到 RAM 中。这个协议叫做 MESI（M-E-S-I）。

它有很多变体，比如 MSI、MEISI，还有各种字母组合的协议，但大多数都是类似 MESI 的。MESI 代表四个状态：Modified（修改）、Exclusive（独占）、Shared（共享） 和 Invalid（无效）。这就是缓存在某条目上可以拥有的四种状态。

缓存会在逻辑上为每一块内存（你可以认为是 RAM 中的每一个地址）保留一个条目。但实际上并非精确到每一个地址，而是按内存块来划分。CPU 有“缓存行（Cache Lines）”的概念。它将所有的主存划分为 64 字节（Bytes）的块，这些 64 字节的块就是一个缓存行。可以想象把 RAM 平铺开来，前 64 字节是一个缓存行，下一个 64 字节是另一个缓存行，依此类推。

缓存是在缓存行的边界上对内存进行追踪的。它追踪哪个 CPU 缓存对哪个缓存行拥有独占访问权，或者哪些 CPU 核心共享对某个特定缓存行的访问权。

接下来是非常有趣的部分：

Modified（修改）：这意味着我拥有唯一的副本。如果它在一个 CPU 核心的缓存中被标记为 Modified，说明我是唯一的持有者，并且它是“脏”的（即它和 RAM 中的值不同）。这意味着如果其他任何人想要读取它，不仅我需要放弃我的权限，我还必须将其回写到别人可以读取的地方。
Exclusive（独占）：意味着我拥有唯一的副本，但它不是“脏”的（未被修改）。如果其他人想要它，他们可以直接拿走而无需先跟我通信；或者他们可能需要确保我将我的状态改为 Invalid，但他们不需要从我这里获取任何数据更新，因为数据没有改变。
Shared（共享）：意味着多个缓存都拥有这个条目。这些缓存条目里的数据全都是相同的（一致的）。否则 Shared 就是非法状态。
Invalid（无效）：意思是我没有这个缓存行的有效副本。这可能是因为它曾经在我的缓存中，但我现在不被允许使用该缓存行条目了。比如它已经被交接给其他人变成了独占状态。

如果你是一个核心，你处于 Shared 状态持有某个特定的缓存行，并且你想要向它写入数据，协议要求你必须先确保没有其他人处于 Shared 状态，必须让它变成只有你持有，然后让所有人都知道你现在将其转移到了 Exclusive 状态。到了那个阶段，你才可以随心所欲地读写。你不需要每次修改时都通知别人，即使你进行了多次修改。最终，如果有人想修改或读取那个缓存行，他们必须通知你将其转回 Shared 状态，以便他们能获取一个可以读取但不能写入的副本。

读写锁（RwLock）为何随线程增加而性能急降？¶

这里有一个非常有趣的观察：向共享数据写入需要核心之间的协调同步。

如果我有一个共享版本的缓存行并想修改它，我基本上必须和所有其他核心通信，因为我需要确保他们知道不要修改它，并且知道也不要读取它。这就是部分开销的来源。这其中有大量的跨核心通信（Cross-core communication）。

事实上，如果我们来看看读写锁（Reader-Writer Lock），获取读锁的内部实现实际上是：将读者数量加 1。锁的内部有一个计数器（注意，不是我们正在跑基准测试读的那个计数器，而是锁内部自身的计数器），用来追踪当前有多少个读者线程。为了获取读锁，你必须对那个计数器进行写入操作。

因此，如果你有 100 个线程都想获取读锁，它们全都在对一个共享字段执行写入操作。这意味着每个核心在某个时刻都需要将那个缓存行变成 Exclusive（独占）模式，更新它，然后再让它变回 Shared（共享）。然后下一个想要读取锁的核心需要将它设为独占模式，修改它，然后再共享它。这 100 个核心全都要经历这个过程。所以从某种意义上说，你可以认为每个读写锁中都有一个“顺序执行”的部分。当然，做完这一步之后，你就不必再和其他核心对话了，但这仅仅是为了“加锁”这个前置步骤！

让我们来看看具体过程是什么样的。假设我们有两个读者试图获取读锁。这里有 Core 0 和 Core 1。我们用 S 代表它们正在操作的缓存行的状态（无论那是什么），然后我们来看发生了什么。

最初，假设 Core 0 对此缓存行有独占（Exclusive）访问权，而 Core 1 没有有效条目（Invalid）。
Core 0 想要执行 fetch_add（获取并累加，因为它想获取读锁）。这很简单，它拥有独占访问权。所以它只需将状态标记为 Modified，然后把计数器加 1。没问题，没有跨核心通信。
现在 Core 1 想要获取锁。它观察到缓存中的这个条目已经被 Core 0 标记为 Modified。因此，现在必须进行一次从 Core 0 的缓存到 Core 1 缓存的回写（Writeback），以通知其更新的值，因为在第 1 步中值被更新了，这个修改必须传递给 Core 1。当这一切发生时，协议会有各种优化（比如你不需要非得经过 Shared 状态），你可以直接把数据连同所有权一起移交给对方。
到这里，Core 0 变成了 Invalid 状态，而 Core 1 变成了 Modified 状态，因为它执行了它的 fetch_add。
然后，Core 0 想要释放它的读锁（减 1 操作）。好，整个过程再次重演。现在我需要 Core 1 写回到 Core 0，以便 Core 0 能处于独占状态并递减读者计数器。

我们看到了什么？对于每一次“我想要获取锁再释放锁”的操作，实际上需要进行两次缓存行传输（Cache Line Transfers）。 一次是为了获取权限执行加法，一次是稍后获取权限执行减法。

而这些状态转换的每一次开销大约是 30 纳秒（ns）。这种“缓存行乒乓效应（Cache Line Ping-Pong）”最终变成了一个非常昂贵的操作。因为与不同部位的内存通信需要花费不同的时间，它们距离核心的距离不同。你可以看到：

如果想访问 L1 缓存中的东西，大约是 1 纳秒。几乎不花时间。
但如果你必须进行跨核心通信（也就是你要进行缓存行传输时必须做的），那大约需要 30 纳秒。

现在想象一下我必须做两次这种传输（一次获取一次释放），在理想情况下那也就是 60 纳秒了。你要知道，访问主存（RAM）需要 100 纳秒，那可是我们认为 CPU 耗时“极长”的操作。而仅仅是通过获取一个读锁，我们就已经花掉了一半以上访问主存的时间！

另一件我认为非常有趣的事情是，对于普通的互斥锁（Mutex），情况并没有那么糟。对于互斥锁，当你获取锁时，你持有了锁，你明确知道没有其他人会尝试递增那个计数器——因为他们根本获取不到锁。从某种意义上说，问题出在“读锁”上。如果你拥有的是排他锁（互斥锁），当你释放时，你确信你仍然是它的所有者。其他人可能拿到过共享副本，但绝不会有独占副本，他们没有需要回写的东西，因为他们所能做的只能是读取。

这就是为什么在这里读锁的伸缩性（Scaling）实际上比互斥锁还要差的原因。 这也是读写锁图表呈下降趋势的原因——随着读者越来越多，它们彼此之间的竞争也越来越激烈。相反，如果你有许多互斥锁在运作，它们其实不怎么相互竞争，因为它们很乐意老老实实地排队按顺序一个接一个来，而不会引发所有这些缓存行乒乓效应。

人们通常不去思考这个问题的理由是，在常规使用锁的场景中，你会在锁的内部执行一大堆代码。你获取锁，跑一大段代码，然后释放锁。所以“获取锁”的开销其实并没有那么重要。

但是，如果你的临界区（Critical Sections）非常短——比如在获取锁和释放锁之间只有极少的代码——这就不成立了。如果是这种情况，你会发现因为缓存未命中（Cache Miss）所花费的时间，比你运行自身代码的时间还要长。总的来说，你越需要这个锁跑得快，使用锁的开销占比反而会上升，这和你想要的正好成反比。

对于长时间的操作，互斥锁完全没问题，随便你怎么用。但这主要发生在当你触及那些关键路径的热循环（Hot Critical Path Loops），你明知道有竞争，你需要用互斥锁来处理竞争，但互斥锁在短促的高频竞争中却表现得很差。这也是为什么现实世界中的代码倾向于不太担心这些问题，只有当你开始在这些极深的热循环中编写高度专业化的代码时，你才需要开始了解诸如 MESI 之类的东西。

替代方案探索：Left-Right 数据结构¶

现在我想岔开一下话题：那么，你能用什么替代呢？如果你既不能用互斥锁，也不能用读写锁，你能用什么？

我并不是在主张这个方案就是所谓“绝对正确的算法”。我稍后会提到，它也有很多自己的权衡（Trade-offs）。我只是想在大家脑海中植入一些其他替代方案的想法，让你们思考还能怎么做，以避开缓存行竞争的问题，尽管它可能带来另一些问题。

我想给大家介绍的是 Left-Right（左右）数据结构。这是我在攻读博士期间研究中使用的东西。当时我有海量的读取操作，但几乎没有写入操作。我基本上就撞到了刚才说的那个问题。当时我在持有读锁时做的全部操作仅仅是一次 HashMap 的查找，别无其他。所以读取过程极短。读锁的开销简直要了我的命。所以我需要别的方案。

有趣的是，它试图解决的问题是：为什么所有的读取者都需要访问一个“共享的缓存行”？感觉上，既然读取者应该是相互独立的，它们就应该拥有各自独立的缓存行，而不是共享一个。

那么，如何设计一个并发原语，它既能够安全地处理多个读取者和一个写入者，又能做到读取者开销极低，而把更多的工作推给写入者呢？因为我的写入发生得相对较少，所以只要能让读取者高度并行，我是愿意在写入端堆砌更多开销的。

Left-Right 的工作原理是：

你保留两份数据副本。一份 Left（左）副本，一份 Right（右）副本。
你在中间放一个指针（一个原子指针），每一个读取者和那个写入者都能访问这个指针。这个指针指向读取者应该去读取的那一方（副本）。
写入者永远只修改指针没有指向的那一半副本（未被读取的副本）。
当写入者对它所拥有的那部分副本（比如 Left）完成了一系列修改后，它就翻转那个原子指针，让它指向这边（Left）。
当指针翻转到另一边时，现在所有新来的读取者都会开始读取另一侧（Left），而写入者最终就可以开始修改之前被读的那一半（Right）了。

这里的核心意图是，读取者们可能根本不需要协调。因为写入者并不关心读取者在干什么，除了唯一的一点：写入者需要知道，它什么时候才能安全地去修改刚刚被切走的那一半副本？

想象一下：你有一群读取线程正在读取左副本（在我们翻转指针之前）。然后写入者翻转了指针。那些旧的读取线程仍然还在左副本里面操作！所以，必须有一种机制来告诉写入者：“所有的读取者都已经读取了更新后的指针值，它们现在都在右副本里了，所以你现在可以安全地去修改左副本了。”

在这里，我们需要某种同步原语。事实证明，你可以通过给每个读取线程分配它们自己的缓存行来实现这一点。每个线程都有一个属于自己的计数器，基本上记录了它们读取指针的次数。

那么写入者的工作将变成：检查每个读取线程的计数器。它执行一个巨大的 for 循环，遍历所有存在的读取者，读取它们各自独立的计数器，并观察到它们所有人的计数器自指针交换以来，至少发生了一次变化（至少增加了1）。这之所以有效，是因为当你交换指针后，你读取所有的计数器；当这些计数器至少改变了 1 次时，意味着那个读者已经读取了最新更新的指针，正在执行第二次操作；如果它读取了新指针，它就不可能还在原来那个旧的映射表中。

这个设计最有趣的地方在于：读取者之间不再共享状态。 读取者只维护自己的计数器（读指针的次数）。它们不需要互相通信。换句话说，回想 MESI 协议，这意味着运行任何给定读取线程的 CPU 核心，可以单纯地将那个缓存行保持在 Exclusive（独占）状态。永远不必进入 Shared（共享）状态！除非当写入者想要切换指针时——那时，运行写入者线程的 CPU 核心必须去读取每个读者的计数器，把它们变成共享状态读取值，然后再交还给读者去更新。但只有当写入者想要与读取者产生竞争时，才会干扰读取者想做的事。在其他任何时候，读取者都是完全独立的。

甚至更好的是，读取者现在不需要等待任何东西。它们完全不等待。即使存在并发写入，它们也可以继续读取它们手头的副本。所以这里的读取是无锁的（Lock-free）。读取操作不会因任何情况而暂停。事实上，它们是无等待的（Wait-free）。它们根本不等待。它们不拿任何锁，也没有循环。它们只是读取指针，递增自己的计数器，然后访问数据。这就完事了。

其最终结果是，你可能会得到一张像这样呈线性飙升的图表！在这张图中，当你增加线程数时，性能曲线完美地向右上方爬升，这正是你梦寐以求的。我们现在有足够的直觉来理解为什么会这样：因为运行读取线程的 CPU 核心根本不需要协调，因此可以完全并行地运行。

(观众提问环节预演的回答) 如果某个线程由于某种原因处于休眠状态，或者正在处理繁重的工作，它们就只是一直持有旧的引用而不增加计数器吗？这会是一个问题吗？ ——这个算法其实比我刚才讲的稍微复杂一点。具体的算法是：读者在开始操作前会增加一次计数器，在操作结束时再增加一次。所以写入者需要寻找的是计数器增加过的读者，或者是计数器为偶数的读者。这样你就知道，处于休眠状态（不在临界区内）的读者并不是问题。那些死死抓住访问权不放的读者确实是个问题，因为它们会阻止写入者去修改另一边。但这不会阻止其他读者继续读取，它只是阻止了对映射表的更新。

接着你会观察到，这里的性能数字非常高。我们能达到大约每秒 30 亿次读取操作。之所以这么高，是因为我们大约用了 10 个核心，所以性能大约是 1 个核心时的 10 倍。而这绝对不是你在读写锁（RwLock）那里能得到的（尽管读写锁的名字暗示你可能应该得到这样的缩放比例）。

然而，此方案的关键在于：它只有在写入操作极其罕见的情况下才有效。 如果写入很罕见，它表现得非常好，极度出色。因为在这个系统中，只有写入操作才会引发竞争。另一方面，如果写入并不罕见，它的表现不会比读写锁更好。事实上，如果反转比例（写入操作多于读取操作），这玩意的表现会更糟。因为写入者必须做一大堆工作，而你根本无法享受到读者低竞争带来的性能红利。

为什么这里读写锁的图表（对比图）依然呈下降趋势呢？其直觉解释还是我们之前谈到的：读写锁随着读者数量的增加，惩罚会加重。在这里读者数量是那里的九倍，所以在这种情况下，因为读者相互竞争更激烈，你会预期到明显的降速。

调试故事：伪共享（False Sharing）陷阱¶

我想给你们讲一个调试故事，因为这里有一个非常有用的洞察。

在为 Left-Right 跑基准测试以生成那张“向右上完美线性爬升”的图表时，我发现它本来并没有一直向右上爬升。图中出现了一个诡异的下跌（Dip），我本以为它会一直保持线性，结果在到了 4 个核心的时候，性能显著下降了——暴跌了大概 10 倍。

我当时想：“为什么会发生这种事？不应该啊！这完全不符合我对 CPU 工作原理的直觉！”

结果发现，问题并不是什么“跨越到了新的 CPU 架构”，或者是“访问了物理距离更远的 CPU 封装”之类的。我在脑海里过了一遍各种关于底层的猜测。但事实证明，原因非常简单。它是当你在这个层面处理并发时最先学到的东西之一。

这就叫 伪共享（False Sharing）。

伪共享之所以发生，是因为正如我们所说，缓存并不是在单个内存地址的粒度上操作的。它在缓存行（64 字节）的粒度上操作。而一个普通的计数器很小，64 字节里面可以塞下好多个计数器。

所以，如果你运气不好，不同线程的计数器（我说的是 Left-Right 内部的那个用于追踪的计数器）落在了同一个缓存行里，那么就算线程 A 只修改自己的计数器，线程 B 只修改它自己的计数器，这也是徒劳的——由于它们都在同一个缓存行上，MESI 的所有权判定是基于整个缓存行的。所以当一个线程写入，另一个线程也写入时，缓存行依然会在不同核心之间反复弹跳（Bouncing），哪怕它们更新的是同一个缓存行里毫不相干的独立部分。

那么修复方案是什么呢？就一行代码。就是为你存放计数器的类型添加 64 字节对齐（64-byte alignment）。因为这样一来，它们就必定位于不同的缓存行上，问题立刻迎刃而解！就这么简单。目前最新发布的 Left-Right 版本已经包含了这个修复，所以如果你现在去用，它也会为你呈现向右上完美爬升的曲线（顺便提一下，我是把这个修复提交给我自己维护的上游仓库的）。

这就引出了一个极其重要的区别： 无锁（Lock-free）并不意味着无竞争（Contention-free）。

仅仅因为没有使用传统的锁，并不意味着 CPU 就不会因为你让内存在总线铜线里疯狂搬运而惩罚你。跨越物理铜线转移数据是极其昂贵的。如果你能避免这么做，你的程序就会跑得更快。这也正是为什么了解这些底层知识十分重要，去培养一种直觉去判断“为什么这个东西的表现是这样？”或者“为什么它没有达到我预期的表现？”并在使用诸如 perf 等工具无法直接给出答案时（因为出问题的地方在于 CPU 之间对话太过频繁，这已经超出了我们通常推理的抽象层级），能够凭借直觉去进行调试。

权衡与总结：如何为你的场景选择并发原语¶

我希望这次演讲传递给你们的核心信息是：我希望你们能开始更明智地做选择。

如果你必须编写需要高度并行、高度并发，且位于关键热循环中的代码，你绝对不能随便拿起你找到的第一个算法就用。即使它在某些性能评测里名列前茅，或者你在 crates.io（Rust 包管理器，或对应语言的包管理器）上看到它号称是“最快的互斥锁”、“最快的读写锁”并直接套用，这都是不可取的。

现实情况是，你必须选择最契合你应用程序数据传输模式的算法。 我们让并发程序变快的方式，是选择与你的程序运行逻辑相对齐的算法。你要利用你自身工作负载中存在的每一个奇特属性，所有这些特性都可以被利用，将算法调配得略微偏向你的特定使用场景。

Left-Right 在这里就是一个绝佳的例子。它绝不是一个通用的直接替换品（Drop-in replacement）。Left-Right 做了很多大多数应用程序根本不想做的事情：

内存翻倍：显然，它需要保留你所有数据的两份副本，这是相当昂贵的。
读到陈旧数据：读取者可能会看到旧数据！写入者修改了东西并且认为修改完成了，但读取者直到下一次指针交换并再次读取时，才能看到新数据。Left-Right 确实提供了一种机制，允许写入者阻塞并等待所有读者切换过来，但这给写入方增加了额外的开销。
单写入者限制：Left-Right 只能支持单写入者，你不能有多个并发的写入者，它的设计前提只有一个。如果你想要多写入者，你必须在写那一端再套上一个互斥锁。而一旦你在一个并发数据结构之上叠加互斥锁，你大概率会得到一个悲剧的性能。虽然可以实现，但这违背了它的设计初衷。
操作必须是确定性的（Deterministic）：你不能随便拿一个任意的数据结构就把它做成支持 Left-Right 的。原因在于这种左右分离的模式：想象一下，你对“左副本”（当前是你的操作区）做了一系列修改，然后你把指针切换过来。现在你需要拿起“右副本”，并把你在左副本激活期间应用的所有变更，重新应用到右副本上，因为右副本现在已经“过时”了。这意味着你必须能够记录（维护一个操作日志）哪些修改被应用到了这里但尚未应用到那里，然后你需要将它们应用过去，并且它们必须产生完全一致的结果。否则，你会导致两份副本状态不一致，读取者就会产生严重混乱。所以，只有当你能维护确定性影响的修改日志时，你才能使用该数据结构，并非所有数据结构都具备这个特性。
写入者等待：写入者必须等待所有阅读者退出临界区。这可能是一个问题，也可能不是。也许你其实希望系统能在大量读取进行时任意进行大量并发写入而毫不关心旧数据，也许那正是你想要的更弱语义的应用程序。如果是那样，你完全可以自己设计一个更快的数据结构。

正是你需要处理的这些细微差别，决定了你最终获得的性能。 Left-Right 还有一些其他限制，比如它不是线性一致性的（Linearizable），它只是最终一致性的（Eventually Consistent），这依然取决于你的容忍度。例如，我绝对不会在“金融交易”中使用 Left-Right，但我会在诸如“缓存（Caches）”、“路由查找（Lookups）”之类的地方使用它。具体情况具体分析。

这里的真理是，每种解决方案都有它自身的妥协与权衡。互斥锁在大量并发算法中就是最正确的选择；正如读写锁在另一些算法中是最正确的选择；而 Left-Right 在某些特定场景下是完美的选择。一切取决于你的具体需求。这才是我想让你们带走的核心观点。

我建议你们在选型时尝试问自己以下几个问题：

我的读取和写入的比例是多少？ 这极大程度影响了你应该选择哪种算法。
我需要同步执行的代码片段有多长？ 是短促还是漫长？这决定了你能够在同步（加锁）开销上分配的性能预算。
我将拥有多少个线程？ 如果你只有 3 个线程，那刚才讲的这堆东西几乎全都无关紧要。如果你只关心 2 个线程比 1 个线程快就行，那可能稍微有一点关系；确实，就像那张图表显示的骤降一样它有影响。但通常在极小规模的并发下，这些底层细节不会成为痛点。
我能容忍最终一致性吗？ 我的读写之间是否需要强一致性？例如，我是否需要能够“读到我刚写的内容（Read-my-own-writes）”？假设我作为写入者刚刚修改了数据结构，立刻去读取，我能保证读到刚写入的值吗？Left-Right 不能提供这种保证（因为你写完可能会被指针指引去读尚未更新的另一张旧图）。如果你需要这个保证，就必须把它纳入算法设计的考量中。
我需要线性一致性（Linearizability）吗？ 你是否需要对两个线程之间可能看到的交错执行路径做出极为严格的保证？

我今天不可能教完大家所有这些并发模型，更多的是抛砖引玉，告诉你们如果想要跳出“仅仅使用现成的标准库并发算法”的局限，你们应当去思考哪些问题。

在开始着手优化这些东西之前，一定要先进行测量（Measure）。 最终的教训是，问题的核心根本就不在于“锁”。自始至终都不是锁本身的问题。由于缓存一致性（Cache Coherence），协调（Coordination）注定是极其昂贵的；因为 CPU 为了保证你的程序正确执行，必须在底层疯狂交互。你所抱怨的锁，仅仅是你碰巧正在使用的顶层接口罢了。

CPU 缓存还有很多其他可能会“烧毁”你程序性能的方式，而以上讲的这种（缓存行竞争），是最有可能让你结结实实栽个跟头却还不明就里的一种。

推荐几篇讨论这些细节的实用文章：

有一篇分析 CPU 内各种操作耗时的文章非常棒，它对比了比如从磁盘读取、访问 L2 缓存、发送 TCP 数据包，以及向世界另一端发送 TCP 数据包各需要多少时间？它们的相对时间刻度是怎样的？
还有一些关于你可能利用的其他数据结构的文章。比如有一篇关于**可扩展读写锁（Scalable Reader-Writer Locks）**的，讨论了如何改造读写锁：你不弄一个全局读者计数器，而是为“每个核心”设置一个计数器。这样一来每个读者只修改本地核心的计数器，几乎所有操作都变成核心本地的了。然后只有写入者才需要去遍历统计所有核心的计数器。也许这种设计更契合你的用例。

最后，我希望你们能花点时间读读这些材料，从而对权衡空间的面貌以及你们想要编写高并发代码时所拥有的选项有一个更清晰的认知。

这就是我今天演讲的全部内容。谢谢大家。

现场问答（Q&A）¶

(听众提问听不清，讲者复述) 问：刚才在中间其实有一些问题，你现在有问题要问吗？这不确定能有多大帮助，但在并行编程的硬件创新方面有没有什么有趣的进展？比如有没有人发布了新的原生硬件指令，能让互斥锁这类东西直接快上 10 倍？

Jon： 我不能说存在某种“革命性”的新东西让整体工作负载突然变快了 10 倍，但确实有一些演进。比如 MESI 协议最早是 MSI 协议，后来他们加入了 E（Exclusive，独占状态），因为他们发现某些特定的工作负载只需加入这个状态就能避免一半以上的缓存行竞争。我认为在某些现代 CPU 架构中，他们甚至把这个协议的字母扩展到了七八个状态（注：如 MOESI）。

部分问题在于，这些通常是专有协议（Proprietary Protocols）。我们知道它们的存在是因为它们记录在 CPU 的规范手册里，但芯片厂商不会告诉我们 CPU 内部确切是怎么实现的。他们只是告诉我们一个用于思考和推理的抽象模型。一些早期的版本是公开的，但近期的版本我们并不知道 CPU 到底在做什么微操，只能大体推断它就是这么运作的。所以目前还没有看到那种让我们大呼“这太疯狂了”的公开底层指令。

我想最接近你说的“创新”的，是他们在制造 CPU 封装时在 3D 堆叠上所做的一些工作。3D 堆叠之所以酷，是因为它可以缩短组件之间的物理距离。你可以把缓存直接堆叠在 CPU 计算核心的上方，这样缓存就有更多向上生长的空间，因此你可以拥有更大的 L3 缓存，并将其共享给更多的核心。这就像 AMD 处理器做的，他们有一个叫 3D V-Cache（讲者口误为 3DX）的东西。你可以买到名字里带 3D 标识的 CPU，那个 3D 就是指他们在上面额外贴了一块 L3 缓存。由于拥有了更多的 L3 缓存，这最终有助于缓解其中一些问题，因为当需要访问比如被另一个核心写入的数据时，数据传输走得路程没那么远了。但老实说，这算不上什么颠覆性的东西。

在 fetch_add（原子获取并累加）指令上也有一些很酷的研究。fetch_add 的巧妙之处在于它是完全可交换的（Commutative）。你可以让多个 CPU 把它们的 fetch_add 操作“池化（Pool）”起来，然后由一个核心统一执行所有的加法，最后把结果发送回其他核心。通过这种方式，你就不需要让同一个缓存行在核心之间来回弹跳了。我不知道当前是否有任何主流平台在硬件层面做了这种优化，但我知道曾有一段时间有些厂商这么做过。同样，让这个回答显得有些不那么令人满意的原因在于，这里有太多专有且不公开的系统，我们不知道哪些多年前发布的论文理念还在被实际应用，所以很多都只能停留在猜测层面。谢谢。

问：对于 Left-Right 数据结构，如果随着时间的推移，有大量的读取者不断地加入和退出，它的性能会受到怎样的影响？

Jon： 对于 Left-Right，目前的设定是：所有读取者的列表被保存在一个互斥锁（Mutex）里面。所以如果一个新的读取者想要加入，它必须获取那个互斥锁，分配它自己的计数器，将其塞进那个互斥锁保护的列表中，然后解锁互斥锁。写入者正是使用同一个列表来找出它需要遍历检查的所有读取者。但是，读取者一旦被创建（加入后），在它们生命周期内只要不彻底退出，就永远不需要再次访问那个互斥锁。事实上，即使它们消亡了，它们大可以把自己的废弃计数器留在那儿，因为那时候计数器已经是偶数了，写入者会自动忽略它们。当然规范的做法是清理掉它们。

如果这个注册/销毁过程最终变成了瓶颈，你完全可以很容易地将那个列表改成一个无锁链表（Lock-free Linked List），因为你只需要向里面追加元素或者遍历它，你永远不需要进行索引查找。这样你就可以让读取者的加入操作也实现并行化。唯一需要稍微小心的地方是：要确保写入者是在完成指针切换之后再去读取所有的计数器，如果在切换之前读取，它就可能产生逻辑混乱。这完全是可以实现的，只不过在我的使用场景里，读取者的加入并没有成为瓶颈，所以我一直没有做这个优化。

问：延续刚才那个关于硬件的问题，在纯软件层面上，互斥锁的实现存在多少多样性？这种实现上的差异又会带来多大影响？

Jon： 在软件层面，互斥锁是一种有点奇特的“野兽”。曾有一段时间，每种编程语言都在搞自己的互斥锁实现。接着许多大公司编写了他们认为更快、更适合自己用的内部实现。直到后来，我们在操作系统层面得到了对互斥锁更好的支持。

例如 Linux 上的 Futexes（Fast Userspace Mutexes，快速用户态互斥锁）。你通常直接使用它们即可，不需要在上面包一层厚厚的包装。在后来的几年里，人们尝试对互斥锁进行各种不同的优化。他们目前的关注点不再是“降低竞争”（因为这已经是底层的物理天花板，你不可能突破 MESI 的限制），而是尝试减小互斥锁的内存占用大小。比如存在一些数据结构中，互斥锁的大小被压缩到了只有 1 个字节。（听众插话提示：现在已经有压缩到 2 比特的了）。对，现在有 2 个比特（bits）大小的互斥锁了！

但是这带来的问题是，如果你开始把许多这种微小的互斥锁紧密打包在一起，你就又撞上了我们前面讲的**缓存行（Cache Line / 伪共享）**问题！现在这些本不相干的互斥锁，由于在同一个 64 字节块里，它们又开始在同一个缓存行上互相竞争了！因此，把它们做得更小并没有带来实质帮助，除非你能非常策略性地、精准地把那些“绝不会互相竞争”的互斥锁挑选出来打包在一起……你可以看到这个兔子洞有多深。

所以在“实现质量”上，我想说如今主流的实现基本都是等效的。唯一的例外是当你去看诸如读写锁（Reader-Writer Locks）这类更复杂的锁时。不同的操作系统为读写锁提供了完全不同的底层机制。和互斥锁一样，它们必须接入操作系统：如果一个线程当前拿不到锁（比如有个写入者正持有锁而读取者来了），它想进入休眠状态，它就必须和操作系统通信，且操作系统必须有一种机制在条件满足时唤醒它。读写锁在操作系统中应该如何运作，我认为这个领域仍然还在迭代中。在用户态也是，就像我之前提到的扩展设计：你拿到了操作系统给的底层读写原语，你能怎么在上面封装让它具有更高的扩展性？比如给每个核心保留一个副本（Per-core），线程来请求锁时，先检查自己在哪个核心上，然后去拿那个核心的锁副本。在读写锁的领域，设计空间仍然比互斥锁要宽广得多。谢谢。

问：你在最早的代码示例中提到，你需要向编译器提供一个小小的“提示（黑盒代码）”，以防止编译器把整个基准测试环境直接给优化没了。我很好奇，在编译器层面针对互斥锁的处理，目前都存在哪些类型的优化？你有没有见过什么特别令人惊讶或震撼的优化行为？

Jon： 编译器在处理互斥锁时通常会表现得非常“谨慎小心”，因为用户会理所当然地假设锁将以某种特定的方式运行。编译器实现这种谨慎的手段，通常是通过插入内存屏障（Memory Barriers）。

我不想讲得太深，去纠结什么 SeqCst（顺序一致性）、Acquire（获取）、Release（释放）之类的细节，那会变得非常痛苦。简单来说，编译器会在生成的汇编代码中注入一些“闪闪发光的小玩意儿”（特殊指令）。有时是给编译器看的，有时是给 CPU 看的，有时是给两者的。这些指令的意思是：“不许动！ 在这个点之前，你不允许把之后的读取操作提前挪上来；在这个点之后，你不允许把之前的写入操作向后推迟。”反之亦然。

它的目的是从根本上保证，例如你获取了一个锁，然后你在锁的内部读取了一些东西。CPU 存在一种被称为“乱序执行（Out-of-order execution）”的特性，屏障的作用就是禁止 CPU 在真获取到锁之前，就投机取巧提前把读取操作给做了——因为那样在并发语义上是灾难性的错误。

所以，这实际上不单纯是个“编译器魔法优化”，而是数据结构（锁）的设计者必须在实现层面，懂得去注入那些底层汇编指令（屏障），以确保编译器和 CPU 能协同保证逻辑的正确性。如果你不这么做，你就会写出一个“表面上看起来是对的”，但运行时偶尔会在加锁成功之前就把值读取出来的互斥锁。

确实，现在的编译器在优化方面极其出色，有时甚至出色得有点过了头。但相比起完全不优化的编译器，我们还是更愿意接受现在这种。不过近年来也有一些呼声认为，既然现代 CPU 已经这么快了，也许我们应该拥有“更蠢（简单）一点”的编译器，这样我们才能随心所欲地写一些看似糟糕底层的代码，同时确保编译器生成的代码完全符合我们的本意（而不会自作聪明地重新排序）。

但我不会说编译器和互斥锁的工作原理有任何极其“深度”的绑定。我觉得基本上就这样。

好了，谢谢大家！