Why elevator design tests state machines in LLD - Scalability Evidence

Scalability Analysis - Why elevator design tests state machines

Growth Table: Elevator System Scaling

Users (People)	Elevator Requests per Minute	State Transitions per Second	System Complexity	Response Time Expectation
100	~10	~1	Simple: Few floors, few requests	Fast, near instant
10,000	~1,000	~100	Moderate: Multiple elevators, more floors	Still fast, some queuing
1,000,000	~100,000	~10,000	Complex: Many elevators, high concurrency	Needs optimized scheduling
100,000,000	~10,000,000	~1,000,000	Very complex: Large buildings, multiple zones	Requires distributed control

First Bottleneck: State Machine Complexity and Coordination

As the number of users and elevator requests grow, the elevator control system's state machine becomes the first bottleneck. This is because each elevator must track its current state (moving up, down, idle, door open/close) and respond to new requests correctly.

With many elevators and requests, the state machine logic and coordination between elevators become complex. Without efficient state management, the system can slow down, causing delays and incorrect behavior.

Scaling Solutions for Elevator State Machines

• Modular State Machines: Break down the elevator control into smaller, manageable state machines per elevator to reduce complexity.
• Hierarchical Control: Use a higher-level controller to coordinate multiple elevators, reducing state conflicts.
• Event-Driven Architecture: Use asynchronous events to handle state transitions efficiently.
• Load Balancing: Distribute requests evenly among elevators to avoid overloading one state machine.
• Simulation and Testing: Use automated tests to verify state transitions under heavy load.

Back-of-Envelope Cost Analysis

• At 1,000 requests per second, each elevator state machine must handle ~10-100 state transitions per second.
• CPU usage grows with the number of elevators and requests; a single server can handle ~1,000 concurrent state machines efficiently.
• Memory usage depends on storing states and queues; typically a few MBs per elevator.
• Network bandwidth is minimal as state machines mostly run locally; coordination messages are small.

Interview Tip: Structuring Scalability Discussion

Start by explaining what a state machine is and why elevators need them to track states.

Discuss how increasing users and requests increase state transitions and complexity.

Identify the first bottleneck as state machine coordination and complexity.

Propose clear scaling solutions like modular design, hierarchical control, and event-driven handling.

Use simple analogies like traffic lights or turnstiles to explain state machines.

Self Check Question

Your elevator control system handles 100 state transitions per second. Traffic grows 10x. What do you do first?

Answer: Break the monolithic state machine into smaller, modular state machines per elevator and introduce a higher-level coordinator to distribute requests. This reduces complexity and improves scalability.

Key Result

Elevator design tests state machines because as user requests grow, the complexity of managing elevator states and coordination becomes the first bottleneck. Modular and hierarchical state machine designs help scale efficiently.

Practice

1. Why is elevator design often used to test state machines in system design?

easy

A. Because elevators have clear states and transitions that model real-world behavior

B. Because elevators require complex database management

C. Because elevators use machine learning algorithms

D. Because elevators operate without any state changes

Solution

1. Step 1: Understand elevator operation basics

   Elevators move between floors and have states like moving up, moving down, idle, door open, and door closed.

2. Step 2: Connect elevator states to state machine concept

   State machines model systems with defined states and transitions, matching elevator behavior perfectly.

3. Final Answer:

   Because elevators have clear states and transitions that model real-world behavior -> Option A

4. Quick Check:

   Elevator states = clear states and transitions [OK]

Hint: Elevators have clear states and transitions [OK]

Common Mistakes:

• Thinking elevators don't have states
• Confusing state machines with databases
• Assuming elevators use AI for basic movement

2. Which of the following correctly represents a state transition in an elevator state machine?

easy

A. Idle -> Door Open -> Moving Up

B. Idle -> Moving Up -> Door Open

C. Door Open -> Moving Down -> Door Closed

D. Moving Up -> Door Closed -> Idle

Solution

1. Step 1: Identify valid elevator state order

   An elevator usually goes from Idle to Moving Up, then Door Open when it reaches the floor.

2. Step 2: Check each option's sequence

   Idle -> Moving Up -> Door Open correctly shows Idle -> Moving Up -> Door Open, a valid transition sequence.

3. Final Answer:

   <code>Idle -> Moving Up -> Door Open</code> -> Option B

4. Quick Check:

   Idle to Moving Up to Door Open = valid transition [OK]

Hint: Elevator moves before doors open [OK]

Common Mistakes:

• Opening doors before moving
• Closing doors while idle
• Skipping moving state

3. Given this simplified elevator state machine code snippet, what is the final state after these events: callElevator(), arriveFloor(), openDoor()?

states = ['Idle', 'Moving', 'DoorOpen']
current_state = 'Idle'

def callElevator():
    global current_state
    if current_state == 'Idle':
        current_state = 'Moving'

def arriveFloor():
    global current_state
    if current_state == 'Moving':
        current_state = 'DoorOpen'

def openDoor():
    global current_state
    if current_state == 'DoorOpen':
        current_state = 'Idle'

medium

A. Idle

B. Moving

C. DoorOpen

D. Error

Solution

1. Step 1: Trace callElevator()

   Starting at 'Idle', callElevator() changes state to 'Moving'.

2. Step 2: Trace arriveFloor() and openDoor()

   arriveFloor() changes 'Moving' to 'DoorOpen', then openDoor() changes 'DoorOpen' back to 'Idle'.

3. Final Answer:

   Idle -> Option A

4. Quick Check:

   Idle after all events = Idle [OK]

Hint: Follow state changes step-by-step [OK]

Common Mistakes:

• Skipping openDoor() effect
• Assuming state stays at DoorOpen
• Confusing event order

4. In this elevator state machine code, what is the bug causing the elevator to never open doors?

current_state = 'Idle'

def callElevator():
    global current_state
    if current_state == 'Idle':
        current_state = 'Moving'

def arriveFloor():
    global current_state
    if current_state == 'Moving':
        current_state = 'Idle'  # Bug here

def openDoor():
    global current_state
    if current_state == 'DoorOpen':
        current_state = 'Idle'

medium

A. current_state is not initialized

B. callElevator() does not change state

C. openDoor() changes state incorrectly

D. arriveFloor() sets state to 'Idle' instead of 'DoorOpen'

Solution

1. Step 1: Analyze arriveFloor() function

   arriveFloor() changes 'Moving' state directly to 'Idle', skipping 'DoorOpen'.

2. Step 2: Understand effect on door opening

   Since state never becomes 'DoorOpen', openDoor() condition never triggers, so doors never open.

3. Final Answer:

   arriveFloor() sets state to 'Idle' instead of 'DoorOpen' -> Option D

4. Quick Check:

   arriveFloor() wrong state change = no door open [OK]

Hint: Check if all states are reachable in transitions [OK]

Common Mistakes:

• Ignoring wrong state assignment
• Assuming callElevator() is faulty
• Overlooking openDoor() condition

5. You are designing an elevator system with multiple elevators and floors. Why is modeling the system as a state machine important for safety and scalability?

hard

A. It eliminates the need for sensors and hardware checks

B. It allows elevators to learn user preferences automatically

C. It ensures predictable behavior and clear transitions, preventing unsafe states

D. It reduces the number of elevators needed by half

Solution

1. Step 1: Understand state machine benefits in complex systems

   State machines define clear states and transitions, making system behavior predictable and easier to manage.

2. Step 2: Connect predictability to safety and scalability

   Predictable transitions prevent unsafe states like doors opening while moving, and help scale by managing multiple elevators consistently.

3. Final Answer:

   It ensures predictable behavior and clear transitions, preventing unsafe states -> Option C

4. Quick Check:

   Predictable states = safety and scalability [OK]

Hint: Predictable states prevent unsafe elevator behavior [OK]

Common Mistakes:

• Confusing state machines with AI
• Ignoring safety in design
• Assuming hardware replaces software logic