State Machines#

Problem statement (interviewer prompt)

Model the lifecycle of an order in an e-commerce system: from CREATED through PAID, SHIPPED, DELIVERED with all valid cancellations and refunds. Discuss flat FSM vs hierarchical state machines, where to put guards, and how to persist state for concurrent updates.

stateDiagram-v2
  [*] --> Created
  Created --> Paid : pay()
  Created --> Cancelled : cancel()
  Paid --> Shipped : ship()
  Paid --> Refunded : refund()
  Shipped --> Delivered : deliver()
  Shipped --> Returned : return()
  Delivered --> [*]
  Refunded --> [*]
  Cancelled --> [*]
  Returned --> [*]

A finite state machine = (states, transitions, events, guards). Anything with a lifecycle - order, booking, ATM card, elevator cabin, video player - is a state machine. Model it explicitly; don't bury transitions in if-chains.

Anatomy#

stateDiagram-v2
  [*] --> Idle
  Idle --> Selecting : insert_coin
  Selecting --> Dispensing : choose_item / guard balance >= price
  Selecting --> Idle : cancel / refund
  Dispensing --> Idle : delivered
  Dispensing --> OutOfStock : stock == 0
  OutOfStock --> Idle : reset

States - Idle, Selecting, ...
Events - insert_coin, choose_item, ...
Transitions - state × event → new state.
Guards - predicates that must hold for the transition (balance >= price).
Actions / side-effects - emit refund, call payment, etc.
Initial / final states.

Hierarchical state machines (HSM)#

stateDiagram-v2
  state Connected {
    [*] --> Idle
    Idle --> Streaming : play
    Streaming --> Paused : pause
    Paused --> Streaming : play
  }
  [*] --> Disconnected
  Disconnected --> Connected : connect
  Connected --> Disconnected : disconnect

Composite state Connected shares "on disconnect → outer" without repeating transitions in every sub-state.

Two implementation styles#

A. Switch + enum (small / inline)#

enum OrderState { CREATED, PAID, SHIPPED, DELIVERED, CANCELLED }

OrderState next(OrderState s, Event e) {
  return switch (s) {
    case CREATED -> switch (e) {
      case PAY    -> PAID;
      case CANCEL -> CANCELLED;
      default     -> throw new IllegalTransition(s, e);
    };
    case PAID -> switch (e) {
      case SHIP   -> SHIPPED;
      case REFUND -> CANCELLED;
      default     -> throw new IllegalTransition(s, e);
    };
    // ...
  };
}

Pros: simple, fast. Cons: scattered guards/actions.

B. State pattern (large / per-state behaviour)#

classDiagram
  class Order {
    -state: OrderState
    +on(event)
  }
  class OrderState {
    <<interface>>
    +on(order, event)
  }
  class Created
  class Paid
  class Shipped
  class Delivered
  OrderState <|.. Created
  OrderState <|.. Paid
  OrderState <|.. Shipped
  OrderState <|.. Delivered
  Order o--> OrderState

Each state class encapsulates its allowed transitions + behaviour. Best when each state has substantial logic (Vending Machine, Elevator, Game).

Validation rules#

For correctness, model and check: - Total: every (state, event) pair is handled (or explicitly rejected). - Reachable: no orphan states. - No deadlocks: every state has at least one outgoing transition (except final). - Determinism: at most one transition per (state, event, guard).

Tools: TLA+, PlantUML state-machine validators, xstate visualisers.

Persistence#

Persist (entity_id, state, version).
Compare-and-swap on version when transitioning → optimistic concurrency.
Or store events: state = fold(events) - see event sourcing.

When the model breaks#

States proliferate (10+ states with criss-cross transitions) - refactor into HSM or split into multiple machines.
Guards become complex business rules - extract a separate domain service.
Transitions need long-running side-effects - model as a saga or workflow (Temporal, Cadence).

Where this shows up#

Vending Machine, ATM, Elevator, Hotel, Movie booking (Tier 11 LLD problems).
Order systems (e-commerce, food delivery, Uber trips).
Payment lifecycle (auth → capture → settle → refund).
Connection lifecycle (WS / SSE / gRPC streams).
Game character states (idle / running / jumping / dead).

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	Distributed transactions	2PC, TCC, sagas, outbox/inbox	distributed-transactions
`HLD`	Observability	metrics, logs, traces, SLOs	observability
`HLD`	Realtime protocols	WS / SSE / polling / gRPC streaming	realtime-protocols
`HLD`	Event sourcing + CQRS	commands -> events; separate read model	event-sourcing-cqrs
`LLD`	State machines	FSM, HSM, transitions, guards	state-machines
`LLD`	OOP pillars	encapsulation, abstraction, inheritance, polymorphism	oop-pillars
`LLD`	Structural patterns	Adapter, Decorator, Facade, Proxy, Composite	structural-patterns
`LLD`	Behavioural patterns	Strategy, Observer, State, Command, Chain	behavioral-patterns
`LLD`	Concurrency primitives	mutex, semaphore, RW lock, atomic, CAS	concurrency-primitives

Quick reference#

Interview heuristic#

When the prompt mentions a lifecycle ("order", "booking", "cabin"), draw the state diagram first, even before classes. It anchors invariants for the rest of the design.

Common bugs#

Forgetting to handle the "rollback" path from a successful state (refund after shipped).
Two events racing toward the same state - pin both to optimistic concurrency.
Implicit transitions hidden in timers / TTLs - make them explicit ("idle → expired after 10 min").

Libraries#

xstate (JS/TS) - visualisable, statecharts.
Stateless (.NET / Java port).
Spring StateMachine.
Akka FSM (Scala / Java).
Temporal / Cadence - durable workflow state machines.

Refs#

David Harel: "Statecharts: A Visual Formalism" (1987).
Miro Samek: Practical UML Statecharts in C/C++.
xstate docs.
"Designing Reactive Systems with Akka FSM" talks.

FAQ#

What is a finite state machine?#

A finite state machine is a model with a fixed set of states, a current state, and labelled transitions triggered by events. It captures the lifecycle of an object explicitly.

When should I use a state machine?#

Use one when an entity has a real lifecycle with rules about what is allowed next, like order processing, payment workflows, or a media player.

What is the difference between a flat and a hierarchical state machine?#

A flat FSM lists all states at one level. A hierarchical FSM groups related states under a parent so common transitions and behaviour are inherited.

How do I persist state machine state in a database?#

Store the current state name in a column with a check constraint for valid values. On every transition, validate the move and write the new state inside a transaction.

What is a guard in a state machine?#

A guard is a boolean condition that must be true for a transition to fire, like balance greater than price. Guards stop invalid transitions even when the right event arrives.

Behavioral Patterns: State pattern is a key behavioral pattern that implements finite state machines in OOP
Async Models: async event loops and reactive streams are driven by state machine semantics
Concurrency Primitives: thread-safe state transitions require the same primitives as concurrent shared state