Skip to content

Latest commit

 

History

History
1418 lines (1382 loc) · 41.4 KB

161-designing-stock-exchange.md

File metadata and controls

1418 lines (1382 loc) · 41.4 KB
Raw
slug id title date comments tags slides
161-designing-stock-exchange
161-designing-stock-exchange
Designing Stock Exchange
2019-08-12 09:50
true
system design
false

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

<svg xmlns="http://www.w3.org/2000/svg" xmlnsXlink="http://www.w3.org/1999/xlink" version="1.1" width="100%" height="100%" viewBox="-0.5 -0.5 672 412" content='7Vxbc5s4FP41flwPiIvtRzuXtjPJNNPsdjf70pFBtrUB5BFyYvfXrwQCA3JsErAFnfbBNQdZEef7zkVHEgPrKtx+onC9uic+CgbA8LcD63oAwMgZ8U8h2KUC2wWpYEmxn4rMveAR/0RSaEjpBvsoLjVkhAQMr8tCj0QR8lhJBiklr+VmCxKU/+oaLpEiePRgoEr/xj5bpdKxY+zlnxFerrK/bBryTgizxlIQr6BPXgsi62ZgXVFCWPot3F6hQOgu00v6u9s37uYDoyhidX7w9Pl+GnyZrrF5C+6+fx+74OXfP8BEDo7tsidGPleAvCSUrciSRDC42UtnlGwiH4luDX61b3NHyJoLTS78DzG2k2jCDSNctGJhIO+iLWb/iJ8PHXn1VLhzvZU9Jxe7wsUDojhEDNFMFjG6K3QkLp+K9/ZdJVdZX+kziwd9U5dSFJMN9dARBWachHSJ2JF2To44txRE+FPQHf8dRQFk+KU8Dig5u8zbyZ9OKYW7QoM1wRGLCz0/CAFvIK2PW1vaozQ+c1ShSKW9ZTrH2vMv6Qiyq8Kj7EUJ7d5BQfnQLzDYSDUolHxBlGFuk3dwjoIHEmOGScRvzQljJCxzK2s7DfBStGGCkzMorzwOsKDPLGaUPKMrEhBBpohEgtgLHASZaAAsw5jd3ALReAXXYijhdimc3BD+3FA0DMkcB+hHjOgL9oSPmiV4IHrzggQs6Xjk0/FRoe1xtqnsyGC0jDIsmXN83XskCwwldquCO8rc1CFGFVB9P2jZiLrvN1q0ddCGDZ82uokxNG0eYkbys9xh6mlkHxUUW7BGcNoaYbxOI+0CbwWas3XBLfM/wUMzKnjqIoCqGWZBUUDlw3iV0yNeQw9Hyz8TalhcgMMkVGf/X+NwyZ8wwHP+CT0BwA8fUz4yIrR9K8wS0R8LSMNh/LJsyRInpy0xs7nL2KGpwHMJO9Qfd61Lxl3VZscVHowrAL9hpe8N4NbE6n4Atz7gMgpkKnoPGYff4SYyr7AgEZN8NcEbXiKMPYj4/zMxLUC0PbdguaNhRfE1HYOdh+3WXYOpwtDREN0Bd+LUdCduQ3fSCFFHMbRviPM25pw2HijZ7hTAy3C+rjBDjzyuiruvPJMtQ9dGfKz6xYlqBqMDZmCdKz6aVg+NAOiyAremFYzbCKrvjoWV2AYmztFY6LrjY+3PNJl1esi3rtNt0ge62cC4PN2A+5turdMNWH3gmzk52v5MfBv3hW8aeDPSmRtaWhMds4DLHqVTnqDkB/ZuoTuewGpa8WsEqd2bCVzMNcmmYrVtkM/hE9ktFo+sCz7baAjfRRy5AzQ4cueXz1M7yknH7gMnXVNDMitVWChvTB++cMEnyNAr7F5xIy/o6SpugN4swnUg+x/VNFCzaRrXioFa7vFCPxjbx9qfqdDfm9lm27w5w6KvNawiriwFpGNTFpHUzpwKGc61GvVOkirjugRJR0oU+Up9RLnoHjJvhaNl5wJJrldtVfL+7ALTH0jGdQOJ1rWisWIGf8WJFTwyQpF2E3CdjplADv9vEzhtApO6JtB0oahZSUyvV/tIScwsAXqyJFaa43oBjGPsVaa5ph7ktdZCba3AX6IWeuHiRl3UGxfcmm2P0DwdBh/w4U0MvkO4azV3R91BHnPIAjXL4fkKK6NHUYx/wnnSQChPToF4a2c2cK4HB/aiVTeYh9j3EyoFYnf6DHrPy4RUhY3ki+TfscxJHl+RIxnkh0aKqB0h/Zt5ljEcO275EEC24f6jM9isCVksuJoV9FqYwk0UPJMpXKw9a7XGlQmw7qzVVGumipKywwveLsCRn1D4hKbmqVrv5rkgJ/XXDeO9oPZU6o7saiFkrJZVwUWVqpYQeqZUMOqaStXpaM9UaptG13gKfvk1vBZTGVD3wABoukDXbOqit8R+6Tnr+VPY2rjbTU+KNLNl9RDFIyPeMxfdIwa1Zz6m27V6nd33iGJWk0nd8cSydfqej5VN9J0/AzX9it4SKFCshCOw0u5OqhOpQ1spxhflvnq25gp6K7WE0G2fYmXnQY/4FPvAOfGz6dXW6lN+wX1mtlE3n2m6i70Z7oZiTzMYwEi8J0EENReGwkzSTy6ZEfL8jNC6C8vzdo3l+cklnZNd44Rtt/2SU905ojvXsVV/j7YMUe5lxINR7HWBiUrSnW8RKujNPaS3cx0qttXamBcgSBNtuYGors8p/7ZM6uxkE+vfalDZaWAfOJl9cOZyLhU6ak6mxsjIr4SU/NC7eUhBp0OLqp6ar6xouNHNrKjfARWTrrvJrdoRsCsdnfnFKI7qhGcw4hN03p0xvfqcfvmOY5h+Q8zrHPVHuqnfmw2kPaluZRssTx870JoNOmqx5gHuQiQtVauJVJdKdBe2HHWpZLrxMTuYNn9Da24QihLVde6Trzt7680rb652H4KmDF4L6OQeK0NnoqKTv2qlFL2sd8PDL/cvY0yjxv6NltbN/w==' style={{ backgroundColor: "rgb(255, 255, 255)" }}

Reverse Proxy
Reverse Proxy
API Gateway
API Gateway
Order Matching
Order Matching
User Store
User Store
settle
settle
Orders
Orders
Stock Meta
Stock Meta
auth
auth
Cache
Cache
Balances & Bookkeeping
Balances & Bookkeeping
external pricing
external pricing
clearing
house
clearing<br>house
Bank, ACH, Visa, etc
Bank, ACH, Visa, etc
Payment
Payment
Audit & Report
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