Design a Distributed Key-Value Store

A distributed key-value store offers two operations, put(key, value) and get(key), spread across many machines. Amazon's Dynamo paper and systems like Cassandra and Riak follow this design. The question tests whether you understand partitioning, replication, consistency trade-offs and failure handling, since those are the building blocks of most large systems.

Requirements#

• put and get on small values (under 10 KB).
• Store petabytes across hundreds of nodes, and add nodes without downtime.
• Highly available for writes, even while some nodes or a whole rack are down.
• Tunable consistency: callers choose between faster, possibly stale reads and slower, fresher ones.

CAP and the choice we make#

When the network partitions, a system must choose between consistency and availability. A shopping cart or session store would rather accept a write and reconcile later than reject it, so we design an AP system with eventual consistency, and let callers dial up consistency per request.

Partitioning with consistent hashing#

Naively, node = hash(key) % N reshuffles almost every key when N changes. Consistent hashing places nodes and keys on a ring; each key belongs to the next node clockwise.

Each physical node owns many virtual nodes spread around the ring. This evens out load and lets bigger machines take more virtual nodes.

Replication#

Each key is stored on the next N distinct physical nodes clockwise (its preference list), commonly N = 3, ideally in different racks or zones.

Quorums#

With N replicas, a write waits for W acknowledgements and a read waits for R responses.

Exposing R and W per request is what "tunable consistency" means.

Resolving conflicts#

Concurrent writes to different replicas can diverge. Two common strategies:

• Last write wins using timestamps. Simple, but clock skew can silently drop writes.
• Vector clocks, which track a version counter per node. They can tell whether one version descends from another or whether they truly conflict; true conflicts are returned to the client to merge (Dynamo merged shopping carts by union).

Handling failures#

• Detecting failures: nodes gossip heartbeats to random peers, so the cluster learns who is down without a central monitor.
• Temporary failures: if a replica is down, another node accepts the write and keeps a hint. When the owner returns, the hint is handed back (hinted handoff).
• Permanent drift: replicas compare data with Merkle trees, hashing ranges of keys so only differing ranges are synced (anti-entropy).
• Read repair: when a read sees a stale replica, the coordinator writes the newest version back to it.

The storage engine on each node#

This log-structured merge tree makes writes sequential and fast. Reads check the memtable, then SSTables, using Bloom filters to skip files that can't contain the key. Background compaction merges SSTables and drops overwritten values and tombstones.