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++.