System requirements

Functional

1. User Sign Ups and details
2. Matching based on players rank and preferences
3. Real Time Game Engine for validating moves
4. Broadcasting The game for high rank players

Non-Functional:

1. Highly Scalable
2. Available
3. Low Latency Game
4. Different Sessions to handle simultaneous games

Capacity estimation

1. How many users connect at a time? Let us assume 1M DAU(Daily Active Users) Active users/ min = 1M/(24*60) = 900 users/ min Let us assume that, on average, a game lasts for 5 mins. Then we can assume a load of 5000 connected users. In place of any event/ peak we can consider this value equal to 20K connected users.

2. Capacity to be computed by matching engine If we assume each request to have size 1KB, we can have total memory to be 20K * 1KB = 20MB We are using a Balanced BST to find O(logN) matches. That's 20K*log(20K) = 300K instructions

API design

1. User Sign-Up:
   • Endpoint: /user/signUp
   • Method: POST
   • Request Body:
   • { "username": "XYZ", "password": "Encrypted Text"}
   • Response:
     • 200 OK if successful
     • Error message in case of failure (e.g., username already taken).
2. User Login:
   • Endpoint: /user/login
   • Method: POST
   • Request Body:
   • { "username": "XYZ", "password": "Encrypted Text"}
   • Response:
   • { "token": "Auth_Token", "expiresAt": "Expiration Time"}
   • Note: The token returned should be used for authenticating further requests.
3. Game Play Request:
   • Endpoint: /game/playRequest
   • Method: POST
   • Request Body:
   • { "type": "Type of Game", "color": "Blue", "preferences": { "time": "Max Time Limit", "maxRating": "opponent's rating", "minRating": "opponent's rating" }}
   • Response:
     • Match found with opponent's details or queue status update.
4. Move Validation:
   • Endpoint: /game/moveValidate
   • Method: POST
   • Request Body:
   • { "pieceType": "Pawn", "currentPosition": "e2", "newPosition": "e4"}
   • Response:
   • { "validate": "ok"}
   • Note: This endpoint confirms a move's validity according to the chess rules.

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

High-level design

High-Level Design Architecture:

1. Gateway:
   • The entry point for incoming API requests. The Gateway delegator routes requests based on their nature (auth, game move, etc.). It maintains a Connection Registry through a caching layer to track which server is handling which user's connection for efficient routing of real-time communications.
2. Connection Registry:
   • Utilizes caching (like Redis) to maintain a map of active user connections to the respective game servers. This enables quick lookup and routing for session management and cross-server communication.
3. User Service:
   • Manages user authentication, registration, and profile management.
4. Matching Service:
   • Pairs users for games based on rank and preferences. Provides the connection information to both the game server and update Gateway of new game establishments.
5. Game Engine:
   • Handles the primary game logic, ensuring move validation and rule enforcement, and updates game state accordingly.
6. Analytics Engine:
   • Collects and analyzes data to understand user behavior, performance metrics, and helps make informed decisions for improvements.

Request flows

A. User Service - Flow

1. Sign-Up Request:
   • Triggered by either direct user input of username and password or through a third-party authentication call.
2. Direct Signup Process:
   • Processes signups directly with username and password.
   • User information is saved to the User Database.
3. Third-Party Auth Provider:
   • Engages with external identity providers (like Google, Facebook, etc.) to authenticate users.
   • Upon successful authentication, moves on to the profile management step.
4. Check Existing Profile (Profile Check):
5. The system checks if a profile already exists for the user.
   • If no, proceed to create a new profile with additional details (username, avatar, location, gender details, etc.).
6. Create New Profile/Link Third-Party Profile:
   • For new users, generate additional profile details like avatar and store in the User Database.
   • If a profile exists, link the third-party account with the existing user record and update information as necessary.
7. Return Success:
   • Confirmation response to the user indicating a successful sign-up or linkage.

B. Matching Service - Flow

1. User Match Request:
   • Users submit a request for a game match, including their preferences such as opponent rating range, game type, etc.
2. Store in DB and Elasticsearch:
   • The request details are stored in a Match Details Database for persistence.
   • Indexed into Elasticsearch to facilitate search operations and number crunching more rapidly, which might be useful for analytics or complex queries.
3. Store in Cache:
   • Utilize a Redis Sorted Set to hold these preferences, keyed by time or other relevance criteria, to quickly match incoming requests with available opponents.
4. Check for Matches:
   • First, query the Cache for any existing match that fits the preferences.
   • Store results based on conditions such as timestamps, which help prioritize older or more suitable match requests.
5. Match Found? (Decision Point):
   • Yes:
     • A suitable match is located in the cache.
     • Return that match to the user and notify the Game Engine to initiate the game.
   • No:
     • Persist the request in both the Database and Cache until a matching request arrives.
     • Employ a timeout or periodic cleaner to ensure the cache is up-to-date and does not carry stale requests.
6. Notify Game Engine:
   • When a match is found, inform the Game Engine to establish the game session and proceed with move handling and real-time interactions.

Note : Concurrency Management:

• • To handle possible conflicts when two users match with the same criteria simultaneously, perhaps leveraging optimistic locking or unique request identifiers.

C. Game Engine - Flow

1. Match Found:
   • Once a match is established between two players, proceed with setting up the game connection.
2. Upgrade to WebSockets:
   • If applicable and supported by the client, transition to WebSocket connections for efficient bidirectional communication.
3. Establish WebSocket Connection:
   • This ensures low-latency and real-time data handling during active games.
4. Game Event Queue:
   • Manages incoming and outgoing game events through WebSockets.
5. Move Validation:
   • Once a move request is received, validate it against current game rules and state.
6. Update Game State:
   • If valid, update the game state stored in cache and apply the Write-Behind strategy to periodically synchronize these changes with the database.
7. Latency Handling:
   • For timing user moves, calculate network latency and adjust the clock accordingly to provide a fair experience. Each player's move may have different network delays.
8. Update Clients:
   • Sending the updated game state to both players involved, ensuring their view remains consistent.
9. Sharding for Cache Management:
   • Use sharding techniques based on user geographical location or rank, optimizing cache memory and ensuring efficient storage and retrieval of game states.
10. Cache Strategy:
    • Employ efficient caching (e.g., Redis) with sharded storage to manage transient game states.
11. Write-Behind Cache:
    • Periodic writes to the database ensure that in the event of a failure, the latest game state can be recovered without significant data loss.
12. Move Rejection:
    • If a move is invalid, notify the player appropriately, ensuring the client interface reflects this status.

Detailed component design

Already covered in flows

Trade offs/Tech choices

Can we avoid the connection between client and server?

1. We can’t do that because we use the game engine to validate moves.

2. The client code or requests may be compromised. Hence it cannot be used as a source of truth.

3. To validate the move, we store the state of the game and check if it's legal on the server

Failure scenarios/bottlenecks

1. Thundering Herd Problem:
   • Cause: When a server or service goes down and comes back up again, a large number of queued requests hit the system all at once, potentially overwhelming it.
   • Solution Strategies:
     • Rate Limiting & Backoff Strategies: Implement exponential backoff and retry mechanisms to spread out the request load over time.
     • Staggered Start: Randomize restart times for services/nodes to avoid simultaneous spikes.
     • Circuit Breakers: Use to prevent requests to services that are currently overloaded; allow them to recover before gradually reintroducing load.
2. Cache Preheating:
   • Cause: If a cache server goes down and is restarted, the system might face a performance hit as frequently accessed data is not immediately available.
   • Solution Strategies:
     • Warm Cache with Historical Data: Preload frequently accessed data or the entire dataset known from previous usage patterns into the cache at startup.
     • Data Snapshotting: Regular snapshots of the cache can be stored and restored on restart to quickly repopulate the cache.
     • Asynchronous Lazy Loading: Allows the cache to populate gradually with the help of background fetchers to minimize immediate load impact.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?