Redlock: Distributed Locking with Redis

The Single-Instance Problem

The SET key value NX PX ttl pattern against a single Redis node is simple and fast, but it has a critical failure mode rooted in Redis's replication model.

Redis replication is asynchronous. When you write a key to the primary, Redis acknowledges the write immediately and replicates to replicas in the background. If the primary crashes between the write acknowledgment and the replication completing, the replica that gets promoted to primary has no record of the lock. A second worker can now acquire the same lock — and both workers proceed simultaneously.

t=0ms  Worker A: SET lock "A" NX PX 30000  → OK (written to primary)
t=1ms  Primary Redis crashes (lock not yet replicated)
t=2ms  Replica promoted to new primary (no lock key exists)
t=3ms  Worker B: SET lock "B" NX PX 30000  → OK
t=4ms  Worker A and Worker B both believe they hold the lock

For low-stakes tasks, this rare race condition is acceptable. For anything requiring stronger guarantees, you need a better approach.

The Redlock Algorithm

Redlock (proposed by Redis creator Salvatore Sanfilippo, known as Antirez) addresses the single-instance failure by distributing the lock across multiple independent Redis masters — nodes that do not replicate from each other.

Setup: Deploy 5 independent Redis masters (no replication between them). An odd number is required; 5 is the recommended minimum for fault tolerance.

The Algorithm (step by step):

1. Record start time. Note the current timestamp in milliseconds.
2. Acquire sequentially. Attempt to SET key uuid NX PX ttl on all 5 nodes, one by one. Use a short per-node timeout (e.g., 5ms) so a slow or down node doesn't block you.
3. Count successes. If you acquired the lock on at least 3 out of 5 nodes (a majority), proceed to step 4. Otherwise, release any partial locks and retry after a random backoff.
4. Check elapsed time. Calculate elapsed = now - start_time. If elapsed < ttl, the lock is valid. The effective validity window is ttl - elapsed - clock_drift_buffer.
5. Do the work. Proceed with the protected task.
6. Release everywhere. When done, send the release Lua script to all 5 nodes.

Why majority matters: For two workers to simultaneously hold the lock, each would need a majority. But two majorities of 5 require at least 6 nodes — impossible. The quorum guarantee ensures mutual exclusion even if up to 2 nodes are down or unreachable.

Node 1: ✅ acquired    Node 1: ✅ acquired
Node 2: ✅ acquired    Node 2: ❌ failed
Node 3: ✅ acquired    Node 3: ✅ acquired
Node 4: ❌ failed      Node 4: ✅ acquired
Node 5: ❌ failed      Node 5: ❌ failed

Worker A: 3/5 ✅ → LOCK HELD    Worker B: 3/5 ✅ → LOCK HELD ← IMPOSSIBLE
                                  (would need nodes 1,3,4 — but 1,3 already locked)