Design a Game Matching (Matchmaking) System

Hello Interview structure · plain notes, one idea per line

Understanding the Problem

🎮 What are we building?

A user picks a game and enters a waiting room for it.
The system groups players with similar skill into a match, and the game starts once the match is formed.
Skill is a number from 0 to 100 that we fetch from an external skill API.
Every user is willing to wait about 5 minutes at most. If we cannot find a good match by then, the game starts anyway.
People who joined earlier should be matched earlier, like a queue.

Functional Requirements

Users should be able to join a game's waiting room and get matched with players of similar skill.
Users should be matched roughly in the order they joined, and nobody should wait forever.
The system should start the game by the deadline (about 5 minutes) even if the match quality is not ideal.
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

Do the scale math first, because it changes the whole question

1M daily users, each joining about 5 games a day. That comes out to about 60 joins per second on average, and maybe 300-600 per second at peak if we assume a 5-10x peak factor.
How many people are waiting at once? That is arrival rate multiplied by average wait. At the PEAK rate of 300-600 per second, with a 30-60 second average wait, about 10-40K people are waiting at the busiest moment.
Each waiting player is a couple hundred bytes of state, so even 40K of them is a few megabytes. Every waiting room in the system fits comfortably in one process's memory.
There are 100K games, but most have nobody waiting. Maybe a thousand games have an active waiting room at any moment.
So say this out loud: this is a correctness and fairness problem, not a throughput problem.

A match request must end in exactly one outcome: one match, or a cancel. Two matches claiming the same request is the disaster case.
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.
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.
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

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.

High-Level Design

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.

Potential Deep Dives

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.

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?

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.

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?

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.

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

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.

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

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.