Concept Drills: 16 Key-Value Store Probes

These mechanisms appear far beyond this chapter — consistent hashing in load balancers and caches, quorums in every replicated store, Merkle trees in Git and blockchains. Worth being fluent.

Partitioning

1. Why not hash(key) % m? · L5 · Testing: the motivating failure

Because m is in the formula, so changing the node count changes the mapping for nearly every key. Adding one node triggers a cluster-wide reshuffle — massive migration, high latency, network congestion. That directly violates incremental scalability, which was a stated requirement.

2. How does consistent hashing fix it? · L4 · Testing: the mechanism

Nodes and keys both hash onto a ring from 0 to n-1. A key belongs to the first node found clockwise from its position. Because a node's position doesn't depend on how many other nodes exist, adding one only takes keys from its immediate successor — everyone else is untouched.

3. Consistent hashing distributes evenly. True? · Staff · Testing: precision

Evenly on average, not guaranteed. Ring positions are random, so gaps are uneven, and a node owning a large arc gets a disproportionate share of traffic — a hotspot that bottlenecks the system. That residual problem is what virtual nodes exist to solve.

4. What do virtual nodes actually buy? · Staff · Testing: whether they know all three

Three things. Even distribution, since many small arcs average better than one large one. Fault tolerance, because a failed node's load spreads across many successors instead of doubling one neighbor. And capacity management — a machine with twice the hardware gets twice the virtual nodes, which is how the design handles a heterogeneous fleet without special-casing anything.

Replication

5. Why peer-to-peer instead of primary-secondary? · L5 · Testing: requirement-driven design

Primary-secondary has a window where writes are impossible — after the primary fails and before a new one is elected. Our functional requirement is the ability to always write, so that model is disqualified. Peer-to-peer means every node accepts writes and no node's loss stops them.

6. What's a preference list? · L5 · Testing: replica placement

The list of successor virtual nodes a coordinator replicates a key to — the next n-1 nodes clockwise on the ring. The coordinator plus that list is where the n copies live.

7. What's wrong with just taking the next n ring positions? · Staff · Testing: the virtual-node hazard

Several consecutive positions can map back to the same physical machine, so all three replicas could land on one box — one failure loses everything and your replication factor was decorative. The preference list must skip virtual nodes whose physical node is already in the list. Ideally it spans data centers too, so a building outage doesn't take all copies.

Versioning

8. Why not resolve conflicts with timestamps? · L5 · Testing: the clock trap

Clocks drift and go unsynchronized, so a physical timestamp can't reliably say which write happened last. A write made earlier in real time can carry a later timestamp and silently overwrite a newer one. That's last-write-wins losing data invisibly, which is why the design tracks causality instead of time.

9. Explain a vector clock. · L5 · Testing: the mechanism

A list of (node, counter) pairs attached to every version of an object. Comparing two clocks tells you the relationship: if every counter in one is at most the matching counter in the other, it's an ancestor and can be discarded. If each has a counter the other lacks, they're concurrent — a genuine conflict.

10. Node A writes twice, then B and C write during a partition. Show the clocks. · Staff · Testing: can they actually do it

A's first write is [A,1], its second [A,2] — the second supersedes the first because it happened on the same node after reading it. Then the partition: B produces ([A,2],[B,1]) and C produces ([A,2],[C,1]). Neither dominates, so they're concurrent. The client gets both plus context ([A,2],[B,1],[C,1]), reconciles, and A coordinates a write producing ([A,3],[B,1],[C,1]).

11. Vector clocks grow unboundedly. What do you do? · Staff · Testing: the limitation

They grow when writes land outside the top n nodes — during partitions or multiple failures. Cap the size: attach a physical timestamp to each entry recording that node's last update, and drop the oldest once you pass a threshold like ten pairs. The cost is that truncation removes causal history, so ancestry can be misjudged and you get false conflicts. That's the safe direction — a spurious conflict is recoverable, a missed one loses data.

12. Why does the client reconcile rather than the store? · Staff · Testing: the design principle

Because only the application knows what the value means. Two divergent shopping carts should be unioned; two divergent profile edits might need a human. The store sees opaque bytes and can't choose. It's exactly the Git model — auto-merge where possible, escalate to the application when not.

Configurability and fault tolerance

13. Explain r + w > n. · L5 · Testing: the invariant

r is the minimum nodes in a successful read, w the minimum in a successful write. The inequality forces the read and write sets to share at least one node, so a reader is guaranteed to touch one that has the newest write. With n=3, r=2 and w=1 gives 3, which is not greater than 3 — illegal, and a read could land entirely on stale replicas.

14. What does raising r cost? · Staff · Testing: tail latency

Latency and availability. A read returns only after r replicas respond, so its latency is the slowest of those r, not the average — raising r pulls in more of the tail. And if fewer than r nodes are reachable the read fails outright. You buy consistency at the most expensive place to pay for it.

15. Sloppy quorum and hinted handoff — what are they and what do they cost? · Staff · Testing: the availability trade

A sloppy quorum uses the first n healthy nodes rather than the designated owners, so writes succeed even when owners are down. Hinted handoff is the follow-up: the substitute stores the data with a hint naming the real owner, and forwards it when that node recovers. The cost is that during the failure the read and write sets may not overlap, so r + w > n doesn't hold — availability bought at the price of the consistency guarantee.

16. How do Merkle trees speed up repair? · Staff · Testing: the anti-entropy mechanism

Leaves hash individual values, parents hash their children. Two replicas exchange root hashes — if they match, the whole range is proven identical in one comparison regardless of size. If they differ, you recurse only into the differing subtrees, so finding divergence is logarithmic rather than a full scan, and you transfer only the keys that actually differ. The cost is that ring membership changes invalidate the trees and force recomputation, which is part of why failure detection is deliberately conservative.

Self-check

The cheat sheet next compresses the whole design onto one page.