Stackbook Logo
← Back to System Architectures

Designing a Distributed Key-Value Store

Design a Dynamo-style key-value store with partitioning, quorum replication, vector clocks, LSM storage and anti-entropy for high availability at scale.

4 min read

A durable key-value store underpins shopping carts, session data and metadata services. This design follows the Dynamo lineage (Cassandra, Riak, DynamoDB) and favors availability and horizontal scale.

Requirements

Functional

  • put(key, value), get(key), delete(key).
  • Values up to 400 KB; keys up to 1 KB.
  • Optional conditional writes and per-key TTL.

Non-functional

  • 200K reads and 100K writes per second, scaling linearly with nodes.
  • p99 read under 10 ms, write under 15 ms.
  • 99.99 percent availability, surviving a node or an entire zone failure.
  • Durability: no acknowledged write lost with three replicas.
  • Tunable consistency, eventual by default.

Capacity estimation

Assume 10 billion items averaging 1 KB: 10 TB raw, 30 TB with three replicas. At 2 TB usable per node (keeping 50 percent headroom for compaction), we need about 30 nodes. Write throughput of 100K per second times three replicas is 300K replica writes per second, about 10K per node, comfortable for SSD-backed LSM engines.

High-level design

 Client --> any node (coordinator)
               |
        hash(key) -> ring position
               |
     +---------+----------+
     v         v          v
  Replica 1  Replica 2  Replica 3   (next N distinct nodes
  (zone a)   (zone b)   (zone c)     clockwise on the ring)
     |
  Commit log -> Memtable -> SSTables (LSM tree)

Every node is symmetric; any node can coordinate a request. Membership spreads via gossip, so there is no single master.

Data model

Logical record: key, value blob, version metadata (vector clock or timestamp), tombstone flag and TTL. Physically, writes append to a commit log, update an in-memory memtable, and flush to immutable sorted files (SSTables). Each SSTable has a Bloom filter and a sparse index.

Key deep-dives

Partitioning. Consistent hashing with 128 virtual nodes per server evens out load and lets a replaced node stream data from many peers in parallel. A preference list holds the next N distinct nodes, skipping nodes in the same failure domain.

Quorum replication. With N=3, choose write quorum W and read quorum R. If R plus W exceeds N (for example R=2, W=2) reads overlap the latest write. W=1 maximizes write availability; R=1 maximizes read speed. The coordinator sends to all replicas and returns after the quorum acknowledges.

Conflict resolution. Concurrent writes during partitions create divergent versions. Vector clocks detect concurrency; the client merges siblings (union of cart items). The simpler option, last-write-wins by timestamp, is easy but silently drops updates and depends on clock sync.

Sloppy quorum and hinted handoff. If a preference-list node is down, the write goes to the next healthy node with a hint naming the intended owner. When the owner recovers, the hint is replayed. This keeps writes available at the cost of weaker consistency.

Anti-entropy. Replicas build Merkle trees over key ranges and compare root hashes periodically, syncing only mismatched subranges. Read repair additionally fixes stale replicas whenever a read notices a mismatch.

Storage engine. LSM trees turn random writes into sequential ones. The read path checks memtable, then SSTables newest-first, using Bloom filters to skip files. Compaction merges files and drops tombstones after a grace period (commonly 10 days) so deleted data does not resurrect from a stale replica.

Failure detection. Gossip with a phi-accrual detector adapts to network jitter better than fixed timeouts.

Failure modes and trade-offs

  • Zone outage: with replicas spread over three zones and W=2, writes continue. Reads at R=2 also continue.
  • Partition: both sides accept writes under sloppy quorums, producing siblings to reconcile later. This is the CAP trade: availability chosen over linearizability.
  • Hot partitions: a popular key overloads its replicas. Cache in front, or split with a key suffix.
  • Write amplification: compaction can be five to ten times the ingest volume. Rate limit it to protect foreground latency.
  • Clock skew: last-write-wins loses data when clocks drift; prefer vector clocks or hybrid logical clocks for sensitive data.
  • Strong consistency need: layer a consensus protocol (Raft per partition) as Spanner and etcd do, paying extra latency and losing availability during minority partitions.

Key takeaways

  • Consistent hashing with virtual nodes plus a replication preference list gives scalable, balanced placement without a master.
  • Tunable quorums (N, R, W) let each workload choose its point between consistency, latency and availability.
  • Vector clocks detect conflicts; applications or CRDTs must resolve them.
  • Hinted handoff, read repair and Merkle-tree anti-entropy together converge replicas after failures.
  • LSM storage matches write-heavy workloads, but plan for compaction cost and tombstone retention.