System design deep dive · HLD
Design an Elevator Control System for a large building: full high-level design.
Requirements, back-of-envelope capacity estimation in requests-per-minute for a multi-car bank, a high-level design diagram, a deeper deployment architecture diagram, sequence diagrams for hall-call dispatch and real-time car-state tracking, and an entity-relationship diagram for the data model.
1. Clarify requirements before drawing any box
A strong system design answer starts by pinning down scope out loud. For an elevator control system, that means separating "which car should answer this hall call" (a dispatch/optimization problem) from "how does one car serve its own queue of stops" (a SCAN/LOOK scheduling problem) - these are two distinct algorithms working together.
Functional requirements
Non-functional requirements
2. Back-of-the-envelope capacity estimation
"Capacity" here means request/decision throughput for a bounded, physical fleet - not web-scale QPS - which shapes how much computation the dispatcher can afford to spend per decision.
| Metric | Assumption | Resulting estimate |
|---|---|---|
| Elevator bank size | 8 cars serving a 40-floor tower | 8 concurrent car-state machines to track |
| Peak hall calls | Morning rush, ~3 calls/floor/minute across ground-floor lobby surge | ~180 hall calls/minute ≈ 3/sec at the worst 5-minute window |
| Dispatch decision cost | Evaluate 8 cars × simple cost function per hall call | Trivial CPU cost (<1ms); the real constraint is response latency, not throughput |
| Car-state update rate | Each car reports position/door/load ~5 times/sec while moving | 8 cars × 5Hz = 40 state updates/sec baseline |
| Average trip round-trip time | ~90 seconds average full cycle (pickup, travel, dropoff, return) | 8 cars × (60s/90s) ≈ theoretical max ~5.3 passenger trips/sec fleet-wide capacity |
3. High-level design (HLD)
The HLD names the major components and the one-directional data flow between them, without committing yet to specific hardware bus protocols or safety-controller wiring - that level of detail belongs in the architecture diagram in the next section.
What each box owns
Dispatcher
Receives a hall call (floor, direction) and scores every car against a cost function - typically estimated time of arrival, factoring in current position, direction, existing stop queue length, and whether the car is already heading toward the caller (a car moving away scores far worse than one already en route in the right direction). It assigns the lowest-cost car and inserts the new stop into that car's queue; it does not talk to hardware directly.
Car controller (one per car, SCAN/LOOK queue)
Maintains its own car's ordered stop queue using a LOOK algorithm variant: while moving in a direction, it services all pending stops in that direction before reversing, rather than serving stops in the order they were requested - this is what prevents a car from bouncing erratically floor-to-floor. It owns the actual motor/door actuation calls and is the only component with direct hardware write access for its car.
Car-state table and safety interlock unit
The car-state table is the live, in-memory source of truth for every car's floor, direction, door state, and load, updated continuously from sensors and read by the dispatcher on every hall-call decision. The safety interlock unit is a logically (often physically) separate control path that enforces hard invariants - doors cannot open while the car is moving, motion cannot start with an open door, overload holds the car - and can override both the dispatcher and any car controller command, since safety rules must never be bypassable by a software bug in the normal control path.
Trip log DB and building management integration
Every dispatch decision and completed trip is logged durably for maintenance analytics (which car needs service, traffic pattern tuning) but this logging is asynchronous and never gates a live dispatch decision. The building management system integration is how a fire alarm or emergency signal preempts normal operation - all cars recall to a designated floor and disable normal hall-call service, a mode that takes strict priority over the dispatcher's cost-function logic.
4. Detailed architecture diagram
The architecture diagram takes every HLD box and answers "how is this actually wired and deployed in the building?" - which is where an interviewer checks whether you understand this is closer to a real-time embedded control system than a cloud web service.
| Decision | Choice | Reasoning |
|---|---|---|
| Dispatcher redundancy | Active/hot-standby pair sharing the car-state bus, not a single instance | The dispatcher is not safety-critical (a wrong car assignment is an inconvenience, not a hazard) but its complete loss would strand the whole bank without hall-call service, so a hot standby takes over on failure. |
| Safety interlock isolation | Physically/logically separate from the dispatcher and car-controller software path | Door/motion safety invariants must hold even if the dispatcher or a car controller has a software bug - this is a hardware-enforced fail-safe layer, not just a code check. |
| Sensor bus protocol | Deterministic real-time fieldbus (CAN or RS-485), not a general-purpose network | Car position/load/door state must be delivered with bounded, predictable latency for safe real-time control - a best-effort network protocol is not appropriate here. |
| Remote monitoring access | Read-only cloud dashboard, no write path into the control loop | Remote maintenance visibility is valuable, but allowing any external network path to issue control commands would be an unacceptable safety and security risk for physical equipment moving people. |
5. Sequence diagrams for the two critical flows
A sequence diagram is where an interviewer checks whether you actually understand call order, what safety checks are non-bypassable, and how a car's own LOOK queue decides stop order independently of the dispatcher.
5.1 Hall-call dispatch (choosing which car answers)
Step 4's cost function is the heart of the dispatch problem: a car already moving toward the caller in the requested direction scores far better than an idle car further away or a car moving away that would need to finish its current direction and reverse. Step 7 shows the new stop being inserted into Car #4's existing LOOK queue at the position matching its physical travel order, not appended to the end - so if the car is already passing floor 10 heading up, floor 12 slots in immediately after any closer pending stops, not after floor 30 if that happened to be requested first.
5.2 Real-time car-state tracking and safety interlock
Step 4 is the non-negotiable safety invariant: the interlock unit independently re-verifies velocity is exactly zero before permitting a door-open command, and it denies the request even though the car controller "knows" it is arriving at the floor - the interlock does not trust the controller's own belief about its state, it re-checks the raw sensor signal itself. This redundancy is deliberate: a bug in the car controller's arrival-detection logic must not be able to open a door on a still-moving car.
6. Entity-relationship (ER) diagram and schema
The data model here mostly serves maintenance analytics and audit, since live control state lives in memory - the persisted schema has to answer: which car served which request, how is a car's live state distinct from its historical record, and how are pending floor requests tracked per car.
Key modeling decisions
| Storage choice | Use when | Watch out for |
|---|---|---|
| Relational (Postgres), single on-site instance | You want simple joins for maintenance dashboards ("which car has the longest average wait time") and the dataset is inherently tiny. | None significant at this scale - the persisted schema is a minor supporting player next to the in-memory real-time control loop. |
| Time-series DB for car_state history | If historical position/load telemetry is wanted for predictive maintenance (vibration/wear trends), a time-series store (InfluxDB) suits the high-frequency sensor stream better than overwriting a single row. | Adds an extra system to operate; only justified if predictive maintenance is an actual requirement, not by default. |
7. Deep dives interviewers actually probe
SCAN/LOOK vs FCFS - why does stop order matter this much?
Serving stops in arrival (first-come-first-served) order can force a car moving up to first go all the way down to serve an earlier-requested lower floor, then back up - wildly inefficient. LOOK (a bounded variant of the SCAN disk-scheduling algorithm) instead services every pending stop in the current direction of travel before reversing, which is both faster on average and matches passenger intuition ("the car is already going up, why would it go down first?").
// Simplified LOOK: insert a stop into the car's ordered queue
void addStop(int floor, Direction currentDir, TreeSet<Integer> upStops, TreeSet<Integer> downStops) {
if (currentDir == UP && floor >= car.currentFloor) upStops.add(floor);
else if (currentDir == DOWN && floor <= car.currentFloor) downStops.add(floor);
else queueForOppositeDirectionPass(floor); // served after this pass reverses
}How do you prevent starvation - a car or a floor never getting served?
Pure "lowest ETA wins" dispatch can starve a far-away floor if closer calls keep arriving. The cost function adds an aging term - a call's effective cost decreases the longer it has waited unserved, eventually overriding ETA-optimality to guarantee an upper bound on wait time. Symmetrically, if one car keeps winning every dispatch (e.g. it happens to sit centrally), the dispatcher can round-robin among near-tied candidates rather than always picking the single lowest score, spreading wear and avoiding one car handling disproportionate trips.
What takes priority: normal dispatch, emergency, or maintenance mode?
A strict priority order, enforced structurally rather than by convention: fire/emergency recall (architecture diagram's building management integration) preempts everything and forces all cars to a designated floor with doors held; maintenance mode locks a specific car out of the dispatcher's candidate pool entirely so it can never be assigned a hall call while a technician is working on it; normal hall-call dispatch runs only when neither higher-priority mode is active. This priority ordering is checked at the point cars are considered for dispatch, not layered on as an afterthought.
How does overload / weight-limit handling work?
The load cell reports weight continuously; crossing the rated capacity threshold triggers the safety interlock to hold the doors open (refusing to close and depart) and sound an audible alarm, rather than departing overloaded - this is a hard interlock, not a dispatcher-level decision, since it is a physical safety concern independent of any software routing logic.
What is the single biggest bottleneck during the morning "up-peak" surge?
Not dispatch computation - scoring 8 cars is trivial. The real constraint is physical: every car funnels through the same ground-floor lobby simultaneously, so round-trip time (load at lobby, travel, unload, return empty) dominates. The mitigation is a specialized up-peak dispatch mode that some cars run as dedicated express lobby-to-upper-floor shuttles during the surge window, rather than using the same general-purpose LOOK dispatch logic that works well the rest of the day - a good example of a design that adapts its algorithm to a known, predictable traffic pattern rather than using one fixed strategy always.
Post a Comment
Add