非阻塞数据结构

标题：Nonblocking data structures

日期：2019/07/08

作者：Michael Scott

链接：https://www.youtube.com/watch?v=9XAx279s7gs

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

备注一：演讲人正是 Michael-Scott Queue 作者，就是 boost.lockfree 使用的那套。

备注二：演讲不仅长达三小时，而且需要加幻灯片才好看懂，后面我看的时候再插入。

第一部分

大家早上好，感谢各位的到来。也谢谢 Peter 的介绍。

我很高兴能来到这里。我一直想来圣彼得堡看一看，所以当我有机会来这里讲课，并且明天还能在 Hydra 大会演讲时，我立刻抓住了这个机会，因为我一直都想到这儿来。

为了方便不了解的人，我先介绍一下罗彻斯特大学的位置。在美国纽约州（地图上的白色部分），罗彻斯特大约位于五大湖中最东边的安大略湖的南岸中部。我们大学是一所小型的私立研究型大学，大约有 11,000 名学生。从大城市来看，我们离加拿大的多伦多最近，而离纽约市则有近 600 公里远。所以当我说我在纽约州时，大家都会以为我在纽约市，但实际上距离非常遥远，我也不常去那里。这是一张校园的鸟瞰图，前景是校园，杰纳西河绕着它拐了个弯。远处可以看到罗彻斯特市中心的天际线，地平线上的蓝色就是安大略湖。

我们大学的计算机科学系成立于 1974 年。目前我们大约有 20 名终身教职轨的教员和 70 到 80 名博士生。我们也有硕士项目和庞大的本科项目。本系最出名的或许是人工智能领域的研究，我大约有一半的同事是做 AI 的。我们在理论、人机交互（HCI）以及我的研究领域——并行与分布式系统方面也享有盛誉。

我今天假设在座的各位或多或少都对共享内存并行编程有些了解。了解一下大家的背景对我会有帮助。所以，如果可以的话，请允许我问一下：有多少人用 Java 写过并行程序？好的，太棒了。有多少人用 C 或 C++？好的。其他语言呢？好的，非常棒。

本次演讲将专注于并发数据结构，这些数据结构通常会被放在一个由专家编写的库里。如果你想成为这些专家之一，这次演讲就是关于构建这些库例程所使用的技术。我们的前提是，从所有其他线程的角度来看，对这些数据结构的操作需要原子性地执行。

我今天总共有大约三个小时的时间。我会尽量控制时间，在适当的时候安排休息。这部分内容在我教授并行与分布式系统课程时，通常需要花费 12 到 15 个小时，所以今天我会尽量讲一些重点，并希望对于任何你们想深入探索的细节，你们都能找到相关的论文来学习。我的重点将是那些贯穿各种算法的共通问题，这些技术值得你放在你的“工具箱”里，或者在你研究具体算法细节时记在心里。如果在任何时候有不清楚的地方，随时打断我都会非常有帮助。他们把灯光设置得很好，我基本上能看到你们所有人，所以如果你有问题，请务必举手提问，我很乐意在有帮助的情况下展开讨论。

关于这些内容，如果想了解更多信息，可以参考我几年前为 Morgan and Claypool 写的那本书，特别是第 1、2、3 和 8 章。这类书通常作为合集的一部分分发给图书馆，所以如果你能使用某个专业图书馆，它很可能就在里面。我目前正在撰写该书的第二版。

为什么不直接用锁？

那么，为什么不直接用锁呢？它们是在并发程序中实现原子性的自然方式，并且在大多数情况下工作得很好。

主要的理论答案是线程失败。如果一个线程持有锁然后死掉了，那么其他任何需要这个锁的线程都将永远无法再取得进展。这正是理论家们最初开发非阻塞数据结构的根本动机。

从系统角度看，我们通常是在同一个程序的线程间共享数据。所以，所有共享数据的线程要么同生，要么共死。如果其中一个线程死了，其余的也都会死掉，你也就不会关心那个数据结构怎么样了。因此在实践中，单个线程死亡这个想法并没有成为系统开发人员使用非阻塞数据结构的强烈动机。这种情况未来可能会改变，在我今天演示文稿的最后会有一张幻灯片回到这个话题。

但在实践中，人们对非阻塞数据结构感兴趣的历史原因主要是因为它们对 抢占（preemption） 有很好的容忍度。如果你使用锁，一个线程持有锁，然后被操作系统抢占，暂停运行了比如 10 毫秒，那么你程序中其他需要该锁的线程在这期间都无法取得进展。这在并行应用中可能是一个严重的性能问题。

在任何处理异步事件的系统中，也存在正确性问题。想象一下，你的线程持有一个锁，然后你的程序收到了一个信号，比如来自用户界面的鼠标点击、I/O 请求完成，或者一个网络数据包到达。如果这个信号处理器（signal handler）需要同一个锁，这就产生了一个 优先级反转（priority inversion） 的例子：低优先级的线程（信号到达前正在运行的线程）持有一个高优先级线程（即信号处理器）所需的资源，然后你的系统就锁死了。非阻塞数据结构解决了这个问题，因为在信号处理器中，你可以直接使用系统在中断发生那一刻的任何状态。

非阻塞数据结构基于这样一个理念：系统的每一个可达状态，都是任何线程都能在其中取得进展的状态。不存在这样一个可达状态，使得一个线程必须等待另一个线程的动作才能继续前进。因此，对于任何具体的、可实现的状态，都对应着一个唯一的、并发对象的抽象状态。你可以看着内存中的比特位说：“这些是我队列中的元素”，或者“这些是我哈希表中的键值对”，这些都由内存中的比特位唯一确定。

典型的操作通常有三个阶段：

  1. 准备阶段：在不打扰任何其他人的情况下，想好自己要做什么。

  2. 执行阶段：通过一个单独的硬件原子指令来完成操作。

  3. 清理阶段：清理工作。

通常算法被设计成第三阶段（清理）可以由任何线程来完成。当然也不总是这样，我们会看到大多数这些规则的例外。但这是一个你在非阻塞数据结构操作中看到的典型模式：准备、单个线性化指令、清理。

硬件基础与内存模型

今天我想确保每个人都具备必要的基础知识。我想谈谈这一切所依赖的硬件原语和内存模型。我意识到本周之前的一些演讲者，特别是 Danny Hendler，已经涵盖了部分内容，所以我希望可以快速过一下。但我确实想确保每个人都理解我使用的术语。

硬件原子原语

很久以前，在 60 和 70 年代，人们对只有加载（load）和存储（store）指令是原子操作的算法非常有兴趣。也有些算法甚至连这些都不是原子的，但人们很早就意识到，如果你在构建并行硬件，你绝不希望一个存储指令最终只存了一半的比特位，然后一个加载指令过来，看到了一半新比特和一半旧比特，之后你才完成存储。那会非常糟糕。所以硬件的设计几乎总是确保加载和存储指令相对于彼此是原子执行的。

然后，在相当久远的过去，大约在 70 年代，人们意识到他们需要更强大的指令，能够将读取、修改、写回一个内存位置作为一个单一的硬件原子操作。有多种这样的原子原语可用。在非阻塞数据结构的文献中最常见的一个是比较并交换（Compare-and-Swap, CAS）。

有多少人知道 CAS 是做什么的？好的，那我不需要详细解释了。它的意思是：“我很确定我知道内存里是什么。如果我对了，就用新值替换它，并告诉我你成功了。如果我猜错了内存里的值，什么也别做，但要告诉我我错了。” 所以，你可以很容易地编写几乎任意的“读-改-写”操作，通过读取一个值，对它应用一个函数，然后尝试用 CAS 将结果写回。下面这个循环就是这种用法：

C++

// CAS 惯用模式
do {
    old_val = *location;
    new_val = f(old_val);
} while (!CAS(location, old_val, new_val));

这个指令自 1970 年左右的 IBM 370 以来就一直存在。今天的 IBM Z 系列机器是其后继者，它们和 Intel 或 AMD 的 x86、Itanium 及 SPARC 架构一样，都支持 CAS。

与 CAS 并列的另一个主要选择是加载链接/条件存储（Load-Link/Store-Conditional, LL/SC），你可以在另一类现代架构上找到它。有多少人熟悉这个？不是很多，好的。如果你不使用 x86，这通常是你构建算法所依赖的通用原子原语。

它是一对指令。第一个是 Load-Link，它是一个加载指令，但附带一个副作用：标记缓存行（cache line）。它会告诉你内存位置中的值，并在 L1 缓存中该缓存行上设置一个比特位。然后 Store-Conditional 会尝试写入那个缓存行，前提是那个比特位仍然被设置着。换句话说，如果你的缓存仍然独占着那条缓存行，你就能用 Store-Conditional 修改它。但如果自从你执行 Load-Link 之后有其他任何人接触过那条缓存行（比如写入了它），它就不再在你的缓存中了，Store-Conditional 就会失败。

LL/SC 的使用方式与 CAS 非常相似：你对某个位置 A 执行 Load-Link，计算出你想放入的新值，然后尝试用 Store-Conditional 将新值写入该位置。如果成功了，很好；如果失败了，你就回到循环开头重试。

C++

// LL/SC 惯用模式
do {
    val = LL(A);
    // ... 计算 new_val ...
} while (!SC(A, new_val));

这个原语在很多机器上都有，最著名的是今天的 Power 和 Arm 架构。它也是 RISC-V 中可用的通用原语，RISC-V 在研究和商业领域的重要性与日俱增。

然而，关于 Store-Conditional 需要注意的关键是，你可能会因为多种原因丢失缓存行。可能是因为别人写了它，也可能仅仅是因为你的 L1 缓存的关联度或容量不足，或者因为某个完全不相关的进程的 I/O 完成导致操作系统处理了一个中断。所以 Store-Conditional 可能会伪失败（fail spuriously）。而 CAS 只有在期望值与内存中的值不符时才会失败。

CAS 失败时，你知道你期望的那个值已经不在内存里了，你甚至可以推断它为什么不在。而 Store-Conditional 失败时，你并不一定知道期望的值不在了，可能只是因为不相关的原因丢失了缓存行。

然而，Store-Conditional 有一个优势，我们稍后在谈论 ABA 问题时会看到。CAS 会在内存中的比特模式是你所期望的时成功，即使这个值出现的原因并非你所期望的。所以，如果内存中的值在比特层面是正确的，但在语义上是错误的，CAS 就会在不该成功的时候成功。但 Store-Conditional 在这种情况下会失败，而你也希望它失败。所以 Store-Conditional 在这里其实有优势。

这两种硬件原语在商业机器上并存的现实，也反映在 C 和 C++ 的标准库中，它们提供了 compare_exchange 原语的两个变体：

  • compare_exchange_strong：意在提供 CAS 的语义。如果它失败，你就知道期望值已经不在内存里了。

  • compare_exchange_weak：意在反映 LL/SC 的语义。它可能会伪失败。

如果你在一个使用 LL/SC 的机器上运行，compare_exchange_strong 是通过库里的一个循环来实现的。库内部会有一个循环说：“如果 Store-Conditional 失败了，我们回去再次检查内存中的值，看看它是不是期望值，以此来判断刚才是不是一次伪失败。” 所以，如果你需要能够基于 CAS 的失败进行推理，你就需要使用库里的 compare_exchange_strong。如果你不在乎伪失败，特别是在你的程序中已经有一个重试循环（就像我之前展示的那样），那么 compare_exchange_weak 就是你想要的。

大多数已发表的算法都使用 CAS，它们不常讨论 LL/SC。但理解它在底层是如何在另一类硬件上实现的，是很有价值的。虽然大多数文献中的算法使用 CAS，但并非全部如此。有时候你可能想使用其他硬件原语，比如 swap (原子交换) 和 fetch-and-add (取值并加)。

  • Swap：无条件地将内存中的值与寄存器中的值交换。它从不失败。在某些算法中，这就是你所需要的全部。如果你有 n 个线程想同时做 swap，使用 CAS 来模拟的话，会只有一个成功，其他 n-1 个都失败重试，这将导致 O(n²) 的时间复杂度。而如果硬件直接支持 swap，n 个线程可以在 O(n) 的时间内完成。

  • Fetch-and-add：对于像计数器这样的东西尤其高效。如果你想给计数器加一，用 CAS 在高竞争下效率极低，因为其他线程的并发增量操作会导致 CAS 大量失败。而 fetch-and-add 可以在 O(n) 时间内让 n 个线程完成增量。稍后我希望能有时间讲一个非常巧妙的队列算法，它在 x86 上利用 fetch-and-add 显著优于使用 CAS 的算法。

内存模型

接下来是内存模型。有多少人熟悉宽松内存模型（relaxed memory models）？大概一半。好的。如果你之前从未听说过这个话题，我得让你失望地告诉你：硬件的运行方式并不像全世界每个人希望的那样，也不像你一直以为的那样。

每个人都想要顺序一致性（Sequential Consistency）。顺序一致性意味着内存表现得如同所有操作（加载或存储）都是原子地发生的，并且程序历史中所有线程的所有加载和存储操作存在一个全局的总顺序。就好像只有一个大内存，你所有的线程都在访问它，每个操作都似乎是按某个顺序发生的。我们希望硬件这样做，但现在没人这么造了。因为如果允许一些令人惊讶的、违反直觉的重排序（在编译器和硬件层面），他们可以获得显著更好的性能。

为了避免看到这种反直觉的行为，你必须在代码中加入额外的同步。通常我们不用担心这个，因为我们大多数人写的程序里，需要原子性的临界区都由锁来保护。我们和硬件有一个美好的约定：如果我们所有的共享内存访问都由锁保护，我们就能得到顺序一致性的表象。所以，如果你在听这个关于非阻塞数据结构的讲座之前，写的是基于锁的代码，你永远不必担心宽松内存模型。但如果你真的在写非阻塞数据结构，你就必须非常关心操作实际发生的顺序。

在某种程度上，这有点乱。不过，有一个中间地带对大多数程序员来说是可行的，我称之为“充分策略”（sufficient strategy）：

  1. 在你的非阻塞数据结构中，任何允许一个线程做出决策（比如该走这条代码路径还是那条）的变量，如果它被其他线程修改，都应该在你的程序中标记为 atomic。在 C 或 C++ 中使用 atomic 关键字，在 Java 中使用 volatile 关键字。

  2. 如果你标记了所有这些变量，基本上正确的事情就会发生。在 C++ 中，对原子变量的访问本身还可以进一步用内存顺序约束来标记。默认的内存顺序约束是 memory_order_seq_cst（顺序一致），这意味着该原子变量的访问相对于所有其他原子变量的访问是顺序一致的。

  3. 你应该坚持使用默认设置。 只需将变量标记为 atomic，正确的事情就会发生。只有当你经过大量的性能分析，确定某个瓶颈可以通过更宽松的顺序来缓解时，你才可以将你的原子访问标记为比顺序一致更弱的级别。但这样做极其危险，非常非常难做对。很多流传出去并在三年后引发严重问题的微妙 bug，都是由不正确地标记原子访问引起的。所以，不要那样做，除非你真的、真的确定你需要那点性能，并且你真的、真的、真的确定你知道自己在做什么。

Treiber 栈和 ABA 问题

好，让我们看一个简单的并发数据结构，比我之前提到的计数器稍微复杂一点：一个栈。这是一个由 IBM 在 1980 年代的一份技术报告中发表的栈算法，主要作者是 Treiber，因此通常被称为 Treiber 栈。

它的思想是使用一个链表。Top 指针指向栈顶节点，第一个节点指向第二个，以此类推，栈底元素的 next 指针为 null。

  • Push (入栈)：

    1. 分配一个新节点（这是无害的准备工作）。

    2. 将新节点的 next 指针设置为当前 Top 指向的节点（更多无害准备）。

    3. 使用 CAS 将 Top 指针从旧的栈顶原子地切换到新节点。

    这是操作发生的瞬间。如果 CAS 失败，意味着在我读取 Top 和执行 CAS 之间，有其他线程执行了 push 或 pop。如果失败了，没关系，CAS 的失败说明栈已经变了，我只需要回到开头重试即可。我会一直这样做直到成功。每次我重试，我都知道是其他某个线程的操作使得整个系统取得了进展。

  • Pop (出栈)：

    1. 读取 Top 指针。

    2. 使用 CAS 将 Top 指针翻转到栈中的下一个节点，如果其他线程执行了 push 或 pop，则重试。

    3. 然后删除旧节点。

这是基本思想。不幸的是，事情没那么简单。

ABA 问题

假设我们有两个操作同时进行：

  1. 线程一开始 pop。它读取了 Head 指向 A 的指针，也读取了 A 指向 C 的指针。它计划将 Head 指向 C。但它目前只做了计划，还没执行 CAS。

  2. 此时，线程二介入，它 pop 了 A，然后释放了 A 的内存。

  3. 接着，线程二又 push 了一个新节点 B。在释放 A 之后，一次新的 malloc 调用有可能返回与 A 相同的内存地址。线程二可能用这个地址创建了新节点 B 并将其推入栈中。

  4. 现在，Head 指针的比特位与线程一开始看到的一样（都指向旧 A 的地址），但栈的结构已经完全不同了。

  5. 线程一现在醒来，执行它的 CAS。这个 CAS 本应失败，但它成功了，因为 Head 的值和它期望的一样。结果，Head 指针指向了 C。这不仅 pop 了 A，还把 B 给弄丢了。我们期望 pop 的是旧的 A，但现在栈完全被破坏了。

这就是我之前提到的 ABA 问题。一个内存位置的值是 A，然后变成了 B，之后又变回了看起来像 A 的东西（比特位相同）。

这个问题在使用 LL/SC 构建栈时不会发生，它是 CAS 固有的问题。在有 CAS 的机器上，构建像 Treiber 栈这样的结构时，可以使用一种叫做 计数器指针（counted pointers） 的技术来避免这个问题。这种技术在许多非阻塞数据结构中都会出现。

我们不再用一个地址来表示指针，而是用一个 序数和地址组成的对（pair） 来表示。每次我们改变指针时，我们不仅更新地址部分，还会递增序数部分。现在，只要我们的系统运行时间不足以让序数回绕（如果序数是 32 位或 64 位，这很容易做到），我们就能保证一个 CAS 不会在不该成功的时候成功。因为即使你重新得到了地址 A，它也会带有一个不同的序数。

当然，这个技术的问题在于，你的 CAS 现在必须同时操作指针的比特模式和序数。这基本上需要一个 双字宽（double-word wide） 的 CAS，有些机器有，有些则没有。

我们也可以用其他的内存管理技术来解决 ABA 问题，最著名的是危险指针（hazard pointers），我稍后会谈到。但现在，你只需要知道计数器指针是一种很常见的技术。

正确性标准

在深入研究其他数据结构之前，我想谈谈正确性。通常我们关心两件事，称为安全性（Safety）和活性（Liveness）。

  • 安全性：坏事永远不会发生。

  • 活性：好事最终会发生。

大多数论文在安全性上花费的笔墨多于活性。通常安全性的证明比活性的证明更难。但你应该注意到，一个并发数据结构的实现，如果每个操作都是一个无限循环（比如 while (true);），那么它在安全性上是正确的——因为什么坏事都没发生，当然好事也没发生。所以我们非常需要活性，因为我们不希望一个只会在无限循环里什么都不做的算法被认为是正确的。

线性一致性（Linearizability） 是我们用于安全性的标准正确性准则。对于活性，我们有几种不同强度的非阻塞进展保证。

安全性：线性一致性 (Linearizability)

线性一致性由 Maurice Herlihy 和 Jeannette Wing 在 1980 年代提出，并已成为非阻塞数据结构的标准正确性准则。

我们说一个数据结构的历史（即一系列随时间发生的调用和返回事件）是线性一致的，如果这个（可能由多个线程交错组成的）调用和返回序列，等价于一个所谓的顺序历史。在这个顺序历史中：

  1. 每个调用都紧跟着它的返回，就像在串行程序中一样。

  2. 它与实际历史具有相同的调用（参数相同）和返回（结果相同）。

  3. 它尊重每个线程内部的程序顺序（我不能让我的第二个调用发生在第一个之前）。

  4. 它尊重数据结构的语义（比如 pop 不能返回栈中错误的元素）。

如果一个数据结构的所有可能历史都是线性一致的，那么这个实现就是线性一致的。

一个等价的思考方式是：每个操作都表现得像是在其调用和返回之间的某个时间点上瞬时发生的。这个点被称为线性化点（linearization point）。事实证明，这个定义更容易用作证明的组织技巧。因此，当我们撰写关于非阻塞数据结构的论文，或者为库构建一个并想说服自己它是正确的时候，我们通过在每个操作中识别出一个线性化点来做到这一点。

让我们回到 Treiber 栈的伪代码。

  • 在 push 操作中，当我们执行一个成功的 CAS，将栈顶指针改为指向新节点时，push 操作就在那个瞬间线性化了。

  • pop 操作稍微复杂一些：

    • 如果栈是空的，pop 读取到 Top 为 null 并直接返回。那么，读取到 null 的 Top 指针就是线性化点。

    • 如果栈非空，pop 尝试进行 CAS。如果 CAS 成功，那么这个成功的 CAS 就是线性化点。

    • 如果 CAS 失败，它会循环重试。在下一次循环中，它可能会发现栈变空了，那么读取到 null 的 Top 指针就成了线性化点。

所以 pop 操作有两个可能的线性化点，具体是哪一个取决于执行期间操作的交错情况。

活性：非阻塞进展 (Non-Blocking Progress)

对于正确性的另一半——活性，有三种主要强度级别的定义：

  1. 无等待（Wait-free）/ 无饥饿（Starvation-free）：这是最强的保证。一个操作是无等待的，意味着它保证在有限的自身步数内完成，无论其他线程在做什么。

  2. 无锁（Lock-free）：这是最常见的中间级别。它保证在有限的系统总步数内，至少有一个线程取得进展。也许不是我的线程，但系统整体上不会被卡住。它防止了活锁（livelock），但单个线程理论上可能饥饿。Treiber 栈就是无锁的。在实践中，单个线程永远无法取得进展的概率极小，所以大多数人对无锁算法很满意。

  3. 无阻碍（Obstruction-free）：这是最弱的保证。它保证如果一个线程在没有其他线程干扰的情况下（即其他线程都暂停），它能在有限的自身步数内完成操作。这可能需要一些带外机制来解决持续冲突的问题。

  • 用 fetch-and-add 实现的计数器是无等待的。

  • 用 CAS 循环实现的计数器是无锁的。

  • 一些软件事务性内存系统是无阻碍的。

无等待算法对于实时应用可能很有用，因为它们有完成时间的上界。它们对于大型只读操作也可能很有价值，比如对一个哈希表计算中位数。如果用无锁算法，这个需要读取整个表的操作很可能被频繁的插入/删除操作干扰而饿死，而无等待的实现则可以保证完成。

一个无等待计数器的例子

让我给出一个简单的无等待数据结构的例子，它不仅说明了无等待性可能涉及什么，也说明了为什么线性化点可能很难识别。这是一个只有 increment 和 read 两个操作的计数器。

我们用一个数组来实现，每个线程在数组中有一个自己的槽位。

  • increment(): 线程只需递增它自己的槽位值 (val[my_id]++)。这显然是无等待的，只需几次操作就能完成。

  • read(): 扫描整个数组，将所有槽位的值加起来。这也是无等待的，时间复杂度是 O(T)，T 是线程数。

这个算法是线性一致的吗？increment 很简单，写入新值的那个存储操作就是它的线性化点。但 read 操作比较棘手。read 操作会持续一段时间，在此期间其他线程可能在执行 increment。

可以证明，read 操作返回的任何值，都介于“read 调用时所有值的总和”和“read 返回时所有值的总和”之间。由于 increment 每次只加一，这两个边界之间的任何整数值都是一个合法的顺序历史状态。

这意味着 read 的线性化点可能非常奇怪。想象一下，我的 read 操作读了一半的数组。然后，某个线程对一个我已经读过的槽位进行了递增。就在那一刻，总和可能恰好等于我如果读完整个数组会得到的某个合法值。于是，我的 read 操作就在那个其他线程的写入操作发生的时刻线性化了，即使我自己的代码还没执行到数组的后面部分。所以，我们无法通过查看代码来指出某个指令是线性化点；它只能通过对整个执行历史进行回顾性推理来确定。

Michael-Scott 队列

接下来是第一个已知的、正确的非阻塞队列，是我和我的学生 Maged Michael 在 1990 年代提出的。这是一个链表实现的无界队列，它有一个 Head 指针和一个 Tail 指针。

  • 结构：队列总是包含一个哑元节点（dummy node）。一个空队列的 Head 和 Tail 都指向这个哑元节点。在一个非空队列中，Head 指向哑元节点，而新元素从 Tail 端加入，旧元素从 Head 端移除。

  • Enqueue (入队)：这是两个操作中比较棘手的一个，因为它需要更新两个东西：链表的链接和 Tail 指针。

    1. 在一个 CAS 中，将当前尾节点的 next 指针从 null 指向新节点。这是入队操作的线性化点。

    2. 在第二个 CAS 中，将 Tail 指针移动到这个新节点。这步是清理（cleanup）。

    如果任何线程发现 Tail 指针指向一个 next 指针不为 null 的节点，它就知道有一个入队操作只完成了一半。这时，任何线程都可以 帮助（helping） 完成那个 Tail 指针的更新。这种帮助机制在非阻塞算法中非常普遍，尤其是在无等待算法中，你常常需要通过完成阻碍你的线程的工作来为自己开路。这个队列算法是无锁的，因为一个线程可能永远都在帮助其他线程入队而无法完成自己的操作，但系统整体总是在前进。

  • Dequeue (出队)：

    1. 读取 Head 指针、哑元节点的 next 指针，以及 next 指针指向的节点中的数据值。

    2. 在一个 CAS 中，将 Head 指针移动到下一个节点（即刚刚读取了数据的那个节点）。这个成功的 CAS 是出队操作的线性化点。

    3. 现在，旧的哑元节点可以被丢弃，而出队元素的节点成为了新的哑元节点。

    注意，你必须在执行 CAS 之前读取数据值，因为一旦 CAS 成功，任何其他线程都可能立即出队并释放你刚刚读取的那个节点。

内存管理问题

我之前对 malloc 和 free 轻描淡写了，但这是个大问题。在一个基于锁的结构中，你持有锁，所以可以安全地分配和释放节点。但在非阻塞算法中，你可能会尝试释放一个其他线程可能正在访问的节点。在那个线程意识到冲突并重试之前，它可能会解引用一个指向已被回收并用于其他目的的内存的指针，导致程序崩溃。

在这个队列中，一个简单的解决方案是：

  1. 使用计数器指针：为 Head 和 Tail 使用计数器指针来解决 ABA 问题。

  2. 使用类型保留分配器（Type-Preserving Allocator）：一旦一块内存被用作队列节点，它就永远是队列节点。当你 free 一个节点时，你把它放回一个专门的队列节点池中，而不是返回给通用的内存分配器。这样可以保证，即使一个线程访问了一个已被释放的节点，它的 next 指针字段仍然包含一个有效的指针（指向另一个队列节点），而不是一些随机的比特位。

当然，如果你在像 Java 这样有 垃圾回收（GC） 的语言中，你就不需要担心这个问题。只要有线程持有对某个节点的引用，GC 就不会回收它。不过要注意，我知道的每个 JVM 中的 GC 都是阻塞的（会用到锁），所以从整个系统的角度看，它可能不再是一个完全非阻塞的算法了。

Harris 链表

最后，我想谈谈一个非常基础的数据结构：单向有序链表。这个算法由 Tim Harris 在 2001 年左右提出。

人们很自然地会想，可以用单个 CAS 来更新链表。比如，插入 C 时，将 B 的 next 指针从 D 原子地改为指向 C。删除 C 时，将 B 的 next 指针原子地改为指向 D。

这在只有插入或只有删除时是可行的，但当插入和删除同时发生时，就会出问题。问题在于，一个插入操作和一个冲突的删除操作可能在不同的内存位置上执行它们的 CAS，导致竞争无法被检测到，最终破坏链表。

Tim Harris 的洞见是，我们可以让这两个冲突的操作都在同一个内存位置上进行 CAS。他的方法是：

  • 指针标记（Pointer Tagging）：利用指针的低位比特通常为 0 的事实（因为内存对齐）。我们可以用最低位的比特来标记一个指针。

  • 删除操作：要删除节点 C，我们不去修改 B 的指针，而是通过 CAS 标记 C 的 next 指针。这个标记操作就是删除的线性化点。一旦 C 的 next 指针被标记，它在逻辑上就被从链表中移除了。所有遍历链表的线程都会将这个节点视为已删除。将它从物理链中断开则成了后续的清理工作。

  • 插入操作：插入操作在尝试 CAS 一个指针时，会检查它是否被标记。如果它发现目标指针（如 B 的 next 指针）指向一个其 next 指针已被标记的节点，它就知道有冲突。它会拒绝插入，并先帮助完成清理工作（物理删除那个被标记的节点），然后重试自己的插入。

这样，插入和删除的冲突就被强制发生在同一个内存位置（被删除节点的 next 指针）上了。

Harris 最初建议可以懒惰地删除，即让逻辑上删除的节点在链表中保留一段时间，然后批量移除。但 Maged Michael 后来指出，在没有 GC 的情况下，这会带来严重的内存管理问题。因为一个线程可能在遍历一个已被逻辑删除的节点时，另一个线程物理地移除了它并重用了内存，导致遍历出错。

解决方案是：

  1. 立即清理：任何时候看到一个被标记的节点，都必须立即帮助物理地移除它，不能越过它继续遍历。再配合计数器指针和类型保留分配器，可以解决问题。

  2. 危险指针（Hazard Pointers）：这是一种更通用的手动内存管理技术。其核心思想是，每当一个线程要解引用一个可能被其他线程删除的指针时，它会先在一个全局可见的位置 “公示” 这个指针，声明“我正在使用这个指针，请勿删除”。一个想要释放节点的线程，在将其从数据结构中物理断开后，会检查这个公示列表，确保没有其他线程正在使用该节点，然后才能安全地回收其内存。

这就是危险指针的关键思想，我们休息之后再回来详细讨论。

谢谢。

（掌声）

第二部分

好的，这是 Michael Scott 讲座“无阻塞数据结构，第二部分”的完整中文翻译，已根据您的要求进行了整理和排版。

我的表显示现在是中午，所以我想我们开始下半场吧。我不确定能讲完多少内容。我准备的幻灯片可能比我能讲完的要多一些，但我想这总比反过来要好。在休息之前，我刚刚介绍了危险指针 (Hazard Pointers) 的概念，这是 Maged Michael 在其论文中引入的一种通用技术，该论文更新了 Tim Harris 关于单向链表的工作，并成为一种可用于许多无阻塞数据结构的通用技术，应用非常广泛。

危险指针的核心思想是，我只想确保在我还持有某个节点的引用时，没有其他线程会删除并重用这个节点。因此，任何我持有引用且可能被其他线程从数据结构中移除的节点，我都会将其指针发布到一个全局位置。在许多算法中，每个线程有限数量的指针就足够了，通常数量还很小。特别是在链表中，每个线程只需要两个危险指针：我当前所在的节点和我刚刚离开的节点。如果我将指向这两个节点的指针放在全局位置，那么任何要删除节点的线程都可以查看线程列表，检查每个线程发布的那零个、一个或两个危险指针。如果一个已从列表中移除的节点没有被任何危险指针引用，那么我们就知道没有线程在关注它，如果我们将其重用于其他目的，也不会打扰到任何线程，所以我们可以安全地回收它。但如果有一个危险指针指向它，那么我们就需要将该节点放在某个地方，直到可以安全回收为止。在文献中，这通常被称为待回收列表 (limbo list)，一个存放处于“ limbo ”（待定）状态的节点的地方，直到它们可以被安全回收。因为在那个时刻，有某个线程的危险指针正指向它们。

从更广的视角来看，如果你有锁，空间回收就很容易，因为只要你持有锁，在一个设计良好的算法中，你通常可以确信没有人在以冲突的方式访问任何东西。所以你可以回收从数据结构中取出的节点。计数指针 (Counted Pointers) 和类型保留分配 (Type-preserving Allocation) 是一种直接的技术，在许多（虽然不是全部）数据结构中都有效。但它们需要一个双倍宽度的 CAS（Compare-and-Swap），这只在某些架构上可用，而非全部。

危险指针是一种通用的解决方案，并且是可移植的。在需要无限数量危险指针的情况下，它们会有点笨拙。例如，想象一下你在进行树操作，你需要为从根到你正在搜索的某个叶子节点的路径上的每个节点都发布一个危险指针。在这种情况下，你必须能够动态地分配危险指针。这虽然可以做到，也有库可以实现，但有点麻烦。危险指针更重要的问题是，每次你更新一个危险指针，也就是写下一个你正在使用的东西的指针时，在做任何其他事情之前，你都必须执行一个释放屏障 (release fence)。也就是说，你需要确保你刚刚对全局位置（用于宣告你正在使用此节点）的写入操作对所有人都可见，然后才能执行任何后续操作。而在许多架构上，这个屏障的开销是昂贵的。所以在许多架构上，更新一个危险指针会有一个不可忽视的成本，粗略估计，大概 30 个时钟周期。因此，人们有动力去寻找处理内存管理的方法，以避免每次解引用指针时都产生昂贵的屏障。

在无阻塞数据结构的内存管理技术领域，有大量的文献，我今天肯定无法详细介绍，但让我给你们一些思路的指引。有好几位研究者使用了通常被称为基于纪元 (Epoch-based Reclamation) 的回收方法的变种。我所知的最早引用是在 Keir Fraser 在剑桥大学的博士论文中，但我不能完全确定他是不是第一个使用它的人。其基本思想是，你有一个缓慢增长的全局时钟。实现这个全局时钟有多种方式。无论何时你使用数据结构的节点，你都会记下你开始执行操作时所在的纪元。而当你想删除一个节点时，你要等到没有任何线程仍在你执行删除操作的那个纪元或更早的纪元中活动。所以基本上，你要等到每个活动线程都进入了比可能存在该节点未完成引用的纪元更晚的纪元，然后你就可以安全地回收它了。这样做的好处是，你只需要在操作开始时更新一次这个纪元的宣告。所以，你不是在每次指针解引用时都执行一个屏障，而只是在操作的开始和结束时各执行一次。当然，问题在于，由于它的粒度更粗，在可以被回收之前，累积在待回收列表中的内存量可能会大得多。事实上，如果你的线程可以在抢占 (preemption) 期间任意长时间地休眠，这个内存量是无界的。

危险纪元 (Hazard Eras) 有点像是基于纪元的系统和危险指针的混合体。它们将一个“纪元”与每个指针关联起来，并且当你解引用一个新指针且它属于一个新的纪元时，它们会更新你所在纪元的全局宣告。所以，只要你正在跟随的所有指针的创建时间不晚于你已经宣告的纪元，你就没事。但一旦你查看一个来自更新纪元的指针，你就必须更新宣告。这在一定程度上减少了空间占用。

就在去年，我的一个学生，Housen Wen 和他的合著者在 PPoPP 上发表了一种算法，通过允许你回收在某个线程进入睡眠状态后创建的东西，避免了因无限期抢占可能发生的无界空间分配。所以一个线程可以去睡觉，但它不会永远阻塞事情。在线程睡眠期间，新的东西可以被回收。要详细讲解这个可能需要很长时间，我建议任何想了解的人去阅读相关文献。但在实践中，大多数现有的算法使用计数指针和类型保留分配、危险指针，或者可能是基于纪元的回收。

哈希表

现在让我们转向一个新的数据结构：哈希表 (Hash tables)。当然，世界上有多种哈希表。最直接的方法是使用 Harris 和 Mikhail 的链表来实现一个带链式桶的哈希表中的桶。所以我们有一个指向链表的头指针数组，然后所有在同一个桶里的东西都在一个从这些头指针延伸出来的单向链表中，就是这样。整个算法就完成了，对吧？我们已经有了单向链表的算法，我们知道它如何工作，我们把它用于每个桶。但这给了我们一个固定大小的哈希表。如果我们在程序执行到一半时发现需要一个更大的哈希表，我们没有机制来适应这种情况。

还有一种替代的哈希表方法是内部的，即所有东西都在一个静态分配的桶中，没有链，你在发生冲突时进行再哈希。这是 Purcell 和 Harris 的工作。这个方法也有一个无阻塞版本。我想告诉你们一个可能是我最喜欢的无阻塞算法，因为它实在太优雅、太聪明了，那就是 Shalev 和 Shavit 在 2006 年提出的一个可调整大小的链式哈希表。这个算法不仅做到了无阻塞，而且所有操作的期望时间都是 O(1)，包括调整表大小的操作。所以我可以在插入操作中将哈希表的大小加倍，并且仍然在常数时间内完成。

关键在于，桶只是提示 (hints)。哈希表中的所有东西都在一个单向链表中，而桶是指向链表内部的指针，告诉你从哪里开始搜索链表。不仅如此，这个链表是保持排序的，不是根据键值，而是根据哈希值。并且哈希值的表示方式非常奇特。所以我们有一个单向链表，桶只是提示，单向链表是根据对哈希值的奇怪位操作来排序的，而且这个位操作很重要。

这是一个例子。我不会试图给你代码，但希望通过看这个例子，你能理解这个算法是如何工作的。这个例子比你实际会做的任何哈希表都要小得多，但这样它才能放在幻灯片上。

目前，我们有四个桶。稍后，我们可能决定要有八个桶，然后是 16 个，再然后是 32 个。每次我们调整大小时，都会将桶的数量加倍，这会在我们使用的哈希值位数上加一。所以我们有很长的哈希值，比如 64 位，但我们并不使用大部分位。我们只用少数几位来索引哈希表。

桶数组中的每个条目要么是 null，就像那里的 2。2 哪里也不指。要么它指向链表中的一个虚拟节点 (dummy node)。虚拟节点永远不会消失。它们是桶数组中提示的目标，并且在适当的位置散布在数据节点之间。所以这是一个初始的哈希表，里面不是键 5、15、16 和 17，而是哈希值为 5、15、16 和 17 的键。在我的例子中我们不需要键，所以我实际上没有展示它们。我只展示了哈希值。如果你看上面，桶上方的对角线位模式，它们展示了对哈希值的位操作。最低有效位要么是 0（对于虚拟节点），要么是 1（对于数据节点）。其余的位是哈希数的位反转。例如，对于哈希值为 5 的节点，它上面的位（除了末尾的 1）反过来是 00101，而 101 当然就是 5。所以哈希值是以反转顺序编码在那些位中的，末尾还有一个额外的位来指示它是否是虚拟节点。

好，让我们插入一个新节点。它的哈希值将是 9，我用浅灰色表示了。它的低位是 1，表示它是一个数据节点，然后是 01001，这是 9 的哈希值（译者注：原文为 01001，但 9 的二进制是 1001，反转是 1001，这里可能是为了对齐位数写作 01001）。它会按照标准的数值顺序被插入到哈希值为 17 和 5 的节点之间。我们除了在列表中找到正确的位置外，什么也没做，我们是通过取哈希值的两个低位，也就是 01，来索引桶数组的。所以我们使用了桶数组中的 1 号条目找到第二个虚拟节点，并从那里遍历列表，找到应该插入 9 的位置。

然后，假设我们决定需要将桶的数量加倍。我们分配了四个新的桶。它们将对应值 4 到 7。我们将开始使用三位哈希值，而不仅仅是之前的两位，但我们所做的仅仅是分配一个额外的数组来存放更多的桶，并且它们是未初始化的。我告诉过你这将在常数时间内发生。这是假设分配器给了我们一个充满空指针的数组。如果我必须遍历并把它们都设为 null，那就不算是常数时间了。但我们只做了这些。我们没有初始化任何指针。它们将被懒惰地 (lazily) 初始化，我们也没有改变链表。但事实证明，当我们懒惰地初始化那些指针时，它们最终会交错地，实际上是均匀地交错地，分布在我们已有的指针之中。换句话说，新的节点为我们提供了对列表提示的细化。它们在我们已有的提示之间穿插了更频繁的提示。

所以现在，如果我们想插入一个新节点，比如说一个哈希值为 21 的，我们会发现，因为我们现在使用三位哈希，低三位 101（即 5）对应的哈希桶是未初始化的。所以我们必须初始化它。那么，它应该去哪里呢？它被穿插在之前两个桶之间。所以如果我们只看两位，01，它告诉我们那个较老的桶，它必须在虚拟节点需要进入列表的位置的下方。所以我们从三位哈希中去掉一位，得到 01。我们用它作为提示进入列表。我们从那里开始仔细查找。在我们走得不太远之前，我们就在 9 和 5 之间发现了桶 5 的虚拟节点需要去的地方。我们用一个无阻塞的列表插入操作把它放进去。所以现在 5 被正确初始化了，我们可以从那里继续查找，很快就找到了 21 应该在的位置。

然后，如果我们去搜索一个节点，我们可能再次发现需要使用一个未初始化的桶。这里，如果我们去搜索 30，它当然不在列表中，我们想发现它不在列表中。我们计算出哈希值，取低三位，110，这需要使用 6 号桶。6 号桶是未初始化的，所以我们只用 10 来找到 6 的虚拟节点应该在的位置的最近提示。那是 2，所以我们从 2 所在的位置进去，向前查找，很快发现 6 需要一个虚拟节点，就在 2 原来指向的位置之后，我们把它放进去。

所以我们所有操作的期望时间都是常数时间，而且它们都是无阻塞的。这一切之所以能行，是因为我们使用了奇怪的哈希值，并选择使用它的多少位，以及将所有东西都放进一个单向链表中。我一直很喜欢这个算法。

（问答环节）

提问者：16 是不是放错位置了？

Michael Scott：希望没有。这些图实际上在我的书里，所以如果错了，我需要修正一些东西。所以 16，1、0、0、0、0、0，然后……嗯，如果……哦，嗯……2 和 6 去的地方之间没有任何元素，因为一旦我们开始使用 8 个桶和 3 位哈希，结果就是 2 号桶是空的。原来在 2 号桶里的东西现在被分到了 2 号和 6 号桶，而它们最终都到了 6 号桶。你知道，唯一的一个，那个 16，最终到了 6 号桶。

提问者：重复一下问题。最初在上面的图中，2 号桶没有任何指向链表的指针。对。那么是不是说，只要访问某个不在哈希表中但应该通过 2 号桶的元素，就会初始化这个指针？

Michael Scott：好的。对。如果我正在寻找某个需要在 2 号桶里的东西，但 2 号桶还没有初始化，那么这个查找操作就会初始化 2 号桶。是的。那么，让我们看看。16，用 3 位哈希，那三位，是使用低三位，那是 000。所以这没问题。而在下面……嗯……这就是问题所在，当然，当我试图站在舞台上深入细节时。我不知道你们怎么样，但我站在前面讲话时无法思考。我只能做其中一件事，要么说话，要么思考。为什么 16 在它应该在的位置？让我想想。嗯……嗯哼。嗯哼。嗯，它是按哈希值的位反转加上末尾一位来排序的。所以上面对角线里的那些数字实际上是按排序顺序排列的。嗯……是的，它们是排好序的。作为二进制数。不是吗？是的，你说得对。确实是。那到底是怎么回事？是。好的。我此刻的印象是，那个图是错的。我今天结束后会去仔细检查一下。如果确实错了，那我需要为教科书的图发布一个勘误。谢谢你。

提问者：您能详细说明一下如何以常数时间和无锁方式调整那个桶数组的大小吗？您可能需要一个数组的数组，那看起来不简单。

Michael Scott：是的。嗯……Shavit 和 Shalev 的原始论文对这一点一笔带过了。所以，如果我调整了十次表的大小，那么我有两个小表，一个比它们中任何一个都大一倍的表，另一个又比那个大一倍，再一个又比那个大一倍。我必须在期望常数时间内进入其中一个的正确元素。他们没有谈论如何做到这一点。你在这里需要一个额外的搜索结构层，它告诉你使用哪个数组。因为每个数组都是独立动态分配的。除了前两个大小相同外，它们的尺寸是连续增大的。为此，你可以使用一个静态分配的数组，它不需要很大就能覆盖你能想象到的最大的哈希表。然后你使用机器上的“查找最高有效位设置”指令来确定使用那个二级数组的哪个元素，来指向正确的桶序列，并告诉你使用该序列中的哪个桶。在图中，这只是 0 号，那是 4 号，但在实践中，你必须找到第二个数组才能索引 4 号，而那个额外的层次可以做到这一点，并且仍然是期望常数时间。只需要一个额外的层次。这有帮助吗？我甚至不确定问题是从哪里来的了。好的。

双端队列

这就是我计划要讲的关于哈希表的全部内容。我推荐那篇论文，它是一篇非常易读的论文，我今天课后确实会去复查我的图。

双端队列 (Double-ended Queues, Deques) 值得一谈，主要是因为有一个非常好的双端队列算法，它是无阻碍性 (Obstruction Freedom) 的动机性例子。无等待性 (Wait Freedom) 和无锁性 (Lock Freedom) 已经存在很长时间了。它们是在 Herlihy 和 Wing 的原始论文中定义的，并且发表了大量符合其中一种性质的算法，大家或多或少都认为无阻塞算法只有这两个有趣的分支。然后，Sun 实验室的一个小组意识到，还有另一个有趣的无阻塞定义，它比无锁性更弱，他们用双端队列作为其动机性例子。所以，引入无阻碍性概念的那篇论文是在我接下来要描述的这个算法的背景下进行的。

在顺序算法中，至少有一个非常精妙的应用是使用双端队列在平面上找到一组点的凸包。这是每个人在数据结构或算法课上都会学到的经典计算几何算法之一。我不知道在并发代码中有什么对真正的双端队列的迫切需求。但它能构成一个很棒的算法。不过，对于近似双端队列，确实有迫切的用途。特别是，一个无阻塞队列，支持由一个线程在一端进行插入和移除，并由任意线程在另一端进行移除，这是一种在工作窃取调度器 (work-stealing schedulers) 中被广泛使用的数据结构。文献中有多种这种受限双端队列的实现，即一个线程在一端进行推入（push）和弹出（pop），而任意线程在另一端进行弹出。当然，你可以为此使用通用的双端队列，但有更适合该目的的专门算法，我今天不打算详细介绍它们。

我将要介绍的是 Herlihy、Luchangco 和 Moir 的无阻碍双端队列 (Obstruction-Free Deque)，并且我会提到，通过将多个原始算法的实例链接在一起，可以使其变得无界。几年前，我的一位本科生 Matt Grotton 做了这件事，并在 ICPP 上发表了。顺便提一下，无阻碍双端队列是在 Magid Michael 的一个早期算法之后出现的。Magid 的算法有点复杂，那是它工作原理的图。注意，推入操作要经过三个步骤。完成一次推入需要三次 CAS。一旦初始的 CAS 发生，它可以被帮助。它需要一个双倍宽度的 CAS，头指针和尾指针都在同一个字里，所以你无法在队列的两端进行并发的、不互相干扰的操作。所以在实践中，这个算法不怎么被使用，但它是第一个发表的、正确的、用于无界双端队列的无阻塞算法。

现在让我们来看那个优雅的，向 Magid 道个歉。Herlihy、Luchangco 和 Moir 的优雅的双端队列最容易通过将其循环结构展开来解释。这是一个有界的循环队列。它确实支持在一端无限地推入和在另一端弹出。所以如果你只想把它当作一个队列来用，它会一圈一圈地转，追逐自己的尾巴，这没问题。或者你可以在两端都进行推入和弹出，但如果你推入了足够多的东西，导致两端相遇，它就会说“对不起，满了”。

好的。我只是把它画成平的，因为这样更容易画。你会注意到，我们有一个左指针和一个右指针，它们指向的应该是队列各自末端之外的第一个未使用的元素。所以我们在中间有数据 A 到 Z，左边有一堆 bottom 元素，右边有一堆 top 元素，它们目前都未使用。当我们将两端连接成一个循环数组时，我们还需要一种额外的空节点，并且我们只需要一个，它位于最后一个 top 和最后一个 bottom 之间，我没有在图中画出来。

关键是，left 和 right 只是提示。它们不必相对于队列末端的推入和弹出操作原子地更新。所以当你想在左端开始一个操作时，你看一下左指针指向哪里。如果它指向一个 bottom 元素，你看它右边的紧邻元素，如果那里面有数据，你就找对地方了。如果你看右边的元素发现它也是个 bottom，那你就知道左指针太靠左了，你必须向右搜索，直到找到第一个数据元素，然后你就知道左指针本应在哪里，你可以修复它，或者以后再修复。同样，在另一端，你看它指向哪里，然后根据你看到的是数据还是 top，以及相邻元素是否是数据，来向左或向右移动。

一旦你找到了正确的位置，入队（enqueue）或出队（dequeue）是一个需要两次 CAS 的操作。数组的每个元素都是一个计数元素 (counted element)。它有一个序列号和实际数据，所以你需要一个双倍宽度的 CAS。你执行的第一个 CAS 操作是对你的相邻元素。假设我想在左边进行一次插入。我想把那个最右边的 bottom 元素变成一个新的数据元素。首先，我会改变相邻数据元素中的计数器。我这样做是为了干扰任何试图删除那个数据元素的线程。然后我尝试做一次 CAS，将 bottom 变成我正在插入的数据元素。类似地，如果我想在左边移除，我最初会改变最右边的 bottom 元素中的计数器，然后通过将数据元素变为 bottom 来移除它。

所以，如果我有两个操作同时迎面而来，一个想通过推入把数据向这边移动，另一个想通过弹出把数据向那边移动，它们各自都会先修改相邻元素，然后尝试 CAS 自己的元素，它们会互相干扰。很有可能它们会各自迫使对方重启，这样你就会遇到活锁 (livelock)，并且这可能无限期地持续下去，这就是为什么它是无阻碍的。所以，有可能两个操作相互碰撞并失败，然后重新开始，再次碰撞失败，再重新开始。解决这个问题是一个带外 (out-of-band) 的问题，而无阻碍算法一个非常优雅和酷的地方在于，为了获得前进保证，你不需要修改算法本身的代码，你可以独立地处理前进保证问题，方法是说，任何尝试太多次的线程就退让一小段时间，一个随机的时间，然后它碰到的那个线程很有可能就会取得进展并让开路。所以你可以在调度器中解决活锁问题，而无需将解决方案嵌入到你的代码中。无论如何，这是无阻碍算法的论点。而这个算法最终比 Maged Michael 的队列要简单得多，并且不需要 left 和 right 在同一个字里，这样你就可以在队列的两端同时进行操作而不会相互干扰。在这种特殊情况下，再说一次，我不知道有谁在实践中需要这个算法，但这是介绍无阻碍性概念的一个好方法。

世界上还有其他东西是无阻碍的。我所知道的最有说服力的例子要难解释得多，它们是软件事务内存系统。

提问者：我只是好奇，这种随机或指数退避的方法，来概率性地保证一种较弱的无等待条件，是不是一种常见的方法？

Michael Scott：嗯，这个的日期是 2003 年，所以这比无阻塞数据结构最初引入的概念要新得多。所以无阻碍性大约有 15 年的历史了，但相对于其他无阻塞技术来说还很年轻。确实有一些算法是无阻碍的。如果你看一些基于对象的软件事务内存系统，它们就有这种味道。Herlihy、Luchangco、Scherer 和 Moir 的 DSTM，我相信是来自 Sun 实验室大约 2004 年的，它是一个用于 Java 的无阻碍软件事务内存系统。之后，来自不同团队的，既有用于 Java 的也有用于其他语言的，有好几个后续者，它们以无阻碍的方式为你提供软件事务。它们需要在调度器中做一些事情来处理活锁的可能性。那个“事情”可能只是调度器中标准的、普通的操作系统扰动。通常情况下，如果你使用一个无阻碍算法，仅仅是系统中来自中断和硬件以各种方式运行流水线的，不完全是随机但却是常规的噪音，就能在线程之间产生足够的抖动，以至于每当它们相互碰撞时，最终都能自行解决。这在 STM 系统中不那么适用，因为事务是长时间运行的，你有可能一个事务开始工作，处理了四五个对象，另一个处理了四五个对象，然后它们相互碰撞，都把对方杀掉了。它们之间有太多可能相互干扰的方式，以至于在下一次运行时，它们仍然很有可能相互碰撞。所以你需要某种竞争管理 (contention management) 技术来处理软件事务内存。

树

树 (Trees) 在计算机科学中当然是无处不在的，而无阻塞的树非常有价值、复杂且多样。有相当多的不同树算法存在，我脑子里没有所有这些的细节。如果你真的对无阻塞树感兴趣，并且想谈论细节，Trevor Brown 就在这附近，他对这个主题了如指掌。那是他的论文题目，也是他持续研究的主题。

第一个无阻塞的二叉搜索树 (binary search tree)，不是一个自平衡的，一个至少有可能变成一个长长的、细长的分支，但是正确的无阻塞二叉搜索树，是 Faith Ellen 和几位合著者在 2010 年提出的。它是一个外部树 (external tree)，所有数据都在叶子节点，内部节点只有键来引导你搜索到合适的叶子。它是一个无锁 (lock-free) 算法，不是无等待的。Trevor 和 Helga 已经将其扩展到了 K 叉树。

有一个内部 (internal) 无锁二叉搜索树，我所知的第一个是 Howley 和 Jones 在几年后提出的，它的数据在内部节点，而不仅仅是在叶子。所以平均来说，它比只有叶子的外部树要浅一层。

有来自 Natarajan 和 Mittal 的更快的外部树，我待会可能会稍微谈谈，它通过更巧妙地标记树中潜在的冲突，扩展了 Ellen 等人的工作，从而在邻近但并不严格相互干扰的操作之间获得更多的并发性。

我所知的第一个无阻塞的平衡树 (balanced tree) 是 Natarajan 等人在 2013 年提出的，它实际上是无等待的 (wait-free)，非常复杂，而且有点慢。他们在那年晚些时候发表了一个该算法的无锁简化版，可能在实际代码中更实用。

然后还有许许多多其他的扩展和变种。例如，Dreszler-Cohen 等人在 2018 年的 PPoPP 上有一篇很好的论文，展示了如何为基本上任意的树算法添加无等待的遍历和查找操作。所以任何无阻塞或基于锁的树，你都可以用他们的工作来为其添加无等待的查找操作。这仍然是一个非常热门的研究领域。

为了给你一点感觉，让我简要描述一下 Ellen 等人最初的算法是如何工作的。它比那张幻灯片上列出的任何其他算法都要简单。想象一个插入操作，这是直接从他们论文中画的图，我 буквально 复制了 PostScript。你在图的左边有一棵树，你想插入这个新节点 C。你要通过添加新的叶子 C 和一个新的包含键 D 的内部节点来做到这一点，这个内部节点会以正确的方式引导你。在右边的图中，原始的叶子 D 仍然存在，只是被移下来，成为新的、内部键为 D 的节点的右孩子。

插入算法是三步，三个 CAS。

  1. 第一步，标记即将成为新插入节点祖父的节点，也就是图中最上面的 B，将其标记为插入的发生地 (locus of insertion)，或者说是冲突操作必须解决冲突的地方。所以我们用一个 CAS 在 B 中放一个标记，并且作为标记操作的一部分，我们写下我们计划要做的所有其他事情。所以我们有一个小的记录，上面写着“我正在将 C 插入这棵树，我想我会通过将一个新的内部节点作为你的右孩子来做到这一点，这个新节点的右孩子将是你原来的右孩子，并且它会有一个新的左孩子”。你把所有这些都写在一个小包里，然后把它放到节点 B 中，来说明你正在做什么。任何其他人过来找到那个标记，都可以为你完成你的操作。所以如果你在写下那个标记后被抢占了，其他人可以帮助它继续进行。这还不是真正的线性化点 (linearization point)，但这是可以发生帮助的点。所以对于插入操作，当你在节点 B 上放置标记时，你的操作就变得不可避免了。

  2. 第二步，你换入你已经作为计划操作一部分创建好的新子树。这是操作看起来瞬间发生的线性化点，你正在插入的东西将会被后续的搜索找到。

  3. 最后，你从 B 中移除标记，表示你完成了，并且你不再与任何可能过来尝试使用节点 B 的操作冲突。

三步。删除是一个四步过程，同样需要四个原子的 CAS 指令。

  1. 第一步，同样标记节点 B 为删除的发生地，这当然会与我们上一张幻灯片上的插入操作冲突。所以如果一个删除操作过来，发现 B 已经被一个插入或删除标记了，它将不得不先帮助那个其他操作，把它弄走。这就是为什么我们有那个信息记录（info record）。假设 B 还没有被标记，我们放一个标记进去，描述我们计划要做什么，在这个信息记录里。

  2. 然后，新的第二步，这是插入操作没有的，是标记节点 D，即中间的那个父节点，为冻结 (frozen)，意味着我们计划将它从树中移除。

  3. 第三步，换入我们创建的新子树，用 B 代替 D。这第三步是线性化点。

  4. 最后，我们取消标记 B。

这里有一个地方，插入操作不需要重试，它们可以被帮助。删除操作也可以被帮助，但删除操作有时必须重试，因为你可能标记了祖父节点，然后看父节点 D，发现有一个与 D 冲突的操作，这个操作同时与 D 和 B 冲突。在那个点，你可能不得不帮助它，然后回退，重新开始。实际上是取消标记，回退，然后帮助，然后重新开始。细节很复杂，我脑子里也没有全部记住，但那是一篇非常易读的论文。

（问答环节）

提问者：…

Michael Scott：是的，是的。但请注意，因为这是一个外部树，一旦你找到了你需要进行插入或删除的地方，你可以在本地判断出你仍然在正确的位置。所以如果我已经找到了，特别是注意到那里的节点 D 是内部节点的最低层，而 C 是一个叶子。我正在尝试删除 C，并且我正在对叶子 C、它的父节点和它的祖父节点进行操作。所以它们在从根开始的路径的底部三个节点。一旦我到了那个区域，树中其他任何地方的操作都不能改变“这里是删除 C 的正确位置”这个事实，这很重要。所以我确实有这个初始搜索把我带到这里，但一旦我在这里，我知道我在正确的位置，只要我能成功地标记 B 和标记 D，这个事实就不会改变。如果我不能成功地标记 B 和标记 D，那么在我自己的局部位置发生了冲突，我必须处理那个冲突。

让我提一下 Natarajan 和 Mittal 对此的变体。这同样是一个二叉搜索树，非自平衡，外部的，所以内部节点仍然只是键，但这允许更多的并发性。这个算法的重大创新是允许更少的操作相互冲突，在冲突检测上做得更精细，这是通过标记边 (flagging edges) 而不是节点来完成的。一个节点有两个孩子，我们可以分别标记指向这些孩子的指针，对不同孩子的操作将不会相互干扰。所以我可以同时在一个左孩子上做插入，在右孩子上做删除，它们不会相互冲突。在实践中，这对于某些工作负载确实能带来显著的性能提升。

在这张图中，同样是直接从 Natarajan 和 Mittal 的论文中画的，下面的叶子 G 是我计划进行插入或移除的地方。F 是 G 的父节点，而图上方的 B，在大多数情况下将是 F 的父节点。所以，在通常的预期情况下，这张图不是，在通常的预期情况下，标记为后继者（successor）的 C 和标记为父节点（parent）的 F 将是同一个节点。它们不是同一个节点的情况，就像这张图所示，是当我们有一些删除操作同时在进行，并且我们希望允许它们同时发生。特别是在这张图中，它代表了一种不太可能但可能发生的情况，从 C 到 F 路径上的所有节点（不包括 C 和 F），也就是节点 D 和 E，正在被移除的过程中，我们希望允许它们的移除操作与我们在叶子 G 那里试图做的任何事情并发地继续进行。

这棵树中有很多未标记的边，大概是这样。然后有两种标记的边。被标记 (flagged) 的边，在图中用双箭头表示，是那些其尾节点正在被移除，但其头节点（它们指向的节点）没有在被移除过程中的边。而虚线箭头是那些尾节点和头节点都在被移除过程中的边。在这种特殊情况下，我猜，是的，我们可能正在尝试移除节点 G，所以那个子树 gamma 将成为 E 的右孩子。所以我猜这是一张删除的图。

正如这张图所暗示的，但其方式比我计划在这里解释的要复杂得多，我们可以在从 C 到 F 的这条路径中间有多个删除操作正在进行，并且仍然能成功地在底部的 G 上做一些事情。这确实是，嗯，这是这个算法的创新之处，它比原始的 Ellen 等人的算法具有更高的并发性。正如我提到的，文献中还有很多其他的树，包括现在，相当近期的，自平衡的无阻塞搜索树。

跳表

继续，文献中也有几个跳表 (skip lists)。我所知的第一个版本也来自 Keir Fraser 的论文。Keir 的论文里有惊人数量的东西，真的非常令人印象深刻。他也是负责 Zen 虚拟机的家伙，或者说其中大部分工作的负责人。一个了不起的人。这是一个基于 Harrison 和 Mikhail 的单向无阻塞链表的跳表。Doug Lee，Java Util Concurrent 库的主要架构师，研究过这个版本，所以 Fraser 跳表的一个更新版本就在 Doug Lee 的 Java 标准库中。然后，在那之后，Herlihy、Lev 和 Shavit 制作了另一个稍微不同的版本。在下一张幻灯片中，我将示意它是如何工作的，并给你一个关于那个特定跳表的简要介绍。还有一大堆相关的跳表实现。然后还有一个独立的，技术上相当不同的，来自 Fomitchev 和 Ruppert，它也使用 H&M 链表，但在那些链表中有向后的链接作为提示。它的主要优点是，当你遇到冲突时，你可以在他们的算法中局部恢复，而不是从头开始你的操作。所以从冲突中恢复变成了一个 O(1) 的操作，而不是 O(log n) 的操作。当然，缺点是反向链接引入了额外的复杂性和持续的开销，所以不清楚在实践中哪个性能更好。但显然，第一个要点的那个更容易解释。

这是一张图，用来示意第一个是如何工作的。希望大家，大家是不是都熟悉跳表？有谁以前没有见过跳表作为一种顺序算法？有几个人。好的，我得告诉你们什么是跳表。跳表超级棒。它们是一种概率性的对数时间搜索结构。如图所示，你有一个链表，一个排序的链表，它有一些额外的稀疏链表与之关联。图中最底层的链接是一个单向链表，如果你想在这个数据结构中找东西，你可以简单地遍历那个链表，直到你碰到你正在寻找的元素，或者你到了一个比它大的东西，所以你知道它不在列表里。但是更高层的链表让你可以在大多数时候跳过前面的东西。

要在一个顺序跳表中插入东西——顺便说一句，这是马里兰大学的 Bill Pugh 20 年前的成果，我不确定具体时间——你要选择一个数，表示它将存在于多少个链表中。所以如果我们有一个 K 层的搜索树，我会在 1 和 K 之间选一个数，表示我要插入的层数。我以 1/2 的概率选 1，以 1/4 的概率选 2，以 1/8 的概率选 3。每个向上的连续层被选中的概率是下面一层的一半。一旦我选好了层数，我就继续，在排序的……由于概率的原因，图中每向下一层，条目数量大致是上一层的两倍。并且有很高的概率，如果我先在最顶层的列表中搜索，找到比我找的东西小的最后一个节点，然后往下，在下一个列表中搜索，找到比我找的东西小的最后一个节点，再往下，我将在对数时间内找到我想要的东西。这就是这个数据结构的想法。

我们想以并发和无阻塞的方式来做这件事。我们可以在每一层都使用 Harris 和 Michael 的链表。在我描述的这个版本中，想法是，最底层的列表是权威的 (definitive, authoritative)，那是真正重要的。上层的列表是提示。如果你向下移动，你必须再次检查你是否真的在你刚刚移动到的那个列表中，你可能会发现你不在，在这种情况下，你必须在你的代码中有效地回退，记住你来自的节点，然后重试。

所以这个算法中的插入操作首先在底部的链表中进行一次 Harris 和 Michael 的插入。如果你选择的节点上方的塔的高度超过一，那么你需要继续，在上面的列表中进行一次插入，然后如果它的高度是 3，你将在再上面一个列表中进行一次插入，直到你用完了你最初选择的所有层数。你将在这些层中进行插入，每一次插入都是一个无阻塞的列表插入。但这意味着，插入操作的集合不是原子完成的。底部的那个是对其他并发操作的线性化点，而上层的提示，允许它们有期望对数时间，但不保证能工作。插入是从下往上工作的。删除实际上是从上往下工作的。所以如果你想删除一个节点，你首先从最顶层的列表中移除它，移除提示，在你移除了所有的提示之后，你在最底层进行真正的、线性化的移除。如果运气特别差，你从来没有建多层，所有东西都只在最底层，它仍然是正确的。顺便说一句，查找是无等待的，无论并发发生什么，它总是在有界步数内完成。

LCRQ 和其他主题

现在我进入了讲座中我只是在综述文献中的东西的部分，没有太多细节，但希望给你们一些有趣的指引，你们可以去查找你们特别感兴趣的数据结构的论文。

2013 年，在 PPoPP 上，Alec Morrison 和 Yehuda Afek 引入了链接并发环形队列 (Linked Concurrent Ring Queue, LCRQ)，据我所知，这是地球上最快的并发队列。它比我休息前描述的 MNSQ 快大约一个数量级。一个数量级，快 10 倍。这真的是一个了不起的算法。它极其复杂，有很多边界情况。PPoPP 论文中的伪代码有两个 bug。其中一个是拼写错误，很明显，仔细读的人可能会发现。另一个是逻辑问题。我的学生 Joe Israelovich 解决了这个问题，找出了算法中需要修改什么来修复这个微妙的逻辑问题。他为此感到非常自豪，他给 Alec Morrison 发邮件报告了这个问题和修复方法，Alec 的回复是“哦，是的，我们知道那个，这是我们的修复方法。”他们的修复方法比我们的更好。所以如果你想要这个算法，你应该去 Alec Morrison 的网站，而不是试图从论文中的伪代码构建它，主要是因为将伪代码翻译成正确的 C++ 就有大量的工程工作。所以你应该使用 Alec 创建的版本。

这个算法之所以快，关键在于它使用读取并加一 (fetch-and-increment) 而不是比较并交换。所以并发的冲突操作都在硬件中工作，但在队列中实现这一点并不简单。基于数组的队列已经存在很长时间了，它们使用读取并加一和读取并减一。Eric Freudenthal 和 Alan Gottlieb 在纽约大学大约 1982 年左右提出了并发的基于数组的队列，它们是阻塞的，不是无阻塞的，但它们是基于读取并加一和读取并减一的，并且非常快。这些是为纽约大学的 Ultra 计算机设计的，如果你们中有人了解多处理器历史，那是一台重要的历史性机器。所以使用读取并加一来在数组中找到一个新槽位的想法已经存在很长时间了。

但是如果你试图用这个来实现一个队列，你会有这个问题：假设有一群生产者正在入队，它们都通过做一次读取并加一来找到添加东西的槽位。这是我的槽位，下一个线程，这是它的槽位，下一个线程，这是它的槽位。这很好。我们有出队的线程，消费者，它们过来，它们也在做读取并加一来找到从中移除东西的槽位，从中移除东西的槽位。但假设出队者超前了入队者。我们有一段时间，队列在逻辑上是空的，因为没有生产足够的数据来满足消费者。嗯，消费者在盲目地执行读取并加一，这是我的槽位，这是我的槽位，这是我的槽位，一路向下。而生产者……所以我们可能会有消费者无限次地超前尝试从队列中取东西，这可能把队列的头部推到任意远的地方，这是因为读取并加一指令总是成功的。

优点是，我们没有在同时发生的操作中产生冲突，这些冲突不得不在软件中序列化。硬件正在为我们序列化读取并加一操作，这就是性能的来源。但它引入了这个非常可怕的问题，即消费者超前于生产者，这就是他们在设计这个算法时必须解决的根本挑战：当消费者超前于生产者时我们该怎么办？关键是给队列一种他们称之为**“发脾气”语义 (tantrum semantics)** 的东西，即在代码的某个点，一个线程可以到达一个地方说“我放弃了，我再也不干了，这个队列完蛋了，建个新的吧”。这是允许的。所以你可以把一个队列标记为“坏掉的”，然后继续用下一个。一个坏掉的队列可以被完成，它里面可能还有一些数据，消费者仍然可以把那些数据取出来，但没有人可以再往里面放任何东西了。你想放更多东西，就拿一个新队列。

你可以因为任何理由这样做。你可以因为你尝试出队太多次，远远超前于入队者，你跟上了，头赶上了尾，你不知道……一个生产者找到了一个入队的槽位，用读取并加一预留了它，然后就去睡觉了，并没有实际填充它。某个出队者过来，找到了它应该出队的槽位，但里面什么都没有。所以它需要重试，因为这是一个无阻塞算法，我们不能让它们等待入队者有空来填充。队列中有一些小洞，入队者预留了槽位但还没放东西进去，我们不知道它们什么时候会醒来放东西，我们只是让它被那些槽位搞糊涂了，在这种情况下，我们说“管它呢，建个新的”。它们可以随心所欲地这样做任意多次，并且有一个这些队列的链表。当然，你需要这个链表是无界的，为了让任意数量的生产者超前于消费者，你需要能够将任意数量的缓冲区链接在一起。所以他们实际上有一个 MNSQ，包含了我们之前休息时看到的所有操作，其元素是环形缓冲区，每个缓冲区可能有几千个条目。在环形缓冲区内部，他们使用读取并加一。代码中有很多很多的边界情况，但性能真的惊人。

几分钟后，我将谈到一种叫做对偶数据结构 (dual data structures) 的东西，这是我明天在 Hydra 演讲的一个预告。我的学生 Joe Israelovich 提出了 LCRQ 的对偶版本，所以我在这场演讲中会几次提到它们。

我提到了通用构造 (universal constructions)，我应该回到这个话题，多说几句。通用构造的思想是一种将正确的顺序代码转换成正确的无阻塞并发代码的方法。你可能想这样做有两个原因：一个只是为了知道这是可能的，另一个是得到一个你可能真的想用的算法。这是两个非常不同的动机。

最初的无阻塞构造来自 Morris Herlihy 在 1990 年代的工作，那是为了第一个目的。它是为了论证硬件原语（如 test-and-set、swap 或 compare-and-swap）的相对能力，并了解哪些在根本上比其他更强大，可以用来模拟其他原语。Morris 能够证明，compare-and-swap 和 load-link/store-conditional 是通用原语，因为任何无阻塞数据结构都可以仅使用单字 CAS 或仅使用单字 load-link/store-conditional 来创建。这种通用性的证明是通过展示一个通用构造来完成的，但它不是一个你真的想用来放在你的库里的通用构造。它的存在是为了展示一个原语的形式化能力。

昨晚在船上我和 Morris 聊了一下，关于你是否真的可能为了第二个目的而需要一个通用构造，这一点还不太清楚。几乎任何你能想到的情况，如果你用一个从顺序数据结构自动制造出来的无阻塞数据结构，总会有办法通过手工调整使其更快。如果你要把它放进一个库里，让很多人使用，你可能想通过手工调整让它更快。所以，可能在任何你真的想放进库里的情况下，精心手工制作的算法才是你想要的。

但有时通用构造可能对其他目的有用。特别是，事务内存 (transactional memory) 系统可以被看作是通用构造的升级版，如果它们是无阻塞的。正如我提到的，一些事务内存系统是无阻塞的。有多少人听说过事务内存？好的。有多少人没有？只有几个。这不是一个关于事务内存的讲座，但事务内存的思想是双重的。首先，在程序层面，你说你希望什么是原子的，你不需要说如何使它成为原子的。所以你基本上可以把一段代码括起来说“这里面的东西应该是原子的，亲爱的系统，搞定它”。然后在底层，实现使用了推测 (speculation)。它猜测同时不会有冲突的事情发生，并像没有冲突一样执行。但它也会监视以确保情况确实如此，如果它真的看到了冲突，它就会回退并重试。所以这是一种推测性的实现，它推测的是没有冲突。如果有冲突，它被设计成能够回退和重试。这就是事务内存。

它可以硬件实现，也可以软件实现。软件版本可以是基于锁的，也可以是无阻塞的。大多数是基于锁的，少数是无阻塞的。我知道一个是无锁的，那是 Obstructional STM，这又是 Keir Fraser 的论文工作。我还知道几个是无阻碍的。这些可以被看作是无阻塞的通用构造。所以我可以拿顺序代码，用一个无阻塞的软件事务内存系统来创建一些东西，我可能真的想这样做，即使它会比手工调整的算法慢，因为我得到了一些额外的东西。那就是“升级版”的部分。那个“升级版”的部分是原子可组合性 (atomic composability)。所以如果我想从这个集合中移除一些东西，并把它放到那个集合中，作为一个单一的原子操作，软件事务内存会让我做到这一点，即永远不会有一个可观察到的情况，它既不在这个集合里，也不在那个集合里，或者同时在两个集合里。如果我的库里有一个正确的集合，另一个库里也有一个正确的集合，我没有一个自然的方法把这些操作组合起来，使整个复合操作成为原子的，除非我有一些别的东西。这就是 STM 可能有用的地方。

这里的最后一个要点，我在休息前提到过，是一个由 Erez Petrank 和他的学生们在几年时间里开发的构造，它展示了如何将无锁结构变成无等待结构，使用一种他们称之为快速路径/慢速路径 (fast path/slow path) 的范式。其思想是，大多数时候，你做无锁结构设计要做的事情。所以你有一个优化的、手工编写的、非常酷的、在你的库里的无锁无阻塞数据结构。但你想保证没有线程会永远饿死，而无锁性不给你这个保证。你想要无等待性。所以你做的是，基本上运行无锁算法，如果它迫使你回退和重试，你就回退和重试。你这样做几次，过了一会儿，你变得不耐烦了，你说“我可能在饿死，我不想饿死”。所以你会在一个全局可见的地方写下你正在尝试做什么。每个其他线程都知道，它必须时不时地查看那个全局地方，看看是否有任何人认为自己可能在饿死，如果是，它就必须帮助他们。

这基本上就是思想。它比这复杂得多，但基本思想是，大多数时候，你只做无锁算法会做的事。但偶尔，这对你不起作用，在这种情况下，你宣告这个事实，而其他所有人都偶尔有义务看看你是否有麻烦并帮助你。所以大多数时候，你不会告诉任何人你在做什么，大多数时候你也不试图帮助别人。但如果有任何你可能饿死的危险，你确实会告诉别人，并且你偶尔会寻找那些正在饿死的人，这样他们就不会无限期地饿死。这个构造在实践中可以提供非常好的性能，但它确实要求你有一个大小与线程数成正比的全局结构。

总结与展望

另一个我不想在这里重复的话题，但让我给你们一点广告预告。你们可能已经注意到，在我今天所讲的所有内容中，我隐含地描述了 remove、dequeue 或 pop 操作，在结构为空或你要找的东西不存在的情况下，它们返回 null 或 bottom。但是想一想所有那些你想要一个并发队列的算法。例如，想象一下你的电子商务流水线，你有一个线程负责从网络上接收请求，它把请求解码后放入一个队列。然后你有一个业务逻辑线程池，从那个队列中拉取东西并进行处理。有时它们需要数据库后端的帮助，所以它们把请求放入一个数据库请求队列中。然后有一个线程池负责从那个队列中取出东西并执行数据库操作。你们大多数人可能都见过类似这样的东西。

嗯，这可能是所有并发编程中最常见的队列用法。如果你试图从队列中取出东西，而它是空的，而你是流水线下一阶段的工作者，你该怎么办？你刚刚去找工作，没有工作。所以直到有工作之前，你无事可做。所以最终你必须再看一次，对吧？可能马上，可能等一会儿，但你再看一次。可能还是没有工作。所以可能马上，或者等一会儿，你再看一次。你坐在这个循环里，说“只要无事可做，就继续看”。

嗯，当你继续看的时候会发生什么？你挡了那些试图往队列里放东西的线程的路。你使用了那些试图往队列里放东西的线程想用的处理器资源。它们想在你的核心上运行。所以，你真正想做的是等到有东西可用时再行动，但那是阻塞 (blocking) 的，对吧？我的意思是，我们正在谈论一个无阻塞算法，而你却想为一个你想从一个空数据结构中取出的东西而阻塞，这似乎说不通。但它实际上是说得通的。这就是对偶数据结构 (dual data structures) 的意义所在。它们是一种将条件同步 (condition synchronization) 引入无阻塞数据结构，而又不把它们变成阻塞数据结构的方法。这就是我明天要讲的话题。

关键思想是，当你试图从一个没有你想要的东西的数据结构中取东西时，你转而插入一个请求 (request)。所以如果你想要的东西不存在，比如队列是空的，你往队列里放一个东西说“我想要点东西，顺便说一句，我正在这个信号量上睡觉等着呢，所以我没打扰任何人”。当有人过来，一个生产者，往队列里放东西，或者准备放东西时，他们发现你的预留（reservation）在那儿。他们就不会真的把数据放进队列，而是拿走你的预留并满足它。要做到这一点而不引入阻塞有点棘手，但我们可以做到，我明天会讲。

如果你没注意到，我现在讲到了讲座中我谈论随机话题的部分，我很高兴回答任何关于这些或者之前出现的其他东西的问题。

（问答环节）

提问者：我有一个受 Leslie Lamport 讲座启发的问题。您有没有试过用 TLA+ 来证明算法的正确性？

Michael Scott：我觉得，我没有。这样做已经在我的待办事项列表上好几年了。我能告诉你的就是，我为还没做这件事感到非常内疚。好的，谢谢。

提问者：你谈到了树，显然设计一个无锁的树是一项艰巨的任务。但你怎么看待持久化数据结构呢？在我看来，似乎可以拿一个持久化树的实现，然后只用一个带计数器的 CAS，这样它就应该是无锁的，对吗？

Michael Scott：当你说持久化树时，你是指在数据结构的历史被保存在数据结构中的那种意义上的持久化吗？是的，就像在函数式编程语言实现中那样。是的，这样的数据结构非常方便。它们可以用于支持无等待的查找或聚合操作。假设我想在整个树上执行一个操作，比如把所有元素加起来。我需要搜索整个东西。如果其他操作正在并发地插入和移除东西，逻辑上，它们每一个都与我正在做的事情冲突。在一个直接的实现中，我的操作会被迫一次又一次地重启，我可能会饿死。但是如果我有一个持久化数据结构，在历史保留的意义上，那么我在一开始就确定我要使用哪个版本的数据结构，然后我遍历那个时间快照的实例。而并发进行的其他操作正在创建数据结构在时间上的新实例，我最终会在我的操作开始时附近线性化。但那是完全可以接受的。这是一个非常慢、延迟很长的操作返回，它在线性化后不久就调用了。所以这是那种持久化数据结构的一个 krásný（漂亮的）用法。

“持久化”这个词还有另一个意思，我几分钟后会在一张幻灯片上讲到，那就是关于断电后内存中值的持久性，对吧？我们现在有了字节可寻址的快速内存，它可以在断电后保留值，而且我们很可能在不久的将来会有其他类似的技术出现。对于那些，谈论不仅相对于执行线程，而且相对于断电后回来的恢复线程都正确的并发数据结构是很有趣的。实际上，这两种持久化的定义之间有一个有趣的交集，因为受函数式启发的、在历史保留意义上持久化的数据结构，是构建能够在崩溃后幸存的一致性数据结构的有用工具。我们几年前在 DISC 上有一篇关于一个名为 DALI 的键值存储的论文，它做的就是这个，它在同一篇论文中使用了两种不同类型的持久性。那很酷。

提问者：所以，问题是，似乎有一种廉价的方法来获得一个无锁的树，就是拿一个第一种意义上的持久化数据结构，但是为什么人们不这么做呢？所以你能把它和你提到的无锁树实现比较一下吗？

Michael Scott：是的，这并不像乍一看那么容易。它解决了长时间运行的操作被并发更新不断强制重启的挑战，但它没有解决更新之间的冲突。如果我试图往树里放一个 3，而你试图放一个 4，它们需要有一个共同的父节点，它没有处理这样一个事实，即我们不知何故必须在最新版本的数据结构中同时拥有它们。

提问者：我的意思是，我可以只用一个带版本的 CAS，对吧？

Michael Scott：嗯，在某个点上，会有一个 CAS 决定我们谁先谁后。但也许我们同时在尝试重新平衡树。如果我们把它们都塞进树里，树就会失衡。所以我们中的一个必须做一个旋转，旋转最终会修改几个节点，路径最终会到不同的地方，也许最后我的 3 应该在这里，你的 4 是一个后继者，但它们最近的共同祖先在旋转后在树上四层高的地方。我的意思是，所有这些都得不知何故得到解决。所以更新之间的冲突并不能通过拥有一个持久化数据结构就轻易解决。谢谢。

提问者：你对非线性化数据结构怎么看？在像服务器这样的常见应用中，我们真的需要线性化吗？

Michael Scott：哦，嗯，显然，不需要线性化的东西是有用的。我的意思是，不说别的，看看分布式系统中所有关于最终一致性的工作。显然人们愿意接受那些更新没有明确总顺序的东西，但这并不意味着他们在所有情况下都乐于接受。肯定有一些算法，比如我的银行，我希望确保所有的更新都是线性化的。所以，在共享内存数据结构上，是否有关于非线性化数据结构的有趣研究空间？绝对有。但我主要对那些有 motivating use case 的感兴趣。它们可能仅仅从一个，你知道，智力上、理论上的角度看很有趣，但是，如果你想在那个领域工作，我鼓励你寻找一个对放宽的语义感到满意的应用。谢谢。

提问者：我有一个关于跳表的问题。当你在跳表中插入元素时，你怎么知道你元素上方那个塔的高度，也就是说你应该在上面多少个队列中插入你的元素？

Michael Scott：是的。嗯，在跳表中，你需要一个具有已知统计特性的伪随机数生成器。一个节点上方塔的高度是在插入时选择的，并且更高的高度具有指数递减的概率。所以如果你有一个公平的硬币，你可以通过抛硬币来做这件事。正面，你只在第一层插入。反面，你再抛一次硬币。如果第二次是正面，你在第一层和第二层插入。如果第二次是反面，你再抛一次。所以你想要指数递减的概率，这让你期望每个列表的元素数量是下面列表的一半。是的，是的，这可以追溯到 Bill Pugh 最初的顺序算法。

提问者：我只是有点好奇，我想你在对偶（dual）和组合（combining）的幻灯片中稍微提到了这一点，但是，更普遍地，当在数据结构的各种风格之间选择时，比如阻塞或非阻塞版本，以及它们的各种风格，关于其他性能相关的事情，比如缓存抖动（cache trashing），有哪些重要的考虑因素？比如一些不那么明显的方面。

Michael Scott：这有点像 Trevor Brown 演讲的主题，对吧？有很多实际的考虑因素会影响数据结构的性能。嗯，很多取决于预期的工作负载。你期望有多大的竞争？如果你期望竞争很少，你可能用一个锁锁住整个数据结构就行了，对吧？如果你有很多并发操作，你需要看其中有多少是更新，有多少只是查找。你需要考虑有多少是聚合操作，即查看许多元素，又有多少是局部操作，只作用于一个元素。所以你需要理解工作负载。然后你需要理解像你机器上的调度是如何工作的。抢占是不是一个问题？也许你在一个用于超级计算机的科学计算领域工作，每个线程都有自己的核心，底层没有调度在进行。所以你永远不用担心抢占，在这种情况下，无阻塞可能对你帮助不大。所以你需要理解系统在调度方面做什么。你需要知道是否有异步事件会在你的同一个核心上被服务。你需要理解内存层次结构，这样你才知道一次缓存未命中会花费多少，以及它有多大可能从附近的缓存而不是跨芯片互连的缓存中得到满足。有很多非常有趣的工作仍在进行，关于 NUMA 感知的算法，它们关注机器的哪个芯片旁边放了什么。这个列表长得令人不安。

提问者：我想概括一下第一个问题。可能这里的每个人都知道，对于基于锁的并发程序，我们可以使用像 Valgrind 这样的工具来验证一切都很好。那么对于无阻塞编程，有没有什么工具或者数学符号可以验证一切都很好？

Michael Scott：所以你基本上是在问，有什么样的工具可以用来调试，也许还有基准测试无阻塞算法。既有实践性的工具，也有形式化的工具。在形式化阵营里，有像 TLA+ 这样的东西，它可能让你证明你的算法的属性，你可以用数理逻辑来陈述这些属性。也有模型检查器，它们会或多或少地详尽地探索多线程状态空间，其中一些快得惊人，比你想象的要快得多，它们会在状态空间中进行一种有向搜索。即使它们没有回来告诉你“是的，我已经证明这是正确的”，如果存在 bug，它们很可能很快找到 bug。所以我推荐，对于有能力使用这些工具并希望对自己库里的东西有很高信心的人，我推荐逻辑方法。我推荐模型检查，对于那些无法让基于逻辑的方法工作的人。坦白说，你仅仅通过猛烈地测试一个数据结构，然后看它的不变量是否被破坏，就能取得很大的进展。所以你在你的代码里填满断言，让很多线程涌上去，如果存在问题，它通常很快就会崩溃。这显然不能告诉你没有 bug，只能告诉你存在 bug。但说实话，这是我调试东西的主要方式。谢谢。

最后几张幻灯片

我应该继续讲最后几张幻灯片吗？你觉得可以吗？

主持人：我想你可以再用 10 分钟。好的，稍微推迟一下。

好的。嗯，我还有几件事情想给你们一些提示，因为我觉得它们很酷，如果你们觉得酷，你们应该去查找论文。

其中一个是组合 (Combining) 的概念，它出现在很多无阻塞数据结构中，实际上也出现在阻塞数据结构中。所以它是一个正交的概念，但它以一些很酷的方式出现在一些无阻塞结构中。总的来说，组合的概念是，有时，鉴于你正在构建的数据结构的语义，有些操作可以被组合成一个复合操作，这比将它们单独应用于数据结构要便宜。

典型的例子是栈。如果我思考栈上发生的推入和弹出一系列操作，并且在那个序列中，我看到一个相邻的推入和弹出对，按那个顺序发生，其中弹出操作得到了被推入的值，因为栈是后进先出的，那么这对操作可以出现在序列的任何地方。它在这里，还是在那里，或者在那里，都无关紧要。所以如果我能以某种方式安排推入者和弹出者找到彼此，而不打扰任何人，他们俩都能满意地回家，并且不与任何人产生竞争。这是组合最简单、最经典的例子。

在一个无阻塞算法中，一个简单的方法是，对于一个栈，拿一个像 Treiber 栈那样的东西，但用一个数组来增强它，称之为组合竞技场 (combining arena)。它有 k 个槽位。当我过来要做一个推入操作时，我说，我掷一个骰子，得到一个 1 到 k 之间的数，我查看数组中的那个槽位。如果我尝试做推入时，它里面有一个弹出操作，我说“嘿，太好了”，我抓住那个弹出，把我的值给它，然后我返回。如果另一方面，那个槽位里有一个推入操作，我再试一次，找另一个槽位。或者如果它是空的，我在里面坐一会儿，希望一个弹出操作会找到我。过了一会儿，如果没有弹出操作找到我，那我就去，继续在 Treiber 栈上做我的推入操作。但我等一小会儿，希望碰到一个我可以与之组合的操作。竞技场中的每个槽位都在不同的缓存行中，所以它们不会相互干扰。在高竞争下，你会有大量的推入和弹出操作找到彼此，而不打扰数组的其余部分，你可以在一个我们直觉上认为是内在串行的数据结构——栈上获得惊人的吞吐量。

事实证明，你可以在多种其他结构上进行组合。令人惊讶的是，你可以让它对队列也起作用，即使它们是先进先出的，只要你愿意等一会儿，并且主要在队列中元素数量相当少的时候受益。

最近，嗯，差不多十年前了，Danny Hendler 的团队提出了扁平组合 (Flat Combining) 的概念，这是一种利用局部性 (locality) 和组合之间权衡的可爱方式。我们刚才有一个问题，关于什么使并发算法快或慢，以及你如何知道哪个会快或慢。影响性能的两个重要因素是局部性，换句话说，你有多少缓存未命中，以及并发性，你能让多少东西同时独立工作。有时它们之间存在权衡。扁平组合利用了这种权衡，并试图找到一个最佳点。

基本上，它说，在高竞争下，如果我的数据结构在缓存中，或者我的数据结构的顶层几层在我的机器的一个节点上的缓存中，那么在那个节点上做所有的操作一段时间可能是个非常好的主意，利用缓存的局部性。而在低竞争下，可能最好是让每个人在想做的时候就做自己的独立操作。所以扁平组合的思想是，线程有点像轮流成为数据结构的所有者。我们有常规的数据结构，扁平组合是附加在它上面的东西，它有一个组合竞技场，这是一个写下你想要执行的操作的地方。当你来到数据结构时，你首先看一下，说“竞争高吗？”如果竞争不高，我就做我的操作，那可能涉及一些缓存未命中。如果竞争高，那么我写下我想要做什么，而此刻有别人拥有数据结构。当他们是所有者时，他们会不断地查看组合竞技场，寻找可以相互组合的东西，并处理所有其他的。所以有人负责处理一段时间内到来的所有数据结构上的操作。过了一会儿，它累了，它说“我不再是所有者了，下一个来的线程应该成为所有者”，他们可以处理一段时间内的所有操作。这比每个操作都自行进行能给你更好的局部性，在高竞争下，它会给你比那种天真的方式好得多的性能。

最后两张幻灯片。我的团队的大量工作，正如我几分钟前在那个漫谈的回答中提到的，一直在研究持久性 (persistence)，在崩溃后幸存 (surviving crashes) 的意义上，使用非易失性内存 (non-volatile memory)。在这里，你可以把那些在崩溃后过来试图理解内存中剩下什么东西的线程，看作是与所有其他线程的执行在任意时间点上并发运行，也就是说，能够看到状态。问题当然是，一致性和我们对内存的看法，即使不是顺序一致的，至少也是合理的，是建立在缓存之上的，而缓存，至少在短期内，是易失性的。所以当你断电时，你失去了缓存中的所有东西，而你在内存中拥有的是缓存感觉在断电前想写回去的东西，那可能不是最旧的东西，可能是一些非常新的东西。所以某人可能在一个列表中插入了某个东西，列表中的节点在缓存中丢失了，但指向它的指针实际上被写回了内存。我在崩溃后不能用那个，我有一个指向虚空的指针。

所以，需要做大量的设计工作，使并发数据结构在崩溃后可用，这涉及到强制缓存按顺序写回某些东西。在如何高效地做到这一点上，有很多有趣的挑战，以试图在正常操作期间获得良好性能，并且仍然能够在崩溃后恢复。我很乐意离线与任何人更多地讨论这个问题。

我最后一张幻灯片是关于我的团队目前正在做的另一个我非常兴奋的项目，它与用户级管理极快设备 (user-level management of extremely fast devices) 有关，其中之一就是共享内存。我认为共享内存是一种设备。但是现在有很多设备，比如网络接口、高端 SSD、GPU 或其他片上加速器，它们非常快，每秒可以执行数百万次操作。一个核心无法让它们保持忙碌，一个核心也无法承受每次与设备交互时都进行系统调用进入操作系统的开销。

因此，世界上每个主要的数据中心现在都在使用对快速设备的内核旁路 (kernel bypass) 服务，你的应用程序可以直接访问硬件，而无需通过操作系统。你可以通过给每个应用程序一个单独的页面来访问设备，使其安全，这样它们就不会相互打扰。但操作系统不再能够强制执行公平性 (fairness)。它不能说“根据我启动你的云服务时与你签订的合同，你只能得到 GPU 带宽的三分之一”，对吧？如果我有两个应用程序发出不同大小的请求，一个有大的 GPU 请求，一个有小的 GPU 请求，而设备只是在它们之间交替，那么那个有大请求的将得到不公平的服务份额。所以，如果我们能让这些设备的不同通道实际相互通信，并让操作系统做它历史上的工作，那将是很好的。这就是我们项目的目的，它也适用于共享内存。

所以想象一下，我有一个应用程序，历史上可能使用过 memcached。有人用过 memcached 吗？好的。一个常用的键值存储，它在内存中维护信息，非常频繁地用作电子商务应用中数据库的缓存。memcached 提供了一个通过 Unix 域套接字访问的服务。所以我的应用程序通过套接字与服务器通信，说“请插入这个键值对”，“请查找这个键对应的值”。但是，它在内存里，对吧？所以为什么不直接把它放在共享内存里呢？嗯，因为如果你把键值存储放在共享内存里，而它代表数据库的缓存，我的应用程序和你的应用程序在同一台机器上运行，我的程序是我写的，你的程序是你写的，你不信任我的，这很好，因为我的程序里有一个内存 bug。如果我们把 memcached 映射到我的地址空间，那么我的内存 bug 可能会把它搞得一团糟并摧毁它，那会很糟糕。

在我们正在做的这个名为 Hodor（为《权力的游戏》粉丝准备的）的项目中，思想是拥有一个比应用程序拥有更多权限的库，但它获得这些权限的成本比操作系统系统调用要低。所以如果你信任这个库，因为它是由写 memcached 的人写的，事实上它就是 memcached，你可以把它映射到多个应用程序中，中间的共享空间就是实际的哈希表。现在我可以在这个哈希表中使用受信任的代码执行查找、插入和移除操作，但是我用我自己的线程，我不需要使用调度器，我不需要进入操作系统，我可以非常快地执行我的操作。事实证明，你可以安全地做到这一点，而且在当前的 x86 硬件上，你可以用一种本周在 USENIX ATC 会议上由我的学生 Mohammed Hedayati 介绍的技术，相当便宜地做到这一点。我很乐意离线更多地讨论这个问题。

那是我最后一张幻灯片。论文列表和其他东西可以在那些 URL 上在线找到。感谢大家的关注。