Implementing Leader Election
1. Understanding Leader Election Algorithms
| Algorithm | Mechanism | Use |
|---|---|---|
| Bully | Highest ID wins | Small clusters |
| Ring | Token passes around ring | Logical ring topology |
| Lease-based | TTL on lock holder | Cloud (etcd, ZooKeeper) |
| Raft / Paxos | Quorum vote per term | Strongly consistent stores |
| Random + heartbeat | Randomized timeout (Raft) | Modern default |
2. Implementing Bully Algorithm
| Step | Action |
|---|---|
| 1 | Node detects leader failure (no heartbeat) |
| 2 | Sends ELECTION to higher-ID nodes |
| 3 | If no response, declares itself COORDINATOR |
| 4 | If response, waits; loser concedes |
| Cost | O(N²) messages worst case |
3. Implementing Ring Algorithm
| Step | Action |
|---|---|
| 1 | Initiator sends ELECTION with own ID around ring |
| 2 | Each node appends ID |
| 3 | Initiator picks max ID, sends COORDINATOR |
| Cost | O(N) messages |
4. Implementing Lease-Based Leader Election
Example: etcd lease lock
cli, _ := clientv3.New(clientv3.Config{Endpoints: endpoints})
session, _ := concurrency.NewSession(cli, concurrency.WithTTL(10))
election := concurrency.NewElection(session, "/svc/leader")
ctx := context.Background()
if err := election.Campaign(ctx, hostname); err != nil { panic(err) }
// I am leader as long as session is alive
defer election.Resign(ctx)
runLeaderWork(ctx)| Property | Value |
|---|---|
| TTL | 5-30s typical |
| Renewal | Keepalive every TTL/3 |
| Failover | Within TTL after leader crash |
5. Using Consensus for Leader Election
| System | Mechanism |
|---|---|
| Raft | Term + RequestVote |
| ZooKeeper | Ephemeral sequential znode; lowest wins |
| etcd | Lease + compare-and-swap on key |
| Kubernetes | Lease object via coordination.k8s.io API |
6. Handling Leader Failures
| Step | Action |
|---|---|
| Detect | Heartbeat / lease expiration |
| Elect | New leader chosen via algorithm |
| Fence old leader | Increment epoch / fencing token |
| Recover state | New leader replays log to latest |
| Resume traffic | Notify clients / update routing |
7. Implementing Fencing Tokens
| Property | Detail |
|---|---|
| Definition | Monotonic id assigned at lock acquisition |
| Use | Resource server rejects ops with token < max_seen |
| Source | Lock service version (etcd revision, ZK zxid) |
Example: Resource server rejecting stale fencing token
public class StorageServer {
private long maxToken = 0;
public synchronized void write(long token, byte[] data) {
if (token < maxToken) {
throw new IllegalStateException("Stale leader; rejected");
}
maxToken = token;
persist(data);
}
}8. Understanding Split-Brain Prevention
| Technique | Detail |
|---|---|
| Quorum | Majority required to elect / commit |
| Fencing tokens | Detect stale leaders |
| STONITH | Hardware/IPMI power-off losers |
| Witness / arbiter | Tie-breaker node in 3rd AZ |
9. Implementing Leader Heartbeat Mechanisms
| Aspect | Tuning |
|---|---|
| Heartbeat interval | 50-150ms (Raft default 50ms) |
| Election timeout | 10× heartbeat (150-300ms randomized) |
| Cross-AZ adjustment | Increase to absorb network jitter |
| Pre-vote | Probe before disrupting (etcd PreVote) |
10. Understanding Leader Election Trade-offs
| Choice | Trade |
|---|---|
| Short timeouts | Fast failover; false positives |
| Long timeouts | Stability; longer outages |
| Strong (Raft) vs lease | Stronger guarantees vs simpler ops |
| No leader (leaderless) | Higher availability; conflict resolution overhead |