How Distributed Locks Actually Work: Redis Redlock, ZooKeeper, and the Pitfalls

Quick Answer

A distributed lock makes sure only one process, out of many running on different machines, is allowed to touch a shared resource at a time, something a normal in-process mutex can't do across machines. Redis's Redlock algorithm does this by requiring a majority of independent Redis nodes to agree a client holds the lock within a time window; ZooKeeper and etcd do it more strongly using ephemeral nodes or leases backed by real consensus. They are not interchangeable, and Redlock has a well-documented safety gap that matters if correctness, not just efficiency, is on the line.

Why a normal mutex doesn't cross machine boundaries

An in-process mutex works because every thread trying to acquire it shares the same memory, the lock is just a variable one thread can see and flip. The moment your "only one worker should process this job" requirement spans multiple machines, that shared memory doesn't exist anymore. You need some external system that every worker, regardless of which machine it's on, can ask the same question: "is this resource currently locked, and by whom?"

This is a genuinely different problem from two others that sound similar and that this site has already covered in detail. Row-level database locking (optimistic vs pessimistic locking) is about controlling concurrent writes to a specific database row, scoped to that one database. Leader election is about picking exactly one coordinator node for an extended period, usually the lifetime of a service. A distributed lock is more general and usually shorter-lived: an arbitrary resource, often not even in a database at all, an S3 object, a cron job, a queue partition, and a lock that's acquired, used briefly, and released, over and over.

The two dominant approaches to building one are: a fast, best-effort lock built on a key-value store like Redis (Redlock), or a slower but stronger lock built on a consensus system like ZooKeeper or etcd. They are not drop-in replacements for each other, and picking the wrong one for what you're protecting is a real, documented source of production incidents.

The basic building block: SET NX PX

Redis has a single atomic command that does almost everything a basic lock needs: SET key value NX PX milliseconds. NX means "only set this key if it doesn't already exist," which is what makes exactly one client win when several race to acquire the same lock. PX attaches an expiry in milliseconds, an automatic safety net: if the client that holds the lock crashes before releasing it, Redis deletes the key on its own after the expiry, instead of the lock staying held forever.

SET lock:job:4471 f83a9c21 NX PX 30000

The value (f83a9c21 above) should be a random token unique to this specific acquisition attempt, not a constant like "locked". That token matters for releasing the lock safely: a naive release just does DEL lock:job:4471, but that's wrong, because if this client's operation ran slower than expected and the lock already expired and got acquired by a second client, an unconditional DEL would delete the second client's lock, not this client's own. The correct release checks the token first and only deletes if it still matches, and it has to do that check-and-delete as one atomic step (a small Lua script run via EVAL) so another client can't slip in between the check and the delete:

if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

This single-key, single-node version already has an obvious weak point: it depends on one Redis instance. If that instance goes down, or fails over to a replica before the lock key has replicated (Redis replication is asynchronous by default), you can end up with two clients both believing they hold the lock. Redlock exists specifically to reduce, not eliminate, that risk.

Redlock: the same idea across N independent nodes

Redlock runs the SET NX PX primitive above against N independent Redis nodes (5 is the number used in the original proposal), that don't replicate each other, and requires a majority to agree before considering the lock acquired. The exact algorithm, as specified by Redis, has five steps:

1. Get the current time in milliseconds.
2. Try to acquire the lock (same key, same random value) on each of the N nodes in turn, using a short per-node timeout so one slow or dead node can't stall the whole attempt.
3. Compute how much time has elapsed doing step 2.
4. The lock is considered acquired only if the client got it on a majority of nodes (at least N/2 + 1, so 3 out of 5) and the elapsed time from step 3 is still less than the lock's total validity window.
5. If acquisition failed (no majority, or too much time elapsed), immediately release the lock on every node it was acquired on, so a failed attempt doesn't leave partial locks scattered across the cluster.

The reasoning behind requiring a majority across independent nodes: any single node failing (crash, network partition, slow disk) affects at most a minority, so the lock's availability and correctness don't hinge on any one instance the way the single-node version does. This is a real improvement over a single Redis instance. It is not, however, the same safety guarantee a consensus system provides, which is the entire subject of the next section.

Martin Kleppmann's criticism: why Redlock isn't safe enough for correctness

In 2016, distributed systems researcher Martin Kleppmann published a detailed critique of Redlock, and it's specific enough to name exactly what breaks, not a vague "Redis isn't reliable enough" complaint. His core argument: Redlock is neither efficient enough to be the cheap option, nor safe enough to be the correct option, it lands in an uncomfortable middle.

The clock-drift problem: Redlock's whole majority-and-elapsed-time check in step 4 assumes clocks across the N nodes advance at roughly the same rate. If one node's clock jumps forward unexpectedly, a bad NTP resync, a VM being paused and resumed, that node can expire its copy of the lock much earlier than the client or the other nodes expect, opening a window where a second client can acquire a majority elsewhere while the first client still believes it holds the lock.

The GC-pause (or any long stall) problem, and this is the sharper of the two arguments: a client can request the lock, receive it, then get paused, a garbage collection pause, a VM hypervisor pause, a slow disk I/O syscall, for longer than the lock's validity window. From that client's own perspective, no time has passed; it resumes and continues exactly where it left off, still believing it holds a lock that has, in real wall-clock time, already expired and been handed to a second client. The first client then goes on to act on the shared resource, unaware it lost the lock, and now two clients are operating under the belief that each of them exclusively owns it. Redlock has no mechanism to detect this, because from inside the paused process, nothing looked wrong.

The missing piece Kleppmann points to as the actual fix is a fencing token: a number that increases every single time the lock is granted (1, 2, 3, ...), which the client must then pass along to the resource it's about to modify. The resource itself rejects any write carrying a fencing token lower than the highest one it has already seen. This pushes the correctness check onto the resource being protected, not onto trusting that the lock and only the lock is enough, and critically, Redlock as specified has no fencing token mechanism at all. Kleppmann's conclusion, and it's a specific, actionable one, not just "don't use Redis": Redlock is a reasonable choice for efficiency locks, where an occasional duplicate execution is wasteful but not damaging (like avoiding running the same cron job twice), and a risky choice for correctness locks, where a duplicate execution corrupts real data.

ZooKeeper and etcd: locking backed by actual consensus

ZooKeeper's locking recipe uses two primitives most key-value stores don't have: ephemeral nodes (automatically deleted the moment the client's session disconnects, no expiry-based guessing) and sequential nodes (ZooKeeper appends a strictly increasing counter to the node name itself). To acquire a lock, a client creates an ephemeral, sequential child node under a shared parent path. It then lists all children of that parent: if its own node has the lowest sequence number, it holds the lock. If not, instead of polling in a loop, it sets a watch on the specific node immediately before its own in sequence, and waits, event-driven, to be notified when that predecessor is deleted (because its owner released the lock, or its session died), at which point it re-checks whether it's now first.

The correctness this gives you is materially stronger than Redlock's, because it isn't built on independently guessing at time windows across nodes, it's built on ZooKeeper's own underlying consensus protocol (Zab), which maintains a single, strictly ordered, agreed-upon log of every operation across the whole ensemble. There is no scenario where two clients both believe they hold the lowest sequence number; the ensemble itself has one agreed answer to that question at all times.

etcd offers essentially the same guarantee through a different, gRPC-native API: a client opens a session (which creates a lease, a time-bound token renewed automatically in the background as long as the client is alive), then calls Lock() from etcd's concurrency package, which creates a key tied to that lease. If the key already exists, meaning someone else holds the lock, the call blocks until the lease expires or the key is deleted, then re-attempts. Unlock() just deletes the key. Because etcd's consistency is backed by the Raft consensus algorithm, every node in the cluster agrees on lock ownership the same way ZooKeeper's ensemble does, and etcd's revision numbers (which strictly increase with every write) can be used directly as the fencing token Redlock is missing, a client can pass its lock's revision number to the downstream resource, which rejects any operation tagged with an older revision than one it has already accepted.

Which one to actually reach for

If you already run ZooKeeper or etcd for something else (service discovery, configuration, leader election), use its native locking recipe for anything where correctness genuinely matters, don't bolt Redlock onto a separate Redis cluster just to avoid learning a slightly different client API. The consensus guarantee is the point.

If you're already running Redis and the cost of an occasional double-execution is genuinely low (skipping a duplicate cache warm, running a scheduled cleanup job twice), a single-instance SET NX PX lock, or Redlock if you want resilience against a single node dropping out, is simpler operationally and perfectly reasonable. The mistake isn't using Redlock, it's using it for the wrong tier of consequence: never rely on it alone to guard something where a duplicate write is expensive or destructive (charging a customer twice, double-shipping an order, corrupting a file two workers both think they exclusively own).

And regardless of which system holds the lock, implement fencing at the resource being protected whenever the stakes justify it. A lock is a coordination mechanism between clients that agree to respect it; a fencing token check at the resource itself is what protects you against a client that, for whatever reason (a pause, a bug, a network hiccup), stopped respecting it without realizing.

Frequently Asked Questions