第五章 线性一致性 (Linearizability)
一、导读
1.1 本章学习目标
深入理解线性一致性（Linearizability）的定义及其作为并发对象正确性标准的意义
掌握线性一致性与顺序一致性（Sequential Consistency）的区别
学会证明一个并发实现是线性一致的
理解线性一致性的组合性（Composability）及其在系统设计中的重要性
掌握线性一致性与其他一致性模型（如最终一致性、因果一致性）的关系
了解线性一致性的检测算法和验证工具
理解线性一致性在分布式系统中的扩展和挑战
1.2 为什么本章如此重要
在并发编程中，"正确性"的含义比顺序编程复杂得多。一个顺序程序的正确性很简单：给定相同的输入，总是产生相同的输出。但一个并发对象的正确性需要考虑所有可能的线程交错——什么样的交错是"正确的"？
线性一致性（Linearizability）是并发对象最强的一致性条件，由 Herlihy 和 Wing 在 1990 年提出。它的核心思想是：每个操作看起来像是在某个瞬间原子地完成的，这个瞬间在操作的调用和响应之间。换句话说，虽然操作可能需要一段时间来完成，但从外部观察者的角度看，它像是在一个时间点上瞬间生效的。
线性一致性之所以重要，首先因为它是程序员最直觉的一致性模型：它保证了每个操作都"立即"生效，程序员可以像编写顺序程序一样推理并发程序。其次，线性一致性具有组合性：如果系统中的每个对象都是线性一致的，那么整个系统也是线性一致的。这意味着可以独立地验证每个组件的正确性，而不需要考虑组件之间的交互。
然而，线性一致性也是一个很强的条件，实现它的代价可能很高。在分布式系统中，线性一致性要求所有节点对操作顺序达成一致，这涉及共识问题，代价更大。理解线性一致性的本质和代价，对于在一致性和性能之间做出合理的权衡至关重要。
1.3 核心问题引导
什么是线性一致性？它如何用形式化的语言来定义？
线性一致性和顺序一致性有什么区别？一个对象可以顺序一致但不线性一致吗？
如何证明一个并发实现是线性一致的？有哪些常用的技术？
线性一致性的组合性意味着什么？为什么它对系统设计如此重要？
在分布式系统中实现线性一致性的挑战是什么？CAP 定理如何约束一致性？
线性一致性的代价有多大？在什么场景下可以放宽一致性要求？
二、核心概念详解
2.1 线性一致性的形式化定义
线性一致性的定义基于操作的历史（History）。一个历史是一系列操作的调用事件（invocation）和响应事件（response）的序列。
一个历史 H 是线性一致的，如果存在一个合法的历史 S（即一个顺序执行的历史），满足以下条件：
等价性：H 和 S 等价。两个历史等价是指它们包含相同的操作，且每个操作的响应相同。这里的"等价"通过每个线程的视角来定义：在每个线程的视角中，操作的顺序和结果相同。
实时顺序性：如果操作 A 在 H 中于操作 B 开始之前完成（即 A 的响应在 B 的调用之前），那么在 S 中 A 也必须在 B 之前。
合法性：S 是对象的一个合法顺序历史，即 S 中的操作按照对象的顺序语义执行。
直观理解：线性一致性要求每个操作可以"收缩"到调用和响应之间的某个时间点上，使得所有操作按这些时间点排序后，形成一个合法的顺序执行。
2.2 线性一致性 vs 顺序一致性
顺序一致性（Sequential Consistency）由 Lamport 定义：所有处理器的操作以某种全局顺序交错执行，每个处理器的操作保持其程序顺序。
线性一致性和顺序一致性的关键区别在于：线性一致性要求尊重实时顺序（如果 A 在 B 之前完成，则 A 必须在 B 之前），而顺序一致性不要求。
一个经典的例子：两个线程分别对两个不同的变量 x 和 y 进行写操作，然后读取另一个变量。在顺序一致性下，只要存在某种全局顺序使得结果合法即可；在线性一致性下，还需要尊重写操作的完成时间。
线性一致性比顺序一致性更强：线性一致 ⟹ 顺序一致，但顺序一致 ⟹̸ 线性一致。线性一致性的优势在于它的组合性：顺序一致性不具有组合性——两个顺序一致的对象组合在一起可能不是顺序一致的。
2.3 线性一致性的证明技术
证明一个并发实现是线性一致的，通常需要构造一个"抽象函数"（Abstraction Function），将实现的状态映射到抽象对象的状态，并证明每个操作的效果等价于在某个时间点上对抽象对象执行相应的操作。
常用的证明技术包括：
基于线性化点（Linearization Point）的证明：为每个操作确定一个"线性化点"——操作在这个点上被视为原子地生效。对于成功的操作，线性化点通常是某个原子操作（如 CAS）成功的时刻。对于失败的操作，线性化点可以是调用时刻或响应时刻。证明需要验证：按照线性化点排序后的操作序列是合法的。
基于前进模拟（Forward Simulation）的证明：定义实现状态和抽象状态之间的关系（模拟关系），证明实现的每一步都对应抽象对象的一步。
基于冲突可串行化（Conflict Serializability）的证明：构建操作的冲突图（Conflict Graph），如果图是无环的，则操作可以串行化。
2.4 线性一致性的组合性
线性一致性的一个关键性质是组合性（Composability）：如果系统中的每个对象都是线性一致的，那么整个系统也是线性一致的。
组合性的证明很直观：每个对象都有一个合法的历史 S_i，将所有 S_i 按照实时顺序合并，得到的全局历史也是合法的。这是因为线性一致性的实时顺序约束保证了不同对象的操作可以正确地交错。
组合性的重要性在于它支持模块化设计：可以独立地实现和验证每个对象，然后将它们组合成一个更大的系统，而无需重新验证整个系统。这大大简化了复杂并发系统的设计和验证。
相比之下，顺序一致性不具有组合性。两个顺序一致的对象组合在一起，可能因为操作交错导致不满足任何合法顺序。
2.5 分布式系统中的一致性
在分布式系统中，线性一致性的实现面临额外的挑战。分布式系统中的多个节点通过网络通信，网络延迟是不确定的，节点可能崩溃，消息可能丢失或乱序。
CAP 定理（由 Eric Brewer 提出）指出：在分布式系统中，一致性（Consistency）、可用性（Availability）和分区容忍性（Partition Tolerance）三者不可兼得。当网络分区发生时，系统必须在一致性和可用性之间做出选择。
线性一致性要求强一致性（C），因此在网络分区时可能不可用。许多实际的分布式系统选择放宽一致性要求以获取更高的可用性和性能：最终一致性（Eventual Consistency）保证在没有新更新的情况下，所有副本最终会达成一致；因果一致性（Causal Consistency）保证因果关系相关的操作按因果顺序执行。
三、深入分析与讨论
3.1 线性一致性的代价
线性一致性是最强的一致性条件，实现它的代价也最高。在单机多处理器环境中，线性一致性要求内存操作满足顺序一致性模型，这可能需要额外的内存屏障（Memory Barrier）指令来防止处理器和编译器的重排序。
在分布式环境中，线性一致性的代价更高。每个写操作需要同步到所有副本（或至少达到法定人数 Quorum），每个读操作需要读取最新的值。这意味着每次操作都涉及网络通信，延迟远高于本地操作。
许多系统通过放宽一致性来换取性能。例如，DNS 使用最终一致性（TTL 过期后更新传播）；社交媒体的"赞"计数可能暂时不一致（不同用户看到的数字可能不同）；分布式数据库通常提供多种一致性级别供用户选择。
3.2 弱一致性模型
除了线性一致性，还有许多更弱的一致性模型，它们在特定场景下可能更合适。
顺序一致性（Sequential Consistency）：不要求尊重实时顺序，只要求存在某种合法的全局顺序。比线性一致性弱，但在某些场景下足够。
因果一致性（Causal Consistency）：保证因果相关的操作按因果顺序执行，非因果相关的操作可以以任意顺序被不同观察者看到。比顺序一致性弱，但在社交网络等场景中更自然。
最终一致性（Eventual Consistency）：保证在没有新更新的情况下，所有副本最终会达到一致。是最弱的一致性模型，但提供了最高的可用性和性能。
3.3 线性一致性的检测
在实际系统中，如何检测一个实现是否满足线性一致性？Knossos 和 Porcupine 等工具通过分析操作的历史记录来检测线性一致性。
检测算法的基本思想是：尝试找到一个合法的历史 S，使得 S 与观察到的历史 H 等价且满足实时顺序约束。这可以建模为一个搜索问题：在操作的所有可能排列中搜索满足条件的排列。
由于搜索空间可能很大（n! 种排列），实际的工具使用各种剪枝策略来加速搜索。对于大规模的历史记录，检测可能是 NP 难的，但实际中的启发式方法通常能在合理时间内完成。
四、实践案例
4.1 线性一致的注册表
最简单的线性一致对象：一个单写多读（SWMR）的注册表（Register）。
实现：使用一个原子变量存储值。写操作通过 CAS 更新值，线性化点为 CAS 成功的时刻。读操作直接读取值，线性化点为读取完成的时刻。
证明线性一致性：对于每个写操作，其线性化点为 CAS 成功的时刻；对于每个读操作，其线性化点为读取完成的时刻。按照这些时间点排序，每个读操作返回的值等于之前最近一次写操作写入的值。
4.2 线性一致的 FIFO 队列
一个基于数组的线性一致 FIFO 队列。使用两个原子变量 head 和 tail 分别表示队列的头部和尾部。
入队操作：通过 CAS 递增 tail，将元素放入 tail 位置。线性化点为 CAS 成功的时刻。
出队操作：通过 CAS 递增 head，返回 head 位置的元素。线性化点为 CAS 成功的时刻。
证明需要处理一个微妙的问题：入队和出队操作可能交错执行，需要确保每个出队操作返回的是正确位置的元素。
五、常见误区与注意事项
5.1 混淆线性一致性和线程安全
线程安全只保证不会出现数据竞争（Data Race），不保证操作的语义正确性。一个线程安全的计数器可能不是线性一致的——如果 increment 操作不是原子的，两个线程同时 increment 可能导致丢失更新。
5.2 忽视内存序的影响
在弱内存模型的处理器上，即使使用了 CAS，如果不设置正确的内存序，操作的可见性可能不满足线性一致性。默认使用 seq_cst 是最安全的选择。
5.3 在分布式系统中追求强一致性
在分布式系统中，线性一致性的代价可能过高（延迟、可用性损失）。许多应用可以接受更弱的一致性模型。在选择一致性级别时，应该根据业务需求来权衡。
5.4 认为线性一致性可以独立验证
线性一致性的组合性允许独立验证每个对象，但前提是对象之间的交互不引入新的约束。如果多个对象之间有跨对象的不变量，需要额外验证。
六、本章小结
本章深入探讨了线性一致性——并发对象最强的正确性标准。线性一致性要求每个操作看起来像是在调用和响应之间的某个瞬间原子完成的。它比顺序一致性更强，且具有组合性——可以独立验证每个对象然后组合。证明线性一致性通常通过确定操作的线性化点来实现。在分布式系统中，线性一致性的实现受 CAP 定理的约束，代价较高。许多实际系统选择更弱的一致性模型来换取性能和可用性。
七、思考题与练习
给出一个顺序一致但不线性一致的执行历史的例子。
证明：如果一个对象是线性一致的，那么它一定是顺序一致的。
为一个基于 CAS 的原子寄存器确定线性化点，并证明其线性一致性。
分析以下场景是否满足线性一致性：两个线程分别对 x 和 y 写 1，然后分别读取 y 和 x。两个线程都读到 0。
解释为什么顺序一致性不具有组合性，给出一个反例。
设计一个检测线性一致性的算法。分析其时间复杂度。
比较线性一致性和最终一致性在以下场景中的适用性：（a）银行转账；（b）社交媒体的点赞计数；（c）DNS 解析。
研究 CAP 定理，讨论在以下系统中如何权衡 C、A、P：（a）分布式键值存储；（b）分布式消息队列。