System Design Interview Vol. 2 · 第 13 章Triton 覆蓋度:🟢 高Triton 線
Stock Exchange
先來先撮,一筆都不能亂序
原書設計一個電子交易所:order book、sequencer 幫每筆單蓋序號、單執行緒的撮合引擎,最後把一切塞進一台巨大的伺服器、用 mmap 當事件儲存,再用 hot-warm 和 Raft 做高可用。Triton 同意核心:每檔股票一個單執行緒引擎、FIFO MQ、批次處理;他不同意的是「event-based 沒有 lock」和「這樣就很穩」:「Super hard to be truly robust」。
給文組
全程用一面「演唱會票券轉讓板」:賣家貼「售」、買家貼「收」、同價先貼先賣,櫃台用號碼牌排順序。一階一階爬 13 個概念;頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。
給工程師
第 8–49 頁完整講原書(25 張圖全部重繪、API 與程式碼照錄),之後是 Triton 的觀點,最後一頁列出所有出處(materials/core)與頁碼對照。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 💬 作者未標示 🔭 依 Triton 原則推論 📅 2026 補充
先用生活理解演唱會票券轉讓板
收的最高價 ≥ 售的最低價,就成交;同價,先貼的先賣
動手試:你想收一張票
| 轉讓板 | 原書的交易所 |
|---|---|
| 整面公告板上還沒成交的便利貼 | Order book:每個 symbol 的買單與賣單 |
| 「收 3,000」「售 3,200」 | Limit order:指定價格的買/賣單 |
| 「不管多少,馬上給我一張」 | Market order:不指定價格,立刻以市價成交 |
| 最高的「收」、最低的「售」 | Best bid、best ask |
| 櫃台阿姨幫忙配對 | Matching engine(撮合引擎) |
| 抽號碼牌,誰先誰後看號碼 | Sequencer:每筆單蓋上連續的序號 |
| 成交後在白板寫「剛剛 3,200 成交」 | Market data:成交價、K 線、order book 深度 |
兩張 3,200 的票,阿明 09:02 貼、小華 09:05 貼,你出 3,200 收,一定先配阿明。先來先撮,不然就不公平。
學習地圖本章的概念階梯
今天爬 13 階。每一階只用前面講過的東西。
- 1order book掛單簿
- 2limit / market限價/市價
- 3price-time先比價再比先來
- 4market data成交白板・K 線
- 5latency等多久・微秒
- 6critical path一定得走的路
- 7sequencer號碼牌機
- 8p99最慢的那 1%
- 9single thread一個阿姨專心配
- 10event sourcing只記發生過的事
- 11hot-warm影子阿姨
- 12multicast大家同時聽到
- 13bottleneck最慢的那一站
第 1–3 階 · 一面轉讓板
要回答:買賣單怎麼排?誰先配到?
第 4–7 階 · 行情、延遲、號碼牌
要回答:一筆單走哪條路?誰先誰後?
第 8–10 階 · 引擎裡面
要回答:怎麼每筆都一樣快?出錯能重來?
第 11–12 階 · 備援與公平
要回答:引擎倒了誰接手?行情怎麼同時送到?
第 13 階 · Triton 的看法
要回答:真正卡住的是哪一站?
全程只用一面板子:週末演唱會的票券轉讓板(虛構)
票價都是 3,000–3,500 元,數字小到能心算。每爬 2–4 階,有一頁「到這裡你已經會了」。
延伸基礎第 1 階 · order book懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
轉讓板上還沒成交的便利貼,就是一本「簿子」
① 先想像
想賣票的人貼黃色「售」便利貼,想買的人貼綠色「收」便利貼。沒人接手的便利貼,就一直留在板上。
你猜猜看:板上「收」有 3,000、3,100;「售」有 3,200、3,300。出價最高的「收」和最便宜的「售」差多少?
最想買的人出 3,100,最便宜的賣家要 3,200,差 100。沒有人讓步,就不會成交。
③ 這叫做 order book、bid / ask
order book:還沒成交的買單和賣單清單,就是這面板子。bid / ask:出價最高的「收」/開價最低的「售」。
④ 跟這章的關係
交易所每檔股票(原書叫 symbol)各有一本 order book。整章就是把這面板子做到每秒 20 萬筆。
② 動手玩:自己貼一張
延伸基礎第 2 階 · limit / market懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
「貴了就不要」和「多少錢都要」
① 先想像
你想收 3 張票。你可以說「最多出 3,300,貴了就算了」,也可以說「多少錢都好,現在就給我」。
你猜猜看:板上「售」只有 3,200、3,300、3,500 各 1 張。你說「現在就要 3 張」,一共付多少?
3,200 + 3,300 + 3,500 = 10,000。從最便宜的一路往上買,最後一張最貴。保證買到,但事先不知道會付多少。
③ 這叫做 limit order、market order
limit order(限價單):指定價格,超過就不買;可能要等、可能只買到一部分。market order(市價單):不指定價格,馬上用板上現有的價格成交。
④ 跟這章的關係
原書的需求只做 limit order(第 8 頁),但 Figure 13 用一筆大額 market order 舉例(第 24 頁)。
② 動手玩:收 1–3 張
延伸基礎第 3 階 · price-time懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
兩張 3,200 的票,先配給誰?
① 先想像
阿明 09:02、小華 09:05 都貼了「售 3,200」;阿美 09:01 貼「售 3,300」。你出 3,300 要收 1 張。
你猜猜看:你出 3,300 收 1 張,櫃台阿姨配給誰?
先比價格:3,200 比 3,300 便宜,對你比較好。同樣 3,200 的阿明和小華,再比誰先到。
③ 這叫做 matching engine、price-time priority
matching engine:負責配對買賣的櫃台阿姨(一支程式)。price-time priority:先比價格,同價再比誰先到,也就是 FIFO(先進先出)。
④ 跟這章的關係
原書的撮合偽碼就是 FIFO(第 42 頁)。「誰先到」要怎麼記,第 7 階揭曉。
② 動手玩:買家一位一位來
到這裡你已經會了小結 1 / 5
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
到這裡你已經會了:一面轉讓板怎麼運作
- 還沒成交的買賣單排在一本 order book 上;出價最高的「收」叫 bid,開價最低的「售」叫 ask。
- limit order 指定價格、可能要等;market order 馬上成交、不保證價錢。
- matching engine 先比價格、同價比誰先到(price-time priority,FIFO)。
下一階要解決的問題
真的交易所要做多大?先看原書在面試一開始問了什麼、估出每秒幾筆。
原書 Step 1理解問題、確立範圍
只做股票、只做限價單、只做正常交易時段
這一步要解決的問題交易所要做多大、做哪些功能?沒問清楚,後面的延遲和容錯都無從設計。
📖 原書 應徵者 × 面試官
| 應徵者問 | 面試官答 |
|---|---|
| 交易哪些證券?股票、選擇權還是期貨? | 為了簡化,只有股票 |
| 支援哪些操作?下單、取消、替換?限價、市價、條件單? | 下新單、取消;訂單類型只考慮限價單 |
| 要支援盤後交易嗎? | 不用,只要正常交易時段 |
| 基本功能與規模?多少使用者、symbol、訂單? | 客戶可下限價單或取消、即時收到成交;可看即時 order book。至少數萬人同時交易、至少 100 個 symbol、每天數十億筆訂單;交易所受監管,要做 risk check |
| Risk check 要做到多細? | 簡單的就好:例如一個使用者一天最多交易 100 萬股 Apple |
| 你沒提到使用者錢包,要考慮嗎? | 好問題!下單時要確認資金足夠;單子還在 order book 等成交時,所需的錢要先凍結,避免超支 |
白話:symbol=股票代號(例如 AAPL);risk check=下單前先檢查有沒有超過限制;wallet=使用者在交易所的錢包,掛單時先凍結要用的錢。
📖 原書 交易所的基本功能是有效率地配對買賣雙方,這件事從物物交換、大聲喊價到今天的超級電腦都沒變。交易所有很多種:有的專注技術(LMAX),有的強調公平(IEX)。動手前先確認規模和重要特性。
📖 原書 Non-functional requirements
- Availability:至少 99.99%,停機幾秒就傷商譽
- Fault tolerance:要有容錯和快速復原機制,限制事故影響
- Latency:往返延遲要到毫秒級,特別看 p99。從市價單進交易所,到它以成交回來為止;p99 持續偏高,少數使用者體驗會很糟
- Security:帳戶管理;開戶前做 KYC;公開資源(有市場資料的網頁)要防 DDoS
白話:availability=能用的時間佔幾成(完整版:02 章);KYC=開戶前確認你是誰;DDoS=有人故意用大量請求灌爆;latency 和 p99 在第 14、28 頁細講。
📖 原書 「100 個 symbol」「數萬使用者」說明面試官要的是中小型交易所,但設計要能擴充到更多 symbol 和使用者,很多面試官會從擴充性追問。
原書 Step 1規模 · Figure 1 · Back-of-the-envelope estimation
每天 10 億筆,平均每秒 4.3 萬、尖峰 21.5 萬
這一步要解決的問題每天 10 億筆單,換成每秒是多少?這個數字決定撮合引擎要多快。
📖 原書 NYSE 每天數十億筆配對,HKEX 每天約 2,000 億股。Figure 1 是市值破兆美元的「trillion-dollar club」。
📖 原書 估算
- 100 symbols
- 1 billion orders per day
- NYSE 週一到週五 9:30–16:00(美東),共 6.5 小時
- QPS: 1 billion / 6.5 / 3600 = ~43,000
- Peak QPS: 5 * QPS = 215,000
開盤後和收盤前的交易量明顯比較高,所以尖峰抓平均的 5 倍。
白話:QPS=每秒幾筆請求;peak=最忙的那一刻。QPS 的完整版:02 章第 23 頁
動手算
原書 Step 2Business Knowledge 101
設計前先懂行話:誰在下單、下的是什麼單
這一步要解決的問題誰會來下單?下的是哪幾種單?這是設計前要先懂的行話。
Broker
多數散戶透過經紀商和交易所交易,例如 Charles Schwab、Robinhood、Etrade、Fidelity。經紀商提供友善的介面讓散戶下單、看市場資料。
🎫 幫你代貼便利貼的票券 app
Institutional client
用專業交易軟體大量交易,需求各不相同:退休基金追求穩定,很少交易、一交易就很大,需要拆單降低 market impact;做市的避險基金靠佣金回扣賺錢,需要低延遲,不能像散戶一樣在網頁或 app 上看行情。
🎫 一次收五百張的黃牛集團
Limit order
以固定價格買或賣。可能不會馬上成交,也可能只成交一部分。
🎫「收 3,000,沒有就算了」
Market order
不指定價格,立刻以當下市價成交。犧牲成本換取保證成交,在變化很快的行情下有用。
🎫「多少錢都好,現在就要」
白話:broker=券商;拆單=把大單切成很多小單慢慢下,免得 market impact(自己把價格推走);做市(market making)=同時掛買和賣、賺中間價差;佣金回扣(rebate)=交易所給掛單者的回饋。
動手試:同一筆 1,000 股的單,限價和市價差在哪?
延伸基礎第 4 階 · market data懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
板子旁邊那塊「剛剛成交」白板
① 先想像
轉讓板旁邊有塊白板,每成交一張就寫一行「3,200」。不看便利貼,也知道現在的行情。
你猜猜看:10 分鐘內依序成交 3,200、3,300、3,100、3,250。「開、高、低、收」是?
開是第一筆、收是最後一筆,高和低是這段時間的最高、最低。四個數字畫成一根棒子。
③ 這叫做 market data、candlestick(K 線)
market data:成交價、掛單這些「行情」,發給所有想看的人。candlestick(K 線):一段時間的開、高、低、收,畫成一根棒子。
④ 跟這章的關係
原書的 market data publisher 就是寫白板的人(第 21 頁)。
② 動手玩:畫一根 K 棒
原書 Step 2Market data levels · Figure 2–4
L1 只看最好的一檔,L2 看好幾檔,L3 連排隊的每一張單都看
這一步要解決的問題行情要給多細?只看最上面兩張便利貼,還是整面板子、連排隊順序都看?
📖 原書 美股報價分三層:L1、L2、L3。
- L1:最佳買價、賣價與數量。Bid 是買方願意付的最高價,ask 是賣方願意賣的最低價
- L2:比 L1 多好幾個價位(depth)
- L3:每個價位,以及該價位上排隊的數量
文組翻譯
L1 是轉讓板最上面那兩張便利貼;L2 是「3,200 有 3 張、3,300 有 1 張」這種統計;L3 是把每張便利貼、誰先貼的都拍下來。
為什麼 L3 有價值?撮合是 FIFO(第 42–43 頁),看得到排隊順序,就知道自己的單前面還有多少人。原書後面也說:L1 日 K 可以從 Google Finance 免費拿,L2/L3 很貴(第 45 頁)。
原書 Step 2Candlestick chart · Figure 5 · FIX
一根 K 棒四個數字;交易所之間講 FIX
這一步要解決的問題一段時間的成交怎麼濃縮成一張圖?交易所之間又用什麼格式溝通?
📖 原書 K 線表示一段時間的價格:open、close、high、low。常見區間是 1 分鐘、5 分鐘、1 小時、1 天、1 週、1 個月。
📖 原書 FIX(Financial Information eXchange)protocol 1991 年建立,是交換證券交易資訊的廠商中立通訊協定。原書的範例:
點一個欄位看它的意思。
原書只給訊息本身、沒有逐欄解釋。欄位名稱依 FIX 4.2 規格補上;代碼值只解釋有把握的幾個。
白話:protocol=雙方事先約好的訊息格式;廠商中立=不屬於任何一家公司,大家都能用。
延伸基礎第 5 階 · latency懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
從交出便利貼到聽見「成交」,等了多久?
① 先想像
你把便利貼交給櫃台,到阿姨跟你說「成交了」,中間那段等待,就是這一階的主角。
你猜猜看:1 毫秒是 1 微秒的幾倍?
1 秒 = 1,000 毫秒 = 1,000,000 微秒。原書說好的交易所,延遲要壓到「數十微秒」。
③ 這叫做 latency、µs(微秒)
latency(延遲):從送出到收到回覆,等了多久。µs(微秒):百萬分之一秒;ms(毫秒)是千分之一秒。記憶體、硬碟、網路誰快的完整版:02 章
④ 跟這章的關係
原書要求往返延遲到毫秒級、而且要穩(第 8 頁);deep dive 會一路壓到微秒(第 29 頁)。
② 動手玩:拿一件事當尺
長條用「數量級」畫(每多一格是 10 倍),不然最短那條會看不見。眨眼約 100 ms 是示意,其他三個量級照原書。
延伸基礎第 6 階 · critical path懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
哪些步驟會讓你等,哪些不會?
① 先想像
你的便利貼要經過:櫃台收單 → 審核有沒有錢 → 抽號碼牌 → 阿姨配對,才知道成交。旁邊有人抄白板、記帳,你不用等他們。
你猜猜看:收單 2 分、審核 3 分、抽號 1 分、配對 1 分;抄白板 5 分、記帳 10 分。你最少要等幾分鐘?
只有那四步一定要走:2 + 3 + 1 + 1 = 7。抄白板和記帳在旁邊同時做,不擋你。
③ 這叫做 critical path
critical path(關鍵路徑):一筆單從進來到成交,一定要走的那一串步驟。你等多久,就是這條路上每一段加起來。
④ 跟這章的關係
原書的關鍵路徑是 gateway → order manager → sequencer → matching engine(下一頁 Figure 6);連寫日誌(logging)都要移出去(第 29 頁)。
② 動手玩:把步驟移出你的路
原書 Step 2High-level design · Figure 6
三條流程:交易(關鍵路徑)、市場資料、報表
這一步要解決的問題一筆單從客戶的手機到成交回報,經過哪些元件?哪一條路最要快?
- 1 客戶透過經紀商的網頁或 app 下單
- 2 經紀商把單送到交易所
- 3 單從 client gateway 進來:輸入驗證、rate limit、認證、正規化等,再轉給 order manager
- 4–5 Order manager 依 risk manager 的規則做 risk check
- 6 通過後,確認 wallet 有足夠資金
- 7–9 送到 matching engine;配對成功產生兩筆 execution(fill),買賣各一。為了重播時結果有決定性,訂單和成交都在 sequencer 排序
- 10–14 成交回傳給客戶
- M1 撮合引擎產生成交串流,送給 market data publisher
- M2 MDP 從成交和訂單串流建出 K 線和 order book,送到 data service
- M3 市場資料存進專用儲存做即時分析;經紀商連 data service 取得並轉給客戶
- R1–R2 Reporter 從訂單和成交收集報表欄位(client_id、price、quantity、order_type、filled_quantity、remaining_quantity),合併寫進 DB
📖 原書 交易流程 1–14 在關鍵路徑上,市場資料和報表不在,延遲要求不同。
白話:client gateway=交易所收單的大門;order manager=管每張單狀態的人;risk manager=訂風險規則的人;reporter=記帳、出報表的人。關鍵路徑見第 15 頁。
延伸基礎第 7 階 · sequencer懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
三個窗口同時收單,誰先誰後?
① 先想像
櫃台有三個窗口同時收單,每個窗口牆上各有一個時鐘,偏偏 B 窗口的鐘慢了 3 秒。
你猜猜看:改成每張單一進門就抽一張號碼牌 101、102、103……阿姨收到 101、102、104,她該怎麼辦?
號碼是連續的,少了 103 一眼就看出來。先把 103 找回來,順序才不會亂。
③ 這叫做 sequencer、sequence ID
sequencer:唯一一台發號碼牌的機器,每筆單蓋上連續的號碼。sequence ID:那個號碼。流水號的另一個例子:12 章的聊天訊息
④ 跟這章的關係
原書:sequencer 讓撮合「有決定性」,同樣的號碼順序重來一次,結果一模一樣(第 18 頁)。
② 動手玩:照時鐘排,還是照號碼排
照各窗口的時鐘排
照號碼牌排
原書 Step 2Trading flow · Matching engine · Sequencer · Figure 7
撮合引擎要「有決定性」,靠的是 sequencer 的連續序號
這一步要解決的問題很多筆單同時湧進來,引擎怎麼保證每一次都用同一個順序處理?
📖 原書 Matching engine(又叫 cross engine)
- 維護每個 symbol 的 order book
- 配對買賣單:一次配對產生兩筆 execution,買賣各一,要快也要準
- 把成交串流當作市場資料發出去
高可用的撮合引擎必須以決定性的順序產生結果:給定同一串訂單,重播時要產生同一串 execution。這是 HA 的基礎。
📖 原書 Sequencer
讓撮合引擎有決定性的關鍵。每筆進來的單在撮合前蓋 sequence ID;每一對 execution 也蓋。所以有 inbound 和 outbound 兩個實例,各自維護序號,而且必須是連續數字,漏號一眼就看得出來。三個理由:時效與公平、快速復原/重播、exactly-once。
它不只發序號,也是 message queue(一條送單進引擎、一條送成交回 order manager)和訂單與成交的 event store,像接了兩條 Kafka stream;如果 Kafka 的延遲更低、更可預測,其實可以用 Kafka。
動手試:號碼牌漏了一張
到這裡你已經會了小結 2 / 5
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
到這裡你已經會了:一筆單走哪條路、誰先誰後
- 成交紀錄就是 market data;一段時間的成交濃縮成一根 K 棒(開、高、低、收)。
- latency 是等待時間,1 ms = 1,000 µs;只有 critical path 上的步驟會讓客人等。
- sequencer 給每筆單蓋連續的號碼:漏號一眼看出,照號碼重來一次,結果一樣。
下一階要解決的問題
各個元件裡面長什麼樣子?order manager、API、資料模型,以及 order book 要怎麼寫才夠快。
原書 Step 2Order manager · Client gateway · Figure 8–9
Order manager 管狀態;gateway 守門,越輕越好
這一步要解決的問題單子進門後,誰管它的狀態?大門又要做哪些檢查?
📖 原書 Order manager
一端收訂單、一端收成交,管理訂單狀態。從 gateway 收到新單後:
- 送去 risk check:例如使用者一天交易量低於 $1M
- 對 wallet 檢查資金足夠(原書請讀者參考 Digital Wallet 那章)
- 送到 sequencer 蓋序號,再由撮合引擎處理。新單屬性很多,只送必要的欄位以縮小訊息
另一端從 sequencer 收成交,經 gateway 回給經紀商。它要快、有效率、準確;狀態轉換是複雜度的主要來源,真實交易所可能有上萬種情況。原書認為 event sourcing 非常適合(第 34 頁)。
📖 原書 Gateway 在關鍵路徑上、對延遲敏感,要保持輕量。放什麼、不放什麼是取捨;原則是複雜的功能留給撮合引擎和 risk check。
📖 原書 散戶和機構有不同的 gateway,考量是延遲、交易量和安全。做市商提供交易所大量流動性,需要極低延遲。極端例子是 colocation(colo)engine:經紀商在交易所機房租的伺服器上跑交易引擎,延遲就是光從那台機器跑到交易所伺服器的時間(第 47 頁)。
白話:normalization=把各種格式的單整理成同一種;做市商=隨時掛買賣單、讓別人隨時買得到賣得到的公司;流動性=想買想賣時,馬上有人接。
原書 Step 2Market data flow · Reporting flow · Figure 10–11
不在關鍵路徑上的兩條:市場資料要快,報表要準
這一步要解決的問題成交之後,行情和報表怎麼產生?它們不在關鍵路徑上,要求有什麼不同?
📖 原書 Market data flow
MDP 從撮合引擎收成交,從成交串流建出 order book 和 K 線,合稱 market data,送到 data service 給訂閱者。
📖 原書 Reporting flow
Reporter 不在關鍵路徑上,但很重要:交易紀錄、稅務報表、合規報表、交割。交易流程講效率和延遲,reporter 講準確與合規。
常見做法是把進來的訂單和出去的成交拼在一起:新單只有訂單細節,成交通常只有 order ID、價格、數量、狀態;reporter 合併兩者產生報表。
📖 原書 本章的 API 和資料模型放在高階設計之後,因為它們用到高階設計才介紹的概念。下一頁開始是 API。
原書 Step 2API design
四支 RESTful API:下單、查成交、查 order book、查 K 線
這一步要解決的問題經紀商要怎麼跟交易所講話?至少要支援哪些功能?
📖 原書 客戶透過經紀商下單、看成交、看市場資料、下載歷史資料。下面用 RESTful 慣例描述經紀商與 client gateway 之間的介面;資源定義見 Data models。
📖 原書 REST 可能滿足不了避險基金這類機構的延遲需求,它們的專用軟體可能用別的協定;但不管用什麼,下面這些基本功能都要支援。
白話:API=事先約好的點餐窗口;RESTful=用網址加動作(GET 查、POST 新增)溝通的慣例。request/API 的完整版:04 章
讀 API 時注意型別
price、quantity是 Long:價格用整數存(例如以最小跳動單位計)- K 線的
open/close/high/low卻是 Double:同一章裡價格型別不一致 - Order 回應的
status只有 new / canceled / filled,沒有 partially filled,要看filledQuantity
以上是讀碼觀察,不是原書的說法;Triton 對價格型別的看法見第 63 頁。
原書 Step 2Data models · Product, order, execution · Figure 12
三種資料:產品、訂單與成交,order book,K 線
這一步要解決的問題同一份訂單和成交,要存成什麼樣子、存在哪裡?
📖 原書 Product:交易標的的屬性,例如產品類型、交易代號、UI 顯示代號、結算幣別、lot size、tick size。不常變動,主要給 UI 用,放哪個資料庫都可以,而且很好 cache。
白話:lot size=一次最少買幾股;tick size=價格最小跳一格是多少;cache=放在手邊的小抄(完整版:01 章);shared memory=同一台機器上的程式共用的一塊記憶體。
📖 原書 Order 是進來的買賣指令,execution(fill)是出去的配對結果。不是每筆單都有成交;一次配對產生兩筆 execution。
📖 原書 同一份資料,三條流程裡長得不一樣
- 關鍵交易路徑:訂單和成交不存資料庫。在記憶體裡撮合,用硬碟或 shared memory 持久化與分享;具體來說存在 sequencer 裡以便快速復原,收盤後歸檔
- Reporter:寫進資料庫,供對帳、報稅
- MDP:用成交重建 order book 和 K 線
原書 Step 2Data models · Order book · Figure 13
一筆 2,700 股的市價買單,吃掉整層 best ask 再多一張
這一步要解決的問題掛單簿要怎麼存,下單、配對、取消才夠快?
📖 原書 Order book 是某個證券的買賣單清單,依價格層級(price level)組織,是撮合引擎快速配對的關鍵資料結構。高效的 order book 要滿足:
- 常數時間查詢:取得某價位、或某些價位之間的量
- 快速新增/取消/成交,最好 O(1):下新單、取消、配對
- 快速更新:替換訂單
- 查詢 best bid / ask
- 逐一走訪價格層級
白話:常數時間、O(1)=不管板上有幾張單,都只要差不多一步。O(1) 的完整版:13 章第 15 頁
📖 原書 例子裡是一筆 2,700 股 Apple 的大額市價買單:它吃掉 best ask 佇列(100.10)裡全部的賣單,再吃 100.11 佇列的第一張。成交後買賣價差變大,價格上移一檔:best ask 變成 100.11。
原書 Step 2Order book 實作 · Figure 14
把 List<Order> 換成雙向鏈結串列,三個操作都是 O(1)
這一步要解決的問題Figure 13 那面板子寫成程式,哪一個操作會變慢?
class PriceLevel{
private Price limitPrice;
private long totalVolume;
private List<Order> orders;
}
class Book<Side> {
private Side side;
private Map<Price, PriceLevel> limitMap;
}
class OrderBook {
private Book<Buy> buyBook;
private Book<Sell> sellBook;
private PriceLevel bestBid;
private PriceLevel bestOffer;
private Map<OrderID, Order> orderMap;
}
📖 原書 這段符合需求嗎?不符合:private List<Order> orders 是一般 list。改成雙向鏈結串列,刪除類操作(取消、配對)也變 O(1):
- 下新單:加到 PriceLevel 的尾端,O(1)
- 配對:從 PriceLevel 的頭端刪掉,O(1)
- 取消:用
orderMapO(1) 找到那張單;單向串列得從頭走到它前一個才能刪,O(n);雙向串列的單自己有指向前一張的指標,不用走
白話:鏈結串列=每張單手牽著下一張排成一串;雙向=也牽著前一張;Map=用價格或 order ID 直接找到東西的索引。
原書 Step 2 · 動手玩Order book + 撮合 + K 線
自己下單:價格優先、時間優先,成交長成 K 棒
這一步要解決的問題把前面學的串起來:自己下單,看撮合怎麼配、K 棒怎麼長出來。
點一張單可以取消它(灰色是你下的單)。
事件(inbound / outbound 序號)
原書 Step 2Data models · Candlestick chart
K 線:時間到就開一根新的,記憶體要設上限
這一步要解決的問題K 線在程式裡怎麼存?很多股票 × 很多區間,記憶體夠嗎?
📖 原書 K 線是 market data processor 裡另一個關鍵資料結構(和 order book 並列)。用 Candlestick 和 CandlestickChart 兩個 class 建模:區間結束時,為下一個區間建立新的 Candlestick,加到 CandlestickChart 的鏈結串列。
class Candlestick {
private long openPrice;
private long closePrice;
private long highPrice;
private long lowPrice;
private long volume;
private long timestamp;
private int interval;
}
class CandlestickChart {
private LinkedList<Candlestick> sticks;
}
📖 原書 市場資料通常放在記憶體內的欄式資料庫(例如 KDB)做即時分析;收盤後存進歷史資料庫。
白話:欄式資料庫=同一欄的資料存在一起,適合大量統計;ring buffer=頭尾相連、重複使用的固定格子(第 45 頁)。
📖 原書 很多 symbol × 很多區間,很吃記憶體。兩個優化:
- 用預先配置的 ring buffer 放 K 棒,減少新物件配置的次數
- 限制記憶體裡的 K 棒數量,其餘寫到磁碟
細節在 deep dive 的 Market data publisher(第 45 頁)。
動手算:全部留在記憶體要多大?
延伸基礎第 8 階 · p99懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
99 人等 1 分鐘,1 人等 30 分鐘
① 先想像
100 位客人排隊。大部分人等 1 分鐘,偶爾阿姨去接電話,那幾位就要等很久。
你猜猜看:99 位等 1 分鐘、1 位等 30 分鐘,平均等多久?
(99 + 30) ÷ 100 ≈ 1.3。平均只多了一點點,但那位等 30 分鐘的客人會上網罵人。
③ 這叫做 p99
p99:把 100 個等待時間由短到長排好,第 99 名那個數字;意思是「99% 的人不會等超過它」。p50 就是正中間那位。
④ 跟這章的關係
原書:交易所看 p99、甚至 p99.99,不看平均(第 29、44 頁)。
② 動手玩:100 位客人
原書 Step 3Design deep dive · Performance
延遲 = 關鍵路徑上每一段時間的總和
這一步要解決的問題延遲要從數十毫秒壓到數十微秒,要從哪裡下手?
動手試:關鍵路徑的延遲預算
📖 原書 現代交易所長什麼樣子?答案可能嚇到很多人:有些大型交易所幾乎把所有東西跑在一台巨大的伺服器上。延遲不只平均要低,整體也要穩定,衡量穩定的好指標是 p99。
Latency = ∑executionTimeAlongCriticalPath
- 減少關鍵路徑上的任務數:只留
gateway -> order manager -> sequencer -> matching engine,連 logging 都移出去 - 縮短每個任務:減少或消除網路和磁碟;縮短每個任務的執行時間
📖 原書 元件分散在不同伺服器:往返網路延遲約 500 µs,好幾跳加起來到個位數毫秒;sequencer 把事件寫磁碟,就算是循序寫,也要數十毫秒。端到端數十毫秒在早期算不錯,現在不夠了。演進後把延遲壓到數十微秒,經過時間考驗的做法是把所有東西放在同一台伺服器,用 mmap 當 event store 溝通。
原書 Step 3Performance · Figure 15 · mmap
一台伺服器、一條 mmap 訊息匯流排
這一步要解決的問題不走網路、不碰磁碟,同一台機器裡的元件要怎麼互傳訊息?
📖 原書 圖中央那條長方形 mmap,指的是 POSIX 的系統呼叫 mmap(2):把一個檔案映射到 process 的記憶體。
白話:process=電腦裡一個正在跑的程式;POSIX=各家 Unix 系統共同遵守的規格;microservices=把系統拆成很多小服務。
mmap(2)提供 process 之間高效能共享記憶體的機制- 檔案放在
/dev/shm時優勢更大:/dev/shm是記憶體做的檔案系統,對它 mmap,存取共享記憶體完全不碰磁碟 - 現代交易所用它盡量把磁碟存取移出關鍵路徑:用
mmap(2)在伺服器內做一條訊息匯流排,關鍵路徑上的元件在上面溝通,沒有網路、沒有磁碟,送一則訊息低於 1 微秒 - 用 mmap 做 event store,配上 event sourcing,就能在一台伺服器裡做出低延遲的 microservices
🎫 原本櫃台、審核、配對分在三棟大樓,用快遞傳單子;現在三個人坐同一張桌子,中間放一塊白板,寫上去大家馬上看得到。
延伸基礎第 9 階 · single thread懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
一位阿姨慢慢配,還是兩位阿姨搶著配?
① 先想像
櫃台阿姨一次只拿一張單,一張配完才拿下一張。如果請兩位阿姨一起配同一面板子,她們可能同時把同一張票賣給兩個人。
你猜猜看:兩位阿姨一起配同一面板子,要怎麼避免「一票兩賣」?
拿到鑰匙的人才能改板子,另一位得等。等鑰匙、交鑰匙的時間,可能比配對本身還久。
③ 這叫做 single thread、lock
single thread(單執行緒):同一件事只交給一個執行者做,就不用搶鑰匙。lock:那把鑰匙,一次只准一個人改。lock 的完整版:22 章
④ 跟這章的關係
原書:每個元件是一個單執行緒的 loop,還釘在固定的一顆 CPU 上(第 32 頁)。Triton 也同意(第 65 頁)。
② 動手玩:配 20 張單
示意:配一張 1 秒,交一次鑰匙 0.5 秒。
原書 Step 3Application loop · CPU pinning · Figure 16
一個執行緒、釘在一顆 CPU 上、一直轉
這一步要解決的問題每個元件裡面要怎麼跑,才能每一筆都一樣快?
📖 原書 Application loop 在 while 迴圈裡持續 poll 要執行的任務,是主要的執行機制。只有最關鍵的任務交給它,目標是縮短每個元件的執行時間、保證高度可預測(低 p99)。每個方框是伺服器上的一個 process;每個 application loop 是單執行緒,而且釘在固定的 CPU core。
📖 原書 釘在 CPU 上的好處
- 沒有 context switch:CPU 1 完全給 order manager 的 loop
- 沒有 lock、沒有 lock contention:只有一個執行緒在更新狀態
兩者都讓 p99 變低。代價是寫程式更複雜:要仔細分析每個任務花多久,不能讓它佔住 loop 太久,否則會擋住後面的任務。
白話:poll=一直主動去看有沒有新工作;context switch=CPU 被叫去做別的事,回來要重新整理桌面;lock contention=大家搶同一把鑰匙(第 31 頁)。
動手試:10,000 個任務的延遲分布
延伸基礎第 10 階 · event sourcing懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
板子燒了,照筆記本重做一遍
① 先想像
阿姨不只改板子,還在筆記本記下每一件事:「阿明貼售 3,200」「你收 1 張,配給阿明」。板子燒了,照筆記本從頭做一次就回來了。
你猜猜看:筆記本記了 5 件事。照著重做兩次,兩次的板子一樣嗎?
同樣的事、同樣的順序,結果就一樣。這就是第 7 階號碼牌的用處;順序一換,結果就可能不同(右邊試試)。
③ 這叫做 event sourcing、event store
event sourcing:不存「現在的樣子」,存「發生過的每一件事」,要的時候照順序重播。event store:存這些事件的那本筆記本。
④ 跟這章的關係
原書把整個交易所建在 event sourcing 上(第 34–36 頁);Triton 對它的保留在第 57 頁。
② 動手玩:重播筆記本
原書 Step 3Event sourcing · Figure 17
不存「現在的狀態」,存「發生過的每一件事」
這一步要解決的問題出了錯,怎麼知道帳是怎麼一步一步變成這樣的?
📖 原書 Event sourcing 在 Digital Wallet 那章談過。傳統應用把狀態存在資料庫,出事時很難追查:資料庫只有現在的狀態,沒有導致這個狀態的事件紀錄。Event sourcing 改存所有改變狀態的事件,是不可變的 log,這些事件是 golden source of truth。左邊的經典 schema 只知道 order 現在是什麼;右邊依序重播所有事件,就能還原狀態。
動手試:重播到第幾筆?
原書 Step 3Event sourcing design · Figure 18
Gateway、撮合、MDP、reporter 都接在同一個 mmap event store
這一步要解決的問題把 event sourcing 套到整個交易所,元件之間要怎麼接?
📖 原書 用 mmap event store 當 message bus,很像 Kafka 的 pub-sub;沒有嚴格延遲要求的話,Kafka 也可以。外部用 FIX 和交易領域溝通:
白話:pub-sub=發布/訂閱,寫的人只管寫,想看的人自己訂;library=可以直接嵌進程式的現成零件;Kafka 見 19 章。
- Gateway 把 FIX 轉成 FIX over SBE(Simple Binary Encoding),快又緊湊;每筆單以預先定義的格式,透過 Event Store Client 送出
NewOrderEvent - 內嵌在撮合引擎裡的 order manager 從 event store 收到 NewOrderEvent,驗證、加進內部的 order state,再送進 matching core
- 配對成功產生
OrderFilledEvent送進 event store - MDP、reporter 等元件訂閱 event store,各自處理
📖 原書 和高階設計的第一個差別:order manager
它變成可重用的 library,嵌進不同元件。訂單狀態對很多元件都重要;如果用集中式的 order manager 讓別人查、改,會傷延遲,尤其是 reporter 這種不在關鍵路徑上的元件。每個元件自己維護訂單狀態,靠 event sourcing 保證一致而且可重播。
原書 Step 3Sequencer 去哪了 · Figure 19
每個 event store 只能有一個 sequencer:單一寫入者
這一步要解決的問題event sourcing 的設計裡,號碼牌機去哪了?可以有好幾台嗎?
📖 原書 在 event sourcing 設計裡,所有訊息只有一個 event store。Event store entry 裡的 sequence 欄位,就是 sequencer 注入的。
- 每個 event store 只有一個 sequencer。多個 sequencer 是壞做法,它們會搶寫入權;在交易所這麼忙的系統,大量時間會浪費在 lock contention
- 所以 sequencer 是單一寫入者:先排序,再送進 event store
- 和高階設計裡兼做 message store 的 sequencer 不同,這裡的 sequencer 只做一件簡單的事,超快
- 它從每個元件本地的 ring buffer 拉事件,蓋 sequence ID,送進 event store
- 可以有備援 sequencer,主的掛了接手
🎫 號碼牌機只能有一台。兩台同時發號,就要先吵「這一號給誰」,吵架的時間比發號還長。
到這裡你已經會了小結 3 / 5
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
到這裡你已經會了:引擎裡面怎麼又快又穩
- 平均會騙人,要看 p99:最慢那 1% 的人等多久。
- 撮合只交給一個 single thread,就不用搶 lock;原書還把它釘在同一顆 CPU。
- event sourcing 只記發生過的事;照同樣的順序重播,結果一模一樣,sequencer 就是那個順序。
下一階要解決的問題
機器壞了怎麼辦?原書的 hot-warm 與 Raft,以及行情怎麼公平地同時送到每個人手上。
延伸基礎第 11 階 · hot-warm懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
旁邊坐一位不出聲的影子阿姨
① 先想像
配對阿姨旁邊坐一位影子阿姨,看著同一本筆記本,在自己的小板子上跟著配,但不開口宣布成交。
你猜猜看:阿姨突然昏倒,影子阿姨要從哪裡接手?
她一直跟著做,小板子和阿姨的一模一樣。只要從下一件事開始,換她開口宣布就好。
③ 這叫做 hot-warm、failover
hot-warm:hot 是正在說話的主角,warm 是跟著做、隨時能接手的替補。failover:主角倒了,換替補上場。高可用(HA)的完整版:02 章
④ 跟這章的關係
原書用 hot-warm 加 Raft 做高可用(第 39–41 頁)。Triton 會再追問:影子阿姨有沒有對答案?(第 61 頁)
② 動手玩:主角昏倒
原書 Step 3High availability · Figure 20
Hot-warm:兩個引擎吃同一串事件,只有 hot 的會說話
這一步要解決的問題撮合引擎是最不能停的元件。它掛了,怎麼幾乎立刻恢復?
📖 原書 目標 4 個 9(99.99%):每天只能停機 8.64 秒,服務掛了要幾乎立刻恢復。
- 先找出 SPOF:撮合引擎掛了是災難,所以在主實例旁放冗餘實例
- 偵測故障、決定 failover 要快
- Stateless 服務(client gateway)加機器就能水平擴充;stateful 元件(order manager、撮合引擎)要能在 replica 之間複製狀態
📖 原書 Hot 引擎是主實例;warm 引擎接收並處理完全相同的事件,但不送任何事件到 event store。Hot 掛了,warm 立刻接手開始送。Warm 掛了,重啟後總能從 event store 還原所有狀態。Event sourcing 的決定性讓還原簡單又準確。除了監控硬體和 process,也可以從撮合引擎送 heartbeat,沒按時收到就可能有問題。
📖 原書 問題是這只在一台伺服器內有效。要跨機器、甚至跨機房,就是整台伺服器 hot 或 warm,整個 event store 從 hot 複製到所有 warm,這需要時間;可以用 reliable UDP 有效率地廣播給所有 warm,例子是 Aeron。
白話:SPOF=壞了就全停的那一個點;stateless/stateful=身上不記事/記著狀態;heartbeat=定時說「我還活著」;reliable UDP=自己補上重傳的快速傳法。
原書 Step 3Fault tolerance · RTO · RPO
連 warm 也掛了怎麼辦?先搞清楚什麼叫「掛了」
這一步要解決的問題連 warm 也掛了怎麼辦?誰決定切換、多久內要恢復、能掉多少資料?
📖 原書 Hot-warm 相對簡單、也還算可用;但 warm 也掛呢?機率低但後果是災難,要有準備。大型科技公司的做法是把核心資料複製到多個城市的機房,降低地震、大停電的風險。要回答的問題:
- 主實例掛了,怎麼、何時決定 failover?
- 備援之中怎麼選 leader?
- 需要多少復原時間(RTO)?
- 哪些功能要復原(RPO)?系統能在降級狀態下運作嗎?
📖 原書 「掛了」沒那麼單純
- 系統可能誤報,造成不必要的 failover
- 程式 bug 讓主實例掛掉;同一個 bug 在 failover 後也讓備援掛掉;所有備援都被 bug 打倒,系統就不可用了
建議:新系統剛上線時可能要手動 failover;累積足夠的訊號和維運經驗、對系統更有信心後,才自動化偵測。Chaos engineering 能更快找出邊角案例。
白話:降級=先只提供最重要的功能;chaos engineering=故意弄壞東西來演練。
📖 原書 RTO:可以停多久
業務可以容忍停機多久而不受重大傷害。交易所要秒級 RTO,一定要自動 failover。做法是依優先順序把服務分類,定義降級策略維持最低服務水準。
📖 原書 RPO:可以掉多少資料
交易所不能接受資料遺失,RPO 接近零。用 Raft 有很多份資料,保證叢集節點間的狀態共識;leader 當機,新 leader 應該能立刻運作。
動手想:同一個 bug
原書 Step 3Fault tolerance · Raft · Figure 21–22
五台機器、各自一份 event store,過半數(3 票)才算數
這一步要解決的問題決定要切換之後,誰接手?五台機器怎麼選出新的 leader?
📖 原書 決定要 failover 後,誰接手?這是被充分理解的問題,有很多久經考驗的 leader election 演算法,原書用 Raft 為例。Leader 把資料送給所有 follower;Raft 執行操作需要的最少票數是 (N/2 + 1),五台就是 3。Follower 透過 RPC 收新事件,存進自己的 mmap event store。
白話:leader/follower=帶頭寫的那台/跟著抄的那幾台(完整版:19 章);RPC=呼叫另一台機器上的功能;term=任期。
- Leader 送 heartbeat(沒有內容的 AppendEntries)給 follower
- Follower 一段時間沒收到 heartbeat,觸發 election timeout,發起新選舉
- 第一個逾時的 follower 變成 candidate,向其他人要票(RequestVote);拿到過半數就成為新 leader
- 如果它的 term 比新節點低,就不能當 leader
- 多個 follower 同時變 candidate 叫 split vote:選舉逾時,重新選
- Raft 把時間切成任意長度的 term,代表正常運作與選舉
原書 Step 3Matching algorithms · 偽碼
撮合偽碼:先檢查序號,再分 NEW / CANCEL,FIFO 配對
這一步要解決的問題前面講的 FIFO 撮合,寫成程式長什麼樣子?
Context handleOrder(OrderBook orderBook, OrderEvent orderEvent) {
if (orderEvent.getSequenceId() != nextSequence) {
return Error(OUT_OF_ORDER, nextSequence);
}
if (!validateOrder(symbol, price, quantity)) {
return ERROR(INVALID_ORDER, orderEvent);
}
Order order = createOrderFromEvent(orderEvent);
switch (msgType):
case NEW:
return handleNew(orderBook, order);
case CANCEL:
return handleCancel(orderBook, order);
default:
return ERROR(INVALID_MSG_TYPE, msgType);
}
Context handleNew(OrderBook orderBook, Order order) {
if (BUY.equals(order.side)) {
return match(orderBook.sellBook, order);
} else {
return match(orderBook.buyBook, order);
}
}
Context handleCancel(OrderBook orderBook, Order order) {
if (!orderBook.orderMap.contains(order.orderId)) {
return ERROR(CANNOT_CANCEL_ALREADY_MATCHED, order);
}
removeOrder(order);
setOrderStatus(order, CANCELED);
return SUCCESS(CANCEL_SUCCESS, order);
}
Context match(OrderBook book, Order order) {
Quantity leavesQuantity = order.quantity - order.matchedQuantity;
Iterator<Order> limitIter = book.limitMap.get(order.price).orders;
while (limitIter.hasNext() && leavesQuantity > 0) {
Quantity matched = min(limitIter.next.quantity, order.quantity);
order.matchedQuantity += matched;
leavesQuantity = order.quantity - order.matchedQuantity;
remove(limitIter.next);
generateMatchedFill();
}
return SUCCESS(MATCH_SUCCESS, order);
}
📖 原書 偽碼用的是 FIFO(First In First Out)撮合演算法:某個價位先進來的單先配對,最後進來的最後配。第一行就是第 18 頁的序號檢查:順序不對,直接回 OUT_OF_ORDER。
原書 Step 3 · 動手玩Matching algorithms · FIFO · FIFO with LMM
同一價位、同一批掛單,換一種分法,誰拿到就不一樣
這一步要解決的問題同一價位的單不夠分時,除了 FIFO,還有哪些分法?
動手比:三種分法
FIFO 與 FIFO + LMM 是原書提到的;Pro-rata(依掛單量比例分)是原書引用的 CME 文件裡的另一種,原書沒有說明,這裡只作比較。LMM 比例 40%、pro-rata 先無條件捨去再把零頭依 FIFO 補,都是示範設定。
📖 原書 撮合演算法有很多種,這些演算法常用在期貨交易。例如 FIFO with LMM(Lead Market Maker):在 FIFO 佇列之前,先按預定比例分一定數量給 LMM;這是 LMM 公司和交易所談來的特權。更多演算法見 CME 網站。撮合演算法也用在其他場景,典型的是 dark pool。
白話:期貨=約好未來某天用某個價格買賣;dark pool=不公開掛單簿的私下撮合場所;CME=芝加哥商品交易所。
文組翻譯
FIFO 是排隊買雞排:先到先拿。LMM 是「贊助商保留席」:開賣前先分一部分給簽約的人,剩下才排隊。Pro-rata 是按「你訂了幾份」比例分:訂得多分得多,不管誰先到。
原書 Step 3Determinism · Figure 23
功能決定性:順序對了結果就一樣;延遲決定性:每筆都一樣快
這一步要解決的問題「每次都一樣」有兩種意思:結果一樣,速度也一樣。
📖 原書 功能決定性前面講過:sequencer 和 event sourcing 保證事件以相同順序重播,結果就相同。有了它,事件實際發生的時間多數時候不重要,重要的是順序。Figure 23 把時間軸上不均勻的離散點換成連續的點,重播/復原的時間可以大幅縮短。
📖 原書 延遲決定性:每一筆交易通過系統的延遲幾乎相同,這對業務很關鍵。衡量方法是 p99,更嚴格是 p99.99,可以用 HdrHistogram 計算。p99 低,交易所就對幾乎所有交易提供穩定效能。大幅的延遲波動要追查,例如 Java 的 safe point;HotSpot JVM 的 Stop-the-World GC 是有名的例子。
白話:GC(garbage collection)=程式自動清垃圾;Stop-the-World=清的時候整個程式暫停;safe point=程式停下來讓 GC 動手的時間點。
動手試:平均值會說謊
📖 原書 關鍵交易路徑的 deep dive 到這裡結束,接下來看交易所其他部分幾個有趣的面向。
原書 Step 3Market data publisher optimizations · Figure 24 · Ring buffer
MDP:K 線分三種粒度,記憶體用預先配置的 ring buffer
這一步要解決的問題行情的資料結構怎麼省記憶體?L2、L3 為什麼有人要付錢買?
動手試:8 格的 ring buffer
📖 原書 從撮合演算法看得出 L3 讓人更了解市場。一天的 K 線可以從 Google Finance 免費拿,但更細的 L2/L3 很貴,很多避險基金透過交易所的即時 API 自己錄,建自己的 K 線和技術分析圖。
📖 原書 MDP 從撮合引擎收結果,重建 order book 和 K 線,再發給訂閱者。重建 order book 和撮合偽碼類似。MDP 是分級服務:散戶預設只能看 5 檔 L2,要 10 檔得加錢。MDP 的記憶體不能無限擴充,K 線要有上限。
📖 原書 Ring buffer(circular buffer)
- 固定大小、頭尾相連的 queue;生產者一直寫,一個或多個消費者拉資料
- 空間預先配置,不需要建立或釋放物件
- 這個資料結構是 lock-free 的
- 還有更多技巧,例如 padding:確保 ring buffer 的 sequence number 不和其他東西擠在同一條 cache line
延伸基礎第 12 階 · multicast懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
一個一個打電話,還是用廣播喇叭?
① 先想像
剛剛成交的價格要告訴 4 位客人。一個一個打電話,第一位永遠先知道;用廣播喇叭,大家同時聽到。
你猜猜看:打一通電話要 1 秒,依序打給 4 位。最後一位比第一位晚幾秒知道?
第 1 位在第 1 秒、第 4 位在第 4 秒,差 3 秒。在交易所,早 1 微秒知道都算「先知道」。
③ 這叫做 unicast、multicast
unicast:一對一地傳,一個一個送。multicast:一次送給一群人,理論上大家同時收到。
④ 跟這章的關係
原書:受監管的交易所要保證所有人同時拿到行情,方法是 multicast 或隨機順序(下一頁)。
② 動手玩:告訴幾位客人
原書 Step 3Distribution fairness · Multicast · Colocation
比別人早 1 微秒看到行情,就像有預言能力
這一步要解決的問題行情發出去的時候,怎麼讓每個人同時收到?
動手試:行情要發給四個訂閱者
📖 原書 受監管的交易所要保證所有接收者同時拿到市場資料。例如 MDP 有一份訂閱者清單,順序由連線先後決定,第一個永遠先收到。結果呢?聰明的客戶會在開盤時搶著排第一。緩解方法:用 reliable UDP 的 multicast 一次廣播給很多參與者;或在訂閱者連線時給隨機順序。
📖 原書 Multicast
- Unicast:一個來源到一個目的地
- Broadcast:一個來源到整個子網路
- Multicast:一個來源到一組主機,可以在不同子網路
同一個 multicast group 的接收者,理論上同時收到。但 UDP 不可靠,datagram 可能沒到所有人;有處理重傳的方案(NACK-Oriented Reliable Multicast)。
白話:UDP=不等回覆、可能掉封包的快速傳法;datagram=UDP 的一個封包;子網路=同一區的一群機器。
📖 原書 Colocation:很多交易所把避險基金或經紀商的伺服器放在同一個機房,下單到撮合引擎的延遲基本上和電纜長度成正比。它不違反公平,可以看成付費的 VIP 服務。
原書 Step 3Network security
公開介面會被 DDoS:原書的五招
這一步要解決的問題公開的行情網頁被灌爆時,怎麼不拖垮交易?
- 把公開服務和資料與私有服務隔離,DDoS 不會影響最重要的客戶;如果提供的是同一份資料,可以有多份唯讀副本隔離問題
- 用 cache 層存不常更新的資料,cache 做得好,多數查詢不會打到資料庫
- 硬化 URL:像
https://my.website.com/data?from=123&to=456,攻擊者改 query string 就能產生很多不同請求;改成https://my.website.com/data/recent比較好,也能在 CDN 層 cache - 有效的 safelist / blocklist,很多網路 gateway 產品有這功能
- Rate limiting 常用來防 DDoS
白話:唯讀副本=只能讀、不能改的影本(01 章);CDN=離使用者最近的接待處,幫你擋掉重複的請求(01 章);rate limiting=門口的保全(04 章);safelist/blocklist=放行名單/黑名單。
📖 原書 交易所通常有一些公開介面,DDoS 是真實的挑戰。
動手試:攻擊者送 1,000 個請求,CDN 擋得住幾個?
原書 Step 4Wrap up · Chapter summary · Figure 25
原書的收尾:最理想的部署,可能是一台巨大的伺服器
這一步要解決的問題讀完整章,最理想的部署長什麼樣子?
📖 原書 讀完本章,你可能會覺得大型交易所的理想部署模型,是把所有東西放在一台巨大的伺服器、甚至一個 process。確實,有些交易所就是這樣設計的!
📖 原書 隨著加密貨幣產業發展,很多加密交易所用雲端基礎設施部署(例如 Coinbase 的 AWS 案例)。有些 DeFi 專案基於 AMM(Automatic Market Making),連 order book 都不需要。雲端生態的便利改變了一些設計、降低入行門檻,一定會為金融世界注入創新能量。
白話:AMM=用公式自動報價、不靠掛單簿配對;DeFi=跑在區塊鏈上的金融服務。
原書到這裡結束。下一頁開始是 Triton 的觀點。
到這裡你已經會了小結 4 / 5
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
到這裡你已經會了:原書的整套交易所
- hot-warm:替補引擎吃同一串事件,主角倒了就接手(failover);跨機器時用 Raft 過半數投票選新 leader。
- 行情要同時送到每個人:用 multicast 或隨機順序;colocation 是公開販售的 VIP 服務,不算不公平。
- 原書的結論:理想的部署可能是一台巨大的伺服器,甚至一個 process。
下一階要解決的問題
原書講完了。Triton 同意哪些?他說「很難做穩」的地方在哪?先複習幾個舊名詞,再爬最後一階。
延伸基礎複習 · Triton 篇會用到的舊名詞懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
Triton 篇的工具箱:別份簡報講過的,一句話帶過
你猜猜看:記帳員每成交一筆就跑一趟銀行(來回 1 分鐘)。今天 600 筆,改成每 100 筆才跑一趟,省下幾趟?
600 筆一筆一趟要 600 趟;每 100 筆一趟只要 6 趟,省下 594 趟。這就是 batch,Triton 篇第 59 頁的主角。
Triton 的 MVP 是「資料庫 + 排隊盒 + 撮合引擎」,所以這幾個舊名詞會一直出現。每一張卡都連到講得最完整的那一份簡報。
延伸基礎第 13 階 · bottleneck懂的人可以跳過
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
三個櫃台、一位阿姨、兩位記帳員:一分鐘出幾張?
① 先想像
轉讓板變成一條龍:櫃台收單,阿姨配對,記帳員把成交寫進帳本。每一站速度不一樣。
你猜猜看:3 位櫃台每分鐘各收 10 張、1 位阿姨每分鐘配 20 張、2 位記帳員每分鐘各記 8 張。整條線每分鐘最多幾張?
記帳員合起來只有 16 張,後面卡住,前面再快也沒用。最慢那一站決定整條線。
③ 這叫做 bottleneck
bottleneck(瓶頸):整條流程裡最慢的那一站,它決定全部的速度。bottleneck 的完整版:02 章
④ 跟這章的關係
Triton:event-based 系統真正的瓶頸是撮合引擎和 DB updater,不是 append(第 57 頁)。
② 動手玩:加人看看
阿姨只能有一位:第 9 階說過,兩位搶著配反而更慢。
Triton 觀點總覽 · 084 · 044
核心設計同意;複雜度和「很穩」的說法,存疑
「We focus on solving actual real-world problem, Not on passing system design interview」🗣️ Triton 本人說 084-order matching-system design.pdf.md · 第 2 頁 Preface
「matching engine 通常都有 existing product 不會需要自己來 from scratch to implementation」🗣️ 044 · 課堂錄音的自動轉錄(ASR),[00:00:00]
「Event-based architecture gives ultra-high performance But – limited to specific use-case. – Super complex – Super hard to be truly robust」🗣️ 084 · 第 22 頁 Conclusion
044 是一場約三小時課程的語音轉錄,錯字很多(例如把 matching engine 轉成 magic engine)。這份簡報只引用意思清楚的句子、附時間碼,並標明是轉錄;聽不清的段落不引用。
先猜再看:原書說單執行緒 + event sourcing「快、沒有 lock、復原容易」。你猜 Triton 同意哪一句?
他同意核心設計很快,自己的 MVP 也長這樣;但他說 lock 只是搬家、而且很難做穩。下面三張卡依序揭曉。
① 同意:每檔股票一個單執行緒引擎、FIFO、批次
Triton 的 MVP 架構是一群 engine,前面接「FIFO MQ by CommodityID」,撮合本身是單執行緒、零 DB IO,事件用 BATCH 處理。和原書的 sequencer + application loop 是同一個核心。084 · 044 · 050 → 第 54–59 頁
② 存疑:event-based 不是沒有 lock,也不是很穩
「The is a LOCK on MQ FIFO channel」;真正的瓶頸是撮合引擎和 DB updater;每個步驟之間當機都要想過。084 · 044 · 049 · 051 → 第 56、57 頁
③ 給一個笨但會動的復原法
「Stupid(but working) approach」:等結果都寫回 DB,從 DB 的 Order 重建 orderbook 再重啟;課堂上再升級成收 order 和 result 的 standby engine,還能抓出「沒死但算錯」。084 · 044 → 第 60–61 頁
Triton 觀點084 第 5–11 頁 · MVP stock exchange
Triton 的 MVP:DB 是真相,撮合引擎只管 orderbook
這一步要解決的問題如果是 Triton 自己做,最小可行的交易所長什麼樣子?真相放在哪裡?
- Placing OrderOn WebService:BUY 時
User.availableBalance -= quantity * price;SELL 時UserPosition.availableQuantity -= quantity;Create Order Record with status = INITIAL, createTs = now();Persist into database;Send Order to MQ;Update Order Record Status INITIAL --> OPEN - Matching EngineFor every incoming order:Match with top orders in orderbook;If order not fully matched, store into orderbook;If there is matching, send MatchingResult to downstream MQ;Send orderbook updates to data-feed;Ack the message
- Database UpdaterFor every incoming MatchingResult:Begin TX,update Order, User, UserPosition accordingly,Commit TX;Ack the message
- Cancel OrderCannot update database directly;Send Order Cancellation Event to Matching Engine;Matching Engine remove order from OrderBook and send canceled order to downstream;Database Updater restore availableBalance and availableQuantity
🗣️ 用字照 084 第 8–11 頁原文(英文),排版整理成一列一個元件。🗣️「每一個Matching Engine的Instant,它只會做單一的Stock的」044 [00:50:56],ASR
Triton 觀點 · 對照原書084 第 4–6 頁 · API 與 schema
兩種解法:記憶體 + event store,或 RDBMS + FIFO MQ
這一步要解決的問題Triton 的 MVP 和原書,一格一格怎麼對?
| 問題 | 📖 原書 | 🗣️ Triton 084 |
|---|---|---|
| 誰決定順序 | Sequencer 蓋連續序號 | FIFO MQ by CommodityID |
| 撮合的並行單位 | 每個 symbol 一本 order book,application loop 單執行緒 | 每個 engine 只做一檔股票,「The matching operation is still in single thread」 |
| 資金凍結 | Order manager 查 wallet,掛單時凍結資金 | 下單時扣 availableBalance / availableQuantity,DB updater 結算或還原 |
| 關鍵路徑碰不碰 DB | 不碰:訂單與成交存在 sequencer,收盤後歸檔 | 撮合前、撮合後都寫 DB(Step 1、3),撮合本身零 DB IO |
| 真相在哪裡 | Event store(mmap),重播得到狀態 | Main DB;orderbook 可以從 DB 的 Order 重建 |
| 取消 | handleCancel 在引擎裡移除 | 「Cannot update database directly」,送 cancellation event 進引擎 |
| 市場資料 | MDP → data service → broker | Engine → Datafeed → WebSocket Cluster |
| 報表 / 結算 | Reporter 寫 DB | Post-Matching DB updater,PK {commodityID, createTs} 的 MatchingResult |
🗣️ MVP stock exchange API 084 第 5 頁
POST /v1/order
action: BUY / SELL
type: LIMIT / MARKET
stockCode
quantity
PUT /v1/order/{orderID}
Allows update status from PENDING to CANCELLED
GET /v1/order
Return list of orders
with status = OPEN / COMPLETED / CANCELLED
GET /v1/user/{userID}
Return positions, totalBalance, availableBalance🗣️ Database schema 084 第 6 頁
Commodity PK: commodityID sellPrice, buyPrice
User PK: userID totalBalance, availableBalance
UserPosition PK: {userID, commodityID} quantity, availableQuantity
Order PK: orderID userID, action, orderType, commodityID,
quantity, unmatchedQuantity, price, status, createTs
MatchingResult PK: {commodityID, createTs}084 第 4 頁:MVP 的 OrderBook 是「Two priorityQueue of []Order (one for BUY side, one for SELL side)」。044 [00:09:03] 強調這只是 MVP,真正的交易所資料結構複雜得多;原書的 PriceLevel + 雙向鏈結串列就是那個「複雜得多」的版本。
Triton 觀點 · 動手玩044 [00:26]–[01:00] · 為什麼要 INITIAL 再轉 OPEN
「Super hard to be truly robust」:在哪一步當機?
原書這樣做會出什麼事?原書用 sequencer 一句「exactly-once」帶過。如果訂單要先寫 DB、再送 MQ,剛寫完 DB 就當機呢?
DB 有紀錄、MQ 沒收到。要有人回頭掃、補送;補送又可能重複,所以下游要去重(去重的完整版:22 章)。
🗣️ 044 的這一段是整堂課最細的地方(以下是轉述,逐字稿雜訊多):AS 先在 DB 寫一筆 INITIAL,送進 MQ 後才改成 OPEN。在中間當機,DB 留下一筆 INITIAL,背景工作每分鐘掃一次,看到超過五分鐘的 INITIAL 就重做;但它不知道 MQ 到底收到沒,所以下游可能收到同一張單兩次,撮合引擎要記住過去五分鐘的 order ID 去重,DB updater 也要去重。Triton 說這其實就是 two-phase commit。
「因為 we are not writing a hard real-time system」🗣️ 044 [00:38:53],ASR:說明為什麼不能先寫 MQ——撮合和 DB updater 有可能比 DB 寫入還快
「所以你會發現,event system actually 為什麼這麼困難? 因為我差不多每一個 stage 我都要思考,如果準備的時候會發生什麼事?」🗣️ 044 [01:00:03],ASR(「準備」疑為「斷掉」)
🔭 對照原書 原書用 sequencer 的連續序號和 exactly-once 一句帶過(第 18 頁)。Triton 的版本把「DB 和 MQ 是兩個 resource」攤開,每個當機點都要有對應的去重或補送。這和 26 章 Payment 的 2PC 是同一種思考。
Triton 觀點084 第 12 頁 · 049 · 051 · 044
Event-based 沒有 lock?lock 只是搬到 MQ 上了
原書這樣說:application loop 只有一個執行緒,所以「no locks」。你猜 Triton 怎麼說?
排隊本身就要有人維持秩序:MQ 的 FIFO 通道上有一把鎖。append 很快,但整條線的速度看最慢的那一站(第 13 階)。
「Misconception on high performance The event-based architecture has no LOCK – The is a LOCK on MQ FIFO channel to maintain data integrity Only APPEND is involved – Yes, but the bottleneck is the matching engine and database updater – The matching operation is still in single thread」🗣️ Triton 本人說 084 · 第 12 頁(「The is」照原文)
「So, event-based system, many people will say, event-based system performance will be better. I will say, yes, on special case, only.」🗣️ 044 [01:06:06],ASR
「channel底層是有 mutex保護的,這代表:你使用 channel,就有一點點效能損失在 channel 上」「看起來用 ring buffer 再配mutex 就能自己寫出來 – 能用 library 就千萬絕對別自己寫」🗣️ 049-concurrency-demo.pdf.md · 第 20、33 頁
動手試:木桶理論,最短那片決定流量
🗣️「木桶能載多少水,是最矮那片木板來決定 – 你的系統能支持多少流量,是最弱的環節來決定」051 · 第 3 頁
🔭 對照原書 原書說 application loop「No locks」,是指一個 loop 裡面只有一個執行緒改狀態;它自己也承認多個 sequencer 會「fight for the right to write」,所以改成單一寫入者(第 36 頁)。兩邊其實同意:同步點一定存在,差別是 Triton 提醒不要把「append 很快」誤當成「整個系統很快」。
Triton 觀點 · 動手算084 第 13–14 頁 · 044 [01:21]–[01:36] · 050
為什麼撮合引擎快:orderbook 不動,動的只有指令和結果
先猜再看:如果不用撮合引擎,改成每檔股票一把鎖,拿鎖、放鎖各一次 0.5 ms 的網路來回。一檔股票每秒最多幾筆?
一筆光等 IO 就要 1 ms,1 秒 ÷ 1 ms = 1,000 筆。撮合本身才幾微秒,時間全花在等。
「The whole Orderbook is stored in matching engine – Likely will be cached in CPU L2 cache Only movement of instructions and results, not the Orderbook data.」🗣️ Triton 本人說 084 · 第 13 頁
「The operation is split into 3 steps – Pre-matching database operations – Order matching – Post-matching database operations Step 1 and Step 3 are very slow – But can be processed in PARALLEL Step 2 is in single-thread – But involves zero database IO – MQ IO is sequential and fast」🗣️ 084 · 第 14 頁
🗣️「Modern main ram latency: ~100ns(at 2025)」「In 100ns, CPU can execute ~300 cycles」「Share nothing between workers」050 · 第 14–15 頁;🗣️「"Single worker" = each stockCode will serviced by SINGLE thread only」050 · 第 10 頁(例子是股價查詢,不是交易所)
動手算:不用撮合引擎,改用「每檔股票一把鎖」
🗣️ 044 轉述 不用 event-based 也做得出來:每檔股票一把 FIFO 的 global lock(lock server),開 DB transaction、扣錢、拿鎖、撮合、放鎖。好處是「非常非常非常容易寫」,壞處是時間都浪費在 IO latency:拿鎖、放鎖各一次網路來回。
「很多High Performance 系統 今天最卡的 重來都是 不是Io Bandwidth 而是Io Latency」🗣️ 044 [01:36:12],ASR(「重來」應為「從來」)
Triton 觀點 · 動手玩084 第 15 頁 · 049 · 044 [01:39]–[01:54]
一筆一筆做 vs 一批一批做:IO latency 只付一次
先猜再看:每次 IO 來回 1 ms,一筆一筆做,每秒最多 1,000 筆。改成 2,000 筆一批一起送,會怎樣?
2,000 筆只付一次 1 ms,每秒可處理的量改由 CPU 決定;代價是先到的要等整批湊齊。下面把每批筆數拉大驗證。
每筆 CPU 工作抓 2 µs;數字是示意。批次不是免費的:最後一筆要等整批湊齊或逾時才一起送。
「Instead of processing the incoming event one-by-one – The matching engine / database updater can process events in BATCH – MASSIVELY reduce IO latency」🗣️ Triton 本人說 084 · 第 15 頁
「現在每 2000 筆資料才會做一次 redis bulk action – 所以每 2000 次才會有一次 network latency – 所以每 2000 次才會有一次 context switching」🗣️ 049 · 第 14 頁(例子是 log 分析寫 Redis)
🗣️ 044 的補充 DB updater 批次,幫助沒那麼大
課堂上 Triton 說 DB updater 也可以把幾筆 MatchingResult 包在同一個 transaction 少做幾次 begin / commit,但對整體效果幫助不大,「因為Database Updata 它自然就可以In Parallel來工作」;真的卡在 DB updater,「你單純拍多一點的Machine,要更多的Worker同一時間來工作就好」。044 [01:51:18]–[01:54:17],ASR
🔭 對照原書 原書沒有「batch」這個字,但它的 ring buffer、mmap、application loop 都是同一個目標:別讓每一筆都付一次 IO 的等待。Triton 044 [01:39]–[01:45] 講的 Kafka / RabbitMQ consumer 預先 buffer 好幾則、非同步 ack,也是同一件事。
Triton 觀點 · 動手比084 第 17 頁 · 044 [01:57]–[02:27]
「Stupid(but working)」:撮合引擎死了,從 DB 重建 orderbook
先猜再看:原書用 hot-warm + Raft。如果你只有一台撮合引擎,它死了,最笨但一定會動的辦法是?
Triton 的 MVP 裡 DB 才是真相,撮合引擎只是可以重建的那面板子。缺點是 Order 表很大,重建要等。
「How to remove the SPOF(Single point of failure) in matching engine? Stupid(but working) approach: – Upon the death of matching engine – Wait all MatchingResult flushed back to database – Rebuild the OrderBook from database Order data – Restart the matching engine」🗣️ Triton 本人說 084 · 第 17 頁 Open Question-2
「只要 all matching results flashback into database 那麼 database 現在就是 那個single point of truth」🗣️ 044 [01:57:16],ASR(flashback = flushed back)
「因為你的order table 不是少的table 很有可能是整個 database 最大的table」→ 所以改成把 order 和 matching result 也送給 standby engine:「所以只要我的engine go wrong,我的stand-by engine就可以很快去promote as a new engine」🗣️ 044 [02:00:18]、[02:03:19],ASR
🗣️ 044 轉述 一檔股票的 master engine 只有一台,standby 可以有好幾台、都聽同一個 MQ;誰升級用 leader election,「最簡單就是ETCD」[02:24:15]。
動手比:撮合引擎掛掉,要停多久?
| 做法 | 要多寫什麼 | 出處 |
|---|---|---|
| 從 DB 重建 | 幾乎不用:DB 本來就是真相 | 🗣️ 084 |
| Standby engine | 每筆 order + result 多送一份、選 leader | 🗣️ 044 |
| Hot-warm + Raft | event store 複製、Raft、heartbeat | 📖 原書 |
停機時間是示意模型:等 DB updater 消化完 backlog + 掃 Order 表裡還 OPEN 的單、重建 orderbook;standby 與 hot-warm 抓偵測 + 升級的秒數。原書的目標是秒級 RTO(第 40 頁)。
Triton 觀點 · 動手玩044 [02:12]–[02:24]
最難防的不是死掉,是「沒死,但算錯了」
原書這樣做會出什麼事?warm 引擎跟著算、但不說話。primary 沒死、只是算錯了一筆,warm 會發現嗎?
warm 自己的板子是對的,但原書沒說要拿它和 primary 的輸出比。錯的成交照樣發出去。
「最困難保護的是,他沒有死,但是他算的,原來是錯的」🗣️ Triton 本人說 044 [02:18:18],ASR
🗣️ 044 轉述 打電動時遊戲算錯,你最多再開一局;股票帳戶裡明明有一萬美金卻變成幾千,使用者會上 Facebook、找報紙。所以 standby 不只收 order,也收 primary 算出來的 matching result,用來判斷 primary 有沒有「發神經」:CPU 過熱、二加二等於五。更好的做法是 primary 定期(例如每分鐘)把整本 orderbook 打包送到同一個 MQ,讓 standby 比對自己的是不是一模一樣。[02:18:18]–[02:24:15]
🔭 對照原書
原書的 warm 引擎「receives and processes the exact same events but does not send any event out」,也就是它會算,但原書沒有說要比對。Triton 多做的就是把 primary 的輸出也送給 standby,讓「重播結果相同」這個決定性,從「復原工具」變成「偵錯工具」。ECC 等硬體保護在 044 也有提到,但他的重點是架構層也要能抓。
Triton 觀點017 · 065 · HA 的定義
「4 個 9、每天 8.64 秒」:先問 HA 到底是什麼意思
先猜再看:原書說 99.99% = 每天只能停 8.64 秒。交易所一天只開 6.5 小時,用交易時段算,能停多久?
6.5 × 3,600 × 0.0001 ≈ 2.3 秒。分母一換,數字就變;Triton 會先問:你說的 HA 到底是什麼意思?
「傳統上我們談High Availability(以下簡稱HA)我們是指:1. 系統中沒有single point of failure 2. 如果single component掛掉,是不需要人類即時行動。」「有HA不代表系統完全零秒的Downtime, 有HA只代表有single component掛了後系統能自動短時間內回復。(一般來說「短時間」=數分鐘內)」🗣️ Triton 本人說 017-High Availability stateful component vs stateless component.md
「啊,bytebytego他亂說的什麼hot-hot HA;他肯定沒有真正動手做過,不知其相關痛苦,也不知道其中關鍵缺少了什麼東西……」🗣️ 017
017 批評的是 ByteByteGo(原書作者的公司)一篇 LinkedIn 的 HA 貼文,不是針對這一章。那篇貼文的「“4 nines”, 99.99% uptime, means the service can only be down 8.64 seconds per day」和 hot-warm 定義,和本章第 39 頁幾乎一樣,所以放在這裡對照。
🗣️ 交易所本來就會關門 065-lesson0.pdf.md · 第 30 頁
「24x7是指沒有計劃外的 downtime,不是沒有 downtime」「股票交易所不是 24x7的」
動手算:99.99% 是用哪個分母算的?
🔭 依 Triton 原則推論 017 說 stateful component 是 HA 裡麻煩的那個,撮合引擎就是最 stateful 的元件。原書的 hot-warm 定義本身沒問題;Triton 會追問的是:偵測多久、誰決定、同一個 bug 會不會連 warm 一起打死、復原後狀態對不對(第 60–61 頁)。8.64 秒只是算術,不是設計。
Triton 觀點 · 動手玩112 · 價格怎麼存
價格是錢:Decimal 或乘上 10,000 的 int64,別用 Double
原書這樣做會出什麼事?Candles API 的價格是 Double。電腦用 double 算 100.10 − 100.08,會剛好得到 0.02 嗎?
double 是二進位小數,0.1 這種十進位數字存不準。右邊按第一個範例驗證。
「如果是要面對financial data(就是任何跟錢有關的東西)永遠用上十進制(Decimal)方式來儲存和計算,而不要用上floating point(binary)來儲存和計算」「如果你是要固定精度的(像小數後4個位)把你本來的value X10000, 然後再以unsigned int64存進DB 這是一個智障而有效的方案」🗣️ Triton 本人說 112-喵提有關 算錢 的數值儲存.md
「所以常常( A * B / C ) != ( A / C * B ) 所以在做跟錢有關的運算時 你應該先定義好X = A * B / C 然後所有X有關的運算全都用同一算式來算出來」🗣️ 112
📖 原書
Order API 的 price 是 Long、Product 的 tickSize 是 decimal、Candlestick class 是 long,但 Candles API 的 open/close/high/low 是 Double。
🔭 Triton 式
全系統同一種:價格 ×104 存 int64(或 Decimal),K 線也一樣;VWAP 這種除法,公式只定義一次。
動手試:double 與 ×10⁴ 整數
整數放得下多大的價格?
💬 留言補充 Nasdaq 的 32 位元系統價格上限 $429,496.7295,Berkshire A 股逼近上限(2021),討論串裡有一則未署名的回覆寫「謝謝補上案例XD」。112
Triton 觀點084 第 18–22 頁 · 083 · 051 · 065 · 044
股票撮合剛好適合 event-based;多數系統不適合
先猜再看:股票撮合很適合 event-based。售票系統能照抄這套嗎?
下股票單時錢和股票已經在帳戶裡;賣票要先確定「還有票」,大家搶同一行,後面用不用 event sourcing 都一樣卡。
「Revisit on stock exchange When user fire an order, the stock / cash is already in user's account When placing an order, there is no need to update any global object LIMIT order is naturally asynchronous」🗣️ Triton 本人說 084 · 第 21 頁
「In most e-comm system, event-based architecture either – Not compatible – Not worth the complexity」🗣️ 084 · 第 22 頁
🗣️ 反例:售票 084 第 18–20 頁
「Overselling is not acceptable」;要一個 remainingQuantity,Update Item set remainingQuantity -= 1 where itemID = ? and remainingQuantity > 0,而且「MUST BEFORE payment」;熱門商品這個 update 就是 hotspot,「no matter if you are using event sourcing in following stages.」
🗣️ Triton 自己畫的界線
- 「如果你的data常常是microsecond level有二個thread在改動的,這明顯就是HFT的世界(我不熟~)」083
- 「香港交易所用 DB2 來處理每天數百萬筆股票成交」065 · 第 37 頁
- 「如果你的流量真的不是那麼大的話 你這樣石碑的architectural design 很多時候,not worth it」044 [02:27:16],ASR(「石碑」疑為「十倍」複雜度)
🔭 依 Triton 原則推論 一台巨大的伺服器
原書收尾說理想部署可能是「one single process」。Triton 在 051 寫:「單一巨型 binary最大問題 – 一個 while(1) loop bug就系統全滅」。原書自己也承認同一個 bug 會打倒所有備援(第 40 頁)。Triton 不一定反對交易所這樣做(那是他說「不熟」的 HFT 世界),但會提醒:把所有東西放進一個 process,換到的是延遲,付出的是爆炸半徑。
Triton 同意原書做對的地方
這些地方,Triton 和原書站在同一邊
這一步要解決的問題Triton 線不是只批評:這章原書和 Triton 的核心幾乎一致。
✅ 一檔股票,一個單執行緒
原書:application loop 單執行緒、釘 CPU。Triton:「The matching operation is still in single thread」084;不同股票 logically independent,分開 instance 做044。
✅ 順序靠 FIFO,不靠時間
原書:sequencer 連續序號。Triton:「FIFO MQ by CommodityID」084;不是 FIFO 就不公平044。
✅ 撮合時不碰 DB
原書:關鍵路徑在記憶體。Triton:Step 2「involves zero database IO」,orderbook「Likely will be cached in CPU L2 cache」084。
✅ 下單先凍結資金
原書:掛單的錢要 withhold。Triton:availableBalance -= quantity * price084,避免下超過自己錢的單044。
✅ 取消也是事件
原書:handleCancel 在引擎裡。Triton:「Cannot update database directly」「Send Order Cancellation Event to Matching Engine」084。
✅ Standby 跟著吃同一串事件
原書的 warm engine ≈ 044 的 standby engine;Triton 多做一步:連 result 一起收來比對(第 61 頁)。
到這裡你已經會了小結 5 / 5
- order book
- limit / market
- price-time
- market data
- latency
- critical path
- sequencer
- p99
- single thread
- event sourcing
- hot-warm
- multicast
- bottleneck
到這裡你已經會了:Triton 怎麼看這一章
- 同意:一檔股票一條 FIFO 隊伍、一個單執行緒撮合、撮合時不碰 DB、能批次就批次。
- 存疑:lock 沒有消失,只是搬到 MQ 上;真正的 bottleneck 是撮合引擎和 DB updater;每一步當機都要想過。
- 先用笨方法:DB 是真相,引擎死了就從 DB 重建 orderbook;再升級成會「對答案」的 standby。
13 階全部走完了
下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。
一句話記住
一檔股票一條隊伍、一個執行緒;
快很容易,做對、做穩才難。
原書對的地方
- Price-time priority:價格優先、同價 FIFO
- Sequencer 連續序號 → 決定性 → 可重播
- PriceLevel + 雙向鏈結串列,O(1) 下單、配對、取消
- 延遲看 p99,消除關鍵路徑上的網路和磁碟
- 市場資料要同時送達:multicast、隨機順序
Triton 會先問的地方
- 「The is a LOCK on MQ FIFO channel」:沒有 lock 是誤解(084)
- 瓶頸是撮合和 DB updater,不是 append(084、051)
- 每一步當機都要想:INITIAL / OPEN、去重(044)
- 沒死但算錯,誰抓得到?(044)
- 多數系統:Not worth the complexity(084)
Triton 式的做法
- RDBMS 是真相;撮合引擎是可重建的 cache(084)
- 撮合前後的 DB 工作平行化,撮合本身單執行緒(084)
- 批次處理,IO latency 一批只付一次(084、049)
- 先用笨方法:從 DB 重建 orderbook;再升級 standby(084、044)
- 價格 ×104 存 int64 或 Decimal(112)
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源(materials/core)與原書對照
Triton 本人的講義 / 文章
- 084-order matching-system design.pdf.md — 第 2 頁 Preface;第 4 頁 MVP OrderBook(two priorityQueue);第 5 頁 API;第 6 頁 schema;第 7 頁架構;第 8–11 頁 Placing Order / Matching Engine / Database Updater / Cancel Order;第 12 頁 Misconception(「The is a LOCK on MQ FIFO channel」);第 13–15 頁 High performance 1–3(L2 cache、3 steps、BATCH);第 16–17 頁 Open Question(multi-thread、SPOF「Stupid(but working)」);第 18–21 頁售票與 Revisit;第 22 頁 Conclusion
- 044-[00-00-00] 我們主要談的是event-based architecture….md — 課堂錄音的自動轉錄(ASR),雜訊多,只引意思清楚的句子並附時間碼:[00:00:00] existing product、[00:38:53] hard real-time、[00:50:56] 一個 instance 一檔股票、[01:00:03] 每個 stage 都要想、[01:06:06] special case only、[01:36:12] IO latency、[01:51:18]–[01:54:17] DB updater 批次與平行、[01:57:16]–[02:27:16] SPOF、standby、ETCD、「沒有死但算錯」、not worth it;其餘為轉述
- 017 HA 定義、ByteByteGo hot-hot · 112 Decimal、×10000 int64、
X = A * B / C· 049 第 14、20、33 頁 bulk 2000、channel 與 mutex · 050 第 10、14–15 頁(只引 Triton 自己的段落,不引「from chatGPT」那段)· 051 第 3、17、20 頁 木桶、hotspot、單一巨型 binary · 065 第 30、37 頁 24x7、HKEX DB2 · 083 HFT「我不熟」、optimistic lock 的適用場景
💬 作者未標示:112 的 Nasdaq 32-bit 案例(留言者補充)。不引用:050 的「Recommended Architecture(from chatGPT)」段、112 中段的簡體 AI 段落、187–195(第三方與 AI 生成)。169 是 083 的重複檔。
一個可以直接問自己的問題
你的撮合引擎在下一秒當機,重啟後 orderbook 從哪裡來?如果它沒有當機、只是算錯,誰會第一個發現?
原書對照
Alex Xu & Sahn Lam, System Design Interview Vol.2 Ch.13。開頭與 Step 1 需求、非功能需求(第 8 頁);規模、Figure 1、估算(9);Business 101:broker、institutional、limit / market order(10);L1–L3 與 Figure 2–4(12);K 線 Figure 5、FIX(13);High-level design 與 Figure 6(16);Matching engine、sequencer、Figure 7(18);Order manager、client gateway、Figure 8–9(20);Market data flow、reporting flow、Figure 10–11(21);API design(22);Product / order / execution、Figure 12(23);Order book、Figure 13(24);Order book 程式碼、Figure 14(25–26);Candlestick 程式碼(27);Performance(29);Figure 15、mmap(30);Application loop、Figure 16(32);Event sourcing、Figure 17(34);Figure 18(35);Sequencer、Figure 19(36);High availability、Figure 20(39);Fault tolerance、RTO、RPO(40);Raft、Figure 21–22(41);Matching algorithms(42–43);Determinism、Figure 23(44);MDP optimizations、Figure 24(45);Fairness、multicast、colocation(47);Network security(48);Wrap up 與心智圖(49)。25 張圖都依原書圖說、alt 與內文重繪;API 與程式碼照錄。
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 13 階:order book(4)、limit / market(5)、price-time(6)、market data(11)、latency(14)、critical path(15)、sequencer(17)、p99(28)、single thread(31)、event sourcing(33)、hot-warm(38)、multicast(46)、bottleneck(52);舊名詞複習(51);小結(7、19、37、50、66);名詞小卡(68)。轉讓板與人名是虛構的示範情境,延伸基礎頁的數字是示意。