Design a Matchmaking System

Group online game players into fair, low-latency matches within seconds, at millions of concurrent players.

Difficulty: medium. Patterns: queues, scheduling, latency, gaming. Reported at Riot Games, Epic Games, Electronic Arts, Activision, Discord.

Study shows every answer; Practice hides them until you have produced your own.

Functional requirements

• Player joins a queue for a game mode. Solo or as a pre-made party of 2–5. Queue per mode and region.
• Form matches of N players (e.g. 5v5). Balanced by skill, acceptable network latency for everyone, party constraints respected.
• Show estimated wait time and let the player cancel. Cancel must be immediate and must not leave a ghost in the queue.
• Assign the match to a game server. Pick a server region that minimises the worst player latency; hand the players connection details.
• Match acceptance. All players confirm within 20 s; decliners are penalised, the rest return to the queue at their previous priority.
• Update skill ratings after the match. Elo / TrueSkill style rating update from the match result.
• Out of scope. The game server itself, anti-cheat, the rating algorithm's math, and social features (friends, chat).

Non-functional requirements

• Scale (5 M concurrent players · 200 k in queue at peak). A queue is small relative to total players, but it churns fast: the whole queue turns over every ~30 s.
• Match time (median < 30 s · p90 < 90 s). The product metric. Traded off directly against match quality.
• Match quality (skill spread within a band · latency < 80 ms for all). Bands widen the longer someone waits. Quality is measured post hoc by win probability closeness and player-reported experience.
• Fairness (no starvation). A rare-skill player (very high or very low rating) must still get a match, with relaxed constraints, within a bounded time.
• Consistency (a player is in at most one match). Double-assignment is the cardinal sin: a player cannot be placed in two matches or lost between them.
• Availability (99.95 %). A matchmaking outage means nobody can play. Degrade by relaxing quality before refusing service.
• Regional. Queues are per region for latency; cross-region only as a last resort for tiny populations.

Back-of-envelope estimates

• Queue joins per second: ~7 k avg · 20 k peak. Average match lasts ~20 min; 5 M concurrent players ÷ 1 200 s ≈ 4 k players finishing/s who mostly re-queue, plus new sessions. Budget ~7 k/s average, ~20 k/s at peak or after a patch.
• Players in queue: ~200 k peak. 7 k joins/s × ~30 s average wait ≈ 200 k in queue by Little's law. Small enough to hold entirely in memory per region and mode.
• Matches formed per second: ~700 avg · 2 k peak. 7 k players/s ÷ 10 per match = 700 matches/s. Each match needs a game server slot, so server provisioning must keep up with this rate.
• Matcher work per tick: ~20 k candidates per region-mode. With ~10 regions × ~5 modes, a busy region-mode queue holds ~4–20 k players. A matcher tick every 1–2 s over 20 k players sorted by rating is trivial; the constraint solving for latency and parties is what costs.
• Game servers needed: ~50 k instances. 5 M concurrent players ÷ 10 per match = 500 k concurrent matches; each server host runs ~10 match instances → ~50 k hosts. Turnover of 700 matches/s means allocating a fresh instance every ~1.5 ms across the fleet.
• Latency probe traffic: ~50 k probes/s. On queue join the client pings ~5–8 candidate datacentres: 7 k × 7 ≈ 50 k small UDP probes/s. Negligible bandwidth, but the results must arrive before matching starts, so probing runs in parallel with the join.
• Queue state size: ~100 MB. 200 k players × ~500 B (id, rating, latency vector to ~10 DCs, party id, join time, constraints) = ~100 MB. Fits in one process per region-mode with room to spare; replication is for availability, not capacity.

Components

• Game client: Joins and cancels queues, measures latency to candidate datacentres with UDP probes, shows estimated wait, shows the accept dialog, and connects to the assigned game server.
• Matchmaking API (auth · WebSocket): Validates the player session and party, forwards join/cancel to the right regional queue, and holds a WebSocket per queued player for wait-time updates, match-found notifications, and accept/decline.
• Party service: Groups of friends queueing together. Provides the party roster, aggregate rating, and the requirement that all members land in the same match on the same team.
• Queue manager (per region × mode): Holds the in-memory set of waiting tickets for one region and mode. Accepts joins and cancels, tracks wait time, widens each ticket's acceptable skill and latency bands as it ages, and hands snapshots to the matcher. Replicated to a standby; ticket state is journaled to Redis.
• Matcher (periodic solver): Every 1–2 seconds, takes the queue snapshot and forms as many valid matches as it can: skill-balanced teams, all pairwise latencies acceptable, parties intact. Prioritises long-waiting tickets. Proposals are committed back to the queue manager atomically.
• Ticket journal (Redis · ticket id → state): Durable-enough record of every ticket and its state (queued, proposed, accepted, assigned, cancelled). The queue manager rebuilds its memory from here on failover. Also enforces "one active ticket per player" with a per-player key.
• Accept coordinator: For each proposed match, collects accept/decline from all players within 20 s. All accept → hand to allocation. Any decline or timeout → penalise the decliner, return the others to the queue with their wait time preserved.
• Server allocator (fleet manager): Maintains a pool of warm game server instances per datacentre. Given a match and its players' latency vectors, picks the datacentre minimising the worst latency, reserves an instance, and returns connection details. Scales the pool on queue depth.
• Game server fleet (dedicated servers): The actual game simulation hosts across datacentres. Report instance lifecycle (ready, in-match, finished) to the allocator, and match results to the rating service.
• Rating service (TrueSkill-style): Stores each player's skill estimate and uncertainty per mode. Updates from match results. Read on queue join to stamp the ticket; the matcher never calls it on the hot path.
• Player DB (Postgres / DynamoDB): Ratings, match history, penalties (dodge timers), and preferences. Keyed by player id.
• Event bus (Kafka): Ticket lifecycle events, match formed and match result events. Feeds analytics (wait time, quality), the rating service, and the allocator's autoscaler.
• Analytics & tuning: Computes wait-time and match-quality distributions per region, mode, and rating bracket. Produces the band-widening curves and wait-time estimates the queue manager uses.

User flows

1. Player joins a queue. A ticket is created with everything the matcher needs, latency is measured in parallel, and the player gets a wait estimate within a second.
2. Matcher forms a match. A periodic solver over the in-memory queue: prioritise the longest waiters, find compatible tickets, balance teams, commit atomically.
3. Match acceptance and a player declining. Ten players have 20 seconds to accept. Handling the decline correctly, without punishing the innocent nine, is where most real bugs live.
4. Allocate a game server and connect. Warm pools per datacentre, a reservation with a lease, and connection details pushed to players. Capacity is the thing that runs out.
5. Cancel, disconnect, and queue manager failover. The unglamorous paths that decide whether the system is trustworthy: leaving the queue cleanly, dropped clients, and a queue manager crash.

Deep dives

1. Match quality vs wait time. Every second of waiting buys a fairer match. How do you decide when to stop waiting?
2. Where the queue lives: in-memory per region-mode. Why is the queue a single in-memory process per region and mode, not a distributed database?
3. Latency: measuring it and choosing a datacentre. Skill fairness is visible in the score; latency fairness is felt every frame. How do you get everyone under 80 ms?
4. Why match acceptance exists and how to make it fair. Acceptance adds 20 seconds to every match. Why have it, and how do you stop one player from ruining it for nine?
5. Skill rating and the matcher. The matcher balances on a number. Where does it come from, how uncertain is it, and what does the matcher do with the uncertainty?