Distributed Locks at Scale: The Redlock Algorithm Debate, Clock Drift, and Split-Brain Prevention

In single-machine multithreaded systems, mutual exclusion is a solved problem: the operating system kernel and hardware atomic instructions (like Compare-And-Swap) provide mutexes, semaphores, and condition variables. But in distributed systems spanning multiple servers across unreliable networks, achieving exclusive access to a shared resource without split-brain anomalies is one of the most deceptively treacherous challenges in computer science.

The quest for safe distributed locking triggered one of the most famous debates in modern software engineering: the intellectual clash between Redis creator Salvatore Sanfilippo (antirez) and distributed systems researcher Martin Kleppmann over the safety of the Redlock algorithm.

Why Single-Instance Redis Locks Fail Under Partitioning

Many engineering teams implement distributed locks using a simple Redis instance with the atomic SET key value NX PX timeout command. When a client finishes its critical section, it executes a Lua script to release the lock only if the value matches its unique ID.

This works under peaceful conditions. However, enterprise production environments require high availability, running Redis in a primary-replica topology. Because Redis replication is asynchronous, a fatal race condition arises:

+--------------------------------------------------------------------------+
|            THE PRIMARY-REPLICA ASYNCHRONOUS REPLICATION HAZARD           |
+--------------------------------------------------------------------------+

 Client 1                   Redis Primary              Redis Replica
    │                             │                          │
    ├── 1. Acquire Lock (SET NX) ─>                          │
    │<── 2. Lock Granted (OK) ────┤                          │
    │                             │                          │
    │                             X (Primary crashes BEFORE) │
    │                               (syncing write to replica)
    │                                                        │
    │                             [ Sentinel / Failover ]    │
    │                             Replica promoted to Primary│
    │                                                        │
 Client 2                                                    │
    ├── 3. Acquire Lock (SET NX) ───────────────────────────>│
    │<── 4. Lock Granted (OK) ───────────────────────────────┤
    │                                                        │
  [ MUTUAL EXCLUSION VIOLATED: Both Client 1 & Client 2 hold lock! ]

The Redlock Algorithm Specification

To eliminate single-point-of-failure vulnerabilities without relying on heavy consensus protocols, Salvatore Sanfilippo proposed Redlock. Instead of one primary-replica cluster, Redlock deploys (N) completely independent, uncoordinated Redis master nodes (typically (N = 5)):

1. Timestamp Acquisition: The client records current timestamp (T_1).
2. Quorum Acquisition: The client attempts to acquire the lock sequentially across all 5 instances using the same key and random token, with a short network timeout (e.g., 5 to 50ms) to prevent lingering on dead nodes.
3. Validity Verification: The client records timestamp (T_2). The lock is considered successfully acquired if and only if:
   • The client secured the lock on a majority (at least (lfloor N/2 floor + 1 = 3) nodes).
   • The total elapsed time ((T_2 - T_1)) is strictly less than the lock validity time.
4. Lease Time Calculation: The true time the client is permitted to hold the lock is calculated as: [ ext{Lease Time} = ext{TTL} - (T_2 - T_1) - ext{Clock Drift Allowance}]
5. Rollback on Failure: If the client fails to obtain a quorum, it broadcasts an unlock Lua script to all instances, even those it failed to acquire.

The Martin Kleppmann Critique: Asynchronous Realities

In 2016, distributed systems expert Martin Kleppmann published a seminal critique demonstrating that Redlock makes unverified assumptions about system timing and physical clocks. In real-world distributed environments, three unavoidable phenomena violate Redlock's guarantees:

1. Stop-the-World Garbage Collection Pauses

Suppose Client 1 acquires the lock on 3 of 5 nodes. Immediately after, Client 1 experiences a multi-second full GC pause (or OS paging pause). While Client 1 is suspended, its lock TTL expires on all Redis nodes. Client 2 now contacts the nodes and legitimately acquires the lock. Client 1 wakes up from its GC pause believing it still owns the lock, and both clients write conflicting updates simultaneously.

 Client 1            Lock Service (Redis / etcd)            Storage (DB / S3)
    │                             │                                 │
    ├── Acquire Lock ────────────>│                                 │
    │<── Lock Granted ────────────┤                                 │
    │                             │                                 │
 [ GC Pause / VM Stall ]          │                                 │
    │ (Lock TTL Expires!)         │                                 │
    │                             │                                 │
 Client 2                         │                                 │
    ├── Acquire Lock ────────────>│                                 │
    │<── Lock Granted ────────────┤                                 │
    │                             │                                 │
    ├── Write Data ────────────────────────────────────────────────>│ (Success!)
    │                             │                                 │
 [ Client 1 Wakes Up ]            │                                 │
    ├── Write Data ────────────────────────────────────────────────>│ (CORRUPTION!)

2. Physical Clock Drift and NTP Jumps

Redlock relies on physical system clocks to measure time elapsed. If an NTP daemon synchronizes time by jumping forward by several seconds (or due to hardware crystal clock skew), a node's lock may expire prematurely while the client still believes it holds the lease.

The Solution: Storage-Side Fencing Tokens

Kleppmann proved that a distributed lock service alone cannot guarantee safety if the storage resource being protected accepts unauthenticated writes. To achieve true consistency, the lock service must return a monotonically increasing integer: a Fencing Token.

+--------------------------------------------------------------------------+
|                  FENCING TOKEN VALIDATION AT STORAGE                     |
+--------------------------------------------------------------------------+

 Client 1                        Lock Service                      Storage
    │                                 │                               │
    ├── 1. Acquire Lock ─────────────>│                               │
    │<── 2. Token #33 Granted ────────┤                               │
    │                                 │                               │
 [ Extended Network Delay ]           │                               │
    │                                 │                               │
 Client 2                             │                               │
    ├── 3. Acquire Lock ─────────────>│                               │
    │<── 4. Token #34 Granted ────────┤                               │
    │                                                                 │
    ├── 5. Write Data (Token #34) ───────────────────────────────────>│
    │                                                                 │ [Storage records:
    │                                                                 │  Max Token = 34]
    │                                                                 │
 [ Client 1 Resumes ]                                                 │
    ├── 6. Write Data (Token #33) ───────────────────────────────────>│
    │                                                                 │ [REJECTED!]
    │<── 7. ERROR: Stale Fencing Token 33 < Current 34 ───────────────┤

When Client 1 finally wakes up and attempts to write to the storage layer, the storage engine inspects the transaction's fencing token. Because Token 33 is smaller than the already committed Token 34, the storage engine unconditionally rejects the stale request.

Production Comparison: Redis vs Zookeeper vs etcd

Frequently Asked Questions