Hey everyone, welcome to the thirty-fifth issue of The Main Thread.
Locking across machines is harder than people usually think. Single-machine locks are a solved problem. The OS gives us a mutex which is backed by atomic CPU instructions. The kernel guarantees that exactly one thread holds it at a time. If the process dies, the lock dies with it. The world is sane.
Now spread that lock across three data centers, ten clients, and a Redis cluster. Now, add a GC pause, add clock skew, add a network partition. Suddenly the same primitive: “exactly one holder at a time” becomes on of the hardest problems in distributed systems.
The cautionary tale here is not hypothetical. In 2016, Martin Kleppmann (author of the famous DDIA) and Salvatore Sanfilipo (Antirez, creator of Redis) had a public, technical disagreement about whether Redis-based distributed locks were safe. The debate is still required reading for anyone building on top of distributed locks today, because the fundamental issues haven’t gone away.
If you are using a distributed lock for anything that matters, you need to understand what these locks actually guarantee, and what they don’t.
Let’s get into it.
Why Local Locks Don’t Generalize
A local mutex works because it sits on top of three guarantees the OS gives us:
Shared Memory: All threads see the same lock state instantly.
Atomic Operations: Compare-and-Swap on a memory address is indivisible.
Process Death = Lock Release: If the thread crashes holding the mutex, the OS cleans up.
As soon as we cross a network, all three guarantees vanish in the thin air.
There’s no shared memory between two services on different hosts because there’s a network in between, and the network can drop, delay, or reorder messages. There is no atomic CAS across machines unless we build one (and “building one” is most of what consensus algorithms do). And if a client dies holding a lock, nobody knows. The lock service is a separate process; it has no idea that the client is gone.
So distributed locks have to solve three problems that local locks get for free:
Mutual exclusion under failure: Only one client may hold the lock, even if other clients believe they hold it.
Liveness: A dead client must not hold the lock forever.
Safety under timing anomalies: Clock drift, GC pauses, and network delays must not allow two clients to both believe they hold the lock simultaneously.
Most simple distributed lock implementations get the first two right and silently fail at the third. The third property is where Kleppmann’s critique lives.
Naive Implementation (And Why It’s Wrong)
Here’s the lock everyone writes first:
# DO NOT use this in production
def acquire_lock(redis, key, client_id):
return redis.setnx(key, client_id) # Set if not exists
def release_lock(redis, key):
redis.delete(key)There are three bugs, all are serious.
Bug 1: No Expiration. If the client crashes while holding the lock, the key sits in Redis forever. No other clients can acquire it. We need a TTL.
Bug 2: Wrong owner can release. Any client can call DEL on the key. If client A’s lock expires, client B acquires it, the client A wake up and releases - it just released B’s lock.
Bug 3: Set-then-expire isn’t atomic. Even if we fix bug 1 with EXPIRE after SETNX, the client can crash between the two commands. We need them in one atomic operation.
Following is the correct version:
import secrets
def acquire_lock(redis, key, ttl_ms):
token = secrets.token_hex(16)
# SET key value NX PX ttl: atomic set-if-not-exists with TTL
acquired = redis.set(key, token, nx=True, px=ttl_ms)
return token if acquired else None
def release_lock(redis, key, token):
# Lua script: only delete if we still own it
script = """
if redis.call("get", KEYS[1]) == ARGV[1] then
return redis.call("del", KEYS[1])
else
return 0
end
"""
return redis.eval(script, 1, key, token)aThis is correct for a single Redis instance. The token solves the wrong-owner problem. The atomic SET with NX and PX solves the expiration race. The Lua script makes the release safe.
But we still have a single point of failure. If that Redis instance dies, our entire lock service is down. So we reach for replication. And the moment we do, we discover Redis replication is async - meaning a master can ACK a lock acquisition, the crash before the write reaches the replica, and a new client can acquire the same lock from the freshly-promoted replica.
That’s the problem Redlock was designed to solve.
Redlock Algorithm: Step by Step
Antirez proposed the Redlock algorithm in 2014 as a way to use multiple independent Redis masters to provide a distributed lock with stronger safety than single-instance locking with replication. The key point was: don’t replicate. Run N independent Redis masters and require a majority to agree.
To acquire a lock with N=5 instances:
Get the current time in milliseconds. Call this
T_start.Try to acquire the lock on all
Ninstances sequentially, using the same key and a random token. Use a small per-instance timeout (say, 50ms), much shorted than the lock TTL. If an instance is down or slow, skip it and move on.Compute the elapsed time:
T_elapsed = now() - T_start.Lock is acquired if:
the client got the lock on a majority of instances
[N/2] + 1, so 3 of 5)T_elapsed < TTL. The lock is still valid
The actual validity time of the lock is
TTL - T_elapsed - clock_drift_factor. That’s how long we have to do our work before the lock is unsafe.If the client failed to acquire (couldn’t get majority, or took too long), it must release the lock on all instances - even the ones it thinks it didn’t acquire, because requests can arrive late.
import time
import secrets
class Redlock:
def __init__(
self,
redis_instances,
retry_count=3,
retry_delay_ms=200
):
# List of independent Redis clients
self.instances = redis_instances
self.quorum = len(redis_instances) // 2 + 1
self.retry_count = retry_count
self.retry_delay = retry_delay_ms / 1000
self.clock_drift_factor = 0.01 # 1%
def acquire(self, resource, ttl_ms):
token = secrets.token_hex(20)
for attempt in range(self.retry_count):
start = int(time.monotonic() * 1000)
acquired_count = 0
for instance in self.instances:
if self._lock_instance(
instance, resource,
token, ttl_ms
):
acquired_count += 1
elapsed = int(time.monotonic() * 1000) - start
drift = int(ttl_ms * self.clock_drift_factor) + 2
validity = ttl_ms - elapsed - drift
if acquired_count >= self.quorum and validity > 0:
return {
"token": token,
"validity_ms": validity
}
# Failed: release on all instances
for instance in self.instances:
self._unlock_instance(
instance,
resource,
token
)
time.sleep(self.retry_delay)
return None
def _lock_instance(
self,
instance,
resource,
token,
ttl_ms
):
try:
return instance.set(
resource,
token,
nx=True,
px=ttl_ms
)
except Exception:
return False
def _unlock_instance(
self,
instance,
resource,
token
):
script = """
if redis.call("get", KEYS[1]) == ARGV[1] then
return redis.call("del", KEYS[1])
else
return 0
end
"""
try:
instance.eval(script, 1, resource, token)
except Exception:
passThe algorithm is clever. By requiring a majority, it tolerated up to [N/2] Redis instance failures. By subtracting elapsed time and clock drift from the TTL, it gives us the conservative validity window. By using independent masters with no replication, it sidesteps the failover-race problem.
So what’s wrong with it?
Kleppmann vs. Antirez Debate
In February 2016, Kleppmann published “How to do distributed locking”, arguing that Redlock has fundamental safety problems. Antirez responded the same week with “Is Redlock safe?” defending the algorithm. The exchange is one of the clearest examples of a real, technical, disagreement between domain experts in distributed systems, and both posts are worth reading in full.
Kleppmann’s core agreement has two parts:
Part 1: Redlock relies on bounded clock drift, but clocks aren’t reliable
Redlock’s safety argument depends on the assumption that the clocks on the Redis nodes don’t drift more than the small fudge factor we bake in. But system clocks can:
Jump forward or backward when NTP corrects (sometimes by significant amounts).
Be manually adjusted by an operator.
Drift differently on different physical machines.
Be affected by leap seconds (or by the OS smearing leap seconds over hours).
If a Redis nodes’s clock jumps forward, a held lock can expire on that node before its TTL would have naturally elapsed. If enough nodes have skewed clocks, a quorum can release prematurely, and another client can acquire the lock while the first believes it holds it.
This is a system model critique. Algorithms like Paxos and Raft are designed to be safe in an async model but they make no assumptions about timing. Their liveness depends on timing (we need messages to eventually arrive), but their safety (no two leaders, no two committed values) does not. Redlock’s safety, Kleppmann argues, depends on timing assumptions that real systems violate.
Part 2: Even with perfect clocks, GC pauses break it
Imagine this sequence:
Client 1: acquire lock (TTL = 10s) → success at t=0
Client 1: about to write to database → t=0
Client 1: stop-the-world GC pause → t=0 to t=15
Client 1: lock has expired during GC → t=10
Client 2: acquire lock → success at t=11
Client 2: writes to database → t=11
Client 1: GC ends, writes to database → t=15 ← UNSAFEClient 1 had no way of knowing the GC pause happened. It thought it still held the lock. It writes to the database, corrupting whatever client 2 just did.
The same scenario can happen with:
A long network delay between the client and the database
A page fault that swaps the client out for seconds
A hypervisor pausing a VM for migration
Any kind of process pause, anywhere in the stack
This is not a Redlock specific bug. It’s the problem of any lock that relies on TTL for safety. Kleppmann’s argument is that no lease-based lock can be safe by itself.
Antirez’s Response
Antirez pushed back on both points. His summarized argument was:
The clock assumption is reasonable in practice. Yes, clocks can jump, but in well-managed production systems with proper NTP configuration, drift is bounded enough that the algorithm holds. Many real systems make timing assumptions and are fine.
The GC argument applies to every lock. If the client can pause for longer than the lock TTL, no distributed lock can save us. Even Zookeeper, Chubby, or etcd-based locks have the same issue if we hold a lease and pause longer than the lease.
Redlock provides a useful set of guarantees for use cases where the lock is for efficiency (avoiding redundant work) rather than correctness (preventing data corruption).
Both sides are right about something important. The disagreement is really about what guarantees a distributed lock should provide, and what application code can reasonably be expected to handle.
The practical takeaway is the resolution Kleppmann proposed for the GC problem, which works for any distributed lock: fencing tokens.
Fencing Tokens: The Safety Net
A fencing token is a monotonically increasing number issued by the lock service every time a lock is acquired. The shared resource must check the token on every write and reject any token lower than the highest it has seen.
Client 1 acquires lock → gets token 33
Client 1 GC pauses
Lock expires
Client 2 acquires lock → gets token 34
Client 2 writes to storage with token 34 → accepted, storage remembers 34
Client 1 wakes up, writes to storage with token 33 → REJECTED (33 < 34)The shared resource enforces ordering even if the lock service makes a mistake. Even if two clients simultaneously believe they hold the lock, only one can successfully write - the one with the higher token.
class FencedStorage:
def __init__(self):
self.last_token = 0
self.data = None
def write(self, token, value):
if token <= self.last_token:
raise StaleTokenError(
f"Token {token} is stale (last seen: {self.last_token})"
)
self.last_token = token
self.data = valueThe crucial property is that the token check makes the lock’s safety independent of timing. The lock service can be wrong about who holds the lock - clock drift, network partition, GC pause, anything. The storage layer rejects the stale write regardless.
This is exactly what Zookeeper provides via its zxid (transaction ID), what etcd provides via its revision number, and what Google’s Chubby paper described decades ago as the “lock generation number”.
The catch is that in Redis-based Redlock, as originally specified, doesn’t give us a fencing token. The random token used in Redlock is for ownership identification - it lets us know if we still own the lock. It is not monotonic and cannot be used for fencing. To get fencing tokens, we need either:
A consensus based lock service (Zookeeper, etcd, Consul) that issues monotonic IDs natively
A separate sequencer service
A storage layer that uses optimistic concurrency control (compare-and-swap on a version number), which is essentially fencing by another name
If the shared resource cannot enforce a fencing token, no distributed lock can give us correctness under arbitrary client pauses.
Clock Drift and Time-Based Expiration
Kleppmann’s clock-drift argument is worth understanding deeply, because it applies to every lease-based system, not just Redlock.
A lease is a promise: “you hold this resource until the time T“. Both the issuer and holder need to agree on what time T is. They can’t talk to each other constantly (that defeats the purpose of lease), so they each consult their own clock.
If their clocks disagree:
Holder’s clock is slow. Holder thinks lease is still valid. Issuer thinks it expired and grants it to someone else. Now, there are two holders.
Holder’s clock is fast. Holder release early. Resource is briefly unowned. This is loss of liveness but no safety violation.
The standard mitigation is to use monotonic clocks (e.g., CLOCK_MONOTONIC on Linux, time.monotonic() in Python) instead of wall clock time for measuring durations. Monotonic clocks don’t jump backward when NTP corrects, and they are not affected by manual time changes. This is non-negotiable for any lock or timeout code.
But monotonic clocks don’t solve the cross-machine problem. Different machines have different monotonic clocks, and they drift relative to each other. The real fix:
Treat lease durations as a hint, not a guarantee. Reduce the effective lease validity by some safety margin. If the lease is 30 seconds, treat it as 25 seconds in the code. The remaining 5 seconds are budget for clock drift, processing time, and unexpected pauses.
Reduce leases proactively. Don’t hold a lease until it’s about to expire and then renew. Renew at, say, one-third of the lease duration, so we have two-thirds of the time as a buffer for failed renewals.
Detect your own pauses. Sample the monotonic clock before and after critical operations. If the gap is much larger than expected, you were paused - assume your lock has expired and abort the operation.
def with_lock(lock, ttl_ms, work):
lease = lock.acquire(ttl_ms)
if not lease:
raise LockAcquisitionFailed()
deadline = time.monotonic() + (lease.validity_ms / 1000) * 0.7 # 70% safety
try:
for step in work:
if time.monotonic() > deadline:
raise LeaseExpired("Aborting before unsafe write")
step()
finally:
lock.release(lease)This is a pragmatic compromise. It doesn’t eliminate the unsafety but shrinks the window. Combined with fencing tokens at the storage layer, it gets us to a place where the lock is genuinely useful for correctness.
Lease Based Locking: Chubby and Friends
Lease-based locks are the dominant pattern in real distributed systems. Google’s Chubby, Apache Zookeeper, etcd, Consul, and Hashicorp Vault all use lease-based built on top of consensus protocols.
The main difference is that these systems use consensus (Paxos, Raft, ZAB) to agree on a lock state, instead of using independent instances and quorum like Redlock. This matters because:
The lock state is a single value with strong consistency. Every node in the consensus group agrees on the current holder.
Failover is principled. If the leader dies, a new leader is elected with full knowledge of outstanding leases.
Monotonic IDs come for free. Every consensus operation has a sequence number which is perfect for fencing.
The trade-off is operational complexity. Running Zookeeper or etcd in production is non-trivial. They demand careful capacity planning, dedicated nodes, and an operational understanding of the consensus failure modes. Redis is often already in the stack, which is part of why Redlock is so tempting.
A typical Zookeeper-based lock looks like this:
def acquire_zk_lock(zk, lock_path, client_id):
# Create an ephemeral sequential znode
my_node = zk.create(
f"{lock_path}/lock-",
client_id.encode(),
ephemeral=True,
sequence=True
)
my_seq = int(my_node.split("-")[-1])
while True:
children = sorted(zk.get_children(lock_path))
my_index = children.index(os.path.basename(my_node))
if my_index == 0:
# We have lowest sequence number:we hold the lock
return my_node, my_seq# my_seq is the fencing token
# Watch the node immediately before us
predecessor = f"{lock_path}/{children[my_index - 1]}"
event = zk.exists(predecessor, watch=True)
if event is None:
continue # Predecessor already gone; re-check
event.wait() # Block until predecessor disappearsThree things this gives us that Redlock doesn’t:
Ephermeral znode: If the client dies (or its session times out), the node is automatically deleted. No need for a TTL on the lock value itself; the session is the lease.
Sequence number: That
my_seqis our fencing token. We pass it to our storage layer.Fair queueing: The sequential znode ordering means clients acquire the lock in the order they requested it.
We still have a GC and clock drift problems but the consensus blocked state and built-in fencing token put us in a much better position than Redlock alone.
When Not to Use a Distributed Lock At All
As always, the best distributed lock is the one we don’t need. Many systems reach for distributed locks when there’s a better tool.
Optimistic Concurrency Control
If the operation is “read, modify, write”, we should use compare-and-swap on a version number instead of a lock:
UPDATE account
SET balance = balance - 100, version = version + 1
WHERE id = 123 AND version = 5;If the version changed between your read and write, the update affects zero rows. Retry the whole operation. No lock needed. This works for any storage system that supports conditional writes such as most SQL databases, Dynamo DB ConditionExpression), Cassandra (lightweight transactions), etcd (transactions on revisions).
The cost of this is contention: if many clients fight for the same row, retries pile up. But for low-to-moderate contention, optimistic concurrency is simpler, faster and inherently safe.
Single-Writer Partitioning
If we can route all writes to a resource through a single process, we don’t need a lock. This is what Kafka does at the partition level: each partition has one consumer in a consumer group. The partition assignment, not a distributed lock, is the sync mechanism.
The same idea works in custom systems where we hash the resource id, route to a fixed worker, let the worker serialize work locally. We are using consistent hashing or partitioning as a coordination primitive instead of a lock.
Idempotency + Retries
If the operation is idempotent (see the previous issue here), we often don’t need exclusion at all. Two workers can both process the same job; the second one’s work is a no-op. The idempotency key is doing the work the lock would have done, with no liveness or safety concerns from a separate lock service.
Database Native Locking
If the resource we are protecting is already in a database, we can use the database’s locking instead of an external lock service. Postgres advisory locks pg_advisory_lock) give us mutual exclusion bound to the database session - when the session ends, the lock releases. No clock issues, no GC issues, no separate service to operate. The lock state is consistent with our transactional state.
-- Acquire an advisory lock on a 64-bit key
SELECT pg_advisory_lock(123456789);
-- Do work...
-- Release
SELECT pg_advisory_unlock(123456789);This is criminally underused. If our “distributed lock” is really protecting access to a single database, advisory locks are almost always the right answer.
Locks for efficiency vs locks for correctness
Antirez made this distinction in his Redlock response, and it’s more useful frame for deciding what to do:
Locks for efficiency: The lock is an optimization. Without it, multiple workers do redundant work, but nothing is corrupted. (Example: a cron-style task we’d prefer not to run twice in parallel, but running twice is harmless).
Locks for correctness: The lock is required for safety. Without it, we corrupt data. (Example: a payment that must not be processed twice)
For efficiency: Redlock or any distributed lock is fine. The occasional lock failure is a wasted CPU cycle, not a corruption.
For correctness: a lock alone is not enough. We need fencing tokens, idempotency, conditional writes, or some combination. We should treat the lock as a contention reduction mechanism on top of a fundamentally safe storage layer.
If we can’t articulate which category our code falls into, we don’t yet understand what our code requires.
Checklist
Before we ship anything that depends on a distributed lock:
Design:
We have identified whether the lock is for efficiency or correctness
If for correctness, the storage layer enforces fencing tokens or conditional writes
We can articulate what happens if two clients believe they hold the lock simultaneously
Implementation:
Lock acquisition is atomic (no SETNX-then-EXPIRE races)
Release checks ownership (Lua script or equivalent — never blind DELETE)
All timing code uses monotonic clocks, not wall clocks
Lease validity is reduced by a safety margin in client code
Critical sections check elapsed time and abort if the lease may have expired
Operations:
NTP is configured and monitored on all lock-service nodes
Lock service failures are alerted on
We have a runbook for "what if the lock service is down", including degraded modes
Alternatives considered:
We have ruled out optimistic concurrency control
We have ruled out single-writer partitioning
We have ruled out database-native advisory locks
We have ruled out idempotency + retries
Takeaway
Distributed locks are a leaky abstraction over a hard problem. They look like familiar mutexes, but they are not, and treating them as if they were is how we end up with the kind of bugs that take days to diagnose and weeks to fix.
The Kleppmann/Antirez debate matters because both are technically correct within their respective models. The debate also forces us to think clearly about what our lock actually guarantees. Remember, if we are betting your data integrity on a TTL-based lock, we have already lost. The safety has to live in the storage layer, via fencing tokens or conditional writes. The lock is just a contention-reduction mechanisms on top.
If we remember three things:
Fence at storage layer. Locks alone can’t give us correctness under arbitrary client pauses.
Use monotonic clocks and conservative lease validity. Wall-clock arithmetic in lock code is a bug waiting to happen.
Prefer not locking at all. Optimistic concurrency, partitioning, advisory locks, and idempotency solve most problems without the failure modes of distributed locks.
We will write code that survives the conditions distributed locks were never quite designed for.
Have you debugged a lock related production incident? I love to hear war stories - clock jumps, GC pauses, replication races, the works. The patterns repeat across companies, and the post-mortems are some of the best teaching material in the field.
Hit reply. I read everything.
Namaste!
— Anirudh
