Redlock and the Kleppmann Critique

Article.

Redlock is Redis’ proposed algorithm for distributed locks across multiple Redis instances. Martin Kleppmann (author of “Designing Data-Intensive Applications”) wrote a famous critique in 2016 explaining when it breaks. The question under the debate is the one worth answering: can a lock with a timeout guarantee that only one process acts at a time, and if not, what does?

The demonstrations below run against fakeredis 2.40 with redis-py 8.1, which execute the same commands and Lua scripts as Redis.

The mechanism: a key with an owner and a TTL

# Acquire
ok = r.set(lock_key, my_id, nx=True, ex=30)
if ok:
    try:
        do_work()
    finally:
        # Release only if we still hold it
        r.eval("""
        if redis.call('get', KEYS[1]) == ARGV[1] then
            return redis.call('del', KEYS[1])
        else
            return 0
        end
        """, 1, lock_key, my_id)

Properties:

• SET ... NX EX 30 atomically claims the key if it doesn’t exist, sets a 30s TTL.
• my_id (a random UUID per attempt) lets the holder identify their own lock.
• The Lua script makes “release only if we own it” atomic.

This is what most code that says “Redis lock” actually does. It works fine for a single Redis instance. The lock auto-releases on TTL if the holder crashes.

What Redlock adds

Redlock targets distributed deployments with N Redis instances (5 is canonical). The lock is acquired only if a majority of instances accept it. Sells itself as “more resilient than single-Redis” — survives losing some Redis nodes.

# Pseudocode for Redlock acquisition
def acquire(key, ttl_ms):
    nodes = [redis_a, redis_b, redis_c, redis_d, redis_e]
    n_required = len(nodes) // 2 + 1     # 3 of 5
    start = time.monotonic_ms()
    acquired = 0
    for node in nodes:
        try:
            with timeout(50):
                ok = node.set(key, my_id, nx=True, px=ttl_ms)
            if ok:
                acquired += 1
        except Exception:
            pass
    elapsed = time.monotonic_ms() - start
    if acquired >= n_required and elapsed < ttl_ms:
        return True
    # Release any we got
    for node in nodes:
        try: node.del(key, my_id)
        except: pass
    return False

Antirez (Redis creator) published this with the claim that it provides correctness equivalent to a “real” distributed lock service.

Kleppmann’s critique

Kleppmann’s 2016 post argued Redlock is NOT correct for two specific failure modes:

1. GC pause / slow process

client A acquires lock with TTL 30s.
client A starts work.
A's process pauses (GC, page fault, network hang) for 35s.
TTL expires; client B acquires the lock.
A wakes up, thinks it still has the lock, modifies the shared resource.
B also modifies it. Mutual exclusion broken.

The lock has a TTL on the lock holder, but the lock holder doesn’t know its own TTL has expired (without checking, which it doesn’t typically do).

This isn’t specific to Redlock — single-Redis locks have the same problem. It’s a fundamental issue with timeout-based locks.

2. Clock skew

Redlock relies on clocks roughly agreeing across Redis instances to compute “have I acquired the majority within the TTL window”. Clock skew or NTP jumps can violate this:

• A clock jumps back; TTL on that node fires later than expected.
• A clock jumps forward; lock “expires” early; another client gets it.

In well-managed infra, clock skew is small. In a misconfigured fleet, it can be seconds — enough to break Redlock.

Kleppmann’s argument: Redlock claims to be a correct distributed mutex but actually relies on bounded clock skew + bounded process pauses, neither of which is fundamentally guaranteed.

Kleppmann’s recommendation

For correctness-critical locks (financial transactions, exclusive access to mutable state), use a fencing token: a number that increases with every acquisition, which the protected storage checks on each write and rejects if it has already seen a higher one:

def acquire_fenced():
    if r.set("lock:ledger", "x", nx=True, px=1000):
        return r.incr("fence")             # monotonic token per acquisition

STORE = r.register_script("""
local max = tonumber(redis.call('get', KEYS[1]) or '0')
if tonumber(ARGV[1]) <= max then return 0 end
redis.call('set', KEYS[1], ARGV[1]); return 1""")

tokens: A=1, B=2
B writes with token 2: accepted=True
A wakes, writes with token 1: accepted=False

The lock still overlapped; the storage refused the stale holder. The safety comes from the check at the resource, not from the lock, which is why the storage layer must participate. In a database that is a WHERE fence_token < :token on the update; ZooKeeper’s zxid and etcd’s revision serve as tokens for resources that live there (Consensus and leader election).

Antirez’s response

Antirez responded that Kleppmann’s assumed failure modes apply to any lock service — not just Redlock. The Redis algorithm is sound under the same assumptions that make ZooKeeper sound. Engineering judgment: pick the right tool, understand the failure modes.

In practice: Antirez is right that any lock relying on timeouts has GC-pause issues; Kleppmann is right that Redlock specifically markets stronger guarantees than it delivers. Both perspectives are correct.

Practical guidance

For most “make sure only one worker runs this job” use cases, single-Redis lock is fine — the cost of a brief overlap is acceptable. For “two writers to the same row would corrupt the financial ledger”, lock-only-via-Redis is insufficient; either use a real distributed consensus system or use the database’s own primitives (advisory locks, optimistic concurrency with version numbers).

Where it breaks in production

A paused holder outlives its TTL

a = acquire()          # SET lock:ledger <uuid> NX PX 1000
time.sleep(1.2)        # GC pause, a slow call, a stalled VM
b = acquire()

A holds: True; after A's 1.2 s pause, B acquires too: True
both wrote: ['A writes', 'B writes']

Nothing failed. A does not know its lease expired, so it writes after B has started. This is the core of Kleppmann’s argument, and it applies to a single Redis, Redlock, and any lock built on a timeout.

A release that deletes someone else’s lock

A's DEL removed B's lock; C acquires while B still works: True
with the compare-and-delete script, A's release deletes: 0

A plain DEL in A’s finally block runs after A’s lease expired and B took over, so it releases B’s lock and lets C in: three holders from one pause. The Lua compare-and-delete above refuses because the value is no longer A’s token. Every hand-written Redis lock should be checked for this.

And the operational ones

• TTL shorter than the work. A job that sometimes takes 40 s under a 30 s lock overlaps on its slowest runs, which are the ones under load. Renew the lease from a watchdog while working (redis-py’s Lock.extend), and still fence.
• Failover drops the lock. Redis replication is asynchronous: a primary that granted the lock and failed before replicating it hands the replica no lock at all, and a second client acquires it. Redlock exists for this case.

In Python, the libraries

redlock-py, the original reference implementation, has had no release since 2016. Most production code uses a single Redis with SET NX PX and the Lua release.

A cleaner alternative: compare-and-set on a version

CAS = r.register_script("""
local current = redis.call('HGET', KEYS[1], 'version')
if current == ARGV[1] then
  redis.call('HSET', KEYS[1], 'value', ARGV[2], 'version', ARGV[3])
  return 1
end
return 0
""")

def conditional_update(key: str, expected_version: str, new_value: str) -> bool:
    new_version = str(int(expected_version) + 1)
    return CAS(keys=[key], args=[expected_version, new_value, new_version]) == 1

The value and its version live together in one hash, and the script changes both only if the version is still the one the caller read. A version that is compared but never written, or compared against the value itself, works once and then never again.

Optimistic concurrency in Redis — no locks at all. Read the value with its version; on update, only succeed if the version matches what you read. Conflict → retry. Pattern: same as ETag-based HTTP, same as DynamoDB conditional writes.

The trade not taken: Redlock across five nodes

Redlock answers failover: five independent Redis instances, a majority needed. It does not answer the paused holder, because a majority of leases expires on a clock just as one lease does. So it costs five instances, a latency-sensitive acquisition loop and clock-drift assumptions, and buys protection against one failure mode while leaving the more common one open.

The design that holds up is cheaper: a single-instance lock for efficiency (most of the time only one worker does the job), and a fencing check or a database constraint for correctness (when two do, the second write is refused). If you need a lock service with real guarantees, use one built on consensus, such as etcd or ZooKeeper, and still fence.

Kleppmann’s bigger point

The takeaway from the Redlock debate isn’t “Redis bad” — it’s that distributed mutual exclusion is genuinely hard, and any system claiming to provide it should be evaluated by what failure modes it survives.

If you can avoid distributed locks entirely (idempotency, optimistic concurrency, single-writer designs), do. Distributed locks are a code smell that you’re trying to use exclusive access to coordinate something that should be expressed differently.