“没有hint的普通家副本差异仍需其他修复渠道。按范围比较Merkle快照可以定位遗漏并join回活动数据；它同样不会从“当前有多少副本”推出授权或实时顺序。”
形式陈述
修复范围先于比较根
反熵同步已有全状态join接口。当两个副本大部分相同，可以先比较摘要，再发送确实不同区域的完整状态。本页实现这次差异定位与修复会话，而不是让一个根哈希替代成员、版本和持久性合同。[1，§4.7]
双方先约定同一个描述符：成员epoch、键范围[low,low+2ᵇ)、桶树深度d≤b、哈希/编码版本。L=2ᵈ个叶桶，每桶覆盖连续2ᵇ⁻ᵈ个整数键。叶号i不是某次局部排序的位置，而是上述固定范围内的位置；不同副本的同号叶必须谈论同一批可能的键。
双方分别冻结一份不可变快照。快照ID含发布者、epoch、稳定修订号及范围描述符，并绑定根；复制过程中更新活动数据不会改变该快照。节点真实存储可用其他一致快照实现，附件为透明起见完整复制。若不能取得或继续读取原快照，会话返回需重启，不混入另一版本的节点内容。
树摘要与叶里的记录
叶内记录按原键递增，记录含(key,tag,deleted,payload)，一个键至多一条。本页用LWW最大标签join；tag在每键命名空间内唯一，相同标签内容一致。删除也是带标签的记录，不能省略成缺键。合并中的缺键只表示当前无信息。
将记录数、每条记录的字段和payload长度按固定宽度规范编码成叶值v_i，再调用已有Merkle认证树的有序叶与分域哈希：
00、01是一个字节的标签，内部摘要固定32字节。附件H为SHA-256，key用u32、tag用u64、删除标志用一个字节、payload先写u32长度。桶值以u32记录数开头，空桶也编码这个零。此处复用旧树结构，未采用稀疏树不同的默认空叶标签。参考器限制0≤d≤b≤12，避免练习意外铺开巨大满树；字段越界会拒绝，正文一般树界不靠把高度视为常数。
描述符在比较前单独精确核对。裸根没有编码全体运行配置，因此即使两个根字节碰巧相同，也不能跳过epoch、范围及编码一致性检查。来源与新鲜性由诚实固定节点及会话接口提供，不由哈希自行提供。
一次比较与修复
从两个根坐标(d,0)开始：
- 当前两摘要相等时，跳过这对快照子树
- 不等且仍是内部节点时，请求双方对应两个孩子；回复须匹配预期快照ID、坐标和层数，且两孩子重新组合出的父摘要等于本次已经接受的父摘要
- 不等且已到叶时，交换两侧完整叶记录；重新验证排序、键范围、唯一性及叶摘要，记录该桶差异
- 将收到的记录逐条join进活动数据并可靠提交，不以整份旧快照覆盖活动表
查询先完整验证本次差异内容再应用，避免把格式错误的半份响应当作成功修复。一次快照对的处理可以声明“这两份快照的信息已经分别纳入两端活动状态”，不能直接声明会话结束时两活动根相等。
直觉
相等分支不必搬内容
如果两本清单从头到尾都相同，根就相同，比较一次便可以结束这份快照对。如果根不同，比较左右半本；相同的半本无需展开，不同的半本继续分开。走到叶桶后才需要拿真正记录来决定如何修复。
摘要只回答是否相同，不回答哪边更新，也不提供业务上的合并。两个不同摘要可能来自不同键、较新值或删除记录，仍要读取带版本内容并按既定join规则处理。
例子与边界
八桶中的三处差异
取范围[0,16)、d=3，叶i覆盖键2i与2i+1。两边epoch和编码一致，冻结以下记录：
| 快照 | 完整记录，括号为版本和值 |
|---|---|
| A | 0:(1,a)，3:(2,c)，8:(4,h)，14:(6,n) |
| C | 0:(1,a)，3:(1,old)，9:(3,i)，14:(7,DELETE) |
差异叶是1、4、7。叶1谈键2/3，叶4谈键8/9，叶7谈键14/15。树会访问根、左右四桶子树，再沿不等分支展开；总共13个节点对，另一个覆盖叶2/3的相等子树在内部便停止。
若比较者本地树已经保存，它需取得13个远端摘要，共416字节，只计13×32这项。每个请求的快照ID、坐标、传输头以及真正叶记录另计。不能把3片差异误写成3次哈希询问，也不能把416称为全部网络流量。
三片差异桶双向传送共六条记录出现次数：两份键3、键8、键9、两份键14。逐键join后，双方保留键0的1、键3的2、键8的4、键9的3、键14的删除7；可见值只有0、3、8、9四键。删除14的记录仍留在版本表。
快照之后的新写不能被旧修复覆盖
仍用同一对快照，但建立后A的活动状态把键3写成版本9/new。本轮传给C的仍是被冻结的3:(2,c)。将C的旧3:(1,old)join进A时，A保留9；C吸收A快照后则只有2。
因此会话完成时两活动状态可以不同。它完成的是两份固定历史信息的交换，并没有暂停世界。重新取快照时仅叶1不同，沿根到叶1的路径访问对应孩子，共7个节点对；第二轮才能把9传给C。
若第一轮把旧快照内容整体赋回A，就把已接受的新9倒退成2。错误不在Merkle哈希，而在安装步骤没有遵守版本join。
不一致树形与混合快照
一边按两键一桶，另一边按四键一桶，不能比较同一个(层,索引)后便解释为同一区域。即使都是空数据，也必须先拒绝不同描述符。成员epoch变化也要求重新确定谁负责哪段范围，旧修复会话不能自行批准迁移。
更隐蔽的错误是先收到快照s₁的根，再收到s₂的孩子。根和孩子各自都可能合法，却不构成一棵树。回复中的快照ID拒绝这次混用；重算父摘要则检查同一会话里内容与已经接受的父节点一致。
把叶1的数据放到叶4同样不行：原键不在该桶范围，叶编码还包含位置，校验应拒绝。若内容读取超时或原快照不可用，结果是未完成，不是“这个桶没有差异”。
摘要省掉的不能是删除证据
若C把14的删除7直接省略为缺键，另一端A的旧14/6会在join时胜过“无信息”，产生复活。树正确地定位了差异，错误在输入已丢掉压制旧值的证据。
墓碑的稳定回收另有已有合同，本页不以根相等或等待一段时间替代它。摘要只比较当前被编码的状态，不能认证某次遗漏从未发生，也不能补出已经被所有副本永久丢失的payload。
推论与应用
不漏差异的条件
固定两份描述符相同的快照，并在本次计算未发生哈希碰撞的条件下推理。若对应节点摘要相等，则其规范输入相同；对内部节点归纳，下面所有叶值相同。若某叶值不同，从根到该叶的每个对应祖先都不等，否则沿树会给出实际哈希碰撞。算法因此不会在这条路径上提前停止，最终访问并交换该差异叶。
规范字段、左右次序、层数和叶位置保证“输入相同”具有明确含义。一般安全性可复用旧认证树的碰撞归约；这里没有声称有限长度SHA-256在数学上无碰撞，也没有从一份自报根推断发布者可信。
叶内完整状态取join，且活动状态也只上升，便保证每端最终状态至少包含两份快照的逐键join。新写可能使一端更高，所以结论是信息下界，不是活动状态相等。
定位成本按差异分布计
设树高d、叶数L=2ᵈ，h片叶的完整编码不同，比较节点对数为C。有h=0时C=1；一般有
每个不等内部节点至少含一片差异叶，因此这类节点至多由h条长d的祖先路径覆盖，共至多dh个。除根以外，每次比较都由一个不等内部节点产生两个孩子，故C≤1+2dh；遍历又不会超过整树2L−1个节点。共享祖先会减少实际访问，主例h3/d3只有13，而粗界19不紧。
d=0时只有一叶，比较根一次；若不等就传整桶内容。稀少差异不保证传很少字节：一个桶可以含许多相同记录，当前接口仍交换它的完整内容，而非假称每个差异键只花常数大小。
快照、编码与重复修复的完整成本
令n为节点源表的总记录数。附件先按键排序并扫描整张源表，再把本范围记录复制到L片叶的不可变列表中；范围外记录不参与本会话。设范围内编码总字节B，建树时间O(1+L+n log(n+1)+B)，摘要数2L−1，额外存储包含O(1+n+L)条结构及B字节。排序、空桶初始化和读取payload都不能藏进“只比较一根”的成本。
已有两树上，下探花O(C)份固定宽度摘要工作；再付差异桶记录的验证、编码和网络字节成本。活动join按字典期望常数定位每条键，另计标签/值比较、复制与可靠提交。快照描述符和本页整数编码范围固定，长业务键或另一哈希成本模型须另计。
若更新最终停止，删除/版本证据保留，且正确副本间不断有成功的共同范围修复，逐键join会传播稳定最大值。无限更新或永久隔离时，本页不承诺某一有限轮结束就全组相等。完整两轮轨迹和格式失败见复制修复终点。
参考资料
- [1] Giuseppe DeCandia等，Dynamo: Amazon’s Highly Available Key-value Store，SOSP2007，§4.7（PDF8页）：共同键范围、树根/孩子比较和范围改变后的重建；§6.2（PDF11–12页）讨论分区布局。本文固定范围并独立加入不可变快照/会话校验和活动join合同，不声称原文逐行采用本教学编码
- [2] RFC9162，§2.1.1的叶/内部节点分域与§2.1.3的路径背景。本文直接复用本库固定满树及额外索引/层数编码，不声称与该RFC任意叶数格式兼容；范围修复是另一上层任务