At 2:47 AM, two background workers on separate machines both check the job queue. Both see the same pending job. Both claim it. Both execute it. The job runs twice.
In one case, a user is charged twice for a subscription. In another, two conflicting database writes corrupt a record. Nobody notices until a customer calls.
Neither worker had a bug. Both followed their logic correctly. The problem is that mutual exclusion stops working when the processes are on different machines.
Why a Mutex Is Not a Distributed Lock
On a single machine, a mutex is a shared variable the OS kernel arbitrates. If the holder crashes, the kernel releases the lock immediately.
Across machines, there is no shared variable. There is only a network. The arbitration becomes a distributed protocol. The failure modes expand to network partitions, clock skew, and crashes mid-critical-section.
A distributed lock has the same three operations: acquire, hold, release. None of them carry the single-machine guarantees.
Acquire requires a round-trip to an external service. The network may drop the response. The caller may not know whether acquisition succeeded.
Hold has no enforcement mechanism. No kernel watches. If the holder crashes, nothing releases the lock automatically unless a TTL is set.
Release requires a round-trip. The process may crash first. The release message may be lost. Another process may have acquired the lock already through TTL expiry.
A distributed lock is not a mutex with network overhead. It is a fundamentally different primitive.
The TTL Trap
The most common design sets a TTL on the lock. If the holder crashes, the lock expires automatically. This is the source of the most dangerous failure mode.
Consider this sequence:
// Process A acquires lock with TTL = 10 seconds
lock = acquire("job-42", ttl=10_seconds)
data = load_record("job-42")
// Process A is paused: GC stop-the-world, OS preemption, slow network
// ... 11 seconds pass ...
// Lock expires. Process B acquires the lock.
// Process B starts working on the same record.
// Process A resumes.
// Process A writes its result — overwriting Process B's work.
// Both A and B believe they completed the job successfully.
Process A did not crash. A pause — garbage collection, OS scheduling, network delay — made the lock expire before the work finished. Two processes are in the critical section simultaneously. Neither knows it.
This is FM12 — Split-Brain. A longer TTL does not eliminate it. Only fencing tokens do.
Fencing Tokens: Where the Safety Guarantee Actually Lives
A fencing token is a monotonically increasing number the lock service issues on every acquisition. Every new acquisition gets a higher token than the last.
The storage layer that the lock protects tracks the highest token it has seen. It rejects writes carrying an older token.
// Lock service issues a fencing token with each grant
function acquire_lock(resource):
token = atomic_increment(lock_service.counter)
lock_record = {holder: this_process_id, token: token, expires_at: now() + TTL}
success = lock_service.set_if_absent(resource, lock_record)
if success: return Lock(resource=resource, token=token)
return None
// Storage enforces token ordering
function storage_write(resource, data, fencing_token):
current_max = storage.get_max_seen_token(resource)
if fencing_token <= current_max:
raise StaleWriteError("token {} rejected, current max is {}"
.format(fencing_token, current_max))
storage.set_max_seen_token(resource, fencing_token)
storage.write(resource, data)
// The split-brain scenario, with fencing
lock_a = acquire_lock("job-42") // A gets token=7
// A pauses 11 seconds. Lock expires.
lock_b = acquire_lock("job-42") // B gets token=8
storage_write("job-42", b_result, token=8) // succeeds
// A resumes and tries to write
storage_write("job-42", a_result, token=7) // REJECTED: token 7 < 8
Fencing shifts the safety guarantee from the lock service to the storage layer. Even if the lock service has a bug, even if the TTL is too short, even if a process pauses for minutes, stale writes are rejected. The invariant — only the most recent holder's writes succeed — is enforced where it matters.
If your logs show lock token does not match existing lock or a similar stale-write rejection, fencing is doing its job. That message is the sound of split-brain being caught at the storage layer.
Redis-Based Locks and Their Limits
Redis is commonly used because it is fast and supports atomic operations. The simplest Redis lock uses SET key value NX PX ttl — set only if absent, with an expiry.
Release must verify ownership through a Lua script that checks the token before deleting. Otherwise a process whose lock has expired can release a lock now held by someone else.
// Release verifies ownership atomically via Lua
script = """
if redis.call("GET", KEYS[1]) == ARGV[1] then
return redis.call("DEL", KEYS[1])
else
return 0
end
"""
The single-node Redis lock has a fatal flaw. If the Redis node fails after granting a lock but before the TTL expires, a replica promoted to primary has no record of the lock. Another process acquires it immediately.
Redlock addresses this by requiring a majority of N independent Redis nodes to agree. N should be odd; five is the recommended value. The lock is valid only if a majority accepted it and enough of the TTL remains after acquisition to be useful.
Redlock's correctness depends on clock drift being small relative to the TTL. Martin Kleppmann's 2016 critique demonstrated that Redlock cannot guarantee safety in all network partition scenarios.
The practical rule: Redis Redlock fits idempotent operations and best-effort deduplication. It does not fit financial transactions or critical record updates.
ZooKeeper: No TTL to Expire Prematurely
ZooKeeper provides ephemeral nodes. These are automatically deleted when the client session that created them ends. A crashed client's session expires, and its ephemeral nodes disappear.
Each lock attempt creates an ephemeral sequential node under /locks/resource/. ZooKeeper assigns a sequence number. The client with the smallest sequence number holds the lock. Others watch the node immediately before them to avoid FM7 — Thundering Herd on release.
The key property: there is no TTL. The lock is held exactly as long as the session is alive. If the holder pauses for 30 seconds, it still holds the lock. No other process can acquire it. If the process dies, ZooKeeper detects session expiry within the session timeout — typically two to ten seconds — and deletes the ephemeral node.
The cost is that ZooKeeper itself must be highly available. That means running five nodes in a quorum. ZooKeeper is a serious operational commitment.
etcd, used by Kubernetes, provides the same abstraction with lease-based locks and session expiry. Google's internal Chubby, built on Paxos, inspired both.
When You Should Not Use a Lock At All
Many workloads do not need a lock. Compare-and-swap (CAS) is an atomic operation that updates a value only if it currently matches an expected value.
function update_record_with_cas(db, record_id, new_value):
for attempt in range(max_retries):
current = db.get(record_id)
new_record = compute_new_state(current, new_value)
new_record.version = current.version + 1
try:
db.conditional_write(
record_id=record_id, value=new_record,
condition="version == " + str(current.version))
return success
except ConditionalCheckFailed:
backoff(attempt)
continue
CAS eliminates the lock service entirely. The storage system provides atomicity directly. When write contention is low, CAS is faster than acquiring a distributed lock. When contention is high, CAS degrades — many writers retry, amplifying load on the database.
Use CAS when conflicts are rare and retries are cheap. Use distributed locks when conflicts are common and wasted work is unacceptable. DynamoDB conditional writes implement this pattern at storage-layer scale.
Sometimes the correct answer is neither. Partition the work. If each worker owns a disjoint subset of records, there is no shared state and no lock is needed. Partition first. Reach for the lock only when partitioning fails.
The Real Tradeoffs
AT1 — Consistency vs Availability. A distributed lock enforces consistency at the cost of availability. If the lock service is down, no work proceeds. CAS degrades to retry loops rather than blocking — lower consistency guarantee, higher availability.
Lock granularity vs contention. A lock on the whole table serialises every writer. A lock per record allows parallel writes but multiplies coordination overhead. Pick the smallest scope that prevents the conflict you care about.
TTL length vs safety window. A long TTL survives slow operations but leaves the system locked longer after a crash. A short TTL recovers faster but risks expiry during legitimate slow work. No single TTL is always right.
Where It Fails
FM12 — Split-Brain. TTL expires while the holder is paused. A second process acquires the lock. The first resumes without checking. Fencing tokens block the damage. They do not prevent the scenario.
FM5 — Latency Amplification. Fifty workers wait behind a 500ms lock holder. The last worker waits 25 seconds. Measure lock wait time separately from hold time. If wait dominates, the lock is the bottleneck.
Deadlock across two resources. A holds lock-1 and waits for lock-2. B holds lock-2 and waits for lock-1. No kernel inspects the graph. Prevent it by acquiring multiple locks in a consistent order.
Lock renewal failure. Long operations renew the lock before TTL expiry. A failed renewal expires the lock mid-operation. Renewal adds a second category of failure the caller must handle.
The Signal That Tells You This Applies
Two instances of a background worker produce conflicting results for the same job. A database record contains partially applied updates from two concurrent writers. Your job queue shows the same job completed twice by different workers.
These are split-brain in production. If you see them and have no fencing token in your storage layer, your distributed lock is protecting nothing under load.
The harder question the book takes up: how do you build a lock service whose safety does not depend on synchronised clocks?
The full framework treatment — compression blocks, three-level exercises, and the complete AT/FM mapping — is in Book 3: Scaling Systems, Chapter 23 (Distributed Locks). Free chapter available at computingseries.com/books/book3.