System Design Interview · 第 9 章Triton 覆蓋度:🟠 低Triton 線

Design A Web Crawler
把整個網路抄一遍,還不能吵到別人

原書這章是經典題:從幾個網址出發,下載、抽出連結、再下載,每月抓 10 億頁。難的不是演算法,而是排隊要有禮貌、不重複、不掉進陷阱。Triton 沒有寫過爬蟲的講義或文章,所以這份簡報以把原書講清楚為主,只在他的通用原則真的用得上的三個地方,加上標明 🔭 的推論卡。

給文組

全程用「圖書館員把全城的書抄一遍」比喻,一階一階爬 13 個概念,二十幾個可以動手玩的小互動。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。

給工程師

原書 10 張圖與 Table 1 全部依描述重繪成可播放的 SVG。最後一頁列出原書段落對照與出處檔案(materials/core)。

標籤怎麼看

📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 📅 2026 補充

先用生活理解爬蟲在做什麼

圖書館員要把全城的書抄一份回館裡

待抄清單

剛抄完

(還沒開始)
0抄了幾次0白抄的重複1待抄清單長度

書目:A → B、C B → D、A C → A、E D → B E → C、F F → (沒有)

每本書最後都有參考書目,寫著其他書在哪裡。館員抄完一本,就把書目裡的書加進待抄清單,一直抄下去。

試試看:把「筆記本」關掉再按幾次。A 引用 B、B 又引用 A,館員會在兩本書之間來回抄到天荒地老。這就是原書說的 URL Seen? 要防的「無限迴圈」。

對照表

  • 館員 = crawler(又叫 robot、spider)
  • 書 = 網頁;參考書目 = 超連結
  • 待抄清單 = URL Frontier;筆記本 = URL Seen?
  • 同一間書店不要一次派十個館員去 = politeness

學習地圖本章的概念階梯

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

  1. 1URL書的地址
  2. 2QPS每秒抄幾本
  3. 3queue待抄清單
  4. 4DNS查號台
  5. 5hash內容的指紋
  6. 6BFS / DFS一層層 vs 一路鑽
  7. 7thread同時幾位館員
  8. 8politeness別擠爆同一家
  9. 9priority重要的先抄
  10. 10buffer桌上的小籃子
  11. 11robots.txt門口的告示
  12. 12bloom filter一排燈的記事板
  13. 13MQ不怕當機的待辦板

第 1–5 階 · 一本書怎麼被抄回來

要回答:原書的 11 個元件各做什麼?

第 6–9 階 · 清單照什麼順序抄

要回答:怎麼又快、又有禮貌、又先抄重要的?

第 10–11 階 · 放哪裡、守規矩

要回答:幾億行清單放哪?哪些書不准抄?

第 12–13 階 · Triton 的原則

要回答:記「看過沒」、放清單,有什麼坑?

全程只用一座圖書館(虛構):館員要把全城的書抄回館裡

書 = 網頁書目上的一條 = 連結書店 = 網站(host)館員 = crawler / thread待抄清單 = URL Frontier筆記本 = URL Seen?

每爬 3–4 階,有一頁「到這裡你已經會了」。QPS、DNS、cache、MQ 在第 1、2、4 章的簡報講過,這裡一句話複習並附連結。

路線圖Triton 覆蓋度:🟠 低

這份簡報怎麼走

📖 原書 Step 1–2

  • 開場、爬蟲的四種用途、Figure 1(第 6 頁)
  • 面試問答、好爬蟲的四個特性(7)
  • 估算:400 QPS、30 PB(8)
  • 高階設計與 11 個元件、Figure 2–4(11–17)

📖 原書 Step 3–4

  • DFS vs BFS、Figure 5(20–23)
  • URL frontier:politeness、priority、freshness、storage、Figure 6–8(24–31)
  • HTML downloader:robots.txt、效能、Figure 9(33–35)
  • Robustness、Extensibility、Figure 10、問題內容、Wrap up(36–38)

🔭 依 Triton 原則推論 只有三頁

  • URL Seen? 用 bloom filter:Triton 在 rate limiter 實戰用過(41)
  • Downloader 該開幾個 thread(42)
  • URL frontier 放 Redis 還是 MQ(45)

為什麼覆蓋度是「低」:materials/core 裡沒有任何談爬蟲的講義、文章或留言。能用的只有 Triton 談 bloom filter、concurrency、Go、MQ 的通用材料。這些都是他在別的情境講的話,套到爬蟲一律標 🔭,不寫成「Triton 認為爬蟲應該……」。

延伸基礎第 1 階 · URL懂的人可以跳過

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

每本書都有地址,書的最後還寫著別本書的地址

① 先想像

每本書貼著一張標籤:「B 書店,第 3 櫃」。照著標籤就找得到書。書最後的參考書目,寫的也是這種標籤。

你猜猜看:書 A 的書目寫了 B、C 兩本。館員抄完 A,手上有幾本「還沒抄的書」的地址?

③ 這叫做 URL、HTML

URL:網頁的地址。HTML:網頁的原稿;裡面的 <a href="…"> 就是一條連結(hyperlink)。

④ 跟這章的關係

爬蟲只做三件事:拿 URL 下載 HTML、從 HTML 找出新的 URL、再排隊下載。

② 動手玩:打開「書 A」這一頁

點一下底線的連結,看它的地址分成哪三段。

原書開場 · Figure 1

從幾個網頁出發,順著連結一直找下去

這一步要解決的問題爬蟲到底是什麼?拿來做什麼?

📖 原書 Figure 1爬取過程的範例(依原書內容重繪)

📖 原書 Web crawler 又叫 robot 或 spider,搜尋引擎用它發現網路上新的或更新過的內容:網頁、圖片、影片、PDF 等。它先收集少數網頁,再順著頁面上的連結收集新內容。

📖 原書 四種用途

  • Search engine indexing:最常見。建立搜尋引擎的本地索引,例如 Google 背後的 Googlebot
  • Web archiving:保存網路資料,例如美國國會圖書館、EU web archive
  • Web mining:例如頂尖金融公司下載股東會與年報,了解公司策略
  • Web monitoring:監控版權與商標侵權,例如 Digimarc 找盜版

白話:indexing=替網頁做索引,像書後面的關鍵字目錄;archiving=典藏;mining=從資料裡挖出有用的東西;monitoring=監控。

📖 原書 複雜度看規模:可以是幾小時寫完的學校作業,也可以是需要專職團隊持續改進的大工程。所以先釐清規模與功能。

原書 Step 1釐清需求

基本演算法只有三步,但面試要先問清楚規模

這一步要解決的問題要抓多少、抓什麼、存多久?規模不同,設計完全不同。

📖 原書 應徵者 × 面試官

應徵者問面試官答
主要用途?搜尋引擎索引、data mining,還是別的?Search engine indexing
每個月收集多少網頁?10 億頁
包含哪些內容類型?只有 HTML,還是也有 PDF、圖片?只有 HTML
要考慮新增或編輯過的網頁嗎?要
爬下來的 HTML 要存嗎?要,最多存 5 年
內容重複的網頁怎麼處理?忽略

原書:這些只是範例問題。就算是爬蟲這種看似單純的產品,你和面試官的假設也可能不同。

📖 原書 基本演算法

  1. 給一組 URL,下載這些 URL 指向的網頁
  2. 從網頁裡抽出 URL
  3. 把新 URL 加進待下載清單,重複這三步

真的這麼簡單嗎?不完全是。要在面試時間內設計出超大型爬蟲幾乎不可能。

📖 原書 好爬蟲的四個特性

  • Scalability:網頁有數十億,要靠平行化
  • Robustness:壞掉的 HTML、不回應的 server、crash、惡意連結都很常見
  • Politeness:短時間內不要對同一網站發太多 request
  • Extensibility:之後要爬圖片,不該整個重新設計

白話:scalability=能靠加機器長大;平行化=很多台同時做;robustness=耐摔;politeness=有禮貌;extensibility=好擴充。

原書 Step 1Back of the envelope estimation

每月 10 億頁:每秒 400 頁、五年 30 PB

這一步要解決的問題每月 10 億頁:要抓多快?倉庫要多大?

~400QPS(頁/秒)
800Peak QPS = 2 × QPS
500 TB每月儲存
30 PB全部保存期間

📖 原書 這些估算建立在很多假設上,要和面試官溝通、取得共識:

  • 每月下載 10 億個網頁
  • QPS:1,000,000,000 / 30 天 / 24 小時 / 3600 秒 ≈ 每秒 400 頁
  • Peak QPS = 2 × QPS = 800
  • 平均網頁大小 500k;10 億頁 × 500k = 每月 500 TB
  • 存五年:500 TB × 12 個月 × 5 年 = 30 PB

文組翻譯

每秒抄 400 本書。五年抄下來的紙,要 30 PB 的書庫來放。單位不熟的話,原書請你回去看「Back-of-the-envelope Estimation」那章的 Power of 2。

複習:QPS=每秒幾次(第 2 章簡報第 23 頁);儲存量怎麼估(第 25 頁);TB、PB 是數有幾個零(第 6 頁)。

延伸基礎第 3 階 · queue懂的人可以跳過

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

待抄清單:新發現的寫在最後,每次從最前面拿

① 先想像

館員把要抄的書寫在一張長紙條上。新發現的寫在最下面,每次從最上面拿一本來抄。跟郵局抽號碼牌一樣。

你猜猜看:紙條上依序是 B、C。抄 B 的時候又發現 D。下一本抄哪一本?

③ 這叫做 queue、FIFO

queue:排隊的清單。FIFO(first in, first out):先排進來的先出去。

④ 跟這章的關係

原書說:放待下載網址的 URL Frontier,可以先想成一條 FIFO queue。

② 動手玩:一張待抄紙條

2紙條上還有幾本—抄過的順序

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

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

到這裡你已經會了:爬蟲要抄什麼、抄多少、怎麼排隊

下一階要解決的問題

下載、檢查、去重、抽連結,原書怎麼把它們接成一條會繞圈的生產線?

原書 Step 2High-level design · Figure 2

一條環狀的生產線:下載、解析、去重、抽連結、再排隊

這一步要解決的問題前面那三步演算法,實際上要拆成哪些元件、怎麼接?

📖 原書 Figure 2高階設計:seed URLs → URL Frontier → HTML Downloader(DNS Resolver)→ Content Parser → Content Seen? → Link Extractor → URL Filter → URL Seen? → 回到 Frontier(依原書內容重繪;原圖的「Content St..」「URL Storag..」是截斷的 Content Storage 與 URL Storage)
原書說這個設計參考了前人的研究:Mercator [4] 與 Olston、Najork 的 Web Crawling [5]。

原書 Step 2元件 1–5

起點、排隊、下載、查地址、拆解

這一步要解決的問題從哪裡開始抄?清單放哪?怎麼找到書店?抄回來的怎麼檢查?

📖 原書 Seed URLs

爬取的起點。要爬一所大學的網站,直覺做法是用大學的網域名稱。要爬整個網路就要有創意:好的 seed 能讓爬蟲走到盡量多的連結。一般策略是把 URL 空間切成小塊:

原書:這是開放性問題,不必給完美答案,把思考過程講出來就好。

📖 原書 URL Frontier

多數現代爬蟲把狀態分成兩份:待下載和已下載。存待下載 URL 的元件叫 URL Frontier,可以先把它想成 FIFO queue。細節在 deep dive(第 24 頁起)。

📖 原書 HTML Downloader

從網路下載網頁,URL 由 URL Frontier 提供。

文組翻譯:DNS = 查書店地址的電話簿(第 1 章簡報第 6 頁);crawl server = 跑爬蟲的機器;Content Parser = 抄回來先檢查有沒有缺頁、亂碼,壞的不歸檔。

📖 原書 DNS Resolver

下載前要把 URL 轉成 IP。HTML Downloader 呼叫 DNS Resolver 拿 IP,例如 www.wikipedia.org 在 2019/3/5 轉成 198.35.26.96。

📖 原書 Content Parser

下載後要解析並驗證,因為格式錯誤的網頁會引發問題、浪費儲存空間。在 crawl server 裡做解析會拖慢爬取,所以 content parser 是獨立元件。

延伸基礎第 5 階 · hash懂的人可以跳過

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

兩本 300 頁的書一不一樣,要逐字比嗎?

① 先想像

逐字比兩本書要一整天。改成:每本書照同一條規則算出一個號碼,當作「指紋」,只比號碼。

你猜猜看:書 X 的指紋是 1234,書 Y 是 1235。兩本內容一樣嗎?

③ 這叫做 hash、fingerprint

hash:把一大段內容壓成一小串固定長度的號碼。fingerprint:拿來辨認內容的那串號碼(指紋)。

④ 跟這章的關係

原書的 Content Seen? 就是比 hash,不逐字比(下一頁)。後面的 bloom filter 也是用 hash 做的。

② 動手玩:兩種「指紋」規則

原書 Step 2元件 6–7 · Content Seen? · Content Storage

29% 的網頁內容是重複的:比 hash,不要逐字比

這一步要解決的問題同一份內容換個網址又出現,怎麼不存兩次、又不用逐字比?

動手試:三個 URL,兩份一樣的內容

Content Seen? 記住的 hash:

(空)

📖 原書 線上研究指出 29% 的網頁是重複內容,會讓同一份內容被存好幾次。Content Seen? 這個資料結構用來消除冗餘、縮短處理時間,偵測系統裡已經存過的內容。

📖 原書 比較兩份 HTML 可以逐字元比,但數十億網頁時又慢又耗時。有效率的做法是比較兩個網頁的 hash 值(原書引用 Rabin 的 fingerprinting [7])。hash 是什麼,見第 13 頁。

📖 原書 Content Storage

存 HTML 內容。選哪種儲存看資料類型、大小、存取頻率、壽命等。磁碟和記憶體都用:

  • 資料集太大放不進記憶體,大部分存磁碟
  • 熱門內容放記憶體,降低延遲

白話:磁碟=倉庫,大但慢;記憶體=桌上,快但小(第 30 頁);延遲=要等多久。

原書 Step 2元件 8 · URL Extractor · Figure 3

從 HTML 抽出連結,相對路徑補成完整網址

這一步要解決的問題連結常常只寫一半(「同一家店的第 3 櫃」),怎麼補成完整地址?

📖 原書 Figure 3連結擷取的例子(依原書內容重繪;alt 只寫出第一個連結 /wiki/Cong_Weixi,其餘三個以 … 表示)

📖 原書 URL Extractor 解析 HTML 頁面並抽出連結。Figure 3 是例子:<a href="/wiki/Cong_Weixi"> 是相對路徑,加上 https://en.wikipedia.org 前綴,轉成絕對 URL。

動手試:相對路徑 → 絕對 URL

頁面所在:https://en.wikipedia.org/wiki/Main_Page。試試 /wiki/Spider、https://www.b.com/、Cong_Weixi(沒有斜線開頭)。

文組翻譯:參考書目寫「同一家書店,三樓第 5 櫃」,館員要先補成「XX 書店,三樓第 5 櫃」,才能放進待抄清單,不然別人看不懂是哪家書店。

原書 Step 2元件 9–11 · URL Filter · URL Seen? · URL Storage

抽出來的連結,先過濾、再查「看過沒」

這一步要解決的問題抽出來的連結,哪些不該排進清單?怎麼知道「看過沒」?

📖 原書 URL Filter

排除特定的內容類型、副檔名、錯誤連結,以及「黑名單」網站的 URL。

📖 原書 URL Seen?

追蹤已經造訪過、或已經在 Frontier 裡的 URL。避免同一個 URL 被加很多次,那會增加 server 負擔,還可能造成無限迴圈。常見實作是 bloom filter 和 hash table;原書不講細節,請讀者看參考資料 [4] [8](第 40、41 頁補上 bloom filter 怎麼運作;hash table=用 hash 當索引的大表,可以很快查到有沒有)。

📖 原書 URL Storage

存已經造訪過的 URL。

動手試:連結的三道關卡

黑名單、副檔名規則是示意。原書只說 filter 會排除「內容類型、副檔名、錯誤連結、黑名單網站」,沒有給規則清單。

原書 Step 2Web crawler workflow · Figure 4

照著 11 個編號,走一遍爬蟲的工作流程

這一步要解決的問題11 個元件,一個網址實際走一圈是什麼順序?

  1. seed URLs 加進 URL Frontier
  2. HTML Downloader 從 Frontier 拿一批 URL
  3. 向 DNS resolver 拿 IP,開始下載
  4. Content Parser 解析、檢查是否格式錯誤
  5. 解析驗證後交給 Content Seen?
  6. 檢查這個 HTML 是否已在 storage
  7. Link Extractor 抽出連結
  8. 連結交給 URL Filter
  9. 過濾後交給 URL Seen?
  10. 檢查 URL 是否已在 storage;在就不用做事
  11. 沒處理過的 URL 加進 URL Frontier
📖 原書 Figure 4加上序號的設計圖(依原書內容重繪;編號位置依 alt 與內文 Step 1–11)

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

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

到這裡你已經會了:原書的生產線繞一圈

下一階要解決的問題

清單上有幾億個網址,要照什麼順序抄?先往深處鑽,還是一層一層來?

延伸基礎第 6 階 · BFS / DFS懂的人可以跳過

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

先把同一層的書抄完,還是一路往下追?

① 先想像

A 的書目有 B、C;B 的書目有 D、E;C 的書目有 F、G。館員可以先抄完 B、C 再往下,也可以抄完 B 就馬上追 D。

你猜猜看:從 A 開始一層一層抄,第三本抄的是?

③ 這叫做 BFS、DFS

BFS:一層一層走,用上一階的 queue。DFS:一路追到底再回頭,像疊盤子,後放的先拿。

④ 跟這章的關係

網路可以深到沒有底。原書說:爬蟲用 BFS(下一頁)。

② 動手玩:同一棵書目樹,兩種抄法

原書 Step 3Deep dive · DFS vs BFS

網路是一張有向圖:先往深處鑽,還是一層一層掃?

這一步要解決的問題網路是一張網,清單要照什麼順序走?

0已下載頁數0目前深度0最深到第幾層

📖 原書 把網路想成有向圖:網頁是節點,超連結是邊。爬取就是在這張圖上走訪。常見的兩種走法是 DFS 和 BFS。

📖 原書 DFS 通常不是好選擇,因為深度可能非常深。BFS 是爬蟲常用的,用 FIFO queue 實作:URL 照加入的順序被取出。

文組翻譯

DFS 像讀維基百科「點下一個連結」點到凌晨三點,越陷越深,同一個主題的旁支全沒看。BFS 像先把每家書店的首頁翻一遍,再一層一層往下。

但 BFS 也有兩個問題,後兩頁講。

延伸基礎第 7 階 · thread懂的人可以跳過

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

一位館員抄 6 本要 6 小時,請 3 位呢?

① 先想像

抄一本要 1 小時:走路去書店、等店員拿書花 50 分鐘,真正動筆只有 10 分鐘。多請幾位館員同時出門。

你猜猜看:6 本書、3 位館員同時出門,全部抄完要多久?

③ 這叫做 thread、worker

thread:電腦裡同時進行的一條工作線,就是一位館員。worker:專門負責某件事(例如下載)的那幾條 thread。

④ 跟這章的關係

原書的 HTML Downloader 用很多 thread 平行下載。可是大家都擠進同一家書店呢?下一頁。

② 動手玩:館員人數

26 本全部抄完(小時)17%動筆時間(綠色;灰色=走路等書)

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

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

同一家書店,一次衝進去 3 位館員

① 先想像

小書店只有一位店員幫忙拿書。館員一次衝進去好幾位,店員忙不過來,真正的客人也買不到書。

你猜猜看:清單前 6 本都在百科書店,有 3 位館員。怎麼抄最不吵到店家?

③ 這叫做 host、politeness

host:網站所在的那台主機,就是「哪一家書店」。politeness:同一個 host 一次只抓一頁,中間還休息一下。

④ 跟這章的關係

原書說 BFS 的第一個問題就是不禮貌,解法是「一個 host 一條 queue」(後兩頁)。

② 動手玩:館員怎麼派

3最忙那家同時有幾位館員4那家每小時被敲門幾次

原書 Step 3BFS 的兩個問題 · Figure 5

BFS 的問題:一窩蜂打同一個網站,而且不分輕重

這一步要解決的問題照 BFS 的順序一路抄下去,會出什麼問題?

📖 原書 Figure 5wikipedia.com 的連結都是內部連結(依原書內容重繪)

📖 原書 問題 1:不禮貌

同一個網頁的連結,大多指回同一個 host。Figure 5 裡 wikipedia.com 的連結全是內部連結,爬蟲忙著處理同一個 host 的 URL。平行下載時,Wikipedia 的 server 會被 request 淹沒,這被視為「impolite」。

📖 原書 問題 2:不看優先順序

標準 BFS 不考慮 URL 的優先權。網路很大,不是每頁的品質和重要性都一樣,所以可能要依 page rank、流量、更新頻率等排序。

白話:page rank=依「被多少重要網頁連到」算出的重要性(第 25 頁)。

文組翻譯:清單上前 1000 本都在同一家書店,館長派 100 個館員同時衝進去,書店老闆會報警。

原書 Step 3URL frontier · Politeness · Figure 6 · Table 1

一個 host 一條 queue,一條 queue 一個 worker

這一步要解決的問題同一個 host 一次只抓一頁,要怎麼做到?

📖 原書 URL frontier 是存待下載 URL 的資料結構,負責 politeness、URL 優先順序、freshness(原書引用論文 [5] [9])。

📖 原書 沒有限制的話,爬蟲每秒可以對同一網站發幾千個 request,甚至被當成 DOS 攻擊。基本想法:同一個 host 一次只下載一頁,兩次下載之間可以加 delay。做法是維護 hostname → 下載 worker thread 的對應。

HostQueue
wikipedia.comb1
apple.comb2
……
nike.combn

📖 原書 Table 1 Mapping table

  • Queue router:確保 b1…bn 每條只放同一個 host 的 URL
  • Mapping table:每個 host 對應一條 queue
  • Queue selector:每個 worker 對應一條 FIFO queue,只從那條下載
  • Worker thread 1…N:一頁一頁下載同一個 host,中間可加 delay
📖 原書 Figure 6管理 politeness 的設計(依原書內容重繪)

延伸基礎第 9 階 · priority懂的人可以跳過

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

市政府公告和路邊傳單,哪個先抄?

① 先想像

館員時間有限,重要的書要先抄。可是傳單也不能永遠不抄。做法:抽籤箱裡,重要的書放 3 張籤,普通的放 1 張。

你猜猜看:抽 4 次,重要的大約被抽中幾次?

③ 這叫做 priority、PageRank

priority:優先權,越高越常被選到。PageRank:Google 用「被多少重要網頁連到」來算網頁有多重要。

④ 跟這章的關係

原書的 front queues 就是好幾個抽籤箱,偏心地抽(下一頁 Figure 7)。

② 動手玩:每分鐘來 1 本重要、1 本普通,館員每分鐘抄 1 本

0經過分鐘0普通的書最久等了幾分鐘

原書 Step 3URL frontier · Priority · Figure 7

Apple 首頁比論壇的隨便一篇文重要:先爬它

這一步要解決的問題重要的網頁先爬,又不讓其他網頁永遠輪不到,怎麼做?

📖 原書 Figure 7管理 URL priority 的設計(依原書內容重繪)

📖 原書 Apple 產品論壇的一篇隨機貼文,和 Apple 首頁的分量差很多,雖然都有「Apple」這個關鍵字。依有用程度排序,可以用 PageRank [10]、網站流量、更新頻率等來衡量。

  • Prioritizer:輸入 URL,計算優先權
  • Queue f1 到 fn:每條 queue 有一個優先權,高的被選中的機率較高
  • Queue selector:隨機選 queue,但偏向優先權高的

動手試:偏心的抽籤

f2、f3 權重固定 3 和 1(示意)。高優先權抽得多,但低優先權不會完全沒機會:這就是「隨機但偏心」。

原書 Step 3URL frontier design · Figure 8

把兩個設計接起來:front queues 管優先,back queues 管禮貌

這一步要解決的問題「管先後」和「管禮貌」兩個設計,怎麼接成同一個 frontier?

📖 原書 Figure 8URL frontier 設計(依原書內容重繪;原圖為上到下,這裡改成左到右以放進一頁)
📖 原書 Front queues:manage prioritization。Back queues:manage politeness。下一頁可以一步一步玩。

原書 Step 3 · 動手玩URL frontier 模擬器

一步一步看:URL 怎麼穿過兩層 queue

這一步要解決的問題兩層 queue 一起跑起來,實際長什麼樣?

0經過秒數

看點 1:Apple 首頁(★)在 f1,很快就被偏心的 front selector 選中、下載。

看點 2:b1 排了一堆 wikipedia,Worker 1 也只能每隔「delay + 1」秒下載一頁:politeness。

看點 3:把 delay 拉到 0,wikipedia 每秒都被打;拉到 4,全部下載完要很久。禮貌是用時間換的。

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

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

到這裡你已經會了:清單照什麼順序抄

下一階要解決的問題

清單有幾億行,放在哪裡才不會塞爆、也不怕當機?哪些書,書店根本不准抄?

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

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

新發現的書,先放桌上的小籃子,滿了再搬去倉庫

① 先想像

桌上拿東西快,但很小,打翻咖啡就全毀。倉庫又大又安全,但走一趟要很久。所以先在桌上湊一籃,再一起搬。

你猜猜看:籃子滿 10 張才搬一次。籃子裡有 7 張時打翻咖啡,會毀掉幾張?

③ 這叫做 buffer

buffer:先暫放、湊滿一批再處理的小籃子。桌上 = 記憶體,倉庫 = 磁碟(第 2 章簡報第 12 頁)。

④ 跟這章的關係

原書:frontier 大部分放磁碟,記憶體留 buffer,定期寫進磁碟(下一頁)。

② 動手玩:籃子要多大?

10100 張要走幾趟倉庫9打翻時最多毀掉幾張

原書 Step 3Freshness · Storage for URL Frontier

舊頁要重爬;幾億個 URL 要放哪

這一步要解決的問題網頁會改,清單有幾億行:什麼時候重爬?清單放哪?

📖 原書 Freshness

網頁不斷被新增、刪除、編輯,爬蟲要定期重爬已下載的頁面。全部重爬又耗時又耗資源,原書的策略:

  • 依網頁的更新歷史決定何時重爬
  • 排優先順序,重要頁面先爬、爬得更勤

📖 原書 Storage for URL Frontier

真實的搜尋引擎爬取,frontier 裡的 URL 可能有數億個 [4]。全部放記憶體不耐久也無法擴展;全部放磁碟又太慢,會變成瓶頸。

原書採混合做法:大部分 URL 存磁碟,空間不是問題;記憶體裡維護 enqueue / dequeue 的 buffer,buffer 的資料定期寫到磁碟。

動手試:記憶體 buffer + 磁碟

延伸基礎第 11 階 · robots.txt懂的人可以跳過

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

書店門口貼著:「館員請勿進入倉庫和休息室」

① 先想像

每家書店門口有一張告示,寫哪些地方不准抄。守規矩的館員進門前先看。告示很少改,抄一份帶在身上就好。

你猜猜看:館員一天進同一家書店 1,000 次。早上抄一份告示帶著,一天要走到門口看告示幾次?

③ 這叫做 robots.txt、cache

robots.txt:網站放在固定位置的告示檔,寫爬蟲不能抓哪些路徑。cache:隨身小抄(第 1 章簡報第 18 頁)。

④ 跟這章的關係

原書:下載前先看 robots.txt,並且 cache 起來(下一頁)。查 DNS 也是同一招。

② 動手玩:百科書店的告示


      

0走回門口看告示的次數0想進門的次數

原書 Step 3HTML Downloader · Robots.txt

進門前先看門口的告示:robots.txt

這一步要解決的問題網站不想被爬的地方,爬蟲怎麼知道?

動手試:這個路徑 Googlebot 能爬嗎?


      

📖 原書 HTML Downloader 用 HTTP 下載網頁。先看 Robots Exclusion Protocol:robots.txt 是網站和爬蟲溝通的標準,寫明爬蟲可以下載哪些頁面。爬一個網站前,要先檢查它的 robots.txt 並遵守。

📖 原書 為了避免重複下載 robots.txt,把結果 cache 起來,定期重新下載存進 cache。左邊的規則取自 https://www.amazon.com/robots.txt:creatorhub 等目錄不准 Googlebot 爬。

文組翻譯

書店門口貼著「館員請勿進入倉庫、員工休息室」。守規矩的館員進門前先看告示;告示抄一份帶在身上,不用每次進門都重看。

📅 2026 補充 robots.txt 在 2022 年成為 IETF 標準 RFC 9309,* 萬用字元與「最長規則優先」都寫進了標準。原書的片段只有 Disallow,所以這裡只判斷前綴與 *。

原書 Step 3HTML Downloader · Performance optimization · Figure 9

四個加速法:分散、DNS cache、就近、短 timeout

這一步要解決的問題每秒要下載 400 頁,下載這一關怎麼加速?

📖 原書 1. Distributed crawl

爬取工作分散到多台 server,每台跑多個 thread。URL 空間切成小塊,每個 downloader 負責其中一部分。

📖 原書 Figure 9分散式爬取(依原書內容重繪)

文組翻譯:分店遍佈各區(分散、就近);書店地址抄在小本子上不用每次打 104(DNS cache);敲門三分鐘沒人應就換下一家(short timeout)。

📖 原書 2. Cache DNS Resolver

DNS 是爬蟲的瓶頸,回應時間 10ms 到 200ms,許多 DNS 介面是同步的。下一頁用動畫演。

📖 原書 3. Locality

把 crawl server 依地理分散。離網站 host 越近,下載越快。Locality 適用大多數元件:crawl server、cache、queue、storage 等。

📖 原書 4. Short timeout

有些 server 回應很慢或根本不回應。設定最長等待時間,host 在時間內沒回應,就停掉這個工作,去爬別的頁面。

原書 Step 3Performance optimization · Cache DNS Resolver

一個 thread 在查 DNS,其他 thread 都得等

這一步要解決的問題查 DNS 很慢,而且一次只能一個人查,怎麼辦?

01 秒內下載完的頁數(4 個 thread)0花在「等別人查 DNS」的 ms

📖 原書 許多 DNS 介面是同步的,回應時間介於 10ms 到 200ms。一個 crawler thread 發出 DNS request 後,其他 thread 會被擋住,直到第一個 request 完成。

📖 原書 維護自己的 DNS cache,避免頻繁呼叫 DNS,是有效的加速技巧。DNS cache 存 domain name → IP 的對應,由 cron job 定期更新。

白話:同步=站著等對方回答,不能先做別的;cron job=定時自動執行的工作,像每天早上的鬧鐘;cache 見第 32 頁。

怎麼看左圖

查 DNS 等別人查完 下載 100ms。同一時間只有一個 thread 能查 DNS。把命中率拉高,黃色和紅色一起消失。

原書 Step 3Robustness · Extensibility · Figure 10

壞了能接著跑;要爬新東西,插一個模組就好

這一步要解決的問題機器會壞、需求會變:怎麼讓爬蟲耐摔又好擴充?

📖 原書 Robustness

  • Consistent hashing:在 downloader 之間分配負載,新增或移除 downloader server(見第 5 章)
  • Save crawl states and data:為了防故障,爬取狀態和資料寫進儲存系統;中斷後載入狀態就能重啟
  • Exception handling:大型系統錯誤無法避免,要優雅處理,不讓整個系統 crash
  • Data validation:防止系統錯誤的重要措施

📖 原書 Extensibility

系統會演進,設計目標之一是彈性地支援新的內容類型,靠插入新模組擴充:

  • PNG Downloader:下載 PNG 檔案
  • Web Monitor:監控網路,防止版權與商標侵權
📖 原書 Figure 10Extension Module:PNG Downloader、Link Extractor、Web Monitor 並排(依原書內容重繪)

原書 Step 3Detect and avoid problematic content

重複、陷阱、雜訊:三種不該抓回來的東西

這一步要解決的問題有些網頁會把爬蟲困住、有些根本不值得存:怎麼避開?

動手試:Spider trap

0URL 長度1這個網站發現的頁數爬取中狀態

📖 原書 1. Redundant content

約 30% 的網頁是重複的,用 hash 或 checksum 偵測(第 14 頁)。

📖 原書 2. Spider traps

讓爬蟲陷入無限迴圈的網頁,例如無限深的目錄:http://www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/...。可以設 URL 最大長度避開,但沒有萬用解法。有陷阱的網站很好認:發現的頁數異常地多。自動演算法很難做,可以人工確認後把網站排除,或套用自訂的 URL filter。

📖 原書 3. Data noise

廣告、程式碼片段、垃圾 URL 等沒什麼價值的內容,能排除就排除。

原書 Step 4Wrap up

原書沒講完的六個討論點

這一步要解決的問題面試最後還有時間,原書建議再聊哪些?

📖 原書 Server-side rendering

很多網站用 JavaScript、AJAX 即時產生連結,直接下載解析會漏掉。先做 server-side rendering(又稱 dynamic rendering)再解析 [12]。

📖 原書 Filter out unwanted pages

儲存和爬取資源有限,anti-spam 元件能過濾低品質與垃圾頁面 [13] [14]。

📖 原書 Database replication and sharding

提升資料層的 availability、scalability、reliability。

📖 原書 Horizontal scaling

大規模爬取要幾百甚至幾千台 server 下載。關鍵是 server 要 stateless。

📖 原書 Availability, consistency, reliability

任何大型系統成功的核心。

📖 原書 Analytics

收集與分析資料是微調系統的關鍵原料。

白話:JavaScript、AJAX=網頁打開後才用程式長出內容;anti-spam=擋垃圾;replication=資料抄好幾份(第 1 章簡報第 14 頁);sharding=分冊存放(第 34 頁);stateless=機器身上不留狀態(第 24 頁);availability=有開門的比例(第 2 章簡報第 15 頁)。

📖 原書 總結:好爬蟲的特性是 scalability、politeness、extensibility、robustness。網路極大又充滿陷阱,可擴展的爬蟲不是簡單的任務。原書最後一句:「恭喜你讀到這裡!給自己拍拍肩膀。」

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

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

到這裡你已經會了:原書整章

下一階要解決的問題

Triton 沒有寫過爬蟲。但「記住看過沒」、「開幾位館員」、「清單放哪」這三件事,他在別的題目講過原則。

延伸基礎第 12 階 · bloom filter懂的人可以跳過

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

記不住一億個書名?門口裝一排 8 盞燈

① 先想像

每本書用兩條固定的規則算出兩個燈號。抄過就把那兩盞打開。要問「抄過沒」,就看那兩盞燈。

你猜猜看:一本書的兩盞燈,有一盞是暗的。這本書抄過嗎?

③ 這叫做 bloom filter、false positive

bloom filter:一排開關加幾條 hash 規則,用很少的空間記「看過沒」。false positive:沒看過,卻說「可能看過」。

④ 跟這章的關係

原書說 URL Seen? 常用 bloom filter,但不講細節。Triton 在別的題目用過它(下一頁)。

② 動手玩:燈號 1 = 書號 ÷ 8 的餘數;燈號 2 = (書號 × 3 + 1) ÷ 8 的餘數

抄過:
問:

補充 · Triton 線URL Seen? 的 bloom filter

Bloom filter:「一定沒看過」或「可能看過」

🔭 推論 089 是 rate limiter,不是爬蟲。套過來:爬蟲的 false positive = 新 URL 被誤以為看過、這次沒爬到,和「少量誤判沒關係」是同一種取捨;多台 downloader 各一份、用 OR 合併,就是 089 的同步法。089 也說 bloom filter「has no expiration」,他每分鐘輪替、保留 30 個;爬蟲要定期重爬,會碰到同一個問題。

你猜猜看:原書說 URL Seen? 也可以用 hash table,把看過的網址全記下來。10 億個網址、每個約 100 bytes,原書這樣做會吃掉多少記憶體?

「Bloomfilter data structure — Constant memory usage … Test(string s) bool — may return false positive」「Little false positive doesn't matter」「Merge use bitwise OR operation on byte array — Allow super fast synchronization between application server」🗣️ Triton 本人說 089-redis-ratelimit.pdf.md · 談 rate limiter 的 active user

「我寫bloomfilter時,就直接在config內寫m = 1000003」🗣️ Triton 本人說 011 · 只引開頭 Triton 的短句

補充 · Triton 線Downloader 該開幾個 thread

Thread 數看 CPU 和 latency,不看有幾億個 URL

「你的 worker threads 數量,應該只跟 CPU core 數量有關,跟你的 tasks 的數量不應有關係」「江湖傳說:某「架構師」,在 4 core 機器上開了 5000 threads」🗣️ Triton 本人說 049-concurrency-demo.pdf.md · 智障架構

「最終版本:不準讓系統資源閒置浪費掉 – 即是說:要卡在系統的 io bandwidth 或 CPU 總效能」「更理想做法:把 blocking IO 的工作以獨立的 thread群來工作」🗣️ Triton 本人說 049 · 分析 100 個 log 檔的例子

「如果 consumer 跑慢了,buffer channel 滿掉後 producor 會被卡住 – 比起你系統OOM崩潰,你的系統跑慢一點不是壞事」🗣️ Triton 本人說 045-anti-patterns-in-go.pdf.md · Abuse of go-routine

你猜猜看:原書只說「每台 server 跑多個 thread」。如果照清單長度開 thread(1 億個網址就開 1 億個),會出什麼事?

文組翻譯

館員要請幾位,看「每抄一本有多少時間在等」和「辦公室有幾張桌子」(CPU core),不看清單有多長。清單再長,也是同一批館員慢慢抄。下一頁用計算機算。

白話:CPU core=電腦裡真正在算的「大腦」有幾顆;IO=讀寫磁碟或網路,大部分時間在等;latency=等多久才有回應(第 2 章簡報第 8 頁)。

補充 · Triton 線Downloader 該開幾個 thread · 動手算

用 049 的算法,算爬蟲要幾個 thread

這一步要解決的問題前一頁的原則,套到「每頁要等網路幾百 ms」的爬蟲,會算出多少?

🔭 推論 用 049 的算法算 downloader thread

🔭 推論 套回原書

  • 049 的公式:每個 thread 只有一部分時間吃 CPU,要用光 n 顆就開 n ÷ (CPU 時間占比) 個;他的例子是 Redis 2ms + CPU 10ms → 1.2n。爬蟲每頁要等網路幾百 ms,同一個算法會算出多很多。
  • 原書把 Content Parser 拆成獨立元件,和 049「blocking IO 獨立一群 thread」同方向;但 049 也說「別有過多的 stage」,每多一個 channel 就多一次複製。
  • 045 的另外兩個坑也在爬蟲裡:用 ioutil.ReadAll 把整頁讀進記憶體;拿無限生命期的 map 當 URL Seen?,delete 後記憶體不會還。

延伸基礎 · 複習第 13 階 · MQ懂的人可以跳過

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

做到一半當機:白板上的待辦,和看板上的待辦

① 先想像

白板:寫得快,拿走一張就擦掉,一停電字全消失。看板:每張先存進檔案櫃才說「收到」,師傅回報做完才撕掉。

你猜猜看:師傅從白板拿走一件待辦,做到一半當機。重開之後,這件事還有人會做嗎?

③ 這叫做 MQ、Redis

message queue(MQ):那塊看板(第 1 章簡報第 30 頁)。Redis:放在記憶體裡的共用白板(第 4 章簡報第 21 頁)。

④ 跟這章的關係

frontier 就是一張越排越長的待辦清單。下一頁看 Triton 怎麼說 Redis 當 queue。

② 動手玩:同樣的待辦,兩塊板子

補充 · Triton 線URL frontier 放哪

Frontier 是一條會一直變長的 queue:別放在 Redis

「Can you use redis to implement a priority task queue? – Sorted Set should be avoided at all cost – For fault tolerance appliation, you should use rabbitMQ instead」🗣️ Triton 本人說 089-redis-ratelimit.pdf.md · Extras

「redis的超高效能,是建基於「所有data都足夠放到RAM內」如果你的consumer消化速度追不上producer生產速度,你的redis很容易就會爆炸掉。rabbitmq / Kafka是使用HDD來存放buffer的。」🗣️ Triton 本人說 030-Redis 不能當 queue 原因.md · 第 3 點(另有斷電掉資料、單一資料結構只住一台的 hotspot)

「正常的MQ Server – 會把收到的Message先存到HDD,然後才回應成功 – 會等待收件者回傳「工作完成」,才真的把訊息刪掉」🗣️ Triton 本人說 078-mq-intro.pdf.md

你猜猜看:原書的 frontier 放記憶體 buffer+磁碟。如果整條 frontier 都放 Redis(全在記憶體),爬蟲又因為 politeness 故意放慢下載,會出什麼事?

🔭 推論 為什麼爬蟲特別中這一條

  • Politeness 就是故意讓 consumer 變慢:每個 host 一次一頁、中間還有 delay。新連結卻一直被發現,backlog 只會變長。原書自己也說幾億個 URL「全部放記憶體不耐久也無法擴展」,這點原書和 030 同一邊。
  • Front queues 就是 priority task queue,用 sorted set 做正是 089 說要避免的。
  • 原書的混合法是「buffer 定期寫磁碟」,當機會掉 buffer(第 31 頁的互動);078 的 MQ 是先寫磁碟才回成功、做完才刪。

補充 · Triton 線URL frontier 要不要上 Kafka

每秒 400 頁,要用 Kafka 嗎?

這一步要解決的問題決定了「放真正的 MQ」,那要選哪一種?先看流量到哪個等級。

🔭 推論 要不要上 Kafka?

🗣️ Triton 本人說「如果系統還沒到每秒1K Message的,kafka對你會是overkill。」138-喵談 rabbitMQ 和 kafka.md。原書沒給每頁有幾個新連結,請自己拉。

文組翻譯

待辦看板也分大小。Kafka 是給「每秒上千張待辦」的大工廠用的;每秒不到 1,000 張,Triton 說用它是殺雞用牛刀。拉左邊的滑桿:每頁抽出幾個新連結,決定了放進看板的速度。

白話:overkill=大材小用;msg/s=每秒幾則訊息;RabbitMQ、Kafka=兩套常見的 MQ 軟體。

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

  1. URL
  2. QPS
  3. queue
  4. DNS
  5. hash
  6. BFS / DFS
  7. thread
  8. politeness
  9. priority
  10. buffer
  11. robots.txt
  12. bloom filter
  13. MQ

到這裡你已經會了:Triton 的三個原則怎麼套進爬蟲

13 階全部走完了

下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。

一句話記住

爬蟲不難在「抓」,難在
排隊有禮貌、不重複、不掉進陷阱。

原書的骨架

  • seed → frontier → downloader → parser → 去重 → 抽連結 → filter → URL seen → frontier
  • BFS,但用 front queues 排優先、back queues 管禮貌
  • robots.txt 先看、cache 起來
  • DNS cache、短 timeout、分散就近

三種「不要」

  • 不要重複:content 比 hash、URL 用 bloom filter
  • 不要掉進陷阱:URL 長度上限、人工排除
  • 不要吵到別人:一個 host 一個 queue、一次一頁

🔭 Triton 原則套進來

  • 少量 false positive 沒關係,bloom filter 可以 OR 合併
  • thread 數由 CPU 和 latency 決定,不由 URL 數決定
  • 會一直變長的 queue 放真正的 MQ,不放 Redis

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

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

web crawler順著連結把網頁抓回來的程式,又叫 robot、spider
URL網頁的地址
HTML網頁的原稿;<a href> 是一條連結
seed URLs一開始給的那幾個起點網址
QPS每秒處理幾次;這章是每秒抓幾頁
TB、PB1 PB = 1,000 TB;五年的書庫要 30 PB
queue、FIFO排隊的清單;先排進來的先出去
URL Frontier待抄清單:存還沒下載的網址
HTML Downloader去書店把網頁抓回來的那一關
DNS、IP查號台;網路上的門牌號碼
Content Parser檢查抓回來的有沒有缺頁、亂碼
hash、fingerprint把內容壓成一小串號碼;拿來比對的指紋
Content Seen?「這份內容存過沒?」比 hash
URL Filter、URL Seen?擋掉圖片、壞連結、黑名單;「這個網址看過沒?」

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

引述來源與原書對照

Triton 本人的講義 / 文章(都不是講爬蟲)

  • 089-redis-ratelimit.pdf.md — High Volume Ratelimiting with Redis:bloomfilter 的 Add/Test/Merge、少量 false positive 沒關係、OR 合併同步、無 expiration 改用輪替;Extras:priority task queue 別用 sorted set、用 rabbitMQ
  • 011-…喵談_質數_bloomfilter.pdf.md — 只引開頭 Triton 的短句(m = 1000003);後面是 AI 生成段落,不引用
  • 049-concurrency-demo.pdf.md — 用光 IO 或 CPU、1.2n 的算法、worker 數只跟 CPU 有關、blocking IO 獨立 thread 群、別有過多的 stage
  • 045-anti-patterns-in-go.pdf.md — goroutine 濫用與 buffered channel 背壓、ReadAll、map as cache
  • 030-Redis 不能當 queue 原因.md、078-mq-intro.pdf.md、138-喵談 rabbitMQ 和 kafka.md — Redis 當 queue 的四個問題、MQ 先寫磁碟後 ack、<1K msg/s 用 Kafka 是 overkill
  • 106-喵 data.md — 只在備註中說明為何不套用

一個可以直接問自己的問題

你的爬蟲 frontier 現在排了多少個 URL?如果 worker 全部停一小時,它會長到多大、放在哪裡、斷電會掉多少?

原書對照

Alex Xu, System Design Interview Vol.1 Ch.9。開場與用途、Figure 1(第 6 頁)、Step 1 問答與特性(7)、估算(8)、高階設計 Figure 2(11)、元件(12–16,Figure 3 在 15)、Workflow Figure 4(17)、DFS vs BFS 與 Figure 5(20–23)、Politeness 與 Figure 6、Table 1(24)、Priority 與 Figure 7(26)、Figure 8(27–28)、Freshness 與 Storage(31)、Robots.txt(33)、Performance 與 Figure 9(34–35)、Robustness、Extensibility 與 Figure 10(36)、Problematic content(37)、Wrap up(38)。10 張圖都依原書圖說與 alt 描述重繪,不是原圖;Figure 3 的 alt 在擷取時被截斷,依原書 HTML 的完整 alt 重繪。原書參考資料:Mercator [4]、Olston & Najork [5]、Bloom 1970 [8]、PageRank [10]、IRLbot [14] 等。

循序漸進(文組版)的頁面

學習地圖(第 3 頁);延伸基礎 13 階:URL(5)、QPS(借第 2 章,8)、queue(9)、DNS(借第 1 章,12)、hash(13)、BFS / DFS(19)、thread(21)、politeness(22)、priority(25)、buffer(30)、robots.txt(32)、bloom filter(40)、MQ(複習第 1、4 章,44);小結(10、18、29、39、47);名詞小卡(49)。Triton 推論頁拆成 41、42–43、45–46。圖書館是虛構的示範情境;書號、館員人數、燈號規則等都是示意數字。

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