Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 36 ยท Reliability and Operations

Testing Distributed Systems

Learn deterministic simulation, fault injection, property-based testing and linearizability checking, with a runnable seeded chaos tester.

Distributed bugs are rude. They appear once in a million runs, depend on the exact order in which messages arrive, vanish when you add a log line, and show up only in production on a Friday evening. A unit test that passes on your laptop proves very little about code that must survive reordered, duplicated, delayed and lost messages and crashing nodes.

The good news is that you can test this kind of software very well, if you stop relying on luck. The core idea is to take control of the sources of nondeterminism (time, scheduling, network, failures) and let a seeded random generator drive them. Every failure is then reproducible from a single number. This lesson shows that approach, plus property-based checks and a linearizability checker in the style of Jepsen. The failure types being injected are described in Failure and System Models.

Test what really breaks

Randomize Reorder, drop, duplicate, delay.
Inject faults Crash nodes, cut links.
Replay Same seed, same bug.
Check properties Assert what must always hold.
1 / 2

Make nondeterminism controllable

Real systems depend on things your test cannot control: the system clock, thread scheduling, network latency. The trick of deterministic simulation is to hide those behind interfaces. In tests you plug in:

  • a fake clock that only advances when the test says so,
  • a simulated network, which is just a list of pending messages that a scheduler delivers in a chosen order,
  • a seeded random number generator that decides which message goes next, which are dropped or duplicated, and when nodes crash.

Run the same code with seed 1, 2, 3 ... 10,000 and you explore thousands of interleavings in seconds. When seed 4,217 breaks an invariant, you run seed 4,217 again and get the identical failure, so you can debug it step by step. Systems such as FoundationDB were built around this idea.

The example below models a service that receives deposit messages over an at-least-once network. The network drops messages (the sender retries) and sometimes duplicates them. The property we check is simple: after all messages have been delivered, the balance equals the sum of the distinct deposits.

Python Seeded simulation finds a duplicate-delivery bug

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.

Without deduplication, almost every seed fails, because duplicates are common in this model. The bug is found at once, and replaying a failing seed produces exactly the same trace, which is what makes it debuggable. With an idempotency check (see Idempotency, Retries and Backoff) all 200 seeds pass. A real network's rates would be lower, but then you simply run more seeds.

Fault injection and chaos

Fault injection means causing failures on purpose: kill a process, drop packets, add latency, fill a disk, skew a clock. In a simulation it is just more random choices. In real systems tools do it for you, and chaos engineering applies it to production-like environments in a controlled way: start with a hypothesis ("if one replica dies, error rate stays under 1%"), inject the fault, measure, and fix what you find.

Useful faults to try on every system:

  • crash and restart a node at a random moment (including in the middle of a write),
  • partition the network into two sides, then heal it,
  • delay or duplicate messages, deliver them out of order,
  • slow one node down without killing it (slow is often worse than dead),
  • jump a clock forward or backward.

Below is a small seeded chaos tester for a three-replica register. Each step, every node is down with 20% probability. Writes go to W random live replicas, reads ask R live replicas and return the newest version. We count how often a read returns something older than the last acknowledged write, for different values of W and R. Quorum ideas come from Quorums and Tunable Consistency.

Python A seeded chaos tester for quorum settings

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 output shows the trade-off in numbers. With W=1, R=1 every run eventually returns stale data. With W=2, R=2 (so R + W > N) no stale read is ever seen, but many reads are unavailable because two live replicas are needed. W=3, R=1 is also safe but makes about half of the writes fail, because all three replicas must be up (not shown in this tally, which counts unavailable reads only). A chaos test does not prove correctness, but it turns an abstract rule into evidence you can rerun.

Property-based testing

Instead of writing a few hand-picked examples, property-based testing states a rule that must hold for all inputs and lets a generator produce hundreds of random ones. When one fails, the tool shrinks it to a small failing case. Libraries such as Hypothesis (Python), QuickCheck (Haskell), fast-check (JavaScript) and jqwik (Java) do this.

For distributed code, good properties are things like:

  • Convergence: after all messages are delivered, every replica has the same state (see CRDTs).
  • Safety: two nodes never both think they are leader in the same term; a committed value is never lost.
  • Idempotence: applying an operation twice equals applying it once.
  • Commutativity: merging in any order gives the same result.

The simulation above was already property-based in spirit: random seeds produce random schedules, and the property is checked at the end. Add a "shrinker" that retries with fewer messages or fewer faults and you get small, readable counterexamples.

Checking linearizability

How do you test that a replicated store behaves like a single correct copy? Record a history: for each client operation, the time it was invoked, the time it returned and its result. A history is linearizable if the operations can be put in a single order that (1) respects real time (if A finished before B started, A comes first) and (2) makes every read return the latest preceding write. This is the strongest model from Consistency Models.

Jepsen, the well-known testing framework, does exactly this on real databases: it runs concurrent clients while a "nemesis" cuts networks and kills nodes, then checks the recorded history. The tiny checker below brute-forces all orderings of a register history. That is fine for a handful of operations, while real checkers use much smarter search.

Python A brute-force linearizability checker

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.

In the first history, the read r2 overlaps the write, so it may legally return the old value; the checker finds the order r2, w1, r1. In the second, r2 begins after r1 has already seen the new value but returns the old one. No valid order exists, which is a stale read, the bug typical of a replica that has fallen behind.

Record histories from your own tests, including operations that timed out. A timed-out write may or may not have happened; checkers treat it as "possibly applied", which catches many real bugs.

Putting it together

A practical test strategy for a new distributed component:

  1. Unit-test the pure logic (state machines, merge functions) with ordinary tests and property tests.
  2. Simulate the whole cluster with a fake network and clock, run thousands of seeds, and assert invariants after each run and during it.
  3. Check histories for the consistency level you promise.
  4. Inject faults in an integration environment, then in production-like chaos experiments.
  5. Keep every failing seed as a regression test.

The two projects at the end of this track use this style: Project: Replicated Key-Value Store and Project: A Mini Raft Cluster.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main benefit of deterministic simulation with a seeded random generator?

    Controlling time, scheduling and failures through a seeded RNG makes rare interleavings reproducible and debuggable.
  2. 2. Which is a good property to check for replicas of a CRDT after all messages are delivered?

    Convergence is the key property; CRDT merges are designed to work under reordering and duplication.
  3. 3. In the linearizability example, why is the second history rejected?

    Real-time order forces r2 after r1 and w1, so r2 must see 1; returning nothing is a stale read.
  4. 4. Why does a chaos test with W=1, R=1 on three replicas show stale reads?

    With R + W not greater than N, the read set and write set may not intersect.

Summary

  • Make time, scheduling, the network and failures controllable, and drive them from a seeded random generator.
  • A failing seed is a reproducible bug report; keep it as a regression test.
  • Fault injection and chaos engineering test crashes, partitions, delays and clock jumps against a hypothesis.
  • Property-based tests assert rules such as convergence, safety and idempotence over many random inputs.
  • Linearizability checkers (the Jepsen approach) verify recorded histories against the promised consistency level.

Next, build something real in Project: Replicated Key-Value Store.