Concurrency
Part 1 of 6 · Distributed locksDistributed Locks — Correctness, Leases & Fencing Tokens
Distributed locks need mutual exclusion, crash safety via leases, and fencing so stale holders cannot corrupt shared state. Prefer CAS/queues when you do not need a multi-step exclusive critical section.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
How you serialize writers across machines
Prefer
Lease + monotonic fencing token at storage
The lock service grants a time-bounded lease and a sequencer. Storage rejects writes whose fence is older than the last accepted token. Crashes expire. Pauses cannot corrupt.
- Mutual exclusion for the critical section; the resource still checks the fence.
- Prefer ZooKeeper/etcd or DB CAS when losing exclusion corrupts money or inventory.
- Single Redis + fencing is enough for soft coordination, not for consensus.
Alternative
SET NX and hope, or a lock with no TTL
Looks like mutual exclusion on a whiteboard. GC pauses, clock skew, and partitions produce two holders. A hard lock without expiry deadlocks forever after a crash.
- TTL without fencing is a footgun for shared mutable state.
- Redlock’s majority of independent Redis nodes is contested (Kleppmann).
- High-frequency per-request locks add latency and availability risk — prefer CAS or a queue.
Failure path the hub exists to name
Each hop is a later lesson. Interviews start at the stale holder, not at Redis trivia.
- 1
Acquire a lease
Lock service returns a holder token and a TTL. Depth: Redis SET NX EX, or ZK/etcd sessions. - 2
Pause past TTL
GC, SIGSTOP, laptop sleep, or a partition. The lease expires while the client still believes it is owner. - 3
Second client acquires
Deadlock freedom: a new holder gets a higher fence. Depth: fencing tokens. - 4
Stale write arrives
Without a storage check, last writer wins and the invariant is gone. - 5
Storage rejects the old fence
Monotonic token at the resource. Renew failures cancel the critical section. Depth: leases, then CAS when a lock was never needed.
Overview
Interview prompt: design a distributed lock for a multi-writer system. Seniors are graded on failure modes — GC pauses, clock skew, partitions — not on Redis trivia.
A distributed lock gives mutual exclusion across processes and machines so only one holder may mutate a shared resource at a time. Local mutexes do not work across nodes. You need a shared coordination service (or the data store itself) to decide who may enter a critical section that spans processes.
Correctness needs more than a TTL: mutual exclusion, deadlock freedom under crashes, and fencing so a paused stale holder cannot write after its lease expires. Prefer leases + monotonic fencing tokens (or CAS/optimistic designs) over "SET NX and hope" when the resource is mutable and correctness-critical.
This hub is the map. The five sibling pages are the whiteboard depth.
You should be able to:
- Draw acquire → work → expire-while-paused → second acquire → stale PUT, with and without a fence.
- Say when you would refuse to introduce a lock.
- Contrast Redis vs ZooKeeper/etcd vs CAS in one sentence each — without re-teaching Raft log replication or in-process mutexes.
What a distributed lock is for
Typical uses:
- Leader election / single-writer for a shard
- Deduplicating a rare expensive job (with care)
- Serializing migrations or schema changes
Anti-uses (prefer the CAS lesson):
- High-frequency per-request mutual exclusion (latency + availability hit)
- Making non-idempotent APIs "safe" (use idempotency keys)
- Replacing a queue / single-writer partition key
Cache stampede coalescing is a different job: SET NX PX to collapse duplicate fills. That lesson is single-flight locking — do not re-teach waiter polling here.
Properties you must name
| Property | Meaning | Failure if missing |
|---|---|---|
| Mutual exclusion | At most one holder for the resource | Two writers, silent corruption |
| Deadlock freedom under crash | Client death must not pin the lock forever | Usually a TTL / lease |
| Fault tolerance of the lock service | The coordinator survives some failures | Redis failover vs ZK/etcd quorum — different stories |
| Fencing | Storage rejects stale holders | TTL/lease locks are unsafe after GC or partition |
Lease vs lock: a lease is a time-bounded grant that auto-expires; a hard lock needs explicit release. Production almost always uses leases + renewals. Depth: lease renewal, clock skew, heartbeats.
Redis vs ZooKeeper/etcd vs CAS
| Approach | Wins | Loses |
|---|---|---|
Single Redis SET NX EX | Fast, one round-trip, fine for soft work if you also fence | Not consensus; replica promotion can resurrect locks |
| Redlock | Majority of independent Redis nodes | Kleppmann: clocks, GC, correlated failure — poor for correctness-critical exclusion |
| ZooKeeper / etcd | Quorum log, ephemeral/lease-bound keys, session as fence boundary | Higher latency and ops cost |
| CAS / conditional writes | No lock-service dependency; version is the fence | Retry storms under contention; weak for multi-step multi-key work |
Depth: Redis vs Redlock, ZK/etcd recipes, CAS. ZooKeeper and etcd are lock recipes on top of consensus — not a re-teach of Raft.
Architecture (stale holder)
Client A acquires, then pauses past the TTL. Client B acquires and writes. A resumes and writes. Without a fence at storage, last writer wins.
Sequence
- 1
1 Client A → 2 Lock service
acquire lease TTL=10s
- 2
2 Lock service → 1 Client A
holding
- 3
1 Client A
GC / partition 20s
- 4
2 Lock service
lease expires
- 5
4 Client B → 2 Lock service
acquire
- 6
2 Lock service → 4 Client B
holding
- 7
4 Client B → 3 Storage
PUT x=B
- 8
3 Storage → 4 Client B
OK
- 9
1 Client A
resumes, still believes owner
- 10
1 Client A → 3 Storage
PUT x=A
- 11
3 Storage → 1 Client A
OK without a fence
Lesson map
Distributed Locks — Correctness, Leases & Fencing Tokens
Distributed locks need mutual exclusion, crash safety via leases, and fencing so stale holders cannot corrupt shared state. Prefer CAS/queues when you do not need a multi-step exclusive critical section.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1 Client A"] l["2 Lock service"] s["3 Storage"] b["4 Client B"] a -->|acquire lease| l l -->|holding| a b -->|acquire| l l -->|holding| b b -->|PUT x=B| s s -->|OK| b
Fencing is the storage check. Depth: fencing tokens.
Decisions
- 1
1 Write + fence F
- next2 F >= last_fence?
- ?
2 F >= last_fence?
- no3 Reject stale holder
- yes4 Apply write
- 3
3 Reject stale holder
- 4
4 Apply write
- next5 last_fence = F
- 5
5 last_fence = F
Sandbox: lease without a fence vs with a fence (Python)
Educational in-memory lock + storage. A pause past TTL lets B acquire. The unfenced store accepts A's late write; the fenced store rejects it.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same idea (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Fail-open vs fail-closed
If the lock service is down: correctness-critical paths fail-closed (refuse to write). Best-effort features may degrade. Never silently proceed as if you hold the lock.
Cross-region locks amplify latency and partition pain. Prefer regional single-writer + async replication, or consensus spanning regions with eyes open on RTT.
How you test
Jepsen-style partitions, forced GC pauses, clock jumps, delayed unlocks, concurrent renewals. Assert storage never accepts a lower fence after a higher one. Size lease TTL greater than work p99 + renew RTT + GC budget, short enough for acceptable failover. Measure renew failures and fence rejects in prod.
Pitfalls
Draw lock service, storage, clients A and B. A acquires, then a 20s GC pause. The lease is 10s. Where does B's acquire go? Where does A's late PUT go with no fence, and with a monotonic token at storage? Now kill the lock service. Do you fail-open or fail-closed?
Interview Q&A
What properties must a distributed lock provide?
Answer
Mutual exclusion, deadlock freedom under client crash (usually via TTL/lease), and fault tolerance of the lock service. For mutable shared state, add fencing.
Why is TTL alone insufficient?
Answer
A holder can pause (GC, SIGSTOP, network) past the TTL, another client acquires, then the first resumes and writes. Without a fencing check at the resource, you get silent corruption.
Lease vs lock?
Answer
A lease is a time-bounded grant that auto-expires; a hard lock needs explicit release. Production almost always uses leases + renewals.
When would you refuse to introduce a distributed lock?
Answer
When idempotency keys, single-writer partitions, or CAS on a version column already solve the race — locks add ops and availability risk.
Redis SET NX EX — safe?
Answer
Safe as best-effort mutual exclusion on a single healthy Redis if you also fence at storage. Not a consensus algorithm; single-node failure modes apply. Depth: SET NX EX vs Redlock.
Is Redlock correct?
Answer
Controversial. Kleppmann argues independent Redis nodes + clock/GC assumptions do not give safety for correctness-critical work. Antirez disagrees on practical risk. Prefer etcd/ZK or DB fencing for critical paths.
How do ZooKeeper locks work at a high level?
Answer
Ephemeral sequential nodes under a path; lowest sequence wins; watch predecessor; session expiry releases. Session is the fence. Depth: ZK/etcd recipes.
What is a fencing token?
Answer
A monotonic number issued on each successful acquire. Storage rejects writes with tokens older than the last accepted token for that resource.
Fail-open vs fail-closed if the lock service is down?
Answer
Correctness-critical paths fail-closed (refuse to write). Best-effort features may degrade. Never silently proceed as if you hold the lock.
How do you size lease TTL?
Answer
Greater than work p99 + renew RTT + GC budget; short enough for acceptable failover. Measure renew failures and fence rejects in prod.
Can two regions share one lock?
Answer
Cross-region locks amplify latency and partition pain. Prefer regional single-writer + async replication, or consensus spanning regions with eyes open on RTT.
How do you test a lock implementation?
Answer
Jepsen-style partitions, forced GC pauses, clock jumps, delayed unlocks, concurrent renewals. Assert storage never accepts a lower fence after a higher one.