Failure detection and leader election

A node stops answering. Is it dead, or slow, or is the network between you and it broken while it carries on serving other clients? No message can tell those apart, and every design that needs to decide — to fail over, to elect a new leader, to give someone else the lock — is built on a guess made with a timeout. This lesson is how to make the guess well, and, since the guess will sometimes be wrong, how to make sure a wrong guess cannot corrupt anything.

#Heartbeats, and what a missed one means

The basic detector: every node sends "I am alive" every T milliseconds; a node that has not heard from a peer in k × T declares it suspect. T and k trade detection time against false positives: heartbeats every second with a three-second timeout fail over in three seconds and fire falsely on every GC pause longer than three seconds, which the JVM course measured in the hundreds of milliseconds to seconds range for a large heap. Kafka's consumer groups have exactly these three timeouts (session.timeout.ms, heartbeat.interval.ms, max.poll.interval.ms) and the Kafka course's "forty rebalances per deploy" was a detector tuned too tight.

A missed heartbeat is evidence, not a verdict: the sender may be paused, the network may have dropped a packet, the receiver may itself be overloaded and processing heartbeats late. The verdict — and the action — should need more than one.

#Suspicion: phi accrual

A fixed timeout treats a heartbeat that is one millisecond late the same as one that is ten seconds late. The phi accrual failure detector (Hayashibara; used by Cassandra and Akka) instead keeps the recent history of heartbeat arrival intervals and computes, for the current silence, the probability that the node has failed given that history — expressed as φ, where each unit is a tenfold increase in confidence. A node whose heartbeats normally arrive every 1,000 ± 50 ms and has been silent for 1,100 ms has a low φ; silent for 3,000 ms, a high one. The application picks a threshold (φ = 8 is Cassandra's default) and gets a detector that adapts to the network's actual behaviour: tolerant on a jittery link, quick on a steady one.

Whatever the detector, the output is suspicion, a level, and different actions want different levels: stop routing new requests to a suspect node at a low φ (cheap to be wrong), fail over its leadership at a high one (expensive to be wrong), and remove it from the cluster only on an operator's say or a very high one.

#Leases: permission with an expiry

A lease is a lock with a deadline: the holder may act as the leader (or own the partition, or hold the row) until time t, and must renew before then or stop. The lock service — ZooKeeper, etcd, a database row with an expiry, the Redis course's SET NX PX — grants it, and if the holder dies the lease simply expires and someone else can take it, with no detector needed beyond the clock.

The clocks lesson is where this gets dangerous. The lease's expiry is measured by the grantor's clock; the holder measures it by its own; and between "I still hold the lease" on the holder and "the lease has expired" at the grantor lies clock skew, plus a GC pause, plus a network delay. The scenario that has happened in production many times: the holder checks the lease (valid), pauses for eight seconds in a stop-the-world collection, resumes, and writes — while, during the pause, the lease expired and a new holder was granted it and also wrote. Two leaders, both correct by their own clock. Shortening the lease makes it more frequent; lengthening it makes failover slower; neither fixes it.

#Fencing tokens: making the stale holder harmless

The fix is not a better clock but a fencing token: every grant of the lease comes with a number that increases monotonically — 33, then 34 — and every write the holder makes to a downstream resource carries it. The resource (the database, the storage service, the queue) remembers the highest token it has seen and rejects any write with a lower one. The paused holder resumes and writes with token 33; the resource has seen 34 from the new holder; the write is refused. The stale leader is not detected; it is made unable to do harm.

// on the resource side, the check that makes the lease safe
void write(Write w, long token) {
    if (token < highestSeen) throw new StaleLeaderException(token, highestSeen);   // an old holder
    highestSeen = token;
    apply(w);
}

This is the same mechanism as the JPA course's optimistic lock (@Version is a fencing token on a row), the Kafka course's producer epoch and the idempotent-producer sequence, and ZooKeeper's zxid. The Redis course's lock lesson made this argument against Redlock: a lock whose holder cannot present a fencing token to the resources it protects is a lock that is safe only until the first pause. When the downstream cannot check a token — a third-party API, an email send — the lease protects nothing there, and the idempotency lesson's keys are what stop the double effect instead.

#Leader election

Many systems need one node to coordinate: to assign partitions, to run the scheduler, to be the single writer. Election chooses it, and the honest way is to not write it yourself: a lease in etcd or ZooKeeper (Kubernetes's Lease object and the leaderelection library, Spring Integration's LockRegistryLeaderInitiator), or a database row with SELECT ... FOR UPDATE and an expiry, where "leader" means "holds the lease" and every leader action carries the token. Underneath the lock service is a consensus protocol — Raft, which the system-design course's consensus lesson explained — that keeps a majority in agreement about who holds what, and that is the part you should not reimplement: the bully algorithm and its cousins from the textbook elect a leader without agreement about when the old one stopped, which is the split brain below.

The behaviours the elected code must have: renew the lease well before it expires (a third of the lease length is common); on a failed renewal, stop leading immediately — cancel the scheduler, stop accepting the writes — rather than continuing until told otherwise; and treat "I am the leader" as a claim checked at every action (with the token), not a flag set once.

#Split brain, and the two leaders

Split brain is two nodes each believing it is the sole leader: a partition separates them, each side's detector declares the other dead, each elects itself. Both serve writes, the partition heals, and the data has diverged in a way no automatic merge can fix. The defences, in order of strength:

• A majority. Leadership requires a lease from a quorum of the lock service's nodes; in a partition, at most one side has a majority, and the other side's lease requests fail. This is why etcd and ZooKeeper run with three or five nodes and why a two-node cluster cannot be made safe.
• Fencing tokens at the resources, so that even if both sides believe they lead, only the newer token's writes land.
• Stopping when unsure: a leader that cannot renew its lease stops leading, and a node that cannot reach the quorum stops serving writes (the CAP lesson's choice of consistency over availability, made explicit per operation). Availability during a partition is bought only by accepting divergence, and that is a product decision, not a default.
• STONITH ("shoot the other node in the head"), in the physical world: a fencing device that powers off the old leader before the new one starts. It is the same idea as the token, applied to the whole machine.

The thing an operator most needs to know: a split brain that was survived leaves two histories, and the recovery is a human comparing them. Design so that it cannot happen (majority plus tokens) rather than so that it can be repaired.