Engineering Atlas › System Design Fundamentals

Mutual exclusion with distributed locks

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

The single-node lease

The common Redis pattern is SET lock:invoice-77 <random-id> NX PX 30000. NX makes it succeed only if the key is absent, and PX sets a 30 s expiry so a crashed holder does not deadlock the system. Release must be a compare-and-delete: delete the key only if its value still equals my random id. Since Redis 8.4 that is one command, DELEX key IFEQ <random-id>; on older versions it is a short Lua script (Redis docs). A plain DEL can remove a lock another client acquired after yours expired.

The weakness is the single Redis node. Replication is asynchronous, so if the primary fails over to a replica before the key replicates, a second client acquires the same lock. The Redis docs call this a safety violation and say the single-node lock suits only cases where an occasional double holder is acceptable.

Redlock

Redlock acquires the same key on N independent Redis masters (typically 5). The client records the start time, tries each node with a short timeout (the spec suggests about 5 to 50 ms for a 10 s TTL, so a dead node cannot eat the validity window), and holds the lock only if it got a majority and the elapsed time is well under the TTL. Remaining validity is ttl - elapsed - drift. If it fails, it releases on all nodes.

The critique, made clearly by Martin Kleppmann, is that Redlock's safety depends on timing: bounded network delay, bounded process pauses, and clocks that do not jump. A GC pause or a clock step after acquiring makes the client act on an expired lock, and he notes stop-the-world pauses have been known to last minutes (Kleppmann). Redlock also gives no fencing token, so the resource cannot detect it. The Redis docs now carry a consistency disclaimer that agrees on two points: implement fencing tokens for long work, and know that Redis TTLs follow the wall clock, not a monotonic one.

Consensus-backed locks

etcd, ZooKeeper, and Consul store lock state through Raft or Zab, so failover does not lose a granted lock. ZooKeeper's recipe creates an ephemeral sequential znode under /locks/x; the lowest sequence number holds the lock, and each waiter watches only its predecessor. The ephemeral node vanishes when the holder's session expires (ZooKeeper recipes). etcd ties a key to a lease and exposes a revision number that increases with every write, which serves as a fencing token.

Consensus makes the grant durable; it does not make the holder safe. Jepsen's 2020 test of etcd 3.4.3 saw two clients hold the same etcd lock at once even in a healthy cluster, and with short leases and process pauses about 18% of acknowledged updates to a lock-guarded set were lost. Its advice is to treat any lock as a performance aid and to fence with the lock key's revision (Jepsen).

Fencing tokens

Every grant comes with a number that never decreases. The holder passes it on every write, and the resource remembers the highest token it accepted and rejects lower ones. This closes the pause gap: a holder that wakes after expiry carries an old token and is refused. It requires the resource to cooperate. A database can check it in a WHERE clause; an S3 bucket or a third-party API usually cannot. The idea is old: Google's Chubby called the token a sequencer, and for servers that could not check one it fell back to a lock-delay, refusing to regrant a lost lock for up to one minute (Chubby paper).

Database locks

If the protected data lives in one database, use that database. SELECT ... FOR UPDATE, advisory locks like pg_advisory_xact_lock, or a conditional update on a version column are transactional with the data itself. That is usually simpler and safer than any external lock. Prefer the transaction-level advisory form: a session-level advisory lock ignores transaction semantics, so it stays held after a rollback until you unlock it or the session ends (Postgres docs).

Down the stack

Layer 1The contract

Be precise about which of two contracts you need. An efficiency lock promises that, most of the time, only one worker does a piece of work; an occasional double run costs money but not correctness. A correctness lock promises mutual exclusion on a resource even across crashes, failovers, pauses and clock jumps. No lease-based lock can deliver the second promise alone, because the holder cannot know it still holds the lock at the instant its write lands. The strongest testable promise is: the lock service grants each lock to one session at a time, every grant carries a strictly larger token, and the resource rejects writes with a smaller token. Latency: one round trip to acquire uncontended, and up to one lease of unavailability when a holder dies.

Layer 2The mechanism

Redis executes commands on a single thread, so SET key val NX PX ttl is atomic, and a Lua release script runs to completion with nothing interleaved. The holder's random value, typically 16 to 20 random bytes, is what makes compare-and-delete safe. Replication is asynchronous, so a grant acknowledged by the primary can vanish if the primary dies before shipping it. Redlock's reference clients subtract a drift allowance of about 1% of the TTL plus a couple of milliseconds from validity, and the algorithm asks that a crashed node stay down for at least one TTL before rejoining, since a restart without the key on disk can grant the lock again.

etcd's concurrency.Mutex writes a key under the lock prefix bound to the session's lease, then waits for deletion of the key whose create revision is just below its own; the holder's create revision doubles as a fencing token. ZooKeeper (usually through Curator's InterProcessMutex) does the same with ephemeral sequential znodes. Consul acquires a KV key with a session and, by default, applies a 15 s lock-delay after a session is invalidated, so a new holder cannot grab the lock while the old one may still be finishing (Consul docs). Postgres advisory locks live in the server's shared-memory lock table and are freed when the transaction or session ends.

Layer 3The machine

A Redis SET NX costs microseconds of CPU; the round trip inside one datacenter is typically a few hundred microseconds. Durability is the weak point: with the common appendfsync everysec setting a crash can lose about the last second of writes, including lock grants, while appendfsync always pays an fsync per write. Redis stores key expiry as an absolute Unix-time deadline, so if the server's wall clock is stepped forward, locks expire early everywhere at once. Consensus-backed locks pay a quorum round trip plus a WAL fsync per acquire and release, usually low single-digit milliseconds, but a grant survives the loss of any minority.

The holder's side is where safety actually breaks. A JVM stop-the-world pause, a VM steal or a page fault on a swapped-out page can freeze a process for longer than its lease. Database session locks fail in a different way: if a client host dies silently, the server notices only when TCP does, and Linux's default keepalive starts probing after 7,200 s (kernel docs), so an advisory lock can be held for hours unless you set keepalives or idle_in_transaction_session_timeout.

Why it's built this way

  1. A process cannot tell a crashed lock holder from a slow one, so locks must expire, which makes them leases.
  2. Leases depend on elapsed time, and processes pause unpredictably, so a holder can always act after its lease ends.
  3. Only the resource sees writes in their true order, so the final safety check must live there, as a monotonically increasing fencing token.
  4. Tokens need a durable, totally ordered counter, which is exactly what a consensus log provides and what an asynchronously replicated cache does not.

Diagram

flowchart TD
    A[Client wants lock] --> B[Record start time]
    B --> C[Try SET NX PX on each of 5 nodes]
    C --> D{Majority and validity above 0?}
    D -- yes --> E[Do work within validity window]
    E --> F[Release with compare and delete]
    D -- no --> G[Release on all nodes]
    G --> H[Back off with jitter and retry]

Worked example

A nightly job generates invoices from 10,000 accounts across 20 workers. Each worker locks account:<id> before generating.

Efficiency case: if two workers occasionally process the same account, the second insert hits a unique constraint on (account_id, period) and is discarded. A single Redis node at about 0.3 ms per SET NX adds 3 s of total lock overhead across the run. Redis is the right tool.

Correctness case: workers also debit a prepaid balance through a ledger service. A worker takes the lock with a 30 s TTL, then stalls 45 s on a slow downstream call. A second worker takes the lock, debits $120, and finishes. The first wakes and debits $120 again. Fix it in layers:

Lock cost on etcd is about 2 to 5 ms per acquire because it is a Raft write. Across 10,000 accounts that is a fair price for money movement.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Single Redis SET NX PXSub-ms, simpleLost on failover, no fencingEfficiency locks, dedup of work
RedlockSurvives minority node lossTiming assumptions, no fencing, 5 nodes to runRarely; prefer the others
etcd / ZooKeeper / ConsulConsensus-backed, sessions, fencing via revisionsMs latency, tier-0 dependency to operateCorrectness locks across services
Database row or advisory lockTransactional with the dataCouples lock load to the DBThe resource is that database
No lock, conditional writesNo coordinator at allNeeds a CAS-capable storeOptimistic concurrency fits the workload

Pitfalls in production

Leadership lens

Check yourself

  1. Why must release check the lock's value before deleting it?

    Show answer

    Your lock may have expired and been granted to another client; an unconditional delete would release their lock and let a third client in.

  2. Why does a fencing token protect against a GC pause when a TTL does not?

    Show answer

    The TTL only expires the lock at the store; the paused client still believes it holds it. The token is checked at the resource, which rejects the stale holder's lower number.

  3. When is a single Redis lock an acceptable choice?

    Show answer

    When a double holder only wastes work and the downstream operation is idempotent or constrained.

  4. What does Redlock's validity calculation subtract, and why?

    Show answer

    The time spent acquiring and an allowance for clock drift, because the lock started expiring on the first node before the last one granted it.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →