Designing Stock Exchange

August 12, 2019 · 16 min read

Requirements

order-matching system for buy and sell orders. Types of orders:
- Market Orders
- Limit Orders
- Stop-Loss Orders
- Fill-or-Kill Orders
- Duration of Orders
high availability and low latency for millions of users
- async design - use messaging queue extensively (btw. side-effect: engineers work on one service pub to a queue and does not even know where exactly is the downstream service and hence cannot do evil.)

Architecture

Reverse Proxy

API Gateway

Order Matching

User Store

settle

Orders

Stock Meta

auth

Cache

Balances & Bookkeeping

external pricing

clearing

house

clearing<br>house

Bank, ACH, Visa, etc

Payment

Audit & Report

Components and How do they interact with each other.

order matching system

shard by stock code
order's basic data model (other metadata are omitted): Order(id, stock, side, time, qty, price)
the core abstraction of the order book is the matching algorithm. there are a bunch of matching algorithms(ref to stackoverflow, ref to medium)
example 1: price-time FIFO - a kind of 2D vector cast or flatten into 1D vector
- x-axis is price
- y-axis is orders. Price/time priority queue, FIFO.
  - Buy-side: ascending in price, descending in time.
  - Sell-side: ascending in price, ascending in time.
- in other words
  - Buy-side: the higher the price and the earlier the order, the nearer we should put it to the center of the matching.
  - Sell-side: the lower the price and the earlier the order, the nearer we should put it to the center of the matching.

x-axis

line of prices

with y-axis cast into x-axis

Id   Side    Time   Qty   Price   Qty    Time   Side  
---+------+-------+-----+-------+-----+-------+------
#3                        20.30   200   09:05   SELL  
#1                        20.30   100   09:01   SELL  
#2                        20.25   100   09:03   SELL  
#5   BUY    09:08   200   20.20                       
#4   BUY    09:06   100   20.15                       
#6   BUY    09:09   200   20.15                       

Order book from Coinbase Pro

The Single Stock-Exchange Simulator

example 2: pro-rata

pure pro-rata

How to implement the price-time FIFO matching algorithm?

shard by stock, CP over AP: one stock one partition
stateful in-memory tree-map
- periodically iterate the treemap to match orders
data persistence with cassandra
in/out requests of the order matching services are made through messaging queues
failover
- the in-memory tree-maps are snapshotting into database
- in an error case, recover from the snapshot and de-duplicate with cache

How to transmit data of the order book to the client-side in realtime?

websocket

How to support different kinds of orders?

same SELL or BUY: qty @ price in the treemap with different creation setup and matching conditions
- Market Orders: place the order at the last market price.
- Limit Orders: place the order with at a specific price.
- Stop-Loss Orders: place the order with at a specific price, and match it in certain conditions.
- Fill-or-Kill Orders: place the order with at a specific price, but match it only once.
- Duration of Orders: place the order with at a specific price, but match it only in the given time span.

Orders Service

Preserves all active orders and order history.
Writes to order matching when receives a new order.
Receives matched orders and settle with external clearing house (async external gateway call + cronjob to sync DB)

References

Share on Twitter

Designing Stock Exchange

Requirements

Architecture