Leader election and leases

The problem: exactly one, but not zero

Several Snip jobs must run in exactly one place at a time:

• The certificate renewer, which renews TLS certificates for custom domains before they expire. Two renewers at once could hit the certificate authority's rate limits or overwrite each other's work.
• The live-count aggregator for a viral link (07.09 Fan-out patterns): two would double the numbers.
• The weekly report scheduler (07.07 Delayed and scheduled jobs), if it isn't using the database trick.

Each runs on three servers for resilience. One should be active, the leader, and if it dies another should take over within seconds. Picking one is easy. Making sure there's never more than one, while never being stuck with none, is the hard part.

Leases

A lease is a lock with an expiry. The leader holds it only as long as it keeps renewing it. If it crashes, it stops renewing, the lease expires, and another instance can take it. No one has to detect the crash; time does it.

In etcd, a client is granted a lease with a time to live, attaches a key to it ("/leaders/cert-renewer = server-2"), and keeps it alive with a stream of keep-alive messages. In etcd's words, a lease expires if the cluster doesn't receive a keep-alive within the TTL, and when a lease expires or is revoked, all keys attached to it are deleted. The election is then just: whoever creates the key first, with a transaction that only succeeds if the key doesn't exist, is the leader. The others watch the key and try again when it disappears.

Because etcd runs Raft (08.06 Consensus and Raft, intuitively), only one client can hold the key at a time, as far as etcd is concerned.

Kubernetes works the same way. Its control-plane components, such as the controller manager and the scheduler, run several copies for high availability, but only one should be active; they coordinate through Lease objects, which are also how each node's kubelet sends its heartbeat.

The catch: a leader that doesn't know it's been replaced

Leases fix crashed leaders. They don't fix paused ones. Suppose Renewer 1 checks "I still hold the lease", then the process freezes for 15 seconds: a long garbage-collection pause, the virtual machine being suspended, a slow disk. Meanwhile its 10-second lease expires and Renewer 2 becomes leader. Then Renewer 1 wakes up and carries on with the work it had already decided to do, believing it's still leader. For a moment there are two.

Nothing in Renewer 1 can prevent this, because the pause can happen between any two lines of code, including between "check the lease" and "do the work". Ways to limit the damage:

• Stop early. A leader stops acting some margin before its lease expires (say at 7 seconds of a 10-second lease), measured on a monotonic clock, never wall-clock time (05.06 Clocks, skew and ordering IDs).
• Make the work safe to repeat. If both renewers request a certificate, the result should be one valid certificate.
• Let the resource reject the old leader. Each new leader gets a higher number, and whatever it writes to checks it. That's a fencing token, and it's the only complete answer (08.08 Distributed locks and fencing tokens).

Choosing the TTL

Snip uses 10 seconds for the certificate renewer, where a minute without a leader doesn't matter, and fencing tokens on its writes.

Recap

Interview questions