Catalog My learning Blog
System Design Roadmap: 100-Day Course for Engineers · Phase 7 · Lesson 70 · 5 min read

System Design: Distributed Key-Value Store

On this page
  1. The problem: design a distributed key-value store
  2. Estimating storage and node count
  3. Partitioning with consistent hashing
  4. Replication across failure domains
  5. Tunable consistency with quorums
  6. Handling conflicts with vector clocks
  7. Failure detection and repair: gossip, hinted handoff, anti-entropy
  8. Storage on each node: LSM trees, Bloom filters and tombstones
  9. The alternative: a leader-based key-value store
  10. What a strong key-value store design includes
  11. Check yourself

The problem: design a distributed key-value store

Design a key-value store with get(key) and put(key, value). It holds 50 TB, serves 500,000 operations per second, keeps working when nodes fail, and lets each application choose between stronger consistency and lower latency. Work through partitioning, replication, consistency, conflicts and failure handling.

Estimating storage and node count

Code
Data       50 TB × 3 replicas                 = 150 TB on disk
Nodes      at ~2 TB of data per node, leaving room for compaction  ≈ 75 nodes
Load       500,000 ops/s ÷ 75 nodes            ≈ 6,700 ops/s per node before replication

Writes count three times, once per replica, so plan per-node capacity on the write share, not just the total. These assumptions are guesses; write them down so they can be challenged.

Partitioning with consistent hashing

50 TB and 500,000 operations per second need many nodes. Place nodes on a consistent hashing ring with virtual nodes, so data spreads evenly and adding a node moves only its share. A node joining or leaving streams the affected key ranges to their new owners in the background.

Replication across failure domains

Store each key on N = 3 distinct nodes: the next three physical nodes clockwise. Place replicas in different racks or availability zones, so one rack failure doesn't take all copies.

Tunable consistency with quorums

Any of the N replicas can coordinate a request. Clients choose W and R per operation:

Code
put(key, value, W=2)   get(key, R=2)    -> reads see the latest write (2 + 2 > 3)
put(key, value, W=1)   get(key, R=1)    -> fastest, may read stale data

Defaults of W = 2 and R = 2 balance consistency and availability; one replica down doesn't block either.

Handling conflicts with vector clocks

Because any replica can accept writes, two clients can update the same key concurrently. Each version carries a vector clock. On read, versions that are ordered collapse to the newest; concurrent versions are returned as siblings for the application to merge (for a cart, the union of items). For data where that's overkill, offer last-write-wins as a per-table option, with its data-loss trade-off stated.

Failure detection and repair: gossip, hinted handoff, anti-entropy

  • Failure detection: nodes exchange membership and health through a gossip protocol, so every node learns about failures without a central coordinator.
  • Hinted handoff: if a replica is down, another node temporarily stores its writes with a hint and delivers them when it returns.
  • Read repair: when a read finds a stale replica, update it.
  • Anti-entropy: background comparison of replicas with Merkle trees to find and fix differences efficiently.
A distributed key-value store: a consistent hashing ring for partitioning, quorum reads and writes, vector clocks for conflicts, and gossip-based failure detection.
A distributed key-value store: a consistent hashing ring for partitioning, quorum reads and writes, vector clocks for conflicts, and gossip-based failure detection.

Storage on each node: LSM trees, Bloom filters and tombstones

Each node writes to an append-only commit log for durability and to an in-memory table, flushed to sorted files on disk and merged in the background: a log-structured merge tree (LSM), the design used by Cassandra and RocksDB. Writes are sequential and fast; reads check memory first, then files, using Bloom filters to skip files that can't contain the key. A Bloom filter is a small bit array that answers "definitely not here" or "maybe here", so most lookups skip most files without reading them.

Deletes are writes too. In a leaderless store, removing a key from one replica isn't enough: a replica that missed the delete would later "repair" the key back into existence. So a delete writes a tombstone, a marker that says "deleted at this time", and tombstones are kept long enough for repair to reach every replica. Cassandra keeps them for 10 days by default (gc_grace_seconds). A replica that's offline longer than that must be rebuilt, not just restarted, or deleted data comes back.

The alternative: a leader-based key-value store

The leaderless design above favors availability (AP). If applications need linearizable reads and no conflicts, use a leader per partition: each key range is a Raft group (Day 62), the leader serializes writes, and a majority must store them. No siblings or vector clocks, at the cost of unavailability for a partition that loses its majority and extra latency for writes. etcd, TiKV and CockroachDB work this way. Say which one you'd choose and why: shopping carts and sessions fit leaderless; balances and inventory fit leader-based.

What a strong key-value store design includes

  • Consistent hashing with virtual nodes, and how scaling moves data.
  • Replica placement across failure domains.
  • Quorum parameters with the W + R > N reasoning.
  • A conflict story: vector clocks with merge, or last-write-wins stated honestly.
  • Failure detection and repair mechanisms.
  • A conscious AP-versus-CP choice.
  • Sizing from numbers, and a delete story with tombstones.

Check yourself

So that a single failure domain going down, such as a rack losing power or a zone losing connectivity, can't remove every copy of a key at once. With replicas spread across three zones, the data stays readable, and with the right quorum settings writable, even while one zone is out.

Tombstones for those deletes expired on the other replicas while the node was away, so its old copies looked current and were repaired back. Rebuild nodes that were offline longer than the tombstone retention.

The two other replicas acknowledge; another node keeps a hinted copy for the down replica and delivers it on recovery, with read repair and anti-entropy fixing anything missed.

When applications need linearizable reads and can't handle conflicting versions, such as balances or inventory, accepting lower availability during partitions.

Each on-disk file has a Bloom filter that quickly answers "this key is definitely not here" or "it might be here". Reads skip files that can't contain the key, which avoids many disk reads, at the cost of a small, tunable rate of false positives.