jonnify·redis /redis-patterns/coordination/redlock/clock-assumptions

R2.03.2 · The Redlock algorithm — dive 2

Clock assumptions.

Redlock is safe while clocks behave. A lease is a real-time budget — and a pause that outlives it lets a second holder in.

Grounding (contrast): echo/apps/echo_mq/jobs.ex:126 · the @claim script — EchoMQ reads one server clock with redis.call('TIME'), so there is no clock to drift; attempts fences a paused worker, refused stale with EMQSTALE.

The pause that outlives the lease — slide the pause length. While the pause fits inside the lease the write is the holder’s alone; past it, a second holder is admitted.
8
acquire 48 s lease · 30 s left at the write lease ends pause 8 s < lease — the write is the holder's alone active holders: 1

Static verdicts — pause < lease → 1 holder, the write is alone · pause ≥ lease → the lease expired, a 2nd holder admitted, 2 writers.

§1

Clock drift and timing

redlock.md.txt · clock drift

Redlock assumes the clocks on different machines advance at approximately the same rate. It does not require synchronized clocks — only that local clocks do not drift significantly relative to the lock TTL. That is a far cheaper assumption than wall-clock agreement, and it is what lets five independent masters cooperate without a time authority between them.

The algorithm is immune to network delays during the acquire, and the reason is the time-check from the previous dive. After acquiring on a majority, a client reads the clock again and computes elapsed = T2 − T1. If too much time passed, the acquire is treated as invalid even when a majority responded — the slow network is caught by the second gate, not by trusting the round-trips were fast. The drift allowance then trims the usable validity: subtract a small percentage, typically 1–2%, to leave headroom for the clocks running at slightly different rates.

What the time-check cannot catch is a clock that jumps. A manual time change or an aggressive NTP correction can move a machine’s clock forward past the lease boundary in an instant — and a lease whose expiry is computed against that clock expires early, while a client elsewhere acts on a lock the holder still counts as live. The mitigation is operational: configure NTP to slew rather than step, and prevent manual clock adjustments on the Redis servers.

Clock drift erodes validity — vary the elapsed acquire and the drift allowance. The validity is what remains after the elapsed and drift segments.
600
1
0 TTL 30 s elapsed usable validity

Static verdicts — validity = TTL − elapsed − drift · validity > 0 → acquired, finish inside the window · elapsed + drift ≥ TTL → no usable lease, treat as not acquired.

A slow acquire is caught by the T2 re-check and a slice goes to drift — what is left is the validity. When elapsed plus drift reach the TTL, the validity is gone and the acquire is no acquire at all.

§2

The fencing problem

redlock.md.txt · fencing

A subtle issue affects every distributed lock with automatic expiration, Redlock included — and it has nothing to do with the clocks on the Redis servers. It is the pause on the client.

  1. Client A acquires the lock.
  2. Client A pauses — a stop-the-world GC, a context switch, a hypervisor freeze.
  3. The lease expires while A is paused.
  4. Client B acquires the lock; from B’s side it is free.
  5. Client A resumes and acts as the holder — but its lease has already expired.
  6. Both clients operate on the shared resource at once. Mutual exclusion is violated — two writers.

No amount of majority counting prevents this. The lock was held correctly; the holder stalled past the lease, and the lease is a real-time budget the algorithm has no way to extend after the fact. The fix is to move the guarantee off the lock and onto the resource: a fencing token. On acquire, also obtain a monotonically increasing token; carry it on every write; the resource rejects any operation whose token is older than the highest it has accepted.

# the fence runs at the resource, not at the lock:
write(resource, payload, token):
  if token > resource.highest_token_seen:
      resource.highest_token_seen = token
      apply(payload)            # accepted
  else:
      reject()                  # stale token — the paused holder is fenced out

A lease cannot promise a paused client will catch that it expired. A fencing token can — because the resource, not the lock, is where ordering is enforced, and it accepts tokens in increasing order only.

§3

The debate

redlock.md.txt · the debate

Martin Kleppmann published a critique arguing that Redlock is unsafe for correctness-critical applications, primarily because of these timing assumptions: a GC pause or a clock jump can produce two holders, and a lock that can fail this way is the wrong tool when a violation corrupts data. His prescription is the fencing token — let the protected resource enforce ordering, and the lock becomes an optimization rather than a correctness boundary.

Salvatore Sanfilippo (antirez, the Redis creator) replied defending the algorithm’s practical safety: the time-check already rejects a slow acquire, well-run NTP keeps drift bounded, and for the coordination tasks Redlock targets the timing checks are sufficient in practice. Both sides agree on one point: fencing tokens provide stronger guarantees where the protected resource supports them.

Kleppmann

The timing assumptions can break: a GC pause or a clock jump admits two holders, so a lock is the wrong correctness boundary — fence at the resource with a monotonic token instead.

Sanfilippo

The T2 time-check rejects a slow acquire and bounded NTP keeps drift small, so the checks are sufficient in practice — while both agree a fencing token is stronger where the resource supports it.

Kleppmann and Sanfilippo disagree on whether the timing checks suffice — and agree a fencing token the resource enforces is stronger than any lock.

§4

The contrast — EchoMQ reads one server clock

echo_mq/jobs.ex:126 · @claim

A job queue steps out of this debate, because it does not need absolute mutual exclusion and it never compares clocks across nodes. EchoMQ holds one lease per job on one Valkey, and the lease is computed against one server clock. The @claim script (echo/apps/echo_mq/lib/echo_mq/jobs.ex:126) reads redis.call('TIME') once, inside the same atomic transition that stamps the lease — so the clock-drift argument has nothing to act on: there is no second clock to drift against the first.

# @claim (jobs.ex:126) — the lease against ONE server clock; no cross-node comparison
local t = redis.call('TIME')                           # the only clock in the transition
local now = t[1] * 1000 + math.floor(t[2] / 1000)
redis.call('ZADD', KEYS[2], now + tonumber(ARGV[2]), id)   # expiry on the server's own clock

The client pause that Redlock cannot fence is handled by the fencing token EchoMQ already carries: attempts, incremented with HINCRBY in @claim and returned to the worker. If a worker pauses past its lease, Jobs.reap (echo/apps/echo_mq/lib/echo_mq/consumer.ex:93) returns the expired entry to pending, the next worker re-claims it and increments attempts again, and when the paused worker resumes and tries to finish, @complete and @retry refuse its stale token with EMQSTALE … token mismatch. The job row enforces ordering exactly as Kleppmann prescribes, and because the handler is idempotent, the recovered re-claim produces the same result. A timing violation in EchoMQ is a recovered re-run, not corruption.

Notes on ValkeyA Lua script runs atomically, and TIME reads the server’s own clock — one clock, no cross-node comparison, the drift argument has nothing to act on — valkey.io/topics/programmability.

the pattern

Redlock’s safety rests on bounded clocks: a clock jump or a process pause past the lease admits two holders, and the stronger fix is a fencing token the resource enforces — not the lock.

its EchoMQ application

@claim reads one server clock (redis.call('TIME')), so there is no clock to drift; a worker that pauses past its lease carries a stale attempts and is refused at @complete/@retry (EMQSTALE), while Jobs.reap reclaims the lease — a timing violation becomes a recovered job.

Redlock is safe while clocks behave; EchoMQ reads one server clock and fences with attempts at the job row — the resource-side fence Kleppmann prescribes, made literal.

a door, not a depth · the EchoMQ course

One server clock, the attempts fence

EchoMQ does not implement Redlock — this dive cites the single-Valkey lease as the road not taken. How the attempts fence is checked across @complete/@retry and the worker-side lock plane are the subject of the dedicated EchoMQ course. The bus that runs every runtime: R2 · Coordination.

§5

Recap — the lease is a real-time budget

next → R2.03.3

Redlock’s safety rests on bounded clock drift, not synchronized clocks: validity = TTL − elapsed − drift, with the T2 re-check absorbing a slow acquire and a 1–2% allowance absorbing drift. A clock jump and a process pause defeat that — a holder that stalls past the lease can find a second holder already in, the fencing problem every expiring lock shares. Kleppmann calls for a fencing token; Sanfilippo calls the checks sufficient; both agree a token at the resource is stronger. EchoMQ sidesteps the argument: one server clock inside one atomic script, the attempts fence at the job row, and Jobs.reap to reclaim a lapsed lease. The next dive resolves the contrast.

§6

References

sources · related

Sources

Related in this course