Distributed locks, leases and fencing tokens
When you need mutual exclusion across machines and how to get it safely: lock services, leases with expiry, why Redis locks can fail, fencing tokens, leader election, optimistic alternatives, and avoiding locks altogether.
Reading is half of it. See this used in a real interview: walk through Design a Distributed Job Scheduler →
Sometimes exactly one machine should do something: run a scheduled job, process a partition, charge a card, hold a seat. On a single machine a mutex does it. Across machines, processes pause, networks partition and clocks drift, so a "lock" can be held by two processes at once without either noticing. Interviewers probe this whenever a design says "we take a lock". Knowing about leases and fencing tokens separates a careful answer from a naive one.
Why it is hard
A distributed lock must expire, or a crashed holder would block everyone forever. But expiry creates the danger:
- Process A acquires the lock with a 10-second lease.
- A pauses for 15 seconds (a long garbage collection, a stalled VM, a slow network).
- The lease expires; process B acquires the lock and starts writing.
- A wakes up, still believing it holds the lock, and writes too.
A has no way to know it was paused. No timeout value fixes this in general; it only makes it rarer.
Leases
A lease is a lock with a time limit that the holder must renew. Lock services such as ZooKeeper, etcd and Consul provide leases backed by consensus, so the lock state itself survives node failures. The holder:
- Renews well before expiry (every third of the lease).
- Stops work as soon as a renewal fails or it is unsure, before the lease could have expired.
- Treats the lease as advisory: a hint that it should be the only worker, not a guarantee.
See consensus and coordination.
Fencing tokens
The robust fix is to make the resource reject stale holders:
- Every time the lock is granted, the lock service returns a monotonically increasing token (33, then 34).
- The holder sends its token with every write.
- The storage system remembers the highest token it has seen and rejects writes with a lower one.
In the scenario above, B holds token 34 and writes; when A wakes and writes with token 33, the write is refused. Correctness no longer depends on timing. ZooKeeper's zxid or etcd's revision can serve as tokens. A conditional write (UPDATE ... WHERE version = ?) is the same idea.
Redis locks
SET key value NX PX 10000 is a quick, popular lock. Be honest about its limits:
- A single Redis instance is a single point of failure; with asynchronous replication, a failover can lose a lock and grant it twice.
- Redlock (majority across independent Redis nodes) still depends on timing assumptions and provides no fencing token.
- Release safely by deleting only if the value is still yours (a Lua script comparing a random value).
Redis locks are fine for efficiency (avoid doing the same work twice; occasional duplication is harmless). For correctness (double charging, overselling), use a consensus-backed service with fencing, or a database constraint.
Leader election
Leader election is a long-lived lock: one scheduler, one partition owner, one primary. The same rules apply: leases, renewals, and fencing tokens (often called epochs or terms) so that an old leader's actions are rejected after a new one takes over. See Design a Job Scheduler.
Often you do not need a lock
Many "lock" problems are better solved without one:
| Need | Lock-free approach |
|---|---|
| Do not sell the same seat twice | conditional update or unique constraint in the database |
| Process each job once | queue with visibility timeout plus idempotent handlers |
| One worker per partition | partition assignment by the consumer group |
| Do not crawl a URL twice | deduplication by key in a set or table |
| Avoid lost updates | optimistic concurrency with version numbers |
| Charge a card once | idempotency key stored with a unique constraint |
The database already provides atomic, durable mutual exclusion on a row. See transactions and isolation, Design Ticketmaster and Design a Web Crawler.
Choosing
- Can a database constraint, conditional write or idempotency key do it? Use that.
- Is duplicate work merely wasteful? A Redis lock with a TTL is enough.
- Must it never happen twice? A consensus-backed lease with fencing tokens checked by the resource.
Checklist
- Every lock has an expiry; holders renew and stop when unsure.
- Fencing tokens checked by the protected resource for correctness.
- Redis locks only for efficiency, released with a value check.
- Leader election with epochs that reject old leaders.
- Prefer constraints, conditional writes, idempotency and partition ownership over locks.