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 樣:

    0你說了幾個字 = 阿姨猜了幾次0筆記本一共幾頁(= 節點數)

    阿姨有一本筆記:每一種「開頭」一頁,頁上早就寫好那個開頭最常被點的 3 樣。你每多說一個字,她就往後翻一頁,直接念出那頁寫的東西,不用當場回想所有客人點過什麼。

    筆記不是每來一張單就改:她每週日晚上把一週的點單收據整理一次,重抄整本。這週突然爆紅的新品,下週才會出現在筆記上。

    對照表

    • 筆記本 = trie;一頁 = 一個節點(一個前綴)
    • 頁上寫好的 3 樣 = 節點上快取的 top k
    • 點單收據 = analytics logs;週日重抄 = 每週重建 trie
    • 阿姨太忙,請兩個阿姨分「開頭是哪個字」= sharding

    學習地圖本章的概念階梯

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

    1. 1prefix開頭那幾個字
    2. 2QPS每秒被問幾次
    3. 3top k前幾名
    4. 4SQL跟帳本問話
    5. 5trie字典分岔路
    6. 6O(1)步數不看資料多寡
    7. 7cache先抄好的答案
    8. 8aggregation收據週日加總
    9. 9key-value抽屜貼標籤
    10. 10browser cache客人自己記
    11. 11sharding分給幾位阿姨
    12. 12lock一次只准一人去
    13. 13hotspot全擠向同一位

    第 1–4 階 · 題目在問什麼

    要回答:打一個字,要回哪 5 個?

    第 5–7 階 · 阿姨的筆記本

    要回答:怎麼在 0.1 秒內答出來?

    第 8–10 階 · 筆記怎麼寫、少被問

    要回答:一週的點單怎麼變成筆記?

    第 11–13 階 · 太忙了怎麼辦

    要回答:分工、搶著補、爆紅新品?

    全程只用一家早餐店(虛構):阿姨聽你說一個字,就猜你要點什麼

    客人說出的開頭 = prefix筆記本 = trie一頁 = node頁上寫好的前 3 名 = top k收據盒 = analytics log週日重抄 = 每週重建客人手機裡的記事 = browser cache幾位阿姨分工 = sharding

    每爬 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懂的人可以跳過

    1. prefix
    2. QPS
    3. top k
    4. SQL
    5. trie
    6. O(1)
    7. cache
    8. aggregation
    9. key-value
    10. browser cache
    11. sharding
    12. lock
    13. hotspot

    客人才說一個「蛋」,阿姨要從哪幾樣裡猜?

    ① 先想像

    菜單上有 12 樣。客人開口說「蛋」,阿姨只想「蛋」開頭的那幾樣,其他的先不管。

    你猜猜看:客人說「蛋」,阿姨該不該猜「起司蛋餅」?

    ③ 這叫做 prefix

    prefix(前綴):一串字最前面的那一段。「蘿蔔糕」的 prefix 有:蘿、蘿蔔、蘿蔔糕。

    ④ 跟這章的關係

    原書面試第一題就問「只比對開頭嗎?」答案是對。整章的資料都依 prefix 整理。

    ② 動手玩:客人說出的開頭

    4「蛋」開頭的有幾樣

    原書開場 · Figure 1

    一邊打字,一邊跳出建議:autocomplete

    這一步要解決的問題這道題到底在做什麼?為什麼又叫「design top k」?

    📖 原書 Figure 1在搜尋框打「dinner」時的自動完成清單(依原書內容重繪;原圖是 Google 首頁截圖,logo 與 Google Search/I'm Feeling Lucky 兩個按鈕不重繪,只畫搜尋框與建議)

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

    這一步要解決的問題每打一個字就問一次,系統每秒要被問幾次?每天多出多少資料?

    ~24,000QPS
    ~48,000Peak QPS = 2 × QPS
    0.4 GB每天新增的資料

    打「dinner」時送出的 request:
    • 📖 原書 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懂的人可以跳過

    1. prefix
    2. QPS
    3. top k
    4. SQL
    5. trie
    6. O(1)
    7. cache
    8. aggregation
    9. key-value
    10. browser cache
    11. sharding
    12. lock
    13. hotspot

    阿姨不必背整張排行榜,只要記前幾名

    ① 先想像

    「蛋」開頭有四樣,每週份數:蛋餅 120、蛋吐司 80、蛋餅加起司 60、蛋堡 45。阿姨只念最多人點的前 2 樣。

    你猜猜看:k = 2,阿姨該念哪兩樣?

    ③ 這叫做 top k

    top k:次數最多的前 k 名。k 是你要幾個,原書 k = 5。

    ④ 跟這章的關係

    這題又叫「design top k」:每個 prefix 都要馬上答出它的 top 5。

    ② 動手玩:全店 12 樣,找前 k 名

    阿姨手上的 k 張卡(目前的前 k 名):

      0 / 12看過幾樣0換卡幾次

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

      1. prefix
      2. QPS
      3. top k
      4. SQL
      5. trie
      6. O(1)
      7. cache
      8. aggregation
      9. key-value
      10. browser cache
      11. sharding
      12. lock
      13. hotspot

      到這裡你已經會了:題目在問什麼

      下一階要解決的問題

      前 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 的次數是幾?

      📖 原書 Figure 2frequency table 依序被更新(依原書內文重繪;原書 alt 把這張圖誤讀成分片示意,表格內容以內文的四次查詢為準)

      原書 Step 2Query service · Table 1 · Figure 3 · Figure 4

      最直覺的做法:一句 SQL 撈出前 5 名

      這一步要解決的問題有了次數表,最直覺怎麼撈出某個開頭的前 5 名?

      📖 原書 Figure 3輸入「tw」時顯示的前 5 名(依原書內容重繪)

      📖 原書 假設 frequency table 如 Table 1,有兩個欄位:Query(查詢字串)、Frequency(被搜尋的次數)。

      QueryFrequency

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

      1. prefix
      2. QPS
      3. top k
      4. SQL
      5. trie
      6. O(1)
      7. cache
      8. aggregation
      9. key-value
      10. browser cache
      11. sharding
      12. lock
      13. hotspot

      字典的分岔路:共同的開頭只走一次

      ① 先想像

      從店門口出發,客人每說一個字,就往一條岔路走一步:蛋 → 餅。蛋餅、蛋堡、蛋吐司都先經過「蛋」這個路口。

      你猜猜看:把蛋餅、蛋堡、蛋吐司畫成分岔路,「蛋」這個路口要畫幾個?

      ③ 這叫做 trie、node

      trie:依開頭分岔的樹,又叫 prefix tree。node(節點):一個路口;最上面的起點叫 root。

      ④ 跟這章的關係

      阿姨的筆記本就是一棵 trie:一個路口=一頁。原書用它取代 SQL(下一頁)。

      ② 動手玩:把菜一樣一樣掛上去

      0路口數(不含 root)0每樣各寫一遍要幾個字

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

      Querytreetrytruetoywishwin
      Frequency102935142550

      📖 原書 Table 2(原書是直式表格,這裡轉成橫式以放進一頁)

      📖 原書 Figure 5存 tree、try、true、toy、wish、win 的 trie,搜尋詞用粗框標示(依原書內容重繪)

      延伸基礎第 6 階 · O(1)懂的人可以跳過

      1. prefix
      2. QPS
      3. top k
      4. SQL
      5. trie
      6. O(1)
      7. cache
      8. aggregation
      9. key-value
      10. browser cache
      11. sharding
      12. lock
      13. hotspot

      收據多了 100 倍,阿姨要多花幾倍時間?

      ① 先想像

      客人問「蘿」開頭誰最熱門。方法 A:把整盒收據翻一遍數。方法 B:翻到筆記「蘿」那一頁,直接念。

      你猜猜看:收據從 100 張變 10,000 張,方法 B 要多翻幾頁?

      ③ 這叫做 O(n)、O(1)

      速記「資料變多時,步數怎麼長」。O(n):跟資料量 n 一起長。O(1):不管資料多少都差不多。

      ④ 跟這章的關係

      原書用這種寫法比兩種查法:沒優化是 O(p) + O(c) + O(c log c),優化後是 O(1)(後面兩頁)。

      ② 動手玩:兩種找法,各要幾步

      100方法 A:翻收據(O(n))1方法 B:翻筆記(O(1))100 倍A 是 B 的幾倍

      原書 Step 3用 trie 找 top k · Figure 7

      三步找前 k 名:找前綴、走子樹、排序

      這一步要解決的問題有了 trie,怎麼從裡面找出前 k 名?要走多少步?

      📖 原書 Figure 7k = 2、使用者輸入「tr」(依原書內容重繪)
      按「下一步」開始。

      📖 原書 先定義符號

      p:前綴長度 n:trie 的節點總數 c:某個節點的子節點數

      📖 原書 取得 top k 的步驟

      1. 找到前綴節點。時間 O(p)
      2. 從前綴節點走訪子樹,拿到所有有效的子節點(能組成有效查詢字串的才算)。時間 O(c)
      3. 排序子節點、取前 k。時間 O(c log c)

      📖 原書 總時間 O(p) + O(c) + O(c log c)。很直觀,但太慢:最壞情況要走訪整棵 trie 才拿得到 top k。原書接著提出兩個優化。

      文組翻譯:客人說「蘿」,阿姨如果沒有筆記,就得把所有「蘿」開頭點過的東西全想一遍、再比誰最多。只有三樣還好,三萬樣就來不及了。

      原書 Step 3兩個優化 · Figure 8

      限制前綴長度、在每個節點存好 top k

      這一步要解決的問題最壞要走整棵樹。能不能讓每次查詢都只走幾步?

      📖 原書 Figure 8每個節點存前 5 名,例如「be」存 [best: 35, bet: 29, bee: 20, be: 15, beer: 10](依原書內容重繪;b 節點的清單在原圖被截斷,照截斷畫)

      第 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 個。代價是每個節點都要存,很佔空間;但回應時間很重要,用空間換時間很值得。

      📖 原書 優化後的時間

      1. 找前綴節點:O(1)
      2. 回傳 top k:已經快取,O(1)

      每一步都是 O(1),整個演算法 O(1)。

      原書 Step 3 · 動手玩Type-ahead 模擬器

      每打一個字,往下走一個節點,直接讀出 top k

      這一步要解決的問題親手打字,比較「有快取」和「沒快取」各要走幾步。

      建議清單(送出 search?q=tw):

        2找前綴走了幾個節點(p)0子樹裡走了幾個節點0排序比較次數 ≈ c log c

        資料:原書 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」時?

        📖 原書 每個節點都存 top k,大幅降低取得前 5 名的時間;但這個設計需要大量空間來存每個節點的熱門查詢。因為快速回應非常重要,用空間換時間是值得的。

        📖 原書 限制前綴最長 50:找前綴的步數有上限,O(p) 變 O(1)。

        怎麼看左邊

        把 p 拉到 1(只打一個字母):沒有快取時,要走的子樹和排序量最大;有快取時永遠只是「走 p 步 + 讀 k 項」。把 k 拉大:時間不變,空間線性變大。這就是原書說的取捨。

        到這裡你已經會了小結 2 / 5

        1. prefix
        2. QPS
        3. top k
        4. SQL
        5. trie
        6. O(1)
        7. cache
        8. aggregation
        9. key-value
        10. browser cache
        11. sharding
        12. lock
        13. hotspot

        到這裡你已經會了:阿姨的筆記本

        下一階要解決的問題

        筆記本誰來寫?客人每點一次就改,還是一週整理一次?

        延伸基礎第 8 階 · aggregation懂的人可以跳過

        1. prefix
        2. QPS
        3. top k
        4. SQL
        5. trie
        6. O(1)
        7. cache
        8. aggregation
        9. key-value
        10. browser cache
        11. sharding
        12. lock
        13. hotspot

        每收一張單就改筆記?還是收據丟盒子、週日一起數?

        ① 先想像

        阿姨每收一張單就停下來改筆記,櫃台的客人只好等。另一種:收據丟進盒子,週日晚上一次數完、重抄筆記。

        你猜猜看:「蘿蔔糕加蛋」有 5 個開頭,一張單要改 5 頁筆記。一週 700 張單都這麼長、都馬上改,週間要改幾頁?

        ③ 這叫做 log、aggregation

        log:只往後加、不改舊的流水帳,就是收據盒。aggregation:把流水帳加總成「每樣幾次」。

        ④ 跟這章的關係

        原書的 data gathering service 就是這樣:log → 每週加總 → 重建 trie(下一頁 Figure 9)。

        ② 動手玩:兩種記帳法

        0週間改了幾頁筆記(櫃台停下來)0盒子裡的收據

        原書 Step 3Data gathering service · Figure 9

        不要每來一個查詢就改 trie:改成每週重建

        這一步要解決的問題每天數十億個查詢,每來一個就改 trie,查詢服務受得了嗎?

        📖 原書 之前的設計是使用者每輸入一個查詢就即時更新資料。這不實際,兩個原因:

        • 使用者每天可能輸入數十億個查詢,每次都更新 trie 會大幅拖慢查詢服務
        • trie 建好後,熱門建議可能變化不大,不需要頻繁更新

        📖 原書 先看資料從哪來、怎麼被用:Twitter 這種即時應用需要最新的建議;但很多 Google 關鍵字的建議每天變化不大。用途不同,基礎卻一樣:建 trie 的資料通常來自 analytics 或 logging 服務。

        白話:analytics/logging 服務=專門把每一筆使用紀錄寫下來的系統(第 21 頁的收據盒)。

        文組翻譯:阿姨不會每收一張單就改筆記,否則櫃台前的客人要排隊等她寫字。她把收據丟進盒子,週日再統一抄。

        📖 原書 Figure 9重新設計的 data gathering service:Analytics Logs → Aggregators → Aggregated Data → Workers →(Update weekly)Trie DB →(Weekly Snapshot)Trie Cache(依原書內容重繪;原圖一列排開,這裡折成兩列)

        原書 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 是那週該查詢出現的總次數。

        querytreetreetreetoytoytoy
        time2019-10-012019-10-082019-10-152019-10-012019-10-082019-10-15
        frequency12000150009000850062568866

        📖 原書 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 頁)。序列化=把整棵樹壓成一長串存檔。

        📖 原書 Figure 10左邊每個 trie 節點對應到右邊一組 <key, value>(依原書內容重繪;樹改成縮排畫法,讓每個節點和右邊那一列對齊)

        文組翻譯:選項 1 是把整本筆記拍照存檔;選項 2 是把每一頁撕下來,用「開頭」當標籤收進抽屜,要哪頁抽哪頁。

        原書 Step 3Query service · Figure 11

        查詢走 Trie Cache;cache 沒有才回 Trie DB

        這一步要解決的問題使用者打字時,request 要走哪幾站才拿到建議?

        Step 0

        按「下一步」。

        1. 搜尋查詢送到 load balancer
        2. load balancer 把 request 導到 API servers
        3. API servers 從 Trie Cache 拿 trie 資料,組出給 client 的建議
        4. 資料不在 Trie Cache 時,補回 cache,之後同一前綴都從 cache 回

        📖 原書 cache miss 可能發生在 cache server 記憶體不足或離線時。查詢服務要「快如閃電」,原書接著提三個優化:AJAX、browser caching、data sampling。

        白話:load balancer=帶位員,把 request 分給不同的 API server(第 1 章簡報第 12 頁);API server=真正回答的那台電腦。

        📖 原書 Figure 11改良後的 query service:User(Web browser、Mobile app)→ ① Load balancer → ② API servers → ③ Trie Cache,④ Trie DB(依原書內容重繪)

        延伸基礎第 10 階 · browser cache懂的人可以跳過

        1. prefix
        2. QPS
        3. top k
        4. SQL
        5. trie
        6. O(1)
        7. cache
        8. aggregation
        9. key-value
        10. browser cache
        11. sharding
        12. lock
        13. hotspot

        客人把阿姨的回答記在手機裡,一小時內不再問

        ① 先想像

        你問過阿姨「蘿」開頭有什麼,順手記在手機記事本。一小時內又想到,就看自己的記事本,不用排隊。

        你猜猜看:記事本有效 1 小時。你 10 分鐘內想了 3 次「蘿」,阿姨被問了幾次?

        ③ 這叫做 browser cache、max-age

        browser cache:瀏覽器替你留的小抄。max-age:小抄有效幾秒,3600 秒 = 1 小時。

        ④ 跟這章的關係

        原書說 Google 的建議就在瀏覽器存 1 小時(下一頁 Figure 12),連 server 都不用碰。

        ② 動手玩:同一個人一直想到「蘿」

        0 分經過時間
        0阿姨(server)被問幾次0看自己記事本幾次

        原書 Step 3Query service 優化 · Browser caching · Figure 12

        建議一小時內不太會變:讓瀏覽器自己記住

        這一步要解決的問題同一個人一直打同樣的開頭,每次都要問 server 嗎?

        📖 原書 Figure 12在 Google 打「system design interview」時的回應 header(依原書內容重繪;原圖是瀏覽器開發者工具截圖,只重畫文字,date/expires 的值 alt 沒有給,以 … 表示)

        📖 原書 很多應用的建議短時間內變化不大,可以存在 browser cache,後續 request 直接從 cache 拿。Google 也是這樣:結果在瀏覽器快取 1 小時。private:結果只給單一使用者,共用的 cache 不可以存;max-age=3600:3600 秒內有效。

        動手試:cache-control 怎麼決定誰能存

        0 分經過時間

        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,只換一小塊畫面。

        我的網站 
        頁面其他內容:文章、圖片、側欄……
        0request 數0傳輸量

        每次回應 615 bytes 取自 Figure 12 的 size;整頁 500 KB 是示意值。

        📖 原書 Data sampling

        大型系統把每個查詢都記下來,要很多運算與儲存。抽樣很重要:例如每 N 個 request 只記 1 個。

        用 Table 1 的次數 × 1000 當作一週的真實搜尋,抽樣後乘回 N 估計。每天 1 億次搜尋 = 原書 10M DAU × 10。

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

        1. prefix
        2. QPS
        3. top k
        4. SQL
        5. trie
        6. O(1)
        7. cache
        8. aggregation
        9. key-value
        10. browser cache
        11. sharding
        12. lock
        13. hotspot

        到這裡你已經會了:筆記怎麼寫、怎麼少被問

        下一階要解決的問題

        筆記寫錯要改、有不該念的要刪、太厚了一位阿姨抱不動,怎麼辦?

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

        📖 原書 Figure 13更新 beer:左 10,右 30(依原書內文重繪;原書 alt 的清單內容有誤植,這裡依各節點子孫的頻率重新排序列出)

        原書 Step 3Trie operations · Delete · Figure 14

        不當的建議:先在 cache 前面濾掉,再慢慢從資料庫刪

        這一步要解決的問題筆記上有不該念的詞,週日重抄以前怎麼先擋住?

        📖 原書 Figure 14Filter Layer 放在 Trie 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。哪一台最忙?

            0最忙的 shard / 平均—最忙的 shard 負責

            字母分布是示意:大致依英文單字開頭字母的常見統計,不是原書的數字,也不是搜尋流量。

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

            📖 原書 Figure 15Shard map manager(依原書內容重繪)

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

            1. prefix
            2. QPS
            3. top k
            4. SQL
            5. trie
            6. O(1)
            7. cache
            8. aggregation
            9. key-value
            10. browser cache
            11. sharding
            12. lock
            13. hotspot

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

            下一階要解決的問題

            原書講完了。接下來用 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、每週管線、分片。會出什麼事?

            「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?

            「用戶頁面顯示的,是「某時間點的 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 名清單,會出什麼事?

            「如果 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

            0KV 計數寫入0清單被改的次數0從資料庫補資料

            補充 · Triton 線模組數與資料量

            原書最後畫了十個元件:小公司要全部照蓋嗎?

            你猜猜看:原書的管線有 Analytics Logs、Aggregators、Aggregated Data、Workers、Trie DB、Trie Cache……一家小公司照抄,最先遇到的麻煩是什麼?

            「越少模組越好」「越少模組,便代表 – 你需要監控和管理的模組便越少 – 代表你的團隊需要掌握的語言/技術便越少」「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 BY cron。
            • 🔭 054 的 100GB 是談分析用的資料量。原書規模下 4 週的原始 log 約 78 GB,加上抽樣(第 28 頁)會更小。這只是量級對照,不是 Triton 對 autocomplete 的建議。

            🔭 推論 Analytics log 有多大?

            假設每列 = 查詢 20 bytes(原書)+ 時間戳 8 bytes,不含 index 與 overhead。

            到這裡你已經會了小結 5 / 5

            1. prefix
            2. QPS
            3. top k
            4. SQL
            5. trie
            6. O(1)
            7. cache
            8. aggregation
            9. key-value
            10. browser cache
            11. sharding
            12. lock
            13. hotspot

            到這裡你已經會了:Triton 的原則套進來

            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,計數分散,別讓熱點擠一台
            • 先數模組、先算資料量

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

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

            autocomplete打字時跳出建議;也叫 typeahead
            prefix一串字最前面的那一段(前綴)
            DAU每天打開的人數
            QPS每秒被問幾次;這章每打一個字就問一次
            top k次數最多的前 k 名;原書 k = 5
            frequency table兩欄的次數表:查詢、被搜幾次
            database、SQL存資料的帳本/跟帳本問話的句子
            trie依開頭分岔的樹(prefix tree)
            node、root樹上的一個路口/最上面的起點
            O(n)、O(1)步數跟資料量一起長/不看資料多寡
            cache先抄好放手邊的答案,正本在別處
            用空間換時間每一頁都抄好前 5 名:佔空間,但查得快

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

            引述來源與原書對照

            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。

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