反熵（Anti-Entropy）

反熵（Anti-Entropy）是分布式存储系统中用于修复副本不一致的一种后台机制。它源自热力学中熵代表无序的类比:系统运行中副本会因故障、丢包等原因逐渐产生分歧(熵增),反熵过程则通过持续比对与同步,把这种无序拉回一致状态。

概述

在采用最终一致性的分布式数据库中,写入可能因网络分区或节点宕机未能同步到所有副本,导致副本间数据出现分歧。反熵作为一种主动修复手段,不依赖客户端请求,而是由后台进程周期性地在副本间扫描比对,发现并弥合差异,保证即使无新写入,数据也会随时间趋于一致。

核心原理

• 副本比对:选取两个副本,交换各自数据的摘要,识别出不一致的部分。
• 默克尔树加速:双方交换默克尔树的哈希,自顶向下比对,快速定位到差异的数据范围,避免逐条比较全部数据。
• 差异同步:仅传输并合并有分歧的数据,通常配合版本向量或时间戳判定哪份数据更新。
• 周期执行:该过程作为低优先级后台任务定期运行,持续消解副本间的熵。

应用场景

Amazon Dynamo及其开源实现Cassandra、Riak等最终一致性系统,普遍采用基于默克尔树的反熵修复。它与读修复、提示移交等机制互补:读修复在读取时顺带修正,反熵则在后台系统性地扫描修复那些长期未被访问的数据,共同保障副本收敛。

常见问题

问:反熵和读修复有什么区别?答:读修复是被动的,只在客户端读取某数据时才检测并修复该数据;反熵是主动的后台过程,系统性扫描全部数据,能修复那些很少被读取、否则可能长期不一致的冷数据。

问:反熵为什么要用默克尔树?答:若逐条比对副本数据,通信和计算开销巨大;默克尔树让双方先比对根哈希,再逐层下钻只定位到有差异的分支,大幅减少需要传输和比较的数据量。