Prompt and context
Design a background anti-entropy service for a replicated key-value store. Nodes may be temporarily offline while writes continue; the system must avoid full scans and eventually converge. Explain how Merkle trees locate differences, how repair is rate-limited, and how stale replicas are prevented from overwriting newer data.
The Dynamo paper describes a Merkle tree per key range: compare the root and internal nodes first, then synchronize only leaf ranges with different hashes. The interview is about connecting detection, version arbitration, concurrent repair, resource budgets, and observability into one protocol.
What the interviewer is testing
The interviewer is testing consistency goals, versioning, partition and tree-update boundaries, incremental comparison, idempotent repair, throttling, retries, topology changes, and a credible convergence argument. Explain when read repair or human recovery is needed.
Clarifying questions
Confirm key-space partitions, replication factor, read and write consistency, version representation, delete semantics, tolerated staleness, data size, and repair bandwidth. Ask about the failure model, partitions, encryption, tenant isolation, and whether repair may share resources with business traffic.
30-second answer
“I would maintain a versioned Merkle tree per virtual-node or key range. Peers exchange the range, root hash, and snapshot watermark; equal roots skip work, while unequal roots recurse to differing leaves and batch the keys. Repair writes carry versions or tombstones and use deterministic conflict rules that reject stale values. Idempotent batches, leases, bandwidth budgets, retries, and saturation metrics keep repair safe. Repair age, difference count, and sampled replica reads demonstrate convergence.”
Deep-dive answer
Step 1: Define partitions and versions
Split the key space into stable ranges with an owner replica set. Each record carries a monotonic version, vector clock, or causal version. Deletes need propagating tombstones; a missing record cannot mean “never existed.”
Step 2: Build a comparable Merkle tree
Leaves aggregate keys and version digests in a deterministic order; parents store child hashes. Rebuild or incremental updates are both possible, but the write snapshot boundary must be explicit so a root has one meaning.
Step 3: Compare from root to leaves
Compare range identity and roots first. Equal roots require no transfer. Unequal roots recurse through children until the smallest differing ranges are found, then keys and version summaries are batched. Split hot ranges or cap batch size so one repair cannot block other partitions.
Step 4: Arbitrate versions and deletes
Compare version relationships when a differing key arrives. Concurrent versions cannot be resolved by arrival time alone; merge, retain conflict, or apply a business rule. Tombstones need a retention period and a safe watermark before cleanup.
Step 5: Make repair batches idempotent
A batch carries its range, snapshot version, sequence, and digest. Repeating it has no extra side effect. The target checks the version before applying; an old batch is rejected or skipped safely. Results are replayable and auditable.
Step 6: Budget resources and concurrency
Set concurrency, bandwidth, CPU, disk-read, and queue budgets by tenant, range, node, and priority. Business traffic wins. Pause repair when a node is overloaded or replication lag crosses a threshold. Add jitter to exponential backoff so nodes do not retry together.
Step 7: Handle topology changes and failure
Recompute replica sets and tree metadata when nodes join, leave, or ranges move. Persist progress, snapshots, and leases so a restart can resume. During a partition, continue accepting writes but expose stale and conflict states rather than claiming convergence.
Step 8: Prove convergence and operate
Monitor last repair time, differing keys, tombstone age, failed batches, version conflicts, and bandwidth per range. Periodically compare sampled reads across replicas and set a maximum-staleness SLO. Alert, isolate, or recover a range manually when repair fails persistently instead of retrying forever.
Model answer
I would partition the key space into virtual-node ranges and maintain a Merkle tree with version digests for each range. Peers exchange range identity, root hash, and snapshot watermark; equal roots skip, while unequal trees recurse to differing leaves and transfer only those keys. Records use vector clocks or monotonic versions, deletes use tombstones, and conflicts follow a deterministic merge or arbitration rule; an older version cannot win because it arrived later. Repair batches carry snapshot, sequence, and digest and are idempotent. Tenant, range, node, and bandwidth budgets protect business traffic, with jittered backoff on failure. Topology changes recalculate replica sets and leases. Operations track differences, repair age, conflicts, tombstones, and failures, sample replica reads, and set a staleness SLO. Persistent divergence isolates a range for human recovery.
Common mistakes
Sending the whole shard when the root differs
The point of a Merkle tree is to locate the smallest differing range recursively. Full transfer multiplies network and disk cost and can block hot partitions.
Solving every conflict with last-write-wins
Clock skew and concurrent writes make arrival time an unsafe causal signal. Use version relationships, merge rules, or business arbitration.
Ignoring deletes and tombstones
If a delete disappears immediately, a lagging replica can resurrect the old value. Tombstone retention and safe cleanup are part of convergence.
Follow-up questions and answers
How do Merkle trees handle continuous writes?
Compare a consistent snapshot or version watermark while new writes enter later versions; advance the repair watermark after the batch completes. A changing root is not one snapshot.
What if one range is extremely hot?
Split it further, cap batch and concurrency, and prioritize the child range with the greatest staleness window. Temporarily reduce read amplification or move replicas when needed.
What if a node restarts mid-repair?
Resume from a lease, batch sequence, and persisted progress. Target-side version checks make duplicate batches safe, and the source revalidates the snapshot.
How do you prevent old tombstones from being removed too soon?
Clean them only after all relevant replicas pass a safe watermark or acknowledgement point, and monitor the oldest tombstone age. Keep them when confirmation is missing.
How does read repair differ from anti-entropy?
Read repair fixes differences discovered on the business read path and covers hot keys. Anti-entropy is proactive background scanning and covers cold data. Both share version and repair semantics.
When should automatic repair stop?
Pause and isolate a range when conflicts cannot be merged, data is corrupt, authorization is abnormal, or resources remain overloaded. Preserve evidence and snapshots for human recovery.