Testing Distributed Systems¶

Why ordinary tests don't work¶

The bugs that matter in distributed systems need a specific interleaving of messages, crashes, and timeouts: a reply delayed past an election, a partition that heals mid-commit, a node restarting between two RPCs. On a real network these interleavings are rare and unrepeatable, and tests that sleep for real seconds are slow and flaky. The techniques on this page make them common, fast, and reproducible, and check results against a precise definition of correct. Everything here is in labs/ and runs with go test.

A simulated network¶

raft.SimNet delivers RPCs between in-process nodes by direct method calls, with everything a real network can do to a message:

// send models one direction of a message: maybe lost, always delayed.
func (s *SimNet) send(from, to int) (*Node, bool) {
    s.mu.Lock()
    ok := s.reachable(from, to) && (s.reliable || s.rng.IntN(10) != 0) // 10% loss when unreliable
    d := s.MinDelay + time.Duration(s.rng.Int64N(int64(s.MaxDelay-s.MinDelay)+1))
    s.mu.Unlock()
    time.Sleep(d)
    if !ok {
        return nil, false // a lost message still costs the sender a timeout
    }
    s.mu.Lock()
    defer s.mu.Unlock()
    if !s.reachable(from, to) { // the partition may have changed while in flight
        return nil, false
    }
    n := s.nodes[to]
    if n == nil || n.dead.Load() {
        return nil, false // the process is down
    }
    return n, true
}

Requests and replies are delayed and dropped independently, so "handled but reply lost" happens naturally. Random delays reorder messages. Partition(groups...), SetUp(id, false), and Heal() change connectivity while messages are in flight. Crashes are a Kill() (all goroutines stop, volatile state is gone) followed by a fresh New() that loads the persisted state.

The node code is unchanged: it talks to a Transport interface, and the simulation is one implementation of it. Designing for this seam — networking, storage, and time behind interfaces — is what makes a distributed system testable at all.

Fake time with `testing/synctest`¶

All the cluster tests run inside synctest.Test. Inside the bubble, time.Sleep, timers, and tickers use a fake clock that jumps forward whenever every goroutine is blocked on a timer or channel. A test in which a cluster runs for 25 seconds of cluster time — with 300–600 ms election timeouts and 1–10 ms network delays — finishes in well under a second of real time. The whole labs/raft suite (seven tests, including 200-round chaos runs and 200 full cluster elections) takes about 2 seconds.

Lessons learned from moving Raft into a fake-time bubble:

Blocking on a mutex is not "durably blocked". If any goroutine sleeps while holding a lock that others are waiting for, fake time can never advance and the test hangs. A simulated fsync delay inside the persist call (made with the node lock held) hung the test suite, and was replaced by counting persists instead.
Fake time exposes timing assumptions. Every node's ticker started in perfect lockstep, which revealed that a 10 ms polling loop erased the randomness of election timeouts (Raft: Leader Election) — a real bug that real clock jitter hid.
Don't seed randomness from the clock. The fake clock starts at the same instant in every run, so time.Now()-based seeds made every run identical.
Every goroutine must be able to exit. synctest.Test waits for all goroutines in the bubble; Kill closes a done channel that every background loop selects on.

Fake time does not make the tests fully deterministic — Go's scheduler still picks goroutine order — but it removes wall-clock flakiness and makes long scenarios cheap enough to run hundreds of times.

Invariant checks while the system runs¶

Assertions at the end of a test miss transient violations. The Raft test harness checks State Machine Safety on every applied entry, on every node, as it happens:

func (c *cluster) consume(i int, ch <-chan ApplyMsg) {
    for m := range ch {
        c.mu.Lock()
        if m.Index != c.next[i] {
            c.t.Errorf("node %d applied index %d, expected %d", i, m.Index, c.next[i])
        }
        c.next[i] = m.Index + 1
        for j := range c.applied {
            if v, ok := c.applied[j][m.Index]; ok && !bytes.Equal(v, m.Command) {
                c.t.Errorf("index %d: node %d applied %q but node %d applied %q",
                    m.Index, i, m.Command, j, v)
            }
        }
        c.applied[i][m.Index] = m.Command
        c.mu.Unlock()
    }
}

and checkOneLeader fails if two nodes ever claim the same term. With these always on, TestChaos — unreliable network, random crashes and restarts, random partitions, commands submitted on every node, 200 rounds, 5 seeds — either passes or points at the exact index and nodes where safety broke.

Linearizability checking¶

For a service, the definition of correct is about what clients observe. Linearizability: every operation appears to take effect at a single instant between its call and its return, and the results match a sequential execution in that order. Equivalently, once a write has returned, every read that starts later sees it (or something newer).

labs/lincheck takes a history of operations with call and return times and searches for such an order:

// checkKey searches for a linearization of one key's operations.
search = func(state string, remaining int) bool {
    if remaining == 0 {
        return true
    }
    memo := done.Text(16) + "|" + state // (set of linearized ops, model state)
    if seen[memo] {
        return false
    }
    seen[memo] = true
    // An op can go next only if no pending op returned before it was called.
    minReturn := earliest Return among pending ops
    for i := range ops {
        if done(i) || ops[i].Call.After(minReturn) {
            continue
        }
        next, ok := step(state, ops[i]) // apply to a sequential KV model; Get must match
        if !ok {
            continue
        }
        markDone(i)
        if search(next, remaining-1) {
            return true
        }
        unmarkDone(i)
    }
    return false
}

This is the Wing & Gong algorithm with Lowe's memoization, the approach used by Porcupine (Go) and Knossos (Clojure, used by Jepsen). The problem is NP-complete in general, so two things keep it tractable: memoizing explored (done-set, state) pairs, and checking each key independently (a KV store is linearizable iff each key's history is).

Its own unit tests pin down the definition: a sequential history is accepted; a read that returns a value overwritten by a write that completed before the read started is rejected; a read overlapping a write may see either value; two appends observed in one order cannot later be observed in the other.

The checker must be able to fail¶

The KV store results in Replicated Key-Value Store — read-through-log and ReadIndex linearizable on ~4,500 operations per run, unsafe local reads non-linearizable in 5 of 5 runs — only mean something because of the last test. The first version of the scenario passed even for the deliberately broken read mode: its clients all migrated off the stale leader together, so no stale read ever happened. A checker and a workload that cannot detect a known bug give false confidence. Always include a mutation: a deliberately broken variant the test must reject.

Deterministic simulation testing¶

The strongest version of these ideas — used by FoundationDB, TigerBeetle, and Antithesis — runs the entire system single-threaded on a simulated network, disk, and clock driven by one random seed. Every failure is reproducible exactly from its seed, and millions of simulated hours run in CI. It requires that all sources of nondeterminism (goroutine scheduling, time, randomness, I/O) go through the simulator, which in Go means designing around interfaces from the start and avoiding free-running goroutines in the core logic (event loops instead). labs/raft is a step on that path — injectable transport, persister, and clock — but not fully deterministic, because it relies on the Go scheduler.

Jepsen-style testing of real deployments¶

Against a real cluster, the same approach scales up: run the actual binaries on several machines, inject faults with real tools (iptables partitions, kill -9, clock skew with faketime or by setting clocks, disk faults with dm-flakey), record a history from real clients, and check it with a linearizability (or weaker consistency) checker. Jepsen's published analyses of etcd, Consul, MongoDB, CockroachDB, Kafka, and others are the best reading on what goes wrong in practice.

A testing checklist for a distributed component¶

Put network, disk, and time behind interfaces; build a simulation.
Write invariants that are checked continuously, not only at the end.
Randomize faults (loss, delay, reordering, partitions, crashes, restarts) and run many seeds; log the seed of any failure.
Check client-visible behaviour against a formal model (linearizability or the weaker guarantee you actually promise).
Include a known-broken mutation that the tests must reject.
Run with -race and under load; logic races are not data races.
Before trusting a pass, ask whether the scenario could have produced the failure you care about.

Common pitfall¶

Testing failover by killing the leader and checking that a new one is elected. The test passes, and says almost nothing: the dangerous cases are not clean crashes but asymmetric and transient faults — the leader that can send but not receive, the partition that isolates the leader with a minority for 2 seconds while clients keep talking to it, the node that pauses for longer than the election timeout and then resumes as if nothing happened, the restart that reads persisted state written halfway. Each of the bugs on these pages — stale reads from a deposed leader, double-applied retries, old-term commits — survives a clean "kill the leader" test. Test the faults that make nodes disagree about who the leader is, not only the ones that remove a node.

Review questions¶

Why are requests and replies dropped independently in the simulated network, and which real-world failure does that model?
What does "durably blocked" mean in synctest, and why did sleeping inside the persist call hang the tests?
Why check invariants on every applied entry instead of only at the end of a test?
Define linearizability in terms of call and return times. Why can each key be checked independently?
Why is a deliberately broken variant an essential part of a linearizability test?