← all topics

Design a Game Matching (Matchmaking) System

Hello Interview structure · plain notes, one idea per line

Understanding the Problem

🎮 What are we building?

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

Non-Functional Requirements

Do the scale math first, because it changes the whole question
  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.

The Set Up

Defining the Core Entities

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

High-Level Design

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

Join: snapshot skill once, stamp the deadline, insert one WAITING row The Player sends a join to JoinAPI. JoinAPI asks SkillAPI for the skill once, falling back to the last-known value or 50 if it is down, then inserts one WAITING row with the deadline into the Postgres MatchRequests table. JoinAPI answers 202 with the requestId and deadline. Player JoinAPI skill snapshotted ONCEdeadline stamped now+5min Postgres (MatchRequests) one row per waiting playerthis table is the truth SkillAPI (external) 1. join {game, region} one WAITING row per (user, game) 2. ask skill ONCE 300ms timeout, then last-known or 50 3. INSERT WAITING deadline saved on the row 4. answers 202 {requestId, deadline} the not-so-happy path: SkillAPI down or slower than its 300ms timeout? last-known skill or default 50, marked estimated

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

One tick: the anchor's window picks the match in join order Step 1: the waiting queue holds players #1 to #7 in join order; the Matcher serves the front, and #1, the anchor, has waited longest so its window is 62 plus or minus 15. Step 2: on the skill line, #2, #5, #1, #7 and #4 fall inside the anchor's window [47 .. 77] and within 15 of each other; #6 at 83 and #3 at 91 fall outside. Step 3: with K = 5 the in-band players form the match, are claimed atomically and leave the queue. STEP 1 - the queue, oldest first. the number is join order, not skill. #1skill 62 #2skill 55 #3skill 91 #4skill 70 #5skill 59 #6skill 83 #7skill 66 Matcher serves the front front: oldest, served next everyone moves this way as the front is served back: new players join here #1 is the ANCHOR: waited longest, so their window is widest: 62 +/- 15 = [47 .. 77] STEP 2 - place everyone on the SKILL line. the dashed band is the anchor's window. 0 25 50 75 100 #1:62 #2:55 #3:91 #4:70 #5:59 #6:83 #7:66 the anchor's window [47 .. 77] #3 and #6 are OUTSIDE the band:they stay waiting, and theirown windows widen meanwhile STEP 3 - K = 5. take the in-band players in JOIN order: #1 #2 #4 #5 #7. that is the match. claim all five atomically (deep dive 1), notify, remove. #3 and #6 move up the queue.

3) The system should start the game by the deadline

One player's acceptable range, growing with their wait For a player with skill 62 the acceptable range is 62 plus or minus 5 on joining, plus or minus 15 after a minute, plus or minus 30 after three minutes, and anything from 0 to 100 at five minutes. Below the bars, the deadline wall is checked every tick; when it fires the game starts now, short-handed, or with bots. one player's acceptable range, growing with their wait (skill 62) 62 just joined 62 +/- 5 after 1 min 62 +/- 15 after 3 min 62 +/- 30 at 5 min anything (0 - 100) the deadline WALL checked on the soonest deadline every tick; fires: start now, short-handed, or bots all ranges center here 0 25 50 75 100 skill quality early, certainty late. the curve is tunable; the wall is not.

4) Users can cancel, and are notified instantly

Cancel and claim race on the same WAITING row A player's cancel and the matcher's claim are both a compare-and-set on the same MatchRequest row, each conditional on status still being WAITING. Whichever commits first wins: a losing cancel gets 409 ALREADY_MATCHED, a losing claim sees fewer than K rows and retries without that player. Player cancels CAS WAITING -> CANCELLED Matcher claims for a match CAS WAITING -> MATCHED MatchRequest row status = WAITING if still WAITING if still WAITING both are a CAS on the same WAITING row.whichever commits first wins; the other is told: cancel lost? 409 ALREADY_MATCHEDclaim lost? row count < K, retry without them

Potential Deep Dives

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

Bad Solution: many matcher threads scanning a shared table with no referee
  • Each thread reads the table, picks players it likes, and writes matches.
  • Sooner or later two matches claim the same player. One match starts a player short, and nobody can explain why.
Good Solution: let the database referee the claim
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;
  • One transaction creates the match, claims all K players, and records an outbox entry saying "this match still needs a server and notifications".
  • If someone cancelled meanwhile, the row count comes back short of K, and the whole transaction rolls back.
  • If you wanted many competing matchers instead, the shape changes: a SELECT ... WHERE status='WAITING' ORDER BY joined_at FOR UPDATE SKIP LOCKED picks candidates first, then the update claims them. Note what SKIP LOCKED costs you: skipping locked rows quietly abandons strict join order, the exact fairness this design is built on.
Great Solution: one single-threaded matcher per waiting room, with the CAS kept as the referee
  • Give each (game, region) exactly one writer. Match forming, cancels, and timeouts all become messages into that one loop, so in steady state there is nobody to race.
  • Be precise about which mechanism does what: the guarded UPDATE is the correctness mechanism, and the single writer is a contention and simplicity optimization. A paused-then-waking zombie matcher, or an adjacent region reaching for your player, still exists; the CAS is what stops them, and the lease carries an epoch number so a stale owner's claims are recognizably stale.
  • We can afford one thread because of the scale math: one waiting room fits in memory, and matching wants to scan a queue, which a single owner does naturally.

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

Bad Solution: one fixed window
  • Say plus or minus 10, forever. At quiet hours there is nobody within 10, so players sit there until the deadline surprises everyone.
Good Solution: widen the window as the player waits
  • Everyone starts picky and gets less picky. You get quality when the room is busy and certainty when it is not.
Great Solution: greedy widening, chosen over batch optimization, with the tradeoff measured
  • Drive each tick from the oldest matchable player, whose window is widest, and enforce the deadline separately with the soonest-deadline check. Order and widening become one mechanism; the promise never depends on the window.
  • Name the serious alternative before someone names it for you: a periodic batch optimizer that, every few seconds, assigns the whole pool to matches minimizing total skill spread subject to wait limits. That formulation fixes greedy's blind spots (head-of-line waste, first-K instead of closest-K). We decline it here because K is small, rooms are small, strict join order is a stated requirement, and greedy with widening plus multi-anchor retry approximates it well at this scale. For team games with roles, revisit that choice.
  • Then watch one number: the fraction of matches that formed by timeout. If it climbs, the window curve is too strict or the game's population is too thin. That single metric, alongside p95 wait and per-match skill spread, drives every tuning conversation.

3) What happens when things die?

Bad Solution: the memory is the only copy
  • The crash silently unqueues thousands of people. They wait forever for a match nobody is building.
Good Solution: truth in Postgres, memory as a cache of it
  • Every join was written to the table before the player got their 202, so a restarted matcher rebuilds its room by reading the WAITING rows.
  • The claim transaction either committed everything or nothing, so the queue itself cannot be half-claimed.
Great Solution: leases for ownership, an outbox for the post-commit gap, heartbeats for ghosts
  • A matcher owns its partition through a lease row in Postgres with an epoch number. If the process dies, the lease expires, a peer takes the partition at the next epoch, and rebuilds the room from the table. Nobody is lost, and a zombie's stale epoch is refused.
  • The database commit is not the finish line. A match can commit and the matcher can die before allocating a server or notifying anyone, leaving K players MATCHED with no game. That is why the claim writes an outbox row: the takeover matcher sweeps unprocessed outbox entries, finishes the allocation call, and re-sends the notifications.
  • Both repeats are safe because each carries the match id: the allocation call uses it as an idempotency key (asking twice returns the same server), and a duplicate push is ignored by the client.
  • Player heartbeats flow to the matcher and live in memory; they are NOT written to Postgres per beat, because 40K waiters beating every 10 seconds would be 4K writes per second, dwarfing the 60-600 joins per second we sized for. On takeover, everyone gets a fresh grace period.
  • When the beats stop, the matcher cancels that player with the same CAS as a user cancel. The point is to evict them BEFORE a match forms around them, so K-1 real players never start a game with a ghost teammate.

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

5) What changes if joins hit 100K QPS?

Matchmaking at 100K joins per second Players join through a pool of API nodes, which insert WAITING rows into one of 64 Postgres shards, hashed by (game, region), and fan the joins and cancels into rooms through a PartitionedLog. Inside a shard, Matchers consume the log and liveness digests from the Gateways, claim matches in one transaction, then allocate game servers and publish MATCHED, which the Gateways push to players. OutboxSweeper reads the committed outbox rows and redoes allocation and publishing after a crash or while the server pool is dry. Players 3-6M waiting API x100 joins + cancels Gateways x60-120 50K sockets each PartitionedLog keyed (game, region) join cancel one shard of 64 -hash(game, region) Postgres shard primary + SYNC standby~1.6K inserts/s Matchers one single-threaded loopper roomdigests, not beats OutboxSweeper redoes 8 and 9after a crash, orwhile the poolis dry GameServerAllocation pre-warmed pool 1. join 100K/s 2. INSERT WAITING 1.6K inserts/s per shard 3. fan into rooms 4. joins + cancels 5. liveness digests beats never leave the socket layer 6. claim: ONE txn ~300/s per shard 7. outbox rows 8. allocate 20K/s 9. publish MATCHED pub/sub by userId; 100K pushes/s held sockets 10. MATCHED push in about a second survived at 100K QPS: exactly one outcome per request (the CAS, now per shard), the 5-minute wall, per-room join ordertraded: no single place to query the world (reporting becomes an async rollup); cross-region matches form in two steps
Bad Solution: buy a bigger Postgres and add read replicas
  • Replicas absorb reads, but this workload is writes: 100K join inserts, about 20K claim transactions touching K rows each, plus cancels, every second. All of it still lands on the one primary and its one WAL, and a single well-tuned primary tops out somewhere in the tens of thousands of small transactions per second. The write volume is past the wall even with heartbeats already kept out of the database.
  • The synchronous standby we rightly insisted on adds a network round trip to every commit, so the latency floor rises exactly when the volume explodes.
  • Vertical scaling also leaves one blast radius: when that primary fails over, every waiting room in the world stalls at once.
Good Solution: shard on the key we already partition by
  • Shard Postgres by hash of (game, region), the same key the matchers already partition on. This is the load-bearing observation: outside the adjacent-region case, all K players of a match live in the same (game, region) partition, so the guarded claim transaction from deep dive 1 stays single-shard. The CAS referee survives sharding untouched.
  • With 64 shards, each shard sees roughly 1.6K inserts per second plus a few hundred claim transactions touching K rows each, plus cancels. That is comfortable for a primary with a synchronous standby, and now a failover stalls 1/64th of the world instead of all of it.
  • Heartbeats stay exactly where deep dive 3 put them: in matcher memory, never in Postgres. Nothing migrates here; there is only a decision to defend when someone suggests persisting liveness for the failover case, and the takeover grace period from deep dive 3 already covers it.
  • The outbox and its sweeper go per-shard, and the pub/sub layer shards by userId. The one cross-shard case is the adjacent-region hand-off from deep dive 4: keep it an ownership hand-off, and form the rare cross-region match as two single-shard steps driven by the outbox (reserve the player at home, then form the match), never a distributed transaction. The reserve step is the same guarded CAS with the forming matchId stamped, so a crash between the two steps is the familiar outbox-crash story from deep dive 1: the sweeper finishes the match or frees the player.
Great Solution: the shards plus a number and a bulkhead for every tier
  • API tier: stateless, so it is arithmetic, but count the real ingress: 100K joins plus 300-600K heartbeats plus cancels is 400-700K requests per second, and heartbeats are most of it. The staff move is to take heartbeats off HTTP entirely: 3-6M players are already holding WebSockets, so liveness rides the socket's ping/pong at the gateway for free, and the API tier sizes for the remaining roughly 100K rps, about 100 nodes at 1K each.
  • Skill API: asked once per join is now 100K reads per second against someone else's service. The snapshot-once rule already saved us from polling; add a short-TTL read-through cache and batch the lookups, and keep the estimated-skill fallback for when it degrades.
  • Join ingestion: joins fan into rooms through a partitioned log keyed by (game, region). The log is transport, not truth: failover recovery still rebuilds the room from the table, exactly as deep dive 3 says.
  • Matchers: the model does not change, one single-threaded loop per room. Call it 10K active rooms at this scale, ten times today's thousand; that averages 10 joins per second per room, which is nothing. Raw heartbeats would be the real message load (a viral room with half a million waiters would take tens of thousands of beats per second into one loop), so gateways aggregate liveness into a per-room digest every few seconds and the loop consumes digests, not beats. The viral-room math from deep dive 4 does change: at 10K joins per second one room holds 300-600K waiting players; the per-tick work is the oldest anchor's window scan, not a full pass over the room, and if that scan ever stops fitting the 500ms tick, the room splits into skill bands with FIFO inside each band.
  • Gateways: 3-6M sockets at about 50K per node is 60-120 nodes. The failure that matters here is the reconnect storm after an AZ loss, so reconnects carry jitter and a resume token, and a reconnect never re-joins a queue, it re-attaches to an existing requestId.
  • Allocation: 20K matches per second against a pre-warmed server pool. While the pool has headroom the call stays on the critical path for latency; when it runs dry, the outbox absorbs the burst and notification lags instead of matches failing.
  • Bulkheads and alarms: a degraded shard 503s joins for its own rooms and touches nothing else, and the alarm is per-room p99 time-to-match against the 5-minute wall, not a global average that hides one dying shard.
  • Close by naming what survived and what was traded. Survived: exactly one outcome per request (single writer plus CAS, now per shard), the 5-minute wall, and join-order fairness, which was always per-room anyway. Traded: there is no longer one place to query the whole world, so global reporting becomes an async rollup, and cross-region matches now form in two steps instead of one transaction.

Final Design

Game matching: final design A Player joins through the API, which asks the SkillAPI once and inserts a WAITING row in Postgres. Inside one (game, region) partition of MatchingService, a single-threaded matcher ticks every 500ms; when it finds K players it claims them in one transaction that commits to Postgres. It then gets a server address from GameServerAllocation and publishes MATCHED to the Gateway, which tells the Player. Player API join / cancel / heartbeat Postgres (the truth) MatchRequest + Match rows SkillAPI (external) 1. join {game, region} skill snapshotted ONCE,deadline stamped now+5min 3. INSERT WAITING 2. ask once MatchingServiceone partition = (game, region) MatcherPool one single-threaded loopper partition, owned via lease MatcherX 4. tick, every 500ms scan from the oldestanchor; windows widenas players wait found K? 5. candidates No: wait a tick,window widens 6. claim: ONE txn CAS all K + INSERT match+ outbox row Yes 7. commit GameServerAllocation 8. get serverAddr idempotent by matchId Gateway (WebSocket) 9. publish MATCHED pub/sub keyed by user 10. pushes MATCHED {matchId, serverAddr} the not-so-happy paths: - crash after 6, before 8/9: the outbox sweep finishes allocation + notification- zombie matcher after lease loss: the claim txn re-checks the lease epoch and aborts- deadline fires: the diamond is bypassed - start with the closest K-1, short-handed, or bots

What is Expected at Each Level