解读

在国内 CouchDB 岗位面试中，Merkle 树问题是“分布式一致性”与“增量同步”两大高频考点的交汇点。面试官真正想验证的是：

1. 你是否理解 CouchDB 多主复制为何要用 Merkle 树做差异检测；
2. 你是否能把“生成”过程拆成 哈希计算 → 自底向上归并 → 剪枝优化 三步，并给出可落地的实现细节；
3. 你是否知道在 海量文档 + 移动端弱网 场景下，如何控制树高、控制分片粒度、控制内存占用。
   答得太浅（“把 hash 拼起来再算一层”）会被追问冲突解决；答得太深（直接甩代码）又容易被质疑工程可行性。因此，回答必须“理论正确 + 工程可落地 + 贴合 CouchDB 源码风格”。

知识点

1. CouchDB 复制 ID：每个数据库实例有 repl_id，用于区分副本。
2. 文档序列化规则：按 _id 字典序升序，value 取 rev + deleted 标志位，保证不同节点同一文档哈希一致。
3. 分片（Shard）与 vBucket：CouchDB 3.x 默认 8 分片，面试时要明确“每分片独立建 Merkle 树”，否则会被追问横向扩容时如何合并。
4. 哈希函数选择：官方源码用 sha1(20 B)，国内金融场景可换 sm3(32 B)，但必须强调“节点间必须协商一致”。
5. 剪枝阈值（Leaf batch size）：默认 100 文档／叶子，面试中给出“经验值 64~256”即可，同时说明“阈值越大，树越矮，网络往返少，但差异粒度粗”。
6. 差异检测协议：CouchDB 采用 “深度优先 + 位图压缩” 的 _revs_diff 二次请求，回答时要提到“第一次只传顶层 hash，第二次只传差异子树”，体现对国内 4G/5G 弱网环境的优化。
7. 并发安全：生成树过程必须 持有 db 快照（erlang 的 read transaction），防止并发写导致 rev 树变化，否则会出现“哈希漂移”。

答案

生成 CouchDB 风格的 Merkle 树分五步，可直接映射到 erlang 源码模块 couch_mrview_indexer 中的实现逻辑：

1. 快照一致性
   在 Erlang 端调用 couch_db:get_snapshot(Db, []) 拿到一个只读快照，保证后续读到的 rev 树不再变化。

2. 文档排序与序列化
   遍历快照，按 _id 字典序排序，对每个文档取 {rev, Deleted} 二元组，拼成二进制 <<RevBin/binary, Deleted:1>>，再算 sha1(DocumentKey)。

3. 分片建叶子
   以 配置项 cluster_q=8 为例，先按 hash(_id) rem 8 把文档路由到对应分片；每个分片内按“leaf batch size=100”做滑动窗口，窗口内 100 个文档哈希拼在一起再算一次 sha1，得到叶子节点哈希。

4. 自底向上归并
   叶子节点数组长度若为奇数，末尾重复最后一个节点，保证偶数；两两拼接后算 sha1 得到父层，循环直到只剩一个根哈希。树高 O(log(N/100))，内存占用 O(N/100)。

5. 序列化与缓存
   整棵树按 {depth, bitmap, nodes} 三元组序列化成 binary，深度与节点哈希一起作为 ETag 返回给客户端；同时写入 本地 ETS 表缓存，TTL 30 s，避免 1 s 内重复生成。

通过以上五步，CouchDB 在 百万文档规模下，首次生成 Merkle 树耗时 < 200 ms（16 核 2.4 GHz，SSD），增量差异检测网络往返 < 3 次，满足国内移动应用离线同步需求。

拓展思考

1. 如果业务文档平均大小 16 KB、总量 10 亿，如何在不牺牲差异精度前提下把生成时间压到 1 s 以内？
   思路：① 把 leaf batch size 提到 1024；② 引入 两级 Merkle 树——先按 doc hash 前缀 8 bit 建 256 棵子树，再对子树根建顶层树；③ 使用 RDMA 或 erlang 的 dirty scheduler 把哈希计算 offload 到 GPU／FPGA，国内阿里云 eRDMA 已落地。

2. 国内多地多活场景，北京、上海、深圳三机房 RTT 30~50 ms，如何防止 Merkle 树差异检测带来的 读放大？
   思路：① 采用 CRDT 计数器维护每个分片的“稳定 seq”，只有 seq 变化才触发树生成；② 在 HTTP Header 里带 X-CouchDB-Merkle-Version，利用 CDN 边缘节点做 树哈希缓存，差异检测请求 302 到就近节点，降低跨城带宽 40%。

3. 如果面试官追问“为何不用 Bloom Filter 而要用 Merkle 树”，可从“可证明差异 + 支持增量修补”角度回答：Bloom Filter 只能回答“可能在/一定不在”，无法定位缺失文档；Merkle 树通过 子树哈希比对可精确给出缺失 _id 列表，这对国内 断点续传、弱网重试 场景至关重要。