System Design Storage
Merkle Trees
Two Cassandra nodes disagree after a network blip. Shipping 2 TB to find a few divergent partitions is impossible as a routine job. A compresses each replica’s state into a ; unequal roots trigger descent until only mismatched leaves need .
This is the SD-focused Merkle note: anti-entropy repair, inclusion proofs, block/chunk integrity, sizing of proofs and trees, and what Merkle trees do not replace (authn, consensus, or encryption).
Repair journey
Equal → done. Differ → something diverged.
Descend mismatches
Exchange child hashes; ignore matching subtrees.
Identify chunk or key-range digests that differ.
Copy only divergent data; re-verify hashes.
What actually happens
Build bottom-up: over chunks or key ranges, then parents H(left ‖ right) (plus domain separation tags in careful designs), until one remains. That root is cheap to ship in gossip, RPCs, or manifests.
For , replicas compare trees and perform only where leaves disagree. For client verification, a lets someone check that a chunk belongs under a trusted root without downloading every sibling leaf.
Merkle trees detect differences and prove inclusion. They do not elect a leader, encrypt bytes, or decide which divergent version is “correct” for the business—you still need version vectors, last-write-wins, or app merge rules after you know where replicas differ.
Building the tree
Read the diagram definition
flowchart TD
D["Data chunks / key ranges"] --> L["Hash each leaf"]
L --> P["Parent = H(left || right)"]
P --> Up["Repeat until one root"]
Up --> R["Merkle root"]Binary Merkle (N leaves, pad if odd):
leaf[i] = H(domain_sep_leaf || chunk[i])
node[level][i] = H(domain_sep_node || left || right)
root = node[top][0]
Height ≈ ceil(log2(N))
Internal nodes ≈ N - 1 (full binary tree)
Incremental update when chunk j changes:
recompute leaf[j]
recompute each ancestor on the path to root
→ O(log N) hashes, not O(N)
Odd leaf: often duplicate last hash or use a unary parent—
document the rule; both sides must match.Domain separation (different prefixes for leaf vs internal nodes) prevents trivial second-preimage tricks where an internal node’s bytes are reinterpreted as a leaf. Storage systems that only fight bit-rot sometimes use faster non-crypto hashes; proof systems and public roots should use cryptographic digests to bound risk.
Anti-entropy repair walk
Read the diagram definition
sequenceDiagram
participant A as Replica A
participant B as Replica B
A->>B: Send root hash
B-->>A: Roots differ
A->>B: Send level-1 child hashes
B-->>A: Left child mismatches
A->>B: Descend left subtree
B-->>A: Leaf range X differs
A->>B: Stream records in range X
B->>B: Apply + verify leaf hashesWide-column stores often build a Merkle tree over token ranges for a column family. Repair jobs compare trees between replicas, then stream divergent partitions. Because most ranges usually match, bandwidth stays proportional to divergence—not to total data size—when trees are fresh.
Cost sketch:
Full scan repair: O(data_size) network + disk
Merkle repair with D divergent leaves out of N:
hash traffic ≈ O(log N) per divergent path (+ fanout exchanges)
data traffic ≈ size of those D ranges
Stale trees:
If the tree lags mutations, you get false mismatches or misses
Rebuild/refresh policy matters as much as the hash function
Priority repair:
Hot keyspaces first; throttle streaming so queries keep IO budgetInclusion proofs
Proof for leaf index i:
siblings = [sib at level 0, sib at level 1, …]
Verifier:
h = H(leaf_bytes)
for each sib in siblings:
h = H(h || sib) or H(sib || h) # order by path bit
accept if h == trusted_root
Proof size:
height × digest_size
N=1e6 leaves, SHA-256 → ~20 × 32 B ≈ 640 B
N=1e9 → ~30 × 32 B ≈ 960 B
SD uses:
package registries, transparency logs, CDN edge verification,
blockchain-style headers (same idea), artifact attestationsTrusted root required
A proof only binds a leaf to a root you already trust (signed, consensus-agreed, or pinned).
Not confidentiality
Proofs reveal sibling hashes; they do not hide data by themselves. Encrypt separately if needed.
Sizing trees and rebuild cost
| Leaves N | Height | ≈ nodes stored | SHA-256 tree bytes |
|---|---|---|---|
| 65,536 (64K) | 16 | ~131K | ~4 MiB |
| 1,048,576 (1M) | 20 | ~2M | ~64 MiB |
| 16,777,216 (16M) | 24 | ~33M | ~1 GiB |
Leaf granularity trade-off:
Fine leaves (small ranges): precise repair, larger tree, more rehash on churn
Coarse leaves (big ranges): smaller tree, but a mismatch streams more data
Example:
10 TB dataset, 64 MB chunks → N ≈ 163,840 leaves
Tree fits in a few MB; mismatch streams 64 MB units
Same data, 4 KB chunks → N ≈ 2.68e9 leaves
Tree metadata alone becomes huge; proofs still O(log N)
but storing/updating all nodes is expensive
Incremental rehash:
Prefer updating the path for hot writes when N is large
Periodic full rebuilds still help after major reshapesSD use cases
Replica anti-entropy
Content-addressed objects and Git
Public verification / transparency
Filesystem and backup integrity
Trade-offs and failure modes
Freshness vs cost. A stale tree causes useless streaming or missed divergence. Rebuild schedules and policies are operational design, not footnotes.
Granularity. Fine leaves localize repair but inflate metadata and CPU. Coarse leaves shrink trees but enlarge each mismatch transfer.
Hash strength. CRC-family checksums catch accidental rot cheaply; adversarial settings need cryptographic digests and authenticated roots.
Semantics after diff. Detecting divergence does not merge shopping carts. Plan conflict resolution separately.
Proof security model. Without a trusted root channel, an attacker can present a consistent but false tree. Sign or pin roots.
Interview sizing soundbites
“1M partitions → height ~20; proof ~640 B with SHA-256.”
“Equal roots ⇒ skip repair for that tree version.”
“D divergent leaves ⇒ stream ~D ranges, not the whole disk.”
“Updating one chunk ⇒ O(log N) rehash along the path.”
“Merkle finds where; versions/CRDTs decide what wins.”Choosing and explaining Merkle trees
A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.
Explain the core idea
A Merkle tree hashes chunks into leaves and aggregates upward so one root summarizes the dataset.
Replicas compare roots and descend only into mismatched subtrees, then stream those ranges (anti-entropy).
Inclusion proofs are O(log N) sibling hashes that bind a leaf to a trusted root.
When it belongs
Designing replica repair without full-dataset copies.
Verifying objects/packages against a published root.
Detecting silent corruption across large block stores.
How it fails
Stale trees → false mismatches or missed divergence.
Wrong leaf granularity → tiny diffs still move huge ranges, or metadata explodes.
Untrusted roots → proofs become theater.
Trade-offs to weigh
Tree storage/CPU versus precision of repair.
Crypto hashes versus faster checksums for accidental-only threats.
Incremental path updates versus periodic full rebuilds.
Common misunderstandings
Treating Merkle equality as consensus or authorization.
Saying proofs are O(1) or require sending all leaves.
Forgetting odd-leaf padding rules must match on both replicas.
Confusing Merkle trees with Bloom filters (membership approx vs cryptographic summary).
Wrap-up
Use Merkle trees whenever comparing or proving large state must stay logarithmic. Size leaves for your repair unit, keep trees fresh, protect roots, and pair diffs with an explicit conflict policy.
Primary sources
Key takeaway
Merkle trees turn “are we the same?” into a root compare and “where do we differ?” into a logarithmic descent. That is the backbone of cheap anti-entropy and compact inclusion proofs—provided roots are trusted and leaves are sized for the sync you can afford.