反熵与传播

一句话

上一章的最终一致性承诺了「停写后终将收敛」，本章揭穿它：那个「终将」不是时间的恩赐，是一笔持续的运营支出。复制协议只负责尝试送达，送不到的部分必须由反熵（anti-entropy）另行补齐——书里把补齐的时机拆成三条互补通道（读时修复、写时暂存、后台比对），再用 gossip（流行病式传播）解决「怎么把信息扩散到全集群」。要建立的认知是：收敛是你雇人去做的事，不是协议的副产品；没人跑 repair 的最终一致集群，「最终」等于「永不」。

Glossary · 术语表

坐标

本章属 Part II「分布式系统」，接在 Ch11（复制与一致性）之后：上一章把一致性排成一条谱系，并把最便宜那档定义为「停写后终将收敛」；本章负责把那个「终将」兑现，也顺带给出集群元信息（成员、故障、schema 版本）的扩散办法。下接 Ch13–14（分布式事务与共识）——那是另一条路：不事后补账，而是事前协调。对应现实里 Cassandra 的 hints / read repair / nodetool repair / gossip 四件套、DynamoDB 与 Riak 的后台 AAE、Consul 与 Serf 的成员传播。

这章要解决什么

先看一个不算故障的场景：三副本、QUORUM 写（w=2）。协调者拿到两个确认就向客户端返回成功——此刻第三个副本上根本没有这条数据，而系统认为一切正常。发散不是异常路径，它就在正常路径上。

再放大：一台节点滚动升级离线 20 分钟，期间集群承接 3000 QPS 写入、其中 1/3 归它负责——回来时它缺了约 360 万条写。而系统并不知道自己差在哪：漏一条和漏三百万条，对外都只表现为「有时读到旧值」。

不解决会怎样？三件事，一件比一件严重：① 陈旧读永久化——那条旧值不会自己消失，会一直被读到；② 删除复活——墓碑过了宽限期被清理，而落后副本手上还留着老数据，下次比对时它会把「自己有、同伴没有」当成对方缺失，热心地把删掉的数据传回来；③ 「最终一致」沦为口号——没有上界的「终将」，工程上等于没有保证。

核心内容，讲透

三个时机：读路径、写路径、后台

本章按「什么时候补账」组织而不是按算法。三条通道覆盖面与成本各异，互为补充而非互相替代——这是整章最该先装进脑子的结构。

读修复与摘要读：搭读请求的便车

读一次本来就要联系多个副本，那就顺便比一比。工程上的关键细节是摘要读：只让一个副本返回完整数据，其余只返回哈希摘要——摘要一致时网络上只走一份数据，对不上才补取全量。「顺手校对」的常态成本因此接近于零。

另一个必须分清的开关是阻塞式还是非阻塞式：阻塞式先把修复写下去、等够一致性级别再返回，读延迟里多一次写往返，换来「单调 quorum 读」（不会出现上一章那种两次读先新后旧）；非阻塞式只在协调者内部合并出正确答案返回，不去修那个落后的副本。

它的根本局限只有一句：只修被读到的数据。冷数据、归档分区、写完再没人碰的 key，永远轮不到。所以读修复是压低常见陈旧度的好工具，但绝不是收敛的保证。

提示移交：写路径上的「代收快递」

目标副本联系不上时，协调者不必让整次写失败，而是把这条变更连同「本该给谁」存成一条提示（hint），等对方复活再重放。它和 sloppy quorum（松散 quorum）是一对：写落在「前 n 个健康节点」上，而不必是本该负责的那 n 个——短时故障于是不再转化为写失败。

代价在三处：① hint 有保质期（Cassandra 默认 3 小时），超时即丢弃，那个副本就一直落后到下次 repair；② hint 本身没有冗余——存它的协调者也挂了，这笔账直接蒸发；③ 恢复瞬间的重放流量容易把刚起来的节点再压垮。所以它的定位是「尽力而为」，不是保证。

Merkle 树：先比指纹，再逐层下降

后台兜底要回答的是：两个各存上亿条记录的副本，怎么在不传全量的前提下找出分歧？答案是哈希树——叶子是每段数据的哈希，父节点是子哈希的哈希，一路收到根。比对时先换根哈希：相同就整棵树跳过；不同则取两个子节点哈希，只沿不一致的那侧下降，直到定位到叶子。通信量于是从「数据量」降到「树高」量级，记作 O(log n)——数据翻一倍，只多问一层。

三个必须一起记住的代价：① 粒度——叶子不是单条记录，而是一段 key 范围，一个叶子对不上就得传整段（过度流式），修 1 行可能搬几百兆；② 重算——树要覆盖全部数据才有意义，所以构建它要读全量数据，磁盘与网络 IO 都不便宜；③ 拓扑变化即失效——加减节点会让 key 范围重新划分，对应的树得重建。

书里也给了针对「重算」的改进：位图版本向量（bitmap version vectors）——不比数据，只记「我见过谁的第几号写」，用一个位图紧凑表示已收到的写序号集合。副本交换这份摘要就能直接算出对方缺哪几条，只补这几条，完全不扫全量。代价是它只对近期缺失有效；长期失联或静默损坏仍要 Merkle 兜底。

Gossip：用冗余换鲁棒

另一半问题是传播：成员变更、故障怀疑、schema 版本这类元信息要让全集群都知道。直接广播要每个节点联系所有人（消息量随节点数平方增长），固定广播树又一断就整条支路失联。gossip 的答案是概率性扩散：每个节点每隔一个周期（Cassandra 是 1 秒）随机挑 f 个同伴交换状态。

书里借流行病学的三态刻画它：易感（还没收到）、感染（收到且正在转发）、移除（收到但不再转发）。从「感染」转为「移除」的时机，就是这个协议真正的调参点：转得太早可能传不全网，转得太晚则满网重复消息。三种交换方式各有脾气：push 早期快、后期浪费；pull 收尾快；push-pull 收敛最快，代价是每轮消息更大。

收敛轮数随节点数对数增长——记作 O(log N)，意思是集群从 100 台涨到 1000 台，传遍全网只多几轮而不是多十倍。这就是为什么成员管理几乎都用 gossip：它对规模不敏感，对故障也不敏感。

从随机到有结构：覆盖网络、混合 gossip、部分视图

纯随机 gossip 的痛处是消息冗余：同一条消息被同一个节点收到七八次很常见，带宽白烧。而一棵固定的生成树（每条消息只走 N-1 条边）效率最优，却一个内部节点挂掉，整条支路失联。本章给出的调和方案是混合 gossip（hybrid gossip），代表是 Plumtree：

• 急切推送（eager push）：沿着一小撮「树边」直接把完整消息推过去——这部分承担绝大多数流量，效率接近生成树。
• 惰性推送（lazy push）：向其余邻居只发一条「我有消息 #42」的通告（几十字节）。正常情况下对方早从树边收到了，通告被丢弃；一旦树断了，只收到通告却等不来正文的节点就主动去拉，并把这条边升级成树边——树自己长好了。

最后一块拼图是部分视图（partial views）：节点不必认识全集群，只维护一小撮活跃邻居（log N 量级）加一份备用名单，挂了就补位（HyParView 一系）。单节点开销于是不随集群规模线性增长——上千节点才可能只靠 gossip 维持成员关系。

关键权衡与选型

表 1 · 三条反熵通道：各补什么、漏什么

表 2 · 传播方式：把消息送到全集群的四条路

判据压成两句。补账通道要全选：它们是三层防线不是备选项，只按数据热度调配比重——热数据靠读修复就能把陈旧度压到很低，冷数据只能指望 repair 的节奏。传播方式看「消息多大、成员多稳」：小而多变的元信息用纯 gossip；负载大又要容错，才值得上混合 gossip 那套复杂度。

为什么重要 / 落到真实系统

这一章的实用价值是把一句运维直觉变成可设计的东西：最终一致系统的健康度，等于你的反熵预算。架构评审里最常见的错，是把「我们用了最终一致的存储」当结论，却没人回答「repair 多久跑一轮、跑得完吗、跑不完会怎样」。面试同理：能说清「读修复为什么替代不了 repair」「hint 过期后会发生什么」，比背出 gossip 三个字有分量得多。

对照真实系统：Cassandra / ScyllaDB 把四件套（hints、read repair、nodetool repair、gossip）全套摆出来，是本章最直接的实现；DynamoDB 与 Riak 走 Dynamo 原路，Riak 的主动反熵（AAE）常驻哈希树；Consul / Serf 用 SWIM 式 gossip 管成员与故障；Redis Cluster 用 gossip 传播槽位与节点状态。反例同样重要：etcd 与 CockroachDB 走共识路线，写入时就必须过多数派，因此根本不需要反熵——这正说明反熵是「事后补账」这条路线特有的运营成本。

易错点与争议

• 最大的误解：以为读修复能代替 repair。它只修被 SELECT 覆盖到的数据，冷分区一辈子轮不到；把它当收敛保证，就是在等数据复活。
• hint 不是保险箱。过期（默认 3 小时）会丢，存 hint 的协调者挂了也会丢——它降低的是「短暂抖动变成写失败」的概率，不提供任何持久保证。
• 「最终一致」的最终，由 repair 节奏定义。宽限期 10 天、每 7 天跑一轮全集群 repair，这不是调优建议而是正确性底线；跑不完，删除就会复活。
• 过度流式常常比想象中贵。叶子覆盖一段 key 范围，差一条记录也要重传整段——很多「repair 把集群打挂了」的事故源头在这里，而不是算法本身。
• 别拿 gossip 传需要确定性的事。它没有交付上界、也不保证顺序。「谁是主」「这次 DDL 生效了吗」必须走共识（Ch14），gossip 只适合可以晚一点知道、且知道错了还能自我纠正的信息。
• 冗余不是 bug，是 gossip 的保费。一味调小扇出省带宽，买来的是传播不全的尾部风险；省带宽的正确做法是混合 gossip。
• 时代位置与反方。2019 年成书时，位图版本向量还偏新，混合 gossip 也主要停留在论文与少数系统里。另一派观点越来越响：既然反熵的运营成本这么高，不如一开始就用共识把写做对——CockroachDB、etcd 的流行即此立场。公允的说法是：反熵买的是分区期间仍可写入的能力，月租就是 repair。

要点