Distributed Locks with the Redlock Algorithm

1. Why distributed locks are needed

A distributed lock solves a problem that is trivial in single server applications: ensuring that only one process enters a critical section at any given time, when those processes run on different machines. A local mutex does not help here because it only works within a single process space. Typical scenarios are preventing duplicate cron jobs across multiple application servers, serializing payment processing for the same shopping cart, or coordinating which worker takes over a specific batch job.

Redis is well suited for distributed locks because it offers a central, fast and atomic storage point that every process can reach. The base operation is deceptively simple: a key is set if it does not exist yet, and it carries an expiry so a crashed process does not hold the lock forever. The difficulty is not this base operation, it lies in the edge cases that a naive implementation can turn into duplicate execution, even though the lock appears to work correctly.

This article builds distributed locks from the simple single instance lock through the Redlock algorithm for multiple independent Redis instances, up to a critical assessment of when each technique is appropriate and where additional safeguards like fencing tokens become necessary.

2. SET NX PX as the basic building block

The foundation of every Redis based distributed lock is the command SET key value NX PX milliseconds. The NX option ensures the key is only set if it does not already exist, guaranteeing atomic acquisition of the lock. The PX option sets an expiry in milliseconds, so the lock is released even if the holding process crashes before releasing it explicitly. As its value, the key carries a random, unique ID that identifies the current owner of the lock.

This unique ID is not a minor detail, it is the prerequisite for correct unlocking. Without it, a process could accidentally release another process's lock once its own has already expired. The distributed lock pattern with SET NX PX is robust enough for a single Redis instance as long as the owner ID is checked before the key is deleted during unlock.

# Acquire a lock: only succeeds if the key does not exist yet
redis-cli> SET order-lock:4711 "worker-a3f9c2" NX PX 30000
OK

# A second worker trying the same lock fails immediately
redis-cli> SET order-lock:4711 "worker-b7e1d4" NX PX 30000
(nil)

# The lock auto-expires after 30 seconds if never released,
# preventing a crashed worker from holding it forever
redis-cli> TTL order-lock:4711
(integer) 27

3. Race conditions in naive unlocking

The classic mistake with distributed locks is unlocking with a plain DEL key, without first checking whether the calling process still owns the lock at all. Suppose process A holds the lock but is paused so long by garbage collection or network latency that the TTL expires. Process B then acquires the same lock and starts its critical section. If process A wakes up afterward and calls its own DEL, it deletes process B's lock even though it lost ownership long ago. A third process C can then acquire the lock while B is still active, and both end up in the critical section at the same time.

The fix for this distributed lock problem is a Lua script that combines the owner ID check and the deletion atomically in a single Redis call. Without atomicity between GET and DEL, a time window remains in which another process can interfere. This pattern is the minimum standard for any production locking with Redis, regardless of whether one or several instances are used.

-- unlock.lua
-- Only delete the lock if the caller still owns it
-- KEYS[1] = lock key, ARGV[1] = owner token
if redis.call("GET", KEYS[1]) == ARGV[1] then
  return redis.call("DEL", KEYS[1])
else
  return 0 -- lock was not owned by this caller anymore
end

4. The Redlock algorithm in detail

The Redlock algorithm extends the single instance lock to multiple independent Redis instances, typically five, to gain resilience against individual node crashes. The flow: the client tries, one after another, to set the same lock with the same owner ID on all N instances, each with a short connection timeout. The lock is considered acquired if it was successfully set on a majority of instances, meaning at least three out of five, and the total time needed for that is less than the original TTL.

The remaining validity of the lock is calculated as the original TTL minus the elapsed acquisition time minus a safety margin. If acquisition on the majority fails, all locks that were already set are released immediately so resources are not blocked unnecessarily. This majority logic is the core idea of Redlock: even if two out of five instances fail or become unreachable, the lock can still be acquired correctly as long as a majority remains reachable.

# Redlock in principle: same key and token attempted on 5 independent nodes
for host in redis-a redis-b redis-c redis-d redis-e; do
  redis-cli -h "$host" SET order-lock:4711 "worker-a3f9c2" NX PX 30000
done
# Quorum reached if at least 3 of 5 respond OK within a short timeout

# Releasing on every node regardless of which ones succeeded
for host in redis-a redis-b redis-c redis-d redis-e; do
  redis-cli -h "$host" EVAL "if redis.call('GET',KEYS[1])==ARGV[1] then return redis.call('DEL',KEYS[1]) end return 0" \
    1 order-lock:4711 "worker-a3f9c2"
done

5. Implementing Redlock step by step

A minimal Redlock implementation iterates over the configured Redis clients, attempts SET NX PX with the same owner ID on each, and counts the successes. A short connection timeout per instance is important, clearly shorter than the lock TTL, so an unreachable instance does not slow down the entire acquisition process. After trying all instances, it checks whether the majority was reached and whether the elapsed time did not exceed the TTL.

Releasing the lock is done consistently on every instance, not just the ones where acquisition succeeded, because an instance previously considered unreachable might come back online in the meantime and still hold the lock. This consistency during unlock is a frequently overlooked part of correct Redlock implementations.

<?php
declare(strict_types=1);

final class Redlock
{
    /** @param \Redis[] $instances Independent Redis instances, typically 5 */
    public function __construct(
        private readonly array $instances,
        private readonly int $connectTimeoutMs = 50
    ) {
    }

    /**
     * Attempts to acquire a lock across a majority of instances.
     * Returns the owner token on success, or null on failure.
     */
    public function acquire(string $resource, int $ttlMs): ?string
    {
        $token = bin2hex(random_bytes(16));
        $quorum = (int) (count($this->instances) / 2) + 1;
        $start = microtime(true);
        $acquired = 0;

        foreach ($this->instances as $redis) {
            try {
                if ($redis->set($resource, $token, ['NX', 'PX' => $ttlMs])) {
                    $acquired++;
                }
            } catch (\RedisException) {
                // Unreachable instance counts as a failed acquisition
            }
        }

        $elapsedMs = (microtime(true) - $start) * 1000;
        $validityMs = $ttlMs - $elapsedMs - 10; // safety margin

        if ($acquired >= $quorum && $validityMs > 0) {
            return $token;
        }

        $this->release($resource, $token);
        return null;
    }

    /** Releases the lock on every instance, regardless of prior success. */
    public function release(string $resource, string $token): void
    {
        $script = <<<'LUA'
        if redis.call("GET", KEYS[1]) == ARGV[1] then
          return redis.call("DEL", KEYS[1])
        end
        return 0
        LUA;

        foreach ($this->instances as $redis) {
            try {
                $redis->eval($script, [$resource, $token], 1);
            } catch (\RedisException) {
                // Ignore unreachable instances during release
            }
        }
    }
}

6. Kleppmann's critique of Redlock

Martin Kleppmann pointed out two fundamental problems with Redlock in his widely cited 2016 analysis. First: Redlock relies on synchronized clocks and bounded process pauses to guarantee safety. A garbage collection stop, a network timeout or an OS scheduling delay can cause a process to pause far longer than the lock's TTL without noticing it itself. When the process wakes up, it mistakenly believes it still holds the lock, even though it was handed to another process long ago. Redlock cannot rule out this class of failure because it has no mechanism to detect process pauses.

Second, Kleppmann argues that Redlock is neither a pure efficiency lock nor a true correctness lock in the sense of distributed consensus systems like ZooKeeper or etcd. For pure efficiency, meaning avoiding duplicate but harmless work, a simpler single instance lock is often sufficient and less complex. For true correctness guarantees, for example when writing to a filesystem or handling financial transactions, Kleppmann recommends systems with explicit fencing tokens instead of relying on plain Redlock. This critique does not mean Redlock is useless, it means its scope needs to be deliberately bounded.

7. Fencing tokens as a complement

A fencing token is a monotonically increasing number issued by the lock service on every lock acquisition and sent along with every access to the protected resource. The protected resource, for example a storage system or a database, only accepts writes with a token higher than the last one it saw. If a paused process wakes up and tries to write with a stale, lower token, the resource rejects the access, even if the process mistakenly believes it still owns the lock.

This pattern solves exactly the problem Kleppmann raises about distributed locks without fencing: it shifts the correctness guarantee from the lock itself to the resource being protected. Redis does not support fencing tokens natively, but a simple INCR counter per resource can serve as the token source, as long as the protected resource actually implements the ordering check. Without that check on the resource side, any locking scheme, however sophisticated, ultimately remains just an optimization for the common case.

8. When a simple lock is enough

Not every application needs the complexity of Redlock across five instances. If brief duplicate processing is tolerable, for example because the operation itself is idempotent or a downstream deduplication step exists, a simple single instance lock with SET NX PX is entirely sufficient. A typical example is a daily reporting job started via cron on multiple application servers but meant to run only once. If it rarely runs twice by mistake, the only consequence is wasted compute time, not data damage.

Moving to Redlock only pays off once the fault tolerance of a single Redis instance is not sufficient, for example because the lock must still function correctly even if one Redis node fails. For use cases where duplicate execution causes real damage, such as duplicate payment approvals, Redlock alone is, according to Kleppmann, not sufficient either. Combining it with fencing tokens or switching to a consensus system is the right choice there.

9. Practice: libraries and operational experience

In practice, almost nobody implements Redlock completely from scratch, instead relying on established libraries like Redisson for Java, redlock-rb for Ruby or PHP packages that already bring retry logic, fencing support and watchdog mechanisms for automatic TTL extension. A watchdog periodically extends the lock as long as the holding process is still active, reducing the risk that a legitimate but longer running operation gets interrupted by a TTL that was set too short.

Operating Redlock in production shows that the five instances really need to be independent, not just replicas of a primary setup. If they run through Sentinel or a cluster with automatic failover, a failover in the middle of a lock cycle can produce exactly the inconsistencies Redlock is meant to prevent, because a new primary does not know about the lock set on the old primary. For true independence, the instances should run on separate hardware without replication between them.

# Watchdog pattern: periodically extend TTL while the holder is alive
while kill -0 "$WORKER_PID" 2>/dev/null; do
  redis-cli EVAL "if redis.call('GET',KEYS[1])==ARGV[1] then return redis.call('PEXPIRE',KEYS[1],ARGV[2]) end return 0" \
    1 order-lock:4711 "worker-a3f9c2" 30000
  sleep 10
done

# Checking independence: instances must not be replicas of each other
redis-cli -h redis-a INFO replication | grep role
role:master

10. Summary

Distributed locks with Redis range from the simple SET NX PX lock on a single instance to the Redlock algorithm across multiple independent instances. For most use cases with tolerable failure consequences, the simple lock with correct owner checking on unlock is entirely sufficient. Redlock increases fault tolerance but, according to Kleppmann's analysis, does not solve the fundamental problem of process pauses and clock drift that is inherent to every time based lock.

Where true correctness is required, for example for critical writes to a shared resource, a fencing token belongs in the picture, enforcing ordering on the resource side itself. The decision between a simple lock, Redlock and a true consensus system like ZooKeeper should be made based on the actual damage caused by duplicate execution, not on the theoretically strongest guarantee available.

11. FAQ: Distributed Locks with Redlock