Distributed Locks: Mutual Exclusion Across Machines

Distributed locks are mutual exclusion for nodes that share no memory: a lease on a named resource (a job, a file, a migration, a turn at a non-transactional system) granted and timed out by coordination infrastructure, such that exactly one holder believes it may proceed at a time. The lock is a performance and correctness tool for a fleet of independent machines, and everything hard about it comes from the two facts distributed systems began with: nodes crash without notice, and no two of them agree on what time it is.

The boundary with the cluster’s other lease mechanism stays drawn, because leader election owns its side: elections are long-lived and system-wide, locks are short-lived and per-resource, and both are leases with fencing underneath. What this article owns is the lock’s side of the rhyme: lease semantics, expiry, the Redis patterns, the Redlock argument, and the fencing discipline that decides which locks are safe at all. The honest scope note belongs up front: a distributed lock coordinates independent nodes around non-transactional resources; it does not replace distributed transactions, and half of its uses, examined honestly, dissolve into idempotency or conditional writes instead.

What is a distributed lock

Start from the local version to see what breaks. On one machine, mutual exclusion is a solved problem: an operating-system mutex, backed by shared memory and a scheduler that knows, authoritatively, whether a thread is alive. Across machines, every one of those guarantees evaporates. There is no shared memory, so the lock must live in infrastructure both nodes can see. There is no authoritative scheduler, so “the holder crashed” is not an observable fact; it is a suspicion that cannot be distinguished from “the holder is slow” or “the network lost the heartbeat.” And there is no shared clock, so no two nodes agree on when a lease started or when it ends. The distributed lock is an attempt to rebuild mutual exclusion out of parts that disagree about all three.

The industry’s answer is the lease: a grant that expires on its own. Instead of holding a lock forever until released (which a crashed holder would do) the lock service grants the right to proceed for a bounded time, and the grant dies when the bound passes, whether or not the holder is alive to release it. The TTL is the lease’s answer to the undetectable crash, and it trades one impossibility for a dilemma: set it too long and a dead holder blocks everyone for the whole interval; set it too short and a slow-but-alive holder loses its grant mid-task, at which point the resource has a new holder while the old one is still working. That dilemma is not a tuning problem to be solved; it is the shape of the problem, and every pattern that follows is a way of living with it.

The worst case deserves a name before the patterns arrive, because it organizes everything that follows. A holder acquires the lease, then pauses (a garbage-collection stop, a virtual-machine migration, a long network partition) for longer than the TTL. The lease expires; the service, correctly, grants it elsewhere; the work proceeds on the second holder. Then the pause ends. The first holder wakes with no idea any time has passed, still certain it holds the lock, and writes. Two holders, one resource, no protocol violated: every component behaved exactly as designed, and the mutual exclusion still failed. This is the failure that fencing exists to stop, and it will recur in every section below like a refrain.

Redis distributed lock

The single-instance Redis pattern is the most implemented distributed lock in the world, and its canonical form is one documented command. Acquire with SET using the key, a unique holder token, the NX condition (set only if absent) and a PX expiry in milliseconds: one atomic command that creates the lease and its death sentence in the same stroke. The unique token matters more than it looks: the release must check that the remover is still the holder (the lock may have expired and been re-granted while the first holder was working) so the unlock compares the stored token against the caller’s own before deleting, classically through a small atomic script because the check-and-delete pair must not be separated. Releasing a lock you no longer hold is the second way a distributed lock double-grants, and the token check is the cheap defense against it.

The single instance has a single point of failure, and the standard fix (Redis replication with automatic failover) reintroduces the exact hazard the lock was managing. Because replication is asynchronous, the master can confirm a lock grant to a client and die before the follower ever hears about it; the promotion hands out a lock state that does not include the grant, and the next requester receives the same lease. Two holders, one caused by the availability machinery itself. This is not a speculative corner: it is the documented caveat in Redis’s own distributed-lock guidance, stated there as the reason a single Redis lock is safe only when mutual exclusion is a matter of efficiency (avoiding wasted duplicate work) rather than of correctness, where a double-grant corrupts data.

That distinction (efficiency locks against correctness locks) is the first question every use of this pattern must answer, and it decides everything downstream. An efficiency lock deduplicates work: two schedulers, one job, and the rare double-run costs a wasted execution, not a wrong system; a single Redis lock serves it well. A correctness lock guards an operation whose double-execution is unacceptable; money, inventory, an external write that cannot be taken back, and no expiry-based lease alone can promise it, because the lease can fail silently in the ways the last section named. Correctness locks need the fencing discipline of a later section, a consensus-based lock service, or storage-side checking, and the honest design review starts by sorting every lock on the list into the two piles before choosing any mechanism at all.

Redlock

Redlock is the multi-node answer Redis’s own author proposed to the single-instance failover caveat: run N independent Redis masters with no replication between them, and grant a lock only when a client acquires it on a majority of them (more than half) within a bounded validity window, retrying with small randomized delays when a majority is not available. The idea is arithmetic availability: a single master’s failover can no longer silently lose the grant, because the majority still remembers it, and the lock survives individual node failures without the asynchronous-replication hazard. For its intended audience (teams already running Redis, needing a stronger efficiency lock) it is a documented, implementable design, and it is widely deployed.

Then came the debate, and it is one of distributed systems’ most instructive public disagreements. The critique (argued publicly by Martin Kleppmann, a well-known author on data-systems design) lands on two points, both already resident in this treatment. First, the pause: no expiry-based scheme survives a holder that freezes longer than its lease (the garbage-collection stop that outlives the TTL and wakes up still believing it holds the lock) and Redlock, which builds its safety entirely on timing, inherits the failure on N nodes at once. Second, correctness-from-expiry: granting safety from TTLs assumes the system’s clocks and delays are bounded in a way no distributed system can promise, and Redlock by construction issues no fencing; nothing downstream can tell a stale holder’s action from a live one’s. The author’s rebuttal is also documented: that practical deployments add fencing or accept Redlock for efficiency-only uses, and that systems which need strict correctness should use different infrastructure altogether.

The debate’s residue, stripped of names, is a decision rule this article can state cleanly. If the lock is for efficiency (deduplicating work, serializing a cache rebuild, picking which node refreshes a feed) a Redis lock, single-node or Redlock, is a reasonable tool, because the rare double-grant wastes work rather than corrupting truth. If the lock is for correctness (anything whose double-execution is unrecoverable) then expiry alone cannot carry the guarantee: the design needs fencing tokens checked at the resource, or a lock service built on the consensus machinery that grants leases through a replicated log, with the same quorum discipline Raft brings to leader terms. The two piles from the last section are the entire argument, restated: Redlock is an excellent answer to the question it was asked, and the wrong answer to the question it is often asked instead.

Fencing tokens

The fencing token is the defense that keeps working after the lock has already failed, and the cluster has shown it twice from two directions. The mechanism: the lock service issues a monotonically increasing number with every grant (epoch 3 to the first holder, epoch 4 to whoever gets the lease next) and every write the holder performs carries its token. The storage on the receiving end remembers the highest token it has seen for that resource and rejects anything bearing an older one: the stale holder wakes from its pause, writes with epoch 3, and is refused by a storage that has already met epoch 4. Raft’s term numbers are exactly this machinery in miniature (“a leader from term 4 is ignored the moment any node has seen term 5”) and leader election already handed this article the connection: “the token is Raft’s term machinery seen from the election side.” The token does not prevent the double-grant; it makes the double-grant harmless, which is the only guarantee a distributed system can actually keep.

The insight buried in the mechanism deserves daylight: the check moves to the resource, the only place where the truth can be enforced. Expiry tries to be right at the lock service, to answer, before the fact, the unanswerable question of whether the holder is still alive. Fencing answers after the fact, where the answer matters: the storage is the arbiter, the token is the evidence, and neither the pause nor the clock drift nor the failed lease can corrupt a decision that is made at the moment of the write by the system being written to. This is also why replication’s split-brain defense is the same pattern; a stale leader’s commands are “safely ignorable” because they carry evidence from an older era, and the storage rejects them on sight. Fencing is indifferent to which lock service issued it, which is precisely the property a defense against lock failure must have.

The honest limit: fencing requires a resource that can check. A database row, a file store, an internal service; these can refuse stale tokens, whether by a dedicated token check, a version column, or the conditional-write family that says “apply this only if the current version is what I expect,” which is fencing’s cousin in a single conditional statement. But an email, a third-party charge, a webhook to someone else’s API (external effects with no token counter) cannot refuse anything. There the defense ladder descends to idempotency: if the effect cannot reject a repeat, it must tolerate one, through dedup keys and recorded outcomes at the boundary. The full design order follows: efficiency locks take any reasonable lease; correctness locks on internal resources take fencing; correctness locks on external effects take idempotency at the boundary, and anything that survives all three questions unchanged is probably not a distributed-lock problem at all.

Lock expiration

The TTL is an estimate of the work’s worst case, and everything about it follows from that sentence. Too short and the lease dies while the holder is legitimately still working; the re-grant happens, the pause failure arrives without any pause, and the mutual exclusion failed because the estimate was optimistic. Too long and every crashed holder taxes the whole interval before the fleet can proceed. The two standard practices are: size from the measured worst-case hold time plus margin, not from hope; and renew; a heartbeat pattern in which the holder’s library extends the lease while it is alive, letting short TTLs coexist with long work. Renewal has its own version of the refrain, worth saying now: the renewal loop can pause too, and a renewal that arrives late is exactly a holder that expired: the watchdog protects against dead holders, never against slow ones.

The waiting side is its own design. When a lock is held, the asking node can fail fast: return, retry later, let the retry pacing own the schedule, or wait, polling or subscribing for the release. Fail-fast suits efficiency locks, where being second is cheap; waiting suits throughput-critical sections, but a fleet waiting on one lock is a queue with extra steps, and everything backpressure taught about bounded queues applies: bound the waiters, watch the depth, and have an answer for “the holder never returns” that is not “wait forever.” Fairness is the last question: locks do not queue politely by default, and a busy section that starves some waiters indefinitely is a livelock wearing a mutex costume. The liveness-versus-safety trade is unavoidable and worth naming in review: short expiries favor liveness (the fleet always progresses, at the price of more mid-work expiries) and long expiries favor the work’s integrity, at the price of waiting on the dead. No number buys both; the use case picks the risk.

The operational discipline closes the loop with three habits. Watch the expiry counter: a lock that expires was misestimated or its holder paused, and both are worth knowing before the incident finds them. Watch hold durations: work growing past its estimate is the early warning that the TTL will soon betray someone. And audit every lock with the two questions this article has been asking throughout, what breaks if this grants twice, and what enforces single-holding when everything below the lock goes wrong? The audit’s honest output is usually demotion: some locks become idempotent operations, some become conditional writes, some become a single-writer design that needs no lock at all, and the few that remain are the ones that genuinely needed to be here: small, fenced, watched, and sized against measured work rather than hope.

FAQ

Is a Redis distributed lock safe?
For efficiency, yes; for correctness, not by itself. A single Redis lock, acquired with SET NX PX and released by verified token, is a sound way to avoid duplicate work, and its own documented caveat is that failover on asynchronous replication can grant the same lock twice. The safe posture is the efficiency-versus-correctness split: waste-avoidance may take the Redis lock; data integrity takes fencing, a consensus-based service, or storage-side checks.

What is Redlock, and should I use it?
Redlock grants a lock through a majority of independent Redis masters, trading single-instance failover risk for quorum arithmetic. The public debate over it (timing assumptions against fencing-based safety) resolves into the same split: Redlock strengthens an efficiency lock and cannot by itself make a correctness one. Use it when the double-grant is affordable; use fencing or consensus infrastructure when it is not.

What is a fencing token, and why do locks need them?
A monotonically increasing number issued with each lock grant, carried on every write, and checked by the resource, which refuses anything bearing a token older than the newest it has seen. It exists because the lock can fail silently: a paused holder, an expired lease, a re-grant. Fencing makes those failures harmless, because the check lives where the damage would, at the storage that can say no.

How long should a distributed lock’s TTL be?
Sized from the measured worst-case hold time, plus margin, never from hope, with renewal heartbeats if the work is long. Short TTLs keep the fleet moving but expire on slow holders; long TTLs protect work but wait on dead ones. The expiry counter is the honest teacher: a lock that expires in production was misestimated, and the estimate deserves the correction, not the incident.

What happens if the lock holder pauses longer than the TTL?
The lease expires, the lock re-grants, and when the paused holder wakes it still believes it holds the lock: the double-hold, arrived with no component misbehaving. The defenses, in order: fencing tokens, if the resource can check them; conditional writes on versioned state; idempotent effects with dedup keys, if the resource cannot refuse anything. A design with none of the three has a correctness question it has not yet answered.

Related articles

• Next read: the saga pattern, the alternative this article kept gesturing at: long-running work across services without holding locks at all; steps, compensations, and the outbox that keeps the promise a lease never could.
• leader election; the close cousin: who leads the cluster versus who holds the resource; the term-and-fencing machinery the two share, seen from the election side.
• distributed consensus; the machinery under the safest locks: leases as replicated log entries, quorum grants, and why the strongest lock services are consensus services.
• the Raft consensus algorithm, fencing in miniature: term numbers that make deposed leaders ignorable, and the same machinery applied to locks here.
• database replication; split-brain and the same defense from the data side: fencing tokens that make a stale leader’s writes safely ignorable.
• Redis caching; the tool whose feature list includes locks, and the contract question that follows: what is flushed safely, and what must never be Redis.
• idempotency; the softer guarantee: the defense ladder’s last rung, for effects that cannot reject a repeat and must therefore tolerate one.