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 分。老闆有三種記分法,右邊是「過去一秒」老闆動了幾次筆:

① 每次有人得分,就把 200 張計分卡收回來重排0
② 一本永遠排好序的大名冊,每次得分就擦掉重寫那一行0
③ 計分卡各自拿著,只有分數超過白板第 10 名才改白板0

① 是原書第一個試的 MySQL 排序;② 是原書的 Redis sorted set;③ 是 Triton 的做法。② 看起來不多,但全部的筆都落在同一本名冊上。按「一群人同時開射」看看(長條是對數刻度)。

學習地圖本章的概念階梯

今天爬 12 階。每一階只用前面講過的東西。

  1. 1QPS每秒破幾顆氣球
  2. 2O(log n)翻幾張卡才找到
  3. 3Redis手邊的白板
  4. 4sorted set永遠排好的名冊
  5. 5skip list跳格電梯
  6. 6partition名冊拆成幾本
  7. 7scatter-gather每班交前幾名
  8. 8percentilePR 值
  9. 9tie-break同分誰先
  10. 10hotspot筆只有一枝
  11. 11top-N白板只寫前幾名
  12. 12snapshot每分鐘拍一張

第 1–3 階 · 一顆氣球破掉之後

要回答:為什麼 MySQL 排名會越來越慢?

第 4–5 階 · 永遠排好的名冊

要回答:sorted set 怎麼做到加分、查名次都很快?

第 6–9 階 · 名冊拆成好幾本

要回答:拆開後怎麼找前 10 名、我第幾名、同分怎麼排?

第 10–12 階 · Triton 的修法

要回答:筆只有一枝怎麼辦?排行榜真的要即時嗎?

全程只用一個攤位:夜市射氣球攤(虛構)

客人 = 玩家(user)射破一顆氣球 = 贏一場、+1 分店員確認氣球真的破了 = game service掛在攤位上的白板 = 排行榜(leaderboard)每人手上的計分卡 = 自己的分數寫白板的老闆 = Redis

200 位客人、白板寫前 10 名。每爬 3–4 階,有一頁「到這裡你已經會了」。

延伸基礎第 1 階 · QPS(複習 DAU、尖峰)懂的人可以跳過

  1. QPS
  2. O(log n)
  3. Redis
  4. sorted set
  5. skip list
  6. partition
  7. scatter-gather
  8. percentile
  9. tie-break
  10. hotspot
  11. top-N
  12. snapshot

一晚破 36,000 顆氣球,每秒有幾顆?

① 先想像

夜市晚上 6 點開到 11 點,客人陸陸續續來射氣球。9 點煙火秀一開始,大家同時舉槍。

你猜猜看:一晚 5 小時(18,000 秒)共破 36,000 顆,平均每秒幾顆?

③ 這叫做 DAU、QPS

DAU:每天有幾個人來玩。QPS:每秒有幾次 request(這裡是每秒加幾次分);要看最忙那一秒,不看平均。DAU:02 章QPS:02 章尖峰:02 章

④ 跟這章的關係

原書從 500 萬 DAU 算出尖峰每秒 2,500 次加分(第 6 頁)。Triton 會問:新年倒數那一秒呢?

② 動手玩:同一個攤位,三個時段

—平均每秒—最忙那一秒

原書 Step 1釐清需求 · Figure 1

面試一開始:分數怎麼算、誰上榜、多即時?

這一步要解決的問題分數怎麼算、誰上榜、多即時?這三件事決定後面用什麼資料結構。

📖 原書 應徵者 × 面試官

應徵者問面試官答
排行榜的分數怎麼算?贏一場得一分。每個使用者有一個總分,每贏一場加一分
所有玩家都上榜嗎?是
排行榜有時間區段嗎?每個月開一場新錦標賽,開一個新排行榜
只在乎前 10 名嗎?顯示前 10 名,以及特定使用者的名次;有時間的話,也討論怎麼回傳某人上下各 4 名
一場錦標賽多少使用者?平均 DAU 500 萬、MAU 2,500 萬
平均每人打幾場?每人每天平均 10 場
同分怎麼排?同分同名次;有時間再談怎麼打破平手
要即時嗎?要,即時或盡量接近即時;不可以呈現批次處理的歷史結果

白話:DAU=每天有幾個人來玩;MAU=一個月內來過幾個人;錦標賽=每個月一場、重新算分的比賽。

📖 原書 Figure 1Leaderboard:排名、玩家、分數(依原書內容重繪)

📖 原書 什麼是排行榜:完成任務或挑戰就得分,分數最高的在最上面。排行榜除了顯示領先者,也要顯示使用者自己在哪裡。

最後一題「要即時」先記住,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 不能直接改分數。

FieldDescription(Table 1)
user_id贏得遊戲的使用者
points贏這場拿到的點數
NameDescription(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 管排行榜

這一步要解決的問題一場勝利從手機到排行榜,要經過哪幾站?

📖 原書 Figure 2High-level design(依原書內容重繪)

📖 原書 流程:

  1. 玩家贏了,client 送 request 給 game service
  2. game service 確認這場勝利有效,呼叫 leaderboard service 更新分數
  3. leaderboard service 更新 leaderboard store 裡這個人的分數
  4. 玩家直接呼叫 leaderboard service 拿資料:a. 前 10 名;b. 自己的名次

白話:service=專做一件事的一組程式;leaderboard store=排行榜存放的地方(下面會比較 MySQL 和 Redis)。

文組版:射氣球攤的店員(game service)確認氣球真的破了,才去跟寫白板的老闆(leaderboard service)報分;客人想看榜,直接看白板。

原書 Step 2兩個被否決的替代方案 · Figure 3–4

為什麼不讓 client 直接報分?要不要中間放個 MQ?

這一步要解決的問題分數可以讓玩家自己報嗎?中間要不要放一台排隊的號碼機(MQ)?

📖 原書 Figure 3Who sets the leaderboard score(依原書內容重繪)

📖 原書 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=依分數由高到低排。

📖 原書 Figure 5Leaderboard table(依原書內容重繪)

延伸基礎第 2 階 · O(n) 與 O(log n)懂的人可以跳過

  1. QPS
  2. O(log n)
  3. Redis
  4. sorted set
  5. skip list
  6. partition
  7. scatter-gather
  8. percentile
  9. tie-break
  10. hotspot
  11. top-N
  12. snapshot

「我第幾名?」要翻幾張計分卡才知道?

① 先想像

200 張計分卡攤在桌上。想知道你第幾名,只能一張一張數「比我高分的有幾張」。卡片如果已經依分數排好,就能像查字典一樣從中間翻。

你猜猜看: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 張一張一張數(最壞)對半翻(最壞)
1616 張5 次
1,0001,000 張10 次
1,000,0001,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)懂的人可以跳過

  1. QPS
  2. O(log n)
  3. Redis
  4. sorted set
  5. skip list
  6. partition
  7. scatter-gather
  8. percentile
  9. tie-break
  10. hotspot
  11. top-N
  12. snapshot

分數收在後面倉庫,還是寫在手邊的白板?

① 先想像

老闆的帳本鎖在後面倉庫,每查一次要走過去翻。白板就掛在手邊,看一眼就好,可是一下大雨就會被沖掉。

你猜猜看:夜市停電又下大雨,隔天哪一份分數還在?

③ 這叫做 Redis、in-memory

Redis:大家共用的白板,讀寫很快。in-memory:資料放在記憶體(白板)而不是硬碟(倉庫),斷電就沒了。Redis:04 章cache:01 章database:01 章

④ 跟這章的關係

原書把排行榜放在 Redis 的 sorted set(下一階),每一場勝利另外記進 MySQL(第 22 頁)。

② 動手玩:查 100 次分數,各要多久?

倉庫來回一趟 1 分鐘(示意)
—
看白板一眼 1 秒(示意)
—

倉庫的帳本(MySQL)

    手邊的白板(Redis)

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

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. snapshot

      到這裡你已經會了:為什麼 MySQL 排名會越來越慢

      下一階要解決的問題

      白板上要用什麼形狀的名冊,才能一邊加分、一邊很快查到名次?

      延伸基礎第 4 階 · sorted set懂的人可以跳過

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. snapshot

      一本永遠排好的名冊:有人加分,只搬他那一行

      ① 先想像

      老闆準備兩樣東西:一本「名字 → 分數」的通訊錄,翻名字就找到;一本依分數由高到低排好的名冊。

      你猜猜看:mary 從 850 分變 880 分,名冊要改幾行?

      ③ 這叫做 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 是「依分數排好的名冊」,加了好幾層書籤,可以很快跳到中間。下一頁拆開看那幾層書籤。

      📖 原書 Figure 8February leaderboard is represented by the sorted set(依原書內容重繪;alt 只舉了 user10、user20 兩個名字,沒有列分數,分數是示意)

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

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. snapshot

      排名榜上的跳格電梯:到 45 樓要停幾次?

      ① 先想像

      64 層的百貨公司有三種電梯:每層都停的、每 4 層停一次的、每 16 層停一次的。

      你猜猜看:到 45 樓,每層停的電梯要停 44 次。先搭每 16 層停的、再換每 4 層停的,大約停幾次?

      ③ 這叫做 skip list、level

      skip list(跳躍表):在排好序的名冊上,多蓋幾層「跳著停」的捷徑。level:第幾層捷徑;越上層停得越少。

      ④ 跟這章的關係

      sorted set 的名冊就是 skip list。找「45 分該插在哪」也是從最上層跳下來(第 18、19 頁)。

      ② 動手玩:從 1 樓出發

      —這樣搭要停幾次—只搭每層停的

      原書 Step 2 · Data modelsSkip list · Figure 9

      跳躍表:在排好序的串列上面,蓋幾層「隔一個跳一個」的捷徑

      這一步要解決的問題排好序的名冊,要怎麼很快找到「45 分該插在哪」?

      📖 原書 Figure 9Skip list:找 45(依原書內容重繪)

      動手試:ZADD 一個新分數,它怎麼找到自己的位置

      原書 Step 2 · Data modelsFigure 10 · 為什麼 sorted set 比 RDB 快

      64 個節點:基底串列走 62 個,跳躍表只走 11 個

      這一步要解決的問題多蓋幾層捷徑,到底能省多少步?

      📖 原書 Figure 10Skip list with 5 levels of indexes(依原書內容重繪;alt 描述底部約 40 個節點,依內文「基底要走 62 個節點」畫 64 個)
      0走訪的節點

      📖 原書 為什麼比 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 名)各用哪個指令?

      📖 原書 Figure 11A user scores a point(依原書內容重繪;alt 說原圖沒有畫箭頭,這裡用虛線表示隱含的呼叫)
      
          

      📖 原書 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 IDdisplay name
      實務上還有很多欄位
      point
      user idscoretimestamp
      每贏一場一筆

      point 表可以拿來做遊玩歷史,也能在基礎架構故障時重建 Redis 排行榜。小優化:前 10 名最常被查,可以另外 cache 他們的使用者資料,資料量不大。

      原書 Step 3Design deep dive · Manage our own services · Figure 15

      自己架:sorted set 存分數,MySQL 存名字和頭像

      這一步要解決的問題榜上要顯示名字和頭像,這些資料放哪?

      📖 原書 Figure 15Manage our own services(依原書內容重繪)

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

      這一步要解決的問題不想自己管機器的話,雲端上怎麼搭?

      📖 原書 Figure 16Score a point(依原書內容重繪;alt 說寫入 MySQL 那條原圖沒畫箭頭,依內文「Lambda 對 Redis 和 MySQL 下指令」用虛線)
      APIsLambda function(Table 5)
      GET /v1/scoresLeaderboardFetchTop10
      GET /v1/scores/{:user_id}LeaderboardFetchPlayerRank
      POST /v1/scoresLeaderboardUpdateScore

      📖 原書 假設現有基礎架構在 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)懂的人可以跳過

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. 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。

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

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. snapshot

      4 班各交前 3 名,老師再挑出全校前 3

      ① 先想像

      依座號分班,每一班都可能有高手。老師想知道全校前 3 名,就請每班把自己的前 3 名交上來。

      你猜猜看:4 班各交前 3 名,全校前 3 名一定在這 12 張裡嗎?

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

      📖 原書 Figure 19Hash partition(依原書內容重繪)

      📖 原書 第二種:用 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

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. snapshot

      到這裡你已經會了:永遠排好的名冊,和怎麼拆它

      下一階要解決的問題

      拆開以後,「我第幾名」變得很難算。原書換成 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=同一份資料用另一種排法再建一份索引;反正規化=把幾張表的欄位抄在一起,查一次就夠。

      📖 原書 Figure 21DynamoDB solution(依原書內容重繪;原圖是 AWS 圖示,這裡畫成有標籤的形狀;alt 說元件之間沒有畫連線)

      原書 Step 3Partition key、write sharding · Figure 23–25

      整個月都塞進一個 partition 會變熱點,所以後面加上 #p0、#p1…

      這一步要解決的問題這個月的資料全擠在同一格,怎麼辦?

      📖 原書 Figure 23Partition key and sort key(依原書內容重繪;分數是示意)

      白話: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懂的人可以跳過

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. snapshot

      成績單不寫第幾名,寫 PR 值

      ① 先想像

      考完試,成績單不寫「你是第 31,245 名」,而是寫「PR 85」:你贏過 85% 的人。

      你猜猜看:全場 1,000 人,你 PR 90,大約排第幾名?

      ③ 這叫做 percentile、cron job

      percentile(百分位):贏過百分之幾的人,PR 90 就是前 10%。cron job:每天固定時間自動跑的工作,例如半夜先把門檻算好。

      ④ 跟這章的關係

      原書分片後算不出精確名次,就改告訴玩家「你在前 10–20%」(下一頁)。

      ② 動手玩:1,000 人的考試(成績是示意)

      —精確名次:要數全部 1,000 人—查門檻表:只看 9 條線

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

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. 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 是第幾名?

      ③ 這叫做 tie-break、timestamp

      tie-break:同分時用來分先後的規則。timestamp(時間戳):記下「幾點幾分幾秒」的那個數字。

      ④ 跟這章的關係

      面試官預設同分同名次;有時間再談打破平手:原書記下「最近一次贏的時間」,早的排前面(下一頁)。

      ② 動手玩:五位客人

      原書 Step 4Faster retrieval and breaking tie

      同分時,誰先拿到這個分數誰在前面

      這一步要解決的問題兩個人同分時,誰排前面?

      
          

      📖 原書 Redis Hash 提供 string field 到 value 的對照,可以用在兩件事:

      1. 存 user id → 使用者物件(要顯示在榜上的資料):比每次去資料庫拿快
      2. 打破平手:同分時,依誰先拿到這個分數來排。每次加分時,另外存一個 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心智圖 · 點葉子跳到那一頁

      原書這一章的全貌

      這一步要解決的問題把原書這一章的每一步放在同一張圖上。

      📖 原書 Chapter summaryGaming Leaderboard 心智圖(依原書內容重繪)
      點任何一片葉子,跳到簡報裡講它的那一頁。

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

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. snapshot

      到這裡你已經會了:原書的整個設計

      下一階要解決的問題

      原書講完了。Triton 自己做過一模一樣的榜,第二版就是原書的設計,結果「再爆掉」。為什麼?

      延伸基礎第 10 階 · single thread、hotspot懂的人可以跳過

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. 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,每吃一罐就改一次分數。原書這樣做會出什麼事?

      Triton 不同意 · 動手玩開服、新年倒數:「開罐罐派對」

      平均的 5 倍不是尖峰:大家同一秒開趴時,哪台 Redis 先死?

      ×1流量倍數0最忙那台 ops/秒正常狀態(示意上限 100,000)

      你猜猜看:原書假設尖峰 = 平均 × 5。新年倒數那一秒,大家同時開罐罐,流量會是平均的幾倍?

      「而更致命的是:原來貓咪也會開趴的,開趴時是超級大量貓咪一起開罐罐派對。像是新年倒數便一起開罐罐狂歡,瞬間有超高流量進了單一台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 的負載會怎樣?

      🗣️ 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 嗎?

      文組翻譯

      白板(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懂的人可以跳過

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. snapshot

      白板只寫前 10 名:大部分人得分時,老闆不用動筆

      ① 先想像

      每位客人自己拿一張計分卡,得分就改自己的卡。只有分數超過白板上的第 10 名,才去找老闆改白板。

      你猜猜看:200 人一晚得分 2,000 次,白板只寫前 10 名。大約要改白板幾次?

      ③ 這叫做 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 裡該放什麼?

      動手試:N = 5,list 最多 2N = 10 筆

      10list 長度0碰到 list 的次數0全部分數更新0從資料庫補資料

      延伸基礎第 12 階 · real-time、snapshot懂的人可以跳過

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. snapshot

      開票看板每幾分鐘才更新,有人抱怨嗎?

      ① 先想像

      選舉開票夜,電視台的看板不是每開一票就跳一次,而是每幾分鐘更新一次。大家看的是同一份數字,也沒人抱怨。

      你猜猜看:每秒 2,500 次得分。如果榜每 1 分鐘才重算一次,一分鐘要算幾次榜?

      ③ 這叫做 real-time、snapshot

      real-time(即時):每次變動立刻反映在榜上。snapshot(快照):某一刻拍下來、之後不再改的那份榜。翻頁時多出新的:11 章

      ④ 跟這章的關係

      原書要求即時。Triton 自己的榜是半即時,翻頁時用 ?ts= 指定看哪一張快照(下一頁)。

      ② 動手玩:每秒 2,500 次得分(原書的尖峰)

      一分鐘要動榜幾次
      —
      最晚多久才看到自己上榜
      —

      Triton 補充087 · 088 · 持續變動中的排名榜怎麼分頁

      翻到第 2 頁,同一個人又出現一次:用 ?ts= 鎖住快照

      你猜猜看:你在看第 1 頁(第 1–5 名),這時第 12 名衝上第 1 名。你再按第 2 頁,會看到什麼?

      「案例 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 預設不是每次寫入都存進硬碟。當機重開後,排行榜會怎樣?

      動手試:當機、對帳、重建

      Triton 補充原書周邊的設計選擇

      Lambda 的 auto-scaling、要不要 MQ、名字怎麼查、分區鍵加編號

      你猜猜看:流量暴增 40 倍時,Lambda 會自動多開很多份。那台放 sorted set 的 Redis 會跟著變多台嗎?

      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

      1. QPS
      2. O(log n)
      3. Redis
      4. sorted set
      5. skip list
      6. partition
      7. scatter-gather
      8. percentile
      9. tie-break
      10. hotspot
      11. top-N
      12. snapshot

      到這裡你已經會了:Triton 怎麼修

      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= 快照;當機後先做總和對帳

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

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

      DAU/MAU每天/每月有幾個人來玩
      QPS每秒幾次 request;看最忙那一秒
      request、API送出去的一張單子/事先講好的點單窗口
      internal API只開給自家機器的窗口,玩家不能直接呼叫
      game service確認輸贏的店員,確認了才報分
      leaderboard service管排行榜的那組程式
      man-in-the-middle有人夾在中間,偷改你送出去的東西
      MQ、Kafka讓訊息先排隊的號碼機
      MySQL、RDB最常見的關聯式資料庫:表格、SQL
      index、LIMIT先排好的索引/只拿前幾筆
      O(n)、O(log n)人多 100 倍工作多 100 倍/人翻倍只多一步
      Redis、in-memory放在記憶體的共用白板:快,但斷電會掉

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

      引述來源(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 名的人才去改?

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