CAP 与一致性模型

一致性模型规定客户端允许观察到哪些执行历史。讨论“读到新数据”之前，先明确对象、操作、客户端顺序与完成时间；讨论“可用”之前，先明确是在说数学模型里的终止性质，还是实际服务的成功率与延迟目标。

CAP：冲突发生在特定故障模型与保证之间

CAP 的 C 通常指原子读写寄存器的线性一致性；A 要求到达非故障节点的操作最终完成；P 表示模型允许节点之间的消息被分区阻断。A 没有统一的毫秒延迟上界，也不是随便返回一个错误页面就满足服务操作的完成契约。

若允许任意长的网络分区，就不能同时保证这样的 C 与 A。它不是让架构师任选两个字母，也不是说所有真实网络必然在某一天发生某种固定形式的分区。Gilbert 与 Lynch：CAP 的理论与实践视角

在 x 初始为 0、没有其他写入的前提下，A 上写 1 已成功，随后 B 收到读请求。B 无法通过消息区分“对面完成写 1”和“对面根本没写”两个世界，却要作出符合历史的回答。一直等也无法在永不恢复的分区中满足终止要求。

系统可以在多数侧继续完成某些强一致操作，在少数侧拒绝或等待；也可以对特定业务允许本地更新并在恢复后合并。CAP 并不要求整个产品在所有接口上永久选择同一个字母标签。

线性一致性：操作像在调用与返回之间瞬间生效

对一个对象的操作历史，若能把每个已完成操作放在自己的调用与返回之间的某一点，并得到符合对象规范的顺序执行，就具有线性一致性。若 A 已返回后 B 才调用，A 必须排在 B 之前；时间重叠的操作则可以按任一合法顺序排列。

例如 write(x=1) 返回后才调用 read(x)，且没有其他写入，则读必须返回 1。如果读与写重叠，返回旧值 0 或新值 1 都可能合法，取决于线性化点的位置。因此“读永远返回墙上时钟意义的最新值”不够准确。

线性一致性是可观察行为约束，不规定一定用 leader、一定经过某个网络往返，也不要求所有物理副本在同一瞬间完成应用。实现可以通过不同复制和读取协议提供该行为。

顺序一致性：保留各客户端顺序，不额外保留跨客户端实时先后

顺序一致性要求存在一个符合对象语义、保留每个进程自身操作顺序的全局顺序，但不要求保留不同客户端之间仅由实时完成关系产生的先后。

例如客户端 A 依次写 x=1、x=2；客户端 B 随后在现实时间里读取到 1。若只看这段历史，它可能被解释为逻辑顺序“写 1、读 1、写 2”，从而满足顺序一致性，却违反第二次写已完成后读取仍旧的线性一致性要求。

这不是现实中的消息能穿越时间，也不意味着任意异步副本读取都满足顺序一致性。若同一个客户端先读到 2，再读到 1，而没有其他写入，就无法用保留其读顺序的上述单调写历史解释。

把定义变成一个小型历史检查器

为一个初始为 0 的寄存器记录四项信息：客户端、操作类型、写入值或读取结果、调用与返回的事件位置。这里的位置来自同一条已知事件序列，不是拿不同机器未经校正的墙钟时间直接排序。客户端一次只有一个未完成操作，所有记录都有成功返回。

检查时先排列操作，再做两道筛选：顺序是否满足必须保留的先后关系；按这个顺序执行时，每次读是否等于寄存器当前值。顺序一致性只加入同客户端的先后约束，线性一致性还加入所有跨客户端的不重叠约束。

from dataclasses import dataclass
from itertools import permutations

@dataclass(frozen=True)
class Op:
    client: str
    kind: str
    value: int
    start: int
    end: int

def witness(history, linear=True):
    assert all(o.kind in ("W", "R") and o.start < o.end for o in history)
    # 教学输入要求同一客户端串行调用，且事件位置没有歧义。
    for i, a in enumerate(history):
        for b in history[i + 1:]:
            if a.client == b.client:
                assert a.end < b.start or b.end < a.start
    edges = [(i, j) for i, a in enumerate(history)
             for j, b in enumerate(history)
             if a.end < b.start and (linear or a.client == b.client)]
    for order in permutations(range(len(history))):
        position = {op: rank for rank, op in enumerate(order)}
        if any(position[i] >= position[j] for i, j in edges):
            continue
        value = 0
        for i in order:
            op = history[i]
            if op.kind == "W":
                value = op.value
            elif op.value != value:
                break
        else:
            return order
    return None

stale = [Op("A", "W", 1, 0, 1), Op("A", "W", 2, 2, 3),
         Op("B", "R", 1, 4, 5)]
assert witness(stale, linear=False) == (0, 2, 1)
assert witness(stale, linear=True) is None

# 读写重叠：两种返回值都有合法解释，但不代表可以返回任意值。
for result in (0, 1):
    overlap = [Op("A", "W", 1, 0, 5), Op("B", "R", result, 2, 3)]
    assert witness(overlap) is not None
assert witness([Op("A", "W", 1, 0, 5), Op("B", "R", 2, 2, 3)]) is None

# B 先读 2 再读 1，与 A 的单调写入顺序无法放入同一个合法全序。
backward = stale[:2] + [Op("B", "R", 2, 4, 5), Op("B", "R", 1, 6, 7)]
assert witness(backward, linear=False) is None
assert witness([]) == ()

第一组返回 (0, 2, 1)，就是把 B 的读放在 A 的两次写之间。它保留 A 的程序顺序，却越过了现实中第二次写已经返回的事实。最后一组即使允许这样调整，也无解：读 2 要排在写 2 后，之后的读 1 又要求回到写 2 前，约束形成了环。

这个检查器的排列数按阶乘增长，只用于理解几个操作的小历史。存在一个见证就足以说明这段完整历史满足所选约束；检查通过并不能证明实现的所有执行都正确。真实测试还需要处理超时后结果未知、尚未返回的操作、对象规范与历史采集误差。尤其不能把超时的写直接从历史中删掉，因为它可能已经生效。Herlihy 与 Wing：Linearizability

同一段历史，哪些顺序还能成立？

可以把“是否一致”改写成一个具体问题：有没有一种操作排列，同时满足先后约束和寄存器读写规则？下面保留 A 的两次串行写，允许修改 B 的读区间与返回值。顺序一致性的见证是对历史的合法解释，不是将真实事件搬回过去；切换约束时，实际时间条保持不变。

因果一致性：先看到依赖，再看到依赖它的结果

A 发布文章，B 读到文章后回复；回复依赖文章。观察者若能看到回复，系统应满足相应因果可见性要求，避免只看到回复却看不到它所依赖的文章版本。彼此没有因果关系的并发操作，不一定需要全体观察者采用同一顺序。

因果关系来自进程顺序、读到某次写入等依赖及其传递闭包。是否把跨服务消息或用户会话切换纳入因果上下文，是 API 与实现契约的一部分。单独附带 Lamport 时间戳或使用版本向量，不会自动形成完整的因果一致读取服务。

会话保证：先保护一个用户的连续体验

读己之写要求会话后续读取不遗漏自己已经完成的相关写入；单调读要求会话观察到的状态不要退回更旧历史；其他会话保证还会约束连续写入和读后写入的传播顺序。

这些保证有明确作用域。让一个浏览器会话读己之写，并不意味着所有其他用户都立即看到其修改。会话迁移到另一个节点时，可能需要携带进度 token 并等待目标追赶。

最终一致性：描述收敛，不承诺中间过程

在更新停止、必要信息能够继续传播并完成合并等条件下，副本最终收敛。单独这个承诺不规定多久收敛，也不规定此前读取是否倒退、并发如何取舍或业务更新是否会被覆盖。

最终一致性可以和会话保证、因果保证一起提供，不应把所有模型机械排成单一强弱刻度。是否采用 LWW、CRDT 或应用合并，也需要额外说明；参见冲突解决。

事务隔离与对象一致性是不同问题

Serializable（可串行化）要求多个事务的效果等价于某个串行事务顺序。Strict serializability 进一步要求该顺序尊重实时先后。单 key 操作线性一致，不会自动把跨 key 的“先读余额、再转账”组成一个原子事务。

同样，一个 API 选项恰好叫 serializable，也应阅读其产品定义。例如 etcd 的 serializable 读取选项允许陈旧读取，不能直接按 SQL 隔离级别的名字推断。

每个操作都线性一致，仍可能丢失一次递增

设两个客户端都要把计数器加 1，却用独立的 read、本地加法和 write 实现。服务完全可以按下表顺序执行所有单次操作，且每次返回都满足寄存器规范。

这里没有违反单次读写的线性一致性，但两次业务递增只留下了 1。解决方法是把递增本身做成一个原子操作，或者使用带版本条件的 CAS/事务并在冲突后重新读取计算。给普通写增加重试次数不会把它自动变成原子递增。

如果使用 CAS，A、B 初次都携带版本 v0；A 成功后版本变成 v1，B 的 v0 条件必须失败。B 再读取值 1 和 v1，重算得到 2，再尝试提交。这也说明检查对象要与业务承诺对齐：只验证底层寄存器历史，还没有验证调用者拼成的复合操作。

速查与工程权衡

PACELC 提醒我们还要看无分区时的延迟与一致性选择，但不是“所有强一致操作固定多 1—2 RTT”的定律。地域布局、租约、缓存、批处理与读取路径都会改变实际代价。

评审时最好写出具体历史：哪个写已经成功，哪个读何时开始，故障发生在哪些连接，允许返回什么。它比给整个数据库贴 CP 或 AP 标签更能指导接口设计。

参考

• Perspectives on the CAP Theorem。
• etcd API 保证。
• 时间与时钟、故障模型。

Keywords: CAP, PACELC, linearizability, sequential consistency, causal consistency, eventual consistency, serializability