Redlock and Redis locks: why the TTL is the whole problem

A Redis lock is one command to acquire and a short script to release. The difficult part is that the lock can expire while the work is still running, and Redis will not tell you.

Originally written on 9 July 2018. Migrated from a WordPress blog and reformatted.

The single-instance Redis lock is well known:

SET lock:report:2018-07 <random-token> NX PX 30000

NX ensures the key is set only if absent, so only one caller succeeds. PX 30000 sets a 30-second expiry so a crashed holder does not block everyone forever. The token identifies the holder, and release checks it before deleting:

if redis.call("GET", KEYS[1]) == ARGV[1] then
    return redis.call("DEL", KEYS[1])
end
return 0

This is correct as far as it goes. The problems are all in what happens around the expiry.

The TTL is a guess about the future

The expiry exists to recover from a holder that dies. It is set before the work starts, so it is a prediction of how long the work will take. When the prediction is wrong, the lock expires while the holder is still working, a second caller acquires it, and two processes run the protected operation concurrently. Neither receives an error.

A 30-second TTL on a report that takes 20 seconds on a normal day and 45 on a busy one will produce duplicate reports on busy days, and only on busy days, which makes the bug look intermittent.

Mitigation: extend from a heartbeat. The holder runs a background timer that re-extends the TTL while the work continues:

-- extend only if we still hold it
if redis.call("GET", KEYS[1]) == ARGV[1] then
    return redis.call("PEXPIRE", KEYS[1], ARGV[2])
end
return 0

This handles slow work. It does not handle the holder being paused.

The holder can be paused

A process can stop for longer than the TTL without crashing: a garbage collection pause, a VM migration, a network partition that delays the heartbeat. When it resumes, it still believes it holds the lock. The heartbeat fires, finds the key gone or owned by someone else, and returns 0, but the code between heartbeats has already continued.

This cannot be fixed inside Redis, because the problem is not Redis's view of the lock but the holder's stale view of it.

Mitigation: fencing tokens. Have the lock return a monotonically increasing number (an INCR on a counter at acquisition). Pass that number to the protected resource with every write, and have the resource reject any write whose number is lower than the highest it has seen. A paused holder resuming with an old token is refused by the resource. This moves enforcement to the place that can actually observe the conflict.

Redlock

Redlock extends the scheme to N independent Redis masters: acquire on a majority within a time bound, and treat the lock as held for the TTL minus the acquisition time. It protects against a single Redis node failing or failing over to a replica that had not received the SET.

It does not address the paused-holder problem, and it adds an assumption that the N clocks advance at roughly the same rate. Whether that assumption is acceptable is a judgement about the environment. For coordinating work where a duplicate execution is tolerable, single-instance locking with heartbeat extension is sufficient and simpler. For work where a duplicate is a correctness failure, a fencing token at the resource is required with or without Redlock.

Decision

• Duplicate execution is wasteful but harmless: single-instance SET NX PX, heartbeat extension, token-checked release.
• Duplicate execution corrupts data: add a fencing token checked by the resource, or make the operation idempotent so that duplicates are harmless.
• Redlock addresses Redis availability, not lock correctness. Use it for the first reason only.