System Design Interview Vol. 2 · 第 10 章Triton 覆蓋度:🟢 高Triton 線
Real-time Gaming Leaderboard
兩千五百萬個玩家,誰排前十名?
原書先試 MySQL,嫌排序太慢;改把每一個玩家放進同一個 Redis sorted set,每贏一場就 ZINCRBY,到 5 億 DAU 才分片。Triton 在「某質數公司」做過一模一樣的排名榜,第二版就是原書這個設計,結果「再爆掉」:sorted set 只有一個,只住在一台 Redis 上,大家一起「開罐罐派對」就死。他的答案:每個人的分數用普通 KV 散在整個 cluster,sorted set 只放前 1000 名。
給文組
全程用「夜市射氣球攤的排行白板」比喻,一階一階爬 12 個概念;頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。每階都有可以動手玩的小模擬:跳格電梯、分班、開服爆量、分頁重複。
給工程師
第 5–38 頁完整講原書(25 張圖和章末心智圖全部重繪、Table 1–5、SQL 與 Redis 指令照錄),後面是 Triton 的觀點,最後一頁列出所有出處(materials/core)與頁碼對照。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 📝 上課筆記 📅 2026 補充
先用生活理解夜市射氣球攤的排行白板
老闆要在白板上寫前 10 名:每打破一顆氣球,他要做多少事?
200 位客人在射氣球,每破一顆加 1 分。老闆有三種記分法,右邊是「過去一秒」老闆動了幾次筆:
① 是原書第一個試的 MySQL 排序;② 是原書的 Redis sorted set;③ 是 Triton 的做法。② 看起來不多,但全部的筆都落在同一本名冊上。按「一群人同時開射」看看(長條是對數刻度)。
學習地圖本章的概念階梯
今天爬 12 階。每一階只用前面講過的東西。
- 1QPS每秒破幾顆氣球
- 2O(log n)翻幾張卡才找到
- 3Redis手邊的白板
- 4sorted set永遠排好的名冊
- 5skip list跳格電梯
- 6partition名冊拆成幾本
- 7scatter-gather每班交前幾名
- 8percentilePR 值
- 9tie-break同分誰先
- 10hotspot筆只有一枝
- 11top-N白板只寫前幾名
- 12snapshot每分鐘拍一張
第 1–3 階 · 一顆氣球破掉之後
要回答:為什麼 MySQL 排名會越來越慢?
第 4–5 階 · 永遠排好的名冊
要回答:sorted set 怎麼做到加分、查名次都很快?
第 6–9 階 · 名冊拆成好幾本
要回答:拆開後怎麼找前 10 名、我第幾名、同分怎麼排?
第 10–12 階 · Triton 的修法
要回答:筆只有一枝怎麼辦?排行榜真的要即時嗎?
全程只用一個攤位:夜市射氣球攤(虛構)
200 位客人、白板寫前 10 名。每爬 3–4 階,有一頁「到這裡你已經會了」。
延伸基礎第 1 階 · QPS(複習 DAU、尖峰)懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
一晚破 36,000 顆氣球,每秒有幾顆?
① 先想像
夜市晚上 6 點開到 11 點,客人陸陸續續來射氣球。9 點煙火秀一開始,大家同時舉槍。
你猜猜看:一晚 5 小時(18,000 秒)共破 36,000 顆,平均每秒幾顆?
36,000 ÷ 18,000 = 2。可是煙火秀那一分鐘,每秒可能有 50 顆。右邊切到「煙火秀」看看。
④ 跟這章的關係
原書從 500 萬 DAU 算出尖峰每秒 2,500 次加分(第 6 頁)。Triton 會問:新年倒數那一秒呢?
② 動手玩:同一個攤位,三個時段
原書 Step 1釐清需求 · Figure 1
面試一開始:分數怎麼算、誰上榜、多即時?
這一步要解決的問題分數怎麼算、誰上榜、多即時?這三件事決定後面用什麼資料結構。
📖 原書 應徵者 × 面試官
| 應徵者問 | 面試官答 |
|---|---|
| 排行榜的分數怎麼算? | 贏一場得一分。每個使用者有一個總分,每贏一場加一分 |
| 所有玩家都上榜嗎? | 是 |
| 排行榜有時間區段嗎? | 每個月開一場新錦標賽,開一個新排行榜 |
| 只在乎前 10 名嗎? | 顯示前 10 名,以及特定使用者的名次;有時間的話,也討論怎麼回傳某人上下各 4 名 |
| 一場錦標賽多少使用者? | 平均 DAU 500 萬、MAU 2,500 萬 |
| 平均每人打幾場? | 每人每天平均 10 場 |
| 同分怎麼排? | 同分同名次;有時間再談怎麼打破平手 |
| 要即時嗎? | 要,即時或盡量接近即時;不可以呈現批次處理的歷史結果 |
白話:DAU=每天有幾個人來玩;MAU=一個月內來過幾個人;錦標賽=每個月一場、重新算分的比賽。
📖 原書 什麼是排行榜:完成任務或挑戰就得分,分數最高的在最上面。排行榜除了顯示領先者,也要顯示使用者自己在哪裡。
最後一題「要即時」先記住,Triton 自己做的榜是「半即時(資料延誤最長一分鐘吧)」(第 48 頁)。
原書 Step 1功能需求 · 非功能需求 · 粗估
500 萬 DAU,尖峰每秒 2,500 次更新分數
這一步要解決的問題每秒要加幾次分、讀幾次榜?這些數字決定一台機器夠不夠。
📖 原書 功能需求
- 在排行榜顯示前 10 名玩家
- 顯示某個使用者的名次
- 顯示該使用者上下各 4 名的玩家(加分題)
📖 原書 非功能需求
- 分數即時更新
- 分數更新即時反映在排行榜上
- 一般的 scalability、availability、reliability
白話:scalability=人變多也撐得住;availability=隨時都能用;reliability=不出錯、不掉資料。
📖 原書 粗估:動手改數字
原書:一天約 105 秒;用量不平均,晚上各時區的人都有空玩,所以假設尖峰是平均的 5 倍。前 10 名的榜只在每天第一次開遊戲時載入。
原書 Step 2API design · Table 1–3
三支 API:更新分數只給 game server 呼叫
這一步要解決的問題外面要怎麼跟排行榜說話?誰可以改分數?
POST /v1/scores
使用者贏一場時,更新他在排行榜上的位置。這是 internal API,只能由 game servers 呼叫,client 不能直接改分數。
| Field | Description(Table 1) |
|---|---|
user_id | 贏得遊戲的使用者 |
points | 贏這場拿到的點數 |
| Name | Description(Table 2) |
|---|---|
200 OK | 成功更新分數 |
400 Bad Request | 更新分數失敗 |
GET /v1/scores · GET /v1/scores/{:user_id}
前者取前 10 名;後者取某個使用者的名次(Table 3:user_id = 想查名次的使用者 ID)。下方右邊按按看,回應格式照原書的 sample response。
白話:internal API=只開給自家機器的窗口;game server=確認輸贏的遊戲伺服器;200/400=成功/你送來的單有問題。
動手試
原書 Step 2High-level architecture · Figure 2
兩個服務:game service 驗證輸贏,leaderboard service 管排行榜
這一步要解決的問題一場勝利從手機到排行榜,要經過哪幾站?
📖 原書 流程:
- 玩家贏了,client 送 request 給 game service
- game service 確認這場勝利有效,呼叫 leaderboard service 更新分數
- leaderboard service 更新 leaderboard store 裡這個人的分數
- 玩家直接呼叫 leaderboard service 拿資料:a. 前 10 名;b. 自己的名次
白話:service=專做一件事的一組程式;leaderboard store=排行榜存放的地方(下面會比較 MySQL 和 Redis)。
文組版:射氣球攤的店員(game service)確認氣球真的破了,才去跟寫白板的老闆(leaderboard service)報分;客人想看榜,直接看白板。
原書 Step 2兩個被否決的替代方案 · Figure 3–4
為什麼不讓 client 直接報分?要不要中間放個 MQ?
這一步要解決的問題分數可以讓玩家自己報嗎?中間要不要放一台排隊的號碼機(MQ)?
📖 原書 Client 直接找 leaderboard service?不行
替代方案由 client 設定分數,不安全:會被 man-in-the-middle attack,玩家架一個 proxy 就能隨意改分數。所以分數要在 server 端設定。
註:像線上撲克這種 server authoritative 的遊戲,遊戲邏輯全在 game server,它知道一局何時結束,可以自己設分數,client 連報都不用報。
📖 原書 Game service 和 leaderboard service 之間要 MQ 嗎?
看分數怎麼被用。如果同一份資料還要給別的地方用,例如 analytics、push notification,或回合制、多人遊戲要通知其他玩家,就像 Figure 4 一樣放進 Kafka,多個 consumer 各自消費。面試官沒有提這個需求,所以原書的設計不用 MQ。
白話:man-in-the-middle=有人夾在中間偷改;proxy=夾在中間轉手的機器;MQ/Kafka=讓訊息先排隊的號碼機(01 章);consumer=從號碼機拿訊息來處理的程式。
原書 Step 2 · Data modelsRelational database solution · Figure 5–7 · Table 4
最簡單的版本:一張表、兩個欄位、ORDER BY
這一步要解決的問題先試最簡單的:一張表存分數,要看榜就排序。
📖 原書 排行榜存放(leaderboard store)有三個候選:關聯式資料庫、Redis、NoSQL(深入篇)。先退一步:如果規模不重要、使用者很少,就用 RDS。每個月一張表,欄位是 user id 和 score;實際上還有 game_id、timestamp 等,但查詢和更新的邏輯一樣。
贏一場(假設每次 +1)。這個月第一次上榜:
INSERT INTO leaderboard (user_id, score) VALUES ('mary1934', 1);之後再贏:
UPDATE leaderboard set score=score + 1 where user_id='mary1934';
查名次:把整張表依分數排序:
SELECT (@rownum := @rownum + 1) AS rank, user_id, score FROM leaderboard ORDER BY score DESC;
白話:RDS=雲端代管的關聯式資料庫(MySQL 這類,01 章);INSERT/UPDATE/SELECT=新增一列/修改一列/查詢;ORDER BY score DESC=依分數由高到低排。
| rank | user_id | score |
|---|---|---|
| 1 | happy_tomato | 987 |
| 2 | mallow | 902 |
| 3 | smith | 870 |
| 4 | mary1934 | 850 |
📖 原書 Table 4Result sorted by score
延伸基礎第 2 階 · O(n) 與 O(log n)懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
「我第幾名?」要翻幾張計分卡才知道?
① 先想像
200 張計分卡攤在桌上。想知道你第幾名,只能一張一張數「比我高分的有幾張」。卡片如果已經依分數排好,就能像查字典一樣從中間翻。
你猜猜看:1,000 張排好的卡,每次從中間翻、丟掉一半,最多翻幾次就找到你?
1,000 → 500 → 250 → … → 1,對半 10 次就到底(2 的 10 次方是 1,024)。沒排好的話,最壞要看完 1,000 張。
③ 這叫做 O(n)、O(log n)
O(n):人數多 100 倍,工作也多 100 倍。O(log n):人數翻一倍,只多翻一次。O(1):13 章
④ 跟這章的關係
原書說 MySQL 查名次要把所有人排一遍(下一頁);sorted set 加分、查名次都是 O(log n)(第 19 頁)。
② 動手玩:16 張排好的計分卡,找出你的位置
| 計分卡 n 張 | 一張一張數(最壞) | 對半翻(最壞) |
|---|---|---|
| 16 | 16 張 | 5 次 |
| 1,000 | 1,000 張 | 10 次 |
| 1,000,000 | 1,000,000 張 | 20 次 |
| 25,000,000(原書 MAU) | 25,000,000 張 | 25 次 |
原書 Step 2 · Data models為什麼 RDB 撐不住
要知道你第幾名,得先把所有人排一遍
這一步要解決的問題表裡有幾百萬人時,「我第幾名」為什麼會慢到幾十秒?
📖 原書 資料少時可行;資料有好幾百萬列時查詢會非常慢:
- 要算某人的名次,得把每一個玩家排到正確位置;而且分數會重複,名次不只是「在列表裡的第幾個」
- 大量、持續變動的資料,SQL 資料庫效能不好;對幾百萬列做 rank 要幾十秒,不符合即時要求
- 資料一直在變,也不適合用 cache
- RDB 不是設計來扛這種高讀取量;做成批次可以,但不符合「即時回傳名次」
📖 原書 一個優化:加 index,再用 LIMIT 限制要掃的頁數:
SELECT (@rownum := @rownum + 1) AS rank, user_id, score FROM leaderboard ORDER BY score DESC LIMIT 10
但擴展性還是不好:① 查某人名次本質上還是要全表掃描;② 對不在榜首的人,沒有直接的辦法算名次。
白話:index=書後面的索引,先排好方便查;LIMIT 10=只拿前 10 筆;全表掃描=一列一列全部看過(第 11 頁的「一張一張數」)。
動手算:表越大,三種查詢各要碰幾列?
示意:碰一列算一單位、排序用 n log n 估算。原書說「對數百萬筆資料執行排名操作將花費數十秒」,這裡只看比例。
延伸基礎第 3 階 · Redis(複習 cache、database)懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
分數收在後面倉庫,還是寫在手邊的白板?
① 先想像
老闆的帳本鎖在後面倉庫,每查一次要走過去翻。白板就掛在手邊,看一眼就好,可是一下大雨就會被沖掉。
你猜猜看:夜市停電又下大雨,隔天哪一份分數還在?
白板快,但一沖就沒了;帳本慢,但鎖在倉庫裡。所以白板當「快速查看」用,正本一定要另外記在帳本。
③ 這叫做 Redis、in-memory
Redis:大家共用的白板,讀寫很快。in-memory:資料放在記憶體(白板)而不是硬碟(倉庫),斷電就沒了。Redis:04 章cache:01 章database:01 章
④ 跟這章的關係
原書把排行榜放在 Redis 的 sorted set(下一階),每一場勝利另外記進 MySQL(第 22 頁)。
② 動手玩:查 100 次分數,各要多久?
倉庫的帳本(MySQL)
手邊的白板(Redis)
到這裡你已經會了小結 1 / 4
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
到這裡你已經會了:為什麼 MySQL 排名會越來越慢
- 每贏一場 +1 分,就是一次寫入。看每秒幾次(QPS),要看最忙那一秒。
- 「我第幾名」= 數比我高分的有幾個。沒排好是 O(n);排好了能對半翻,O(log n)。
- Redis 是放在記憶體的白板:很快,但會被沖掉,所以正本另外記在 MySQL。
下一階要解決的問題
白板上要用什麼形狀的名冊,才能一邊加分、一邊很快查到名次?
延伸基礎第 4 階 · sorted set懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
一本永遠排好的名冊:有人加分,只搬他那一行
① 先想像
老闆準備兩樣東西:一本「名字 → 分數」的通訊錄,翻名字就找到;一本依分數由高到低排好的名冊。
你猜猜看:mary 從 850 分變 880 分,名冊要改幾行?
其他人的順序沒變,只有 mary 往上搬。右邊按「mary1934 +30」看看。
③ 這叫做 sorted set、member/score
sorted set:Redis 裡一份「自動排好序」的清單,通訊錄和名冊兩本合一。member/score:清單裡的名字/他的分數。
④ 跟這章的關係
原書的主設計:整個月所有玩家放進同一個 sorted set(下一頁)。這句「同一個」,Triton 會挑出來講。
② 動手玩:有人加分,名冊怎麼變?
通訊錄:名字 → 分數
名冊:依分數由高到低
原書 Step 2 · Data modelsRedis solution · Figure 8
Redis sorted set:插入時就排好位置
這一步要解決的問題有沒有一種名冊,加分時就自動排好,查名次不用從頭數?
📖 原書 想要的是:就算幾百萬使用者,效能也可預測,常見的排行榜操作都很好做,不用寫複雜的 DB query。
📖 原書 Redis 是 in-memory 的 key-value store,讀寫很快;它有一種資料型態 sorted set,很適合排行榜:
- 像 set:每個 member 唯一,但每個 member 帶一個 score,score 可以重複
- 依 score 由小到大排序
- 內部是兩個資料結構:hash table(使用者 → 分數)+ skip list(分數 → 使用者)
- 可以想成一張有 score 和 member 兩欄、依分數由大到小排的表(Figure 8)
文組版:hash table 是「名字 → 分數」的通訊錄,一翻就到;skip list 是「依分數排好的名冊」,加了好幾層書籤,可以很快跳到中間。下一頁拆開看那幾層書籤。
延伸基礎第 5 階 · skip list懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
排名榜上的跳格電梯:到 45 樓要停幾次?
① 先想像
64 層的百貨公司有三種電梯:每層都停的、每 4 層停一次的、每 16 層停一次的。
你猜猜看:到 45 樓,每層停的電梯要停 44 次。先搭每 16 層停的、再換每 4 層停的,大約停幾次?
1 → 17 → 33(2 次),換電梯 33 → 37 → 41 → 45(3 次),共 5 次。右邊按「出發」看。
③ 這叫做 skip list、level
skip list(跳躍表):在排好序的名冊上,多蓋幾層「跳著停」的捷徑。level:第幾層捷徑;越上層停得越少。
④ 跟這章的關係
sorted set 的名冊就是 skip list。找「45 分該插在哪」也是從最上層跳下來(第 18、19 頁)。
② 動手玩:從 1 樓出發
原書 Step 2 · Data modelsSkip list · Figure 9
跳躍表:在排好序的串列上面,蓋幾層「隔一個跳一個」的捷徑
這一步要解決的問題排好序的名冊,要怎麼很快找到「45 分該插在哪」?
動手試:ZADD 一個新分數,它怎麼找到自己的位置
原書 Step 2 · Data modelsFigure 10 · 為什麼 sorted set 比 RDB 快
64 個節點:基底串列走 62 個,跳躍表只走 11 個
這一步要解決的問題多蓋幾層捷徑,到底能省多少步?
📖 原書 為什麼比 RDB 快
資料少時看不出差別。sorted set 在插入或更新時,元素就自動放到正確順序;新增、查找都是對數時間 O(log n)。
📖 原書 RDB 要算某人的名次,得寫巢狀查詢
SELECT *,(SELECT COUNT(*) FROM leaderboard lb2
WHERE lb2.score >= lb1.score) RANK
FROM leaderboard lb1
WHERE lb1.user_id = {:user_id};原書 Step 2 · Data modelsImplementation using Redis sorted sets
四組指令就能做出排行榜
這一步要解決的問題實際要下哪幾個 Redis 指令?
動手試:在 leaderboard_feb_2021 上下指令
📖 原書 指令與複雜度
ZADD:使用者不在集合就插入,在就更新分數。O(log(n))ZINCRBY:把分數加上指定的增量;不在集合裡就當作從 0 開始。O(log(n))ZRANGE/ZREVRANGE:依分數取一段使用者,可指定順序(range 或 revrange)、筆數、起始位置。O(log(n)+m),m 是要取的筆數(通常很小),n 是集合大小ZRANK/ZREVRANK:以對數時間取得任一使用者在升冪/降冪中的位置
語法:ZINCRBY <key> <increment> <user>。要由高到低,所以用 rev 版本;WITHSCORES 讓結果帶上每人的總分。
原書 Step 2 · Data modelsWorkflow with sorted sets · Figure 11–14
得分、看前十、看自己、看上下四名
這一步要解決的問題四個功能(得分、前 10、我的名次、上下 4 名)各用哪個指令?
📖 原書 1. 得分:每個月建一個新的 sorted set,舊的移到歷史資料儲存。贏一場得 1 分,呼叫 ZINCRBY 在當月的榜加 1;還沒上榜就順便加入。
📖 原書 2. 前 10 名:ZREVRANGE 降冪取,帶 WITHSCORES,回傳 [(user2,score2),(user1,score1),(user5,score5)...]。
📖 原書 3. 我的名次:ZREVRANK,一樣用 rev 版本,由高到低排。
📖 原書 4. 上下各 4 名(不是明確需求):Mallow007 排第 361,用 ZREVRANGE 取 357 到 365。
原書 Step 2 · Data modelsStorage requirement · 輔助的 MySQL 表
2,500 萬人 × 26 bytes ≈ 650 MB:一台 Redis 就夠
這一步要解決的問題2,500 萬人放得進一台 Redis 的記憶體嗎?掛了怎麼辦?
📖 原書 動手算記憶體
長條:占一台 64 GB 記憶體 Redis 的比例(64 GB 是示意)。
📖 原書 CPU 與 I/O:尖峰每秒 2,500 次更新,「這在單台 Redis 伺服器的效能範圍內」。
📖 原書 Redis 掛了怎麼辦
Redis 支援 persistence,但大的 instance 從磁碟重啟很慢。通常會配一個 read replica:主節點掛了就把 replica 升上來,再接一個新的 replica。
白話:persistence=把白板定時拍照存到硬碟;read replica=隨時跟著抄的副本(01 章)。
📖 原書 再加兩張 MySQL 表
| user | |
|---|---|
| user ID | display name |
| 實務上還有很多欄位 | |
| point | ||
|---|---|---|
| user id | score | timestamp |
| 每贏一場一筆 | ||
point 表可以拿來做遊玩歷史,也能在基礎架構故障時重建 Redis 排行榜。小優化:前 10 名最常被查,可以另外 cache 他們的使用者資料,資料量不大。
原書 Step 3Design deep dive · Manage our own services · Figure 15
自己架:sorted set 存分數,MySQL 存名字和頭像
這一步要解決的問題榜上要顯示名字和頭像,這些資料放哪?
📖 原書 Step 3 要談的
- 要不要用雲端:自己管服務,或用 AWS 這類雲端
- Scaling Redis
- 替代方案:NoSQL
- 其他考量
📖 原書 部署有兩條路,看現有基礎架構。第一條自己管:每月建一個 sorted set 存當期的 member 和 score;名字、頭像等其他資料存在 MySQL。取排行榜時,API servers 除了拿 sorted set,還要查資料庫拿對應的名字和頭像。
長期下來太沒效率的話,用一個 user profile cache 存前 10 名玩家的資料。
白話:web servers=接 request 的那群機器;load balancer=帶位員,把 request 分給不同機器(01 章);user profile cache=前 10 名的名字頭像放手邊。
原書 Step 3Build on the cloud · Table 5 · Figure 16–17
建在雲端:API Gateway → Lambda → Redis、MySQL
這一步要解決的問題不想自己管機器的話,雲端上怎麼搭?
| APIs | Lambda function(Table 5) |
|---|---|
GET /v1/scores | LeaderboardFetchTop10 |
GET /v1/scores/{:user_id} | LeaderboardFetchPlayerRank |
POST /v1/scores | LeaderboardUpdateScore |
📖 原書 假設現有基礎架構在 AWS。用兩樣東西:Amazon API Gateway 定義 RESTful API 的 HTTP endpoints、接到後端;AWS Lambda 是最熱門的 serverless 平台之一,不用自己準備或管理 server,需要時才跑,依流量自動擴展。Google 有 Cloud Functions、Microsoft 有 Azure Functions。
📖 原書 遊戲呼叫 API Gateway → 叫對應的 Lambda → Lambda 對儲存層(Redis 和 MySQL)下指令 → 結果回 API Gateway → 回 app。AWS 支援從 Lambda 呼叫 Redis client,也能隨 DAU 成長自動擴展。
📖 原書的建議 Lambda 的 infra 會自動擴展,不用管 scaling、環境設定和維護。如果遊戲從零開始,建議用 serverless。
白話:serverless=不用自己顧機器,有人來才開工;Lambda=AWS 的 serverless 小程式;API Gateway=雲端的大門。
延伸基礎第 6 階 · fixed/hash partition(複習 sharding)懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
名冊太厚要拆成 4 本:依成績分,還是依座號分?
① 先想像
一本放不下,要拆成 4 本。就像學校分班:可以依成績分班,也可以依座號尾數分班。
你猜猜看:依成績分班時,要找「全校前 3 名」,要問幾班?
前幾名一定在最高分那段。代價:低分的人最多,最低分那班最忙。依座號分就反過來:每班一樣忙,但每班都要問。
③ 這叫做 fixed partition、hash partition
fixed partition:依分數範圍分本(1–100 分一本…)。hash partition:把名字算成一個號碼,照號碼分本。sharding:01 章hash:05 章
④ 跟這章的關係
原書到 5 億 DAU 才拆,兩種都比過,最後選 fixed(第 26–29 頁)。
② 動手玩:40 位學生分成 4 班
原書 Step 3Scaling Redis · Fixed partition · Figure 18
5 億 DAU:65 GB、每秒 25 萬次,按分數範圍切
這一步要解決的問題人數變 100 倍,一台放不下,要怎麼拆?先看依分數段拆。
📖 原書 500 萬 DAU 時,不管儲存或 QPS,一台 Redis 都夠。但如果 5 億 DAU(100 倍):最壞 65 GB(650 MB × 100)、250,000 QPS(2,500 × 100),就要 sharding。兩種:fixed 或 hash partition。
- 假設一個月的分數範圍 1–1000,切 10 片,每片 100 分。分數要分布平均,不平均就要調整每片的範圍。分片寫在應用程式碼裡
- 寫入時要知道使用者在哪一片:可以從 MySQL 算他目前分數;更快的做法是另外一個 secondary cache 存 user ID → score
- 分數跨過邊界:要從目前那片移除,加到新的那片
- 前 10 名:從分數最高那片([901, 1000])拿
- 某人名次 = 自己那片裡的名次(local rank)+ 所有更高分片的人數;每片人數用
info keyspace以 O(1) 取得
動手試:mary1934 一路贏上去
白話:sharding=名冊拆成好幾本(第 25 頁);secondary cache=另一份「名字 → 分數」的小抄,用來查他在哪一本。
延伸基礎第 7 階 · scatter-gather懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
4 班各交前 3 名,老師再挑出全校前 3
① 先想像
依座號分班,每一班都可能有高手。老師想知道全校前 3 名,就請每班把自己的前 3 名交上來。
你猜猜看:4 班各交前 3 名,全校前 3 名一定在這 12 張裡嗎?
全校前 3 名,在自己班上一定也是前 3。代價:要等最慢交卷的那班;要的名次越多、班越多,老師要排的卡越多。
③ 這叫做 scatter-gather
scatter-gather:先把同一個問題分頭丟給每一本(scatter),再把答案收回來合併(gather)。
④ 跟這章的關係
原書 hash partition 取前 10 名(Figure 20)、DynamoDB 的 Figure 25 都是這招;Triton 的 086 也是(第 46 頁)。
② 動手玩:4 班各交前 K 名,老師再排
原書 Step 3Hash partition · Figure 19–20
交給 Redis cluster 切:寫入簡單,前 10 名要每片都問
這一步要解決的問題另一種拆法:交給 Redis cluster 依 key 平均分。
📖 原書 第二種:用 Redis cluster,分數很集中、群聚時比較適合。它不用 consistent hashing,而是 hash slot:共 16384 個 slot,CRC16(key) % 16384 算出 slot,加減 node 不用重分所有 key。Figure 19 三個 node:[0, 5500]、[5501, 11000]、[11001, 16383]。
📖 原書 更新:只改對應那片裡的分數。前 10 名比較麻煩:每片拿前 10,由應用程式排序(Figure 20),可以平行查降低延遲。限制:
- K 很大時延遲高:每片回很多筆,還要排序
- 分區越多延遲越高:要等最慢的那片
- 沒有直接算某人名次的辦法
📖 原書的結論 所以傾向第一個:fixed partition。
白話:hash slot=16384 個編號抽屜,key 算出號碼就放進對應的抽屜(hash 見 05 章)。
🗣️ Triton 「因為sorted set只有一個,即使建立了redis-cluster也只會存到其中一台redis上。」182 一個 sorted set 是一個 key,只落在一個 slot;要分片得自己開好幾個 key(第 46 頁)。
原書 Step 3 · 動手玩兩種分片的取捨 · Sizing a Redis node
按分數切還是按 hash 切?看寫入、前 K 名、我的名次
這一步要解決的問題兩種拆法各贏在哪、輸在哪?一台 Redis 要配多大?
📖 原書 Sizing a Redis node
- 寫入密集的應用需要多很多記憶體:故障時要建 snapshot,得容納所有寫入。保險起見,寫入密集就配兩倍記憶體
- Redis 有
redis-benchmark:模擬多個 client 下多個查詢,回報這台硬體每秒能處理幾個 request
白話:這裡的 snapshot=把整個記憶體拍照存到硬碟;benchmark=叫一群假客人來實測。
怎麼看這個互動
上排長條是每片承受的寫入。Fixed:低分的人多,低分那幾片最忙;Hash:平均。下排是查前 K 名時每片要回幾筆:Fixed 只碰最高的一兩片;Hash 每片都回 K 筆、要等最慢的那片。
到這裡你已經會了小結 2 / 4
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
到這裡你已經會了:永遠排好的名冊,和怎麼拆它
- sorted set = 通訊錄(名字 → 分數)+永遠排好的名冊;加分、查名次都是 O(log n)。
- 名冊就是 skip list:多蓋幾層跳格電梯,64 個節點只走 11 個。
- 一台放不下就拆:依分數段(fixed)好找前 10 名、寫入不平均;依 hash 寫入平均,前 10 名要每本都問(scatter-gather)。
下一階要解決的問題
拆開以後,「我第幾名」變得很難算。原書換成 DynamoDB 也一樣,要給玩家什麼才好?
原書 Step 3Alternative solution: NoSQL · Figure 21–22
換成 DynamoDB:Redis 和 MySQL 都拿掉
這一步要解決的問題不用 Redis 和 MySQL,換一種資料庫行不行?
📖 原書 想要的 NoSQL 特性:
- 為寫入優化
- 能在同一個 partition 內依分數有效排序
📖 原書 DynamoDB、Cassandra、MongoDB 都合適,本章用 DynamoDB:fully managed、效能可靠、擴展性好。要用主鍵以外的屬性有效查資料,用 global secondary index(GSI):它包含父表的部分屬性,但用不同的主鍵組織。
📖 原書 假設是西洋棋遊戲的排行榜,初始的表(Figure 22)是 leaderboard 和 user 兩張表的反正規化 view,畫排行榜要的東西都在裡面。可行,但擴展不好:資料越多,要掃整張表才找得到最高分。
白話:NoSQL=不用 SQL 表格的資料庫統稱;GSI=同一份資料用另一種排法再建一份索引;反正規化=把幾張表的欄位抄在一起,查一次就夠。
原書 Step 3Partition key、write sharding · Figure 23–25
整個月都塞進一個 partition 會變熱點,所以後面加上 #p0、#p1…
這一步要解決的問題這個月的資料全擠在同一格,怎麼辦?
白話:partition key=決定放哪一格;sort key=格子裡怎麼排;hot partition=大家擠同一格;write sharding=把一格拆成好幾格分擔寫入。
📖 原書 第一次嘗試:game_name#{year-month} 當 partition key、score 當 sort key(Figure 23)。可行,但高負載會出問題:DynamoDB 用 consistent hashing 把資料分到多個 node,每筆依 partition key 落在一個 node。最近一個月的資料全在同一個 partition,變成 hot partition。
📖 原書 解法:切成 N 個 partition,在 partition key 後面加上編號(user_id % number_of_partitions),叫 write sharding;key 變成 game_name#{year-month}#p{partition_number}。讀寫都變複雜,要仔細權衡。
動手試:partition 要幾個?
延伸基礎第 8 階 · percentile懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
成績單不寫第幾名,寫 PR 值
① 先想像
考完試,成績單不寫「你是第 31,245 名」,而是寫「PR 85」:你贏過 85% 的人。
你猜猜看:全場 1,000 人,你 PR 90,大約排第幾名?
贏過 90% = 在前 10%。1,000 × 10% = 100,大約第 100 名。
③ 這叫做 percentile、cron job
percentile(百分位):贏過百分之幾的人,PR 90 就是前 10%。cron job:每天固定時間自動跑的工作,例如半夜先把門檻算好。
④ 跟這章的關係
原書分片後算不出精確名次,就改告訴玩家「你在前 10–20%」(下一頁)。
② 動手玩:1,000 人的考試(成績是示意)
原書 Step 3分片後的「我的名次」:改給百分位
「你在前 10–20%」可能比「你是第 1,200,001 名」更好
這一步要解決的問題拆開以後算不出精確名次,要給玩家什麼?
📖 原書 跟 Redis 分片一樣,DynamoDB 的做法也沒有直接算出某人相對名次的辦法。但可以拿到百分位,可能就夠了:現實裡告訴玩家「你在前 10–20%」,可能比顯示精確的第 1,200,001 名好。
📖 原書 規模大到要分片時,可以假設各分片的分數分布大致相同。如果成立,就用一個 cron job 分析每片的分數分布,把結果 cache 起來:
10th percentile = score < 100 20th percentile = score < 500 ... 90th percentile = score < 6500
之後就能很快回傳使用者的相對排名(例如第 90 百分位)。
動手試:輸入你的分數
10th、20th、90th 是原書的數字;中間(30th–80th)原書用「...」省略,這裡填的是示意值。
延伸基礎第 9 階 · tie-break懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
三個人都 10 分,白板上誰寫前面?
① 先想像
收攤前,B、C、D 都是 10 分。D 在 19:58 就到 10 分,B 是 20:01,C 最晚,20:05。
你猜猜看:A 12 分,B、C、D 都 10 分,E 8 分。「同分同名次」時,E 是第幾名?
比 E 高分的有 4 個人,所以 E 是第 5 名;三個 10 分的人並列第 2。右邊切兩種排法對照。
③ 這叫做 tie-break、timestamp
tie-break:同分時用來分先後的規則。timestamp(時間戳):記下「幾點幾分幾秒」的那個數字。
④ 跟這章的關係
面試官預設同分同名次;有時間再談打破平手:原書記下「最近一次贏的時間」,早的排前面(下一頁)。
② 動手玩:五位客人
原書 Step 4Faster retrieval and breaking tie
同分時,誰先拿到這個分數誰在前面
這一步要解決的問題兩個人同分時,誰排前面?
📖 原書 Redis Hash 提供 string field 到 value 的對照,可以用在兩件事:
- 存 user id → 使用者物件(要顯示在榜上的資料):比每次去資料庫拿快
- 打破平手:同分時,依誰先拿到這個分數來排。每次加分時,另外存一個 user id → 最近一次贏的時間戳;平手時,時間戳比較舊的排前面
白話:Redis Hash=一個 key 底下一張「欄位 → 值」的小表。
文組版:射氣球攤兩個人都 10 分,老闆看計分卡背面「最後一次得分的時間」,先到 10 分的人排前面。
原書 Step 4System failure recovery · Wrap up
Redis cluster 整個掛了:用 MySQL 的 point 表一筆一筆 ZINCRBY 回來
這一步要解決的問題Redis 整個掛了,排行榜怎麼找回來?
📖 原書 Redis cluster 可能發生大規模故障。因為 MySQL 在每次有人贏一場時都記一筆帶時間戳的資料,可以寫一個腳本:逐一走過每個使用者的每一筆紀錄,每筆呼叫一次 ZINCRBY,必要時離線重建排行榜。
📖 原書 Wrap up
本章做了一個百萬 DAU 等級的即時遊戲排行榜:先看 MySQL 的直覺做法,因為擴展不到百萬使用者而放棄;再用 Redis sorted set 設計;再用分片把 Redis 擴展到 5 億 DAU;最後提出 NoSQL 的替代方案。面試還有時間,可以多談:更快的檢索與平手處理(第 36 頁)、系統故障復原(本頁)。
原書 Chapter summary心智圖 · 點葉子跳到那一頁
原書這一章的全貌
這一步要解決的問題把原書這一章的每一步放在同一張圖上。
到這裡你已經會了小結 3 / 4
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
到這裡你已經會了:原書的整個設計
- 拆開後精確名次很難算:改給 percentile(PR 值),cron job 先把門檻算好。
- 同分:預設同分同名次;要打破平手(tie-break),就比誰先拿到這個分數。
- Redis 整個掛了:用 MySQL 的 point 表,一筆一筆
ZINCRBY回來。
下一階要解決的問題
原書講完了。Triton 自己做過一模一樣的榜,第二版就是原書的設計,結果「再爆掉」。為什麼?
延伸基礎第 10 階 · single thread、hotspot懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
筆只有一枝:店員請再多,白板還是寫不快
① 先想像
白板只有一塊、筆只有一枝,只有老闆能寫,一次寫一筆。平常每秒 2 個人得分,煙火秀時每秒 50 個。
你猜猜看:老闆每秒最多寫 20 筆。多請 3 位店員站旁邊,可是筆只有一枝。每秒最多寫幾筆?
筆只有一枝,人再多也只能排隊等。大家都擠向同一份東西時,加人、加機器都沒用。
③ 這叫做 single thread、hotspot
single thread(單執行緒):一次只做一件事的工人,每台 Redis 都是這樣。hotspot:大家都擠向同一台,只有它被打爆。hotspot:04 章hot key:11 章
④ 跟這章的關係
原書整個月只有一個 sorted set:它只住在一台 Redis,那台只有一條執行緒(第 43 頁)。
② 動手玩:每台機器每秒最多改 20 筆(示意)
Triton 不同意182 · 一百萬隻貓吃罐罐
Triton 的排名榜做了三版:第二版就是原書的設計
「那一個專案嘛,你可以想像系統中有一百萬隻貓,這一百萬隻貓會不停地吃罐罐。現在需要做一個排名榜,去半即時(資料延誤最長一分鐘吧)地顯示首一千隻吃了最多罐罐的貓。」🗣️ Triton 本人說 182-資料結構很重要,他媽的重要!,用即時排名來講述.md
你猜猜看:v2 把一百萬隻貓全放進一個 sorted set,每吃一罐就改一次分數。原書這樣做會出什麼事?
每次 O(log n) 都很快,但一百萬隻貓的每一次加分,都排隊等同一台 Redis 的同一條執行緒(第 40 頁「筆只有一枝」)。按左邊 v2 看 Triton 怎麼說。
Triton 不同意 · 動手玩開服、新年倒數:「開罐罐派對」
平均的 5 倍不是尖峰:大家同一秒開趴時,哪台 Redis 先死?
你猜猜看:原書假設尖峰 = 平均 × 5。新年倒數那一秒,大家同時開罐罐,流量會是平均的幾倍?
平均 × 5 是「一整晚比較忙」;倒數是「同一秒」。左邊按「開服/新年倒數」:流量衝到 ×40,放 sorted set 的那台先變紅。
「而更致命的是:原來貓咪也會開趴的,開趴時是超級大量貓咪一起開罐罐派對。像是新年倒數便一起開罐罐狂歡,瞬間有超高流量進了單一台redis。」🗣️ Triton 本人說 182 · v2
「首先,在redis中會有 cat_id --> 其所吃罐罐數量的key-value pairs,散落在redis cluster上的每一個node上。(所以流量也會平均地分散到每一台redis上)然後,當一隻貓吃完了罐罐,更新了其的key-value pairs的數值後。再對比第一千位貓的罐罐數量(這部份會再做caching),如果是超過了,會讓他進入首一千的名單時,才會更新sorted set。」🗣️ Triton 本人說 182 · v3
🗣️ 「“Happy new year”問題 – 用戶在同秒發訊息」051 · 第 6 頁;原書的尖峰是「平均 × 5」(第 6 頁)。
Triton 不同意087 · 074 · 088 · 089 · 029
為什麼加 node 救不了:一份資料只住一台,那台只有一條執行緒
你猜猜看:Redis cluster 從 6 台加到 16 台,原書那個 sorted set 的負載會怎樣?
cluster 是把「不同的 key」分給不同機器;一個 sorted set 就是一個 key,永遠只住一台,而那一台一次只做一件事。
🗣️ Triton 本人說 Redis 是 single thread
「在 redis cluster,一份資料只存放在一個 node上」「每一個 node都是 single thread的」壞處:「跟 node.JS一樣,只要一個工作要跑比較久,該 node的 latency立即衝破宇宙」「容易發生 hotspot,沒法以增加硬體手段解決」087 · 第 8 頁
「在 Redis,如果有人在跑 CPU-intensive工作, 沒跑完前所有人都會被卡住要等待」「一般來說,不建議使用 redis sorted sets」088 · 第 6 頁
🗣️ Triton 本人說 他在 RDBMS 課就舉過排名榜
「沒有思考 hotdata hotspot(續) 例子:用 redis sorted set來存全體用戶的分數排名 榜 – 所有用戶的分數改動都需要改動這個 sorted set – 單一的 sorted set只存到單一的 redis上 – 所有用戶的分數改動都去了單一的 redis上 方案 – 對排名榜作 sharding by userID ? – 只存首X個高分數用戶進 redis ?」074 · RDBMS 課程第四課第 39 頁
🔭 推論 兩個「方案」剛好是原書(晚到 5 億 DAU 才 shard)和 Triton 182 的 v3(只存前 X 名)。
Triton 不同意089 · 029 · 兩句常被引用的話要看上下文
「avoided at all cost」在講 priority queue;O(nlogN) 是筆記的寫法
你猜猜看:Triton 寫過「Sorted Set should be avoided at all cost」。意思是排行榜絕對不能用 sorted set 嗎?
那句的上下文是「能不能用 redis 做 priority task queue」。講排行榜時他的說法比較溫和:088「一般來說,不建議」;151 他自己的公司一開始也用 sorted set(第 51 頁)。
文組翻譯
白板(sorted set)本身沒有錯;錯的是讓 2,500 萬人都去改同一塊白板。人少的時候直接用沒關係。
那句「avoided at all cost」的上下文
🗣️ 「Can you use redis to implement a priority task queue? – Sorted Set should be avoided at all cost – For fault tolerance appliation, you should use rabbitMQ instead」089 · Extras
這句是在談拿 sorted set 當 priority queue,不是在談排行榜;排行榜他的說法是 088 的「一般來說,不建議」加上 088 的 top-N 規則(下一頁)。
📝 上課筆記 「redis 是 single thread 的。你的 operation 是 O(1) 的,當然很OK 如果是 O(n) 或 O(wholeDB) 通常會死掉。」「Redis Zrange 代表每次的 operation O(nlogN) 的。」「我們的實戰經驗,單台的 redis 大約能支持 C10K。」029-Redis.md(無署名的課堂筆記) 筆記寫 O(nlogN),原書寫 O(log(n)+m),以原書(Redis 文件)為準。
延伸基礎第 11 階 · KV、top-N懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
白板只寫前 10 名:大部分人得分時,老闆不用動筆
① 先想像
每位客人自己拿一張計分卡,得分就改自己的卡。只有分數超過白板上的第 10 名,才去找老闆改白板。
你猜猜看:200 人一晚得分 2,000 次,白板只寫前 10 名。大約要改白板幾次?
只有榜上的人、或剛好擠進榜的人得分才要改白板。10 人占 200 人的 5%,2,000 × 5% ≈ 100,再加上擠進榜的那幾次。
③ 這叫做 KV、top-N
KV(key-value):一個名字對一個數字,像每人自己的計分卡。top-N:只維護前 N 名的榜。top k:13 章
④ 跟這章的關係
Triton 182 的 v3:每隻貓的分數用 KV 散在整個 cluster,超過第 1000 名才更新 sorted set;088 是只存前 2N 名(下一頁)。
② 動手玩:200 位客人,一晚得分 2,000 次
Triton 的做法088 · 086 · 實作 top-N item
超過一千萬個 item、只要前 N 名:只維護前 2N 名的 list
「實作 top-N item 如果 item count < 1M,單純把全部 item用 redis sorted set來存就好 如果 item count >10M,然後 N <= 1000時 以 List來存 Top 2N sorted item」🗣️ Triton 本人說 088-redis-intro.pdf.md · 第 21 頁
🗣️ 「有 new item時 – 看看其 score是否高於 list的最後一個 item 如果比較高,就把 new item insert進 list 有 update item時 – 如果其 new score比最後一個 item還低,就把 item從 list丟掉 否則,更新其在 list內的位置 如果 list count > 2N,就丟掉多餘的 如果 list count <= 1.1N,就從資料庫補資料」088 · 第 22 頁
🗣️ 寫入太多時的分片:「用 Redis Sorted Set 來存首一萬個物品分數,會讓單一台 redis CPU太高」「我們改用16個 hash – 每一個 hash 只負責mod (itemId, 16) == n 的物品 – 每個 hash 只存首一萬個物品 要得到首 10000 個物品,只需要把 16 個 hash 都拿出來,然 後再跑一次 sorting 便好」086 · 第 25–26 頁
🔭 推論 原書是 2,500 萬 MAU、只要前 10 名:照 088 的門檻早就該用 top-2N list。086 也是 scatter-gather(原書 Figure 20),但每片只放前 N 名。1M–10M 之間 Triton 沒說。
你猜猜看:2,500 萬玩家、只要顯示前 10 名。照 Triton 088 的 top-N 規則,Redis 裡該放什麼?
item 超過一千萬、N ≤ 1000 時,只存前 2N 名。其他人的分數放資料庫或 KV;得分時先跟榜尾比一下,沒超過就不碰 list。
動手試:N = 5,list 最多 2N = 10 筆
延伸基礎第 12 階 · real-time、snapshot懂的人可以跳過
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
開票看板每幾分鐘才更新,有人抱怨嗎?
① 先想像
選舉開票夜,電視台的看板不是每開一票就跳一次,而是每幾分鐘更新一次。大家看的是同一份數字,也沒人抱怨。
你猜猜看:每秒 2,500 次得分。如果榜每 1 分鐘才重算一次,一分鐘要算幾次榜?
不管這一分鐘有多少人得分,榜只算 1 次。代價:上榜最晚要等 1 分鐘才看得到。
③ 這叫做 real-time、snapshot
real-time(即時):每次變動立刻反映在榜上。snapshot(快照):某一刻拍下來、之後不再改的那份榜。翻頁時多出新的:11 章
④ 跟這章的關係
原書要求即時。Triton 自己的榜是半即時,翻頁時用 ?ts= 指定看哪一張快照(下一頁)。
② 動手玩:每秒 2,500 次得分(原書的尖峰)
Triton 補充087 · 088 · 持續變動中的排名榜怎麼分頁
翻到第 2 頁,同一個人又出現一次:用 ?ts= 鎖住快照
你猜猜看:你在看第 1 頁(第 1–5 名),這時第 12 名衝上第 1 名。你再按第 2 頁,會看到什麼?
大家都往後擠一格:原本的第 5 名變第 6 名,出現在第 2 頁的第一個;衝上第 1 名的那位你兩頁都沒看到。下面依序按 ① ② ③ 驗證。
「案例 2: data snapshotting 想像一下:你在看一個持續改動中的排名榜 如果沒有 snapshotting,剛好第十名的物品變第十一,然後你拿 Page 2的資料 – 你就會看到重覆的物品 RESTful endpoint: – GET /v1/leaderboard?ts=1561042015」🗣️ Triton 本人說 087-redis-2019.pdf.md · 第 25 頁
🗣️ v1:「建立 crontab,每一分鐘從資料庫拿建立新的 snapshot 丟到 redis」,每個 DataXXX-<ts> 是一個 hashSet,「P1是對應第 1 – 50個 items」;v2:跟上一份相同就只存 ts。snapshot「是永遠不會改動的資料 所以,其 localcache TTL應該跟 Redis 相同的」087 · 第 26–28 頁
🗣️ 「用戶頁面顯示的,是「某時間點的 snapshot」 而不是「即時資訊」」088 · 第 8 頁
🔭 推論 原書要求即時,「不可以呈現批次處理的歷史結果」,Triton 自己的榜是延誤最長一分鐘(182)。原書的「上下各 4 名」(ZREVRANGE 357 365)在一個一直變的 sorted set 上,同樣會遇到這頁的問題。
Triton 補充087 · 031 · 081 · 重建之後怎麼知道是對的
Redis 一定會掉資料;原書的 point 表是對的,再加一道對帳
🗣️ 「Redis的預設,是每 10000個WRITE才會寫入 Harddisk的」「如果 Redis當掉,一定會有 data loss的」所以正常人:「用作 caching,資料同時存放於主資料庫」「儲存沒了也死不了人的 Hot Data」087 · 第 6 頁
🗣️ 遊戲剛好適合:「Game data is usually fault-tolerance – Users will f**k the developers and keep playing」;但也要「Must prepared for the inconsistent state after crash-and-recovery」031-Redis-Game-Server.pdf.md(Triton Ho@Mars' Potato)
🗣️ 線上遊戲的對帳:「正常人不會沒事去做MRI,而是每年做費用低很多的血液檢查」,例行檢查要問的是「所有用戶帳戶的加總是否能對上?」加一張 banker 表,「系統中的user_balance和banker的加總應該是永遠都是零的。」081
🔭 推論 原書把 MySQL 的 point 表當真相、Redis 當可重建的 hot data,和 087 一致。套 081:重建或當機恢復後,先比「point 表總分 = Redis 裡所有人的分數總和」,對不上才逐人比對(血液檢查 → MRI)。
你猜猜看:Redis 預設不是每次寫入都存進硬碟。當機重開後,排行榜會怎樣?
還沒存進硬碟的那幾次加分就沒了。原書另外在 MySQL 記每一場(point 表),所以補得回來;問題是:你怎麼知道少了誰?
動手試:當機、對帳、重建
Triton 補充原書周邊的設計選擇
Lambda 的 auto-scaling、要不要 MQ、名字怎麼查、分區鍵加編號
你猜猜看:流量暴增 40 倍時,Lambda 會自動多開很多份。那台放 sorted set 的 Redis 會跟著變多台嗎?
Lambda 多開的是「店員」;白板(Redis 裡那個 sorted set)還是只有一塊。下面四格是原書周邊的設計選擇,第一格就是這件事。
Auto-scaling 救不了 Redis
🗣️ 「先說結論: Auto-scaling是用來省錢的 一般用在 App. Server層,別用在 DB層 流量上升是慢慢的,不是爆發性的」051 · 第 5 頁;Redis「實務上當成stateful會比較安全」,stateful 的 HA「請使用像AWS RDS multi-AZ這些別人建好的方案」017
🔭 推論 原書推薦 serverless 是因為會自動擴展;但 Lambda 擴展的是無狀態的那一層,後面那一台放 sorted set 的 Redis 還是只有一台。
不放 MQ:同意
🗣️ 「把工作先丟MQ再慢慢處理,一般而且有3個原因」:要跑很久的工作、慢慢做也死不了人的工作、「你家主管不知從那邊聽到MQ好棒棒高大上」185;「如果系統還沒到每秒1K Message的,kafka對你會是overkill。」138
🔭 推論 原書因為「這不是明確需求」而不放 Kafka,和這個判準一致;真的有多個 consumer 才放。
名字和頭像:一次拿回來
🗣️ 「Anti pattern: data size-dependent IO operations」:「一筆一筆地把ActivityHistory.UserID轉成User.displayName 如果有 1000筆ActivityHistory,就跑 1000次 redis GET」,正確是「以 redis MGET,一次過拿回」088 · 第 13 頁;SQL 也一樣,一筆一個 query 光 overhead 就「10 * 5ms = 50ms」150
🔭 推論 原書 Figure 17 的 ② Fetch user details:前 10 名的資料要一次 MGET 或一個 IN (...),不要 10 次來回。
容量用壓測量,write sharding 他也用過
🗣️ 「平日做stress testing去正確設定好系統容量,和設定好每一層的max_conn之類的參數囉。」155 原書也說用 redis-benchmark、benchmark 決定 partition 數,方向一致。
🗣️ 熱門的 banker 紀錄:「同種類的banker record可以不止有一個,而是n個。……以hash(userID) % n來決定也行。」081 🔭 這就是原書 DynamoDB 的 user_id % number_of_partitions。
Triton 同意原書做對的地方 · 別把 Triton 讀成教條
先用最簡單的,爆了再寫演算法;但要先知道 N 有多大
✅ 一開始用 sorted set 沒關係
🗣️ 「其實我們公司,其要面對C10K的系統中,某個很常用排行榜的功能最初也只是用redis的sorted set功能去支持的。等到我們redis爆了不少次後,我們才決定寫算法去解這個問題的。」151
那篇的標題就是「在專案開始的第一天,你首先需要的是normalization而絕對不是optimization。」
✅ 先算 N
🗣️ 「如果才 10000 個點 單純 2 層 for-loop , O(n^2) solution 吧」「如果 n > 1M 則肯定不能暴力解」064;088 的 top-N 規則也是先看 item 數(< 1M 直接 sorted set)。
🔭 原書從「如果規模不重要,且只有少數使用者」的 RDB 開始、再估 DAU 和 QPS,順序是對的;差在估出 2,500 萬人之後沒換資料結構。
✅ Redis 適合遊戲的 hot data
🗣️ 「For high traffic game server, Redis is still easier than a group of RDBMS server.」「Memory is cheap and WILL BE cheaper」031
原書把真相留在 MySQL 的 point 表、Redis 只放可重建的榜,符合 087 的「資料同時存放於主資料庫」。
✅ 用近似換效能
🗣️ 「In the world of >10K QPS, consistency is usually sacrificed for performance」089
🔭 原書分片後改給百分位(第 34 頁),和 Triton 只算前 1000 名、其他人不給精確名次,是同一種取捨。
✅ Scatter-gather
086 的 16 個 hash 各存前一萬、拿出來再排一次,就是原書 Figure 20 的 scatter-gather;差別是每片只放前 N 名,不是所有人。
✅ 每月一個新榜,舊資料搬走
🗣️ 談遊戲交易紀錄的保留:「你愛用delete不是不行,但是常見手法是用table partitioning再配上truncrate table」081
🔭 原書每月開新 sorted set、舊的移到歷史儲存;MySQL 的 point 表一直長,照 081 依月份 partition,過期整片 truncate。
到這裡你已經會了小結 4 / 4
- QPS
- O(log n)
- Redis
- sorted set
- skip list
- partition
- scatter-gather
- percentile
- tie-break
- hotspot
- top-N
- snapshot
到這裡你已經會了:Triton 怎麼修
- 一個 sorted set 只住一台、只有一條執行緒:「開罐罐派對」時那台就是 hotspot,加 node 沒用。
- 每人的分數用 KV 散在整個 cluster;只有超過第 1000 名的才碰 sorted set(top-N)。
- 排行榜不一定要即時:半即時、翻頁用
?ts=的 snapshot,不重複也不漏。
12 階全部走完了
下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。
一句話記住
每個人的分數各自記,
白板上只寫前一千名。
原書對的地方
- 分數只在 server 端算,client 不能直接報
- 沒有明確需求就不放 Kafka
- 真相放 MySQL 的 point 表,Redis 可重建
- skip list、ZINCRBY / ZREVRANGE / ZREVRANK 的用法
- 分片後用 scatter-gather、百分位
Triton 不同意 / 原書沒講
- 2,500 萬人全放一個 sorted set:只住一台、單執行緒
- 尖峰不是平均 × 5:「開罐罐派對」是同一秒
- 加 node、加 Lambda 都救不了一個熱 key
- 移動中的榜分頁會重複、漏掉
Triton 的做法
- 每人一個 KV 計數,平均散在 cluster
- 超過第 1000 名的分數(cache)才碰 sorted set
- >10M 個 item、N ≤ 1000:只存前 2N 名的 list
- 分頁用
?ts=快照;當機後先做總和對帳
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源(materials/core)與原書對照
Triton 本人的講義 / 文章
- 182-資料結構很重要,他媽的重要!,用即時排名來講述.md — 一百萬隻貓、半即時(延誤最長一分鐘)前 1000 名;v1 SQL 全表 group by + TTL 一分鐘;v2 單一 sorted set 只住一台、開罐罐派對;v3 KV 散在 cluster + 只放前 1000 名、比較第 1000 名(cache)
- 088-redis-intro.pdf.md — 第 6 頁 single thread、不建議 sorted sets;第 8 頁頁面是 snapshot;第 13 頁 MGET;第 21–22 頁 top-N:<1M sorted set、>10M 且 N≤1000 存 top 2N list、插入/更新/丟掉/≤1.1N 補資料
- 087-redis-2019.pdf.md — 第 6 頁每 10000 個 write 才寫硬碟、一定會 data loss;第 8 頁一份資料一個 node、single thread、hotspot 加硬體解決不了;第 25–28 頁
?ts=snapshot - 074-lesson4.pdf.md 第 39 頁 sorted set 排名榜的 hotspot · 086-redis-2018.pdf.md 第 25–26 頁 16 個 hash 各存前一萬 · 089-redis-ratelimit.pdf.md Extras「Sorted Set should be avoided at all cost」(priority queue 的上下文)、More thought
- 031-Redis-Game-Server.pdf.md(By Triton Ho@Mars' Potato)遊戲資料 fault-tolerance、crash 後的不一致 · 081 線上遊戲對帳、banker 加總為零、n 個 banker · 151 公司排行榜最初也用 sorted set
- 051 auto-scaling 是省錢用、Happy new year 問題 · 017 Redis 當 stateful、用別人建好的 HA · 185 MQ 三個原因 · 138 <1K msg/s overkill · 150 一筆一個 query 的 overhead · 155 stress testing · 064 先看 n
上課筆記(📝):029-Redis.md(無署名的 Redis 課堂筆記:single thread、ZRANGE O(nlogN)、單台約 C10K)。未引用:006(029 的 Notion 版)、053(Roy 的 redis intro 筆記)。
原書對照
Alex Xu & Sahn Lam, System Design Interview Vol.2 Ch.10。開場與 Figure 1、Step 1 問答(第 5 頁);需求與粗估(6);API design 與 Table 1–3(7);High-level architecture 與 Figure 2(8);client 報分、MQ 與 Figure 3–4(9);Relational database solution、Figure 5–7、Table 4(10–12);Redis sorted set 與 Figure 8(16);Skip list 與 Figure 9–10(18–19);Redis 指令(20);Workflow 與 Figure 11–14(21);Storage requirement、user/point 表(22);Manage our own services 與 Figure 15(23);Build on the cloud、Table 5、Figure 16–17(24);Scaling Redis、Fixed partition 與 Figure 18(26);Hash partition 與 Figure 19–20(28–29);Sizing a Redis node(29);NoSQL 與 Figure 21–22(31);write sharding 與 Figure 23–25(32);百分位(34);Faster retrieval and breaking tie(36);System failure recovery、Wrap up(37);Chapter summary(38)。原書 25 張圖與章末心智圖都依原書的圖說與描述重繪,不是原圖;AWS、Redis、MySQL 的 logo 不重繪,畫成有標籤的形狀。
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 12 階(第 4–47 頁,頁首標「延伸基礎」);小結(14、30、39、52);名詞小卡(54);Triton 頁的「先猜再看」(41–50)。射氣球攤、分班、電梯、PR 值是虛構的示範情境,示意數字不是實測值。
一個可以直接問自己的問題
你的排行榜上有幾個人?每一次加分,是所有人都去改同一個資料結構,還是只有擠進前 N 名的人才去改?