jonnify·redis /redis-patterns/coordination/redlock/majority-of-n

R2.03.1 · The Redlock algorithm — dive 1

The majority of N.

One Redis node down is no lock at all. Acquire on a majority of N independent masters, and a lock survives the failure of a minority — three of five, with no replication between them.

Grounding (contrast): echo/apps/echo_mq/jobs.ex:126 · the @claim script — EchoMQ holds one lease per job on one Valkey, against one server clock, no majority of N.

The majority vote — toggle each of five masters. Select a master to flip it OK or down; the readout reports whether the count clears the majority line.
M1OK M2OK M3OK M4down M5down majority line: 3 of 5 majority reached
readout · Three of five masters OK — a majority. The lock is held and survives the two down masters.

Static verdicts — 3+/5 OK → majority, held · 2/5 OK → not a majority, released on all 5 · the majority line for N=5 is floor(5/2)+1 = 3.

§1

Why a majority of N

redlock.md.txt · the majority

Redlock runs N independent Redis masters — typically five — with no replication between them. A lock counts as held only when a client got OK on a majority of instances: N/2+1, so at least three of five. The number is what buys the fault tolerance.

With five masters, the majority line is three. Two masters can be down or unreachable and a client can still reach three of the remaining — the lock is still acquirable. That is the property a single-instance lock cannot offer: one node down is no lock at all. The majority also keeps two clients from both holding the lock. Two disjoint majorities of five cannot exist — any two sets of three share at least one master — so the first client to claim three has claimed a master the second cannot also claim, and the second falls short of its own majority.

Independence is the whole point. Each master must be fully independent: no replication, no clustering, ideally in different availability zones. A replicated pair is not two votes — it is the single-instance failover race wearing a second hat. The exact gap Redlock removes reopens the moment two of the N masters are a master and its replica.

N = 5
Five independent masters — the common choice. Tolerates up to two failures while a majority of three survives.
N/2+1
The majority line: three of five. Below it, the acquire failed and the lock is released on all instances.
no replication
Each master is its own vote. A replica is not a second vote; a failover into it is the single-instance race Redlock removes.
quorum overlap
Any two majorities of five share a master, so two clients cannot both reach a majority on disjoint sets.

Five independent masters, three of them a majority — the count buys fault tolerance one node cannot, and the overlap keeps two clients from both winning.

§2

The acquire protocol, in full

redlock.md.txt · acquire

The acquire is time-checked end to end, because a slow acquire can eat the lease before the work begins. The source spells out six steps: read a clock, attempt the lock on every instance, read the clock again, and admit the lock only when both the vote and the elapsed time pass.

# 1. read clock T1
T1 = now_ms()
# 2. on each of N instances, with a 5–50 ms per-instance timeout:
SET resource_name <random_value> NX PX 30000
# 3. read clock T2 → elapsed = T2 − T1
# 4. ACQUIRED only if (OK count ≥ N/2+1) AND (elapsed < TTL)
# 5. validity = TTL − elapsed − clock_drift_allowance
# 6. else → release on ALL instances at once, wait a random delay, retry

The random value is unique across every client and every attempt — at least 20 bytes from a cryptographically secure source. The short per-instance timeout (5–50 ms) keeps an unavailable node from stalling the whole acquire: a master that does not answer within the window is counted as a miss, not waited on. The release runs the same token-checked Lua script on every instance — GET == token then DEL — so a delete lands only on a lock this client still owns, and it is attempted on all N instances, even those where the acquire appeared to fail.

Read a clock, vote across the masters, read the clock again — the acquire is two reads around a set of independent SETs, and the gap between them is the gate.

§3

The two gates behind “held”

redlock.md.txt · the time-check

The vote and the time-check are two independent gates, and a held lock has to clear both. The vote gate is the majority: count the OK responses across the N masters. Below N/2+1, the acquire failed — the lock is released on all instances and retried after a random delay.

The time gate is elapsed < TTL. This is the gate that makes Redlock immune to a slow network during the acquire. Suppose all five masters returned OK, but the round-trips took 31 seconds against a 30-second TTL. By the time the last OK arrived, the first lock had already expired — so the algorithm treats the whole acquire as invalid even though five of five responded, and releases everywhere. Slide the elapsed time below against a fixed majority to watch the second gate rule the lock out on its own.

The elapsed-time guard — 5/5 OK, but does the acquire fit the lease. Slide the elapsed acquire time; the readout reports the validity that remains.
120
0 36 s lease · TTL 30 s TTL elapsed 120 ms < TTL — valid

Static verdicts — elapsed < TTL → valid, validity = TTL − elapsed − drift · elapsed ≥ TTL → the first lock expired, released on all 5 even at 5/5 OK.

A lock is held only when the votes clear the majority line and the acquire fits inside the lease. Five of five means nothing if the acquire ran past the TTL — miss either gate, and the lock is released on all N.

§4

The contrast — EchoMQ holds one lease on one Valkey

echo_mq/jobs.ex:126 · @claim

Redlock spends five independent masters to keep a lock through the failure of a minority. EchoMQ does not take that road. Its per-job lock is the claim lease, and it lives on one Valkey, reached through one EchoMQ.Connector. The @claim script (echo/apps/echo_mq/lib/echo_mq/jobs.ex:126, run by Jobs.claim/3 at jobs.ex:283) is one atomic Lua transition: pop the next id, increment the fence, mark the row active, read one server clock, and stamp the lease.

# @claim (jobs.ex:126) — one lease per job, on one Valkey, against one server clock
local popped = redis.call('ZPOPMIN', KEYS[1])    # the next pending id
if #popped == 0 then return {} end
local id = popped[1]
local jk = ARGV[1] .. id
local att = redis.call('HINCRBY', jk, 'attempts', 1)   # the monotone fence
redis.call('HSET', jk, 'state', 'active')
local t = redis.call('TIME')                           # one server clock, not a majority
local now = t[1] * 1000 + math.floor(t[2] / 1000)
redis.call('ZADD', KEYS[2], now + tonumber(ARGV[2]), id)   # the lease in the active set
return {id, redis.call('HGET', jk, 'payload'), att}

There is no majority of N and no vote. The trade is sound for a job queue because the protected work is made idempotent and a lost lease is a recoverable re-claim, not corruption. When a lease lapses, Jobs.reap (echo/apps/echo_mq/lib/echo_mq/consumer.ex:93) returns the expired entry from active to pending on the same server clock, and the next worker re-claims it; because the handler is idempotent, the re-run is safe. So the rare failure that drops a lock becomes a rare double-run the queue recovers from — the exact outcome Redlock spends five masters to avoid, made harmless instead.

Notes on ValkeyA Lua script runs atomically, so the read-clock-and-stamp of @claim cannot interleave with another worker, and TIME reads the server’s own clock — valkey.io/topics/programmability.

the pattern

Redlock counts votes across N independent masters: a lock is held only on a majority, so a minority of node failures does not drop it — fault tolerance bought with five instances and the time-check.

its EchoMQ application

@claim holds one lease per job on a single Valkey against one server clock (redis.call('TIME')), with attempts (HINCRBY) the fence; a lapsed lease is reclaimed by Jobs.reap as a safe re-claim, not corruption.

Redlock survives a minority of node failures by counting votes; a single-Valkey lease cannot, and that is the whole trade — a queue makes the work idempotent and keeps one Valkey.

a door, not a depth · the EchoMQ course

The single-Valkey lease, on one server clock

EchoMQ does not implement Redlock — this dive cites the single-Valkey lease as the road not taken. The worker-side lock plane and the full v2 script bundle (EVALSHA/NOSCRIPT dispatch, the version-fence internals) are the subject of the dedicated EchoMQ course. The bus that runs every runtime: R2 · Coordination.

§5

Recap — the vote and the clock

next → R2.03.2

Redlock removes the single point of failure by acquiring on a majority of N independent masters: with five and no replication between them, two can be down and a client still reaches three, and two disjoint majorities cannot exist. The acquire is two clock reads around a set of SETs, and a lock is held only when the votes clear N/2+1 and the elapsed acquire fits inside the lease — else it is released on all N. EchoMQ weighs that cost and keeps one Valkey instead, making the protected work idempotent so a lost lease is a recovered re-claim. The next dive takes the timing argument the whole Redlock debate turns on.

§6

References

sources · related

Sources

Related in this course