Design a scalable game matchmaking and waiting-queue system
You are designing the matchmaking system for a large real-time multiplayer game (think of a Roblox-style platform hosting many game experiences). Players — solo or as a party that must stay together — join a waiting queue and are matched into games under constraints such as team size, region/latency, and skill level. Once a viable match is found, the system runs a ready-check, allocates a game server, and hands the players the connection details so the game can start.
Walk through the end-to-end design: the overall architecture and data flow from Join Queue to Game Start, the data model, the matchmaking algorithm, how you balance match quality against wait time, how you handle timeouts/cancellations/retries, how constraints are enforced and relaxed, and how the system stays performant and reliable under high concurrency and peak spikes.
Constraints & Assumptions
-
Global player base
spread across multiple regions; players must be matched into a region with acceptable network latency.
-
Multiple game modes
with different team structures — e.g., 1v1, 3v3, 5v5 — running concurrently.
-
Parties
of players queue together and must never be split across a match.
-
Peak spikes
: arrival rate swings widely (e.g., game launch or evening prime time); the system must absorb large bursts without unbounded wait or data loss.
-
Targets
: low wait time (state a concrete p95 target, e.g. tens of seconds for common modes) balanced against high match quality (skill-balanced teams, acceptable latency).
-
Correctness floor
: a queued player is never silently lost, never matched into two games at once, and a crashed worker never strands a ticket forever.
-
You consume an MMR/skill rating and its uncertainty as
inputs
; computing/updating the rating after a match (Elo/Glicko/TrueSkill) is out of scope. Gameplay netcode is out of scope — you hand off at "server allocated + connection string returned."
Clarifying Questions to Ask
-
What is the priority order between
wait time
and
match quality
, and does it differ by mode (casual vs. ranked)?
-
What concrete scale should I design for — peak tickets/sec, number of regions, number of concurrent modes?
-
Are parties bounded in size, and can a party span players on different platforms or in different skill bands?
-
Is cross-region matching ever allowed, or are modes strictly region-locked?
-
Is there a hard maximum acceptable latency, and how is each player's latency to a region measured (client-reported vs. server-measured)?
-
What is the expected behavior on a ready-check decline or timeout — drop everyone, or requeue the acceptors?
Part 1 — Overall architecture and end-to-end flow
Lay out the major components and the data flow from Join Queue to Game Start. Identify which components are stateless vs. stateful, where the hot working set of queued players lives, and how a ticket moves through the system until the players receive connection info.
What This Part Should Cover
-
A clear component decomposition (gateway/ingress, ticket service, queue store, matchmaker workers, ready-check/orchestrator, server allocator, notifier, event bus) with which are stateless.
-
The request path from join to start, including how the client learns of a match (push vs. poll).
-
Where durable state lives vs. where the low-latency working set lives, and why.
-
An explicit ticket lifecycle / state machine threading through the components.
Part 2 — Data model, indexes, and storage choices
Define the core entities (ticket, party, match, reservation, server allocation), their required fields, the indexes/access patterns, and the storage technology for each. Pay particular attention to how you organize queued players so the matcher can efficiently find compatible candidates.
What This Part Should Cover
-
Entities with required fields and clear primary keys; party and reservation modeled explicitly.
-
A justified split between an ephemeral hot store (the live queue) and a durable store (recovery/audit/idempotency).
-
The key design decision of the bucket key and why skill stays out of it.
-
Secondary access patterns (party → tickets, bucket → tickets for rehydration, idempotency lookups).
Part 3 — Matchmaking algorithm
Describe the queueing model, candidate selection, scoring, and match formation. Cover both a simple case (1v1) and a team case (e.g., 5v5 with parties), and how a region with acceptable latency and server capacity is chosen. Show how a worker atomically claims candidates and proposes a match.
What This Part Should Cover
-
A candidate-organization model (aging priority so the oldest rise to the front) and how starvation is structurally prevented.
-
The time-based relaxation schedule as the explicit quality-vs-wait mechanism.
-
Concrete formation logic for both 1v1 and team modes, with parties kept atomic.
-
Region selection that treats server capacity and a latency ceiling as hard inputs.
-
An atomic claim/reserve/commit step that is safe under concurrent workers.
Part 4 — Fairness, low wait times, and the quality/latency tradeoff
Explain the policies and mechanisms that keep wait times low and fair while preserving match quality. Make explicit where the dial between match quality and latency lives and how you would tune it.
What This Part Should Cover
-
Concrete anti-starvation mechanisms tied to the priority/relaxation design.
-
Cross-bucket fairness so one popular mode doesn't monopolize a worker.
-
A clear statement that the relaxation schedule (its parameters and SLA threshold)
is
the quality-vs-latency dial, and how it would be tuned per mode.
Part 5 — Timeouts, cancellations, and retries
Design the ready-check flow, client heartbeats / liveness, cancellation, and requeue logic. Specify what happens on a ready-check decline or timeout, and how the system stays correct under retried client requests.
What This Part Should Cover
-
Heartbeat/TTL liveness and how a disconnected client's ticket is cleaned up.
-
A ready-check flow with a deadline and explicit decline/timeout handling that preserves acceptor age.
-
Idempotent cancel and idempotent mutating requests so retries are safe.
-
Reservation TTL as the self-healing recovery primitive.
Part 6 — Constraint enforcement and relaxation
For each constraint — team size, region/latency, skill level, and parties — specify whether it is hard or soft, how it is enforced, and (for soft constraints) how it is relaxed over time. Note any constraint that must never be trusted from the client.
What This Part Should Cover
-
A per-constraint classification (hard vs. soft) with the enforcement mechanism for each.
-
The relaxation rule for each soft constraint, tied to ticket age.
-
The non-negotiables (party atomicity, latency ceiling, ban/exclusion lists) that never relax.
-
Server-side latency measurement / anti-spoofing.
Part 7 — High concurrency, sharding, and hot-spot mitigation
Describe the sharding strategy, how workers are assigned, and how you mitigate hot spots (e.g., one very popular mode+region at peak). Address how a party always lands on one shard and how correctness is preserved when you must parallelize a single hot bucket.
What This Part Should Cover
-
A sharding scheme aligned to the bucket key, with party→shard assignment that keeps a party intact.
-
One-active-worker-per-shard (leader election) and why the steady state is lock-free.
-
Hot-spot mitigation (sub-sharding, top-K sampling, admission control/backpressure) and an explicit statement of where correctness comes from when single-ownership is relaxed.
Part 8 — Reliability: idempotency, failure recovery, backpressure, observability
Cover how the system stays correct and available under failure: idempotency guarantees, recovery from a worker/region failure, backpressure/overload behavior, and the observability needed to operate and tune it.
What This Part Should Cover
-
The exactly-one-match guarantee (idempotency keys + the Queued-only-reservable invariant + reservation nonce).
-
Failure recovery: worker death, region failure, and rebuilding the hot store from the durable store + event log.
-
Backpressure / load-shedding behavior under overload and circuit breakers on downstream dependencies.
-
A concrete observability plan: per-bucket wait-time SLIs, match-quality distribution, ready-check accept rate, allocation success, queue length/age, plus tracing across the full flow.
What a Strong Answer Covers
Across all parts, a strong answer treats this as one coherent system rather than eight disconnected essays: the bucket key chosen in Part 2 is the same key that drives sharding in Part 7; the time-based relaxation schedule is recognized as the single dial that ties together the algorithm (Part 3), fairness (Part 4), and constraint relaxation (Part 6); and the atomic reservation + Queued-only-reservable invariant is the one primitive that simultaneously delivers no-double-match (Part 3), self-healing retries (Part 5), hot-bucket correctness (Part 7), and exactly-one-match reliability (Part 8). The candidate should ground decisions in rough numbers (e.g., Little's Law to show the queue is small and the real hardness is concurrency + the commit/allocation pipeline, not storage), state hard vs. soft constraints crisply, and name explicit tradeoffs (quality vs. wait, single-owner simplicity vs. globally optimal matches) rather than presenting the design as free of compromise.
Follow-up Questions
-
How would you backfill a near-complete match (e.g., bots or lower-priority candidates) when wait time exceeds a threshold, and what are the risks?
-
A region's server fleet is saturated at peak — what does the matcher do, and how does that interact with the relaxation schedule and admission control?
-
How would you A/B test a change to the relaxation weights (
α
, the SLA threshold, the scoring weights) safely in production, and what metrics decide success?
-
A subset of players is "decline-sniping" (declining ready-checks to dodge specific opponents) — how do you detect and discourage it without punishing honest declines?