Raft

Deep dive

How it works

Parts:

• persistent state — term, voted_for, log[], fsynced before answering any RPC
• election timer — randomized timeout that starts an election
• replication tracker (leader) — next_index[], match_index[] per follower
• commit index — highest entry known to be on a majority
• state machine — applies committed entries in log order

Operations: election, replication, commit, new-leader no-op (steps below).

State per node: persistent term, voted_for, log[] (fsynced before answering any RPC); volatile commit_index; leader-only next_index[], match_index[].

1. Election. A follower that hears nothing for a random timeout (e.g. 150-300 ms in the paper) increments term, votes for itself, sends RequestVote(term, last_index, last_term). A node grants at most one vote per term, and only if the candidate's log is at least as up to date (higher last term, or same last term and ≥ last index). Majority → leader.
2. Replication. Leader appends the command locally and sends AppendEntries(term, prev_index, prev_term, entries, leader_commit). The follower rejects unless its entry at prev_index has prev_term (log matching property), truncates any conflicting suffix, appends.
3. Commit. An entry is committed once stored on a majority and it is from the leader's current term; earlier-term entries commit indirectly with it. Followers learn commit_index from the next AppendEntries.
4. New leader appends a no-op in its term so prior entries get committed quickly.

roles: Follower ─timeout─► Candidate ─majority─► Leader ─higher term seen─► Follower

client ──► Leader ──AppendEntries──► F1 (append, fsync, ack)
             │  └────────────────────► F2 (append, fsync, ack)
             └ commit when 2 of 3 hold entry from current term ─► apply ─► reply

Code

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Role { Follower, Candidate, Leader }

#[derive(Clone, Debug)]
pub struct Entry { pub term: u64, pub cmd: Vec<u8> }

pub struct AppendReq {
    pub term: u64, pub prev_index: usize, pub prev_term: u64,
    pub entries: Vec<Entry>, pub leader_commit: usize,
}
// On failure `index` is a hint: the leader retries from index + 1.
pub struct AppendResp { pub term: u64, pub success: bool, pub index: usize }

pub struct Raft {
    pub id: usize,
    pub n: usize,                  // cluster size including self
    pub term: u64,                 // persistent
    pub voted_for: Option<usize>,  // persistent
    pub log: Vec<Entry>,           // persistent; log[0] = sentinel {term: 0}
    pub role: Role,
    pub commit: usize,
    pub next_index: Vec<usize>,
    pub match_index: Vec<usize>,
}

impl Raft {
    fn last(&self) -> (usize, u64) { let i = self.log.len() - 1; (i, self.log[i].term) }

    fn observe_term(&mut self, term: u64) {
        if term > self.term { self.term = term; self.voted_for = None; self.role = Role::Follower; }
    }

    pub fn on_request_vote(&mut self, term: u64, cand: usize, last_idx: usize, last_term: u64) -> (u64, bool) {
        self.observe_term(term);
        let (li, lt) = self.last();
        let up_to_date = last_term > lt || (last_term == lt && last_idx >= li);
        let grant = term == self.term && up_to_date && self.voted_for.map_or(true, |v| v == cand);
        if grant { self.voted_for = Some(cand); } // persist + reset election timer before replying
        (self.term, grant)
    }

    pub fn on_append(&mut self, r: AppendReq) -> AppendResp {
        if r.term < self.term { return AppendResp { term: self.term, success: false, index: 0 }; }
        self.observe_term(r.term);
        self.role = Role::Follower;                    // a candidate in the same term yields
        // reset election timer here
        if r.prev_index >= self.log.len() {
            return AppendResp { term: self.term, success: false, index: self.log.len() - 1 };
        }
        if self.log[r.prev_index].term != r.prev_term {
            return AppendResp { term: self.term, success: false, index: r.prev_index - 1 };
        }
        let n = r.entries.len();
        for (k, e) in r.entries.into_iter().enumerate() {
            let i = r.prev_index + 1 + k;
            if i < self.log.len() {
                if self.log[i].term == e.term { continue; } // already have it: never truncate on a stale RPC
                self.log.truncate(i);
            }
            self.log.push(e);
        }
        let last_new = r.prev_index + n;
        if r.leader_commit > self.commit { self.commit = r.leader_commit.min(last_new); }
        AppendResp { term: self.term, success: true, index: last_new } // fsync log before replying
    }

    pub fn become_leader(&mut self) {
        self.role = Role::Leader;
        self.log.push(Entry { term: self.term, cmd: Vec::new() }); // no-op commits older entries
        self.next_index = vec![self.log.len(); self.n];
        self.match_index = vec![0; self.n];
    }

    pub fn on_append_resp(&mut self, from: usize, resp: AppendResp) {
        self.observe_term(resp.term);
        if self.role != Role::Leader || resp.term != self.term { return; }
        if resp.success {
            self.match_index[from] = self.match_index[from].max(resp.index);
            self.next_index[from] = self.match_index[from] + 1;
            self.advance_commit();
        } else {
            let hinted = (resp.index + 1).min(self.next_index[from]);
            self.next_index[from] = hinted.max(self.match_index[from] + 1);
        }
    }

    fn advance_commit(&mut self) {
        let mut m = self.match_index.clone();
        m[self.id] = self.log.len() - 1;
        m.sort_unstable();
        let majority_idx = m[(self.n - 1) / 2]; // held by at least a majority
        // Only count replicas for entries of the current term (Raft paper, Fig. 8).
        if majority_idx > self.commit && self.log[majority_idx].term == self.term {
            self.commit = majority_idx;
        }
    }
}

Complexity and constants

• Messages per commit: 2(n−1) (AppendEntries + ack); with batching, one RPC carries many entries.
• Latency: 1 RTT to the fastest majority + max(leader fsync, follower fsync) if done in parallel. Datacenter RTT order of 0.1-0.5 ms; fsync order of 20 µs (NVMe with power-loss protection) to several ms (consumer SSD, cloud volumes).
• Throughput: leader CPU + NIC bound; batched + pipelined implementations reach order of 10⁴-10⁵ small writes/s per group.
• Failover: election timeout + one round of voting, i.e. order of 1-2× the election timeout.

Efficiency

• Cost: 2(n−1) messages per commit (AppendEntries plus ack), fewer per entry when batched. Latency is 1 RTT to the fastest majority plus the larger of leader and follower fsync when done in parallel: datacenter RTT order of 0.1-0.5 ms, fsync order of 20 µs (NVMe with power-loss protection) to several ms (consumer SSD, cloud volumes). Batched, pipelined implementations reach order of 10⁴-10⁵ small writes/s per group. Bound: fsync latency, then leader CPU and NIC.
• Levers:
  • batch many entries per AppendEntries and per fsync — amortizes RTT and fsync (group commit; Ongaro thesis) — any write load
  • pipeline AppendEntries without waiting for acks — hides RTT (Ongaro thesis) — high-latency links
  • leader writes to disk in parallel with replication — commit waits for max, not sum, of fsync and RTT (Ongaro thesis) — all deployments
  • one Raft group per range or region (multi-Raft, CockroachDB, TiKV) — one leader no longer bounds throughput — large datasets
  • read-only queries without a log entry (ReadIndex or leader lease, Ongaro thesis) — no fsync on reads — read-heavy loads
• Naive → standard → state of the art:
  • one RPC and one fsync per entry · RTT plus fsync, about 0.2-2 ms per write
  • batched entries, parallel leader fsync · many writes per RTT and fsync
  • batching, pipelining and multi-Raft sharding · order of 10⁴-10⁵ writes/s per group, scaled out by group count

Implementation notes

• Persist before replying: term, voted_for, and log entries must be durable before any RPC response, or a restarted node can double-vote. Use a write-ahead log and group commit.
• Pipeline: the leader keeps sending AppendEntries without waiting for acks (optimistically bumps next_index); fsync locally in parallel with network send.
• Pre-vote (thesis §9.6): a partitioned node first asks whether it would win before bumping its term, so it can't disrupt a healthy leader on rejoin. CheckQuorum: a leader steps down if it hasn't heard from a majority within an election timeout.
• Linearizable reads without writing to the log: ReadIndex (leader records commit index, confirms leadership with a heartbeat round, waits until applied) or lease reads (skip the heartbeat while a lease is valid; needs bounded clock drift).
• Snapshots: compact the log; send InstallSnapshot to followers that fell behind the compaction point.
• Membership change: single-server changes (add/remove one at a time) or joint consensus; never switch configs for several nodes at once.
• Multi-Raft: thousands of groups per process; coalesce heartbeats per node pair and quiesce idle groups.

Pitfalls

• Committing a previous-term entry by counting replicas (the Figure 8 bug): it can be overwritten. Only count for current-term entries.
• Truncating the log on every AppendEntries instead of only on a term conflict: a delayed RPC then deletes committed entries.
• Election timeout too close to heartbeat interval or RTT/fsync tail: endless elections. Keep timeout ≥ 10× heartbeat and well above p99 fsync.
• Serving reads from the leader without ReadIndex/lease: a deposed leader returns stale data.
• Even cluster sizes: 4 nodes tolerate 1 failure, same as 3, with a larger quorum.

Variants and alternatives

In production

Configuration and orchestration: etcd (etcd-io/raft, used by Kubernetes), HashiCorp Consul/Nomad/Vault (hashicorp/raft). Databases: CockroachDB and TiKV (raft-rs, multi-Raft per range/region), YugabyteDB. Messaging: Kafka KRaft metadata quorum, RabbitMQ quorum queues (Ra).

Implementations

Sources

• Diego Ongaro, John Ousterhout, In Search of an Understandable Consensus Algorithm, USENIX ATC 2014. paper · talk page
• Diego Ongaro, Consensus: Bridging Theory and Practice, PhD thesis, Stanford, 2014. thesis
• Heidi Howard, Richard Mortier, Paxos vs Raft: Have We Reached Consensus on Distributed Consensus?, PaPoC 2020. paper