Move validation in LLD - Scalability & System Analysis

Scalability Analysis - Move validation

Growth Table: Move Validation System

Users	Requests per Second (RPS)	Validation Complexity	Latency Requirements	Storage Needs
100 users	~50 RPS	Simple synchronous validation	Low latency (~100ms)	Minimal, mostly in-memory
10,000 users	~5,000 RPS	Moderate complexity, caching possible	Low latency (~50-100ms)	Moderate, some persistent logs
1,000,000 users	~500,000 RPS	High complexity, distributed validation	Very low latency (~20-50ms)	High, distributed storage and caching
100,000,000 users	~50,000,000 RPS	Very high complexity, sharded and cached	Ultra low latency (~10-20ms)	Very high, multi-region storage and caching

First Bottleneck

The first bottleneck is the validation logic CPU and memory on the application servers. As user count and requests grow, the synchronous move validation consumes significant CPU cycles and memory, causing increased latency and request queuing.

At medium scale, the database or state store that holds game state for validation also becomes a bottleneck due to high read/write operations.

Scaling Solutions

• Horizontal scaling: Add more application servers behind a load balancer to distribute validation requests.
• Caching: Cache frequently accessed game state to reduce database hits during validation.
• Asynchronous validation: For less critical moves, validate asynchronously to reduce latency impact.
• Sharding: Partition game state by user or game session to distribute load across multiple databases.
• Use of in-memory data stores: Employ Redis or similar for fast state access during validation.
• Optimize validation logic: Simplify or precompute rules to reduce CPU usage.

Back-of-Envelope Cost Analysis

• At 10,000 users (~5,000 RPS), assuming each validation request is ~1KB, bandwidth needed is ~5MB/s.
• Database must handle ~5,000 QPS, near upper limit for a single instance; requires read replicas or caching.
• Application servers: each handles ~2,000 concurrent connections; need ~3 servers minimum.
• Storage: logs and game state grow with users; estimate ~10GB/day at 10K users, scaling linearly.

Interview Tip

Start by defining the scale and requirements clearly. Identify the critical path for move validation and its latency needs. Discuss bottlenecks in CPU, memory, and database. Propose scaling solutions step-by-step, justifying each with the bottleneck it addresses. Mention trade-offs like consistency vs latency. Use real numbers to show understanding.

Self Check

Your database handles 1000 QPS. Traffic grows 10x to 10,000 QPS. What do you do first?

Answer: Add read replicas and implement caching to reduce direct database load before scaling vertically or sharding.

Key Result

Move validation systems first hit CPU and memory limits on app servers as user requests grow; scaling requires horizontal app servers, caching, and database sharding.

Practice

1. What is the primary purpose of move validation in a system design context?

easy

A. To create user interfaces

B. To speed up the system by skipping checks

C. To store user data securely

D. To ensure changes follow rules and prevent invalid actions

Solution

1. Step 1: Understand move validation role

   Move validation checks if a requested change or move follows system rules.

2. Step 2: Identify its main goal

   The goal is to prevent invalid or harmful actions that could break system logic or data.

3. Final Answer:

   To ensure changes follow rules and prevent invalid actions -> Option D

4. Quick Check:

   Move validation = Prevent invalid moves [OK]

Hint: Move validation means checking rules before allowing changes [OK]

Common Mistakes:

• Confusing validation with data storage
• Thinking validation speeds up by skipping checks
• Mixing validation with UI creation

2. Which of the following is a correct basic check in move validation logic?

easy

A. if move.position = max_position:
return True

B. if move.position == 'any':
return True

C. if move.position < 0 or move.position > max_position:
return False

D. if move.position > max_position then return False

Solution

1. Step 1: Check syntax correctness

   if move.position < 0 or move.position > max_position: return False uses proper comparison operators and syntax for boundary check.

2. Step 2: Identify errors in other options

   if move.position == 'any': return True uses string instead of number, C uses assignment (=) instead of comparison (==), D uses invalid syntax 'then'.

3. Final Answer:

   if move.position < 0 or move.position > max_position: return False -> Option C

4. Quick Check:

   Boundary check uses < and > with proper syntax [OK]

Hint: Use proper comparison operators and syntax for validation checks [OK]

Common Mistakes:

• Using assignment '=' instead of comparison '=='
• Using invalid keywords like 'then'
• Checking position against wrong data types

3. Given the code snippet for move validation, what will be the output if move.position = 5 and max_position = 4?

def validate_move(move, max_position):
    if move.position < 0 or move.position > max_position:
        return False
    return True

print(validate_move(move, max_position))

medium

A. True

B. False

C. Error

D. null

Solution

1. Step 1: Evaluate condition with given values

   move.position = 5, max_position = 4, so 5 > 4 is true.

2. Step 2: Determine return value

   Since condition is true, function returns False.

3. Final Answer:

   False -> Option B

4. Quick Check:

   5 > 4 triggers False return [OK]

Hint: Check boundary conditions carefully to predict output [OK]

Common Mistakes:

• Assuming 5 <= 4 is true
• Confusing return values
• Ignoring condition logic

4. Identify the bug in this move validation function:

def validate_move(move, max_position):
    if move.position <= 0 or move.position >= max_position:
        return False
    return True

medium

A. It incorrectly disallows move.position = 0

B. It allows move.position = max_position which should be invalid

C. It uses wrong comparison operators for boundaries

D. It returns true for all positions

Solution

1. Step 1: Analyze boundary conditions

   Condition disallows move.position <= 0, so position 0 is invalid.

2. Step 2: Check if position 0 should be allowed

   Usually position 0 is valid boundary, so disallowing it is a bug.

3. Final Answer:

   It incorrectly disallows move.position = 0 -> Option A

4. Quick Check:

   Check boundary inclusiveness carefully [OK]

Hint: Check if boundary conditions exclude valid edge values [OK]

Common Mistakes:

• Confusing < and <= in conditions
• Assuming 0 is always invalid
• Ignoring inclusive vs exclusive boundaries

5. In a system where moves must be validated for both boundary and occupancy, which design approach best ensures scalability and maintainability?

hard

A. Use separate modular validators for boundary and occupancy checks, composed in sequence

B. Combine all validation logic in a single monolithic function

C. Skip occupancy checks to improve performance

D. Validate moves only after applying them to the system state

Solution

1. Step 1: Consider modular design benefits

   Separating boundary and occupancy checks into modules improves clarity and reusability.

2. Step 2: Evaluate scalability and maintainability

   Modular validators can be updated independently and composed flexibly, aiding scalability.

3. Final Answer:

   Use separate modular validators for boundary and occupancy checks, composed in sequence -> Option A

4. Quick Check:

   Modular design = scalable and maintainable [OK]

Hint: Modular validation improves system scalability and clarity [OK]

Common Mistakes:

• Combining all logic makes code hard to maintain
• Skipping important checks reduces reliability
• Validating after applying moves risks inconsistent state