无锁链表

在多核处理器的世界里，传统的锁机制可能成为主要的性能瓶颈，迫使线程空闲等待，从而阻碍了可伸缩性。无锁编程提供了一种强大的替代方案，允许多个线程同时操作共享数据结构，而无需互相阻塞。然而，这种并行性引入了显著的复杂性，产生了极难管理的微妙竞争条件。本文将探讨最基本的无锁数据结构之一：链表。

本文旨在提供一份全面的指南，以理解无锁链表之间错综复杂的协作关系。第一章“原理与机制”将解构核心概念，从原子性的“比较并交换”（CAS）操作入手。它将引导您了解常见的陷阱，如臭名昭著的 ABA 问题，并解释安全节点删除和内存回收所需的复杂解决方案。随后，“应用与跨学科联系”一章将理论与实践联系起来，展示这些原理如何用于构建高性能的队列、缓存和调度器，这些构成了现代操作系统、数据库和大规模应用的支柱。

想象一个繁忙的厨房，许多厨师都想在同一个操作台上工作。传统方法是每次只给一位厨师一个特殊的信物——一把锁——授予他们独占访问权。当一名厨师工作时，其他所有人都必须等待。这种方式安全，但效率极低。如果我们能设计一个系统，让所有厨师都能同时工作，通过微妙、闪电般的姿态协调他们的行动，从不互相妨碍，那会怎样？这就是无锁编程的承诺，一场并发执行的美妙而复杂的舞蹈。在本章中，我们将以朴素的链表为舞台，踏上理解使这场舞蹈成为可能的基本原理的旅程。

整个无锁数据结构的大厦建立在现代处理器提供的一个强大工具之上：原子操作。其中最常见的一种被称为​​比较并交换​​（Compare-And-Swap），简称 ​​CAS​​。

想象一下，你想更换图书馆书架上的一本书。在伸手去拿之前，你先在脑海里拍下一张快照：“我期望在 C4 位置找到《白鲸记》。”你走过去，就在放下你的新书《了不起的盖茨比》之前，你再次确认：“《白鲸記》还在 C4 位置吗？”如果还在，你就交换书籍。然而，如果另一位图书管理员已经用《战争与和平》替换了它，你的期望就被打破了。你不会盲目地把你的书塞进去；你会退后一步，注意到这个变化，然后重新思考你的计划。

这正是 CAS 所做的事情，但它是在一个单一、不可分割、瞬时的步骤中完成的。CAS(address, expected_value, new_value) 操作的含义是：“查看内存地址 address。如果其内容正是我所期望的 expected_value，就用 new_value 更新它，并告诉我操作成功。否则，什么都不做，并告诉我操作失败。”

这个简单的条件更新就是我们的原子性握手。在多线程同时操作可能引发的混乱中，它是唯一的顺序保证。有了它，我们可以构建这样的算法：线程推测性地执行工作，然后尝试用一个 CAS 来“提交”它们的更改。如果成功，它们的工作就完成了。如果失败，这意味着世界已经改变，它们必须根据新的状态重试。

让我们从一个简单的结构开始：一个后进先出（LIFO）的栈，它被实现为一个只访问 head 节点的链表。

要​​推入 (push)​​ 一个新值，线程会“离线”创建一个新节点。它将这个新节点的 next 指针指向它当前看到的栈 head。然后，它使用 CAS 尝试将全局 head 指针从旧的头部切换到它的新节点。

要​​弹出 (pop)​​ 一个值，线程会读取当前的 head 及其 next 节点。然后，它使用 CAS 将 head 指針指向那个 next 节点，从而有效地移除顶部元素。

这种“读取、修改、CAS”的循环是无锁算法的基本模式。但是，一个操作究竟在何时生效？这由一个至关重要的概念——​​线性一致性 (linearizability)​​ 来回答。对于这些算法，操作被认为在成功执行 CAS 的那一瞬间发生。 在那一瞬间之前，推入或弹出操作尚未发生。在那一瞬间之后，它已经发生，并对整个系统可见。这为我们提供了一种方法来理解我们混乱的厨房：想象每个厨师的动作，无论准备了多久，都在一个单一的原子瞬间发生。

我们基于 CAS 的优雅栈看似完美，但它隐藏着一个微妙而危险的缺陷，称为 ​​ABA 问题​​。这是一个可能导致数据结构损坏的身份识别错误。

让我们来看一个故事：

1. 线程 $T_1$ 想要从一个栈中弹出一个元素，该栈的头部是节点 $A$，指向节点 $B$。$T_1$ 读取头部，得到 $A$，并确定新的头部应该是 $B$。它准备执行 CAS(, A, B)。
2. 但在它执行之前，操作系统让 $T_1$ 进入休眠状态。
3. 在 $T_1$ 休眠期间，线程 $T_2$ 出现了。它弹出 $A$，于是头部变为 $B$。然后它又弹出 $B$，头部变为 $C$。
4. 现在，$T_2$ 推入一个新节点。巧合的是，内存分配器给了它与原始节点 $A$ 完全相同的内存地址。我们称这个新节点为 $A'$。$T_2$ 将 $A'$ 推入栈中，所以头部现在是 $A'$。
5. $T_1$ 醒来了！它继续执行 CAS(, A, B) 的计划。它检查头部，看到它指向地址 $A$（实际上是 $A'$，但地址相同！），于是 CAS 成功了。头部现在被错误地设置为 $B$——一个已经被弹出并且可能是垃圾内存的节点。我们刚刚丢失了节点 $A'$，并损坏了我们的栈！

这就是 ABA 问题：指针值从 $A$ 变为 $B$ 又变回 $A$，欺骗了 CAS。为了战胜这个幽灵，我们需要的不仅仅是地址；我们需要知道指针的历史是否发生了变化。

解决方案是给我们的指针加上“标签”或“戳”。head 不再仅仅是一个指针，而是一个组合：(pointer, version)。每次我们成功地对头部进行 CAS 操作时，我们都增加版本号。[@problem-id:3205711]

在我们的故事中，$T_1$ 会读取 (A, version=0)。在 $T_2$ 的一番操作后，头部会变成 (A, version=3)。当 $T_1$ 醒来并尝试 CAS(, (A, 0), (B, 1)) 时，比较会失败，因为当前的版本（3）与它期望的版本（0）不匹配。数据损坏得以避免。

解决了 ABA 问题后，我们可以从简单的栈转向通用的链表，我们可以在任何位置插入和删除。

​​插入​​遵循一个极其安全的原则：在公开新节点之前，完全在一旁准备好它们。要在一个前驱节点 $P$ 之后插入一个新节点 $N$，我们首先将 $N$ 的 next 指针设置为 $P$ 的 next 指针当前指向的内容。只有当 $N$ 完全构建好之后，我们才尝试对 $P.next$ 进行一次 CAS 操作，将其指向 $N$。这确保了任何其他遍历列表的线程要么看到插入前的列表，要么看到插入后的列表，但绝不会看到部分构建的、损坏的状态。

​​删除​​则要狡猾得多。你不能简单地找到一个节点的前驱，然后通过 CAS 操作让其 next 指针绕过该节点。为什么？因为在你寻找前驱节点时，另一个线程可能正好在你想要删除的那个节点上，准备读取它的 next 指针！如果你釜底抽薪，那个线程就会持有一个悬空指针。

解决方案是一个优雅的两阶段过程：先标记，后移除。

1. ​​逻辑删除（标记）：​​ 你不是立即断开一个节点的链接，而是首先将其标记为“逻辑上已删除”。这通常通过使用 CAS 在其 next 指针中设置一个特殊位来完成。这个 CAS 是线性化点：删除合法发生的时刻。该节点现在成了一个幽灵；它物理上还在列表中，但逻辑上已经消失了。[@problem-id:3245595]
2. ​​物理删除（断链）：​​ 节点被标记后，必须在物理上断开链接。这通过对前驱节点的 next 指针进行第二次 CAS 操作来完成，使其绕过被标记的节点。

这个方案真正的美妙之处在于​​协作​​机制。任何线程在遍历过程中遇到一个被标记的节点时，可以——也应该——帮助完成物理删除。如果一个线程标记了一个节点然后被延迟，系统不会因此停滞。其他线程会在发现这些被标记的“幽灵”时清理它们。这种协作清理是使该算法成为​​无锁​​的核心：它保证了整个系统总是在向前推进。[@problemid:3245680]

我们已经构建了一台宏伟、精巧的机器。我们用版本标签击败了 ABA 幽灵。我们设计了一种协作式的删除策略。但还剩下最后一个巨大的挑战：我们该如何处理已删除节点的内存？

如果我们立即将被物理断链的节点的内存返还给操作系统，灾难就会发生。一个线程 $T_1$ 可能仍然持有着指向那个节点的指针，这是它在该节点被断链前一刻读取的。如果当 $T_1$ 暂停时，这块内存被释放并重新分配，那么当它醒来时，它将持有一个指向垃圾数据的“悬空指针”，导致“释放后使用”（use-after-free）的错误——这是并发编程中最可怕的噩梦之一。

这揭示了仅靠版本化指针并非完整的解决方案。它们解决了 CAS 逻辑中的 ABA 问题，但没有解决内存生命周期中的 ABA 问题。我们需要一个​​安全的内存回收​​方案。我们不能释放内存，除非我们绝对确定没有任何线程还在查看它。两种主要策略应运而生。

1. ​​风险指针 (Hazard Pointers, HP):​​ 这是一种个人声明系统。在一个线程解引用一个指针之前，它会在自己的“风险列表”中公开声明：“我将要使用这个指针，请不要删除它！”内存管理器在释放一块内存之前，必须检查所有线程的风险列表。如果该内存地址在任何列表上，就不能释放它。这是一个简单直接的约定，可以防止“释放后使用”的错误。

2. ​​基于纪元的回收 (Epoch-Based Reclamation, EBR):​​ 這是一種同步的批处理系统。时间被划分为“纪元”。当一个线程想要读取列表时，它会加入当前的全局纪元。当一个节点被删除时，它会被放入该纪元的一个“退休列表”中。在纪元 $E$ 中退休的节点的内存，只有在一个“宽限期”过去后才能被释放，这个宽限期被定义为每一个线程都已经进入大于 $E$ 的纪元的那一刻。这就像在关灯锁门之前，等待教室里的所有人都离开一样。

这两种方法揭示了一个深刻的权衡。在 EBR 中，如果单个线程停滞或卡在一个旧的纪元中，它会阻止任何内存被系统性地回收，可能导致内存无限增长。相比之下，使用风险指针，一个停滞的线程只会阻止它正在积极查看的少数几个节点被释放。影响是局部的。

通往一个正确的无锁链表的旅程，是并发思维的一堂大师课。它始于 CAS 的简单力量，但很快就迫使我们面对像 ABA 问题这样的微妙幽灵、多阶段操作的复杂性，以及最后，在时间本身都是相对的世界里内存生命周期的根本问题。由此产生的算法是一曲协作的交响乐，线程并行工作，含蓄地互相帮助，以维持一个一致且正确的现实，而无需停下来等待。

在经历了无锁链表错综复杂的原理和机制的旅程之后，你可能会问一个非常合理的问题：“这一切都非常巧妙，但它存在于哪里？它有什么用？”这是一个极好的问题，因为答案揭示了这些抽象概念并不仅仅是智力上的好奇。它们是我们整个数字世界中无形而不知疲倦的建筑师。我们即将看到，从这个听起来很简单的概念——无锁地将节点连接在一起——我们可以构建出操作系统、数据库以及互联网结构的核心机制。

我们可以用无锁链表做的最直接、最明显的事情就是构建其他基本的数据结构。想象一下，你有多个工作者——计算机程序中的线程——需要进行通信。一个工作者生产一项工作，另一个消费它。你如何交接工作？你可以把它放进一个共享队列里。生产者添加到队尾，消费者从队首取走。一个无锁队列，比如经典的 Michael–Scott 队列，对于这项任务来说是一个效率惊人的奇迹。仅仅使用原子性的比较并交换（CAS）操作，线程就可以以最小的干扰入队和出队。如果一个线程变慢了，它不会让整个系统停滞不前。这种队列是无数系统跳动的心脏：Web 服务器用它将传入的请求分发给工作线程，用户界面框架用它处理事件，并行计算也用它来划分任务。

当然，如果我们能构建一个队列（先进先出），我们也能构建它更简单的表亲——栈（后进先出）。无锁栈甚至更容易实现：你只需在列表头部添加和移除元素。而计算领域最基本的问题之一是什么？管理内存。当一个程序用完一块内存时，它会“释放”它。那块内存去了哪里？它会进入一个“空闲列表”，准备被重用。这个空闲列表通常被实现为一个栈。使用无锁技术，我们可以构建一个速度极快的内存分配器，线程可以抓取和归还内存块而无需彼此等待。我们甚至可以做得更复杂，创建一个空闲列表数组，每种常见的块大小对应一个列表——即“分离式列表分配器”——这是现实世界中 malloc 实现的常见设计。所以，从一个朴素的链表开始，我们构建了操作系统本身的基石！

这一切听起来很美妙，但自然不会轻易泄露她的秘密。当你踏入无锁编程的世界，你会遇到一些迷人而微妙的挑战——必须用智慧和洞察力来驯服的恶龙。

其中最著名的一个是 ​​ABA 问题​​。想象一个线程读取一个内存位置，看到值 A。它去做其他工作，并计划回来对该位置进行 CAS 操作，前提是它仍然是 A。但在它离开期间，其他线程来了，将值从 A 改为 B，做了一些工作，然后又把它改回 A。当我们的第一个线程回来时，它查看该位置，看到 A，然后想：“啊哈！什么都没变。”但一切都变了！它现在看到的 A 可能是一个指向完全不同数据的指针，只是恰好驻留在同一个内存地址上。基于这个错误假设的 CAS 操作可能导致灾难性的列表损坏。

我们如何解决这个难题？我们需要一种方法来不仅知道值，还要知道它的历史。一个漂亮的解决方案是使用“带标签”或“带戳”的指针。我们不只存储指针 A，而是存储一个对：(A, version)。每次更新指针时，我们都增加版本号。所以序列变成了 (A, 0) -> (B, 1) -> (A, 2)。现在，当我们的原始线程返回时，它期望看到 (A, 0)，但它发现的是 (A, 2)。CAS 失败，灾难得以避免。只要版本号不会过快地回绕，这个简单的版本控制就足以防范 ABA 问题。其他解决方案，如风险指针或基于纪元的回收，从另一个角度解决了这个问题：它们阻止内存管理器重用地址 A，直到它绝对确定没有任何线程可能还在查看旧的 A。

另一条恶龙是​​性能​​。无锁并不总是意味着快。考虑两个线程试图向列表头部添加元素。线程 1 读取头部，准备好它的 CAS。线程 2 也做了同样的事情。它们同时发出 CAS 请求。两者都失败了。于是它们都立即重试。它们再次读取头部，准备，然后再次 CAS。它们又失败了。这可能永远持续下去！线程们都在忙碌，消耗 CPU 周期，但没有实际工作完成。这是一种被称为​​活锁 (livelock)​​ 的病态。这就像两个过分礼貌的人试图通过一扇门，每个人都说“你先请”、“不，你先请”，结果谁也没动。解决方案非常简单：打破对称性。我们引入一点随机性。在 CAS 失败后，线程等待一个随机的时间再重试。这种“概率性退避”使得线程持续碰撞的可能性变得微乎其微，系统得以再次取得进展。

关于争用的这个想法引出了另一个关键见解。数据结构的不同部分并非生而平等。列表的头部通常是许多线程试图进行更改的“热点”。然而，在长列表的深处进行插入则是一个安静得多的事情；不太可能有另一个线程在完全相同的位置工作。我们可以从数学上对此进行分析。使用概率论的模型，比如泊松过程，我们可以计算出一次插入的预期重试次数。结果证实了我们的直觉：头部的争用程度远高于中间部分。头部插入的重试次数可能要大几个数量级，特别是当列表变长时。这不仅仅是一个学术练习；它告诉真实系统的设计者要警惕那些将所有活动都集中在单一热点上的算法。

有了这些健壮且被充分理解的构件，我们现在可以组装出远为复杂和强大的系统。

一个简单的有序链表搜索起来很慢。​​跳表 (skip list)​​ 是一个绝妙的增强——它是一个带有多个“快车道”的链表。节点被随机提升到更高级别的列表中，这些列表跳过许多中间节点，从而实现闪电般的快速搜索。我们可以构建并发跳表，允许线程在不锁定整个结构的情况下进行插入、删除和搜索。通过使用“乐观搜索”（无锁搜索）策略，然后只锁定需要更改的少数几个节点，我们可以构建高性能、可 beautifully 伸缩的内存数据库和搜索索引。

另一个普遍应用是​​缓存 (caching)​​。几乎每个高性能系统，从 CPU 到 Web 浏览器，都使用缓存来将频繁访问的数据放在手边。决定在缓存中保留什么的一个常见策略是“最近最少使用”（LRU）。每当一个项目被访问时，它就被移动到列表的“最近使用”端。当缓存已满并且需要添加一个新项目时，“最不常使用”端的项目就会被驱逐。这个列表的头部、尾部和中间部分都在不断地被修改。构建一个并发 LRU 缓存需要一个可以被多个线程同时安全修改的双向链表。这引入了一个新的难题：死锁。如果线程以任意顺序锁定节点，它们可能最终陷入循环等待。解决方案是一个优雅的规则：始终以固定的全局顺序获取锁（例如，根据它们在列表中的位置或它们的内存地址）。这个简单的纪律使得死锁变得不可能，从而能够构建高效、可伸缩的缓存。

现实世界甚至更复杂。系统中的一个对象通常同时参与多种关系。考虑操作系统调度器中的一个任务。它可能存在于一个按优先级排序的列表上，同时又存在于另一个按截止日期排序的列表上。当我们删除这个任务时，我们必须将它从两个列表中移除，并且整个操作必须看起来是原子的。这是一个巨大的挑战。一个健壮的解决方案结合了我们所见过的技术：首先，使用原子性的 CAS 通过设置一个标志来“逻辑删除”任务。这个单一的操作赢得竞争，并确保删除只发生一次。然后，获胜的线程可以继续进行物理清理，小心地获取任务在两个列表中邻居的锁（使用全局锁顺序以防止死锁）并断开它的链接。这个模式是在大规模并发软件中管理复杂、相互关联状态的关键。

旅程并未在算法层面结束。为了获得终极性能，软件必须与其运行的物理硬件保持和谐。现代多核处理器拥有复杂的内存层次结构。对于给定的 CPU 核心，一些内存是“本地的”，访问速度非常快。其他内存是“远程的”，属于同一芯片上的另一个处理器，访问速度要慢得多。这被称为​​非一致性内存访问 (NUMA)​​。

一个没有意识到这种“内存地理”的算法可能会遭受巨大的性能损失。想象一下我们并发列表的一个天真实现，其中头部和尾部指针存储在 CPU 0 的内存中，但 CPU 1 上的线程却不断地尝试访问它们。CPU 1 的每一次操作都将招致远程内存访问的高昂成本。一个更聪明的、NUMA 感知的策略将是这样设计数据结构，使得线程主要操作本地内存。例如，可以对列表进行分区或使用每节点哨兵，确保 CPU 0 上的线程处理结构的一部分，而 CPU 1 上的线程处理另一部分。通过将算法及其数据布局策略与硬件架构协同设计，我们可以实现吞吐量的巨大提升。这揭示了一个深刻的真理：最优雅的算法是尊重机器物理现实的算法。

所以，我们看到了完整的弧线。我们从一个简单、抽象的原则——链表上的原子更新——开始。这让我们能够构建构成并发程序管道的基本队列和栈。我们学会驯服 ABA 问题、活锁和争用热点这些微妙的恶龙。然后，我们使用这些经过强化的构件来构造复杂的缓存、数据库和调度器。最后，我们调整这些结构，使之与处理器的物理硅片和谐共存。

下次你加载网页、玩多人游戏，甚至只是在屏幕上移动鼠标时，花点时间欣赏一下你电脑内部发生的无声而激烈的芭蕾舞。数以万亿计的电子在流动，由这些极其聪明的无锁算法精心编排，确保成千上万的并发任务能够无缝、高效、正确地协作。这正是让我们的现代世界成为可能的美丽、看不见的机器。