WeChat (微信公众号)
dev-toolsai-engineering
Original source

如何設計一個高性能訂單簿

Summary

分析 2012 Tower Research QuantCup 大賽冠軍的高性能訂單簿（Order Book）設計，所有操作 O(1)。

核心設計：最簡二級索引

  1. 第一級：全價格數組索引 — 用空間換時間，價格做成數組而非紅黑樹
    • 訂單插入：與 bidMax/askMin 比較判斷是否交叉，無交叉只需一次數組偏移
    • 撮合：按價格順序遍歷直至無法成交
  2. 第二級：時間單向鏈表索引 — 利用「時間優先」單調向前不可變的特性
    • 插入：鏈表尾部 O(1)
    • 成交：從頭部向後遍歷
    • 刪除：將 size 置 0 代替雙向鏈表指針維護（用成交時開銷增加換取刪除開銷減少）

設計啟示

  • 高性能設計需融合三層：上層業務特徵、中層數據結構適用性、底層硬件知識（SIMD、內存預取、cache 親和性）
  • 利用業務特性：價格集中性、撤單多於成交、價格-時間優先規則
  • 內存預分配避免頻繁動態申請/釋放

參考：C 源碼 gist、C++ 實現 github.com/ajtulloch/quantcup-orderbook

（這篇是前一條「Agent 低延時優化」文章中提到的前置知識文章）