Redlock and the Kleppmann Critique

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. Knowing both sides is a senior-level interview signal.

The single-Redis lock

# 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 monotonically increasing ID associated with each lock acquisition. The storage layer checks the token:

client A acquires lock, token=22.
client A pauses; TTL expires.
client B acquires, token=23.
A wakes up, sends "write with token 22" to storage.
storage sees "current is 23, reject 22". Operation rejected.

This requires the storage layer to participate. Redis doesn’t natively. ZooKeeper, etcd, Consul provide monotonic sequence numbers usable as fencing tokens.

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).

In Python, the libraries

Most production code uses single-Redis with the simple SET NX EX pattern + Lua-script release. Redlock is rarely worth the operational complexity.

A cleaner alternative: SET NX with version check

def conditional_update(key, old_version, new_value, new_version):
    return r.eval("""
    if redis.call('get', KEYS[1]) == ARGV[1] then
        redis.call('set', KEYS[1], ARGV[2])
        return 1
    end
    return 0
    """, 1, key, old_version, new_value)

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.

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.

Interview angle

• “How would you implement a distributed lock in Redis?” — SET key value NX EX 30 with a unique value (UUID), Lua-script release that checks the value matches. The simple recipe is widely used and correct for best-effort coordination on a single Redis.
• “What’s Redlock?” — multi-instance variant: lock is held if a majority of N Redis instances grant it. Antirez’s proposal for distributed-lock-on-Redis. Operationally complex; rarely worth it over single-Redis for most use cases.
• “What’s wrong with timeout-based distributed locks?” — process pauses (GC, page fault, network hang) can outlast the TTL; another client acquires the same lock; both clients modify the protected resource. Fundamental to any timeout-based lock, not specific to Redis.
• “What’s a fencing token?” — monotonically increasing ID issued per lock acquisition. The protected storage layer validates the token on writes — rejects out-of-date tokens. Kleppmann’s recommended pattern for safety-critical exclusion.
• “Redis vs ZooKeeper for distributed locks?” — ZooKeeper offers strict linearizability, monotonic sessions, fencing-token-like ephemeral nodes. Higher operational complexity. Redis locks are simpler and faster but rely on TTL + bounded pauses for correctness. Pick based on whether you need genuine safety or best-effort coordination.
• “How do you avoid needing distributed locks at all?” — idempotency (operations safe to retry), optimistic concurrency (version numbers, ETags, conditional writes), single-writer architectures (one service owns mutation of a resource), DB-native primitives (Postgres advisory locks, DynamoDB conditional writes). Locks are a last resort.