Leader election, leases and locks

A subscription company runs its monthly billing job at 1 a.m. on two servers, so that one can take over if the other dies. A Redis lock with a 30 second expiry makes sure only one runs at a time. One night the first server freezes for 40 seconds in a long garbage collection. Its lock expires, the second server takes it and starts billing, and then the first server wakes up and carries on from where it was. Thousands of customers are charged twice before anyone looks at a graph.

The lock worked exactly as designed. The design was missing one number, and this chapter is about that number.

Why you need exactly one#

A lot of work must be done by one machine at a time. The nightly billing run. The scheduler that hands out jobs. The single writer for a shard. The primary database. Running two of them at once means double charges, double emails or two diverging copies of the data.

Picking that one machine and agreeing on it is leader election. A lock is the same idea for a shorter piece of work: "I am the one doing this, until I say I am done". Both have to answer the same hard question: what happens when the holder stops responding?

Locks that cannot outlive their holder: leases#

A plain lock held by a machine that then crashes is held forever. Nobody else can ever take it, because "the holder is dead" and "the holder is slow" look the same from outside (Partial failure again).

So every lock between machines is a lease: a lock with an expiry time. The holder keeps it alive by renewing well before it expires, typically every third of its length. If the holder dies, it stops renewing, and the lease runs out on its own.

Kubernetes uses exactly this for its own components. The scheduler and the controller manager run several copies, and one holds a Lease object in the API. By default the lease lasts 15 seconds, the leader must renew within 10, and the others try to take it every 2. So a dead leader is replaced in about 15 seconds, and nobody had to decide it was dead.

The length of the lease is a trade. Shorter means a dead holder is replaced faster, and that a slow network or a busy holder that misses a renewal loses the lease while still alive. Longer means fewer false losses, and a longer outage when the holder really dies.

The holder does not know it lost#

The lease protects you from a holder that dies. The cold open is a different failure: a holder that stops and then starts again. During the pause it cannot renew, its lease expires, and someone else takes over. When it wakes, it is in the middle of its work and has no reason to think anything happened. It checked the lease a moment ago, as far as it can tell.

Move the pause and see when it goes wrong, then turn on the storage check.

Nothing the worker does can close this gap. Checking the lease just before writing still leaves the moment between the check and the write. Measuring the lease on the monotonic clock with a safety margin (good practice anyway) shrinks the window without closing it. A 40 second pause beats any margin you would accept.

The fix has to be on the other side: the storage that receives the write.

Fencing tokens#

Every time the lock service grants the lease, it hands out a number that only ever goes up: 33 for this grant, 34 for the next. The holder sends that number with every write. The storage remembers the highest number it has seen, and rejects anything lower.

The stale worker shows up with 33 after the storage has seen 34. Rejected. The worker gets an error, which is the first moment it learns it lost the lease, and it stops. This is a fencing token, and Google's Chubby lock service shipped the same idea in 2006 under the name sequencer.

-- The job row remembers the newest token that has written to it.
UPDATE invoice_runs
SET    status = 'charged', charged_at = now(), fence = $2
WHERE  customer_id = $1
  AND  fence <= $2;      -- 0 rows updated: a newer lease holder has been here

Where the token comes from depends on the lock service. In etcd, the revision at which your lock key was created only increases, so it works as a token. In ZooKeeper, the sequence number of your lock node does the same. A plain Redis lock has no such number, which is the heart of the criticism in the callout below.

The catch: the resource must check. A database row can compare a number. An email provider or a card network cannot. For those, the same job is done by an idempotency key derived from the work itself ("invoice for customer 8812, October"), so the second attempt is recognised as a repeat rather than fenced off.

Where to get a lock#

A Redis lock done properly takes two details: set it only if absent with an expiry, and release it only if it is still yours.

import { randomUUID } from 'node:crypto'
 
const key = 'lock:cache-rebuild'
const token = randomUUID()
 
// Take the lock only if nobody holds it, and let it expire by itself after 30 s.
const ok = await redis.set(key, token, { NX: true, PX: 30_000 })
if (!ok) return // someone else is already doing it
 
try {
  await rebuildCache()
} finally {
  // Delete it only if it is still ours. Without this check, a worker whose lock
  // expired would delete the next holder's lock.
  await redis.eval(
    "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end",
    { keys: [key], arguments: [token] },
  )
}

Leader election with etcd#

Long running leadership is a lease that is renewed for as long as the leader lives. etcd's election recipe:

Watching only the key just ahead of yours, rather than the leader's key, matters at scale. If fifty candidates all watched the leader, its death would wake all fifty at once to compete for the same thing (a herd). Watching your predecessor wakes exactly one.

Checkpoint#