Designing a Key-Value Store

Back to Study

Designing a Key-Value Store

A key-value store keeps data as pairs: a unique key, and a value stored under it. It offers two operations, put(key, value) and get(key). Caches, session stores, shopping carts and user settings are all key-value workloads. Designing one that spans many machines is a classic interview question because it brings together almost every earlier topic: partitioning, replication, the CAP trade-off, and efficient storage.

Step 1: agree the requirements

Following the interview framework, start with scope. A typical set:

  • Values are small, under about 10 KB.
  • The store must hold more data than fits on one machine, and grow by adding machines.
  • It must stay available when individual machines fail.
  • Reads and writes must be fast, measured at a high percentile, not on average.
  • The application can tolerate briefly stale reads in exchange for availability (an assumption to confirm; it decides the CAP choice).

The obvious approach: one big hash table

On one machine, a key-value store is simply a hash table in memory: very fast and simple. It stops working for two reasons: the data outgrows one machine's memory and disk, and one machine is a single point of failure. The design therefore has to spread data across many machines and keep copies of it.

Step 2: partition the data

Each key must have a home machine that any server can work out. Plain hash(key) % N would move almost every key whenever a machine is added or removed, so key-value stores use consistent hashing: machines and keys are placed on the same ring, and each key belongs to the first machine clockwise from it. Adding a machine moves only a small share of the keys, and virtual nodes keep the share even. Try it in the consistent hashing visualization.

Step 3: replicate for availability

Key K is stored on the first node clockwise and copied to the next two

Each key is stored on N machines, usually 3: its home on the ring and the next N - 1 machines clockwise. If one fails, two copies remain. In practice the copies are placed in different racks or data centres, so a single power or network failure cannot remove all of them.

Step 4: choose consistency with quorums

With three copies, a write cannot wait forever for all three, and a read cannot always ask all three. Quorums make this tunable with two numbers:

  • W: a write succeeds once W copies confirm it.
  • R: a read asks R copies and returns the newest value among them.

With N = 3, W = 2 and R = 2, every read overlaps every write in at least one node

If R + W > N, every read overlaps every successful write in at least one copy, so it sees the latest value. With N = 3, the settings R = 2 and W = 2 give that guarantee while tolerating one slow or failed copy for both reads and writes. Changing them shifts the trade-off:

  • W = 1, R = 3: very fast writes, slow reads.
  • W = 3, R = 1: fast reads, but writes fail if any copy is down.
  • R + W ≤ N: fastest of all, but reads may be stale. This is the availability side of the CAP theorem.

Step 5: handle failures

  • Temporary failures. If a home machine is briefly down, the write goes to the next healthy machine on the ring with a note, a hint, saying where it really belongs. When the home machine returns, the data is handed back. Writes keep succeeding throughout.
  • Diverged copies. After failures, copies may differ. Machines compare their data in the background using Merkle trees (trees of hashes), which find the differing keys by exchanging only a few hashes rather than all the data.
  • Conflicting writes. If two clients update the same key on different copies during a partition, both versions are kept with version information (such as vector clocks) so the conflict can be detected and resolved, either automatically (for example, latest write wins) or by the application.
  • Knowing who is alive. Machines exchange membership and health information with random peers, a gossip protocol, so there is no central registry to fail.

Step 6: store data on each machine

Writes go to a commit log and a memory table; reads check memory, then Bloom filters, then only the files that may hold the key

A common storage design on each machine, used by Cassandra and similar systems:

  • Write path: append the write to a commit log on disk (so it survives a crash), then put it in a sorted memory table. When the memory table is full, write it to disk as an immutable sorted file. Writes are fast because they are sequential appends.
  • Read path: check the memory table first. Otherwise, check each file's in-memory Bloom filter and read only the files that may contain the key.
  • Compaction: in the background, merge the sorted files to discard old versions and keep the number of files small.

A real system: Amazon Dynamo

Amazon's Dynamo paper (2007) describes exactly this design, built for services such as the shopping cart that must accept writes at all times. In its own words:

  • It "exposes two operations: get() and put()".
  • It partitions data with consistent hashing and uses quorums: "Setting R and W such that R + W > N yields a quorum-like system", and "The common (N,R,W) configuration used by several instances of Dynamo is (3,2,2)".
  • For temporary failures it uses a "sloppy quorum" with hinted handoff: a replica written to another machine "will have a hint in its metadata that suggests which node was the intended recipient".
  • It recovers from permanent failures with "Anti-entropy using Merkle trees", tracks versions with vector clocks, and uses a "Gossip-based membership protocol and failure detection" that "avoids having a centralized registry".
  • It measures latency "at the 99.9th percentile of the distribution", not the average.

Dynamo's ideas live on in Apache Cassandra, Riak and Amazon DynamoDB.

Summary of the design

  • get and put on keys, partitioned by consistent hashing with virtual nodes.
  • N = 3 copies across failure domains.
  • Quorums (R + W > N for consistency, lower for availability).
  • Hinted handoff, Merkle-tree repair, version information and gossip for failures.
  • Commit log, memory table, sorted files and Bloom filters on each machine.

Implementing it in your project

  • Use one, rather than build one. Redis is the usual in-memory key-value store; DynamoDB and Cassandra are distributed key-value stores with replication and partitioning built in. Pick based on durability needs: Redis for caches and fast shared state, DynamoDB or Cassandra for durable data at large scale.
  • To learn by building, write a toy in stages: an in-memory hash map with get and put; then an append-only log file so data survives a restart; then three processes with a consistent hash ring to choose the home of each key; then writes to N = 3 copies with W = 2 and reads with R = 2. Each stage shows why the real systems have the parts they have.

Sources and credibility

Everything above is written from scratch; the quotes come from the source below, attributed where used.

Primary (highest confidence)

  • Dynamo: Amazon's Highly Available Key-value Store, DeCandia et al., SOSP 2007. Source of the interface, the quorum rule and (3,2,2) setting, the sloppy quorum, hinted handoff, Merkle trees, gossip and the 99.9th percentile requirement.
  • Bloom Filters, Apache Cassandra documentation. Source of the use of Bloom filters on the read path.

Method

  • The step-by-step structure follows the key-value store chapter of Alex Xu's System Design Interview, Vol. 1. The explanations are our own.

On copyright: the diagrams on this page were drawn for this article, and the explanations are original. Quoted phrases are short and attributed.