Lecture 10: Consistency Models — 一致性模型

目录 · ← l9 · l11 →

第五部分：时间、一致性与全局状态

这一部分是整门课的理论基石。在没有全局时钟的异步系统中，如何定义事件的顺序、如何刻画「一致性」、如何捕获一个自洽的全局状态？后续所有协调算法（互斥、选举、共识、复制）都建立在这一部分之上。

Lecture 10: Consistency Models — 一致性模型

讲义对应：CS 425 FA2026 Lecture 11（其中的 Consistency Models 部分，与 Time and Ordering 同讲）与 Lecture 24 B: Consistency Models（原始讲义 L24.B.FA25.pdf，16 页，Final 版）。补充素材：L9-11.FA25.pdf（CAP 定理、quorum、最终一致性的工程实践）、L12.FA25.pdf（因果序与逻辑时钟）、L21.FA25.pdf（复制控制与 one-copy serializability）。说明：本章跨章引用使用课程讲次编号（与课程日程一致）；对应的本笔记章节号见第 9 节的章节对照表。 教材对应：Coulouris 5th Ed. Ch. 18（Replication，Sec 18.1–18.3：一致性模型）、Sec 14.1–14.4（逻辑时钟、happens-before、向量时钟）、Ch. 14（时间与全局状态）；补充：Tanenbaum & van Steen Ch. 7（Consistency and Replication）。 阅读材料：Lamport, How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs (1979)；Herlihy & Wing, Linearizability: A Correctness Condition for Concurrent Objects (1990)；Terry et al., Session Guarantees for Weakly Consistent Replicated Data (1994)；Gilbert & Lynch, Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (2002)；Abadi, Consistency Tradeoffs in Modern Distributed Database System Design（PACELC, 2012）；Shapiro et al., Conflict-free Replicated Data Types (2011)；Viotti & Vukolić, Consistency in Non-Transactional Distributed Storage Systems (2016)。

10.1 概述

本讲的核心问题只有一个：当我们为了可用性、可扩展性和低延迟而把同一份数据复制到多个副本上之后，”读操作究竟允许返回什么值”这个规则该由谁来定、能定得多严？一致性模型（Consistency Model）就是这个问题的答案——它是分布式系统与应用之间的一纸契约（contract）：系统承诺”在我这个模型下，读绝对不会返回越界的结果”，应用则承诺”我只会按照这个模型的语义来写代码”。契约定得越强（越接近”只有一份数据”的假象），程序员写代码越容易，但系统要付出的协调（coordination）代价越大，性能与可用性越低；契约定得越弱（例如最终一致性），系统可以永远可写、延迟极低，但把冲突检测、版本管理、甚至业务层面的”数据看起来不对”的锅甩回给应用。

本讲依次建立四层知识：(1) 用”历史（history）+ 全序/视图”的形式化框架把一致性模型精确地定义出来，并逐个给出”违反该模型”的具体执行反例；(2) 建立数据为中心（data-centric）模型之间的层次结构（lattice）——线性一致 ⇒ 顺序一致 ⇒ 因果一致 ⇒ FIFO 一致——并证明每一步的蕴含关系、给出每一步不可逆的反例；(3) 转向以客户端为中心（client-centric）的四条会话保证（单调读、单调写、读己之写、写跟随读），它们在真实产品（社交网络、购物车、协同编辑）中的重要性远超教科书给人的印象，而且它们可以在分区可用的系统上实现；(4) 用 CAP 定理及其现代修正 PACELC 说明”一致性不是一个布尔属性，而是一个可以按操作拧动的旋钮”。

在整门课中，本章处在”时间与顺序 → 一致性 → 复制与共识“这条主干的枢纽位置：它向前引用 Lecture 12 的 happens-before 与向量时钟（因果一致性的实现基础）、Lecture 9 的 Cassandra 与 $R+W>N$ quorum；向后为 Lecture 15 的多播通信（因果广播/全序广播）、Lecture 17 的共识（FLP）、Lecture 19 的 Paxos/Raft（线性一致性的实现引擎）、Lecture 22 的复制控制（one-copy serializability、2PC）提供语义目标。换句话说：后面几讲讲的全是”怎么做到”，而本讲回答”到底要做到什么”。

10.2 核心概念与分布式机制图解

10.2.1 复制的根本矛盾与”契约”观（The Contract View）

定义与目的：复制（Replication）指同一份数据对象在多个服务器上各保存一份完全相同的拷贝，每份拷贝称为副本（replica）。复制的三个动机是：容错（fault tolerance）——$k$ 个副本可以容忍 $k-1$ 台服务器故障；负载均衡（load balancing）——读/写负载被分摊到 $k$ 个副本上；以及由此得到的高可用性（availability）。若单台服务器的故障概率为 $f$，无复制时对象可用性为 $1-f$，有 $k$ 个副本时对象可用性为

\[A = 1 - f^{k}\]

例如 $f=0.1$ 时，无复制可用性 90%，$k=3$ 时 99.9%，$k=5$ 时 99.999%。复制把可用性提升了若干个 9，但它同时制造了一个新问题：$k$ 份拷贝可能不一致。

直观解释（”它是什么？”）：一致性模型像一份银行服务合同。线性一致性像”全市只有一个柜台的银行”——你去任何网点办事，看到都是同一个账本，任何一笔存款当场对所有人生效；最终一致性像”小道消息传播的办公室“——你把消息告诉离你最近的同事，消息会慢慢传遍全公司，但总有人在你之后、消息传到之前还保留着旧版本。合同不会规定银行内部怎么记账（实现自由），只规定”客户能看到什么”（可观察行为）；一致性模型同样不规定实现，只规定允许的观察结果集合。
机制图解：

                    一致性模型 = 契约（contract）
     ┌────────────────────────────────────────────────────────────┐
     │ "在并发读写之下，读操作允许返回哪些值？"                   │
     └────────────────────────────────────────────────────────────┘
          ▲                              ▲
          │ 系统开发者视角               │ 应用开发者视角
          │ · 设计/优化系统满足契约      │ · 必须理解契约的语义
          │ · 选择副本协议与一致性级别   │ · 否则应用正确性无从谈起
     ┌────┴──────────────────────────────┴────────────────────────┐
     │            分布式系统（多个副本 + 并发客户端）             │
     │    C1 ──┐                                                  │
     │    C2 ──┼──►   R1    R2    R3   ←── 同一对象的多个副本     │
     │    C3 ──┘                                                  │
     └────────────────────────────────────────────────────────────┘

为什么不可能”又强又快”：要让所有客户端在任何时刻看到同一份数据（线性一致），系统必须在写生效前协调（coordination）——至少要让一部分副本达成一致；协调意味着消息往返（至少 1 个 RTT）、意味着等待最慢的副本（长尾）、意味着网络分区时少数派一侧必须拒绝服务。反过来，如果允许”先返回、后同步”，就没有任何机制能阻止两个客户端在同一时刻看到不同的值。“一致性—延迟—可用性”的三方权衡是本讲所有内容的骨架。
关键假设与系统模型：本章默认异步系统模型（消息延迟与进程执行时间无界，见 Lecture 12）与崩溃—停止（crash-stop）故障模型（节点只会宕机，不会作恶；拜占庭故障见 Lecture 27）。副本之间的通道可能丢失、延迟、乱序、并且在分区（partition）期间完全阻断。客户端是顺序的（一次只发出一个请求，收到响应后才发下一个），这保证了”同一客户端的操作不重叠”这一良构性（well-formedness）假设——本讲所有形式定义都依赖它。

10.2.2 两种视角：数据为中心 vs 以客户端为中心

定义与目的：
- 数据为中心的一致性模型（data-centric）：规定同一数据项上的所有操作（来自所有客户端、作用于所有副本）之间的可见性关系。它回答的是”整个系统对外呈现的、关于这份数据的全局行为是什么”。这是本节 10.2.4–10.2.10 的主体。
- 以客户端为中心的一致性模型（client-centric）：只规定单个客户端对数据的视图——它回答的是”我自己看到的东西，对我来说是否自相矛盾”。这是 10.2.11–10.2.16 的主体。
直观解释（”它是什么？”）：数据为中心的一致性像”法律面前人人平等“——它管的是全体公民（所有客户端）之间关于同一事实的共识；以客户端为中心的一致性像”不许自相矛盾“——它不管你和其他人看到的是不是同一个版本，只管你自己前后两次陈述不能打架。一个移动用户从北京连到 A 副本、又飞到纽约连到 B 副本，他真正在意的是”我刷新页面时，之前看到的东西不会凭空消失”，而不是”全世界所有人此刻是否看到同一个值”。这正是手机 App 里”消息闪回”“头像没更新”这类 bug 的根源。
机制图解：

   【数据为中心】关注整份数据在所有进程间的可见性
        P1 ──W(x=1)──┐
                     ├──►  所有进程对 x 的可见序列必须满足某个全局约束
        P2 ──R(x)=?──┘
   【以客户端为中心】只关注单个客户端的视角是否自洽
        C1: R(x)=5 ──► R(x)=3        ✗ 时间倒流（违反单调读）
        C1: W(avatar=new) ──► R(avatar)=old   ✗ 看不到自己的写（违反读己之写）
        其他客户端看到什么，本模型不管

关键假设与系统模型：以客户端为中心的模型需要客户端参与：客户端必须保存会话元数据（版本号、序号、连接信息），并可能需要对读做路由（route to a fresh enough replica）。这也是它便宜的原因——协调的成本从”全局”降级为”每个客户端自己的状态”，因此在分区可用的系统上依然可以实现。

10.2.3 形式化框架：历史、实时序、程序序与”最近一次写”

要精确讨论一致性模型，必须先有一套共同的语言。下面这套记号贯穿本章，也是 10.4 的检查器代码直接实现的对象。

历史（History / Execution）：一次执行的可观察记录 $H$ 是一组操作（operation）的集合。每个操作 $o$ 带有：

\[o = \langle \text{proc}(o),\ \text{type}(o),\ \text{key}(o),\ \text{val}(o),\ s(o),\ e(o) \rangle\]

其中 $\text{proc}(o)$ 是发起它的客户端编号，$\text{type}(o)\in\{W,R\}$ 表示写或读，$\text{key}(o)$ 是数据项，$s(o)$ 与 $e(o)$ 分别是它的调用时刻与响应时刻（真实时间），对读操作 $\text{val}(o)$ 表示读到的返回值，对写操作表示写入的值。

实时序（real-time order）：若 $e(a) < s(b)$（$a$ 在 $b$ 开始之前就已经完成），记 $a \prec_{rt} b$。两个操作若时间区间重叠（$s(a) < e(b)$ 且 $s(b) < e(a)$），则称它们是并发的（concurrent）——注意这是一个关于”观察不到先后”的事实判断，不是关于因果的判断。
程序序（program order）：同一客户端先后发出的操作之间的顺序，记 $a \prec_{po} b$。由良构性假设，$\prec_{po} \subseteq \prec_{rt}$。
最近一次写规则（most-recent-write rule）：给定一个操作的全序 $S$，读操作 $r$ 必须返回”$S$ 中排在 $r$ 之前的、对同一 key 的最后一个写操作”所写的值；如果它之前没有任何写，就返回该 key 的初始值。这条规则是”顺序一致性”这类模型的心脏——全序本身是自由的，但一旦选定全序，读到什么就被唯一确定了。
happens-before（$\to$）：Lecture 12 定义的因果偏序——同进程内的先后、消息发送先于接收、以及传递闭包。它是因果一致性的基石。
机制图解（一份历史画在时间轴上）：

        时间 ──────────────────────────────────────────────────────────────►
   P1        ├──W(x=1)──┤
   P2              ├────────R(x)=1────────┤
   P3                   ├─────W(x=2)─────┤
                         ▲               ▲
                   R(x) 与 W(x=2) 并发     W(x=2) 与 R(x)=1 也是并发的
   实时序：W(x=1) ≺rt R(x)=1（前者先完成）
   程序序：R(x)=1 ≺po W(x=2)（同一客户端 P2/P3 视实现而定）
   注意：并发 ≠ 无因果关系；并发只是"实时上分不出先后"

关键假设与系统模型：我们假设同一个 (key, value) 最多被写一次（否则”读返回的是哪个写”会有歧义，检查器无法作唯一归因），且历史中未完成（pending）的操作可以按标准做法”补齐后再判定”（extend and complete），不影响结论。

10.2.4 严格一致性 / 线性一致性（Strict Consistency / Linearizability / Atomic Consistency）

定义与目的：
- 严格一致性（Strict Consistency）：任何读操作都返回最近一次写操作的值。它要求存在一个所有进程共享的绝对时间轴，写瞬间对所有进程可见——这在异步分布式系统中是不可实现的（没有任何时钟/协调机制能让”瞬间”具有全局意义），因此教科书通常把它当作一个理想化的参照点。
- 线性一致性（Linearizability，又称原子一致性 Atomic Consistency）：Herlihy 与 Wing 给出的、可实现的严格化版本：

定义 10.1（线性一致性） 历史 $H$ 是线性一致的，当且仅当存在一个把 $H$ 中所有操作排成全序 $S$（称为一个线性化 linearization），使得： (i) 实时序保持：若 $a \prec_{rt} b$（$a$ 先完成、$b$ 才开始），则 $a$ 排在 $S$ 中的 $b$ 之前； (ii) 读返回最近写：每个读操作 $r$ 返回 $S$ 中排在它之前、对同一 key 的最近一次写所写的值（无写则返回初始值）。等价的说法：每个操作都可以被看作在它的时间区间 $[s(o), e(o)]$ 内的某个线性化点上原子地、瞬间地生效。

直观解释（”它是什么？”）：线性一致性就是单副本语义（one-copy semantics）——”所有操作看起来就像在一个单机上、按某个顺序原子执行”。这也是 CAP 定理里的那个 “C”。它最贴近人类直觉（所以最好编程），代价也最大（所以最难做到）。
机制图解（讲义中的经典四客户端例子）：

        C1  ├──W(x=1)──┤
        C2          ├──────W(x=2)──────┤
        C3   ├─R(x)=1─┤                              （R 与 W(x=2) 并发）
        C4                        ├──R(x)=2──┤       （合法：与 W(x=2) 并发）
                                  ▲
        关键问题：C4 的 R(x) 能返回 1 吗？
        ── 能，但仅当 R(x) 与 W(x=2) 并发（此时线性序可以把它排在 W(x=2) 之前）。
        ── 若 R(x) 在 W(x=2) 完成之后才发起，则必须返回 2，返回 1 即违反线性一致性。

违反线性一致性的经典反例（本讲后面代码里的 H2，也是区分线性一致与顺序一致的”标准试验”）：

   P1   ├──W(x=1)──┤
   P2   ├──W(x=2)──┤                         两个写并发
   P3                     ├─R(x)=2─┤   ├─R(x)=1─┤
   时间 ─────────────────────────────────────────────────►
   两次读都在两个写完成之后才开始，因此实时序要求
        W(x=1)、W(x=2) 都必须排在两次读之前（全序必须如此）
   而 R(x)=2 要求"它前面最近的写"是 W(x=2)，R(x)=1 要求"最近的写"是 W(x=1)：
        · 若把 W(x=1) 排在 R(x)=2 之前 ⇒ 由于 R(x)=2 前最近的写必须是 W(x=2)，
          得 W(x=1) < W(x=2)；但 R(x)=1 前最近的写必须是 W(x=1)，又要求 W(x=2) < W(x=1)，矛盾。
        · 若把 W(x=1) 排在 R(x)=2 之后 ⇒ 与实时序（W(x=1) 早于 R(x)=2 发起）矛盾。
   ⇒ 不存在合法全序，该历史非线性一致。

最弱的、允许线性一致性的实现：一个单主（single leader）的注册表（register）——所有写和读都经过领导者，领导者按到达顺序串行执行；如果要求”任何副本都能服务读”，则需要 quorum：$R + W > N$ 且 $W > N/2$（见 Lecture 9 的 Cassandra 与 Lecture 22 的复制控制），或者更一般地用共识（Paxos/Raft）把每个写放进一个全局全序的日志（见 Lecture 19）。判断依据是接口的强度，而不是系统的规模：只要每次操作都必须先经过协调再返回，就是在提供线性一致性。
代价：需要协调（coordination）⇒ 写延迟至少 1 个 RTT，读若要求”读最新”则同样需要 quorum/leader 确认；在网络分区期间，少数派一侧必须阻塞或报错（不可用）——这正是 CAP 定理的内容。
注意（严格 vs 线性）：严格一致性假设”全局绝对时间”，线性一致性只用可观察的实时序（谁先完成），因此在异步系统中线性一致性是可实现、可判定的正确性条件，而严格一致性不是。课程讲义把二者当作同一端的两个名字（都叫 strong consistency）；考试中若被问到定义，请使用线性一致性的”全序 + 实时序保持 + 读返回最近写”三件套。

10.2.5 顺序一致性（Sequential Consistency）

定义与目的：Lamport 在 1979 年给出的原始表述是：

“… the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.”

定义 10.2（顺序一致性） 历史 $H$ 是顺序一致的，当且仅当存在所有操作的一个全序 $S$，使得： (i) 程序序保持：若 $a \prec_{po} b$（同一客户端先发 $a$ 后发 $b$），则 $a$ 排在 $S$ 中 $b$ 之前； (ii) 读返回最近写：每个读返回 $S$ 中排在它之前、对同一 key 的最近一次写所写的值。

直观解释（”它是什么？”）：顺序一致性像”事后统一口径“——所有人都同意”事情就是按这个顺序发生的”，但这个顺序只要求”说得通”（不违反任何人自己的操作顺序），不要求与各人当时的真实经历（真实时间）一致。它保证”所有人拿到同一个故事”，却不保证”这个故事按时间讲”。
与线性一致性的关键区别（本章最重要的一个对比）：顺序一致性不要求全序与真实时间一致，只要求与各客户端的程序顺序一致。 换句话说，线性一致性说”所有客户端看到同一个顺序，而且这个顺序不能与真实时间矛盾”；顺序一致性说”所有客户端看到同一个顺序，但允许这个顺序把已经完成的写在时间上’往后挪’“。因此顺序一致性允许过期读（stale reads）：一个写明明已经完成，后面的读仍然可以合法地返回更旧的值，只要全局存在一个不违反任何客户端程序序的解释即可。
机制图解（顺序一致 vs 线性一致的差别）：

   ── 顺序一致允许、线性一致不允许 ─────────────────────────────────────
        P1   ├──W(x=1)──┤
        P2   ├──W(x=2)──┤                     两个写并发，并都在读之前完成
        P3                       ├─R(x)=2─┤        ├─R(x)=1─┤
        顺序一致的解释 S：W(x=2) → R(x)=2 → W(x=1) → R(x)=1
                          每个客户端的程序序都被保持（✓），
                          但已完成的 W(x=1) 被排到 R(x)=2 之后 ⇒ 违反实时序（✗）
   ── 线性一致要求的额外约束 ───────────────────────────────────────────
        R(x)=2 之前最近的写 = W(x=2)；R(x)=1 之前最近的写 = W(x=1)
        ⇒ 若要同时满足实时序，两个写必须被"同一个读之前"的最近写同时占据 → 不可能

违反顺序一致性的反例（代码中的 H5）：同一个写者发出的两个写被倒序看到：

        P1   ├──W(x=1)──┤        ├──W(x=2)──┤
        P2                                ├─R(x)=2─┤   ├─R(x)=1─┤
        全序必须保持 P1 的程序序：W(x=1) 排在 W(x=2) 之前。
        但 R(x)=2 要求它前面最近的写是 W(x=2)，R(x)=1 要求最近的写是 W(x=1)，
        而两次读又必须按 P2 的程序序先后排列 ⇒ 无论怎样排都矛盾。

“再来一次读”的经典追问：若 P3 读完 R(x)=2 之后再读一次 x，第二次读可以返回什么？在顺序一致性下答案是”1 或 2 都可能“——只要存在一个合法全序，例如把 W(x=1) 插在两次读之间（这正是上一张图的情形）。这说明顺序一致性下同一客户端的连续两次读并不保证单调（”读到新值以后又读到旧值”是允许的）。这恰恰是以客户端为中心的”单调读”保证要解决的问题（见 10.2.12），也是讲义提出的那个问题”因果一致性是否蕴含单调读？“的答案：不蕴含。
最弱的、允许顺序一致性的实现：全序广播（total-order broadcast）——所有副本把收到的更新放进同一个全局顺序里（用一个定序者 sequencer，或者用共识决定下一个位置），然后各自按该顺序执行（见 Lecture 15 多播通信）。注意：全序广播本身不要求发送者之间的实时一致性，因此它天然给出顺序一致性而非线性一致性；若要升级到线性一致性，还需要保证”写完成之前该写已在全序中定位”（例如多数派确认后才返回）。
代价：仍然需要协调（要有全局唯一的顺序），因此分区期间不可用；但它比线性一致性略便宜：可以批量定序、可以用异步的全序广播（写返回不必等待所有副本应用）。

10.2.6 因果一致性（Causal Consistency）

定义与目的：因果一致性只要求有因果关系的写操作被所有进程以相同的顺序看到；并发（无因果关系）的写允许在不同进程上以不同顺序被看到。它依赖 Lecture 12 的 happens-before 关系 $\to$。

定义 10.3（因果一致性） 设 $\to$ 是写操作之间的因果序，它是最小的满足下列条件的偏序： (a) 程序序：同一客户端先发出的写 $w_1$ 与后发出的写 $w_2$ 满足 $w_1 \to w_2$； (b) 读—写依赖（read-from）：若某进程读到了 $w_1$ 所写的值，之后又发出写 $w_2$，则 $w_1 \to w_2$； (c) 传递闭包：$w_1 \to w_2$ 且 $w_2 \to w_3$ 则 $w_1 \to w_3$。
历史 $H$ 是因果一致的，当且仅当可以为每个进程 $p$ 指定一个”已看到的写”的集合 $V_p$（$p$ 的视图）及其上的一个全序，使得： (i) 向下封闭：若 $w \in V_p$ 且 $w^{\prime} \to w$，则 $w^{\prime} \in V_p$； (ii) 顺序一致（对所有进程相同）：每个 $V_p$ 上的全序都是 $\to$ 的线性扩展（即因果相关的写在所有进程看来顺序相同）；不同的 $V_p$ 之间，并发写可以顺序不同； (iii) 读规则：$p$ 自己的读按程序序发生，且每个读返回视图 $V_p$ 中该 key 最近一次写的值；$p$ 自己发出的写一定出现在 $V_p$ 中。

直观解释（”它是什么？”）：因果一致性像”聊天群里不能出现’回复’先于’原消息’的情况“——回复依赖于原消息，所以任何人在看到回复时，也必然看过原消息；但两个互不相干的群成员同时发言，谁先谁后无关紧要，不同的人看到不同顺序完全可以接受。讲义用一句话概括：“Causality, not messages”——管的是因果关系，不是消息到达顺序。
机制图解（讲义中的经典例子）：

        C1   ├──W(x=1)──┤
        C2                     ├─R(x)=1─┤  ├──W(y=1)──┤
        C3                                              ├──R(x)=?──┤  ├──R(y)=1──┤
        因果链：W(x=1) → W(y=1)   （C2 读到了 x=1 才写 y=1）
        · C3 的 R(y)=1 已经被看到 ⇒ 它必须同时看到 W(x=1)
          因此 C3 的 R(x) 必须返回 1，返回 0（初始值）就是违反因果一致性
        · 若另一个客户端 C4 的写 z=3 与 W(x=1) 并发，则不同客户端
          看到 x=1 与 z=3 的先后可以不同 —— 这不违反因果一致性

必须给出违反因果一致性的例子（代码中的 H4）：看到了”果”，却没看到”因”。

        P1   ├──W(x=1)──┤
        P2                 ├─R(x)=1─┤  ├──W(y=1)──┤        因果：W(x=1) → W(y=1)
        P3                                               ├─R(y)=1─┤  ├─R(x)=0─┤
        合法性检查：W(x=1) 与 W(y=1) 因果相关，故任何进程都必须先看到 x=1 再看到 y=1。
        但 P3 的视图若包含 y=1 却不包含 x=1，就违反了向下封闭（条件 i）；
        若视图包含 x=1，则 R(x) 必须返回 1 而非 0。两条路都走不通 ⇒ 违反因果一致性。
        有趣的是：这个历史在 FIFO 一致性下是合法的（见 H4 的判定结果），
        因为 P1 与 P2 是不同的写者，FIFO 不要求"写者之间"的因果顺序。

实用价值与可实现性：因果一致性是最弱但仍有实用价值的数据为中心模型：它排除了绝大多数让用户困惑的异常（”评论先于原帖”“回复先于消息”），却不需要全局协调——只要把因果依赖随数据一起传播即可。实现方式是向量时钟（vector clock，Lecture 12）：每个副本维护一个向量，收到写时检查其因果依赖是否都已应用（否则缓冲），并把它自己的版本作为新写的依赖。它是 Lecture 15 的因果广播（causal broadcast）在存储系统上的对偶。代表系统：COPS（Geo-replication with causal consistency）、AntidoteDB、Riak（用 dotted version vector）。
一个著名结论（可提及）：Attiya、Ellen 与 Morrison 证明，在分区期间保持可用并且要求”副本最终收敛”的约束下，因果一致性是可能实现的最强一致性模型（causal consistency is the strongest consistency that is achievable for convergent, available, partition-tolerant systems）。换言之：如果你打算在分区期间继续服务，那就别指望比因果一致性更强的东西——这个结论把”AP 系统的天花板”钉死在因果一致性上。
代价与代价的对偶：元数据开销（每个 key 带版本向量）、需要缓冲乱序到达的写、读可能被”因果延迟”而等待。但在分区下可用。

10.2.7 FIFO 一致性（FIFO Consistency / PRAM Consistency）

定义与目的：FIFO 一致性（在共享内存文献中称为 PRAM 一致性，Pipelined RAM，Lipton & Sandberg 1988）只保证”同一个写者发出的写，被所有其他进程按该写者发出的顺序看到“，而不同写者的写可以被不同进程以不同顺序看到。

定义 10.4（FIFO 一致性） 历史 $H$ 是 FIFO 一致的，当且仅当可以为每个进程 $p$ 指定一个视图 $V_p$ 及其全序，使得： (i) 每个 $V_p$ 是”同一写者的写之间的程序序”这一偏序的线性扩展（即同一写者的写在各处顺序一致）； (ii) 每个进程的读按程序序发生，且返回 $V_p$ 中该 key 最近一次写的值。与因果一致性相比，唯一的区别是把 (i) 中的偏序从因果序 $\to$ 削弱为每个写者自己的程序序——不再有 read-from 依赖，也就没有传递闭包。

直观解释（”它是什么？”）：FIFO 一致性像”每个寄件人自己的信件按寄出顺序投递，但不同寄件人的信谁先到无所谓“。A 发的信 1 一定比 A 发的信 2 早到；但 B 的信 3 与 A 的信 4 谁先到，不同收件人可以有不同的答案。它比因果一致性更弱：它连”你回复了别人的信，你的回复不能早于那封信被别人看到”都不保证。
例：A 依次写 x=1、x=2，所有进程都必须按 1、2 的顺序看到 x；但 A 写 y=3 与 C 写 z=4 之间没有任何约束，任意顺序都合法。
最弱的、允许 FIFO 一致性的实现：每个写者给自己的写带一个单调递增的序号（sequence number），接收方按写者分别维护”已收到的最大序号”，拒绝/缓冲乱序到达的写。不需要任何全局协调，也不需要跨副本交换元数据——这正是它成为”最便宜的数据为中心模型”的原因。分区下完全可用。
它为什么有用：FIFO 一致性是”每个客户端的操作在系统里保持顺序“这一直觉的最低要求；它也是以客户端为中心的”单调写”在数据为中心视角下的对应物（见 10.2.13）。很多消息队列/日志系统（Kafka 的单分区语义）本质上提供的就是 FIFO 一致性 + 持久化。

10.2.8 弱一致性（Weak Consistency）

定义与目的：弱一致性引入同步操作（synchronization operation），用同步点划出”一致性边界”：模型不保证任何时刻都一致，但保证在同步点上一致。三个性质（弱序 weak ordering + 同步的标准定义）：

定义 10.5（弱一致性） (i) 对同步变量（synchronization variable）的访问是顺序一致的； (ii) 在一个同步操作完成之前，不允许访问任何数据项（即同步操作具有”屏障”语义，它之前的普通读写必须先完成）； (iii) 在所有同步操作完成之前，所有之前的写必须已经完成（写对所有人可见）。

直观解释（”它是什么？”）：弱一致性像”会议纪要“——会议期间大家各说各的、记录可以有出入（不一致），但会议结束时必须形成一份所有人认可的纪要（同步点）。它是”屏障（barrier）”思想在一致性问题上的第一次形式化：程序员用显式的同步点告诉系统”这里我需要看到一致的状态”，其余时间系统可以放手优化（乱序、合并、延迟传播）。
最弱的、允许弱一致性的实现：共享内存系统（DSM，见 Lecture 25）与多处理器内存系统：普通读写走本地缓存并允许乱序传播，遇到 fence/barrier/acquire-release 时把之前的写刷出去、把之后的读拦下来。放宽 (ii)(iii) 的强弱程度就得到 释放一致性（Release Consistency）（只要求 release 前的写可见、acquire 前的同步可见）与入口一致性（Entry Consistency）（每个数据项与某个锁关联，只在获取该锁时同步该数据项）——它们是现代 CPU 内存模型（x86-TSO、ARM 弱序）与分布式数据库事务边界的共同祖先。
关键假设与系统模型：弱一致性假设程序员愿意并且能够显式标注同步点；没有同步操作的程序在弱一致性下几乎没有保证（这与”最终一致性”不同：后者即使没有同步操作也保证最终收敛）。

10.2.9 最终一致性（Eventual Consistency）

定义与目的：

定义 10.6（最终一致性） 若对某个 key 不再有新的写操作，那么最终所有副本上该 key 的值会收敛到相同的值。 $\forall r_1, r_2 \in \text{replicas}: \exists T,\ \forall t > T:\ \text{state}(r_1, t) = \text{state}(r_2, t)$

关键：它不规定何时收敛、也不规定中间状态。 “最终”是一个活性（liveness）承诺（只要网络最终恢复通信），而不是安全性承诺；中间过程里读操作可能读到任意旧的版本，甚至读到互相冲突的多个版本。
直观解释（”它是什么？”）：最终一致性像”小道消息传播的办公室“——你告诉最近的同事，消息一波一波往外传，总有人的信息是旧的；但只要没人再更新，最终全公司都会知道。讲义用”一波滞后于最新值的移动的波（moving wave of updated values）“来形容：写持续进行时，系统永远在追赶，读可能读到”上一波”甚至”上上波”的值。
机制图解（讲义中的例子与”追赶的波”）：

   C1 ──W(x=1)──┐
   C2 ──W(x=2)──┤          副本之间异步传播，客户端可能读到任意旧值
   C4 ──R(x)=0──┘    ← 读到初值 0：在最终一致性下完全合法！
   时间 ──────────────────────────────────────────────────────────►
       写：  x=0 ████████ x=1 ██████ x=2 ████████████████
       副本R1:      x=0    ┃     x=1   ┃    x=2
       副本R2:         x=0        ┃      x=1        ┃      x=2
       副本R3:             x=0         ┃       x=1        ┃      x=2
                                    ▲ 读此刻可能返回 0 或 1（滞后，但合法）

必须点明它的弱点：收敛时间无界（没有”多久之内收敛”的承诺，只有”最终”）；中间状态可能违反任何直觉（读到旧值、看到自己不写过的值、同一用户两次刷新看到不同内容）。因此任何自称最终一致的产品都必须配套三种机制：
1. 读修复（read repair）：读时发现副本间版本不一致，就顺手把最新版本回写（Cassandra 的协调者在后台做这件事，见 Lecture 9）；
2. 反熵（anti-entropy）：后台周期性比较副本（用 Merkle Tree 比较差异），把缺失的更新补上（Cassandra 的 repair、Dynamo 的 Merkle Tree）；
3. 冲突解决（conflict resolution）：并发写到达不同副本后必须有确定的合并规则——LWW（Last-Writer-Wins，按时间戳大小取胜）、向量时钟（保留并暴露冲突版本，让应用层解决）、或 CRDT（让冲突在设计上不存在）。
真实系统：DNS 是最早、也最成功的最终一致性系统——域名记录的更新通过 zone transfer 传播，递归解析器缓存 TTL 之内的旧记录是常态，全世界都接受了这一点（因为域名很少改）。此外 Cassandra、Dynamo、Riak、Voldemort 都是最终一致（Cassandra 的冲突解决是 “latest timestamp wins”，即 LWW，见 Lecture 9），Amazon S3（覆盖写最终一致）、DynamoDB（默认最终一致的读）亦然。
收敛速度的现实：讲义指出，最终一致性”在有若干低写入期时工作得很好”——写停下来的间隙里系统迅速追平；而在”背靠背大量写”时读可能一直读到旧值。这解释了为什么它非常适合”读多写少、写有间歇”的场景（社交动态、商品目录、DNS），而不适合”写后立刻必须看到”的场景（余额扣减、库存、抢票）。

10.2.10 CRDT：让冲突在设计上不存在（Conflict-free Replicated Data Types）

定义与目的：CRDT（无冲突复制数据类型）是一类被专门设计过的数据结构，使得”并发/乱序的更新以任意顺序合并，结果都一样”。讲义的原话是 “Data structures for which commutated writes give same result”（可交换的写产生相同结果），由法国 INRIA 等团队提出。它提供的保证叫强最终一致性（Strong Eventual Consistency, SEC）：所有收到相同更新集合的副本，无需任何冲突解决过程，就处于相同状态。
直观解释（”它是什么？”）：普通复制像”两个会计各自记账，月底对账时发现数字不一致，只能开会吵架”；CRDT 像”两个会计只被允许做加法“——谁先加谁后加都无所谓，怎么加都对，永远不会对不上账。讲义举的最简单例子就是”值是一个整数，且唯一允许的操作是 +1“。
机制图解（G-Counter：只增计数器）：

┌─────────────────────────────────────────────────────────────────┐
│ 三个副本各自维护一个向量 (c1,c2,c3)，本地的 +1 只增加自己的分量 │
│ R1: (3,0,0)      R2: (0,2,0)      R3: (1,0,1)                   │
│                                                                 │
│ 合并操作 ⊔ = 逐分量取 max（join）：                             │
│     (3,0,0) ⊔ (0,2,0) = (3,2,0)                                 │
│     再 ⊔ (1,0,1)      = (3,2,1)                                 │
│ 任意顺序、任意次数合并（含重复合并），结果都是 (3,2,1)          │
│ 计数值 = 3+2+1 = 6，即系统里一共发生了 6 次 +1                  │
└─────────────────────────────────────────────────────────────────┘

交换律、结合律、幂等律：(1) 交换 $a \sqcup b = b \sqcup a$；(2) 结合 $(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$；(3) 幂等 $a \sqcup a = a$。满足这三条 + 单调性的 $(S, \sqcup)$ 构成并半格（join-semilattice），而”任意顺序、任意次数地把一堆状态 join 起来”的结果恒等于这堆状态的最小上界（least upper bound）——这就是 CRDT 收敛性的全部数学内容（形式化论证见 10.3.4）。
四个必知的数据类型： | 类型 | 语义 | 状态与合并 | 典型用途 | |—|—|—|—| | G-Counter | 只增计数器 | 每副本一个分量，合并 = 逐分量 max，值 = 分量求和 | 点赞数、访问量 | | PN-Counter | 可增可减计数器 | 两个 G-Counter（P 与 N），值 = sum(P) − sum(N) | 库存增减、票数 | | OR-Set | 可增可删集合 | 元素带唯一标签（tag）的增集合 ∪ 删集合；合并 = 标签集合取并；元素存在 ⟺ 有未被删的标签 | 购物车、标签、好友列表 | | LWW-Register | 单值寄存器 | 值 + 时间戳（+ 副本 id 打破并列），合并 = 取更大的时间戳 | 用户资料、配置项 |
为什么 OR-Set 需要标签：如果只是”集合的并集/差集”，并发”加”与”删”会产生歧义（”删”该不该覆盖并发的”加”？）。OR-Set 用唯一标签把每次 add 变成一个新身份，remove 只删除”它当时看到的那些标签”，因此”并发 add 一定获胜”（不丢数据），而”因果在后的 remove 会生效”。这体现了 CRDT 设计的核心功力：把语义选择写进数据结构，而不是留给运行时。
代价与边界：CRDT 的状态与元数据会单调增长（标签、墓碑 tombstone 需要垃圾回收）；它只适用于”可交换/可结合”的操作语义，很多业务规则（如”余额不能为负”“库存不能超卖”）本质上要求协调，无法用纯 CRDT 表达——这类约束必须在应用层用 quorum/共识来兜底。此外 LWW-Register 需要”可比较的时间戳”，而物理时钟有偏移（Lecture 12），所以实践中常用混合逻辑时钟（HLC）。
相关的新模型：讲义的 Red-Blue 一致性把一个事务里的操作拆成两类：blue 操作可以跨数据中心以任意顺序执行/交换（最终一致），red 操作必须在每个数据中心按相同顺序执行（强一致）。这是一种”一个系统里同时提供两种一致性“的组合模型，本质上是把 CRDT 的思想用到了事务级别。另外还有 per-key sequential（每个 key 内部保证全局顺序，key 之间不管）——正是 Kafka 分区语义与很多”per-key 全序”KV 系统（如 Scatter）的做法。

10.2.11 以客户端为中心的模型总览：会话保证（Session Guarantees）

动机：一个移动客户端可能在不同时刻连到不同副本（换基站、换 WiFi、跨地域负载均衡、副本故障切换），它真正关心的是”我自己看到的东西是否合理“，而不是”全世界是否看到同一个值”。Terry 等人在 1994 年的 Bayou 项目中把这类需求形式化为四条会话保证（session guarantees）：单调读、单调写、读己之写、写跟随读。讲义明确指出：这四条保证在存在网络分区时依然可以实现（available in the presence of partitions）——因为每条保证都只涉及”客户端自己”的状态，不需要全局协调。
为什么”以客户端为中心”比”数据为中心”便宜：数据为中心的强模型要求所有人对所有数据达成一致；会话保证只要求你对你自己的操作序列达成一致。前者需要全局协调（共识/quorum），后者只需要客户端记住自己做过什么（版本号、序号）并在读的时候挑一个足够新的副本。代价从”每次操作都要跨副本协商”变成”客户端多存几十字节 + 偶尔多一次路由”。
机制图解（四条保证的”违反现场”，这是本章最贴近真实故障的图）：

   ① 单调读被违反（"消息凭空消失"）
      客户端连到 R1（新）读到 post=3 条；切到 R2（旧）后只看到 2 条
          R1: [p1 p2 p3]  ──►  R2: [p1 p2]      ✗ 时间倒流
   ② 单调写被违反（"我的写被写坏了"）
      客户端写 x=1、再写 x=2；两条写走不同路径，副本先收到 2 后收到 1
          到达顺序 2 → 1 ，按到达顺序生效 ⇒ 最终 x=1     ✗ 用户的第二次写丢失
   ③ 读己之写被违反（"头像怎么还是旧的？"）
          用户上传 new.jpg ──► R1（新）
          刷新页面被路由 ──► R2（旧）  ⇒ 显示 old.jpg      ✗ 用户以为上传失败，反复重传
   ④ 写跟随读被违反（"回复先于原消息出现"）
          用户读到消息 m，然后回复 r（r 依赖 m）
          别人先看到 r 再看到 m ⇒ 回复看起来毫无来由      ✗ 因果倒置

关键假设与系统模型：客户端是有状态的（保存会话元数据）；副本是版本化的（每个 key 的每个值带一个可比较的版本号/版本向量）；读可以被路由到满足条件的副本（或等待副本追上）。不需要全局时钟，也不需要所有副本达成一致。

10.2.12 单调读（Monotonic Reads, MR）

定义与目的：如果一个客户端读到了值 $v$，那么它后续的读永远不会看到比 $v$ 更旧的值。

定义 10.7（单调读） 对客户端 $c$ 的任意两次读 $R_1, R_2$，若 $R_1$ 在程序序上先于 $R_2$，且 $R_1$ 在 key $k$ 上观察到的版本为 $ver_1$，则 $R_2$ 对 $k$ 观察到的版本 $ver_2$ 必须满足 $ver_2 \ge ver_1$。

直观解释（”它是什么？”）：客户端的时间不能倒流。讲义的原话是 “reads cannot go back in time”。
违反场景（真实案例）：用户在地铁里刷消息流，先连到低延迟的新副本看到”第 3 条消息”，出站后负载均衡把它切到一个尚未追平的旧副本，刷新后第 3 条消失了——用户会认为”消息被删了”或”App 有 bug”。在分布式收发邮件、聊天、订单列表等多个场景中，这一条违反造成的用户投诉最多。
实现方式：客户端记录”每个 key 已读到的最大版本”（$lastRead[k]$）；下一次读时要求副本的版本 $\ge lastRead[k]$，否则换一个副本或等待该副本追平（实践中通过读修复/等待复制位点）。也可以由服务端用会话粘性（session stickiness）把同一客户端的请求固定到同一副本；粘性只解决”不切换副本”的情形，一旦发生故障切换仍需版本过滤兜底。
复杂度：客户端每个 key 一个整数；读可能多一次 RTT（路由到更合适的副本）或等待复制延迟。

10.2.13 单调写（Monotonic Writes, MW）

定义与目的：一个客户端的写操作，按它发出的顺序在副本上执行。

定义 10.8（单调写） 对客户端 $c$ 的任意两次写 $W_1, W_2$，若 $W_1 \prec_{po} W_2$，则任何副本（以及任何后续读者）看到的效果顺序必须是 $W_1$ 先、$W_2$ 后；即最终状态必须反映 $W_2$。

违反场景：客户端在同一会话里执行 x=1 然后 x=2（例如”先保存草稿再提交”），两条写经由不同网络路径/不同协调者到达同一副本，副本按到达顺序生效，先收到 2 后收到 1 ⇒ 最终 x=1，用户的第二次写被静默丢失（”我明明改成了 2，怎么又变回去了？”）。
注意一个重要的细节：如果系统用版本号/时间戳 + LWW 合并（如 Cassandra 按时间戳取胜），单调写通常会”顺带”被满足——因为后发的写时间戳更大。但它并不自动成立：时间戳来自物理时钟，时钟回拨（NTP 调整、闰秒、虚拟机迁移）会让后发的写拿到更小的时间戳；多主（multi-master）系统中不同副本的时钟也无法保证单调。因此”单调写”在实现上依赖客户端/连接级别的顺序保证，而不是服务器时钟。
实现方式：客户端给写编号（$seq$），并要求副本按序号应用（拒绝或缓冲序号倒退的写）；或者用连接粘性保证同一会话的写走同一条有序通道（TCP 本身保序）。在多副本场景中，正确做法是把”写序列号 + 会话 id”随写传播，接收副本对每个会话维护 lastSeq。

10.2.14 读己之写（Read Your Writes, RYW / Read My Writes, RMW）

定义与目的：客户端能看到自己之前的写。

定义 10.9（读己之写） 若客户端 $c$ 执行了写 $W$（对 key $k$），随后执行读 $R$（$W \prec_{po} R$），则 $R$ 必须返回”等于或新于 $W$ 所写版本”的值。

违反场景（务必记住的例子）：用户更新了头像。
1. 用户在设置页上传新头像 new.jpg，请求被路由到副本 R1（写入成功，返回 200 OK）；
2. 用户立刻返回个人主页，这次请求被负载均衡路由到副本 R2，而 R1→R2 的异步复制还在路上；
3. 页面显示的还是 old.jpg。用户会认为”上传失败”，于是反复重传（造成大量重复写与流量），或者直接投诉”这个 App 坏了”。购物车的”加了商品但购物车是空的”、发帖后”我的主页没有这条帖子”、改密码后”新密码登不上”都是同一个 bug 的不同马甲。这类问题在任何”写主副本、读从副本”（读写分离）的架构里都天然存在，与系统规模无关。
实现方式：把读路由到包含该客户端最新写的副本（客户端记录 $lastWrite[k]$ 的版本，读时要求副本版本 $\ge lastWrite[k]$）；或者让写者在写完成后携带版本号并粘住连接（sticky session）；或者在客户端做本地回写（write-through cache：写成功后把值放进本会话缓存，后续读直接命中）——最后这种做法在移动端非常常见。
与因果一致性的关系：读己之写 ≈ 会话内部的因果一致性。若把”同一客户端”看作一个进程，那么 $W \to R$ 的要求正是因果一致性中”读到某写的效果前必须看到该写”的会话局部版本。这也说明：读己之写不需要全局协调，它只需要保证”我这个客户端的因果链”在会话内不被打破。

10.2.15 写跟随读（Writes Follow Reads, WFR）

定义与目的：如果一个客户端在读到值 $v$ 之后写了值 $w$，那么在任何看到 $w$ 的副本上，$v$ 也已经被看到。

定义 10.10（写跟随读） 若客户端 $c$ 的读 $R$ 读到了写 $W_v$ 的值，之后 $c$ 发出写 $W_w$，则在任何副本上，$W_w$ 的生效都必须晚于 $W_v$ 的生效（$W_v$ 是 $W_w$ 的因果前驱）。

直观解释（”它是什么？”）：写的因果前驱必须先于写本身到达。它保证了”依赖关系的可传递性“：我的回复依赖于我读到的内容，所以看到我回复的人也必须先看到那个内容。
违反场景：用户在论坛读到帖子 A（内容”会议改到周三”），然后回复帖子 B（”收到，周三见”）。如果写路径没有携带因果依赖，B 可能先于 A 复制到某个副本：其他用户刷到 B 时看到”收到，周三见”，却不知道在说什么——因果倒置。群聊里”（回复）好的”出现在原消息之前的”幽灵回复”就是这一类。
实现方式：写操作携带它在读时观察到的依赖集合（可以用版本向量表示：$dep(W_w) = $ 客户端读到的所有写的版本），接收副本必须先应用 $dep$ 中的所有写、再应用 $W_w$（否则缓冲）。这就是把 Lecture 15 的因果广播思想用在存储写入路径上；COPS 系统称之为”因果依赖的写”。
与单调写的区别：单调写约束”我的写之间”的顺序（$W_1 \to W_2$）；写跟随读约束”我的读与我的写之间”的顺序（$R \to W$）。两者结合（MR + MW + RYW + WFR）恰好等于”会话内的因果一致性“。

10.2.16 四条保证的组合、实现方案与它和因果一致性的关系

组合关系（必须讲清）：
1. 四条保证彼此正交，可以任意组合。只实现单调读不实现读己之写是常见的（例如只做”读时版本过滤”而不记录写版本）；反过来只做”写后粘住连接”就得到读己之写而不一定有单调读。
2. 四条全开 ≈ “会话因果一致性”：把每个客户端看作一个进程，四条保证合起来保证”客户端自己看到的视图是因果一致的”，而且跨客户端也满足”写跟随读”这一条因果约束（因为 $W_v \to W_w$ 被传播到所有看到 $W_w$ 的副本）。
3. 它们都可以在分区可用的系统上实现：因为每条保证的判定只需要客户端自己的元数据 + 副本的版本号，不需要任何跨副本协商；分区期间最坏的结果是”某个副本版本不够新”，此时客户端换副本或降级即可（而不是不可用）。

一个综合实现方案（客户端维护版本向量 + 会话粘性）：

会话状态（客户端本地，每个会话一份）：
    vv_client      : 客户端已观察到的版本向量（每次读写后合并副本返回的 vv）
    lastRead[k]    : 每个 key 已读到的最大版本           → 支撑 单调读 MR
    lastWrite[k]   : 每个 key 自己写入的最大版本          → 支撑 读己之写 RYW
    seq            : 客户端发出的写序号（单调递增）        → 支撑 单调写 MW
    dep            : 最近一次读观察到的写集合（版本向量）  → 支撑 写跟随读 WFR
读操作：
    1) 计算 need = max(lastRead[k], lastWrite[k])
    2) 优先选择"版本 ≥ need"的副本（按延迟排序，粘性优先）
    3) 副本返回 (value, vv_replica)；客户端更新 lastRead[k] = max(...)，vv_client ⊔= vv_replica
    4) 若所有候选副本都 < need：等待该副本追平（有界等待），或返回"会话未就绪"错误
写操作：
    1) 随写携带 (seq, dep)，交给协调者
    2) 副本要求：本会话的 lastSeq < seq（否则丢弃/缓冲，保证 MW）
                 且 dep 中的所有写都已应用到本副本（否则缓冲，保证 WFR）
    3) 写成功后返回新版本号；客户端更新 lastWrite[k]，seq += 1

与因果一致性的关系（考试常问）：
- 读己之写 ≈ 会话内因果一致性（见 10.2.14）；
- 独立的因果一致性并不蕴含单调读：因果一致性约束的是”因果相关的写在所有人眼中顺序相同”，它允许一个客户端先读到并发的写 $w_2$、之后才”得知”并发的 $w_1$（因为 $w_1 \vert w_2$，顺序自由），于是同一个客户端在同一个 key 上会看到”2 然后 1”——这正是代码里 H2 的历史，它在因果一致性下合法，却违反单调读。回答讲义那个问题：”Does causal imply MR?” → 不蕴含。
- 反过来，会话保证也不蕴含因果一致性：会话保证只管”我自己的视角”，两个不同客户端的视角之间可能互相矛盾（例如甲看到 $x=1,y=1$，乙看到 $y=1,x=0$）。
- 实践含义：如果一个系统是 AP（分区可用）的，那么它最多能给到因果一致性；如果连因果一致性都没有，就至少应该给会话保证——因为会话保证覆盖了绝大多数用户能直接感知到的异常。

10.2.17 CAP 定理（CAP Theorem）与 PACELC

定义与目的：CAP 定理由 Eric Brewer 于 2000 年提出猜想，2002 年由 Gilbert 与 Lynch 形式化证明。它说的是：在一个分布式数据系统中，下面三条性质不可能同时满足：
1. 一致性（Consistency）：所有节点在任何时刻看到相同的数据，或者说读返回最近一次写——严格地说，CAP 中的 C 指的是原子一致性 / 线性一致性（定义 10.1）；
2. 可用性（Availability）：系统始终允许操作，且每个到达未故障节点的请求都在有限时间内返回响应（注意：不是”返回正确结果”，也不是”返回得很快”）；
3. 分区容忍（Partition Tolerance）：即使网络分区（节点之间的消息被任意丢弃）系统仍然继续工作。
直观解释（”它是什么？”）：CAP 像”地震时被切成两半的银行“：连接两家分行的线路断了（分区已经发生，无法选择），此时只剩两条路——要么让其中一家分行的柜员停下来告诉客户”现在办不了”（保一致性、牺牲可用性），要么让两家都继续收钱、但账本在一段时间内对不上（保可用性、牺牲一致性）。注意”线路断了”是既成事实，不是你能选的选项。
定理陈述与证明思路（严格版见 10.3.3）：

定理 10.1（CAP） 不存在这样的异步、确定性、单对象读/写寄存器的实现：它在任意网络分区下既满足原子一致性（C）又满足可用性（A）。

证明是构造性反证：把节点分成两组 $G_1, G_2$，让它们之间的所有消息被丢弃。客户端 1 向 $G_1$ 中的节点写 $v_1$；由于要满足 A，这次写必须在有限时间内返回。客户端 2 向 $G_2$ 中的节点读；同样由于 A，这个读也必须在有限时间内返回。但 $G_2$ 中的节点与 $G_1$ 之间的所有消息都被丢弃，它在本地看到的事件序列与”根本没有发生过这次写“的执行完全一致（不可区分），因此它只能返回初值 $v_0$。可是按实时序，写在读开始之前就已完成，任何线性化都必然把写排在读之前，读必须返回 $v_1 \ne v_0$。矛盾。$\blacksquare$

三个关键澄清（学生最容易误解的地方，务必记牢）：
1. P 不是可选项：网络分区（跨数据中心断网、海底光缆被切断、机架交换机故障、DNS 失效）在真实系统中必然会发生，问题只是”何时”与”持续多久”。因此工程上正确的问法不是”要不要 P”，而是”分区期间牺牲 C 还是牺牲 A“。
2. CAP 的取舍只在分区期间生效：没有分区时，C 和 A 可以同时拥有（只是可能要付出延迟代价）。所以正确的表述是”分区期间在 C 与 A 之间做二选一“，而不是“三选二”——”三选二”的说法误导了几代工程师。
3. 多数派一侧可以继续保持 C：在 quorum 系统里，分区后多数派一侧仍然能组成 quorum，因而继续提供线性一致性（少数派一侧拒绝服务）；这正是”CP 系统”的真实行为，也是 10.4.2 的代码演示的内容。
机制图解（CAP 三角与 PACELC 决策树）：

                    C（线性一致性）
                           /\
                          /  \
                         /     \
                        /        \
                       /   现实    \
                      /    只能选    \
                     /     一条边      \
                    /                    \
                   /                       \
                   /_______________________
                  A ───────────────────────P

   ┌──────────────────────────────────────────────────────────────────────┐
   │ CP（牺牲可用性）  : HBase, BigTable, ZooKeeper, etcd, Spanner        │
   │ AP（牺牲一致性）  : Cassandra, Dynamo, Riak, Voldemort, DNS          │
   │ 可调（按操作选）  : MongoDB（读/写关注）、Cassandra 一致性级别       │
   │ 非复制 RDBMS      : CA（单机无所谓分区；一旦真分区即不可用）         │
   └──────────────────────────────────────────────────────────────────────┘

   PACELC 决策树（Abadi 2012：P 时选 A/C，否则选 L/C）
   ┌──────────────────────────────────────────────────────────────────────┐
   │ 发生了网络分区 P 吗？                                                │
   │   ├── 是 ⇒ 在 A（可用性）与 C（一致性）之间取舍                      │
   │   │        · 选 A ⇒ PA：Cassandra、Dynamo、Riak                      │
   │   │        · 选 C ⇒ PC：HBase、Spanner、ZooKeeper、etcd              │
   │   └── 否 ⇒ 在 L（延迟）与 C（一致性）之间取舍   ← 这一半更常见！     │
   │            · 选 L ⇒ EL：Dynamo、Cassandra、PNUTS                     │
   │            · 选 C ⇒ EC：BigTable、HBase、VoltDB、Megastore           │
   └──────────────────────────────────────────────────────────────────────┘
   读法：Cassandra 常被写作 PA/EL —— 分区时选可用性，无分区时选低延迟。

CAP 的常见误用（极其重要）：

概念	出处	含义	与 CAP 的 C 的关系
CAP 的 C	Brewer / Gilbert-Lynch	线性一致性 / 原子一致性：读返回最近一次写，所有操作看起来原子生效	—— 就是它本身
ACID 的 C	数据库事务	不违反完整性约束（外键、唯一性、断言等），是应用定义的不变量	完全不同！ACID 的 C 是事务的语义约束，与副本、并发、分区无关
BASE 的 E（最终一致）	NoSQL 实践	副本最终收敛，中间可以不一致	是 CAP 的 C 的反面，常被错误地当成”CAP 的 C 的一个弱版本”
“三选二”	流行误读	以为可以放弃 P	错：P 不可放弃，只能在分区期间取舍 C 与 A

PACELC 定理（更精确的扩展，务必掌握）：Abadi 指出 CAP 只描述了”分区期间”的行为，而分区在真实系统中是罕见事件——系统在 99.9% 的时间里都在无分区状态下运行，此时真正的权衡发生在延迟（Latency）与一致性（Consistency）之间：

PACELC：if (P) then choose A or C; Else choose L or C. 即：发生分区时在可用性与一致性之间取舍；否则（无分区时）在延迟与一致性之间取舍。

为什么无分区时也有这个取舍？因为”强一致”意味着写必须等到足够多的副本确认（跨数据中心就是几十毫秒的 RTT），读必须去协调者/多数派取最新值。这些等待与分区无关，纯粹是”等别人“的延迟成本。PACELC 因此比 CAP 更贴近工程现实，也是面试与系统选型时更该引用的模型。

10.2.18 一致性模型的层次结构（Lattice）与实现机制映射

这是本章最重要的一张图。 强模型蕴含弱模型（能提供强一致的系统”顺便”满足所有更弱的模型），反之不成立；每一处”蕴含”都对应一个真实存在的、合法的执行反例（见 10.3.5 的证明与 10.4.1 的代码判定矩阵）。

机制图解（蕴含关系的偏序格）：

   ════════════════ 一致性模型的蕴含格（越往上越强） ════════════════

    ┌────────────────────────────────────────────────────────────────┐
    │ 严格一致性 Strict（理想化：需要全局绝对时间）                  │
    │   └─ 线性一致性 Linearizable / 原子一致性（= CAP 中的 C）      │
    └────────────────────────────┬───────────────────────────────────┘
                                 │ 蕴含（严格更强）   ✗ 反例：H2、H6（允许过期读）
    ┌────────────────────────────────────────────────────────────────┐
    │ 顺序一致性 Sequential（全序 + 每个客户端的程序序）             │
    └────────────────────────────┬───────────────────────────────────┘
                                 │ 蕴含（严格更强）   ✗ 反例：H3（并发写顺序可不同）
    ┌────────────────────────────────────────────────────────────────┐
    │ 因果一致性 Causal（因果相关的写必须同序）                      │
    └────────────────────────────┬───────────────────────────────────┘
                                 │ 蕴含（严格更强）   ✗ 反例：H4（看到果、没看到因）
    ┌────────────────────────────────────────────────────────────────┐
    │ FIFO / PRAM（只保证同一写者的写有序）                          │
    └────────────────────────────┬───────────────────────────────────┘
                                 │ 蕴含（严格更强）   ✗ 反例：H5（同一写者的写倒序）
    ┌────────────────────────────────────────────────────────────────┐
    │ 最终一致性 Eventual（不再写 ⇒ 最终收敛；中间状态无保证）       │
    └────────────────────────────────────────────────────────────────┘

 旁支（与主线正交，可自由组合）：
   · 弱一致性 / 释放一致性 / 入口一致性 —— 用"同步点/屏障"划出一致性边界
   · 以客户端为中心的四条会话保证（MR / MW / RYW / WFR）—— 只管单客户端视角
   · 强最终一致性 SEC = 最终一致性 + CRDT（无冲突自动合并）
   · 混合型：Red-Blue 一致性、per-key sequential、有界陈旧（bounded staleness）

模型 ↔ 实现机制 ↔ 代价 ↔ 真实系统：

一致性模型	实现机制	是否需要协调	分区下可用？	真实系统
线性一致性	quorum 读写 $R+W>N$；共识（Paxos/Raft）日志；单主	是（每次操作都要）	否（少数派阻塞/报错）	Spanner、etcd、ZooKeeper、HBase(单 region)
顺序一致性	全序广播（定序者或共识决定全局顺序），异步应用	是（定序需要）	否	教学系统、部分内存一致性模型
因果一致性	向量时钟 + 因果广播/因果依赖的写	部分（只需传播因果依赖，不需全局定序）	是	COPS、AntidoteDB、Riak（dotted version vector）
FIFO 一致性	每个写者一个单调序号，接收方按写者保序	否	是	消息队列单分区（Kafka）、日志复制
弱一致性	屏障 / 同步点 / fence（release-acquire）	部分（只在同步点）	——	共享内存系统、DSM、多核内存模型
最终一致性	异步复制 + 读修复 + 反熵（Merkle Tree）+ 冲突解决	否	是	DNS、Cassandra、Dynamo、Riak、S3、DynamoDB
会话保证（MR/MW/RYW/WFR）	客户端版本元数据 + 读路由 + 连接粘性	否	是	几乎所有移动 App 的后端、Cosmos DB（session 级）

10.2.19 更新的模型，以及”一致性是一个旋钮”

有界陈旧（Bounded Staleness）：最终一致性的”可量化版”——承诺数据最多滞后 $K$ 个版本或 $T$ 个时间单位，用户/应用可以在读时设置 $K$ 或 $T$。这样既保留了低延迟，又给应用一个可验证的边界（”我最多看到 5 秒前的数据”，而不是”不知道多久”）。
概率有界陈旧（Probabilistically Bounded Staleness, PBS）：进一步给出期望意义上的边界——”在 99.9% 的读中，陈旧度不超过 $k$ 个版本或 $t$ 毫秒”，即一种 SLA 式的、统计化的一致性预测。它承认了”分布式系统的延迟是概率分布而不是确定值”这一事实。
Red-Blue 一致性：把客户端事务重写成”红操作 + 蓝操作”两类，蓝操作跨数据中心可交换执行（最终一致），红操作必须在每个数据中心以相同顺序执行（强一致）。它把”一致性的粒度”从”整个系统”细化到”每个操作“。
Per-Key Sequential：每个 key 内部保证全局全序，不同 key 之间不保证。它是很多真实系统的实际语义（Kafka 的分区、单键事务、分片数据库）。
现代观点：一致性是一个可调的谱（spectrum），而不是一个布尔属性。 讲义用一条从”强（Sequential/Linearizable）”到”最终一致”的光谱来表达这件事，并在结尾给出选择原则：

Use the lowest consistency model that is “correct” for your application. （使用能满足你应用正确性的最弱的一致性模型——这样才能拿到最快的读写与最高的可用性。）

这条原则的实践含义是：不要全系统统一上强一致。同一个应用里，”用户余额扣减”需要线性一致，”商品浏览计数”用最终一致就够了，”我自己的购物车”用会话保证就够，”推荐列表”甚至可以容忍分钟级陈旧。把一致性的粒度做到”每个操作可调”，才是现代系统（Cassandra 的一致性级别、Cosmos DB 的 5 种级别、MongoDB 的 read/write concern）真正的设计哲学。

10.3 算法伪代码与正确性分析

算法 10.3.1：一致性历史判定器（History Checking / Model Checking）

假设与系统模型

系统模型：异步。我们只使用历史中可观察的实时序（调用/响应时刻），不假设任何全局时钟同步。
故障模型：无故障（判定的是”已记录下来的执行是否符合契约”）；实际工程中由探针（Jepsen 等工具）在不注入故障/注入故障两种条件下分别收集历史。
良构性假设：(a) 客户端是顺序的（同一客户端的操作不重叠）；(b) 同一个 $(key, value)$ 最多被写一次，使”读返回的是哪个写”有唯一归因；(c) 未完成的操作按标准做法补齐（extend and complete）后再判定。
输入规模：$n$ 个操作，$m$ 个 key，$p$ 个客户端。

伪代码

算法 LINEARIZABLE(H) —— 判定历史 H 是否存在合法线性化（全序 S）
输入：H = {o_1 … o_n}，o_i = (proc, type, key, val, s, e)
输出：true（线性一致）/ false（不线性一致）

 1  must ← 空表                                  // must[i] = 必须排在 o_i 之前的操作集合
 2  for i ← 1 to n:
 3      for j ← 1 to n:
 4          if e(o_i) < s(o_j) then must[j] ← must[j] ∪ {i}        // 实时序约束
 5          if proc(i)=proc(j) and s(o_i) < s(o_j) then must[j] ← must[j] ∪ {i}
 6  return SEARCH(0, ∅, {})                       // placed = ∅, last = 空映射

函数 SEARCH(cnt, placed, last) -> bool
 7  if cnt = n then return true                   // 全部操作已放置 ⇒ 找到合法全序
 8  for i ← 1 to n:
 9      if i ∈ placed then continue
10      if must[i] ⊄ placed then continue         // 前驱未放置 ⇒ 剪枝
11      if type(o_i) = R then                     // 读：必须返回"最近一次写"
12          if last[key(o_i)] ≠ val(o_i) then continue              // 剪枝
13          if SEARCH(cnt+1, placed ∪ {i}, last) then return true
14      else                                      // 写：成为该 key 新的"最近一次写"
15          last' ← last ⊕ {key(o_i) → val(o_i)}
16          if SEARCH(cnt+1, placed ∪ {i}, last') then return true
17  return false

算法 10.3.1b SEQUENTIAL(H)   ：同上，但第 4 行的实时序约束被删除（只保留程序序）
算法 10.3.1c CAUSAL(H)       ：为每个进程 p 独立搜索一个"视图" V_p：
       每步可选 (1) 应用 p 的下一个操作（读：要求 V_p 中该 key 的最近写 = 读到的值）；
                 (2) 把某个"因果前驱都已进入 V_p"的写加入 V_p；
       要求 V_p 对因果序 → 向下封闭。所有进程都存在这样的 V_p ⇔ 因果一致。
算法 10.3.1d FIFO(H)         ：同 10.3.1c，但把因果序 → 换成"同一写者的写之间的程序序"。

算法逻辑解说

先建约束图：第 2–5 行把”谁必须排在谁前面”算出来。线性一致性的约束是实时序（严格地说再加上程序序，由良构性它是实时序的子集，写上更稳妥）；顺序一致性只保留程序序——这就是两个模型在算法层面的唯一差别，也解释了为什么”线性一致 ⇒ 顺序一致”。
深度优先地”造”一个全序：第 7–17 行从左到右逐个决定”下一个生效的操作是谁”。只有当前所有前驱都已被放置的操作才是候选（第 10 行）。这一步保证最终得到的一定是约束偏序的合法线性扩展。
读操作的即时校验（关键剪枝）：因为全序是从左到右构建的，放下一个读 $r$ 的那一刻，”$r$ 之前最近一次写”是已知的（就是 last[key]）。只要它与 $r$ 的返回值不符，这条路立刻剪掉（第 12 行）。不需要等全序造完再回头检查——这是整个算法的效率来源。
走的例子（H2）：历史为 $W_1=$P1:W(x,1)[0,10]、$W_2=$P2:W(x,2)[0,10]、$R_1=$P3:R(x)=2[20,30]、$R_2=$P3:R(x)=1[40,50]。
- 约束：实时序 $W_1 \to R_1, W_1 \to R_2, W_2 \to R_1, W_2 \to R_2$；程序序 $R_1 \to R_2$。
- 候选第一步只能是 $W_1$ 或 $W_2$（两个读都被写”卡住”）。
- 取 $W_1$：last[x]=1。下一步候选：$W_2$（$R_1$ 仍需 $W_2$ 先放置）。放 $W_2$ 后 last[x]=2。
- 下一步放 $R_1$：要求 last[x] = 2 = 返回值 2 ✓。再放 $R_2$：要求 last[x] = 1，但当前是 2 ✗ → 回溯。
- 回溯到取 $W_2$ 开头：对称地 $R_1$ 通过、$R_2$ 失败。所有分支穷尽 → 返回 false（非线性一致）。
- 而 SEQUENTIAL(H2) 返回 true：去掉实时序后，全序 $W_2, R_1, W_1, R_2$ 合法。同一个历史、同一份代码，只差一条约束边，判定结果就不同——这正是”线性一致严格强于顺序一致”的算法体现。
实用加速（工程实践）：线性一致性的判定问题是 NP-完全的（Gibbons & Korach, 1997），因此真实工具（Knossos、Porcupine、Jepsen）不会硬搜全部操作，而是利用以下性质：
- 局部性（locality）：一份历史线性一致 $\iff$ 它对每个对象的限制都线性一致（Herlihy & Wing 的局部性定理）。因此可以按 key 分片并行判定。
- P-组合性（P-compositionality）：对某些”可交换”的操作类型（例如只读操作、对不同 key 的写）可以独立判定后再合并。
- 必要条件的快速排除：对每个读 $r$，若”在 $r$ 开始之前完成的、对同 key 的写”中恰好只有一个 $w$，且没有对同 key 的写与 $r$ 并发，则 $r$ 必须返回 $w$ 的值——违反即可立即判定为非线性一致（无需搜索）。这就是”对每个读，检查它的返回值必须来自它之前最近的那次写“的实用形式。

正确性论证

可靠性（Soundness，判定为 true 必有依据）：算法只在两处接受一个操作——第 10 行（所有前驱已放置）与第 12 行（读值与当前 last 一致）。返回 true 时的放置顺序 $S$ 因此满足：① 对每条约束边 $i \to j$ 都有 $i$ 在 $j$ 之前（第 10 行的不变式：任何被放置的操作，其全部前驱都已被放置，归纳得所有约束边都指向”从前到后”的方向）；② 每个读的值都等于 $S$ 中它前面最近一次写的值（第 12 行）。这正是定义 10.1 的两个条件，故 $H$ 线性一致。
完备性（Completeness，判定为 false 必无解）：设存在合法线性化 $S^$。按 $S^$ 的顺序依次做放置决策：第 $k$ 步放 $S^$ 中第 $k$ 个操作。由 $S^$ 尊重全部约束，它的所有前驱必在它之前被放置，故第 10 行不剪枝；由 $S^*$ 满足读规则，第 12 行也不剪枝。于是搜索沿这条路径一路到达 cnt = n 并返回 true。不存在”有解却判无解”的情形。
终止性（Liveness）：SEARCH 每层递归 $cnt$ 严格加 1，深度不超过 $n$；每层最多 $n$ 个分支 → 搜索树有限，必然终止。对因果/FIFO 版本，每个进程的视图搜索同样是有限深度的回溯，也会终止。
注意：本算法判定的是”这份历史是否可能来自一个线性一致的系统”，即验证（verification）；它不是“实现一个线性一致系统”的算法（那是 quorum/共识，见 Lecture 19）。

复杂度

时间：最坏 $O(n!)$（即穷举全序）；对满足”每个读在它之前恰好有一个已完成的写”的顺序历史（无并发），剪枝后是 $O(n)$；实际工具中单个 key 的操作数通常很小（并发窗口内只有几个操作），因此局部化后可以做到 $O(n \cdot c!)$，其中 $c$ 是单个 key 上并发操作的最大数目。
空间：递归栈 $O(n)$，每层维护 last 的副本 → $O(n \cdot m)$（可用回溯 + 撤销把 last 降到 $O(m)$）。
判定问题的固有难度：线性一致性判定是 NP-完全的；顺序一致性判定同样是 NP-完全的（对有限历史）；因果一致性与 FIFO 一致性的判定可在多项式时间内完成（只需为每个进程构造视图的线性扩展并用拓扑排序检查读规则），因为它们的约束是”每个进程一组约束”，而不是”一个全局全序”。

算法 10.3.2：以客户端为中心一致性的会话状态机（Session State Machine）

假设与系统模型

客户端有状态、单线程（一次一个请求）；副本版本化（每个 key 的每个值带一个可比版本号 $ver$，可以是标量或版本向量）；副本可能落后，但永远不撒谎（返回的 $ver$ 一定与值匹配）。
通道可能丢失/延迟/重复；客户端可以在不同时刻连接不同副本（移动场景）。
副本集 $R$，每个操作一次 RPC；分区可能发生。

伪代码

会话状态（客户端本地）：
    lastRead[k]   : 对 key k 已读到的最大版本          // 支撑 单调读 MR
    lastWrite[k]  : 自己对 key k 写入的最大版本        // 支撑 读己之写 RYW
    seq           : 本会话已发出的写次数（单调递增）    // 支撑 单调写 MW
    dep           : 最近一次读观察到的版本向量         // 支撑 写跟随读 WFR
    candidates(R) : 当前可用的副本列表（按 RTT 排序，粘性副本优先）

CLIENT-READ(k):
 1  need ← max(lastRead[k], lastWrite[k])              // 会话视角要求的最低版本
 2  for r in candidates(R) ordered by (sticky, RTT):
 3      (v, ver, vv) ← SEND r.CLIENT-READ(k)
 4      if ver ≥ need then                              // 该副本足够新
 5          lastRead[k] ← max(lastRead[k], ver)
 6          dep ← dep ⊔ vv                              // 合并副本的版本向量
 7          return v
 8      else remember (v, ver) as best-so-far
 9  return best-so-far 或 SESSION-NOT-READY           // 全部候选都太旧：等待或报错

CLIENT-WRITE(k, v):
10  seq ← seq + 1
11  choose coordinator r ∈ candidates(R)               // 建议：与上次成功写相同的 r（粘性）
12  SEND r.CLIENT-WRITE(k, v, seq, session_id, dep)    // 随写携带序号与因果依赖
13  wait for ACK (ver_new) 或 超时
14  if ACK: lastWrite[k] ← max(lastWrite[k], ver_new)
15  return ACK / FAIL

副本端（对每个会话 session_id 维护 lastSeq）：
16  upon receiving CLIENT-WRITE(k, v, seq, sid, dep):
17      if seq ≤ lastSeq[sid] then DROP/REPLY-ACK        // 保证 MW：序号倒退的写被丢弃
18      if dep ⊄ applied_writes then BUFFER              // 保证 WFR：因果前驱未到，先缓冲
19      lastSeq[sid] ← seq ; APPLY(k, v) ; return ACK(ver_new, vv)

算法逻辑解说

读的两阶段决策（第 1–9 行）：先算出”我这次读至少要看到多新的版本”——取 $lastRead$ 与 $lastWrite$ 的最大值：前者保证”不比上次读到的更旧”（单调读），后者保证”能看到自己的写”（读己之写）。然后按”粘性优先、延迟次之”的顺序试副本：第一个满足版本要求的副本直接返回（这样大多数读仍然是 1 个 RTT，只有在切换副本/故障切换时才多花一次尝试）。
写的元数据（第 10–15 行）：写携带 $seq$（同一会话内严格递增）与 $dep$（读到的依赖集合）。$seq$ 用于让副本按序应用（拒绝倒退的写），$dep$ 用于让副本在因果前驱都到齐之后才应用。粘性协调者（第 11 行）让大多数写走同一条连接，从而天然大概率保持顺序。
数值小例子（对应 10.4.3 的代码）：客户端先在 R0 读到 x=5（$ver=2$，$lastRead[x]=2$）；用户移动，会话切到 R2（只有 x=3，$ver=1$）。第 1 行算出 $need=2$；第 4 行对 R2 失败，记下 best-so-far；继续试 R0，$ver=2 \ge 2$ ✓ 返回 x=5。用户永远看不到”消息消失”。
退化的情形：若所有候选副本都太旧（例如客户端只连到一个严重滞后的副本），算法会走到第 9 行——要么有界等待（等副本追上，牺牲延迟），要么返回”会话未就绪”（牺牲可用性）。这是一个工程选择：大多数产品选择”等待 + 超时后降级”，因为对于”我自己的写”这类语义，返回错误比返回错误的值更好。

正确性论证

不变式 I1（单调读）：每次成功返回前，第 5 行令 $lastRead[k] \ge ver_{returned}$；下一次读的 $need \ge lastRead[k] \ge ver_{returned}$，第 4 行保证新读的版本 $\ge need$。归纳得：客户端读到的版本单调不减。
不变式 I2（读己之写）：写成功后第 14 行令 $lastWrite[k] \ge ver_{new}$；后续读的 $need \ge ver_{new}$，返回的版本必 $\ge ver_{new}$，即至少要包含自己那次写（或更新的值）。注意：这要求副本的”版本 $\ge ver_{new}$”确实意味着”包含那次写”——对单值 key 的版本号成立；对需要版本向量的数据类型，需把 $lastWrite$ 记成版本向量并做偏序比较（$\ge$ 换成 $\sqsubseteq$）。
不变式 I3（单调写）：副本端第 17 行丢弃序号 $\le lastSeq[sid]$ 的写，且第 19 行只在应用后推进 $lastSeq[sid]$，因此对同一会话，副本应用写的顺序与客户端发出的顺序一致（归纳：客户端发出 $seq=1,2,\dots$ 的顺序与应用顺序一致）。前提：同一会话的写必须交给同一副本或共享同一 $lastSeq$ 表的副本组；跨副本时需把 $lastSeq$ 随会话迁移（否则要退化为”按序号缓冲 + 补发”）。
不变式 I4（写跟随读）：dep 是客户端读到的写集合的版本向量；第 18 行要求依赖全部已应用才应用本写 ⇒ 任何看到本写的副本都已经看到 $dep$ 中的写。边界条件：若依赖永远不到达（分区），该写会一直缓冲；实现上需要”有界缓冲 + 超时降级”，此时应保证降级方向是拒绝写而不是违反因果。
活性（Liveness）：只要存在一个版本足够新的健康副本且网络最终恢复，第 2–8 行的循环就会在有限次尝试后成功；有界等待/超时确保算法不会无限阻塞。反之在持续分区且客户端只连到落后副本时，算法有意识地牺牲可用性（返回 SESSION-NOT-READY）——这是设计选择，不是缺陷。

复杂度

客户端空间：$O(\#\text{keys})$ 个版本号 + 一个版本向量（$O(p)$ 个整数），即”每个 key 几十字节”。
读的消息复杂度：1 个 RTT（乐观情形：第一个候选副本就满足）；最坏 $\vert R\vert $ 个 RTT（逐个尝试）或一次有界等待。
写的消息复杂度：1 个 RTT（除非需要重发/粘性协商）。
对比全局强一致：线性一致的读在 quorum 下需要 $R$ 个 RPC（至少一个多数派），而会话保证下”没有版本冲突时”只需 1 个 RPC 给任意副本——这是它在 AP 系统上可行的根本原因。

算法 10.3.3：CAP 不可能性证明（作为分析性”伪代码”/形式化论证）

假设与系统模型

系统由节点集合 $\{n_1, \dots, n_N\}$ 组成，节点之间通过可任意丢弃消息的网络通信（分区容忍 P 的模型化：网络是一个”对手”，可以选择丢弃某条消息）。
系统实现单个读/写寄存器（对象 $x$，初值 $v_0$）；每个节点各存一份拷贝。这是最弱的接口假设，因此结论对任何更强的接口（多 key、事务）都成立。
客户端可以向任意节点发起 $\text{write}(v)$ 或 $\text{read}()$；节点可以互相转发消息；算法是确定性的；系统是异步的（无时钟上界）。
C（原子一致性）：所有操作存在一个全序 $S$，$S$ 尊重实时序，且每个读返回 $S$ 中它前面最近一次写的值（定义 10.1）。
A（可用性）：任何到达未故障节点的请求，都必须在有限时间内返回一个正确的响应（读返回某个合法值、写返回成功）。注意：把”总是返回错误”也算作响应会让 A 平凡成立，因此标准做法是把错误/超时响应排除在 A 之外。

形式化论证（反证法）

定理：不存在同时满足 C 与 A 且容忍任意分区的异步寄存器实现。

证明（构造性反证）：
  1. 假设存在这样的实现 ALG。
  2. 构造执行 α1：把节点划分为两个非空集合 G1、G2，令 G1 与 G2 之间的
     所有消息都被丢弃（分区成立，P 被满足）。
  3. 客户端 c1 向 G1 中的节点 n1 发出 write(v1)：
       由 A，ALG 必须在有限时间内返回（记为时刻 t1）；由 C，此后任何读都必须看到 v1。
  4. 客户端 c2 在 t1 之后向 G2 中的节点 n2 发出 read()：
       由 A，ALG 必须在有限时间内返回某个值 v_ret。
  5. 构造辅助执行 α0：与 α1 完全相同，唯一区别是 —— 客户端 c1 的 write(v1)
     从未发出（或者它发给了 G1，但所有跨分区的消息本来就被丢弃）。
       关键观察：n2 在 α1 与 α0 中"看到"的本地事件序列完全一致
       （它收到的消息、本地时钟、本地状态都一样，因为跨分区消息全部丢失），
       而 ALG 是确定性的，因此 n2 在两次执行中返回相同的值 v_ret。
  6. 在 α0 中只有一次 read、没有任何成功的 write，因此 v_ret 只能是初值 v0
       （任何线性化都必须把 read 排在最前）。
  7. 于是 α1 中的 read 也返回 v0。但在 α1 中 write(v1) 已在 t1 完成，
     且 read 在 t1 之后才发起（实时序 write ≺rt read），
     任何线性化都必须把 write(v1) 排在 read 之前 ⇒ read 必须返回 v1 ≠ v0。
     矛盾。
  8. 因此假设不成立：¬(C ∧ A) 在存在分区的执行中成立。    ∎

论证解说与常见追问

矛盾的本源是”不可区分性（indistinguishability）”：$G_2$ 一侧的节点无法区分”另一侧发生了写”与”另一侧什么都没发生”，因为在两种情况下它收到的消息完全一样。这是分布式系统里最重要的推理工具之一（与 FLP 不可能性、两将军问题同源，见 Lecture 17）。
算法只有三种可能的”出路”，都不满足 C ∧ A：(a) 阻塞等待分区恢复 → 违反 A（未在有限时间返回）；(b) 返回错误/超时 → 违反 A（按上面 A 的定义）；(c) 返回旧值 → 违反 C。“三选一”是强制的，没有第四条路。
多数派一侧可以同时保持 C 和 A：若 $G_1$ 有 $N/2+1$ 个副本，它仍能组成 quorum 并继续提供线性一致性；少数派一侧则拒绝服务。所以”CP 系统”并不是”永远不可用”，而是”少数派一侧不可用”。 这也解释了 Cassandra 中 QUORUM 读写为什么在”客户端连到多数派一侧”时仍然是强一致的（见 Lecture 9 的 $R+W>N$）。
推论 1（延迟代价，PACELC 的来源）：即使没有分区，为了满足 C，写必须等到足够多副本确认（跨数据中心即一个 RTT 量级），读必须去取最新版本。因此”无分区时在 L 与 C 之间取舍”是必然的，只是把 CAP 的 A 换成了 L。
推论 2（CAP 的适用边界）：定理只谈单个对象上的原子一致性 + 可用性。它并不意味着”AP 系统什么都不能保证”——因果一致性、会话保证、CRDT 的强最终一致性全都在分区下可实现；也不意味着”CP 系统写不了”——它能写，只是以可用性/延迟为代价。

算法 10.3.4：CRDT 的收敛性论证（以 G-Counter 与 OR-Set 为例）

假设与系统模型

副本集合 $\{r_1,\dots,r_N\}$，每个副本有一个状态 $s_r \in S$。
状态型 CRDT：存在一个合并函数 $\sqcup : S \times S \to S$，满足 (M1) 交换律 $a \sqcup b = b \sqcup a$；(M2) 结合律 $(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$；(M3) 幂等律 $a \sqcup a = a$；并且 $(S, \sqsubseteq)$ 是偏序集、$\sqcup$ 是最小上界（join），即 $\sqcup$ 关于 $\sqsubseteq$ 单调。
更新（update）是” inflationary “的：本地更新把状态变成 $s \sqcup u$（$s \sqsubseteq s \sqcup u$）。
传播：副本之间通过 gossip/反熵交换状态，接收方执行 $s \leftarrow s \sqcup s_{\text{收到的}}$。通道可能丢失、延迟、乱序、重复；只要有公平（fair）的传播机制，每个更新最终会送达每个副本。

伪代码 / 论证结构

CRDT-MERGE(r, s)                    // 收到某个副本的状态 s
    state[r] ← state[r] ⊔ s

定理 10.3（强最终一致性 SEC）：
    若两个副本 r1、r2 收到了同一组更新 U（顺序任意、次数任意），
    则 state[r1] = state[r2] = ⊔{ u : u ∈ U }

证明：
  设 r 收到更新的顺序为一个序列 u_1, u_2, …, u_k（允许重复，k ≥ |U|）。
  由更新语义，state[r] = s_init ⊔ u_1 ⊔ u_2 ⊔ … ⊔ u_k
   （s_init 为初始状态，且 s_init ⊑ 任何状态，故不影响上界）。
  1. 由 (M1) 交换律，可把序列重排为"U 中每个元素各出现一次 + 若干重复"；
  2. 由 (M3) 幂等律，消除所有重复；
  3. 由 (M2) 结合律，任意加括号得到相同结果；
  故 state[r] = s_init ⊔ (⊔{u : u ∈ U}) —— 只取决于集合 U，与顺序、重复无关。
  对 r1、r2 同理，二者收到同一集合 U ⇒ state[r1] = state[r2]。    ∎

活性（最终收敛）：若每个更新都被公平地传播（每个副本无限次地与其它副本交换状态），
    则对任意更新 u 与副本 r，存在有限时刻之后 u ∈ D_r（r 已收到 u）；
    于是当所有更新都停止产生后，所有副本的"已收集合"最终相同 ⇒ 状态相同。

G-Counter 的具体实例

状态空间：$S = \mathbb{N}^{N}$（$N$ 个副本，第 $i$ 个分量是”由 $r_i$ 执行的增量次数”）。
合并：$\sqcup = $ 逐分量取 $\max$。
验证三律：逐分量 $\max$ 显然满足交换律、结合律、幂等律；$\sqsubseteq$ 取逐分量 $\le$（乘积偏序），$\max$ 正是它的最小上界。✓
本地更新 $+1$：$r_i$ 执行 $s[i] \leftarrow s[i] + 1$，即 $s \leftarrow s \sqcup e_i$（第 $i$ 个分量的单位增量），满足 inflationary。✓
值函数：$\text{value}(s) = \sum_{i=1}^{N} s[i]$。由于值只取决于状态，而状态在”收到同一组更新”后唯一 ⇒ 读到的计数必然一致（这正是”点赞数永远单调不减、且不会因为合并顺序不同而不同”的数学保证）。
对比：如果用”普通整数 + LWW”来做计数器，并发 $+1$ 会互相覆盖（丢失更新，见 10.4.2 实验 C 中 $x=99$ 被静默丢弃）；G-Counter 则永远不会丢失任何一次 $+1$——这就是”用数据结构消灭冲突”的含义。

OR-Set 的具体实例（可增可删集合）

状态空间：$S = \mathcal{P}(E \times \text{Tag}) \times \mathcal{P}(\text{Tag})$，即 $(\text{adds}, \text{removed})$。
合并：逐分量取并集（$\cup$）；并集满足交换律、结合律、幂等律，且是幂集偏序 $(\subseteq)$ 的最小上界。✓
add(e)：生成一个全局唯一标签 $t$（例如 (replica_id, 本地计数器)），执行 $\text{adds} \leftarrow \text{adds} \cup \{(e,t)\}$。
remove(e)：把当前观察到的 $e$ 的所有标签加入 $\text{removed}$：$\text{removed} \leftarrow \text{removed} \cup \{t : (e,t) \in \text{adds}\}$。
查询：$e \in \text{set} \iff \exists t:\ (e,t) \in \text{adds} \wedge t \notin \text{removed}$。
“并发加 vs 删 ⇒ 加获胜”的证明：设副本 A 执行 add(e) 生成标签 $t_A$（$t_A$ 全局唯一，任何其他副本的 removed 集合中都不可能有 $t_A$），副本 B 并发执行 remove(e)，其 removed 只包含它当时看到的标签（都不等于 $t_A$）。合并后 $(e,t_A) \in \text{adds}$ 且 $t_A \notin \text{removed}$ ⇒ $e$ 存在 ✓。这就是 add-wins 语义，也正是购物车”并发加商品不会被另一设备的删除操作吃掉”的保证。
收敛性：由定理 10.3，合并顺序与重复都不影响最终 $(\text{adds},\text{removed})$ ⇒ 所有副本的查询结果一致 ✓。

正确性论证的边界（必须说清 CRDT 不提供什么）

CRDT 提供的是强最终一致性（SEC）：收敛 + 无冲突解决过程。它不提供线性一致性——两个副本在收敛之前可以读到不同的值，CRDT 只是保证了”最终相同”以及”相同的更新集合 ⇒ 相同的状态”。
元数据单调增长：标签集合与墓碑（tombstone）不会自动缩小，需要垃圾回收（例如基于因果稳定时间戳的回收，或 delta-CRDT 减小传输量）。
有些语义本质上不可交换（”余额不得为负”“库存不得超卖”“先到先得”），这类约束必须用协调（quorum/共识）来保证，不能靠 CRDT 绕过。

10.3.5 四种数据为中心模型的蕴含关系：证明链与反例

定理 10.2（层次结构） 在客户端顺序（良构）的假设下： $\text{Linearizable} \;\Longrightarrow\; \text{Sequential} \;\Longrightarrow\; \text{Causal} \;\Longrightarrow\; \text{FIFO/PRAM}$ 且每一步都严格（反向不成立），反例分别为代码中的 H2/H6、H3、H4。

第 1 步：线性一致 $\Rightarrow$ 顺序一致

证明：设 $S$ 是线性化全序。定义 10.1(i) 保证 $S$ 尊重实时序；由良构性，程序序 $\prec_{po} \subseteq \prec_{rt}$，故 $S$ 也尊重程序序，满足定义 10.2(i)；读规则两条定义完全一致，满足 (ii)。于是同一个 $S$ 就是顺序一致性的见证。$\blacksquare$
严格性反例（H2）：$P_1{:}W(x,1)$、$P_2{:}W(x,2)$ 并发，$P_3$ 先读到 2、后读到 1。顺序一致性有解 $S = W(x,2), R(x){=}2, W(x,1), R(x){=}1$（程序序保持），但该 $S$ 把”早已完成的 $W(x,1)$”排到了 $R(x){=}2$ 之后，违反实时序，故线性一致性无解。
另一个反例（H6，过期读）：$W(x,1)$ 完成后 $R(x)$ 仍返回初值 0。这在顺序一致性下合法（把 $R$ 排在 $W$ 之前即可），线性一致性下非法。它说明了顺序一致性允许”过期读”，这是它与线性一致性最直观的差别。

第 2 步：顺序一致 $\Rightarrow$ 因果一致

证明：设 $S$ 为顺序一致的全序，$\to$ 为写上的因果序。先证 $S$ 是 $\to$ 的线性扩展（即 $w_1 \to w_2 \Rightarrow w_1 <_S w_2$），对 $\to$ 的定义归纳：
- 程序序边：同客户端先发的 $w_1$、后发的 $w_2$，由定义 10.2(i) 直接得 $w_1 <_S w_2$。
- read-from 边：若 $w_2$ 的作者在发出 $w_2$ 之前读了 $r$，且 $r$ 返回 $w_1$ 写的值。由定义 10.2(ii)，$S$ 中 $r$ 之前最近的写恰是 $w_1$，故 $w_1 <S r$；又 $r \prec{po} w_2$，由 10.2(i) 得 $r <_S w_2$；传递得 $w_1 <_S w_2$。
- 传递闭包：$<_S$ 是传递的，闭包步骤自动保持。现在把所有写操作（按 $S$ 的顺序）作为每个进程 $p$ 的视图 $V_p$：
- (i) 向下封闭：$V_p$ 包含所有写，且 $S$ 是 $\to$ 的线性扩展 ⇒ 若 $w^{\prime} \to w$ 则 $w^{\prime} <_S w$，$w^{\prime}$ 自然也在 $V_p$ 中 ✓；
- (ii) $V_p$ 的全序（$S$ 在写上的限制）是 $\to$ 的线性扩展 ✓；
- (iii) $p$ 的读按程序序出现在 $S$ 中，且每个读返回 $S$ 中它前面最近的写（定义 10.2(ii)），这正是 $V_p$ 中该 key 最近的写 ✓；$p$ 自己的写也在 $V_p$ 中 ✓。于是同一个全局视图对所有进程都合法 ⇒ 因果一致性成立。$\blacksquare$
严格性反例（H3）：$P_1{:}W(x,1)$、$P_2{:}W(x,2)$ 并发（互不因果），$P_3$ 读到 1 再读到 2，$P_4$ 读到 2 再读到 1。因果一致性允许（两个并发写在不同进程上顺序可不同：$P_3$ 的视图是 $[W_1, W_2]$，$P_4$ 的是 $[W_2, W_1]$）；顺序一致性要求唯一全序，而 $P_3$ 要求 $W(x,1) < R_3{=}1 < W(x,2) < R_3{=}2$、$P_4$ 要求 $W(x,2) < R_4{=}2 < W(x,1) < R_4{=}1$，两条链合起来给出 $W(x,1) < W(x,2)$ 与 $W(x,2) < W(x,1)$，矛盾 ⇒ 无解。$\blacksquare$

第 3 步：因果一致 $\Rightarrow$ FIFO 一致

证明：FIFO 的写序 $R_{\text{FIFO}}$ 只包含”同一写者的写之间的程序序”这一种边，而因果序 $\to$ 的定义中同样包含程序序边并做了传递闭包，故 $R_{\text{FIFO}} \subseteq \to$。设 $V_p$ 是因果一致性的一个合法视图：它对 $\to$ 向下封闭且其全序是 $\to$ 的线性扩展。由于 $R_{\text{FIFO}} \subseteq \to$：(a) 该全序也是 $R_{\text{FIFO}}$ 的线性扩展 ✓；(b) 向下封闭性对 $R_{\text{FIFO}}$ 的子集自动成立 ✓；(c) 读规则（iii）在两种模型下完全相同 ✓。因此同一个 $V_p$ 也是 FIFO 一致性的合法视图。$\blacksquare$
严格性反例（H4）：$P_1{:}W(x,1)$；$P_2$ 读到 $x{=}1$ 后写 $W(y,1)$；$P_3$ 读到 $y{=}1$ 后读 $x$ 得到 0。这里 $W(x,1) \to W(y,1)$（read-from）⇒ 因果一致性要求所有进程”看到 $y{=}1$ 就必须看到 $x{=}1$”，$P_3$ 违反；但 FIFO 一致性不关心写者之间的关系（$P_1$ 与 $P_2$ 是不同写者），因此它只要求 $P_3$ 的读按程序序、且各写者的写内部有序——这些都被满足 ⇒ FIFO 一致成立。$\blacksquare$

补充观察 1（因果一致性不蕴含单调读）：H2 的历史在因果一致性下合法（$P_3$ 的视图从 $[W(x,2)]$ 扩展为 $[W(x,2), W(x,1)]$），但它让同一个客户端先读到 $x{=}2$、后读到 $x{=}1$，违反以客户端为中心的单调读。所以讲义的问题”Does causal imply MR?”的答案是否——数据为中心的模型管的是”所有人的共识”，会话保证管的是”单个人的视角”，两者是正交的。这正是”会话保证”必须作为独立一族存在的理由。

补充观察 2（强弱与可用性的对应）：定理 10.2 的链条同时也是协调代价的链条：线性一致/顺序一致需要全局协调（分区不可用），因果一致只需传播因果依赖（分区可用），FIFO 只需写者内序号（分区可用），最终一致完全不需要协调（分区可用）。“越强越贵”这一直觉在形式层面表现为”约束边越多、需要协商的对象越多”。

10.4 代码示例与分布式实现

本节的三段代码分别回答三个问题：(1) 给我一份执行历史，它到底符不符合某个一致性模型？（判定器，最重要）；(2) 强一致、quorum、最终一致三种模式在延迟、陈旧读、分区可用性上差多少？（CAP 实验）；(3) 以客户端为中心的保证怎么落到代码里？（会话状态机）。三段代码都只用 Python 标准库，单机 python3 直接可跑，随机种子固定，输出可复现。

代码 10.4.1：一致性模型检查器（History Checker）

"""一致性模型检查器：判定历史是否满足线性一致 / 顺序一致 / 因果一致 / FIFO 一致。
只用标准库：python3 c10_code1.py"""
from collections import namedtuple
INIT = 0                                                 # 所有 key 的初始值
Op = namedtuple("Op", "proc kind key value start end")    # kind: W 写 / R 读

def W(p, k, v, s, e):
    return Op(p, "W", k, v, s, e)
def R(p, k, v, s, e):
    return Op(p, "R", k, v, s, e)                        # 读的 value = 读到的值
def history(*ops):
    """历史 = 一组操作。假设：客户端一次只发一个请求（同客户端操作不重叠），
    且同一个 (key, value) 最多被写一次，这样"读返回哪个写"没有歧义。"""
    return list(ops)

def writes(h):
    return [i for i, o in enumerate(h) if o.kind == "W"]

def writer_of(h, key, value):                            # 写出该值的写操作编号
    return next((i for i in writes(h) if h[i].key == key and h[i].value == value), None)

def prog_edges(h):                                       # 程序序：同一客户端按发出顺序
    return {j: [i for i in range(len(h)) if i != j and h[i].proc == h[j].proc
                and h[i].start < h[j].start] for j in range(len(h))}
def exists_total_order(h, must):
    """回溯搜索合法全序：按顺序放置操作，放下一个读时立刻检查它是否返回了
    全序中它前面最近一次写的值（不满足就剪枝）。must[i]=必须排在 i 前的操作。"""
    n = len(h)
    def dfs(cnt, placed, last):
        if cnt == n:
            return True
        for i in range(n):
            if i in placed or any(j not in placed for j in must[i]):
                continue
            o = h[i]
            if o.kind == "R":
                if last.get(o.key, INIT) != o.value:
                    continue
                if dfs(cnt + 1, placed | {i}, last):
                    return True
            elif dfs(cnt + 1, placed | {i}, dict(last, **{o.key: o.value})):
                return True
        return False
    return dfs(0, frozenset(), {})

def is_linearizable(h):
    """存在全序 S：S 尊重真实时间序（a 完成先于 b 开始 => a 排在 b 前），
    且每个读返回 S 中它前面最近一次写的值。"""
    real = {j: [i for i in range(len(h)) if i != j and h[i].end < h[j].start]
            for j in range(len(h))}
    prog = prog_edges(h)
    return exists_total_order(h, {j: sorted(set(real[j]) | set(prog[j])) for j in real})

def is_sequentially_consistent(h):
    """存在全序 S：只要求 S 尊重每个客户端的程序序，不要求与真实时间一致。"""
    return exists_total_order(h, prog_edges(h))
def write_order(h, causal):
    """写操作之间的偏序：同进程程序序；causal=True 时再加 read-from 与传递闭包。"""
    e = {i: [] for i in writes(h)}
    for a in writes(h):
        for b in writes(h):
            if a != b and h[a].proc == h[b].proc and h[a].start < h[b].start:
                e[b].append(a)
    if causal:
        for b in writes(h):
            for r in h:                                  # read-from：读到 w 之后才写出 b
                if r.kind == "R" and r.proc == h[b].proc and r.end <= h[b].start:
                    w = writer_of(h, r.key, r.value)
                    if w is not None and w != b:
                        e[b].append(w)
        changed = True
        while changed:                                   # 传递闭包
            changed = False
            for b in writes(h):
                for a in list(e[b]):
                    for c in e[a]:
                        if c not in e[b]:
                            e[b].append(c)
                            changed = True
    return e

def is_causally_consistent(h):
    """每个进程有一个"已看到的写序列"（视图）：它是因果序的线性扩展且向下封闭，
    读返回视图中该 key 最近一次写的值；并发写在不同进程上顺序可以不同。"""
    return views_ok(h, write_order(h, causal=True))

def is_fifo_consistent(h):
    """FIFO(PRAM)：只要求同一写者的写被所有进程按发出顺序看到（不含 read-from）。"""
    return views_ok(h, write_order(h, causal=False))

def views_ok(h, we):
    for p in sorted({o.proc for o in h}):
        own = sorted([i for i, o in enumerate(h) if o.proc == p], key=lambda i: h[i].start)
        if not view_exists(h, own, we):
            return False
    return True

def view_exists(h, own, we):
    """为单个进程找合法视图：每步可选（1）处理自己的下一个操作，
    或（2）把某个"因果前驱都已看到"的写加入视图，两种选择可任意交错。"""
    pos_of = {i: k for k, i in enumerate(own)}
    own_w = {i for i in own if h[i].kind == "W"}
    def step(pos, seen, latest):
        if pos == len(own):
            return True
        i = own[pos]
        if h[i].kind == "R":
            if latest.get(h[i].key, INIT) == h[i].value and step(pos + 1, seen, latest):
                return True                              # 读：看视图里该 key 最新的写
        elif i in seen:
            if step(pos + 1, seen, latest):
                return True
        elif all(a in seen for a in we[i]):              # 自己的写：等因果前驱进视图
            if step(pos + 1, seen | {i}, dict(latest, **{h[i].key: h[i].value})):
                return True
        for w in writes(h):                              # 扩展视图
            if w in seen or any(a not in seen for a in we[w]):
                continue
            if w in own_w and pos_of[w] >= pos:          # 不能提前看到自己未来的写
                continue
            if step(pos, seen | {w}, dict(latest, **{h[w].key: h[w].value})):
                return True
        return False
    return step(0, frozenset(), {})
def build():
    def mk(*spec):                                       # ("客户端","W/R","key",值,起,止)
        return history(*[Op(*s) for s in spec])
    H = {}
    H["H1 lin-ok"] = mk(("P1", "W", "x", 1, 0, 10), ("P2", "R", "x", 1, 20, 30))
    H["H2 seq-not-lin"] = mk(("P1", "W", "x", 1, 0, 10), ("P2", "W", "x", 2, 0, 10),
                             ("P3", "R", "x", 2, 20, 30), ("P3", "R", "x", 1, 40, 50))
    H["H3 causal-not-seq"] = mk(("P1", "W", "x", 1, 0, 10), ("P2", "W", "x", 2, 0, 10),
                                ("P3", "R", "x", 1, 20, 30), ("P3", "R", "x", 2, 40, 50),
                                ("P4", "R", "x", 2, 20, 30), ("P4", "R", "x", 1, 40, 50))
    H["H4 fifo-not-causal"] = mk(("P1", "W", "x", 1, 0, 10),
                                 ("P2", "R", "x", 1, 20, 30), ("P2", "W", "y", 1, 40, 50),
                                 ("P3", "R", "y", 1, 60, 70), ("P3", "R", "x", 0, 80, 90))
    H["H5 none"] = mk(("P1", "W", "x", 1, 0, 10), ("P1", "W", "x", 2, 20, 30),
                      ("P2", "R", "x", 2, 40, 50), ("P2", "R", "x", 1, 60, 70))
    H["H6 stale-read"] = mk(("P1", "W", "x", 1, 0, 10), ("P2", "R", "x", 0, 20, 30))
    return H

CHECKS = [("LIN", is_linearizable), ("SEQ", is_sequentially_consistent),
          ("CAUS", is_causally_consistent), ("FIFO", is_fifo_consistent)]
EXPECT = {"H1 lin-ok": (1, 1, 1, 1), "H2 seq-not-lin": (0, 1, 1, 1),
          "H3 causal-not-seq": (0, 0, 1, 1), "H4 fifo-not-causal": (0, 0, 0, 1),
          "H5 none": (0, 0, 0, 0), "H6 stale-read": (0, 1, 1, 1)}

if __name__ == "__main__":
    res = {n: tuple(1 if f(h) else 0 for _, f in CHECKS) for n, h in build().items()}
    head = "%-20s | %-5s %-5s %-5s %-5s" % ("history", *[n for n, _ in CHECKS])
    print(head + "\n" + "-" * len(head))
    for n, r in res.items():
        print("%-20s | %s" % (n, " ".join("%-5s" % ("YES" if v else "no") for v in r)))
    assert res == EXPECT, "判定结果与预期不符"
    print("\n[OK] 6 份历史 x 4 个模型的判定全部符合预期")
    for s, w, d in [(0, 1, "线性一致 => 顺序一致"), (1, 2, "顺序一致 => 因果一致"),
                    (2, 3, "因果一致 => FIFO 一致")]:
        assert all((not r[s]) or r[w] for r in res.values()), "蕴含关系不成立：" + d
        print("[OK] %-22s 反例（弱成立、强不成立）：%s"
              % (d, ", ".join(n for n, r in res.items() if r[w] and not r[s])))

运行输出：

history              | LIN   SEQ   CAUS  FIFO 
----------------------------------------------
H1 lin-ok            | YES   YES   YES   YES  
H2 seq-not-lin       | no    YES   YES   YES  
H3 causal-not-seq    | no    no    YES   YES  
H4 fifo-not-causal   | no    no    no    YES  
H5 none              | no    no    no    no   
H6 stale-read        | no    YES   YES   YES  

[OK] 6 份历史 x 4 个模型的判定全部符合预期
[OK] 线性一致 => 顺序一致           反例（弱成立、强不成立）：H2 seq-not-lin, H6 stale-read
[OK] 顺序一致 => 因果一致           反例（弱成立、强不成立）：H3 causal-not-seq
[OK] 因果一致 => FIFO 一致        反例（弱成立、强不成立）：H4 fifo-not-causal

【代码做什么？】

操作与历史的数据结构：Op(proc, kind, key, value, start, end) 严格对应 10.2.3 的形式化框架——客户端编号、读/写类型、数据项、值、调用时刻、响应时刻；对读操作，value 字段表示读到的返回值。history(*ops) 是历史 $H$ 的构造器。
两条约束边的计算：prog_edges 计算程序序（同一客户端按 start 排序）；is_linearizable 另外计算实时序（h[i].end < h[j].start），并与程序序取并。这一步把”线性一致 vs 顺序一致”的差别压缩成一行代码。
exists_total_order：回溯搜索一个合法全序（算法 10.3.1）。它按顺序逐个放置操作：只有所有前驱都已放置的操作才是候选；放下一个读时立刻用 last[key] 检查”是否返回了最近一次写的值”，不符就剪枝；写操作则把 last[key] 更新为自己的值（回溯时恢复）。
is_causally_consistent / is_fifo_consistent：视图模型。先算”写之间的偏序”write_order：FIFO 只用”同一写者的程序序”；因果一致额外加入 read-from（若某进程读到 $w$ 的值之后才发出 $w^{\prime}$，则 $w \to w^{\prime}$）并做传递闭包。再对每个进程独立搜索一个合法视图：每步要么处理自己的下一个操作，要么把”因果前驱都已进入视图”的写加进来，两种选择任意交错——这正是”并发写在不同进程上可以顺序不同”的机制化表达。
六份精心构造的历史：H1（线性一致）、H2（顺序一致但非线性——并发写被倒序读到）、H3（因果一致但非顺序一致——两个读者顺序相反）、H4（FIFO 一致但违反因果——看到果没看到因）、H5（全部违反——同一写者的写倒序）、H6（过期读：顺序一致但非线性）。
判定矩阵与断言：程序打印”历史 × 模型”的 ✓/✗ 矩阵，并断言三件事：矩阵与预期完全一致；强模型成立则弱模型必须成立（蕴含关系）；每一步蕴含都存在反例（严格性）。断言失败会直接抛 AssertionError。
可复现：没有随机性，输出完全确定。

【分布式机制透视】

这段代码不模拟网络，它模拟的是“裁判”：分布式系统运行后留下的可观察历史就是系统的”证词”，检查器负责判断这份证词是否与宣称的一致性契约相符。真实工程里，历史由注入故障的测试框架收集（Jepsen/Knossos/Porcupine 就是工业级的同款工具），本代码是它们的极小内核。
start/end 就是分布式系统里客户端侧的调用/响应时刻。注意它们只用于比较先后，不需要时钟同步——实时序只要求”本地观察到的先后”，因此在异步系统中是可获得的（这正是线性一致性可以在没有全局时钟的系统中被定义和判定的原因）。
视图模型里的”每个进程一个视图”对应真实系统里每个客户端/副本各自维护的已见写集合：因果一致性在实现上就是”随写传播版本向量（Lecture 12），接收方检查依赖是否到齐”。
剪枝的效率来源（last[key] 的即时校验）在真实工具中同样关键：并发窗口越小，可判定的历史规模越大。

代码 10.4.2：强一致 vs quorum vs 最终一致——把 CAP 跑出来

"""强一致 / quorum / 最终一致三种复制模式的离散事件模拟，并用分区场景把 CAP
定理"跑"出来。只用标准库：python3 c10_code2.py"""
import heapq
import random
import unicodedata
N = 3                # 副本数
BASE, JITTER = 2.0, 1.0           # 单程网络延迟 (ms)
SLOW_P, SLOW_EXTRA = 0.15, 25.0   # 慢节点概率与额外延迟：强一致必须等它
TIMEOUT = 50.0       # 等不到足够副本时的超时 (ms)
PROP_DELAY, RETRY = 4.0, 10.0     # 异步传播延迟 / 分区期间的重传间隔 (ms)
THINK = 3.0          # 客户端两次操作之间的思考时间 (ms)
INIT = 0

def pad(s, w):
    """按东亚字符宽度补齐，让中英混排的表格对齐。"""
    return s + " " * max(0, w - sum(2 if unicodedata.east_asian_width(c) in "WF"
                                    else 1 for c in s))

class Replica:
    def __init__(self, rid):
        self.rid = rid
        self.store = {}          # key -> (value, version)
        self.side = 0            # 分区组号

class Cluster:
    """mode: strong=写/读全部副本；quorum=R=W=2（W+R>N）；eventual=写一个副本+本地读"""
    def __init__(self, seed=425):
        self.rng = random.Random(seed)
        self.reps = [Replica(i) for i in range(N)]
        self.partition = False
        self.now = 0.0
        self.pending = []        # 小顶堆：(送达时刻, 副本, key, value, version, 发送方组号)
        self.ver = 0             # 全局写版本号（时间戳），用于 LWW 冲突解决
    def reachable(self, rid, side):
        return (not self.partition) or self.reps[rid].side == side
    def side_replicas(self, side):
        return [r for r in range(N) if self.reachable(r, side)]
    def latency(self):
        lat = 2.0 * (BASE + self.rng.random() * JITTER)      # 一次 RPC 往返
        return lat + (SLOW_EXTRA if self.rng.random() < SLOW_P else 0.0)
    def apply(self, rid, key, val, ver):
        cur = self.reps[rid].store.get(key)                  # LWW：版本大者获胜
        if cur is None or ver > cur[1]:
            self.reps[rid].store[key] = (val, ver)
    def run_until(self, t):
        """把模拟时钟推进到 t，并送达所有到期的异步消息（分区阻断的重传）。"""
        self.now = max(self.now, t)
        while self.pending and self.pending[0][0] <= self.now:
            at, rid, key, val, ver, side = heapq.heappop(self.pending)
            self.now = max(self.now, at)
            if self.partition and self.reps[rid].side != side:
                heapq.heappush(self.pending, (self.now + RETRY, rid, key, val, ver, side))
                continue
            self.apply(rid, key, val, ver)
    def split(self, groups):
        self.partition = True
        for i, g in enumerate(groups):
            self.reps[i].side = g
    def heal(self):
        self.partition = False
        for r in self.reps:
            r.side = 0
        self.run_until(self.now + 10 * RETRY)                # 等待反熵补齐
    def write(self, key, val, mode, side=0):
        """返回实际延迟；None 表示超时不可用。"""
        self.ver += 1
        ver = self.ver
        targets = self.side_replicas(side)
        if mode == "eventual":                               # 写一个副本即返回
            if not targets:
                return None
            coord = self.rng.choice(targets)
            lat = self.latency()
            self.now += lat
            self.apply(coord, key, val, ver)
            for r in range(N):
                if r != coord:
                    heapq.heappush(self.pending, (self.now + PROP_DELAY, r, key,
                                                  val, ver, side))
            return lat
        need = N if mode == "strong" else 2                  # W = N 或 W = 2
        if len(targets) < need:
            self.now += TIMEOUT                              # 阻塞到超时 -> 不可用
            return None
        lat = max(self.latency() for _ in targets[:need])
        self.now += lat
        for r in targets[:need]:
            self.apply(r, key, val, ver)
        return lat
    def read(self, key, mode, side=0):
        """返回 (value, version, 延迟, 是否可用)。"""
        targets = self.side_replicas(side)
        if mode == "eventual":                               # 只问本侧一个副本
            if not targets:
                return None, -1, None, False
            lat = self.latency()
            self.now += lat
            val, ver = self.reps[self.rng.choice(targets)].store.get(key, (INIT, 0))
            return val, ver, lat, True
        need = N if mode == "strong" else 2                  # R = N 或 R = 2
        if len(targets) < need:
            self.now += TIMEOUT
            return None, -1, None, False
        lat = max(self.latency() for _ in targets[:need])
        self.now += lat
        best = max((self.reps[r].store.get(key, (INIT, 0)) for r in targets[:need]),
                   key=lambda t: t[1])
        return best[0], best[1], lat, True

def pct(xs, q):
    xs = sorted(xs)
    return xs[min(len(xs) - 1, int(q * len(xs)))]

def exp_a(rounds=40):
    print("实验 A：无分区，每轮先写 x=t 再立刻读 x，统计陈旧读比例与延迟")
    print(pad("mode", 10) + pad("可用率", 9) + pad("陈旧读比例", 13) +
          pad("p50 延迟", 11) + "p95 延迟")
    print("-" * 56)
    for mode in ("strong", "quorum", "eventual"):
        c, stale, avail, lat = Cluster(), 0, 0, []
        for t in range(1, rounds + 1):
            wl = c.write("x", t, mode)
            c.run_until(c.now + THINK)
            val, ver, rl, ok = c.read("x", mode)
            if wl is None or not ok:
                continue
            avail += 1
            lat.append(wl + rl)
            stale += (val != t)
        print(pad(mode, 10) + pad("%.0f%%" % (100.0 * avail / rounds), 9) +
              pad("%.0f%%" % (100.0 * stale / max(avail, 1)), 13) +
              pad("%.2f ms" % pct(lat, 0.5), 11) + "%.2f ms" % pct(lat, 0.95))

def exp_b():
    print("\n实验 B：网络分区 {R0} | {R1,R2}；客户端 A 在 R0 侧，客户端 B 在 R1R2 侧")
    print(pad("mode", 10) + pad("A 侧写 x=99", 26) + "B 侧读 x")
    print("-" * 68)
    for mode in ("strong", "quorum", "eventual"):
        c = Cluster()
        c.write("x", 1, "strong")                            # 先建立初值 1
        c.run_until(c.now + PROP_DELAY * 3)
        c.split([0, 1, 1])
        wl = c.write("x", 99, mode, side=0)
        c.run_until(c.now + PROP_DELAY * 3)
        val, ver, rl, ok = c.read("x", mode, side=1)
        wtxt = "不可用（%.0fms 超时）" % TIMEOUT if wl is None else "成功，%.2f ms" % wl
        rtxt = "不可用（%.0fms 超时）" % TIMEOUT if not ok else \
               "返回 x=%s（%s）" % (val, "新值" if val == 99 else "旧值")
        print(pad(mode, 10) + pad(wtxt, 26) + rtxt)
        if mode == "eventual":
            c.heal()
            vals = [c.reps[i].store.get("x", (INIT, 0))[0] for i in range(N)]
            print(pad("", 10) + "修复后三副本收敛为 %s，断言 %s" % (vals, vals == [99] * N))
            assert vals == [99] * N
    print("结论：分区期间 strong/quorum 在少数派一侧「不可用」（牺牲 A 保 C），")
    print("      eventual 两侧都可用，但少数派读到旧值（牺牲 C 保 A）——这就是 CAP。")

def exp_c():
    print("\n实验 C：分区期间两侧都接受写（eventual 模式），修复后靠 LWW 收敛")
    c = Cluster()
    c.write("x", 1, "eventual")
    c.run_until(c.now + PROP_DELAY * 3)
    c.split([0, 1, 1])
    la = c.write("x", 99, "eventual", side=0)                # 少数派侧写 99
    c.run_until(c.now + PROP_DELAY)
    lb = c.write("x", 77, "eventual", side=1)                # 多数派侧写 77（版本更大）
    c.run_until(c.now + PROP_DELAY)
    print("    两侧都写入成功：A 侧 x=99（%.2fms），B 侧 x=77（%.2fms）" % (la, lb))
    print("    分区中的副本状态：%s  <-- 已分叉（divergence）"
          % [c.reps[i].store.get("x", (INIT, 0))[0] for i in range(N)])
    c.heal()
    after = [c.reps[i].store.get("x", (INIT, 0))[0] for i in range(N)]
    print("    修复并反熵后：%s  <-- 收敛到 LWW 胜者 x=77" % after)
    assert after == [77] * N
    print("    最终一致只承诺「最终收敛」，不承诺收敛到哪个值：x=99 被静默丢弃。")

if __name__ == "__main__":
    exp_a()
    exp_b()
    exp_c()

运行输出：

实验 A：无分区，每轮先写 x=t 再立刻读 x，统计陈旧读比例与延迟
mode      可用率   陈旧读比例   p50 延迟   p95 延迟
--------------------------------------------------------
strong    100%     0%           34.72 ms   61.09 ms
quorum    100%     0%           11.55 ms   60.63 ms
eventual  100%     68%          10.50 ms   60.33 ms

实验 B：网络分区 {R0} | {R1,R2}；客户端 A 在 R0 侧，客户端 B 在 R1R2 侧
mode      A 侧写 x=99               B 侧读 x
--------------------------------------------------------------------
strong    不可用（50ms 超时）       不可用（50ms 超时）
quorum    不可用（50ms 超时）       返回 x=1（旧值）
eventual  成功，5.20 ms             返回 x=1（旧值）
          修复后三副本收敛为 [99, 99, 99]，断言 True
结论：分区期间 strong/quorum 在少数派一侧「不可用」（牺牲 A 保 C），
      eventual 两侧都可用，但少数派读到旧值（牺牲 C 保 A）——这就是 CAP。

实验 C：分区期间两侧都接受写（eventual 模式），修复后靠 LWW 收敛
    两侧都写入成功：A 侧 x=99（5.21ms），B 侧 x=77（5.20ms）
    分区中的副本状态：[99, 77, 77]  <-- 已分叉（divergence）
    修复并反熵后：[77, 77, 77]  <-- 收敛到 LWW 胜者 x=77
    最终一致只承诺「最终收敛」，不承诺收敛到哪个值：x=99 被静默丢弃。

【代码做什么？】

离散事件模拟（discrete-event simulation）：全局模拟时钟 now，所有网络往返都推进它；异步传播的消息放在小顶堆 pending 里，run_until(t) 把时钟推进到 t 并送达所有到期消息。不sleep、不多线程，因此结果完全确定、可复现。
三种复制模式（write/read 的 mode 参数）：
- strong：写全部 $N$ 个副本、读全部 $N$ 个副本（$W=R=N$），取版本号最大的值；
- quorum：$W=R=2$，$N=3$，满足 $R+W>N$ 与 $W>N/2$（Lecture 9 的 quorum 条件）；
- eventual：写只落到一个协调者副本就返回，其余副本在 PROP_DELAY 之后异步收到；读只问本侧随机一个副本。
版本号与 LWW 冲突解决：每次写分配一个全局递增的 ver（相当于时间戳），apply 只在 ver 更大时才覆盖本地值——这就是 Cassandra 的 “latest timestamp wins”。
慢节点/长尾：每次 RPC 有 15% 概率多加 25 ms（SLOW_P/SLOW_EXTRA）。这模拟真实数据中心的 straggler；强一致必须等最慢的那个副本，因此它的 p50/p95 延迟被显著拉高。
实验 A（无分区）：40 轮”写 x=t → 立刻读 x”，统计可用率、读到陈旧值的比例、延迟分位数。
实验 B（分区 + 单写者）：把副本分成 $\{R_0\}$ 与 $\{R_1,R_2\}$ 两侧，客户端 A 在少数派侧写 x=99、客户端 B 在多数派侧读 x——三种模式的表现就是 CAP 定理本身。
实验 C（分区 + 双写者）：分区期间两侧各自接受写（x=99 与 x=77），修复分区后靠 LWW 收敛，并断言收敛结果。

【分布式机制透视】

副本状态：每个 Replica 就是一个 key-value 存储（store[key] = (value, version)）；Cluster 是它们的集合加上”网络”（延迟模型 + 分区判定 + 消息队列）。
分区怎么模拟：split([0,1,1]) 给副本打上组号，reachable() 规定”只有同组才能通信”；被阻断的异步消息会被重新排队重试（相当于反熵 repair 的持续重传），因此 heal() 之后副本能自动补齐——这就是最终一致性”收敛”的机制来源。
可用性怎么体现：write/read 在可达副本数不足 need 时推进 TIMEOUT 时钟并返回 None，即”阻塞到超时”，对应真实系统的超时报错；exp_b 因此能直接打印出”不可用（50ms 超时）”。
陈旧读怎么度量：实验 A 中只有单一写者，因此”读到的值 ≠ 刚写入的值”就是一次陈旧读。eventual 模式下读到陈旧值的比例约 2/3——因为读会随机命中三个副本之一，而写只落在其中一个，另外两个要等异步传播。
与真实系统的对应：strong ≈ 同步复制 + 全副本确认（RDBMS 主从同步、etcd 的线性读）；quorum ≈ Cassandra QUORUM/Dynamo 的 $R+W>N$；eventual ≈ Cassandra ONE/ANY、Dynamo 的异步复制、DNS 的 zone 传播。

【与理论的对应】

实验 A 的”陈旧读比例”把 10.2.9 最终一致性的弱点量化了：它是可以读到任意旧值的（讲义：”Reads might see any previous write”）。
实验 B 是 定理 10.1（CAP） 的一次构造性复现：同一个分区、同一个 key，strong/quorum 在少数派侧不可用（保 C 弃 A），eventual 两侧都可用但返回旧值（保 A 弃 C）。注意 quorum 在多数派侧的读是”正确”的——因为少数派侧根本没能提交写，多数派侧的旧值就是当时唯一的”最近一次写”。
实验 C 是 10.2.10 CRDT 与冲突解决的反面教材：普通寄存器 + LWW 在并发写下会静默丢弃一次更新（$x=99$ 消失）；换成 G-Counter 这样的 CRDT 就不会丢（见 10.3.4）。
长尾对 strong 延迟的影响对应 PACELC 的 EL/EC 权衡：无分区时强一致的真实代价主要不是”分区”，而是”必须等最慢的副本“。

代码 10.4.3：以客户端为中心的一致性——会话元数据的力量

"""以客户端为中心的一致性演示：裸客户端 vs 带会话元数据的客户端。
覆盖单调读、单调写、读己之写三条保证的违反与修复。
运行：python3 c10_code3.py
"""
INIT = 0

class Replica:
    def __init__(self, rid):
        self.rid = rid
        self.store = {}          # key -> (value, version)
        self.propagate = []      # 待送达的其他副本：(送达时刻, key, value, version)
        self.last_seq = {}       # 单调写：session_id -> 已应用的最大序号

class Fabric:
    """3 副本 + 异步复制的极简模型（时间单位为 ms）。"""
    def __init__(self):
        self.reps = [Replica(i) for i in range(3)]
        self.now = 0.0
        self.ver = 0
    def bump(self):
        self.ver += 1
        return self.ver
    def put(self, rid, key, val, ver):
        """直接设置某个副本上的值（用于搭建场景的初始状态）。"""
        self.reps[rid].store[key] = (val, ver)
        self.ver = max(self.ver, ver)
    def raw_apply(self, rid, key, val, ver):
        """没有顺序保证的副本：按到达顺序覆盖（最后一次到达者获胜）。"""
        self.reps[rid].store[key] = (val, ver)
    def versioned_apply(self, rid, key, val, ver):
        """带版本号的副本：只接受更新的版本（LWW）。"""
        cur = self.reps[rid].store.get(key)
        if cur is None or ver > cur[1]:
            self.reps[rid].store[key] = (val, ver)
    def write(self, rid, key, val, lag, ver=None, seq=None, session=None, ordered=False):
        """在副本 rid 上写入，并在 lag 毫秒后异步传播到其他副本。"""
        if ver is None:
            ver = self.bump()
        r = self.reps[rid]
        if ordered and session is not None:
            # 单调写：拒绝序号倒退的写（真实系统用连接粘性或序列号实现）
            if seq < r.last_seq.get(session, -1):
                return ver, False
            r.last_seq[session] = seq
        if ordered:
            self.versioned_apply(rid, key, val, ver)
        else:
            self.raw_apply(rid, key, val, ver)
        for other in self.reps:
            if other.rid != rid:
                other.propagate.append((self.now + lag, key, val, ver))
        return ver, True
    def tick(self, dt):
        self.now += dt
        for r in self.reps:
            keep = []
            for at, key, val, ver in r.propagate:
                if at <= self.now:
                    self.versioned_apply(r.rid, key, val, ver)
                else:
                    keep.append((at, key, val, ver))
            r.propagate = keep
    def read(self, rid, key):
        return self.reps[rid].store.get(key, (INIT, -1))

class Session:
    """带会话元数据的客户端。policy=None 表示"裸客户端"，没有任何保证。"""
    def __init__(self, fabric, sid="S1", policy="session"):
        self.f = fabric
        self.sid = sid
        self.policy = policy
        self.read_ver = {}       # key -> 已读到的最大版本（单调读）
        self.write_ver = {}      # key -> 自己最后一次写的版本（读己之写）
        self.seq = 0             # 单调写：客户端自己给写编号
    def write(self, rid, key, val, lag, ordered=True):
        self.seq += 1
        ver, ok = self.f.write(rid, key, val, lag, seq=self.seq, session=self.sid,
                               ordered=ordered)
        if self.policy == "session" and ok:
            self.write_ver[key] = max(self.write_ver.get(key, -1), ver)
        return ok
    def read(self, candidates, key):
        """candidates = 客户端尝试连接的副本顺序（模拟移动/换接入点）。"""
        if self.policy != "session":
            rid = candidates[0]                     # 裸客户端：连到谁就问谁
            val, ver = self.f.read(rid, key)
            return val, ver, rid, False
        # 会话保证：需要看到自己写过的版本，且不能比上一次读到的版本更旧
        need = max(self.read_ver.get(key, -1), self.write_ver.get(key, -1))
        best = None
        for rid in candidates:
            val, ver = self.f.read(rid, key)
            if best is None or ver > best[1]:
                best = (val, ver, rid)
            if ver >= need:
                break
        val, ver, rid = best
        if ver >= need:
            self.read_ver[key] = max(self.read_ver.get(key, -1), ver)
            return val, ver, rid, True
        return val, ver, rid, False             # 所有可连副本都太旧：需要等待或报错

def banner(t):
    print("\n" + "=" * 72)
    print(t)
    print("=" * 72)

def scenario_monotonic_reads():
    banner("场景 1：单调读（Monotonic Reads）—— 客户端的时间不能倒流")
    for policy in (None, "session"):
        f = Fabric()
        # 副本 0 已经收到较新的写 x=5（版本 2），副本 1/2 还停在旧值 x=3（版本 1）
        f.put(0, "x", 5, 2)
        f.put(1, "x", 3, 1)
        f.put(2, "x", 3, 1)
        cli = Session(f, policy=policy)
        v1, ver1, rid1, _ = cli.read([0], "x")           # 先连到新副本
        cli.f.tick(5)                                    # 用户移动，接入点切换
        stale_ver = f.read(2, "x")[1]                    # 副本 2 上的版本（落后的版本）
        v2, ver2, rid2, ok = cli.read([2, 0], "x")       # 再连到落后副本（回退到 0）
        tag = "裸客户端" if policy is None else "带会话元数据"
        print("  [%s] 第一次读 R0 -> x=%s (v%s)；切换后读 R2 -> x=%s (v%s)" %
              (tag, v1, ver1, v2, ver2))
        if policy is None:
            assert (v1, v2) == (5, 3)
            print("       x 从 5 变回 3 —— 「消息消失了」，单调读被违反")
        else:
            assert (v1, v2) == (5, 5)
            print("       会话发现 R2 上只有 v%s < 已读的 v%s，改由 R0 服务 -> x=%s，未回退" %
                  (stale_ver, ver1, v2))

def scenario_read_your_writes():
    banner("场景 2：读己之写（Read Your Writes）—— 头像更新了吗？")
    for policy in (None, "session"):
        f = Fabric()
        for r in range(3):                             # 老照片（版本 1）在所有副本上
            f.put(r, "avatar", "old.jpg", 1)
        cli = Session(f, policy=policy)
        cli.write(1, "avatar", "new.jpg", lag=1000)     # 上传新头像（版本 2，只到副本 1）
        cli.f.tick(5)
        v, ver, rid, ok = cli.read([2, 1], "avatar")    # 刷新页面，被路由到副本 2
        tag = "裸客户端" if policy is None else "带会话元数据"
        print("  [%s] 上传 new.jpg 后刷新页面，被路由到 R2 -> 看到 %s" % (tag, v))
        if policy is None:
            assert v == "old.jpg"
            print("       用户看到旧头像，以为上传失败反复重传 —— 读己之写被违反")
        else:
            assert v == "new.jpg"
            print("       R2 版本不足，会话路由回 R1 -> 看到 new.jpg，用户满意")

def scenario_monotonic_writes():
    banner("场景 3：单调写（Monotonic Writes）—— 客户端自己的写不能乱序生效")
    for ordered in (False, True):
        f = Fabric()
        f.reps[0].store["x"] = (INIT, -1)
        cli = Session(f, policy="session")
        v1 = f.bump()
        v2 = f.bump()
        # 两条写走不同的网络路径：后发的 W2 先到，先发的 W1 后到
        arrivals = [(2.0, "x", 2, v2, 2), (5.0, "x", 1, v1, 1)]
        applied = []
        for at, key, val, ver, seq in arrivals:
            f.tick(max(0.0, at - f.now))
            r = f.reps[0]
            if ordered:
                if seq < r.last_seq.get(cli.sid, -1):
                    applied.append((val, "被丢弃（序号倒退）"))
                    continue
                r.last_seq[cli.sid] = seq
                f.versioned_apply(0, key, val, ver)
            else:
                f.raw_apply(0, key, val, ver)
            applied.append((val, "已应用"))
        final = f.read(0, "x")[0]
        print("  [%s] 客户端依次发出 x=1(seq1)、x=2(seq2)，副本到达顺序：%s" %
              ("无保序" if not ordered else "带序号", [a[0] for a in applied]))
        print("       副本应用记录：%s；最终 x=%s" % (applied, final))
        if not ordered:
            assert final == 1
            print("       用户写了 2，系统留下 1 —— 单调写被违反（写丢失）")
        else:
            assert final == 2
            print("       序号倒退的写被拒绝，最终 x=2，与客户端发出顺序一致")

if __name__ == "__main__":
    scenario_monotonic_reads()
    scenario_read_your_writes()
    scenario_monotonic_writes()
    banner("小结")
    print("  以客户端为中心的保证只需要客户端维护自己的会话元数据（读版本/写版本/序号），")
    print("  再配合把读路由到「版本足够新」的副本，就能在分区可用（AP）的存储之上，")
    print("  给每个用户一个「不自相矛盾」的视图 —— 这正是它比全局强一致便宜得多的原因。")

运行输出：

========================================================================
场景 1：单调读（Monotonic Reads）—— 客户端的时间不能倒流
========================================================================
  [裸客户端] 第一次读 R0 -> x=5 (v2)；切换后读 R2 -> x=3 (v1)
       x 从 5 变回 3 —— 「消息消失了」，单调读被违反
  [带会话元数据] 第一次读 R0 -> x=5 (v2)；切换后读 R2 -> x=5 (v2)
       会话发现 R2 上只有 v1 < 已读的 v2，改由 R0 服务 -> x=5，未回退

========================================================================
场景 2：读己之写（Read Your Writes）—— 头像更新了吗？
========================================================================
  [裸客户端] 上传 new.jpg 后刷新页面，被路由到 R2 -> 看到 old.jpg
       用户看到旧头像，以为上传失败反复重传 —— 读己之写被违反
  [带会话元数据] 上传 new.jpg 后刷新页面，被路由到 R2 -> 看到 new.jpg
       R2 版本不足，会话路由回 R1 -> 看到 new.jpg，用户满意

========================================================================
场景 3：单调写（Monotonic Writes）—— 客户端自己的写不能乱序生效
========================================================================
  [无保序] 客户端依次发出 x=1(seq1)、x=2(seq2)，副本到达顺序：[2, 1]
       副本应用记录：[(2, '已应用'), (1, '已应用')]；最终 x=1
       用户写了 2，系统留下 1 —— 单调写被违反（写丢失）
  [带序号] 客户端依次发出 x=1(seq1)、x=2(seq2)，副本到达顺序：[2, 1]
       副本应用记录：[(2, '已应用'), (1, '被丢弃（序号倒退）')]；最终 x=2
       序号倒退的写被拒绝，最终 x=2，与客户端发出顺序一致

========================================================================
小结
========================================================================
  以客户端为中心的保证只需要客户端维护自己的会话元数据（读版本/写版本/序号），
  再配合把读路由到「版本足够新」的副本，就能在分区可用（AP）的存储之上，
  给每个用户一个「不自相矛盾」的视图 —— 这正是它比全局强一致便宜得多的原因。

【代码做什么？】

Fabric 模拟三个副本与异步复制：write(rid, key, val, lag, ...) 在本副本立即写入，其余副本在 lag 毫秒后收到；tick(dt) 推进时间并送达消息。put 用于手工搭建场景（例如”R0 上是最新的 x=5（版本 2），而 R1/R2 还停在 x=3（版本 1）”）。
Session 是带会话元数据的客户端：read_ver（每个 key 已读到的最大版本）、write_ver（自己写过的最大版本）、seq（本会话写序号）。policy=None 表示裸客户端（连到谁就问谁），policy="session" 表示启用会话保证。
读的核心逻辑：need = max(read_ver[k], write_ver[k])，然后按 candidates 顺序试副本，返回第一个版本 ≥ need 的副本的结果；若所有副本都太旧，则返回 ok=False（真实系统会在这里选择”短暂等待”或”降级报错”）。
场景 1（单调读）：客户端先在 R0 读到 x=5，切换后连接 R2。裸客户端读到 x=3——时间倒流；带会话元数据的客户端发现 R2 只有 v1 < 已读的 v2，转由 R0 服务，仍返回 5。
场景 2（读己之写）：上传头像 new.jpg（只到 R1），刷新页面被路由到 R2。裸客户端看到 old.jpg——用户以为上传失败、反复重传；会话客户端因 $write\_ver$ 要求而不接受 R2 的旧版本，转由 R1 服务，看到 new.jpg。
场景 3（单调写）：客户端的 x=1（seq 1）与 x=2（seq 2）走不同网络路径，副本先收到 2、后收到 1。无保序时副本按到达顺序覆盖，最终 $x=1$（用户的写被写坏）；带序号时副本用 last_seq[session] 拒绝序号倒退的写，最终 $x=2$。
断言：三个场景各自用 assert 校验”违反”与”修复”两种结果，任一处不符都会失败。

【分布式机制透视】

副本状态：Replica.store[key] = (value, version)，version 是所有保证的比较基准；Replica.last_seq[sid] 是每个会话的写序号水位，用于实现”单调写”。
消息传递：异步复制用 propagate 列表 + tick() 实现”延迟到达”；写路径直接作用于目标副本（模拟客户端到协调者的同步 RPC）。
版本号从哪来：Fabric.bump()（全局递增计数器）或手工 put。真实系统用 per-key 时间戳（Cassandra）、版本向量（Riak）、或混合逻辑时钟（HLC，Lecture 12 的延伸）；代码里”版本”是一个抽象的、可比较的偏序元素，这正是一致性模型与实现解耦的地方。
客户端路由是这套机制的关键动作：会话保证不是靠”让副本变强”，而是靠”客户端挑一个足够新的副本“。在真实系统中它由 SDK/代理层实现（会话 token 放在 cookie 或请求头里，网关据此路由）；如果做不到路由，就退化为”等待复制位点”（read-after-write consistency 的常见实现）。
为什么这在 AP 系统上可行：整个机制只用到”客户端自己记得的版本”和”副本自报的版本”，不需要任何跨副本协商，因此分区期间照样能工作（最坏情况是等待或降级，而不是全系统不可用）。

10.5 性能与可扩展性分析

10.5.1 延迟与吞吐：一致性强度的价格标签

一致的强度最终都兑换成三种成本：消息往返次数（RTT）、需要等待的副本数量（尾延迟）、串行化程度（吞吐上限）。

模型	写路径	读路径	延迟下限	吞吐特征
线性一致（单主/共识）	领导者定序 + 多数派确认（Paxos/Raft 1–2 RTT；$W=N$ 时等全部）	走领导者或读 quorum（$R$ 个 RPC）	1–2 RTT（跨可用区 ≈ 1–5 ms，跨地域 ≈ 30–150 ms）	同一 key 的写被串行化，单 key 吞吐受领导者与磁盘 fsync 限制；可读扩展
线性一致（quorum $R+W>N$）	写 $W$ 个副本（并行，等最慢的）	读 $R$ 个副本并取最新版本	1 RTT，但 p99 被最慢副本拖长	单 key 写仍然要多数派，跨 DC 写吞吐受限
顺序一致（全序广播）	定序（可异步确认）	本地副本即可读	1 RTT（定序），读可 0 RTT	定序器可能成为瓶颈；可批量流水线化
因果一致	本地写 + 传播因果依赖	本地读（等待依赖到齐）	写近 0 RTT（本地提交）+ 异步传播	高吞吐、跨地域友好；元数据（版本向量）带来存储与带宽开销
FIFO	本地写 + 每写者序号	本地读（同一写者内保序）	≈ 0 RTT	几乎无额外开销；但保证很弱
最终一致	本地写即返回	本地读	0 RTT（本地）	写吞吐最高（多主可并发写），冲突解决（LWW/CRDT）是主要成本
会话保证	与底层模式相同	本地读 + 版本过滤/路由	1 RTT（乐观情形，无额外等待）	只增加客户端元数据与偶发路由，几乎不影响吞吐

关键结论：

一致性越强，延迟下界越高、可用性越低、单 key 吞吐越低，但编程难度越低；
尾延迟（p95/p99）比平均延迟更能区分强弱模型——强一致必须等”最慢的那个副本”，这在 10.4.2 的实验 A 里表现为 strong 的 p50/p95 被 straggler 显著拉高；
跨地域部署会把差距放大一个数量级：同城内 RTT 约 0.5 ms，跨可用区 1–2 ms，跨大洲 30–150 ms。因此”跨洲强一致”的写延迟下界就是几十毫秒，这正是 Google Spanner 要用原子钟 + TrueTime（把不确定窗口 $\varepsilon$ 压到 ~7 ms 并做 commit-wait）的原因，也是大多数跨洲系统选择最终一致或因果一致的原因。

10.5.2 可用性：强一致到底牺牲了多少？

设单副本可用性为 $1-f$。无复制的对象可用性是 $1-f$；$k$ 副本只要有一个活着就能读（最终一致/本地读）的可用性是 $1-f^{k}$；而需要 $W$ 个副本同时可达（强一致/quorum）的可用性是

\[A_W = \sum_{i=W}^{N} \binom{N}{i}(1-f)^i f^{N-i}\]

以 $N=3$ 为例：

单副本故障概率 $f$	本地读可用（$W=1$）	quorum 写（$W=2$）	$W=N$ 强一致写	无复制
0.1	99.9000%	97.2000%	72.9000%	90.0000%
0.05	99.9875%	99.2750%	85.7375%	95.0000%
0.01	99.9999%	99.9702%	97.0299%	99.0000%

读法：$f=0.1$ 时（一个不算健康的集群），要求”三个副本全活”的强一致写的可用性是 72.9%，而”随便一个副本活着就行”的最终一致读是 99.9%；如果把要求从 $W=3$ 放宽到 $W=2$（quorum），可用性立刻回到 97.2%。这就是”一致性强度折算成可用性”的具体汇率——也是 Cassandra 把 $W$ 做成可调旋钮（ONE/QUORUM/ALL）的原因。

10.5.3 分区下的行为对照

模型	分区期间少数派一侧	分区期间多数派一侧	分区恢复后
线性一致（单主/共识）	不可用（拒绝写，也可能拒绝读）	可用且保持线性一致	无冲突需要解决（日志未分叉）
顺序一致（全序广播）	不可用（无法定序）	可用	顺序继续，无分叉
因果一致	可用（本地提交，因果依赖缓存）	可用	传播因果链，无冲突（所有副本最终看到同一因果序）
FIFO / 最终一致	可用（各自接受写）	可用	可能出现并发冲突，需要 LWW/版本向量/CRDT 解决
会话保证	可用（最坏情况回退到本地读）	可用	客户端视角自动恢复一致

10.5.4 实现复杂度与真实系统中的落地方式

一致性级别	实现难度	主要工程负担
线性一致（共识）	高	领导者选举、日志复制与 fsync、成员变更、读的租约/ReadIndex、快照与日志压缩
线性一致（quorum）	中	版本号（时间戳）比较、读修复、sloppy quorum 与 hinted handoff 会破坏 $R+W>N$ 的限制
因果一致	中高	版本向量（元数据膨胀）、依赖缓冲与垃圾回收、跨 DC 传播有界性
最终一致	低	反熵（Merkle Tree）、读修复、冲突解决策略（业务语义耦合在这里）
会话保证	低	客户端 SDK 状态、会话 token 在网关的传递、副本路由与回退策略
CRDT	低（运行时）/ 高（设计时）	数据类型必须选对；墓碑与元数据回收；不可交换的业务约束无法表达

真实系统的落地方式（三条典型路线）：

Google Spanner —— 用”时间”换”协调”：每个数据中心部署 TrueTime（GPS + 原子钟），API 返回一个不确定窗口 $[earliest, latest]$ 保证 $\varepsilon \approx 7$ ms；写事务在 Paxos 组内复制，提交时执行 commit-wait（等到 $latest$ 之后才对外可见），从而给出外部一致性（external consistency = 严格可串行化）：跨洲事务的延迟因此至少是 $\varepsilon$ 量级 + 一个跨洲 RTT。它证明了”强一致可以在全球规模上做到，但要付延迟与专用硬件的钱“。
Apache Cassandra —— 用”每个操作可调”换灵活性：一致性级别 ANY / ONE / QUORUM / LOCAL_QUORUM / EACH_QUORUM / ALL 让客户端对每一次读/写选择强度（Lecture 9）：ONE 得到最终一致与最低延迟，LOCAL_QUORUM 得到”本 DC 内强一致 + 跨 DC 异步”（工程上最常用），ALL 得到最强保证但可用性最差。同一个系统的不同操作可以处在一致性谱的不同位置——这是”旋钮”哲学最成功的产品化。
Azure Cosmos DB —— 把”谱”显式做成 5 档：Strong（线性一致）、Bounded Staleness（有界陈旧，$K$ 个版本或 $T$ 秒）、Session（会话保证，默认级别）、Consistent Prefix（保证读到的更新序列没有”空洞”，即不会先看到第 5 条再看到第 3 条——这是一个介于会话与最终之间的实用保证）、Eventual。它把本章讨论的模型直接做成了产品菜单，并允许不同账户/不同容器选不同档位。

10.5.5 一致性的可扩展性瓶颈从哪里来

强一致的瓶颈是”必须协商”：任何要求”全局唯一顺序/单副本语义”的模型，都要求某些操作经过一个（逻辑上的）公共点——领导者、quorum 交集或共识实例。瓶颈不是带宽，而是延迟（等待最慢副本）与串行化（同一 key 的写不能并行）。因此强一致系统的扩展策略通常是分片：把全序拆成”每个分片内部的全序”（per-key/per-shard sequential），用跨分片事务（2PC/共识）为代价换回全局保证。
弱一致的瓶颈是”元数据与冲突”：最终一致系统写吞吐可以随副本数增长，但每个 key 都要携带版本/时间戳/标签等元数据（Cassandra 的 cell timestamp、Riak 的 dotted version vector、CRDT 的标签集合），反熵修复会消耗后台带宽，而 LWW 的”静默丢更新”是最容易被忽视的正确性风险。
扩展性的经验法则：读多写少 + 可容忍陈旧 ⇒ 最终一致/会话保证；写少但必须准确（余额、库存、配置、元数据、锁）⇒ 线性一致；跨地域协作 + 不能看到因果倒置 ⇒ 因果一致。把这条法则落实到”每个 key、每个操作”的粒度上，就是现代分布式数据库的一致性分级设计。

10.6 关键要点

一致性模型是”系统与应用的契约”，不是实现细节：它规定的是”并发读写之下读允许返回什么”，既不规定协议也不规定硬件；越强的契约越好写代码、越贵（延迟/可用性/吞吐），越弱的契约越快越可用、但把复杂度推给应用。
四条数据为中心的模型构成了一条严格的蕴含链：$\text{Linearizable} \Rightarrow \text{Sequential} \Rightarrow \text{Causal} \Rightarrow \text{FIFO}$；每一步都有真实可构造的反例（H2/H6、H3、H4），“强”意味着”约束边更多”，而约束边正是协调成本的来源。
CAP 的正确表述是”分区期间在 C 与 A 之间取舍”：P 不是可选项，”三选二”是误读；CAP 的 C 是线性一致性，与 ACID 的 C（不违反完整性约束）毫无关系；PACELC 补充了更常见的那一半——无分区时你仍在延迟与一致性之间取舍。
因果一致性是”分区可用”系统的天花板：Attiya 等人的结论表明，在”分区期间可用 + 副本收敛”的约束下，因果一致性是能实现的最强模型；它只传播因果依赖，不需要全局协调。
以客户端为中心的保证（MR/MW/RYW/WFR）是被低估的工程利器：它们只需客户端维护几十字节的版本元数据 + 一次读路由，就能消灭”消息消失”“头像没更新”“回复先于原帖”这类用户直接可见的 bug，而且在 AP 系统上照样可用；四条合起来 ≈ 会话内的因果一致性，并且因果一致性本身并不蕴含单调读。
黄金法则：一致性不是一个布尔属性，而是一个可调旋钮；选哪个取决于你的应用能容忍什么。 用能满足应用正确性的最弱一致性模型（讲义原文：Use the lowest consistency model that is “correct” for your application）——这才拿得到最快的读写与最高的可用性。

10.7 常见陷阱与注意事项

把 CAP 的 C 混同于 ACID 的 C（或最终一致性）
- 为什么错：CAP 的 C 是线性一致性（读返回最近写、单一全序、尊重实时序）；ACID 的 C 是“事务不违反应用定义的不变量”（外键、唯一约束等），与副本和分区无关。用 ACID 的 C 去论证”我们满足 CAP 的 C”是彻底的偷换概念。
- 正确做法：谈 CAP 时明确说”这里的 C 指可线性化/原子一致性”，并用”读是否一定返回最近一次已提交的写”来检验。
相信”CAP 三选二”，或认为可以选择放弃 P
- 为什么错：网络分区（跨 DC 断链、机架交换机故障、DNS 故障）是物理事实，不是设计选项；放弃 P 等于假设网络永不分区，一旦发生分区系统要么行为未定义要么完全不可用。
- 正确做法：把问题重述为”分区期间我要 C 还是要 A“，并且细化到每个操作（读写各自的强度）。
认为用了 $R+W>N$ 就等于拿到了线性一致性
- 为什么错：$R+W>N$ 只保证”读 quorum 与写 quorum 必有交集”，从而读到最近一次已完成写的值；它不自动提供实时序意义上的原子性（例如并发写的定序依赖时间戳，而物理时钟会偏移），并且一旦启用 sloppy quorum / hinted handoff（Lecture 9），写可能落在”非责任副本”上，交集性质被破坏，保证随之失效。
- 正确做法：把 $R+W>N$ 视为”可调强一致“的必要条件而非充分条件；需要真正的线性一致时，用共识（Paxos/Raft）或带版本校验的读修复，并在文档中声明当前配置是否允许 sloppy quorum。
把”最终一致”理解成”很快一致”
- 为什么错：最终一致性只有”最终”这个活性承诺，收敛时间没有任何上界；DNS 的记录可能被缓存数小时，Cassandra 的跨 DC 反熵在分区期间完全停摆。
- 正确做法：需要边界时改用 bounded staleness（$K$ 个版本 / $T$ 秒）或 PBS（概率界），并用监控测量实际的复制延迟分位数（p99），而不是假设。
认为”因果一致性”蕴含”单调读”
- 为什么错：因果一致性约束的是”因果相关的写在所有人眼中同序”，允许并发写在不同进程上顺序不同；因此同一个客户端可以”先读到并发的 $w_2$、后读到并发的 $w_1$”，时间在它看来倒流了（H2 就是这样的历史）。
- 正确做法：把会话保证当作独立的一层显式实现（客户端版本过滤 + 读路由），不要指望底层的数据为中心模型”顺便”给你。
用 LWW + 物理时间戳实现计数器/累加类语义
- 为什么错：LWW 会静默丢弃并发更新（10.4.2 的实验 C 中 $x=99$ 被 $x=77$ 覆盖后永远消失）；时钟偏移还会让”后发的写”拿到更小的时间戳，导致更新被更旧的写覆盖。
- 正确做法：累加用 G-Counter/PN-Counter，集合用 OR-Set，需要”保留冲突供应用决策”时用向量时钟暴露多版本（Dynamo 的 sibling）；只有”最后写的确实应该赢”的语义（用户资料）才用 LWW，并配 HLC 保证时间戳单调。
混淆”线性一致性”与”可串行化（Serializability）”
- 为什么错：可串行化是事务层面的隔离性保证，它只要求”等价于某个串行顺序”，不约束真实时间（一个已提交的读事务可以不看到更早提交的写事务的效果）；线性一致性是单对象层面的实时性保证。
- 正确做法：同时要实时性与事务隔离时，用 严格可串行化（strict serializability）/外部一致性（Spanner、CockroachDB 的默认隔离级别），并清楚它比可串行化更贵。
以为会话粘性（sticky session）就实现了读己之写
- 为什么错：粘性只在副本不变时有效；副本故障切换、负载均衡重试、客户端换网络（4G→WiFi）都会让会话落到另一个副本，此时旧副本仍可能服务读。
- 正确做法：把版本号写进会话 token 并在服务端强制校验（版本不足则回退到足够新的副本或等待），让粘性只是”乐观优化”而不是正确性依赖。

10.8 思考题（带答案）

Q1（计算题｜强一致的可用性代价） 某系统把数据复制到 $N=3$ 个副本，单副本故障概率 $f=0.1$。 (a) 如果读只要求访问本地一个副本，对象可用性是多少？ (b) 如果写要求全部 3 个副本确认（$W=3$），写可用性是多少？ (c) 如果改用 quorum 写（$W=2$），可用性是多少？ (d) 从 (b) 到 (c)，一致性被削弱了什么？给出一个在 $W=2$ 下会被破坏、而在 $W=3$ 下不会的场景。

答案： (a) $1-f^{3} = 1-0.001 = 99.9\%$。 (b) $A_3 = (1-f)^3 = 0.9^3 = 72.9\%$。 (c) $A_2 = \sum_{i=2}^{3}\binom{3}{i}(0.9)^i(0.1)^{3-i} = 3\times0.81\times0.1 + 0.729 = 0.243+0.729 = 97.2\%$。 (d) 从 $W=3$ 到 $W=2$，放弃了”所有副本都有这份写“这一保证，只保留”多数派有“。破坏场景：分区把副本分成 $\{R_0\}$ 与 $\{R_1,R_2\}$ 两侧。$W=2$ 时多数派侧仍可接受写并成功返回，此时若客户端去少数派侧的 $R_0$ 读（配 $R=1$ 的读、或用 LOCAL_QUORUM 之外的弱读），就会读到旧值——这正是 10.4.2 实验 B 中 quorum 一行的现象；而 $W=3$ 时多数派侧根本无法提交写（写会超时失败），因此不会出现”已经成功返回、随后又读到旧值”的情形（代价是可用性从 97.2% 掉到 72.9%）。注意：只要读也用 $R\ge2$（$R+W>N$），多数派侧的读仍然是”最近一次成功写”的值，因为少数派侧的写从未成功过。

Q2（推演题｜给出历史、判断模型） 判断下列历史满足哪些模型：$P_1$ 写 $x=1$；$P_2$ 读到 $x=1$ 后写 $y=1$；$P_3$ 读到 $y=1$，随后读 $x$ 得到 $0$（初值）。

答案：

违反因果一致性：$P_2$ 的 $W(y,1)$ 依赖于它读到的 $x=1$，因此 $W(x,1) \to W(y,1)$。因果一致性要求”看到果必看到因”——$P_3$ 看到了 $y=1$ 就必须已经看到 $x=1$，从而它的 $R(x)$ 必须返回 1，而实际返回 0。用检查器的语言：$P_3$ 的视图若含 $W(y,1)$，则因向下封闭必须含 $W(x,1)$，此时 $R(x)$ 只能是 1，矛盾；若视图不含 $W(x,1)$，则无法解释 $R(y)=1$。无解 ⇒ 违反。
违反顺序一致性（若因果一致性不满足，则更强的模型必然也不满足，由定理 10.2）。可直接验证：任何全序要同时满足 $W(x,1) < R_2(x){=}1 < W(y,1) < R_3(y){=}1 < R_3(x){=}0$（程序序与读规则），但 $R_3(x){=}0$ 要求 $W(x,1)$ 排在它之后——与链首矛盾。
满足 FIFO/PRAM 一致性：FIFO 只要求”同一写者的写按序被看到”。$P_1$ 只有一个写、$P_2$ 只有一个写，不存在同一写者的两个写，因此没有约束；$P_3$ 的读按程序序（先 $y$ 后 $x$）、且读返回视图中该 key 的最近写（视图可以取 $\{W(y,1)\}$，$x$ 上无写 ⇒ 返回初值 0）合法。这正是检查器 H4 的判定结果（FIFO ✓，因果 ✗），也是”FIFO 一致性很便宜但很弱”的直观例证。

Q3（直觉陷阱题｜”我们用了 quorum，所以是强一致的”） 团队声称：”我们的 KV 存储写用 $W=2$、读用 $R=2$，$N=3$，$R+W>N$，所以我们是线性一致的。”这个推理错在哪？

答案：至少有三处漏洞。

交集只保证”读到最近一次成功写”，不保证实时序下的原子性：两个并发写的定序通常靠时间戳（LWW），而物理时钟有偏移（Lecture 12），因此”哪个写更晚”的判定可能违背真实时间序；线性一致性要求存在一个同时满足实时序的全序。
sloppy quorum / hinted handoff 会破坏交集性质：Cassandra 在责任副本不可达时会把写交给别的节点并暂存（Lecture 9），此时”写 quorum”与”读 quorum”未必有交集，$R+W>N$ 的形式条件不再成立——工程上必须显式关闭它（或把 ANY 从写路径移除）才能谈强一致。
读修复是后台异步的：协调者先返回给客户端、再在后台修复其余副本；如果客户端随后去读一个尚未修复的副本（且读级别低），仍会读到旧值。此外，若写路径本身是异步的（”Just write and return”），写返回时数据甚至还没到 $W$ 个副本。 正确表述：这套配置提供的是”可调强一致“——在给定 quorum 组合、禁用 sloppy quorum、且读返回最新时间戳版本的条件下，能保证”读到最近一次成功写”；要宣称线性一致性，需要共识（Paxos/Raft）或附加的实时序保证。

Q4（设计题｜多设备购物车与用户资料） 一个电商 App 有：(a) 用户资料（头像、昵称）；(b) 购物车（可加可删）；(c) 库存扣减；(d) 商品浏览计数。请为每一项选择合适的一致性模型与实现，并说明理由。

答案：

(a) 用户资料：需要读己之写（改完头像立刻能看到）+ 单调读（不能刷新后又变回旧头像）。多设备并发改名用 LWW + HLC 时间戳 即可（语义上”最后改的赢”是用户能接受的），上层的”用户资料”用 LWW-Register CRDT 实现跨副本收敛。成本：客户端保存版本号，读时路由到足够新的副本。
(b) 购物车：必须不丢任何一次”加”，并发”加/删”要有一致语义 ⇒ 用 OR-Set CRDT（add-wins）：设备 A 加商品、设备 B 同时删同一商品，合并后商品存在（宁可多留不可错删）；配合读己之写 + 单调读让用户不困惑。绝不能只上 LWW 覆盖整个购物车（会丢掉另一台设备的添加）。
(c) 库存扣减：必须不能超卖，这是不可交换的业务约束 ⇒ 必须用线性一致的协调：单 key 用共识（Raft/Paxos）做条件更新（”当库存 ≥ 1 时减 1”，即 CAS/事务），或先用 Redis/etcd 做分布式锁 + 幂等扣减，再异步落库。跨分片/跨服务时用 2PC 或 Saga（Lecture 20、22）。这里的”强一致”绝不能省。
(d) 商品浏览计数：只需 最终一致（甚至允许分钟级陈旧）⇒ G-Counter CRDT 或 Cassandra ONE 写 + 定期聚合，牺牲实时性换取吞吐。用一个 LWW 整数去 +1 是典型错误（并发加会丢）。总结：同一套系统里四项用了四种不同强度的一致性——这正是”一致性是可调旋钮、按操作选择“的实践样板。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li

第五部分：时间、一致性与全局状态

Lecture 10: Consistency Models — 一致性模型

10.1 概述

10.2 核心概念与分布式机制图解

10.2.1 复制的根本矛盾与”契约”观（The Contract View）

10.2.2 两种视角：数据为中心 vs 以客户端为中心

10.2.3 形式化框架：历史、实时序、程序序与”最近一次写”

10.2.4 严格一致性 / 线性一致性（Strict Consistency / Linearizability / Atomic Consistency）

10.2.5 顺序一致性（Sequential Consistency）

10.2.6 因果一致性（Causal Consistency）

10.2.7 FIFO 一致性（FIFO Consistency / PRAM Consistency）

10.2.8 弱一致性（Weak Consistency）

10.2.9 最终一致性（Eventual Consistency）

10.2.10 CRDT：让冲突在设计上不存在（Conflict-free Replicated Data Types）

10.2.11 以客户端为中心的模型总览：会话保证（Session Guarantees）

10.2.12 单调读（Monotonic Reads, MR）

10.2.13 单调写（Monotonic Writes, MW）

10.2.14 读己之写（Read Your Writes, RYW / Read My Writes, RMW）

10.2.15 写跟随读（Writes Follow Reads, WFR）

10.2.16 四条保证的组合、实现方案与它和因果一致性的关系

10.2.17 CAP 定理（CAP Theorem）与 PACELC

10.2.18 一致性模型的层次结构（Lattice）与实现机制映射

10.2.19 更新的模型，以及”一致性是一个旋钮”

10.3 算法伪代码与正确性分析

算法 10.3.1：一致性历史判定器（History Checking / Model Checking）

算法 10.3.2：以客户端为中心一致性的会话状态机（Session State Machine）

算法 10.3.3：CAP 不可能性证明（作为分析性”伪代码”/形式化论证）

算法 10.3.4：CRDT 的收敛性论证（以 G-Counter 与 OR-Set 为例）

10.3.5 四种数据为中心模型的蕴含关系：证明链与反例

10.4 代码示例与分布式实现

代码 10.4.1：一致性模型检查器（History Checker）

代码 10.4.2：强一致 vs quorum vs 最终一致——把 CAP 跑出来

代码 10.4.3：以客户端为中心的一致性——会话元数据的力量

10.5 性能与可扩展性分析

10.5.1 延迟与吞吐：一致性强度的价格标签

10.5.2 可用性：强一致到底牺牲了多少？

10.5.3 分区下的行为对照

10.5.4 实现复杂度与真实系统中的落地方式

10.5.5 一致性的可扩展性瓶颈从哪里来

10.6 关键要点

10.7 常见陷阱与注意事项

10.8 思考题（带答案）

Share on