Distributed Locks

Why Distributed Locks

Distributed locks coordinate access to shared resources across multiple nodes.

The Problem

Without Distributed Lock:

Node A: Read X = 100
Node B: Read X = 100
Node A: Write X = 150
Node B: Write X = 120

Result: X = 120 (lost update from A!)

With Distributed Lock

With Distributed Lock:

Node A: Acquire lock on X
Node A: Read X = 100
Node A: Write X = 150
Node A: Release lock

Node B: Acquire lock on X
Node B: Read X = 150
Node B: Write X = 120
Node B: Release lock

Result: X = 120 (correct顺序)

Use Cases

Use Case	Why Lock
Leader election	Only one leader
Resource allocation	Prevent double allocation
Task scheduling	One worker per task
Cache invalidation	Prevent duplicate invalidation
Database migrations	One migration at a time

Requirements

1. Mutual exclusion: Only one holder
2. Deadlock-free: Always releasable
3. Fault tolerance: Works with failures
4. Performance: Minimal overhead

Redis Distributed Lock

Basic Implementation

import redis
import uuid
import time

class RedisLock:
    def __init__(self, redis_client, lock_key, ttl=10):
        self.redis = redis_client
        self.lock_key = f"lock:{lock_key}"
        self.ttl = ttl
        self.lock_value = str(uuid.uuid4())  # Unique identifier
    
    def acquire(self, timeout=10):
        """Acquire lock with timeout"""
        end_time = time.time() + timeout
        
        while time.time() < end_time:
            # SET with NX (only if not exists) and EX (expiry)
            if self.redis.set(self.lock_key, self.lock_value, nx=True, ex=self.ttl):
                return True
            time.sleep(0.01)  # Small delay before retry
        
        return False
    
    def release(self):
        """Release lock (only if we own it)"""
        # Lua script for atomic check-and-delete
        script = """
        if redis.call('get', KEYS[1]) == ARGV[1] then
            return redis.call('del', KEYS[1])
        else
            return 0
        end
        """
        self.redis.eval(script, 1, self.lock_key, self.lock_value)
    
    def __enter__(self):
        if not self.acquire():
            raise Exception('Failed to acquire lock')
        return self
    
    def __exit__(self, exc_type, exc_val, exc_tb):
        self.release()

# Usage
redis_client = redis.Redis()

with RedisLock(redis_client, 'resource:123') as lock:
    # Critical section
    process_resource()

Why Use Lua Script?

Problem with GET + DEL:
1. GET lock_value
2. ... time passes ...
3. DEL lock_key

If TTL expires between 1 and 3:
- Another process acquires lock
- We delete THEIR lock!

Solution: Atomic check-and-delete with Lua

Lock Expiry

Lock TTL (auto-expiry):
- Prevents deadlock if holder crashes
- Must be long enough for operation
- But short enough for recovery

Typical: 10-30 seconds

Best Practices

1. Use unique lock value (UUID)
2. Use Lua for atomic release
3. Set appropriate TTL
4. Implement lock renewal for long operations
5. Handle lock acquisition timeout

Redlock Algorithm

Problem with Single Redis

Single Redis:
- If Redis fails, lock is lost
- No redundancy
- Split-brain possible

Redis Cluster:
- Data sharded across nodes
- Lock on one shard only
- Not truly distributed

Redlock Solution

Redlock:
- Multiple independent Redis masters
- Lock acquired on majority
- Tolerates minority failures

Example with 5 Redis masters:
- Need 3/5 to acquire lock
- Can tolerate 2 failures

Algorithm

1. Get current timestamp
2. Try to acquire lock on N/2+1 Redis masters
3. Calculate time elapsed
4. If acquired majority AND elapsed < TTL:
   - Lock acquired
   - Valid for (TTL - elapsed) time
5. If failed, release all locks

Implementation

class Redlock:
    def __init__(self, redis_clients, ttl=10):
        self.redis_clients = redis_clients
        self.ttl = ttl
        self.quorum = len(redis_clients) // 2 + 1
    
    def acquire(self, resource, timeout=10):
        lock_value = str(uuid.uuid4())
        start_time = time.time()
        
        # Try to acquire on majority
        acquired = 0
        for client in self.redis_clients:
            if client.set(f"lock:{resource}", lock_value, nx=True, ex=self.ttl):
                acquired += 1
        
        elapsed = time.time() - start_time
        drift = self.ttl * 0.01 + 0.002  # Clock drift allowance
        
        if acquired >= self.quorum and elapsed < self.ttl - drift:
            return lock_value  # Lock acquired
        else:
            # Release all locks
            for client in self.redis_clients:
                self.release_lock(client, resource, lock_value)
            return None  # Failed
    
    def release(self, resource, lock_value):
        for client in self.redis_clients:
            self.release_lock(client, resource, lock_value)
    
    def release_lock(self, client, resource, lock_value):
        script = """
        if redis.call('get', KEYS[1]) == ARGV[1] then
            return redis.call('del', KEYS[1])
        else
            return 0
        end
        """
        client.eval(script, 1, f"lock:{resource}", lock_value)

Redlock Controversy

Criticisms:
1. Clock assumptions may not hold
2. GC pauses can break safety
3. Network delays can cause issues

Alternatives:
- ZooKeeper locks
- etcd locks
- Consensus-based (Raft)

When to Use

Scenario	Recommendation
Single Redis, low stakes	Basic Redis lock
High availability needed	Redlock or ZooKeeper
Strong consistency needed	ZooKeeper/etcd
Simple coordination	Redis lock