Distributed Locks
A distributed lock provides mutual exclusion across multiple processes running on different machines, so only one of them can perform a critical section at a time. The naive implementation — set a key in Redis with a TTL — is unsafe under GC pauses, network partitions, and clock skew. Safe distributed locking requires either a consensus-based lock service (etcd, ZooKeeper, Chubby) or the Redlock algorithm with fencing tokens to defend against stale-lock holders. The general lesson is that distributed locking is harder than it looks and should usually be avoided in favor of idempotency or single-leader designs.
Foundational.
How it works
A distributed lock provides mutual exclusion across processes on different machines. The semantics:
- Acquire: a process asks the lock service for the lock. If no one holds it, the process gets it; otherwise it waits (or fails).
- Hold: the process performs its critical section. The lock has a TTL — if the holder crashes, the lock auto-expires so others can take over.
- Release: when done, the process explicitly releases the lock.
The four safety properties a correct distributed lock must guarantee:
- Mutual exclusion: at any instant, at most one process holds the lock.
- Termination: if the holder crashes, the lock is eventually released (via TTL).
- Fairness (optional): locks are granted in request order (FIFO). Many systems skip this for performance.
- Stale-holder safety: even if the holder pauses (GC, VM suspend), its subsequent writes do not corrupt state. This requires fencing tokens.
Three implementations dominate production:
-
Consensus-based (etcd, ZooKeeper, Chubby): the lock is a key written via Raft/ZAB consensus. Acquisition succeeds only if the key does not exist; the holder keeps a session (heartbeat) alive; if the session dies, the key is deleted. Strong safety because every operation goes through consensus. The standard for Kubernetes leader election (etcd leases) and Hadoop (ZooKeeper).
-
Redis single-instance:
SET key value NX PX ttlatomically acquires if absent; the value is a unique ID so the holder can safely release (using a Lua script to check-and-delete). Simple, fast, but unsafe under partitions (Redis is AP — a partitioned slave can be promoted and reissue the lock). -
Redlock (Salvatore Sanfilippo): acquire the lock on N (typically 5) independent Redis instances simultaneously; if a majority grants it within the TTL, the lock is held. Designed to fix the single-instance partition problem. Martin Kleppmann's critique: Redlock is still unsafe under GC pauses and clock skew because it relies on wall-clock TTL across independent nodes that may not share a clock.
The robust answer is: use consensus-based locks if you need strong safety; use Redis locks only for performance optimization (caching, dedup) where occasional double-execution is acceptable.
Any distributed lock that protects a side effect (write to storage, send email, charge card) must issue a fencing token — a monotonically increasing integer incremented on every acquisition. The holder includes the token on every side-effecting operation. Storage rejects writes with stale tokens. This defends against the GC-pause bug: even if a paused holder writes after its TTL expired, the storage layer refuses the stale token. Without fencing, distributed locks are unsafe under pause — and every process eventually pauses (GC, page fault, VM migration). Kleppmann's critique of Redlock is precisely that Redlock does not issue fencing tokens (Redis does not support them on writes).
Leases are the time-bounded version of locks. The holder gets a lease for a fixed duration (e.g., 10 seconds) and must renew it before expiry. If the holder fails to renew (crashed, partitioned), the lease expires and another process can take it.
Leases are how Chubby, etcd, and GFS master election work. They are more efficient than heartbeat-based locks because the holder does not need constant communication — it just needs to renew before the deadline. The risk: clock skew. If the holder's clock jumps (NTP step, VM migration), it may believe it has time when the lease has expired elsewhere. Mitigations:
- Use a conservative margin: stop serving at
expiry - margin(e.g., 1 second before). - Use bounded clock uncertainty (Spanner's TrueTime bounds skew to ~7ms).
- Use a monotonic clock for measuring elapsed time, not wall clock.
Lease-based leadership is the dominant pattern in distributed systems today because it is simpler than constant heartbeats and handles failure cleanly via expiry.
Before reaching for a distributed lock, consider alternatives — they are often better:
- Idempotency: if the operation can be safely executed twice, you do not need a lock. Use an idempotency key on every side effect (Stripe's API does this). The first execution wins; duplicates no-op.
- Single leader: route all writes for a key through a single leader (Kafka partition leader, database primary). The leader serializes operations natively, no distributed lock needed.
- Database transaction: a row lock or SELECT FOR UPDATE serializes access within a single database. Cheaper and stronger than a distributed lock.
- Optimistic concurrency: include a version field; the write fails if the version changed. Used by Figma, Google Docs, and most collaborative editors.
Distributed locks are the right answer only when (a) the operation is not idempotent, (b) there is no single leader for the resource, and (c) the resource is not in a database that supports row locks. This is a narrow set of cases — most production uses of distributed locks are either unnecessary or could be replaced by a simpler primitive.
A process holds a Redis lock with TTL=10s. It pauses for 15s due to a GC pause. When it resumes, it performs a side effect. What went wrong, and how do you fix it?
Pick one answer.
Why does Martin Kleppmann argue that Redlock is unsafe even though it acquires the lock on a majority of independent Redis instances?
Pick one answer.
You need to ensure only one process runs a nightly batch job. The job is idempotent. Which approach is best?
Pick one answer.
Engineering mental model
Mental model. Think of Distributed Locks as a deliberate boundary in a system. The boundary exists because something becomes harder to manage when everything is done in one place: latency, scale, failure isolation, consistency, cost, or team ownership. The useful question is not “what does Distributed Locks mean?” but “what pressure makes this boundary worth introducing, and what new failure mode does it create?”
Before choosing Distributed Locks, name the workload, the critical user path, the dominant bottleneck, the failure you are trying to absorb, and the trade-off you are willing to accept. If you cannot name those five things, the design is probably premature.
// Pseudocode
request = receive()
result = distributed_locks(request)
return result
// Production questions:
// 1. What happens on timeout?
// 2. Can this operation be retried safely?
// 3. What is the bottleneck?Back-of-the-envelope reasoning
Numerical lens: write down traffic, payload size, read/write ratio, peak multiplier and durability target before choosing a component. The numbers should justify the architecture.
Interactive thought experiment: Distributed Locks
Change the variables below and predict what breaks first in Distributed Locks. The production lab can later reuse these same inputs.
Change one variable at a time. Predict the failure mode first, then move the slider and see whether your mental model matches the simplified system response.
If you are stuck on Distributed Locks, start by drawing the request path and marking every network hop, stateful component, queue, cache and failure boundary. Then estimate where the system will saturate.
You increase traffic by 10× in a system using Distributed Locks. What should you inspect first?
Pick one answer.
Which statement is the safest engineering habit when using Distributed Locks?
Pick one answer.
You have dashboards for traffic, latency, errors and saturation. You can change the architecture, but every change has operational cost.
Production scenario: your system uses Distributed Locks, traffic suddenly spikes, and p99 latency doubles. What is your first move?
Interview drill
Answer this without notes: When would you choose Distributed Locks, and when would you intentionally avoid it? Mention at least one bottleneck it addresses, one failure mode it introduces, and one alternative. Then quantify the workload you are designing for.
A useful engineering lens for Distributed Locks: define the problem it solves, the simpler design that fails first, the constraint that forces you to introduce this concept, and the new failure modes the concept creates.
Numerical sanity check
Back-of-the-envelope reasoning beats fake precision. State your traffic, payload, concurrency and growth assumptions explicitly, then calculate enough to know whether the current architecture is orders of magnitude away from the target.
Do not optimize for a memorized definition. Reason from the workload and failure mode.
Imagine the simplest version of a system using Distributed Locks. What breaks first as traffic grows by 10×, and what would you change before reaching 100×?
Pick one answer.
What you gain, what you pay
- +Mutual exclusion across processes on different machines — enables single-execution semantics.
- +Lease-based variants handle holder crashes cleanly via TTL expiry.
- +Consensus-based locks (etcd, Chubby) are as safe as the underlying consensus (Raft/Paxos).
- +Foundation for leader election and lease-based coordination.
- −Hard to get right — GC pauses, clock skew, and partitions cause subtle correctness bugs.
- −Fencing tokens are required for side-effect protection, but not all systems support them.
- −Adds latency and infrastructure — another moving part to deploy and monitor.
- −Often unnecessary — idempotency, single-leader designs, or database transactions are simpler.
- −Redlock-style TTL locks are unsafe under pause and clock skew (Kleppmann critique).
How this breaks in production
- GC-pause or VM-suspend stale holder — writes after TTL expired; mitigated by fencing tokens.
- Clock skew — lease holder believes it has time when lease has expired elsewhere; mitigated by conservative margin and bounded clocks.
- Split-brain during partition — Redis single-instance slave promotion can reissue a held lock; mitigated by consensus-based locks.
- Lock holder crash without releasing — TTL must be short enough for fast takeover but long enough to handle worst-case processing time.
- Lock service outage — every lock-dependent operation blocks; mitigated by HA lock service and graceful degradation.
Don't fall into these traps
- •Using Redis SET NX for safety-critical locks without fencing tokens.
- •Forgetting that TTLs are wall-clock-based — GC pauses and clock skew break them.
- •Treating Redlock as 'safe' — it is performance-optimization-only.
- •Reaching for a distributed lock when idempotency or a database transaction would do.
- •Setting TTLs too short — lock expires during normal processing; too long — slow failover after holder crash.
- •Not renewing leases before expiry — common in long-running jobs.
Real systems using this
How real systems implement this
- etcd (Kubernetes) — Lease-based locks via Raft consensus. Used for Kubernetes leader election: only one instance of each controller (scheduler, controller-manager) is active at a time; the others standby. If the active instance fails to renew its lease, another takes over within seconds.
- Google Chubby — Paxos-based distributed lock service used internally at Google for leader election (GFS master, Bigtable master) and coarse-grained locking. Holds leases with bounded renewal; clients cache the lock state. The foundation of Google's distributed coordination.
- Redis single-instance locks — SET key value NX PX ttl atomically acquires if absent; Lua script releases only if value matches holder's unique ID. Common for performance optimization (cache stampede prevention, deduplication) but unsafe for correctness-critical use without fencing.
- Postgres advisory locks — pg_advisory_lock provides cooperative locking within a single Postgres cluster. Used for cross-process coordination (only one cron worker pulls from a queue, only one migration runs at a time). Not distributed across machines, but safe within a Postgres cluster.
Practice saying it out loud
- Q1Explain the GC-pause bug in naive distributed locks. How do fencing tokens fix it?
- Q2Why is Redlock considered unsafe by Martin Kleppmann? When is it acceptable to use?
- Q3Compare etcd-based locks, Redis single-instance locks, and Redlock. Which would you use for what?
- Q4Your batch job is idempotent. Do you need a distributed lock? Why or why not?
- Q5What is a lease? How does it differ from a lock, and what are the failure modes?
Further reading & references
Core explanations are original NO CAP material. External references are provided for deeper study and standards.
What next?
Mark as understood once the mental model clicks.
Next recommended
Leader Election