Lecture 9: Key-Value Stores and NoSQL — Cassandra 与最终一致性
Lecture 9: Key-Value Stores and NoSQL — Cassandra 与最终一致性
讲义对应：CS 425 FA2026 Lecture 9。本章合并课程 Lecture 9-11「Key-Value/NoSQL Stores」 的全部 Key-Value/NoSQL 内容（原始讲义
L9-11.FA25.pdf，共 88 页：键值抽象、RDBMS 对比、CAP、Cassandra 全貌、quorum 与一致性级别、HBase、MongoDB）；其中集群成员管理与故障检测（gossip、Φ 累加故障检测器）部分对应 Lecture 6「Failure Detection and Membership」（L6.FA25.pdf）。 教材对应：Coulouris 5th Ed. Ch. 2（系统模型）、Ch. 10（Peer-to-Peer 系统，DHT）、Ch. 14（时间与全局状态）、Ch. 18（复制）；补充阅读：Amazon Dynamo（SOSP 2007）、Cassandra（Lakshman & Malik, 2010）、Brewer 的 CAP 猜想（2000）、Gilbert & Lynch 的 CAP 形式化证明（2002）。 阅读材料：Dynamo 论文（Cassandra 的直接思想来源）、Cassandra 论文、Bigtable 论文（可选）。
9.1 概述
本章回答一个贯穿整个分布式系统课程的核心问题：当数据大到一台机器装不下、请求多到一个节点扛不住、而机器又必然故障时，我们该如何存储和读取数据？ 传统关系数据库（RDBMS）用 ACID 事务和 SQL 把这件事做得极其漂亮，但它的强一致性与单点写入模型在”跨地理分布 + 高可用 + 线性扩展”的负载下代价高昂。于是出现了一类新的系统：键值存储 / NoSQL，它们用 get(key) / put(key, value) 这样极简的接口、用分片（sharding）+ 多副本（replication）换取水平扩展，用最终一致性（eventual consistency）换取永远可写、快速响应。本章以 Apache Cassandra 为主线解剖这类系统的每一项机制：环状分区（DHT + vnodes）、复制策略、可调一致性（tunable consistency）与 $R+W>N$ quorum 条件、提示移交（hinted handoff）、读修复（read repair）、Merkle Tree 反熵修复（anti-entropy repair）、gossip 成员管理与 Φ 累加故障检测器，以及 LSM-Tree 风格的写路径 / 读路径（CommitLog → Memtable → SSTable，Bloom Filter、Compaction、Tombstone），最后横向对比 HBase、Bigtable、MongoDB、Redis、DynamoDB/Riak。
本章在整门课中处于”复制与一致性“这一支柱的核心位置：它向前承接 Lecture 5 的 RPC/间接通信与 Lecture 8 的 DHT/Chord（Cassandra 的环就是没有 finger table 的 Chord），向后为 Lecture 12 的向量时钟与冲突解决、Lecture 15 的因果一致性、Lecture 19 的共识（Paxos/Raft）、Lecture 26 的时钟同步埋下伏笔。一句话概括本章的黄金洞见：
Cassandra 用最终一致性换来了极高的可用性与线性可扩展的写吞吐；当应用真的需要强一致时，用 $R+W>N$ 把它”调”回来。一致性与可用性不是一个固定的属性，而是一个可以按操作拧动的旋钮。
9.2 核心概念与分布式机制图解
9.2.1 从关系数据库到 NoSQL：能力与错配
定义与目的：关系数据库管理系统（Relational Database Management System, RDBMS）把数据组织成表（table），表有固定的模式（schema），每行有一个在该表内唯一的主键（primary key），用 SQL（Structured Query Language） 查询，支持连接（join）与外键（foreign key）。MySQL 是其中最流行的一个。
直观解释（”它是什么？”）：RDBMS 像一家管理严格的图书馆——每本书必须登记到固定的字段（书名、作者、ISBN），索引卡片保证你能按任意字段快速找到书，还能方便地做”把所有借过 A 书的读者借过的 B 书列出来”这种关联查询（join）。它的规范化（normalization）设计哲学是：每份事实只存一份，通过外键引用避免冗余，因此更新一处即可全局一致——这正是 ACID 事务最擅长的场景。
机制图解：讲义给出的两张经典表与三条查询。
users 表（主键 user_id） blog 表（主键 blog_id）
┌─────────┬─────────┬─────────┬──────────────────┐ ┌─────────┬──────────────────┬──────────────┬───────────┐
│ user_id │ name │ zipcode │ blog_url │ │ blog_id │ url │ last_updated │ num_posts │
├─────────┼─────────┼─────────┼──────────────────┤ ├─────────┼──────────────────┼──────────────┼───────────┤
│ 101 │ Alice │ 12345 │ alice.net │ │ 1 │ alice.net │ 5/2/14 │ 332 │
│ 422 │ Charlie │ 45783 │ charlie.com │ │ 2 │ bob.blogspot.com │ 4/2/13 │ 10003 │
│ 555 │ Bob │ 99910 │ bob.blogspot.com │ │ 3 │ charlie.com │ 6/15/14 │ 7 │
└─────────┴─────────┴─────────┴──────────────────┘ └─────────┴──────────────────┴──────────────┴───────────┘
▲ 主键 user_id ▲ 主键 blog_id
▲ url 被 users.blog_url 引用（外键）
SQL 查询示例：
① SELECT zipcode FROM users WHERE name = "Bob"
② SELECT url FROM blog WHERE id = 3
③ SELECT users.zipcode, blog.num_posts
FROM users JOIN blog ON users.blog_url = blog.url ← 跨表连接（join）
RDBMS 的强项：原子性事务、ACID、成熟的 SQL 优化器、丰富的二级索引、外键约束下的参照完整性、几十年的运维与人才积累。
与今天负载的错配：讲义列举了现代 Web/云负载的特征——
| 今天负载的特征 | 对 RDBMS 造成的压力 |
|---|---|
| 数据巨大且非结构化（日志、推文、传感器、视频元数据） | 严格 schema 与规范化带来沉重的迁移与 join 成本 |
| 大量随机读和随机写 | B+ 树在磁盘上做随机 IO，单机吞吐受寻道时间限制 |
| 有时写密集（write-heavy） | 单主写入 + 事务日志两阶段提交成为瓶颈 |
| 极少需要外键 | 参照完整性检查变成纯开销 |
| join 不常用 | 优化器与分布式 join 的复杂度用不上 |
现代负载真正的诉求（讲义原话）：Speed（速度）、避免单点故障（SPoF, Single Point of Failure）、低 TCO（Total Cost of Operation/Ownership，总拥有/运营成本）、更少系统管理员、增量可扩展性（incremental scalability）——即 scale out, not scale up。
关键假设与系统模型：RDBMS 隐含的模型是单机（或单主） + 强一致 + 可假设机器基本不坏。本章要替换的正是这三点：我们假设有成千上万台 COTS（Components Off The Shelf，商用现货）机器，故障是常态而不是例外（Lecture 6 的算例：单机 10 年一坏，120 台机器时平均 1 个月坏一台，12000 台时约 7.2 小时就有一台坏），且网络随时可能分区。
9.2.2 纵向扩展 vs 横向扩展（Scale Up vs Scale Out）
定义与目的：Scale up（纵向扩展）= 用更强的机器替换现有机器来提升集群容量；Scale out（横向扩展）= 通过增加更多普通机器来增量地提升容量。
直观解释（”它是什么？”）：Scale up 像把一辆小货车换成一辆更大的卡车——单次运力提升了，但价格曲线在”甜点（sweet spot）”之上急剧上扬，而且你还得频繁地整车替换。Scale out 像组建一支车队：每辆都是便宜的标配车，坏一辆不影响运输，需要更多运力就再买一辆；长期来看还能”一边淘汰几辆旧车、一边补充几辆新车（phase in newer, phase out older）”，硬件始终停留在性价比最优的区间。今天几乎所有自建数据中心与云厂商都走这条路。
机制图解：
Scale Up（纵向扩展，传统做法） Scale Out（横向扩展，云时代做法）
┌────────────────────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐
│ $$$$ 超级服务器 │ │COTS│ │COTS│ │COTS│ │COTS│
│ 32 cores / 1 TB RAM│ └────┘ └────┘ └────┘ └────┘
│ 单一故障域 → SPoF │ +1 台机器 = +1 份容量（近似线性）
└────────────────────┘
容量 ↑ 但价格曲线越过甜点，不划算 任意一台坏掉 → 其余继续服务
换机器 = 停机 + 全量迁移 可一边淘汰旧机、一边补入新机
仍是单点故障（SPoF） 软件必须支持分区 + 复制才可行
- 关键假设与系统模型：Scale out 的可行性前提是软件必须无状态或可分区：请求可以被任意节点处理、数据可以被切分并复制到多台机器。这正是分布式存储系统（DHT、键值存储、GFS/HDFS）存在的理由。代价是：一致性维护、成员管理、数据再平衡（rebalance）全部变成软件问题。
9.2.3 CAP 定理（CAP Theorem）
定义与目的：CAP 定理由 Eric Brewer（Berkeley） 提出，随后由 Gilbert 与 Lynch（NUS / MIT） 形式化证明。它指出：在一个分布式系统中，下面三条保证最多只能同时满足两条：
- 一致性（Consistency, C）：所有节点在任何时刻看到相同的数据，或者说读操作返回任意客户端最近一次写入的值；
- 可用性（Availability, A）：系统在任何时刻都允许操作，且操作能快速地返回（形式化版本：每个到达未故障节点的请求都必须在有限时间内返回一个响应）；
- 分区容忍性（Partition tolerance, P）：系统在发生网络分区时仍能继续工作。
- 直观解释（”它是什么？”）：把 CAP 想成一家在两个城市都有分店的银行，某天两城之间的电话线断了（分区）。这时储户 A 在城市 1 存了 100 元。此时城市 2 的柜员面对一笔”查询余额”的请求，只有两个选择：
- 拒绝服务（”今天跨行系统故障，请稍后再来”）→ 你保住了一致性，牺牲了可用性（这是 CP）；
- 照常服务，用本地可能已经过时的账本回答”余额还是老数字”→ 你保住了可用性，牺牲了一致性（这是 AP）。
你不可能既让城市 2 给出正确答案、又让它在完全不知道城市 1 发生了什么事的情况下继续服务。这就是 CAP 的全部直觉。
- 机制图解：
C（一致性）
/\
/ \
/ CA \ ← 只在"网络永不分区"的理想世界成立
/ 单机 \
/ RDBMS \
/__________\
/\ /\
/ \ / \
/ CP \ / AP \
/______\ /______\
P A
（分区容忍） （可用性）
┌────────────────────────────────────────────────────────────────────────┐
│ CP 阵营：HBase、Bigtable、Spanner、ZooKeeper、HyperTable │
│ 分区时宁可让部分请求失败/阻塞，也绝不给陈旧数据 │
│ AP 阵营：Cassandra、Dynamo、Riak、Voldemort │
│ 分区时两边各自继续服务，接受短期不一致，事后收敛 │
│ CA 阵营：单机（不复制）的 RDBMS —— 一旦真正跨网络复制，它就退化为 CP │
└────────────────────────────────────────────────────────────────────────┘
为什么 P（分区容忍）不是可选项？ 这是初学者最容易误解的一点。CAP 里的 P 不是”你要不要支持分区”这种产品特性，而是你对网络所做的假设：P 表示”网络可能任意丢弃节点之间的消息”。要”放弃 P”，你必须在设计里假设网络永不分区（同步、可靠、有界延迟）——而这在工程上是不成立的：
- 跨数据中心的分区必然发生：互联网断连、路由器故障、海底光缆被切断、DNS 不工作；
- 数据中心内部同样会分区：机架交换机（rack switch）故障会把一个机架与其他机架隔开；
- 更微妙的是，一个被 GC 停顿（stop-the-world）或长时间调度饥饿的进程，在其它节点眼中与”分区”完全等价——它收不到消息、也不回消息。你无法通过”买更好的网络”来消灭这一类事件，只能选择如何应对它。
因此真正可选的只有 C 与 A：当分区真的发生时，系统是拒绝一部分请求（保 C）、还是继续服务并可能返回陈旧数据（保 A）。讲义由此得出结论：”因为分区容忍在今天的云计算系统中是必需的，CAP 定理就意味着系统必须在一致性与可用性之间做选择。”
重要的细化（补充说明）：CAP 的取舍只在分区发生期间生效。没有分区时，C 和 A 可以同时拥有——这正是 Cassandra 用”可调一致性”把旋钮交给应用的理论依据。业界常补充一条 PACELC：如果发生 P，则在 A 与 C 之间选；否则（Else）在 L（延迟）与 C 之间选——因为即使没有分区，跨副本同步复制也会引入延迟。Brewer 本人在 2012 年也强调：分区其实很少见，因此把 C/A 的选择细化到每个操作（而不是整系统一刀切）才是最有价值的工程实践，Cassandra 的一致性级别正是这一思想的产物。
为什么可用性如此重要（讲义数据）：可用性 = 读写可靠且快速地完成。测量显示，Amazon.com 或 Google.com 上500 ms 的延迟增加可导致 20% 的收入下降；较新的测量是 Amazon 每 100 ms → 销售额降 1%，Akamai 每 100 ms → 降 7%；在 Amazon，每多 1 ms 延迟意味着每年 600 万美元的损失（更新的说法：1 秒 ≈ 16 亿美元）。还有”用户认知漂移（cognitive drift）“：点击后超过 1 秒才有响应，用户的注意力早就飘走了。服务商写下的 SLA（Service Level Agreement） 主要约束的正是客户端感受到的延迟。
为什么一致性重要（讲义数据）：一致性 = 所有节点在任何时刻看到相同数据，或读返回任意客户端最近写入的值。当你用笔记本、工作站、手机、平板同时访问银行或投资账户时，你希望一个客户端上的更新立刻能被其他客户端看到；当数千名顾客同时抢订机票时，任何客户端的更新（比如”订走了一张票”）都应该对其他客户端可见。
关键假设与系统模型：Gilbert–Lynch 证明所采用（并被普遍引用）的定义是：C 是原子一致性 / 线性一致性（atomic / linearizable consistency），A 是每个未故障节点收到的请求都在有限时间内返回响应，P 是网络可以任意丢弃节点间的消息。证明思路极简：设分区把节点分成 $\{G_1, G_2\}$，客户端向 $G_1$ 写入 $v_1$，另一客户端向 $G_2$ 读同一 key。若系统满足 A，则 $G_2$ 的读必须在有限时间内返回；但在异步网络中 $G_2$ 无法区分”$G_1$ 已停机”与”消息被分区阻隔”，因此它不可能知道 $v_1$ 的存在，只能返回旧值 $v_0 \ne v_1$，这违反 C。故 A 与 C 在分区期间不可兼得。$\blacksquare$
补充说明（Cassandra 的定位）：讲义明确把 Cassandra 归入 AP：最终（弱）一致性 + 可用性 + 分区容忍；把传统 RDBMS 归入”分区时选强一致性而放弃可用性”。
9.2.4 BASE 模型与 ACID 的对比
定义与目的：传统 RDBMS 提供 ACID；键值存储（如 Cassandra）提供 BASE：Basically Available（基本可用）、Soft state（软状态）、Eventual consistency（最终一致性）。BASE 的本质是”偏好可用性胜过一致性“。
直观解释（”它是什么？”）：ACID 像银行转账——要么钱从 A 扣了同时加到 B，要么什么都不发生，全世界任何时刻查账看到的都是同一个已提交状态。BASE 像社交网络的点赞数——你在北京看到 100 个赞，朋友在上海可能看到 99 个，但几秒后大家都会看到同一个数字；在此期间，系统从不拒绝任何一次点赞。
机制图解：
ACID（RDBMS） BASE（Cassandra 等）
────────────────────────────────────── ──────────────────────────────────────
A 原子性 Atomicity Basically Available
事务要么全做要么全不做 系统基本总是可读写（分区时两边都继续服务）
C 一致性 Consistency Soft state
事务把 DB 从一个一致状态带到另一个 状态可以"软"：副本之间暂时可以不一致，
I 隔离性 Isolation 不需要外部输入也会自己演进（收敛）
并发事务互不干扰 Eventual consistency
D 持久性 Durability 若对一个 key 的写停止，则所有副本
提交后即使宕机也不丢 最终会收敛到相同的值
│ │
▼ ▼
分区时：宁可拒绝服务，也不返回陈旧数据 分区时：两边都继续服务，接受短期不一致
→ CP → AP
最终一致性（Eventual Consistency）的精确含义：若对一个 key 的所有写都停止，则该 key 的所有副本的值最终会收敛（converge）。若写持续不断，系统会一直努力追赶；可以想象成一道”移动的波（moving wave）”：已更新的值像波浪一样滞后于客户端发来的最新值，但始终在追赶。它仍可能向客户端返回陈旧值（例如同一 key 上背靠背的大量写）；但在写有间歇的场景下，系统能很快收敛。
哪些机制帮助了收敛（讲义思考题）：本章后面将详细展开的 提示移交（hinted handoff）、读修复（read repair）、反熵修复（anti-entropy repair，Merkle Tree） 三者，正是 Cassandra 从”总是可写”走向”最终收敛”的三条腿。
关键假设与系统模型：BASE 假设冲突可被自动解决（Cassandra 用时间戳 last-write-wins），因此它不需要共识协议、不需要 leader，可以在任意网络条件下保持可用。代价是：并发写可能静默丢失（详见 9.3.3），且没有跨 key 事务（Cassandra 后来加入的轻量级事务 LWT 是基于 Paxos 的例外，性能代价高，属补充说明）。
9.2.5 NoSQL 的分类与代表系统
定义与目的：NoSQL = “Not Only SQL”——不是”不要 SQL”，而是”不只是 SQL”。它的最小接口是
get(key)与put(key, value)；在此之上扩展出各自的数据模型与查询语言（例如 Cassandra 的 CQL）。直观解释（”它是什么？”）：NoSQL 不是一个具体系统，而是一类为了水平扩展与高可用而放弃部分关系代数能力的数据存储。选型时可以问自己三个问题：(1) 我主要按 key 查，还是要做复杂关联？(2) 我的数据形态是标量、宽行、文档还是点边关系？(3) 我能接受最终一致吗？答案决定你落在下表哪一格。
机制图解与对比表：
┌──────────────────┬────────────────────────────────┬────────────────────────────────┬────────────────────────────────────┐
│ 分类 │ 数据模型 │ 代表系统 │ 擅长场景 │
├──────────────────┼────────────────────────────────┼────────────────────────────────┼────────────────────────────────────┤
│ 键值 Key-Value │ key → 不透明的 value │ Redis、Dynamo、Riak、Voldemort │ 会话、缓存、购物车、计数器 │
│ 列族 Wide-Column │ row → 多个 (column, value) │ Cassandra、HBase、Bigtable │ 写密集的大规模 OLTP、时序、消息 │
│ 文档 Document │ key → 半结构化文档 (JSON/BSON) │ MongoDB、CouchDB │ 内容管理、目录、快速迭代的产品数据 │
│ 图 Graph │ 节点 + 边 + 属性 │ Neo4j、JanusGraph │ 社交关系、推荐、知识图谱、反欺诈 │
└──────────────────┴────────────────────────────────┴────────────────────────────────┴────────────────────────────────────┘
| 分类 | 数据模型 | 代表系统 | 典型查询 | 擅长场景 |
|---|---|---|---|---|
| 键值（Key-Value） | key → opaque value | Redis、Dynamo、Riak、Voldemort、Memcached | GET/PUT/DEL | 会话、缓存、购物车、计数器 |
| 列族/宽列（Column-Family / Wide-Column） | (row key, column) → value，行内列可稀疏、按列簇组织 | Cassandra、HBase、Bigtable、HyperTable | 按行键取行、按列范围扫描 | 时序数据、消息、写密集的大规模 OLTP |
| 文档（Document） | key → 半结构化文档（BSON/JSON） | MongoDB、CouchDB | 按文档内字段查询/更新/聚合 | 内容管理、目录、快速迭代的产品数据 |
| 图（Graph） | 节点 + 边 + 属性 | Neo4j、JanusGraph | 多跳遍历、最短路径 | 社交关系、推荐、知识图谱、反欺诈 |
- 键值/NoSQL 的”表”与 RDBMS 的”表”的差别（讲义原文的对照）：NotSQL 里也叫表，但叫法不同——Cassandra 叫 “column family”（列族），HBase 叫 “table”，MongoDB 叫 “collection”（集合）。它们像 RDBMS 的表，但：
- 可以没有模式（schema-less）：数据可以是非结构化的；
- 某些列在某些行里可以缺失（稀疏）；
- 不总是支持 join，也没有外键；
- 可以像 RDBMS 一样拥有索引表。
RDBMS 的表（严格 schema） NoSQL 的表（无 schema / 稀疏）
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
│ user_id │ name │ zipcode │ │ user_id │ name │ zipcode │
├─────────┼─────────┼─────────┤ ├─────────┼─────────┼─────────┤
│ 101 │ Alice │ 12345 │ │ 101 │ Alice │ 12345 │
│ 422 │ Charlie │ 45783 │ │ 422 │ Charlie │ ✗ 缺列 │
│ 555 │ Bob │ 99910 │ │ 555 │ ✗ 缺列 │ 99910 │
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
缺列必须写 NULL（占空间，NULL 有语义） 缺列 = 该行没有这一列（不占空间）
✗ 在 NoSQL 中“不存在”是常态，不是异常
- 列式存储（Column-Oriented Storage）：讲义特别指出 NoSQL 系统常用列式存储。RDBMS 把一整行存在一起（磁盘上或同一台服务器上）；NoSQL 系统通常把一列（或一组列）存在一起。列内的条目被索引，给定 key 就能（双向地）快速定位。为什么有用？ 列内的范围搜索很快，因为你不需要取回整个数据库。讲义的例子：要查”过去一个月内更新过的所有 blog_id”，只需在
last_updated列里搜索，再取出对应的blog_id列——完全不用碰其它列。
行式（RDBMS）: [101,Alice,12345,alice.net][422,Charlie,45783,...][555,Bob,...]
↑ 查 num_posts 也要把整行读进内存
列式（NoSQL）: last_updated: [5/2/14 | 4/2/13 | 6/15/14] ← 只扫这一条就能筛出结果
blog_id : [ 1 | 2 | 3 ] ← 只取这一列的值
url : [ ... | ... | ... ] ← 不读
- 关键假设与系统模型：NoSQL 的模型假设查询模式先于数据模型被确定（access-pattern-driven design），并且接受冗余存储以换取读取时的局部性——这正是下一节的反范式化。
9.2.6 反范式化与查询驱动的数据建模
定义与目的：反范式化（denormalization）指有意地复制数据、放弃第三范式，使得每次查询只需访问单个分区（单台机器的单次顺序读），而不需要跨节点的 join。查询驱动的数据建模（query-driven modeling）是它的方法论：在 Cassandra 里，先写下你要执行的所有查询，再据此设计表——这与 RDBMS”先建规范化的实体模型、再写任意查询”的顺序正好相反。
直观解释（”它是什么？”）：RDBMS 建模像把图书馆按主题分区、互相引用；NoSQL 建模像给每个部门各印一份只包含它需要的章节的定制装订本。同一份事实可能在很多本装订本里重复；代价是更新时要更新所有副本（写放大、需要靠物化视图或应用层双写维护），收益是读取永远是一次本地查找。
机制图解：
┌───────────────────────────────────────────────────────────────────┐
│ 写入时：应用（或物化视图 / BATCH 日志）必须把多份冗余副本都写一致 │
│ 读取时：任意一个查询都只命中一个分区 → 单个节点上的一次顺序读 │
└───────────────────────────────────────────────────────────────────┘
关键假设与系统模型：反范式化把复杂度从读路径搬到了写路径，并要求应用接受”最终一致的冗余副本“：如果两份冗余副本的更新之间发生故障，它们会短暂（或永久，若无修复机制）不一致。因此批量写入应尽量落到同一分区（Cassandra 的
BATCH保证同一分区内的原子性），跨分区的原子性则不做保证。Cassandra 与 RDBMS 的性能对比（讲义实测数据，数据量 > 50 GB）：
| 系统 | 平均写延迟 | 平均读延迟 |
|---|---|---|
| MySQL | 300 ms | 350 ms |
| Cassandra | 0.12 ms | 15 ms |
写快了约 2500 倍，读快了约 23 倍。讲义随即抛出一个关键提问：”代价是什么？我们失去了什么？“——答案就是下一节开始反复出现的 CAP 定理与最终一致性。
9.2.7 Cassandra 数据模型：Keyspace → Column Family → Row → Column（含时间戳）
- 定义与目的：Cassandra 是一个分布式键值存储（distributed key-value store），最初由 Facebook 设计，后开源并成为 Apache 项目；它面向数据中心内部（也跨数据中心）运行。生产环境使用者包括 IBM、Adobe、HP、eBay、Ericsson、Symantec、Twitter、Spotify、PBS Kids，以及 Netflix（用 Cassandra 记录你正在看的视频的播放位置）。它的数据模型是四层嵌套：
Keyspace（键空间） ≈ RDBMS 的 database/schema：绑定复制策略、副本因子等
└── Column Family / Table ≈ RDBMS 的 table（CQL3 起直接叫 table）
└── Row（由 row key / partition key 唯一标识）
└── Column（name, value, timestamp [, TTL]）
直观解释（”它是什么？”）：把 keyspace 想成一栋大楼，column family 是楼里的档案柜，row key 是抽屉编号，而抽屉里放的不是格式统一的表格，而是一叠便利贴：每张便利贴上写着”字段名 → 值 → 写这张纸条的时刻”。哪个抽屉里有哪些字段完全自由——这就是稀疏。RDBMS 的抽屉里是一张印刷好的表格，所有抽屉的栏目必须一样，没有内容的格子也得空着（写 NULL）。
机制图解（列族结构：多行、稀疏列、每列带时间戳）：
Keyspace: myapp replication = NetworkTopologyStrategy, RF = 3
└── Column Family / Table: users PRIMARY KEY (user_id, ts)
partition key = user_id
clustering key = ts
┌──────────────────┬────────────────┬─────────────────────────────────────────────────────────┬────────────────────────────┬────────────────────────────────────────┐
│ partition key │ clustering key │ name │ zipcode │ blog_url │
│ (决定落哪个节点) │ (决定行内排序) │ 每列 = (name, value, timestamp) │ │ │
├──────────────────┼────────────────┼─────────────────────────────────────────────────────────┼────────────────────────────┼────────────────────────────────────────┤
│ user_id = 101 │ ts=2026-01-01 │ ("name","Alice",t=1005) │ ("zipcode","12345",t=1002) │ ("blog_url","alice.net",t=1001) │
│ user_id = 101 │ ts=2026-02-11 │ ("name","Alice L.",t=1099) │ ✗ 本行没有这一列 │ ("blog_url","alice.net",t=1098) │
│ user_id = 422 │ ts=2026-01-03 │ ("name","Charlie",t=1070) │ ("zipcode","45783",t=1069) │ ✗ 本行没有这一列 │
│ user_id = 555 │ ts=2026-01-07 │ ("name","Bob",t=1088) + ("phone","217-555-0100",t=1300) │ ("zipcode","99910",t=1201) │ ("blog_url","bob.blogspot.com",t=1201) │
└──────────────────┴────────────────┴─────────────────────────────────────────────────────────┴────────────────────────────┴────────────────────────────────────────┘
同一 partition key 的多行 = 同一分区（同一台机器上），按 clustering key 排序存放
稀疏性：user_id=101 的两行都有 name；422 行没有 blog_url；555 行额外多出 phone 列。
不存在的列不占空间、也不是 NULL —— 这是与 RDBMS 固定模式表的关键区别。
一个列（更准确地说是单元 cell）的内部结构：
┌─────────────┬──────────────┬───────────────────────┬─────┐
│ column name │ column value │ write timestamp │ TTL │
├─────────────┼──────────────┼───────────────────────┼─────┤
│ "zipcode" │ "99910" │ 1735689600123456 (µs) │ 无 │
└─────────────┴──────────────┴───────────────────────┴─────┘
稀疏性（Sparsity）是本质区别：在 RDBMS 中，表的每一行都有相同的列集合，缺失列写
NULL；在 Cassandra 中，每一行可以有完全不同的列集合，不存在的列不占空间、也不是 NULL。这使得”给表加一个列”是零成本的，也使得同一个表能为形状各异的数据服务。Cassandra 的行在磁盘上表现为一串(clustering key, column, value, timestamp)，行与行之间长度可以差异极大。- Super Column（超列，Cassandra 1.x 的旧概念）：早期 Cassandra（0.6/1.x）允许一种值是”列的有序映射”的列，称为 super column：
SuperColumn name → { sub-column name → value }。它被用来表达”一行里再嵌套一层”的结构（例如给每个用户存多个”标签→值”）。它为什么被废弃（补充说明，讲义未展开）：- 无法部分读取：读一个子列必须先把整个 super column 反序列化到内存——一个 super column 内所有子列被强制绑在一起，无法按子列做局部读写；
- 热点：同一 super column 的全部子列必须落在同一个节点、同一个分区，写压力无法分散——这直接违背了分区是为了打散负载的初衷；
- 不支持二级索引与逐子列 TTL，且与后来的 CQL 关系模型冲突；
- 取而代之的是 composite column（复合列）：把多个组件拼成一个列名，从而在不嵌套的情况下表达同样的层次，同时保留了稀疏性与分区能力。super column 在 Cassandra 1.2 起被弃用，3.0 中彻底移除。今天的 Cassandra 里没有 super column，遇到它的唯一场景是阅读老资料。
- 分区键 vs 聚簇键（Partition Key vs Clustering Key）：这是 Cassandra 数据模型最重要的区分：
PRIMARY KEY ( (user_id, region), ts, device )
└── partition key ──┘ └── clustering columns ──┘
决定数据落在哪个节点 决定数据在节点内如何排序
token = hash(user_id, region) 同一分区内按 (ts, device) 字典序/时间序排列
用于数据分片与副本放置 用于高效的范围扫描（range query）
不能做范围查询（只支持 = / IN） 支持 <, >, <=, >= 与 ORDER BY
- 分区键决定数据去哪个节点（由 partitioner 计算 token）；一个”分区（partition）”就是同一分区键下的所有行，它们在物理上必须存在同一台机器的同一张 SSTable 集合中，并按聚簇键排序。
- 聚簇键决定分区内数据的排序，从而让”取某用户最近 10 条消息”这类查询成为一次顺序定位读取，而不是全表扫描。
工程含义：分区键的基数和均匀性是性能的生死线——分区键选取不当会产生超大分区（wide partition，单分区 > 100 MB 会导致 GC 压力、compaction 压力、甚至读超时）。聚簇键则决定你能做哪些范围查询。
- 时间戳（Timestamp）与 last-write-wins：每个列值都携带一个写时间戳（微秒精度，通常由客户端或协调者写入时给定，而不是由接收副本各自”记下当前时间”）。它的唯一作用是冲突解决：当同一个 cell 在不同副本上有多个版本时，时间戳最大的版本获胜（last-write-wins, LWW）。这就是 Cassandra 不需要共识就能让副本收敛的机制来源。
- 危险（必须理解）：LWW 的”新”完全依赖这个时间戳，而时间戳来自不同机器的本地时钟。时钟不同步会直接导致数据永久丢失：若客户端 A 的钟慢 5 秒而客户端 B 的钟准，A 后写的值会因为时间戳更小而被 B 先写的值”覆盖掉”，而且没有任何机制会发现这件事（详见 Lecture 26 的时钟同步、Lecture 12 的向量时钟如何解决这一问题的替代方案）。
- 时间戳相同时的 tie-break（完整定义）：若两个版本时间戳完全相同，Cassandra 用值本身的字节序比较，字节序更大（deeper/更大）的值获胜。因此 LWW 的完整定义是：
(timestamp, value_bytes)二元组的字典序最大值获胜。这是一个确定性规则，保证所有副本在拿到同一组冲突版本时独立算出同一个赢家——这是收敛性的关键前提。
- TTL、Counter、Secondary Index 的语义与限制（补充说明：讲义只在删除/墓碑处隐含提到 TTL，这里补齐工程语义）：
| 特性 | 语义 | 关键限制 |
|---|---|---|
| TTL（Time To Live） | 写入时给 cell 指定存活秒数，如 INSERT ... USING TTL 3600；到期后该 cell 被视为删除（读取时不可见，并在 compaction 时被真正清理） | TTL 是逐 cell 的；过期不是”定时任务”而是”读时判断 + 合并时清理”；大量短 TTL 数据会产生大量墓碑；表级 default_time_to_live 只是写入时的默认值 |
| Counter（计数器） | 支持 UPDATE t SET c = c + 1 WHERE k = ... 的分布式计数，读时把各副本的计数合并（非 LWW） | 不能与普通列混用在同一张表；不支持 TTL；非幂等——写超时后重试可能重复计数；没有时间戳，因此无法用 LWW，也不参与普通读修复逻辑；所有 counter 更新都走一轮读-改-写（Paxos 变体的历史实现），写吞吐远低于普通写 |
| Secondary Index（二级索引，2i） | 在非主键列上建索引，支持 WHERE col = x | 索引是本地的（per-node local index），不是全局索引：查一个没有分区键的二级索引条件，协调者必须向所有节点 scatter-gather，随集群规模线性放大延迟；高基数（高唯一值比例）列上效果极差（几乎等于全表扫描）；不支持范围查询；需配合 ALLOW FILTERING 的场合意味着你在做分布式全表扫描 |
- 关键假设与系统模型：数据模型假设 (1) 查询模式已知且有限（因此可以按查询建表）；(2) 同一分区内的数据总能被放在一台机器上（因此分区不能无限大）；(3) 冲突可以用时间戳这类”可交换、可结合、确定性”的规则解决（因此无需协调）。任何一条假设被破坏，就要付出巨大代价（全表扫描、超大分区、静默丢数据）。
9.2.8 数据分区：Partitioner 与虚拟节点（vnodes）
定义与目的：数据分区（partitioning）解决”一个 key 应该存在哪些服务器上”。Cassandra 使用基于环的 DHT（Distributed Hash Table）——但没有 finger table、没有多跳路由；key→server 的映射由 Partitioner（分区器） 决定。
直观解释（”它是什么？”）：想象一个 0 到 $2^{64}-1$ 的圆形号码牌，每台机器在圆上认领若干位置（token）。要放一个 key，就把 key 丢进哈希函数算出一个号码，然后顺时针走，遇到的第一个”认领点”的主人就是它的归属。这与 Lecture 8 的 Chord 是同一个环形 DHT 思想，区别在于Cassandra 里每个节点都知道全部成员，因此可以一步定位，不需要 Chord 的 $O(\log N)$ 跳转发。
机制图解（一致性哈希环 + vnodes + 副本放置）：
token 环：0 ── 顺时针 ──▶ 2^64-1 ── 回绕 ──▶ 0
┌───────────────────────────────────────────────────────────────────┐
│ ● 0 / 2^64（环的起点） │
│ N1:v3 ●──╱ ╲──● N2:v2 │
│ ╱ ╲ │
│ N4:v1 ●─────╱ ╲─────● N2:v1 │
│ ╲ ╱ ╲ ╱ │
│ ╲ ╱ ╲ ╱ │
│ N3:v2 ●───●───────────────●───● N1:v1 │
│ N3:v1 N4:v2 │
│ │
│ ● = 一个 vnode（虚拟节点，即环上的一个 token） │
│ 示例中 N1/N2/N3/N4 各拥有 2 个 token（生产默认 num_tokens = 256） │
└───────────────────────────────────────────────────────────────────┘
token(K13) = 331，落在 N3:v2 与 N2:v1 之间
→ 顺时针第一个 vnode = N3:v2 ⇒ N3 是 primary replica
→ 继续顺时针取 N = 3 个“不同物理节点” ⇒ 副本集合 = { N3, N2, N4 }
把环剪开成线性形式，副本放置看得更清楚：
顺时针 ───────────────────────────────────────────────────────────▶
│N1:v3│N3:v2│N2:v1│N4:v2│N2:v3│N1:v1│N3:v1│N4:v1│
t=100 t=250 t=480 t=610 t=730 t=890 t=1010 t=1150
▲
token(K13)=331 → 顺时针第一个是 N3:v2
副本 (N=3)：N3(primary) → N2 → N4（跳过同一物理节点的其它 vnode）
把环”剪开”成线性形式更容易看清副本放置：
顺时针 ─────────────────────────────────────────────────────────────────────▶
│N1:v3│N3:v2│N2:v1│N4:v2│N2:v3│N1:v1│N3:v1│N4:v1│
t=100 t=250 t=480 t=610 t=730 t=890 t=1010 t=1150
▲
token(K13)=331 → 顺时针第一个是 N3:v2
副本 (N=3)：N3(primary) → N2 → N4 ← 注意：跳过同一物理节点的其它 vnode
- 两类 Partitioner：
| Partitioner | 做法 | 优点 | 缺点 |
|---|---|---|---|
| RandomPartitioner / Murmur3Partitioner | 用哈希（MD5 / Murmur3）把 key 映射到环上的 token，即”Chord 式哈希分区” | 负载在环上均匀分布，无热点 | 不保留 key 的顺序：范围查询（如”取出 [a–b] 开头的用户”）必须广播到所有节点 |
| ByteOrderedPartitioner | 直接把 key 的字节顺序映射为 token，等于把 key 的连续区间分配给服务器 | 范围查询极其高效：Get me all twitter users starting with [a-b] 只需访问少数几个节点 | 热点（hotspot）：顺序写入的 key（时间戳、自增 ID、以固定前缀开头的 key）会全部落到同一节点，写入无法分散；也破坏负载均衡 |
Cassandra 的默认选择是 Murmur3Partitioner（1.2 起取代 MD5 的 RandomPartitioner），因为负载均衡与写吞吐远比范围查询重要；需要范围查询时，正确做法是通过聚簇键在同一分区内做范围扫描，而不是依赖分区器保留顺序。
- 为什么用 vnodes 而不是”一个节点一个 token”：早期 Cassandra 每个物理节点只拥有一个 token，于是产生了三个问题：
- 负载不均：随机哈希把一个 token 放到环上，各节点负责的区间长度是随机的，节点少时方差很大（有节点可能只负责 5% 的数据，另一个负责 25%）；
- 再平衡（rebalance）粗粒度：加一个节点时，它只能从环上的前一个节点手里”切走一半”区间，等于从一台机器搬走一半数据——大而慢，且只能改善一个邻居的负载；
- 异构集群无法利用：更强的机器无法多承担数据。 vnodes（虚拟节点 / tokens）的做法是：每个物理节点认领环上多个（默认 $num\_tokens=256$）位置。
- 负载均衡：一个节点拥有的 token 越多，它负责的总区间长度就越接近 $1/N$（大数定律），方差急剧下降；
- 快速再平衡：加入新节点时，它从许多已有节点各”借”一小段区间，多路并行流式传输（streaming），速度快、对单节点冲击小；
- 异构支持：配置更强的机器可以给更多
num_tokens，按比例承担负载； - 故障后的重建：一个节点挂掉后，它的 256 段区间由集群中许多节点同时接管，恢复速度快、不会压垮单一邻居；
- 代价（补充说明）：元数据与 gossip 消息更大、需要管理的区间（range）更多，因此 repair 与 compaction 的调度开销上升——这也是后来 Cassandra 支持
num_tokens调小（如 16、8）甚至回到单 token 的原因。
- 关键假设与系统模型：分区假设哈希函数把 key 均匀打散（否则热点）、所有节点对环的视图一致（靠 gossip 传播 token 与状态）、节点数远小于 token 数（否则 vnode 的均衡优势消失）。
9.2.9 复制策略：SimpleStrategy、NetworkTopologyStrategy 与 Snitch
定义与目的：复制策略（Replication Strategy）决定副本放在哪些节点上。Cassandra 提供两种：SimpleStrategy（单数据中心）与 NetworkTopologyStrategy（多数据中心、机架感知，生产必选）。
直观解释（”它是什么？”）：SimpleStrategy 是”从这个 key 顺时针数，连续取前 $N$ 个节点”——简单但对”一个机架断电”毫无抵抗力。NetworkTopologyStrategy 是”每个数据中心各放几份，且这些副本尽量分散到不同机架“——它假设故障是有相关性的：一个机架交换机的电源或一条上行链路，会让整个机架的机器同时消失。
机制图解：
── SimpleStrategy（仅单 DC）── ── NetworkTopologyStrategy（生产）──
┌─────────────────────────────────────────────┐ ┌─────────────────────────────────────────────────┐
│ 环上顺序（顺时针）：N1 → N2 → N3 → N4 → N1 │ │ DC1 放 3 份：分别落在 Rack1 / Rack2 / Rack3 │
│ token(K) 落在 N1 与 N2 之间 │ │ DC2 放 2 份：分别落在 Rack1 / Rack2 │
│ primary = 顺时针第一个节点 = N2 │ │ 第一个副本由 Partitioner 决定；之后顺时针前进， │
│ 副本集合 = { N2, N3, N4 }（沿环连续取 3 个）│ │ 遇到“不同机架”的节点才放下一个副本 │
│ ⚠ 3 个副本可能全落在同一个机架上 │ │ ⚠ 每 DC 的 RF 不应超过该 DC 的机架数 │
└─────────────────────────────────────────────┘ └─────────────────────────────────────────────────┘
为什么必须跨机架放副本？同一机架共享交换机 / PDU 电源 / 上行链路，
一次机架级故障会同时带走所有副本 —— 那等于没有复制。
SimpleStrategy 的规则：第一个副本放在持有该 token 的节点上，然后沿环顺时针依次放置其余 $N-1$ 个副本（跳过同一物理节点上的其它 vnode）。只用于单数据中心部署——因为它完全不懂机架与 DC，副本可能落在同一机架上。
- NetworkTopologyStrategy 的规则：按 DC 指定各自的副本数（如
{'dc1':3,'dc2':2}）。在每个 DC 内：- 第一个副本按 Partitioner 决定（与 SimpleStrategy 相同）；
- 然后沿环顺时针前进，直到遇到处于不同机架的节点才放下一个副本；机架用尽后才能在同一机架放第二份。 因此 每 DC 的副本数不应超过该 DC 的机架数，否则”跨机架容错”这一保证必然被打破。讲义强调的两种常见配置就是”每 DC 2 个副本”与”每 DC 3 个副本”。
为什么要跨机架放副本？ 因为故障域（failure domain）问题：同一机架内的机器共享交换机、PDU 电源与上行链路。若 $N$ 个副本都落在同一机架，一次机架级故障就会同时带走所有副本 —— 这等于没有复制。跨机架（以及跨 DC）放置使得”单个机架死掉”最多影响一个副本，集群仍然可读可写。
- 副本因子 $N$（Replication Factor）：一个 key 的副本总数。它同时决定了：
- 容错能力：$N=3$ 时可以容忍 $\lfloor (N-1)/2 \rfloor = 1$ 个副本故障而仍能凑齐 QUORUM；$N=5$ 可以容忍 2 个；
- quorum 的大小：$\text{QUORUM} = \lfloor N/2 \rfloor + 1$；
- 存储成本与写放大：每个写都要被写 $N$ 次（实际按 $W$ 等待 ack，但最终所有副本都会被写）；
- 生产常见 $N=3$（跨 3 个机架/3 个 AZ），跨 DC 部署则每个 DC 3 份。
- Snitch（拓扑嗅探器）：snitch 负责把IP 地址映射到机架与数据中心，配置在
cassandra.yaml中。没有正确的 snitch，NetworkTopologyStrategy 就无从判断”下一个副本该放哪里”。- SimpleSnitch：不感知拓扑（Rack-unaware），单 DC 默认；
- RackInferringSnitch：从 IP 的八位组推断拓扑，规则是
101.201.202.203 = x.<DC 八位组>.<机架八位组>.<节点八位组>，即第二个八位组是 DC、第三个八位组是机架（要求 IP 规划严格遵守该约定）； - PropertyFileSnitch：从配置文件读取 IP→DC/机架 的映射，最精确但需要人工维护；
- GossipingPropertyFileSnitch：同样用配置文件，但通过 gossip 把拓扑信息传播给所有节点，避免每个节点都要维护全量映射，是生产推荐；
- EC2Snitch / EC2MultiRegionSnitch：直接使用云厂商元数据——EC2 Region = DC，Availability Zone = 机架。
- 关键假设与系统模型：复制策略假设故障是机架/DC 相关的（correlated），并且snitch 提供的拓扑信息是正确的。如果 snitch 配置错误（例如所有节点被当成同一机架），NetworkTopologyStrategy 会静默退化为”随机放副本”，容错能力远低于运维人员的预期——这是生产事故的经典来源。
9.2.10 可调一致性（Tunable Consistency）与 $R+W>N$
这是本章最重要的分布式机制：一致性不是系统的固定属性，而是每次操作的参数。
定义与目的：客户端为每个操作（读或写）指定一致性级别。读一致性级别对应 $R$（读副本数），写一致性级别对应 $W$（写副本数），$N$ 是该 key 的副本总数。协调者（coordinator）等待 $R$ 个读响应或 $W$ 个写确认后才返回给客户端。
直观解释（”它是什么？”）：把一致性想象成投票：写需要收集至少 $W$ 张”我记下了”的票才算成功；读需要收集至少 $R$ 张”我看到的值是”的票才敢回答。如果两组票加起来超过总票数 $N$，那么按照鸽巢原理，这两组票必然有重叠——也就是说，读的时候至少碰到了一个人手里攥着刚写下的那张票。重叠越大，越不可能读到旧值。
机制图解（$R+W>N$ 的 quorum 交集）：
N = 5 个副本围成一圈（同一 key 的 5 份拷贝）
┌─────────┐
┌──────┤ R5 ├──────┐
│ └─────────┘ │
┌─────┴─────┐ ┌─────┴─────┐
│ R1 W● │ │ R2 W● │ ● = 写到达的副本 (W=3)
└─────┬─────┘ └─────┬─────┘ ○ = 读接触的副本 (R=3)
│ ┌─────────┐ │
└──────┤ R3 W● ○├──────┘ 交集：{R3}（非空 → 强一致）
└─────────┘
┌─────────┐
│ R4 ○ │ 读集合 {R3,R4,R5}
└─────────┘ 写集合 {R1,R2,R3}
|写|+|读| = 6 > 5 ⇒ 必相交
── 反例：W = 1, R = 1, N = 5 ──
写集合 {R1}，读集合 {R4}，1+1 = 2 ≤ 5 → 可以完全不相交 → 读到陈旧值
- 两种操作的语义（讲义原文）：
- 写：客户端指定 $W \le N$；协调者把新值写到 $W$ 个副本后返回。两种风格：(a) 协调者阻塞直到达到 quorum；(b) 异步，发出去就返回。
- 读：客户端指定 $R \le N$；协调者等待 $R$ 个副本响应后才把结果返回客户端，并返回其中时间戳最新的值；同时在后台检查其余 $N-R$ 个副本的一致性，必要时发起读修复（read repair）。
- 一致性级别全表：
| 一致性级别 | 含义 | 适用于 | 延迟 | 可用性 | 说明 |
|---|---|---|---|---|---|
| ANY | 任意一台服务器，可以不是副本；协调者把写缓存下来就立即回复 | 仅写（读无意义） | 最快 | 最高 | 用提示移交换取”永远可写”；写成功后立刻读可能读不到 |
| ONE | 至少 1 个副本 | 读/写 | 很快 | 高（容忍 $N-1$ 个副本故障） | 与 ALL 相对；$R+W$ 通常 $\le N$，最终一致 |
| TWO / THREE | 恰好 2 / 3 个副本 | 读/写 | 中 | 中 | 显式指定小 quorum，常用于 READ 快而 WRITE 稍稳 |
| QUORUM | 所有 DC 中全部副本的多数：$\lfloor N/2 \rfloor + 1$ | 读/写 | 中 | 中 | 全局一致但跨 DC 需等待 WAN 往返 |
| LOCAL_QUORUM | 协调者所在 DC 内的多数 | 读/写 | 快 | 中 | 生产最常用：避免跨 DC 延迟，本 DC 内强一致 |
| EACH_QUORUM | 每个 DC 各自达到多数 | 仅写 | 慢 | 中 | 支持分层应答，保证每个 DC 都达到 quorum |
| ALL | 全部 $N$ 个副本 | 读/写 | 最慢 | 最低（任一副本故障即失败） | 提供最强的强一致性 |
- 核心公式与正确性论证（本章黄金公式）：
形式化论证见 9.3.3 算法 9.3.3，这里给出骨架：
- 设最近一次成功的写 $w$ 写入了副本集合 $S_W$，$\vert S_W\vert = W$（这些副本都持有 $w$ 的新值，因为写成功的定义就是 $W$ 个副本已确认）；
- 设当前读接触副本集合 $S_R$，$\vert S_R\vert = R$；
- $S_W, S_R \subseteq \mathcal{R}$（$\mathcal{R}$ 为该 key 的 $N$ 个副本），故 $\vert S_W \cup S_R\vert \le N$；
- 若 $S_W \cap S_R = \varnothing$，则 $\vert S_W\vert + \vert S_R\vert = \vert S_W \cup S_R\vert \le N$，即 $R + W \le N$，与前提 $R+W>N$ 矛盾；
- 故 $S_W \cap S_R \ne \varnothing$：读集合中至少有一个副本持有 $w$ 的值；
- 协调者按时间戳取”最新的值”返回，因此返回值的时间戳 $\ge$ $w$ 的时间戳，读不会返回比 $w$ 更旧的值。$\blacksquare$
反之，$R + W \le N$ 时存在一种副本选择使读、写集合完全不相交，因此只保证最终一致性（靠读修复与反熵在事后收敛）。
- 讲义给出的两条”一致性必要条件”：$W + R > N$ 与 $W > N/2$。
- $R+W>N$ 是读-写 quorum 相交的条件，如上所证；
- $W > N/2$ 额外保证任意两次写的 quorum 也彼此相交（$\lfloor N/2 \rfloor + 1$ 是保证两个写集合必相交的最小值）。补充说明：Cassandra 用时间戳做 LWW，写-写冲突本身靠时间戳而非 quorum 相交解决；$W>N/2$ 真正的意义在于保证”后一个写者能观察到前一个写者的结果“，这是 read-modify-write（读-改-写）不丢更新的前提。
- 具体数值例子（$N=3$）：
| $(W, R)$ | $R+W$ vs $N$ | 保证 | 延迟 | 容错 | 适用负载（讲义口径） |
|---|---|---|---|---|---|
| $(1,1)$ | $2 \le 3$ | 最终一致 | 最低 | 容忍 2 个副本故障 | 极少读写的冷数据；可容忍陈旧读 |
| $(2,2)$ | $4 > 3$ | 强一致 | 中 | 容忍 1 个副本故障 | 通用默认（QUORUM/QUORUM） |
| $(3,1)$ | $4 > 3$ | 强一致 | 读快写慢 | 写零容错 | 读密集负载 |
| $(1,3)$ | $4 > 3$ | 强一致 | 写快读慢 | 读零容错 | 写密集、且同一 key 基本只有一个客户端在写 |
| $(3,3)$ | $6 > 3$ | 最强 | 最高 | 零容错 | 类 RDBMS 语义，可用性最低 |
讲义对选型的经验法则：$(W=1,R=1)$ 读写都最少；$(W=N,R=1)$ 适合读密集；$(W=N/2+1, R=N/2+1)$ 适合写密集（补充说明：这实际上也是最常用的读写均衡默认值）；$(W=1,R=N)$ 适合写密集且每个 key 基本只有一个写入者的场景。
延迟与一致性的权衡：$W=\text{ALL}$ 一致性最强但最慢且可用性最低——任一副本故障，写就失败；$W=\text{ONE}$ 最快但可能被读到陈旧值。一致性越高，协调者必须等待的副本数越多，长尾（tail）延迟由最慢的那个副本决定（即”木桶效应”）。这正是”旋钮”的物理含义。
关键假设与系统模型：$R+W>N$ 的论证依赖三个假设：(1) 写”成功”意味着 $W$ 个副本已经持久化该版本（不是缓存、不是异步投递）；(2) 副本集合稳定——期间没有发生重新平衡使副本位置改变；(3) 版本可由时间戳（或版本号）比较出”最新”。若 (1) 被打破（例如用了
ANY，写到 hint 上就算成功），强一致保证立刻失效——这是ANY + ONE组合会读到陈旧值的原因。
9.2.11 无主复制与”任意节点都是协调者”
定义与目的：在 Cassandra 中，任意一个节点都可以充当协调者（coordinator）。客户端连接到集群中任意节点，该节点负责把请求转发给该 key 的副本，并收集应答。这是一种无主（leaderless）复制：没有主节点、没有选举、没有单点写入口。
直观解释（”它是什么？”）：像一家任何柜台都能办事的银行：你不必去”总行”，随便走进一家网点，柜员会替你联系所有相关分店并把结果汇总给你。与之相对的是有主（leader-based）复制：所有写必须先到”店长”那里，店长再通知其他人——好处是顺序天然确定（容易实现强一致），坏处是店长挂了或网络把它隔开，就没人能写。
机制图解：
── 无主复制（Cassandra / Dynamo）── ── 有主复制（HBase+ZK / MongoDB RS / Raft）──
┌──────────────────────────────────────────┐ ┌────────────────────────────────────────────┐
│ Client 可连**任意**节点（该节点当协调者）│ │ Client 必须连 Leader（或由 Follower 转发） │
│ 协调者并行联系该 key 的 N 个副本 │ │ Leader 把日志复制给 Followers │
│ 凑够 W 个 ack 即可返回 → 永远可写 │ │ 需要多数派 ack 才算提交 │
│ 无选举、无主、无单点写入口 │ │ 需要选举（Paxos / Raft / Zab） │
└──────────────────────────────────────────┘ │ 分区时少数派一侧无法写 → CP ─┘
└───────────────────────────────────────────┘
Client Client
│ │
▼ ▼
┌────────┐ 并行 ┌────┐ ┌────┐ ┌────┐ ┌────────┐ 日志复制 ┌──────────┐
│任一节点│◀───────▶│ R1 │ │ R2 │ │ R3 │ │ Leader │──────────▶│ Follower │
│(协调者)│◀───────▶└────┘ └────┘ └────┘ └────────┘ └──────────┘
└────────┘ ▲ 需要多数派 ack 提交
无选举；W 个 ack 即返回 ▲ 需要 Leader 选举
协调者的粒度：讲义指出协调者可以是 per-key（按键）、per-client（按客户端） 或 per-query（按请求）。其中 per-key coordinator 能保证同一 key 的写被串行化（同一个协调者按序转发），这对保持单一客户端的写入顺序很有用。
- 与 Lecture 19（共识）的对照：无主复制的哲学是”用可交换的冲突解决规则（时间戳 LWW）替代共识“——因此它永远可用但只能提供弱一致；有主复制（Paxos/Raft/Zab，ZooKeeper、HBase、Spanner）的哲学是”用多数派共识换强一致“——因此它在分区时必然牺牲一侧的可用性。Cassandra 里的例外是”轻量级事务（LWT）”：它基于 Paxos，因此写延迟约高一个数量级，且与普通写路径不共享性能特征——这恰好反证了上面这条权衡的普遍性。
讲义还提到一个多 DC 的细节：每个数据中心一个环，需要每个 DC 选出一个协调者与其他 DC 协调，这个选举通过 ZooKeeper（运行 Paxos 的一个变体）完成。这生动地说明：即使是 AP 系统，在”跨 DC 的元数据协调”这种小规模、低频、要求强一致的子问题上，仍然会借用共识。
- 关键假设与系统模型：无主复制假设冲突解决规则是可交换且确定的（同一组版本在任何副本上算出同一结果），且任何节点都能算出任一 key 的副本集合（因此每个节点都保存完整成员表与 token 表，见 9.2.15）。
9.2.12 提示移交（Hinted Handoff）
定义与目的：提示移交是 Cassandra”永远可写（always writable）“的核心机制。若某个目标副本宕机或不可达，协调者照常把写发给其余副本，同时在本地保存一条 hint（提示）——记录”这个写本该发给谁”；等该副本恢复（通过 gossip 发现）后重放（replay）hint，把落后的写补上。
直观解释（”它是什么？”）：像快递员发现收件人不在家，就把包裹寄存在自己站点并留一张便签，等人回来了再送一次。收件人不会因为”不在家”而错过包裹，发件人也不必等着——这就是可用性的来源。
机制图解：
正常情况: Client ──▶ Coordinator ──▶ R1 ✔ R2 ✔ R3 ✔ W=3 达成
副本 R3 宕机:
Client ──▶ Coordinator ──┬──▶ R1 ✔
├──▶ R2 ✔
└──✗ R3 (down)
│
└──▶ 本地 hints 表：{target=R3, key=K, value=V, ts=t}
W=2 已达（若 W≤2）→ 立刻回复 client "成功"
稍后: gossip 发现 R3 回到 NORMAL 状态
Coordinator ──replay hint──▶ R3 （写补上，hint 删除）
它如何提高可用性：写不会因为单个副本故障而失败。配合一致性级别 ANY，即使所有目标副本都不可用，协调者也可以把写缓冲在本机（讲义：可缓冲数小时）并回复成功——系统在任何时刻都接受写。
- 它的代价（关键）：
- hint 节点自己也会坏：hint 只存在协调者本地，若该节点在重放之前故障，hint 丢失，写永久丢失；
- hint 队列积压：副本长时间不可用会让 hint 不断堆积，占用磁盘与内存，恢复时的”hint 风暴“可能压垮刚回来的副本；
- 有时间窗口：Cassandra 的
max_hint_window_in_ms（默认 3 小时）限制了对某个宕机节点保存 hint 的时长；超过窗口后不再记录 hint，这些写只能靠反熵修复找回； - 它不保证可读性：写成功 ≠ 能被读到。用
ANY写的值可能只存在于 hint 中，此时用ONE去读读不到（这就是ANY不能提供 read-your-writes 的原因）。 因此 hinted handoff 必须由 anti-entropy repair 兜底：前者是”快速的尽力而为”，后者是”最终一定收敛”的保证。
- 关键假设与系统模型：假设故障是短暂的（crash-recovery 模型）且协调者比目标副本更可靠。它不假设故障副本的数据已丢失——恢复后的副本仍需通过 repair 与其它副本对齐（因为它可能错过了超出 hint 窗口的写）。
9.2.13 读修复（Read Repair）
定义与目的：读修复利用”读”这个机会顺便修复不一致的副本：协调者读一个 key 时，不仅返回最新值，还把过旧的副本就地更新。它使每一次读都可能”顺手治好”一个陈旧副本，从而推动最终收敛。
直观解释（”它是什么？”）：像老师收作业时发现某个同学交的是旧版本，于是当场把最新版本复印一份塞给他——不用专门再跑一趟办公室。读操作本来就要联系副本，顺手修复几乎是”免费”的收敛机会。
机制图解（阻塞式 vs 异步）：
① 阻塞式读修复（blocking read repair）
Client ──read(K, QUORUM)──▶ Coordinator
├── 向所有 N 个副本请求 (value, timestamp) 或 digest
├── 收齐后比较：R2 的 ts 最旧、与最新值不同
├── 阻塞等待 R2 被写入最新值 ← 读延迟被最慢的修复拖长
└── 返回最新值给 Client
✔ 修复一定是"已被读到的那份数据"，不会读到陈旧值
✘ 读延迟 = max(所有副本)，长尾更差
② 异步 / 后台读修复（async read repair）
Client ──read(K, ONE)──▶ Coordinator
├── 只等 R 个副本（例如只等 R1）
├── 立即返回最新值给 Client ← 客户端很快
└── 后台联系其余 N-R 个副本，发现 ts 更旧则写回
✔ 读延迟低（只等 R 个）
✘ 返回时可能刚好读到尚未修复的陈旧值；修复是"尽力而为"
③ 两种都依赖同一件事：每个副本要能报出 (value, timestamp)，
才能判断"谁最新" → 所以读修复需要版本号/时间戳
讲义口径：读时”协调者联系 $R$ 个副本，可以优先选择过去响应最快的副本；当 $R$ 个副本响应后，协调者返回其中时间戳最新的值；此外协调者还会去取其它副本的值，在后台检查一致性，若任意两个值不同就发起读修复“；这个机制”力图最终把所有副本更新到最新”。
需要版本/时间戳来判定”谁最新”：读修复必须回答”哪个副本更旧”。Cassandra 用每个 cell 的写时间戳（LWW）来回答；Riak/Dynamo 则用向量时钟（vector clock）来回答”这两个版本是因果关系还是并发冲突”（详见 Lecture 12）。没有版本信息，读修复只能发现”不一致”，无法决定”往哪边修”——这是很多人实现自研 KV 存储时踩的坑。
关键假设与系统模型：假设至少有一个副本持有正确（最新）值——这正是 $R+W>N$ 保证的；如果没有这个保证（例如 $R=1,W=1$），读修复可能把陈旧值当作”最新”传播，反而造成”修复风暴/脏读扩散“。此外假设比较所需的元数据（时间戳）本身不会被压缩掉。
9.2.14 反熵修复与 Merkle Tree
定义与目的：反熵（anti-entropy）修复是 Cassandra 的兜底收敛机制：周期性地（或由运维显式触发，
nodetool repair）逐区间比较两个副本的全部数据，找出差异并修复。直接比较全部数据需要传输 $O(n)$ 个 key，代价无法接受；Merkle Tree（哈希树 / hash tree）把比较代价降到只需传输树节点哈希，并通过逐层下降定位到具体不同的 key。直观解释（”它是什么？”）：两个人核对两份各有一万行的名单，逐行念太慢。于是先各自把名单算一个总校验和：相同 ⇒ 完全一致，结束；不同则把名单切成 10 段，各报 10 个分段校验和：只有 1 段不同 ⇒ 只需深入这 1 段。如此递归，比较次数是对数级的。这就是 Merkle Tree：”先在粗粒度上筛，再在细粒度上钻”。
机制图解（Merkle Tree 比较过程：两个副本的树，逐层下降）：
副本 A 的 Merkle 树 副本 B 的 Merkle 树
（叶子 = 每个 key 的 hash，按 key 排序） （同样的划分与排序）
┌──────────┐ ┌──────────┐
Level 0 │ H_root_A │ = 9f3c… │ H_root_B │ = 4a17… ← 不同！
└────┬─────┘ └────┬─────┘
┌────────┴────────┐ ┌────────┴────────┐
L1 ▼ ▼ ▼ ▼
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
│ H_A1 │=7b21… │ H_A2 │=cc40… │ H_B1 │=7b21… │ H_B2 │=11de… ← 不同
└──┬───┘ └──┬───┘ └──┬───┘ └──┬───┘
┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐
L2 ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼
h(k1) h(k2) h(k3) h(k4) h(k1) h(k2) h(k3) h(k4)
=a1 =b2 =c3 =d4 =a1 =b2 =c3 =XX ← 只有这一个叶子不同
↑相同 ↑相同 ↑相同 ↑相同 ↑相同 ↑相同 ↑相同 ↑不同
比较过程：根不同(1 次) → 比 2 个子节点 → 只有 H_B2 不同 → 比 H_B2 的 2 个孩子
→ 定位到 h(k4) 不同 → 只传输 key=k4 的数据
访问节点数 = 1 + 2 + 2 = 5 = O(log n × 分支因子)，而非 O(n)=4（本例）或百万级（真实规模）
- 构造算法：
- 取一个 token range（token 区间） 内的全部 key，按 key 排序（Cassandra 中即按分区器 token 顺序）；
- 每个叶子是该 key 对应数据（或该 key 的 value）的哈希；为控制树高，通常把连续的若干个 key 打包成一个叶子（Cassandra 用
partition keys per leaf，即tree_depth与max_tree_depth控制）； - 逐层向上，把子节点哈希拼接后再哈希得到父节点哈希，直到根；
- 树的大小与区间内 key 数成正比（$O(n)$），但只有哈希在网络上传输，每个哈希 32 字节（MD5）左右。
- 比较算法：
- 两个副本交换根哈希；
- 若相同 ⇒ 该区间数据完全一致，停止（这是最好情况，代价 $O(1)$）；
- 若不同 ⇒ 双方各自发送子节点哈希列表，逐一定位不同子树；
- 递归下去，直到到达叶子（具体 key）；
- 对这些具体 key，按时间戳 LWW 决定谁是最新值，把较旧的一方修复（传输实际数据）；
- 对”只有一方有、另一方没有”的 key（因故障期间漏写），同样补齐。
- 复杂度分析：设区间内 key 数为 $n$，树的分支因子为 $b$，深度 $d = \log_b n$。
- 构造：$O(n)$ 时间与空间（哈希每个 key，再逐层合并）；
- 比较（完全一致）：$O(1)$ 个哈希传输，1 轮网络往返；
- 比较（有 $d_{iff}$ 个叶子不同）：需要访问的节点数上界为 $O\!\left(d_{iff} \cdot \log_b n\right)$；最坏情况（只有 1 个 key 不同）只需要 $O(\log n)$ 个节点哈希——这正是讲义强调的”$O(\log n)$ 而非 $O(n)$”；
- 数据传输：仅传输真正不同的 key 的数据，即 $O(d_{iff})$，与”全量传输 $O(n)$”相比是决定性的改进。
- 范围大小（range size）与树的深度/开销的权衡：Merkle Tree 按 token range 构建（Cassandra 把整个环切分成很多小区间，
nodetool repair会分区间并行构建）。区间越大 ⇒ 树越深、每个叶子的判定越慢、修复时的传输粒度越粗、单次 repair 的内存压力越大；区间越小 ⇒ 树浅、定位精准、可并行，但树的个数变多，根哈希的交换与调度开销（以及每棵树的固定开销）上升。Cassandra 的实践是把新区间切到足够小以使每棵树能放进内存，并并行地修复多个区间——这是一个典型的”元数据开销 vs 定位精度 vs 内存占用“三角权衡。
- Merkle Tree 的前提约束（最容易被忽略，也最容易导致线上事故）：
- 副本的数据必须按相同顺序排列：哈希树是对”有序的 key/value 序列“做哈希。若两个副本的分区器不同、分区键或聚簇键顺序不同（schema 不一致，例如一方
ORDER BY相反），那么即使数据内容相同，树的形状与哈希也会处处不同——比较结果的”不同”毫无意义，修复会变成盲目全量传输。因此 repair 要求schema 一致、分区器一致； - 必须基于同一时间点的快照：repair 过程中若有新写入，两边的树是在”流动的数据”上构建的，会导致虚假差异。Cassandra 因此用 snapshot（快照） 在修复期间固定数据视图；
- 必须正确处理墓碑（tombstone）：删除在 Cassandra 中就是一个带时间戳的墓碑。若一方已经 compaction 掉墓碑（因为它超过了
gc_grace_seconds）、另一方还没删，那么”没有数据”的一方会被误判为”缺少数据”，修复时把已删除的数据复活（resurrection）。所以：必须在gc_grace_seconds（默认 10 天）内完成对每个节点的 repair，否则会出现”删除的数据又回来了”这一经典故障； - 同一分区键必须在同一方：Merkle Tree 的比较是逐副本、逐区间的，它假设”这个 token 区间的副本就是我”；若期间发生了重新平衡（有人 bootstrap/离开），区间归属改变，比较对象就错了——因此 repair 期间应避免拓扑变更。
- 副本的数据必须按相同顺序排列：哈希树是对”有序的 key/value 序列“做哈希。若两个副本的分区器不同、分区键或聚簇键顺序不同（schema 不一致，例如一方
- 关键假设与系统模型：假设 schema/分区器一致、数据可快照、时钟偏差在可接受范围内（否则 LWW 在修复时也会选错赢家）。这些前提一旦不成立，”修复”反而会成为不一致的放大器。
9.2.15 成员管理与故障检测：Gossip 与 Φ 累加故障检测器
定义与目的：因为任意节点都可能是协调者，所以每个节点都必须维护一份”当前集群成员表”；这张表必须随节点加入（join）、离开（leave）、故障（fail）自动更新。Cassandra 采用 gossip 式成员协议 + Φ 累加故障检测器（Phi Accrual Failure Detector）。
直观解释（”它是什么？”）：gossip 像办公室里的八卦：每个人每隔一会儿随机找几个人聊天，交换”我最近听说的关于同事的消息”；消息以指数速度扩散，不需要任何人广播给所有人。Φ 累加故障检测器则像一个经验丰富的护士：她不会因为病人 5 分钟没动静就宣布死亡，而是根据”这个病人平时多久动一次、波动多大”给出一个怀疑程度（0 到很大），让医生（应用）自己决定”超过多少算死”。
机制图解（gossip 成员表合并）：
节点 2 的成员表（当前时间 = 70） 节点 3 发来的成员表
┌───────────┬───────────┬─────────────┐ ┌───────────┬───────────┬─────────────┐
│ Address │ Heartbeat │ Time(local) │ │ Address │ Heartbeat │ Time(local) │
├───────────┼───────────┼─────────────┤ ├───────────┼───────────┼─────────────┤
│ 1 (10118) │ 64 │ 68 │ │ 1 (10120) │ 70 │ 69 │
│ 2 (10110) │ 64 │ 70 │ │ 2 (10110) │ 64 │ 69 │
│ 3 (10098) │ 63 │ 69 │ │ 3 (10098) │ 70 │ 69 │
│ 4 (10111) │ 65 │ 70 │ │ 4 (10111) │ 65 │ 69 │
└───────────┴───────────┴─────────────┘ └───────────┴───────────┴─────────────┘
合并规则：逐条目比较，取 heartbeat 更大的版本（freshness 优先）；
heartbeat 相同时再比较该条目自身的版本/时间戳。
合并后：节点 1 的 heartbeat 64 → 70，节点 3 的 heartbeat 63 → 70。
若某条目的 heartbeat 超过 Tfail 未增加 → 标记为 Suspected/Failed；
再经过 Tcleanup 才从表中删除（否则“死亡消息”会失去传播者，成员表抖动）。
为什么需要额外的清理超时（Tcleanup），而不是立即删除？ 讲义用一张图给出反例：如果节点 3 的条目在 $T_{fail}$ 到点后立刻被删除，那么节点 3 的”死亡”信息只能通过持有该条目的节点传播；一旦所有节点都删掉了它，一个”关于死亡的消息”就再也没有传播者了——更糟的是，一个刚恢复/刚加入的节点会从别人那里重新学会这个条目，于是”已死”的节点在成员表中反复出现又消失（成员表抖动）。因此成员协议保留条目一段时间（墓碑式的”失败标记”），让它有时间传播到全网。这正是 Lecture 6 中标记失败与删除之间需要第二个超时的原因。
- Gossip 的传播复杂度（Lecture 6 结论）：一次 gossip 传播到全网需要 $O(\log N)$ 时间（感染式/流行病式传播）。由此：
- 若每节点可用带宽是 $O(N)$，$N$ 个心跳可在 $O(\log N)$ 时间内传遍全网；
- 若每节点带宽只有 $O(1)$，则需要 $O(N \log N)$ 时间；
- 代价是 $\Theta(N)$ 量级的消息开销：每个节点每秒要与随机节点交换包含全网条目的消息，这就是 gossip 成员管理的规模上限来源（见 9.5）。
- gossip 周期 $T_{gossip}$ 减小会加快传播但增加带宽；$T_{fail}$、$T_{cleanup}$ 增大则误判率（false positive）下降但检测变慢——这是”误判率 vs 检测时间 vs 带宽“的三方权衡。
- Φ 累加故障检测器（Phi Accrual Failure Detector）：
- 它不是什么：它不是”心跳超时 → 判死”的二元判断。所有固定超时的检测器都必须在”误判（把慢当成死）”与”检测慢”之间二选一。
- 它是什么：输出一个怀疑度（suspicion level）$\phi$，让应用自己选择阈值。讲义给出的计算式：
其中 $t_{last}$ 是**最近一次收到该成员 gossip 消息的时间**，$P_{\\text{later}}(x)$ 是"**下一次心跳到达间隔大于 $x$**"的概率，即 $P_{\\text{later}}(x) = 1 - F(x)$，$F$ 是**心跳到达间隔（inter-arrival time）的累积分布函数**。讲义明确：$\\phi$ 基于**gossip 消息的到达间隔时间**，并"把历史到达间隔的波动考虑进去"。 - **$\\phi$ 的直观意义**：$\\phi = 1$ 表示"现在还没收到心跳，这件事发生的概率约 $10^{-1}$（不稀奇）"；$\\phi = 5$ 表示"约 $10^{-5}$ 的小概率事件发生了（很可疑）"；$\\phi$ 越大越可疑。**$\\phi$ 直接决定了检测超时，但它是自适应**的：网络抖动大时，需要更长的静默才会判定失败。 - **具体计算思想（正态近似，补充说明）**：设最近 $W$ 个到达间隔样本为 $\\delta_1,\\dots,\\delta_W$，计算均值 $\\mu$ 与标准差 $\\sigma$，则
当 $t \\gg \\mu$ 时，$P_{\\text{later}} \\to 0$，$\\phi \\to \\infty$。工程实现要点：**给 $\\sigma$ 设下界（防止样本方差为 0 导致除零/瞬时判死）**、用**滑动窗口**采样、并**在样本不足时用保守默认值**（Cassandra 的 `PhiAccrualFailureDetector` 正是这么做的）。 - **实践取值**：讲义指出 **$\\phi = 5$ 对应约 10–15 秒的检测时间**；Cassandra 的 `phi_convict_threshold` 默认值为 **8**（提高门限可减少误判，代价是检测更慢）。 - **优点**：**自适应**于网络与故障行为；**可调**（应用自己定阈值）；在"网络抖动"与"真故障"之间给出连续的概率判断，而不是硬边界。
- 种子节点（Seed Nodes）：新节点启动时如何发现集群？它必须知道至少一个”活着的入口”。配置在
cassandra.yaml的 seed 列表就是这个入口：新节点联系 seed，握手交换成员表，从而学会整个环。要点：- seed 不是主节点，不承担特殊的数据角色，也不是数据路径上的单点（数据仍按 token 放置）；
- 但 seed 是加入路径上的关键：所有现有节点都必须在配置中列出相同的 seed 列表，否则会出现”脑裂式“的多集群视图；
- 每个 DC 建议配置 2–3 个 seed（互为备份），且优先选负载轻、稳定的节点（因为新节点加入会先从 seed 拉取元数据）。
Snitch 与拓扑感知：见 9.2.9——snitch 提供 IP→DC/机架 的映射，gossip 与 NetworkTopologyStrategy 都依赖它。
- 关键假设与系统模型：假设 fail-stop / crash-recovery 故障模型（进程崩溃后可重启，不产生任意的错误状态）、网络最终能传递消息（fair-loss）、时钟是异步的（因此用逻辑心跳计数器而非绝对时间判断新鲜度）。检测器的完整性（completeness）可以被”最终检测到”保证，但准确性（accuracy）只能是概率性的——Lecture 6 引用 Chandra–Toueg 的结论：在丢包网络中无法同时做到”完整 + 准确”，否则就能解共识（而共识在异步系统中不可解）。
9.2.16 存储引擎（一）：写路径 CommitLog → Memtable → SSTable
定义与目的：Cassandra 的写必须”无锁（lock-free）且快（没有读、没有磁盘寻道）“。它采用 LSM-Tree（Log-Structured Merge Tree） 风格的三层结构：CommitLog（提交日志，磁盘顺序写）→ Memtable（内存有序表）→ SSTable（磁盘不可变有序文件）。
直观解释（”它是什么？”）：像记账：先在流水账本上按时间顺序一笔笔往后写（顺序写，极快且不怕断电），同时把当天的账记在脑子里的活页夹（Memtable，方便随时查）。活页夹满了，就把它整理装订成一本只读的账册（SSTable）归档——注意，已经装订的账册永不修改，新的修改写到新的活页夹里；查询时需要同时翻活页夹和所有账册，取”最新的那一版”。
机制图解（完整写路径）：
CLIENT COORDINATOR REPLICA 节点 (×N)
┌──────────────────────────────────────────────────────────────────┐
│ COORDINATOR（客户端连上的任意节点） │
│ ① token = hash(K)，用 Partitioner 定位 primary + 顺时针 N 个副本 │
│ ② 并行把 (K,V,ts) 发给全部 N 个副本（不是只发 W 个！） │
└──────────────────────────────────────────────────────────────────┘
│
│ ── 并行发送 WRITE_DATA(K,V,ts) ──▶ 每个副本各自执行下面三步
│
┌───────────────────────────────────────────────────────────────────────┐
│ REPLICA（每个副本上） │
│ ③ append to CommitLog（磁盘顺序追加，用于崩溃恢复）← 先落盘保持久性 │
│ ④ 更新 Memtable（内存有序表，按 key 排序，支持范围扫描） │
│ 讲义：Memtable 是“多个键值对的内存表示”，是可按 key 搜索的缓存， │
│ 且是写回（write-back）缓存，而不是写透（write-through） │
│ ⑤ 回 ack 给 Coordinator │
└───────────────────────────────────────────────────────────────────────┘
│
▼
⑥ Coordinator 凑够 W 个 ack → 回复 client“写成功”（不是等全部副本！）
⑦ 对不可达的副本：把 (target, K, V, ts) 记入本地 hints 表 = Hinted Handoff，
待 gossip 发现它回到 NORMAL 后，按“原始时间戳”重放
── 之后，在副本本地异步发生 ──────────────────────────────────────────
Memtable 满 ──flush──▶ SSTable（磁盘、按 key 排序、不可变）
├── Data file ：有序的 (key, value) 列表
├── Index file：(key, 在 data file 中的偏移量)
├── Bloom Filter：判断“本表是否含这个 key”
└── （可选）压缩信息、统计信息
CommitLog 段写满 ──▶ 归档/删除（内容已在 SSTable 或 Memtable 中）
- 为什么用”内存表 + 追加日志”（LSM 思想）：
- 顺序写远快于随机写：追加到 CommitLog 与顺序写 SSTable 都是顺序 IO，几乎不产生寻道；而 B+ 树更新需要”找到页 → 读 → 改 → 写回”，是随机 IO。讲义用一道题点出这个数量级差异：磁盘寻道比 DRAM 访问慢约 50000 倍（随机寻道 ~10 ms 量级 vs DRAM ~100 ns 量级）。
- 写路径上完全没有读：不需要先读旧值（LWW 靠时间戳，不靠比较旧值），也没有行锁——这就是”lock-free and fast”。
- 不可变的 SSTable 带来并发友好：读者不会被写者阻塞，天然支持无锁读。
- Memtable 是 write-back cache：写只进内存（加快），落盘由 CommitLog 保证持久性，而 Memtable 本身以”满即 flush”的方式回写。
持久性与 ack 的关系（补充说明）：Cassandra 的
commitlog_sync有两种模式：periodic（默认，周期性 fsync，例如每 10 s，性能高但极端掉电会丢最后一段窗口的数据）与batch（每次写都 fsync 后才 ack，持久性最强但吞吐显著下降）。“写 ack”发生在 CommitLog 追加（以及 memtable 更新）之后，这是R+W>N论证中”写成功意味着已持久化”的工程基础。- 关键假设与系统模型：假设 Memtable 与 CommitLog 都在同一台机器上（因此单机掉电 = 该副本暂时不可用），假设 SSTable 一旦写成就不再修改（因此删除必须用墓碑表达，见 9.2.19），假设磁盘的空间回收依赖 compaction（因此写放大不可避免）。
9.2.17 存储引擎（二）：读路径与 Bloom Filter
定义与目的：读路径需要把内存中的 Memtable 与磁盘上的多个 SSTable 中同一个 key 的多个版本合并，返回时间戳最新的那个。为了不把每个 SSTable 都真的读一遍，Cassandra 为每个 SSTable 配一个 Bloom Filter 与分区索引（partition index）。
直观解释（”它是什么？”）：Bloom Filter 像每本书扉页上的”关键词清单”：你想知道某本书里有没有”quorum”这个词，先扫一眼扉页——清单上没有 ⇒ 书里一定没有（省下翻书的时间）；清单上有 ⇒ 可能有，得真去翻（可能是别的词造成的巧合）。它偶尔会让你白翻一次书（假阳性），但绝不会让你漏掉一本真正含该词的书（无假阴性）。
机制图解（完整读路径）：
CLIENT ──read(K, R)──▶ COORDINATOR
│ ① token = hash(K) → 选 R 个副本
│ （优先联系“过去响应最快”的副本，例如同机架；
│ 同时后台联系其余 N-R 个副本）
┌─────────────────┴─────────────────┐
▼ ▼
┌────────────────────────────────────────────────────────────────┐
│ REPLICA R1 的本地读（R2 流程相同） │
│ ② 查 Memtable（内存，最新数据）→ 命中则得候选版本 v_mem │
│ ③ 从新到旧遍历每个 SSTable： │
│ BloomFilter.contains(K)? │
│ ├── false → 跳过（确定不含 K，无假阴性） │
│ └── true → 查 partition index 得到 offset │
│ → seek 到 offset，读出该 key 的行/列片段 │
│ ④ 把 Memtable 与各 SSTable 的候选按 timestamp 合并 → 取最新值 │
│ ⑤ 回 (digest, ts)（digest 相同即认为内容相同） │
└────────────────────────────────────────────────────────────────┘
└───────────┬───────────┘
▼
⑥ Coordinator 收齐 R 个响应 → 取 timestamp 最大的版本 → 返回 Client
⑦ 后台（或阻塞式）联系其余 N-R 个副本：
发现 timestamp 更旧 → 把最新值写回 = READ REPAIR
超时联系不上 → 标记“需要反熵修复”，由 Merkle Tree 兜底
为什么读比写慢（讲义明确指出）：一行可能被拆散在多个 SSTable 里（每次 memtable flush 产生一个新 SSTable，同一个 key 的旧版本留在老的 SSTable 中），因此读需要访问多个 SSTable，读比写慢（但仍然很快）。写只需要一次顺序追加 + 一次内存更新。
Bloom Filter 的机制与数学：
- 结构：一个长度为 $m$ 的位数组（bit array），初始全 0；$k$ 个相互独立的哈希函数 $h_1,\dots,h_k$，每个把元素映射到 $[0, m)$。
- 插入 $x$：计算 $h_1(x),\dots,h_k(x)$，把这 $k$ 个位置置 1。
- 查询 $x$：计算同样的 $k$ 个位置，若全部为 1 则返回”可能存在”，否则返回”一定不存在”。
- 假阴性（false negative）不存在——证明：假设 $x$ 曾被插入。插入时我们显式地把 $h_1(x),\dots,h_k(x)$ 这 $k$ 个位置为 1。此后这些位永远不会被清 0（Bloom Filter 只支持”加”，不支持”删”；SSTable 是不可变的，其 Bloom Filter 也因此一次构建、永不修改）。因此在任何后续查询中，这 $k$ 个位必然都是 1，查询必然返回 true。故 $x$ 的查询永不返回 false，即 $P(\text{漏报}) = 0$。$\blacksquare$
- 假阳性（false positive）与公式：插入 $n$ 个元素后，某个特定位仍为 0 的概率是 $\left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}$，故该位为 1 的概率是 $1 - e^{-kn/m}$。查询一个不在集合中的元素时，它的 $k$ 个位全部碰巧为 1 的概率是
- 最优哈希函数个数：令 $f(k) = \left(1-e^{-kn/m}\right)^k$，取对数 $\ln f = k \ln(1-e^{-kn/m})$，对 $k$ 求导并令为 0（记 $u = e^{-kn/m}$），可得 $u = 1/2$，即
也就是说：**每个元素分配约 9.6 bit 时，假阳性率约 1%**；分配越多位，假阳性率指数下降。 - **讲义给出的具体数字**：$k = m = 4$（4 个哈希函数）、$n = 100$ 个元素、位数组 $m = 3200$ bit ⇒ **假阳性率 $\\approx 0.02\\%$**。代入公式验证：$kn/m = 4\\times100/3200 = 0.125$，$e^{-0.125} = 0.8825$，$1-0.8825 = 0.1175$，$0.1175^{4} = 1.9\\times10^{-4}$ ⇒ **约 0.019% ≈ 0.02%**，与讲义一致。 - **为什么"无假阴性"是读路径正确性的关键**：读路径使用 Bloom Filter 的方式是"**若返回 false 就跳过这个 SSTable**"。这是一个**优化决策**，只有当"false ⇒ 该 SSTable 真的不含该 key"成立时才是安全的。**无假阴性恰好提供了这个安全性**：跳过的一定是空手而归的表，因此**不会漏掉任何可能含该 key 的版本**，也就**不会返回陈旧值或错误地报告 key 不存在**。反之，若允许假阴性，则 Bloom Filter 会把"存在"读成"不存在"，读路径就会漏掉最新版本——**这是一个安全性（safety）而非性能问题**。 - **假阳性率太高会怎样**：并非正确性问题，而是**性能问题**：每次查询都会去真的打开那些其实不含该 key 的 SSTable，读放大上升、延迟增加（讲义思考题："What if the false positive rate of Bloom filter is too high?" 的答案正是"读变慢，但结果仍然正确"）。Cassandra 支持 `bloom_filter_fp_chance` 参数（默认约 0.01，LCS 下 0.1），值越小内存占用越大。
- 关键假设与系统模型：假设 SSTable 不可变（Bloom Filter 不需要删除支持，因此无假阴性的证明成立）；假设 Memtable 与 SSTable 的版本可用时间戳全序比较；假设读修复的元数据（digest）足以判断版本是否相同（digest 相同即认为内容相同，存在极小的碰撞概率，工程上可接受）。
9.2.18 Compaction：STCS / LCS / TWCS
定义与目的：数据更新不断累积，SSTable 与日志需要被合并：compaction 就是合并 SSTable 的过程，即把同一个 key 的多个更新合并成一个；它在每台服务器上周期性、本地地运行。它同时承担四件事：回收墓碑、丢弃被覆盖的旧版本、减少 SSTable 数量（降低读放大）、回收磁盘空间。
直观解释（”它是什么？”）：像整理一摞草稿：同一个章节你改了 10 遍，每一遍都是一张新的纸（SSTable）。compaction 就是把这些草稿合并誊抄成一份干净的定稿，把被划掉的旧句子（旧版本）和”此处删除”的批注（墓碑，在满足条件后）扔掉。誊抄要花力气（写放大），但之后查资料就快多了（读放大降低）。
三种主要策略的图解与对比：
① SizeTieredCompactionStrategy (STCS, 默认)：把"大小相近"的 SSTable 分组，攒够
min_threshold(默认 4) 个就合并成一个大表 → 形成"金字塔"式的层
sst1 ▉ sst2 ▉ sst3 ▉ sst4 ▉ sst5 ▉▉ sst6 ▉▉ （大小分层）
└──────┬──────┘ └───┬───┘
合并 ─▶ ▉▉▉▉ (更大) 合并 ─▶ ▉▉▉▉
读放大：最坏要查每一层各 1 个表（层数 = O(log n)）
写放大：低（每个字节被重写的次数少）
空间放大：高（最大一层可能占一半空间是"待合并的重复数据"）
② LeveledCompactionStrategy (LCS)：强制分层，每层容量是上一层的 T 倍（默认 T=10）
L0: (memtable flush 出来的，允许重叠) ▉ ▉ ▉
L1: 约 10 倍 L0 容量，层内**互不重叠** ▉▉▉▉▉▉▉▉
L2: 约 10 倍 L1 容量，层内**互不重叠** ▉▉▉▉▉▉▉▉▉▉▉▉...
L3: ...
⇒ 一个 key 在每层最多只出现在**一个** SSTable 中
读放大：≈ 层数（极少，通常 1~2 个 SSTable/层）
写放大：高（每层都可能重写，约 10 倍/层 → 总计 10~20 倍）
空间放大：低（约 10%）
③ DateTiered / TimeWindowCompactionStrategy (DTCS/TWCS)：按写入时间分窗
窗口1 (00:00-01:00) ▉▉▉ 窗口2 (01:00-02:00) ▉▉▉ 窗口3 ▉▉▉
⇒ 每个窗口内合并，**窗口之间从不合并**
写放大：最低（旧窗口不再被重写）
适用：带 TTL 的时序/日志数据（数据整体过期，无需跨窗口整理）
缺点：对"更新历史数据"的负载完全不适用（会造成墓碑与旧值长期并存）
| 策略 | 合并触发 | 读放大 | 写放大 | 空间放大 | 最适合 |
|---|---|---|---|---|---|
| STCS（SizeTiered，默认） | 大小相近的 SSTable 攒够 4 个 | 中–高 | 低 | 高（可达 50%） | 写密集、通用、更新频繁但读不密集 |
| LCS（Leveled） | 每层容量超阈值后与下层重叠表合并 | 低（≈ 层数） | 高（10–20×） | 低（≈10%） | 读密集、更新频繁、延迟敏感 |
| DTCS / TWCS（时间窗口） | 同一时间窗内的表合并 | 低（只查相关窗口） | 最低 | 低 | 时序数据、日志、带 TTL 的”只写不更新”数据 |
三种”放大”的本质权衡（补充说明：可概括为 RUM 猜想）：读放大（read amplification）= 读一个 key 需要触碰多少个 SSTable；写放大（write amplification）= 每写入 1 字节，磁盘实际被写了多少字节；空间放大（space amplification）= 磁盘占用 / 逻辑数据量。三者不可能同时最优——你最多能优化其中两个。LCS 用巨大的写放大换低读放大与低空间放大；STCS 用高空间放大换低写放大；TWCS 用”不能更新历史数据”的约束换最低写放大。
墓碑回收与 compaction 的关系：删除在 SSTable 中是一个墓碑。只有当 compaction 确认”某个墓碑比它所有的旧版本都新、且已经过了
gc_grace_seconds“时，才能把这个墓碑连同它遮蔽的数据一起丢弃。若墓碑被过早丢弃而某个副本尚未看到该删除，被删数据就会”复活”。关键假设与系统模型：假设磁盘容量有限（因此必须回收）、写放大是可接受的代价（因此 compaction 可以重写数据）、副本之间最终会通过 repair 对齐（因此墓碑的回收必须以
gc_grace_seconds与 repair 周期为前提）。
9.2.19 删除与墓碑（Tombstone）
定义与目的：删除不立即移除数据：写入一个 tombstone（墓碑） 到日志中，表示”在这个时间戳上，这个单元被删除了”；最终，当 compaction 遇到墓碑并且它已经”安全”（超过
gc_grace_seconds）时，才真正删除该数据。直观解释（”它是什么？”）：SSTable 是已装订的账册，不能涂改。要在账册上”删除”一条记录，唯一的办法是在新的账册上写一句”某年某月某日，某某记录作废”，并盖一个时间戳。以后查账时，只要看到比旧记录更新的”作废”批注，就认为这条记录不存在了。这句批注就是墓碑。
机制图解：
t=100 INSERT K=alice, V=100
t=200 DELETE K=alice → 写入墓碑 TOMBSTONE(alice, t=200, local_delete_time=200)
t=250 INSERT K=alice, V=300 → t=250 > t=200，所以 alice 又"存在"了，值为 300
磁盘上的物理状态（SSTable 不可变，只能追加新的）:
SSTable#1: [alice→100 @t=100]
SSTable#2: [alice→TOMBSTONE @t=200]
SSTable#3: [alice→300 @t=250]
读时合并三个版本，按时间戳取最新 = alice→300 ✔
删除语义（无后续写的版本）:
SSTable#1: [bob→42 @t=100]
SSTable#2: [bob→TOMBSTONE @t=200]
读时最新是墓碑 → 返回 "key 不存在"（读放大：必须先读墓碑才知道它不存在！）
compaction 时: 若 now - local_delete_time > gc_grace_seconds(默认 864000s = 10 天)
→ 墓碑与 bob→42 一起被丢弃，磁盘空间才真正回收
- 墓碑积累的性能问题：
- 读放大：墓碑和数据一样要参与合并——读一个已删除的 key，必须扫描所有墓碑才能确认”它不存在”。一个被大量更新/删除的分区（如队列、频繁覆盖写的表）可能积累成千上万墓碑，导致读超时。Cassandra 用
tombstone_warn_threshold（默认 1000）与tombstone_failure_threshold（默认 100000）告警与中止； - 写放大：每次 flush 都产生新墓碑，compaction 要反复搬运它们；
- 磁盘不释放：墓碑本身占空间，且会压住（shadow）旧数据不让它被回收——删除有时会让磁盘占用先涨后降；
- range tombstone：
DELETE FROM t WHERE pk=? AND ck > x这类范围删除会产生范围墓碑，它覆盖一个区间，影响更大。
- 读放大：墓碑和数据一样要参与合并——读一个已删除的 key，必须扫描所有墓碑才能确认”它不存在”。一个被大量更新/删除的分区（如队列、频繁覆盖写的表）可能积累成千上万墓碑，导致读超时。Cassandra 用
gc_grace_seconds与”数据复活”事故（必考要点）：默认 864000 秒 = 10 天。它的含义是：墓碑至少在 10 天内不会被 compaction 丢弃，从而给”宕机超过 10 天的副本”留出通过网络修复重新学习该删除的机会。因此运维铁律是：- 每个节点必须在
gc_grace_seconds内至少完成一次 repair（否则把gc_grace_seconds调大，或更频繁地 repair）； - 不要把
gc_grace_seconds设为 0（某些教程为了”快速释放磁盘”这么建议），除非你每次删除后立刻对所有副本做 repair——否则一旦某个副本在墓碑被清理后才回来，它会把自己那份未删除的数据通过读修复/反熵传播回去，已删除的数据复活； - 对只写不删的场景（纯时序数据 + TTL），TWCS + TTL 可以避免墓碑问题，因为过期数据整体丢弃。
- 每个节点必须在
- 关键假设与系统模型：假设SSTable 不可变（因此删除必须表达为”写入一个否定事实”），假设所有副本最终都会在
gc_grace_seconds窗口内被修复，假设时钟偏差不会大到让墓碑的时间戳错误地”新于”或”旧于”它应该遮蔽的数据。
9.2.20 其他 NoSQL 系统横向对比
- HBase：Google Bigtable 是第一个”blob 式”存储系统，Yahoo! 将其开源为 HBase，今天是重要的 Apache 项目，Facebook 内部也在用。
- API：
Get/Put(row)、Scan(row range, filter)（范围查询）、MultiPut； - 与 Cassandra 的关键差别：HBase 偏好一致性胜过可用性（CP）；
- 架构：HMaster（主）+ 多个 HRegionServer（从）+ ZooKeeper；数据存在 HDFS 上；ZooKeeper 是一小群服务器运行 Zab（一个 Paxos 类共识协议），负责元数据与协调；
- 存储层次：一张表被切成多个 region（分布在多台服务器上，可复制）；ColumnFamily = 一组查询模式相似的列；每个 (ColumnFamily, region) 组合对应一个 Store；每个 Store 有一个 MemStore（内存更新，满则 flush）与多个 StoreFile（即 HFile，其格式源自 Bigtable 的 SSTable）；
- HFile 的键结构：
Key length \| Value length \| Row length \| Row \| Column Family length \| Column Family \| Column Qualifier \| Timestamp \| Key type，即每一行数据都自带 row、列族、列限定符、时间戳与类型——这清楚表明了”键 = 行键 + 列族 + 列 + 时间戳“这一列族模型的核心； - 强一致的来源：Write-Ahead Log（HLog）——先写 HLog，再写 MemStore；崩溃恢复时重放 HLog（用时间戳判断数据库相对日志的位置）把编辑重新加到 MemStore；
- 跨数据中心复制：单个 Leader（Master）集群 + 若干 Follower（Slave）集群复制同样的表；Leader 同步地把 HLog 发给 Follower；集群间协调通过 ZooKeeper（它可以像文件系统一样存控制信息，例如
/hbase/replication/state、/hbase/replication/peers/<peer>、/hbase/replication/rs/<hlog>）。
- API：
HBase 架构（讲义的层次）
Client ──▶ HMaster ◀──▶ Zookeeper (Zab, Paxos-like)
│
├──▶ HRegionServer ─┬─ HRegion ─┬─ Store (ColumnFamily A) ─┬─ MemStore
│ │ │ └─ StoreFile(HFile)…
│ │ └─ Store (ColumnFamily B) ─┬─ MemStore
│ │ └─ StoreFile(HFile)
│ └─ HLog（先写日志再写 MemStore）
└──▶ HRegionServer ── … │
▼
HDFS
Bigtable：GFS + Chubby（锁服务） + SSTable 的组合；数据模型是列族（column family）下的稀疏多维有序映射
(row, column, timestamp) → value；表按 tablet（行区间）水平切分并由 tablet server 服务；HBase 是它在开源世界的直系后代。- MongoDB（讲义版本 2015，读偏好/写关注更新于 2016 v3.2）：文档型 NoSQL。
- 数据模型：以 BSON（Binary JavaScript Object Notation） 文档存储数据，例如
{ name:"travis", salary:30000, designation:"Computer Scientist", teams:["front-end","database"] }；一组共享同一索引的相关文档构成一个 collection（集合）； - 查询：
db.employee.find({salary:{$gt:18000}}, {name:1}).sort({salary:1})—— 集合、条件、投影（projection）、修饰符（modifier）四部分清晰对应；支持insert/update（含$set、$inc、multi:true）/remove；支持count、skip、limit等聚合命令； - 部署：数据按 shard key 切成 chunk（可用 hash 或范围分区）；shard = 一组 chunk，被分配给一个副本集（replica set）；副本集通常由 3 个 mongod 组成，成员互为镜像，一个是 primary，其余是 secondary；Router（mongos）接收客户端查询并路由到正确的副本集；Config server 保存集合级元数据；
- 复制：用 oplog（操作日志） 做数据同步：oplog 维护在 primary，增量连续/定期传到 secondary；需要时通过Leader 选举协议选出 primary；有些 mongod 不存数据但可以投票，称为 Arbiter（仲裁者）；
- 可调的两个旋钮：
- Read Preference（读偏好）：默认 primary；另有 primaryPreferred、secondary、nearest、majority——帮助降低延迟、提高吞吐，但从 secondary 读可能取到陈旧数据；
- Write Concern（写关注）：0（不确认）/ 1（primary 确认）/ majority——写关注越弱，写越快；
- 写操作性能：Journaling（预写日志，journal 可以是内存映射的）提供持久性；索引意味着每次写都必须更新与该 collection 关联的每一个索引；
- 均衡：chunk 会随时间变得大小不一 —— Splitting（chunk 达到上界就分裂）与 Balancing（分布不均时在 shard 间迁移 chunk）；
- 一致性：既可强一致也可最终一致，取决于读偏好与写关注的组合；从 CAP 看，”在强一致配置下，发生分区时 MongoDB 会变为写不可用，从而保证一致性”（即 CP 行为）。
- 数据模型：以 BSON（Binary JavaScript Object Notation） 文档存储数据，例如
Redis：内存键值存储（补充说明，讲义未展开）。单线程执行命令、丰富的数据结构（string/list/hash/set/zset/stream）、主从异步复制（可用
WAIT做有限同步）、Redis Cluster 用 16384 个哈希槽分片，节点间通过 gossip（cluster bus）交换成员与槽位信息，故障转移由副本提升完成。CAP 上偏 AP：异步复制意味着故障切换时可能丢失最后一批写；Redis Sentinel 提供监控与自动故障转移。定位是缓存/低延迟结构服务，而不是持久化的事实来源。- DynamoDB / Riak（Dynamo 论文的直系后代）：Amazon 的 Dynamo（2007）是 Cassandra 的直接思想来源，它的每一项机制都能在本章前面的小节里找到对应：
- 一致性哈希 + 虚拟节点做分区（对应 9.2.8）；
- N/R/W 可调一致性 + sloppy quorum（宽松 quorum）：写不必落在”偏好列表（preference list）”的前 N 个节点上，若不可达就写到环上后继节点并附一个 hint（这正是 hinted handoff 的原始形式，对应 9.2.12）；
- 向量时钟（vector clock）做冲突检测：Dynamo 与 Riak 不用 LWW 丢弃冲突，而是检测出并发版本并把冲突交给应用解决（对应 Lecture 12；Riak 后来也支持 CRDT 与 dotted version vector）；
- Merkle Tree 反熵做副本对齐（对应 9.2.14）；
- gossip 成员管理（对应 9.2.15）。
- 横向对比表：
| 系统 | 数据模型 | 一致性模型 | CAP 定位 | 复制方式 | 代表场景 |
|---|---|---|---|---|---|
| Cassandra | 列族/宽列（分区键+聚簇键，稀疏） | 可调（默认最终一致，可用 $R+W>N$ 调成强一致） | AP | 无主、任意节点协调、N 副本、hinted handoff + read repair + Merkle repair | 写密集、跨 DC、时序、消息、推荐特征 |
| HBase | 宽列（row key + column family + qualifier + ts） | 强一致（行级原子） | CP | 有主：HMaster + ZooKeeper(Zab)，HLog 同步复制到从集群 | HDFS 之上的随机读写、大表扫描 |
| Bigtable | 稀疏多维有序映射（row, col, ts） | 强一致（单行） | CP | tablet + Chubby 锁 | Google 内部大规模结构化数据 |
| MongoDB | 文档（BSON） | 可调（读偏好 + 写关注） | 强配置下 CP，弱配置下偏 AP | 副本集（primary/secondary + oplog），sharding | 内容、目录、快速迭代的产品数据 |
| Redis | 内存键值 + 丰富结构 | 异步复制 ⇒ 弱一致 | AP | 主从异步 + Cluster 槽位 + gossip | 缓存、会话、排行榜 |
| DynamoDB / Riak | 键值（Riak 支持 CRDT） | 最终一致（Riak 用向量时钟暴露冲突） | AP | sloppy quorum + hinted handoff + Merkle anti-entropy + gossip | 购物车、高可用键值 |
- 关键假设与系统模型：这些系统的分歧只有一条主轴——面对分区时，是”拒绝服务以保一致（CP）”还是”继续服务并容忍不一致（AP）”。所有具体的架构差异（有无 master、有无共识、是否暴露冲突、是否可调）都是这条主轴的派生结果。
9.3 算法伪代码与正确性分析
本节给出五份伪代码：Cassandra 的写路径与读路径（含读修复）、$R+W>N$ 的强一致性正确性论证（含并发写与 LWW 的完整定义）、Merkle Tree 的构造与差异比较、Φ 累加故障检测器。所有伪代码都采用统一的系统模型假设，逐条给出安全性、活性与复杂度分析。
算法 9.3.1：Cassandra 写路径 write(key, value, ts, W)
假设与系统模型
- 系统组成：$N_s$ 个节点组成一个环（单 DC 场景），每个 key $k$ 的副本集合为 $\mathcal{R}(k)$，$\vert \mathcal{R}(k)\vert = N$（副本因子）。
- 故障模型：crash-recovery（节点可能崩溃后重启，重启后磁盘数据保留，内存中的 Memtable 丢失一部分但 CommitLog 保留）；无拜占庭故障。协调者与被写入副本都可能崩溃。
- 通道假设：点对点通道可能丢失、延迟、乱序（异步网络）；使用超时判断”副本不可用”。客户端与协调者之间的通道是可靠的（TCP）。
- 时钟：各节点本地时钟不同步；写时间戳 $ts$ 由客户端/协调者在发起写时指定，并由所有副本原样使用（副本不用自己的本地时间覆盖它）——这是 LWW 收敛的前提。
- 持久性假设：一个副本报告 “ack” 意味着该 $(k,v,ts)$ 已经追加到 CommitLog（
commitlog_sync=batch时还要完成 fsync），并已更新 Memtable。 - 参数：$W \le N$ 为写一致性级别；失败副本由提示移交（hinted handoff）兜底。
伪代码
# ============ 客户端 ============
write(k, v, W):
ts <- now_us() # 客户端生成写时间戳（微秒）
c <- pick_any_node() # 任意节点都可以当协调者
send WRITE_REQ(k, v, ts, W, reply_to=client) to c
wait for WRITE_ACK(k, results) from c
return (count(results == OK) >= W) # 达到 W 即成功
# ============ 协调者 c ============
upon receiving WRITE_REQ(k, v, ts, W, reply_to) from client:
ks <- coord_kspace
tok <- partitioner.hash(k) # Murmur3 / Random
replicas <- replica_placement(tok) # N 个节点，按 9.2.8/9.2.9 规则
acks <- 0 ; hints <- []
for each r in replicas: # 并行发送（不是只发 W 个！）
send WRITE_DATA(k, v, ts, ks) to r # 异步、并行
wait until (acks >= W) or (all replicas responded or timed out):
upon receiving WRITE_ACK(k) from r:
acks <- acks + 1
upon timeout for r (replica unreachable):
hints.add( (target = r, ks, k, v, ts) ) # 记 hint，见下面 replay
# 若 W 已达：立刻回复；剩下未回的副本继续在后台完成
if acks >= W:
send WRITE_ACK(k, results=replicate(OK, acks)) to reply_to
else:
send WRITE_ACK(k, results=FAIL) to reply_to
# ============ 协调者 c：提示移交 ============
upon detecting (via gossip) that node r transitioned to NORMAL:
if max_hint_window not exceeded for r: # 默认 3 小时
for each hint h in local_hints where h.target == r:
send WRITE_DATA(h.k, h.v, h.ts, h.ks) to r # 重放：用原来的时间戳！
on WRITE_ACK: remove h from local_hints
else:
# 超过 hint 窗口：放弃 hint，等待 anti-entropy repair 兜底
drop hints for r
# ============ 副本 r ============
upon receiving WRITE_DATA(k, v, ts, ks) from c:
append_to_commitlog(ks, k, v, ts) # ① 顺序写磁盘，用于崩溃恢复
memtable[ks].put(k, v, ts) # ② 更新内存有序表（write-back cache）
send WRITE_ACK(k) to c
# 注意：这里不做锁、不读旧值、不检查冲突 —— 冲突留给读时的 LWW 解决
upon restart after crash:
replay_commitlog_into_memtable() # 恢复内存中丢失的未 flush 数据
算法逻辑解说（用一个具体数值例子走一遍） 设 $N=3$，副本 $\mathcal{R}(K13)=\{N3, N2, N4\}$（token(K13)=331，见 9.2.8 的环），客户端写 K13 = "v1"，时间戳 $ts=1000$，要求 $W=2$。
- 客户端连到任意节点（比如 N1），$N1$ 成为协调者；
- N1 算 token、得到副本集合 $\{N3,N2,N4\}$，并行发三份
WRITE_DATA； - N3 先回 ack（已写 CommitLog + Memtable）→
acks=1；假设 N4 此刻宕机，N1 对它超时 → 记下hint(target=N4, K13, "v1", ts=1000)； - N2 回 ack →
acks=2 = W→ N1 立刻回复客户端”写成功”； - 客户端认为写已完成，尽管 N4 尚未持有该值；
- 稍后 gossip 发现 N4 回到 NORMAL，N1 重放 hint，把
(K13,"v1",ts=1000)发给 N4 —— 注意用的是原始时间戳 1000，不是重放时刻的时间，否则会导致错误的时间序； - 若 N4 在 3 小时内一直没回来，hint 被丢弃，只能靠反熵修复补齐。
正确性论证
- 安全性（Safety）：写操作只有在 $W$ 个副本已持久化该版本（已写 CommitLog）后才返回成功。若 $W \le \vert \text{alive replicas}\vert $，写成功；否则返回 FAIL，客户端明确知道写没生效（不会出现”报成功但完全没写”的情况，因为 ack 的语义被严格定义）。注意：这不是线性一致性的安全性，只是”写成功的语义明确”这一弱安全性。
- 活性（Liveness）：只要 $\mathcal{R}(k)$ 中至少有 $W$ 个节点存活且网络可达，写必然在有限时间内返回成功；即使存活的副本少于 $W$，协调者也会在等待超时后返回 FAIL（不会无限等待）。配合一致性级别
ANY，协调者可以容忍全部副本不可用（把写缓存在本地 hint 中）——这就是”always writable“。 - 不变量（Invariant）：所有副本对同一 $(k, ts)$ 存的是字节完全相同的值（协调者转发原始 $v$ 与 $ts$，副本不做任何改写），因此 LWW 的裁决函数在任意副本上对同一组候选版本给出同一个赢家——这是收敛性（convergence）的前提。
复杂度
- 消息复杂度：每次写 $O(N)$ 条
WRITE_DATA/WRITE_ACK（$N$ 为副本因子；注意 Cassandra 向所有 $N$ 个副本写，而不只是 $W$ 个，因此 $N$ 而非 $W$ 决定消息量）。加上 hinted handoff 的重放，长期总量仍是每个写 $O(N)$。 - 时间（延迟）复杂度：客户端看到的是第 $W$ 个最快 ack 的到达时间，即 $W$ 阶顺序统计量 $T_{(W)}$，不是最慢副本的时间。这正是 $W$ 越小延迟越低的原因；$W=N$（ALL）时延迟 $=\max_r T_r$（木桶效应）且任一副本故障即写失败。
- 空间复杂度：每个副本 $O(\text{CommitLog 段大小} + \text{Memtable 大小})$；协调者额外承担 $O(\text{hint 队列长度})$，未受控的 hint 队列是可用性风险（见 9.5）。
算法 9.3.2：Cassandra 读路径与读修复 read(key, R)
假设与系统模型
- 与 9.3.1 相同的节点、故障与通道模型。
- 参数：$R \le N$ 为读一致性级别；副本持有的是
(value, timestamp)或等价的(digest, timestamp)。 - 版本可比较：任意两个版本可用 $(ts, value\_bytes)$ 的字典序比较出”更新”，且比较结果在所有节点上一致（LWW 的确定性要求）。
- 读修复模式：
blocking（读时同步修复差异副本后再返回）或async（返回后后台修复）。伪代码同时给出两条路径。
伪代码
# ============ 客户端 ============
read(k, R):
c <- pick_any_node()
send READ_REQ(k, R, reply_to=client) to c
wait for READ_RESP(k, value, ts_m) from c
return (value, ts_m)
# ============ 协调者 c ============
upon receiving READ_REQ(k, R, reply_to) from client:
tok <- partitioner.hash(k)
replicas <- replica_placement(tok) # N 个副本
# ① 优先联系"过去响应最快"的副本（例如同机架），先凑齐 R 个
fast <- sort_by_past_latency(replicas)
sent <- fast[0 .. R-1] ; rest <- the remaining N-R replicas
responses <- {}
for each r in sent: send READ_DIGEST(k) to r # 先要 digest（省带宽）
for each r in rest: send READ_DIGEST(k) to r # 后台也联系其余副本
wait until |responses| >= R (or all responded / timed out):
upon receiving READ_RESP(k, digest, ts) from r:
responses.add( (r, digest, ts) )
if mode == blocking and mismatch(digest, max_ts_digest_of(responses)):
send READ_DATA(k) to r # 拉取完整值以修复
pick (v_m, ts_m) <- the response with the largest (ts, value_bytes)
send READ_RESP(k, v_m, ts_m) to reply_to # ② 先返回给客户端（低延迟）
# ③ 后台读修复（async 模式；blocking 模式在返回前已完成）
for each response (r, digest, ts) in responses where (ts, digest) != (ts_m, digest_m):
send FORCE_READ_REPAIR(k, v_m, ts_m) to r # 把最新值写回落后副本
for each r in replicas that timed out or errored:
mark r as "needs anti-entropy repair" # 交给 Merkle tree 兜底
# ============ 副本 r ============
upon receiving READ_DIGEST(k) from c:
(v, ts) <- local_read(k) # 见下面的 local_read
send READ_RESP(k, digest(v), ts) to c
upon receiving FORCE_READ_REPAIR(k, v_m, ts_m) from c:
# 读修复 = 一次普通写，用原始时间戳；走 CommitLog + Memtable
append_to_commitlog(ks, k, v_m, ts_m)
memtable[ks].put(k, v_m, ts_m)
# ============ 副本 r：本地读（Memtable + SSTable + Bloom Filter）============
local_read(k):
candidates <- []
if memtable has k: candidates.add( memtable.get(k) ) # 内存里的最新数据
for sst in sstables_from_newest_to_oldest: # 从新到旧
if not bloom_filter[sst].contains(k):
continue # 无假阴性 ⇒ 可安全跳过
off <- partition_index[sst].lookup(k) # 索引定位 offset
if off != NOT_FOUND:
candidates.add( read_at_offset(sst, off) ) # 读该 key 的行/列片段
return max_by(candidates, key = (ts, value_bytes)) # LWW：合并多个版本
算法逻辑解说（数值例子） 设 $N=3$，副本 $\{R1,R2,R3\}$，$R=2$（QUORUM 在 $N=3$ 时也是 2）。
- 此前算法 9.3.1 的写已让 $R1$ 和 $R2$ 持有
K13="v1" @ts=1000，而 $R3$ 因宕机错过了（hint 还没重放，或者 hint 已丢失）。 - 客户端发起
read(K13, R=2)，协调者按历史延迟优先联系 $\{R1,R2\}$：- $R1$ 返回
(digest("v1"), ts=1000)；$R2$ 相同 ⇒ 两个响应都到齐，$R=2$ 达成； - 协调者取最大时间戳版本 ⇒
("v1", 1000)，立即返回给客户端；
- $R1$ 返回
- 后台协调者联系 $R3$：$R3$ 返回
(digest("v0"), ts=900)—— 与最新值不同 ⇒ 发起读修复，把("v1", ts=1000)写回 $R3$； - 下一次读时 $R3$ 已一致。这就是”读操作把副本推向收敛”。
- 若此时读用 $R=1$ 且协调者恰好选了 $R3$（例如它响应最快），则客户端会读到陈旧的 “v0” —— 这就是 $(W=2,R=1)$ 在 $N=3$ 下 $R+W=3 \le N$ 时可能读到旧值的直观例子（等下：$W=2,R=1$，$R+W=3 = N$，不满足 $>N$，所以确实可能读到旧值）。必须用 $(W=2,R=2)$ 或 $(W=3,R=1)$ 才能避免。
正确性论证
- 安全性（Safety，在 $R+W>N$ 时）：见 9.3.3 的完整证明。简言之，读集合与最近一次成功写的写集合必然相交，而协调者取”时间戳最大”的版本，因此返回值的时间戳不旧于该次写。
- 安全性（Bloom Filter 环节）：跳过 SSTable 的判定
bloom_filter.contains(k) == false⇒ 该 SSTable 确实不含 $k$（无假阴性，证明见 9.2.17），因此”跳过”不会遗漏任何候选版本，local_read返回的 max 就是该副本本地真正的最新版本。 - 收敛性（Convergence）：每次读都会（在 async 模式的后台、或 blocking 模式的返回前）把最新版本推给所有陈旧的副本；结合周期性的反熵修复，”读修复覆盖到的 key”与”repair 覆盖到的区间”共同保证：一旦没有新的写，所有副本的值最终收敛到同一个 $(ts_{max}, v)$。收敛的前提是 LWW 的裁决函数在所有节点上确定一致（同 9.3.1 的不变量）。
- 活性（Liveness）：只要 $\mathcal{R}(k)$ 中至少有 $R$ 个副本可达，读就会在有限时间内返回（协调者对所有未响应的副本使用超时，不会无限等待）。$R=\text{ALL}$ 时任一副本不可达即读失败——可用性最低。
- 已知的弱安全性（必须诚实指出）：$(R,W)$ 不满足 $R+W>N$ 时，读可能返回陈旧值；async 读修复期间返回的值可能仍是陈旧的（因为修复发生在返回之后）；读修复在并发写同时发生时可能把一个”中间版本”当作最新版本（因为它在读的那一瞬间确实是时间戳最大的）——这属于 LWW 语义下的合法行为，但可能静默丢弃另一个并发写（见 9.3.3 的讨论）。
复杂度
- 消息复杂度：协调者向所有 $N$ 个副本发请求（$R$ 个在关键路径上、$N-R$ 个在后台），加读取回包与读修复写回，总计 $O(N)$；若使用 digest 机制，关键路径上的数据传输量从”$R$ 份完整值”降到”$R$ 份小 digest + 1 份完整值”。
- 延迟复杂度：客户端延迟 $= T_{(R)}$（第 $R$ 快的副本）$+$ 一轮 digest 交换；
blocking读修复会把延迟抬到 $\max_r T_r$，async则不受影响。 - 本地读的复杂度：需检查 Memtable + 所有候选 SSTable。设 SSTable 数为 $S$，Bloom Filter 每次检查 $O(k)$ 次哈希（$k$ 通常 10 以内）——这一步把”要不要真的打开这个 SSTable”从 $O(\log n)$ 的索引查找降为 $O(k)$ 的位检查。真正被打开的 SSTable 数即”读放大“，STCS 下最坏为 $O(S)$，LCS 下为 $O(\text{层数})$。
算法 9.3.3：$R+W>N$ 强一致性的正确性论证（含并发写与 LWW）
这一节不是”伪代码”，而是一个完整的分析性论证——它是本章的理论核心。
假设与系统模型（形式化）
- 副本集合 $\mathcal{R} = \{r_1,\dots,r_N\}$，$\vert \mathcal{R}\vert = N$；
- 写操作 $w$ 具有唯一版本标识 $\text{ver}(w) = (ts_w, v_w)$；写 $w$ 的写集合 $S_W(w) \subseteq \mathcal{R}$ 是”在 $w$ 返回成功之前确认已持有 $w$ 的副本集合”，且按定义 $\vert S_W(w)\vert \ge W$（写成功的语义）；
- 读操作 $r$ 的读集合 $S_R(r) \subseteq \mathcal{R}$ 是”其响应被协调者计入回答的副本集合”，$\vert S_R(r)\vert \ge R$；
- 裁决函数 $\text{win}(V) = \arg\max_{(ts,v) \in V} (ts, v)$（按 $(ts, \text{value\_bytes})$ 的字典序取最大），它确定、可交换、可结合；
- 假设副本集合在讨论期间不变（没有重新平衡把 key 搬到别的节点）；假设没有静默数据损坏（磁盘返回的就是写入的内容）；假设写失败的副本不会持有该版本（即”部分写”不会以新版本的形式残留——Cassandra 中写失败的副本要么没写、要么写了完整的 $(k,v,ts)$，因为写是单条记录的原子追加）。
论证一：$R+W>N \Rightarrow$ 读不会遗漏最近一次成功的写（read-write 冲突的排除）
定理 T1（Quorum Intersection）:
若 R + W > N，则对任意一次成功的写 w 与任意一次读 r（在 w 返回之后发起），
有 S_W(w) ∩ S_R(r) ≠ ∅。
证明:
1. S_W(w) ⊆ R 且 S_R(r) ⊆ R （都取自同一副本集合）
2. |S_W(w)| ≥ W, |S_R(r)| ≥ R （写成功/读达成的定义）
3. |S_W ∪ S_R| ≤ |R| = N （并集不超过全集）
4. 由容斥: |S_W ∩ S_R| = |S_W| + |S_R| - |S_W ∪ S_R|
≥ W + R - N
> 0 （由前提 R + W > N）
5. 故 |S_W ∩ S_R| ≥ 1，即存在副本 ρ ∈ S_W ∩ S_R。 ∎
推论 C1（读的返回值不旧于最近一次成功的写）:
由 T1，读集合中存在副本 ρ 持有 w 的版本 ver(w)。
读在 ρ 处读到（至少）ver(w)；协调者取 max，
故返回的版本 ver_read 满足 ver_read ≥ ver(w)（按 (ts, value_bytes) 的字典序）。
∎
这一步的关键假设是”写成功表示 $W$ 个副本真的持有了这个版本”。若使用一致性级别 ANY（协调者把写缓存在本地 hint 就算成功），则 $S_W(w)$ 中的节点可能只有 hint、没有数据，T1 的前提被打破，$R+W>N$ 不再保证强一致。这是”$ANY$ + $ONE$ 会读到旧值”的根本原因。
论证二：为什么还需要读修复来处理并发写
T1/C1 只保证”读不旧于最近一次成功的写“。它没有保证有多个并发写时读者拿到的是”最后被发起的那一个”。考虑两个并发写 $w_1, w_2$（客户端 A、B 同时在写同一个 key，互不知情）：
客户端 A: write(K, "A", ts=1000) 客户端 B: write(K, "B", ts=1001)
两者都要求 W=2，N=3，副本 {R1,R2,R3}
网络乱序导致：
w1 到达 R1, R2 → S_W(w1) = {R1,R2}
w2 到达 R2, R3 → S_W(w2) = {R2,R3}
最终各副本的持有状态：
R1: "A" @1000 R2: "B" @1001 (两个都到过，取时间戳大的) R3: "B" @1001
此时 read(K, R=2):
若读集合为 {R1,R2}: max = "B"@1001 ✔ 与 w2 一致
若读集合为 {R1,R3}: max = "B"@1001 ✔ 与 w2 一致
若读集合为 {R2,R3}: max = "B"@1001 ✔ 与 w2 一致
本例中 B 的时间戳更大，所以所有读都看到 B —— 但这是"时间戳决定的"，
不是"因果顺序决定的"：如果 A 的钟快 10 ms（ts_A=1010 尽管 A 后写），
那么 LWW 会让**先写的 A** 覆盖**后写的 B**，而 B 的写已经"成功"返回给客户端了。
由此得出三条重要结论：
- 读修复（与反熵）负责把”读集合之外”的副本也拉齐：T1 只约束”被读到的 $R$ 个副本”，而未参与本次读的 $N-R$ 个副本可能仍持有旧版本。读修复在后台联系它们并写回最新值，使”最近一次读”顺便完成一次收敛；若没有读修复，陈旧副本只能靠周期性的反熵修复才能对齐，收敛窗口会长得多。因此在 $(R,W)$ 满足 $R+W>N$ 时，读修复的作用是提高收敛速度与降低长期不一致的概率，而不是”弥补 quorum 的缺陷”。
- 并发写的裁决完全交给时间戳：LWW 在 $R+W>N$ 下仍然会丢弃一个版本——$w_1$ 在 R1 和 R3 上被 $w_2$ 覆盖（或反之）。这不是 bug，而是设计选择：系统选择”用不可靠的物理时钟做全局序”，从而避免了任何共识开销。代价是：若时钟偏差超过两个写的真实时间差，”后写的”会被”先写的”覆盖，数据静默丢失（详见下面的风险分析）。
- $W>N/2$ 的第二重作用：若 $W > N/2$，则任意两次成功写的写集合也必然相交（同样的鸽巢论证），因此在至少一个副本上，两个版本会真正”碰面”并交由 LWW 裁决——这保证了”后一个写者若先读过（read-modify-write），它的写一定建立在最新值之上”（避免了”丢更新”链），这是 $R+W>N$ 单独不能提供的保证。
LWW 的完整定义（”last write wins”到底是什么意思）
裁决函数 win(V) 对候选版本集合 V 的定义:
win(V) = argmax_{x in V} ( x.ts , x.value_bytes )
↑ 第一关键字：写时间戳（微秒，由客户端/协调者指定）
↑ 第二关键字：值的字节序（tie-break）
其中字节序比较是确定性的（例如按无符号字节逐位比较），
因此 win(V) 是一个**确定性的全序极大元**：任何副本、任何时刻
用同一组 V 都会算出同一个赢家 ⇒ 收敛性得到保证。
- tie-break 的必要性：如果只按 $ts$ 比较，两个并发写可能拿到完全相同的时间戳（同一微秒），此时若各副本”各自决定”赢家，就会永久不一致（发散）。加入 value 的字节序作为第二关键字后，所有副本独立计算的结果必然相同——这是”用确定性函数替代共识“的关键技巧。
- LWW 的数据丢失风险（为什么 Riak/Dynamo 改用向量时钟）：LWW 无法区分”后来的写”与”并发写”。它的全部信息只有一个标量时间戳，因此：
- 场景 A（真正并发、需要应用裁决）：两个用户同时往购物车里加商品，LWW 会丢掉其中一件；而向量时钟能识别出”这两个版本是并发的（不可比）”，从而把两个版本都返回给应用，让应用做”合并购物车”这样的语义操作；
- 场景 B（时钟偏差）：A 的钟慢 5 s，A 的写虽然晚 1 s 发生，时间戳却更小，于是被丢掉——而系统没有任何迹象表明数据丢了；
- 因此 Riak / Dynamo 选择向量时钟：它不是”选一个新赢家”，而是检测冲突并把冲突暴露给应用（”siblings”），把”丢掉哪个版本”的决定权交还给知道业务语义的人；代价是客户端复杂度上升（必须写合并函数）、元数据膨胀（每个版本携带一个向量）、墓碑与向量时钟的垃圾回收变得复杂。这是一个典型的“把不确定性推给上层” vs “静默选择一个版本” 的架构权衡（详见 Lecture 12）。
论证三：Bloom Filter 无假阴性（读路径优化的安全性基础）
定理 T2（Bloom Filter 无假阴性）:
设 BF 由 n 次 insert 操作构建（每次插入元素 x 时把 h_1(x)..h_k(x) 置 1），
构建过程中**没有任何位被清 0**。则对任意曾插入的元素 x，
query(x) 必然返回 true。
证明:
1. insert(x) 执行后，位 h_1(x),...,h_k(x) 均为 1。 （插入的定义）
2. 设此后到 query 之间共发生 m 次插入。每次插入只把某些位**置 1**，
不改变任何已为 1 的位（| 运算，无删除操作）。
3. 归纳: 位 h_i(x) 在所有后续时刻保持为 1。 （由 2 的单调性）
4. query(x) 检查 h_1(x),...,h_k(x)，由 3 全部为 1 ⇒ 返回 true。 ∎
推论 C2（跳过 SSTable 是安全的）:
当 bloom_filter[sst].contains(k) == false 时，由 T2 的逆否命题，
k **从未**被插入过该 filter；而该 filter 正是为 sst 中的所有 key 构建的，
因此 k ∉ sst。跳过一个不含 k 的 SSTable 不会遗漏任何版本。 ∎
注意: 单调性（只置 1 不清 0）与"不可变的 SSTable"是同一个设计决定的
—— 正因为 SSTable 不可变，filter 才不需要支持删除，T2 才成立。
复杂度与保证汇总
| 结果 | 条件 | 保证强度 | 代价 |
|---|---|---|---|
| T1 / C1 | $R+W>N$，写成功语义严格 | 单 key 强一致（读不旧于最近一次成功的写） | 延迟 $\ge T_{(R)}$；$W$ 越大可用性越低 |
| $R+W \le N$ | — | 最终一致（靠 read repair + anti-entropy 收敛） | 可能读到陈旧值，无时间上界保证 |
| 并发写 | LWW（确定性裁决） | 收敛到同一版本，但可能静默丢弃一个写 | 数据可能无告警地丢失 |
| T2 / C2 | SSTable 不可变 + 单调置位 | 读路径优化不影响正确性 | 假阳性造成额外的 SSTable 打开（读放大） |
消息/时间/空间复杂度：论证本身不引入额外通信；实现 $R+W>N$ 的代价是把每次读的等待时间从 $T_{(1)}$ 提高到 $T_{(R)}$、每次写的等待时间从 $T_{(1)}$ 提高到 $T_{(W)}$，并把可容忍故障数从”$N-1$ 个副本”降到”$\min(N-R, N-W)$”（写要求至少 $W$ 个副本存活 ⇒ 最多容忍 $N-W$ 个副本故障；同理读最多容忍 $N-R$ 个）。
算法 9.3.4：Merkle Tree 的构造与差异比较（反熵修复）
假设与系统模型
- 两个副本 $A, B$ 持有同一个 token range $\mathcal{K}$ 的数据，且数据按同一个全序排列（相同的分区器与 schema ⇒ 相同的 key 顺序），否则算法前提被破坏（见”前提约束”）。
- 叶子语义：每个叶子对应若干个连续 key 的哈希（Cassandra 中由
partition keys per leaf控制）；哈希函数 $H$ 抗碰撞（工程上用 MD5/xxHash 等）。 - 数据快照：树在同一个快照（snapshot）上构建，构建期间该区间的数据视图不变。
- 故障模型：crash-recovery；允许一方拥有另一方没有的 key（漏写），也允许同一 key 有不同版本。
- 裁决：同一 key 的不同版本由 $(ts, value\_bytes)$ 的 LWW 裁决（同 9.3.3）。
伪代码
# ============ 构造 Merkle Tree ============
build_merkle(range, keys_per_leaf):
ordered <- sorted_keys(range) # 前提 1：两副本必须用同一个顺序
leaves <- []
for i in 0, keys_per_leaf, 2*keys_per_leaf, ... :
block <- ordered[i : i + keys_per_leaf]
leaf_hash <- H( concat( H(key_j, value_hash(key_j)) for key_j in block ) )
leaves.add( leaf_hash )
level <- leaves
while |level| > 1: # 自底向上，两两合并（可推广到 b 叉）
next <- []
for i in 0, 2, 4, ... :
if i+1 < |level|:
next.add( H( level[i] || level[i+1] ) )
else:
next.add( level[i] ) # 奇数个节点时直接上提
level <- next
return Tree(root = level[0], levels = [leaves, ..., level], ordered_keys = ordered)
# ============ 差异比较（递归下降）============
compare(node_A, node_B, path, stats):
stats.nodes_visited <- stats.nodes_visited + 1 # 用于统计 O(log n) 的访问量
if node_A.hash == node_B.hash:
return [] # 子树完全一致，剪枝
if node_A.is_leaf and node_B.is_leaf:
# 到达叶子：逐 key 精确比较
diffs <- []
for key in node_A.block_keys ∪ node_B.block_keys:
(vA, tsA) <- A.get(key) # 可能为 MISSING
(vB, tsB) <- B.get(key) # 可能为 MISSING
if (tsA, vA) != (tsB, vB): # 内容或时间戳不同
winner <- argmax_{(ts,v)} { (tsA,vA), (tsB,vB) } # LWW 裁决
loser <- the other side
diffs.add( (key, winner, loser) )
return diffs
diffs <- []
for each child pair (ca, cb) in zip(node_A.children, node_B.children):
diffs.extend( compare(ca, cb, path + [child_index], stats) )
return diffs
# ============ 完整反熵修复流程 ============
anti_entropy_repair(A, B, ranges, keys_per_leaf):
for range in ranges: # 通常并行处理多个 range
treeA <- build_merkle(range, keys_per_leaf) # 在快照上构建
treeB <- build_merkle(range, keys_per_leaf)
if treeA.root.hash == treeB.root.hash:
log("range 一致，跳过（O(1) 次哈希交换）") # 最好情况
continue
stats <- Stats()
diffs <- compare(treeA.root, treeB.root, [], stats)
log("访问了 %d 个树节点，发现 %d 处差异" % (stats.nodes_visited, len(diffs)))
for (key, winner, loser) in diffs:
loser.put(key, winner.value, winner.ts) # 用原始时间戳写回（LWW）
# 注意：墓碑必须参与比较，且只有在 now - tombstone.local_delete_time
# > gc_grace_seconds 时才允许在 compaction 中被丢弃
算法逻辑解说 以 9.2.14 的图为例：区间内有 4 个 key，keys_per_leaf = 1，树高 2（4 个叶子 → 2 个中间 → 1 个根）。
- 两边各自构建树（各 7 个节点，$O(n)$）；
- 交换根哈希：不同 ⇒ 第 1 次节点访问（root）；
- 交换两个中间节点的哈希，发现左半相同、右半不同 ⇒ 第 2、3 次访问，左半整棵子树被剪枝；
- 进入右半子树，比较它的两个叶子：$h(k_3)$ 相同、$h(k_4)$ 不同 ⇒ 第 4、5 次访问；
- 定位到 $k_4$，读取两边的 $(v, ts)$，LWW 裁决后把赢家写到输家一侧；
- 总访问节点数 5，而朴素全量比较需要检查 4 个 key 的数据并传输它们——本例规模太小看不出优势，但当区间有 $10^6$ 个 key、只有 1 个不同时，访问量是 $O(\log n) \approx 20$ 个节点哈希 + 1 个 key 的数据，而全量比较要传输 $10^6$ 个 key —— 差异是 5 个数量级。
正确性论证
- 安全性（不会误报”一致”）：若某 key 的版本在两副本不同，则从该 key 到根的路径上至少有一条路径上的节点哈希不同（否则根哈希相同，而相等的子节点哈希必然推出相等的父节点哈希，与”叶子不同”矛盾）。因此算法不会把一个真正不同的区间判定为一致——前提是哈希函数无碰撞（工程上取碰撞概率可忽略）。$\blacksquare$
- 完整性（能找到所有差异）：递归下降只在”子树哈希相同”时剪枝，而剪枝的子树确实完全一致（同上论证的逆否），因此所有差异子树都会被展开到叶子，所有差异都会被枚举。$\blacksquare$
- 修复的正确性：对每个差异 key，使用 LWW 裁决（与读路径、写路径完全相同的裁决函数），因此修复后的值与其他修复路径（read repair、hinted handoff 重放）不会互相打架，系统收敛到同一个终态。$\blacksquare$
- 活性：只要两副本可达且区间有限，比较过程必然终止（每次递归树高减 1，树高有限）；差异数有限，因此写回也必然终止。
复杂度
- 构建：时间 $O(n)$（$n$ 为区间内 key 数），空间 $O(n/b)$ 个哈希（$b$ = 每叶 key 数），网络传输 $O(1)$（只传根）到 $O(n/b)$（传全树）。
- 比较（最好情况，完全一致）：$O(1)$ 次哈希交换，1 个 RTT；节点访问数 = 1（只比根）。
- 比较（最坏情况）：子树有 $d$ 个叶子不同时，访问节点数 $O(d \cdot \log_b(n/b))$；$d=1$ 时仅为 $O(\log n)$，这正是讲义强调的结论。
- 数据传输：$O(d)$ 个 key 的实际数据（而非 $O(n)$）。
- 范围大小与树深度的权衡：$b$ 增大 ⇒ 树高 $h = \log_b(n/b)$ 减小 ⇒ 比较的往返轮数减少，但每个差异叶子的修复粒度变粗（要多传 $b$ 个 key）；$b$ 减小 ⇒ 定位精准但树更深、元数据更多。实践做法是把整个环切成足够多的区间（每棵树的哈希能放进内存），再并行修复各区间，从而同时获得”树浅”与”粒度细”。
前提约束（再次强调，因为这是最常见的错误来源）：
- 两副本的数据必须按相同顺序排列（相同分区器、相同 schema/聚簇顺序）。若顺序不同，同一份数据会生成完全不同的叶子边界，比较结果全是”不同”，修复退化为盲目全量传输——不仅没省带宽，还引入了巨大的额外开销。
- 必须处理墓碑：删除必须作为版本参与比较，且在
gc_grace_seconds内不允许被 compaction 清理掉；否则会出现”一方已删、一方未删”被误判为”一方缺数据”，从而复活已删除的数据。 - 必须基于快照：构建期间的数据变化会让”同一区间的两棵树”建立在不同数据上，产生虚假差异。
- 不可在修复期间改变拓扑：若期间有节点 bootstrap/离开，token 区间归属改变，”这两个副本应当一致”的前提就不成立了。
算法 9.3.5：Φ 累加故障检测器（Phi Accrual Failure Detector）
假设与系统模型
- 进程集合 $P$ 中的每个进程周期性发送心跳/gossip 消息（Cassandra 中 gossip 周期约 1 秒，且不保证严格周期）。
- 故障模型：fail-stop / crash-recovery；网络是异步的，消息可能延迟、丢失、乱序（因此”多久没收到心跳”不能直接等价于”对端死了”）。
- 时钟：每个进程只使用自己的本地时钟测量到达间隔（因此不需要全局同步时钟）。
- 目标：不输出”死/活”二元判断，而是输出怀疑度 $\phi \ge 0$，由应用选择阈值 $\Phi_{thr}$ 决定何时判死。
- 样本模型：到达间隔 $\delta$ 近似服从正态分布 $N(\mu, \sigma^2)$（Hayashibara 等的原始假设；Cassandra 的实现即用最近窗口的均值与标准差，并对 $\sigma$ 设下界）。
伪代码
# 每个被监控进程 p 维护一个状态:
state[p] = { t_last: last arrival time, # 最近一次收到 p 的消息的本地时间
samples: deque(maxlen = W), # 最近 W 个到达间隔（W 典型取 1000）
mu: mean, sigma: stddev, # 由 samples 估计
phi: 0.0 }
# ---- 由到达间隔估计分布参数 ----
update_stats(state):
if len(state.samples) >= 2:
state.mu <- mean(state.samples)
state.sigma <- max( stddev(state.samples), MIN_SIGMA ) # 关键：σ 下界
# MIN_SIGMA 防止"间隔极其规律"时 σ=0，导致任何微小抖动都判定为故障
else:
state.mu <- INITIAL_MEAN # 样本不足时用保守默认值
state.sigma <- INITIAL_SIGMA
# ---- 收到一条来自 p 的消息 ----
upon receiving message m from p at local time t_now:
if state[p].t_last is set:
delta <- t_now - state[p].t_last
state[p].samples.append(delta)
update_stats(state[p])
state[p].t_last <- t_now
state[p].phi <- 0.0 # 收到消息 ⇒ 怀疑度归零
# ---- 周期性（或在每次查询时）计算怀疑度 ----
compute_phi(p, t_now):
t <- t_now - state[p].t_last # 已经静默了多久
if len(state[p].samples) < 2:
return state[p].phi # 样本不足，保持原值
# 把 t 标准化为 z 分数，再求右尾概率 P_later = 1 - CDF(t)
z <- (t - state[p].mu) / state[p].sigma
cdf <- 0.5 * (1 + erf( z / sqrt(2) )) # 正态 CDF
p_later <- 1.0 - cdf # P(下一个间隔 > t)
p_later <- max(p_later, 1e-12) # 防止 log10(0) = -inf
return -log10(p_later) # Φ 的定义
# ---- 应用侧的判定（Cassandra 用 phi_convict_threshold，默认 8）----
upon each gossip round:
for p in members:
phi_p <- compute_phi(p, now_local())
if phi_p > PHI_THRESHOLD: # 讲义: PHI=5 ⇒ 约 10–15 秒检测
mark p as SUSPECTED
disseminate (SUSPECTED, p, incarnation) via gossip # 见 Lecture 6 的怀疑机制
if phi_p > PHI_THRESHOLD and suspected_long_enough:
mark p as FAILED # 触发 hinted handoff 保存、副本重建等
elif p was SUSPECTED and message arrived:
p <- ALIVE ; phi_p <- 0
算法逻辑解说（数值走一遍） 设某节点与 $p$ 之间过去 1000 次 gossip 的到达间隔均值为 $\mu = 1.0$ s、标准差 $\sigma = 0.2$ s。
- 若 $t = 1.5$ s 没收到消息：$z = (1.5-1.0)/0.2 = 2.5$，$\text{CDF}(2.5) \approx 0.9938$，$P_{later} \approx 0.0062$，$\phi = -\log_{10}0.0062 \approx 2.2$ ⇒ 不太可疑（0.6% 的概率事件而已）；
- 若 $t = 2.0$ s：$z = 5$，$\text{CDF}(5) \approx 1 - 2.9\times10^{-7}$，$\phi \approx 6.5$ ⇒ 可疑；
- 若 $t = 2.5$ s：$z = 7.5$，$\text{CDF}(7.5) \approx 1 - 3.2\times10^{-14}$，$\phi \approx 13.5$ ⇒ 非常可疑，超过阈值 8，判定 SUSPECTED/FAILED；
- 若网络本身很抖（$\sigma = 1.0$ s），则 $t = 2.5$ s 时 $z = 1.5$，$\text{CDF}(1.5)\approx0.9332$，$\phi \approx 1.2$ ⇒ 仍然不判死。 这就是”自适应”的含义：同样的静默时长，在网络稳定时高度可疑，在网络抖动时完全正常。
正确性论证
- 完整性（Completeness，最终一定检测到）：若 $p$ 崩溃，则 $t = t_{now} - t_{last} \to \infty$；固定 $\mu, \sigma$ 时 $\text{CDF}(z) \to 1$，故 $P_{later} \to 0$，$\phi \to \infty$，必然在有限时间内超过任意有限阈值 $\Phi_{thr}$，从而被判为 SUSPECTED/FAILED。$\blacksquare$（注意：前提是样本窗口停止更新——崩溃后不再有新消息，$\mu,\sigma$ 冻结，这个条件成立。）
- 准确性（Accuracy，只能是概率性的）：$\phi > \Phi_{thr}$ 时判死的误判概率约为 $10^{-\Phi_{thr}}$（在正态模型精确成立时）。例如 $\Phi_{thr} = 5$ 对应约 $10^{-5}$ 的单次误判概率。这不是确定性的准确性保证，与 Lecture 6 引用的 Chandra–Toueg 结论一致：在丢包网络中不可能同时保证”完整 + 准确”，否则可以解共识。
- 收敛/稳定性：收到任何消息后 $\phi$ 立即归零（代码中的
state[p].phi <- 0.0），因此”误判”是可撤销的——这正是 Lecture 6 的怀疑机制（suspicion mechanism）的基础：先把节点标为 SUSPECTED 并通过 gossip 传播，若它随后有消息到达就恢复为 ALIVE（并用 incarnation number 覆盖旧的怀疑消息），只有持续怀疑才升级为 FAILED。这显著降低了”因为一次丢包就把节点踢出集群”的概率。 - 依赖的假设（必须明说）：正态分布假设在真实网络中只是近似（真实到达间隔常呈重尾/长尾）；$\sigma$ 必须有下界（否则规律性极强的对端一抖动就被判死）；样本必须来自稳定的网络状态（网络拓扑或负载突变时应重置样本）。
复杂度
- 时间：每次收到消息 $O(1)$（增量更新均值/方差）；每次计算 $\phi$ 为 $O(1)$（一次
erf或查表）； - 空间：每个被监控进程 $O(W)$（保存最近 $W$ 个间隔样本，$W$ 通常取 1000，可化为增量均值/方差实现 $O(1)$）；
- 消息：零额外消息——$\phi$ 完全基于已有的 gossip/心跳消息的到达时间计算，这也是它优于”专用探测消息”的原因；
- 对比固定超时：固定超时检测器需要为最坏抖动预留超时 ⇒ 检测慢；$\phi$ 累加检测器用统计模型替代固定阈值 ⇒ 在同等误判率下检测更快，或在同等检测速度下误判更少。
9.4 代码示例与分布式实现
本节给出三个可直接 python3 运行的模拟器（只用标准库，固定随机种子）。它们不是玩具：每个都精确地把 9.2/9.3 中的机制代码化，并在结尾用断言与统计验证理论结论。
代码 9.4.1 完整的 Cassandra 风格键值存储模拟器
把下面的代码保存为 cassandra_sim.py 后直接运行（约 300 行，因为它需要完整实现环、三层存储、可调一致性、hinted handoff、read repair、Merkle tree 与实证实验；运行约 1 秒）。
"""Cassandra 风格键值存储模拟器：一致性哈希环 + vnodes + 三层存储 + 可调一致性
+ Hinted Handoff + Read Repair + Merkle Tree 反熵修复 + R+W>N 实证。"""
import hashlib
import random
random.seed(42)
VNODES = 8 # 每个物理节点的 vnode 数（token 数）
N = 3 # 副本因子 N
def h64(s):
"""确定性 64 位哈希，替代现实的 Murmur3Partitioner。"""
return int.from_bytes(hashlib.md5(str(s).encode()).digest()[:8], "big")
class Replica:
"""一个存储节点：CommitLog(顺序日志) -> Memtable(内存) -> SSTable(磁盘不可变)。"""
def __init__(self, name, lag=0):
self.name, self.lag = name, lag # lag: 写可见性延迟（模拟 GC 停顿/慢盘）
self.commitlog = [] # 追加日志，用于崩溃恢复
self.memtable = {} # key -> (value, ts)，内存有序表
self.sstables = [] # 不可变快照列表
self.pending = [] # (visible_at, key, value, ts) 延迟到达的写
self.alive = True
def write(self, key, value, ts):
self.commitlog.append((key, value, ts)) # 1) 顺序写日志（持久化）
self.memtable[key] = (value, ts) # 2) 写内存表
if len(self.commitlog) % 8 == 0: # 3) 内存表满 -> flush 成 SSTable
self.sstables.append(dict(self.memtable))
self.memtable = {}
def write_at(self, key, value, ts, now):
if self.lag == 0:
self.write(key, value, ts)
else:
self.pending.append((now + self.lag, key, value, ts))
def tick(self, now):
"""把到期的延迟写落到 memtable。"""
keep = []
for item in self.pending:
if item[0] <= now:
self.write(item[1], item[2], item[3])
else:
keep.append(item)
self.pending = keep
def get(self, key):
"""读路径：先查 memtable，再从新到旧查 SSTable，按 timestamp 取最新。"""
best = self.memtable.get(key)
for sst in reversed(self.sstables):
cand = sst.get(key)
if cand and (best is None or cand[1] > best[1]):
best = cand
return best
class Ring:
"""一致性哈希环（带 vnodes）+ SimpleStrategy 副本放置。"""
def __init__(self, nodes):
self.replicas = {n.name: n for n in nodes}
self.ring = []
for n in nodes:
for v in range(VNODES):
self.ring.append((h64("%s#%d" % (n.name, v)), n.name))
self.ring.sort()
def owners(self, key):
"""token -> 顺时针第一个 vnode 起，取 N 个不同物理节点。"""
tok = h64(key)
start = 0
for i, (t, _) in enumerate(self.ring):
if t >= tok:
start = i
break
out, i = [], start
while len(out) < N:
name = self.ring[i % len(self.ring)][1]
if name not in out:
out.append(name)
i += 1
return out
class Coordinator:
"""任意节点都可以当协调者；这里单独建模以显式记录 hints。"""
def __init__(self, ring):
self.ring = ring
self.hints = [] # (target, key, value, ts)
def write(self, key, value, ts, W, now):
acks, times = 0, []
for name in self.ring.owners(key): # 并行发给全部 N 个副本（不只 W 个）
r = self.ring.replicas[name]
if r.alive:
r.write_at(key, value, ts, now)
acks += 1
times.append(now + r.lag)
else:
self.hints.append((name, key, value, ts)) # 提示移交
ok = acks >= W
return ok, acks, (sorted(times)[W - 1] if ok else None)
def replay_hints(self, now):
n = 0
for target, key, value, ts in self.hints:
r = self.ring.replicas[target]
if r.alive:
r.write_at(key, value, ts, now) # 用原始时间戳重放
n += 1
self.hints = [h for h in self.hints if not self.ring.replicas[h[0]].alive]
return n
def read(self, key, R, now, repair=True):
reps = [self.ring.replicas[x] for x in self.ring.owners(key)]
for r in reps:
r.tick(now)
alive = [r for r in reps if r.alive] # 只联系存活副本
if len(alive) < R:
return None, [], [r.name for r in alive] # 达不到 R → 读失败
chosen = random.sample(alive, R) # 模拟"选过去响应最快的 R 个"
best = None
for r in chosen:
v = r.get(key)
if v and (best is None or (v[1], v[0]) > (best[1], best[0])):
best = v # LWW: (ts, value_bytes) 取最大
repaired = []
if repair and best:
for r in alive: # 后台读修复：其余副本也联系
cur = r.get(key)
if cur != best:
r.write(key, best[0], best[1])
repaired.append(r.name)
return best, repaired, [r.name for r in chosen]
# ---------------- Merkle Tree：反熵修复 ----------------
PAD = "0" * 8
def leaf_hash(key, value, ts):
return hashlib.md5(("%s|%s|%s" % (key, value, ts)).encode()).hexdigest()[:8]
def build_merkle(leaves):
"""把叶子补齐成满二叉树后自底向上构建，返回各层。"""
n = 1
while n < len(leaves):
n *= 2
cur = list(leaves) + [PAD] * (n - len(leaves))
levels = [cur]
while len(cur) > 1:
cur = [hashlib.md5((cur[i] + cur[i + 1]).encode()).hexdigest()[:8]
for i in range(0, len(cur), 2)]
levels.append(cur)
return levels
def merkle_diff(la, lb, lvl, idx, stats, out):
"""逐层下降：哈希相同则剪枝，否则下沉到叶子。"""
stats[0] += 1
if la[lvl][idx] == lb[lvl][idx]:
return
if lvl == 0:
out.append(idx)
return
for c in (idx * 2, idx * 2 + 1):
if c < len(la[lvl - 1]):
merkle_diff(la, lb, lvl - 1, c, stats, out)
def demo_ring():
print("=" * 74)
print("[1] 一致性哈希环 + vnodes + SimpleStrategy 副本放置")
nodes = [Replica(x) for x in ("N1", "N2", "N3", "N4")]
ring = Ring(nodes)
for key in ("user101", "user422", "tweet:9981"):
print(" key=%-12s owners=%s" % (key, ring.owners(key)))
print(" ring 上共 %d 个 vnode（%d 节点 x %d vnodes）" % (len(ring.ring), 4, VNODES))
def demo_write_read_paths():
print("=" * 74)
print("[2] 写路径 CommitLog->Memtable->SSTable 与读路径 merge")
r = Replica("N1")
for i in range(9):
r.write("k%d" % i, "v%d" % i, 100 + i)
print(" commitlog 长度=%d, memtable=%d 项, sstables=%d 张"
% (len(r.commitlog), len(r.memtable), len(r.sstables)))
r.write("k0", "v0-new", 999) # 覆盖写：旧版本留在老 SSTable 里
print(" 覆盖写后 k0 =", r.get("k0"), " memtable=", r.memtable.get("k0"))
print(" 读 k0 需要合并 memtable + %d 张 SSTable -> 读放大" % len(r.sstables))
def demo_hinted_handoff():
print("=" * 74)
print("[3] Hinted Handoff：副本宕机时写仍然成功")
nodes = [Replica(x) for x in ("N1", "N2", "N3", "N4")]
ring = Ring(nodes)
co = Coordinator(ring)
key = "cart:alice"
down = ring.owners(key)[2]
ring.replicas[down].alive = False
ok, acks, _ = co.write(key, "item42", 500, W=2, now=0)
print(" 副本 %s 宕机 -> write(W=2) ok=%s acks=%d" % (down, ok, acks))
print(" 协调者本地 hint 队列 =", co.hints)
v, _, chosen = co.read(key, 1, 0, repair=False)
print(" 从存活副本读到 =", v, " (读集合 %s)" % chosen)
print(" 宕机副本 %s 的本地值 = %s" % (down, ring.replicas[down].get(key)))
ring.replicas[down].alive = True
n = co.replay_hints(now=10)
print(" %s 恢复 -> 重放 %d 条 hint，其值 = %s" % (down, n, ring.replicas[down].get(key)))
def demo_read_repair():
print("=" * 74)
print("[4] Read Repair：读时发现陈旧副本并自动修复")
nodes = [Replica(x) for x in ("N1", "N2", "N3", "N4")]
ring = Ring(nodes)
co = Coordinator(ring)
key = "profile:bob"
for n in nodes:
n.write(key, "v1", 100)
victim = ring.owners(key)[1]
v = ring.replicas[victim]
v.memtable.clear(); v.sstables.clear(); v.commitlog.clear() # 模拟该副本数据丢失/落后
print(" 修复前 %s 的值 = %s" % (victim, v.get(key)))
best, repaired, chosen = co.read(key, R=2, now=0) # 读 R=2 并触发读修复
print(" 读(R=2) 集合=%s 返回=%s 修复了=%s" % (chosen, best, repaired))
print(" 修复后 %s 的值 = %s (断言: %s)"
% (victim, v.get(key), v.get(key) == best))
assert v.get(key) == best
def demo_merkle():
print("=" * 74)
print("[5] Merkle Tree 反熵修复：只访问 O(log n) 个节点")
keys = ["k%04d" % i for i in range(1024)]
A = {k: ("v", 100) for k in keys}
B = dict(A)
B["k0512"] = ("v-CHANGED", 200) # 制造恰好 1 处差异
la = build_merkle([leaf_hash(k, A[k][0], A[k][1]) for k in keys])
lb = build_merkle([leaf_hash(k, B[k][0], B[k][1]) for k in keys])
stats, out = [0], []
print(" 区间内 key 数 = %d，Merkle 树高 = %d" % (len(keys), len(la) - 1))
print(" 根哈希: A=%s B=%s -> %s" % (la[-1][0], lb[-1][0],
"相同则 O(1) 结束" if la[-1][0] == lb[-1][0] else "不同，下沉"))
merkle_diff(la, lb, len(la) - 1, 0, stats, out)
diff_keys = [keys[i] for i in out]
print(" 访问树节点数 = %d (对比：朴素比较需检查 %d 个 key)" % (stats[0], len(keys)))
print(" 定位到差异 key = %s A=%s B=%s" % (diff_keys, A["k0512"], B["k0512"]))
loser = min([("A", A), ("B", B)], key=lambda kv: kv[1]["k0512"][1])[0]
print(" LWW 裁决: ts 较大的一方 (%s) 获胜 -> 写回 %s" % ("B", loser))
assert diff_keys == ["k0512"]
def experiment_stale_reads(trials=150):
print("=" * 74)
print("[6] 实证 R+W>N：同一操作序列下统计“读到陈旧数据”的次数 (N=3)")
print(" %-14s %-8s %-16s %s" % ("(W,R)", "R+W", "stale_reads", "判定"))
for W, R in [(1, 1), (2, 1), (2, 2), (3, 1), (1, 3)]:
random.seed(42)
stale = 0
for i in range(trials):
nodes = [Replica(x) for x in ("N1", "N2", "N3")]
nodes[i % 3].lag = 2 # 每轮让不同副本“慢”下来
ring = Ring(nodes)
co = Coordinator(ring)
key = "key%03d" % i # 每轮用新 key，避免修复互相影响
for n in nodes:
n.write(key, "old", 1)
ok, acks, finish = co.write(key, "new", 2, W, now=10)
if not ok:
continue
best, _, _ = co.read(key, R, finish, repair=False)
if best is None or best[0] != "new":
stale += 1
verdict = "OK (R+W>N 强一致)" if R + W > N else "可能陈旧 (R+W<=N)"
print(" %-14s %-8s %-16s %s"
% ("W=%d,R=%d" % (W, R), R + W, "%d/%d" % (stale, trials), verdict))
print(" 结论：只有 R+W>N 的组合 stale_reads 恒为 0 —— 与鸽巢原理的证明一致。")
print(" 注意读修复默认关闭，因此这里测的是纯 quorum 交集效应。")
if __name__ == "__main__":
demo_ring()
demo_write_read_paths()
demo_hinted_handoff()
demo_read_repair()
demo_merkle()
experiment_stale_reads()
print("=" * 74)
实际运行输出（节选，可复现）
[1] 一致性哈希环 + vnodes + SimpleStrategy 副本放置
key=user101 owners=['N3', 'N1', 'N2']
key=user422 owners=['N2', 'N1', 'N3']
key=tweet:9981 owners=['N1', 'N2', 'N3']
ring 上共 32 个 vnode（4 节点 x 8 vnodes）
[3] Hinted Handoff：副本宕机时写仍然成功
副本 N2 宕机 -> write(W=2) ok=True acks=2
协调者本地 hint 队列 = [('N2', 'cart:alice', 'item42', 500)]
从存活副本读到 = ('item42', 500) (读集合 ['N3'])
宕机副本 N2 的本地值 = None
N2 恢复 -> 重放 1 条 hint，其值 = ('item42', 500)
[4] Read Repair：读时发现陈旧副本并自动修复
修复前 N4 的值 = None
读(R=2) 集合=['N1', 'N4'] 返回=('v1', 100) 修复了=['N4']
修复后 N4 的值 = ('v1', 100) (断言: True)
[5] Merkle Tree 反熵修复：只访问 O(log n) 个节点
区间内 key 数 = 1024，Merkle 树高 = 10
根哈希: A=2f42b29c B=71635bf0 -> 不同，下沉
访问树节点数 = 21 (对比：朴素比较需检查 1024 个 key)
定位到差异 key = ['k0512'] A=('v', 100) B=('v-CHANGED', 200)
LWW 裁决: ts 较大的一方 (B) 获胜 -> 写回 A
[6] 实证 R+W>N：同一操作序列下统计“读到陈旧数据”的次数 (N=3)
(W,R) R+W stale_reads 判定
W=1,R=1 2 55/150 可能陈旧 (R+W<=N)
W=2,R=1 3 55/150 可能陈旧 (R+W<=N)
W=2,R=2 4 0/150 OK (R+W>N 强一致)
W=3,R=1 4 0/150 OK (R+W>N 强一致)
W=1,R=3 4 0/150 OK (R+W>N 强一致)
【代码做什么？】
h64()用 MD5 前 8 字节模拟 Murmur3Partitioner：把任意 key 映射到 $[0, 2^{64})$ 的 token（确定性，保证同一 key 每次落同一处）。Replica实现三层存储：write()先 append 到commitlog（顺序日志，对应 9.2.16 的第 ③ 步），再写memtable（第 ④ 步），每 8 条 flush 一次生成一个不可变的sstable；get()实现 merge 多版本 + 按 timestamp 取最新（9.2.17 的读路径）。write_at()/tick()引入lag：模拟”某个副本的写会晚一点才可见”（GC 停顿、慢盘、网络抖动）——这是整个第 [6] 项实验的故障注入点。Ring实现带 vnodes 的一致性哈希环（每个物理节点 8 个 token）与 SimpleStrategy 放置（owners()顺时针取前 3 个不同物理节点）。Coordinator.write()实现可调一致性写：向全部 $N$ 个副本发写，统计 ack，达到 $W$ 才返回成功；对不可达副本记录 hint。finish的计算sorted(times)[W-1]精确刻画了”客户端等待的是第 $W$ 快的 ack“（而不是最慢的）。Coordinator.replay_hints()实现提示移交重放，并且用原始时间戳写入（这就是 LWW 收敛的关键细节）。Coordinator.read()实现可调一致性读 + 后台读修复：从存活副本中选 $R$ 个，按(ts, value)字典序取最大，然后把最新值写回所有不一致的副本；不足 $R$ 个存活副本则读失败。build_merkle()/merkle_diff()实现 Merkle Tree 的构造与逐层下降比较，并用stats[0]统计访问过的树节点数——第 [5] 项打印出 21 次节点访问 vs 朴素比较的 1024 个 key，正是 $O(\log n)$ 的实证。experiment_stale_reads()是核心实验：在 $N=3$ 下，每一轮让不同的一个副本变慢，同一个操作序列（写"old"→ 写"new"→ 读）分别用 5 组 $(W,R)$ 跑 150 轮，统计”读到的不是"new"“的次数。
【分布式机制透视】
- 环与副本：
Ring.ring是真实的 token 环，owners()是真实的副本选择；换 key 会落到不同节点，换节点数会改变所有 key 的归属——这与真实 Cassandra 一致。 - 消息传递与”网络”：这里没有用 socket，而是用对象方法调用 + 延迟队列建模”异步、可能延迟的消息”。
lag字段就是”这个副本的网络/磁盘比别的慢”的抽象；alive字段是”节点不可达”。 - 时序：
now/finish是逻辑时间，用来表达”写在什么时刻对读可见”。第 [6] 项实验的本质是”读发生的时刻，是否已经覆盖了写成功所依赖的那 $W$ 个副本“——这正是 $R+W>N$ 的物理含义。 - 每个进程的状态：
Replica各自持有 commitlog/memtable/sstables，Coordinator独立持有 hint 队列——协调者不是数据所有者，它只是一个汇总者，这正确反映了无主复制的结构。 - 故障：
alive=False是崩溃故障；lag是性能故障（慢节点）。很多真实的一致性异常来自后者，而固定超时的”存活/死亡”模型往往看不到它——本模拟器特意把这两类都建了出来。
【与理论的对应】
- 第 [6] 项是 算法 9.3.3 定理 T1 的实证：$R+W>N$ 的三组
stale_reads == 0，而 $R+W \le N$ 的两组各出现 55 次陈旧读（$\approx 1/3$ —— 因为 $R=1$ 时恰好选中那个变慢副本的概率是 $1/3$）。这就是”鸽巢原理”在数据上的样子。 - 第 [5] 项对应 算法 9.3.4：
merkle_diff的剪枝条件la[lvl][idx] == lb[lvl][idx]就是”哈希相同 ⇒ 子树完全一致”的推断；访问 21 个节点即 $O(\log n)$。 - 第 [3]/[4] 项对应 算法 9.3.1 的 hinted handoff 分支与 算法 9.3.2 的读修复分支：写成功（
ok=True）与”所有副本都持有”是两件不同的事——这正是 BASE 与 ACID 的分界线。 - 第 [2] 项对应 9.2.16/9.2.17：覆盖写不会修改老 SSTable，只会留下新版本，读时必须 merge——读放大由此产生。
代码 9.4.2 Bloom Filter 的实现、假阳性率验证与”无假阴性”验证
"""Bloom Filter：假阳性率公式验证 + “无假阴性”的构造性验证。"""
import hashlib
import math
import random
random.seed(7)
class BloomFilter:
def __init__(self, m, k):
self.m, self.k = m, k # m = 位数组大小, k = 哈希函数个数
self.bits = bytearray((m + 7) // 8) # 全 0 的位数组
def _positions(self, item):
"""双重哈希：h_i(x) = (h1 + i*h2) mod m，用 2 次真实哈希模拟 k 个独立哈希。"""
h1 = int.from_bytes(hashlib.md5(("1|" + item).encode()).digest()[:8], "big")
h2 = int.from_bytes(hashlib.md5(("2|" + item).encode()).digest()[:8], "big") | 1
for i in range(self.k):
yield (h1 + i * h2) % self.m
def add(self, item):
for p in self._positions(item): # 插入：把 k 个位置置 1
self.bits[p >> 3] |= 1 << (p & 7)
def contains(self, item):
return all(self.bits[p >> 3] & (1 << (p & 7)) for p in self._positions(item))
def ones(self):
return sum(bin(b).count("1") for b in self.bits)
def predicted_fp(m, k, n):
"""p ≈ (1 - e^{-kn/m})^k"""
return (1.0 - math.exp(-k * n / m)) ** k
def measure(m, k, n, probe=20000):
bf = BloomFilter(m, k)
inserted = ["ins-%d" % i for i in range(n)]
for x in inserted:
bf.add(x)
# ① 无假阴性验证：所有插入过的 key 必须 100% 命中
hits = sum(1 for x in inserted if bf.contains(x))
assert hits == n, "false negative detected!"
# ② 假阳性率：用从未插入过的 key 探测
fp = sum(1 for i in range(probe) if bf.contains("probe-%d" % i))
return hits, (fp / probe if probe else 0.0)
def main():
n = 1000
print("=" * 78)
print("[1] 参数 (m, k) 对假阳性率的影响：n = %d 个已插入 key，20000 个未插入 key 探测" % n)
print(" %-8s %-4s %-8s %-12s %-12s %-10s" %
("m(bits)", "k", "m/n", "实测FP", "公式FP", "位使用率"))
for m in (4000, 8000, 16000):
for k in (1, 2, 4, 7, 10):
hits, fp = measure(m, k, n)
bf = BloomFilter(m, k)
for x in ("ins-%d" % i for i in range(n)):
bf.add(x)
print(" %-8d %-4d %-8.1f %-12.5f %-12.5f %-10.3f" %
(m, k, m / n, fp, predicted_fp(m, k, n), bf.ones() / m))
print("=" * 78)
print("[2] 最优哈希个数 k* = (m/n)·ln2，此时 p* ≈ 0.6185^(m/n)")
for m in (4000, 8000, 16000):
kopt = max(1, round((m / n) * math.log(2)))
best_measured, best_k = 1.0, 0
for k in range(1, 16):
_, fp = measure(m, k, n, probe=20000)
if fp < best_measured:
best_measured, best_k = fp, k
print(" m/n=%-5.1f k*公式=%-3d 实测最优 k=%-3d (FP=%.5f) 公式预测 p*(k*)=%.5f"
% (m / n, kopt, best_k, best_measured, predicted_fp(m, kopt, n)))
print("=" * 78)
print("[3] 讲义的例子：m=3200, k=4, n=100")
_, fp = measure(3200, 4, 100, probe=200000)
print(" 实测假阳性率 = %.5f%% 公式 (1-e^{-kn/m})^k = %.5f%%"
% (fp * 100, predicted_fp(3200, 4, 100) * 100))
print("=" * 78)
print("[4] 无假阴性的构造性验证（50000 个 key，多组参数）")
for m, k in ((1024, 3), (4096, 7), (100, 5)):
hits, _ = measure(m, k, 50000, probe=0) # 极小的 m 会让位图饱和
print(" m=%-6d k=%d: 50000/50000 命中 (断言通过，FP 率在此无关紧要)" % (m, k))
print(" 结论：位只会被置 1、永不清 0 ⇒ 插入过的 key 查询必然为真 ⇒ 无假阴性。")
print("=" * 78)
if __name__ == "__main__":
main()
实际运行输出（节选，运行约 7 秒）
m(bits) k m/n 实测FP 公式FP 位使用率
4000 1 4.0 0.21840 0.22120 0.219
4000 4 4.0 0.14815 0.15966 0.621
8000 4 8.0 0.02035 0.02397 0.389
8000 10 8.0 0.02870 0.03419 0.707
16000 4 16.0 0.00180 0.00239 0.220
16000 10 16.0 0.00035 0.00047 0.460
[2] 最优哈希个数 k* = (m/n)·ln2
m/n=4.0 k*公式=3 实测最优 k=3 (FP=0.13875) 公式预测 p*(k*)=0.14689
m/n=8.0 k*公式=6 实测最优 k=5 (FP=0.01990) 公式预测 p*(k*)=0.02158
m/n=16.0 k*公式=11 实测最优 k=10 (FP=0.00035) 公式预测 p*(k*)=0.00046
[3] 讲义的例子：m=3200, k=4, n=100
实测假阳性率 = 0.02000% 公式 (1-e^{-kn/m})^k = 0.01906%
【代码做什么？】
BloomFilter用bytearray实现位数组；_positions()用双重哈希（Kirsch–Mitzenmacher 技巧）从一个 64 位哈希对生成 $k$ 个位置：$h_i(x) = (h_1 + i\,h_2) \bmod m$，因此只需要 2 次真实哈希计算就能模拟 $k$ 个独立哈希，这是工程上最常见的实现方式。measure()先插入 $n$ 个 key 并断言全部命中（assert hits == n）——这就是无假阴性的构造性验证；再用probe个从未插入过的 key 统计假阳性率。- 第 [1] 项打印 $(m, k, m/n, \text{实测 FP}, \text{公式 FP}, \text{位使用率})$ 对照表：实测值与公式高度吻合，验证了 $p \approx (1-e^{-kn/m})^k$。
- 第 [2] 项对每个 $m/n$ 扫描 $k=1..15$，找出实测最优 $k$ 并与公式 $k^* = \frac{m}{n}\ln 2$ 对比；第 [3] 项复现讲义的例子（$m=3200$、$k=4$、$n=100$ ⇒ 0.02%）；第 [4] 项用 50000 个 key 在极小位数组（$m=100$、$k=5$，位图几乎饱和）上验证”无假阴性”依然成立。
- 表里的位使用率（
bf.ones()/m）很有启发性：$k$ 过大时位图被迅速填满（如 $m/n=4,k=10$ 时 91.2% 的位为 1），假阳性率反而上升——这就是”$k$ 不是越大越好”的原因。
【分布式机制透视】
- 在 Cassandra 的读路径上，每个 SSTable 一个 Bloom Filter，SSTable 一旦写成就不再修改，因此 filter 只增不改——
add()只做\|=（置 1），代码里根本没有删除操作。这个约束正是无假阴性证明的前提。 - 内存成本：$m/n = 8$ 时，每个 key 只花 1 字节 就能把假阳性率压到约 2%；$m/n=10$ 时最优配置的假阳性率约 1%（Cassandra 默认
bloom_filter_fp_chance约 0.01）。这是”用少量内存换取跳过磁盘 IO“的经典交易。 - 分布式含义：读路径上的 Bloom Filter 是每个副本各自持有的本地结构，不需要任何跨节点协调——它把”这个 key 在不在我这个节点的某张表里”变成一个常数时间的本地判断，从而让”并行读 $R$ 个副本”真正可行。
【与理论的对应】
- 第 [2] 项验证 $k^* = \frac{m}{n}\ln 2$ 与 $p^* \approx 0.6185^{m/n}$（9.2.17 的推导）。
- 断言
assert hits == n是 算法 9.3.3 定理 T2（Bloom Filter 无假阴性） 的直接检验；正是 T2 的推论 C2 保证了”contains() == False⇒ 该 SSTable 一定不含该 key”，读路径的跳过优化才是安全的（而不是仅仅”通常正确”）。 - 第 [4] 项展示了一个重要区分：假阳性率可以随参数恶化到几乎 100%（正确性不受影响，只是慢），假阴性率永远是 0%（一旦出现就是正确性 bug）。这正是 Bloom Filter 能被用于读路径的根本原因。
代码 9.4.3 LSM-Tree 写读路径演示（写放大 / 读放大 / compaction）
"""LSM-Tree 写/读路径演示：CommitLog -> Memtable -> SSTable、compaction、
写放大/读放大/空间放大，以及 Bloom Filter 对读放大的作用。"""
import hashlib
import math
import random
random.seed(11)
NKEYS = 2000
NWRITES = 6000
class Bloom:
"""每个 SSTable 一个 Bloom Filter（构建后只读，故无假阴性）。"""
def __init__(self, n, fp=0.01):
self.m = max(64, int(-n * math.log(fp) / (math.log(2) ** 2)))
self.k = max(1, int(round(self.m / max(1, n) * math.log(2))))
self.bits = bytearray((self.m + 7) // 8)
def _pos(self, item):
h1 = int.from_bytes(hashlib.md5(("1|" + item).encode()).digest()[:8], "big")
h2 = int.from_bytes(hashlib.md5(("2|" + item).encode()).digest()[:8], "big") | 1
for i in range(self.k):
yield (h1 + i * h2) % self.m
def add(self, item):
for p in self._pos(item):
self.bits[p >> 3] |= 1 << (p & 7)
def maybe(self, item):
return all(self.bits[p >> 3] & (1 << (p & 7)) for p in self._pos(item))
class SSTable:
def __init__(self, data):
self.data = dict(data) # key -> (value, ts)
self.bloom = Bloom(len(self.data))
for k in self.data:
self.bloom.add(k)
class LSM:
def __init__(self, flush_at=200, trigger=8):
self.mem, self.ssts = {}, []
self.flush_at, self.trigger = flush_at, trigger
self.logical = 0 # 逻辑写次数
self.disk = 0 # 实际写到磁盘的记录条数（日志 + flush + compaction）
self.flushes, self.compactions = 0, 0
def put(self, key, value, ts):
self.logical += 1
self.disk += 1 # CommitLog 顺序追加
self.mem[key] = (value, ts)
if len(self.mem) >= self.flush_at:
self.flush()
while len(self.ssts) >= self.trigger: # STCS：大小相近的表攒够就合并
self.compact()
def flush(self):
self.ssts.append(SSTable(self.mem))
self.disk += len(self.mem)
self.flushes += 1
self.mem = {}
def compact(self):
group = sorted(self.ssts, key=lambda s: len(s.data))[:self.trigger]
merged = {}
for s in group: # 从旧到新合并，新的覆盖旧的（LWW）
merged.update(s.data)
for s in group:
self.ssts.remove(s)
self.ssts.append(SSTable(merged))
self.disk += len(merged)
self.compactions += 1
def get(self, key, use_bloom=True):
"""返回 (value, ts, 打开的 SSTable 数)"""
opened, best = 0, self.mem.get(key)
if best:
return best[0], best[1], 0
for s in reversed(self.ssts): # 从新到旧
if use_bloom and not s.bloom.maybe(key):
continue # 无假阴性 ⇒ 可安全跳过
opened += 1
cand = s.data.get(key)
if cand and (best is None or cand[1] > best[1]):
best = cand
return (best[0], best[1], opened) if best else (None, None, opened)
def space_amp(self, unique_keys):
live = sum(len(s.data) for s in self.ssts) + len(self.mem)
return live / unique_keys
def main():
db = LSM()
keys = ["k%05d" % i for i in range(NKEYS)]
for i in range(NWRITES): # 覆盖写工作负载（更新多于插入）
k = random.choice(keys)
db.put(k, "v%d" % i, ts=1000 + i)
print("=" * 74)
print("[1] 写路径：%d 次逻辑写 -> %d 条记录真正落盘" % (db.logical, db.disk))
print(" flush 次数 = %d, compaction 次数 = %d, 当前 SSTable 数 = %d"
% (db.flushes, db.compactions, len(db.ssts)))
print(" 写放大 WA = 落盘记录 / 逻辑写 = %.2fx" % (db.disk / db.logical))
print(" 空间放大 = 物理记录 / 唯一 key = %.2fx" % db.space_amp(NKEYS))
print("=" * 74)
print("[2] 读路径：Bloom Filter 对读放大的作用")
for use in (False, True):
random.seed(3)
tot = 0
for _ in range(2000):
k = random.choice(keys) if random.random() < 0.7 else "miss%04d" % random.randint(0, 999)
_, _, opened = db.get(k, use_bloom=use)
tot += opened
label = "开启 Bloom Filter" if use else "关闭 Bloom Filter（每次都真读表）"
print(" %-32s 平均打开 SSTable 数 = %.3f" % (label, tot / 2000))
print("=" * 74)
print("[3] Compaction 的效果：把 %d 张表合并成 1 张" % len(db.ssts))
def measure_read_amp(rounds=2000):
random.seed(3)
tot = 0
for _ in range(rounds):
k = random.choice(keys) if random.random() < 0.7 else "miss%04d" % random.randint(0, 999)
_, _, opened = db.get(k)
tot += opened
return tot / rounds
before_ssts, before_amp, before_space = len(db.ssts), measure_read_amp(), db.space_amp(NKEYS)
merged = {}
for s in sorted(db.ssts, key=lambda s: len(s.data)):
merged.update(s.data)
db.ssts = [SSTable(merged)]
db.disk += len(merged)
db.compactions += 1
after_ssts, after_amp, after_space = len(db.ssts), measure_read_amp(), db.space_amp(NKEYS)
print(" SSTable 数 : %d -> %d" % (before_ssts, after_ssts))
print(" 平均读放大 : %.3f -> %.3f （表少了，一次读要碰的表也少了）" % (before_amp, after_amp))
print(" 空间放大 : %.2fx -> %.2fx （旧版本被丢弃、墓碑被回收）" % (before_space, after_space))
print(" 总写放大 WA= %.2fx（compaction 重写是写放大的主要来源）" % (db.disk / db.logical))
print("=" * 74)
if __name__ == "__main__":
main()
实际运行输出（可复现）
[1] 写路径：6000 次逻辑写 -> 16101 条记录真正落盘
flush 次数 = 28, compaction 次数 = 3, 当前 SSTable 数 = 7
写放大 WA = 落盘记录 / 逻辑写 = 2.68x
空间放大 = 物理记录 / 唯一 key = 1.55x
[2] 读路径：Bloom Filter 对读放大的作用
关闭 Bloom Filter（每次都真读表） 平均打开 SSTable 数 = 6.699
开启 Bloom Filter 平均打开 SSTable 数 = 1.078
[3] Compaction 的效果：把 7 张表合并成 1 张
SSTable 数 : 7 -> 1
平均读放大 : 1.078 -> 0.643
空间放大 : 1.55x -> 1.00x
总写放大 WA= 3.00x
【代码做什么？】
put()精确复现写路径：disk += 1（CommitLog 顺序追加）→ 写mem（Memtable）→ 满flush_at=200条就flush()成 SSTable（disk += len(mem)）。compact()实现 STCS（SizeTiered）：把最小的 8 张表合并成 1 张，合并时merged.update(s.data)按从旧到新的顺序覆盖，因此新版本自然胜出（这就是 LWW 在 compaction 里的体现）；合并后disk += len(merged)—— 旧数据被重写一遍，这就是写放大的来源。get()统计平均打开的 SSTable 数作为读放大的度量：关闭 Bloom 时”每张表都要真读”（6.699），开启 Bloom 后降到 1.078 —— 约 6 倍的减少。- 第 [1] 项打印 写放大 2.68x（6000 次逻辑写导致 16101 条记录落盘）；第 [3] 项做一次”全量 compaction”后，SSTable 数 7→1、读放大 1.078→0.643、空间放大 1.55x→1.00x，而写放大升到 3.00x ——三者之间的此消彼长被完整量化。
【分布式机制透视】
- 这台”单机 LSM”就是 Cassandra 每个副本内部的引擎：每个副本独立跑自己的 flush 与 compaction，compaction 完全是本地的，不需要任何跨节点协调——这是 Cassandra 能线性扩展的关键设计（与此相反，任何需要全局协调的合并都会成为瓶颈）。
- 与分布式一致性的连接点：SSTable 不可变使得”读修复 / Merkle Tree 比较”可以在快照上进行；墓碑在 compaction 中被回收的时刻由
gc_grace_seconds约束，与副本间的修复进度耦合——本代码没有建模墓碑，但space_amp的下降恰好就是”墓碑与旧版本被回收”的数值体现。 - 读放大的对比还揭示了分布式读的代价结构：客户端看到的读延迟 = 协调者选副本 + 每个副本本地的读放大（
opened张 SSTable 的磁盘访问）的最大值。所以”读修复能提高一致性，但 SSTable 太多会直接拖慢读”，这也是为什么需要 LCS/compaction 调优的原因。
【与理论的对应】
if use_bloom and not s.bloom.maybe(key): continue这一行是 算法 9.3.2 的local_read的核心，其安全性由 定理 T2/C2 保证。merged.update()的”从旧到新覆盖”对应 算法 9.3.3 的win(V) = argmax(ts, value_bytes)在 compaction 场景下的等价形式（当键唯一时，后覆盖即取最大时间戳）。- 写放大 / 读放大 / 空间放大的三角关系，正是 9.2.18 中 STCS 与 LCS 权衡的量化依据（LCS 把读放大压到 $O(\text{层数})$，代价是写放大升到 10–20x — 与这里的 STCS 的 2.68–3.00x 形成鲜明对比）。
9.5 性能与可扩展性分析
9.5.1 写吞吐：为什么 Cassandra 的写快得不讲道理
| 因素 | 作用 | 量化 |
|---|---|---|
| CommitLog 顺序追加 | 磁盘只做顺序 IO，几乎无寻道 | 讲义实测：MySQL 平均写 300 ms vs Cassandra 0.12 ms（数据量 > 50 GB） |
| Memtable 常驻内存 | 写路径上没有读、没有行锁、没有冲突检查 | 写延迟与”数据总量”解耦，只与内存和日志带宽有关 |
| SSTable 不可变 | 读不阻塞写，写不阻塞读 | 无锁并发，可用满所有核 |
| $W$ 决定等待时间 | 客户端只等第 $W$ 快的 ack，而不是全部副本 | $W=1$ 时延迟 $\approx$ 最快副本的 RTT |
| 任意节点可写（无主） | 没有 leader 成为写瓶颈，可线性扩展 | 集群吞吐随节点数近似线性增长 |
| 提示移交 | 单个副本故障不阻塞写 | 优雅降级而非报错 |
瓶颈在哪：Compaction（写放大）、磁盘容量与 IO 带宽、以及”分区键热点”。写吞吐的上限不是 CPU，而是”磁盘每秒能顺序写多少 + compaction 能多快地把重复数据合并掉”。若分区键选得不好（如以时间戳为分区键），再多的节点也只有一台在忙——这是”无热点”的前提被打破时最典型的扩展性崩塌。
9.5.2 读延迟与读放大
| 读路径环节 | 代价 | 优化手段 |
|---|---|---|
| Memtable 查找 | 内存，$O(\log n)$（有序结构） | 内存足够时命中率越高越好 |
| 每个 SSTable 的 Bloom 检查 | $O(k)$ 次哈希（常数） | bloom_filter_fp_chance 越小越少误开表，但内存越贵 |
| 真正打开 SSTable | 一次磁盘 seek + 读 | 减少 SSTable 数（compaction、LCS） |
| 合并多版本 | 比较时间戳 | 减少版本数（compaction） |
| 跨副本 | 等待第 $R$ 快的副本 | 提高 $R$？→ 延迟上升；降低 $R$？→ 可能陈旧 |
- 读比写慢是设计的结果：一行可能被拆散在多个 SSTable中，一次读要触碰多张表。讲义实测 Cassandra 平均读 15 ms（MySQL 350 ms）——仍远快于 RDBMS，但比自己的写慢两个数量级。
- 读放大的三个来源：SSTable 数量（LSM 版本数）、跨副本的 $R$ 个并行读、以及墓碑（读一个已删除的 key 必须扫完所有墓碑）。
- 长尾效应：读延迟由最慢的那个被选中副本与最慢的那张被打开的 SSTable 决定。因此”复制到更多节点”并不降低单次读的 P99，反而增加了遇到慢节点的概率（这也是 hedged request / 读修复 + LOCAL_QUORUM 这类优化的动机）。
9.5.3 Compaction 的写放大、读放大与空间放大的三角
| 指标 | 定义 | STCS | LCS | TWCS |
|---|---|---|---|---|
| 写放大 | 每 1 字节逻辑写导致多少字节物理写 | 低（约 2–3x，本讲代码实测 2.68–3.00x） | 高（约 10–20x，每层约 10 倍重写） | 最低（旧窗口不再重写） |
| 读放大 | 读一个 key 需触碰的 SSTable 数 | 中–高（层级数） | 低（≈ 层数，通常 ≤ 2/层） | 低（只查相关时间窗） |
| 空间放大 | 物理占用 / 逻辑数据量 | 高（最大层可达 ~50% 冗余，代码实测 1.55x） | 低（约 10%） | 低（可整体按 TTL 丢弃） |
| 最适负载 | — | 写密集、通用 | 读密集、延迟敏感、更新频繁 | 时序、日志、只写不更新 |
- 三者不可同时最优（RUM 猜想）：这是存储引擎的第一性权衡。选择 compaction 策略本质上是选择”你愿意为哪种放大付费”。
- 写放大的连锁反应：LCS 的 20x 写放大意味着 SSD 寿命、IO 带宽与副本间修复带宽都被放大 20 倍；因此”更省空间的策略”往往是最贵的策略。
- compaction 与修复的相互作用（补充说明）：compaction 期间产生的 SSTable 新版本会改变 Merkle Tree 的哈希，因此repair 与 compaction 不应在同一个区间上并发进行；Cassandra 通过快照与调度尽量避免这种冲突。
9.5.4 $W$/$R$ 的选择：延迟、可用性与成本的联合权衡
| $(W,R)$，$N=3$ | 一致性 | 客户端写延迟 | 客户端读延迟 | 写可用性（可容忍副本故障数） | 读可用性 | 典型用途 |
|---|---|---|---|---|---|---|
| $(1,1)$ | 最终 | 最低（$T_{(1)}$） | 最低 | 2 | 2 | 日志、计数器、可容忍陈旧 |
| $(2,2)$ | 强 | 中 | 中 | 1 | 1 | 通用默认（LOCAL_QUORUM） |
| $(3,1)$ | 强 | 高（等全部 ack） | 最低 | 0 | 2 | 读密集 |
| $(1,3)$ | 强 | 最低 | 高 | 2 | 0 | 写密集、单写者 |
| $(3,3)$ | 最强 | 最高 | 最高 | 0 | 0 | 类 RDBMS 语义，最不可用 |
ANY+$(1)$ | 无保证 | 最低 | 最低 | 3（全宕也能写） | 2 | 只为”永不拒绝写”的服务 |
- 核心洞察：$W$ 与 $R$ 是可调的旋钮，但”调高一致性”的代价同时落在延迟和可用性上。$W=N$ 时”任一副本故障即写失败”，$R=N$ 时”任一副本故障即读失败”——强一致性是用可用性买来的。
- 生产建议：单 DC 用
LOCAL_QUORUM/LOCAL_QUORUM（避免跨 DC RTT）；跨 DC 用LOCAL_QUORUM/EACH_QUORUM，并按”是否需要跨 DC 强一致”决定是否升级为全局QUORUM。 ANY的陷阱：ANY只用于写。它保证”永远能写”，但不保证”写得能被读到”——因为这 $W$ 个”副本”可能只是 hint。
9.5.5 跨数据中心复制的延迟
| 部署方式 | 一致性级别 | 延迟 | 说明 |
|---|---|---|---|
| 单 DC | LOCAL_QUORUM | 1 个局域网 RTT（亚毫秒–几毫秒） | 生产常见形态 |
| 双 DC，各 3 副本（$N=6$） | 全局 QUORUM（需 4 个 ack） | 必须等待跨 DC 往返（同区域 ~10–40 ms，跨洲 100–200 ms） | 强一致但慢；写延迟由 WAN 决定 |
| 双 DC | LOCAL_QUORUM（各 DC 各自 2 个 ack） | 只有本地 RTT | 快，但跨 DC 只是最终一致 |
| 双 DC | EACH_QUORUM（写） | 每个 DC 都必须达到多数 | 保证每个 DC 都能立即读到自己的写，但写延迟 = 最慢 DC |
- 量化直觉：$N=6$ 时
QUORUM = 4，写要凑够 4 个 ack；若 3 个副本在本地 DC、3 个在远端 DC，则至少要等 1 个远端 ack ⇒ 写延迟从”局域网 RTT”变成”WAN RTT”，上升一到两个数量级。这就是 9.2.10 中”一致性旋钮的代价以毫秒计费”的物理含义。 - 异步跨 DC 复制（如 HBase 的 Leader→Follower HLog 同步、Cassandra 的多 DC 后台修复）则把 WAN 延迟移出关键路径，代价是跨 DC 读可能陈旧。
9.5.6 Gossip 成员管理的 $O(N)$ 开销与集群规模上限
- 开销结构：gossip 的每条消息包含全体成员的状态摘要（$O(N)$ 条目）；每个节点每秒与常数个（Cassandra 默认最多 3 个）节点交换。因此每节点的 gossip 带宽与消息处理开销是 $\Theta(N)$，全集群总开销 $\Theta(N^2)$。此外每个 token/range 的调度、repair 与 compaction 的元数据量也随 $N$ 增长。
- 规模上限的工程结论：
- 单数据中心的节点数与
num_tokens（vnodes）共同决定了 range 数量。num_tokens=256时，100 个节点就有 25600 个 range——每个 range 都要参与 repair 调度、gossip 元数据与 streaming，管理开销非常可观。这正是社区把默认num_tokens一路下调（256 → 16 → 8 → 单 token）的原因； - 单集群规模的运维经验是”数百到 ~1000 节点量级“比较稳妥；再往上，gossip 的 $O(N)$ 摘要、repair 的全量扫描时间、以及”必须每个节点每
gc_grace_seconds修复一次“的硬性要求共同构成天花板； - 实务上通过划分多个较小的集群（每个集群服务一组 keyspace/租户）来绕开单集群上限。公开案例中，Apple 曾运行 75,000+ 节点的 Cassandra 部署——但那是多个集群组成的舰队，而不是一个单集群；
- 一个必须在规模上考虑的硬约束：repair 的总工作量是 $O(N \times \text{数据量})$，且必须在
gc_grace_seconds（默认 10 天）内对每个节点完成一次。集群越大、数据越多，这个”修复窗口”越紧，最终成为不可逾越的运维约束。
- 单数据中心的节点数与
- 可扩展性总结表：
| 维度 | 复杂度 | 瓶颈点 | 缓解手段 |
|---|---|---|---|
| 写吞吐 | 近似 $O(\text{节点数})$ 线性 | compaction 写放大、分区键热点 | 好的分区键、STCS、批量写合并 |
| 读吞吐 | 近似线性，但受长尾限制 | 读放大（SSTable 数）、慢副本 | LCS、Bloom、tombstone 治理、hedged reads |
| 元数据/gossip | 每节点 $\Theta(N)$ | 大集群的 gossip 与 range 调度 | 减少 vnodes、限制单集群规模、拆分集群 |
| 修复 | $O(N \times \text{数据量})$，须在 gc_grace_seconds 内完成 | repair 时间随规模线性以上增长 | 增量 repair、减少 vnodes、按需 repair 子集 |
| 跨 DC | 每次跨 DC 写 $+1$ WAN RTT | WAN 延迟与带宽 | LOCAL_QUORUM、异步跨 DC 复制 |
9.6 关键要点
- 一致性与可用性是一个旋钮（knob），不是一个固定属性：Cassandra 默认为 AP（永远可写、最终一致），而 $R+W>N$ 就是把这个旋钮拧回强一致的唯一条件——用”读集合与写集合必相交”（鸽巢原理）把一致性买回来，代价用延迟和可用性支付。
- $P$ 不是选项，是假设：分区容忍不是”要不要支持的功能”，而是”是否假设网络会分区”。因为分区（跨 DC 断连、机架交换机故障、进程 GC 停顿）必然发生，CAP 在三者中真正让你选的只有 C 与 A。
- 写快、读慢是 LSM 的必然结果：CommitLog 顺序写 + Memtable 内存写让写路径没有读、没有锁、没有寻道；而读必须合并 Memtable 与多个不可变 SSTable，因此读放大是这套设计的固有税，Bloom Filter 与 compaction 都是在为这笔税打折。
- 收敛需要三条腿：hinted handoff（快）、read repair（顺手）、anti-entropy/Merkle（兜底）。少了任何一条，系统要么可用性下降，要么最终不再”最终一致”（例如 hint 超过 3 小时窗口丢失、或超过
gc_grace_seconds未 repair 导致墓碑失效）。 - 用确定性函数替代共识：LWW 的
(timestamp, value_bytes)裁决在任意副本上给出同一结果，因此无需 Paxos 也能收敛——代价是并发写会被静默丢弃（这正是 Dynamo/Riak 改用向量时钟、把冲突交给应用的原因）。 - 所有优化都是”三种放大”之间的交易：读放大、写放大、空间放大不可能同时最优（RUM）；compaction 策略、Bloom Filter 参数、$W/R$ 的选择，都是在同一条权衡曲线上选点。
9.7 常见陷阱与注意事项
- 把
ANY当成”至少一个副本”。- 为什么错：
ANY允许协调者把写缓存在本地 hint 中就返回成功，此时没有任何副本持有该数据。随后用ONE去读可能读不到刚写的值（本讲代码第 [3] 项的输出就展示了ok=True但副本值为None）。 - 正确做法：需要 read-your-writes 时，写用
ONE/QUORUM等”真实副本”级别；ANY只用于”绝不拒绝写”的场景（如日志采集）。
- 为什么错：
- 认为 $W>N/2$（或 $W=R=\text{QUORUM}$）单独就能保证强一致。
- 为什么错：强一致的核心条件是 $R+W>N$（读-写交集）；只满足 $W>N/2$ 而 $R$ 很小时（如 $N=5$，$W=3$，$R=1$ 时 $R+W=4 \le 5$）读仍可能取到陈旧值。$W>N/2$ 保证的是写-写相交（避免丢更新），不是读-写相交。
- 正确做法：明确写下你要的保证，然后同时验证 $R+W>N$；生产常用
LOCAL_QUORUM/LOCAL_QUORUM。
- 用 LWW 处理”需要合并语义”的并发写。
- 为什么错：两个用户同时往购物车加商品，LWW 会丢掉其中一件且不报警；时钟偏差会进一步让”后写”被”先写”覆盖。
- 正确做法：需要保留并发信息时用向量时钟/CRDT/应用层合并（如把购物车建模成”集合的并集”这种可交换操作），或把冲突暴露给应用（Riak 的 siblings）。
- 在
gc_grace_seconds内不 repair，或为了省磁盘把gc_grace_seconds设为 0。- 为什么错：墓碑在 compaction 中被清除后，一个长时间离线的副本回来时仍持有”已删除”的数据，它会在读修复/反熵中把删除掉的数据复活。
- 正确做法：保证每个节点在
gc_grace_seconds（默认 10 天）内至少完成一次 repair；对只写不删的数据用 TWCS+TTL 从根上避免墓碑问题。
- 把 Merkle Tree 当成”万能比较器”而忽略前提。
- 为什么错：若两副本的排序/schema/分区器不一致，树形结构就不同，比较结果全是”不同”，修复退化为全量传输；若在非快照数据上建树，会产生虚假差异；若墓碑处理不当会复活数据。
- 正确做法：保证 schema 与分区器一致、在快照上构建、把墓碑纳入比较并在
gc_grace_seconds窗口内完成 repair。
- 用单调递增的值（时间戳、自增 ID）作分区键，或用
ByteOrderedPartitioner图省事。- 为什么错：所有写都会集中到环上的同一个区间（同一台机器），集群再大也只有一台在写：这就是热点。
ByteOrderedPartitioner虽然让范围查询变快，但它把”负载均衡”这个更重要的性质牺牲掉了。 - 正确做法：用
Murmur3Partitioner+ 高基数的分区键（如(user_id, bucket)），把范围查询交给聚簇键在分区内完成。
- 为什么错：所有写都会集中到环上的同一个区间（同一台机器），集群再大也只有一台在写：这就是热点。
- 把
W/R设成ALL来”保证安全”。- 为什么错：
ALL让任一副本故障就写/读失败，可用性最低——在 1000 台机器的集群里，”总有一台在重启”是常态，ALL会让系统几乎不可用（这直接违背 BASE 的初衷）。 - 正确做法：用满足 $R+W>N$ 的最小组合（如 $N=3$ 时 $2/2$），把冗余留给容错而不是浪费在等待全部副本上。
- 为什么错：
- 以为”最终一致”意味着”总会一致，不用管”。
- 为什么错：收敛依赖机制被正确运维——hint 有 3 小时窗口、repair 必须在 10 天内跑完、读修复只覆盖被读到的 key。任何一环缺失，数据就永远不一致（不是”晚一点一致”）。
- 正确做法：把 repair 纳入例行运维（监控
nodetool repair的完成度与时间），监控 hint 队列长度与墓碑数量（tombstone_warn_threshold）。
9.8 思考题（带答案）
题 1（计算与推演）：某键空间使用 NetworkTopologyStrategy，DC1 有 5 个副本、DC2 有 3 个副本（$N=8$）。 (a) 全局 QUORUM 的 $R$、$W$ 分别是多少？它满足 $R+W>N$ 吗？请另举一个”看起来稳妥、实际不满足 $R+W>N$”的常见组合。 (b) 若要求在 DC1 内实现强一致（不等待 DC2），LOCAL_QUORUM 是多少？此时在 DC1 内部满足 $R+W>N$ 吗？跨 DC 的读会不会看到旧值？ (c) 若应用改用 $(W=1, R=1)$ 的 LOCAL_ONE，最多能容忍多少个副本同时故障而读仍成功？
答案： (a) 全局 QUORUM $= \lfloor N/2 \rfloor + 1 = \lfloor 8/2 \rfloor + 1 = 5$。因此 $R=W=5$，$R+W=10 > 8$ ✔ 满足（可以证明：对任意 $N$，$2(\lfloor N/2 \rfloor + 1) > N$ 恒成立，所以 QUORUM/QUORUM 永远满足 quorum 条件）。但”用了 QUORUM”绝不等于”一定强一致”——反例是把 QUORUM 与一个更弱的读级别混搭：$(W=5, R=1)$ 时 $R+W = 6 \le 8$，读照样可能陈旧。更常见的直觉陷阱是”写达到多数就够了”：$N=5$ 时 $(W=3, R=1)$ ⇒ $4 \le 5$ ✗；$N=3$ 时 $(W=2, R=1)$ ⇒ $3 \le 3$ ✗。$W$ 达到多数只保证”任意两次写有交集”（避免丢更新），不保证”读与写有交集”。 (b) DC1 内 LOCAL_QUORUM $= \lfloor 5/2 \rfloor + 1 = 3$；DC2 内则是 $\lfloor 3/2 \rfloor + 1 = 2$。用局部的 $N=5$ 验证：$3+3 = 6 > 5$ ✔，所以 DC1 内部是强一致的（客户端在 DC1 读写时，只要都用 LOCAL_QUORUM）。但跨 DC 的读可能看到旧值：写只保证 DC1 的 3 个副本，DC2 的副本是异步被复制的；若客户端跑到 DC2 用 LOCAL_QUORUM 读（只要求 DC2 内 2 个副本），此时 DC2 可能一个副本都还没收到该写，于是返回旧值。要跨 DC 强一致，必须用全局 QUORUM（$R+W=10$）或写入用 EACH_QUORUM，代价是每次写都要等 WAN 往返。 (c) LOCAL_ONE 的读只要求协调者所在 DC 内 1 个副本响应。若客户端在 DC1，则最多可容忍 DC1 的 5 个副本中 4 个故障；若使用全局 ONE（可落在任意 DC 的副本上），则可容忍 $N-1 = 7$ 个副本故障。但代价是既不保证读到最新值（$R+W = 2 \ll 8$），也不保证读修复能选对”最新版本”——这是”用一致性换可用性”的极端点。
题 2（推演）：$N=5$，客户端 A 在 $t=100$ 写 $v_1$（$W=2$），客户端 B 在 $t=101$ 写 $v_2$（$W=2$）。两次写都返回成功。 (a) 用 LWW 裁决，最终哪个值会存活？在什么情况下这会丢掉 A 的写，即使 A 的写在真实时间上更晚发生？ (b) 若系统改用向量时钟（Dynamo/Riak），会有什么不同？为什么 Cassandra 不这么做？ (c) 如果两次写的时间戳完全相同，系统靠什么保证所有副本收敛到同一个值？
答案： (a) LWW 取 (ts, value_bytes) 最大的版本 ⇒ $v_2$（$ts=101$）存活。若客户端 A 的本地时钟比 B 慢 5 个单位，而 A 的写实际上发生在 B 之后（例如 $t=110$ 才发起），A 会带上 $ts=105$（因为它的钟慢）——仍然小于 101？不，$105>101$，所以存活的是 A——这说明”钟慢”不必然导致丢失，关键看偏移量。真正会丢失的场景是：A 的写时间戳因为时钟偏差而小于 B 的写时间戳，但 A 的写发生在 B 之后（例如 A 的钟慢 20 个单位：A 在真实时刻 110 写、时间戳为 90，而 B 在真实时刻 101 写、时间戳 101 ⇒ A 的写被静默丢弃）。总之：只要”时间戳的顺序”与”真实发生的顺序”不一致，LWW 就会丢掉”真正的最后一次写”，而且不会有任何报错。 (b) 向量时钟能判断 $v_1$ 与 $v_2$ 是否并发：若两个版本不可比（各自记录了对方未知的更新），Dynamo/Riak 会同时保留两个版本（siblings）并返回给客户端，由应用合并（例如把两个购物车合并）。区别是：LWW 会丢掉信息，向量时钟会保留冲突。Cassandra 不这么做，是因为它追求极简的写路径与确定的收敛：一旦引入”需要应用参与合并”的语义，客户端复杂度、元数据体积（每个版本带一个向量）与垃圾回收的复杂度都会显著上升，而大多数 Cassandra 目标场景（时序、日志、消息）不需要合并语义。 (c) 靠 tie-break：值本身的字节序。LWW 的完整定义是 $\arg\max (ts, value\_bytes)$；由于字节序比较是确定性的，任何副本用同一组候选版本独立计算都会得到同一个赢家，因此系统收敛。如果没有这个 tie-break（例如按”本副本先看到的为准”），并发写会导致副本永久发散。这个细节是”用确定性函数替代共识”的关键。
题 3（”直观但错误的想法”错在哪）：”Cassandra 用时间戳做冲突解决，所以在所有节点上部署 NTP 把时钟同步到毫秒级，LWW 就正确了，也就等于有了强一致性。”
- 错在哪：
- NTP 只能把偏差压小，不能消除，而且会跳变（步进校正可能让时间倒退），毫秒级偏差在”背靠背写”的场景下就足以让 LWW 选错；
- 即便时间戳绝对准确，LWW 仍然会丢弃并发写——它无法区分”后来的写”与”并发的写”，这是语义问题，不是时钟问题；
- 强一致性根本不是 LWW 能提供的：强一致（读不旧于最近一次成功的写）要求读集合与写集合相交，即 $R+W>N$；时间戳只解决”谁赢”，不解决”读能不能遇到写”。时钟同步再完美，$R=W=1$ 也照样读到陈旧值。
- 正确做法：把这两件事分开——用 $R+W>N$ 获得读-写交集（一致性），用时间戳获得收敛（唯一赢家）；对时钟偏差敏感的场景，改用向量时钟/CRDT，或把 LWW 的裁决权交给应用。
题 4（计算）：某副本与对端的历史 gossip 到达间隔均值 $\mu = 2.0$ s、标准差 $\sigma = 0.5$ s。当前已静默 $t = 3.0$ s。 (a) 用正态近似求 $\phi$，并判断在阈值 5 与 8 下是否触发怀疑。 (b) 若网络抖动增大到 $\sigma = 1.5$ s，$\phi$ 变成多少？这说明了什么？
答案： (a) $z = (3.0-2.0)/0.5 = 2.0$，$\text{CDF}(2.0) \approx 0.9772$，$P_{later} \approx 0.0228$，$\phi = -\log_{10}(0.0228) \approx 1.64$。阈值 5 和 8 都不触发（$\phi$ 远小于它们），节点仍被视为存活。若要 $\phi > 5$，需要 $P_{later} < 10^{-5}$ ⇒ $z \gtrsim 4.4$ ⇒ $t > 2.0 + 4.4\times0.5 = 4.2$ s。 (b) $z = (3.0-2.0)/1.5 = 0.667$，$\text{CDF}(0.667)\approx 0.748$，$P_{later} \approx 0.252$，$\phi \approx 0.6$ —— 怀疑度更低。这说明 $\phi$ 是自适应的：在网络抖动大的环境里，同样的静默时长被认为是”正常波动”；而在网络稳定的环境里，同样的 3 秒就可能意味着故障。这正是 Φ 累加检测器相对固定超时的核心优势——它把”抖动”这一信息纳入了判定。