Distributed Locks & Fencing Tokens
Coordinate mutual exclusion across independent processes and survive node crashes, network pauses, and GC stalls using leases and monotonic fencing tokens.
Overview
The Problem Statement
When multiple autonomous server processes must coordinate access to a shared resource (such as executing a daily billing batch, migrating database schemas, or modifying a shared cloud file), local mutexes are useless because processes run in separate memory spaces on distinct physical servers. Without distributed mutual exclusion, multiple workers execute concurrently, leading to data corruption and race conditions.
- Preventing duplicate scheduled batch jobs across autoscaled cron worker fleets.
- Leader election for single-writer distributed topologies.
- Coordinating serialized access to legacy third-party non-transactional resources.
- Guarding distributed state mutations where optimistic locking is too costly.
- Within a single relational database (use database transactions or SELECT ... FOR UPDATE).
- Fine-grained row-level locking under high write contention (causes massive distributed locking latency).
- When optimistic concurrency control (version checks, CAS) is feasible.
Why It Exists
Client 1 acquires a distributed lock in Redis with a 10-second TTL. While writing files to S3, Client 1 experiences a 15-second Stop-The-World Java GC pause. The Redis lock lease expires after 10 seconds. Client 2 acquires the lock and starts writing to S3. Client 1's GC finishes, resumes execution thinking it still owns the lock, and writes its data to S3, silently overwriting and corrupting Client 2's new data—the classic Martin Kleppmann distributed locking failure.
- Silent data corruption in shared storage and external services.
- Split-brain execution where two nodes act as active primary.
- Permanent cluster deadlocks when lock owners crash without releasing.
- System freeze when lock coordinators experience network partitions.
How It Works
A distributed lock coordinates mutual exclusion by storing a lock flag in a centralized coordinator (e.g. Redis, etcd, Consul, or ZooKeeper).
To acquire the lock safely, the client generates a cryptographically random unique owner token (e.g., UUID) and issues an atomic conditional write: `SET resource_key owner_token NX PX 10000` (Set if Not eXists, with 10,000ms TTL).
The TTL (lease) guarantees liveness: if the client crashes or loses network connectivity, the coordinator automatically purges the key after the TTL expires, allowing other nodes to acquire.
To release the lock, the client must verify ownership before deleting: it must execute an atomic Lua script that compares the stored token against its own token. Naively calling `DEL key` would accidentally delete a lock acquired by a successor client if the first client's lease expired prematurely.
To solve the Stop-The-World GC pause problem, systems must use Monotonic Fencing Tokens. The lock coordinator dispenses an incrementing integer (fencing token: 1, 2, 3...) with every lock grant. The target storage system checks that the caller's fencing token is strictly greater than the last written token, safely rejecting stale writes from delayed clients.
Redis single-node locks are fast (~1ms) and sufficient for efficiency locks (preventing duplicate work). Strongly consistent consensus locks (etcd, Consul using Raft) are mandatory for correctness locks where duplicate execution causes irrecoverable financial or state corruption.
Redis SET NX PX with Lua Release
Atomic acquisition via `SET key token NX PX ttl`; atomic release via Lua script comparing token before `DEL`.
Consensus Session Lock (etcd / ZooKeeper)
Ephemeral znode or etcd lease tied to active client heartbeat session with linearizable Raft consensus.
Redlock Algorithm
Acquires lock across N independent Redis primary masters (e.g. 5 masters). Requires quorum (N/2 + 1) within valid time budget.
Prove It: Predict the System Behavior
Worker A acquires a distributed lock in Redis with a 10-second TTL. Worker A then experiences a 15-second Stop-The-World Garbage Collection (GC) pause.
While Worker A is paused, the 10s TTL expires and Worker B acquires the lock. Worker A then wakes up from GC and attempts to write to shared storage. What happens?
Worker A automatically detects it was paused and aborts its write.
Worker A unknowingly executes the write with expired credentials, potentially overwriting Worker B's data unless monotonic fencing tokens are checked at the storage layer.
Redis terminates Worker A's process remotely.
Interactive Visualizer
Race Worker A and Worker B for a distributed lock. Simulate a 15-second Stop-The-World GC pause to see how monotonic fencing tokens reject stale writes.
Distributed Lock & Monotonic Fencing Tokens
Solving the Stop-The-World GC pause dilemma via incrementing tokens.
Build It Step-by-Step
The engineering blueprint. Expand each sequential milestone to examine requirements, architectural impacts, common pitfalls, and blueprint pseudocode.
Generate Unique Lock Owner Identity
Every client acquisition must generate a globally unique token (UUID v4 or cryptographic random string). This token proves ownership during release.
ownerToken = uuid.v4()
Execute Atomic Conditional Write with TTL
In Redis: `SET lock:{resource} {ownerToken} NX PX {ttlMs}`. This single command is atomic in Redis's event loop.
Implement Heartbeat Lease Renewal (Auto-Refresh)
Launch a background timer (watchdog) that renews the TTL by sending `PEXPIRE` every `ttl/3` milliseconds as long as the worker thread is healthy.
watchdog = setInterval(every ttl / 3):
if taskStillRunning:
renewLease(key, ownerToken, ttl)Implement Atomic Check-and-Delete Release
Execute an atomic Lua script: check if `redis.call('GET', key) == ownerToken`. If true, delete; otherwise return 0.
if redis.call("GET", KEYS[1]) == ARGV[1] then
return redis.call("DEL", KEYS[1])
else
return 0
endGenerate Monotonic Fencing Tokens
Every successful lock acquisition increments an atomic counter (fencing token: 41, 42, 43). Pass this token with every storage write.
token = redis.incr("lock_fencing:" + resource)
storage.write(data, fencingToken=token)Handle Acquisition Failures with Jittered Backoff
If lock acquisition fails, wait with randomized exponential backoff before retrying, or subscribe to lock release events via Redis pub/sub.
Enforce Failure Recovery & Alerting
Monitor lock hold durations. If a lock frequently expires before being explicitly released, investigate worker task slowdowns.
Code Implementation
Production-ready, idiomatic reference implementations across Go, TypeScript, Python, and Java with sticky language switching, copy-to-clipboard, and source download.
Core Architectural Design Decisions
Invariants & MechanicsContext manager support guarantees release execution on Python scope exit.
redis.register_script optimizes Lua evaluation by utilizing SHA hashes.
import uuid
import time
from typing import Optional
RELEASE_LUA_SCRIPT = """
if redis.call('GET', KEYS[1]) == ARGV[1] then
return redis.call('DEL', KEYS[1])
else
return 0
end
"""
class DistributedLock:
def __init__(self, redis_client, resource_key: str, ttl_ms: int = 10000):
self.redis = redis_client
self.key = f"lock:{resource_key}"
self.ttl_ms = ttl_ms
self.owner_token = str(uuid.uuid4())
self._release_script = self.redis.register_script(RELEASE_LUA_SCRIPT)
def acquire(self) -> bool:
"""Atomically acquires the lock with NX and millisecond TTL."""
acquired = self.redis.set(
self.key,
self.owner_token,
nx=True,
px=self.ttl_ms
)
return bool(acquired)
def release(self) -> bool:
"""Safely releases the lock only if owned by this token."""
result = self._release_script(
keys=[self.key],
args=[self.owner_token]
)
return result == 1
def __enter__(self):
if not self.acquire():
raise RuntimeError("Failed to acquire distributed lock")
return self
def __exit__(self, exc_type, exc_val, exc_tb):
self.release()Edge Cases & Failure Modes
Investigate real-world production incidents. Expand each failure mode to analyze symptoms, root causes, and defensive engineering mitigations.
Production Considerations
Production checklist covering observability metrics, horizontal sharding, reliability fail-open patterns, and client identity security.
- Avoid distributed locks for high-frequency database row updates; use database optimistic concurrency control (`UPDATE ... WHERE version = ?`).
- Shard lock namespaces across multiple Redis clusters to prevent bottlenecking on a single coordinator.
Trade-offs
Select an algorithm below to dynamically compare memory footprints, burst tolerance, boundary precision, and distributed suitability.
| Approach | Advantages | Disadvantages | Use When |
|---|---|---|---|
| Redis SET NX PX + Lua | Sub-millisecond acquisition latency; simple operational footprint; low resource cost. | Asynchronous replication can lose locks on master crash; clock drift risk. | Efficiency locks (preventing duplicate work, cron job coordination, caching). |
| Consensus Locks (etcd / ZooKeeper / Consul) | Provably strong consistency; survive leader crashes without losing locks; built-in monotonic fencing. | Higher latency (5-20ms); heavier operational complexity. | Correctness locks (financial settlement, split-brain leader election, schema migrations). |
Further Reading
Authoritative industry references, IETF RFC standards, and systems engineering papers.
How to do distributed locking
The seminal critique of distributed locking, GC pauses, and the introduction of fencing tokens.
Distributed Locks with Redis (Redlock)
The original Redlock specification and response to distributed systems trade-offs.