Design a game matchmaking system

01The design, in the six-step framework

1. Requirements and use cases

Two reports shape this one. An L4 candidate solved chess-style matchmaking by keeping waiting players in a TreeSet and using ceiling and floor to find the closest rating. A SWE II candidate was asked about player queues, skill matching and efficient room assignment. So the core is an ordered structure, and the rest is time and concurrency around it.

• A player joins the queue with a rating and is matched with the waiting player of the closest rating, if within a tolerance.
• A player cancels before being matched.
• The tolerance widens the longer a player waits, trading fairness for speed.
• A player who waits too long times out and is removed and told so.
• A matched pair is assigned a game room, the lowest free room id; a room returns to the pool when the game ends.

Out of scope: team matches, regional routing, rating updates after a game. Constraints: join, cancel and closest lookup are O(log n) on an ordered structure; thousands of joins per second arrive on many threads, so matching state needs one clear lock; the time source is injected, so widening and timeout are testable without sleeping; the matching rule is swappable.

2. Core entities and relationships

• Ticket: an immutable record of a player's request: id, player, rating, joined-at time.
• WaitingPool: tickets ordered by rating, with closest-neighbour lookup and removal.
• MatchPolicy: decides the allowed gap for a ticket at a given time.
• Match: two tickets paired.
• RoomPool: free room ids in a heap.
• Matchmaker: the API; it holds the lock, a heap of expiry times, and a queue of matches for the workers that start games.

The matchmaker composes the pool and the rooms, and aggregates the policy, which is configuration. Tickets are only aggregated by the pool: a ticket outlives its time in the pool as part of a Match.

3. Interfaces and key methods

import bisect, heapq, itertools, queue, threading
from dataclasses import dataclass
from typing import Callable, Optional, Protocol

@dataclass(frozen=True)
class Ticket:
    id: str
    player: str
    rating: int
    joined_at: float
    seq: int            # arrival order: breaks rating ties

@dataclass
class Match:
    a: Ticket
    b: Ticket
    room: Optional[int] = None

class MatchPolicy(Protocol):
    def allowed_gap(self, ticket: Ticket, now: float) -> int:
        """The largest rating difference this ticket accepts right now."""

class Matchmaker:
    def join(self, player: str, rating: int) -> Ticket:
        """Match immediately if a close enough opponent waits, else enqueue."""
    def cancel(self, ticket_id: str) -> bool:
        """False if the ticket was already matched or removed."""
    def tick(self) -> list:
        """Periodic: re-try matches as tolerances widen; returns tickets that timed out."""
    def start_next(self, timeout: Optional[float] = None) -> Match:
        """Worker call: block for the next match and assign it a room."""

Invariants: a ticket is in the pool or in exactly one match, never both; entries stays sorted by (rating, seq); a stale expiry for a matched ticket is harmless, because it is checked against by_id; each room id is held by at most one match.

4. Design patterns and the choices behind them

An ordered pool for closest rating

The force: the closest opponent lies next to you in rating order. In Java a TreeSet gives that with floor and ceiling; here a sorted list with bisect does it, with O(log n) search and O(n) insert, and a balanced tree or a sorted-list library closes that gap. Only two candidates need checking: the neighbour on each side. A heap would be wrong, since it finds an extreme rather than a neighbour, which is a useful thing to say when reasoning about priority queues in design.

Heaps where they do fit, with lazy deletion

Expiries are a heap keyed by deadline. When a ticket matches or cancels, removing it from the heap would be O(n), so the entry stays and is ignored when it reaches the top. RoomPool is a min-heap of free ids, giving the lowest room in O(log r).

Widening as a strategy

The force: games differ in how much they value fairness over speed. MatchPolicy.allowed_gap is a strategy: a fixed gap, a linear widening, or a step function. Both players must accept the gap, so a newcomer with a tight tolerance does not get a bad match just because the other has waited for minutes. That two-sided check is a detail worth stating.

Producer-consumer for starting games

The force: joins must be quick, while starting a game (reserving a room, notifying clients) may be slow. join only pairs tickets under the lock and puts the match on a queue; worker threads take from it and assign rooms. That is the producer-consumer pattern. The queue is the only shared structure outside the lock, and it is thread-safe by construction. start_next blocks and returns one match, which matches what a worker wants; the API stays four methods wide.

5. Core flow and code

1. join creates a Ticket, then takes the lock.
2. It asks the pool for the closest waiting ticket and checks the gap against both tickets' allowed gap.
3. If acceptable, it removes the opponent and queues a Match; otherwise it adds the new ticket to the pool and pushes its deadline.
4. tick runs every second or so: it pops expired tickets, then re-tries the waiting tickets, since tolerances have widened.
5. A worker calls start_next, which takes a match and acquires a room.

class WaitingPool:
    def __init__(self) -> None:
        self.entries: list = []        # sorted (rating, seq, ticket id)
        self.by_id: dict = {}

    def __len__(self) -> int:
        return len(self.by_id)

    @staticmethod
    def _key(t: Ticket) -> tuple:
        return (t.rating, t.seq, t.id)

    def add(self, ticket: Ticket) -> None:
        bisect.insort(self.entries, self._key(ticket))
        self.by_id[ticket.id] = ticket

    def remove(self, ticket: Ticket) -> None:
        del self.entries[bisect.bisect_left(self.entries, self._key(ticket))]
        del self.by_id[ticket.id]

    def closest(self, ticket: Ticket) -> Optional[Ticket]:
        i = bisect.bisect_left(self.entries, self._key(ticket))
        candidates = []
        for j in (i - 1, i, i + 1):
            if 0 <= j < len(self.entries) and self.entries[j][2] != ticket.id:
                candidates.append(self.by_id[self.entries[j][2]])
        if not candidates:
            return None
        return min(candidates, key=lambda t: (abs(t.rating - ticket.rating), t.seq))

    def tickets(self) -> list:
        return sorted(self.by_id.values(), key=lambda t: t.seq)

class FixedGap:
    def __init__(self, gap: int) -> None:
        self.gap = gap
    def allowed_gap(self, ticket: Ticket, now: float) -> int:
        return self.gap

class WideningPolicy:
    def __init__(self, base: int = 50, per_second: int = 10, maximum: int = 400) -> None:
        self.base, self.per_second, self.maximum = base, per_second, maximum
    def allowed_gap(self, ticket: Ticket, now: float) -> int:
        return min(self.maximum, int(self.base + self.per_second * (now - ticket.joined_at)))

class RoomPool:
    def __init__(self, count: int) -> None:
        self.free = list(range(count))
        heapq.heapify(self.free)
        self._lock = threading.Lock()
    def acquire(self) -> Optional[int]:
        with self._lock:
            return heapq.heappop(self.free) if self.free else None
    def release(self, room_id: int) -> None:
        with self._lock:
            heapq.heappush(self.free, room_id)

class Matchmaker:
    def __init__(self, policy: MatchPolicy, rooms: int, clock: Callable[[], float], max_wait: float = 120) -> None:
        self.policy, self.clock, self.max_wait = policy, clock, max_wait
        self.pool = WaitingPool()
        self.rooms = RoomPool(rooms)
        self.expiries: list = []                 # (deadline, ticket id)
        self.matches: "queue.Queue[Match]" = queue.Queue()
        self._lock = threading.Lock()
        self._seq = itertools.count(1)

    def _acceptable(self, a: Ticket, b: Ticket, now: float) -> bool:
        gap = abs(a.rating - b.rating)
        return gap <= self.policy.allowed_gap(a, now) and gap <= self.policy.allowed_gap(b, now)

    def _try_match(self, ticket: Ticket, now: float) -> bool:
        other = self.pool.closest(ticket)
        if other is None or not self._acceptable(ticket, other, now):
            return False
        self.pool.remove(other)
        if ticket.id in self.pool.by_id:
            self.pool.remove(ticket)
        self.matches.put(Match(other, ticket))
        return True

    def join(self, player: str, rating: int) -> Ticket:
        now = self.clock()
        with self._lock:
            seq = next(self._seq)
            ticket = Ticket(f"t{seq}", player, rating, now, seq)
            if not self._try_match(ticket, now):
                self.pool.add(ticket)
                heapq.heappush(self.expiries, (now + self.max_wait, ticket.id))
            return ticket

    def cancel(self, ticket_id: str) -> bool:
        with self._lock:
            ticket = self.pool.by_id.get(ticket_id)
            if ticket is None:
                return False
            self.pool.remove(ticket)
            return True

    def tick(self) -> list:
        now = self.clock()
        expired = []
        with self._lock:
            while self.expiries and self.expiries[0][0] <= now:
                _, tid = heapq.heappop(self.expiries)
                ticket = self.pool.by_id.get(tid)     # lazy deletion: gone means already matched
                if ticket is not None:
                    self.pool.remove(ticket)
                    expired.append(ticket)
            for ticket in self.pool.tickets():
                if ticket.id in self.pool.by_id:
                    self._try_match(ticket, now)
        return expired

    def start_next(self, timeout: Optional[float] = None) -> Match:
        match = self.matches.get(timeout=timeout)
        match.room = self.rooms.acquire()
        return match

if __name__ == "__main__":
    t = [0.0]
    mm = Matchmaker(WideningPolicy(50, 10, 400), rooms=2, clock=lambda: t[0], max_wait=30)
    a = mm.join("ann", 1500)
    b = mm.join("bo", 1700)
    assert len(mm.pool) == 2                 # 200 apart: too far for now
    c = mm.join("cy", 1530)
    m = mm.start_next(timeout=1)
    assert {m.a.player, m.b.player} == {"ann", "cy"} and m.room == 0
    t[0] = 16.0                              # bo's tolerance has widened, but nobody else waits
    assert mm.tick() == [] and mm.cancel(b.id)
    assert not mm.cancel(a.id)               # ann was already matched

6. Extensions, concurrency and what interviewers probe

• "Why not a heap or a hash map?" The query is nearest in order, so an ordered structure is the right fit. Buckets by rating band are a good alternative at scale: O(1) insert, with a search through neighbouring bands.
• "No rooms are free." acquire returns None, so the worker holds the match and waits on a condition, or the pool blocks using a semaphore. Object pools cover the pattern.
• "Thread safety." One lock guards the pool and expiries. Holding it through slow work would be the bug, which is why room assignment happens outside, in start_next. See locks and mutexes.
• "Team games or parties." A ticket becomes a group with a size and average rating, and the pool matches until a team is full; MatchPolicy stays as it is.
• Test first: with an injected clock, cover a gap that is refused now and accepted later, a cancelled player never matching, and expiry of a stale ticket doing nothing.
• Common mistake: checking only the next higher neighbour, and applying the widened tolerance of one player while ignoring the other's.

02Where this question was reported

• LeetCode Discuss · Online game (e.g. chess) matchmaking; waiting players in a TreeSet, ceiling()/floor() to find closest rating
• Taro · Player queues, skill matching, efficient room assignment