You are asked to design an in-memory order book / order matching system for a single electronic trading venue. The implementation language is C++, and the system must meet strict runtime and latency requirements (microseconds to low milliseconds) under high throughput.
Requirements
-
Core functionality
-
The system receives a stream of
orders
. Each order has at least:
-
order_id
(unique identifier)
-
side
(BUY or SELL)
-
price
-
quantity
-
timestamp
or sequence number (arrival time)
-
type
(e.g., LIMIT, MARKET; you can assume at least LIMIT orders must be supported)
-
Maintain an
order book
with two sides:
-
Bid side
: buy limit orders, sorted by descending price, then by time (price-time priority).
-
Ask side
: sell limit orders, sorted by ascending price, then by time (price-time priority).
-
On the arrival of a
new order
, the system must:
-
Attempt to
match
it against existing orders on the opposite side according to price-time priority.
-
Generate
trades
when a match occurs (specify what fields a trade has, e.g., trade_id, price, quantity, involved order_ids, timestamp).
-
Handle
partial fills
and
complete fills
.
-
If the order is not fully filled and is still valid (e.g., not IOC), insert the remaining quantity into the book.
-
Order types and constraints
-
At minimum, support:
-
Limit orders
.
-
Cancel
existing orders by
order_id
.
-
Describe briefly how you would extend to support additional types (e.g., MARKET, IOC, FOK, GTC) and any constraints that implies.
-
Performance and complexity constraints
-
The system must support
very high throughput
(e.g., tens or hundreds of thousands of orders per second) with
low latency
per operation.
-
Target
time complexity
per operation:
-
Insertion of a limit order.
-
Matching an incoming order (scanning and removing top-of-book orders on the opposite side).
-
Cancel by
order_id
.
-
You may assume the order book fits in memory on a single machine.
-
Data structures and design
-
Propose
specific C++-oriented data structures
to:
-
Maintain price levels on each side (bids/asks) in sorted order.
-
Maintain FIFO order of orders
within a price level
.
-
Support
O(1)
or near O(1) cancellation by
order_id
.
-
Discuss how you would organize these structures (e.g., maps from price to queues, auxiliary hash maps for order lookup, custom allocators, object pools, etc.).
-
Concurrency and threading
-
Assume the system may receive orders from multiple network threads.
-
Describe how you would design the core matching logic to be
thread-safe
and avoid contention as much as possible while preserving strict price-time ordering.
-
Consider options such as:
-
Single-threaded matching engine with message queues.
-
Sharding per symbol.
-
Lock-free queues or carefully scoped locking.
-
Failure handling and robustness
-
What happens on process restart? Do you need to recover the order book state? If so, how might you snapshot or log state efficiently?
-
How do you ensure that each order is
processed exactly once
and that trades are not duplicated when recovering?
-
API and output
-
Sketch a simple API for the engine (C++ interfaces or function signatures) to:
-
Submit a new order.
-
Cancel an order.
-
Query the current top-of-book (best bid/ask) and possibly full depth.
-
Show what the engine outputs when matches occur (trade events, order status updates, etc.).
-
Complexity analysis
-
Analyze the
time and space complexity
of your design:
-
Average and worst-case complexities for add, match, cancel, and query best bid/ask.
-
Discuss any
trade-offs
you made between simplicity and performance.
Explain your design choices step-by-step and justify why your approach can meet strict runtime and latency requirements in C++.