Skip to content

Leader Election#

Problem statement (interviewer prompt)

A cluster of N stateless replicas must elect exactly one leader to serialize a critical operation (e.g. compaction, schema migration, primary-write coordinator). The election must terminate within seconds of any failure and never produce two leaders simultaneously.

Pick a single coordinator from a group of peers, detect when it dies, and elect a replacement. Implementations rely on an existing consensus primitive (Raft/Paxos via ZooKeeper, etcd, Consul) or run consensus inline.

flowchart LR
  N1[Node 1] -->|TryAcquire /leader| ZK[(ZooKeeper / etcd<br/>session lock)]
  N2[Node 2] -->|TryAcquire /leader| ZK
  N3[Node 3] -->|TryAcquire /leader| ZK
  ZK -->|granted| N1
  N1 -. heartbeat / lease .-> ZK
  N2 -.watch.-> ZK
  N3 -.watch.-> ZK

    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    class N1,N2,N3 service;
    class ZK datastore;

The winner holds a time-bounded lease; followers watch and trigger a new election when the lease expires.

A leader election protocol must satisfy two properties:

  • Safety: at most one node believes itself the leader at any time (no split brain).
  • Liveness: when the leader dies, a new one is chosen within a bounded time.

Patterns#

1. ZooKeeper ephemeral nodes#

sequenceDiagram
  participant N1 as Node 1
  participant N2 as Node 2
  participant ZK as ZooKeeper
  N1->>ZK: create /leader/n_ ephemeral+sequential
  ZK-->>N1: /leader/n_0001
  N2->>ZK: create /leader/n_ ephemeral+sequential
  ZK-->>N2: /leader/n_0002
  N1->>ZK: list /leader
  ZK-->>N1: [0001, 0002] -> I am leader (lowest)
  N2->>ZK: watch /leader/n_0001
  Note over N1: crash -> session expires -> n_0001 deleted
  ZK-->>N2: watch fires
  N2->>ZK: list /leader -> n_0002 is lowest -> I am leader
  • Ephemeral node = tied to a client session; auto-removed on disconnect.
  • "Lowest sequence wins" avoids the herd effect: each node only watches its predecessor.

2. etcd / Consul lease#

session = etcd.lease(ttl=10)
key = etcd.put("/leader", node_id, lease=session)
# refresh in a background thread every 3s
  • A lease is a TTL-bound association.
  • Whoever wins the compare-and-swap if key absent then put owns leadership until the lease expires.

3. Inline Raft (no external dependency)#

When the service already uses a Raft library (etcd-raft, hashicorp/raft), elect the Raft leader and reuse it as the application leader. Saves a dependency but couples leadership to log replication tempo.

Classical algorithms#

Algorithm How Use
Bully Highest-id node wins; broadcasts "I'm leader" Small clusters, in-process
Ring Pass token; highest-seen id wins Token-ring networks
Raft / Paxos Quorum vote Anything requiring linearizable decisions
ZK recipe Sequential ephemeral nodes Heavy ZooKeeper deployments

Split-brain and fencing tokens#

A lease can expire while the old leader is still alive (long GC pause, network partition). To stop the old leader from corrupting data, hand out a monotonically increasing fencing token at election:

sequenceDiagram
  participant L1 as Leader (token=42)
  participant DB as Storage
  participant L2 as New leader (token=43)
  L1->>DB: write x, token=42
  Note over L1: GC pause, lease expires
  L2->>DB: write y, token=43
  L1->>DB: write x', token=42
  DB-->>L1: 409 - stale token

Storage rejects any operation with a token less than the highest it has seen. Used in HDFS, Kafka, and Chubby.

Lease tuning#

Setting Effect
Long lease (30s) Stable leader, slow failover
Short lease (3s) Fast failover, more election churn under jitter
Refresh interval Must be < lease/2 to survive one missed refresh
Clock skew tolerance Add network RTT × 2 to lease

How leader election composes#

flowchart TB
  LE((Leader<br/>election))
  RAFT[Consensus Raft/Paxos<br/>safety primitive]
  DL[Distributed lock<br/>same lease mechanism]
  GOS[Gossip protocol<br/>membership view]
  SD[Service discovery<br/>publishes current leader]
  FEN[Fencing token<br/>storage rejects stale]
  RAFT --> LE
  GOS --> LE
  LE --> SD
  LE --> DL
  LE --> FEN

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class LE service;
    class RAFT,DL,GOS,SD,FEN datastore;

Glossary & fundamentals#

Tag Concept What it is Page
HLD Consensus Raft Paxos underlying agreement protocol consensus-raft-paxos
HLD Distributed lock mutual exclusion across nodes distributed-lock
HLD Gossip protocol how membership view is built gossip-protocol
HLD Service discovery locating the current leader service-discovery

Quick reference#

Properties required#

  • Safety: at most one leader at a time.
  • Liveness: a new leader emerges in bounded time after failure.

Common implementations#

Approach Tool
Ephemeral + sequential ZooKeeper recipe
Lease + watch etcd, Consul
Inline Raft etcd-raft, hashicorp/raft
Bully algorithm small in-process clusters

ZK recipe (sketch)#

  1. create /leader/n_ EPHEMERAL_SEQUENTIAL
  2. List children; you're leader if your seq is lowest.
  3. Otherwise watch the seq immediately below you.

Fencing tokens#

  • Monotonically increasing on every election.
  • Storage rejects stale tokens → prevents split-brain corruption.

Lease tuning#

Setting Recommendation
Lease TTL 10-30s typical
Refresh interval < TTL/2
Detection time ~TTL worst case

Pitfalls#

  • Long GC pause can pause heartbeats - use fencing tokens
  • Don't trust wall-clock; use monotonic clock for refresh timing
  • Don't elect over network you also rely on for the lease

Refs#

  • Burrows - Chubby (OSDI 2006)
  • ZooKeeper and etcd recipes
  • Kleppmann - How to do distributed locking

FAQ#

What is leader election?#

Leader election picks exactly one node from a group to coordinate work like writes, compactions, or schema changes. A new election runs when the leader fails.

How does Raft elect a leader?#

Each node has a randomized election timeout. On timeout it becomes a candidate, asks for votes, and a node that wins a quorum becomes leader for that term.

What is split brain and how is it prevented?#

Split brain is when two nodes both think they are leader. Quorum-based elections, monotonic leader terms, and fenced storage tokens prevent two writers from racing.

What is a lease in leader election?#

A lease is a time-bounded grant. The leader must renew before it expires, and a successor cannot act until the old lease is provably expired, avoiding two active leaders.

Which tools are used in production?#

etcd, ZooKeeper, and Consul provide consensus-backed locks. Raft, Multi-Paxos, or ZAB run underneath. Apps often just use a lock primitive instead of running consensus themselves.

Further reading#