I've been building kvraft in the background for a couple of weeks: a distributed key-value store sitting on top of a Raft implementation I'm writing myself, no consensus library underneath. I do it in milestones and make myself keep the build and tests green at every step, mostly so I can't lie to myself about progress. Today's milestone was M1, leader election. It's the first one where the project stops looking like a key-value store with a lot of empty folders and starts behaving like Raft.
I started the way I usually do, by building and running the tests before
touching anything. M0 was still fine, the write-ahead log test passed,
and the raft package had two files in it, clock.go and
transport.go. Both were just interfaces with a real
implementation on one side and nothing on the other. There was no
consensus code at all yet, which made the next move obvious: write the
state machine that uses those two interfaces to elect a leader.
What the election actually involves
"Elect a leader" packs a lot of moving parts into three words. Three processes that can't share a clock have to agree on which one of them is in charge, and stay agreed until that one dies. Raft does it with a handful of pieces that only make sense together.
There's a term, which is really just a counter that every node carries and every message includes. A higher term always wins the argument, so the moment a node sees one bigger than its own it knows it's behind and steps down. There's the election timeout, and the detail that matters is that it's randomized per node. If everyone waited the same fixed time before putting themselves forward, they'd all become candidates at the same instant, split the vote evenly, and do it again forever; the randomness is the reason a split vote is a rare hiccup instead of a permanent state. A candidate asks the others for votes, and each node hands out at most one per term. Once someone wins, it sends empty AppendEntries messages on a short interval, and every one of those resets the other nodes' election timers, which is what stops a healthy cluster from re-electing over and over.
The code for all of that is short. What's easy to get wrong is the order you check things in. One case that caught me: when an AppendEntries shows up carrying a term lower than mine, I reject it and, on purpose, don't reset my own election timer. If I did reset it, a leader that's already been deposed could keep sending stale heartbeats and stop me from ever starting the election the cluster is waiting for. It's one line of behavior with a real failure mode sitting behind it, and the paper is careful about exactly these orderings. I left the section numbers from the paper in comments next to the rules they map to, so I can trace any decision back to where it came from.
The part that made testing easy
The design choice I'm most glad about is that the Raft core never touches
real time or real sockets. It knows about two interfaces and nothing else,
Clock and Transport. In production those are
backed by wall-clock timers and gRPC. In tests they're backed by fakes,
and that's the thing that makes the tests bearable to write.
Because Transport is an interface, my test network is just a map from node ID to node, with a method that delivers an RPC by calling the destination node's handler directly, in the same process. No ports, no serialization, no waiting on real timeouts. I gave the network a per-node up/down switch, so taking a leader offline or partitioning it away is a single boolean. The election test brings up three nodes, waits for one to win, flips the leader off, and checks that the remaining two elect a new leader at a higher term. Then it brings the old leader back and checks that it quietly steps down instead of trying to stay in charge. The whole scenario finishes in about a tenth of a second.
The bug
The messy part was concurrency, which is where I always end up spending
the time on code like this. Each node has a goroutine running its election
timer, and when it wins it starts a second goroutine to send heartbeats. I
was tracking both with a sync.WaitGroup so that
Stop could wait for everything to finish before returning.
The failure is a timing window. A node decides it has won inside the
goroutine that's counting votes, and that's where it calls
wg.Add for the heartbeat goroutine. If Stop
happens to run at that same moment, it closes the done channel, the
election-timer goroutine notices and exits, the counter drops to zero, and
then a late vote reply arrives, the node "wins," and calls
Add on a WaitGroup that's already at zero with a
Wait in progress. Go panics on that:
panic: sync: WaitGroup misuse: Add called concurrently with WaitIt's the kind of thing that shows up once in a few hundred runs and never
while you're watching. The fix is to have Stop set a stopping
flag under the same mutex before it closes the channel and waits, and to
have the win-the-election path check that flag, under the same mutex,
before it starts the heartbeat goroutine. The same lock on both sides
gives you the ordering you need: if shutdown got there first, the
Add simply never happens. I wrote the reasoning into a comment
next to it, because the two lines look arbitrary without it.
Checking it holds
An awkward admission: I couldn't run Go's race detector on this machine.
It needs cgo, cgo needs a C compiler, and there's no gcc installed here, so
the one tool built for exactly the bug above wasn't available. What I did
instead was keep the concurrency deliberately boring, all the mutable state
behind a single mutex and no goroutine ever making an RPC while holding it,
and then run the tests twenty times back to back to flush out anything
timing-dependent. Twenty green runs and a clean go vet. That's
not the same as a race-detector pass, and I'll run one properly once I've
got a toolchain set up on this box, but it was enough to call the milestone
done.
Both tests pass: a single leader elected with the other two agreeing on it and its term, and a correct re-election after the leader is taken out. M0 and M1 are green in the README now.
Next
M2 is the interesting one. Actual log replication, applying committed entries to the key-value state machine, and serving client reads and writes through the leader. That's when the AppendEntries messages that are empty heartbeats today start carrying real entries, and the log comparison I left as a stub for M1, with a comment noting it's trivially true while the log is empty, has to turn into the real up-to-date check from the paper.