Design an in-memory order matching engine

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

1. 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.
2. 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.
3. 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.
4. 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.).
5. 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.
6. 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?
7. 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.).
8. 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++.