← Isaac Ishimwe

Distributed systems · built from scratch

Concordia.Five servers. One truth. Break them.

Concordia (Latin for agreement, literally “hearts together”) is a from-scratch implementation of Raft, the consensus algorithm that keeps etcd, Kubernetes and CockroachDB consistent. Five servers named after Rwandan cities elect a leader and agree on one shared log. Crash them, cut the network in half, drop a third of all messages. A checker running after every single event proves that nothing committed is ever lost or contradicted.

300chaos seeds in the test suite
~1Msafety checks, 0 violations
2,700+crashes and partitions survived
4Raft safety properties checked live
Clusterbooting…
Click a server to crash or restart it
RequestVote vote granted vote refused AppendEntries (with data) heartbeat / ack dropped ring = election timeout
Break things
Scenarios
Clients
Faults
Message loss 0%
Speed 0.22×
Safety checkerall holding
Election safety: at most one leader per term✓
Log matching: same index + term ⇒ same history✓
Leader completeness: leaders hold every committed entry✓
State machine safety: no two servers apply different entries at one index✓
checks run 0 · violations 0
Replicated logs

Each cell is one log entry, coloured by the term it was written in. Solid = committed, dashed = not committed yet. The green bar marks each server's commit index. Watch the dashed entries on a cut-off leader get overwritten after you heal a split brain.

What just happened
time 0sterm 0elections 0msgs 0dropped 0committed 0

Under the hood

Agreement,
without trust in any one machine.

01Terms and elections

Time is split into numbered terms. A follower that hears nothing from a leader before its randomised timeout (the ring) becomes a candidate, bumps the term and asks for votes. A majority makes it leader. Random timeouts stop everyone running at once.

02Only up-to-date logs win

A server refuses its vote if the candidate's log is behind its own. Combined with majorities overlapping, that guarantees any new leader already has every committed entry. Try it: crash the leader right after a write.

03Log replication

The leader appends client writes and streams them with AppendEntries. Each message carries the index and term of the entry just before, and a follower rejects it if that does not match. The leader walks back until the logs agree, then overwrites the follower's conflicting tail.

04The commit rule

An entry is committed once a majority stores it, and only entries from the leader's current term are committed by counting (Figure 8 in the paper). New leaders append a no-op so older entries can commit too.

05A deterministic world

The network is a discrete-event simulation with a seeded random generator: latency, loss and partitions are reproducible, so any bug found by chaos testing can be replayed exactly.

06Proving it, not hoping

The test suite runs 300 seeds of 30 simulated seconds each under crashes, partitions and 15% message loss, checking the four safety properties about a million times. Then it plants real Raft bugs (double voting, voting for stale logs) to prove the checker catches them.