Design an Order Execution System for Market and Limit Orders with Cancellation

Design the order execution system for a retail brokerage. Users can place two kinds of orders to buy or sell a stock:

• a market order, which should execute as soon as possible at the best price available;
• a limit order, which may execute only at the user's limit price or better (at or below it for a buy, at or above it for a sell), and otherwise waits.

Users can cancel any order that has not yet completely executed. The design must explain how orders are executed and how their status changes, how failures are handled, how each user's balances are tracked, and how the system scales to millions of orders.

Constraints and Clarifications

• An order can execute in several pieces (partial fills), possibly at different prices, before it is complete.
• Cancelling an order cancels only its unexecuted remainder; whatever has already executed stays executed.
• The stated scale is "millions of orders"; the time window and the peak rate are for you to pin down.

Clarifying Questions

• Does the system match buy and sell orders itself, or does it route orders to external exchanges or market makers that report executions back?
• Is the target millions of orders per day, and what peak rate must the design survive, for example in the first minutes after the market opens?
• Are only cash accounts in scope, or also margin accounts that can borrow?
• What latency is expected between submitting an order and seeing it acknowledged?

Part 1 — Order execution, status flow and failure handling

Walk through what happens from the moment a user submits a market or limit order until the order is completely executed, cancelled, rejected or expired. Define the order states and which transitions between them are allowed, including partial fills and a user's cancel that arrives while the order is being filled. Then explain how the system behaves when something fails along the way: a service crashes after sending an order to the market, a confirmation or execution report is lost or arrives twice, or the market rejects the order.

Clarifying Questions for this Part

• What should a market order submitted while the market is closed do: be rejected, or wait for the open?
• Do limit orders expire at the end of the trading day, or stay open until cancelled?

What This Part Should Cover

• An explicit state machine that covers partial fills, cancel requests, rejections and expiry, with only legal transitions
• Different handling of market and limit orders from submission to completion
• Idempotent submission and messaging with the market, plus recovery from lost, late and duplicate reports
• Correct resolution of a cancel that races with a fill

Part 2 — Tracking user balances

Explain how the system tracks each user's cash and share positions as orders are placed, executed and cancelled. A user must not be able to spend the same cash, or sell the same shares, twice by submitting several orders at once. Explain how balances stay correct when execution reports arrive out of order or more than once, and how you would show that the balances are right.

What This Part Should Cover

• How cash and shares are represented, including amounts committed to open orders
• An atomic check-and-update on submission that prevents overspending under concurrency
• Exact balance updates on each execution, cancellation and rejection, applied idempotently
• A durable record from which balances can be rebuilt and reconciled

Part 3 — Scaling to millions of orders

Scale the design to millions of orders, including bursts when many users trade at once. Explain how you partition data and services, what must stay strongly consistent and what can be asynchronous, and how the system protects itself, and the markets it sends orders to, during a spike.

What This Part Should Cover

• Throughput and storage estimates tied to the stated volume
• A partition key that keeps each order's state changes and its balance changes in one partition
• Asynchronous fan-out of order events to notifications, history and live updates
• Back-pressure, rate limits and graceful degradation at peak