System Design · Design Question

Design a Key-Value Store

Dynamo-style distributed KV: put/get, partitioning, replication, consistency, and failure handling.

1. Requirements

put(key, value), get(key); optional delete, TTL.
Huge scale: billions of keys, high QPS, multi-TB/PB.
Tunable consistency vs availability (state CAP preference).
Survive node failures; rebalance when nodes join/leave.

Assume: values up to a few MB; larger → object store + pointer SLA: put/get p99 < 10–50ms within region

2. API

PUT /v1/kv/{key} body: raw bytes / JSON value GET /v1/kv/{key} → 200 value | 404 DELETE /v1/kv/{key} Headers: X-Consistency: quorum|one (optional)

3. Data model

Logical: key → { value, version/vector_clock, ts, ttl } On disk per node: LSM (memtable + SSTables) or bitcask-style log suited for high write ingest

4. High-level design

Client → Coordinator / Any node | +-- consistent hash ring → preference list (N replicas) | put: send to N replicas, wait W ACKs get: read R replicas, return newest / repair

5. Partitioning

Consistent hashing with virtual nodes. Key maps to a primary and walks the ring for replicas on distinct physical nodes. Adding a node moves only neighboring key ranges.

6. CAP choice (Dynamo-style)

Classic Dynamo-inspired KV stores usually choose AP under partition: keep accepting puts/gets on reachable replicas, then reconcile. If the product needs linearizability (config, locks), say so and switch the story to Raft/Paxos per shard (CP) instead of pretending both.

7. Replication and quorum

N = 3 replicas, W = 2 write ACKs, R = 2 read responses R + W > N → overlap guarantees reading a node that got the write (common case) W=1,R=1 → faster, stale reads possible W=N,R=1 → durable writes, slower puts

Sloppy quorum + hinted handoff

If a preferred replica is down, a healthy node temporarily accepts the write (sloppy quorum) and stores a hint. When the target recovers, the hint is forwarded so the replica catches up. Improves availability; readers may need read-repair until handoff completes.

Anti-entropy / Merkle trees

Background process compares replica ranges using Merkle trees (hash trees of key ranges). Only divergent subtrees are synced — cheap detection of silent drift that hinted handoff missed.

Read repair: on get, push newer version to stale replicas.
Hinted handoff: temporary write diversion + replay.
Anti-entropy: periodic Merkle reconciliation.

8. Gossip for failure detection

Nodes periodically exchange membership and health rumors (gossip). Failure detection is decentralized — no single monitor SPOF. Trade-off: suspicion is probabilistic; use suspicion timeouts + phi accrual style detectors to limit false positives before removing a node from the ring.

9. Bloom filters on the read path

Each SSTable (or shard) can keep a bloom filter of keys. A get that misses the filter skips that file’s disk I/O. False positives waste a read; false negatives must not happen. Critical for LSM-backed KV nodes.

10. Conflict resolution

Last-write-wins (timestamp) — simple, can lose concurrent updates.
Vector clocks — detect conflicts; client merges (shopping cart classic).
CRDTs — mergeable types when domain allows.

11. Deep dive — failure

Node down: ring still serves via remaining replicas Network split: prefer AP with conflict resolution OR CP with leader per shard Leaderful alt: each shard has Raft leader (etcd/TiKV style) — stronger consistency

Pick a story: Dynamo-style AP+quorum or Raft per partition for CP. Do not mix hand-wavy both without saying the trade-off.

12. Scaling

More nodes on the ring; vnodes for balance.
Client or proxy caching of ring membership.
Hot keys: split keyspace or replicate hot key to many nodes.
Compaction / disk IO tuning on LSM nodes.

13. Client vs server coordination

Some designs put the coordinator in the client library (Dynamo paper); others use a proxy/router tier. Proxies simplify clients but add a hop and must be HA. State the choice and why.

Smart client: knows ring, talks to replicas directly Proxy tier: clients → stateless routers → storage nodes

14. Compaction and tombstones

Deletes write tombstones; GC after they propagate to all replicas.
Too-aggressive GC → resurrected deletes (classic distributed bug).
Backups must include tombstone epoch rules.

15. Decision summary

Decision	Common Dynamo-style pick	Alternative
Partitioning	Consistent hash + vnodes	Range shards / directory
Replication	N replicas on ring	Raft group per shard
Consistency	Quorum R/W; usually AP	CP leader per partition
Conflict resolution	LWW or vector clocks	CRDTs
Storage engine	LSM (memtable + SSTables)	B-tree if read-heavy OLTP-like

16. Related concepts

Consistent Hashing
Replication
Storage Engines
Caching (bloom filters, negative cache ideas)
Distributed Cache
Availability Patterns

17. Interview outline

API + size assumptions.
Hash ring + vnodes + N replicas.
CAP (usually AP) + quorum R/W and what R+W>N buys you.
Gossip, hinted handoff, read repair, Merkle anti-entropy.
Conflict story (LWW vs vector clock) + LSM + blooms.

Quick revision

KV at scale = partition + replicate + handle conflicts.
Dynamo-style usually AP; Raft-per-shard if you need CP.
Quorum R/W; R+W>N for strong-ish read-after-write in stable runs.
Hinted handoff, read repair, Merkle anti-entropy heal replicas.
Gossip for membership/failure detection.
LSM + bloom filters on the local read path.
Hot keys need special handling beyond the ring.