Polymarket 預測市場 (Design Polymarket)

1. 釐清需求與範圍 (Clarify & Scope ~5 min)

開場後先框邊界，別急著畫撮合引擎。金融交易所題最容易在「一致性語意」與「鏈上 vs 鏈下分界」上翻車，必須先問清。

2. 功能性與非功能性需求 (FR / NFR 與設計北極星)

• 功能性需求 (FR)

  • 所有市場皆為 binary（YES / NO）。
  • 使用者 管理訂單：建立新單、修改既有單（price / size）、取消未成交單。
  • 撮合成立後，鏈上 collateral（USDC）↔ outcome tokens（YES/NO） 交換；市場 resolve 後勝方兌回 USDC、敗方 token burned（價值 0）。
  • 使用者查看每個市場的 即時價格與狀態（best bid / ask、last trade）。

• 非功能性需求 (NFR)

  • 訂單強一致：訂單一旦接受 / 取消，後續查詢必須反映最新狀態（讀服務允許 小而有界 的傳播延遲）。
  • 可擴展：~20M DAU、~100M trades/day、數千並行市場。
  • 低延遲：下單 / 取消 p95 < 200ms（同區）；價格更新 次秒級 傳播。
  • 隱含：寫密集 + 撮合零容錯（已 ack 的 order / fill 不可遺失）。

設計北極星（NFR 直接導出後續所有選型的判準）：

3. 容量估算 (Back-of-Envelope ~4 min)

估算目的是 驅動 sharding 與讀路徑解耦決策（估算 → 選型 hand-off）。回連 02-Distributed-Systems/05-Numbers-to-Know。

寫流量（撮合 QPS）

~100M trades/day
平均 QPS = 100,000,000 ÷ 86,400 s ≈ 1,157 trades / sec
撮合尖峰（熱門市場結算前、新聞事件）常為平均的 5~10x → ~6k~12k orders/sec（推導值）
→ 單一 Matching Engine 扛不住所有市場 → 必須依 market_id 分片

讀流量（價格 / 訂單查詢）

20M DAU，每人每天多次刷新價格 + 查訂單，讀遠多於寫（read-heavy 的 UI 層）
價格更新需「每筆 order event → 計算新價 → 推給所有訂閱者」的 fan-out
→ 讀路徑（MDS/OQS）流量量級遠高於撮合本身 → 必須與撮合解耦獨立擴展

狀態 / 儲存

數千並行市場，每個市場一份 in-memory order book（活躍訂單）
WAL：每筆 order/fill event append（永久或長期保留以供重建 / 重放）
Order DB（OQS materialized）：歷史訂單 + 狀態，依 user_id sharding

下表 QPS 與尖峰倍數皆為 推導值（由 trades/day ÷ 86,400 與一般金融尖峰經驗推出；來源僅給 20M DAU / 100M trades/day / 數千市場 / <200ms / 次秒級等輸入）。

4. 用到的積木 / Building Blocks Used

架構即目錄：先給導覽圖，再展開。下表每個決策都對映一個既有 concept note（無 alias 連結）；本表即「本案例練到哪些積木」的單一事實來源（single source of truth）。

5. API 設計 (API Design ~3 min)

由 FR 驅動，採 REST 資源風格（理據見 03-API-Design/02-REST）；即時價格走「HTTP 取 baseline + WebSocket 串增量」雙軌。

6. 資料模型與儲存選型 (Data Model & Storage Choice ~4 min)

核心不是「一張 DB 表」，而是 三種狀態載體：撮合引擎的 in-memory order book、持久化的 WAL、以及 OQS materialized 的 Order DB。

In-Memory Order Book（per market，撮合引擎內，極低延遲）
--------------------------------------------------
bids:  price → [orders FIFO]   （價格層級，由高到低）
asks:  price → [orders FIFO]   （價格層級，由低到高）
index: orderId → (price, side) ← O(1) 定位以做 cancel / modify
--------------------------------------------------
不落 DB：撮合需 < 200ms；當機靠 WAL + snapshot 重建

WAL（per market shard，append-only，唯一事實來源）
--------------------------------------------------
seq | leaderEpoch | type(NEW/CANCEL/MODIFY/FILL) | orderId | marketId | payload | ts
--------------------------------------------------
+ 定期 snapshot（in-memory book 快照 + 對應最後 WAL offset）
重啟：載入最新 snapshot → replay 該 offset 之後的 WAL → deterministic 重建

Order DB（OQS materialized view，依 user_id sharding）
--------------------------------------------------
orderId PK | userId(shard key) | marketId | side | type | limitPrice
          | numShares | filledShares | status | createdAt | updatedAt
--------------------------------------------------
為查詢最佳化（分頁 / 篩選 / 歷史 / analytics），由 order event 餵養更新

On-chain（CTF / Polygon，鏈上結算與所有權）
--------------------------------------------------
conditionId → outcomeIndex(YES=0 / NO=1)   ← UMA oracle resolve 後寫入
USDC collateral escrow ↔ YES/NO outcome tokens（mint / burn）

儲存選型：

→ 積木：撮合的序列化與一致性見 05-Database-Advanced/01-Transactions；WAL 持久化見 12-Ops-and-Reliability/03-Reliable-Delivery；OQS 讀模型見 06-Database-Tech/04-OLTP-vs-OLAP 與 10-Design-Patterns/02-Scaling-Writes；分片見 05-Database-Advanced/02-Sharding。

7. 高階架構 (High-Level Design ~7 min)

把積木串成端到端流程。先看三條核心 flow，再看 scaled 架構。

(A) 下單 / 撮合 flow（order → match）

Client
  │  POST /orders { side, type, marketId, limitPrice, numShares }
  ▼
API Gateway ──► Matching Engine（依 market_id 路由到對應 shard）
  │ 1. append order event → WAL（先持久化！）
  │ 2. 更新 in-memory order book（價格層級）
  │ 3. 撮合：找到 maker+taker → 產生 FILL event → append WAL → 更新 book
  │ 4. 把撮合對交給 Settlement Service（鏈上結算，非同步）
  ▼
回傳 Order { status, filledShares }   （撮合完成才回 success，且 WAL 已 ≥1 replica ACK）

(B) 鏈下執行 ↔ 鏈上結算 flow（off-chain ↔ on-chain）

撮合成立（off-chain，已寫 WAL）
        │  撮合對送 Settlement Service
        ▼
   Settlement Service
        │ 1. 確認 collateral / outcome-token reservation 已存在
        │ 2. JSON-RPC → Polygon 上的 CTF Exchange contract
        │       └─ atomic swap：USDC collateral ↔ YES/NO outcome tokens
        │ 3. 鏈上失敗 → retry / 升級 ops
        │       ★ 絕不 rollback 已完成的 off-chain fill（append-only / deterministic）
        ▼
   taker 錢包持有 outcome tokens
        │
        ▼（市場 resolve 時）
   UMA oracle 把 outcome 寫上鏈：conditionId → outcomeIndex(YES=0/NO=1)
   勝方呼叫 CTF → 兌 1 USDC；敗方 token → burned（價值 0）

(C) Scaled 架構（端到端 — CQRS 扇出）

                                Client
                                  │  下單/取消 (write)        訂閱價格/查訂單 (read)
                                  ▼                                  ▲
                            API Gateway                              │
                                  │ route by market_id              │
        ┌─────────────────────────┼──────────────────────────┐     │
        ▼                         ▼                            ▼     │
  Matching Engine          Matching Engine             Matching Engine
   (shard A: market 1..n)   (shard B ...)               (shard C ...)
   primary + replicas       每 shard：WAL + in-mem book
        │ append WAL → 更新 book → publish order events
        ▼
   ┌──────────────────────────────────────────────────────────┐
   │            Kafka pub/sub  (partition by market_id)         │ ← 解耦撮合與讀路徑
   └───────────────┬───────────────────────┬───────────────────┘
                   │ (consume)              │ (consume)
                   ▼                        ▼
            Market Data Svc (MDS)     Order Query Svc (OQS)
            算 best bid/ask/last       materialize → Order DB
            更新 price cache           (依 user_id sharding)
                   │                        │
       Redis Pub/Sub (per-market channel)   └──► GET /orders 查訂單
                   │ push incremental
                   ▼
          WebSocket / SSE ──► Client（次秒級價格）
                                  ▲
                       HTTP snapshot 取 baseline 後升級為 WS

關鍵 hand-off：API Gateway 依 market_id 路由 → 對應 Matching Engine shard（in-mem book + WAL，每市場單一 sequencer）→ publish 到 Kafka → MDS（價格 fan-out via Redis Pub/Sub + WebSocket）與 OQS（materialize 成可查的 Order DB）各自獨立消費。撮合的延遲關鍵路徑與重 UI 讀路徑 徹底解耦。

8. 深入探討 (Deep Dives ~9 min)

8.1 使用者如何追蹤訂單狀態（OQS）

問題：UX 上使用者要能查「我所有 open orders」「我最近 100 筆交易」「market X 的訂單」——這些是 pagination / 彈性篩選 / analytics / big join 型查詢。
為何是瓶頸：直接打 Matching Engine 取訂單看似最省事，但 撮合引擎是為低延遲撮合調校的，這類重查詢會 吃掉撮合的延遲預算（< 200ms），等於用 UI 流量拖垮交易主幹。

選擇與理由：採 B（OQS）。OQS 像 MDS 一樣 tail WAL（後續改 tail Kafka），把 order event materialize 到查詢最佳化的 Order DB，client 的所有訂單查詢走 OQS。代價是 NFR 已允許的「小而有界的讀傳播延遲」——這正是強一致需求被刻意限定在「order management 本身」而非「讀服務」的原因。Order DB 依 user_id sharding，同一使用者的訂單查詢只落單一 shard。
→ 積木：06-Database-Tech/04-OLTP-vs-OLAP（撮合 OLTP / OQS 偏分析查詢）、10-Design-Patterns/02-Scaling-Writes（CQRS 讀寫分離）、05-Database-Advanced/02-Sharding（user_id shard）

8.2 系統如何擴展到每日大量交易（Kafka 解耦 + 分片）

問題：~100M trades/day + 尖峰 + 數千市場，且 MDS / OQS 都要能水平擴展。
為何是瓶頸：原始設計裡 MDS 與 OQS 都直接 tail Matching Engine。一旦把這三者各自加 instance 水平擴展，Matching Engine 與 consumer 的連線數呈爆炸式成長，而且 Matching Engine 還得負責 MDS/OQS 的 downtime recovery——這會直接侵蝕撮合的即時效能。

選擇與理由：採 B。Matching Engine 在 append WAL + 更新 in-mem book 後，把 order event publish 到 Kafka；一個 event 可被多 consumer（MDS / OQS）同時消費，各服務獨立擴展、各自管自己的 recovery（從 Kafka replay 而非回連撮合引擎）。Kafka 依 market_id 分區，保證同一市場內訂單的 ordering 與 consistency。而 Matching Engine 本身也 依 market_id sharding——每市場 單一 sequencer，其 shard 的 WAL 即該市場所有訂單的 authoritative event source，故能靠 snapshot + WAL replay deterministic 重建 book。
→ 積木：09-Messaging-Coord/03-Kafka（分區 / ordering / consumer group）、09-Messaging-Coord/01-Data-Pipeline（event 管線 / 重放）、05-Database-Advanced/02-Sharding（market_id 分片）

8.3 容錯：撮合引擎掛了怎麼辦（failover 不丟單）

問題：Matching Engine 是某市場 order book 的 source of truth，一旦掛掉就失去權威市場資料。目標：即使 leader 回應後立刻 crash，已 ack 的 order / fill 一筆都不能丟。
為何是瓶頸：純 in-memory book 一掉電就全沒；單靠本地 WAL，若整台機器死了也救不回。

做法（per shard 配 replica）：

1. Client 下單 → primary
2. primary append log entry → 本地 durable log（WAL）
3. primary 透過 TCP 把 WAL entry 送 replicas
4. replicas 套用 WAL 到各自 in-memory state machine
5. ≥1 replica ACK → 才回 client「success」（保證事件至少存活 2 台機器）

failover：
- replica 知道最後完整套用的 WAL sequence
- 一個 replica 被 promote 成新 primary（leader election 用 Raft / ZooKeeper / etcd 防 split-brain）
- 新 primary 以新的 leader epoch 繼續 append WAL
- 其餘 replica follow 新 leader

選擇與理由：WAL + primary/replica + ≥1 ACK 是「不丟單」的最小代價組合；leader election 交給 共識協議 / ZooKeeper / etcd 防雙主。需要同步幾個 replica 是 latency vs consistency 的旋鈕——本題定在「≥1」以守住 200ms 延遲預算。
→ 積木：05-Database-Advanced/03-Replication（primary/replica / failover）、12-Ops-and-Reliability/03-Reliable-Delivery（ack / 不丟）、09-Messaging-Coord/05-Zookeeper（leader election / 防 split-brain）

8.4 招牌取捨：撮合 append-only、永不回滾

問題：撮合在鏈下已完成（寫進 WAL），但 鏈上結算可能失敗（gas / 合約 revert / 節點問題）。要不要把 off-chain fill 回滾以保持鏈上鏈下一致？
為何重要：這決定了整個系統的一致性語意，是本題的 core_tradeoff。

選擇與理由：選 B。撮合流程必須 deterministic 且 append-only——一旦回滾，會 破壞 ordering guarantee、增加狀態重建複雜度、導致 replica 與下游 consumer 狀態分歧。所以鏈上失敗時 只 retry 或升級 ops，絕不 rollback 已完成的 off-chain 撮合。實務上再用 settlement batching / 預先 pre-mint positions 讓撮合 不被鏈上吞吐量阻塞。用「鏈上結算只保證最終一致」換「鏈下撮合的確定性與可重建性」——這就是 core_tradeoff。
→ 積木：09-Messaging-Coord/01-Data-Pipeline（append-only event log / 重放）、12-Ops-and-Reliability/03-Reliable-Delivery（retry / 最終一致收斂）

9. 擴展與瓶頸 (Scaling & Bottlenecks ~5 min)

主動找出系統會先在哪裂開並補強（訓練 drive 而非被動回答）。

10. 取捨總表與收尾 (Trade-off Recap & Wrap-up ~2 min)

後續追問演練 (Interviewer Follow-ups — "What if…")

主動回想：白板重建 (Whiteboard from Scratch)

不看上文，照下面提示把整個設計重建一次。每格都該能 30 秒內口述。

• 0. Frame：一句話定位（鏈下撮合 + 鏈上結算）+ 宣告 35 min 配速 → __
• 1. Clarify：列 3 個必問（鏈上/鏈下分界？一致性語意？規模/延遲？）→ __
• 2. FR / NFR：4 個 FR、4 個 NFR、一句話北極星 → __
• 3. 估算：撮合平均/尖峰 QPS = ？ 結論（為何要分片 + CQRS）= ？ → __
• 4. Building Blocks：默寫 ≥8 個決策→積木對映 → __
• 5. API：6 個 endpoint（含 WS stream）→ __
• 6. 資料模型：in-mem book / WAL / OQS Order DB / on-chain CTF 四種載體 → __
• 7. 架構：畫 下單→撮合 flow / 鏈下↔鏈上 flow / CQRS 扇出圖（撮合 shard→Kafka→MDS+OQS）→ __
• 8. Deep Dives：OQS 訂單追蹤、Kafka 解耦 + market_id 分片、replica failover + ≥1 ACK、append-only 永不回滾 → __
• 9. Scaling：先在哪裂開？分片 / Kafka 解耦 / WAL+replica / Redis fan-out / OQS → __
• 10. Recap：一句話招牌取捨 = ？ → __

常見陷阱 (Exam Traps for This Problem)

Related Notes

• 02-Distributed-Systems/05-Numbers-to-Know
• 05-Database-Advanced/01-Transactions
• 05-Database-Advanced/02-Sharding
• 05-Database-Advanced/03-Replication
• 06-Database-Tech/04-OLTP-vs-OLAP
• 07-Caching-Storage/04-Redis
• 09-Messaging-Coord/01-Data-Pipeline
• 09-Messaging-Coord/03-Kafka
• 09-Messaging-Coord/05-Zookeeper
• 10-Design-Patterns/02-Scaling-Writes
• 10-Design-Patterns/05-Real-time-Updates
• 01-Networking/05-Realtime-Protocols
• 11-Infrastructure/01-API-Gateway
• 12-Ops-and-Reliability/01-Dealing-With-Contention
• 12-Ops-and-Reliability/03-Reliable-Delivery
• 03-API-Design/02-REST