Distributed Locks, Fencing Tokens & Leases

Distributed Locks, Fencing, and Leases

On one machine, a mutex guarantees that only one thread runs a critical section. Across machines, there is no such guarantee. A "distributed lock" is really a lease: a lock service grants ownership for a limited time, and the holder must renew it before it expires. That time limit is what lets the system recover when a holder crashes — and it is also what breaks mutual exclusion. If the holder pauses for longer than the lease (a long garbage collection, a frozen virtual machine, a slow disk, a network partition), the lease expires, another process acquires it, and the original holder wakes up still believing it owns the lock. Now two processes write at once.

No lock service can prevent this on its own, because the paused process cannot know it was paused. The fix is to make the protected resource reject stale holders, using fencing tokens — or to design so that correctness never depends on a lock.

TL;DR

Distributed locks are leases: time-limited, renewable grants of ownership.
A holder can lose its lease without knowing — through GC pauses, VM freezes, or network delays — and keep acting.
Fencing tokens fix this: each grant carries a strictly increasing number, and the resource rejects writes with older tokens.
Use a consensus-backed lock service (etcd, ZooKeeper, Kubernetes Lease) for correctness; Redis locks are fine for efficiency (avoiding duplicate work), not for safety.
Make expected assumptions explicit: maximum pause, clock drift, and lease duration.
Often the better design is no lock: conditional writes, idempotency, partition ownership, or database constraints.

Quick Example

The failure, as a timeline:

The fencing check lives in the resource being protected — here, a conditional database update:

To reproduce this in a test, acquire a short lease, sleep past its TTL inside the critical section, let a second worker acquire and write, then resume the first worker and assert its write is rejected.

Core Concepts

Leases

A lease combines ownership with expiry. The holder renews it periodically (heartbeats); if the holder crashes, renewals stop and the lease expires, letting another process take over. The lease duration trades failover speed (short leases recover faster) against false expiry (short leases expire during ordinary pauses).

Why Holders Lose Leases Without Knowing

A process checking "is my lease still valid?" right before writing does not help: the pause can happen between the check and the write.

Fencing Tokens

Every time the lock service grants the lease, it issues a monotonically increasing token. The holder sends the token with every write, and the resource remembers the highest token it has accepted, rejecting anything lower. Consensus systems provide natural tokens: etcd revisions, ZooKeeper zxids or sequential node numbers. If the resource cannot check tokens — an external API, a file on shared storage — the lock cannot be made fully safe, and the design must tolerate duplicates.

Efficiency Locks Versus Correctness Locks

Lock Services

Leader election is the same problem: an old leader that does not know it was replaced must be fenced.

Designs That Avoid Locks

Conditional writes: compare-and-set with version columns or ETags — the resource itself enforces ordering.
Idempotent operations: duplicates become harmless. See Idempotency.
Single ownership by partition: assign each key to one consumer (Kafka partitions, consistent hashing) so no lock is needed. See Consistent Hashing.
Database constraints and transactions: unique constraints, SELECT ... FOR UPDATE, or SKIP LOCKED job queues within one database.
Consensus for state, not just locks: store the decision itself in a strongly consistent store. See Distributed Consensus.

Best Practices

Write Down the Assumptions

Document lease duration, renewal interval, maximum tolerable pause, and what happens if two holders act at once. If the answer is "data corruption", fencing is mandatory.

Fence at Every Resource

Every write path protected by the lock must carry and check the token — including retries, background flushes, and cleanup jobs.

Renew Early and Stop Promptly

Renew well before expiry (for example at one third of the TTL) and stop work immediately when renewal fails, while still relying on fencing for safety.

Test With Injected Pauses

Simulate long pauses inside critical sections in tests and chaos experiments to prove that stale holders are rejected. See Chaos Engineering.

Common Mistakes

Redis Locks for Correctness

Checking Validity Before Writing

Long Leases to "Fix" Expiry

FAQ

What is a distributed lock?

A mechanism that lets one process at a time across multiple machines own a resource or task, usually implemented as a time-limited lease granted by a coordination service and renewed by the holder.

What is a fencing token?

A strictly increasing number issued with each lock or lease grant. The holder includes it with every write, and the protected resource rejects writes whose token is lower than one it has already seen, blocking stale holders.

Is Redlock safe?

It is widely debated. Because it relies on timing assumptions and provides no fencing tokens, it should not be used where correctness depends on mutual exclusion. It is reasonable for efficiency, such as avoiding duplicate work.

How long should a lease be?

Long enough to survive normal pauses and renewal delays, short enough for acceptable failover time — often seconds to tens of seconds — with renewal well before expiry. Safety must come from fencing, not from choosing the perfect duration.

When do I not need a distributed lock?

When the operation can be made idempotent, when a single database transaction or constraint can enforce the rule, or when work can be partitioned so each key has exactly one owner.