Let’s design a stock exchange like NASDAQ
- Users should be able to bid buy/sell prices for a stock
- Users should be able to view the real time and historic view of stock price aka ticker
- Compute top 50 best and worst performing stock
- Publish the changes of stock price to subscribers
Non Functional Requirements
- System should be able to handle 100k clients
- System should be able to handle around 100 million bids/day
- System should be able to serve prices for stocks with historic view
Stock exchanges usually busy during the day 9 AM – 5 PM. So will be serving the traffic during the 8 hour window. Hence we can calculate the capacity for bidding service for this duration. In case of bidding we can assume that read to write ratio is 1:1
100 * 10 ^ 6 / ( 8 * 60 * 60 ) = 3472 QPS
Bandwidth should be calculated for 2 two components here which is bidding and ticker.
Bidding - 3500 * 200Byte / 1024 / 1024 = ~0.6 MBps Ticker - 100k * 10 * 200Byte / 1024 / 1024 = 190 MBPS
- System should scale around 3.5K QPS
- Bidding system require ~1 MBps
- Ticker system require ~190 MBps
High Level Design
At high level we can visualise 2 components needed for the stock exchange
- Bidding Service is responsible for taking bids from customer
- Ticker Service is responsible for showing current price change of stock
Low Level Design
In this section we will be discussing about the components we have identified in the HLD.
Bidding service needs to take the buy/sell bids from the user and should be able to find the buyers/sellers and complete the transaction.
We need a matching engine which needs to take incoming buy/sell bid and able find the match one or more buyer/seller and execute the transaction, if it can’t find the match we need to store the bid and try execute the transaction once the matching bid arrives.
Bidding Data Model
Ticker service needs to serve the clients with latest price of a stock and able to historic view based on the time. Current price of the stock needs to be computed from executed transactions from bidding service and stored in historic price DB.
We need transaction happened on Stock DB to be used by ticker service to compute the latest price of a stock, in this case we can use design pattern called Change Data Capture
Ticker Data Model
I often see that people choose the DB first and try to force fit their case. We always need to identify the requirement for each DB in our services and choose the Datastore based on it, ideally based on the query pattern, scalability, reliability etc.
- Should be able to store millions of bids
- Should be able to store and retrieve the data at low latency and high QPS
In-Memory sharded datastore should be able to satisfy the above requirement.
Stock Transaction Store
- Should be to store the transaction with ACID guarantee
- Should be able to support multi transaction commit, incase 1 buy bid is matched with multiple sell bids
We can choose any Datastore with ACID guarantee for this use case
Historic Price Store
- Should be able to store the price of a stock based on the time
We can choose any store which can provide the time series based retrieval
One of key aspect of the scalability is partition the data in the right way. So that data growth will not be a problem.
I will try to cover this in another separate post, because find top k term is common problem in lot of systems. Ex. Twitter trending, popular product in e-commerce website etc.