Move validation in LLD - System Design Exercise

Design: Move Validation System

Design the core move validation logic and system architecture. Exclude UI design and player matchmaking.

Functional Requirements

FR1: Validate moves in a turn-based board game (e.g., chess, checkers).

FR2: Ensure moves follow game rules before applying them.

FR3: Support multiple game types with different move rules.

FR4: Provide immediate feedback if a move is invalid.

FR5: Allow undoing moves only if they were valid and last move.

FR6: Support concurrent games for multiple players.

FR7: Log moves for replay and audit.

Non-Functional Requirements

NFR1: Handle up to 10,000 concurrent games.

NFR2: Validate moves with p99 latency under 100ms.

NFR3: System availability of 99.9%.

NFR4: Support extensibility for new game rules without downtime.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

❓ Question 7

Key Components

Game state storage (in-memory or database)

Move validation engine (rule checker)

API layer for receiving moves

Cache for fast state access

Logging and audit service

Undo management component

Design Patterns

Command pattern for moves

Strategy pattern for different game rules

Event sourcing for move history

Cache aside pattern for game state

CQRS for separating read/write operations

Reference Architecture

Client
  |
  v
API Gateway
  |
  v
Move Validation Service <--> Game State Cache <--> Persistent Storage
  |
  v
Logging Service

Undo Service <--> Move Validation Service

Rule Engine (plug-in modules) <--> Move Validation Service

Components

API Gateway

REST/HTTP

Receive move requests from clients and route to validation service

Move Validation Service

Microservice (e.g., Node.js, Python)

Validate moves using game rules and current game state

Game State Cache

Redis or in-memory store

Store current board state for fast access during validation

Persistent Storage

Relational DB (PostgreSQL) or NoSQL

Store game states, move history, and audit logs

Logging Service

Kafka or centralized logging

Record all moves and validation results for replay and audit

Undo Service

Microservice

Manage undo requests and validate undo conditions

Rule Engine

Modular plug-in system

Encapsulate game-specific move validation logic

Request Flow

1. Client sends move request to API Gateway.

2. API Gateway forwards move to Move Validation Service.

3. Move Validation Service fetches current game state from Game State Cache.

4. Move Validation Service calls Rule Engine module for the specific game to validate the move.

5. If valid, Move Validation Service updates Game State Cache and Persistent Storage with new move.

6. Move Validation Service sends success response to client.

7. Move Validation Service sends move details to Logging Service.

8. If undo requested, Undo Service checks last move validity and updates state accordingly.

Database Schema

Entities: - Game: game_id (PK), game_type, current_state, status - Move: move_id (PK), game_id (FK), player_id, move_data, timestamp, valid_flag - Player: player_id (PK), name - UndoLog: undo_id (PK), game_id (FK), move_id (FK), timestamp Relationships: - Game 1:N Move - Player 1:N Move - Move 1:1 UndoLog (optional)

Scaling Discussion

Bottlenecks

Game State Cache saturation under high concurrent games.

Move Validation Service CPU load with complex rule checks.

Database write latency for move history logging.

Undo Service consistency under concurrent undo requests.

Solutions

Partition cache by game_id to distribute load and use sharding.

Scale Move Validation Service horizontally with stateless design.

Use asynchronous logging with batching to reduce DB write pressure.

Implement optimistic concurrency control and locking in Undo Service.

Interview Tips

Time: 10 minutes for requirements and clarifications, 15 minutes for architecture and components, 10 minutes for scaling and trade-offs, 10 minutes for Q&A.

Clarify game types and validation strictness early.

Explain modular rule engine for extensibility.

Describe caching strategy for low latency validation.

Discuss data consistency and undo handling.

Highlight scalability and fault tolerance approaches.