Order tracking state machine in LLD - Scalability & System Analysis

Scalability Analysis - Order tracking state machine

Growth Table: Order Tracking State Machine

Users	Orders per Second	State Transitions per Second	Storage Size (Order States)	Latency Requirements
100	10	20	~10 MB	Low (seconds)
10,000	1,000	2,000	~1 GB	Medium (sub-second)
1,000,000	100,000	200,000	~100 GB	High (milliseconds)
100,000,000	10,000,000	20,000,000	~10 TB	Very High (milliseconds)

First Bottleneck

The first bottleneck is the database handling state transitions. As order states update frequently, the database must handle many writes and reads per second. At around 10,000 users, the database write throughput and latency become critical because each order state change requires a write and often a read to confirm the current state.

Scaling Solutions

• Database Scaling: Use write-optimized databases or NoSQL stores for fast state updates. Add read replicas to handle read-heavy queries.
• Caching: Cache current order states in memory (e.g., Redis) to reduce database reads.
• Horizontal Scaling: Add more application servers behind load balancers to handle increased state transition requests.
• Sharding: Partition orders by user ID or region to distribute database load.
• Event Sourcing: Use event logs to track state changes asynchronously, reducing direct database writes.
• CDN: Use CDN for static content but it has minimal impact on state machine scaling.

Back-of-Envelope Cost Analysis

• At 10,000 users: ~1,000 orders/sec, ~2,000 state transitions/sec.
• Database must handle ~2,000 writes/sec and ~3,000 reads/sec (including queries).
• Storage: Each order state record ~1 KB, so 1 million orders ~1 GB storage.
• Network bandwidth: Assuming 1 KB per state update, 2,000 updates/sec = ~2 MB/s bandwidth.
• At 1 million users: 100,000 orders/sec, 200,000 state transitions/sec, requiring distributed databases and caching.

Interview Tip

Start by explaining the order state machine and its transitions. Then discuss expected load and how it grows with users. Identify the database as the first bottleneck due to frequent writes. Propose caching and sharding to reduce load. Mention horizontal scaling of app servers. Always justify why each solution fits the bottleneck.

Self Check

Your database handles 1,000 QPS for order state updates. Traffic grows 10x to 10,000 QPS. What do you do first?

Answer: Add read replicas and implement caching to reduce direct database reads. Consider sharding the database to distribute write load. Also, horizontally scale application servers to handle increased requests.

Key Result

The database handling frequent order state updates is the first bottleneck; scaling requires caching, sharding, and horizontal scaling of app servers.

Practice

1. What is the main purpose of an Order Tracking State Machine in system design?

easy

A. To manage user authentication and sessions

B. To store customer payment information securely

C. To calculate the total price of an order

D. To represent the different stages an order goes through and control transitions

Solution

1. Step 1: Understand the role of state machines

   A state machine models states and transitions between them based on events.

2. Step 2: Apply to order tracking context

   In order tracking, it shows order stages like placed, shipped, delivered, and controls valid moves.

3. Final Answer:

   To represent the different stages an order goes through and control transitions -> Option D

4. Quick Check:

   State machine = stages and transitions [OK]

Hint: Think: states show progress steps, transitions move between them [OK]

Common Mistakes:

• Confusing state machine with data storage
• Mixing order calculation with state control
• Assuming it handles user login

2. Which of the following is the correct way to define a state transition in a state machine for order tracking?

easy

A. transition('delivered', 'placed', event='return_order')

B. transition('placed', 'shipped', event='ship_order')

C. transition('shipped', 'placed', event='cancel_order')

D. transition('cancelled', 'delivered', event='refund')

Solution

1. Step 1: Identify valid order flow transitions

   Orders move forward: placed -> shipped -> delivered; backward or invalid transitions are not typical.

2. Step 2: Check each option's direction and event

   transition('placed', 'shipped', event='ship_order') correctly moves from placed to shipped on ship_order event; others reverse or skip states incorrectly.

3. Final Answer:

   transition('placed', 'shipped', event='ship_order') -> Option B

4. Quick Check:

   Valid forward transition = transition('placed', 'shipped', event='ship_order') [OK]

Hint: Transitions should follow logical order flow forward [OK]

Common Mistakes:

• Defining backward transitions without valid reason
• Skipping intermediate states
• Using wrong event names

3. Given this simplified state machine code snippet:

state = 'placed'
event = 'ship_order'
if state == 'placed' and event == 'ship_order':
    state = 'shipped'
elif state == 'shipped' and event == 'deliver_order':
    state = 'delivered'
print(state)

What will be the output if event = 'deliver_order' when state = 'placed'?

medium

A. shipped

B. delivered

C. placed

D. error

Solution

1. Step 1: Check condition for event 'deliver_order' when state is 'placed'

   The first if checks for 'ship_order' event; it does not match 'deliver_order'. The elif checks for 'shipped' state, but current state is 'placed'.

2. Step 2: Determine state after conditions

   No condition matches, so state remains unchanged as 'placed'.

3. Final Answer:

   placed -> Option C

4. Quick Check:

   No matching transition keeps state same [OK]

Hint: If no condition matches, state stays unchanged [OK]

Common Mistakes:

• Assuming event triggers transition regardless of current state
• Confusing elif with else
• Expecting error without exception handling

4. Identify the bug in this order tracking state machine snippet:

state = 'shipped'
event = 'cancel_order'
if state == 'placed' and event == 'cancel_order':
    state = 'cancelled'
elif state == 'shipped' and event == 'cancel_order':
    print('Cannot cancel after shipping')
else:
    state = 'cancelled'
print(state)

medium

A. The else block cancels order even after shipping

B. Missing transition from 'placed' to 'shipped'

C. No print statement for cancellation confirmation

D. State variable is not updated correctly for 'placed' state

Solution

1. Step 1: Analyze conditions for state 'shipped' and event 'cancel_order'

   The if does not match. The elif matches, prints 'Cannot cancel after shipping' but leaves state unchanged. However, if event were different (e.g., 'deliver_order') with state='shipped', if and elif fail, else wrongly sets state='cancelled'.

2. Step 2: Identify why this is a bug

   The else acts as a catch-all, allowing cancellation of shipped orders for unhandled events, contradicting the intent to prevent cancellation after shipping.

3. Final Answer:

   The else block cancels order even after shipping -> Option A

4. Quick Check:

   Else wrongly cancels unhandled shipped cases [OK]

Hint: Else block can override specific conditions--check carefully [OK]

Common Mistakes:

• Ignoring else block effects
• Assuming print prevents state change
• Not testing all branches

5. You need to design an order tracking state machine that handles normal flow and exceptions like cancellation and returns. Which design approach best ensures scalability and clarity?

hard

A. Model states hierarchically with sub-states for exceptions and normal flow

B. Use a single flat state list with many transitions for all cases

C. Handle exceptions outside the state machine with separate logic

D. Use only two states: 'active' and 'closed' to simplify design

Solution

1. Step 1: Understand complexity of order states

   Orders have normal states (placed, shipped, delivered) and exceptions (cancelled, returned) which can be grouped logically.

2. Step 2: Evaluate design approaches for scalability and clarity

   Hierarchical states allow grouping related states, reducing complexity and improving maintainability compared to flat or oversimplified models.

3. Final Answer:

   Model states hierarchically with sub-states for exceptions and normal flow -> Option A

4. Quick Check:

   Hierarchical states = scalable and clear [OK]

Hint: Group related states hierarchically for clarity and scale [OK]

Common Mistakes:

• Using flat states causing many transitions
• Ignoring exceptions in state machine
• Oversimplifying states losing detail