DESIGN.md

Design notes

This document covers the decisions that are not obvious from the code, the ones worth understanding before changing it.

One mutex, three goroutines

Each Raft node has a single mutex guarding all of its state. Concurrency comes from three long-running goroutines rather than fine-grained locking:

• The ticker wakes every 25ms, and if an election timeout has elapsed without contact from a leader or a granted vote, it starts an election.
• The heartbeat loop fires every 100ms on a leader and broadcasts AppendEntries to every follower. Start also triggers an immediate broadcast so a new command does not wait up to a full heartbeat interval to replicate.
• The applier waits on a condition variable and delivers committed commands and installed snapshots to the service through applyCh.

The single mutex keeps the state machine of the protocol easy to reason about. The cost is that every handler is short and never blocks while holding the lock. The one rule that makes this safe is that the applier copies what it needs under the lock, releases it, and only then sends on applyCh. Sending on a channel while holding the lock would deadlock against any handler the receiver calls back into.

The log and its snapshot sentinel

The log is a slice whose entry zero is a sentinel. The sentinel does not hold a real command; it holds the index and term of the last entry covered by the most recent snapshot. After a snapshot at index 500, the sentinel carries {Index: 500, Term: ...} and real entries follow at 501 and up. Every access goes through helpers (at, termAt, sliceFrom, compactTo) that translate between absolute log indices and slice offsets, so the rest of the code never does the offset arithmetic by hand. This is what lets compaction discard a prefix without the leader or follower logic having to special-case it.

Commit only entries from the current term

The subtle safety rule from Figure 8 of the paper: a leader may not consider an entry from a previous term committed just because it is stored on a majority. It must first commit an entry from its own term; that entry's commitment then commits everything before it indirectly. advanceCommit enforces this by refusing to advance the commit index onto an entry whose term is not the current term. Test C2 drives the cluster through crashes and restarts and would lose a committed entry if this rule were dropped.

Fast backtracking

When a follower rejects an AppendEntries because the previous entry does not match, replying with a single "no" would make the leader back up one index per round trip. Instead the follower returns a conflict hint: the term of the conflicting entry and the first index of that term, or the log length if it is simply too short. The leader uses the hint to skip an entire term's worth of entries at once. This is the standard optimization from the paper's discussion and matters when a follower has diverged by many entries.

Handling a term change during a pending request

When a client request is submitted, the KV server calls Start, gets back the index the entry would occupy if this node stays leader, and waits for that index to be applied. Two things can go wrong, and both are handled by checking the identity of what actually commits at that index rather than trusting the index alone:

• The node loses leadership and a different leader places a different command at that index. The applier delivers that command; the waiting handler sees that the applied client ID and sequence number do not match its own request and returns ErrWrongLeader so the client retries elsewhere.
• The entry never commits because the node was partitioned. The handler times out after 700ms and returns a retryable error.

This is why the notification passed from the applier to the handler carries the applied operation's client ID and sequence number, not just its result.

Exactly-once writes

The client library assigns each logical operation a sequence number that increases per client. The state machine keeps, per client, the sequence number and result of the most recent write it applied. When it sees a write whose sequence number it has already applied, it returns the remembered result without mutating state. Reads are not deduplicated because they do not mutate anything. This turns the at-least-once delivery of the retrying client into exactly-once application, which is what makes Append safe to retry.

The dedup table is part of the snapshot. If it were dropped on compaction, a retry that arrived after a snapshot could be applied a second time, so it has to travel with the key-value data.

Persistence format

A node persists its current term, its vote, and its log as a single gob-encoded blob, written together with the snapshot in one atomic Save. Writing them together is what guarantees the two can never be inconsistent after a crash: the log prefix the snapshot covers and the snapshot itself always agree. The in-memory persister models this for tests by holding both blobs and handing out independent copies across a simulated restart; the file-backed persister writes each blob to a temporary file and renames it into place.

On restart a node reads its snapshot directly to rebuild the service state and sets its applied and commit indices to the snapshot point. It does not redeliver the snapshot through applyCh; only a snapshot installed at runtime by a leader is delivered that way. This keeps restart from replaying work the service has already absorbed.

When snapshots are triggered

The service, not Raft, decides when to snapshot. After applying each command the KV server checks the size of the persisted Raft state against its configured maxraftstate. When the state exceeds the threshold it serializes the store and the dedup table and calls Snapshot, which compacts the log up to that index. A maxraftstate of -1 disables snapshots entirely, which the correctness tests use when they want the full log to remain.

A follower that has fallen so far behind that the leader has already discarded the entries it needs is caught up with InstallSnapshot instead of AppendEntries. The follower replaces its log prefix, schedules the snapshot for delivery to its service, and advances its applied and commit indices so it never replays the covered entries.

The transport seam

The consensus and store layers depend only on rpcend.End, an interface with a single Call method. The in-memory harness used by the tests and the real TCP transport used by the binaries both satisfy it. The tests can therefore drop and delay messages deterministically, while the same code paths run unmodified over real sockets. The TCP transport adapts the handlers, whose signatures match the harness convention of taking arguments by value and returning nothing, to net/rpc, which expects a method returning error, and registers them under the same service names so the dispatched method strings are identical.