Distributed locks, leader election & fencing tokens

You've already used a lock that works perfectly: the advisory lock and SELECT FOR UPDATE from the databases track. Those are single-node locks — one Postgres instance arbitrates, so "who holds it" has exactly one authority and there's no ambiguity. A distributed lock — mutual exclusion across multiple machines with no single arbiter — is a completely different and famously treacherous problem, and it's treacherous in a way that catches even experienced engineers, because the naive version looks correct and fails only under conditions your tests never reproduce.

You reach for one whenever "only one at a time, across the whole fleet" matters: only one worker should run the nightly job, only one node should process a given resource, one instance should be the "leader" for some singleton duty. The question is how to do it safely, and the answer is more subtle than it first appears.

The naive lock and the pause that breaks it

The standard first attempt uses Redis: SET lock_key node_id NX PX 30000 — set the key only if it doesn't exist (NX), with a 30-second expiry (PX). Acquiring the key means you hold the lock; the TTL means that if the holder crashes, the lock doesn't stay held forever — it expires and someone else can acquire it. This seems to handle the obvious failure (a dead holder) neatly.

It has a hole, and it's a correctness hole, not an efficiency one:

Fencing tokens: making the resource enforce the lock

The fix moves the safety guarantee from the lock to the resource being protected. Each time the lock service grants the lock, it also issues a fencing token — a number that strictly increases with every grant (1, 2, 3, …). The holder must include its token on every operation it sends to the protected resource, and the resource remembers the highest token it has seen and rejects any operation carrying a lower one.

Now replay the disaster. A acquires the lock with token 33 and pauses. Its lock expires; B acquires with token 34 and writes to the resource — the resource records "highest seen: 34." A wakes up and tries to write with its stale token 33 — and the resource rejects it (33 < 34). A's late write is fenced out. Two nodes briefly believed they held the lock, but only one could act, because the resource enforces the ordering the lock couldn't guarantee. The lock became advisory; the token made it safe. The one requirement is that the protected resource can check and store the token — which is why fencing works cleanly against a database (a WHERE token > current check, the compare-and-swap from optimistic concurrency) and not against a resource that can't reason about tokens.

Run the pause scenario both ways. With fencing OFF, Node A wakes from its pause and its stale write is accepted — two nodes wrote the same resource. Turn fencing ON and the resource rejects token 33 as below the 34 it has already seen. Same disaster, one line of defense.

Leader election is distributed locking in disguise

Leader election — picking one node to be "the leader" for some duty (run the singleton job, be the write coordinator) — is the same problem wearing a different name: the leader is whoever holds the leader lock. The robust way to do it is a lease: the lock is granted with a TTL, and the leader must continually renew it (a heartbeat). As long as it renews, it stays leader; if it stops (crash, partition), the lease expires and the others elect a new leader. This is exactly how coordination services expose it — etcd and ZooKeeper offer leases / ephemeral nodes that vanish when a client stops heartbeating, and they back those primitives with consensus (Raft/ZAB) so the "who holds it" decision is itself agreed safely. Which is the real lesson about where to get a distributed lock: from a consensus-backed coordinator (etcd, ZooKeeper, Consul), because they solve the underlying agreement problem correctly — not from a bare key in a cache.

Efficiency locks vs correctness locks

The distinction that ties it together (from Kleppmann): why do you hold the lock?

• For efficiency — the lock just avoids duplicate work. If it occasionally fails and two nodes do the same job, the result is wasteful but harmless (two workers regenerate the same cache entry; the second overwrites the first with identical data). Here a simple Redis lock is fine — the rare double-execution costs a little CPU, nothing more.
• For correctness — a failure corrupts data or double-charges. Here the naive lock is not acceptable, because the pause scenario is a real path to catastrophe. You need fencing tokens or a consensus-backed lock, full stop.

Most distributed-lock mistakes are using an efficiency-grade lock (bare Redis) for a correctness-grade job. Ask which kind you have before choosing the mechanism.