Distributed Locks: Leases, Fencing Tokens, and Why Redlock Is Controversial

A mutex inside one process is a solved problem. Stretch the same idea across machines — "only one worker may run this billing job," "only one instance may write this file" — and every guarantee you relied on quietly dissolves. The lock service can crash. The network can partition. And most insidiously, the process holding the lock can stall at exactly the wrong moment.

Distributed locking is less about acquiring locks and more about surviving the moment your lock stops being true.

The naive lock and its first failure

The Redis one-liner everybody starts with:

SET job:billing:2026-07 worker-42 NX PX 30000

Set if not exists, expire in 30 seconds. The TTL is not an optimization — it is mandatory. Without it, a worker that crashes while holding the lock leaves it stuck forever and your billing job never runs again. A lock with an expiry is properly called a lease: ownership for a bounded time, not ownership.

Releasing has its own trap: DEL alone can delete a lock someone else now holds (your lease expired, another worker acquired it, you delete their lock). Correct release checks ownership atomically:

-- release only if we still own it
if redis.call("GET", KEYS[1]) == ARGV[1] then
    return redis.call("DEL", KEYS[1])
end
return 0

The pause that breaks everything

Here is the failure that makes distributed locks fundamentally hard, popularized by Martin Kleppmann's analysis of Redlock:

t=0    Worker A acquires lease (TTL 30s), starts writing to storage
t=5    Worker A hits a stop-the-world GC pause / VM migration / disk stall
t=30   Lease expires. Worker A has no idea — it is frozen.
t=31   Worker B acquires the lease, legitimately. Starts writing.
t=40   Worker A wakes up, believes it still holds the lock, resumes writing.
       → Two writers. Corruption.

No TTL tuning fixes this. The client cannot reliably know its lease expired, because the very thing that delays its work also delays its clock checks. Checking "do I still hold it?" right before writing just shrinks the window; it cannot close it.

Fencing tokens: making the resource enforce the lock

The fix is to stop trusting lock holders entirely. The lock service hands out a monotonically increasing token with every grant — 33 to worker A, 34 to worker B. Every write to the protected resource carries the token, and the resource itself rejects tokens older than the highest it has seen:

Worker A (token 33) — paused...
Worker B (token 34) — writes accepted, storage records 34
Worker A wakes, writes with token 33 → REJECTED (34 already seen)

The zombie writer is fenced out no matter how long it slept. The catch: the storage system must participate — a compare-and-swap on a version column, an object-store conditional put, or any check that refuses stale tokens. If your downstream cannot do a conditional write, a fencing token has nowhere to land, and your lock is best-effort no matter what issues it.

ZooKeeper and etcd give you the raw materials properly: session-based ephemeral locks, and a monotonic number (zxid or the lease/revision counter) to use as the fencing token.

The Redlock controversy in one paragraph

Redlock is Redis's multi-node locking algorithm: acquire the lease on a majority of 5 independent Redis nodes, and consider yourself locked if you got 3+ within a time bound. Kleppmann's critique: it depends on bounded clock drift and bounded pauses — assumptions real systems violate — and it issues no fencing tokens, so it cannot survive the zombie-writer scenario above. Antirez (Redis's author) responded that the timing assumptions are reasonable in practice. Both are right in their own frame: Redlock is fine for efficiency, insufficient for correctness. That distinction is the actually useful takeaway:

• Efficiency lock: two workers doing the same job is wasteful but harmless (duplicate email at worst, and idempotency makes it harmless). A single Redis SET NX PX is perfect. Cheap, fast, occasionally wrong, nobody hurt.
• Correctness lock: two workers doing the same job corrupts data or moves money twice. Now you need consensus-backed locks (etcd/ZooKeeper) plus fencing tokens enforced by the resource — or better, a design that needs no lock at all.

You probably don't need the lock

Most "we need a distributed lock" conversations I have been in ended somewhere better:

Stated need	Better tool
Only one worker processes each message	Consumer groups already partition work — Kafka does this natively
Don't double-charge on retry	Idempotency keys + unique constraint, not mutual exclusion
Single writer per entity	Route all writes for a key to one partition/actor — uniqueness by construction
Scheduled job must run once	Database row claim: UPDATE jobs SET owner=... WHERE id=... AND owner IS NULL, one winner guaranteed by the DB
Don't lose concurrent updates	Optimistic concurrency: version column + compare-and-swap, retry on conflict

A relational database you already run is a shockingly good lock service for coarse locks: SELECT ... FOR UPDATE SKIP LOCKED for work claiming, advisory locks for singleton jobs, with locks tied to the connection so a crashed holder releases automatically.

Takeaways

Every distributed lock is a lease, and every lease can outlive its holder's sanity — GC pauses guarantee it. Fencing tokens move enforcement from the trusting client to the resource, which is the only place enforcement actually works. Classify each lock as efficiency (Redis is fine) or correctness (consensus + fencing, or redesign). And treat "we need a distributed lock" as a prompt to look for the partition, constraint, or idempotency key that makes the lock unnecessary — the lock you never take is the only one with no failure modes.