How Raft Works: Leader Election, Replicated Logs, and Majority Quorums

A replicated database, a Kubernetes control plane, and a coordination service all need the same guarantee: after a machine dies, the survivors still agree on what already happened.

Agreement is not the same problem as placing a key on a hash ring. Placement answers which node owns this key. Consensus answers which history is the history. If two replicas apply different writes in different orders, clients see forks. Raft is a protocol that elects one writer at a time and replicates a single ordered log until a majority of servers have the same prefix.

This article is about that protocol: terms, votes, AppendEntries, commit index, and the election restriction that keeps committed entries from disappearing. It is not a second tour of consistent hashing or of SQL versus NoSQL data models.

The contract

Raft implements a replicated state machine. Each server keeps a persistent log of commands tagged with an index and a term, a state machine that applies committed commands in index order, and persistent metadata: current term and who it voted for in that term.

Clients send commands to the leader. The cluster promises election safety (at most one leader per term), leader append-only logs, log matching (same index and term implies identical prefixes), leader completeness (a committed entry is present on every later leader), and state-machine safety (an applied index never receives a different command elsewhere).

Availability is separate: a majority must be reachable. A five-node cluster survives two failures. A four-node cluster still only survives one, because a majority of four is three.

Roles and terms

A server is a follower (answers RPCs, applies committed entries), a candidate (only during an election), or a leader (the only server that accepts client writes and appends new entries). Leaders send heartbeats so followers do not start elections.

Time is divided into terms, monotonically increasing integers. A term begins with an election and contains at most one leader if the election succeeds. Seeing a higher term is an order to step down. Terms are a logical clock; they make stale leaders detectable without synchronized wall clocks.

Leader election

Followers expect periodic AppendEntries messages. An empty AppendEntries is a heartbeat. Each follower draws a random election timeout, typically in a 150–300 ms window in the original description, and resets it on a valid heartbeat or granted vote.

If the timeout fires, the follower increments currentTerm, becomes a candidate, votes for itself, persists votedFor, and sends RequestVote RPCs in parallel.

A voter grants the vote only if the candidate’s term is high enough, the voter has not already voted for someone else in that term, and the candidate’s log is at least as up-to-date as the voter’s. Up-to-date is not length alone: a higher last-entry term wins; if last-entry terms are equal, the longer log wins.

That election restriction carries committed history forward. A candidate missing a committed prefix cannot collect a majority, because at least one member of any majority already has that prefix and will refuse the vote.

Outcomes: a majority of votes (including the candidate) makes a leader, who heartbeats immediately; a higher-term leader or RPC forces the candidate back to follower; a split vote expires and retries with a new term. Randomized timeouts make simultaneous retries uncommon. Two nodes in a minority partition cannot elect a leader, so they cannot accept writes the majority would later overwrite.

Log replication

The leader assigns indices. It appends (index, currentTerm, command), then sends AppendEntries including the previous index and term, the new entries, the leader term, and the commit index. A follower accepts only if its log matches at that previous index and term. On rejection the leader decrements the per-follower next-index and retries an earlier prefix until the logs line up, then ships the suffix.

When the new entry is stored on a majority and belongs to the leader’s current term, the leader advances commitIndex, applies through that index, and returns success. Followers apply when later messages carry the new commit index.

The previous-index check maintains log matching incrementally. Same index and term means the histories up to that point are identical.

A compact example

Index     1     2     3     4     5
Leader   [1]   [1]   [2]   [2]   [3]
S2       [1]   [1]   [2]   [2]
S3       [1]   [1]   [2]
S4       [1]   [1]
S5       [1]   [1]   [2]   [2]   [3]

The term-3 leader has appended index 5. After S2 or S5 stores it, a majority has the entry. The leader commits index 5 and, by log matching, every earlier index. S4 is repaired by walking next-index backward, then shipping 3–5. S4 never invents entries.

Why previous-term entries are not committed by counting

A new leader may inherit uncommitted entries from an older term. Those entries can later sit on a majority. Raft still refuses to mark them committed by replica count alone. An entry from term 2 can be on a majority and still be overwritten if a different candidate, whose log never contained that entry, wins the next election before any current-term entry is committed. Only an entry from the leader’s current term may be committed by counting replicas. Once such an entry commits, log matching commits every preceding index with it. Many implementations append a no-op in the new term immediately so that inherited prefix can commit.

Persistence

Before a server replies to RequestVote or AppendEntries it must have recorded currentTerm, votedFor, and accepted log entries on stable storage. commitIndex, lastApplied, and the leader’s next-index and match-index tables are volatile. Acknowledging a vote or append and then losing that disk write can break election safety or log matching.

Membership changes

The basic protocol assumes a fixed set. Joint consensus moves through a transitional configuration C_old,new that needs a majority of the old set and a majority of the new set. Only after that configuration commits does the cluster use C_new alone. One-server-at-a-time changes, used by etcd and others, keep consecutive majorities overlapping so two leaders cannot appear in one term.

What Raft is not

Raft does not place keys. Consistent hashing can choose a shard; Raft inside the shard replicates that shard’s log. Raft does not make a single disk durable: quorum is a count of servers. It does not linearize reads by default; a stale leader can serve old state unless the implementation uses a read-index/quorum read or a carefully bounded lease. Multi-Raft runs many independent groups, one per range. That is a scaling pattern, not a different algorithm.

Where this shows up

• etcd and the Kubernetes API server’s backing store
• Consul’s catalog and sessions
• MongoDB replica-set elections after the protocol change
• CockroachDB, TiKV, and other range-partitioned stores
• Log devices and queue controllers that need one committed offset

A single process writing a local file does not need Raft. Two live writers whose clients cannot tolerate forks do.

Misconceptions

The leader is a single point of failure. It is a single point of coordination. When it dies, a majority elects another. Writes pause for an election timeout plus about one RTT.

Majority means more than half of the original machines after disks vanish. Majority is of the current configuration. Silently redefining it after a crash is how split-brain starts.

A longer log is always more up-to-date. A longer log with an older last term loses to a shorter log whose last entry has a newer term.

Followers apply an entry as soon as they store it. They wait for commitIndex. Applying early would expose a command a later leader might still overwrite.

Paxos and Raft solve different problems. They target the same problem. Raft constrains the solution so implementations are easier to follow.

Takeaways

Raft splits consensus into electing one leader per term, replicating one log from that leader, and refusing to elect anyone whose log could be missing a committed prefix. Majority is the unit of election and of commit. Current-term entries are the only ones committed by counting replicas; older entries ride along once a current-term entry commits. Heartbeats are empty AppendEntries. Randomized timeouts exist to break split votes.

If you already know how a cluster maps keys onto nodes, Raft is the piece that keeps those nodes from disagreeing about the writes they accepted.

Related reading on this site: How Consistent Hashing Works, SQL vs NoSQL Explained, and How Databases Work Internally.