Leader election, leases and fencing tokens

Many jobs need exactly one process at a time: the scheduler that starts a nightly report, the owner of a partition, the only writer of a file. If that process holds a 10-second lease and stalls for 15 seconds, a second one takes over meanwhile, and both may write. Leader electionleader election: Choosing one process out of several to do a job alone, usually through a coordination service, with a lease so that a crashed leader is replaced without anyone's help. picks the one process, usually with the help of a coordination servicecoordination service: A small service replicated with consensus, such as ZooKeeper or etcd, that other systems use for leader election, locks, leases and shared configuration. such as ZooKeeper or etcd. Leases make leadership expire when the leader stops renewing it, so a crashed leader is replaced without anyone’s help. Fencing tokens are numbers that grow with every new leader, and the resource refuses any write that carries an older number than one it has seen. A design needs all three, because leases alone fail in a way that is easy to miss: a leader that is only paused looks exactly like a dead one.

A paused leader outlives its lease, so leases alone are not enough

Leader election on a coordination service takes a few lines. In ZooKeeper each candidate creates an ephemeralephemeral node: A ZooKeeper node that exists only as long as the session of the client that created it; when the session ends, ZooKeeper deletes it., sequential node, the lowest sequence number leads, and an ephemeral node vanishes when its owner’s session ends (ZooKeeper recipes; ZooKeeper guide). In etcd each candidate attaches its key to a leaselease: A time-limited right to act, as a leader or as the holder of a lock. The holder may act only while the lease lasts, and no successor starts before it has expired. More in “Failover, split brain and fencing” that it keeps alive, and the key is deleted when the lease runs out (etcd API). Leases are what make both work, and leases depend on time.

A garbage-collection pause, a stalled virtual machine or a slow network can stop a leader for longer than its lease. The service correctly gives the lease to someone else; the old leader resumes, unaware that any time has passed, and finishes what it was doing. Kleppmann notes that HBase once had exactly this bug (Kleppmann), and Amazon’s Builders’ Library warns that during failures a system may have zero leaders or two (Builders’ Library). Here is the case of the opening, top to bottom in the order things happen:

The program replays the diagram with its times:

# Worker A holds a 10-second lease on "report.csv" and pauses (a long garbage-collection pause, say) halfway through
# its update. The lease expires, worker B takes over and writes, then A wakes up and finishes the write it had
# started, believing it still leads. Times are seconds; the storage accepts every write it receives.
LEASE_S = 10

lease = {"holder": None, "expires": 0}
storage = {"report.csv": "v1 (before)"}
log = []


def acquire(worker, t):
    if lease["holder"] is None or t >= lease["expires"]:
        lease.update(holder=worker, expires=t + LEASE_S)
        log.append(f"t={t:>2}  {worker} gets the lease until t={t + LEASE_S}")
        return True
    return False


def write(worker, t, value):
    storage["report.csv"] = value
    log.append(f"t={t:>2}  {worker} writes {value!r}")


acquire("A", 0)
log.append("t= 4  A reads the file and starts its update; then it pauses for 15 s")
for t in range(1, 20):
    if acquire("B", t):  # B keeps trying; it wins as soon as A's lease has expired
        write("B", t + 1, "v2 (from B)")
        break
log.append("t=19  A resumes; as far as it knows, no time has passed")
write("A", 19, "v2 (from A, built from the v1 it read at t=4)")

for line in log:
    print(line)
print(f"\nThe file now holds {storage['report.csv']!r}: B's update is lost, and two workers acted as leader.")

t= 0  A gets the lease until t=10
t= 4  A reads the file and starts its update; then it pauses for 15 s
t=10  B gets the lease until t=20
t=11  B writes 'v2 (from B)'
t=19  A resumes; as far as it knows, no time has passed
t=19  A writes 'v2 (from A, built from the v1 it read at t=4)'

The file now holds 'v2 (from A, built from the v1 it read at t=4)': B's update is lost, and two workers acted as leader.

B’s update is lost, and nothing failed loudly. Checking the lease again just before writing does not help, because the pause can fall between the check and the write. The fixes are structural. Fencing tokensfencing token: A number that rises every time a lease or leadership changes hands. The storage refuses a write that carries a lower token than one it has already accepted. More in “Failover, split brain and fencing” let the storage refuse the stale write itself. Lease timing with a monotonic clock, counted from when each renewal was sent, keeps the leader’s own estimate safe. Idempotent work lets a second leader repeat a step without harm. A failure detector, the timeout that declares a leader gone, decides how fast all of this starts. Leader election itself stays simple; the care goes into listing every resource a stale leader could still reach and making each of them refuse it. Fencing tokens do that for anything you can change, which makes them the default for every resource whose corruption you cannot afford.

ZooKeeper and etcd elect the oldest candidate and drop a leader whose session ends Pro: opens with a Pro, Premium or Ultimate pass