客户端 A 写入 x=1 并收到成功，客户端 B 随后读到 x=0。这个结果是否错误，取决于存储接口承诺的一致性模型。若接口承诺线性一致，且没有其他写入，它就是反例；若只承诺顺序一致，还要检查客户端之间的程序关系；若只承诺最终收敛，仅凭这一次旧读无法判定违反承诺。

上一篇：时钟与因果偏序用 happens-before 描述事件之间的因果关系。本篇把对象的读写规格加入时间线，区分哪些观察可以由一次合法执行解释。MIT 6.5840 和 Stanford CS244B 都将一致性、复制与容错放在课程主线中；这里先建立检查读写历史的工具，下一篇再比较复制协议如何满足这些约束。

先规定一个读写对象

设一个 KV 对象初始所有键的值都是 0。Put(x,1) 把 x 改为 1，并返回 OK；Get(x) 返回当前 x 的值。单线程执行 Put(x,1); Get(x) 时，读取必须得到 1。这个规则称为顺序规格，独立于对象用内存、磁盘还是多个副本实现。

并发历史记录每个操作的调用和返回事件，也记录客户端身份、参数及返回值。W_A(x,1)[1,4] 表示 A 在事件 1 调用写，在事件 4 收到成功。区间中的数字是同一观察者记录的事件序号，不是多台机器各自的墙钟时间。若另一个读的区间是 [2,3]，两次操作重叠；若是 [5,6]，写已经完成后才调用读。

本文采用良构客户端：一个客户端等上次操作返回后再发起下一次调用。现实程序有异步并发时，可以分别建模各条顺序调用链，或者使用支持更一般历史的检查器。把一个线程中没有等待关系的请求强行排成程序顺序，会凭空添加约束。

返回超时的 RPC 还需要另外处理。网络层超时不能直接记成对象执行失败，也不能无条件记成没有发生的写。这个问题延续了 01 篇的 RPC 重试边界：请求可能已执行，只是响应没有到达。本篇实验明确拒绝未完成操作，正文则保留其形式化含义。

线性一致性约束实时先后

一个完整历史是线性一致的，当且仅当存在一个合法的顺序历史，包含相同操作、参数和返回值，并保留不重叠操作的实时顺序。若 a 已经返回之后 b 才调用，顺序历史必须把 a 放在 b 前面。重叠操作可以选择任一顺序，只要全部读写能由同一顺序解释。Herlihy 与 Wing，§2

例如写 W_A(x,1)[1,4] 与读 R_B(x)=0[2,3] 重叠，可以解释成先读后写。虽然读的返回早于写的返回，这本身既没有证明也没有否定线性一致性。若读返回 1，也可以解释成先写后读。线性化点是对这种解释的表达：每次操作仿佛在其调用与返回之间的某个瞬间生效。

1
2
3
4
事件序号     1       2       3       4
A 写 x=1    [-----------------------]
B 读 x=0            [-------]
合法顺序             读0 → 写1

若把读改成 [5,6]，写已在事件 4 返回，合法顺序只能先写后读。没有其他覆盖写时，返回 0 就不合法。复制节点在后台是否最终同步，与这条已经完成的错误读取无关；后来的收敛不能修复历史中已经违反的安全性质。

这个定义没有要求客户端必须读主节点，也没有规定副本数量。它约束接口可见行为。读取主节点仍可能因旧任期、恢复错误或错误的确认点而违反约束；读取副本也可能通过适当协议满足约束。具体读路径需要在协议模型和产品 API 中分别验证。

pending 操作与定义修订

历史 H 可能以某次调用结束，该调用没有匹配的返回事件，称为 pending。线性一致性允许给其中一部分调用补上返回，得到 H′，再去掉仍未完成的调用，检查剩余完整历史。选择补全的操作可能已经改变了对象状态，因此会影响已经返回的读。

设初始 x 为 0，写 1 已调用但没有返回，另一个完整读返回 1。补全写并把它放在读前面，可以解释这个结果。一律删除所有 pending 写，会错误地拒绝这段历史。若读返回 0，也可能通过省略这次 pending 写得到合法解释。

但完整读先返回 1、随后才调用 pending 写 1 的历史不合法。在这段历史中，写调用发生得太晚，无法解释此前的读。Sela、Herlihy 和 Petrank 在 2021 年指出，1990 年论文定义中的一个符号遗漏会使这种反例被错误接受。修正后的实时约束针对补全后保留的操作：complete(H′) 的实时序必须包含在候选顺序中。《Linearizability: A Typo》v2，§3–4

补全是存在性定义中的选择，并不表示检查器替服务器实际执行了一次写。没有返回的操作最终是否完成，仍是活性问题。为了避免把这部分语义压成错误的启发式，本篇程序只接受全部操作均已返回的历史；遇到 pending 明确报“不支持”。

顺序一致保留程序顺序

Lamport 1979 年的顺序一致性要求：执行结果可以解释成一个顺序执行，并且每个处理器的操作保持其程序顺序。移到本篇客户端模型，就是存在一个共同的合法总序，同时保留各客户端自己的先后关系。它不额外保留不同客户端操作之间的外部实时顺序。原论文，印刷页690

A 的写 W_A(x,1)[1,2] 已完成，B 的读 R_B(x)=0[3,4] 才开始。线性一致性不允许这个读值；顺序一致性可以将 B 的读排在 A 的写之前，因为这两次操作没有同客户端程序序约束。这个结论以历史中只包含这些内存操作为前提。如果程序通过另一通信通道传递“写已完成”的信息，建模时就必须说明该通道是否属于待检查对象及其顺序约束，不能一边使用额外同步，一边在解释中将它删除。

同一个客户端先写 1、再读到 0，则连顺序一致性也不满足。候选总序不能倒置它自己的两次操作。多个客户端之间还可能形成更隐蔽的环：A 先写 x=1 再读 y=0，B 先写 y=1 再读 x=0，且没有其他写。

A 的程序序要求 Wx < Ry，读 y=0 又要求 Ry < Wy。B 的程序序要求 Wy < Rx，读 x=0 则要求 Rx < Wx。合起来得到 Wx < Ry < Wy < Rx < Wx，不存在合法总序。这也说明逐个客户端检查“自己的读取似乎合理”不够；顺序一致性仍是整个对象历史的共同约束。

因果顺序与最终收敛

Ahamad 等人的 causal memory 模型把进程内程序顺序和读值所依赖的写联系起来。若进程读取了某次写的值，随后再写另一项数据，后一次写在因果上依赖前一次写。因果序取这些关系的传递闭包。原论文，1995，§4

设 A 写 x=1，B 读到这个 1 后写 y=1。C 先读到 y=1，再读 x=0，而 x 没有其他覆盖写，就违反这条因果依赖。C 观察到依赖写时，其后续观察不能把原因仍放在未来。示例中的写值唯一，因此 read-from 关系清楚；多次写入相同数值时，单凭返回值可能无法识别读依赖哪次写。

因果一致性允许不同进程对没有因果关系的并发写采用不同顺序。以初始 x、y 都为 0 为例，两个进程分别写 x=1、y=1，只读进程 C 可以依次读到 x=1、y=0，另一个只读进程 D 可以依次读到 y=1、x=0。C 的视图把写 y 放在其读取之后，D 的视图则把写 x 放在其读取之后。只要各自的合法视图都遵守因果依赖，原论文模型不要求把这两个独立写固定成所有进程共同采用的总序。

最终一致性常用的收敛条件则是：停止更新以后，在系统满足约定的通信与恢复条件时，副本的观察最终收敛。它没有单独规定“这次读必须返回多新”。持续网络隔离、更新永不停止或消息永不投递时，必须重新检查收敛承诺的前提；不能把这些条件省略后仍宣称无条件收敛。Bailis 与 Ghodsi，2013

因果顺序和收敛回答不同问题。一个产品可以同时承诺两者，也可能另加会话读己之写等条件。“最终一致”这个标签本身不足以推断它是否有这些保证。一次测试最后观察到副本相同，只证明这次有限观察中的事实；它无法证明所有允许的无限执行都会收敛。

CAP 的不可区分执行

Gilbert 与 Lynch 2002 年的证明研究异步网络中的读写对象。这里的 C 是原子一致性，即线性一致性。A 要求每个非故障节点收到请求后，最终返回符合对象规格的响应。网络模型允许任意数量消息丢失，包括两组节点之间的消息一直无法通过。A 不附带统一的毫秒级完成上限。原论文，§2–3

设对象初始为 0，网络被分成 G1、G2，两边节点继续运行。向 G1 写入 1。若算法满足 A，这次写最终必须完成。随后向 G2 读取，由 A，它也必须完成。但 G2 没收到 G1 的任何消息，它无法区分“另一边已经写过 1”和“根本没有写”这两种执行。

在没有写的执行中，读取必须返回 0；因此具有相同局部观察的读取，也会在写已完成的执行中返回 0。后者违反线性一致性。若选择等待通信恢复以确认值，永久分区执行中的请求就无法完成；若返回旧值，则牺牲该执行中的 C。这个推导没有借助特定数据库或某种共识算法。

把所有请求立即返回“服务不可用”，并没有实现上述读写对象的 A。规格要求读返回值、写完成其效果；若另定义一个允许任意拒绝的 API，讨论的已经是另一个任务。实际服务选择拒绝少数派请求可能完全合理，但应报告该路径放弃了怎样的完成保证。

“多数节点仍在服务”也不等于定理中的 A，后者量化到每个非故障节点收到的请求。工程 SLA 允许一定比例失败、限定入口路由或排除维护窗口，可以十分有用，却需要自己的分母和测量方式，不能直接拿百分比替换定理。

分区、超时与恢复的工程解释

Brewer 在 2012 年讨论了“三选二”表述的误导：选择可以落实到不同操作、数据和分区阶段，系统还需要恢复协议。分区期间可以限制某些操作，恢复后再处理冲突；这并不意味着所有业务都能补偿成功。例如同一余额在两边独立扣款，恢复时的数据合并未必能撤销已经发出的商品。IEEE Computer 官方合作转载

网络慢到超过超时阈值时，服务也会面临等待、拒绝或返回本地结果的选择。但这是工程时限下的解释。2002 年定理中的 A 只要求最终完成，并没有把 500 毫秒超时写进定义。纯异步系统无法仅靠等待时间区分永久丢失与极慢传输。

原论文 Corollary1.1 进一步指出：若算法必须在所有允许的执行中可用，就不能只在“所有消息最终都会送达”的执行中保证线性一致。一个已经返回错误旧值的有限前缀，可以继续扩展为所有延迟消息最终到达的执行；消息后来到达不会撤销旧读。因而“无分区时总能同时得到 C 和 A”不能脱离系统模型和算法义务单独引用。

CAP 也没有直接给出事务隔离级别。ACID 中的 C 通常指业务约束的保持，与这里的线性一致不同。单键读取满足线性一致，不自动保证两次读取属于同一快照；这种跨操作原子边界需要在事务章节继续定义。

用独立规格枚举历史

实验代码位于仓库 examples/distributed-systems/consistency06/，使用 Go 标准库。程序不启动存储服务、不打开端口，也不注入真实网络故障。它检查五组人工构造的有限历史，目的在于把定义变成可执行断言。

从 examples/distributed-systems 运行：

1
2
3
go run -race ./consistency06
go run ./consistency06 -scenario sequential-only
go vet ./consistency06

输入每次操作都带调用与返回序号，检查器先验证 ID 唯一、事件唯一、调用在返回之前，并拒绝同一客户端重叠调用。缺少返回的 pending 操作与超过 8 次操作的历史返回“不支持”，不会被当成一致性反例。

随后建立前驱约束。顺序一致模式只保留同客户端顺序；线性一致模式为所有不重叠操作添加实时先后边。DFS 每次选择前驱均已选中的操作，执行独立的顺序 KV 规格。读值不匹配时舍弃该分支；选完全部操作则输出见证顺序。

这套搜索的正确性可以分两边检查。它输出的顺序逐步满足规格，并且每次选择都满足前驱边，因此是合法见证。反过来，若存在合法见证，其下一个操作的前驱必然已经出现在前缀里，搜索会枚举到这个选择；该见证上的读也不会被错误剪枝。操作上限约束了运行规模，最坏仍可能搜索阶乘数量的排列。

场景 线性一致 顺序一致 判定依据
写与读重叠，读0 可 可 见证为读、写
A写已完成，B再读0 不可 可 SC可重排两个客户端
A写后自己读0 不可 不可 程序序禁止倒置
两键写后互读0 不可 不可 共同顺序形成环
没有写却读到9 不可 不可 任意排列都违反规格

本地运行已通过这五组断言、输入边界检查和 go vet。程序还运行一个负向变异：故意删除所有顺序边，三个负例就会被错误接受；返回凭空数值的例子仍被顺序规格拒绝。这区分了排序约束与对象规格的作用。-race 没有发现数据竞争，但这个检查器是顺序程序，结果不能用来证明分布式服务没有并发缺陷。

有限历史通过检查，只表示这些观察存在合法解释。要验证一个实际 KV，还需要可靠采集调用、返回、失败和客户端关系；要证明实现正确，还需要覆盖所有允许执行的不变量与活性论证。本实验没有收集真实产品历史，也没有验证网络分区中的服务完成率。验证记录与论断证据保存在本文同名素材目录。

两道推导题

回复丢失后能否删除写

初始 x=0。A 调用写1后没有收到响应，B 随后完整读取到1。删除 A 的调用后，检查器报告读值非法。这足以证明服务违反线性一致吗？

不足以。A 的写属于 pending，可以在扩展历史中补全并排在 B 的读之前。一个只支持完整历史的检查器应拒绝这样的输入，而不是擅自删除写后给出反例。如果 B 的读已经返回之后 A 才调用写1，且没有其他写，则补全也无法解释读1，因为修订后的实时约束禁止把 A 移到 B 前面。

末尾同步能否修复分区旧读

G1 写1返回成功，之后 G2 读到0。分区恢复后，两边都读到1。若把最后一次同步事件补进历史，之前的结果能否变成线性一致？

不能。原有写返回先于旧读调用的关系仍然存在，且这次旧读的返回值仍为0。除非历史遗漏了合法的覆盖写等关键操作，否则增加后续同步不会消除这条反例。同步结果可以支持“本次最终观察收敛”的记录，却不能把已经违反的实时顺序改写掉。

下一篇 07 将把确认时刻、复制进度与可读状态放进主从复制和 Chain Replication 的故障时间线，检查协议究竟在哪些假设下维持这些读写约束。

参考资料