Design an In-Memory Order Matching Engine

You are tasked with designing an in-memory order book and 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; 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++.