Design a Game Matching (Matchmaking) System

Functional Requirements

1. Users should be able to join a game's waiting room and get matched with players of similar skill.
2. Users should be matched roughly in the order they joined, and nobody should wait forever.
3. The system should start the game by the deadline (about 5 minutes) even if the match quality is not ideal.
4. Users should be able to cancel while waiting, and should hear about their match the moment it forms.

Below the line (out of scope):

• Hosting the game servers and running the game session itself. We ask that system for a server address and hand off.
• Computing the skill number. The skill API owns that.
• Party queues, where friends want to be matched together. It is worth one sentence as an extension if asked.

Non-Functional Requirements

1. A match request must end in exactly one outcome: one match, or a cancel. Two matches claiming the same request is the disaster case.
2. The 5-minute promise is enforced by machinery. Honestly stated, the bound is 5 minutes plus a small failover slack (lease timeout plus rebuild time, a few seconds) if a matcher dies at the wrong moment.
3. Joining should survive soft dependencies failing (the skill API). Postgres is the one hard dependency; it runs with a SYNCHRONOUS standby, which these tiny write volumes easily afford, so a failover can never un-commit a match a player was already told about.
4. When a match forms, players should hear about it within a second or two. The budget behind that: one matcher tick (500ms) + the server-allocation call (a few hundred ms, it sits on the critical path) + one push.

Defining the Core Entities

• Match request is one waiting player. It stores a snapshot of their skill (plus a flag if that snapshot was estimated), when they joined, a hard deadline of join time + 5 minutes, a status that moves WAITING → MATCHED or CANCELLED, and the match id once matched.
• Match is the formed group: which game, which players, how far apart their skills ended up, and whether it formed normally (FILLED) or because time ran out (TIMEOUT). Timed-out players still become MATCHED; the TIMEOUT tag lives on the match, not on the player.
• Game config says how many players a match needs (K, somewhere from 2 to 10, and K includes the anchor player), how fast the skill window widens, and whether bots may fill empty seats. 100K games get a global default curve with per-game overrides.
• Skill is fetched from the external skill API once, when the player joins, and saved on the request. The matcher never calls the API itself. External answers get recorded at the boundary, not re-asked in a loop.

API or System Interface

POST   /v1/games/{gameId}/queue     { region }   // region = where the player is; we match nearby first
  → 202 { requestId, skillSnapshot, deadline }   // deadline is stamped now and never moves
  → 409, body: { error: ALREADY_QUEUED, requestId }   // unique index on (userId, gameId) where status=WAITING; a retry gets the existing id back
GET    /v1/queue/{requestId}                        // polling fallback for status
WS     /v1/ws                                       // push: MATCHED { matchId, serverAddr }
DELETE /v1/queue/{requestId}                        // cancel; 200 while WAITING; 409 ALREADY_MATCHED or ALREADY_CANCELLED
PUT    /v1/queue/{requestId}/heartbeat              // stop sending these and we cancel you

• We return 202 rather than 201 because joining starts a process rather than creating a finished thing. The real answer arrives later, over the socket.
• There is only one push type. A timed-out start is still a MATCHED push, because a timeout still forms a real match with a real server address.
• The 409 on cancel exists because a cancel can race the match forming. Deep dive 1 covers who wins.

1) Users should be able to join a game's waiting room

• When a player joins, the API asks the skill API once, saves the answer on the request, stamps the deadline, and inserts the request into Postgres with status WAITING.
• That Postgres table, match_requests, is the source of truth. Everything else in the system can be rebuilt from it.
• The skill call gets a 300ms timeout inside the join path. Down OR slow, same fallback: use the player's last known skill, or 50 as a default, and set the estimated flag. Match quality degrades a little; availability and join latency do not.
• The matcher actually uses that flag: an estimated player starts with a wider window (say ±15), because pretending we know an estimated number to ±5 would manufacture bad matches.

2) Users should be matched by skill, in join order

• Each (game, region) pair has exactly one matcher: a single-threaded loop that keeps that waiting room in memory. Joins, cancels, and heartbeats reach it as messages.
• Every 500ms (the tick), the matcher starts from the player who has been waiting the longest. Call them the anchor.
• The anchor has an acceptable skill range that grows the longer they wait: roughly plus or minus 5 when they just joined, 15 after a minute, 30 after three minutes, and anything goes as the deadline approaches.
• The matcher walks the queue in join order and collects players whose skill falls inside the anchor's range, until it has K players including the anchor. To keep the match itself coherent, it also drops a candidate whose distance from the players already collected exceeds the window, so two teammates cannot be twice the window apart.
• Notice the window is one-sided, and that is a choice: admission is judged by the anchor's widened range, so a freshly joined player can be pulled into a wide match sooner than their own young window would allow. We accept that because it rescues long-waiting players faster; a stricter variant also checks the candidate's own window and pays for it with longer waits.
• If it finds K, it claims all of them atomically (deep dive 1), gets a server address, notifies everyone, and removes them from the queue.
• If the anchor cannot be matched this tick, the matcher does NOT stop: it tries the next-oldest player as anchor, up to a bounded depth (say the 10 oldest). This matters because a lone skill-5 outlier at the head must not block six skill-90 players behind them from matching each other. Head-of-line blocking is the classic failure of naive FIFO matching, and this is the fix.
• The outlier anchor is not abandoned either: their window keeps widening, and their deadline is absolute. Age buys reach; the wall catches whoever reach never helped.

3) The system should start the game by the deadline

• The matcher keeps requests indexed by deadline as well as by join order, and checks the SOONEST deadline every tick. This matters once priority reordering exists, because the front of the queue is then not always the soonest deadline.
• When someone's deadline fires, the skill window no longer applies. We still prefer the closest-skill players who are waiting, but we accept whatever spread we must, and we start the game.
• If fewer than K players are waiting, we start with fewer, or fill the empty seats with bots where that game allows it. The match records that it formed by TIMEOUT, which feeds the tuning metric in deep dive 2.

4) Users can cancel, and are notified instantly

• Cancelling and being matched are both a compare-and-set on the same WAITING status in Postgres. Whichever commits first wins, and the loser is told what happened.
• The cancel API does the CAS synchronously, so it can answer 200 or 409 immediately, and then sends the matcher a message so the in-memory queue evicts that player rather than anchoring on a ghost.
• Notification is a push over the player's WebSocket. The matcher does not hold sockets; it publishes the MATCHED event to a pub/sub channel keyed by user, and whichever gateway node holds that player's socket delivers it. If the gateway restarted, the client reconnects and the GET status endpoint catches it up.
• A duplicate push is harmless because it carries the same match id. Polling is the fallback for everything.

• If they just nod and wait: "the riskiest part is the claim transaction, shall I open exactly-one-match?"
• Running behind: protect dives 1 and 3. Dive 5 exists for the goalpost move to 100K QPS; do not open it unprompted.

1) How do we guarantee a player lands in exactly one match?

• The race we are afraid of is two writers reaching for the same WAITING player at the same moment: a stale matcher during a lease handover, or a cancel racing a claim. Adjacent-region matching (deep dive 4) adds one more way for two rooms to want the same player.

BEGIN;
SELECT 1 FROM leases WHERE partition=$p AND epoch=$my_epoch FOR SHARE;
-- zero rows means we are a zombie: ROLLBACK. Takeover bumps the epoch with an
-- UPDATE, which conflicts with this FOR SHARE, so a stale owner cannot slip through.
INSERT INTO matches (id, game_id, players, formed_by) VALUES (...);
UPDATE match_requests SET status='MATCHED', match_id=$1
  WHERE id IN ($2...$k+1) AND status='WAITING';
-- row count must equal K, or ROLLBACK and retry without the missing player
INSERT INTO match_outbox (match_id) VALUES ($1);
COMMIT;

2) How do we balance match quality against the 5-minute promise?

• Here is the tension in one sentence: a strict skill window makes great matches and broken promises, and a loose one keeps the promise while ruining the matches.

3) What happens when things die?

• Three separate failures hide in this question: the matcher process dies, a match commits and THEN the matcher dies, and the player's client dies.

4) Regional matching, activity, priority, and the viral game

• Regional: region is part of the partition key, so matching starts local. When a player has waited long enough, their home matcher offers them to the adjacent region's matcher and keeps ownership (and the deadline) until an acknowledgement comes back; only then does the hand-off complete. A lost offer therefore costs nothing: the player simply stays home and the offer repeats next tick. The CAS referee backstops the brief window where both rooms know the player.
• Activity level (how recently and how much someone plays): make matching distance a weighted sum of skill difference and activity difference, compared against the same widening threshold. One mechanism handles any number of dimensions.
• Priority (paid tiers, tournament re-queues): give those players a head start on the queue clock, capped at about 30 seconds, and leave their 5-minute deadline untouched. The cap is the no-starvation argument, and the deadline index from HLD-3 is what keeps the promise intact while the queue order bends.
• The viral game: check numbers before designing. Even if one game somehow carried the entire system's peak of 600 events per second, that is light work for one thread. If it ever truly breaks, split that one game's room into skill bands with FIFO inside each band.
• One product decision to surface: a player can queue for two different games at once and win both. If the product wants exclusivity, a MATCHED push triggers cancels of the player's other WAITING requests; if not, it is allowed and documented.

5) What changes if joins hit 100K QPS?

• Redo the scale math before touching the architecture, because every choice so far leaned on the numbers being small. 100K joins per second is a different planet from our 300-600 peak: the waiting population becomes arrival rate times average wait, so 100K/s x 30-60s means 3-6M players waiting at once. Their state is still only about 1GB in aggregate, so memory is not the problem. Write throughput is.
• Hunt for the biggest number first, because it is not joins. If every waiting player heartbeats every 10 seconds, that is 300-600K heartbeats per second arriving, three to six times the join rate. Deep dive 3 already keeps heartbeats out of Postgres (they live in matcher memory), and at this scale that decision stops being a nicety and becomes the design: the biggest flow never touches the database. What remains is to carry it through the front door and size every tier for it.
• The downstream numbers, using K=5: about 20K matches per second, so 20K server allocations per second, 100K MATCHED pushes per second, and 3-6M concurrent WebSocket connections that all want an answer within a second or two.
• Say this out loud: the problem was correctness at small scale; at 100K QPS it is correctness AND throughput, and the win condition is keeping the exactly-one-outcome machinery while spreading the writes.

Final Design

• Joining snapshots your skill once, stamps a hard deadline, and writes the truth to Postgres.
• One single-threaded matcher owns each (game, region) room, matches from the oldest matchable player outward with a widening window, retries deeper anchors so no outlier blocks the queue, and claims match + players + outbox in one guarded commit.
• The soonest-deadline check every tick is what makes the 5-minute promise real. Timeout matches start short-handed or with bots and are recorded as timeouts.
• After the commit, the matcher gets a server address, publishes the MATCHED event, and gateways deliver it to the right sockets. The outbox sweep finishes anything a crash interrupted.
• Leases with epochs own partitions; heartbeats evict ghosts before they ruin a match; Postgres runs with a standby because it is the one hard dependency.

What is Expected at Each Level

• Mid-level candidates are expected to produce a working queue, matcher, and timeout path, and to know the skill API should be asked once at join rather than polled during matching.
• Senior candidates are expected to nail the exactly-one-match machinery (the guarded claim, the cancel race, the outbox for the post-commit crash), keep truth in the table with memory as a cache, and state the widening window as an actual curve.
• Staff candidates are expected to open with the scale math that turns this into a correctness problem, to name both alternatives (SKIP LOCKED fleets and batch optimization) and decline them with reasons, to spot head-of-line blocking in their own greedy design, to treat the timeout fraction as the product dial, to drive the exactly-one-match probe instead of waiting for it, and, when the interviewer moves the goalposts to 100K QPS, to redo the scale math, notice the biggest flow (heartbeats) already bypasses the database, and size every tier for it before adding hardware.

A1) What the poll costs today, and what actually changes

• Price the current loop before replacing it.
  • Each 500ms tick runs an ordered scan to find the oldest waiter, a range scan over skill rating, and a second scan when the first window comes up short.
  • At a queue depth of 50,000, every one of those touches a large index on a table that is simultaneously taking inserts from joins and updates from cancels.
  • The scan grows with depth while the tick rate stays fixed, which is the shape of the problem: the work per tick is unbounded and the time per tick is not.
• What changes, stated narrowly. Redis holds the live pool. Postgres still records every join, every cancel and every formed match.
  • So nothing about correctness or recovery depends on Redis surviving. That sentence is the one that keeps the dive out of trouble.

A2) Structure: two sorted sets over one member set, plus a hash

• One sorted set is not enough, because the matchmaker needs two orderings at once.
  • It picks the anchor by longest wait, and it searches candidates by skill rating.
  • A sorted set gives you exactly one score dimension, so you keep two of them over the same member set.
• A hash alongside holds the per player facts that the two sets cannot carry.
  • Region and mode are what a cancel needs in order to build the two key names it must clean.
  • State is what the client is told it is in, and an expiry on the hash stops abandoned entries leaking.

Every value below comes from the durable join row, written to Postgres before Redis is touched.

-- SOURCE of every value below: the durable join row
SELECT player_id, mmr, enqueued_at
  FROM matchmaking_request WHERE player_id = 'p:9182';
 player_id | mmr  | enqueued_at
 p:9182    | 1450 | 1755530400000

# mm:pool:na:ranked  -  Sorted Set  -  score = MMR
# ordered low to high by rating, which is what a window scan walks
ZADD mm:pool:na:ranked 1450 p:9182
ZRANGE mm:pool:na:ranked 1400 1500 BYSCORE LIMIT 0 50 WITHSCORES
ZREM mm:pool:na:ranked p:9182

# mm:enq:na:ranked  -  Sorted Set  -  score = enqueue time, epoch ms
# ordered oldest to newest, so index 0 is always the anchor
ZADD mm:enq:na:ranked 1755530400000 p:9182
ZRANGE mm:enq:na:ranked 0 0
1) "p:9182"

# mm:player:9182  -  Hash  -  per player facts
# tells cancel which two keys to clean, and tells the client its state
# region, mode and mmr are columns of the same join row.
# 3600 is a chosen policy constant, not a fetched value.
HSET mm:player:9182 region na mode ranked mmr 1450 state QUEUED
(integer) 4          # how many NEW fields it created

HGETALL mm:player:9182
1) "region"   2) "na"
3) "mode"     4) "ranked"
5) "mmr"      6) "1450"
7) "state"    8) "QUEUED"
# a FLAT alternating list: field, value, field, value.
# every value returns as a STRING, including the mmr, so the
# caller parses "1450". The sorted set score is genuinely
# numeric; this field is not.
# fields 2 and 4 are what build the two key names a cancel needs.

EXPIRE mm:player:9182 3600
(integer) 1          # 1 means the timeout was set

A3) The search, worked twice so the widening is not hand waved

• State the window formula up front. window(w) = 50 + 25 * floor(w / 5s), capped at 400 rating points, where w is how long the anchor has waited. Match size is 4 for this example.
• Only two of the six steps are Redis calls per axis. The rest is arithmetic, and saying which is which is what stops the trace sounding like magic.

# PASS 1, tick clock 1755530400000

# STEP 1 - who is the anchor, and when did they join?
# ENQ set. 0 0 = POSITIONS, not scores: no BYSCORE, so this
# means "first element by rank" = oldest waiter.
ZRANGE mm:enq:na:ranked 0 0 WITHSCORES
1) "p:9182"
2) "1755530400000"

# STEP 2 - derive the wait (arithmetic, no Redis call)
#   w = 1755530400000 - 1755530400000 = 0 ms

# STEP 3 - derive the window half-width from w
#   window = 50 + 25 * floor(0 / 5000) = 50

# STEP 4 - the anchor's rating. THIS is where 1450 comes from.
# ZSCORE reads the POOL set, because rating lives there.
ZSCORE mm:pool:na:ranked p:9182
"1450"

# STEP 5 - derive the bounds (arithmetic)
#   low = 1450 - 50 = 1400 ; high = 1450 + 50 = 1500

# STEP 6 - read the window
# POOL set. 1400 1500 = SCORES, because BYSCORE is present.
# Different key, different axis, same command name as STEP 1.
# LIMIT takes offset then count: skip 0, return at most 50.
ZRANGE mm:pool:na:ranked 1400 1500 BYSCORE LIMIT 0 50 WITHSCORES
1) "p:7735"  2) "1408"
3) "p:9182"  4) "1450"
5) "p:4471"  6) "1490"       # 3 found, need 4

Three candidates is short of four, so the tick forms nothing and the anchor stays in the pool.

# PASS 2, tick clock 1755530405000. Same six steps, only the clock moved.

ZRANGE mm:enq:na:ranked 0 0 WITHSCORES
1) "p:9182"
2) "1755530400000"          # anchor unchanged, still the oldest

#   w = 1755530405000 - 1755530400000 = 5000 ms
#   window = 50 + 25 * floor(5000 / 5000) = 75

ZSCORE mm:pool:na:ranked p:9182
"1450"                      # read again rather than assumed

#   low = 1450 - 75 = 1375 ; high = 1450 + 75 = 1525

ZRANGE mm:pool:na:ranked 1375 1525 BYSCORE LIMIT 0 50 WITHSCORES
1) "p:7735"  2) "1408"
3) "p:9182"  4) "1450"
5) "p:4471"  6) "1490"
7) "p:6013"  8) "1523"       # 4 found, enough

• The match forms with p:7735, p:9182, p:4471 and p:6013. Ratings 1408, 1450, 1490 and 1523, a spread of 115 points.
  • p:2210 at 1612 and p:8890 at 1701 stay in the pool, and p:2210 becomes the next anchor on the following tick.
• Why anchor by wait time rather than sweeping the rating axis.
  • Scanning rating alone starves whoever sits at a sparse part of the rating curve.
  • Anchoring on the longest waiter puts a ceiling on queue time, and the widening window is what pays for that ceiling in match quality.
  • This is the same mechanism as deep dive 2, moved to a different store. Nothing about the fairness argument changes.

A4) The claim: check and remove in one Lua script

• Reading candidates and removing them are two round trips, and the gap between them is the bug. Another worker or a cancel can take a player in that gap.
• Redis runs a Lua script as a single atomic unit against the whole keyspace, so putting the check and the removal inside one script closes the gap with no lock.

-- KEYS[1] = mm:pool:na:ranked
-- KEYS[2] = mm:enq:na:ranked
-- ARGV    = the candidate player ids
for i = 1, #ARGV do
  if redis.call('ZSCORE', KEYS[1], ARGV[i]) == false then
    return 0          -- someone is gone, claim nothing
  end
end
redis.call('ZREM', KEYS[1], unpack(ARGV))
redis.call('ZREM', KEYS[2], unpack(ARGV))
return #ARGV        -- all claimed

# register once. Redis returns the SHA1 of the script body,
# which is what EVALSHA takes. It is computed, not invented.
SCRIPT LOAD "<the exact script body above>"
"a4095851f126b1312fa5253c3176d2d41b165a71"

# the 4 ids below are NOT chosen here. They are exactly the
# members STEP 6 of pass 2 returned. The 2 is the key count,
# so KEYS[1] and KEYS[2] follow it.
EVALSHA a4095851f126b1312fa5253c3176d2d41b165a71 2 \
  mm:pool:na:ranked mm:enq:na:ranked \
  p:7735 p:9182 p:4471 p:6013
(integer) 4          # equals the 4 ids passed in, so the group is yours

A5) Cancel races the claim, and that is fine

• Cancel is the same shape: one atomic script touching the same two keys, so Redis serializes cancel against claim for free.
• The design work is not preventing the race. It is deciding what the player is told.

-- cancel script
local n = redis.call('ZREM', KEYS[1], ARGV[1])
redis.call('ZREM', KEYS[2], ARGV[1])
return n

• Returns 1. Cancel won the race. Flip the Postgres row to CANCELED and confirm to the client.
• Returns 0. The claim already removed them, so a match exists with this player in it.
  • Return 409 Conflict carrying the match identifier rather than a bare failure, and let the client jump straight to the accept screen.

A6) Durability: Redis is the working set, not the record

Every state change writes Postgres. Redis is a derived index that exists to make the search cheap.

• If Redis is lost entirely, the pool rebuilds from the durable rows. No player is dropped, they just take one extra tick to reappear.
• Write ordering matters, and it only goes one way.
  • Insert the Postgres row first, then add to Redis. A crash between them leaves a player queued but invisible, which the rebuild sweep fixes.
  • The reverse ordering leaves a player matchable with no durable record, which nothing fixes.

-- rebuild source of truth
SELECT player_id, mmr, enqueued_at
  FROM matchmaking_request
 WHERE status = 'QUEUED'
   AND region = 'na' AND mode = 'ranked';

 player_id | mmr  | enqueued_at
 p:9182    | 1450 | 1755530400000
 p:2210    | 1612 | 1755530401500
 p:8890    | 1701 | 1755530404000

# replay every returned row into both sets. Each score below is
# a column from the result above, nothing is recomputed.
ZADD mm:pool:na:ranked 1450 p:9182
ZADD mm:enq:na:ranked 1755530400000 p:9182
ZADD mm:pool:na:ranked 1612 p:2210
ZADD mm:enq:na:ranked 1755530401500 p:2210
ZADD mm:pool:na:ranked 1701 p:8890
ZADD mm:enq:na:ranked 1755530404000 p:8890

A7) What you bought and what you owe

• What you bought is a search that no longer competes with writes. Both reads go from a scan on a hot table to a logarithmic read on a separate box.
• What you owe is a reconciler, and it is the honest price. Run a periodic sweep comparing QUEUED rows older than a threshold against sorted set membership, and repair either direction.
  • Without it, a dropped write becomes a player who queues forever, which is the exact failure the Postgres design could not produce.

• Both mechanisms are needed, for different reasons.
  • Partitioning is the primary strategy because it removes contention instead of resolving it.
  • Optimistic claiming is the safety net that keeps correctness during the seconds when partition ownership is ambiguous, which is exactly when a worker dies or a deploy rolls.

B1) Mechanism 1, partition: shard by region and mode

• The partition key is region:mode. Each partition owns its own pair of sorted sets, so two workers on different partitions never touch the same key.

• Do not shard on skill rating. This is the part interviewers are actually listening for.
  • A rating band boundary is a wall the widening window can never cross, so a player sitting just under a boundary at a quiet hour waits forever while a perfectly good opponent sits just above it.
  • Region and mode are natural walls, because a cross region match is genuinely undesirable. A rating wall is an artifact of your sharding scheme, not of the product.
  • If you must split a rating axis, use overlapping bands (1400 to 1600 and 1550 to 1750 sharing a seam) and let the atomic claim from A4 settle the case where two workers reach into the overlap.

B2) Mechanism 2, ownership: leases so a partition has one live owner

• Static configuration is simplest, and it leaves a partition dark when its worker dies. Nobody matches in that region until a human notices.
• A lease in Redis gives automatic failover with no extra coordination service. One key per partition, taken only if absent, and held open by renewal.

# acquire: NX means set only if the key does not exist
# PX 10000 is a 10 second TTL
SET mm:lease:na:ranked worker-3 NX PX 10000
OK                    # nil means another worker owns it

GET mm:lease:na:ranked
"worker-3"

-- renew every 3s, only if still the owner
if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('PEXPIRE', KEYS[1], ARGV[2])
else
  return 0        -- lost it, stop working this partition
end

• Renew at roughly one third of the TTL, so two renewals can fail before ownership moves.
• Worker death costs at most one TTL of queue delay on that partition, not a global outage. That is the number to say when asked what a crash costs.

B3) The gap leases alone leave open: fencing tokens

• A lease bounds how long a worker believes it owns a partition. It does not bound how long a stalled worker takes to notice.
  • A long garbage collection pause, a network partition, or a paused container all leave worker-3 waking up after its lease expired and worker-7 took over.
  • worker-3's next claim is a perfectly valid Redis command. Nothing about it looks wrong from Redis's side.
• The fix: every ownership change increments a counter, and the claim script refuses any token that is not current. This is deep dive 3's Postgres lease epoch, written in Redis.

# worker-3 acquired the lease first, so it INCRs first.
INCR mm:fence:na:ranked
(integer) 41          # worker-3 holds token 41

# later, worker-7 takes over and INCRs the same counter.
# 42 is not chosen, it is 41 + 1 returned by Redis.
INCR mm:fence:na:ranked
(integer) 42          # worker-7 holds token 42

-- claim script, fenced version
-- KEYS[3] = mm:fence:na:ranked, ARGV[1] = caller's token
if redis.call('GET', KEYS[3]) ~= ARGV[1] then
  return -1         -- stale owner, reject before touching the pool
end
for i = 2, #ARGV do
  if redis.call('ZSCORE', KEYS[1], ARGV[i]) == false then
    return 0
  end
end
redis.call('ZREM', KEYS[1], unpack(ARGV, 2))
redis.call('ZREM', KEYS[2], unpack(ARGV, 2))
return #ARGV - 1

• t = 0sworker-3

  Holds the lease on na:ranked with fencing token 41. Reads the anchor p:9182 and a candidate window.

• t = 1sworker-3

  Enters a 9 second garbage collection pause. Renewals stop. It does not know it has stopped.

• t = 10sredis

  The lease key expires on its own TTL. The partition is now unowned.

• t = 11sworker-7

  SET NX succeeds, INCR returns token 42. Takes over, forms a match containing p:9182, and the claim returns 4.

• t = 12sworker-3

  Wakes up mid loop, still believing it owns the partition, and calls claim on its stale candidate list. Without fencing this is where p:9182 gets double booked.

• t = 12sworker-3

  With fencing, the script compares token 41 against the current 42 and returns -1 before touching the pool. worker-3 drops its candidates, re-reads the lease, finds it lost, and stops working the partition.

B4) Load shape: hot partitions and the starved sub-pool

• Partitions are not equal. North America ranked can carry the majority of concurrent players while another partition carries a rounding error, and one owner per partition means one worker doing nearly all the work.
• Split the hot one by hashing the player identifier into sub-pools, each with its own owner.

# derive the shard number (arithmetic, no Redis call)
#   crc32("p:9182") = 649320882
#   649320882 mod 4 = 2   -> sub-pool 2 of 4
# scores are the same two columns from the join row, unchanged
ZADD mm:pool:na:ranked:2 1450 p:9182
ZADD mm:enq:na:ranked:2 1755530400000 p:9182
# each sub-pool leases and fences independently
SET mm:lease:na:ranked:2 worker-5 NX PX 10000
INCR mm:fence:na:ranked:2

• Fix it with an overflow pool. Any player whose wait crosses a threshold is promoted out of their sub-pool into one undivided pool that a single dedicated worker drains with a wide window.
  • Density where it matters, parallelism everywhere else.
  • The promotion runs as one Lua script for the same reason the claim does, so a player is never in two pools and never in neither.

# READ both scores first, because the ZREM destroys them and
# the overflow pool has to be rebuilt from the real values
ZSCORE mm:pool:na:ranked:2 p:9182
"1450"
ZSCORE mm:enq:na:ranked:2 p:9182
"1755530400000"

ZREM mm:pool:na:ranked:2 p:9182
ZREM mm:enq:na:ranked:2 p:9182

# re-add with the two scores just read, so the original wait
# survives the move and the player keeps their place
ZADD mm:pool:na:ranked:overflow 1450 p:9182
ZADD mm:enq:na:ranked:overflow 1755530400000 p:9182

B5) The three layers, and what each one is actually for

• Partition is the only layer that removes work rather than resolving it. Two healthy workers on different partitions never read the same keys, so in steady state there is no contention to arbitrate.
• The lease exists for the handover, not for the steady state. It bounds how long a partition can sit unowned after a worker dies, and it stops two workers deliberately starting on one partition.
• The fence exists for the one case the lease cannot see. A stalled worker that wakes up still believing it owns the partition, whose next claim Redis has no reason to refuse.
• Say which layer is correctness and which is optimization. The fenced claim script is the correctness mechanism. Partitioning is a contention optimization on top of it, exactly as the single-writer matcher is in deep dive 1.

• The ordering constraint is the whole reason this section exists. Players are already out of the pool when allocation runs.
  • Any failure after this point strands them, so every branch below either lands them on a server or puts them back in the pool with their original wait time intact.

C1) Capacity: a warm fleet, never a cold boot

• Booting a game server process takes seconds to tens of seconds. That is not a cost you can pay while a player watches a queue spinner, so servers are started before they are needed and held ready.
• Fleet per region. A pool of processes already running and idle, registered with an allocator such as Agones on Kubernetes.
• Buffer sizing. Keep ready capacity above peak concurrent match formation rate multiplied by boot time, with headroom.
  • An undersized buffer means allocation failures during exactly the traffic spike you built it for.
• Scale on the buffer, not on CPU. The autoscaler watches how many ready servers remain, because CPU utilization on idle servers tells you nothing about whether the next match can be placed.

C2) Allocation, and the branch when it fails

• The matchmaker asks the allocator for one ready server in the match's region and gets back an address and a session identifier.
  • It writes the match and the session together in a single Postgres transaction, so a match row never exists without the address its players need.
• When no server is available, there are exactly three moves and one of them is wrong.
  • Retry within region a small number of times with backoff, since the autoscaler may land capacity within a second or two.
  • Then return everyone to the pool with their original enqueue timestamp, not the current time. They keep their place, so a failed allocation does not silently punish the longest waiter.
  • Do not silently place cross region. A player who queued for North America and lands on a European server gets a worse game than a longer queue would have given them. Offer it as a choice on the client after a long wait rather than deciding for them.

-- the claim already removed these players from Redis, so the
-- scores are gone. Re-read them from the durable row.
SELECT player_id, mmr, enqueued_at
  FROM matchmaking_request WHERE player_id = 'p:9182';
 player_id | mmr  | enqueued_at
 p:9182    | 1450 | 1755530400000

# return to the pool using enqueued_at, NOT the current clock.
# That is what preserves their place in line.
ZADD mm:pool:na:ranked 1450 p:9182
ZADD mm:enq:na:ranked 1755530400000 p:9182

C3) The accept window, and what a decline costs

• Players go idle in queue. Sending four people to a server when one has walked away produces a broken game, so the match holds in a PENDING_ACCEPT state with a fixed window, usually around ten seconds.

• t = 0sserver

  Match created PENDING_ACCEPT. Server is allocated and held. The accept prompt is pushed to all four players.

• t = 3sall four

  Accept. The match moves to READY, connection details are released, and the server stops being held.

• t = 10sp:6013

  The window expires with no response. The match moves to DISSOLVED.

• t = 10sserver

  The allocated server is released back to the ready fleet rather than left held.

• t = 10sthe three

  Re-enqueued with their original enqueue timestamps, so they are near the front and are matched again quickly.

• t = 10sp:6013

  Re-enqueued with a current timestamp and a short cooldown. Repeated non-acceptance is what the penalty is aimed at, not one missed prompt.

C4) Notification: delivering the match without losing it

• Pushing directly from the matchmaker means a player whose connection dropped one second earlier never learns they were matched, while their server sits held until the accept window expires.
• Write the event in the same transaction as the match, then deliver it separately. This is the transactional outbox, the same mechanism deep dive 3 uses for the post-commit gap.

# STEP 1 - ask the allocator for one ready server in the region.
# The address is RETURNED here. It is not known before this call.
POST /allocate  { "fleet": "na-ranked", "region": "na" }
200 { "session_addr": "10.4.2.19:7777",
      "match_id": "m:5521" }

# STEP 2 - both values below are fields of that response.
# The player list is the same 4 ids the claim returned.
BEGIN;
  INSERT INTO match (id, session_addr, state)
    VALUES ('m:5521', '10.4.2.19:7777', 'PENDING_ACCEPT');
  UPDATE matchmaking_request SET status = 'MATCHED'
    WHERE player_id IN ('p:7735','p:9182','p:4471','p:6013');
  INSERT INTO outbox (topic, payload)
    VALUES ('match.found', '{"match":"m:5521","addr":"10.4.2.19:7777"}');
COMMIT;

• A relay reads the outbox and publishes to the gateway holding player connections. If publishing fails, the row is still there and gets retried.
• The gateway pushes over a persistent connection, a WebSocket or Server-Sent Events stream, opened when the player entered the queue rather than at match time.
• The client also polls the match status endpoint as a fallback, because a push you cannot confirm is not a delivery.
  • On reconnect the client asks for its current state and picks up the pending accept it missed.
• Delivery is at least once, so the client must tolerate the same match event arriving twice. Key the handler on match identifier and ignore repeats.