Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 65 ยท Case Studies: Classic Designs

Design a Distributed Key-Value Store

Design a Dynamo-style key-value store: consistent hashing, replication, quorum reads and writes, vector clocks, hinted handoff and anti-entropy, with Python simulations.

A key-value store maps a key to a value with two operations, put(key, value) and get(key). Systems such as Dynamo, Cassandra and Riak scale this idea across hundreds of machines. The case study is a tour of the main distributed-systems tools: partitioning, replication, quorums, conflict handling and failure recovery.

Requirements

  • put and get with small values (under 1 MB), low latency (single-digit milliseconds).
  • Scale to petabytes and millions of operations per second by adding nodes.
  • Highly available for writes even when some nodes are down.
  • Tunable consistency: callers choose between speed and strictness.
  • Automatic recovery when nodes fail or join.

The CAP theorem says that during a network partition you must choose between consistency and availability. This design chooses availability (an AP system) with eventual consistency, and lets clients tune it with quorums.

Partitioning with consistent hashing

Place nodes on a hash ring. Each key is hashed to a point on the ring and belongs to the first node clockwise from there. Adding or removing a node only moves the keys next to it, instead of reshuffling everything as hash(key) % N would. Each physical node owns many virtual nodes (for example 100 points) so load stays even and a bigger machine can take more points.

Replication

To survive failures, copy each key to the next N distinct nodes clockwise (typically N = 3). That group is the key's preference list. Any node can act as the coordinator for a request: it finds the preference list and talks to those replicas.

Python A hash ring with virtual nodes and replicas

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Quorums

With N replicas, a write waits for W acknowledgements and a read asks R replicas. If R + W > N, every read set overlaps every write set, so a read sees at least one up-to-date copy.

N W R Behaviour
3 2 2 Balanced, survives one node failure
3 3 1 Fast reads, writes fail if any node is down
3 1 1 Fastest, may read stale data
Python Quorum reads and writes with a down node

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The R=1 read asks only the recovered node C and returns the stale v1. The R=2 read also asks B, which holds v2, and picks the highest version.

Conflicts and versioning

If two clients write the same key through different coordinators during a partition, replicas can disagree. Systems resolve this with:

  • Last-write-wins using timestamps: simple, but silently drops one write and depends on clocks.
  • Vector clocks: each value carries a counter per node. If one clock dominates the other, the newer wins; if neither dominates, the writes were concurrent and the client (or a merge function) reconciles them.

Handling failures

flowchart TD
    W["put(k, v)"] --> CO["Coordinator"]
    CO --> A["Replica A"]
    CO --> B["Replica B"]
    CO -. "C is down" .-> D["Next node D holds a hint for C"]
    D -. "C recovers" .-> C["Replica C"]

Hinted handoff keeps writes available when a replica is down.

  • Failure detection: nodes gossip heartbeats; a node unreported for a while is marked down. Gossip avoids a single monitor.
  • Hinted handoff: a stand-in node stores the write with a hint and forwards it when the real owner returns.
  • Anti-entropy: replicas compare Merkle trees (hashes of key ranges) to find and repair differences cheaply.
  • Write path on one node: append to a commit log, update an in-memory table, flush to sorted files (SSTables) and compact in the background. This is an LSM-tree design, great for writes.
  • Read path on one node: check the memory table, then Bloom filters to skip files that cannot hold the key, then the files.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. With N=3, which setting guarantees that every read overlaps the latest write?

    R + W must be greater than N. 2 + 2 = 4 > 3.
  2. 2. Why do nodes use virtual nodes on a hash ring?

    Many points per machine smooth out the distribution of keys.
  3. 3. What does hinted handoff do?

    It keeps writes available during short failures and repairs the owner afterward.
  4. 4. Two concurrent writes have vector clocks where neither dominates. What happens?

    Neither write happened before the other, so the system keeps both and lets the application merge them.

Summary

  • Partition with consistent hashing and virtual nodes; replicate to N successive nodes.
  • Tune consistency with R and W; R + W > N gives overlap.
  • Handle conflicts with vector clocks or last-write-wins and know the trade-off.
  • Recover with gossip failure detection, hinted handoff and Merkle-tree anti-entropy.
  • Each node stores data in an LSM tree: commit log, memtable, SSTables, Bloom filters.

Next: Design a Chat System