Distributed locks and fencing tokens

The problem: two renewers, one certificate

Snip renews the TLS certificate for go.shop.example under a lock: take the lock, request a certificate, store it, release. One evening, renewer A takes the lock, starts its request, and is paused by a long garbage collection. Its lock expires. Renewer B takes the lock, gets a fresh certificate and stores it. Then A wakes up and stores the certificate it requested, an older one, overwriting B's. A believes it holds the lock; it has no way to know otherwise.

First ask: what is the lock for?

Martin Kleppmann's essay on distributed locking separates two purposes:

• Efficiency: the lock avoids doing the same work twice. If it fails occasionally, some work is repeated: a wasted certificate request, a duplicate email. Annoying, not dangerous.
• Correctness: the lock stops processes stepping on each other's toes. If it fails, data is corrupted: an old certificate replaces a new one, money moves twice.

For efficiency, a simple lock is fine. A common one is a single Redis key set with "only if absent" and an expiry: SET lock:cert:go.shop.example <random-id> NX PX 30000, released only by the holder (checking the random ID, so you don't delete someone else's lock). If Redis loses the key, two workers occasionally both renew; acceptable.

For correctness, no lock alone is enough, however carefully built, because of the paused holder above. The resource being protected has to help.

Fencing tokens

Each time the lock service grants the lock, it hands out a fencing token: a number that only ever increases. The holder sends its token with every write, and the storage remembers the highest token it has seen and rejects anything older.

In Postgres, the check is a condition on the update:

CREATE TABLE certificates (
  domain text   PRIMARY KEY,
  cert   text,
  fence  bigint NOT NULL DEFAULT 0  -- highest fencing token that has written here
);

-- Renewer B, token 34
UPDATE certificates SET cert = $2, fence = 34
 WHERE domain = 'go.shop.example' AND fence < 34;

-- Renewer A wakes up with token 33: matches no row, so it changes nothing
UPDATE certificates SET cert = $2, fence = 33
 WHERE domain = 'go.shop.example' AND fence < 33;

Tested against Postgres: B's update set the certificate and fence 34; A's late update with token 33 updated zero rows, and the table kept B's certificate. The writer checks the row count and, seeing zero, knows it has lost the lock.

Where do tokens come from? From the consensus store that grants the lock. etcd and ZooKeeper both give every change a number that only increases (etcd's revision, ZooKeeper's zxid), which works as a token. Google's Chubby calls the same idea a sequencer: a lock holder passes it to servers, which check it before acting.

Why not just a stronger lock?

Redlock, an algorithm that takes a lock on a majority of five independent Redis nodes, is often suggested for correctness. Kleppmann's critique is twofold: it doesn't produce fencing tokens, so the paused-holder problem remains, and it assumes that delays, pauses and clock drift are all small compared with the lock's time to live, which a long garbage-collection pause or a clock jump breaks. Redis's creator wrote a rebuttal, and the debate is worth reading; the practical lesson that came out of it is the one above. If correctness depends on the lock, fence the writes; if it doesn't, a simple lock will do.

Recap

Interview questions