Building a Raft Consensus Engine from Scratch in Rust

A deep dive into implementing the Raft consensus algorithm with durability, snapshots, joint consensus, and a production-grade WAL.

Source: https://github.com/cb7chaitanya/networking/tree/main/raft-consensus ~15,000 lines · 319+ tests · 3 fuzz targets · 22+ Prometheus metrics

Why Build a Consensus Engine?

The distributed systems literature is full of consensus. etcd, ZooKeeper, CockroachDB, TiKV — all production systems that thousands of clusters depend on — use it. But using those systems leaves the hard questions unanswered: how does a group of unreliable servers agree on anything? What prevents two nodes from both believing they are leader? Why must a crashed node forget its vote?

Raft is the clearest answer to those questions in the academic literature. Diego Ongaro's 2014 dissertation "Consensus: Bridging Theory and Practice" and the original paper are unusual in that they specify not just the algorithm but the rationale behind each design decision. This specificity makes Raft ideal for an implementation project: every line of code corresponds to a sentence in the paper.

This implementation covers the full Raft paper plus the dissertation extensions: PreVote, joint consensus, leadership transfer, ReadIndex, and snapshotting, with a production-grade segmented write-ahead log and a complete Prometheus/Grafana observability stack. The goal is to make the protocol mechanics visible at every level — from the byte layout of an RPC to the sequence of events during a leader failover.

Architecture Overview

The central design decision is a pure state machine: RaftNode owns no threads, no async runtime, no sockets. It cannot perform I/O. Instead, the caller drives it with four operations:

• step(msg): Deliver an inbound RPC or response to the node
• tick(): Advance the logical clock by one tick (drives timers)
• drain_messages(): Collect outbound RPCs the node wants sent to peers
• drain_applied(): Collect log entries the state machine has committed

This design comes directly from etcd's raft library and has a critical property: the node is fully deterministic. Given the same sequence of inputs in the same order, it always produces the same outputs. There is no hidden state, no race condition to debug, and no threading to reason about. The in-process simulator exploits this to test failure scenarios that would be nearly impossible to reproduce with real sockets.

┌─────────────────────────────────────────────────────┐
│                     Application                     │
│          propose()  →  drain_applied()              │
├─────────────────────┬───────────────────────────────┤
│   TcpTransport      │  tick() / step() / drain_…()  │
│  [body_len u32]     │  Length-prefixed framing       │
│  [from u64][to u64] │                               │
├─────────────────────┴───────────────────────────────┤
│             RaftNode (pure state machine)           │
│  Leader election · Log replication · Snapshots      │
├──────────────────────┬──────────────────────────────┤
│  MemoryStorage       │   WalStorage (production)    │
│  Vec<LogEntry>       │   Segmented CRC32-framed WAL │
└──────────────────────┴──────────────────────────────┘
plain text

The TcpTransport layer lets external callers inject log entries via handle.propose(data).

Wire Protocol

All Raft RPCs are encoded in a hand-rolled binary format with no external schema dependencies. The format is deliberately simple: a 1-byte type tag followed by a fixed layout of big-endian integers and length-prefixed byte slices. Zero allocations for fixed-size messages; one allocation for the entry data in AppendEntries.

Message types and wire sizes:

• 0x01 RequestVote: 33 B — term, candidate_id, last_log_index, last_log_term
• 0x02 RequestVoteResponse: 10 B — term, vote_granted
• 0x03 AppendEntries: 45 B + entries — term, leader_id, prev_log_index, prev_log_term, leader_commit, entries[]
• 0x04 AppendEntriesResponse: 18 B — term, success, match_index
• 0x05 PreVote: 33 B — same as RequestVote
• 0x06 PreVoteResponse: 10 B — term, vote_granted
• 0x07 InstallSnapshot: 46 B + data — term, leader_id, last_included_index/term, offset, data, done
• 0x08 InstallSnapshotResponse: 9 B — term

Each entry in an AppendEntries carries its own length prefix:

[term: u64][data_len: u32][data: bytes]
plain text

The transport wraps the encoded RPC in a 20-byte frame header:

[body_len: u32][from: u64][to: u64]
plain text

This allows the receiver to pre-allocate an exact-size buffer before reading the body.

Leader Election and PreVote

Raft's election algorithm is elegant in its simplicity: a follower starts an election when its election timer fires without receiving a heartbeat from the leader. It increments its term, votes for itself, and sends RequestVote RPCs to every peer. The first candidate to receive votes from a majority of the cluster becomes leader.

Follower         Candidate            Peer A       Peer B
    │                │                  │             │
    │ (timer fires)  │                  │             │
    │───────────────►│                  │             │
    │                │── RequestVote ──►│             │
    │                │── RequestVote ───────────────►│
    │                │◄─ vote_granted ──│             │
    │                │  (now leader)    │             │
    │                │── AppendEntries(hb) ──────────►│
plain text

Two problems lurk in the basic algorithm.

First, split votes: if multiple followers time out simultaneously and split the cluster's votes, no one wins. Raft prevents this with randomized election timeouts — each node picks a random delay in [election_timeout_min, election_timeout_max). The first to time out usually wins before others even wake up.

Second, disruptive partitioned nodes: a node that was network-partitioned accumulates a high term, then rejoins and immediately starts an election that briefly disrupts the stable cluster. Section 9.6 of the dissertation introduces PreVote to solve this. Before starting a real election, a node runs a speculative pre-election: it sends PreVote RPCs asking peers whether they would grant a vote. Peers reply yes only if they haven't heard from a leader recently and the candidate's log is at least as up-to-date. A partitioned node almost never satisfies these conditions, so it can rejoin without disruption.

The term invariant: The current term must be persisted to durable storage before any RPC response that depends on it. A node that crashes and restarts with a forgotten term could vote twice in the same term, potentially allowing two leaders to coexist — the fundamental safety violation Raft is designed to prevent.

Log Replication

Once elected, the leader accepts proposals from clients, appends them to its log, and replicates them to followers via AppendEntries RPCs. A log entry is committed once the leader has received acknowledgement from a majority of the cluster. The leader tracks each follower's progress with two indices:

• next_index: the next entry to send
• match_index: the highest entry confirmed replicated

Every AppendEntries carries a consistency check — prev_log_index and prev_log_term. A follower rejects the RPC unless its log contains a matching entry at that position. This ensures that when a follower accepts an AppendEntries, its log matches the leader's through the new entries, satisfying the Log Matching property.

Three scenarios require the leader to repair follower logs:

• Missing entries: a follower that lagged behind receives entries starting from where it diverged, not just new entries.
• Conflicting entries: a follower that was briefly a leader may have uncommitted entries the current leader doesn't have. These are overwritten, not merged.
• Far-behind follower: a follower that missed more entries than are retained in memory receives an InstallSnapshot RPC instead, which transfers a compacted state machine snapshot and the log entries after it.

Only current-term entries can be committed. The leader never directly commits entries from previous terms — it commits them indirectly by committing a current-term entry that follows them. This prevents a subtle scenario where a majority acknowledges an entry, then a new election produces a different majority such that the entry was never actually safe.

The Write-Ahead Log

Three pieces of state must survive a crash: the current term, the voted-for node ID, and every log entry that has been acknowledged to the leader. The WAL provides durable storage for all three, plus snapshot metadata.

The WAL is segmented: as the active segment grows past a configurable threshold (default 64 MiB), a new segment is opened. Segment filenames are zero-padded 64-bit IDs: 0000000000000001.wal, 0000000000000002.wal, etc. Segments are append-only and never rewritten — compaction happens by deleting old segments after a snapshot is installed.

Record format

┌──────────────┬──────────────────┬────────────┬────────────────────────┐
│  crc32 (4 B) │ payload_len (4 B)│  kind (1 B)│   payload (N bytes)    │
└──────────────┴──────────────────┴────────────┴────────────────────────┘
plain text

Record kinds:

• TERM (0x01): current_term as u64 big-endian (8 bytes)
• VOTE (0x02): term (u64) + voted_for node_id (u64) — 16 bytes
• ENTRY (0x03): index (u64) + term (u64) + data_len (u32) + data bytes
• TRUNCATE (0x04): from_index (u64) — entries at this index and above are deleted
• SNAPSHOT_META (0x05): last_index (u64) + last_term (u64) + cluster config

Recovery

On startup, all segments are read in ID order. If a record has a mismatched CRC32, a truncated header, a truncated payload, or an unknown kind byte, reading stops at that point. The segment file is truncated to the last clean byte, and all subsequent segment files are deleted. This cleanly handles the most common crash scenario: a partial write at the end of the last segment.

Three fsync policies let operators trade durability for throughput:

• FsyncPolicy::Always: fsync after every write. Safe for leader failover; low throughput.
• FsyncPolicy::EveryN(Duration): fsync at most once per interval. Bounded data-loss window; higher throughput.
• FsyncPolicy::Never: rely on OS page cache. Maximum throughput; data in cache may be lost on hard crash.

Advanced Features

Snapshots (§7)

As the log grows, older entries accumulate. Snapshots compact the log: the leader transfers its state machine snapshot to a lagging follower in chunks via InstallSnapshot RPCs, along with the log index and term of the last included entry. The follower can then discard its entire log up to that point. Snapshot data is stored atomically via write-then-rename in snapshot.bin, with a corresponding SNAPSHOT_META WAL record so the WAL and snapshot file stay consistent across crashes.

Joint Consensus (§6)

Adding or removing cluster members safely requires a two-phase transition. The naive approach — switching from the old configuration to the new one — risks a moment where two disjoint majorities can coexist and elect two leaders. Joint consensus solves this by routing through an intermediate joint configuration where commits require a majority from both the old and new sets. The cluster stays in the joint configuration until the entry proposing it is committed, then switches to the new configuration.

Leadership Transfer (§3.10)

A graceful leader handoff sends a TimeoutNow message to the intended successor, triggering an immediate election without waiting for the election timer. During the transfer window, the current leader rejects new proposals to avoid log divergence. If the transfer doesn't complete within an election timeout, the lock is released and proposals resume.

ReadIndex (§6.4)

Linearizable reads normally require a round-trip through the log. ReadIndex is a lighter alternative: the leader records the current commit index, confirms its leadership with a heartbeat round-trip, then serves the read once the state machine has applied entries through the recorded index. No log entry needed for most reads, and reads stay linearizable.

The In-Process Simulator

Integration testing distributed consensus without determinism is difficult: race conditions surface only under specific timing, network faults must be injected precisely, and test failures may not be reproducible. The simulator eliminates all of that.

let mut sim = Simulator::new(3, config, /* seed */ 42);
sim.elect(1);                    // force node 1 to become leader
sim.propose(b"hello".to_vec()); // append an entry
sim.stabilize();                 // run until quiescent
sim.assert_one_leader();
sim.assert_logs_consistent();   // all nodes agree on every entry
rust

The simulator owns a set of RaftNode instances and a virtual network. It drives them synchronously: tick all nodes, collect their outbound messages, apply network conditions, deliver messages to recipients. Everything is on a single thread. A SplitMix64 PRNG seeded at construction controls all randomness, so the same seed always produces the same message-drop sequence.

Simulator capabilities:

• Message delay: Messages sit in a queue for N ticks before delivery
• Message loss: PRNG-driven drop with configurable rate
• Network partition: Bidirectional block between node sets
• Node crash: Node removed, volatile state lost, storage retained
• Node restart: RaftNode::restore() from saved storage
• Reproducibility: Seeded PRNG; same seed → identical test run

Every test that exercises failure scenarios — split-brain avoidance, log repair after a crash, re-election under partition — runs through this simulator. Tests that appear to exercise randomness are in fact deterministic: the seed is fixed per test case.

Observability

A production Raft cluster needs visibility into election frequency, replication lag, WAL throughput, and transport bandwidth. The metrics server exposes a Prometheus text format endpoint at /metrics, a JSON snapshot at /raft, and a health check at /healthz.

Key metrics:

• raft_current_term (gauge): Current Raft term; fast-growing terms indicate election instability
• raft_leader_id (gauge): Node ID of current leader (0 = no leader)
• raft_is_leader (gauge): 1 while this node is leader
• raft_commit_index (gauge): Highest committed log index
• raft_last_applied (gauge): Highest applied index; lag = commit_index − last_applied
• raft_elections_total (counter): Elections initiated by this node
• raft_proposals_total (counter): Log entries proposed by the application
• raft_proposals_committed_total (counter): Entries committed (rate = commit throughput)
• raft_append_entries_total (counter): AppendEntries RPCs sent (includes heartbeats)
• raft_transport_bytes_sent_total (counter): TCP bytes sent to peers
• raft_wal_bytes_written_total (counter): Bytes appended to WAL segments
• raft_peer_match_index (gauge × peer): Per-peer replication progress

The Grafana dashboard has 27 panels across 9 row sections: Leader Timeline, Term History, Proposal Throughput, Commit Latency, Replication Lag, Follower Status, Snapshot Activity, WAL Growth, and Transport Bandwidth.

Performance Benchmarks

All benchmarks use Criterion.rs with statistical sampling. Numbers are measured on a single core; the hot path in a real cluster is disk fsync latency, not CPU.

• append_entries_encode (10 entries): 61 ns — per-heartbeat serialisation cost
• append_entries_encode (100 entries): 270 ns — bulk replication encode, ~3.7M entries/s ceiling
• append_entries_encode (1000 entries): 3.0 µs — large batch, scales linearly
• append_entries_decode (10 entries): 471 ns — follower parse cost, allocation dominates encode
• append_entries_decode (100 entries): 4.2 µs — 100-entry follower parse path
• request_vote_encode (33 B): 17.6 ns — election RPC, nearly free
• request_vote_decode (33 B): 17.2 ns — vote processing cost per peer
• log_append (100 entries): 2.4 µs — in-memory log write path (Vec extend)
• commit_advancement (10 entries): 8.6 µs — stepping a node through ACKs until commit
• snapshot_install (100 entries): 754 ns — installing a snapshot and truncating the log

The encode/decode asymmetry is expected: encoding AppendEntries writes into a Vec<u8> sequentially, while decoding must allocate a LogEntry and copy each payload. At 270 ns for 100 entries, the leader can encode approximately 3.7 million entries per second per peer — throughput entirely outside the bottleneck budget of any real deployment.

Testing Strategy

With 319+ tests across unit, simulation, integration, and fuzz layers, the test suite is structured so that each layer finds a different class of bug.

Unit tests (293 in-module)

Each module tests its own invariants in isolation. node.rs has 151 tests driving the state machine directly: elections, log repair, commit advancement, snapshot install — all through the pure step/tick interface. storage.rs has 32 tests covering both MemoryStorage and WalStorage, including crash injection by truncating WAL segment files mid-record. wire.rs has 25 tests including roundtrip identity for all 8 message types and boundary cases.

Simulation tests (22 in simulator.rs)

The simulator layer tests multi-node scenarios that would be impossible to make deterministic with real sockets: leader election under partition, log repair when a partitioned node rejoins with stale entries, snapshot installation when a follower is too far behind to catch up via log replication, and split-vote avoidance under simultaneous timeouts. Every test is reproducible by construction.

Integration tests (26 in tests/)

The metrics server tests start a real HTTP listener and exercise the /metrics, /raft, and /healthz endpoints, including concurrent request handling and verification that metric values update correctly as the node state changes.

Fuzz testing

Three libFuzzer targets exercise the decode paths with arbitrary byte inputs:

• wire_decode: fuzz Rpc::decode(); must never panic or memory-corrupt
• message_roundtrip: encode a synthesized message, fuzz the bytes, verify decode succeeds or returns a clean error
• snapshot_decode: fuzz InstallSnapshot payload parsing

Targets run with cargo fuzz and integrate into CI via cargo fuzz run --fuzz-dir fuzz -- -max_total_time=30.

What This Project Reveals

01 — Persistence ordering is the hardest invariant to maintain. Every RPC response that depends on durable state must be sent after that state is written to stable storage. Violating this ordering — even once — can cause the same node to vote twice in the same term. The Storage trait makes the ordering visible: methods return only after the write is durable.

02 — The pure state machine is worth the ceremony. Having no I/O in the consensus core makes every edge case testable in microseconds, without mocks, sleep statements, or port allocation. The 151 tests in node.rs run in under a second and cover scenarios that would require a multi-hour soak test to trigger in a real cluster.

03 — Election randomization prevents cascades, not races. The randomized timeout doesn't prevent two candidates from existing simultaneously — it reduces the probability that they emerge at the same tick. When they do coexist, the term-increment mechanism ensures exactly one survives into the next election cycle.

04 — Committing requires a current-term entry. The most surprising rule in Raft: a leader cannot commit entries from previous terms by counting acknowledgements alone. It must wait until a current-term entry is replicated to a majority, which then carries the older entries with it. Figure 8 of the Raft paper shows exactly why omitting this rule leads to committed entries being overwritten.

05 — WAL recovery must be pessimistic. On crash, the last record in the WAL may be partial: the process died mid-write. Reading must stop at the first anomaly and truncate aggressively. An optimistic approach that tries to skip partial records risks reading garbage as a valid term or vote, permanently corrupting the node's state.

06 — Observability reveals what tests can't. Running a real 3-node cluster under Prometheus + Grafana showed a pattern the simulator tests didn't: after a leader failover, the new leader's AppendEntries rate spikes sharply as it catches up all followers, then settles to the heartbeat baseline. This is expected behaviour, but seeing it measured confirmed the replication catch-up path was working as intended.

07 — PreVote changes the system model, not just performance. PreVote is often described as an optimisation. It is more accurate to call it a correctness improvement for realistic deployments: without it, a node that flaps in and out of the network will repeatedly disrupt the cluster by forcing new elections, even though it can't win them. PreVote makes the cluster robust to this class of misbehaviour at the cost of one extra round-trip per election.

Closing Thoughts

The Raft paper is famous for being understandable. But "understandable" doesn't mean "easy to implement correctly": it means the rules are stated clearly enough that violations are detectable. Working through this implementation, the places where the code can be subtly wrong turn out to be exactly the places where the paper goes to the trouble of explaining why a rule exists, not just what it is.

The persistence ordering requirement, the current-term commit restriction, the pessimistic WAL recovery — each of these has a specific failure scenario that motivated it, described in the paper. Implementing the feature and then reading the paper's motivating scenario for it is a reliable way to build the kind of understanding that doesn't fade.

The complete source is available at https://github.com/cb7chaitanya/networking/tree/main/raft-consensus.