Consensus and Coordination Algorithms Questions

Short answer

A robust single-instance Redis (an in-memory key-value data store; in production it typically runs as one primary node plus replica copies, so a single node's loss doesn't lose the data) lock has three atomic operations: acquire with SET key <random-owner-id> NX PX <ttl> (set only if absent, with an expiry in milliseconds), renew with a Lua script that extends the expiry only if the value is still my owner ID, and release with a Lua script that deletes only if the value is still my owner ID. The random owner ID prevents lock-stealing (one client deleting another's lock), and the TTL (time-to-live) prevents deadlock when a holder crashes. What it cannot prevent is a holder that pauses past its TTL and wakes up still acting, or a lock lost in a Redis failover, so for anything where two holders would corrupt data you also need a fencing token that the protected resource checks. Without that, a Redis lock is an efficiency lock: it stops duplicate work most of the time, not always.

Design

Owner identifier. A random value generated per acquisition (a UUID), not a hostname or thread ID, so a client's second acquisition, or a retry, can never be confused with its first.

Why every check-then-act runs in Lua. Lua is a small scripting language built into Redis; Redis runs a Lua script atomically, so "is it still mine? then delete" cannot be interleaved with another client's acquire. The naive GET then DEL from the client has a window where the lock expires and someone else acquires between the two commands, and the DEL removes their lock.

Renewal (a watchdog). A background task renews at about one third of the TTL. If renewal returns 0, or has not succeeded by the time the local deadline passes, the holder must abort its work.

Fencing token. On each successful acquire, INCR a per-lock counter and hand that number to the protected resource with every write; the resource rejects any number lower than the highest it has accepted.

Pseudo-code

(EVAL runs a Lua script atomically on the Redis server; PEXPIRE resets a key's time-to-live, in milliseconds.)

acquire(key, ttlMs, waitUpTo):
    owner = randomUUID()
    until waitUpTo elapses:
        if SET key owner NX PX ttlMs == OK:
            fence = INCR key + ":fence"
            start watchdog: every ttlMs/3 -> renew(key, owner, ttlMs) or signal LOST
            return (owner, fence)
        sleep(random jitter, growing backoff)          // jitter: a small random delay, so waiting clients don't all retry at once and collide again
    return TIMEOUT

renew(key, owner, ttlMs):      EVAL "if GET(key)==owner then return PEXPIRE(key, ttlMs) else return 0"
release(key, owner):           stop watchdog; EVAL "if GET(key)==owner then return DEL(key) else return 0"

Executed demonstration

This runs against a disposable Redis (docker run -d --name redis-demo -p 6379:6379 redis:7-alpine, removed afterwards with docker rm -f redis-demo) using the redis Python package. The scenario is the orchestrated-rollback case: only one orchestrator may roll a set of microservices (small, independently deployable services that together make up the application) back at a time, and the deploy system is the protected resource that checks fencing tokens.

import os, time, uuid
import redis

r = redis.Redis(port=int(os.environ.get("REDIS_PORT", "6379")), decode_responses=True)

RENEW = r.register_script("""
if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('PEXPIRE', KEYS[1], ARGV[2])
end
return 0""")
RELEASE = r.register_script("""
if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('DEL', KEYS[1])
end
return 0""")

def acquire(key, ttl_ms):
    owner = uuid.uuid4().hex                      # unique per acquisition, not per process
    if r.set(key, owner, nx=True, px=ttl_ms):     # atomic "create if absent, with expiry"
        fence = r.incr(key + ":fence")            # monotonically increasing fencing token
        return owner, fence
    return None, None

def renew(key, owner, ttl_ms):  return RENEW(keys=[key], args=[owner, ttl_ms]) == 1
def release(key, owner):        return RELEASE(keys=[key], args=[owner]) == 1

# The protected resource remembers the highest fencing token it has accepted.
highest_seen = {"rollback:checkout-svc": 0}
def guarded_write(resource, fence, what):
    if fence < highest_seen[resource]:
        return f"REJECTED {what} (token {fence} < {highest_seen[resource]})"
    highest_seen[resource] = fence
    return f"ACCEPTED {what} (token {fence})"

r.delete("lock:rollback", "lock:rollback:fence")
a_owner, a_fence = acquire("lock:rollback", 200)
print("A acquire:", a_owner is not None, "fence", a_fence)
b_try, _ = acquire("lock:rollback", 200)
print("B acquire while A holds:", b_try is not None)
print("A renew while valid:", renew("lock:rollback", a_owner, 200))
time.sleep(0.3)                                   # A stalls (GC pause) past its TTL
b_owner, b_fence = acquire("lock:rollback", 5000)
print("B acquire after A's TTL lapsed:", b_owner is not None, "fence", b_fence)
print("A renew after losing lock:", renew("lock:rollback", a_owner, 200))
print("A release after losing lock:", release("lock:rollback", a_owner))
print("lock still held by B:", r.get("lock:rollback") == b_owner)
print(guarded_write("rollback:checkout-svc", b_fence, "B: set checkout-svc to v41"))
print(guarded_write("rollback:checkout-svc", a_fence, "A: set checkout-svc to v42"))
print("B release:", release("lock:rollback", b_owner))

Output:

A acquire: True fence 1
B acquire while A holds: False
A renew while valid: True
B acquire after A's TTL lapsed: True fence 2
A renew after losing lock: False
A release after losing lock: False
lock still held by B: True
ACCEPTED B: set checkout-svc to v41 (token 2)
REJECTED A: set checkout-svc to v42 (token 1 < 2)
B release: True

The 0.3 s sleep stands in for a garbage-collection pause longer than A's 200 ms TTL. The owner-checked renew and release stop A from extending or deleting B's lock. The final two lines are the only thing that stops A's late write: the lock alone could not.

Worked example: orchestrated rollback across microservices

A bad release has shipped to checkout-svc, payments-svc and inventory-svc. Two on-call engineers trigger a rollback from different consoles within seconds of each other.

1. Both orchestrators call acquire("lock:rollback", ttl=30s). Only one SET NX succeeds; the other waits or reports "rollback already in progress by owner X".
2. The winner gets fencing token 57 and records it in the rollback plan. Every call to the deploy API carries fence=57, and the deploy API stores the highest token seen per service.
3. The winner renews every 10 s while it drains traffic (stops routing new requests to the service while letting in-flight ones finish) and redeploys each service in dependency order (inventory, then payments, then checkout).
4. If the winner's host freezes for 45 s, its lock expires, the second orchestrator acquires with token 58 and takes over. When the first one wakes and tries to redeploy checkout-svc, the deploy API rejects token 57.
5. Each step is idempotent (deploying version v41 twice leaves v41), so a takeover that repeats a step is harmless.

Failure modes

What about Redlock?

Redlock is Redis's documented algorithm for acquiring the lock on a majority of N independent Redis masters (typically 5, and unlike the primary-plus-replica pair used above, these N instances do not replicate to each other) to survive the failover case. It is widely debated: Martin Kleppmann's critique argues that it still relies on bounded process pauses, network delay and clock drift for safety, and that it produces no fencing token; the Redis author's reply argues the assumptions are reasonable in practice. The practical conclusion either way: if two holders would corrupt data, you need fencing, and once you need a strongly consistent token source you may as well use a consensus store for the lock itself. Redlock mainly improves availability for efficiency locks.

Complexity and edge cases

Acquire, renew and release are each O(1) and one round trip (plus one for INCR). Edge cases: a SET whose reply is lost (retry with the same owner ID and treat "value equals my owner" as success), release after expiry (returns 0, which is normal), renewal racing release (the Lua check makes either order safe), and a TTL shorter than one network round trip (the lock may expire before the client learns it acquired it; enforce a minimum TTL).

Direct answer

A replicated database keeps several copies of each piece of data, and those copies must agree on the order of writes. The simplest way to get one order is to let exactly one node, the leader, accept writes and tell the others (the followers) what to apply. Leader election is the protocol that picks that node and replaces it when it fails, and it must never let two nodes both believe they are leader at the same time. Raft and Paxos are the algorithms; etcd and ZooKeeper are systems that package them. The price is a short write outage every time the leader dies or gets cut off, plus the rule that only the side of a partition holding a majority may keep working.

Why a leader at all

Without a single writer, two replicas can accept conflicting writes to the same row at the same moment ("set balance to 80" on one node, "set balance to 50" on another), and the cluster ends up with copies that disagree. Resolving that afterwards is either impossible (money) or needs merge rules the application must supply. A leader serialises writes: it assigns each write a position in a log (entry 41, 42, 43...), and every follower applies the same log in the same order, so every copy ends in the same state. This pattern is called state machine replication.

Two terms appear in every leader-election protocol:

• Quorum (majority): more than half the voting members, for example 3 of 5. Any two majorities of the same group share at least one member, and that shared member is what stops two leaders from being elected for the same period.
• Term (Raft) / epoch (ZooKeeper) / ballot (Paxos): a number that increases with every election. Messages carry it, and a node that sees a higher number steps down. It is how the cluster tells the current leader from an old one.

The common algorithms and systems

Note the two layers. A database such as CockroachDB or TiKV (distributed SQL/key-value databases that split their data into many small pieces) embeds Raft and elects a leader per data range (one such piece: a contiguous slice of the keyspace, replicated and led independently of the other pieces). A service that is not itself replicated (say, one active scheduler among three instances) borrows an election from etcd or ZooKeeper instead of implementing consensus.

How leader election affects availability

While there is no leader, the cluster cannot accept writes, and strongly consistent reads (reads guaranteed to reflect every write acknowledged before them, rather than possibly returning slightly old data) also stall. The outage is roughly:

failure detection time + election time + client retry time.

Worked example with etcd's documented defaults (heartbeat 100 ms, election timeout 1000 ms): a leader crashes. Followers wait up to about 1 s without a heartbeat, one starts an election, and with a network round trip of a few milliseconds it wins almost immediately. Clients that were mid-request see an error or timeout and retry. So a leader crash costs on the order of one to two seconds of write unavailability, not zero. A 5-member cluster tolerates 2 simultaneous failures (3 of 5 is still a majority); a 3-member cluster tolerates 1.

Reads that can accept slightly old data may be served by any follower during the gap, which is a deliberate trade of freshness for availability.

What an architect must consider

Network partitions. Suppose 5 nodes split into groups of 3 and 2. Only the group of 3 can elect a leader and commit writes; the group of 2 must refuse writes. If the old leader was in the group of 2, it keeps thinking it is leader until it notices it cannot reach a majority. That is the split brain risk (two nodes both acting as leader). Raft prevents two committed histories because the minority leader cannot get majority acknowledgements, but the stale leader can still serve stale reads or keep doing side effects outside the database unless:

• reads go through the leader with a majority check or a leader lease (a period during which the leader knows no one else can be elected), and
• external side effects carry a fencing token (the term number, checked by the receiving system so it rejects anything from an older term).

Placement. Put members in at least three failure domains (availability zones or regions). With two zones, losing the zone holding the majority takes the cluster down.

Leader churn. Frequent re-elections cost more than one clean failover, because each election is a write outage. Common causes are an election timeout set too close to the real network round trip, slow disks (a leader stuck in a disk sync misses heartbeats), long garbage-collection pauses and overloaded CPUs. The fixes are tuning the timeout to at least 10 times the round trip time (etcd's own guidance), fast dedicated disks, and alerting on the rate of leader changes rather than just on "is there a leader".

Cluster size. Use an odd number of voters, usually 3 or 5. Going from 5 to 7 tolerates one more failure but every write now waits for 4 acknowledgements instead of 3, so writes get slower.

Trade-offs and pitfalls

• Consensus is not free availability. It trades availability during partitions for correctness. If the data can tolerate conflicts (a "likes" counter, a shopping cart), a leaderless eventually consistent design (every replica can accept writes independently, and copies converge to the same value over time rather than agreeing instantly) may be the better fit.
• Rolling your own election with a heartbeat and a timeout (whoever has not heard from the leader for 5 s takes over) produces two leaders the first time a network is slow rather than dead. Borrow a proven implementation.
• Believing the process that holds leadership is the only one acting. A leader paused by garbage collection can wake up and act after it has been replaced. Fencing tokens, not timeouts, make that safe.
• Watching only "leader exists". A cluster that re-elects every few minutes looks healthy on that metric while clients see repeated error spikes.

Direct answer

Hold leadership as a single key in etcd (a distributed key-value store that replicates every write through the Raft consensus protocol) and tie that key to a lease: a server-side timer with a TTL (time-to-live) that deletes every attached key unless the owner keeps renewing it. A candidate wins by running a compare-and-swap (CAS) transaction ("create the key only if it does not exist yet"), keeps winning by streaming lease keep-alives, and loses automatically when it stops renewing, because the server deletes the key. Two extra pieces make it robust rather than merely working: every write the leader makes is fenced by the key's create revision, so a leader that was paused and woke up late cannot overwrite its successor, and a graceful shutdown deletes the key explicitly so followers take over at once instead of waiting out the TTL.

Vocabulary first

• Leader election: picking exactly one process out of several to do a job (run the scheduler, own a partition) so the others stay on standby.
• Heartbeat: a periodic "I am still alive" message. Here the heartbeat is the lease keep-alive: stop sending it and the lease expires.
• Revision: etcd keeps one cluster-wide counter that goes up by one on every write. Each key records the revision at which it was created (CreateRevision). A key that does not exist has CreateRevision 0, which is what makes "create only if absent" expressible as a comparison.
• Transaction (Txn): If(conditions).Then(ops).Else(ops), evaluated atomically on the server. Two candidates racing cannot both see "absent".
• Split brain: two processes both believing they are leader at the same moment.
• Fencing token: a number that only ever increases with each new leader. The resource being protected rejects any write carrying an older number, so a stale leader is harmless even if it does not know it is stale.

Approach

1. Grant a lease (Grant, TTL 3 s in the demo). The TTL is the longest the cluster will wait for a dead leader before replacing it.
2. Contest the key with one transaction: If CreateRevision(key) == 0 Then Put(key, myID, WithLease(lease)) Else Get(key). Exactly one racer succeeds. The winner records the response's header revision: that is the key's create revision and becomes the fencing token.
3. Losers revoke their unused lease and watch the key, starting from the transaction's revision + 1. Starting the watch at a specific revision matters: if the leader's key is deleted between the losing Txn and the Watch call, etcd still delivers that delete from history, so the follower never sleeps forever.
4. The leader renews with KeepAlive, which returns a channel of renewal responses. Leadership is considered lost when that channel closes (lease revoked, expired, or the client gave up) or when no renewal has been confirmed for a whole TTL. The second condition is a local watchdog, because during a network partition the stream can simply go quiet rather than close.
5. Guard every leader action with a transaction that compares the leadership key's CreateRevision to the token. If a new leader exists, the key has a newer create revision and the write is refused atomically.
6. Graceful stepdown (Resign): stop keep-alives, delete the key only if it is still ours (same revision comparison, so we never delete a successor's key), then revoke the lease.

Code (Go, go.etcd.io/etcd/client/v3)

Start a throwaway single-node etcd and fetch the client:

docker run -d --name etcd-demo -p 2379:2379 quay.io/coreos/etcd:v3.5.13 \
  etcd --advertise-client-urls http://0.0.0.0:2379 --listen-client-urls http://0.0.0.0:2379
mkdir leaderdemo && cd leaderdemo
go mod init leaderdemo
go get go.etcd.io/etcd/client/v3@v3.5.16
# save the program below as main.go, then:
go run .

package main

import (
	"context"
	"errors"
	"fmt"
	"log"
	"os"
	"time"

	clientv3 "go.etcd.io/etcd/client/v3"
)

const (
	electionKey = "/election/report-scheduler"
	ttlSeconds  = 3
)

// Candidate contests one leadership key. While it is leader, leaderRev (the
// key's create revision) doubles as a fencing token for every guarded write.
type Candidate struct {
	id        string
	cli       *clientv3.Client
	leaseID   clientv3.LeaseID
	leaderRev int64
	stopKA    context.CancelFunc
	lost      chan struct{} // closed when leadership is lost for any reason
}

func NewCandidate(id, endpoint string) (*Candidate, error) {
	cli, err := clientv3.New(clientv3.Config{Endpoints: []string{endpoint}, DialTimeout: 3 * time.Second})
	if err != nil {
		return nil, err
	}
	return &Candidate{id: id, cli: cli}, nil
}

// Campaign blocks until this candidate holds the key, or ctx is cancelled.
func (c *Candidate) Campaign(ctx context.Context) error {
	for {
		// 1. A fresh lease per attempt: the key dies with it if we stop renewing.
		lease, err := c.cli.Grant(ctx, ttlSeconds)
		if err != nil {
			return err
		}
		// 2. Compare-and-swap: create the key only if nobody holds it.
		resp, err := c.cli.Txn(ctx).
			If(clientv3.Compare(clientv3.CreateRevision(electionKey), "=", 0)).
			Then(clientv3.OpPut(electionKey, c.id, clientv3.WithLease(lease.ID))).
			Else(clientv3.OpGet(electionKey)).
			Commit()
		if err != nil {
			c.cli.Revoke(context.Background(), lease.ID)
			return err
		}
		if resp.Succeeded {
			c.leaseID, c.leaderRev = lease.ID, resp.Header.Revision
			return c.startKeepAlive()
		}
		// 3. Lost the contest: drop our unused lease, then wait for the holder's
		// key to disappear. Watching from the Get's revision+1 means a delete
		// that happens between the Txn and the Watch call is not missed.
		c.cli.Revoke(ctx, lease.ID)
		holder := resp.Responses[0].GetResponseRange().Kvs[0]
		fmt.Printf("[%s] follower: leader is %s (rev %d), watching\n", c.id, holder.Value, holder.CreateRevision)
		if err := c.waitForDelete(ctx, resp.Header.Revision+1); err != nil {
			return err
		}
	}
}

func (c *Candidate) waitForDelete(ctx context.Context, fromRev int64) error {
	wctx, cancel := context.WithCancel(ctx)
	defer cancel()
	for wr := range c.cli.Watch(wctx, electionKey, clientv3.WithRev(fromRev)) {
		if err := wr.Err(); err != nil {
			return err
		}
		for _, ev := range wr.Events {
			if ev.Type == clientv3.EventTypeDelete {
				fmt.Printf("[%s] saw leader key deleted, contesting\n", c.id)
				return nil
			}
		}
	}
	return ctx.Err()
}

// startKeepAlive renews the lease in the background. Leadership is treated as
// lost when the keep-alive stream closes OR when no renewal has been confirmed
// for a full TTL (the stream can stall silently during a partition).
func (c *Candidate) startKeepAlive() error {
	kactx, cancel := context.WithCancel(context.Background())
	ch, err := c.cli.KeepAlive(kactx, c.leaseID)
	if err != nil {
		cancel()
		return err
	}
	c.stopKA, c.lost = cancel, make(chan struct{})
	go func() {
		defer close(c.lost)
		watchdog := time.NewTimer(ttlSeconds * time.Second)
		defer watchdog.Stop()
		for {
			select {
			case ka, ok := <-ch:
				if !ok || ka == nil {
					return // stream closed: lease revoked, expired, or ctx cancelled
				}
				// Stop() returns false if the timer already fired (or was already
				// stopped); when that happens a value may be sitting unread on
				// watchdog.C, and draining it here is required before Reset, or a
				// later loop iteration could read that stale fired-value and treat
				// a freshly-reset timer as if it had already expired.
				if !watchdog.Stop() {
					<-watchdog.C
				}
				watchdog.Reset(ttlSeconds * time.Second)
			case <-watchdog.C:
				return // no confirmed renewal for a whole TTL: assume the worst
			}
		}
	}()
	fmt.Printf("[%s] LEADER (fencing token = create revision %d)\n", c.id, c.leaderRev)
	return nil
}

// FencedPut performs a write only if we are still the holder we think we are.
// etcd evaluates the comparison and the write atomically in one transaction.
func (c *Candidate) FencedPut(ctx context.Context, key, val string) error {
	resp, err := c.cli.Txn(ctx).
		If(clientv3.Compare(clientv3.CreateRevision(electionKey), "=", c.leaderRev)).
		Then(clientv3.OpPut(key, val)).
		Commit()
	if err != nil {
		return err
	}
	if !resp.Succeeded {
		return errors.New("fenced out: leadership key no longer carries our revision")
	}
	return nil
}

// Resign is the graceful stepdown: delete our key (only if it is still ours)
// so followers take over immediately instead of waiting out the TTL.
func (c *Candidate) Resign(ctx context.Context) error {
	c.stopKA()
	_, err := c.cli.Txn(ctx).
		If(clientv3.Compare(clientv3.CreateRevision(electionKey), "=", c.leaderRev)).
		Then(clientv3.OpDelete(electionKey)).
		Commit()
	c.cli.Revoke(ctx, c.leaseID)
	fmt.Printf("[%s] resigned\n", c.id)
	return err
}

func main() {
	ctx := context.Background()
	endpoint := "localhost:2379"
	if e := os.Getenv("ETCD_ENDPOINT"); e != "" {
		endpoint = e
	}
	a, err := NewCandidate("A", endpoint)
	if err != nil {
		log.Fatal(err)
	}
	b, err := NewCandidate("B", endpoint)
	if err != nil {
		log.Fatal(err)
	}
	a.cli.Delete(ctx, electionKey) // clean slate for a repeatable demo

	if err := a.Campaign(ctx); err != nil {
		log.Fatal(err)
	}
	fmt.Println("[A] fenced write:", a.FencedPut(ctx, "/jobs/last-run", "A@1"))

	bLeader := make(chan struct{})
	go func() {
		if err := b.Campaign(ctx); err != nil {
			log.Fatal(err)
		}
		close(bLeader)
	}()

	time.Sleep(4 * time.Second) // B stays a follower while A keeps renewing
	fmt.Println("simulating a stall in A: keep-alives stop, A's process keeps running")
	a.stopKA()
	<-bLeader // B takes over once A's lease expires on the server
	<-a.lost  // A's keep-alive loop has exited too, but A never re-checked it
	fmt.Println("[A] stale write after waking up:", a.FencedPut(ctx, "/jobs/last-run", "A@2"))
	fmt.Println("[B] fenced write:", b.FencedPut(ctx, "/jobs/last-run", "B@1"))

	start := time.Now()
	if err := b.Resign(ctx); err != nil {
		log.Fatal(err)
	}
	get, _ := b.cli.Get(ctx, electionKey)
	fmt.Printf("leader key present after resign: %v (freed without waiting %ds TTL: %v)\n",
		get.Count > 0, ttlSeconds, time.Since(start) < time.Second)
}

The main function drives a full scenario with two in-process candidates: A wins, B follows, A stops renewing (standing in for a long garbage-collection (GC) pause or a partition between A and etcd, while A's process keeps running and still believes it leads), B takes over, A's late write is rejected, and B resigns.

Output on a freshly started etcd (executed; the revision numbers are larger on a cluster that has already seen writes, and the rest is identical):

[A] LEADER (fencing token = create revision 2)
[A] fenced write: <nil>
[B] follower: leader is A (rev 2), watching
simulating a stall in A: keep-alives stop, A's process keeps running
[B] saw leader key deleted, contesting
[B] LEADER (fencing token = create revision 5)
[A] stale write after waking up: fenced out: leadership key no longer carries our revision
[B] fenced write: <nil>
[B] resigned
leader key present after resign: false (freed without waiting 3s TTL: true)

Reading the revisions: revision 2 is A's leadership key, 3 is A's fenced write to /jobs/last-run, 4 is the server deleting A's key when the lease expired, and 5 is B's leadership key. The token moved from 2 to 5, which is exactly why A's comparison CreateRevision == 2 failed.

Key points

• Correctness comes from the server, not the client. The CAS and the fenced write are single atomic transactions that etcd linearizes (orders as if they happened one at a time, consistent with real time) through Raft. No client-side check-then-act sequence exists anywhere.
• The lease protects liveness; the fencing token protects safety. The lease guarantees a dead leader is eventually replaced. It cannot stop a paused leader from acting after it was replaced, because the paused process has no way to notice time passing. The fenced write is what closes that gap, and in the demo A's lost channel had fired but A never looked, which is the realistic failure.
• Watch from a revision, not from "now". Otherwise a delete that lands between the losing transaction and the watch is missed.
• Each attempt uses a fresh lease and revokes it on loss, so a failed contest does not leave orphaned leases counting down on the server.

Complexity

• Campaign attempt: two round trips to etcd (Grant, then Txn), each one Raft commit on the server side.
• Steady state: one keep-alive per lease roughly every TTL/3 (the client library's cadence), independent of the number of followers; each follower holds one open watch.
• Failover time after a crash: up to one TTL for the server to expire the lease, plus a watch notification and one transaction. After a graceful Resign it is a single watch notification plus a transaction, because nothing waits for the TTL.
• On a leader loss every follower contests at once: N followers send N transactions and N-1 of them fail, a thundering herd (every waiter waking up and competing at the exact same instant, even though only one can possibly win). That herd is O(N) per failover and is fine for a handful of replicas.

Edge cases

• Paused leader (GC pause, VM freeze, laptop lid). Covered by fencing. Any external side effect (writing to a database, calling a payment API) must carry the token too, and the external system must reject older tokens. Fencing only inside etcd protects only etcd.
• Keep-alive stream goes silent without closing. Covered by the watchdog, which treats "no confirmed renewal for one TTL" as lost. The server may still consider the lease alive for a moment longer, which errs on the safe side (the leader stops early, never late). Why: the client can only reset its watchdog when it has confirmed a renewal, by actually receiving a response. If anything after that last confirmation goes missing (the next request, the next response, or both), the client has no way to know the lease was renewed again, so its watchdog keeps counting down from that last confirmed point. The server, meanwhile, only ever extends the real deadline when it actually receives a request; it never renews on faith. So the server's true expiry is always anchored to a request it can point to, while the client's watchdog is anchored to the last response it can point to, which is never later than that request. When the network keeps carrying the client's requests to the server but stops carrying responses back, the two drift apart in the safe direction: the server's real deadline runs later than the client's belief, not earlier, so the client gives up while the server would still, briefly, honour a renewal it does not know happened.
• etcd unreachable for the whole cluster. No one can win or renew; after the TTL the leader steps down and no one replaces it. That is the correct choice: without a quorum (a majority of the cluster's members agreeing) there is no safe way to know that nobody else leads.
• Process crash without Resign. The lease expires and the server deletes the key; followers wake from their watch.
• TTL choice. Too short and a slow network or GC pause causes spurious failovers; too long and a crashed leader leaves a gap. etcd enforces a minimum lease TTL, so very small values are raised by the server. Choose it from the longest pause you expect to tolerate, not from how fast you wish failover were.
• History already compacted. etcd periodically discards old revisions. If a follower's watch starts at a revision that has been compacted away, the watch reports a compaction error instead of the delete; waitForDelete returns that error, and the caller should simply start Campaign again, which re-reads the current state.
• Deleting a successor's key. Resign compares the create revision before deleting, so a leader that resigns late cannot remove the new leader's key.

Trade-offs and pitfalls

• In production, prefer the library. go.etcd.io/etcd/client/v3/concurrency provides Session (which owns the lease and keep-alive) and Election (Campaign, Resign, Observe). It orders candidates by creating a key per candidate under a prefix and letting the lowest create revision lead, with each waiter watching only the key just ahead of it, which removes the herd described above. Hand-rolling is worth doing to understand the mechanism and to explain it in an interview; shipping it means owning every edge case listed here.
• Leadership is not a lock on the outside world. The most common senior-level miss is treating "I hold the key" as sufficient. It only means "I held it at the last renewal". The token has to travel with the work.
• Do not put this on a hot request path. Election decides who does background or singleton work. Asking etcd "am I leader?" per user request turns a coordination service into a bottleneck.

Short answer

Raft is a consensus algorithm: a way for a small group of servers (typically 3 or 5) to agree on one ordered log of commands even when some of them crash. It works through a single leader that all writes go through. When followers stop hearing from the leader for longer than their election timeout, one of them becomes a candidate, bumps the term (a logical epoch number), votes for itself and asks the others for votes. Whoever collects votes from a majority (a quorum: 3 of 5) becomes leader for that term. Split votes are made rare by giving every server a randomized election timeout, so one server usually times out, campaigns and wins before anyone else wakes up.

The pieces, one at a time

Server states. Every server is in exactly one of three states:

Heartbeats. The leader sends AppendEntries messages (empty ones act as heartbeats) to every follower more often than the election timeout. Each valid heartbeat resets the follower's election timer.

Election timeout. If a follower's timer fires without a heartbeat from a current leader, it assumes the leader is dead and starts an election. The Raft paper suggests a range like 150 to 300 ms, drawn at random per server and re-drawn at the start of every election.

Term numbers. A term is a monotonically increasing integer that acts as a logical clock. Each term has at most one leader. Terms are how stale information is detected:

• Every message carries the sender's term.
• If a server sees a higher term than its own, it adopts that term and reverts to follower (a leader that learns it is stale steps down immediately).
• A request carrying a lower term than the receiver's is rejected.

Starting an election. The candidate increments its term, votes for itself, resets its own timer, and sends RequestVote(term, candidateId, lastLogIndex, lastLogTerm) to every other server.

Vote-granting rules. A server grants its vote only if all of these hold:

1. The request's term is at least the voter's current term.
2. The voter has not already voted for a different candidate in this term (one vote per term, first come first served). This is what makes two leaders in the same term impossible: two majorities of the same cluster always share at least one server, and that server can only vote once.
3. The candidate's log is at least as up-to-date as the voter's: its last entry has a higher term, or the same last term and an index at least as large. This "election restriction" guarantees the new leader already holds every committed entry (an entry safely replicated to a majority of the cluster and therefore promised to survive, even across leader changes).

Outcomes of an election.

• The candidate gets a majority: it becomes leader and immediately sends heartbeats to stop other elections.
• It receives an AppendEntries from another server with a term at least as high as its own: someone else won, so it returns to follower.
• Nobody reaches a majority (a split vote): timers expire again and a new election starts with term + 1.

How Raft keeps split votes rare

A split vote happens when several followers time out at almost the same moment, each votes for itself, and the remaining votes are divided so no one reaches a majority. Raft's fix is randomization: if timeouts are spread over a window that is wide compared with the time a vote request takes to arrive, the first server to time out usually reaches the others before their own timers fire, and they vote for it.

Worked example: measuring the effect with a small simulation

Model a 5-node cluster whose leader has just died, so 4 followers race. Each follower's timer fires at a random time; a candidate's vote request reaches the others 5 ms later; a follower grants the earliest request that reaches it before its own timer fires, otherwise it votes for itself. We count how often someone gets 3 votes in the very first round.

import random

def first_round_winner(timeouts, delay, majority):
    """One term: every follower whose timer fires becomes a candidate and votes for itself.
    A RequestVote from candidate c reaches node n at timeouts[c] + delay. Node n grants it
    only if the vote arrives before n's own timer fires (n has not voted yet this term);
    among several arriving requests, n grants the earliest one."""
    n = len(timeouts)
    votes = [0] * n
    for voter in range(n):
        arrivals = [(timeouts[c] + delay, c) for c in range(n) if c != voter]
        first_arrival, c = min(arrivals)
        if first_arrival < timeouts[voter]:
            votes[c] += 1              # voted for the earliest candidate it heard from
        else:
            votes[voter] += 1          # its own timer fired first: votes for itself
    return any(v >= majority for v in votes)

random.seed(42)
TRIALS, SURVIVORS, MAJORITY, DELAY_MS = 100_000, 4, 3, 5   # 5-node cluster, leader just died
for lo, hi in [(150, 150.5), (150, 160), (150, 300)]:
    wins = sum(first_round_winner([random.uniform(lo, hi) for _ in range(SURVIVORS)],
                                  DELAY_MS, MAJORITY) for _ in range(TRIALS))
    print(f"timeouts uniform in [{lo}, {hi}] ms: first-round leader in {wins / TRIALS:.1%} of trials")

Output:

timeouts uniform in [150, 150.5] ms: first-round leader in 0.0% of trials
timeouts uniform in [150, 160] ms: first-round leader in 31.2% of trials
timeouts uniform in [150, 300] ms: first-round leader in 99.4% of trials

Reading it: when every follower uses nearly the same timeout, they all become candidates before any vote request lands, and every round splits. A 10 ms spread only rescues about a third of first rounds, while the 150 ms window from the paper makes a clean first-round win the norm. The rule of thumb behind this is the Raft timing requirement: broadcast time (one round trip plus disk write) must be much smaller than the election timeout, which in turn must be much smaller than the mean time between server failures. The model is deliberately simple (equal logs, fixed delay, no message loss), so treat the percentages as illustrating the mechanism, not as a prediction for a real network.

Trade-offs worth naming

• Shorter timeout, faster failover, more false elections. A short timeout detects a dead leader sooner but misfires on transient slowness. Longer timeouts are safer for noisy networks at the cost of seconds of write unavailability after a real crash.
• Safety never depends on the timers. Randomized timeouts only affect liveness (whether a leader eventually emerges). The one-vote-per-term rule and majority requirement are what guarantee at most one leader per term, however badly the timers behave.

Practical pitfalls when implementing leader election

1. Not persisting currentTerm and votedFor before replying. Both must be written to stable storage (durable storage, such as disk, that survives a crash or restart, unlike volatile memory) and fsynced (forced to complete that physical write before replying, rather than just handed to a write cache that a crash could lose) before a vote is granted. If a server votes, crashes and restarts with its vote forgotten, it can vote again in the same term and two candidates can each assemble a "majority", which means two leaders in one term.
2. Resetting the election timer on the wrong events. The timer should reset when you receive a valid AppendEntries from the current leader, when you start an election, and when you grant a vote. Resetting it on every incoming RequestVote (including ones you reject) lets a server with a stale log keep everyone else from ever timing out, so the cluster never elects anyone.
3. Using a fixed timeout, or not re-randomizing it. The simulation above shows the result: repeated split votes. Draw a fresh random value for every election.
4. Timeouts that are too tight for the real environment. If a leader's garbage-collection pause (many language runtimes periodically freeze the whole process for a moment to reclaim memory; nothing, including heartbeats, gets sent while it is frozen) or a slow fsync is longer than the election timeout, followers depose a healthy leader, causing leadership churn and write unavailability. Size the timeout from measured disk and network latency, not from the paper's default.
5. Disruptive rejoining servers. A server cut off from the cluster keeps timing out and incrementing its term. When it reconnects, its high term forces the working leader to step down even though it cannot win (its log is behind). Production implementations add a Pre-Vote phase: a would-be candidate first asks whether it could win, without incrementing its term, and only campaigns for real if a majority says yes.

Direct answer

Without snapshots a Raft log (the replicated command log of Raft, a leader-based consensus protocol) grows forever: disk fills, a restarted node must replay every entry since the cluster was born, and a new or far-behind follower can only be caught up by resending all of history. A snapshot captures the state machine (the application's actual data, produced by executing the committed log in order, e.g. a key-value map) at some log index, after which every entry up to that index can be deleted (log compaction). The catch is that the leader may have discarded entries a lagging follower still needs, so it sends the snapshot itself with InstallSnapshot. The follower must then fit the snapshot together with AppendEntries messages that may arrive before, after, or overlapping it, and its apply loop must jump forward to the snapshot point without ever replaying or rolling back state.

Terms

• Log entry: a command with its index (position) and term (the leadership period it was created in).
• Commit index: the highest index known to be stored on a majority, so safe to apply.
• Applied index (lastApplied): the highest index actually executed against the local state machine.
• AppendEntries: the RPC a Raft leader uses to replicate new log entries to followers (and, when sent empty, as a heartbeat).
• Snapshot metadata: lastIncludedIndex and lastIncludedTerm, the index and term of the last entry the snapshot covers. The follower needs the term so the next AppendEntries consistency check (which compares the term of the entry just before the new ones) still works after the entry itself is deleted.

Why snapshots are necessary

Each server snapshots independently, usually when its log passes a size threshold. Snapshots only cover committed, applied entries, so they never contain anything that could later be overwritten.

InstallSnapshot, step by step (follower side)

1. Reject if the leader's term is stale; otherwise reset the election timer (the snapshot counts as contact from the leader).
2. Stale snapshot check: if lastIncludedIndex <= commitIndex, the follower already has at least this much committed state. Ignore it. Installing it would roll the state machine back.
3. If the follower's log has an entry at lastIncludedIndex with the same term, keep the entries after it: they may be newer entries that already arrived via pipelined AppendEntries (the leader sends several AppendEntries without waiting for each one's reply, so they can arrive, or be processed, out of the order they were sent). Otherwise discard the whole log.
4. Replace the state machine with the snapshot, and set commitIndex and lastApplied to lastIncludedIndex.
5. Persist the snapshot and the new log start before replying, so a crash does not lose it.

Interaction with in-flight AppendEntries

The leader typically pipelines messages, so a follower can receive them out of order relative to the snapshot:

• AppendEntries older than the snapshot (its previous-entry index is below lastIncludedIndex): the prefix up to the snapshot is already covered. Trim those entries, treat the snapshot point as the matching previous entry, and append the rest. Rejecting the message would force a needless retry; blindly appending would corrupt indexes.
• AppendEntries that arrived before the snapshot, extending past lastIncludedIndex: step 3 keeps them if the terms match at the snapshot point.
• Leader side: after sending a snapshot, the leader sets that follower's nextIndex (the log position the leader will send that follower next) to lastIncludedIndex + 1 and resumes normal replication once the follower acknowledges.

Interaction with state-machine application

• The applier (the loop that executes committed entries) and the snapshot installer both change lastApplied, so they must be serialised: typically the installer hands the snapshot to the same apply thread as a special message, which keeps "apply entry 99" from running after "install snapshot at 100".
• After installing, the applier resumes at lastIncludedIndex + 1, never at an entry the snapshot already contains.
• On the node taking a snapshot, the snapshot must reflect exactly the state at lastApplied, taken while applies continue: use a copy-on-write structure (one where a write creates a new version instead of overwriting data in place, so a reader keeps seeing a stable version while writes continue) or a consistent read view (a snapshot-style read straight from storage that is guaranteed to reflect a single instant, even while other writes proceed), then truncate the log only after the snapshot is safely on disk.

Worked example

A follower installs a snapshot at index 100 (term 3) containing x = 7, y = 2. Then a delayed pipelined AppendEntries arrives whose previous-entry index is 98, carrying entries 99 to 102, with the leader's commit index at 101. Later a duplicate of the same snapshot arrives. The sketch below implements steps 2 to 4 and the trimming rule and runs that sequence.

class Follower:
    def __init__(self):
        self.snap_index, self.snap_term, self.snap_state = 0, 0, {}
        self.log = []                 # entries after the snapshot: (term, (key, value))
        self.commit = self.applied = 0
        self.state = {}

    def last_index(self):
        return self.snap_index + len(self.log)

    def term_at(self, i):
        if i == self.snap_index:
            return self.snap_term
        if self.snap_index < i <= self.last_index():
            return self.log[i - self.snap_index - 1][0]
        return None                   # compacted away or not present

    def install_snapshot(self, idx, term, state):
        if idx <= self.commit:        # stale or duplicate: we already have this much
            return "ignored (already committed past it)"
        if self.term_at(idx) == term: # our log agrees at idx: keep the suffix
            self.log = self.log[idx - self.snap_index:]
        else:
            self.log = []             # conflicting or too short: discard everything
        self.snap_index, self.snap_term, self.snap_state = idx, term, dict(state)
        self.state = dict(state)      # reset the state machine to the snapshot
        self.commit = self.applied = idx
        return f"installed at {idx}, kept {len(self.log)} later entries"

    def append_entries(self, prev_idx, prev_term, entries, leader_commit):
        if prev_idx < self.snap_index:
            # Entries up to snap_index are already covered by the snapshot:
            # trim that prefix and treat the snapshot point as the match.
            skip = self.snap_index - prev_idx
            entries, prev_idx, prev_term = entries[skip:], self.snap_index, self.snap_term
        if self.term_at(prev_idx) != prev_term:
            return False
        for k, e in enumerate(entries, start=prev_idx + 1):
            if self.term_at(k) not in (None, e[0]):
                self.log = self.log[:k - self.snap_index - 1]   # drop conflicting suffix
            if k > self.last_index():
                self.log.append(e)
        self.commit = max(self.commit, min(leader_commit, prev_idx + len(entries)))
        self.apply()
        return True

    def apply(self):
        while self.applied < self.commit:
            self.applied += 1
            key, value = self.log[self.applied - self.snap_index - 1][1]
            self.state[key] = value


f = Follower()
print(f.install_snapshot(100, 3, {"x": 7, "y": 2}))
# A delayed AppendEntries from before the snapshot overlaps it (entries 99..102).
old = [(3, ("x", 6)), (3, ("x", 7)), (3, ("y", 9)), (3, ("z", 1))]
print("overlapping append ok:", f.append_entries(98, 3, old, leader_commit=101),
      "| last index", f.last_index(), "| applied", f.applied, "| state", f.state)
# A duplicate of the same snapshot arrives late.
print(f.install_snapshot(100, 3, {"x": 7, "y": 2}), "| state", f.state)

Output:

installed at 100, kept 0 later entries
overlapping append ok: True | last index 102 | applied 101 | state {'x': 7, 'y': 9}
ignored (already committed past it) | state {'x': 7, 'y': 9}

Entries 99 and 100 were trimmed (already inside the snapshot), 101 and 102 were appended, and 101 was applied (y = 9). Without the stale-snapshot check in step 2, the duplicate would have reset y back to 2, silently undoing a committed write.

Trade-offs and pitfalls

• Snapshot frequency: frequent snapshots cost disk bandwidth and CPU; rare ones mean long restarts and more InstallSnapshot traffic. Base the threshold on log size, not a timer.
• Large snapshots: send them in chunks with an offset, and throttle so snapshot transfer does not starve AppendEntries and heartbeats to other followers.
• Truncating too eagerly: if a follower is only slightly behind, the leader would rather replay a few entries than ship the whole state. Keep a short tail of entries after the snapshot point.
• Common implementation bugs: installing a stale snapshot (state rollback), applying an entry at an index already covered by the snapshot, and computing log positions without subtracting the snapshot offset.