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 階。每一階只用前面講過的東西。

  1. 1order book掛單簿
  2. 2limit / market限價/市價
  3. 3price-time先比價再比先來
  4. 4market data成交白板・K 線
  5. 5latency等多久・微秒
  6. 6critical path一定得走的路
  7. 7sequencer號碼牌機
  8. 8p99最慢的那 1%
  9. 9single thread一個阿姨專心配
  10. 10event sourcing只記發生過的事
  11. 11hot-warm影子阿姨
  12. 12multicast大家同時聽到
  13. 13bottleneck最慢的那一站

第 1–3 階 · 一面轉讓板

要回答:買賣單怎麼排?誰先配到?

第 4–7 階 · 行情、延遲、號碼牌

要回答:一筆單走哪條路?誰先誰後?

第 8–10 階 · 引擎裡面

要回答:怎麼每筆都一樣快?出錯能重來?

第 11–12 階 · 備援與公平

要回答:引擎倒了誰接手?行情怎麼同時送到?

第 13 階 · Triton 的看法

要回答:真正卡住的是哪一站?

全程只用一面板子:週末演唱會的票券轉讓板(虛構)

一張便利貼 = order整面板子 = order book櫃台阿姨 = matching engine號碼牌機 = sequencer阿姨的筆記本 = event store成交白板 = market data影子阿姨 = warm engine

票價都是 3,000–3,500 元,數字小到能心算。每爬 2–4 階,有一頁「到這裡你已經會了」。

延伸基礎第 1 階 · order book懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

轉讓板上還沒成交的便利貼,就是一本「簿子」

① 先想像

想賣票的人貼黃色「售」便利貼,想買的人貼綠色「收」便利貼。沒人接手的便利貼,就一直留在板上。

你猜猜看:板上「收」有 3,000、3,100;「售」有 3,200、3,300。出價最高的「收」和最便宜的「售」差多少?

③ 這叫做 order book、bid / ask

order book:還沒成交的買單和賣單清單,就是這面板子。bid / ask:出價最高的「收」/開價最低的「售」。

④ 跟這章的關係

交易所每檔股票(原書叫 symbol)各有一本 order book。整章就是把這面板子做到每秒 20 萬筆。

② 動手玩:自己貼一張

—最高的「收」—最低的「售」—中間差多少

延伸基礎第 2 階 · limit / market懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

「貴了就不要」和「多少錢都要」

① 先想像

你想收 3 張票。你可以說「最多出 3,300,貴了就算了」,也可以說「多少錢都好,現在就給我」。

你猜猜看:板上「售」只有 3,200、3,300、3,500 各 1 張。你說「現在就要 3 張」,一共付多少?

③ 這叫做 limit order、market order

limit order(限價單):指定價格,超過就不買;可能要等、可能只買到一部分。market order(市價單):不指定價格,馬上用板上現有的價格成交。

④ 跟這章的關係

原書的需求只做 limit order(第 8 頁),但 Figure 13 用一筆大額 market order 舉例(第 24 頁)。

② 動手玩:收 1–3 張

—馬上買到—一共付—貼在板上等

延伸基礎第 3 階 · price-time懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

兩張 3,200 的票,先配給誰?

① 先想像

阿明 09:02、小華 09:05 都貼了「售 3,200」;阿美 09:01 貼「售 3,300」。你出 3,300 要收 1 張。

你猜猜看:你出 3,300 收 1 張,櫃台阿姨配給誰?

③ 這叫做 matching engine、price-time priority

matching engine:負責配對買賣的櫃台阿姨(一支程式)。price-time priority:先比價格,同價再比誰先到,也就是 FIFO(先進先出)。

④ 跟這章的關係

原書的撮合偽碼就是 FIFO(第 42 頁)。「誰先到」要怎麼記,第 7 階揭曉。

② 動手玩:買家一位一位來

0買家們一共付

到這裡你已經會了小結 1 / 5

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

到這裡你已經會了:一面轉讓板怎麼運作

下一階要解決的問題

真的交易所要做多大?先看原書在面試一開始問了什麼、估出每秒幾筆。

原書 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 億筆單,換成每秒是多少?這個數字決定撮合引擎要多快。

📖 原書 Figure 1Largest stock exchanges(原圖是依市值決定大小的世界地圖;這裡只畫出區域與名稱,大小僅示意)(依原書內容重繪)

📖 原書 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懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. 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 連排隊的每一張單都看

這一步要解決的問題行情要給多細?只看最上面兩張便利貼,還是整面板子、連排隊順序都看?

📖 原書 Figure 2Level 1 data:best ask / best bid 與數量(依原書內容重繪)

📖 原書 美股報價分三層: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

這一步要解決的問題一段時間的成交怎麼濃縮成一張圖?交易所之間又用什麼格式溝通?

📖 原書 Figure 5A single candlestick chart(依原書內容重繪)

📖 原書 K 線表示一段時間的價格:open、close、high、low。常見區間是 1 分鐘、5 分鐘、1 小時、1 天、1 週、1 個月。

📖 原書 FIX(Financial Information eXchange)protocol 1991 年建立,是交換證券交易資訊的廠商中立通訊協定。原書的範例:

點一個欄位看它的意思。

原書只給訊息本身、沒有逐欄解釋。欄位名稱依 FIX 4.2 規格補上;代碼值只解釋有把握的幾個。

白話:protocol=雙方事先約好的訊息格式;廠商中立=不屬於任何一家公司,大家都能用。

延伸基礎第 5 階 · latency懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

從交出便利貼到聽見「成交」,等了多久?

① 先想像

你把便利貼交給櫃台,到阿姨跟你說「成交了」,中間那段等待,就是這一階的主角。

你猜猜看:1 毫秒是 1 微秒的幾倍?

③ 這叫做 latency、µs(微秒)

latency(延遲):從送出到收到回覆,等了多久。µs(微秒):百萬分之一秒;ms(毫秒)是千分之一秒。記憶體、硬碟、網路誰快的完整版:02 章

④ 跟這章的關係

原書要求往返延遲到毫秒級、而且要穩(第 8 頁);deep dive 會一路壓到微秒(第 29 頁)。

② 動手玩:拿一件事當尺

長條用「數量級」畫(每多一格是 10 倍),不然最短那條會看不見。眨眼約 100 ms 是示意,其他三個量級照原書。

延伸基礎第 6 階 · critical path懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

哪些步驟會讓你等,哪些不會?

① 先想像

你的便利貼要經過:櫃台收單 → 審核有沒有錢 → 抽號碼牌 → 阿姨配對,才知道成交。旁邊有人抄白板、記帳,你不用等他們。

你猜猜看:收單 2 分、審核 3 分、抽號 1 分、配對 1 分;抄白板 5 分、記帳 10 分。你最少要等幾分鐘?

③ 這叫做 critical path

critical path(關鍵路徑):一筆單從進來到成交,一定要走的那一串步驟。你等多久,就是這條路上每一段加起來。

④ 跟這章的關係

原書的關鍵路徑是 gateway → order manager → sequencer → matching engine(下一頁 Figure 6);連寫日誌(logging)都要移出去(第 29 頁)。

② 動手玩:把步驟移出你的路

—你要等—在旁邊做、不擋你

原書 Step 2High-level design · Figure 6

三條流程:交易(關鍵路徑)、市場資料、報表

這一步要解決的問題一筆單從客戶的手機到成交回報,經過哪些元件?哪一條路最要快?

📖 原書 Figure 6High-level design:實線是關鍵路徑 1–14,虛線是 M1–M3 與 R1–R2;編號依內文步驟(依原書內容重繪)
  1. 1 客戶透過經紀商的網頁或 app 下單
  2. 2 經紀商把單送到交易所
  3. 3 單從 client gateway 進來:輸入驗證、rate limit、認證、正規化等,再轉給 order manager
  4. 4–5 Order manager 依 risk manager 的規則做 risk check
  5. 6 通過後,確認 wallet 有足夠資金
  6. 7–9 送到 matching engine;配對成功產生兩筆 execution(fill),買賣各一。為了重播時結果有決定性,訂單和成交都在 sequencer 排序
  7. 10–14 成交回傳給客戶
  8. M1 撮合引擎產生成交串流,送給 market data publisher
  9. M2 MDP 從成交和訂單串流建出 K 線和 order book,送到 data service
  10. M3 市場資料存進專用儲存做即時分析;經紀商連 data service 取得並轉給客戶
  11. 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懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

三個窗口同時收單,誰先誰後?

① 先想像

櫃台有三個窗口同時收單,每個窗口牆上各有一個時鐘,偏偏 B 窗口的鐘慢了 3 秒。

你猜猜看:改成每張單一進門就抽一張號碼牌 101、102、103……阿姨收到 101、102、104,她該怎麼辦?

③ 這叫做 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。

📖 原書 Figure 7Inbound and outbound sequencers(依原書內容重繪)

動手試:號碼牌漏了一張

到這裡你已經會了小結 2 / 5

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

到這裡你已經會了:一筆單走哪條路、誰先誰後

下一階要解決的問題

各個元件裡面長什麼樣子?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。

📖 原書 Figure 8Client gateway components(依原書內容重繪)

📖 原書 散戶和機構有不同的 gateway,考量是延遲、交易量和安全。做市商提供交易所大量流動性,需要極低延遲。極端例子是 colocation(colo)engine:經紀商在交易所機房租的伺服器上跑交易引擎,延遲就是光從那台機器跑到交易所伺服器的時間(第 47 頁)。

白話:normalization=把各種格式的單整理成同一種;做市商=隨時掛買賣單、讓別人隨時買得到賣得到的公司;流動性=想買想賣時,馬上有人接。

原書 Step 2Market data flow · Reporting flow · Figure 10–11

不在關鍵路徑上的兩條:市場資料要快,報表要準

這一步要解決的問題成交之後,行情和報表怎麼產生?它們不在關鍵路徑上,要求有什麼不同?

📖 原書 Figure 10Market Data Publisher(依原書內容重繪)

📖 原書 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 線

這一步要解決的問題同一份訂單和成交,要存成什麼樣子、存在哪裡?

📖 原書 Figure 12Product, order, execution 的邏輯模型;原書強調不是資料庫 schema(依原書內容重繪)

📖 原書 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 再多一張

這一步要解決的問題掛單簿要怎麼存,下單、配對、取消才夠快?

📖 原書 Figure 13Limit order book illustrated(依原書內容重繪)

📖 原書 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)
  • 取消:用 orderMap O(1) 找到那張單;單向串列得從頭走到它前一個才能刪,O(n);雙向串列的單自己有指向前一張的指標,不用走

白話:鏈結串列=每張單手牽著下一張排成一串;雙向=也牽著前一張;Map=用價格或 order ID 直接找到東西的索引。

📖 原書 Figure 14Place, match, and cancel an order in O(1)(依原書內容重繪)

原書 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懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

99 人等 1 分鐘,1 人等 30 分鐘

① 先想像

100 位客人排隊。大部分人等 1 分鐘,偶爾阿姨去接電話,那幾位就要等很久。

你猜猜看:99 位等 1 分鐘、1 位等 30 分鐘,平均等多久?

③ 這叫做 p99

p99:把 100 個等待時間由短到長排好,第 99 名那個數字;意思是「99% 的人不會等超過它」。p50 就是正中間那位。

④ 跟這章的關係

原書:交易所看 p99、甚至 p99.99,不看平均(第 29、44 頁)。

② 動手玩:100 位客人

—平均—第 50 名—第 99 名

原書 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 訊息匯流排

這一步要解決的問題不走網路、不碰磁碟,同一台機器裡的元件要怎麼互傳訊息?

📖 原書 Figure 15A low latency single server exchange design(依原書內容重繪)

📖 原書 圖中央那條長方形 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懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

一位阿姨慢慢配,還是兩位阿姨搶著配?

① 先想像

櫃台阿姨一次只拿一張單,一張配完才拿下一張。如果請兩位阿姨一起配同一面板子,她們可能同時把同一張票賣給兩個人。

你猜猜看:兩位阿姨一起配同一面板子,要怎麼避免「一票兩賣」?

③ 這叫做 single thread、lock

single thread(單執行緒):同一件事只交給一個執行者做,就不用搶鑰匙。lock:那把鑰匙,一次只准一個人改。lock 的完整版:22 章

④ 跟這章的關係

原書:每個元件是一個單執行緒的 loop,還釘在固定的一顆 CPU 上(第 32 頁)。Triton 也同意(第 65 頁)。

② 動手玩:配 20 張單

—配完 20 張要多久—一票兩賣

示意:配一張 1 秒,交一次鑰匙 0.5 秒。

原書 Step 3Application loop · CPU pinning · Figure 16

一個執行緒、釘在一顆 CPU 上、一直轉

這一步要解決的問題每個元件裡面要怎麼跑,才能每一筆都一樣快?

📖 原書 Figure 16Application loop thread in Order Manager(依原書內容重繪)

📖 原書 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 個任務的延遲分布

–p50–p99–p99.9

延伸基礎第 10 階 · event sourcing懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

板子燒了,照筆記本重做一遍

① 先想像

阿姨不只改板子,還在筆記本記下每一件事:「阿明貼售 3,200」「你收 1 張,配給阿明」。板子燒了,照筆記本從頭做一次就回來了。

你猜猜看:筆記本記了 5 件事。照著重做兩次,兩次的板子一樣嗎?

③ 這叫做 event sourcing、event store

event sourcing:不存「現在的樣子」,存「發生過的每一件事」,要的時候照順序重播。event store:存這些事件的那本筆記本。

④ 跟這章的關係

原書把整個交易所建在 event sourcing 上(第 34–36 頁);Triton 對它的保留在第 57 頁。

② 動手玩:重播筆記本

原書 Step 3Event sourcing · Figure 17

不存「現在的狀態」,存「發生過的每一件事」

這一步要解決的問題出了錯,怎麼知道帳是怎麼一步一步變成這樣的?

📖 原書 Figure 17Non-event sourcing vs event sourcing(依原書內容重繪)

📖 原書 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 套到整個交易所,元件之間要怎麼接?

📖 原書 Figure 18An event sourcing design(依原書內容重繪)

📖 原書 用 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 的設計裡,號碼牌機去哪了?可以有好幾台嗎?

📖 原書 Figure 19Sample design of Sequencer(依原書內容重繪)

📖 原書 在 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

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

到這裡你已經會了:引擎裡面怎麼又快又穩

下一階要解決的問題

機器壞了怎麼辦?原書的 hot-warm 與 Raft,以及行情怎麼公平地同時送到每個人手上。

延伸基礎第 11 階 · hot-warm懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. 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 的會說話

這一步要解決的問題撮合引擎是最不能停的元件。它掛了,怎麼幾乎立刻恢復?

📖 原書 Figure 20Hot-warm matching engine(依原書內容重繪)

📖 原書 目標 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?

📖 原書 Figure 21Event replication in Raft cluster(依原書內容重繪)

📖 原書 決定要 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

功能決定性:順序對了結果就一樣;延遲決定性:每筆都一樣快

這一步要解決的問題「每次都一樣」有兩種意思:結果一樣,速度也一樣。

📖 原書 Figure 23Time in event sourcing(依原書內容重繪)

📖 原書 功能決定性前面講過: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 為什麼有人要付錢買?

📖 原書 Figure 24Market Data Publisher(依原書內容重繪)

動手試: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懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

一個一個打電話,還是用廣播喇叭?

① 先想像

剛剛成交的價格要告訴 4 位客人。一個一個打電話,第一位永遠先知道;用廣播喇叭,大家同時聽到。

你猜猜看:打一通電話要 1 秒,依序打給 4 位。最後一位比第一位晚幾秒知道?

③ 這叫做 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:原書的五招

這一步要解決的問題公開的行情網頁被灌爆時,怎麼不拖垮交易?

  1. 把公開服務和資料與私有服務隔離,DDoS 不會影響最重要的客戶;如果提供的是同一份資料,可以有多份唯讀副本隔離問題
  2. 用 cache 層存不常更新的資料,cache 做得好,多數查詢不會打到資料庫
  3. 硬化 URL:像 https://my.website.com/data?from=123&to=456,攻擊者改 query string 就能產生很多不同請求;改成 https://my.website.com/data/recent 比較好,也能在 CDN 層 cache
  4. 有效的 safelist / blocklist,很多網路 gateway 產品有這功能
  5. Rate limiting 常用來防 DDoS

白話:唯讀副本=只能讀、不能改的影本(01 章);CDN=離使用者最近的接待處,幫你擋掉重複的請求(01 章);rate limiting=門口的保全(04 章);safelist/blocklist=放行名單/黑名單。

📖 原書 交易所通常有一些公開介面,DDoS 是真實的挑戰。

動手試:攻擊者送 1,000 個請求,CDN 擋得住幾個?

原書 Step 4Wrap up · Chapter summary · Figure 25

原書的收尾:最理想的部署,可能是一台巨大的伺服器

這一步要解決的問題讀完整章,最理想的部署長什麼樣子?

📖 原書 Chapter Summary本章心智圖;分支的 Step 歸屬照 alt(依原書內容重繪)

📖 原書 讀完本章,你可能會覺得大型交易所的理想部署模型,是把所有東西放在一台巨大的伺服器、甚至一個 process。確實,有些交易所就是這樣設計的!

📖 原書 隨著加密貨幣產業發展,很多加密交易所用雲端基礎設施部署(例如 Coinbase 的 AWS 案例)。有些 DeFi 專案基於 AMM(Automatic Market Making),連 order book 都不需要。雲端生態的便利改變了一些設計、降低入行門檻,一定會為金融世界注入創新能量。

白話:AMM=用公式自動報價、不靠掛單簿配對;DeFi=跑在區塊鏈上的金融服務。

原書到這裡結束。下一頁開始是 Triton 的觀點。

到這裡你已經會了小結 4 / 5

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

到這裡你已經會了:原書的整套交易所

下一階要解決的問題

原書講完了。Triton 同意哪些?他說「很難做穩」的地方在哪?先複習幾個舊名詞,再爬最後一階。

延伸基礎複習 · Triton 篇會用到的舊名詞懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

Triton 篇的工具箱:別份簡報講過的,一句話帶過

你猜猜看:記帳員每成交一筆就跑一趟銀行(來回 1 分鐘)。今天 600 筆,改成每 100 筆才跑一趟,省下幾趟?

Triton 的 MVP 是「資料庫 + 排隊盒 + 撮合引擎」,所以這幾個舊名詞會一直出現。每一張卡都連到講得最完整的那一份簡報。

database(DB)帳本:錢和庫存的正本,最不能錯。01 章
transaction一組動作要嘛全做、要嘛全不做。22 章
message queue(MQ)排隊盒:先放進去的先拿出來,接手的人慢慢處理。19 章
batch收滿一袋再跑一趟,來回只付一次。17 章
idempotency・去重同一張單送兩次,只算一次。22 章
2PC兩邊都說「好」才算數。22 章
WebSocket一直接通的對講機,伺服器可以主動推。12 章
round trip去倉庫一趟來回,跑幾趟比拿多少更花時間。02 章

延伸基礎第 13 階 · bottleneck懂的人可以跳過

  1. order book
  2. limit / market
  3. price-time
  4. market data
  5. latency
  6. critical path
  7. sequencer
  8. p99
  9. single thread
  10. event sourcing
  11. hot-warm
  12. multicast
  13. bottleneck

三個櫃台、一位阿姨、兩位記帳員:一分鐘出幾張?

① 先想像

轉讓板變成一條龍:櫃台收單,阿姨配對,記帳員把成交寫進帳本。每一站速度不一樣。

你猜猜看:3 位櫃台每分鐘各收 10 張、1 位阿姨每分鐘配 20 張、2 位記帳員每分鐘各記 8 張。整條線每分鐘最多幾張?

③ 這叫做 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 同意哪一句?

① 同意:每檔股票一個單執行緒引擎、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 自己做,最小可行的交易所長什麼樣子?真相放在哪裡?

🗣️ 084 第 7 頁 System architecture講義只有方框名稱、沒有箭頭;連線依第 8–11 頁的流程推論(依講義文字重繪)
  1. 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
  2. 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
  3. Database UpdaterFor every incoming MatchingResult:Begin TX,update Order, User, UserPosition accordingly,Commit TX;Ack the message
  4. 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 → brokerEngine → Datafeed → WebSocket Cluster
報表 / 結算Reporter 寫 DBPost-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 就當機呢?

    🗣️ 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 怎麼說?

    「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 的網路來回。一檔股票每秒最多幾筆?

    「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 筆一批一起送,會怎樣?

    –每秒可處理–處理 10,000 筆要幾次 IO–同批最早一筆多等

    每筆 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。如果你只有一台撮合引擎,它死了,最笨但一定會動的辦法是?

    「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 + Raftevent store 複製、Raft、heartbeat📖 原書

    停機時間是示意模型:等 DB updater 消化完 backlog + 掃 Order 表裡還 OPEN 的單、重建 orderbook;standby 與 hot-warm 抓偵測 + 升級的秒數。原書的目標是秒級 RTO(第 40 頁)。

    Triton 觀點 · 動手玩044 [02:12]–[02:24]

    最難防的不是死掉,是「沒死,但算錯了」

    原書這樣做會出什麼事?warm 引擎跟著算、但不說話。primary 沒死、只是算錯了一筆,warm 會發現嗎?

    「最困難保護的是,他沒有死,但是他算的,原來是錯的」🗣️ 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 小時,用交易時段算,能停多久?

    「傳統上我們談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 嗎?

    「如果是要面對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。售票系統能照抄這套嗎?

    「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

    1. order book
    2. limit / market
    3. price-time
    4. market data
    5. latency
    6. critical path
    7. sequencer
    8. p99
    9. single thread
    10. event sourcing
    11. hot-warm
    12. multicast
    13. bottleneck

    到這裡你已經會了:Triton 怎麼看這一章

    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)

    本章名詞小卡課後複習用 · 每個名詞一句白話

    今天出現的名詞,一句話講完

    order book還沒成交的買單和賣單清單,就是那面轉讓板
    bid / ask出價最高的「收」/開價最低的「售」
    spreadbid 和 ask 中間差多少
    limit order指定價格,超過就不買;可能要等
    market order不指定價格,馬上用板上的價格成交
    matching engine配對買賣的櫃台阿姨(程式),又叫 cross engine
    price-time priority先比價格,同價再比誰先到
    FIFOfirst in, first out,先進先出
    execution / fill一次配對產生的成交回報,買賣各一筆
    symbol股票代號,例如 AAPL
    broker券商:幫散戶把單送進交易所
    risk check、wallet下單前的風險檢查/先凍結要用的錢

    給工程師的重點出處與標籤

    引述來源(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)。轉讓板與人名是虛構的示範情境,延伸基礎頁的數字是示意。

    ← → 翻頁 · S 講者備註 · D 深/淺色
    1 / 1目錄