設一個交易撮和引擎來練習System design。
-
- 4.1. TODO
-
新增限價單、市價單。
-
刪除掛單。
-
交易搓合的規則如下:
限價單(Limit): 當掛單進來時會優先查找低於限價的最優價格，如果有，則依照時間優先來進行數量撮合，如果沒有或者成交數量不足則放進掛單簿。
市價單(Market): 不指定價格，會依照當時最優價格及時間進行撮合，如果當下沒有完全成交就部分成交，不進入掛單簿。
-
能夠向外通知以下事件:
- 訂單已加入訂單簿
- 訂單搓合完成
- 訂單已取消
- 可用性高 - 程式重啟(意外死掉後 或 正常重開) 可以繼續搓合
- DONE
在每次作動都即時去更新資料庫裡的資料 - TODO 啟動時會去把資料庫裡撈還沒搓合完的資訊
- DONE
flowchart TD
Limit --> buy(從掛賣單中的最優價格開始取訂單\nAmount總數會剛好等於taker Amount 或超過一點)
buy --> check_buy{finish makers\n長度是否為零}
check_buy -- Yes --> addToBuy(加到掛單隊列)
check_buy -- No --> match(搓合成功)
match --> delete_maker(更新Maker在訂單簿的狀態)
delete_maker --> buyAmount{掛買剩餘Amount大於0}
buyAmount -- Yes --> addToBuy
buyAmount -- No --> End
addToBuy --> End
flowchart TD
Limit --> sell(從掛買單中的最優價格開始取訂單\nAmount總數會剛好等於taker Amount 或超過一點)
sell --> check_sell{finish makers\n長度是否為零}
check_sell -- Yes --> addToSell(加到賣單隊列)
check_sell -- No --> match(搓合成功)
match --> delete_maker(更新Maker在訂單簿的狀態)
delete_maker --> sellAmount{掛賣剩餘Amount大於0}
sellAmount -- Yes --> addToSell
sellAmount -- No --> End
addToSell --> End
flowchart TD
Market --> sell(從掛單中的最優價格開始取訂單\nAmount總數會剛好等於taker Amount 或超過一點)
sell --> check_sell{finish makers\n長度是否為零}
check_sell -- Yes --> End
check_sell -- No --> match(搓合成功)
match --> delete_maker(更新Maker在訂單簿的狀態)
delete_maker --> End
沒有撮合成功的訂單或者還有數量未撮合完的訂單會放進一個集合中，等待之後的訂單嘗試撮合，我們把這個集合稱為掛單簿(Order Book)。 在掛單簿中會有掛買與掛賣的集合，在單一撮合引擎下我們期望在任何操作速度越快越好，才有辦法負荷大量的訂單近來，因此我們需要一個資料結構來滿足以下需求。
- 插入與刪除盡可能快。
- 查詢速度盡可能快。
所以我評估了以下資料結構與演算法，來看何種適合
- n 為資料數量。
- 有兩個時間複雜度時，前者為平均，後者為最差。
| Data Struct | Algorithm | Search | Insert | Remove |
|---|---|---|---|---|
| Array | 線性搜尋 | O(n) | O(n) | O(n) |
| Tree | Binary Search | O(log n) / O(n) | O(log n) / O(n) | O(log n) / O(n) |
| Tree | AVL | O(log n) | O(log n) | O(log n) |
| Tree | 紅黑樹 RBT | O(log n) | O(1) / O(log n) | O(1) / O(log n) |
根據以上表格 AVL 與 RBT 可以盡可能做到 log n 的時間複雜度，但在這邊我會選擇 RBT，原因是AVL在樹的高度平衡做的嚴謹，會比RBT多做幾次旋轉，意味著會比較浪費，故選擇紅黑數來當作我的資料結構。
在這邊不自己做輪子，引用了在Github上的開源 emirpasic/gods 來實現紅黑樹。
根據撮合規定，會有需要價格順序，再來是時間順序，所以我會有一個 PriceTree 以紅黑樹來實現，再來每個節點裡都會在放一個 TimeTree 也是以紅黑樹來實現，用來排序時間且裡面會放各個Order。
雖然表上RBT是最快的，但實現起來卻不是，原因是在之中會去呼叫一些函式，需要再花時間看一下哪邊可以讓他更快。
-
Web Framework 此service 當前為了方便送request，故選擇開 http 的接口去收 http request，之後如果轉為內部服務，則會考慮開grpc或者從mq收資料去搓合。
-
gin: 由於fiber的案例，原本想找最快的來使用，但還是乖乖選擇最多人使用的老牌框架。 -
fiber: 在此選了 fiber 這個框架做使用，原因是在當fiber開啟 prefork 模式時，處理request的效率是最高的，根據這裡。觀察他在Github上的星星樹與還有在維護的部分，選擇fiber作為我的web Framework。
-
-
關連式資料庫
Mysql用來儲存訂單跟交易結果來呈現資料，故選最常用的。
請使用 Postman 導入此文件
├── build -- 放置dockerfile
├── cmd -- 主要的程式
├── configs -- 配置檔案
├── deployment -- 部屬檔案的放置
│ ├── mysql -- 與mysql部署相關的檔案
│ │ └── init
│ └── trading-engine -- 與server部署相關的檔案
│ └── config
├── docs -- 文件放置
│ ├── image -- 圖片
│ └── postman -- Postman
├── internal -- 私有代碼
│ ├── config -- 配置檔結構及讀取
│ ├── engine -- 搓合引擎的實現
│ ├── handler -- 處理路由
│ ├── model -- 各個模型及功能實現
│ ├── server -- http gin server
│ └── storage -- 有關儲存
│ └── mysql -- mysql的實例及方法
├── pkg -- 可以讓別人用的
│ └── logger -- zerolog相關配置
└── test -- 放unit test的