target: stock exchange system
Step 1 - Understand the Problem and Establish Design scope
functional requirements
- trade: only stocks
- order type: limit order
- normal trading hours
- basic function:
- place new limit orders
- cancel an order
- receive matched trades in real time
- view the real-time order book
- support at least tens of thousands of users trading at the same time.
- at least support 100 symbols
- trading volume: support billions of orders per day
- risk checks: like a user can only trade a maximum of 1 million shares of Apple stock in one day
non-functional requirements
- Availability: at least 99.99%.
- Fault tolerance: a fast recovery mechanism
- Latency: The round-trip latency should be at the millisecond level
- Security: account management and KYC and prevent DDoS
back-of-the-envelope estimation
- 100 symbols
- 1 billion orders a day
- 6.5 hours in total a day.
- QPS: 1 billion / 6.5 / 3600 = ~43,000
- Peak QPS: 5 * QPS = 215,000.
Step 2 - Propose High-Level Design and Get Buy-In
business knowledge 101
- broker: like Robinhood
- bid price: the highest price a buyer is willing to pay for a stock
- ask price: the lowest price a seller is willing to sell the stock
High level design
Step 3 - Design Deep Dive
- trading flow:
- matching engine
- sequencer
- order manager
- client gateway
- Market data flow
- Reporting flow
API Design
Data models
production, order, execution
order book
The following code snippet shows an implementation of the order book.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class PriceLevel{
private Price limitPrice;
private long totalVolume;
private LinkedList<Order> orders;
}
class Book<Side> {
private Side side;
private Map<Price, PriceLevel> limitMap;
}
class OrderBook {
private Book<Buy> buyBook;
private Book<Sell> sellBook;
private PriceLevel bestBid;
private PriceLevel bestOffer;
private Map<OrderID, Order> orderMap;
}
比较核心的就是这个order book的设计。
- orders的数据结构设计为双向链表。维护一个Map<orderId, Order>的结构，当删除一个order 的时候就可以直接定位到order，然后在双向链表中进行删除就是O(1)的时间复杂度。
.png)
