数据库系统内幕

反熵和传播

｜

213

及其每个接收者都必须在工作时间上有重叠，而这在某些情况下可能难以实现。

为了放宽这些限制，我们可以假设

某些

更新可能会传播失败。协调者尽力将消息传递给所

有可用的参与者，而一旦出现故障，反熵（anti-entropy）机制会让节点重新同步。这样，

传递消息的责任由系统中所有节点共同承担，并分成两个步骤：主要传递和定期同步。

熵

（entropy）是一种衡量系统无序程度的属性。在分布式系统中，熵表示节点之间的状

态分歧程度。我们希望将熵保持在最低的水平，有许多技术可以帮助减少熵。

反熵机制通常用于在主要传递机制失败的情况下将节点恢复最新状态。即使协调者在某

个时刻发生故障，系统也可以继续正常运行，因为其他节点将继续传播信息。换句话

说，在最终一致的系统中，反熵被用来降低收敛的时间界限。

为了保持各节点的同步，反熵会触发一个后台或前台进程，比较和调和丢失或冲突的记

录。后台反熵进程会利用 Merkle 树之类的辅助数据结构，从更新日志中识别出分歧的数

据。前台反熵进程会捎带（piggyback）地在读取或写入请求上附加额外逻辑，比如提示

移交、读修复等。

如果多副本系统中的副本间出现分歧，为了恢复一致性和同步，我们必须通过成对比较

副本状态来查找和修复丢失的记录。对于大型数据集这会非常耗时：我们必须从两个节

点分别读出整个数据集，并将尚未传播的、包含最新状态的更改通知相关副本。为了降

低成本，我们可以考虑副本过期的方式以及数据访问的模式。

12.1

读修复

读取时最容易检测出副本之间的差异，因为此时我们可以联系副本，从每个副本上查询 ...