Distributed Locks and Coordination Services
On this page
A naive distributed lock
Three workers process files from shared storage. To avoid two working on one file, each takes a lock first:
acquire lock "file-42" -> do the work -> write results -> release lockWhat if a worker crashes while holding the lock? Nobody else can ever take it. So locks get an expiry: a lease. And that introduces the real problem.
How a lease-based lock fails: the paused holder
- Worker A acquires the lock on
file-42with a 10-second lease. - A stops for 15 seconds: a garbage collection pause, a VM migration, a swapped-out process.
- The lease expires. Worker B acquires the lock and starts writing results.
- A resumes. From A's point of view, no time passed; it still "holds" the lock and writes its results too.
Now two workers have written, and one overwrote the other. Renewing the lease more often doesn't help: A was paused and couldn't renew. Checking the lease right before writing narrows the gap but doesn't close it; A could pause between the check and the write. Martin Kleppmann's 2016 analysis of distributed locking walks through exactly this.
Fencing tokens
Make the resource enforce the lock:
- Each time the lock is granted, the lock service hands out an increasing token: 33, then 34, and so on. ZooKeeper's znode version or zxid, or etcd's revision, serve as tokens.
- Every write to the protected resource includes the token.
- The resource remembers the highest token it has accepted and rejects any write with a lower one.
A acquires lock -> token 33 -> pauses
B acquires lock -> token 34 -> writes with 34 (storage records 34)
A resumes -> writes with 33 (rejected: 33 < 34)This requires the resource to check tokens: a conditional update in a database (UPDATE ... WHERE fence < :token), an object store's conditional write, or an application-level check. If the resource can't check tokens, no lock can be made fully safe against pauses.
Here's the database side, tested in SQLite. The row remembers the highest token that has written to it, and the update only applies when the new token is higher:
# fence.py: the storage rejects a write from a lock holder whose token is out of date
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE results (file TEXT PRIMARY KEY, body TEXT, fence INTEGER NOT NULL)")
db.execute("INSERT INTO results VALUES ('file-42', '', 0)")
def write(file, body, token):
cur = db.execute("UPDATE results SET body = ?, fence = ? WHERE file = ? AND fence < ?",
(body, token, file, token))
return "written" if cur.rowcount == 1 else "rejected: a newer lock holder already wrote"
print("B, token 34:", write("file-42", "B's results", 34))
print("A, token 33:", write("file-42", "A's results", 33)) # A wakes up from its pause
print(db.execute("SELECT body, fence FROM results").fetchone())B, token 34: written
A, token 33: rejected: a newer lock holder already wrote
("B's results", 34)A's write reached the database after B's, and the database turned it away. Neither worker had to know about the other: the comparison in the WHERE clause did all the work, in the one place both writes meet.
Coordination services and Redlock
etcd, ZooKeeper and Consul are built for this: small, strongly consistent (CP) stores running consensus, with primitives for leases, watches, ordered sequential keys and transactions (Day 19). They provide correct lock ownership and tokens. Redis-based locks are a different matter. Redlock takes the lock on a majority of independent Redis nodes, each with its own expiry. It has two weaknesses where correctness matters: it hands out no fencing token, so the paused-holder problem above remains, and it assumes every node's clock runs at about the same rate, because each node expires the key on its own timer. That's fine for an efficiency lock, where a rare double run only wastes work. For a correctness lock, where a double run corrupts data, use a consensus-based store and fencing tokens.
Do you need a lock at all?
Often a different design removes the need:
| Instead of a lock | Use |
|---|---|
| Preventing duplicate processing | Idempotent processing with unique keys (Day 21) |
| Updating a record safely | Optimistic concurrency: a version column and conditional update |
| Ensuring one worker per item | Partitioning: each item belongs to exactly one consumer (as in Kafka consumer groups) |
| A uniqueness rule | A unique constraint in the database |
Use locks when you need mutual exclusion over something those can't express, and then use fencing.
Check yourself
A paused process can't renew; its lease expires, another client takes the lock, and the paused process resumes still believing it holds it.
The resource itself must check each write's token and reject writes with a token lower than the highest it has already accepted. If the storage can't do that check, a paused former holder can still write, whatever the lock service does.
Make processing idempotent with unique keys, or use optimistic concurrency with conditional updates; partitioning work by key and unique constraints also help.
It issues no fencing token, so a paused holder can still write after its lock expires, and its safety depends on all nodes' clocks running at similar rates.