Distributed Systems Coordination

Distributed Locking

Mutual exclusion across distributed nodes — why it is fundamentally harder than single-process locking, the Redis Redlock controversy, ZooKeeper-based alternatives, and fencing tokens as a correctness backstop.

⏱ 10 min read

What it is

A distributed lock is a mutual-exclusion mechanism that spans multiple processes or machines. Only one holder can possess the lock at a time across the entire cluster, preventing concurrent access to a shared resource or preventing duplicate execution of a critical section. Unlike an in-process mutex, a distributed lock must handle clock drift, network partitions, process crashes, and the impossibility of atomic operations across machine boundaries.

Why it exists

Distributed systems frequently need to ensure that only one node performs a task at a given time: generating unique identifiers, updating a shared external resource, running a periodic job, or serving as a primary. A single-node mutex is invisible to other processes on other machines. Distributed locking provides a cross-process critical section, but the distributed context introduces hazards that have no equivalent in single-process programming.

When to use

Ensuring that a scheduled job runs on exactly one node.
Preventing concurrent writes to an external system that has no built-in concurrency control.
Coordinating access to a shared resource that cannot use optimistic concurrency (e.g., a non-transactional external API).
Leader election where you need a lightweight approach without a full consensus protocol.

When not to use

The target resource supports conditional writes (compare-and-swap, optimistic locking via ETags or version numbers) — prefer that approach as it avoids the distributed lock complexity entirely.
Correctness guarantees are critical and clock drift or GC pauses could expire the lock while the holder is still executing — use fencing tokens + storage guard rails instead.
High contention scenarios where many clients compete for the same lock, degrading throughput.

Typical architecture

Redis Single-Node Lock (SET NX PX)
───────────────────────────────────
Client A: SET lock:resource "token-A" NX PX 30000
  → OK (lock acquired)

Client B: SET lock:resource "token-B" NX PX 30000
  → nil (lock not acquired — retry with backoff)

Client A releases: DEL lock:resource (only if value == "token-A")
  → 1 (released)

Fencing Token Pattern (safe with any lock backend)
───────────────────────────────────────────────────
Lock service issues a monotonically increasing token on each grant:
  Client A acquires lock → receives token 33
  Client A pauses (GC) → lock expires
  Client B acquires lock → receives token 34
  Client A resumes, sends write with token 33 to storage
  Storage rejects: "token 33 < current fence 34"
  Client B's write with token 34 is accepted ✓

Pros and cons

Pros

Redis single-node lock is simple, low-latency, and sufficient for use cases that can tolerate rare duplicates (efficiency locks, not correctness locks).
ZooKeeper-based locks backed by consensus are strongly consistent and safe.
Automatic TTL expiry prevents indefinite lock holding by crashed clients.

Cons

Redis Redlock is unsafe for correctness-critical locking — clock drift, GC pauses, and network delays can cause two clients to believe they hold the lock simultaneously.
Any TTL-based lock has a window where the holder's TTL expires but it has not yet stopped executing.
ZooKeeper-based locks add infrastructure complexity and latency.
Distributed locks are a frequent source of hard-to-diagnose bugs and production incidents.

Implementation notes

Redis single-node lock: use SET key value NX PX ttl for atomic acquire. For release, use a Lua script to atomically check the value and delete — never use a plain DEL as it may delete another client's lock. Set the TTL conservatively: long enough for the critical section to complete, short enough to recover quickly if the holder crashes. This approach is sufficient for "efficiency locks" where occasional duplicate execution is tolerable.

Redis Redlock (acquiring a lock across N independent Redis nodes) was proposed by Redis's author as a stronger algorithm. However, Martin Kleppmann's critique demonstrated that Redlock can fail under clock jumps and GC pauses in ways that single-node Redis cannot prevent. The Redis author responded, and the debate continues. The consensus in the distributed systems community: use Redlock only as an efficiency lock, never as a correctness lock.

ZooKeeper / etcd locking: these systems are backed by consensus algorithms (ZAB, Raft), making their locks strongly consistent. etcd provides a transaction API (Txn) with compare-and-set semantics. ZooKeeper provides sequential ephemeral znodes. Both are more operationally complex than Redis but correct for critical sections where safety matters more than performance.

Fencing tokens are the ultimate correctness backstop: regardless of which lock backend you use, if the guarded resource can validate a monotonically increasing token, you get safety even if the lock expires before the holder realises it. This requires storage-layer support (a simple IF fence_token > last_seen_fence THEN accept check).

Common failure modes

GC pause longer than TTL: JVM garbage collector pauses for longer than the lock TTL; lock expires, another client acquires it; original holder resumes and proceeds with stale assumption of ownership.
Clock jump: system clock steps forward (NTP correction or VM migration), causing TTL to expire prematurely from the lock server's perspective.
Network partition: lock holder loses connectivity to lock service; service expires the lock and grants it to another client; holder regains connectivity unaware the lock is gone.
Releasing another client's lock: client fails to validate the lock token before deleting, removing a lock it does not own.
Lock contention storm: many clients polling for the same lock creating thundering-herd load on the lock service.

Decision checklist

Is this an efficiency lock (duplicate work is wasteful but tolerable) or a correctness lock (duplicates cause data corruption)?
Does the guarded resource support fencing tokens to provide a correctness backstop?
Is the TTL set to safely exceed the worst-case critical section duration (including GC pauses)?
Is lock release atomic and conditional on token ownership?
Have you considered optimistic concurrency (CAS/ETags) as a simpler alternative?
Is there monitoring for lock acquisition failures and lock contention?

Example use cases

Distributed cron: ensuring a background job (e.g., sending daily digests) runs on exactly one application instance.
Exclusive access to a legacy external system with no built-in locking support.
Preventing duplicate payment processing in an idempotent payment gateway wrapper.
Kubernetes controller leader election via Lease API (backed by etcd consensus).

Leader Election — leader election is a specialised form of distributed locking for designating a primary node.
Split Brain Problem — what happens when a distributed lock fails to prevent concurrent primaries.
Distributed Coordination — ZooKeeper and etcd provide consensus-backed primitives for safe distributed locking.