Consensus and leader election

The problem it solves

A payouts service sends a batch of transfers to the bank every second. It must run on exactly one machine: two copies would send every batch twice. So there are two instances, A and B, and each pings the other once a second. If B hears nothing from A for 5 seconds, B takes over.

Then the switch between them drops packets for 40 seconds. Both machines are healthy and both can reach the bank. A hears nothing from B, so A keeps going. B hears nothing from A, so B takes over. For 35 seconds both send, and 35 batches go out twice.

This is split brain, and no timeout fixes it. From inside one machine, “the other node crashed” and “the network between us broke” look identical. So any rule a node applies, using only what it can see, gives two leaders whenever the two sides see different things. The same problem appears wherever several machines must hold one answer:

What must be agreed	Example	What two answers cost
Who leads	The primary database, the active scheduler, the sequencer	Two writers, double side effects
The order of writes	The metadata log of a Kafka or Kubernetes cluster	Replicas that diverge
Who holds a lock or owns a shard	One owner per document, per city, per partition	Two owners writing the same data
Who is in the cluster	Adding or removing a replica	Two groups that each think they are a majority

Consensus is the general fix. A group of nodes agrees on a value, or a sequence of values. Every node that decides gets the same answer. And the group keeps deciding while a majority is up and can talk.

Agree on a sequence of commands, and you have a replicated log. Feed it to the same deterministic code on every node, and you have a replicated state machine. That’s three or five copies of a lock table or config map, behaving like one machine that never crashes.

Few teams write a consensus implementation. Almost everyone depends on one: etcd under Kubernetes, or the Raft groups inside CockroachDB.

How it works

Step 1: Majorities, so two decisions always overlap

The fix for split brain is to stop letting a node decide alone. A node may act only with the agreement of a majority (a quorum) of a fixed group. Any two majorities of the same group share at least one member. So two conflicting decisions can never both collect a majority. The shared member would have to agree to both, and it refuses the second.

A partition: only the side with a majority can decide

Scroll or pinch to zoom, drag to pan

• Color key
• Cut off, cannot decide
• Majority, keeps working

To survive f failed or unreachable nodes, you need 2f + 1. So 3 nodes survive 1 failure, and 5 survive 2. Above, the 3-node side keeps working, and the 2-node side stops. That is the price: the minority is unavailable, as CAP predicts for a consistent system. It’s also the point. The 2-node side knows it is a minority, so it never acts as if it leads.

So the payouts job cannot be fixed with two nodes. It needs a third voter: a third instance, a small witness, or a lock in a coordination service that is itself 3 or 5 nodes.

Step 2: What consensus promises, and what it cannot

• Safety, always. No two nodes decide differently. A committed entry is never lost or changed. And no term has two leaders. This holds through any crashes, restarts, lost or reordered messages, and partitions.
• Liveness, only when the network behaves. The cluster elects leaders and commits writes only while a majority is up, and messages arrive within some bound, for long enough.

The gap is not a weakness of one protocol. The FLP result (Fischer, Lynch and Paterson, 1985) proves it. Picture a fully asynchronous network, where a message can take any finite time. There, no deterministic protocol can guarantee that it always reaches a decision, if even one node may crash. That’s because a slow node and a dead node cannot be told apart. FLP rules out guaranteed termination, not safety.

Real protocols assume partial synchrony instead. The network may misbehave for a while, but eventually messages arrive within a bound. During the bad period, they stall. They never lie. Timeouts restore progress. They never decide what is true.

Nodes are assumed to fail by stopping, not by lying. Tolerating lying (Byzantine) nodes takes 3f + 1 nodes, and protocols such as PBFT.

Step 3: Raft elects a leader per term

Raft (Ongaro and Ousterhout, 2014) was designed to be understandable, and it has become the default. etcd, Consul, CockroachDB, TiKV and Kafka’s KRaft use it. MongoDB’s replication protocol is derived from it.

Time is divided into numbered terms. Each starts with an election, and has at most one leader. Every message carries the sender’s term. A node that sees a higher term adopts it, and becomes a follower, even if it was leader. A message with a lower term is rejected. The term is the epoch from the replication page: a fencing token built into the protocol.

Raft roles

Scroll or pinch to zoom, drag to pan

• Color key
• State

A follower that hears no heartbeat within its election timeout becomes a candidate. It increments its term, votes for itself, and sends RequestVote to every other node. Each node grants at most one vote per term, first come first served. It writes the vote to disk before replying, since a node that forgot its vote on restart could vote twice. A candidate with a majority becomes leader. It sends heartbeats (empty AppendEntries messages) that reset every follower’s timer.

If two candidates split the vote, nobody wins, and both retry in a higher term. Randomized election timeouts make that rare. Each node picks its timeout from a range, 150 to 300 ms in the paper. So one node usually times out first, and wins before the others wake. etcd defaults to a 100 ms heartbeat and a 1,000 ms election timeout. The paper’s rule of thumb is broadcast time << election timeout << mean time between failures. A timeout close to a round trip plus a disk write causes elections nobody needed.

Step 4: The leader replicates a log

Only the leader accepts writes. Each write becomes a log entry, holding the command, its term, and its index (position in the log). The leader appends it locally, and sends it to every follower in an AppendEntries message.

One write through a five-node Raft group

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database

An entry from the leader’s current term is committed once it is stored on a majority. (Step 5 covers older entries.) A committed entry will never be lost or changed. So the leader applies it, and answers the client. Followers learn the new commit index from the next AppendEntries. A write costs one round trip to the fastest majority, plus a disk flush on each. The slowest nodes do not matter.

Every AppendEntries also carries the index and term of the entry just before the new ones (prevLogIndex, prevLogTerm). A follower accepts only if its own log has that entry. If not, it refuses. The leader retries one step further back, until the logs agree. Then it overwrites everything the follower has after that point.

This gives the Log Matching Property. If two logs hold an entry with the same index and term, they are identical up to that entry. Followers never decide anything. They copy the leader, and drop what it lacks. That is safe only because of two rules.

Step 5: Two rules that make it safe

Rule 1: vote only for a candidate whose log is at least as up to date as yours. In RequestVote, the candidate sends the index and term of its last entry. A voter refuses if its own last entry has a higher term, or the same term and a higher index.

Here’s why that works. A committed entry is on a majority. A winning candidate has votes from a majority. The two majorities share a node. That node refused anyone missing the entry. So every elected leader already holds every committed entry. This is called Leader Completeness.

Rule 2: a leader commits only entries from its current term by counting copies. A majority of copies is not enough for an entry left over from an earlier term. Figure 8 of the Raft paper shows why:

1. A term 2 leader copies an entry to a minority, and crashes.
2. A term 3 leader writes a different entry at that index, and crashes.
3. The first node returns, wins term 4, and copies its old entry to a majority.

Say that entry were now treated as committed. The term 3 node could still win an election, because its last entry is from a later term. And it would overwrite the entry. So a new leader appends an entry of its own term, usually a no-op. Only that entry commits by counting. Everything before it then commits too, by Log Matching.

Both rules are a few lines:

JRaftNode.javaPyraft_node.pyC#RaftNode.csGoraft_node.goTSraft-node.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

record Entry(int term, String command) {}

record VoteReply(int term, boolean granted) {}

// The two rules that make Raft safe, on one node. Everything else in Raft (heartbeats, retries,
// snapshots) exists to make these two checks reachable.
class RaftNode {
    final String id;
    // currentTerm, votedFor and log must be on disk before any reply is sent. A node that forgets
    // its vote after a restart can vote twice in one term and elect two leaders.
    int currentTerm;
    String votedFor = null;
    final List<Entry> log; // index 1 is log.get(0)
    int commitIndex = 0;

    RaftNode(String id, int currentTerm, List<Entry> log) {
        this.id = id;
        this.currentTerm = currentTerm;
        this.log = new ArrayList<>(log);
    }

    int lastIndex() {
        return log.size();
    }

    int termAt(int index) {
        return index == 0 ? 0 : log.get(index - 1).term();
    }

    // Rule 1: a vote goes to at most one candidate per term, and only to one whose log is at
    // least as up to date as ours. Every committed entry is on a majority, every winner has a
    // majority of votes, the two majorities overlap, so every winner holds every committed entry.
    VoteReply handleRequestVote(int term, String candidate, int lastLogIndex, int lastLogTerm) {
        if (term < currentTerm) return new VoteReply(currentTerm, false); // an old-term candidate
        if (term > currentTerm) {
            currentTerm = term; // a newer term ends our old vote
            votedFor = null;
        }
        int myLastTerm = termAt(lastIndex());
        boolean upToDate = lastLogTerm > myLastTerm
                || (lastLogTerm == myLastTerm && lastLogIndex >= lastIndex());
        if ((votedFor == null || votedFor.equals(candidate)) && upToDate) {
            votedFor = candidate; // a real node also restarts its election timer here
            return new VoteReply(currentTerm, true);
        }
        return new VoteReply(currentTerm, false);
    }

    // Rule 2, on the leader: an entry is committed when a majority holds it AND it is from the
    // leader's current term. Older entries commit only behind a current one. Counting copies of
    // an old-term entry is the bug in Figure 8 of the Raft paper: it can still be overwritten.
    int advanceCommitIndex(int[] matchIndex) {
        // matchIndex has one slot per voter, the leader's own last index included.
        int[] ranked = matchIndex.clone();
        Arrays.sort(ranked); // ascending
        int onMajority = ranked[(ranked.length - 1) / 2]; // the highest index a majority holds
        if (onMajority > commitIndex && termAt(onMajority) == currentTerm) {
            commitIndex = onMajority;
        }
        return commitIndex;
    }
}

class Main {
    public static void main(String[] args) {
        // A follower in term 2 whose log ends with an entry from term 2.
        RaftNode a = new RaftNode("A", 2,
                List.of(new Entry(1, "x=1"), new Entry(1, "x=2"), new Entry(2, "x=3")));
        System.out.println(a.handleRequestVote(3, "B", 3, 1)); // false: B's last entry is term 1
        System.out.println(a.handleRequestVote(3, "C", 3, 2)); // true: as up to date as A
        System.out.println(a.handleRequestVote(3, "D", 4, 2)); // false: A already voted in term 3

        // A leader of term 4 holds index 3 from term 2, and 3 of 5 nodes now have it.
        RaftNode leader = new RaftNode("L", 4,
                List.of(new Entry(1, "x=1"), new Entry(2, "x=2"), new Entry(2, "x=3")));
        leader.commitIndex = 1;
        System.out.println(leader.advanceCommitIndex(new int[] {3, 3, 3, 1, 1})); // 1: older term

        // The leader appends its own entry; once a majority has index 4, 3 commits with it.
        leader.log.add(new Entry(4, "no-op"));
        System.out.println(leader.advanceCommitIndex(new int[] {4, 4, 4, 1, 1})); // 4
    }
}

Now watch it run. The ring around each node is its election timer. Dots are messages.

1. Wait for a leader (blue), select it and Write a few times. Solid cells are committed.
2. Press Split 2 | 3 and write through the cut-off leader: the entry stays dashed (2 of 5).
3. The other side elects a leader in a higher term. Write through it: it commits.
4. Read from the old leader with Local reads: a stale value. With ReadIndex it refuses.
5. Press Connected: the old leader steps down and drops its uncommitted entries.
6. Pick Fixed timeouts and crash the leader: the followers split the vote forever.

ConnectedSplit 2 | 3

Random timeoutsFixed

Local readsReadIndex

• vote request
• vote
• AppendEntries
• reply

S1S2S3S4S5

Write via S1Read S1Crash S1

Leaders

none

Highest term

0

Committed

0

Elections

0

PauseReset

Nobody leads yet. Watch the timer rings: the first follower to time out asks for votes.

Time runs about 20 times slower than a real cluster: heartbeats every 0.9 s here, about 50 to 100 ms in etcd; election timeouts of 2.5 to 5 s here, 150 to 300 ms in the Raft paper and about 1 s in etcd. Solid log cells are committed on that node, dashed ones are not yet.

The minority leader in step 2 never told the client the write failed. The client timed out. Clients must treat a timeout as “unknown”, and retry with an idempotency key.

Step 6: Reads that do not lie

Writes go through the log, so they are linearizable. Reads are where systems quietly break the guarantee. A leader answering from memory may have been replaced without knowing it, as step 4 of the demo shows.

A deposed leader serves a stale read

Scroll or pinch to zoom, drag to pan

• Color key
• Database

Client 2 finished writing x = 8 before client 1 asked, and client 1 got 7. For a lock service, that means two clients told they hold the same lock. The fixes:

• Read through the log. Append the read as an entry and answer once it commits. Correct, and as expensive as a write.
• ReadIndex. The leader records its commit index. It sends one round of heartbeats, and waits for a majority to answer. If they do, no newer leader existed at that moment. So it answers once it has applied up to the recorded index. That’s one round trip, with no disk write, shared by many reads. A new leader must first commit its no-op from step 5. This is etcd’s default. The consistency models page draws the flow.
• Lease read. Followers do not elect a new leader until an election timeout has passed since they last heard from the current one. So the leader can answer locally, for a lease somewhat shorter than that. The lease counts from when it sent a heartbeat that a majority acknowledged. No synchronized clocks are needed. But clock rates must stay within a bounded drift. And a leader that pauses mid-check can still serve past its lease.
• Follower read. A follower asks the leader for a read index. It waits until it has applied that far, then answers. That’s linearizable, with the load spread out. A follower that answers from its own state without asking gives a stale read. Examples are etcd’s “serializable” reads, ZooKeeper’s default, and Consul’s stale mode.

Step 7: Snapshots keep the log finite

A log grows forever, and a restarting node would replay all of it. So each node now and then writes a snapshot of its state machine at some index, and deletes the log up to it. etcd does so every --snapshot-count entries.

A follower that needs entries the leader has discarded gets the snapshot instead (InstallSnapshot). A 4 GB state machine over a 1 Gbit/s link takes over 30 seconds to send. And the leader is also serving clients meanwhile. That’s one reason coordination stores keep their data small.

Step 8: Changing who votes

Adding or replacing nodes changes what “a majority” means. Nodes switch configuration at different moments, so for a while two disjoint majorities can exist.

Growing from 3 to 5 voters in one step can elect two leaders

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database
• Failure

Raft offers two safe ways:

• Joint consensus. The leader first commits a combined configuration, C(old, new). In it, every decision needs a majority of the old set and a majority of the new set. Once that commits, it commits C(new). There’s no moment when either set can decide alone.
• One server at a time. Add or remove a single node per change. Any majority of 3 nodes and any majority of 4 nodes share a member (2 + 3 > 4). So an old-config majority and a new-config majority always overlap. Going from 3 to 5 takes two changes. It’s simpler, and it’s what etcd’s membership API does.

Either way, a new node should first join as a learner. It receives the log, but doesn’t vote. Here’s why. Add an empty voter to 3 nodes, and you get 4 nodes needing 3 acks. But the newcomer can ack nothing until it has copied the whole log. So the cluster briefly survives zero failures. etcd added learners in 3.4.

Go deeperThe single-server change bug, and other membership details2 min

In 2015, Diego Ongaro reported a bug in the single-server change algorithm from his own thesis. Say leaders change while back-to-back membership changes are in flight. Then an old and a new configuration can fail to overlap, and an entry already committed can be overwritten. The fix is one rule. A new leader must commit an entry from its own term (the same no-op from step 5) before it starts a membership change. Implementations written before then needed patching.

Other details that matter in practice:

• The configuration is itself a log entry. A node uses the newest configuration in its log as soon as it appends it, without waiting for it to commit.
• A leader removed from the configuration finishes committing that change, then steps down.
• Removed nodes no longer get heartbeats, time out, and send RequestVote with ever higher terms, which would disrupt the cluster. Raft’s fix: a node that has heard from a current leader within the minimum election timeout ignores RequestVote messages.
• Replacing a dead node is remove first, then add. So the cluster never temporarily needs a majority of a larger set that includes the dead node.

Step 9: Leader election as a service

Most systems do not embed Raft. They need one active scheduler, or one owner per shard. They get it from a coordination service that runs consensus for them: etcd, ZooKeeper or Consul.

ZooKeeper uses ephemeral sequential znodes. Each candidate creates /election/candidate- with both flags, and gets a name such as candidate-0000000017. The lowest number leads. Each other candidate watches only the node just below its own. So a leader’s death wakes one candidate, not a herd. Ephemeral nodes vanish when the client’s session expires. So the session timeout (2 to 20 times the 2 second tickTime) is the lease.

etcd uses a lease with a TTL, kept alive by the client. A transaction creates the election key on that lease, only if the key does not exist (its create revision is 0). If renewals stop, the lease expires, and the key is deleted. etcd raises the key’s revision on every write, so it is a natural fencing token. Kubernetes controllers do the same with Lease objects. They use 15 second leases, renewed within 10 seconds, and retried every 2.

The loop each candidate runs is short. What matters is the stop-early margin and measuring from when the renewal was sent:

JElector.javaPyelector.pyC#Elector.csGoelector.goTSelector.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.Objects;

// Stands in for etcd or ZooKeeper: a key with an owner, an expiry and a revision. The real store
// is itself a Raft group, which is what makes compare-and-set on it safe.
class LeaseStore {
    private String owner = null;
    private double expiresAt = 0;
    private long revision = 0;

    // Create the key only if nobody holds it, as an etcd transaction comparing the key's create
    // revision with 0 does. The new revision doubles as the fencing token. Returns 0 on failure.
    long tryAcquire(String who, double ttl, double now) {
        if (owner != null && now < expiresAt) return 0;
        owner = who;
        expiresAt = now + ttl;
        return ++revision;
    }

    boolean renew(String who, long token, double ttl, double now) {
        if (!Objects.equals(owner, who) || revision != token || now >= expiresAt) {
            return false; // the lease ran out, or someone else holds it now
        }
        expiresAt = now + ttl;
        return true;
    }
}

class Elector {
    static final double TTL = 10; // seconds the store keeps the lease without a renewal
    static final double RENEW_EVERY = 3; // renew well inside the TTL, so one lost request is not fatal
    static final double MARGIN = 2; // assume we lost the lease this long before the store expires it

    final String name;
    private final LeaseStore store;
    long token = 0; // 0 means not leading
    private double deadline = 0; // local monotonic time after which we must not act as leader
    private double nextRenew = 0;

    Elector(String name, LeaseStore store) {
        this.name = name;
        this.store = store;
    }

    // Called in a loop. `now` is a monotonic clock: wall-clock jumps must not extend a lease.
    void tick(double now) {
        if (token == 0) {
            token = store.tryAcquire(name, TTL, now);
            if (token != 0) extend(now);
        } else if (now >= deadline) {
            token = 0; // stop first, before the store hands the lease to someone else
        } else if (now >= nextRenew) {
            if (store.renew(name, token, TTL, now)) extend(now);
            else token = 0;
        }
    }

    // Count from when the request was sent, not when the reply came back: the store's timer may
    // have started any time after that. The margin covers clock rate drift.
    private void extend(double sentAt) {
        deadline = sentAt + TTL - MARGIN;
        nextRenew = sentAt + RENEW_EVERY;
    }

    boolean isLeader(double now) {
        return token != 0 && now < deadline;
    }
}

class Main {
    public static void main(String[] args) {
        LeaseStore store = new LeaseStore();
        Elector a = new Elector("A", store), b = new Elector("B", store);

        for (int t = 0; t < 8; t++) { // both run their loops once a second
            a.tick(t);
            b.tick(t);
        }
        System.out.println(a.isLeader(7) + " " + a.token + " " + b.isLeader(7)); // true 1 false

        // A stalls in a 13 second GC pause: no ticks from t=8 to t=20. B keeps trying.
        for (int t = 8; t <= 20; t++) b.tick(t);
        System.out.println(b.isLeader(20) + " " + b.token); // true 2: A's lease expired at t=16

        // A wakes at t=20. Its own deadline (renewed at t=6, so 6 + 10 - 2 = 14) has passed, so
        // it knows to stop before doing anything. A pause that strikes between isLeader() and the
        // write cannot be caught here: the resource must reject token 1 once it has seen token 2.
        System.out.println(a.isLeader(20)); // false
        a.tick(20);
        System.out.println(a.token); // 0
    }
}

The loop cannot make leadership exclusive by itself. Say “am I still leader?” returns true. Before the write lands, the process can pause for garbage collection or a VM migration. It can resume after the lease has passed to someone else. Only the resource being written can stop that. It refuses tokens lower than the highest it has seen. That’s a fencing token (Chubby called it a sequencer). The storage side is a few lines, and the replication page has the code.

A paused lock holder is stopped by the storage, not by the lock

Scroll or pinch to zoom, drag to pan

• Color key
• Background worker
• Service

Options and tradeoffs

Where consensus belongs

Consensus costs a majority round trip and a disk flush per decision. It belongs on small, important, rarely changing state, not on the data path.

Use it for	Why	Typical home
Leader election, locks, shard ownership	Two holders is a correctness bug	etcd, ZooKeeper, Consul leases
Cluster metadata and config	Every node must see the same membership and settings	Kafka KRaft, Kubernetes on etcd
Sequencers and ID ranges	A number handed out twice is a duplicate ID or a reordered trade	A Raft group or a consensus-backed counter
Uniqueness and compare-and-set	“Only if absent” needs one order of operations	Spanner, CockroachDB, DynamoDB conditional writes
Not bulk data	Gigabytes per second of events, logs or blobs	Replicated by a leader chosen through consensus

Consensus decides who leads, and what the configuration is. Data moves without a consensus round per record. Kafka replicates messages to in-sync replicas. Only leadership changes go through the KRaft log.

TradeoffConsensus for control, plain replication for data

We gain

The data path runs at the speed of one leader and its followers. Leadership, membership and ownership changes are decided safely, with no split brain.

We give up

Two systems to understand, and the data path’s safety now depends on every write checking the epoch or token that consensus handed out.

Which protocol

Raft is the default. It’s well specified, with mature libraries (etcd’s raft, hashicorp/raft) that have survived years of production and fault-injection testing. Multi-Paxos and ZAB solve the same problem, with the same majority-and-epoch idea. You meet them inside Spanner, DynamoDB and ZooKeeper, instead of choosing them. Whichever runs underneath, one leader per group handles every write. And a leader failure pauses writes for an election timeout plus a round trip.

Go deeperRaft, Multi-Paxos, ZAB and their relatives4 min

Protocol	Leader	How a value is chosen	Used by	When it wins
Raft	Strong leader per term, log has no holes	Leader appends, majority stores, commits current-term entries	etcd, Consul, CockroachDB, TiKV, Kafka KRaft	Default choice: well specified, many tested libraries
Multi-Paxos	A stable proposer, elected informally	Phase 1 once per leader, then one accept round per slot	Chubby, Spanner, Megastore, DynamoDB partitions	When you need the flexibility of the general theory
ZAB	Primary per epoch	Primary broadcasts, majority acks, new primary syncs followers first	ZooKeeper	You run ZooKeeper; it is not offered as a library

Paxos (Lamport, a 1989 report published in 1998) is the original. In its basic form, it has two phases:

1. Prepare. A proposer picks a ballot number n. It asks acceptors to promise to ignore lower ballots.
2. Accept. If a majority promises, the proposer must adopt the highest-numbered value any of them already accepted. If none did, it uses its own. Then it asks them to accept it.

A value accepted by a majority is chosen. That decides one value in two round trips.

Multi-Paxos runs a log of such slots. A stable leader does phase 1 once, for all future slots. So each value then costs one round trip, which is what Raft does too. Multi-Paxos allows holes in the log, and leaves leader election loosely specified. That’s why so many Paxos implementations differ.

ZAB (ZooKeeper Atomic Broadcast) is primary-backup with epochs. Each transaction ID (zxid) is 64 bits: the epoch in the high 32 and a counter in the low 32. A new primary first collects the latest history from a quorum and syncs every follower to it, then starts broadcasting.

• Viewstamped Replication (Oki and Liskov, 1988) solved the same problem as Paxos at about the same time with a primary and view numbers. Raft’s design is closer to VR than to Paxos.
• Flexible Paxos (Howard, Malkhi and Spiegelman, 2016) showed that the election quorum and the replication quorum only need to intersect each other, not themselves. With 10 nodes, writes could need 3 acks if elections need 8. Faster writes, slower and more fragile elections.
• Raft with witnesses: a node that votes, and stores log entries until they commit, but holds no state machine. It’s cheap enough to be the third vote for a pair of data nodes.
• Chain replication orders writes along a chain. It needs a separate consensus-backed master to reconfigure the chain when a node fails. That’s consensus for control again.

Build it in, or use a service

Option	How	Wins	Loses
Coordination service (etcd, ZooKeeper, Consul)	Leases, watches and compare-and-set on a 3 or 5 node cluster	Battle tested; your service stays stateless	Another critical cluster; small values only
Embedded Raft library	Your nodes are the Raft group	No external dependency, data and decisions together	You now operate consensus: snapshots, membership, disks
Conditional writes in your database	Lease row with owner, expires_at, version, updated by compare-and-set	No new system; the version is the fencing token	Only as available and consistent as that database’s own failover
A managed lock (DynamoDB lock client, Kubernetes Lease)	A library over a store you already have	Little to run	Same pauses and clocks; still needs fencing on writes

TradeoffA coordination service for leases, fencing in the store

We gain

Application instances stay stateless, one etcd or ZooKeeper cluster serves many services, and correctness does not rest on the lease alone.

We give up

Every service depends on the coordination cluster for failover, and every write path must carry and check a token.

Which read path

Read path	Linearizable	Cost per read	Used by
Through the log	Yes	A full write: round trip plus fsync	Simple implementations, strict audits
ReadIndex	Yes	One heartbeat round, batched	etcd default, TiKV
Lease read	Yes, while clock drift stays bound	Local	Spanner, CockroachDB leaseholders, TiKV
Follower read via ReadIndex	Yes	One round trip to the leader	etcd and TiKV followers
Stale follower read	No: may be seconds behind	Local	etcd serializable, ZooKeeper default, Consul stale

TradeoffReadIndex by default, stale reads where staleness is fine

We gain

Correct reads with no dependence on clocks, at the price of a network round trip. And cheap local reads for dashboards, caches, and anything that tolerates a second of lag.

We give up

ReadIndex adds about one intra-region round trip (under 1 ms) per read batch, and every reader must choose its mode deliberately.

How many nodes, and where

Voters	Majority	Failures tolerated	Notes
1	1	0	Fine for development; the disk is the only copy
2	2	0	Worse than 1: two machines that can each stop the cluster
3	2	1	The default; one node can be down for maintenance with no margin left
4	3	1	Same tolerance as 3, one more ack needed per write
5	3	2	Survives a failure during maintenance; common for critical clusters
7	4	3	Rare: every write waits for 4, and elections get slower

Even numbers do not help: a 2 + 2 split stops a 4-node cluster, where 3 nodes split 2 + 1 keep going. Add read capacity with learners or follower reads, not voters.

Placement sets the write latency. A commit waits for the fastest majority - 1 followers. Three nodes in three zones of one region commit in about 1 to 2 ms, plus fsync. Now place five nodes: 2 in us-east, 2 in us-west, and 1 in Europe. They survive losing a region. But a us-east leader needs an ack from outside its region. That’s 60 to 70 ms on every write, forever.

TradeoffFive voters across three zones of one region

We gain

Writes in a few milliseconds, two simultaneous failures tolerated, and a whole zone can go down with the cluster still writable.

We give up

A region outage stops the cluster. Surviving it costs 30 to 100 ms per write, so most systems keep consensus regional and replicate across regions asynchronously.

How it fails

Failure	What breaks	How you see it	Fix
Election storm	Split votes or early timeouts; no leader for seconds	Term climbing fast, many leader changes	Randomized timeouts at least 10 heartbeats long, PreVote
Slow disk, leader churn	Late fsyncs delay heartbeats, followers elect someone else, repeatedly	WAL fsync p99 over 10 ms, frequent elections	A dedicated SSD for the log; raise timeouts only after fixing the disk
GC or VM pause	A lease holder sleeps past its lease and wakes up acting as leader	Writes rejected for old tokens	Fencing tokens checked by the resource, a stop-early margin
Quorum lost	2 of 3 (or 3 of 5) down: no writes, no linearizable reads	Proposals failing, no leader	Voters in separate failure domains; manual recovery can lose writes
The 2-node trap	Either node failing stops writes, or “both may lead” splits the brain	Outage on any single failure	A third voter, even a small witness
Clock-based lease	A fast-running lease or an unnoticed pause serves reads after the lease	Stale reads, only under faults	ReadIndex, monotonic clocks, a drift margin
Disruptive rejoining node	A node with a term inflated by failed elections deposes a healthy leader	An election whenever a flaky node reconnects	PreVote, and CheckQuorum on leaders
Too much data or watchers	Big values slow snapshots; watch fan-out saturates the leader	Database near quota, apply lag	Store pointers, not blobs; compact; watch proxies

The disk row is the one teams hit first. A leader whose fsync takes 500 ms sends heartbeats late, followers elect a new leader, and the new one often shares the same storage. etcd’s guidance is a WAL fsync p99 under 10 ms, which rules out many network volumes under load.

The disruptive node is subtler. It’s cut off behind a flaky link. It times out again and again, and its term climbs to 47. When the link returns, that term deposes a healthy leader of term 12.

PreVote fixes this. A node first asks whether a majority would vote for it, without raising its term. Followers that still hear a leader say no. CheckQuorum is the leader-side twin. A leader that has not heard from a majority within an election timeout steps down. So a leader stranded on the minority side stops accepting writes, instead of collecting doomed ones.

Partial partitions test the timeouts hardest. That’s where A reaches B, and B reaches C, but A cannot reach C. In November 2020, Cloudflare described one. A partially failed network switch left an etcd cluster changing leaders over and over. The database failover tooling built on etcd degraded their control plane (API and dashboard) for hours.

Go deeperRecovering from lost quorum1 min

If a majority is permanently gone, the cluster cannot recover by itself. By design, a minority never decides. The recovery is manual, and unsafe:

1. Pick the surviving node with the most up-to-date log.
2. Restart it as a new single-node cluster (etcd’s --force-new-cluster, or restoring a snapshot with etcdctl snapshot restore).
3. Add fresh members, one at a time.

Any entry that was committed on the lost majority, but not on the survivor, is gone. Practise this. And back up the coordination store’s snapshot on a schedule, like any database.

Common mistake

"The lock service guarantees only one holder"

It guarantees that the lock service never grants the same lock twice at once. It cannot stop a client from believing it still holds a lock it lost during a pause. So a ZooKeeper or etcd lock used for correctness needs a fencing token. The protected resource checks it on every write. Redlock uses five independent Redis nodes, with no consensus between them. It gives no tokens, and depends on clocks. So it has the same hole, with fewer guarantees.

At scale

Quantity	Typical value
etcd heartbeat / election timeout defaults	100 ms / 1,000 ms
Commit latency, 3 zones in one region	1 to 5 ms: a zone round trip plus fsync
Commit latency, voters in 3 regions	30 to 100 ms, one cross-region round trip
Failover, Raft group	Election timeout plus a round trip: about 1 to 3 s in etcd
etcd request size / default quota / suggested max	1.5 MiB / 2 GB / 8 GB
etcd WAL fsync p99 target	Under 10 ms
Small writes per second, one etcd cluster	Tens of thousands with batching, bound by the leader and its disk

One Raft group is one leader. Every write passes through one machine’s network card and disk, and adding voters makes writes slower, not faster. What changes with growth:

• 10 times the writes. Batch many entries into one fsync, and pipeline AppendEntries. Use a faster disk. Move reads to followers with ReadIndex, so the leader only orders writes.
• 100 times, or terabytes of state. Split the keyspace into ranges, each its own Raft group. This is multi-Raft. CockroachDB and TiKV run thousands of groups per cluster, and spread leaders across nodes. They coalesce heartbeats, so a node sends one message per peer, not per group. A small separate group tracks which group owns which range.

Watch leader changes, failed proposals, fsync latency and database size against quota. For a lease-based leader in your own service, also alert on writes rejected for stale tokens: each one is a pause that fencing caught.

Go deeperThe etcd metrics behind those signals1 min

Signal	etcd metric	Why
Leader changes	etcd_server_leader_changes_seen_total	More than a few an hour means disk, network or timeout trouble
Failed and pending proposals	etcd_server_proposals_failed_total, ..._pending	Writes that could not commit: lost quorum or churn
WAL fsync and backend commit latency	etcd_disk_wal_fsync_duration_seconds, etcd_disk_backend_commit_duration_seconds	The leading cause of churn
Peer round trip time	etcd_network_peer_round_trip_time_seconds	Should be well under the heartbeat interval
Database size against quota	etcd_mvcc_db_total_size_in_bytes	At the quota, etcd raises an alarm and refuses writes

In the interview

Interviewer asksWhy run 5 coordination nodes and not 4 or 6?

4 nodes need 3 acks and survive one failure, like 3, and a 2 + 2 split stops everything. 5 survive two failures: one planned upgrade plus one surprise. 6 also survives two and costs a node more. Start at 3 across three zones and move to 5 when maintenance must not leave zero margin.

Interviewer asksThe leader ends up on the minority side of a partition. What happens to writes and reads there?

Its writes never reach a majority. So they never commit, and clients time out. With CheckQuorum, it steps down after an election timeout. The majority side elects a leader in a higher term. On healing, the old leader sees that term, and steps down. Its uncommitted entries are overwritten. Reads are the danger. Answered locally, they return data the new leader has replaced. ReadIndex refuses, because it cannot confirm leadership with a majority. Lease reads are safe only while the drift assumption holds.

Interviewer asksYou need exactly one active instance of a scheduler. Walk me through it.

Instances campaign for a key in etcd, on a 10 second lease renewed every 3. The winner gets the key’s revision as its token. The leader stops at its own deadline, before etcd expires the key. That deadline is the last renewal sent, plus the TTL, minus a margin. Standbys watch the key, and campaign when it goes. A pause can still outlast the lease. So every side effect carries the token. The job store refuses lower tokens, and the bank call carries an idempotency key. Failover takes about one lease period. And two leaders become harmless, not impossible.

Common mistake

"FLP says consensus is impossible" or "Raft is always available"

FLP says no deterministic protocol can guarantee termination in a fully asynchronous network with one possible crash. Raft never violates safety and terminates whenever the network is calm long enough, which is almost always. But it is not always available either: a minority partition, or a cluster that lost its majority, stops accepting writes. That is the design working.

Mid-level covers

Uses ZooKeeper or etcd for leader election. Knows a majority is needed, and that 3 or 5 nodes are typical. Knows the leader takes the writes.

Senior adds

Explains why majorities stop split brain, and separates safety from liveness. Walks through the vote restriction and the current-term commit rule. Explains stale reads from a deposed leader. Insists on fencing tokens. Names the real failures: slow disks, pauses, disruptive nodes.

Seen in

• Key-value store: a Raft or Paxos leader per partition weighed against leaderless quorums, and compare-and-set through Paxos.
• Message queue: a KRaft controller quorum holds the metadata, and picks partition leaders. Messages replicate without consensus rounds.
• Job scheduler: partition leases with epochs. Raft per partition was rejected as building a database.
• Collaborative editor: document slots leased in etcd, fenced by writing each revision only if absent.
• Ride hailing: one dispatcher per city on an etcd or ZooKeeper lease, taken over with a higher epoch.
• Stock exchange: sequencer promotion by leader election with an epoch in every entry.
• Unique ID generator: worker IDs as etcd keys on a lease, with a high-water mark kept off the lease.
• Web crawler: crawl partitions leased in etcd. Lost quorum pauses the crawl, which is the safe direction.
• Chat: conversation partitions on leases, with a conditional insert as the fence.
• Distributed cache: a cluster manager on etcd that promotes a replica only after the old primary’s lease runs out.

Recap

Why. Several machines must hold one answer (who leads, what order, who owns what) through crashes and partitions. A node deciding alone gives split brain.

Majorities. 2f + 1 nodes survive f failures. Two majorities always overlap. Use 3 or 5 voters, never even numbers. The minority side stops, by design.

Guarantees. Safety always, liveness only under partial synchrony (FLP): unavailable, never wrong.

Raft. Terms as a built-in fence. One persisted vote per term. Randomized timeouts. AppendEntries checks the previous entry (Log Matching). Vote only for logs at least as up to date. Count copies only for current-term entries, so a new leader commits a no-op first.

Reads. A deposed leader serves stale reads. Use ReadIndex, lease reads (clocks), follower reads via ReadIndex, or deliberately stale reads.

Operations. Snapshots, one-server membership changes with learners, PreVote, fsync p99 under 10 ms.

As a service. etcd leases or ZooKeeper ephemeral nodes, stop early, and fencing tokens checked by the resource. Consensus for control, never for the bulk data path.

Further reading

• On this site: replication (failover, epochs, the fencing check), consistency models (linearizability, ReadIndex), partitioning (many groups) and CAP and PACELC.
• Diego Ongaro and John Ousterhout, In Search of an Understandable Consensus Algorithm, USENIX ATC 2014: the Raft paper, including Figure 8 and joint consensus.
• Martin Kleppmann, How to do distributed locking: why a lease needs a fencing token, and why Redlock does not provide one.
• Martin Kleppmann, Designing Data-Intensive Applications, chapter 9 (Consistency and Consensus): linearizability, total order broadcast and consensus as one idea.