Distributed Locking with Redis and the Redlock Algorithm

When multiple processes or services need exclusive access to a shared resource, you need a distributed lock. Unlike local mutexes, distributed locks must work across machines, handle network partitions, and deal with processes that crash while holding a lock. Redis is a popular choice for distributed locking because of its speed and atomic operations.

The basic Redis lock

The simplest distributed lock uses Redis SET with the NX (set if not exists) and EX (expiry) flags:

import redis
import uuid
import time

client = redis.Redis(host='localhost', port=6379, decode_responses=True)

def acquire_lock(lock_name: str, ttl_seconds: int = 10) -> str | None:
    """Try to acquire a lock. Returns a token if successful, None otherwise."""
    token = str(uuid.uuid4())
    acquired = client.set(
        f"lock:{lock_name}",
        token,
        nx=True,   # only set if key does not exist
        ex=ttl_seconds  # auto-expire after TTL
    )
    return token if acquired else None


def release_lock(lock_name: str, token: str) -> bool:
    """Release a lock only if we own it (token matches)."""
    # Lua script ensures atomic check-and-delete
    script = """
    if redis.call("GET", KEYS[1]) == ARGV[1] then
        return redis.call("DEL", KEYS[1])
    else
        return 0
    end
    """
    result = client.eval(script, 1, f"lock:{lock_name}", token)
    return result == 1

Why use a token?

The token (a random UUID) identifies the lock owner. Without it, any process could release another process’s lock:

# WITHOUT token: dangerous
Process A acquires lock
Process A takes too long, lock expires
Process B acquires lock
Process A finishes and deletes the lock  <-- deletes B's lock!
Process C acquires lock  <-- now B and C both think they have the lock

The Lua script in release_lock atomically checks that the token matches before deleting, preventing this race condition.

Using the lock

def transfer_funds(from_account: str, to_account: str, amount: float):
    lock_key = f"account:{from_account}"
    token = acquire_lock(lock_key, ttl_seconds=30)

    if token is None:
        raise Exception("Could not acquire lock, try again later")

    try:
        balance = get_balance(from_account)
        if balance < amount:
            raise InsufficientFundsError()

        debit(from_account, amount)
        credit(to_account, amount)
    finally:
        release_lock(lock_key, token)

Lock renewal (watchdog)

If your critical section might take longer than the lock TTL, you need to renew the lock. A background thread (watchdog) periodically extends the TTL while the lock holder is still active.

import threading

class DistributedLock:
    def __init__(self, client, name, ttl=10):
        self.client = client
        self.name = f"lock:{name}"
        self.ttl = ttl
        self.token = str(uuid.uuid4())
        self.watchdog = None
        self.acquired = False

    def acquire(self, timeout=30) -> bool:
        """Try to acquire the lock within a timeout period."""
        deadline = time.time() + timeout
        while time.time() < deadline:
            if self.client.set(self.name, self.token, nx=True, ex=self.ttl):
                self.acquired = True
                self._start_watchdog()
                return True
            time.sleep(0.1)
        return False

    def release(self):
        """Release the lock and stop the watchdog."""
        self._stop_watchdog()
        if self.acquired:
            script = """
            if redis.call("GET", KEYS[1]) == ARGV[1] then
                return redis.call("DEL", KEYS[1])
            else
                return 0
            end
            """
            self.client.eval(script, 1, self.name, self.token)
            self.acquired = False

    def _start_watchdog(self):
        """Periodically renew the lock TTL."""
        def renew():
            while self.acquired:
                # renew only if we still own the lock
                script = """
                if redis.call("GET", KEYS[1]) == ARGV[1] then
                    return redis.call("PEXPIRE", KEYS[1], ARGV[2])
                else
                    return 0
                end
                """
                result = self.client.eval(
                    script, 1, self.name, self.token, self.ttl * 1000
                )
                if result == 0:
                    self.acquired = False
                    break
                time.sleep(self.ttl / 3)  # renew at 1/3 of TTL

        self.watchdog = threading.Thread(target=renew, daemon=True)
        self.watchdog.start()

    def _stop_watchdog(self):
        self.acquired = False
        if self.watchdog:
            self.watchdog.join(timeout=2)

    def __enter__(self):
        if not self.acquire():
            raise TimeoutError("Failed to acquire lock")
        return self

    def __exit__(self, *args):
        self.release()


# usage with context manager
with DistributedLock(client, "payment-processing") as lock:
    process_payment()

The Redlock algorithm

A single Redis instance is a single point of failure. If the Redis server crashes, the lock is lost. The Redlock algorithm, proposed by Salvatore Sanfilippo (antirez), uses multiple independent Redis instances to make the lock more resilient.

How Redlock works

1. Get the current time in milliseconds.
2. Try to acquire the lock on N independent Redis instances (typically 5) using the same key and token.
3. Calculate the elapsed time. If the lock was acquired on a majority (N/2 + 1) of instances AND the elapsed time is less than the lock TTL, the lock is considered acquired.
4. If the lock was not acquired on a majority, release the lock on all instances.

class Redlock:
    def __init__(self, redis_instances, ttl=10000):  # ttl in ms
        self.instances = redis_instances  # list of redis.Redis clients
        self.ttl = ttl
        self.quorum = len(redis_instances) // 2 + 1
        self.clock_drift_factor = 0.01  # 1% clock drift

    def acquire(self, resource: str) -> dict | None:
        token = str(uuid.uuid4())
        retry_count = 3

        for attempt in range(retry_count):
            start_time = time.time() * 1000  # ms
            acquired_count = 0

            for instance in self.instances:
                try:
                    if instance.set(
                        f"lock:{resource}", token,
                        nx=True, px=self.ttl
                    ):
                        acquired_count += 1
                except redis.RedisError:
                    pass  # instance unreachable, continue

            elapsed = time.time() * 1000 - start_time
            drift = self.ttl * self.clock_drift_factor + 2  # ms

            # check if we got quorum within time budget
            validity_time = self.ttl - elapsed - drift
            if acquired_count >= self.quorum and validity_time > 0:
                return {
                    'token': token,
                    'resource': resource,
                    'validity': validity_time
                }

            # failed: release all locks
            self._release_all(resource, token)
            time.sleep(0.05 * (attempt + 1))  # random delay before retry

        return None

    def release(self, lock_info: dict):
        self._release_all(lock_info['resource'], lock_info['token'])

    def _release_all(self, resource: str, token: str):
        script = """
        if redis.call("GET", KEYS[1]) == ARGV[1] then
            return redis.call("DEL", KEYS[1])
        else
            return 0
        end
        """
        for instance in self.instances:
            try:
                instance.eval(script, 1, f"lock:{resource}", token)
            except redis.RedisError:
                pass

Redlock tradeoffs

Redlock is more resilient than a single-instance lock, but it has been debated extensively. Martin Kleppmann raised concerns about clock drift and process pauses. The key points:

• Clock drift: Redlock assumes clocks on different machines do not drift significantly. In practice, NTP keeps clocks synchronized within milliseconds, but large jumps can happen.
• Process pauses: A GC pause or OS scheduling delay can cause a process to think it still holds a lock after the lock has expired.

Fencing tokens

Fencing tokens are the strongest defense against stale lock holders. The idea: each lock acquisition generates a monotonically increasing token. The protected resource rejects operations with tokens older than the last one it saw.

def acquire_lock_with_fence(lock_name: str, ttl: int = 10) -> tuple[str, int] | None:
    token = str(uuid.uuid4())
    acquired = client.set(f"lock:{lock_name}", token, nx=True, ex=ttl)

    if acquired:
        # increment fencing token
        fence_token = client.incr(f"fence:{lock_name}")
        return (token, fence_token)
    return None


def write_with_fence(resource_id: str, data: dict, fence_token: int):
    """Write only if our fencing token is the latest."""
    # the storage layer must enforce this
    result = db.execute("""
        UPDATE resources
        SET data = %s, fence_token = %s
        WHERE id = %s AND fence_token < %s
    """, (json.dumps(data), fence_token, resource_id, fence_token))

    if result.rowcount == 0:
        raise StaleTokenError("A newer lock holder has already written")

With fencing tokens, even if a process holds a stale lock due to a GC pause, its writes are rejected because its fencing token is outdated.

Common pitfalls

1. Forgetting to set a TTL: A lock without expiration becomes permanent if the holder crashes.
2. Releasing a lock you do not own: Always use a token and the Lua check-and-delete script.
3. Using SETNX + EXPIRE separately: These are not atomic. Use SET key value NX EX ttl instead.
4. Ignoring clock drift in Redlock: Account for drift in your validity time calculation.
5. Not handling Redis failures: Wrap Redis calls in try/except. A lock you cannot release is worse than no lock at all.
6. Using locks for performance instead of correctness: If you are using locks to reduce load, consider rate limiting or queuing instead.

When to use distributed locks

• Correctness: Preventing double-processing of payments, preventing concurrent modifications to the same resource.
• Coordination: Ensuring only one instance runs a scheduled job at a time.
• Not for performance: If you are locking to prevent thundering herds, consider caching or circuit breakers instead.

Summary

For most applications, a single Redis instance lock with a Lua-based release script and a watchdog for renewal is sufficient. Use Redlock when you need higher availability and can accept its complexity. Always use fencing tokens when the cost of a stale lock holder is high. The safest distributed lock is the one you do not need, so design your systems to minimize the need for coordination whenever possible.