Leader Board
我們將設計一個即時遊戲排行榜系統
能參考 Binance 的 leaderboard 。
Step 1 : Requirements and Scope
Candidate: How is the score calculated for the leaderboard?
Interviewer: The user gets a point when they win a match. We can go with a simple point system in which each user has a score associated with them. Each time the user wins a match, we should add a point to their total score.
用戶在贏得一場比賽時會得到一點分數。我們可以採用一個簡單的積分系統，每個用戶都有一個與之相關聯的分數。每當用戶贏得一場比賽，我們就應該在他們的總分中增加一點。
Candidate: Are all players included in the leaderboard?
Interviewer: Yes.
Candidate: Is there a time segment associated with the leaderboard?
排行榜是否有相關的時間分段（或賽季）？
Interviewer: Each month, a new tournament kicks off which starts a new leaderboard.
每個月都會啟動一次新的錦標賽，並開始一個新的排行榜。
Candidate: Can we assume we only care about the top 10 users?
我們是否可以假設我們只需要關心前 10 名用戶？
Interviewer: We want to display the top 10 users as well as the position of a specific user on the leaderboard. If time allows, let's also discuss how to return users who are four places above and below a specific user.
我們想要顯示前 10 名用戶，以及特定用戶在排行榜上的位置。如果時間允許，我們也來討論如何回傳特定用戶排名上、下各四位的玩家。
Candidate: How many users are in a tournament?
Interviewer: Average of 5 million daily active users (DAU) and 25 million monthly active users (MAU).
平均有 500 萬每日活躍用戶 (DAU) 和 2,500 萬每月活躍用戶 (MAU)。
Candidate: How many matches are played on average during a tournament?
Interviewer: Each player plays 10 matches per day on average.
每位玩家平均每天進行 10 場比賽。
Candidate: How do we determine the rank if two players have the same score?
Interviewer: In this case, their ranks are the same. If time allows, we can talk about ways to break ties.
Candidate: Does the leaderboard need to be real-time?
Interviewer: Yes, we want to present real-time results, or as close as possible. It is not okay to present a batched history of results.
是的，我們希望呈現即時的結果，或盡可能接近即時。呈現批次處理的歷史結果是不可接受的。
| 類型 | 項目 | 詳細要求 |
| 功能需求 (F.R.) | 排行榜顯示 | 1. 顯示排行榜前 10 名玩家。 2. 顯示特定用戶的當前排名。 3. （加分項）顯示特定用戶上下四個排名的玩家。 |
| 非功能需求 (N.F.R.) | 即時性 (Real-time) | 積分更新必須即時反映在排行榜上，不接受延遲的結果。 |
| 比賽規則 | 計分方式 | 用戶每贏得一場比賽，總分加 1 點。 |
| 時間範圍 | 賽季長度 | 每個月開始一個新的錦標賽，即新的排行榜。 |
| 規模估算 | 每日活躍用戶 (DAU) | 500 萬 (5M) 用戶。 |
| 規模估算 | 分數更新 QPS (峰值) | 約 2,500 次/秒。 |
User Scale
系統的規模假設：
每日活躍用戶 (DAU): 500 萬 (5 Million)
每月活躍用戶 (MAU): 2,500 萬 (25 Million)
QPS estimate
QPS 估算決定了系統的即時處理能力。主要估算了兩種類型的 QPS：
A. Score Update QPS
指玩家贏得比賽後，系統需要更新分數的頻率。
| 項目 | 數量/假設 |
| 活躍用戶 | 5,000,000 DAU |
| 分數更新事件 | 假設每位 DAU 平均每天贏得 1 場比賽（即 1 次分數更新）。 |
| 平均 QPS | 5000000次更新/86400秒 = 57.87次/秒 |
為了設計具有冗餘和彈性的系統，設定了更高的 QPS 基準：
🎯 思考： 為什麼在設計一個每月都會重置的排行榜系統時，我們需要同時關注 DAU (每日活躍用戶) 和 MAU (每月活躍用戶)？哪一個數字對儲存排行榜數據的總容量影響最大？
B. Leaderboard Read QPS
這是指用戶查看前 10 名排行榜的頻率。
🎯 思考： 如果我們必須在這兩項 QPS 中選擇一個來進行優先優化，你會選擇優化 2,500 次/秒的「分數更新」 還是 50 次/秒的「排行榜查詢」？為什麼？
Step 2 : High-Level Design
API Design
首先，系統必須定義外部服務和客戶端如何與排行榜系統互動。設計了三個核心 API：
| API URI | 方法 | 描述 | 呼叫方 (Caller) | Request Fields | Response Fields |
/v1/scores | POST | 更新用戶分數 (Score Update)（用戶贏得比賽時） | 遊戲服務器 (Game Service) （內部 API） | user_id (string): 玩家唯一 ID points (integer): 要增加的分數（通常為 1） | success (boolean): 操作結果狀態 new_score (integer): 更新後的總分數 |
/v1/scores | GET | 獲取排行榜前 10 名 (Get Top 10) | 客戶端 App (Client App) | 無 | leaderboard (array): 包含多個物件，每個物件有： user_id (string) score (integer) rank (integer) |
/v1/scores/{:user_id} | GET | 獲取特定用戶排名 (Get User Rank) | 客戶端 App (Client App) | URI 參數： user_id (string) | user_id (string) score (integer): 玩家分數 rank (integer): 玩家排名 neighbors (array/optional): 該用戶上下四位玩家的列表。 |
GET /v1/scores (獲取排行榜前 10 名)
這個 API 用於獲取排行榜上分數最高的 N 個玩家（在此設計中為前 10 名）。
API 目的： 顯示完整的排行榜首頁。
{
"status": "success",
"data": {
"leaderboard": [
{
"user_id": "Aquaboys_976",
"score": 976,
"rank": 1
},
{
"user_id": "B_team_956",
"score": 956,
"rank": 2
},
{
"user_id": "Berlins_Angels_890",
"score": 890,
"rank": 3
},
{
"user_id": "Grendel_Team_878",
"score": 878,
"rank": 4
},
{
"user_id": "Player_500",
"score": 701,
"rank": 9
},
{
"user_id": "Last_Top_10",
"score": 695,
"rank": 10
}
],
"count": 10
}
}
GET /v1/scores/{:user_id} (獲取特定用戶排名)
這個 API 用於查詢特定用戶的個人資訊，並滿足額外需求：「顯示特定用戶上下四個排名的玩家」（即 neighbors）。
API 目的： 讓用戶快速找到自己的位置，並查看附近競爭者的分數。
假設查詢用戶：user_id: CurrentPlayer_750
{
"status": "success",
"data": {
"user_id": "CurrentPlayer_750",
"score": 750,
"rank": 1500,
"neighbors": [
{
"user_id": "Rival_A",
"score": 755,
"rank": 1496
},
{
"user_id": "Rival_B",
"score": 754,
"rank": 1497
},
{
"user_id": "Rival_C",
"score": 753,
"rank": 1498
},
{
"user_id": "Rival_D",
"score": 752,
"rank": 1499
},
{
"user_id": "CurrentPlayer_750",
"score": 750,
"rank": 1500,
"is_current_user": true
},
{
"user_id": "Friend_E",
"score": 748,
"rank": 1501
},
{
"user_id": "Friend_F",
"score": 745,
"rank": 1502
},
{
"user_id": "Friend_G",
"score": 744,
"rank": 1503
},
{
"user_id": "Friend_H",
"score": 743,
"rank": 1504
}
]
}
}
High-level Arch.
為了確保系統的可擴展性和職責分離，架構被劃分為兩個主要服務：
遊戲服務 (Game Service)：專注於遊戲本身的邏輯和驗證。
排行榜服務 (Leaderboard Service)：專注於管理和顯示分數與排名。
運作流程：
玩家贏得遊戲 → 遊戲服務驗證 → 調用排行榜服務 API (POST /v1/scores) → 排行榜服務更新 Leaderboard Store 中的分數。
元件與分工
Client（使用者裝置）：觸發遊戲結果上報，並向排行榜服務查詢資料。
Game service：接收「玩家贏得遊戲」的事件並進行必要驗證，之後請求排行榜服務更新分數。
Leaderboard service：提供更新與查詢排行榜的介面，對下游的 Leaderboard Store 進行資料存取。
Leaderboard Store：抽象的排行榜儲存層（圖中未指定技術或資料庫種類）。
寫入流程（①②③）
玩家贏一場遊戲，Client 發請求給 Game service。
Game service 確認結果有效後，呼叫 Leaderboard service 更新分數。
Leaderboard service 將更新寫入 Leaderboard Store。
讀取流程（④a / ④b）
Do we need a message queue between the game service and the leader board service?
是否需要要看「Game score event 會不會被多方使用」。
Data Model & Storage Options
關聯式資料庫（Relational DB）方案
1️⃣ 基本設計
2️⃣ 分數更新流程
當玩家贏得比賽時：
若該玩家尚未有紀錄 → 新增一筆：
INSERT INTO leaderboard (user_id, score) VALUES ('mary1934', 1);
若已有紀錄 → 更新分數：
UPDATE leaderboard SET score = score + 1 WHERE user_id = 'mary1934';
3️⃣ 查詢玩家名次
為了找出排行榜名次，必須根據分數排序：
SELECT (@rownum := @rownum + 1) AS rank, user_id, score
FROM leaderboard
ORDER BY score DESC;
⚠️ 問題點
當玩家很多（數百/千萬筆）時，排序操作非常耗時。
SQL 排序與排名計算屬於 掃描（scan）, even table scan。
每次要查名次都必須對整張表排序 → 不適合即時系統。
若資料頻繁變動（玩家持續上分），無法依靠 cache/index。
只能做 batch job，不適合實時排行榜。
即使加上索引與 LIMIT（僅取前 N 名）仍無法從根本改善「找名次」問題。
RDB 中求特定玩家排名的 SQL
SELECT *,
(SELECT COUNT(*) FROM leaderboard lb2 WHERE lb2.score >= lb1.score) AS rank
FROM leaderboard lb1
WHERE lb1.user_id = :user_id;
外層查詢 (lb1)
取出指定玩家的資料（例如 mary1934）。
🔹內層子查詢 (lb2)
計算所有分數「大於等於該玩家分數」的筆數。
也就是：
如果有 3 個人分數比她高或一樣高，
那她的名次（rank）就是第 3 名。
雖然邏輯簡單，但這查詢的問題在於：
❗ 每次都執行一次完整的 COUNT(*)
對於每一位使用者，要重新掃描整張 leaderboard：
所以整體時間複雜度是：
O(N²)（平方級別，非常慢）
SQL 為何在這場景下無法快？
關聯式資料庫（RDB）沒有內建「自動維持排序名次」的結構。
COUNT(*) + >= 會導致資料庫必須掃描整個表。
即使加索引，也只能幫部分情況加速，仍需大量比較操作。
這就是為什麼書中說：
SQL databases are not performant when we have to process large amounts of continuously changing information.
Redis 方案
Redis 提供 Sorted Set (ZSet) 直接對應排行榜問題，在插入時就自動排序好，而且能直接用指令查名次：：
每個元素（玩家）都有一個「分數」。
Redis 自動根據分數排序。
提供操作：
ZINCRBY：增加玩家分數。O(log n)
每當玩家贏得一場比賽時，他的分數要加 1。ZINCRBY <KEY> <INCREMENT> <USER>
ZINCRBY leaderboard_feb_2021 1 'mary1934' ，在 leaderboard_feb_2021（2021 年 2 月排行榜）中，將使用者 mary1934 的分數增加 1。若她之前不在榜上，會自動新增。
上個月的排行榜則會被移到歷史資料庫保存。因為 Redis 存在記憶體中，長期資料會定期清除或搬走。核心精神是 過往紀錄不會再被修改了，放在關聯式資料庫以replica 跟 veiw 提供快速讀取。
ZADD : UPSERT 使用者與分數。O(log n)
ZREVRANGE：取得前 N 名。O(log n + m) ,n 是排行榜中總成員數量。m 是要取出的筆數（通常很小，例如前 10 名）。
ZREVRANGE <KEY> <START> <STOP> WITHSCORES
取 Top 10 ZREVRANGE leaderboard_feb_2021 0 9 WITHSCORES 。ZREVRANGE：取出成員並依照分數由高到低排序（rev = reverse）。WITHSCORES：同時返回使用者分數。
當月的 Top 10 用 Redis 這樣的解法比較快，因為 RDB 要全表排序才能得出結果。但過往的能另外做成一個存 Top 10 的 view.
查詢附近名次，若 Mallow007 排名為 361，想看前後 4 名， ZREVRANGE leaderboard_feb_2021 357 365 ，會返回 rank 357–365 的玩家清單。
ZREVRANK：查玩家名次 ZREVRANK leaderboard mary1934。O(log n)
ZSet 內部實作：Skip List（跳表）
Redis Sorted Set 是用 Skip List（跳表） 實作的。
概念：
類似「多層索引」的鏈結串列。
舉例：搜尋節點 45 時，原本需走 8 步，
從 Level 1 開始走：
1️⃣ 1 → 8 → 15 → 36 → 60
2️⃣ 發現 60 > 45，就往下切換到底層。
3️⃣ 從 36 繼續走到底層：36 → 45 ✅
👉 大概只花 6 步。
再加更多層索引
每一層都「再跳更遠」：
從 Level 2 開始走：
1️⃣ 1 → 15 → 60
2️⃣ 發現 60 太大，往下一層 Level 1。。
3️⃣ 從 15 往後走：15 → 36 → 60
4️⃣ 再往下層從 36 找：36 → 45 ✅
👉 大概只花 6 步。
Storage 需求
記憶體估算
因為主要放 Redis ，那就要粗略估一下當月排行榜可能要多少記憶體來儲存。
最基本的情況下，排行榜需要儲存兩個欄位，user_id 與 score
因此每個排行榜entry至少需要：
總共約 26 bytes。
最壞情況（worst-case scenario）
假設有 2,500 萬月活躍使用者 (MAU)，而每個人至少贏過一場比賽，
因此每個人都會在排行榜中佔有一筆紀錄。大概需要 ≈ 650 MB
再加上 Redis 的 Index （skip list + hash table），
記憶體需求約 1.3 GB 左右。
效能負載
CPU / I/O 考量：
估算每秒有約 2,500 次更新請求（QPS 2500），最基本的情況下，排行榜需要儲存兩個欄位
小 case!
Redis 的持久性問題 (Persistence Concern)
我們的需求量不高，基本一台主機提供讀寫即可，為此我們考慮高可用的情況下，通常會考慮做 failover。
雖然 Redis 有持久化機制（RDB / AOF），
但從磁碟重啟大資料集仍然較慢，
所以設計上會使用多副本來確保即時可用。
Redis 進行 快照（snapshot / RDB dump） 時，會使用 Copy-on-Write（COW） 機制：
當 Redis 把記憶體內容寫入磁碟的同時，新的寫入仍在發生，這些新資料會暫存在新的記憶體區塊。
👉 所以在這段期間，實際記憶體用量可能暫時翻倍。
💡 範例：
Redis 支援兩種持久化方式：
Redis 官方提供 redis-benchmark 工具，用來模擬多用戶同時存取的情況。
你可以用它測試：
藉由這些數據，你可以判斷目前硬體配置（CPU、記憶體、網路）是否足以支撐你的排行榜負載。
關聯式資料庫
Redis 處理排行榜的即時更新與查詢，
但仍需要 關聯式資料庫 來保存永久性資料。
系統會設計兩張輔助表：
User Table︰儲存 User profile
Point Table︰儲存 play history(include user_id, score, timestamp)。也能充當 redis 重建排行榜用的依據。
可以另外建立一個小型 view/cache ，專門存前十名玩家的詳細資料。因為這部分資料最常被查詢。且這不會佔用太多記憶體或儲存空間。
TODO : Demo by K3D
SLO：更新/查詢 P95 < 50ms；峰值 2,500 QPS 可撐。
場景 1 : Only RDBMS
先演示並解釋上述 SQL 的執行計畫
壓測腳本，並關注 dashboard
場景 2 : Use Redis
- 壓測腳本，並關注 dashboard 上的 duration
Demo Code
總結
先顧好的「小而關鍵」工程細節
冪等性：POST /v1/scores 帶 match_id，服務端去重（避免重複加分）。
限流 & 防濫用：在 Leaderboard Service 前做簡單令牌桶即可。
安全邊界：只能由 Game Service 更新分數（client 不直寫）。
可觀測性：QPS、P95 延遲、Redis 內存使用、慢查、鍵數量、複製延遲。
高可用但簡單：主從複製（1 主 1 從）；RDB/AOF 擇一或混合；記憶體預留 2× 應對 COW snapshot。
月度滾榜：leaderboard_YYYYMM 新鍵；歷史榜定期歸檔到 RDB（之後做離線報表/回放）。
什麼時候才引入複雜度（明確觸發點）
1) 要不要 MQ（Kafka）？
只有當「分數事件一對多」被其他服務共用（風控/分析/推播/成就）時才加。
2) 要不要 Redis Cluster / Sharding？
當 單節點達到兩類瓶頸才升級：
3) 要不要 CQRS？
讀寫壓力/模型明顯分離、讀的花樣很多（多維排序、濾條件多）且你準備投入維運成本時再做。這題的讀模型單純（Top-N + 單人名次），沒必要。
風險與反模式（避免一開始就踩）
過度設計：一上來就 Kafka、Cluster、CQRS，交付慢、故障面積大、Demo 不出來。
把歷史查詢放即時層：舊榜查報表丟給 RDB/離線系統，別拖累 Redis。
客戶端直改分數：安全洞；必須 server-authoritative。
忘了預留 2× 記憶體：快照時 COW 會瞬時吃雙倍 RAM。
未做冪等/限流：比「沒用 MQ」更容易把系統打爆。
我會在面試中強調的三句話
先用最小架構打穿功能與即時性：單台 Redis ZSet + MySQL 歷史表，三支 API 即可交付。
明訂升級門檻與路徑：多消費者上 MQ；容量/吞吐逼近單機上限再分片或 Cluster。
工程實務先做對小事：冪等等幂、限流、觀測、HA、月度滾榜與資料歸檔——這些比任何流行名詞更值錢。
References
https://medium.com/analytics-vidhya/redis-sorted-sets-explained-2d8b6302525
https://systemdesign.one/leaderboard-system-design/
