Course contents
On this page
Consensus and leadership — extended reference
Original detailed coverage and citations accompanying the focused consensus and leadership lesson.
This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.
Part 5: Correctness across machines
Prerequisites: Lesson 27 and the preceding foundations.
Learning outcomes
- Explain replicated-state-machine safety through terms, durable votes, log matching, and commitment.
- Trace a Raft election and distinguish leader selection, replication, commitment, and application.
- Explain fencing and membership changes without treating any reachable node as authoritative.
A majority must agree on a history, not just a leader name
A five-node cluster loses contact between two groups. Three nodes elect a new leader while the old leader remains alive with one follower. If both groups can acknowledge incompatible updates, the system no longer has one authoritative history. Preventing this requires durable protocol rules, not just a heartbeat timeout.
Consensus establishes agreement on decisions under a stated failure model. A replicated state machine uses an agreed sequence of commands or changes so replicas evolve consistently. The implementation must connect leader election, log replication, commitment, application, and reconfiguration.
State-machine replication
A state machine has a current state and a defined transition for each accepted command. Replicas beginning from equivalent state and applying the same deterministic transition sequence should reach equivalent state. Nondeterministic inputs such as time, randomness, and external results must be ordered or represented appropriately.
The log is the ordered input or effect history. A replica can have an entry without knowing it is committed, and can know it is committed before applying it. These positions must remain distinct. A client response claiming an effect should follow the protocol’s required commit and application boundary.
Exactly which data is replicated varies. Commands can be compact but require deterministic execution and compatible code. Replicated effects can avoid re-executing application logic but consume different bandwidth and couple to storage representation. Neither choice alone supplies consensus; the ordering and decision protocol is still necessary.
Raft terms and voting
Raft organizes leadership into terms. A server records the current term and voting information durably under the protocol. Candidates seek votes, and a majority is required to become leader. Election restrictions consider log freshness so a replacement does not casually discard committed history.
For five voters, a majority is three. The system can continue making decisions with two voters unavailable if communication and the protocol’s other assumptions permit progress. This does not mean any arbitrary three records are sufficient for recovery; their durable protocol state and log relationships matter.
Randomized timeouts help reduce repeated election collisions. Safety comes from voting and log rules, not the randomness itself. A paused old leader that resumes in an obsolete term must stop exercising authority when it learns of the newer term, and other participants reject its stale requests according to the protocol.
Log matching and conflict repair
A leader sends entries with information about the preceding log position and term. A follower verifies that its history matches at that boundary before accepting subsequent entries. If histories diverge, the protocol finds a common prefix and replaces conflicting uncommitted suffixes under its rules.
leader: ... [index 8, term 3] [index 9, term 5]
follower: ... [index 8, term 3] [index 9, term 4]The diagram shows a possible uncommitted suffix conflict. It is not permission to overwrite committed history arbitrarily. The election and commit rules ensure that a valid leader can reconcile suffixes while preserving already committed decisions.
Persistence must precede acknowledgments where the protocol relies on surviving crashes. A follower that replies before recording required state durably can later forget its promise or accepted entry, undermining the proof. Consensus logic and storage error handling are therefore inseparable.
Commitment and application
A leader determines commitment under the protocol’s quorum and term rules. Raft has an important restriction around committing entries from prior terms by replica counting; entries from the leader’s current term provide the relevant safe commitment progression. Simplified pseudocode that commits any entry merely because several machines hold it can be wrong.
After commitment, each replica applies entries in order to its state machine. Application can lag replication. A client may need to wait for the leader to apply its command before receiving a result. Operation identifiers prevent a retried command from applying the business effect twice even when the log contains repeated client attempts.
A command can be committed without its client receiving a response. That uncertain outcome remains after consensus has done its job. Consensus establishes the authoritative decision; it does not guarantee perfect response delivery to a disconnected client.
Strong reads and stale leaders
A leader that has not recently communicated with the relevant quorum can be obsolete without knowing it. Serving a supposedly current read from its local state may violate linearizability. A strong-read path needs evidence of valid authority and sufficient application progress under the chosen protocol.
Read-index or quorum-confirmation techniques can establish a safe boundary. Lease-based paths can reduce communication under explicit clock and timing assumptions. The implementation must not silently apply a lease optimization outside those assumptions.
Follower reads need their own freshness contract. Reading a committed but lagging state can be useful, but it is not automatically the same operation as reading the latest authoritative value. A database may expose both paths with different semantics and latency.
Snapshots and membership changes
A snapshot represents state through a known log position and associated configuration. Installing it allows an old follower to catch up without replaying the entire history. The subsequent log must begin at the correct boundary, and partial installation must not expose inconsistent state.
Membership changes alter majority sets. Raft’s joint-consensus approach uses overlapping configuration requirements during a transition. Other safe variants have their own rules. Replacing members by editing a list independently on each machine can create disjoint authorities.
Operational procedures must account for simultaneous failures and catch-up. Adding a node that is not ready to vote safely can reduce availability or complicate recovery. Removing a voter while already degraded changes the remaining failure tolerance. Configuration automation should be treated as protocol execution.
Paxos as another agreement formulation
Paxos explains agreement through proposals, promises, and accepted values under ballot ordering. Multi-Paxos extends the basic agreement pattern to a sequence with leadership-related optimizations. Its terminology differs from Raft, but both families rely on overlapping decision sets and durable restrictions on what participants can later accept.
The course does not present a few lines of pseudocode as a complete implementation of either protocol. Correct consensus code needs careful treatment of persistence, retries, duplicate messages, reconfiguration, snapshots, and shutdown. The purpose of studying the mechanisms is to understand the invariant preserved at each step and the failure that step prevents.
A concrete election preserves committed history
Take five voters A through E. In term 4, leader A replicates entry 12 to A, B, and C and commits it under the protocol’s rules. A and B then become isolated. C, D, and E can form a majority, but D and E are missing entry 12. An election must not permit a stale candidate to win by treating all reachable nodes as interchangeable.
Raft’s vote rule compares the candidate’s last-log term and index with the voter’s own log. C refuses an insufficiently up-to-date candidate. A candidate able to obtain the required majority must satisfy the election restrictions, which preserve the relevant committed prefix together with the other protocol rules. The reasoning depends on durable voting state and quorum intersection, not merely on who sent a heartbeat most recently.
A voter records its term and vote before replying when that persistence is required by the protocol. If it votes for C, crashes, forgets the vote, and votes for D in the same term, two candidates could collect incompatible evidence. Persist-before-response ordering is part of consensus safety, just as log-before-page ordering is part of crash safety.
When A resumes, it may still believe it is leader in term 4. It cannot commit new entries without the necessary majority. Peers observing a higher term cause the required state transition. External side effects still require fencing at their own resource boundary: a replicated log cannot prevent an obsolete process from writing to an unrelated service that ignores authority.
Why a prior-term majority is not enough in Raft
A subtle Raft rule limits how a leader advances commitIndex by counting replicas. The leader can directly establish commitment for an entry from its current term once the required majority contains it. Committing that entry also commits the preceding log prefix. It must not simply choose any old-term entry that currently appears on a majority and assume the same reasoning applies.
The counterexample involves an older entry appearing on a majority while a different candidate has a later log term that can still win under election rules and replace the uncommitted suffix. The paper’s restrictions align election freshness with safe commitment. A current-term entry anchors the prefix in a way the proof can preserve through future elections.
advance_commit(candidate_index):
require log[candidate_index].term == current_term
require majority_match_index_at_least(candidate_index)
commit_index = max(commit_index, candidate_index)
apply_committed_prefix_in_order()This sketch isolates the leader’s direct majority-counting rule for a fixed configuration. It omits membership transitions, persistent state, message handling, application errors, and many implementation details. Followers can learn commit progress through the protocol without individually performing this leader calculation. Treating the sketch as a complete library would be unsafe.
A newly elected leader commonly establishes current-term progress before using optimized strong-read paths. Otherwise it may not yet know the full committed prefix it must expose. This is another example of why “I won the election” and “I can answer a current read immediately” are different claims.
Log matching is a prefix invariant
Each entry carries an index and term. Append requests identify the preceding entry expected by the leader. If a follower does not match that boundary, it rejects or follows the protocol’s conflict-repair path. Once the boundary matches, the leader can extend the shared prefix and remove conflicting uncommitted suffixes as specified.
The leader must not truncate a follower merely because an empty heartbeat lacks entries. Truncation is associated with a genuine conflict at relevant positions, not a blanket deletion of everything beyond a heartbeat’s previous index. Message reordering and retries can deliver older append requests after newer progress, so handlers must preserve monotonic safety despite delayed traffic.
A follower can persist entries before learning that they are committed. On restart, those entries remain candidates in its log, not automatically accepted state-machine effects. Commitment evidence and applied state must be reconstructed or learned consistently. Applying uncommitted suffixes to authoritative state without a rollback/visibility protocol would break state-machine replication.
The log-matching property concerns identical entries at a matching index and term and the shared prefix implied by the protocol. It does not mean every node always has the same log. Followers can legitimately lag or carry different uncommitted tails. Consensus preserves one committed history while allowing temporary physical differences.
Separate commit, apply, and response
Suppose an entry reaches a majority and becomes committed, but the leader’s application thread is busy. The replicated decision exists, while its effect is not yet visible in the state machine. A read that needs the new effect waits until appliedIndex reaches the appropriate boundary. Exposing commitIndex as though it were application progress can return stale state.
A client result can depend on execution output, such as the allocated order identifier or whether a conditional update succeeded. The leader may need to apply the command before constructing that result. If the command itself is interpreted against state, replicas must produce compatible results under deterministic execution and version assumptions.
After application, the response can still be lost. The client retries its request through another leader. A replicated deduplication table containing client identity, sequence, and prior result can avoid repeating the logical effect. The deduplication update belongs to the same deterministic transition or transactional boundary as the effect it protects.
Bounded retention is again part of the contract. If sequence state is discarded while very old retries remain allowed, the same request can be applied anew. A system can reject obsolete sequence ranges explicitly, retain them for the maximum retry horizon, or use another durable identity policy. Consensus orders duplicate commands; application semantics decide whether they produce duplicate effects.
A strong read needs authority and an applied boundary
A local process cannot establish current leadership merely by checking its role variable. It may be partitioned from a newly elected majority. A safe quorum-confirmed read path obtains evidence that the leader still has authority for the relevant term and establishes a read index. It then waits until local application reaches that index before reading state.
The exact protocol must also account for current-term commitment and message context. Delayed heartbeat replies from an earlier read cannot blindly authorize a later one. The evidence must correspond to the read’s safety boundary and current leadership state. A read-index implementation is a distributed protocol rather than a local timestamp check.
A lease can avoid per-read communication while its validity assumptions hold. The old holder must stop treating itself as authoritative before another holder can legitimately act. Clock drift, pauses, and how lease intervals are measured affect that proof. Using ordinary wall-clock timestamps without bounded assumptions is not sufficient.
Follower reads can be useful at a known historical or bounded-staleness point. A follower might also obtain an authoritative read index and wait until it applies through it. These modes have different latency and availability behavior. The API should expose the requested freshness rather than silently choose a stale path when quorum confirmation is inconvenient.
Membership changes preserve overlap across time
For a fixed five-node group, every majority has three members and intersects every other majority. Replacing the membership can destroy that fact. An old majority drawn from A through E and a new majority drawn from F through J can be disjoint, allowing incompatible histories if both configurations act independently.
A safe transition establishes a period or protocol in which decisions meet the required overlapping configuration constraints. Raft’s joint-consensus description requires majorities of both old and new configurations during the joint phase. Other restricted one-at-a-time change protocols have different rules. The operator must follow the protocol actually implemented rather than combine convenient fragments.
New members should catch up sufficiently before becoming essential voters. Otherwise adding a node can reduce progress by increasing the required quorum while the node is not ready. Removing a failed voter can also require a valid existing quorum; an operator cannot bypass safety by declaring the unreachable members absent independently on each surviving machine.
Emergency recovery after losing quorum may deliberately choose one history and reinitialize a group, but that is a different operational contract with data-loss risks. It should not be described as ordinary consensus failover. Preserving a distinction between safe protocol reconfiguration and disaster recovery is essential for honest availability claims.
Snapshots compact history without erasing its meaning
A snapshot includes state through a known log index and term, along with relevant configuration and application metadata. After installation, entries through that boundary need not remain in the active log. Future append consistency checks still need enough boundary information to align the retained suffix.
Snapshot transfer can be chunked, retried, and interrupted. The receiver should not expose a half-installed snapshot as authoritative state. It can write a new generation, verify completeness and integrity, publish it through a recovery-safe boundary, and retain the old state until replacement is valid. The exact mechanism depends on the storage engine.
Application metadata includes deduplication state if it is necessary to preserve retry semantics. Copying rows while omitting the client sequence table can restore visible data but allow old commands to execute again. A snapshot is a complete logical recovery artifact, not merely the largest table’s bytes.
Consensus has resource costs and bounded failure tolerance
For five voters, at least three are required for ordinary majority decisions, so two can be unavailable while progress remains possible under suitable timing. Losing three prevents progress, but safety can still hold. Adding voters increases tolerance only as majority arithmetic and placement permit; it also increases replication traffic and operational complexity.
Latency depends on which voters form the successful majority, their storage persistence, and the leader’s own processing. If one fast local majority survives, a distant slow follower may not dominate every commit. If surviving failure domains force a distant vote, the WAN becomes part of the required path. Quorum count alone cannot predict milliseconds.
Many databases run numerous consensus groups to distribute ownership. That introduces per-group logs, heartbeats, elections, scheduling, and metadata. A million tiny groups can create substantial background overhead even when each group receives little traffic. Group granularity balances independent placement and scaling against protocol bookkeeping.
What consensus does not provide
Consensus can agree on a sequence of commands but does not automatically make the command logic correct. An agreed command that creates an unauthorized sword is consistently wrong. Multi-key transactions, query isolation, authorization, backup, and overload control require additional layers.
Paxos and Raft explain ways to preserve agreement under stated failure assumptions. Their practical value lies in the constraints they impose before a node can promise, accept, commit, or apply. Database architecture then composes those constraints with storage and transaction semantics. The composition is the difficult engineering work that a diagram labeled “uses consensus” often hides.
Read a five-replica log state
committed prefix | uncommitted suffix
A, old leader: [1:t1][2:t1][3:t2] | [4:t2]
B: [1:t1][2:t1][3:t2] | [4:t2]
C: [1:t1][2:t1][3:t2] |
D: [1:t1][2:t1] |
E: [1:t1][2:t1] |Assume entry 3 was committed in term 2 under valid protocol rules, and entry 4 reached only A and B. After A and B become isolated, C is the up-to-date candidate in the remaining majority. The valid election path preserves entry 3. Entry 4 lacks a committed outcome in this example and may be replaced after a future leadership change. The drawing labels that assumption explicitly because physical replica count alone cannot reveal all prior commitment evidence.
Once C establishes a new term and commits a current-term entry through its majority, followers apply the committed sequence. D and E first catch up on missing history. A and B can later rejoin and replace conflicting uncommitted suffixes according to the protocol. No step permits overwriting entry 3 simply because another leader is newer.
Define the unit of agreement before scaling it
One consensus group can protect a shard, a metadata range, or a transaction-decision record. A database with thousands of groups can execute independent ownership domains concurrently while each group preserves its own order. Cross-group transactions still require an additional protocol to relate those orders.
This distinction explains why “uses consensus” does not predict a database-wide throughput ceiling or a global transaction guarantee. The size and placement of each agreement unit, its workload, and its composition with transaction coordination determine the actual architecture. Small local groups can make tenant-local work efficient, while globally shared metadata or invariants can remain bottlenecks.
A correct implementation makes these boundaries observable through term, commit, apply, and configuration metrics, so operators can distinguish slow progress from unsafe authority.
Case analysis and design conclusion
The Raft extended paper and Paxos Made Simple are primary sources for these mechanisms. Their safety arguments are more important than memorizing message names. A production database can layer transaction coordination, storage, and routing above consensus, so consensus alone does not establish every SQL-level guarantee.
A complete design identifies the unit of agreement, durable participant state, commit rule, read authority, application order, and membership transition. Lesson 29 divides the dataset into multiple ownership domains, introducing the question of how many such agreement groups or partition owners are needed and how clients find them.