Design DoorDash

Problem Statement

You've been asked to architect a matchmaking system for a popular online multiplayer game with millions of active players. The system needs to pair players together for matches based on skill level, geographical location, preferred game modes, and party composition. Players expect to find matches within seconds, and once matched, they need real-time communication about match status, lobby details, and game server assignments.

The system must handle peak loads of 500,000 concurrent users attempting to find matches, support various game modes (solo, duo, squad), and gracefully handle scenarios where players disconnect, decline matches, or experience network issues during the matchmaking process. The platform operates globally across multiple regions and must provide a fair, fast, and reliable experience that keeps players engaged.

Key Requirements

Functional

• Player queueing -- Allow players to enter matchmaking queues with specified preferences (game mode, region, skill tier)
• Skill-based matching -- Match players of similar skill levels using a rating system (ELO, MMR)
• Party support -- Enable groups of friends to queue together and find appropriate opponents
• Match confirmation -- Notify all matched players and handle accept/decline responses within a timeout window
• Game server assignment -- Allocate and communicate game server details to confirmed players
• Queue status updates -- Provide real-time feedback on queue position, estimated wait time, and match found notifications

Non-Functional

• Scalability -- Support 500,000+ concurrent matchmaking requests with ability to scale during peak hours
• Reliability -- Maintain 99.9% uptime with graceful degradation when components fail
• Latency -- Provide sub-second queue updates and match players within 30-60 seconds for 95% of requests
• Consistency -- Ensure no duplicate matchmaking, handle concurrent requests correctly, maintain accurate skill ratings

What Interviewers Focus On

Based on real interview experiences, these are the areas interviewers probe most deeply:

1. Matchmaking Algorithm Design

The core challenge is efficiently pairing players with compatible attributes from a massive pool while balancing match quality with wait time. Interviewers want to see how you handle the tradeoff between perfect skill matches and acceptable wait times.

Hints to consider:

• Consider bucket-based strategies that group players into skill tiers initially, then expand search radius over time
• Think about how to handle edge cases like high-skill players who have few potential matches
• Discuss data structures for fast lookups (priority queues, spatial indexes for region-based matching)
• Address how party matchmaking affects the complexity (matching a party of 3 with another party or solo players)

2. Real-Time State Management and Communication

Players expect instant feedback throughout the matchmaking journey. The system must broadcast state changes to connected clients efficiently and handle network failures gracefully.

Hints to consider:

• Evaluate WebSocket connections versus Server-Sent Events for maintaining live connections with players
• Design a message queue architecture for broadcasting match found notifications to all participants simultaneously
• Consider how to handle partial failures (some players receive notification, others don't)
• Think about heartbeat mechanisms to detect disconnected players still in queue

3. Race Conditions and Concurrent Matchmaking

Multiple matchmaking services may attempt to place the same player in different matches simultaneously, or players may cancel queue while a match is being formed.

Hints to consider:

• Use distributed locking or reservation systems to prevent double-matching
• Design an idempotent match confirmation flow with clear state transitions
• Consider eventual consistency tradeoffs when removing players from queues
• Think about how to handle clock skew across distributed services making concurrent decisions

4. Geographic Distribution and Latency Optimization

Players around the world need fair matchmaking, but network latency to game servers significantly impacts gameplay quality.

Hints to consider:

• Design a multi-region architecture where matchmaking happens regionally first
• Consider how to handle sparse regions with fewer players (cross-region matching with latency limits)
• Think about where to place matchmaking services relative to game servers and player populations
• Discuss CDN-like strategies for distributing game server capacity

Suggested Approach

Step 1: Clarify Requirements

Start by confirming the scope and constraints with your interviewer. Ask about the expected number of concurrent players, typical party sizes, how strict skill-based matching should be, and whether the system needs to support multiple game titles or just one. Clarify the acceptable matchmaking time before quality degrades, the typical match size (2 players, 10 players, 100 players), and whether features like role selection or preferred playstyle matter. Understand if the game servers are managed by this system or external, and what happens when a player declines a match.

Step 2: High-Level Architecture

Sketch the main components: API Gateway for client connections, Matchmaking Service (likely multiple instances per region), Queue Management with skill-based buckets, Match Formation Service that runs the pairing algorithm, Notification Service for real-time updates, Game Server Allocation Service, and supporting datastores for player profiles and match history. Show the flow from a player clicking "Find Match" through queue entry, matching, confirmation, and game server assignment. Indicate which components need to be stateful versus stateless and where you'll need caching layers.

Step 3: Deep Dive on Matchmaking Algorithm

Walk through your matching logic in detail. Describe a bucketing system where players are initially grouped by skill tier and region. Explain how a background process continuously scans buckets looking for compatible groups, using a scoring function that considers skill difference, wait time, and party composition. Discuss how buckets gradually expand their search criteria (relaxing skill requirements) the longer players wait, ensuring everyone eventually finds a match. Address the data structures (priority queues sorted by wait time within each bucket) and how to efficiently remove players who cancel. Show the match formation transaction where players are temporarily locked, notified, and must confirm within a timeout window.

Step 4: Address Secondary Concerns

Discuss scalability strategies like horizontal scaling of matchmaking workers with partitioning by region and skill tier. Explain how you'll use Redis or similar for fast queue operations and session state. Cover failure scenarios: if a matchmaking service crashes, players in its queues should be redistributed to healthy instances. Address monitoring with metrics on average wait time, match quality scores, and queue depths. Talk about optimizations like pre-warming game servers in anticipation of matches, and using machine learning to predict wait times more accurately based on time of day and current queue composition.