Everyone thinks matchmaking is “put waiting players in a list, grab the first ten, start a game.” That works in a hackathon demo with fifty players. Then the interviewer piles on the real constraints: the ten players you grabbed have to be close in skill or the match is a stomp and everyone rage-quits; they have to be in the same region or the connection lags to death; the ping between them has to be low even within a region; nobody should wait more than about thirty seconds staring at a “finding match” spinner; and the two teams you form out of those ten have to be balanced against each other, not just individually skilled. And you are doing this for 10 million people queued at the same time, continuously.
Matchmaking is deceptive because it is not one problem, it is a constrained optimization running under a latency budget. You are trying to satisfy skill closeness, region, network latency, and low queue time all at once, and those goals fight each other: the tightest-skill match might be a player on another continent, and the lowest-ping match might be someone 400 ELO above you. The whole design is about how you search a huge pool of waiting players for a good-enough group fast, how you relax your requirements as someone waits longer so they never wait forever, how you split two teams evenly, and how you do all of it across many machines when the pool is too big for one.
Let me do it properly.
Functional Requirements (FR)
In scope:
- Enqueue for a match. A player hits “play”; the system creates a matchmaking ticket holding their skill rating, region, latency measurements to nearby datacenters, party members, and the game mode they want. The ticket enters a pool of waiting players.
- Form a match. Group N players (say 10 for a 5v5) who are mutually acceptable: close skill, same region, low pairwise latency, compatible mode. Emit a match proposal.
- Skill-based matching (ELO/MMR). Players should face opponents near their own rating. A 1500 should not be dropped into a lobby of 2400s.
- Team balancing. Once N players are chosen, split them into two teams whose summed (or averaged) skill is as equal as possible, so the game is a coin-flip, not a foregone conclusion.
- Expanding search over queue time. The longer a player waits, the wider the acceptable skill and latency window grows, guaranteeing a match eventually even for rare ratings (a top-500 grandmaster at 3am).
- Party / group support. A pre-made party of 3 must be matched together, and their combined skill considered as a unit.
- Match lifecycle. After a proposal, players accept, a game server is allocated, and the lobby handshake completes. Handle declines and no-shows by re-queuing the rest.
- Cancel / dequeue. A player backs out; their ticket is removed cleanly.
Explicitly out of scope (name it so you own the scope):
- The rating algorithm itself. How ELO/Glicko/TrueSkill numbers are computed after a match is a separate ratings service. We consume a rating and update it post-match, but designing the math is not this system.
- Game server hosting / netcode. Spinning up the actual game simulation, tick loop, and authoritative physics is a separate fleet. We allocate a server and hand off; we do not build it.
- Anti-cheat and smurf detection. Detecting boosted or alt accounts is a large adjacent system. We assume ratings arriving are the player’s real skill and note where the gate sits.
- Voice chat, social graph, friend invites. Party formation we handle; the friends list and voice are separate.
- Ranked ladder / seasonal rewards. Turning wins into ladder points and season rewards is downstream business logic reading match results.
The one decision that drives everything: matchmaking is a soft, multi-constraint optimization under a hard time budget, not an exact lookup. There is rarely a perfect group waiting; there is a good-enough group, and “good enough” gets looser the longer you wait. So the design is dominated by how you index waiting players so you can find nearby-skill candidates fast, and how you widen the acceptance window over time so match quality degrades gracefully instead of anyone waiting forever.
Non-Functional Requirements (NFR)
- Scale: ~10M concurrent players in queue at peak across all regions and modes. Ticket creation on the order of hundreds of thousands per second at rush hour (matches are short, 10-30 min, so players re-queue constantly). A 5v5 match consumes 10 tickets, so match formation runs at tens of thousands of matches/sec.
- Latency: the p50 time-to-match should be a few seconds, p99 under 30 seconds. The matchmaking decision (once candidates are gathered) should be milliseconds; the wait is dominated by pool depth, not compute. Ticket enqueue ack under ~50ms.
- Match quality: teams within a target skill delta (say both teams within ~50-100 ELO of each other), all players within a region, pairwise ping under a threshold (say 60-80ms) that widens with wait time.
- Availability: 99.9%+. Matchmaking down means nobody can play, which is a revenue and reputation event. It must survive node failures without losing queued tickets or forming corrupt lobbies.
- Consistency: a player must be in exactly one match at a time. Double-booking a player into two lobbies is the cardinal sin. This needs a real exclusivity guarantee (a lock / atomic claim) even though most of the system is eventually consistent and best-effort.
- Fairness / no starvation: every ticket must eventually match. Rare ratings and off-peak hours must not leave someone spinning forever. The expanding window is what enforces this.
- Durability: a ticket is transient (seconds to tens of seconds of life) but must not vanish on a node crash mid-queue, or the player is stuck on a dead spinner. Tickets are persisted/replicated enough to survive a single node loss.
Back-of-the-Envelope Estimation (BoE)
Let me ground it in numbers.
Traffic:
Concurrent players in queue (peak): 10,000,000 (10M)
Avg match length: ~15 min
A player finishes a match and re-queues; also new players log on.
Ticket creation rate:
If 10M are cycling through ~15-min matches, each player generates
~4 match-joins/hour => 10M * 4 / 3600 sec ≈ 11,000 tickets/sec average.
But arrivals are spiky (a match ends -> a burst of 10 players re-queue
together; prime-time login waves). Size for peak:
Peak ticket creation ≈ 100,000 - 300,000 tickets/sec
Matchmaking is spiky in a way leaderboards are not: when a 100-player battle royale ends, 100 tickets appear in the same instant, and prime-time login waves stack on top. Size for the peak, not the 11K average.
Match formation rate:
5v5 mode: 10 tickets per match.
At 100K tickets/sec incoming, we must FORM matches at:
100,000 / 10 = 10,000 matches/sec (just to keep the pool from growing)
Across regions and modes this is spread, but a single popular
region+mode bucket can carry tens of thousands of tickets/sec alone.
The critical insight: match formation must keep pace with ticket arrival, or the queue depth (and therefore wait time) grows without bound. If tickets arrive at 100K/sec and we only form matches for 80K/sec worth of players, the backlog swells and p99 wait time blows past 30s. Throughput of the matcher is the thing we design for.
Read vs write:
Writes:
- Ticket enqueue: ~100K-300K/sec peak (the hard number).
- Ticket state updates (matched/accepted/cancelled): similar order.
Reads:
- The MATCHER reads candidate pools: each matching pass scans/queries
a skill-neighborhood of the pool. This is the internal hot read,
not user-facing. Millions of pool reads/sec across all buckets.
- Player polling "am I matched yet?": 10M players polling every ~2s
= 5M QPS if we poll. => push over WebSocket instead (see HLD).
If 10M waiting players each polled “am I matched yet?” every 2 seconds, that is 5M QPS of pure status checks. That alone justifies a push channel (WebSocket/SSE) so we notify on match instead of being hammered by polls. The internal hot read is the matcher scanning skill-neighborhoods, which is what we actually optimize.
Storage:
Per ticket in the active pool:
player_id (16B) + rating (4B) + region (4B) + mode (4B)
+ latency vector to ~5 DCs (~20B) + party info (~32B)
+ timestamps/state (~24B) ≈ ~150-250 bytes/ticket.
Active pool at peak: 10M tickets * ~200 B ≈ 2 GB in RAM.
Two gigabytes of active tickets is small; matchmaking is not a storage problem, it is a compute and coordination problem. The pool fits in memory easily. The pool is also highly transient: a ticket lives seconds to tens of seconds, then it is consumed by a match or cancelled. There is no year-over-year growth to store; the “database” here is a fast, shardable, in-memory pool.
Bandwidth:
Ticket enqueue payload: ~250 B. At 300K/sec => ~75 MB/sec ingress. Modest.
Match notifications: push a small "match found" msg (~500 B) over WS
at match rate (tens of thousands/sec) => a few
tens of MB/sec. Modest.
Bandwidth is a non-issue. The scarce resources are matcher throughput (forming 10K+ matches/sec while honoring skill+region+latency constraints) and exclusivity coordination (never double-booking a player). Size for those.
High-Level Design (HLD)
The system splits into an ingest path that creates and persists tickets and routes them into the correct pool, a set of matchers that each own a slice of the pool and continuously form groups, an allocation path that reserves a game server and drives the accept handshake, and a notification path that pushes results to players. The heart of it is the pool, partitioned by region+mode and indexed by skill, plus the matcher loop that runs an expanding-window search over that pool.
INGEST PATH (ticket creation, ~100K-300K/sec peak)
┌──────────────────────────────────────────────────────────────────────┐
│ Game Client --"play"--> API Gateway / LB --> Matchmaking Ingest Svc │
└───────────────────────────────────────┬────────────────────────────────┘
│ build ticket {rating,region,
│ latency-vec,mode,party,ts}
┌─────────▼──────────┐
│ Ingest Service │ (stateless)
│ - persist ticket │
│ - route to pool │
└───┬───────────┬────┘
durable/replicated│ │ route by (region, mode)
┌───────────▼──┐ ┌───▼────────────────────────┐
│ Ticket Store │ │ MATCHMAKING POOLS │
│ (Redis + WAL /│ │ partitioned region+mode, │
│ replicated) │ │ each bucketed by SKILL │
│ SOURCE OF │ │ ┌────────────┐ ┌──────────┐ │
│ TRUTH for │ │ │ NA / 5v5 │ │ EU / 5v5 │ │
│ ticket state │ │ │ skill │ │ skill │ │
└───────────────┘ │ │ buckets: │ │ buckets │ │
│ │ [0-800] │ │ ... │ │
│ │ [800-1200] │ │ │ │
│ │ [1200-1600]│ │ │ │
│ │ ... │ │ │ │
│ └─────┬──────┘ └──────────┘ │
└───────┼──────────────────────┘
│ each pool owned by a
│ MATCHER (leader per shard)
┌────────▼─────────┐
│ Matcher Workers │ loop:
│ - scan neighbor │ gather candidates
│ skill buckets │ in expanding window
│ - form group of N│ balance 2 teams
│ - ATOMIC claim │ reserve players
└───────┬───────────┘
match proposal │
┌──────────▼───────────┐
│ Allocation Service │
│ - reserve game server│
│ from Server Fleet │
│ - accept handshake │
└───────┬───────────────┘
│ push "match found"
┌──────────▼───────────┐
│ Notification Gateway │ WebSocket/SSE
│ fan-out to N players │ to each client
└───────────────────────┘
Request flow - enqueue and match (the hot path):
- The client sends
POST /queuewith the desired mode. The Ingest Service enriches it into a full ticket: pulls the player’s current rating from the ratings service, reads the client-measured latency vector (ping to each nearby datacenter), attaches party members, and stampsenqueued_at. - Ingest persists the ticket to the Ticket Store (Redis, replicated, with a WAL) so it survives a node crash, then routes it to the correct pool by
(region, mode), inserting it into the skill bucket matching its rating. Ack the client202with a ticket id and open a WebSocket for the result. - The matcher owning that pool runs a continuous loop. Each pass it takes the oldest waiting tickets, gathers candidates from the player’s skill bucket and, as needed, adjacent buckets (the expanding window), until it has N mutually acceptable players (skill delta, region, pairwise latency all within the current, wait-time-widened thresholds).
- Once it has N players, the matcher balances two teams (partition the 10 into two 5s with near-equal summed skill) and then performs an atomic claim: it must reserve all N tickets exclusively so none of them is grabbed by another match. If the atomic claim succeeds, it emits a match proposal; if any player was already claimed, it releases and retries.
- The Allocation Service reserves a game server in the players’ shared region and drives the accept handshake. On all-accept, it hands the server address to all N clients via the Notification Gateway. On decline/timeout, the accepted players are re-queued (with a slight priority bump for having waited).
Request flow - the notification path:
- Rather than 10M clients polling, each waiting client holds a WebSocket to the Notification Gateway. When a match forms, the gateway pushes “match found + accept prompt,” then “server ready + connect here.” This turns a 5M-QPS poll storm into event-driven pushes at match rate.
The key architectural insight: the pool is partitioned so that any single matcher only ever looks at players who could plausibly match each other (same region, same mode, near skill). A 10M-player global pool is unsearchable in a 30s budget; ten thousand small (region, mode, skill-band) pools are each trivially searchable, and the only cross-pool work is the expanding window occasionally reaching into a neighboring skill band. Partition-to-make-tractable is the whole game.
Component Deep Dive
Four hard parts: (1) the matcher itself - how you find a good-enough group fast without scanning 10M players, (2) the expanding search window that trades match quality for bounded wait time, (3) balancing two teams evenly, and (4) exclusivity - never double-booking a player across concurrent matchers. I will walk each from naive to scalable.
1. Finding a Group: Linear Scan -> Skill-Bucketed Pools
Approach A: One global queue, scan for a group (the naive instinct)
Keep all waiting players in one list. To form a match, scan for N players whose skills are within some delta and who share a region.
pool = [ticket, ticket, ...] # every waiting player, one list
for each new/oldest ticket t:
candidates = [c for c in pool
if abs(c.rating - t.rating) < DELTA
and c.region == t.region
and mode == t.mode]
if len(candidates) >= N: form match
Where it breaks: the scan is O(pool size) per matching attempt, and the pool is 10M. To form 10K matches/sec you would scan 10M players 10K times/sec, which is 10^11 comparisons/sec. It is dead on arrival. Worse, it is a single global lock point: one list that every match formation contends on, so you cannot parallelize the matcher without everyone fighting over the same structure. And it mixes NA with EU players who can never match, wasting every comparison that crosses a region boundary.
Approach B: Partition by (region, mode), bucket by skill
Two moves. First, partition the pool by (region, mode): an NA 5v5 player and an EU deathmatch player are in completely separate pools and are never compared. This immediately shrinks each pool from 10M to the size of one region+mode slice, and lets each pool be owned by an independent matcher (no global lock).
Second, within a pool, bucket by skill. Slice the rating range into bands (0-800, 800-1200, 1200-1600, …). A player at 1350 lives in the 1200-1600 bucket. To find a match, the matcher looks only at that bucket (and neighbors when widening), not the whole pool.
Pool = (region=NA, mode=5v5)
skill buckets (each an ordered structure, e.g. a sorted set by rating):
[ 0- 800] -> {p_a:410, p_b:680, ... }
[ 800-1200] -> {p_c:900, p_d:1150, ... }
[1200-1600] -> {p_e:1350, p_f:1590, ... } <- player at 1350 lives here
[1600-2000] -> {...}
[2000+ ] -> {... (sparse, the elite tail)}
To match a 1350 player: gather from [1200-1600] first.
If not enough within tight skill delta, expand to touch [800-1200]
and [1600-2000] (the neighboring buckets). Never scan [0-800] or [2000+].
Now a matching pass touches ~one bucket of maybe a few thousand tickets, not 10M. Storing each bucket as a sorted set keyed by exact rating means “give me players within +/- 50 of 1350” is a range query (ZRANGEBYSCORE), O(log n + k) for k results, not a scan. The matcher can pull a tight skill-window instantly and only widen when the window is too sparse.
Bucket sizing against skill skew. Ratings follow a bell curve: most players cluster in the middle bands, few at the extremes. Equal-width buckets create a giant, hot mid-skill bucket and near-empty tail buckets. Size buckets by population (narrow bands where players are dense, wide bands in the sparse tail) so no single bucket is a hotspot and the elite tail still has enough neighbors to form a match. This is the same range-vs-hash tension as any ordered partitioning: you keep the order (which makes skill-neighborhood queries cheap) and pay for it with adaptive boundary balancing.
Approach C: Continuous batch matcher, not per-ticket greedy
Instead of trying to match each ticket the instant it arrives (greedy, which produces poor pairings because few candidates have accumulated yet), the matcher runs a short batch cycle (say every 1-2 seconds per pool). Each cycle it takes the current set of waiting tickets in a skill neighborhood and solves a small local assignment: pick the best group of N among the candidates present, prioritizing the longest-waiting tickets. Batching gives the matcher a richer candidate set to choose from, so matches are higher quality, at the cost of up to ~1-2s of extra latency, which is well inside the 30s budget. This is the leaderboard “batch to amortize” idea applied to matching: a slightly delayed decision over many candidates beats an instant decision over few.
2. The Expanding Search Window (bounded wait vs quality)
The core tension: a tight skill/latency window gives great matches but can leave a player waiting (few candidates that close), and a loose window matches fast but produces stomps and laggy games. The resolution is to make the window a function of how long the ticket has waited.
Approach A: Fixed window (naive)
Accept only candidates within a fixed +/- 50 ELO and < 50ms ping. Simple, but a top-500 grandmaster or an off-peak player in a thin region has almost nobody within +/- 50, so they wait forever (starvation) - violating the “everyone matches under 30s” NFR. A fixed window cannot serve both a packed mid-skill pool and a sparse elite tail.
Approach B: Time-widened window
Each ticket carries an acceptance window that grows with wait time. The longer you have waited, the more skill difference and higher ping you will tolerate, because a slightly worse match now beats a perfect match never.
elapsed = now - ticket.enqueued_at
skill_window(elapsed):
base 50 ELO, +25 ELO per 5 seconds waited, capped at ~400 ELO
0s : +/- 50 (tight, ideal)
5s : +/- 75
15s : +/- 125
30s : +/- 400 (wide - take almost anyone near your band)
latency_window(elapsed):
base 50ms, +10ms per 5s waited, capped at ~120ms
30s : up to 120ms (playable, if not ideal)
region relaxation:
after ~20s with no match, allow ADJACENT regions
(NA-East may accept NA-West; EU-West may accept EU-North)
Two tickets match only if both of their current windows accept each other (mutual acceptance), so a fresh 1400 with a +/-50 window will not be dragged into a match with a 1700 unless the 1400’s window has also widened enough to accept 1700. As tickets age, their windows overlap more, so a match becomes increasingly likely, and the oldest ticket is guaranteed to eventually find someone because its window keeps growing toward “anyone in a compatible region.” This is the anti-starvation guarantee: monotonically widening windows mean bounded wait.
Prioritize the oldest. Within a pool, the matcher processes waiting tickets oldest-first (a priority by enqueued_at). This ensures the player closest to the 30s cliff gets first pick of the current candidate pool, keeping p99 wait under budget. A ticket approaching the deadline can even be given an escalating priority so it is matched preferentially in the next cycle.
matcher cycle (per pool, every ~1-2s):
waiting = tickets sorted by enqueued_at ASC # oldest first
for t in waiting (oldest first):
if t already claimed this cycle: skip
win = current windows(t) # widened by t's age
cands = pool.range(t.rating - win.skill, t.rating + win.skill)
filtered by mutual-window accept + latency compat
if enough candidates for N: form group, claim, propose
else: leave t for next cycle (its window is wider then)
Approach C: Latency as a first-class constraint, not an afterthought
Region alone is too coarse: two NA players can still have 120ms between them if one is in Miami and one in Seattle. So each ticket carries a latency vector: measured ping to each nearby datacenter (the client pings a handful of DCs at queue time). A group is only viable if there exists a common datacenter where all N players’ ping is under the current latency window. The matcher, having chosen candidate skills, checks: is there a DC that serves all of them acceptably? This also decides where the game server is allocated (the DC minimizing max ping). Under the widening scheme, the acceptable ping ceiling rises with wait time, and after enough waiting, adjacent regions/DCs open up. Latency is not “same region == fine”; it is “there exists a server location good for everyone,” which is what actually determines whether the game feels responsive.
3. Balancing Two Teams
Having chosen 10 players, we must split them into two teams of 5 so the match is fair. “Individually similar skill” is not enough; the team totals must be close.
Approach A: Random or alternating split (naive)
Shuffle the 10 and deal 5 to each side, or snake-draft by rating. Random can produce lopsided sides by luck; snake-draft is better but not optimal, and both ignore that the goal is minimizing the difference between the two teams’ summed skill.
Approach B: Minimize team-skill difference (partition problem)
This is the balanced partition problem: split N players into two sets of size N/2 minimizing |sum(teamA) - sum(teamB)|. For N=10 this is tiny - there are only C(10,5)/2 = 126 ways to split 10 into two labeled-then-halved teams, so the matcher can enumerate all splits and pick the one with the smallest skill-sum gap. It is a brute force that is trivially fast at N=10.
players = [r1..r10] # ratings of the chosen group
best = None
for each subset A of size 5 (C(10,5)=252, /2 for symmetry = 126):
B = the other 5
gap = abs(sum(A) - sum(B))
best = min(best, gap)
choose the split with smallest gap
# optionally add a secondary objective: also balance role/lane coverage
For larger N (say a 50-player mode), full enumeration is too big, so use a greedy + local-swap heuristic: sort by rating, snake-draft into two teams, then repeatedly swap the pair of players (one from each team) that most reduces the gap until no swap helps. This lands within a percent or two of optimal in a handful of passes. For the common 5v5/6v6 case, exact enumeration is simplest and fast.
Party constraint. Pre-made parties must stay on the same team. So team balancing is constrained: parties are atomic units placed whole. A party of 3 goes entirely to one side, and the balancer fills the rest around that constraint. This can occasionally make a perfectly balanced split impossible, in which case the matcher either accepts a slightly wider team gap or, if too wide, rejects the group and re-gathers - another quality-vs-wait trade the widening window governs (a longer-waiting party gets more slack).
Approach C: Match by party-adjusted skill up front
Rather than gather 10 individuals and then discover the parties do not balance, feed party structure into the gathering step. Treat a party as a single composite candidate with a combined rating (and a size), and gather groups whose party structure can be balanced (e.g. avoid putting two 3-parties in a 5v5 where they cannot split evenly). This pushes the constraint upstream so the balancer almost always finds a good split, instead of gathering, failing to balance, and re-queuing.
4. Exclusivity: Never Double-Book a Player
The pool is sharded and matchers run in parallel; the deadliest bug is two matchers both grabbing the same player for two different matches, or the expanding window reaching into a neighbor bucket that another matcher owns. A player in two lobbies at once is the cardinal sin (NFR: exactly one match).
Approach A: Hope it does not happen / soft delete (naive)
Matcher reads candidates, forms a group, and marks them matched. Where it breaks: between the read and the mark, another matcher (or the same one, next cycle) can read the same ticket and also claim it. Classic read-modify-write race. Under 10K matches/sec across parallel matchers, this happens constantly, and you get players yanked into two games or a lobby that starts with 9 players because one was stolen.
Approach B: Atomic claim with compare-and-set
Each ticket has a state (WAITING -> CLAIMED -> MATCHED, or back to WAITING on failure). Claiming a group is an atomic conditional transition: flip all N tickets from WAITING to CLAIMED only if all are currently WAITING. In Redis this is a single Lua script (atomic, server-side) that checks all N and sets them, or a small transaction; the all-or-nothing check is what prevents partial claims.
CLAIM(ticket_ids[]): # atomic Lua script on the pool shard
for id in ticket_ids:
if state[id] != WAITING: return FAIL # someone already took one
for id in ticket_ids:
state[id] = CLAIMED
return OK
# If FAIL: release nothing (we set nothing), matcher retries with a
# fresh candidate set next cycle. If OK: proceed to propose the match.
Because the check-and-set is atomic and server-side, no two matchers can both claim overlapping players: the second one’s CLAIM sees a non-WAITING ticket and fails cleanly. On failure the matcher simply re-gathers next cycle - the lost candidate is cheap.
Keep matchers from fighting: partition ownership. Even better than racing-then-failing is not racing. Assign each (region, mode, skill-band) pool to a single owning matcher (via a leader election / consistent-hash assignment). That matcher is the only writer for its pool, so within a pool there is no contention at all. The atomic claim then only matters at the boundaries where an expanding window reaches into a neighbor band owned by a different matcher. Cross-boundary grabs go through the atomic CLAIM; intra-pool matching is single-writer and race-free. This is the “shard so most work is uncontended, use locks only at the seams” pattern.
Approach C: Reservation with timeout for the accept phase
A claim is not the end - players still have to accept. So CLAIMED is a reservation with a TTL: if all N accept within, say, 10 seconds, tickets go MATCHED and are consumed. If someone declines or times out, their ticket is discarded (or penalized) and the accepted players’ tickets revert to WAITING with a priority boost (they already waited, do not punish them). The TTL guarantees a crashed matcher or a stuck accept cannot freeze players in CLAIMED forever - the reservation expires and they return to the pool automatically. This makes the whole claim-accept flow self-healing: any failure path leads back to WAITING within a bounded time, so no ticket is ever lost or stuck.
API Design & Data Schema
Player-facing API (the control plane)
POST /v1/queue
{ "player_id":"p_4a1", "mode":"5v5_ranked",
"party_id":"pty_77" | null,
"latency":[{"dc":"nae","ms":22},{"dc":"naw","ms":58},{"dc":"eu","ms":140}] }
202 Accepted
{ "ticket_id":"tkt_9f2", "status":"WAITING", "ws":"wss://mm.gg/t/tkt_9f2" }
-- rating is looked up server-side from the ratings service, not trusted
-- from the client. Client opens the returned WebSocket for results.
DELETE /v1/queue/{ticket_id} # cancel / dequeue
200 OK { "ticket_id":"tkt_9f2", "status":"CANCELLED" }
GET /v1/queue/{ticket_id} # fallback status poll (WS is primary)
200 OK
{ "ticket_id":"tkt_9f2", "status":"WAITING", "waited_ms":8200,
"est_wait_ms":6000, "current_skill_window":125 }
POST /v1/match/{match_id}/accept # accept the found match
{ "player_id":"p_4a1" }
200 OK { "match_id":"m_31c", "status":"WAITING_FOR_OTHERS" }
Push events over the WebSocket (server -> client), not polled:
{ "event":"MATCH_FOUND", "match_id":"m_31c", "accept_deadline_ms":10000 }
{ "event":"MATCH_READY", "match_id":"m_31c",
"server":{ "dc":"nae", "host":"10.2.4.9:7777", "token":"..." } }
{ "event":"MATCH_CANCELLED", "reason":"peer_declined", "requeued":true }
Internal matcher / allocation API
# Matcher -> Allocation, once a balanced group is claimed
POST /internal/match/propose
{ "group":[ "tkt_9f2","tkt_1c7", ... 10 ids ],
"teams":{ "A":["p_a","p_b",...], "B":["p_c","p_d",...] },
"dc":"nae", "mode":"5v5_ranked" }
200 OK { "match_id":"m_31c", "server":{...} } # server reserved
Data model: pool (fast, transient) + ticket store (durable state)
Ticket / pool - Redis (in-memory, sharded by (region, mode), skill-bucketed):
Pool key per bucket:
pool:{region}:{mode}:{skill_band} e.g. pool:nae:5v5:1200_1600
Type: ZSET (sorted set), member = ticket_id, score = exact_rating
-> ZRANGEBYSCORE for "players within +/- window of my rating": O(log n + k)
Ticket detail (hash), source of ticket state:
ticket:{ticket_id}
player_id STRING
rating INT
region STRING
mode STRING
party_id STRING | null
latency JSON # [{dc,ms}, ...] measured at queue time
state ENUM # WAITING | CLAIMED | MATCHED | CANCELLED
enqueued_at INT # epoch ms, drives oldest-first + window widening
claimed_at INT # for CLAIMED TTL / reservation expiry
Replication: >=1 replica per shard (async) + AOF for crash recovery.
TTL safety: CLAIMED reservations auto-expire back to WAITING after ~10s.
Why Redis / in-memory and not SQL for the pool: the access pattern is “insert a ticket, range-scan a skill neighborhood, atomically flip N tickets’ state, all at 100K+ ops/sec with millisecond latency.” A sorted set gives the O(log n) skill-range query; a Lua script gives the atomic multi-ticket claim; and the data is transient (seconds of life, ~2 GB total), so durability needs are modest and served by replication + AOF, not a disk-first relational store. A B-tree SELECT ... WHERE rating BETWEEN ... FOR UPDATE across 100K/sec would drown in lock contention and disk IO.
Match records - Postgres (durable, low volume):
match
match_id UUID PK
mode TEXT
dc TEXT
team_a JSONB # player ids
team_b JSONB
team_a_skill INT # summed/avg rating, for post-hoc quality audit
team_b_skill INT
created_at TIMESTAMP
status TEXT # PROPOSED | READY | STARTED | ABORTED
INDEX (created_at), INDEX (mode, created_at)
-- match rate is tens of thousands/sec of SHORT-lived proposals but the
-- durable record is written once per started match; volume is fine for SQL.
Match records are relatively low volume (one row per started match), long-lived, and want relational querying for analytics (match quality over time, wait-time distributions), so SQL fits. The pool wants speed and atomicity, so Redis fits. Different jobs, different stores.
Bottlenecks & Scaling
Where it breaks first, in order, and the fix for each:
1. The matcher scan (breaks first). A single global queue scanned per match is O(10M) per attempt and cannot form 10K matches/sec. Fix: partition by (region, mode) and bucket by skill, storing each bucket as a sorted set. A matching pass touches one small bucket via an O(log n) range query, not the whole pool. This is the move that makes matchmaking tractable at all.
2. Match throughput vs arrival rate. If forming lags arrival, queue depth and wait time grow unboundedly past 30s.
Fix: run many independent matchers, one per (region, mode, skill-band) shard, each an uncontended single writer. Popular buckets get more shards (sub-partition a hot mid-skill band). Throughput scales horizontally with shard count.
3. Starvation of rare ratings / thin pools. A grandmaster or an off-peak player has nobody in a tight window and would wait forever. Fix: the time-widening acceptance window - skill/latency tolerance grows with wait time, region relaxes after ~20s, and matchers process oldest-first with escalating priority near the 30s cliff. Guarantees bounded wait at the cost of looser late matches.
4. Double-booking a player (correctness, not throughput). Parallel matchers race to claim the same ticket, especially at bucket boundaries. Fix: single-writer ownership per pool so intra-pool matching is race-free, plus an atomic compare-and-set CLAIM (Lua script) for the boundary grabs where an expanding window crosses into a neighbor bucket. All-or-nothing claim; failed claims retry next cycle.
5. Stuck reservations / matcher crash mid-claim. A CLAIMED ticket whose matcher dies could freeze a player out of the pool. Fix: CLAIMED is a TTL reservation - it auto-reverts to WAITING after ~10s. Any accept-phase failure (decline, timeout, crash) returns accepted players to the pool with a priority boost. The flow is self-healing; no ticket is lost.
6. Poll storm. 10M waiting clients polling status is ~5M QPS of pure overhead. Fix: push over WebSocket/SSE - notify on state change instead of being polled. A poll endpoint stays as a degraded fallback only.
7. Hot bucket skew. Ratings cluster in the middle, so the mid-skill bucket is a giant hotspot while the tail buckets are near-empty. Fix: population-sized buckets (narrow where dense, wide where sparse) and sub-shard the hottest buckets across multiple matchers, partitioning that band by a secondary key (e.g. sub-region) so no single matcher eats the whole hot band.
8. Ticket loss on node failure. Tickets live in memory; a Redis node dying could strand queued players on a dead spinner. Fix: replicate each pool shard (async replica + AOF) so a node loss fails over without losing tickets; clients also hold a WS that re-issues the ticket on reconnect if needed. The Ticket Store is the state of record for a ticket’s lifecycle.
9. Cross-region / global coordination. A single global matcher across continents is both slow and pointless (cross-continent play is unplayable). Fix: keep matchers region-local and independent; only relax to adjacent regions late in the wait window. There is no global matcher - region is a natural, hard partition that also happens to be the right latency boundary.
10. Game server supply. Even a perfect group cannot play if no game server is free in their DC. Fix: the Allocation Service maintains a warm pool of pre-provisioned servers per DC and autoscales on queue-depth signals; if a DC is momentarily dry, the widening latency window lets the group fall back to a neighboring DC rather than block.
Wrap-Up
The trade-offs that define this design:
- Partition to make it tractable. A 10M-player pool is unsearchable in 30s, so we split it into thousands of small
(region, mode, skill-band)pools, each independently and cheaply searchable, with cross-pool work only at the seams. This single choice turns an impossible scan into a set of trivial ones. - Widening window over fixed window. We make skill, latency, and region tolerances grow with wait time, trading match quality for a hard bound on wait time. A tight match now-or-never becomes a slightly looser match guaranteed inside 30s, which is what “no player waits forever” actually requires.
- Batch matcher over greedy. We run a short (1-2s) batch cycle over accumulated candidates rather than matching each ticket on arrival, spending a little latency to get a richer candidate set and higher-quality groups and balanced teams.
- Single-writer shards plus atomic claim over global locking. Most matching is race-free because each pool has one owner; we pay the cost of an atomic compare-and-set only at bucket boundaries, so exclusivity (“exactly one match per player”) holds without a global lock choking throughput.
- Fast transient pool over durable database for matching. The pool is an in-memory, sharded, replicated Redis structure tuned for skill-range queries and atomic claims; the durable match record lives in SQL. Speed and atomicity where the hot path needs it, durability and queryability where the record needs it.
One-line summary: shard the waiting pool by region+mode and bucket it by skill so each small pool is searchable in milliseconds, run per-shard single-writer batch matchers with a wait-time-widening acceptance window and oldest-first priority, balance two teams by brute-force partition, and guarantee one-match-per-player with an atomic TTL-reservation claim - trading a little match quality late in the queue for a hard sub-30-second match time across 10M concurrent players.
Comments