Design a Matchmaking System

• 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).

• 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.

• 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.

• 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.

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.
   1. Client requests to join a mode; in parallel it probes latency to candidate datacentres.
   2. API resolves the party and checks the player is not already queued or in a match.
   3. Queue manager stamps the ticket with ratings and creates it in memory and the journal.
   4. Client reports probe results; ticket gains a latency vector.
   5. Queue manager publishes ticket.queued and starts pushing wait estimates.
2. Matcher forms a match — A periodic solver over the in-memory queue: prioritise the longest waiters, find compatible tickets, balance teams, commit atomically.
   1. Every tick, the matcher takes a consistent snapshot of the queue for one region-mode.
   2. Matcher picks the longest-waiting eligible ticket as the seed and gathers candidates within its bands.
   3. Matcher fills two teams of five from candidates, respecting party sizes and balancing average rating.
   4. Matcher chooses the datacentre minimising the worst player's latency and emits a proposal.
   5. Queue manager commits the proposal: all tickets move queued → proposed atomically, or none do.
   6. Committed match is handed to the Accept coordinator; unmatched tickets widen their bands.
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.
   1. Accept coordinator notifies all players over their WebSockets and starts a 20 s timer.
   2. Players accept; the coordinator records each response in the journal.
   3. One player declines (or the timer expires with a missing accept).
   4. The other nine tickets return to the queue with their original join time.
   5. On full acceptance, the coordinator asks the allocator for a server.
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.
   1. Allocator reserves a warm instance in the chosen datacentre.
   2. If the datacentre has no idle instance, fall back to the next-best datacentre within everyone's latency limits, and signal the autoscaler.
   3. Allocator returns connection details; players are told to connect.
   4. Clients connect directly to the game server; the server confirms the roster.
   5. Tickets are completed and per-player locks released; events emitted for analytics.
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.
   1. Player cancels; the ticket is removed if still queued.
   2. A queued player's WebSocket drops.
   3. A queue manager instance crashes.
   4. Journal and memory disagree after failover (a cancel landed in memory but not the journal).
   5. Matcher crash mid-tick.

Ask: Every second of waiting buys a fairer match. How do you decide when to stop waiting?

Good answers name: Per-ticket band widening on a data-driven schedule, Fixed bands, wait as long as it takes, Fixed wait, take the best available match at the deadline, Global optimisation over the whole queue each tick.

Our pick: Per-ticket widening. Each ticket carries a rating band and a latency limit that grow with its wait time along a per-mode schedule; the matcher seeds from the longest waiter so widened bands are used first. A quality floor prevents absurd matches: predicted win probability must stay within a range, and max latency has a hard ceiling. Past a maximum wait the ticket becomes eligible for fallbacks (cross-region, or bots in casual modes). The tuning job recomputes schedules weekly from observed wait and quality distributions and publishes them to the queue managers. Expose the current band to the client so the wait estimate is explainable.

1. A top-0.01 % player queues at 3 am in Oceania. What happens minute by minute?
   Minute 0: band ±100, nobody in range. Minute 1: ±300, still nobody. Minute 2: ±600, a few players; a match forms if latency allows, with the top player carrying a team. Minute 3+: cross-region eligibility opens (higher latency accepted), or in casual modes bots fill. The player sees the band widening in the UI, which is more tolerable than a mystery wait.
2. How do you evaluate a new widening schedule without hurting players?
   Simulate first: replay a day of real queue joins through the matcher with the new schedule and compare wait and quality distributions. Then A/B by region-mode with a small share of tickets on the new schedule, since tickets in the same queue interact. Watch p90 wait, predicted win probability spread, and post-match sentiment.
3. Why seed from the longest waiter rather than trying to form the best match in the queue?
   Fairness and starvation: forming the best match repeatedly serves the dense middle of the rating distribution and lets outliers wait forever. Seeding from the longest waiter guarantees progress for everyone and, because their bands are widest, they are also the easiest to place. It is a greedy heuristic that works well in practice.
4. Should parties be matched against parties?
   Ideally yes, because a coordinated five-stack beats five solo players of equal rating. Model it as a rating bonus for party size and prefer matches with symmetric party structure, widening that preference over time like other bands. Many games also keep a separate solo-only queue.

Ask: Why is the queue a single in-memory process per region and mode, not a distributed database?

Good answers name: One in-memory queue manager per region-mode, journaled to Redis, warm standby, Queue in a distributed database, stateless matchers, Shard the queue by rating bracket, Redis sorted set as the queue with matcher reading it directly.

Our pick: A queue manager process per region-mode holding tickets in memory with a rating-sorted index, plus a warm standby. Every state change is written to the Redis journal before being acknowledged, so the journal is authoritative and memory is a fast replica of it. Atomic commits of proposals run as a Lua script against the journal so the CAS on ten tickets is one round trip. The matcher runs in the same process or as a sidecar receiving snapshots. If a region-mode ever outgrows a process, split by sub-region first (which preserves latency locality) before considering rating shards.

1. What is the exact invariant that prevents a player being in two matches?
   A ticket has exactly one state, transitions are CAS operations, and a proposal commits only if every ticket is in queued. Plus one active ticket per player enforced by SET NX at join. Together: a player has at most one ticket, and a ticket is in at most one proposed or assigned match. Everything else (crashes, retries) reduces to these two checks.
2. Failover takes 5 seconds. What do players experience?
   Nothing visible for queued players: their wait timers continue because joined_at is in the journal, and the next tick after failover matches them. Players trying to join get a retry-after and the client retries silently. Proposed matches are unaffected because the accept coordinator is separate. The only cost is one or two missed ticks.
3. How do you split load if a region-mode has 2 M players in queue after a viral launch?
   First check whether it is really a queue problem or a server capacity problem; usually the latter. If the queue itself is the limit, split by sub-region (players probe latency anyway, so group by nearest datacentre), each with its own manager. Cross-sub-region matching becomes the fallback path. Do not shard by rating.

Ask: Skill fairness is visible in the score; latency fairness is felt every frame. How do you get everyone under 80 ms?

Good answers name: Client probes each candidate datacentre at join; matcher minimises max latency, GeoIP to nearest region, Historical latency per player from past matches.

Our pick: Probe at join to the 5–8 datacentres suggested by the region hint, 3 samples each, take the median. The ticket holds a latency vector and is eligible only once it arrives. The matcher requires a common datacentre under every ticket's current latency limit and picks the one minimising the maximum latency, with the average as tiebreaker. Limits widen with wait time like skill bands but with a hard ceiling. Re-probe if a ticket waits more than 60 s. Server-side, reject probe results inconsistent with the client's IP geography beyond a wide margin to blunt spoofing.

1. A player spoofs low latency to a datacentre to play with friends abroad. Consequence and defence?
   Consequence: they and their opponents get a laggy match. Defence: the game server measures real latency in the first seconds and reports it; players whose measured latency repeatedly contradicts their probes get their probe results discounted or replaced by server-measured history. Also cross-check against IP geolocation with a generous margin.
2. Two groups of five, each with great latency to a different datacentre, and 120 ms to each other's. Match them?
   Not under the normal limits. Either group waits for a better match, and if their bands widen past 120 ms they can be matched with the datacentre in between (if one exists) or at one side with the other side accepting the lag. In practice, the widening ceiling should be set where the game remains playable; beyond that, prefer waiting or bots.
3. How does the allocator handle a datacentre running out of servers at peak?
   The allocator holds an idle buffer per datacentre sized from recent formation rate, scales ahead of demand, and falls back to the next datacentre in each match's acceptable set when empty. The matcher can also be told a datacentre is full so it prefers others at formation time rather than at allocation time. Burst headroom is cheaper than angry players.

Ask: Acceptance adds 20 seconds to every match. Why have it, and how do you stop one player from ruining it for nine?

Good answers name: Server-timed acceptance with early void and priority-preserving requeue, No acceptance; start immediately, Acceptance before teams are revealed.

Our pick: Acceptance with a 20 s server-side deadline, nothing about the teams revealed until all accept. A decline or the deadline voids the match immediately; the coordinator moves the remaining tickets back to queued with their original join time via CAS, so they keep their widened bands and priority. The decliner's ticket is cancelled and a dodge counter increments with an escalating queue lock (5 min, 15 min, 60 min). Accepts are idempotent and journaled, so a coordinator restart mid-acceptance resumes from the journal. Show live "7/10 accepted" to make the wait legible.

1. The accept coordinator crashes with three matches mid-acceptance. What happens?
   Each match's state (proposed, deadline, accepts so far) is in the journal. A new coordinator instance scans for proposed matches, recomputes remaining time from the stored deadline, and continues. Clients keep their countdown. If the crash lasted past a deadline, those matches are voided on recovery with no penalty applied, because the timeout was the system's fault.
2. Is it fair to penalise a player whose network dropped during acceptance?
   The first offence penalty is small precisely because of this. Also give a reconnect grace: if the socket returns within the deadline and the player accepts, no penalty. Past that, the effect on the other nine is identical whether the cause was malice or Wi-Fi, so a small penalty is defensible; escalation targets repeat behaviour.
3. How would you detect players who dodge strategically after peeking at the match?
   In ranked nothing is revealed, so there is nothing to peek at. In modes that reveal information, correlate decline rate with the revealed attributes (e.g. always declining when a certain teammate appears) and treat statistically significant patterns as dodging for penalty purposes.

Ask: The matcher balances on a number. Where does it come from, how uncertain is it, and what does the matcher do with the uncertainty?

Good answers name: Mean plus uncertainty per player per mode, stamped on the ticket; conservative estimate for balance, Single Elo number, Rating read live during matching.

Our pick: TrueSkill-style mean and sigma per player per mode, stored in the player DB and cached. At join the queue manager stamps the ticket with both, and for parties computes an aggregate that weights the strongest member more than the mean (parties punch above their average). The matcher balances teams on a conservative estimate and applies a quality floor on predicted win probability. Sigma also feeds band widening: high-sigma tickets start with wider bands. After a match, the game server emits a result event keyed by match id; the rating service applies the update exactly once per match id and publishes new values. Provisional placement matches and a visible "calibrating" state manage new-player expectations.

1. A match result is reported twice, once by the server and once by a retry. What prevents a double rating update?
   The update is keyed by match id and recorded in a processed table before applying; the second report is a no-op. Rating updates are also computed from the pre-match snapshot stored with the match, not from current values, so order and duplication cannot compound.
2. How do you handle a player who leaves mid-match for rating purposes?
   Game rules decide the outcome, but the rating system needs a policy: typically the leaver takes a full loss and the remaining teammates take a reduced or zero rating change if the leave happened early. Encode the leaver flag in the result event so the rating service can apply the policy consistently.
3. Smurfs: a top player on a fresh account. What does the system do?
   High initial sigma plus a large rating step on early wins move them up in a handful of matches; conservative balancing limits their damage in the meantime. Beyond that, detection is a separate system: account age, hardware fingerprints, win rate and performance statistics far above rating. Matchmaking can consume a "suspected smurf" flag to place them higher immediately.