Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 36 ยท Projects

Project: Replicated Key-Value Store

Build a quorum-replicated key-value store with versions, read repair and node failures, then test it with seeded random fault injection.

Time to combine what you have learned. In this project you build a small replicated key-value store in Python in the style of Dynamo and Cassandra: every key lives on several nodes, writes and reads need a quorum, versions decide which value is newest, and read repair heals replicas that fell behind. Then you break it on purpose with seeded node failures and write tests that check the guarantees.

It is a simulation, not a network service: nodes are objects, and a "crash" flips a flag. That keeps everything deterministic and runnable in your browser. The concepts come from Replication: Leaders and Followers, Quorums and Tunable Consistency, Partitioning and Sharding and Testing Distributed Systems.

What we are building

Placement Hash a key to pick N owner nodes.
Quorum write Succeed once W owners acknowledge.
Quorum read Ask R owners, keep the newest.
Read repair Fix stale replicas we notice.
1 / 2

The design

  • Cluster: 5 nodes. Each key is stored on N = 3 of them: the node chosen by hashing the key, plus the next two around the ring. This is a simplified form of the consistent hashing from Partitioning and Sharding.
  • Write quorum W = 2, read quorum R = 2. Since 2 + 2 > 3, any read set shares at least one replica with any successful write set.
  • Versions: the coordinator (the client library) stamps each write with an increasing counter. A replica keeps a value only if the version is newer. Real systems use timestamps or vector clocks (Vector Clocks and Causality), because there is no single counter when many coordinators exist.
  • Failures: a crashed replica ignores requests. A write needs at least W live owners, or it raises Unavailable.
  • Read repair: after a read, replicas that answered with an older version receive the newest one.

Step 1: why the quorum math works

Before the code, check the rule by brute force. For three replicas, try every possible write set of size W and every read set of size R, and see whether they always share a replica.

Python Do read and write quorums overlap?

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.

W=2, R=2 always overlaps, and so do the extremes (write to all, read one; write one, read all). W=1, R=1 and W=2, R=1 can miss each other, which is the cause of stale reads. The last lines show how versions compare: tuples sort by the counter first, and ties fall back to the node name, a common deterministic tie-break.

Step 2: the store

Read the code in the next block carefully. It has three groups of ideas: placement (owners), quorum logic (put, get) and maintenance (read repair, crash, recover). The demo after the classes walks through a realistic failure story with a key called cart.

Python The store and a failure story

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.

Follow the story in the output:

  1. put("cart", "apple") reaches all three owners (n3, n4, n0). Then n0 crashes.
  2. put("cart", "banana") still succeeds with two acknowledgements, but n0 keeps version 1 (apple).
  3. n0 returns, but still holds the stale value. Nothing has fixed it yet.
  4. Reads always return banana: a read set of two owners must include at least one of n3 or n4. As soon as a read happens to ask n0, read repair brings it to version 2 (one repair is counted).
  5. With two owners down, put fails with Unavailable: only one acknowledgement. That is the price of strong quorums, the trade-off discussed in CAP, PACELC and Real Trade-offs.
  6. The failed put is not rolled back. The one live owner stored cherry at version 3, and later reads return it. A failed write means "unknown", not "did not happen". Real systems accept this (clients retry, operations are idempotent) or add cleanup.

Do not treat Unavailable from a write as proof that nothing was stored. After a timeout or a failed quorum, the value may still appear later. Design your operations to be safe to retry.

Step 3: tests

Now turn the guarantees into tests. A hand-written test per behavior covers the scenarios, and one seeded random test drives random crashes and operations and checks the key invariant: every read returns the last acknowledged write, or a value from a later failed write. The second part is the "failed puts can surface" behavior you just saw. Without it, a correct store would be flagged by the test.

The last test is a deliberate negative control. We run the same random test against a weak configuration (W=1, R=1) and require that the test catches it. A test that cannot fail proves nothing.

Python The store with a test suite

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.

All tests print PASS, and the weak configuration breaks on nearly every one of 300 seeds, with seed 0 as the first. If you ever see a failure, the seed tells you exactly which run to replay.

Extensions to try

Change the code in the editors above and see what happens:

  • Set n=3, w=3, r=1 in the random test: it still passes, but put now fails whenever any owner is down.
  • Add hinted handoff: when an owner is down, store the write on a fourth node with a hint and replay it later (a sloppy quorum). What happens to the overlap guarantee? See Quorums and Tunable Consistency.
  • Replace the counter with (timestamp, node) versions and give two coordinators skewed clocks, then watch last-write-wins lose a write (Physical Clocks, Drift and Skew).
  • Add anti-entropy: a background pass comparing replicas and copying newer versions, so keys that are never read still heal.
  • Add deletes with tombstones. Why can't you simply remove the key from a replica?

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. With N=3, which settings guarantee that a read overlaps with every successful write?

    R + W must exceed N. Only W=2, R=2 gives 4 > 3 here.
  2. 2. A put raised Unavailable because only one replica was reachable. What can be said about the value?

    Partial writes are not rolled back in this design; the result is unknown, so operations should be safe to retry.
  3. 3. What does read repair do?

    Whenever a read sees differing versions, the coordinator updates the stale responders.
  4. 4. Why does the test suite include a weak W=1, R=1 configuration that must fail?

    A negative control shows that the checker is capable of failing; otherwise a passing result would mean little.

Summary

  • Keys are placed on N owner nodes by hashing; quorum writes (W) and reads (R) with R + W > N overlap on at least one replica.
  • Versions decide the newest value; read repair spreads it to stale replicas that answer a read.
  • A failed quorum write may still leave a partial write, so clients must treat it as unknown and retry safely.
  • Seeded random fault tests check invariants across hundreds of schedules; a negative control proves the test has teeth.

Next: Project: A Mini Raft Cluster, where replicas must agree on an ordered log.