Leader Election

Metadata

1. Overview

What problem does it solve?

In a distributed system, you often have 5 identical servers running the exact same code. This is great for handling massive read traffic (stateless). But what if the task is stateful or requires absolute coordination?

• E.g., A cron job that charges credit cards at midnight. If all 5 servers run it, the user is charged 5 times.
• E.g., A database cluster that needs to accept a WRITE. If 5 servers all accept different writes at the same time, the data is hopelessly corrupted.

Leader Election ensures that out of N identical nodes, exactly ONE node is designated as the "Leader" (or Master/Primary) at any given time. The Leader makes the authoritative decisions (or runs the cron job), and the other nodes wait as "Followers". If the Leader dies, the Followers automatically elect a new one.

What breaks without it?

• Split-Brain: Two nodes both think they are the leader. They both accept writes, resulting in two diverging copies of the database that cannot be merged.
• Duplicate Execution: A distributed cron job runs multiple times, spamming users with duplicate emails or duplicate charges.

2. Motivation

Before the cloud, High Availability meant buying two massive servers: one active, one passive. If the active one died, a human manually flipped a network switch.

When Google started building massive clusters of cheap, unreliable computers (MapReduce/GFS), they needed a way for computers to decide amongst themselves who was in charge without human intervention. They built Chubby, a distributed lock service. Yahoo later open-sourced a clone of Chubby called ZooKeeper, which became the backbone of almost all Hadoop-era Big Data systems (Kafka, HBase).

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The Election Lifecycle

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff'}}}%%
stateDiagram-v2
    direction LR
    
    state "FOLLOWER" as Follower
    state "CANDIDATE" as Candidate
    state "LEADER" as Leader

    Follower --> Candidate : Leader Heartbeat Timeout
    Candidate --> Leader : Wins Election
    Candidate --> Follower : Loses Election
    Leader --> Follower : Node crashes / Partition
    Leader --> Leader : Renew Lease (Heartbeat)

1. All nodes start as Followers.
2. They realize there is no Leader. They become Candidates and race to acquire a lock (e.g., creating an ephemeral node in ZooKeeper or writing a key in Redis).
3. The winner becomes the Leader. It immediately begins sending heartbeats to maintain its lock.
4. The losers go back to being Followers and watch the lock.
5. If the Leader crashes, its lock expires. The Followers notice and trigger a new election.

6. Internal Working

The Lease Mechanism

How do you guarantee only one Leader exists? You use an external CP (Consistent + Partition Tolerant) system like ZooKeeper, etcd, or Redis to hold a Lease (a time-bound lock).

1. Node A writes SET leader_key "Node A" EX 5 NX (Set if Not eXists, expire in 5 seconds).
2. It succeeds! Node A is the leader.
3. Every 3 seconds, Node A runs a background thread to update the expiration back to 5 seconds. (Heartbeat).
4. Node B tries to write SET leader_key "Node B" EX 5 NX. It fails because the key exists. Node B remains a follower.
5. Node A's motherboard catches fire. It stops sending heartbeats.
6. 5 seconds later, Redis automatically deletes leader_key.
7. Node B tries again. It succeeds! Node B is the new leader.

The Split-Brain Danger

What if Node A doesn't die, but simply experiences a 6-second Garbage Collection pause?

1. Node A pauses. Its lease expires in Redis.
2. Node B acquires the lease and becomes the Leader.
3. Node A finishes GC. It still thinks it's the leader!
4. Now both Node A and Node B are writing data to the database. SPLIT BRAIN.

Solution: Fencing Tokens. When Node B takes over, the lease manager (ZooKeeper) increments a global version number (e.g., Epoch = 2). Node B writes to the database with Epoch=2. When Node A wakes up and tries to write with Epoch=1, the database rejects it.

7. Implementation

Why Go? Go's channels and goroutines make writing concurrent background tick mechanisms (heartbeats) and lock monitoring exceptionally clean. We will mock a Redis SETNX lock to demonstrate the core Lease loop.

/*
022 - Leader Election
A Go simulation of a Lease-based Leader Election algorithm.
Multiple nodes compete for a mock distributed lock (Redis).
*/
package main

import (
	"fmt"
	"math/rand"
	"sync"
	"time"
)

// ── 1. The Mock Distributed Lock (e.g. Redis, etcd) ──

type MockRedis struct {
	mu           sync.Mutex
	leaderID     string
	expiryTime   time.Time
}

// SetNX (Set if Not eXists) or Renew if already the owner
func (r *MockRedis) TryAcquireOrRenew(nodeID string, ttl time.Duration) bool {
	r.mu.Lock()
	defer r.mu.Unlock()

	now := time.Now()

	// 1. If lock is free or expired, acquire it!
	if r.leaderID == "" || now.After(r.expiryTime) {
		r.leaderID = nodeID
		r.expiryTime = now.Add(ttl)
		return true
	}

	// 2. If I already own it, renew it!
	if r.leaderID == nodeID {
		r.expiryTime = now.Add(ttl)
		return true
	}

	// 3. Someone else owns it and it hasn't expired. I failed.
	return false
}


// ── 2. The Node (Candidate) ──

type Node struct {
	id       string
	redis    *MockRedis
	isLeader bool
}

func (n *Node) StartElectionLoop() {
	// The Lease TTL is 5 seconds. We heartbeat every 2 seconds.
	leaseTTL := 5 * time.Second
	ticker := time.NewTicker(2 * time.Second)

	for range ticker.C {
		// Attempt to acquire or renew the lock
		success := n.redis.TryAcquireOrRenew(n.id, leaseTTL)

		if success && !n.isLeader {
			fmt.Printf("👑 [%s] I WON THE ELECTION! I am the new Leader.\n", n.id)
			n.isLeader = true
			n.DoLeaderWork()
		} else if success && n.isLeader {
			fmt.Printf("   [%s] Renewed leader lease.\n", n.id)
		} else if !success && n.isLeader {
			fmt.Printf("💀 [%s] I LOST MY LEASE! Stepping down to Follower.\n", n.id)
			n.isLeader = false
		} else {
			// I am a follower and someone else has the lock. Do nothing.
		}
	}
}

func (n *Node) DoLeaderWork() {
	// Only the leader runs this critical task
	fmt.Printf("   [%s] Doing critical database writes...\n", n.id)
}


// ── 3. Test Harness ──

func main() {
	redis := &MockRedis{}
	
	nodeA := &Node{id: "Node-A", redis: redis}
	nodeB := &Node{id: "Node-B", redis: redis}
	nodeC := &Node{id: "Node-C", redis: redis}

	// Start all nodes asynchronously. They will race for the lock!
	// We add a tiny random sleep so they don't hit it exactly at the same microsecond
	go func() { time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond); nodeA.StartElectionLoop() }()
	go func() { time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond); nodeB.StartElectionLoop() }()
	go func() { time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond); nodeC.StartElectionLoop() }()

	time.Sleep(7 * time.Second)

	fmt.Println("\n🔥 INJECTING FAILURE: The current leader crashes! (Simulated by stopping its heartbeat)")
	
	// We simulate a crash by artificially changing the Redis lock owner to a dead node
	// so the current leader's next renewal will fail.
	redis.mu.Lock()
	redis.leaderID = "Dead-Node"
	redis.expiryTime = time.Now().Add(-1 * time.Second) // Force expire
	redis.mu.Unlock()

	// Wait to watch the Followers notice the expired lock and elect a new leader
	time.Sleep(7 * time.Second)
	fmt.Println("\nSimulation Complete.")
}

Sample Output

👑 [Node-B] I WON THE ELECTION! I am the new Leader.
   [Node-B] Doing critical database writes...
   [Node-B] Renewed leader lease.
   [Node-B] Renewed leader lease.
   [Node-B] Renewed leader lease.

🔥 INJECTING FAILURE: The current leader crashes! (Simulated by stopping its heartbeat)
💀 [Node-B] I LOST MY LEASE! Stepping down to Follower.
👑 [Node-C] I WON THE ELECTION! I am the new Leader.
   [Node-C] Doing critical database writes...
   [Node-C] Renewed leader lease.
   [Node-C] Renewed leader lease.

Simulation Complete.

Notice how Node-B successfully held the lease, but when it "crashed" and missed its renewal window, Node-C instantly noticed the lock was free and took over.

8. Complexity

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. What is Split-Brain and how does Leader Election attempt to solve it? Hint: Split-brain is when a cluster fractures and two nodes both think they are the leader, resulting in corrupted data. Leader Election solves this by using a centralized, atomic lock (like ZooKeeper) that only one node can hold at a time.

2. Why do we use Leases (TTL) instead of permanent locks? Hint: If Node A acquires a permanent lock and then crashes, the lock is held forever, and the cluster is permanently deadlocked. A Lease automatically expires if the leader doesn't actively heartbeat.

3. What is a Fencing Token? Hint: A monotonically increasing integer (Epoch) granted by the lock service. If a "zombie" leader wakes up from a GC pause and tries to write to the database using an old token (Epoch 1), the database rejects it because it already accepted writes from the new leader (Epoch 2).

13. Used By (Downstream Blocks)

• 023 Distributed Consensus (Raft/Paxos) — The fundamental mathematical algorithms that things like ZooKeeper and etcd use under the hood to manage the locks that enable Leader Election.
• 039 SSTable & LSM Tree — Databases using LSM trees often require a designated leader to manage compactions and metadata.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Implement Fencing Tokens

Modify the Go code. When a node wins the election, MockRedis should return an epoch integer (incremented every time the lock changes hands). DoLeaderWork() should print this epoch.

Exercise 2: Graceful Step-down

Add a mechanism where a node can voluntarily give up leadership (e.g., if it receives a SIGTERM from Kubernetes to shut down). It should actively delete its lock in Redis rather than waiting 5 seconds for it to expire, allowing another node to take over instantly.

Website Metadata