Real-Time Matchmaking System

Skill-based matchmaking for online games

Design the service that puts players who are queuing for an online game into fair matches quickly: rate their skill, group players of similar skill and good ping, confirm everyone is ready, and hand the match to a game server.

Overview

Players press Play and expect a fair game within a minute. The matchmaker takes everyone waiting for a game mode, finds groups whose skills are close and whose ping to a common server is low, splits them into balanced teams, and hands each group to a game server.

Two things make this harder than a queue. First, skill is not known exactly: a new player's rating is a guess, and a good rating system says how unsure it is. Second, quality and wait time conflict. With few players at a given skill at 4 a.m., or for a top-ranked player at any hour, a perfect match may never appear, so the rules must loosen the longer someone waits.

The work itself is small. At the scale assumed here, about 20,000 people are searching at once across 40 pools, so each pool holds a few hundred tickets that fit in one process's memory. The interview is about the rules (rating, windows, teams, parties) and the correctness around them (no player in two matches, no match with a missing player).

Questions to ask first

Team size and modes? — 5 versus 5 ranked, plus four other modes
How many players? — 10 million a day; 20,000 searching at once at peak
How long may players wait? — Aim for 30 seconds; widen rules until a match forms
Regions? — 8; a match plays in one region
Parties? — Yes, 1 to 5 players queue together and stay on one team
What happens if someone does not accept? — The match is canceled; the others go back to the front of the queue

What you will be able to do

Explain Elo, Glicko and TrueSkill in one breath each, and why uncertainty matters.
Design a pool worker that forms matches on a timer with widening search windows.
Balance teams and fit parties without breaking them up.
Keep a player out of two matches, and recover when someone does not accept.
Size the system and say why the matching itself is cheap.

Key concepts

Matchmaking ticket
Pool per mode and region
Skill rating with uncertainty
Elo and Glicko
TrueSkill match quality
Widening search window
Party tickets
Ready check
Game server allocation

Functional requirements

Join the queue for a mode and region, alone or as a party; leave at any time
Form matches of similar skill and acceptable ping, widening the rules as players wait
Keep a party on one team; balance the two teams' total skill
Ask every player to accept; cancel and re-queue if someone does not
Allocate a game server in the chosen region and send its address to players
Update each player's rating from the match result
Show queue status and an estimated wait

Non-functional requirements

Median wait under 30 seconds at peak for most ratings (a target we chose)
A player is never in two matches at once
A lost pool worker delays matches for a few seconds; no ticket is lost
Rating updates apply once per match, even if the result is reported twice
Queue status reaches the client within about a second

Interview questions

How do you trade match quality against wait time?
Why not just use Elo?
How do you guarantee a player never ends up in two matches?
How do you handle parties?
How do you choose the game server?
What happens when a matchmaker worker crashes?
How do you estimate the wait shown to players?