参考：反熵与故障检测

它是什么

一个有几百个节点的集群没有中心化的 master 来说明谁还活着、哪个副本已经过期，所以它必须自己搞清楚。有两类机制来做这件事。故障检测与成员关系（gossip）回答”谁在集群里，谁挂了？“；反熵与修复（hinted handoff、read repair、Merkle 树）回答”哪些副本已经漂移，它们怎么收敛？“二者合起来，让故障成为系统持续处理的一种稳态，而不是需要有人去处理的事件。

Important

核心要点： 按故障持续的时间使用分层的修复：用 hinted handoff 处理几分钟到几小时的故障，用 read repair 作为读操作的副产品修复热点 key，用 Merkle 树反熵处理永久丢失。hint 是一张欠条，不是副本。

何时需要它

对一个有复制的存储，任何”节点挂了会怎样？“的追问都落在这里，而在几百个节点的规模上，故障是常态。常见的陷阱是把 hinted handoff 当成持久性的全部。面试官想听到的是分层，以及每一层存在的原因。

Note

面试信号： 按持续时间把故障分开（暂时的、永久的），并为每种说出一个修复机制，说明你运行过集群。再补一句：副本同步时，Merkle 比较只花几 KB，所以修复可以持续运行，这是让回答落地的细节。

成员关系：gossip

环的成员关系不存放在中央 master 里；那会把 leaderless 设计已经去掉的单点故障又引回来。每个节点维护自己的视图，并通过 gossip 对账：

每秒，每个节点挑几个随机的对等节点，交换自己的环状态：节点 id、token 位置、心跳计数器、状态。
信息像流行病一样扩散：大约经过 log₂ N 轮之后（150 个节点的集群中大约 7 轮），每个节点都看到了更新。
每个条目带一个 generation（更高表示节点重启过）和一个 version（更高表示它的状态变了）。较新的总是胜出。

一次加入或离开会在几秒内传遍整个集群。一个怀疑对等节点宕机的节点，会开始绕开它走，这只是本地的怀疑，不是经过 quorum 一致同意的事实。这对这种设计是对的：一次错误的怀疑只会多出几个不必要的 hint，而不是一次 failover。Seed 节点（每个区域两三个知名地址）只是为了让新节点能找到它的第一批对等节点。

故障检测有一个取舍：短超时能快速发现真正的故障，但会把慢节点（比如一次垃圾回收暂停）误判为死亡；长超时稳定，但反应慢。许多系统使用自适应的检测器，根据每个对等节点的心跳间隔有多反常来给它打分，而不是用固定的超时。

修复的分层

故障	机制	它做什么	局限
暂时的（几分钟到几小时）	Hinted handoff	由一个替身节点存储错过的写入，目标恢复后再把它们重放给它	hint 会过期；替身节点如果先挂了，hint 就丢了
读到过期副本	Read repair	coordinator 把最新版本推送给任何返回了旧版本的副本	只修复被读到的 key
永久丢失或长期漂移	Merkle 树反熵	副本比较哈希树，只传输有差异的 key 范围	后台工作；需要带宽和调度

Hinted handoff。 当某次写入的某个副本宕机时，coordinator 把那份副本写到下一个健康的节点，并打上一个 hint 标记。替身把它保存在单独的缓冲区里（不在它的主 keyspace 里），带有时间限制，并在目标恢复时重放。

Caution

常见错误： 把 hint 写入永远算作持久的副本。如果替身在重放之前死了，那份副本就没了，这个 key 就悄悄地以复制因子 2 在运行。Hint 是给暂时性故障打的补丁；真正持久的修复是反熵。

Read repair。 当一次读在它的 R 个响应里发现一个过期的副本时，coordinator 会异步地把胜出的版本发回给它。热点 key 被读得最勤，所以也修复得最快，这是对的倾向。

Merkle 树反熵。 每个节点为每个 key 范围维护一棵 Merkle 树：叶子对一段 key 取哈希，父节点对其子节点取哈希。两个副本先比较根：

比较根哈希 -> 相同？  完成：该范围已同步（一条消息）
          -> 不同？  比较子节点，递归
                     -> 找出有差异的叶子范围
                     -> 只传输这些 key

算例。 副本同步时，比较一个几 GB 的范围只花几 KB 的哈希，而这是常见情形，所以集群可以负担得起持续地运行修复。当它们不同时，只有存在差异的片段会被传输，而不是整个范围。单个 key 的差异，代价是沿树向下走一遍（约 log₂ 叶子数的比较）外加一个片段，而不是一次全量扫描。

删除也是写入

删除不能简单地移除记录：错过了这次删除的副本会在修复时把这个 key 复活，因为”缺失的 key”和”从未写过的 key”看起来是一样的。所以删除要写入一个 tombstone，一个带版本的”这个 key 已被删除”的标记，它像任何写入一样传播，并在版本比较中获胜。Tombstone 会保留一段宽限期，这段期间要长于最长的修复间隔，之后才被 compaction 清除。如果某个副本宕机的时间超过了这段期间，就应该通过重建它把它找回来，而不是让它带着旧数据重新加入，否则已删除的 key 会回来。

尾延迟：hedged read

一个相关的问题是不是死了、而只是慢的节点。在 N=3, R=2 时，一次读要等第二快的响应，但垃圾回收暂停或 compaction 突发会让某些响应慢得多。Hedged request 的做法是：如果预期的响应在一个阈值（大约中位延迟）内还没到，就把读发给一个额外的副本，并使用最先到达的 R 个响应。慢的副本被绕过，而不是被等待。

算例。 没有 hedging 时，向 A、B、C 发读请求，A（3 ms）和 B（8 ms）响应后返回；如果 B 卡在一次 50 ms 的暂停后面，读就要 50 ms。设置 5 ms 的 hedge 阈值，5 ms 时向 D 发出请求，D 在 6 ms 响应，读在 6 ms 返回。代价是少量额外请求（只有慢的那几个百分点会被 hedge）；收益是 p99 向 p50 靠拢。Google 报告说，用不到 5% 的额外负载，把 p99 降低了一半甚至更多。

如何选择

情形	机制
一个节点短时间宕机	Hinted handoff；确保 hint 会过期
一个 key 的副本不一致，并且这个 key 经常被读	Read repair
节点丢失，或副本长期漂移	Merkle 树反熵，持续调度
节点很多，没有 master	带 generation 和 version 的 gossip
一个慢副本拉高了 p99	在大约中位延迟处做 hedged read
一个节点在长时间故障后回来	重建它；不要让过期数据复活已删除的 key