Redis Redlock: Algorithm, Controversy, and Hard Truths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# ACQUIRE LOCK
# SET key value NX EX seconds
# - NX: Only set if key does not exist
# - EX: Set expiration time in seconds
 
SET lock:inventory "client-abc-request-123" NX EX 30
 
# Returns:
# - "OK" if lock acquired (key was created)
# - nil if lock NOT acquired (key already exists)
 
 
# RELEASE LOCK (Safe version using Lua script)
# Only delete if we are still the holder
 
EVAL "
  if redis.call('get', KEYS[1]) == ARGV[1] then
    return redis.call('del', KEYS[1])
  else
    return 0
  end
" 1 lock:inventory client-abc-request-123
 
# Returns:
# - 1 if lock released (we were holder)
# - 0 if lock NOT released (we weren't holder, or already expired)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Timeline WITHOUT atomic release:
 
Client A                    Redis                       Client B
────────                    ─────                       ────────
GET lock:inventory
→ "client-a-123"
                                                        
(comparing values...)                                   (lock expires!)
                                                        
                            DEL lock:inventory          SET lock:inventory
                            (A's TTL expired)           "client-b-456" NX EX 30
                                                        → OK (acquired)
DEL lock:inventory
→ 1 (DELETED!)              Lock deleted                (thinks it has lock)
 
Result: A deleted B's lock. B continues unaware it lost the lock.
 
The Lua script prevents this by making check-and-delete atomic.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

REDLOCK ALGORITHM (N=5 independent Redis instances):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
PARAMETERS:
- N = 5 (number of Redis instances, should be odd)
- TTL = Lock validity time (e.g., 10 seconds)
- Quorum = N/2 + 1 = 3 (majority)
- Clock drift factor = 0.01 (1% assumed max clock drift)
 
ACQUIRE LOCK:
━━━━━━━━━━━━
 
1. Get current time T1 (in milliseconds)
 
2. Attempt to acquire lock on ALL N instances sequentially:
   For each Redis instance i (from 1 to 5):
     - SET resource_name random_value NX PX (TTL in ms)
     - Use very short timeout per instance (e.g., 5-50ms)
     - If instance unreachable, move on immediately
 
3. Get current time T2 after all attempts
 
4. Calculate elapsed time: elapsed = T2 - T1
 
5. Calculate validity time:
   validity = TTL - elapsed - (TTL * clock_drift_factor)
   
   Example: TTL=10000ms, elapsed=50ms, drift=1%
   validity = 10000 - 50 - 100 = 9850ms
 
6. Check success criteria:
   - Did we acquire on MAJORITY (≥ 3) instances?  AND
   - Is validity > 0?
   
   If YES: Lock acquired! Use for at most 'validity' milliseconds.
   If NO:  Lock NOT acquired. Go to RELEASE.
 
 
RELEASE LOCK:
━━━━━━━━━━━━
 
1. Attempt to release on ALL N instances (not just ones we acquired from):
   For each Redis instance i:
     - Run release Lua script with our random_value
     - Ignore failures/timeouts
 
Why release on all? We may have acquired on an instance but think we 
didn't due to network issues when reading the response.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

5 Independent Redis Instances: R1, R2, R3, R4, R5
 
Client A attempts lock with TTL=10s:
 
Time    R1          R2          R3          R4          R5
────    ──          ──          ──          ──          ──
t0      SET OK ✓    SET OK ✓    SET OK ✓    (timeout)   SET OK ✓
        5ms         10ms        8ms         50ms        12ms
 
Elapsed: 85ms total
Successful instances: 4 (R1, R2, R3, R5) ← Majority achieved!
Validity: 10000 - 85 - 100 = 9815ms
 
Result: Lock ACQUIRED on 4/5 instances.
        Client A may hold lock for up to 9815ms.
 
 
Client B attempts same lock (while A holds):
 
Time    R1          R2          R3          R4          R5
────    ──          ──          ──          ──          ──
t100    SET nil ✗   SET nil ✗   SET nil ✗   SET OK ✓    SET nil ✗
        (A's lock)  (A's lock)  (A's lock)  (was down)  (A's lock)
 
Successful instances: 1 (only R4)
1 < 3 (majority) → Lock NOT acquired
Client B must retry after delay.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

SCENARIO: GC Pause Causes Safety Violation
 
Timeline:
────────
 
t0:    Client A acquires lock on R1, R2, R3 (majority)
       TTL = 10 seconds
       Validity = 9.8 seconds
       
t1:    Client A begins critical section
 
t2:    Client A enters LONG GC PAUSE (e.g., 15 seconds)
       (A is frozen, time appears stopped from A's perspective)
 
t10:   Lock expires on R1, R2, R3 (TTL reached)
       A is still frozen in GC
 
t11:   Client B acquires lock on R1, R2, R3
       B begins critical section
       
t15:   Client A's GC completes
       A checks: "Do I still have validity time left?"
       A's calculation: t_now (t15) - t_acquired (t0) = 15 seconds
       Wait, that's > TTL... but A might not check properly!
       
       Or worse: A's local clock was also affected by the pause,
       so A believes only 1 second has passed.
       A proceeds with critical section.
 
t16:   BOTH A AND B ARE IN CRITICAL SECTION
       Mutual exclusion violated.
 
 
THE PROBLEM:
Redlock's validity calculation happens at acquire time.
If a pause occurs AFTER acquire but BEFORE checking validity,
the client can believe it still holds a lock that has expired.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

THE CENTRAL DISAGREEMENT:
━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Kleppmann's Position:
  "A distributed lock algorithm MUST be correct under asynchronous 
   network assumptions. Redlock is not, because it relies on
   synchronized clocks and bounded process execution."
 
Sanfilippo's Position:
  "Real systems are quasi-synchronous. With reasonable bounds on
   clock drift and process pauses, Redlock provides practical safety."
 
Underlying Philosophical Difference:
  Kleppmann: Safety guarantees should be mathematical, not probabilistic.
  Sanfilippo: Probabilistic guarantees that work 99.999% of the time
              are sufficient for most use cases.
 
Who's Right?
  Depends on your use case:
  - If failure means data corruption: Kleppmann is right.
  - If failure means duplicate work: Sanfilippo may be right.
  
  The problem is that engineers often don't know which category
  they're in until disaster strikes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

import time
import redis
from typing import Optional, Tuple
 
class RedlockWithFencing:
    def __init__(self, redis_instances: list, ttl_ms: int = 10000):
        self.instances = [redis.Redis(host=h, port=p) for h, p in redis_instances]
        self.ttl_ms = ttl_ms
        self.quorum = len(self.instances) // 2 + 1
        self.clock_drift_factor = 0.01
    
    def acquire(self, resource: str, client_id: str) -> Optional[Tuple[int, float]]:
        """
        Acquire lock and return (fencing_token, validity_ms) or None.
        
        The fencing token is the maximum lock_version across all instances.
        This provides weak monotonicity - not perfect, but better than nothing.
        """
        start_time = time.time() * 1000
        acquired_count = 0
        max_version = 0
        
        for instance in self.instances:
            try:
                # Use INCR to generate a version, then SET with that version
                version = instance.incr(f"{resource}:version")
                result = instance.set(
                    resource, 
                    f"{client_id}:{version}",
                    nx=True, 
                    px=self.ttl_ms
                )
                if result:
                    acquired_count += 1
                    max_version = max(max_version, version)
            except redis.RedisError:
                continue
        
        elapsed = time.time() * 1000 - start_time
        validity = self.ttl_ms - elapsed - (self.ttl_ms * self.clock_drift_factor)
        
        if acquired_count >= self.quorum and validity > 0:
            return (max_version, validity)
        
        # Failed to acquire, release any partial locks
        self.release(resource, client_id)
        return None
    
    def release(self, resource: str, client_id: str):
        """Release lock on all instances."""
        release_script = """
        local val = redis.call('get', KEYS[1])
        if val and string.find(val, ARGV[1]) then
            return redis.call('del', KEYS[1])
        end
        return 0
        """
        for instance in self.instances:
            try:
                instance.eval(release_script, 1, resource, client_id)
            except redis.RedisError:
                continue
 
 
# Protected resource with fencing
class FencedDatabase:
    def __init__(self):
        self.highest_token = 0
    
    def update(self, fencing_token: int, data: dict) -> bool:
        if fencing_token < self.highest_token:
            raise StaleTokenError(
                f"Token {fencing_token} < current {self.highest_token}"
            )
        
        self.highest_token = fencing_token
        # Proceed with update
        self._commit(data)
        return True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

const Redlock = require('redlock');
const Redis = require('ioredis');
 
// Connect to 5 independent Redis instances
const redisClients = [
    new Redis({ host: 'redis1', port: 6379 }),
    new Redis({ host: 'redis2', port: 6379 }),
    new Redis({ host: 'redis3', port: 6379 }),
    new Redis({ host: 'redis4', port: 6379 }),
    new Redis({ host: 'redis5', port: 6379 }),
];
 
const redlock = new Redlock(redisClients, {
    // Time in ms before retrying
    retryDelay: 200,
    // Max attempts to acquire lock
    retryCount: 10,
    // Clock drift factor (0.01 = 1%)
    driftFactor: 0.01,
});
 
async function doExclusiveWork() {
    try {
        // Acquire lock for 10 seconds
        const lock = await redlock.acquire(['locks:my-resource'], 10000);
        
        console.log('Lock acquired:', lock.value);
        
        try {
            // CRITICAL SECTION
            // Use lock.expiration to check remaining time
            console.log('Expiration:', lock.expiration);
            
            await processExclusiveOperation();
            
        } finally {
            // Release lock
            await lock.release();
            console.log('Lock released');
        }
        
    } catch (error) {
        if (error.name === 'LockError') {
            console.log('Could not acquire lock:', error.message);
        } else {
            throw error;
        }
    }
}
 
// Auto-extending locks (for long operations)
async function doLongWork() {
    const lock = await redlock.acquire(['locks:long-operation'], 10000);
    
    // Extend lock every 5 seconds
    const extendInterval = setInterval(async () => {
        try {
            await lock.extend(10000);
            console.log('Lock extended');
        } catch (e) {
            console.error('Failed to extend lock!');
            clearInterval(extendInterval);
        }
    }, 5000);
    
    try {
        await veryLongOperation();
    } finally {
        clearInterval(extendInterval);
        await lock.release();
    }
}