Leader Election and Heartbeats

Most distributed systems need a leader: one node that owns the write path, assigns sequence numbers, or serializes decisions. Raft has one. ZooKeeper's ZAB has one. Kafka's controller has one, and so does every HDFS NameNode failover. A leader is a serialization point — the machine that makes "who goes next" a well-posed question. The hard part is not electing a leader. It is making sure that when a leader dies, exactly one replacement takes over — and that the old one, which may not know it died, stops writing.

Heartbeats and timeouts

Leadership is maintained by heartbeats. The leader sends a heartbeat every interval H; each follower resets a timer; if the timer exceeds a timeout T > H with no heartbeat, the follower declares the leader dead and starts an election.

leader:
  every H ms: send heartbeat(term) to all followers
 
follower:
  on heartbeat: reset timer; adopt leader's term
  on timer > T: become candidate; start election

The uncomfortable truth is that a timeout is an indirect guess. The follower cannot distinguish "leader is slow" from "leader is dead" from "leader is in a 10-second GC pause" — all three produce silence, and a pause is not death. The timer does not detect failure; it detects absence of evidence of life. Every election is therefore a guess made under uncertainty, which is why elections are designed to be safe even when they are wrong.

Term numbers

Elections use monotonically increasing term (or epoch) numbers. A candidate increments the term, requests votes, and wins only with a majority. Each node votes once per term, and a node that hears a higher term immediately steps down.

Terms make stale messages detectable. A message carrying an old term is garbage; a leader that receives a heartbeat with a higher term knows it lost and becomes a follower. Majority intersection guarantees the core safety property: at most one leader per term. Two leaders would each need a majority of votes, and any two majorities overlap in at least one node — which can only have voted for one of them.

The old leader problem

Terms solve messaging between nodes. They do not solve the case that actually bites: the old leader that never hears the news.

Picture a partition. The old leader keeps serving clients on one side, sending heartbeats into the void. On the other side, the majority elects a new leader with a higher term. Two leaders now accept writes. Both believe they are legitimate; neither will learn otherwise until the partition heals, at which point the damage — divergent state — is already done. Every split-brain story in production is this scenario with a different coat of paint.

Fencing tokens

The fix is to make the storage reject stale leaders, not to hope the leaders behave. When a leader is elected, the authority issues a fencing token: a monotonically increasing value (a Raft term, a ZooKeeper zxid, an etcd revision, a Kafka controller epoch). The leader stamps every write with its token, and the storage keeps the highest token it has accepted:

func (s *Store) Write(token int64, key string, value []byte) error {
    if token < s.lastToken {
        return ErrStaleLeader // fenced: this leader lost an election
    }
    s.lastToken = token
    return s.apply(key, value)
}

When the old leader's write arrives with a token lower than the new leader's, the storage refuses it. The leader's identity is not "whoever last sent a heartbeat" — it is "whoever holds a token the storage will accept." This is how HDFS fences stale NameNodes, Kafka's controller epoch rejects old controllers, and Spanner prevents split-brain writes. The fence is the enforcement; the election is the ceremony.

Leases: time-bounded leadership

A lease is leadership with an expiration: the leader holds permission for duration L, renews it with heartbeats, and followers refuse to elect a new leader until the old lease has expired. Leases close the window in which a slow-but-alive leader coexists with a newly elected one: the new leader must wait out the old lease before writing.

Leases are wall-clock math, and that is their weakness. Their correctness depends on bounded clock skew and bounded message delay. If a follower's clock runs behind, it can conclude the lease expired early and elect a new leader while the old one is still valid — two leaders, both holding what they believe is a live lease. NTP skew is measured in milliseconds; lease margins must be measured in the same units, with slack.

Why wall clocks can't order events

A recurring temptation is to use wall-clock timestamps to decide who is authoritative: "the write with the latest timestamp wins." That fails because now() on machine A and now() on machine B are different clocks — NTP skew, clock steps, and drift mean a timestamp from A cannot be compared with one from B for correctness. Timestamps are for telemetry and TTLs; terms, tokens, and sequence numbers — local and monotonic — are for ordering. When two machines disagree about "now," only machine-generated order survives.