Distributed Locks with Redis (Redlock)

In a single-instance application, synchronization primitives (like Java's synchronized, Node.js lock patterns, or Go's sync.Mutex) are sufficient to prevent race conditions. However, when an application is scaled horizontally across multiple servers or container pods, local locks are useless.

A Distributed Lock ensures that only one process across the entire distributed system can perform a specific operation or access a shared resource at any given time.

1. Why Local Locks Fail in Distributed Systems

Consider a multi-server checkout system attempting to update a stock count:

Because Server 1 and Server 2 have separate memory spaces, they are unaware of each other's locks. Both update the database concurrently, leading to double-allocation or data corruption. We need a centralized, fast coordinator. Redis is perfect for this.

2. Single-Instance Redis Lock Pattern

The simplest way to implement a distributed lock is on a single Redis instance.

Acquiring the Lock

To acquire a lock, a client sends a SET command with special arguments:

SET resource_name unique_token NX PX 30000

• resource_name: The key representing the shared resource.
• unique_token: A randomly generated string (e.g., UUID) unique to the client acquiring the lock.
• NX: Only set the key if it does not already exist. This ensures mutual exclusion (only the first client succeeds).
• PX 30000: Expire the key in 30,000 milliseconds (30 seconds). This prevents permanent deadlocks if the client crashes or loses connection while holding the lock.

Releasing the Lock Safely

Releasing the lock is not as simple as calling DEL resource_name.

The Expiry Race Condition:

1. Client A acquires the lock for 30 seconds.
2. Client A gets blocked by a long database query or GC pause for 35 seconds.
3. The lock expires in Redis.
4. Client B acquires the lock.
5. Client A wakes up and calls DEL resource_name.
6. Client A has just deleted Client B's lock! Client B is now unprotected.

The Safe Release (Using a Lua Script)

To prevent this, the client must check if the value stored in the key matches its unique_token before deleting it. This check-and-delete must be atomic. Since Redis is single-threaded, we can achieve this using a Lua script:

-- KEYS[1] is the resource name (e.g. 'lock:order:123')
-- ARGV[1] is the client's unique token (e.g. UUID)
if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

In Node.js or Python, you send this script via EVAL to guarantee atomicity.

3. The Redlock Algorithm (Multi-Instance Lock)

A single Redis instance is a single point of failure (SPOF). If the instance crashes, no lock can be acquired. Furthermore, if you use Redis master-replica replication, replication is asynchronous:

1. Client A writes a lock to Master.
2. Master crashes before replicating the write to the Replica.
3. Replica is promoted to Master.
4. Client B attempts to acquire the lock and succeeds (because the key is missing).
5. Both Client A and Client B now hold the lock.

To solve this, Redis creator Salvatore Sanfilippo proposed the Redlock algorithm, which works on N independent master nodes (typically 5).

Step-by-Step Execution

To acquire the lock, the client performs the following steps:

1. Get Current Time: Captures the current timestamp in milliseconds.
2. Acquire Sequentially: Attempts to acquire the lock on all N instances using the same key and unique token, using a timeout that is much smaller than the lock validity time (e.g., if lock is 10s, timeout is 50-100ms). This prevents the client from wasting too much time on a dead node.
3. Compute Elapsed Time: Calculates how much time was spent acquiring the locks.
4. Evaluate Success: The lock is successfully acquired if and only if:
   • The client successfully acquired the lock on a majority of nodes (at least N/2 + 1, i.e., 3 out of 5 nodes).
   • The total time elapsed to acquire the locks is less than the lock validity time.
5. Calculate Lock Validity: The lock's active lease time is the original validity time minus the time spent acquiring it.
6. Release on Failure: If the client fails to acquire the lock (due to timeout or lack of majority), it sends a release script to all nodes (even those it failed to lock).

4. The Safety Critique: Martin Kleppmann vs. Salvatore

In 2016, distributed systems researcher Martin Kleppmann published a detailed critique of Redlock. He argued that Redlock is unsafe for systems where correctness is absolute (e.g., double-charging money).

The GC Pause / Stop-The-World Vulnerability

Kleppmann pointed out that Redlock assumes a model where physical clocks are synchronized and processes do not experience random, long pauses. However, modern JVMs/runtimes experience garbage collection (GC) pauses that stop all threads:

The Clock Drift Vulnerability

If one of the Redis servers experiences clock drift (its internal clock jumps forward due to NTP corrections), a lock key can expire much faster than expected on that node, breaking the majority guarantees.

The Solution: Fencing Tokens

Kleppmann proposed that a lock coordinator should return a fencing token (a monotonically increasing number like 101, 102) every time a lock is acquired.

The target database or storage resource must validate this token:

• Storage keeps track of the highest token it has processed (e.g., 102).
• If Client 1 wakes up from a GC pause and tries to write with token 101, the database rejects it because a higher token (102) has already written.

Client 1 (Acquires Lock) -> Token = 31
Client 2 (Acquires Lock) -> Token = 32

Client 2 Writes to DB -> DB records last_processed_token = 32
Client 1 (After GC Pause) Writes -> DB rejects (Token 31 < 32)

5. Summary & Practical Guidelines