Leader Election - Complete Deep Dive

Prerequisites: Distributed Locking, CAP Theorem Used in: Job Scheduler, Key-Value Store

What is Leader Election?

Leader election is the process of choosing one node in a distributed system to act as the coordinator (leader) while others are followers. The leader makes decisions, assigns work, or handles writes — preventing conflicts from multiple nodes acting independently.

Real-world analogy: A classroom group project. Without a leader, everyone works on the same section (conflicts) or nobody does certain parts (gaps). Electing a team lead means one person assigns tasks, tracks progress, and resolves conflicts. If the lead is absent, the group picks a new one.

Without leader:
  Node A: "I'll process job 42"
  Node B: "I'll process job 42"     ← Duplicate work!
  Node C: "I'll process job 42"

With leader:
  Leader: "Node A → job 42, Node B → job 43, Node C → job 44"
  Followers: execute assigned work only

Why Do We Need a Leader?

Key use cases:

• Database primary (handles all writes, replicates to followers)
• Job scheduler coordinator (assigns tasks to workers)
• Distributed lock manager (one authority)
• Message queue partition leader (handles reads/writes for partition)

How It Works

The Lifecycle

flowchart TD
    A[Follower] -->|"election timeout"| B[Candidate]
    B -->|"lost vote"| A
    B -->|"won majority"| C[Leader - active]
    C -->|"leader dies"| A
    
    classDef service fill:#10b981,stroke:#065f46,color:#fff
    classDef async fill:#818cf8,stroke:#4338ca,color:#fff
    classDef data fill:#fbbf24,stroke:#92400e,color:#000
    class A service
    class B async
    class C data

Leader maintains position via heartbeats. If heartbeats stop → followers trigger new election.

Approaches to Leader Election

1. Bully Algorithm (Simplest)

The node with the highest ID (or priority) always becomes leader.

Nodes: [N1, N2, N3, N4, N5]  (N5 = highest priority)

N5 is leader. N5 crashes.

Step 1: N3 detects N5 is down (missed heartbeat)
Step 2: N3 sends ELECTION to all higher nodes (N4, N5)
Step 3: N4 responds "I'm alive, I'll take over"
        N5 doesn't respond (dead)
Step 4: N4 sends ELECTION to N5 (no response)
Step 5: N4 declares itself leader
Step 6: N4 sends COORDINATOR message to all: "I'm the new leader"

Timeline:
  N3: "Election!" ──▶ N4: "I'm here, back off"
                       N4: "Election!" ──▶ N5: (dead, no response)
                       N4: "I am the leader now."

Pros: Simple to implement. Deterministic. Cons: Highest-ID node always wins (even if it’s slow). Frequent elections if top node is flaky.

2. Raft Consensus (Industry Standard)

Leader elected by majority vote. Uses terms (epochs) and randomized timeouts to prevent conflicts.

```mermaid
flowchart TD
    A["1. Election timeout expires<br/>random 150-300ms"] --> B["2. Follower becomes CANDIDATE"]
    B --> C["3. Increments term - votes for itself"]
    C --> D["4. Requests votes from all nodes"]
    D --> E{"5. Nodes vote YES if<br/>not voted in term AND<br/>log is up-to-date"}
    E -->|"Majority"| F["6. Becomes LEADER"]
    F --> G["7. Sends heartbeats"]

    classDef service fill:#10b981,stroke:#065f46,color:#fff
    classDef async fill:#818cf8,stroke:#4338ca,color:#fff
    class A,B,C,D,F,G service
    class E async

Example with 5 nodes: Term 1: N1 is leader, sending heartbeats Term 1: N1 crashes (heartbeats stop) …150ms pass… Term 2: N3’s election timeout fires first (random!) Term 2: N3 → Candidate, votes for itself (1/5) Term 2: N3 asks N2, N4, N5 for votes Term 2: N2 votes YES (2/5), N4 votes YES (3/5) ← MAJORITY! Term 2: N3 is now leader Term 2: N3 sends heartbeats to all

**Why randomized timeouts?** Prevents all nodes from starting elections simultaneously (which would split votes and delay election).

---

### 3. ZooKeeper Ephemeral Nodes

Uses ZooKeeper's coordination primitives. Nodes create ephemeral sequential znodes — lowest sequence number becomes leader.

ZooKeeper: /election/ ├── node_0000000001 (created by Server A) ← LEADER (lowest) ├── node_0000000002 (created by Server B) └── node_0000000003 (created by Server C)

How it works:

1. Each server creates an ephemeral sequential znode under /election/
2. Server checks: “Am I the lowest sequence number?”
   • YES → I am the leader
   • NO → Watch the node just before me (not all nodes!)
3. If leader crashes → ephemeral node auto-deleted by ZooKeeper
4. Next node in sequence sees deletion → becomes new leader

Ephemeral = auto-deleted when session dies (server crash/disconnect) Sequential = ZooKeeper assigns incrementing numbers

Server A crashes: /election/ ├── node_0000000001 ← DELETED (session expired) ├── node_0000000002 (Server B was watching 001) │ → B is now lowest → B is leader! └── node_0000000003 (Server C watches 002, not affected yet)

---

## Comparison Table

| Feature | Bully | Raft | ZooKeeper |
|---|---|---|---|
| Complexity | Low | High | Medium (uses ZK) |
| Consistency | Weak | Strong (linearizable) | Strong (ZAB protocol) |
| Speed of election | Fast | 150-300ms | Fast (session timeout) |
| Split-brain safe? | No | Yes (majority quorum) | Yes (majority quorum) |
| External dependency | None | None | Requires ZK cluster |
| Replication | Not included | Built-in log replication | Separate from election |
| Used by | Simple systems | etcd, CockroachDB, TiKV | Kafka, HBase, Hadoop |

---

## Split-Brain Problem

The most dangerous failure in leader election: **two nodes both think they're leader**.

```mermaid
flowchart LR
    subgraph PartA["Partition A"]
        N1["N1 - leader<br/>thinks its still leader"]
        N2["N2"]
    end
    subgraph PartB["Partition B"]
        N3["N3 - elected as new leader"]
        N4["N4"]
        N5["N5"]
    end

    PartA -.->|"NETWORK PARTITION<br/>no communication"| PartB

    classDef service fill:#10b981,stroke:#065f46,color:#fff
    classDef async fill:#818cf8,stroke:#4338ca,color:#fff
    class N1,N3 async
    class N2,N4,N5 service

DANGER: Two leaders accepting writes → data corruption!

Solutions to Split-Brain

1. Majority Quorum (Raft/ZooKeeper approach)

5 nodes total. Need 3+ votes to be leader.
Partition A: 2 nodes → can't get majority → old leader steps down
Partition B: 3 nodes → gets majority → elects new leader
Only one partition can have a leader at any time!

2. Fencing Tokens

Each leader gets an incrementing token (epoch/term).
Leader 1: token = 5
Leader 2: token = 6 (elected after partition)

All writes must include the token.
Storage rejects writes with token < current max.
Even if old leader (token=5) sends a write, storage rejects it.

3. Lease-Based Leadership

Leader holds a time-limited lease (e.g., 30 seconds).
Must renew before expiry. If network partition prevents renewal,
leader's lease expires and it must step down.
New leader elected only after old lease expires.

When to Use / When NOT to Use

Use Leader Election When:

• Database replication — one primary handles writes
• Job scheduling — one coordinator assigns tasks
• Distributed locks — one authority grants locks
• Consensus — one node proposes and commits decisions
• Cache invalidation — one node coordinates cache coherence

When NOT to Use:

• Stateless services — no coordination needed, just load balance
• Read-heavy workloads — all replicas can serve reads
• Event-driven architectures — consumers are independent
• When single leader is a bottleneck — consider leaderless (Cassandra)
• Simple systems — if you have 2-3 nodes, a simpler approach (manual failover) might suffice

Real-World Examples

Common Interview Questions

Q: “How does your job scheduler ensure only one node processes each job?” A: Use leader election. One node is elected leader (via ZooKeeper or Raft). The leader is responsible for assigning jobs to workers. Workers only execute jobs assigned to them. If the leader crashes, a new one is elected and takes over the assignment duty. Jobs in progress continue on workers unaffected.

Q: “What happens during a network partition?” A: With quorum-based election (Raft/ZooKeeper), only the partition with majority can have a leader. The minority partition’s old leader will fail to get heartbeat acknowledgments and step down. No split-brain. The minority partition is unavailable for writes until the partition heals.

Q: “How fast is leader election? What’s the downtime?” A: Typically 1-10 seconds. Raft: election timeout is 150-300ms, but detecting leader failure takes 1-3 missed heartbeats (seconds). ZooKeeper: session timeout (default 30s, tunable to 2-5s). During election, the system is unavailable for writes. Reads from followers may still work.

Q: “Raft vs ZooKeeper — which would you choose?” A: If building a new distributed system from scratch — embed Raft (no external dependency, used by etcd, CockroachDB). If already running ZooKeeper in the infra (Kafka, Hadoop ecosystem) — use ZK for leader election (simpler to implement, battle-tested). ZooKeeper is easier to use but adds operational complexity.