Design a Stock Exchange Matching Engine
Design a system that matches buy and sell orders in a financial market. Focus on latency, concurrency, and maintaining an order book (priority queue/heap).
Why Interviewers Ask This
Interviewers at Stripe ask this to evaluate your ability to design low-latency, high-concurrency systems under strict consistency constraints. They specifically test your grasp of data structures like heaps for order matching, your understanding of race conditions in distributed ledgers, and your capacity to prioritize performance metrics critical to financial infrastructure.
How to Answer This Question
1. Clarify Requirements: Define the scope (e.g., limit orders vs. market orders), latency targets (microseconds), and consistency needs (strong vs. eventual). 2. High-Level Architecture: Propose a single-threaded or lock-free core engine to minimize context switching, surrounded by API gateways for scaling read/write traffic. 3. Data Structure Design: Detail the Order Book implementation using a priority queue (max-heap for asks, min-heap for bids) sorted by price and time. 4. Matching Logic: Explain the algorithm for crossing orders, handling partial fills, and updating the book atomically. 5. Concurrency & Scalability: Discuss strategies like partitioning by asset class or using sharding with consistent hashing to handle massive throughput without sacrificing speed.
Key Points to Cover
- Prioritizing single-threaded or lock-free designs to eliminate race conditions and reduce latency
- Correctly implementing Price-Time priority using dual heaps for the order book
- Defining clear sharding strategies based on asset symbols for horizontal scalability
- Addressing the atomic nature of trade execution and partial fill scenarios
- Emphasizing audit trails and data consistency suitable for financial applications
Sample Answer
To design a stock exchange matching engine, I first clarify that we need sub-millisecond latency and strong consistency for trade execution. For the core architecture, I would avoid multi-threaded locks on the order book due to contention. Instead, I propose a single-threaded event loop processing orders sequentially per symbol, which guarantees FIFO ordering and eliminates race conditions entirely. The central data structure is the Order Book, implemented as two priority queues: a min-heap for buy orders and a max-heap for sell orders, both prioritized by price then timestamp. When a new order arrives, it attempts to match against the opposite heap. If matched, we execute the trade, update the remaining quantity, and potentially trigger further matches until the order is filled or exhausted. For scalability beyond a single node, we can shard the system by ticker symbol, ensuring all orders for 'AAPL' go to one specific instance. This allows horizontal scaling while maintaining the simplicity of the single-threaded logic within each shard. Finally, we must implement an audit log using an append-only store to ensure every state change is recoverable, aligning with Stripe's focus on reliability and correctness in financial transactions.
Common Mistakes to Avoid
- Suggesting heavy database locking for the active order book, which creates unacceptable bottlenecks
- Ignoring the Price-Time priority rule, which is the fundamental standard for fair trading
- Over-engineering with complex distributed consensus algorithms before solving the core matching logic
- Failing to address how to handle edge cases like market crashes or extreme volume spikes
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.