01排行榜需要哪些 window——任意範圍，還是固定的時／日／月？
只有固定 window：過去一小時、一天、一個月，以及全時段。任意時間範圍不在範圍內。
免費完整指南
Top K Songs (Spotify)
設計Top K Songs (Spotify)。請涵蓋Framing top-K as a heavy-hitters/frequency-estimation problem over a play-count stream, Count-Min Sketch + heap (bounded error, memory trade-off) vs exact per-partition...
00
練習檢查點
面試節奏保持精簡,讓頁面能把注意力花在真正的設計決策上。
- 01釐清範圍
- 02需求 + 規模
- 03API + 資料模型
- 04畫出架構
- 05深入探討
- 06取捨決策
01
形塑設計的需求
不要只是陳述需求,要主動問出來。每張卡把設計限制和一句你可以在畫架構前說出口的釐清問句配成一組。
功能需求
02K 最大能到多少？
每份排行榜最多 1,000 首歌。
03一次新的播放要多快出現在排行榜上？
約一分鐘內——近乎即時，不是瞬間。
04兩首歌在第 K 名平手——用什麼打破平手？
一個固定的破平手規則——先比次數，再比 song id。同一個查詢每次都回傳同一份清單，所以排行榜永遠不會閃動。
05地區與曲風排行榜——現在還是以後？
之後。全球榜先出貨；地區榜與曲風榜在後面的階段才做。
06一首歌被下架——它什麼時候離開排行榜？
立即——一首被下架的歌必須同時從每一份排行榜上消失，絕不等次數重算。
範圍外任意時間範圍（from/to 查詢） · 每使用者或每地區的個人化排行榜 · 播放刷量偵測
非功能需求
01攝取要為多少事件率做規劃？
尖峰每秒數十萬次播放事件。
02一次排行榜讀取要多快？
數十毫秒——打開排行榜必須感覺瞬間完成。
03數字非得精確不可嗎？
先問清楚，因為它會改變設計。這裡的主路徑是精確計數。這些數字可能會餵進權利金申報，所以系統性的多算是不可接受的。
04如果有東西在一小時進行到一半時崩潰，丟幾次播放可以接受嗎——還是每一次播放最終都必須被計入？
什麼都不能遺失。每一次播放最終都必須被算到。復原期間新鮮度短暫下降是可以接受的。
05一首歌吃掉一半播放量怎麼辦？
單一首熱門歌曲可能一下子搶走全部播放中很大的一份。這不能拖慢計數，也不能讓排行榜變得過時。
持續追問 —— 面試是一場對話
真實面試探得比一份整齊清單深得多。這些範圍問句,區分出真正拷問問題的人和只是背誦的人。
- 過去的排行榜必須保留多久——有人能調出去年三月的每日排行榜嗎，還是只有目前的 window？
- 機器人與刷量播放在範圍內嗎，還是在到我們這裡之前就被上游過濾掉？
- 每日排行榜的「一天」由哪個時區定義——UTC，還是聽眾的當地時間？
- 全時段有多長——它會重置嗎？
- 如果唱片公司對某個排行榜名次提出爭議，我們需要一條從排行榜回溯到原始播放的稽核軌跡嗎？
02
逼出架構決策的數字
把每個估算都當成一種壓力,用來合理化一個元件:快取、佇列、分片、副本、worker pool 或退路。
事件攝取率
每日數百億次播放（刻意設的 70B/day 壓力上限——比今天的串流量高一個數量級）70B ÷ 86,400 s ≈ 810K events/s
只有一個分區過的 log 才吸收得了這個量。聚合器接著平行地消費每個分區。
預先聚合的好處
聚合器在寫入前，把每首歌每分鐘的次數批次起來一首歌每分鐘播 10,000 次 → 1 次寫入而非 10,000 次
串流預先聚合把熱門歌的儲存寫入砍掉 3-4 個數量級。
精確計數的記憶體
假設約 1 億首不同的歌 × 計數器 + key ≈ 50 B100M × 50 B ≈ 5 GB per window
精確計數在這裡負擔得起。這就是為什麼它是主路徑，而不是 sketch。
Sketch 替代方案
Count-Min Sketch，4 個 hash 列 × 200 萬個 bucket × 4 B≈ 32 MB per window vs 5 GB 精確
當每個窗口的記憶體很要緊時（很多窗口、很多地區），sketch 用的狀態少了大約 150 倍。代價是一個有界的多算。
排行榜刷新成本
以一個 min-heap 在次數更新上維護 Top-1,000heap 更新 O(log 1,000) ≈ 每首被計數的歌-分鐘約 10 次比較
持續維護排行榜很便宜。每次查詢都從頭重算就不便宜了。
決策範例
數字
每秒八十萬次播放正湧進來。產品問題很小：四個固定窗口的前 1,000 首歌，一分鐘內保持新鮮。
我的選擇
讓每一次播放落進一個分區過的事件 log。在串流處理器裡，以一分鐘為批次精確計數每首歌的播放，然後把分鐘捲成小時、小時捲成天——每個窗口保留自己的計數。每個窗口一個小 heap，持續把前 1,000 名保持在最新。API 服務一份快取的快照，每分鐘刷新一次，並在窗口邊界預熱。
避免
我不會做的事：用資料庫遞增來計數播放。在每秒 810K 次遞增下，那是一場寫入風暴，而預先聚合的串流免費就把它吸收掉。我也不會預設就伸手拿 Count-Min Sketch。精確計數在這裡每個窗口約花 5 GB，負擔得起，而精確數字替權利金等級的用途留了一扇門。當窗口倍增成每地區榜、變成好幾十個窗口、而有界的多算可以接受時，sketch 才是對的工具。
何時改變
如果產品加了每地區與每曲風榜（好幾百個窗口），我會依熱門程度來拆。熱門歌曲留在精確計數器上，長尾放進 Count-Min Sketch——熱門歌曲保持精確，而長尾幾乎不花成本。
03
架構路徑
先看一張完整的圖,再把每條路徑各自畫成一張圖 —— 寫入路徑與讀取路徑承載不同流量,合理化不同的元件。
完整全貌
總覽 —— 每個元件
- 播放由左往右流動；每 window 的 heap 讓前 1,000 名的答案持續保持備妥。
- 虛線 = 不在即時路徑上：每夜一次的批次在事件 log 上重算，校正任何漂移。
- 下架發生在服務當下：Chart API 用一份 denylist 過濾被下架的歌，所以移除是立即的，永遠不等次數重算。
路徑 1
寫入路徑——先計數，再排名
串流內的預先聚合把一首熱門歌的 10,000 次播放變成一次被計數的寫入；heap 隨著次數變化而更新。
路徑 2
讀取路徑——服務快照
讀取永遠看不到原始次數。快照每分鐘刷新，並在 window 交界處預熱，所以整點的請求跟其他任何請求一樣快。
04
API 與資料模型
在最佳化之前,先讓契約可被檢視:端點、實體、擁有權、重試與狀態。
GET/charts/top?window={hour|day|month|all}&k=100
回應200 [{ song_id, plays }] (≤1,000 entries)
從快取服務最新的 ChartSnapshot——cache key charts:{window}:{window_start}，在 window 翻轉時預熱，讓交界那一分鐘永遠不會慢。
STREAMplay-events topic (partitioned by song_id + hot-key salt)
回應consumed by the windowed aggregator
唯一的寫入路徑。生產者 fire-and-forget；持久性來自 log，不是來自生產者。
核心實體
PlayEventsong_id · user_id · played_at
僅追加的串流記錄；帶保留期的 log 是重放的真相來源。
WindowCountsong_id · window (hour/day/month/all) · window_start · plays
精確的每 window 次數，隨著 window rollup 而在更粗的粒度上聚合（小時 → 天 → 月）。
ChartSnapshotwindow · window_start · top_k: [song_id, plays][]
API 服務的那份預先算好的答案；每分鐘刷新一次，帶 TTL 快取。
05
深入方向
在面試最後三分之一挑一條路線。每條路線給你主題、它該回答的面試官問題,以及要避免的失敗模式。
精確還是近似
問
在這裡 Count-Min Sketch 什麼時候才是對的選擇，你到底放棄了什麼——用數字說？
回答
就用精確計數。在這裡那大約是每個視窗 5 GB，1 億首歌每首約 50 bytes，負擔得起。只有在視窗爆增成上百張地區與曲風榜時，才動用 Count-Min Sketch。它能把狀態砍 150 倍到 32 MB，但每個計數都可能高估，絕不會低估。對排行榜沒問題，對版稅就錯了。
避免
反射性地伸手去拿 sketch——每 window 5 GB，精確計數負擔得起，而且嚴格來說更有用。
一首歌吃掉整條串流
問
一首熱門單曲吃掉 30% 的播放。它的分區會怎樣，你又如何在不搞壞次數的前提下把它鋪開？
回答
幫 partition key 加鹽。在熱門歌曲的 key 後面加一個小的隨機後綴，讓它的播放次數分散到好幾個分區，而不是壓垮一個。接著在排序前，把那些部分計數合併成一首歌的總數。跳過這步合併，熱門歌就會裂成好幾筆，每一筆都只有它真實播放次數的一小部分。
避免
把分區 key 加了 salt，卻忘了把加了 salt 的次數合併回一首歌的總數。
window 交界
問
現在是 00:00:01，所有人都在要新的每小時排行榜。那個答案從哪裡來？
回答
從一份已經預熱好的快照。在邊界之前，聚合器就把即將關閉的視窗的 top-1,000 定案並寫進快取。所以換檔之後的第一個請求就是一次單純的 cache 命中，跟其他請求沒兩樣。反過來在那第一個請求才去算榜單，你就把這一小時裡最忙的那一秒變成最慢的一秒。
避免
在翻轉後的第一個請求上才計算排行榜——改成預熱快照。
聚合器掛掉
問
串流處理器在一個小時 window 進行到第十分鐘時崩潰。排行榜顯示什麼，次數又如何恢復？
回答
榜單繼續供應上一份快取的快照。它會過時個一兩分鐘，但絕不會空白。接手的 processor 載入它最後的 checkpoint，從那個 offset 開始重放事件 log，只重新計算當前視窗的尾巴。什麼都不會遺失，因為每一次播放在被計數之前，都先落進了 log。
避免
在處理器記憶體裡計數卻沒有 checkpoint——從 log 重放才是整個安全故事。
為什麼不用時序資料庫
問
Prometheus 式的時序引擎會儲存隨時間變化的次數——為什麼它們在這裡不合適？
回答
兩個原因，第一個是 cardinality。把 1 億個歌曲 ID 當成 tag 值，遠在寫入速率造成傷害之前，就先把索引和記憶體撐爆了。查詢的形狀也不對。那些引擎很會答「單一序列隨時間的變化」，卻很不會答「跨所有序列的 top 1,000」——而後者正是這套系統存在要回答的問題。
避免
忽略基數：1 億個 song ID 當 tag 值，正是時序引擎會噎住的東西。
準備好練習了嗎?
把 Top K Songs (Spotify) 大聲講一遍,讓 AI 為你的說明評分。