Discover how distributed systems automatically recover from failures without human intervention. Master leader election algorithms that make systems self-healing and highly available.
Save
Complete lesson & earn 250 PX
EXERCISE
1Understanding why simple monitoring creates an infinite loop. This fundamental problem leads us to leader election.
Save
EXERCISE
2Learn the leader-worker pattern that breaks the infinite monitoring loop. Understand how systems automatically promote workers to leaders.
Save
EXERCISE
3Explore the algorithms that enable automatic leader selection. From simple Bully algorithm to production-grade Raft consensus.
Save
EXERCISE
4See how major companies implement leader election at scale. Learn from production deployments handling millions of requests.
Save
EXERCISE
5Leader election is powerful but not always the right choice. Understand the trade-offs, failure modes, and alternatives.
Save
You have 3 servers behind a load balancer. They serve user requests.
Problem: Servers crash sometimes. When one crashes, you need to spin up a replacement.
Solution: Create an Orchestrator component.
Orchestrator watches your API servers.
Every 10 seconds: Ping each . Is it healthy?
Server responds? Great, do nothing.
Server does not respond? Server is dead. Spin up new server. Add to load balancer.
Architecture:
[Orchestrator]
↓ monitors
[API Server 1] [API Server 2] [API Server 3]
↓ serve
[Users]
Perfect! Now your servers auto-recover.
New problem: What if the Orchestrator crashes?
Your API servers are down. Orchestrator is dead. Nobody spins up replacements. Complete outage.
Solution: Create Orchestrator Monitor to watch the Orchestrator!
New Architecture:
[Orchestrator Monitor]
↓ monitors
[Orchestrator]
↓ monitors
[API Server 1] [API Server 2] [API Server 3]
Great! Now if Orchestrator dies, Orchestrator Monitor restarts it.
Question: What if Orchestrator Monitor crashes?
Answer: Create Orchestrator Monitor Monitor to watch it!
Question: What if Orchestrator Monitor Monitor crashes?
Answer: Create Orchestrator Monitor Monitor Monitor...
You see the problem. This is infinite recursion. There is always another layer needed.
Without a base case, you need infinite layers.
In practice, companies try 2-3 layers then give up.
Result: The top layer still has no monitor. Single point of failure remains.
When that top layer fails: Human gets paged at 3 AM. Manual intervention required. High-availability promise broken.
Team does daily standups. Manager runs them.
Manager is on vacation. Who runs standup?
Bad approach: Hire a backup manager to monitor the manager. But what if backup manager is sick?
Good approach: Team members automatically decide among themselves who runs standup that day.
No hierarchy needed. The team self-organizes.
This is leader election.
Hierarchical monitoring assumes: Something at the top is always alive.
Reality: Everything fails eventually. Including the thing at the top.
What we need: A system where components monitor each other horizontally, not vertically.
When one component fails, others notice and elect a replacement from among themselves.
No infinite recursion. No human intervention. Self-healing.
Leader election is the base case that stops the infinite monitoring loop.
Instead of asking "Who monitors X?", we ask "How do peers elect a new X when it fails?"
This changes everything. We move from hierarchical monitoring (infinite recursion) to peer-based coordination (finite problem).
Understanding this philosophical shift is key to understanding distributed systems.
Instead of one Orchestrator, we have multiple Orchestrator instances.
One is the Leader. Others are Workers.
Architecture:
[Orchestrator Leader] ← Coordinates workers
↓
[Orchestrator Worker 1] [Orchestrator Worker 2] [Orchestrator Worker 3]
↓ each monitors
[API Servers]
Now we have redundancy and coordination.
Workers (Orchestrator Worker 1, 2, 3):
Do the actual monitoring work. Watch API servers. If API server crashes, spin up replacement.
Why multiple workers? Redundancy. If one worker crashes, others continue.
Leader (Orchestrator Leader):
Does NOT monitor API servers directly. Instead, monitors the workers.
If a worker crashes, Leader spins up a new worker.
Coordinates work distribution among workers (optional).
This is where leader election solves everything.
Scenario: Leader crashes at 2 AM.
Step 1: Workers notice. "Leader has not sent heartbeat for 30 seconds. Leader is dead."
Step 2: Workers initiate leader election among themselves.
Step 3: Election algorithm runs. One worker is chosen as new Leader.
Step 4: Chosen worker promotes itself to Leader role.
Step 5: Other workers recognize the new Leader.
Step 6: System continues operating normally.
Total downtime: 30-60 seconds. Fully automatic. No human intervention.
Key insight: Workers monitor each other through leader election.
No need for "Who monitors the leader?" because workers monitor the leader by being ready to replace it.
The recursion stops here.
uses this exact pattern.
Leader: Kubernetes Controller Manager (runs on master )
Workers: Kubernetes nodes running pods
What happens:
Leader manages cluster state. Schedules pods. Handles failures.
Leader node crashes? Another master node (worker) becomes leader through election.
Kubernetes keeps running. Pods keep traffic. Nobody gets paged.
This is why Kubernetes can achieve extremely high .
PostgreSQL with Patroni (high-availability setup):
Leader: Primary (handles writes)
Workers: Standby replicas
Primary database crashes?
No manual failover. No data (with synchronous ). Self-healing.
How do workers know leader is alive?
Leader sends periodic heartbeat: "I am alive!" message every 10 seconds.
Workers track last heartbeat time.
If 30 seconds pass without heartbeat: Leader is dead. Start election.
Why 30 seconds? Balance between:
Production systems typically use 15-60 second timeouts.
When leader dies, workers do this:
Election takes 5-15 seconds typically.
During election, system operates in degraded mode but does not crash.
Scenario: 3 workers, 1 leader.
Time 0:00: Leader crashes. Workers elect Worker 1 as new leader.
Time 0:05: Worker 2 crashes. New leader (Worker 1) notices. Spins up Worker 4.
Time 0:10: New leader (Worker 1) crashes. Workers 3 and 4 elect Worker 3 as leader.
System keeps healing itself. No human intervention needed.
As long as at least one worker survives, system recovers.
Before leader election: Human on-call gets paged. Logs in. Investigates. Manually restarts failed component. Takes 15-60 minutes.
With leader election: System detects failure. Elects new leader. Continues operating. Takes 30-60 seconds. Human learns about it in morning summary email.
This is the difference between 99.9% uptime and 99.99% uptime.
Self-healing systems enabled by leader election are the foundation of modern high-availability infrastructure.
Challenge: Multiple workers must agree on one leader. No central authority to decide.
Requirements:
Algorithms provide the rules for this coordination.
Core idea: Highest ID always becomes leader.
How it works:
Setup: 5 workers with IDs: 1, 2, 3, 4, 5. Worker 5 is current leader.
Leader (Worker 5) crashes.
Step 1: Worker 3 notices first. Sends "Election" message to workers with higher IDs (4, 5).
Step 2: Worker 4 responds: "I am alive and have higher ID. I will take over."
Step 3: Worker 4 sends "Election" message to Worker 5. No response (crashed).
Step 4: Worker 4 declares: "I am the leader now" (sends "Victory" message to all).
Step 5: All workers acknowledge Worker 4 as new leader.
Why "Bully"? Highest ID "bullies" its way to leadership.
Workers: [1] [2] [3] [4] [5-CRASHED]
Worker 3 detects failure:
3 → 4: "Election?"
3 → 5: "Election?" (no response)
Worker 4 responds:
4 → 3: "I have higher ID, I will handle this"
Worker 4 checks higher IDs:
4 → 5: "Election?" (no response)
Worker 4 declares victory:
4 → ALL: "I am leader"
Workers acknowledge:
1,2,3 → 4: "Acknowledged"
New leader: Worker 4
Pros:
Cons:
Best for: Small clusters, development environments, learning.
Used by: etcd, Consul, many distributed databases.
Core idea: Majority vote determines leader.
How it works:
Setup: 5 workers. Each worker has a term number (election round).
Leader crashes.
Step 1: Worker detects leader missing. Increments its term number. Becomes candidate.
Step 2: Candidate requests votes from all workers: "Vote for me in term 10!"
Step 3: Workers vote for first candidate they hear from in this term.
Step 4: Candidate receiving majority votes (3 out of 5) becomes leader.
Step 5: New leader sends heartbeats to maintain leadership.
Workers: [A] [B] [C] [D] [E-CRASHED]
Term: 9
Worker B detects failure, increments term to 10:
B → A,C,D: "RequestVote for term 10"
Workers vote (first-come-first-served):
A → B: "Vote granted"
C → B: "Vote granted"
D → B: "Vote granted"
Worker B receives majority (3/5):
B → ALL: "I am leader for term 10"
New leader: Worker B with term 10
Scenario: Multiple workers detect failure simultaneously.
Workers A and C both become candidates in term 10. Both request votes.
Possible outcomes:
Outcome 1: Worker A gets votes from B, D. Worker C gets vote from E. A wins (3 vs 1).
Outcome 2: Split vote. A gets 2 votes, C gets 2 votes. Nobody has majority.
If split vote: Workers wait random timeout (100-300ms), then retry with term 11.
Random timeout prevents perpetual ties.
Pros:
Cons:
Best for: Production systems requiring high availability and correctness.
Used by: Amazon DynamoDB, Amazon EBS, many AWS services.
Core idea: Leader "rents" leadership for a time period from a central store.
How it works:
Setup: Central database (like DynamoDB) stores current leader and lease expiration.
Becoming leader:
Worker writes: "I am leader, lease expires in 60 seconds" to database.
If database already has a leader with unexpired lease, write fails.
If no leader or lease expired, write succeeds. Worker is now leader.
Maintaining leadership:
Leader updates lease every 30 seconds: "Extending lease for another 60 seconds."
If leader crashes:
Leader stops updating lease. After 60 seconds, lease expires.
Another worker writes its own lease, becoming new leader.
DynamoDB Table: leadership
| leader_id | lease_expires_at |
|-----------|------------------|
| Worker-A | 2024-01-01 10:00:45 |
Time: 10:00:30
Worker A heartbeats:
UPDATE leadership SET lease_expires_at = 10:01:30
Time: 10:00:40
Worker A crashes
Time: 10:01:00 (lease expired)
Worker B attempts takeover:
UPDATE leadership SET leader_id=Worker-B, lease_expires_at=10:02:00
Success! Worker B is new leader.
Pros:
Cons:
Best for: Systems already using DynamoDB/similar services, AWS-native applications.
Bully: Learning, small dev clusters, non-critical systems.
Raft: Production systems needing strong consistency, distributed databases, .
Lease-Based: AWS infrastructure, systems with existing central database, simpler operational model.
Most production systems use Raft or Lease-Based. Bully is mostly educational.
Challenge: Kubernetes clusters need highly available control plane.
Solution: Run 3 or 5 master nodes. Use leader election for controllers.
Implementation:
Kubernetes uses leader election with leases stored in etcd.
Components using leader election:
How it works:
3 master nodes running controller-manager. Only one is active leader.
Leader holds lease in etcd. Updates every 10 seconds.
Leader crashes? Lease expires after 15 seconds. Another controller becomes leader.
User experience: Zero downtime. Kubernetes continues scheduling pods and managing resources.
What is etcd? Distributed key-value store used by Kubernetes, CloudFlare, and others.
Challenge: Store critical cluster state. Must be highly available and consistent.
Solution: etcd cluster with Raft consensus.
Setup: 5 etcd nodes. Raft elects one leader.
Leader handles writes. Followers replicate data.
Leader crashes? Followers elect new leader in 1-2 seconds.
Why this matters: etcd stores state. If etcd is down, entire Kubernetes cluster is read-only or down.
With Raft leader election: etcd achieves 99.99%+ availability.
Challenge: Each EBS volume distributed across many storage servers. Must maintain consistency.
Solution: Leader election per volume region.
Implementation:
Each volume area has a primary (leader) and followers.
Primary uses lease-based leader election.
Primary orders all reads and writes for consistency.
Primary fails? Follower detects lease expiration. Promotes itself to primary in seconds.
User experience: Brief I/O pause (seconds), then volume continues working.
Scale: Amazon EBS handles millions of volumes, each with its own leader election.
Split-brain: Two nodes both think they are leader. Catastrophic for data integrity.
How it happens:
Network partition splits cluster into two groups.
Each group cannot communicate with the other.
Both groups elect their own leader.
Now you have two leaders making conflicting decisions.
Example disaster:
Bank database splits. Leader A processes withdrawal. Leader B processes withdrawal.
Network heals. Both withdrawals recorded. Account overdrawn incorrectly.
Solution: Require majority (quorum) to elect leader.
Example: 5 nodes. Need 3 votes to become leader.
Network partition: 3 nodes in one group, 2 in another.
Group of 3: Can elect leader (has majority).
Group of 2: Cannot elect leader (no majority). Goes read-only.
Result: Only one leader ever exists.
This is why production systems use odd numbers (3, 5, 7 nodes). Ensures clear majority.
Problem: Lease-based election depends on time. Clocks can .
Scenario:
Leader thinks: "My lease expires at 10:00:30"
Follower thinks: "Leader lease expired at 10:00:25" (clock 5 seconds ahead)
Follower becomes leader while old leader still thinks it is leader. Split-brain!
Solution 1: NTP (Network Time Protocol) keeps clocks synchronized within milliseconds.
Solution 2: Use logical clocks instead of wall-clock time. Raft does this.
Best practice: Assume clocks can skew. Design for safety anyway.
Amazon provides library: DynamoDB Lock Client for leader election.
How to use:
AmazonDynamoDBLockClient client = new AmazonDynamoDBLockClient(
AmazonDynamoDBClientBuilder.defaultClient(),
"LeaderElection"
);
LockItem lock = client.acquireLock("my-service-leader");
if (lock != null) {
// I am the leader
while (doLeaderWork()) {
lock.sendHeartbeat(); // Maintain lease
}
lock.release();
}
Benefits: Proven, tested, handles edge cases. No need to implement from scratch.
What is ZooKeeper? Distributed coordination service. Used by Hadoop, Kafka, HBase.
Provides: Leader election, distributed locks, configuration management.
How leader election works:
Applications create ephemeral sequential nodes in ZooKeeper.
Node with lowest sequence number becomes leader.
Leader connection dies? ZooKeeper deletes ephemeral node. Next lowest becomes leader.
Example:
/election/leader-0000000001 (leader)
/election/leader-0000000002 (follower)
/election/leader-0000000003 (follower)
Leader crashes:
ZooKeeper deletes leader-0000000001
leader-0000000002 becomes new leader
Common problems:
Flapping leaders: Leader changes every few minutes. Usually network instability or resource exhaustion.
Stuck without leader: Election keeps failing. Usually split configuration or network partition.
Multiple leaders: Split-brain. Critical bug. Check quorum settings and network partition handling.
How to debug:
Logs: Track leadership changes. "Became leader", "Lost leadership", "Election started".
Metrics: Time spent without leader. Election duration. Leadership tenure.
Alerts: Alert when leadership changes more than once per hour (unusual).
Start with proven libraries: DynamoDB Lock Client, etcd client, ZooKeeper. Do not build your own unless necessary.
Use odd numbers: 3, 5, or 7 nodes for clear majority.
Monitor leadership: Track current leader, election frequency, leadership duration.
Test failure scenarios: Regularly kill leaders. Verify automatic recovery works.
Lease durations: Balance detection speed vs false positives. 30-60 seconds is typical.
Heartbeat frequency: Half of lease duration (15-30 seconds if lease is 60 seconds).
These patterns are battle-tested across billions of requests daily. Learn from them.
Irony: Leader election solves monitoring recursion but creates a new single point of failure: the leader itself.
What happens when leader is slow?
Leader becomes bottleneck. All decisions flow through leader. System performance capped by leader capacity.
Example:
Database cluster with leader-follower. Leader handles all writes.
Load increases. Leader saturated. Write throughput cannot increase. Adding followers does not help (they only handle reads).
Solution: Shard data across multiple leader-elected groups. More leaders = more write capacity.
Trade-off: Increased complexity.
Split-brain remains possible if leader election is misconfigured.
Real incident (anonymized company):
Setup: 3-node cluster. Quorum = 2 nodes.
Network partition: Node A isolated. Nodes B and C together.
Expected: B and C elect new leader. A goes read-only.
Bug: Faulty quorum config. Both sides thought they had majority. Two leaders.
Result: Data corruption. Conflicting writes to database. Hours of manual reconciliation.
Lesson: Test network partition scenarios religiously. Use proven libraries.
Leader election adds latency to system startup and recovery.
Without leader election: Service starts, immediately begins working. Startup: 2 seconds.
With leader election: Service starts, waits for election, then begins working. Startup: 10-15 seconds.
During leader failure: Election takes 5-15 seconds. System in degraded mode during this time.
Trade-off: Slightly slower startup and recovery for automatic failover.
Scenario: Web API servers. Stateless. Any server can handle any request.
Do you need leader election? No.
Better approach: Load balancer distributes traffic. Servers independently handle requests. No coordination needed.
Adding leader election here: Unnecessary complexity. Bottleneck. No benefit.
Scenario: Startup with 100 users. Single database. Single API server.
Do you need leader election? Not yet.
Better approach: Focus on product. Manual failover acceptable at this scale.
Adding leader election: Over-engineering. Time better spent on .
When to add: 10,000+ users, requirements, 24/7 operations.
Scenario: Social media feed. Eventual consistency acceptable. Multiple writers okay.
Do you need leader election? Probably not.
Better approach: Multi-master replication. Conflict resolution through CRDTs or last-write-wins.
Example: Cassandra. No leader. All nodes equal. Writes go to any node.
Trade-off: Give up strong consistency for higher availability and write throughput.
Scenario: Financial transactions. Strong consistency required.
Leader election option: Leader handles all writes. Guarantees consistency.
Better option: Use managed database with built-in high availability (AWS RDS Multi-AZ, Google Cloud SQL).
Why better: Database teams already solved this problem. Do not reinvent the wheel.
Example: Bitcoin. No leader. Nodes reach consensus through proof-of-work.
Pros: Truly decentralized. No single point of failure.
Cons: Slow. Expensive. Complex.
Use when: Decentralization is paramount (blockchain applications).
Strategy: Divide data into shards. Each shard has its own leader.
Example: MongoDB sharded cluster. 100 shards. 100 leaders (one per shard).
Pros: Scales horizontally. No single leader bottleneck.
Cons: More complex. Cross-shard operations difficult.
Use when: Single leader cannot handle load.
Strategy: Make all operations idempotent. Multiple executions = same result.
Example: "Set user name to John" (idempotent) vs "Add 1 to counter" (not idempotent).
Benefit: No leader needed. Multiple systems can execute same operation safely.
AWS Step Functions approach: Prefer this over leader election when possible.
Use when: Operations are naturally idempotent or can be made so.
Strategy: Assume no conflicts. Detect conflicts when they occur. Retry.
Example: Update user record with version number.
UPDATE users SET name='John', version=version+1
WHERE id=123 AND version=5
If version changed (someone else updated), retry.
Pros: No leader. No coordination overhead.
Cons: Conflicts require retries. Not suitable for high-contention scenarios.
Use when: Low conflict rate expected.
Critical metrics:
Leadership changes per hour: Should be zero or very low. High rate indicates instability.
Time without leader: Should be seconds, not minutes. Long periods indicate election issues.
Leader workload: Monitor CPU, memory, request rate of leader. Detect bottlenecks.
Election duration: How long elections take. Increasing duration indicates problems.
Best practices:
Alert on unexpected leadership changes: More than 2 per day needs investigation.
Dashboard showing current leader: Operators should quickly see who is leader.
Logs of leadership events: "Became leader", "Lost leadership", "Election failed".
Every pattern has cost. Leader election costs:
Development time: Implementing or integrating election library. Testing failure scenarios.
Operational complexity: Understanding leader state. election issues. Training team.
Failure modes: New ways system can fail (split-brain, stuck elections, slow leaders).
Ask before adding leader election:
If unsure, start simple. Add leader election when scale and requirements demand it.
Use leader election when:
Avoid leader election when:
Leader election is powerful but not a universal solution. Use wisely.
Who monitors the monitor? Leader election solves this infinite recursion problem. When a leader fails, workers automatically elect a new leader, creating systems that heal themselves without manual intervention.