Design a Matchmaking Service With Join, Cancel, Matching, Notification and Expiry
Company: Waymo
Role: Software Engineer
Category: System Design
Difficulty: medium
Interview Round: Onsite
Design a matchmaking service for an online game. The service must support:
- joining the matchmaking queue;
- cancelling a matchmaking request;
- matching two compatible players;
- notifying both players when a match is found;
- handling disconnects and expired requests.
```hint One player, one match
Think about the moment two matchers, or a match and a cancel, act on the same waiting player at the same time.
```
```hint The queue is not one queue
Before scaling anything, ask which players could ever be matched with each other at all.
```
### Clarifying Questions
- What makes two players compatible: skill rating within some range, the same game mode, the same region or latency class, something else?
- How many players are searching at the same time, and how many join per second at peak?
- How long may a player wait? Should the compatibility requirement relax as the wait grows?
- Is a match always exactly two players, or could parties or larger matches come later?
- How do clients receive the notification: an open connection to the service, push notifications, or polling?
- How long can a request stay in the queue before it expires, and what does the player see when it does?
### What a Strong Answer Covers
- The API for join, cancel and match notification, with idempotent request identifiers
- A request state machine (waiting, matched, cancelled, expired) and who may move a request between states
- Partitioning of the waiting pool by compatibility so that matching stays fast at scale
- Atomic matching: a player is never placed in two matches, and a cancelled player is never matched
- Reliable notification of both players, including what happens if one of them is gone
- Disconnect detection with heartbeats or leases, and expiration of stale requests
- Wait time versus match quality, and the metrics that show whether the balance is right
### Follow-up Questions
- Players now queue as parties of different sizes and matches need two equal teams. What changes in the matcher?
- One compatibility bucket (a popular mode at peak time) becomes much hotter than the rest. How do you scale it?
- A player is notified of a match but never confirms. How do you return the other player to the queue without losing their place?
- How would you detect and prevent players manipulating matchmaking, for example by repeatedly cancelling to pick opponents?
Overview: Design a matchmaking service that lets players join and cancel requests, pairs compatible players, notifies both, and handles disconnects and expired requests. Tests request state machines, atomic matching, partitioned waiting pools and reliable notification.