The 100 problems, solved / Storage and files / 007 · Design a distributed key-value store

Design a distributed key-value store

A billion keys, single-digit-millisecond reads, survive a machine dying mid-write.

Problem 007 of 100Storage and filesL51 Nov 2026
Concepts this design leans on
  • Key-value stores — The simplest database: a hash map spread over machines.
  • Consistent hashing — Assigning keys to machines so adding one machine moves only a few keys.
  • Replication — Keeping copies so reads scale and a dead machine loses nothing.
  • LSM trees and B-trees — The two ways disks store sorted data, and why writes and reads favour different ones.
  • Quorums — Reading and writing enough copies that the two always overlap.
  • Consistency models — What a reader is promised about writes they did not see happen.

01The design, in the six-step framework

1. Requirements

Functional

  • get(key), put(key, value), delete(key); keys up to 1 KB, values up to 1 MB.
  • Optional: a TTL per key and a compare-and-set for the callers that need it.
  • Out of scope: range scans, secondary indexes, multi-key transactions.

Non-functional

  • 1 billion keys, 1 TB of values; 100,000 reads/s and 20,000 writes/s, growing 10× over three years.
  • Read p99 under 10 ms, write p99 under 20 ms within a region.
  • No acknowledged write is lost when any single machine dies; the service keeps serving through one machine failure with no operator action.
  • Tunable consistency: default is strong for a single key (read your own write); callers may ask for faster eventually consistent reads.
Back of the envelope

Data: 1 TB of values plus keys and overhead ≈ 1.5 TB; with 3 replicas, 4.5 TB. That fits in RAM across a handful of 256 GB machines, or on SSD across any machines.

Per node at 10× growth: 1.2 million reads/s and 200,000 writes/s total; at 20,000 reads/s per node that is 60 nodes for reads, plus headroom → plan 100 nodes, 150 GB each.

A single SSD does 100,000 random reads/s, so disk is not the limit; the network round trip and the replica fan-out set the latency budget.

2. Core entities

  • Record: key, value, version (a logical clock or timestamp), TTL, tombstone flag.
  • Partition: a range of the hash ring, its replica set (3 nodes), its current leader if using leader-based replication.
  • Node: id, address, partitions owned, health.

3. API

  • GET /kv/{key}?consistency=strong|eventual → value, version.
  • PUT /kv/{key} body: value, optional ttl, optional if_version for compare-and-set → new version, or 409 on mismatch.
  • DELETE /kv/{key} → writes a tombstone.
  • Internal: replicate(partition, record) between nodes; handoff(partition, from, to) for rebalancing.

4. High-level design

ClientsRoutingStorage nodesControlget / putwritereplicatereplicatering mapnode downheartbeatClient library(ring-aware)Coordinator(any node)Node Aleader for P7Node Breplica P7Node Creplica P7Membership + ring(consensus-backed)Failure detector

A put followed by a strong get:

  1. The client hashes the key onto the ring, finds partition P7 and its leader (Node A) from a cached ring map, and sends the put there (or to any coordinator, which forwards).
  2. Node A appends the record to its write-ahead log and memtable, sends it to B and C, and acknowledges the client once a quorum (2 of 3) has it durably. The record carries a version.
  3. A strong get goes to the leader, or reads from a quorum and returns the highest version; an eventual get reads from the nearest replica.
  4. Memtables flush to sorted files on disk; compaction merges them and drops old versions and expired TTLs.

5. Deep dives

How are keys spread over nodes, and what happens when a node is added?

Modulo hashing (key hash mod N) moves almost every key when N changes. Consistent hashing with virtual nodes places 100 or so tokens per physical node on a ring; a key belongs to the first token clockwise, and adding a node takes about 1/N of the keys from everyone evenly. Replicas are the next distinct physical nodes clockwise, so a partition's replica set is derived, not configured. Rebalancing streams partitions from old owners to the new node in the background while both serve reads, with the ring map versioned so clients retry on a stale map. Hot keys are the remaining problem: a single key read 100,000 times a second lands on three nodes however good the hashing is. The answer is a small client-side cache for keys marked hot plus read replicas beyond three for that partition.

Leader-based or leaderless replication?

OptionWrite latencyConsistencyFailoverComplexity
Leader per partition (Raft)one round trip to a quorumstrong by defaultelection, a few seconds of unavailabilityconsensus library
Leaderless (Dynamo-style, W + R > N)same quorum round tripeventual; conflicts need vector clocks or last-writer-winsnone needed, always writableread repair, hinted handoff, conflict resolution

Choice: leader per partition with Raft, because the requirement is strong single-key consistency by default and compare-and-set, both of which are natural with one writer and painful with concurrent writers. Eventual reads are served from followers. Leaderless designs win when the requirement is "always accept writes, even partitioned", which was not asked.

A node dies mid-write. What exactly is guaranteed?

The write was acknowledged only after two of three replicas appended it to their logs, so at least one surviving replica has it. The failure detector (missed heartbeats for a few seconds) marks the node down; the remaining replicas of each of its partitions elect a new leader, which must have the latest acknowledged log entry (Raft guarantees it). Clients get a few failed requests, refresh the ring map, and retry. Writes that were in flight but not yet acknowledged may or may not have survived, which is why every put carries a client-supplied version or idempotency token so a retry cannot double-apply. After the node is replaced, its partitions are re-replicated from the leaders, throttled so recovery does not starve traffic.

The storage engine: why an LSM tree here?

Writes are appended to a log and a memtable and flushed as sorted immutable files, which turns random writes into sequential ones and keeps write p99 low even under compaction. Reads check the memtable, then per-file Bloom filters so most files are skipped, then the file's index. See LSM trees and B-trees for why a B-tree would win if the workload were read-mostly with small updates in place. TTLs are enforced lazily: expired records are filtered on read and dropped at compaction. The read-only variant one Blind report describes (1 billion keys, no updates, 40 ms p95 at 100 QPS) is simpler still: build one sorted file per partition once, keep its index in memory, and the whole thing fits on a few machines with the question becoming a capacity exercise rather than a replication one.

Multi-region: what changes when readers are on another continent?

A single-region quorum write costs one round trip inside a data centre, about 1 ms. Stretching the replica set across continents makes every write pay a 100 ms round trip to reach a quorum, which breaks the 20 ms target. The usual answer is to keep each partition's quorum within one region and asynchronously ship the log to a replica in the other region, which serves eventual reads locally and can be promoted if the home region is lost, with a bounded window of recent writes at risk. Callers who need strong reads from far away pay the round trip to the home region. Saying this explicitly, with the numbers, separates a strong answer from one that waves at "geo-replication".

6. What a strong answer sounds like

  • Size it: 4.5 TB replicated, 100 nodes at 10× growth, and note that SSD IOPS are not the bound.
  • Draw the ring with virtual nodes and say in one sentence what moves when a node joins.
  • Pick leader-based replication and justify it from the strong-consistency and compare-and-set requirements; mention when leaderless would be the right call.
  • State the durability guarantee precisely (quorum ack, log-based election) and how clients recover.
  • Expect follow-ups on hot keys, large values (store them in blob storage and keep a pointer), and multi-region.
  • Common mistake: "I will just use Redis" without explaining partitioning, replication and what happens on failure.

02Where this question was reported