使用者每敲一個字元就發一次請求，系統要在 100ms 內回傳依熱門度排序的前 5 個建議。核心是用 trie 換掉關聯式查詢，並在每個節點預先快取結果。
📋 Requirements
- 功能：給定 prefix，回傳依歷史查詢頻率排序的前 5 個建議（只在開頭匹配）。
- 規模：1,000 萬 DAU、每人每天 10 次搜尋、每字元一次請求 → 約 24,000 QPS，尖峰約 48,000。
- 非功能：回應快（100ms 內）、相關、依熱門度排序、可擴展、高可用。
🧠 Core Ideas
TIP
系統分成資料蒐集服務（彙總查詢日誌、建 trie）與查詢服務（讀 trie 回前 k）。關聯式 DB 的 top-k 查詢在資料量大時是瓶頸，改用 trie；再靠「限制 prefix 長度」與「每節點快取熱門查詢」把讀取降到 O(1)。
⚖️ Reference Design
Trie 與兩項最佳化
- 基本 trie：每節點存一字元、代表一個 prefix；節點再加上頻率資訊以支援排序。
- 樸素取 top-k：找 prefix O(p) → 走訪子樹 O(c) → 排序取前 k O(c log c)，最壞需走遍整棵 trie，太慢。
- 限制 prefix 最大長度：p 視為小常數，找 prefix 降為 O(1)。
- 每節點快取熱門 k 個查詢：k 很小（5～10），取 top-k 直接讀節點，降為 O(1)；用空間換時間。
資料蒐集 — 離線建 trie
- 即時更新不實際：查詢量極大、且建好後熱門建議變化不大。
- 流程：Analytics Logs（append-only）→ Aggregators 彙總（假設每週一次）→ Aggregated Data → Workers 非同步建 trie 存入 Trie DB。
- Trie DB 兩種存法：document store（序列化 trie 快照）或 key-value store（prefix 為 key、節點資料為 value）。
查詢服務 — 讀路徑加速
- Trie Cache：分散式快取把 trie 放記憶體、每週對 DB 拍快照；cache miss 時回填。
- 請求經 load balancer → API server 從 Trie Cache 取 trie、組建議。
- 進一步最佳化：AJAX 請求、瀏覽器快取（如 cache-control private、max-age=3600）、資料抽樣（每 N 個請求記 1 個）。
更新、刪除與擴展
- 更新：優先每週整棵替換；直接改單一節點很慢（須連同所有祖先節點更新其快取的熱門查詢）。
- 刪除：在 Trie Cache 前加過濾層擋掉不當建議，實際資料非同步移除、下個週期重建。
- 擴展：依首字母 sharding（最多 26 台，可多層），但分布不均（c 遠多於 x）；用 shard map manager 依歷史分布做更聰明的切分。
- 多語言／地區：節點存 Unicode 字元、各國各建一棵 trie，並可將 trie 放 CDN 改善回應時間。
🔑 Takeaways
- 讀路徑的關鍵是 trie + 每節點快取 top-k，把取建議降到 O(1)。
- 建 trie 走離線批次（每週重建）而非即時，避免拖垮查詢服務。
- 擴展難點是首字母分布不均，需依歷史資料做加權 sharding。
- 即時趨勢查詢是本設計的邊界：需縮小工作集、調整排名權重、引入串流處理。
No notes yet — jot your takeaways or Q&A here.