System Design Interview · 第 13 章Triton 覆蓋度:🟠 低Triton 線
Design A Search Autocomplete System
才打一個字,就要猜中你想搜什麼
原書這題又叫「design top k」:使用者每打一個字,系統要在 100ms 內回傳最熱門的 5 個搜尋詞。主角是一棵每個節點都存好 top k 的 trie、一條每週重建一次的資料管線,以及依第一個字母分片。Triton 沒有寫過 autocomplete 或 trie 設計的講義,所以這份簡報先把原書講完整,再用他談 N、RDBMS、cache、top-N 的原則補五段標明 🔭 的推論。
給文組
全程用「早餐店阿姨猜你要點什麼」比喻,一階一階爬 13 個概念,二十個可以動手玩的小互動。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。
給工程師
原書 15 張圖與 4 張表全部依描述重繪成可播放的 SVG。最後一頁列出原書段落對照與出處檔案(materials/core)。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 📝 上課筆記 🔭 依 Triton 原則推論
先用生活理解autocomplete 在做什麼
早餐店阿姨:你才說「蘿」,她就問「蘿蔔糕加蛋?」
你是客人,一個字一個字說出你要點的東西(點下面的字):
阿姨翻到「(封面)」這一頁,上面寫著最常被點的 3 樣:
阿姨有一本筆記:每一種「開頭」一頁,頁上早就寫好那個開頭最常被點的 3 樣。你每多說一個字,她就往後翻一頁,直接念出那頁寫的東西,不用當場回想所有客人點過什麼。
筆記不是每來一張單就改:她每週日晚上把一週的點單收據整理一次,重抄整本。這週突然爆紅的新品,下週才會出現在筆記上。
對照表
- 筆記本 = trie;一頁 = 一個節點(一個前綴)
- 頁上寫好的 3 樣 = 節點上快取的 top k
- 點單收據 = analytics logs;週日重抄 = 每週重建 trie
- 阿姨太忙,請兩個阿姨分「開頭是哪個字」= sharding
學習地圖本章的概念階梯
今天爬 13 階。每一階只用前面講過的東西。
- 1prefix開頭那幾個字
- 2QPS每秒被問幾次
- 3top k前幾名
- 4SQL跟帳本問話
- 5trie字典分岔路
- 6O(1)步數不看資料多寡
- 7cache先抄好的答案
- 8aggregation收據週日加總
- 9key-value抽屜貼標籤
- 10browser cache客人自己記
- 11sharding分給幾位阿姨
- 12lock一次只准一人去
- 13hotspot全擠向同一位
第 1–4 階 · 題目在問什麼
要回答:打一個字,要回哪 5 個?
第 5–7 階 · 阿姨的筆記本
要回答:怎麼在 0.1 秒內答出來?
第 8–10 階 · 筆記怎麼寫、少被問
要回答:一週的點單怎麼變成筆記?
第 11–13 階 · 太忙了怎麼辦
要回答:分工、搶著補、爆紅新品?
全程只用一家早餐店(虛構):阿姨聽你說一個字,就猜你要點什麼
每爬 3–4 階,有一頁「到這裡你已經會了」。QPS、SQL、cache、key-value、sharding、lock、hotspot 在第 1、2、5、6 章的簡報講過,這裡一句話複習並附連結。
路線圖Triton 覆蓋度:🟠 低
這份簡報怎麼走
📖 原書 Step 1–2
- 題目與 Figure 1(第 6 頁)
- 面試問答、五個需求(7)
- 估算:24,000 QPS、每天 0.4 GB(8)
- 高階設計:資料收集 + 查詢服務、Figure 2–4(11–12)
📖 原書 Step 3–4
- Trie、top k 演算法、兩個優化、Figure 5–8(14–19)
- 資料收集管線、Trie DB、Figure 9–10(22–24)
- 查詢服務、browser cache、AJAX、sampling、Figure 11–12(25–28)
- Trie 操作、分片、Wrap up、Figure 13–15(30–34)
🔭 依 Triton 原則推論 五段
- Triton 說過什麼、沒說過什麼(36)
- 先知道 N:SQL、暴力解、小 k 用 heap(37–38)
- Trie cache 是預先算好的 snapshot;miss 要上鎖(39–40)
- 即時熱門:top-N 存 2N、別讓熱點擠一台(41–42)
- 先數模組、先算資料量(43–44)
為什麼覆蓋度是「低」:materials/core 裡沒有任何談 autocomplete、typeahead 或 trie 設計的講義、文章或留言。唯一提到 trie 的是 075 的一行清單。能用的是 Triton 在別的題目講的原則(排行榜、cache、geohash、backend 模組),套到這章一律標 🔭,不寫成「Triton 認為 autocomplete 應該……」。
延伸基礎第 1 階 · prefix懂的人可以跳過
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
客人才說一個「蛋」,阿姨要從哪幾樣裡猜?
① 先想像
菜單上有 12 樣。客人開口說「蛋」,阿姨只想「蛋」開頭的那幾樣,其他的先不管。
你猜猜看:客人說「蛋」,阿姨該不該猜「起司蛋餅」?
這題只看開頭。「起司蛋餅」要等客人說「起」才會被猜到。右邊點點看。
③ 這叫做 prefix
prefix(前綴):一串字最前面的那一段。「蘿蔔糕」的 prefix 有:蘿、蘿蔔、蘿蔔糕。
④ 跟這章的關係
原書面試第一題就問「只比對開頭嗎?」答案是對。整章的資料都依 prefix 整理。
② 動手玩:客人說出的開頭
原書開場 · Figure 1
一邊打字,一邊跳出建議:autocomplete
這一步要解決的問題這道題到底在做什麼?為什麼又叫「design top k」?
📖 原書 在 Google 搜尋或在 Amazon 購物時,你在搜尋框打字,下面就跳出一個或多個符合的結果。這個功能叫 autocomplete,也叫 typeahead、search-as-you-type、incremental search。
📖 原書 很多產品都有這個重要功能,於是有了這道面試題:設計 search autocomplete system,也叫 「design top k」或「design top k most searched queries」。
文組翻譯
「top k」就是「前幾名」。這題的本質是:給一個開頭,馬上說出這個開頭最常被搜的前 k 名。後面所有設計都在回答兩件事:前幾名怎麼算出來、怎麼在 0.1 秒內回答。
原圖下方還有一個「Report inappropriate predictions」連結,讓使用者回報不當建議,後面講 Delete 時(第 31 頁)會用到這個概念。
原書 Step 1Understand the problem and establish design scope
七個問題,把題目縮小到「英文小寫、前綴、前 5 名」
這一步要解決的問題只比對開頭嗎?要回幾個?依什麼排?先把題目縮到做得出來的大小。
📖 原書 應徵者 × 面試官
| 應徵者問 | 面試官答 |
|---|---|
| 只比對搜尋字串的開頭,還是中間也要? | 只比對開頭 |
| 要回傳幾個建議? | 5 個 |
| 系統怎麼知道要回傳哪 5 個? | 依熱門度,由歷史查詢頻率決定 |
| 要支援拼字檢查嗎? | 不用,不支援 spell check 或 autocorrect |
| 搜尋都是英文嗎? | 是。時間夠的話,最後可以談多語言 |
| 允許大寫和特殊字元嗎? | 不,假設全部是小寫英文字母 |
| 有多少使用者? | 1,000 萬 DAU |
白話:DAU=每天打開的人數;spell check/autocorrect=自動改錯字;ranking model=決定誰排前面的公式;highly available=壞了一部分還能用。
📖 原書 需求摘要
- Fast response time:使用者打字時建議要夠快出現。Facebook 的 autocomplete 文章 [1] 指出要在 100 毫秒內回傳,否則會卡頓(stuttering)
- Relevant:建議要和搜尋詞相關
- Sorted:結果依熱門度或其他 ranking model 排序
- Scalable:能處理高流量
- Highly available:部分系統離線、變慢或遇到網路錯誤時,系統仍可用
文組翻譯
「只比對開頭」很關鍵:「蘿」可以猜到「蘿蔔糕」,但「糕」不必猜到「蘿蔔糕」。這個限制讓整章可以用「前綴」來組織資料。
原書 Step 1Back of the envelope estimation
每打一個字就是一次 request:每秒 24,000 次
這一步要解決的問題每打一個字就問一次,系統每秒要被問幾次?每天多出多少資料?
- 📖 原書 1,000 萬 DAU,平均每人每天搜尋 10 次
- 每個查詢 20 bytes:ASCII,1 字元 = 1 byte;一個查詢平均 4 個字、每字 5 個字元,4 × 5 = 20
- 搜尋框每輸入一個字元,client 就向後端要一次建議,所以每次搜尋平均 20 個 request。打完「dinner」,後端已收到 6 個:
search?q=d…search?q=dinner - ~24,000 QPS = 10,000,000 × 10 × 20 / 24 小時 / 3600 秒
- Peak QPS = QPS × 2 = ~48,000
- 假設 20% 的查詢是新的:10M × 10 × 20 bytes × 20% = 每天新增 0.4 GB
文組翻譯
一個人搜一次,系統其實被問了 20 次。查詢的人數不多,但「打字的次數」很多,所以讀取量才是這題的壓力來源。
第 2 階複習:QPS=每秒被問幾次(第 2 章簡報第 23 頁);尖峰為什麼要乘 2(第 24 頁)。ASCII=英文字母的編碼,1 個字母 1 byte。
延伸基礎第 3 階 · top k懂的人可以跳過
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
阿姨不必背整張排行榜,只要記前幾名
① 先想像
「蛋」開頭有四樣,每週份數:蛋餅 120、蛋吐司 80、蛋餅加起司 60、蛋堡 45。阿姨只念最多人點的前 2 樣。
你猜猜看:k = 2,阿姨該念哪兩樣?
120 和 80 最大。k 就是「要念幾樣」;這章原書的 k 是 5。
③ 這叫做 top k
top k:次數最多的前 k 名。k 是你要幾個,原書 k = 5。
④ 跟這章的關係
這題又叫「design top k」:每個 prefix 都要馬上答出它的 top 5。
② 動手玩:全店 12 樣,找前 k 名
阿姨手上的 k 張卡(目前的前 k 名):
到這裡你已經會了小結 1 / 5
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
到這裡你已經會了:題目在問什麼
- 客人說出的開頭叫 prefix;這章只比對開頭,「糕」不必猜到「蘿蔔糕」。
- 每打一個字就問一次:1,000 萬 DAU → 約 24,000 QPS,尖峰 48,000。
- 每個 prefix 都要答出次數最多的前 5 名:top k,k = 5。
下一階要解決的問題
前 5 名要從哪裡算出來?先看最直覺的做法:一張次數表,加一句 SQL。
原書 Step 2High-level design · Data gathering service · Figure 2
高階設計:一邊收集查詢、一邊回答前 5 名
這一步要解決的問題先畫最粗的兩塊:資料從哪裡收進來?前 5 名從哪裡答出去?
📖 原書 高階設計把系統分成兩部分:
Data gathering service
收集使用者輸入的查詢,即時彙整。原書直說:資料集大時即時處理並不實際,但這是好的起點,deep dive 再換成實際的做法(第 22 頁)。
Query service
給一個搜尋字串或前綴,回傳 5 個最常被搜尋的詞。
📖 原書 簡化的例子:一個 frequency table 存查詢字串和次數。一開始是空的,使用者依序輸入 twitch、twitter、twitter、twillo,表格依序更新(右圖)。
白話:service=負責一件事的一組程式;frequency table=兩欄的次數表:查詢、被搜幾次;即時=每來一筆馬上算。
你猜猜看:依序輸入 twitch、twitter、twitter、twillo 之後,表裡 twitter 的次數是幾?
同一個查詢再出現一次,次數就 +1。按下面的「播放」看表格一格一格更新。
原書 Step 2Query service · Table 1 · Figure 3 · Figure 4
最直覺的做法:一句 SQL 撈出前 5 名
這一步要解決的問題有了次數表,最直覺怎麼撈出某個開頭的前 5 名?
📖 原書 假設 frequency table 如 Table 1,有兩個欄位:Query(查詢字串)、Frequency(被搜尋的次數)。
| Query | Frequency |
|---|
📖 原書 Table 1 frequency table
📖 原書 使用者打「tw」,依 Table 1 顯示前 5 名(Figure 3),SQL 如 Figure 4。資料集小時這是可以接受的解法;資料集大時,存取資料庫會變成瓶頸,deep dive 再優化。
第 4 階複習:database=存資料、不怕重開機的帳本(第 1 章簡報第 8 頁)。SQL=跟帳本問話的句子:LIKE 'tw%'=tw 開頭;ORDER BY frequency DESC=次數由大到小;LIMIT 5=只要前 5 列。
延伸基礎第 5 階 · trie懂的人可以跳過
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
字典的分岔路:共同的開頭只走一次
① 先想像
從店門口出發,客人每說一個字,就往一條岔路走一步:蛋 → 餅。蛋餅、蛋堡、蛋吐司都先經過「蛋」這個路口。
你猜猜看:把蛋餅、蛋堡、蛋吐司畫成分岔路,「蛋」這個路口要畫幾個?
共同的開頭只畫一次,走到「蛋」再分岔。右邊一樣一樣加進去看。
③ 這叫做 trie、node
trie:依開頭分岔的樹,又叫 prefix tree。node(節點):一個路口;最上面的起點叫 root。
④ 跟這章的關係
阿姨的筆記本就是一棵 trie:一個路口=一頁。原書用它取代 SQL(下一頁)。
② 動手玩:把菜一樣一樣掛上去
原書 Step 3Trie data structure · Figure 5 · Figure 6 · Table 2
Trie:把字串依「開頭」掛成一棵樹
這一步要解決的問題SQL 每次都要撈出所有符合的列。能不能把字串先依開頭整理好?
📖 原書 高階設計用關聯式資料庫,但從 RDB 撈前 5 名沒效率,所以改用 trie(prefix tree)。trie 對這題很關鍵,但原書也說它比較像資料結構題、網路上資料很多,所以只做概述,重點放在怎麼優化以縮短回應時間(部分想法來自 [2] [3])。
📖 原書 Trie 的主要概念
- 讀作「try」,名字來自 retrieval,是為字串檢索設計的樹狀結構
- root 代表空字串
- 每個節點存一個字元,有 26 個子節點(每個可能的字元一個);為了省空間,空連結不畫
- 每個節點代表一個單字或一個前綴字串
白話:RDB=關聯式資料庫,一張張表格的帳本;retrieval=把東西找出來。
📖 原書 基本 trie 只存字元。要依頻率排序,節點也要存頻率。加入 Table 2 的頻率後就是 Figure 6。
| Query | tree | try | true | toy | wish | win |
|---|---|---|---|---|---|---|
| Frequency | 10 | 29 | 35 | 14 | 25 | 50 |
📖 原書 Table 2(原書是直式表格,這裡轉成橫式以放進一頁)
延伸基礎第 6 階 · O(1)懂的人可以跳過
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
收據多了 100 倍,阿姨要多花幾倍時間?
① 先想像
客人問「蘿」開頭誰最熱門。方法 A:把整盒收據翻一遍數。方法 B:翻到筆記「蘿」那一頁,直接念。
你猜猜看:收據從 100 張變 10,000 張,方法 B 要多翻幾頁?
方法 B 只跟客人說了幾個字有關,跟收據多少無關。方法 A 就要多翻 100 倍。
③ 這叫做 O(n)、O(1)
速記「資料變多時,步數怎麼長」。O(n):跟資料量 n 一起長。O(1):不管資料多少都差不多。
④ 跟這章的關係
原書用這種寫法比兩種查法:沒優化是 O(p) + O(c) + O(c log c),優化後是 O(1)(後面兩頁)。
② 動手玩:兩種找法,各要幾步
原書 Step 3用 trie 找 top k · Figure 7
三步找前 k 名:找前綴、走子樹、排序
這一步要解決的問題有了 trie,怎麼從裡面找出前 k 名?要走多少步?
📖 原書 先定義符號
p:前綴長度 n:trie 的節點總數 c:某個節點的子節點數
📖 原書 取得 top k 的步驟
- 找到前綴節點。時間 O(p)
- 從前綴節點走訪子樹,拿到所有有效的子節點(能組成有效查詢字串的才算)。時間 O(c)
- 排序子節點、取前 k。時間 O(c log c)
📖 原書 總時間 O(p) + O(c) + O(c log c)。很直觀,但太慢:最壞情況要走訪整棵 trie 才拿得到 top k。原書接著提出兩個優化。
文組翻譯:客人說「蘿」,阿姨如果沒有筆記,就得把所有「蘿」開頭點過的東西全想一遍、再比誰最多。只有三樣還好,三萬樣就來不及了。
原書 Step 3兩個優化 · Figure 8
限制前綴長度、在每個節點存好 top k
這一步要解決的問題最壞要走整棵樹。能不能讓每次查詢都只走幾步?
第 7 階複習:cache=先抄好放手邊的答案,正本在別處(第 1 章簡報第 18 頁)。這裡的「正本」就是整棵子樹。
📖 原書 1. Limit the max length of a prefix
使用者很少打很長的查詢,可以說 p 是小整數,例如 50。限制前綴長度後,「找前綴」從 O(p) 變成 O(小常數),也就是 O(1)。
📖 原書 2. Cache top search queries at each node
為了不走訪整棵 trie,每個節點存好前 k 個最常用的查詢。5 到 10 個建議就夠,k 很小;這題只快取前 5 個。代價是每個節點都要存,很佔空間;但回應時間很重要,用空間換時間很值得。
📖 原書 優化後的時間
- 找前綴節點:O(1)
- 回傳 top k:已經快取,O(1)
每一步都是 O(1),整個演算法 O(1)。
原書 Step 3 · 動手玩Type-ahead 模擬器
每打一個字,往下走一個節點,直接讀出 top k
這一步要解決的問題親手打字,比較「有快取」和「沒快取」各要走幾步。
建議清單(送出 search?q=tw):
資料:原書 Table 1(tw 開頭的 8 個詞)加上 Figure 8(be、bee、beer、best、bet、buy、win)。試試 t、tw、twi、twitch、b、be、x。
原書 Step 3 · 動手算用空間換時間的帳
越短的前綴越要命:快取 top k 把它變成常數
這一步要解決的問題每個節點都存一份清單,要多花多少空間?值得嗎?
沒有快取
每個節點快取 top k
假設(示意,原書沒有給這些數字):查詢平均 20 字元(原書估算)、開頭字母平均分布、節點數用「完全不共用前綴」的上限估;清單每項存查詢字串 20 bytes + 次數 4 bytes。
你猜猜看:沒有快取時,只打一個字母「t」要走的節點,比打了「twitt」時?
前綴越短,底下的子樹越大:打 t 要走 t 底下的整棵樹,打 twitt 只剩幾個節點。左邊把 p 拉到 1 看看。
📖 原書 每個節點都存 top k,大幅降低取得前 5 名的時間;但這個設計需要大量空間來存每個節點的熱門查詢。因為快速回應非常重要,用空間換時間是值得的。
📖 原書 限制前綴最長 50:找前綴的步數有上限,O(p) 變 O(1)。
怎麼看左邊
把 p 拉到 1(只打一個字母):沒有快取時,要走的子樹和排序量最大;有快取時永遠只是「走 p 步 + 讀 k 項」。把 k 拉大:時間不變,空間線性變大。這就是原書說的取捨。
到這裡你已經會了小結 2 / 5
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
到這裡你已經會了:阿姨的筆記本
- 最直覺的是次數表加一句 SQL;資料大時,每次都要撈出所有符合的列再排序。
- 把開頭掛成分岔路(trie),共同開頭只存一次;每一頁還先抄好前 5 名(cache)。
- 步數只跟打了幾個字有關,前綴又限制最長 50:O(1)。代價是很佔空間。
下一階要解決的問題
筆記本誰來寫?客人每點一次就改,還是一週整理一次?
延伸基礎第 8 階 · aggregation懂的人可以跳過
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
每收一張單就改筆記?還是收據丟盒子、週日一起數?
① 先想像
阿姨每收一張單就停下來改筆記,櫃台的客人只好等。另一種:收據丟進盒子,週日晚上一次數完、重抄筆記。
你猜猜看:「蘿蔔糕加蛋」有 5 個開頭,一張單要改 5 頁筆記。一週 700 張單都這麼長、都馬上改,週間要改幾頁?
700 × 5 = 3,500 頁,每改一頁櫃台就停一下。丟盒子、週日再數,週間 0 頁;代價是新品要等下週才上筆記。
③ 這叫做 log、aggregation
log:只往後加、不改舊的流水帳,就是收據盒。aggregation:把流水帳加總成「每樣幾次」。
④ 跟這章的關係
原書的 data gathering service 就是這樣:log → 每週加總 → 重建 trie(下一頁 Figure 9)。
② 動手玩:兩種記帳法
原書 Step 3Data gathering service · Figure 9
不要每來一個查詢就改 trie:改成每週重建
這一步要解決的問題每天數十億個查詢,每來一個就改 trie,查詢服務受得了嗎?
📖 原書 之前的設計是使用者每輸入一個查詢就即時更新資料。這不實際,兩個原因:
- 使用者每天可能輸入數十億個查詢,每次都更新 trie 會大幅拖慢查詢服務
- trie 建好後,熱門建議可能變化不大,不需要頻繁更新
📖 原書 先看資料從哪來、怎麼被用:Twitter 這種即時應用需要最新的建議;但很多 Google 關鍵字的建議每天變化不大。用途不同,基礎卻一樣:建 trie 的資料通常來自 analytics 或 logging 服務。
白話:analytics/logging 服務=專門把每一筆使用紀錄寫下來的系統(第 21 頁的收據盒)。
文組翻譯:阿姨不會每收一張單就改筆記,否則櫃台前的客人要排隊等她寫字。她把收據丟進盒子,週日再統一抄。
原書 Step 3Analytics Logs · Aggregators · Aggregated Data · Workers · Trie Cache · Table 3 · Table 4
原始 log → 每週加總 → 建 trie → 放進記憶體
這一步要解決的問題原始 log 又大又亂,怎麼變成建 trie 用的「每週每個詞幾次」?
📖 原書 Table 3 Analytics log(append-only、沒有 index)
彙整結果(query, time, frequency)
📖 原書 Table 4 每週彙整的例子:time 是一週的起始日,frequency 是那週該查詢出現的總次數。
| query | tree | tree | tree | toy | toy | toy |
|---|---|---|---|---|---|---|
| time | 2019-10-01 | 2019-10-08 | 2019-10-15 | 2019-10-01 | 2019-10-08 | 2019-10-15 |
| frequency | 12000 | 15000 | 9000 | 8500 | 6256 | 8866 |
📖 原書 Analytics Logs:存搜尋查詢的原始資料,append-only、不建 index(Table 3)。
📖 原書 Aggregators:log 通常很大、格式也不對,要先彙整。依用途彙整方式不同:Twitter 這種即時應用用較短的間隔;很多情況每週一次就夠。面試時要確認即時性重不重要。原書假設 trie 每週重建。
📖 原書 Aggregated Data:每週彙整的資料(Table 4)。
📖 原書 Workers:一組定期執行非同步工作的 server,建 trie、存進 Trie DB。
📖 原書 Trie Cache:分散式 cache,把 trie 放在記憶體加速讀取,每週對 DB 拍一次 snapshot。
白話:append-only=只往後加、不改舊的;index=帳本的索引,查得快、寫得慢;非同步=不用等它做完;snapshot=某個時間點拍下的一份副本。
原書 Step 3Trie DB · Figure 10
trie 要存進資料庫:整棵序列化,或拆成 key-value
這一步要解決的問題建好的 trie 要存在哪裡,才不會一關機就沒了?
📖 原書 Trie DB 是持久化儲存,有兩個選項:
1. Document store
新的 trie 每週建一次,可以定期拍 snapshot、序列化後存進資料庫。MongoDB [4] 這類 document store 很適合存序列化資料。
2. Key-value store
trie 可以用 hash table 表示 [4]:
- trie 的每個前綴 → hash table 的一個 key
- 每個節點上的資料 → 一個 value
KV store 怎麼運作,原書請讀者回去看「Design a key-value store」那章。
第 9 階複習:key-value=一個名字對一份內容(第 6 章簡報第 4 頁)。序列化=把整棵樹壓成一長串存檔。
文組翻譯:選項 1 是把整本筆記拍照存檔;選項 2 是把每一頁撕下來,用「開頭」當標籤收進抽屜,要哪頁抽哪頁。
原書 Step 3Query service · Figure 11
查詢走 Trie Cache;cache 沒有才回 Trie DB
這一步要解決的問題使用者打字時,request 要走哪幾站才拿到建議?
Step 0
按「下一步」。
- 搜尋查詢送到 load balancer
- load balancer 把 request 導到 API servers
- API servers 從 Trie Cache 拿 trie 資料,組出給 client 的建議
- 資料不在 Trie Cache 時,補回 cache,之後同一前綴都從 cache 回
📖 原書 cache miss 可能發生在 cache server 記憶體不足或離線時。查詢服務要「快如閃電」,原書接著提三個優化:AJAX、browser caching、data sampling。
白話:load balancer=帶位員,把 request 分給不同的 API server(第 1 章簡報第 12 頁);API server=真正回答的那台電腦。
延伸基礎第 10 階 · browser cache懂的人可以跳過
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
客人把阿姨的回答記在手機裡,一小時內不再問
① 先想像
你問過阿姨「蘿」開頭有什麼,順手記在手機記事本。一小時內又想到,就看自己的記事本,不用排隊。
你猜猜看:記事本有效 1 小時。你 10 分鐘內想了 3 次「蘿」,阿姨被問了幾次?
只有第一次要問;後兩次看自己的記事本。超過 1 小時,記事本作廢,再問一次。
③ 這叫做 browser cache、max-age
browser cache:瀏覽器替你留的小抄。max-age:小抄有效幾秒,3600 秒 = 1 小時。
④ 跟這章的關係
原書說 Google 的建議就在瀏覽器存 1 小時(下一頁 Figure 12),連 server 都不用碰。
② 動手玩:同一個人一直想到「蘿」
原書 Step 3Query service 優化 · Browser caching · Figure 12
建議一小時內不太會變:讓瀏覽器自己記住
這一步要解決的問題同一個人一直打同樣的開頭,每次都要問 server 嗎?
📖 原書 很多應用的建議短時間內變化不大,可以存在 browser cache,後續 request 直接從 cache 拿。Google 也是這樣:結果在瀏覽器快取 1 小時。private:結果只給單一使用者,共用的 cache 不可以存;max-age=3600:3600 秒內有效。
動手試:cache-control 怎麼決定誰能存
A、B 在同一間公司,共用一台 proxy(shared cache)。public 與 no-store 是對照用的補充,原書只講 private。
白話:header=回覆最上面的幾行小標籤;proxy=公司裡大家共用的轉接站,也能替大家存一份。
原書 Step 3Query service 優化 · AJAX request · Data sampling
只換建議清單、不重整整頁;log 只記 N 分之 1
這一步要解決的問題每打一個字就重新整理整頁?每一個查詢都要記下來嗎?
📖 原書 AJAX request
網頁應用通常用 AJAX 取得建議。主要好處:送出/接收 request 時不會重新整理整個網頁。
白話:AJAX=網頁在背景偷偷送 request,只換一小塊畫面。
每次回應 615 bytes 取自 Figure 12 的 size;整頁 500 KB 是示意值。
📖 原書 Data sampling
大型系統把每個查詢都記下來,要很多運算與儲存。抽樣很重要:例如每 N 個 request 只記 1 個。
用 Table 1 的次數 × 1000 當作一週的真實搜尋,抽樣後乘回 N 估計。每天 1 億次搜尋 = 原書 10M DAU × 10。
到這裡你已經會了小結 3 / 5
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
到這裡你已經會了:筆記怎麼寫、怎麼少被問
- 點單不即時改筆記:先進 log,每週加總(aggregation),workers 重建 trie。
- trie 存進資料庫:整本序列化,或每一頁用 prefix 當 key 存成 key-value。
- 查詢先問 Trie Cache;建議一小時內不太變,讓瀏覽器自己記(browser cache)。AJAX 只換清單,log 只抽樣。
下一階要解決的問題
筆記寫錯要改、有不該念的要刪、太厚了一位阿姨抱不動,怎麼辦?
原書 Step 3Trie operations · Create · Update · Figure 13
更新一個節點,所有祖先的 top k 都要跟著改
這一步要解決的問題次數變了,trie 要怎麼改?為什麼原書寧可整棵重建?
📖 原書 Create
trie 由 workers 用彙整資料建立,資料來源是 Analytics Log/DB。
📖 原書 Update:兩種方式
- 選項 1:每週更新。新 trie 建好後取代舊的
- 選項 2:直接更新單一節點。慢,盡量避免;但 trie 小的話可以接受。更新一個節點時,一路到 root 的祖先都要更新,因為祖先存著子孫的熱門查詢
📖 原書 Figure 13:左邊 beer 原本是 10,右邊更新成 30,這個節點和它的祖先上的 beer 都變成 30。
白話:祖先=從這一頁往回走到 root 經過的每一頁。「beer」的祖先是 bee、be、b。
原書 Step 3Trie operations · Delete · Figure 14
不當的建議:先在 cache 前面濾掉,再慢慢從資料庫刪
這一步要解決的問題筆記上有不該念的詞,週日重抄以前怎麼先擋住?
Trie Cache 裡的「wh」top 5(示意)
過濾後使用者看到的
📖 原書 必須移除仇恨、暴力、色情或危險的建議。在 Trie Cache 前面加一層 filter layer,過濾不想要的建議。
📖 原書 有 filter layer,就能依不同的過濾規則彈性移除結果。不想要的建議會非同步地從資料庫實體刪除,這樣下一次更新週期建 trie 時,就會用正確的資料集。
文組翻譯
筆記已經抄好了,週日前不會重抄。發現某一頁寫了不該說的東西,阿姨先在腦中記一條「這個不要念出來」(filter),收據盒裡那幾張也挑出來丟掉(非同步刪除),下週重抄就乾淨了。
原書 Step 3Scale the storage · 依第一個字母分片
依第一個字母分片:c 開頭的字比 x 多太多了
這一步要解決的問題trie 大到一台放不下,要怎麼切給好幾台?
你猜猜看:原書說三台時用 a–i、j–r、s–z。哪一台最忙?
a、b、c、d 這些常見的開頭字母都在 a–i;s 雖然多,但 u–z 都很少。下面拉拉看。
字母分布是示意:大致依英文單字開頭字母的常見統計,不是原書的數字,也不是搜尋流量。
📖 原書 trie 太大、一台 server 放不下時要擴展。只支援英文,簡單的做法是依第一個字元分片:
- 兩台:a–m 一台,n–z 一台
- 三台:a–i、j–r、s–z
- 照這個邏輯最多 26 台(first level sharding)。超過 26 台就在第二層、甚至第三層分片,例如 a 開頭分成 4 台:aa–ag、ah–an、ao–au、av–az
📖 原書 乍看合理,直到你發現 c 開頭的字比 x 多得多,分布不均。解法在下一頁:分析歷史分布,用 shard map manager。
文組翻譯:請三個阿姨,依開頭的注音分工。分到「ㄉ」的阿姨(蛋餅、蛋堡、豆漿)忙翻,分到「ㄘ」的在發呆。
第 11 階複習:sharding=把資料切成幾份、各放一台(第 1 章簡報第 34 頁)。
原書 Step 3Scale the storage · Shard map manager · Figure 15
先問 shard map「在哪一台」,再去那台拿
這一步要解決的問題平均分字母會不均,怎麼依真實的流量分?
📖 原書 為了緩解資料不平衡,分析歷史資料的分布模式,套用更聰明的分片邏輯(Figure 15)。Shard map manager 維護一個 lookup 資料庫,用來找出資料列該存在哪裡。
白話:lookup 資料庫=查「這個字放在哪一台」的對照表,像大樓一樓的樓層指引。
📖 原書 例如歷史上 s 開頭的查詢量,和 u、v、w、x、y、z 加起來差不多,就可以用兩個 shard:一個給 s,一個給 u 到 z。
原書 Step 4Wrap up
面試官的三個追問:多語言、各國不同、即時熱門
這一步要解決的問題主體設計完,面試官最常追問的三件事。
📖 原書 怎麼支援多語言?
在 trie 節點存 Unicode 字元。Unicode 的定義是「涵蓋世界上所有書寫系統(現代與古代)字元的編碼標準」[5]。
第 2 頁的早餐店例子就是中文字當節點。
📖 原書 各國的熱門查詢不一樣?
可以為不同國家建不同的 trie。為了縮短回應時間,trie 可以放在 CDN。
白話:Unicode=全世界文字的統一編號;CDN=開在客人附近的分店(第 1 章簡報第 21 頁);stream=源源不絕流進來、拿不到全部的資料。
📖 原書 怎麼支援即時熱門(trending)?
新聞事件爆發,某個查詢突然暴紅,原設計不行:workers 每週才跑一次,還沒排到;就算排到了,建 trie 也太久。即時 autocomplete 很複雜、超出範圍,只給幾個想法:
- 用分片縮小工作資料集
- 改變 ranking model,近期查詢給更高權重
- 資料可能是 stream,無法一次拿到全部。串流處理需要另一套系統:Apache Hadoop MapReduce [6]、Spark Streaming [7]、Storm [8]、Kafka [9] 等,需要專門知識,原書不深入
📖 原書 原書最後一句:「恭喜你走到這裡!給自己一個讚。做得好!」原書沒有另外列 other talking points,只有這三個追問。
到這裡你已經會了小結 4 / 5
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
到這裡你已經會了:原書的完整設計
- 改一個詞的次數,它所有祖先頁的前 5 名都要跟著改;所以原書寧可每週整棵重建。
- 不當建議先用 filter layer 擋住,資料庫再慢慢刪。
- 一台放不下就分片(sharding);依字母平均分會不均,要依歷史分布用 shard map。
下一階要解決的問題
原書講完了。接下來用 Triton 在別的題目講過的原則檢查這套設計:資料到底多大?cache 空了誰去補?爆紅的詞擠哪一台?
補充 · Triton 線先講清楚出處的邊界
Triton 談過什麼、沒談過什麼
「我在職場上用過的演算法 /知識 – Trie – 用來解大量文章和 keyword的matching」🗣️ Triton 本人說 075-letter-to-rookie.pdf.md · 給菜鳥的一封信,一行清單
沒有出處的部分(不推論)
- trie 節點怎麼設計、要不要每個節點存 top k
- 每週重建 vs 即時更新 trie
- browser cache-control、AJAX
- 依第一個字母分片、shard map manager
- 多語言、各國不同的 trie
075 那一行講的是 keyword matching,不是 autocomplete,也沒有說怎麼做。這些主題在這份簡報裡只有原書的說法。
🔭 有原則可以套的四個地方
- 原書自己說「資料小時 SQL 可以接受」:Triton 一再講先知道 N、暴力解也是算法、先問能不能用 RDBMS(064、073、182)→ 第 37 頁
- Trie Cache 每週 snapshot、cache miss 補回:Triton 談 cron 預熱、snapshot、cache miss 要上鎖(087、088)→ 第 39 頁
- 即時熱門、top k 的維護:Triton 的即時排行榜與 top-2N list(182、088)→ 第 41 頁
- 資料管線的模組數與資料量:越少模組越好、<100GB 用 RDBMS(073、054;058 是筆記)→ 第 43 頁
讀法:每張卡上 🗣️ 的引文是 Triton 在別的題目說的話,原題目寫在出處旁邊;🔭 那段才是我們套到 autocomplete 的推論。
補充 · Triton 線先知道 N
資料只有一點點,也要蓋整套 trie 嗎?
你猜猜看:你的產品只有 1 萬 DAU、10 萬個不同查詢。原書這樣做:一開始就蓋 trie、每週管線、分片。會出什麼事?
1 萬 DAU 約每秒 23 次,SQL 從 10 萬列撈一小段很快。原書自己也說「資料集小時可以接受」。Triton 在別的題目講的原則是:先量 N,N 變大再換解法。
「Bruteforce algorithm (暴力解法)也是算法的一種啊! – 特別在 n 很小的時間」「N 很小時, O(n^2) / O(n^3) 也好 1ms 和 0.1ms 對用戶感覺是沒差別的」「了解 N (像是 QPS / user count / data size )」「管理系統中的 tech debt ,在 N 變大時換上更好解法」🗣️ Triton 本人說 064-introToAlgorithm.pdf.md · 談 1 萬個點找最近鄰居
「例子:是否使用 ElasticSearch ? – 你需要 Tokenization 嗎? – 能不能先在 RDBMS 做 searching ?」🗣️ Triton 本人說 073-lesson3.pdf.md · backend 課程第三課「通用 vs 專精?」
「如果 k 很小, quick search 不一定最好解法 – 像是 k < 256」「把 array第1到 k 個 item 放到 maxHeap」🗣️ Triton 本人說 064 · K-th item in array
🗣️ Triton 本人說 182 的即時排行榜第一版就是「group by … order by sum(amount) desc limit 1000 + cache TTL 一分鐘」,結果「每次都要掃瞄整個food_consumption資料表」,資料長大後就爆了。182
補充 · Triton 線先知道 N · 動手算
先問 N:資料不大時,Figure 4 那句 SQL 就夠了
🔭 推論 算一下你的 N
🔭 推論 套回原書
- 原書自己寫了「資料集小時是可以接受的解法」。064 的意思是:先量出 N,不要因為面試題是 1,000 萬 DAU,就在 1 萬 DAU 的產品上先蓋 trie 管線。
- 原書第 3 步把子節點全排序 O(c log c);k = 5 時,064 的小 k 用 heap 只要約 c log k。原書的優化是把排序整個移到離線。
- 182 第一版爆掉的原因,和原書說 SQL「資料大時會變瓶頸」是同一件事:每次查詢都重算全部。
補充 · Triton 線Trie Cache 與 cache miss
Trie Cache 空了一格,誰去補?
你猜猜看:原書 Figure 11 第 4 步:前綴不在 cache,就去 Trie DB 拿、再補回。某個前綴每秒被問 1000 次,從 Trie DB 讀回要 80ms。這 80ms 裡有幾個 request 衝進 Trie DB?
每秒 1000 個,0.08 秒就來了 80 個,每個都發現 cache 沒有、各自去 DB 拿。Triton 在 087 的寫法:先上鎖,只讓一個去拿。
「用戶頁面顯示的,是「某時間點的 snapshot」 而不是「即時資訊」」「常用的 cache(像是 ptt的「熱門看板」排名) 要不要寫 cron job,每分鐘重建一次,讓其永遠 留在 redis? – 延伸思考: Data materialization???」🗣️ Triton 本人說 088-redis-intro.pdf.md · 反思 caching
「如果資料X的 QPS是 1000…… – 如果主資料庫需要 80ms回傳資料X,那麼便有 80個 request進了主資料庫」「2 拿到資料X的鎖(在離開時釋放) 3 再次從 Redis拿資料X;如有則直接回傳」🗣️ Triton 本人說 087-redis-2019.pdf.md · 「一般」的 caching 問題、高流量下的 caching
「土法煉鋼但是有效的做法: – 寫一個 crontab,在 cache miss前到主資料庫拿資料放到 redis」🗣️ Triton 本人說 087 · caching 預熱
第 12 階複習:lock=一次只准一個人去做,其他人先等;cache 一空大家同時衝進 DB 叫 cache stampede(第 1 章簡報第 44 頁)。
補充 · Triton 線Trie Cache 與 cache miss · 動手玩
Trie Cache 是預先算好的 snapshot;cache miss 要上鎖再查
🔭 推論 Figure 11 第 4 步:一個熱門前綴 miss 了
- 🔭 原書的 Trie Cache「每週對 DB 拍 snapshot」,正是 088 說的「顯示的是某時間點的 snapshot」與 087 的 cron 預熱:建議本來就不是即時資訊。
- 🔭 原書說 miss 會在 cache server 離線時發生:那是整台的前綴一起 miss。用 087 的算法,預設值 1000 QPS × 80ms 就有 80 個 request 同時打進 Trie DB。
補充 · Triton 線即時熱門與 top-N
即時熱門:一個詞突然暴紅,誰會先被擠爆?
你猜猜看:新聞爆發,「solar eclipse」一分鐘被搜 1 萬次。原書沒說計數放哪;如果每一次搜尋都去改「s」開頭那份前 5 名清單,會出什麼事?
一份清單只住在一台機器上,1 萬次改寫全擠向它,這就是 hotspot。Triton 談排行榜時的修法:計數散開,只有夠格的才去動清單。
「如果 item count < 1M,單純把全部 item用 redis sorted set來存就好」「如果 item count >10M,然後 N <= 1000時 以 List來存 Top 2N sorted item」「如果 list count > 2N,就丟掉多餘的 如果 list count <= 1.1N,就從資料庫補資料」🗣️ Triton 本人說 088-redis-intro.pdf.md · 實作 top-N item;同一份也寫「一般來說,不建議使用 redis sorted sets」
「因為sorted set只有一個,即使建立了redis-cluster也只會存到其中一台redis上」「原來貓咪也會開趴的……瞬間有超高流量進了單一台redis」「這個sorted set只需要存放top 1000貓的資料便好」🗣️ Triton 本人說 182-資料結構很重要…用即時排名來講述.md
第 13 階複習:hotspot=大家都擠向同一台,只有它被打爆(第 5 章簡報第 27 頁)。sorted set=Redis 裡自動排好名次的清單;redis-cluster=好幾台 Redis 分工。
補充 · Triton 線即時熱門與 top-N · 動手玩
即時熱門:計數分散存,只讓 top 2N 的清單被改
- 🔭 新聞爆發 = 182 的「開罐罐派對」:一個詞瞬間暴量。原書的 trending 想法沒說計數放哪;182 的做法是每個查詢的計數散在 KV,超過門檻才動清單。
- 🔭 和排行榜不同:一個查詢屬於每一個前綴的清單,「twitter」一次搜尋要比對 t、tw、twi… 7 個門檻。原書限制前綴長度,在這裡也是在限制寫入放大。
- 🔭 依第一個字母分片時,s 那台就是 182 說的單一熱點(第 32 頁)。
🔭 推論 前綴「s」的清單:N = 5,存 2N = 10
補充 · Triton 線模組數與資料量
原書最後畫了十個元件:小公司要全部照蓋嗎?
你猜猜看:原書的管線有 Analytics Logs、Aggregators、Aggregated Data、Workers、Trie DB、Trie Cache……一家小公司照抄,最先遇到的麻煩是什麼?
每多一個元件,就多一個要監控、會壞、要有人懂的東西。Triton 在 backend 課程講的原則:越少模組越好;資料不到 100GB 先用 RDBMS。
「越少模組越好」「越少模組,便代表 – 你需要監控和管理的模組便越少 – 代表你的團隊需要掌握的語言/技術便越少」「Search DB:看老闆的錢包深度,沒錢別額外架 Search DB」🗣️ Triton 本人說 073-lesson3.pdf.md · 理想的 backend 系統
「資料量不夠大 (<100GB) 就乖乖回去用 RDBMS 就好啦」🗣️ Triton 本人說 054-data-analysis.pdf.md · Data Analysis WITHOUT RDBMS 前言
📝 上課筆記「流量小 先直接全放 Postgres 等流量大 再慢慢搬出去做 例如搜尋用 Elasticsearch」058 · Roy 的 columnar storage mini-talk 筆記,非本人原文
白話:模組=系統裡一個獨立的零件;Search DB、Elasticsearch=專門做搜尋的資料庫;RDBMS=一張張表格的資料庫,例如 PostgreSQL(Postgres)。
補充 · Triton 線模組數與資料量 · 動手算
原書最後畫了十個元件:先數模組、先算資料量
原書的元件
點一下可以標成「小規模時先不要」,看看剩幾個。
- 🔭 原書每個元件都有道理,但 073 會先問:哪些是這個 N 下真的需要的?Aggregators、Aggregated Data、Workers 在資料不大時,可以是 RDBMS 裡的一張 log 表加一個每週的
GROUP BYcron。 - 🔭 054 的 100GB 是談分析用的資料量。原書規模下 4 週的原始 log 約 78 GB,加上抽樣(第 28 頁)會更小。這只是量級對照,不是 Triton 對 autocomplete 的建議。
🔭 推論 Analytics log 有多大?
假設每列 = 查詢 20 bytes(原書)+ 時間戳 8 bytes,不含 index 與 overhead。
到這裡你已經會了小結 5 / 5
- prefix
- QPS
- top k
- SQL
- trie
- O(1)
- cache
- aggregation
- key-value
- browser cache
- sharding
- lock
- hotspot
到這裡你已經會了:Triton 的原則套進來
- 先量 N:資料小時,一句 SQL 加一個每週的 cron 就夠,原書自己也這麼說。
- 熱門前綴的 cache 空了:上鎖(lock),只讓一個去 Trie DB,其他人等著再查 cache。
- 爆紅的詞:計數散在 KV,清單只存 top 2N,別讓一台被擠爆(hotspot)。
13 階全部走完了
下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。
一句話記住
autocomplete 的快,是在背後先算好的:
每個前綴的前 k 名早就寫在那一頁上。
原書的骨架
- 每打一個字一次 request:24K QPS、peak 48K
- trie + 限制前綴長度 + 每個節點快取 top k → O(1)
- log → aggregators → workers 每週重建 → Trie DB → Trie Cache
- AJAX、browser cache(private, max-age=3600)、抽樣
- filter layer 先擋、依歷史分布分片
原書承認的取捨
- 用空間換時間:每個節點都存清單
- 每週重建:犧牲即時性換讀取速度
- 直接改單一節點很慢:祖先全要改
- 即時熱門超出範圍,只給方向
🔭 Triton 原則套進來
- 先量 N:資料小時 SQL 就夠(原書自己也這麼說)
- cache 是 snapshot;miss 要上鎖再查
- top-N 存 2N,計數分散,別讓熱點擠一台
- 先數模組、先算資料量
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源與原書對照
Triton 本人的講義 / 文章(都不是講 autocomplete)
- 075-letter-to-rookie.pdf.md — 職場用過的演算法清單:「Trie – 用來解大量文章和 keyword的matching」(唯一提到 trie 的地方)
- 064-introToAlgorithm.pdf.md — 暴力解也是算法、了解 N、N 變大再換解法;k 很小用 heap
- 073-lesson3.pdf.md — 越少模組越好、「能不能先在 RDBMS 做 searching?」、沒錢別額外架 Search DB
- 182-資料結構很重要…即時排名.md — 排行榜三版:group by + cache、單一 sorted set 熱點、KV 計數 + 只放 top 1000
- 088-redis-intro.pdf.md — top-N:<1M 用 sorted set、>10M 且 N≤1000 存 top 2N list、補資料規則;不建議 sorted set;cache 是 snapshot、cron 重建
- 087-redis-2019.pdf.md — 「一般」caching 的 80 個 request、上鎖再查、crontab 預熱
- 054-data-analysis.pdf.md — <100GB 用 RDBMS
- 058(📝 Roy 的筆記,非本人原文)— 流量小先放 Postgres,等流量大再把搜尋搬到 Elasticsearch
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 6 頁:prefix(5)、top k(9)、trie(13)、O(1)(15)、aggregation(21)、browser cache(26);QPS、SQL、cache、key-value、sharding、lock、hotspot 連到第 1、2、5、6 章簡報;小結(10、20、29、35、45);名詞小卡(47)。早餐店是虛構情境,菜名與份數是示意。
原書對照
Alex Xu, System Design Interview Vol.1 Ch.13。開場與 Figure 1(第 6 頁)、Step 1 問答與需求(7)、估算(8)、高階設計與 Figure 2(11)、Query service、Table 1、Figure 3–4(12)、Trie、Figure 5–6、Table 2(14)、top k 演算法與 Figure 7(16)、兩個優化與 Figure 8(17–19)、Data gathering 與 Figure 9(22)、Table 3–4 與各元件(23)、Trie DB 與 Figure 10(24)、Query service 與 Figure 11(25)、Browser caching 與 Figure 12(27)、AJAX 與 Data sampling(28)、Create/Update 與 Figure 13(30)、Delete 與 Figure 14(31)、Scale the storage 與 Figure 15(32–33)、Wrap up(34)。15 張圖都依原書圖說與 alt 重繪,不是原圖;Figure 2、13 的 alt 有誤,依內文重繪。參考資料:Facebook typeahead [1]、Prefixy [2]、Prefix Hash Tree [3]、MongoDB [4]、Unicode FAQ [5]、Hadoop/Spark Streaming/Storm/Kafka [6]–[9]。
一個可以直接問自己的問題
你的產品有多少個不同的查詢?最短的前綴(一個字母)底下有幾列?在你的資料庫上跑一次 LIKE 'a%' ORDER BY frequency DESC LIMIT 5,量一下要多久,再決定要不要蓋 trie。