Raft Deep Dive: Consensus Internals, Edge Cases, and the Paxos Problems It Solves

1. Problems with Paxos

Saying "Paxos is hard to understand" undersells the problem. The paper is specific about three structural reasons.

The nondeterminism problem. Paxos has a large state space, many ways servers can legally disagree with each other mid-protocol, and many possible orderings of events that all have to be reasoned about separately. That's what makes it hard to build intuition for. Raft attacks this directly: logs aren't allowed to have holes, a leader never reorders or rewrites its own log, and followers only ever diverge from a leader in constrained, well-understood ways. Interestingly, Raft doesn't eliminate nondeterminism everywhere, it deliberately keeps it in exactly one place: election timeouts are randomized. That's a case where nondeterminism helps, because the rule becomes "any of you could time out first, it doesn't matter which".

The single-decree decomposition problem. Paxos is built up from "single-decree Paxos", a protocol for agreeing on exactly one value, and multi-Paxos bolts multiple instances of that together to form a log. The trouble is that single-decree Paxos is itself dense and non-intuitive, so nothing built on top of it inherits any simplicity. Worse, there's no single, universally agreed-upon algorithm for how to compose those instances into multi-Paxos, the original description barely covers it, so every real implementation ends up inventing its own composition rules. Raft skips this entirely by designing directly around a log from the start, instead of gluing together independent single-value agreements after the fact.

The symmetric peer-to-peer problem. Paxos's core protocol treats all servers as symmetric peers, with leader election bolted on afterward purely as a performance optimization, it isn't fundamental to the protocol. That's reasonable if you're only ever deciding one value, but it's a mismatch for a log, where you're making a sequence of decisions. Raft makes the leader load-bearing and structural: elect one server first, then let it unilaterally sequence everything. Fewer roles to reason about, one direction of data flow, and no conflicting proposals from multiple peers to reconcile.

2. The Fault Model: Non-Byzantine Only

Raft (like Paxos) assumes non-Byzantine faults. A Byzantine fault is a component failing in an arbitrary or malicious way, sending different, contradictory information to different peers, corrupting messages, or actively lying about its own state. Tolerating that requires extra cryptographic and protocol machinery, since no single message can be trusted at face value.

Raft instead assumes fail-stop behavior: a server either works correctly, or it crashes and simply stops responding, it does not send corrupted or intentionally misleading messages while it's still running. A crashed server may later recover from stable storage and rejoin. The algorithm still has to tolerate an adversarial network, delayed, dropped, duplicated, or reordered messages, just not an adversarial server. Byzantine-tolerant systems typically need 3f+1 nodes to survive f faults, versus the much cheaper 2f+1 that non-Byzantine protocols get away with.

3. How Many Failures Can You Actually Survive?

Because Raft and Paxos are both majority-quorum protocols, they have identical fault tolerance. Raft's advantage is understandability, not resilience. Progress requires a majority of servers reachable and healthy; drop below a majority and the cluster stops accepting new commands. It doesn't corrupt anything, it just halts.

For an odd-sized cluster of N = 2f + 1 servers, it survives exactly f failures. That's why five-server clusters are so common in practice, two failures tolerated, without the extra operational overhead of running seven or nine nodes.

4. Terms and Index: The Two Numbers That Make Everything Work

Term is Raft's logical clock. It's a monotonically increasing integer, and every term starts with an election. There is never more than one leader in a given term (the Election Safety property). Servers exchange their current term on every RPC, if a server sees a term higher than its own, it immediately updates and steps down to follower. This is how Raft detects and discards stale leaders without relying on wall-clock time at all.

Index is simply an entry's position in the log (indexing starts at 1). Every log entry is really a triple: (index, term, command) position, the term the leader created it in, and the actual state machine command. The term stamped on each entry is what lets Raft detect inconsistencies between logs without comparing full histories.

5. Server States vs. Server State

"What state" actually means two different things here, worth separating.

Server states (the role a server is playing): exactly three — follower, candidate, and leader. Every server starts as a follower. A follower that stops hearing from a leader becomes a candidate. A candidate that wins a majority vote becomes leader. Any of the three reverts to follower the instant it sees a higher term than its own.

Server state (the data each server actually tracks) splits into three groups:

nextIndex[] and matchIndex[] only exist on the current leader and get reset from scratch every time a new leader takes over, they're replication bookkeeping, not part of the durable log.

6. The Two RPCs That Run The Whole Protocol

Ignoring snapshots and client interaction, Raft's basic operation needs exactly two RPC types.

RequestVote: sent by a candidate to every other server during an election.

• Carries: the candidate's term, its ID, and the index/term of its last log entry.

• A receiver grants its vote only if it hasn't already voted for someone else this term, and the candidate's log is at least as up-to-date as its own. Otherwise it declines.

AppendEntries: sent by the leader, both to replicate real entries and as an empty heartbeat.

• Carries: the leader's term, the index/term of the entry immediately before the new ones (prevLogIndex / prevLogTerm), the new entries themselves (empty for a heartbeat), and the leader's commitIndex.

• A receiver rejects it if the term is stale, or if it doesn't have an entry matching prevLogIndex/prevLogTerm — this consistency check is what stops logs from silently diverging. If accepted, conflicting entries are deleted and replaced, new entries are appended, and commitIndex advances to match the leader's.

Both RPCs return the responder's own term — how a stale leader or candidate discovers it's out of date and steps down.

7. Rules for Servers

Condensed into the actual behavioral rules each role follows:

ALL SERVERS:
  if commitIndex > lastApplied: apply log[lastApplied] to state machine, lastApplied += 1
  if any RPC contains a term > currentTerm: update currentTerm, revert to follower

FOLLOWERS:
  respond to RequestVote and AppendEntries
  if election_timeout elapses with no valid RPC from a leader/candidate: become candidate

CANDIDATES:
  on becoming candidate: currentTerm += 1, vote for self, reset timer, send RequestVote to all
  if majority votes received: become leader
  if AppendEntries received from a legitimate new leader: become follower
  if timeout elapses with no result: start a new election

LEADERS:
  on election: send empty AppendEntries (heartbeat) immediately, and periodically thereafter
  on client command: append to own log, replicate via AppendEntries
  if a follower is behind: send it entries starting at nextIndex[follower]
  if AppendEntries succeeds: update nextIndex/matchIndex for that follower
  if AppendEntries fails due to log mismatch: decrement nextIndex, retry
  if some index N is on a majority AND log[N].term == currentTerm: commitIndex = N

8. What Actually Happens When Things Fail

• A minority of servers gone (say 2 of 5, neither the leader): no visible impact. The leader still reaches a majority on every commit; clients notice nothing except the cluster now has less headroom for a second failure.

• A follower gone: effectively the same, the leader just stops getting acknowledgments from that one server and keeps retrying AppendEntries to it indefinitely. No effect on commits, since those only ever need a majority.

• The leader gone: followers stop receiving heartbeats. Once one hits its randomized election timeout, it becomes a candidate and triggers an election. There's a brief unavailability window, roughly one election timeout, until a new leader is chosen and heartbeats resume.

• A majority gone (say 3 of 5): this is the real failure mode. No candidate can gather enough votes to become leader, and even a surviving old leader can't reach a majority to commit anything new. The system simply halts until enough servers come back, it does not return an incorrect result. Unavailability is the price Raft pays to keep safety unconditional.

9. The Trickiest Edge Case: A Majority Isn't Always Enough

This is the scenario that trips people up, and it's a genuinely subtle part of the paper. It answers: can a leader commit an entry from an earlier term just because it now sees that entry sitting on a majority of servers?

Walk through it with five servers, S1–S5:

1. S1 is leader in term 2. It appends an entry at index 2 and starts replicating it, but only gets it onto itself before crashing, nowhere near a majority.

2. S1 crashes. S5 wins an election for term 3 (votes from S3, S4, and itself, valid, since none of them had that index-2 entry yet). S5 accepts a different command at index 2, then S5 also crashes before that entry commits anywhere.

3. S1 restarts and gets re-elected. call it term 4. As the new leader, it forces followers to match its own log, so its original term-2 entry at index 2 gets pushed back out and lands on, say, S1, S2, and S3. That's now a majority of the cluster holding that term-2 entry, but it is still not committed. Raft only counts replicas toward commitment for entries from the leader's current term; a majority of an old-term entry doesn't qualify.

4. If S1 crashes again right here, before committing anything from term 4 itself, S5 can be re-elected, this time with votes from S2, S3, and S4. That's legal: S5's log (last entry from term 3) is more up-to-date than S2/S3's log (last entry from term 2), which satisfies the election restriction. Once S5 is leader again, it overwrites that "majority-held" term-2 entry with its own term-3 entry. The entry that looked safe -> sitting on a majority -> just got erased. That's exactly why Raft refuses to treat old-term majority replication as committed.

5. But if instead S1, after step 3, manages to replicate one new entry from its own current term (term 4) onto a majority before crashing, that entry commits directly, and because of the Log Matching Property, everything before it in S1's log (including the old term-2 entry) becomes committed indirectly at the exact same moment. Now S5 can never win another election: its log (term 3) is less up-to-date than the majority's (term 4), so nobody holding the newer log will vote for it.

The takeaway: "replicated on a majority" and "committed" are not the same thing unless the entry is from the current leader's own term. That one deliberately conservative rule is what stops a resurrected old leader or a stale candidate from ever silently erasing something that looked safe a moment earlier.

10. Why Election Timeouts Are Randomized

If every follower used the same fixed timeout, a leader failure would make all of them become candidates at once, split the vote across however many candidates there are, and repeat the identical tie indefinitely. Randomizing each server's timeout (typically drawn uniformly from a fixed window, e.g. 150–300ms) means one server almost always fires first, requests votes before anyone else even notices the leader is missing, and wins cleanly before a second candidate can emerge. It's nondeterminism used on purpose: instead of building a mechanism to break ties, Raft just makes ties rare in the first place.

11. Timing and Availability

Raft's safety never depends on timing, a slow network or a paused server can only ever cost availability, never correctness. But availability obviously does depend on timing, and the paper expresses the requirement as one inequality:

broadcastTime ≪ electionTimeout ≪ MTBF

• broadcastTime, the average round-trip time for a leader to send an RPC to every server and get responses back.

• electionTimeout, the randomized follower timeout described above.

• MTBF, Mean Time Between Failures: the average uptime of a single server before it crashes.

electionTimeout needs to sit comfortably above broadcastTime, or leaders can't reliably deliver heartbeats before followers give up on them and trigger pointless elections. And it needs to sit comfortably below MTBF, or the cluster spends a meaningful fraction of its life leaderless every time a server dies. Measured broadcast times ran roughly 0.5–20ms depending on the storage layer, and typical server MTBF is months, so a 150–300ms election timeout comfortably satisfies both sides. Their own benchmarks got a leader elected in well under 40ms on average with a much lower 12–24ms timeout, but they explicitly recommend staying conservative in production rather than chasing the fastest possible failover, since shaving the timeout too close to broadcast time risks unnecessary leader churn.

12. Reads, Leases, and Why Raft's Default Avoids Clocks

Read-only requests don't strictly need to go through the log, there's nothing to replicate. But answering a read straight from local state is dangerous: if this leader has been silently deposed (say, it's stuck on the wrong side of a network partition and a new leader was already elected on the other side), it could hand back stale data without ever realizing it. Raft's solution is two extra safeguards:

1. A new leader commits a blank no-op entry at the very start of its term, purely so it can be certain which entries are actually committed (Leader Completeness guarantees it has every committed entry, but not that it yet knows which ones those are).

2. Before answering any read, the leader does a live heartbeat round with a majority to confirm it's still actually the leader.

That heartbeat round-trip is the cost of safety, it adds real latency to every read. The paper explicitly floats a faster alternative: instead of confirming liveness on every single read, let the leader assume it holds a lease, "I heard back from a majority as recently as time T, so I'm valid until T + some window", and skip the round-trip entirely during that window. This is faster, but it quietly swaps a message-based safety proof for a clock-based one: it now only holds if clocks across the cluster stay within bounded drift and the leader's own process never stalls longer than expected (GC pauses, scheduler delays, VM freezes, NTP jumps). Break either assumption, and a "leased" leader can serve a read after a new leader has already taken over elsewhere, a real linearizability violation, and a nasty one, because it fails silently instead of loudly.

This isn't just theoretical caution, production Raft implementations expose it as an explicit trade-off. etcd's Raft library, for example, ships two read modes: a quorum-confirmed mode that stays safe under any clock behavior (the default, and the one it recommends), and a separate lease-based mode, documented as vulnerable to serving stale data if clock drift is unbounded. Teams that want the latency win take it deliberately and opt-in, usually paired with conservative clock-drift assumptions, not as the out-of-the-box default.

13. Cluster Membership Changes: Joint Consensus

The problem. You can't have every server flip from an old configuration to a new one at the same instant, each one notices the change at a slightly different time. If servers switch one by one, there's a window where the cluster could split into two independent majorities: some servers still counting quorum under the old member list, others already counting it under the new one. Both groups could elect their own leader for the same term, a straightforward safety violation.

The fix: joint consensus. Raft introduces a transitional configuration, C_old,new, combining both member lists. While the cluster is in this state:

• Log entries replicate to every server in either configuration.

• A server from either configuration is eligible to become leader.

• Both elections and commitment require separate majorities — one from C_old and one from C_new at the same time.

That last rule closes the gap: there's never a moment where the old or new configuration alone can make a unilateral decision.

Walkthrough: S1 is leader, with S2 and S3 as followers (C_old = {S1, S2, S3}). An admin requests adding S4 and S5, giving C_new = {S1, S2, S3, S4, S5}.

• Phase 0: catch-up. S4 and S5 join as non-voting members. S1 starts sending them log entries like any follower, but they don't count toward any majority yet, for elections or for commitment. This avoids a window where two brand-new, empty servers would suddenly be required for quorum before they've even caught up on history.

• Phase 1: the joint entry. Once S4 and S5 are caught up, S1 appends a C_old,new entry to its log and replicates it. The instant any server even S4 or S5 sees this entry in its own log, it starts applying joint rules immediately, whether or not the entry is committed yet. S1 considers C_old,new committed once it's on a majority of C_old (2 of {S1,S2,S3}) and a majority of C_new (3 of {S1,S2,S3,S4,S5}).

  • If S1 crashes here before replicating C_old,new anywhere else: nobody else has seen it, so the resulting election just runs under plain C_old rules.

  • If S2 or S3 crashes here (after C_old,new is committed): watch the quorum math closely. Losing both S2 and S3 leaves only S1 from C_old — 1 of 3, not a majority, so the cluster halts, even if S1, S4, and S5 are all healthy (which is technically 3 of 5, a C_new majority on its own). Joint consensus deliberately requires both majorities together, so satisfying only the new config's quorum isn't enough by itself.

• Phase 2 — the final entry. Once C_old,new is committed, S1 appends a plain C_new entry and replicates it. This one only needs a majority of C_new (any 3 of the five) to commit. Once it does, C_old stops mattering entirely, and any server not in C_new can be safely shut down.

  • If the leader itself isn't part of C_new (say this reconfiguration also drops S1), it steps down to follower the moment it commits the C_new entry, since it's now coordinating a cluster it isn't even a member of.

Keeping removed servers from causing chaos. Once S2 or S3, say, are dropped from the configuration, they stop receiving heartbeats. Naturally, they time out and start requesting votes with an incremented term, which, left unchecked, would force the legitimate leader to see a higher term and step down needlessly, over and over. Raft's fix here is effectively a lease on trust: a server ignores incoming RequestVote RPCs if it has heard from a currently-active leader within the last minimum election timeout, regardless of the term number in the request. As long as the real leader keeps its heartbeats flowing to the rest of the cluster, a removed or partitioned server's vote requests just get quietly ignored.

14. Log Compaction: Snapshots and Copy-on-Write

An unbounded log is a real operational problem, more disk, and a much slower replay if a server ever has to restart and reprocess its whole history. Raft's answer is snapshotting: periodically write the entire current state machine state to stable storage, then discard every log entry the snapshot covers.

A snapshot carries a little metadata alongside the actual state: the last included index and last included term, the position and term of the final entry it replaces. These matter because the very next log entry after the snapshot still needs a valid prevLogIndex/prevLogTerm to pass the normal AppendEntries consistency check, even though the entry it's checking against no longer physically exists. The snapshot also carries the latest cluster configuration as of that index, so a membership-change entry doesn't vanish along with the log entries around it.

Snapshotting happens independently on each server, not coordinated by the leader, typically triggered by something simple like "the log has reached N bytes." This is a deliberate exception to Raft's strong-leader philosophy: since a snapshot only ever covers already-committed entries, there's no decision being made and therefore no conflict risk, so there's no need to route it through the leader at all.

The exception is a follower that's fallen too far behind, if the leader has already discarded (via its own snapshot) the exact entries that follower still needs, it can't just send more AppendEntries. Instead the leader uses a separate InstallSnapshot RPC, sending the snapshot itself in chunks (a byte offset per chunk, and a done flag on the final one, so the follower can reset its election timer between chunks instead of timing out mid-transfer). On receipt, the follower usually discards its entire existing log, it's superseded, unless the snapshot only covers a prefix of what it already has, in which case it keeps whatever comes after the snapshot's last included index.

Copy-on-write. Serializing an entire state machine to disk takes real time, and that shouldn't block new writes from being accepted in the meantime. Two common approaches: state machines built on immutable/functional data structures get this for free, since the old version stays valid while a new one is built alongside it. Otherwise, you lean on the OS, fork() on Linux gives you a child process with a copy-on-write view of the parent's entire memory at that exact instant. The child serializes that frozen view to disk while the parent keeps handling new commands, and pages only get duplicated as either side actually modifies them. The paper's own reference implementation uses exactly this fork-based approach.

15. Client Interaction and Linearizable Semantics

Finding the leader. A client starts by contacting a randomly chosen server. If that server isn't the leader, it rejects the request and, since every AppendEntries carries the leader's address, tells the client who to talk to instead. If the leader later crashes mid-request, the client's call just times out and it retries against another random server.

The duplicate-execution problem. Suppose the leader commits a command but crashes before responding to the client. The client, seeing no response, retries against the new leader, and without protection, that command now executes twice. The fix: clients tag every command with a unique, increasing serial number. Each state machine remembers the last serial number it processed per client, along with the result. A retry carrying an already-seen serial number just gets the cached result replayed back, no re-execution, making retries safely idempotent.

The stale-read problem and its solution. This is the same territory as the lease discussion above: a leader can't just answer reads from local memory without first proving, via the no-op-entry-at-term-start plus a per-read majority heartbeat, that it's still actually in charge. Skip that proof by trusting a time-based lease instead of a fresh confirmation, and you reintroduce exactly the failure mode Raft was built to avoid: a technically-deposed leader confidently handing back an answer that's already out of date, with no error and no warning, just quietly wrong data reaching a client that assumed linearizability. That's the real cost of the lease shortcut: it doesn't make the system wrong most of the time; it makes it wrong in a way that's very hard to notice until it already has been.

Where this leaves you

None of these mechanisms are individually exotic, majority quorums, a logical clock, randomized timers, a two-phase reconfiguration. What makes Raft worth studying isn't any single piece; it's how deliberately each one was chosen to keep the reasoning simple, even though the underlying problem, servers that crash, networks that lie about time, leaders that die mid-decisionvery much isn't.

If you want the primary source for any of this, it's all in the paper at raft.github.io/raft.pdf, including the formal TLA+ specification and the full safety proof this piece only summarized.