Katkat
Back

Design an online chess game with undo and leaderboard

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This problem tests the ability to design a low-latency, stateful system for a turn-based game, focusing on synchronization, undo history management, and scalable real-time leaderboard updates.

Design an Online Chess System

Design a backend architecture for a real-time, online chess platform that supports multiplayer matches, an "undo" move feature, and a global leaderboard. The system needs to support millions of concurrent users.

Functional Requirements

  1. Game Play: Players can join a match and make legal moves in real-time.
  2. Undo/Redo: Players can request to undo their last move, which the opponent must accept or decline.
  3. Leaderboard: A global ranking system based on Elo ratings that updates after every completed game.

Non-Functional Requirements

  1. Low Latency: Move validation and propagation should feel instantaneous to both players.
  2. Consistency: Game states must be strictly consistent for both players in a match.
  3. Reliability: In the event of a server crash, the game state should be recoverable.
  4. Scalability: The system must handle high traffic during peak hours (e.g., tournaments).

Scope of Answer

  • API Design: Define key endpoints or message types for moves and undo requests.
  • Data Modeling: Propose a schema for storing game history, player rankings, and current board state.
  • Architecture: Explain how you would handle real-time communication between players (e.g., WebSockets, pub/sub).
  • State Management: Describe the strategy for implementing undo functionality while maintaining move history and enforcing game rules.
  • Leaderboard: Explain how to update rankings efficiently without locking the entire leaderboard database.

Hints

Hint 1

Consider using an in-memory data store like Redis to hold active game states for low-latency access and fast board validation.

Hint 2

For the undo feature, represent the match as a stack of board states or a list of move deltas to allow for efficient reversal and re-validation.

Hint 3

Use a message queue or event streaming platform to decouple the completion of a game from the expensive operation of updating global leaderboard rankings.

Follow-up questions

  • How would you handle a player disconnecting in the middle of a game and reconnecting later?
  • If the leaderboard needs to show 'Top 100' players, how would you ensure the query performance remains constant as the number of users grows to millions?
  • How would you prevent 'cheating' where a client sends a malicious move packet to the server?