知识卡片
Merkle定位差异
内容
Merkle 树把数据块哈希逐层汇总成根哈希。两个副本只需比较树节点，就能快速定位少量不同的数据范围，适合副本修复、反熵同步和内容完整性校验。
参考来源
- 位置：《大数据日知录：架构与算法》第3章《大数据常用的算法与数据结构》"3.4 Merkle哈希树"一节（源文件：_epub-src/OEBPS/text00008.html）
- 结论依据：原文明确"主要用来在海量数据下快速定位少量变化的数据内容"，并以Dynamo为例说明"两个节点都对两者所存储数据的共同键值范围部分建立Merkle树……首先比较两棵Merkle树的根节点，如果发现哈希值相同，说明两者仍然同步……否则说明有部分内容有差异，于是两者交换……子节点，找到具有不同哈希值的子节点，依次类推可以逐步找到不同步的数据内容"。
- 原始内容：Merkle树最初用于高效Lamport签名验证，后来被广泛应用在分布式领域，主要用来在海量数据下快速定位少量变化的数据内容……首先比较两棵Merkle树的根节点，如果发现哈希值相同，说明两者仍然同步则无须后续操作；否则说明有部分内容有差异，于是两者交换Merkle树根节点的所有子节点，找到具有不同哈希值的子节点，依次类推可以逐步找到不同步的数据内容。