Distributed Locking with Redis: Understanding the Redlock Algorithm

A single Redis instance makes a fine lock for a single-process app, but the moment you have multiple services racing to acquire the same lock — and that Redis instance can fail — a naive SETNX isn't safe anymore. Redlock, proposed by Redis's creator, is an algorithm for acquiring a distributed lock across multiple independent Redis nodes so that no single node's failure or slowness can silently break mutual exclusion.

This is genuinely advanced material — understanding it requires comfort with distributed systems failure modes, not just Redis commands.

Why a Single Redis Lock Isn't Enough

A basic lock looks simple:

SET resource:order-42 my-random-value NX PX 30000

This sets the key only if it doesn't exist (NX), with a 30-second expiry (PX) so a crashed client doesn't hold the lock forever. The problem is that this single Redis node is a single point of failure. If it goes down before replicating the write to a replica, and the replica gets promoted to master, another client can acquire the "same" lock — because the new master never saw the key.

The Redlock Algorithm

Redlock solves this by using N independent Redis masters (the reference implementation uses 5), with no replication or coordination between them. A client wanting the lock does the following:

1. Get the current time in milliseconds.
2. Try to acquire the lock on all N instances sequentially, using the same key and a random value, with a small timeout per instance so a down node doesn't stall the whole process.
3. Compute elapsed time. The lock is considered acquired only if the client got the lock on a majority (N/2 + 1) of instances, and the total elapsed time is less than the lock's validity time.
4. If acquired, the effective validity time is the original TTL minus the elapsed time and clock drift.
5. If the lock wasn't acquired, release it on every instance immediately, whether or not that instance thought it succeeded.

graph TD
    A[Client wants lock] --> B[Record start time T1]
    B --> C[Try SET NX PX on Redis Node 1]
    B --> D[Try SET NX PX on Redis Node 2]
    B --> E[Try SET NX PX on Redis Node 3]
    B --> F[Try SET NX PX on Redis Node 4]
    B --> G[Try SET NX PX on Redis Node 5]
    C --> H{Count successes}
    D --> H
    E --> H
    F --> H
    G --> H
    H -->|Majority acquired AND time OK| I[Lock acquired]
    H -->|Majority failed OR time expired| J[Release lock on all nodes]
    J --> K[Retry after random backoff]

Why Majority Matters

Requiring a majority (not all N) means Redlock tolerates the failure of a minority of nodes — with 5 nodes, up to 2 can be down or unreachable and the lock still works correctly, the same fault-tolerance principle behind Raft and Paxos-based systems. It also prevents split-brain: two clients can't both get a majority of 5 nodes simultaneously, because any two majorities of 5 must overlap by at least one node.

The Random Value and Safe Release

Each client generates a unique random value for its lock attempt (not just any placeholder). Releasing the lock must check that the stored value still matches before deleting it, done atomically via a Lua script:

if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

Without this check, a client could accidentally delete a lock it no longer owns — for example, if its own lock expired and a different client acquired it in the meantime.

Clock Drift: The Real Weakness

Redlock's correctness assumes clocks across the N nodes don't drift too far apart relative to the lock's TTL. If a node's clock jumps forward unexpectedly (a bad NTP sync, a VM pause-and-resume, manual clock changes), that node might expire a lock much earlier than the others believe, opening a window where two clients think they hold the lock simultaneously. This is the core of Martin Kleppmann's well-known critique of Redlock: it depends on real-time clock behavior in ways that are hard to fully guarantee.

Fencing Tokens: The Practical Fix

Even with Redlock done correctly, a paused client (GC pause, VM suspend, network partition) can wake up after its lock has expired and still act as if it holds it — writing to a shared resource after another client has already acquired the lock and moved on. The standard mitigation is a fencing token: a monotonically increasing number returned every time a lock is granted.

Client A acquires lock, gets token 33
Client A pauses (GC, network delay...)
Client A's lock expires
Client B acquires lock, gets token 34
Client B writes to storage, tagging the write with token 34
Client A wakes up, tries to write with token 33
Storage rejects it: 33 < 34 (already saw a higher token)

The protected resource itself — a database, a file store, an API — must be the one enforcing the token check. Redlock alone cannot make this guarantee; it can only reduce the likelihood of two clients believing they hold the lock at once.

When to Use Redlock (and When Not To)

Redlock is a reasonable choice for efficiency locks — cases where a duplicate execution is wasteful but not catastrophic, like preventing the same cron-triggered job from running twice, or coalescing duplicate cache-rebuild requests. It is a risky choice for correctness locks — cases where a duplicate execution corrupts data, like coordinating writes to a financial ledger. For those, use a system with strong consistency guarantees (a consensus-based lock service like ZooKeeper or etcd) combined with fencing tokens enforced by the resource itself, not just Redis.

Common Pitfalls

Using an even number of nodes defeats the majority-quorum logic that makes Redlock resilient — always use an odd number so a majority is unambiguous. Setting per-node acquisition timeouts too high means a single slow node can blow past your lock's TTL before you've even finished the acquisition phase. And treating Redlock as a strict correctness guarantee, rather than a best-effort mutual exclusion mechanism, is the mistake that leads to production incidents — pair it with fencing tokens whenever the operation it protects actually matters.

Redlock reduces the probability of a broken lock; it does not eliminate it. Design your protected operations to survive the case where the lock briefly fails.

Originally published at https://cslant.com/tips/distributed-locking-with-redis-understanding-the-redlock-algorithm