System Design Interview · 第 9 章Triton 覆蓋度:🟠 低Triton 線
Design A Web Crawler
把整個網路抄一遍,還不能吵到別人
原書這章是經典題:從幾個網址出發,下載、抽出連結、再下載,每月抓 10 億頁。難的不是演算法,而是排隊要有禮貌、不重複、不掉進陷阱。Triton 沒有寫過爬蟲的講義或文章,所以這份簡報以把原書講清楚為主,只在他的通用原則真的用得上的三個地方,加上標明 🔭 的推論卡。
給文組
全程用「圖書館員把全城的書抄一遍」比喻,一階一階爬 13 個概念,二十幾個可以動手玩的小互動。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。
給工程師
原書 10 張圖與 Table 1 全部依描述重繪成可播放的 SVG。最後一頁列出原書段落對照與出處檔案(materials/core)。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 📅 2026 補充
先用生活理解爬蟲在做什麼
圖書館員要把全城的書抄一份回館裡
待抄清單
剛抄完
書目: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 階。每一階只用前面講過的東西。
- 1URL書的地址
- 2QPS每秒抄幾本
- 3queue待抄清單
- 4DNS查號台
- 5hash內容的指紋
- 6BFS / DFS一層層 vs 一路鑽
- 7thread同時幾位館員
- 8politeness別擠爆同一家
- 9priority重要的先抄
- 10buffer桌上的小籃子
- 11robots.txt門口的告示
- 12bloom filter一排燈的記事板
- 13MQ不怕當機的待辦板
第 1–5 階 · 一本書怎麼被抄回來
要回答:原書的 11 個元件各做什麼?
第 6–9 階 · 清單照什麼順序抄
要回答:怎麼又快、又有禮貌、又先抄重要的?
第 10–11 階 · 放哪裡、守規矩
要回答:幾億行清單放哪?哪些書不准抄?
第 12–13 階 · Triton 的原則
要回答:記「看過沒」、放清單,有什麼坑?
全程只用一座圖書館(虛構):館員要把全城的書抄回館裡
每爬 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懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
每本書都有地址,書的最後還寫著別本書的地址
① 先想像
每本書貼著一張標籤:「B 書店,第 3 櫃」。照著標籤就找得到書。書最後的參考書目,寫的也是這種標籤。
你猜猜看:書 A 的書目寫了 B、C 兩本。館員抄完 A,手上有幾本「還沒抄的書」的地址?
只知道書目上的 B、C。其他書要等抄到 B、C,看它們的書目才知道。爬蟲就是這樣「順著連結」一路找下去。
③ 這叫做 URL、HTML
URL:網頁的地址。HTML:網頁的原稿;裡面的 <a href="…"> 就是一條連結(hyperlink)。
④ 跟這章的關係
爬蟲只做三件事:拿 URL 下載 HTML、從 HTML 找出新的 URL、再排隊下載。
② 動手玩:打開「書 A」這一頁
點一下底線的連結,看它的地址分成哪三段。
原書開場 · 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 年 |
| 內容重複的網頁怎麼處理? | 忽略 |
原書:這些只是範例問題。就算是爬蟲這種看似單純的產品,你和面試官的假設也可能不同。
📖 原書 基本演算法
- 給一組 URL,下載這些 URL 指向的網頁
- 從網頁裡抽出 URL
- 把新 URL 加進待下載清單,重複這三步
真的這麼簡單嗎?不完全是。要在面試時間內設計出超大型爬蟲幾乎不可能。
📖 原書 好爬蟲的四個特性
- Scalability:網頁有數十億,要靠平行化
- Robustness:壞掉的 HTML、不回應的 server、crash、惡意連結都很常見
- Politeness:短時間內不要對同一網站發太多 request
- Extensibility:之後要爬圖片,不該整個重新設計
白話:scalability=能靠加機器長大;平行化=很多台同時做;robustness=耐摔;politeness=有禮貌;extensibility=好擴充。
原書 Step 1Back of the envelope estimation
每月 10 億頁:每秒 400 頁、五年 30 PB
這一步要解決的問題每月 10 億頁:要抓多快?倉庫要多大?
📖 原書 這些估算建立在很多假設上,要和面試官溝通、取得共識:
- 每月下載 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懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
待抄清單:新發現的寫在最後,每次從最前面拿
① 先想像
館員把要抄的書寫在一張長紙條上。新發現的寫在最下面,每次從最上面拿一本來抄。跟郵局抽號碼牌一樣。
你猜猜看:紙條上依序是 B、C。抄 B 的時候又發現 D。下一本抄哪一本?
B 抄完就劃掉了。D 寫在 C 的後面,先來先抄,所以是 C。
③ 這叫做 queue、FIFO
queue:排隊的清單。FIFO(first in, first out):先排進來的先出去。
④ 跟這章的關係
原書說:放待下載網址的 URL Frontier,可以先想成一條 FIFO queue。
② 動手玩:一張待抄紙條
到這裡你已經會了小結 1 / 5
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
到這裡你已經會了:爬蟲要抄什麼、抄多少、怎麼排隊
- 網頁的地址叫 URL,內容原稿是 HTML,裡面的連結指向別的 URL。
- 原書的規模:每月 10 億頁,約每秒 400 頁(QPS),五年存 30 PB。
- 待抄清單是一條 queue:新的排最後,從最前面拿(FIFO)。
下一階要解決的問題
下載、檢查、去重、抽連結,原書怎麼把它們接成一條會繞圈的生產線?
原書 Step 2High-level design · Figure 2
一條環狀的生產線:下載、解析、去重、抽連結、再排隊
這一步要解決的問題前面那三步演算法,實際上要拆成哪些元件、怎麼接?
原書 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懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- 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 櫃」),怎麼補成完整地址?
📖 原書 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 個元件,一個網址實際走一圈是什麼順序?
- seed URLs 加進 URL Frontier
- HTML Downloader 從 Frontier 拿一批 URL
- 向 DNS resolver 拿 IP,開始下載
- Content Parser 解析、檢查是否格式錯誤
- 解析驗證後交給 Content Seen?
- 檢查這個 HTML 是否已在 storage
- Link Extractor 抽出連結
- 連結交給 URL Filter
- 過濾後交給 URL Seen?
- 檢查 URL 是否已在 storage;在就不用做事
- 沒處理過的 URL 加進 URL Frontier
到這裡你已經會了小結 2 / 5
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
到這裡你已經會了:原書的生產線繞一圈
- 下載前先問查號台(DNS)拿到書店的門牌號碼(IP)。
- 內容比 hash(指紋)就知道重複,不逐字比;網址也要查「看過沒」(URL Seen?)。
- 11 個元件繞成一圈:Frontier → 下載 → 解析 → 去重 → 抽連結 → 過濾 → 回 Frontier。
下一階要解決的問題
清單上有幾億個網址,要照什麼順序抄?先往深處鑽,還是一層一層來?
延伸基礎第 6 階 · BFS / DFS懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
先把同一層的書抄完,還是一路往下追?
① 先想像
A 的書目有 B、C;B 的書目有 D、E;C 的書目有 F、G。館員可以先抄完 B、C 再往下,也可以抄完 B 就馬上追 D。
你猜猜看:從 A 開始一層一層抄,第三本抄的是?
順序是 A、B、C、D…:A 書目上的 B、C 是同一層,要先抄完。一路往下追的話,第三本會是 D。
③ 這叫做 BFS、DFS
BFS:一層一層走,用上一階的 queue。DFS:一路追到底再回頭,像疊盤子,後放的先拿。
④ 跟這章的關係
網路可以深到沒有底。原書說:爬蟲用 BFS(下一頁)。
② 動手玩:同一棵書目樹,兩種抄法
原書 Step 3Deep dive · DFS vs BFS
網路是一張有向圖:先往深處鑽,還是一層一層掃?
這一步要解決的問題網路是一張網,清單要照什麼順序走?
📖 原書 把網路想成有向圖:網頁是節點,超連結是邊。爬取就是在這張圖上走訪。常見的兩種走法是 DFS 和 BFS。
📖 原書 DFS 通常不是好選擇,因為深度可能非常深。BFS 是爬蟲常用的,用 FIFO queue 實作:URL 照加入的順序被取出。
文組翻譯
DFS 像讀維基百科「點下一個連結」點到凌晨三點,越陷越深,同一個主題的旁支全沒看。BFS 像先把每家書店的首頁翻一遍,再一層一層往下。
但 BFS 也有兩個問題,後兩頁講。
延伸基礎第 7 階 · thread懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
一位館員抄 6 本要 6 小時,請 3 位呢?
① 先想像
抄一本要 1 小時:走路去書店、等店員拿書花 50 分鐘,真正動筆只有 10 分鐘。多請幾位館員同時出門。
你猜猜看:6 本書、3 位館員同時出門,全部抄完要多久?
6 本分給 3 人,每人 2 本 × 1 小時 = 2 小時。時間大多花在「等」,所以人多就快。
③ 這叫做 thread、worker
thread:電腦裡同時進行的一條工作線,就是一位館員。worker:專門負責某件事(例如下載)的那幾條 thread。
④ 跟這章的關係
原書的 HTML Downloader 用很多 thread 平行下載。可是大家都擠進同一家書店呢?下一頁。
② 動手玩:館員人數
延伸基礎第 8 階 · politeness懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
同一家書店,一次衝進去 3 位館員
① 先想像
小書店只有一位店員幫忙拿書。館員一次衝進去好幾位,店員忙不過來,真正的客人也買不到書。
你猜猜看:清單前 6 本都在百科書店,有 3 位館員。怎麼抄最不吵到店家?
百科書店一次只有一位館員,店員應付得來;另外兩位去抄別家的書,總速度沒有變慢。
③ 這叫做 host、politeness
host:網站所在的那台主機,就是「哪一家書店」。politeness:同一個 host 一次只抓一頁,中間還休息一下。
④ 跟這章的關係
原書說 BFS 的第一個問題就是不禮貌,解法是「一個 host 一條 queue」(後兩頁)。
② 動手玩:館員怎麼派
原書 Step 3BFS 的兩個問題 · Figure 5
BFS 的問題:一窩蜂打同一個網站,而且不分輕重
這一步要解決的問題照 BFS 的順序一路抄下去,會出什麼問題?
📖 原書 問題 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 的對應。
| Host | Queue |
|---|---|
| wikipedia.com | b1 |
| apple.com | b2 |
| … | … |
| nike.com | bn |
📖 原書 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
延伸基礎第 9 階 · priority懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
市政府公告和路邊傳單,哪個先抄?
① 先想像
館員時間有限,重要的書要先抄。可是傳單也不能永遠不抄。做法:抽籤箱裡,重要的書放 3 張籤,普通的放 1 張。
你猜猜看:抽 4 次,重要的大約被抽中幾次?
重要的佔 4 張籤裡的 3 張,所以大約 3 次;普通的大約 1 次,不會完全輪不到。
③ 這叫做 priority、PageRank
priority:優先權,越高越常被選到。PageRank:Google 用「被多少重要網頁連到」來算網頁有多重要。
④ 跟這章的關係
原書的 front queues 就是好幾個抽籤箱,偏心地抽(下一頁 Figure 7)。
② 動手玩:每分鐘來 1 本重要、1 本普通,館員每分鐘抄 1 本
原書 Step 3URL frontier · Priority · Figure 7
Apple 首頁比論壇的隨便一篇文重要:先爬它
這一步要解決的問題重要的網頁先爬,又不讓其他網頁永遠輪不到,怎麼做?
📖 原書 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?
原書 Step 3 · 動手玩URL frontier 模擬器
一步一步看:URL 怎麼穿過兩層 queue
這一步要解決的問題兩層 queue 一起跑起來,實際長什麼樣?
看點 1:Apple 首頁(★)在 f1,很快就被偏心的 front selector 選中、下載。
看點 2:b1 排了一堆 wikipedia,Worker 1 也只能每隔「delay + 1」秒下載一頁:politeness。
看點 3:把 delay 拉到 0,wikipedia 每秒都被打;拉到 4,全部下載完要很久。禮貌是用時間換的。
到這裡你已經會了小結 3 / 5
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
到這裡你已經會了:清單照什麼順序抄
- BFS 一層一層、DFS 一路鑽到底;網路深不見底,爬蟲用 BFS。
- 很多 thread 一起下載,但同一個 host 一次一頁(politeness):一個 host 一條 back queue。
- 重要的先抄、但不讓別人餓死(priority):front queues 偏心地抽。
下一階要解決的問題
清單有幾億行,放在哪裡才不會塞爆、也不怕當機?哪些書,書店根本不准抄?
延伸基礎第 10 階 · buffer懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
新發現的書,先放桌上的小籃子,滿了再搬去倉庫
① 先想像
桌上拿東西快,但很小,打翻咖啡就全毀。倉庫又大又安全,但走一趟要很久。所以先在桌上湊一籃,再一起搬。
你猜猜看:籃子滿 10 張才搬一次。籃子裡有 7 張時打翻咖啡,會毀掉幾張?
倉庫裡的都還在,只有還沒搬的那 7 張毀了。籃子越大,走的趟數越少,但一次可能毀掉的也越多。
③ 這叫做 buffer
buffer:先暫放、湊滿一批再處理的小籃子。桌上 = 記憶體,倉庫 = 磁碟(第 2 章簡報第 12 頁)。
④ 跟這章的關係
原書:frontier 大部分放磁碟,記憶體留 buffer,定期寫進磁碟(下一頁)。
② 動手玩:籃子要多大?
原書 Step 3Freshness · Storage for URL Frontier
舊頁要重爬;幾億個 URL 要放哪
這一步要解決的問題網頁會改,清單有幾億行:什麼時候重爬?清單放哪?
📖 原書 Freshness
網頁不斷被新增、刪除、編輯,爬蟲要定期重爬已下載的頁面。全部重爬又耗時又耗資源,原書的策略:
- 依網頁的更新歷史決定何時重爬
- 排優先順序,重要頁面先爬、爬得更勤
📖 原書 Storage for URL Frontier
真實的搜尋引擎爬取,frontier 裡的 URL 可能有數億個 [4]。全部放記憶體不耐久也無法擴展;全部放磁碟又太慢,會變成瓶頸。
原書採混合做法:大部分 URL 存磁碟,空間不是問題;記憶體裡維護 enqueue / dequeue 的 buffer,buffer 的資料定期寫到磁碟。
動手試:記憶體 buffer + 磁碟
延伸基礎第 11 階 · robots.txt懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
書店門口貼著:「館員請勿進入倉庫和休息室」
① 先想像
每家書店門口有一張告示,寫哪些地方不准抄。守規矩的館員進門前先看。告示很少改,抄一份帶在身上就好。
你猜猜看:館員一天進同一家書店 1,000 次。早上抄一份告示帶著,一天要走到門口看告示幾次?
早上看一次、抄下來,一整天都看自己的小抄,省下 999 次。隔天再重新抄一次,告示改了也跟得上。
③ 這叫做 robots.txt、cache
robots.txt:網站放在固定位置的告示檔,寫爬蟲不能抓哪些路徑。cache:隨身小抄(第 1 章簡報第 18 頁)。
④ 跟這章的關係
原書:下載前先看 robots.txt,並且 cache 起來(下一頁)。查 DNS 也是同一招。
② 動手玩:百科書店的告示
原書 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 負責其中一部分。
文組翻譯:分店遍佈各區(分散、就近);書店地址抄在小本子上不用每次打 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 很慢,而且一次只能一個人查,怎麼辦?
📖 原書 許多 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:監控網路,防止版權與商標侵權
原書 Step 3Detect and avoid problematic content
重複、陷阱、雜訊:三種不該抓回來的東西
這一步要解決的問題有些網頁會把爬蟲困住、有些根本不值得存:怎麼避開?
動手試:Spider trap
📖 原書 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
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
到這裡你已經會了:原書整章
- frontier 大部分放磁碟,記憶體當 buffer;代價是當機時會掉一小批。
- 進門先看 robots.txt,抄一份 cache 起來;DNS 也 cache,再加上分散、就近、短 timeout。
- 還要防陷阱(spider trap)、能接著跑(robustness)、能插新模組(extensibility)。
下一階要解決的問題
Triton 沒有寫過爬蟲。但「記住看過沒」、「開幾位館員」、「清單放哪」這三件事,他在別的題目講過原則。
延伸基礎第 12 階 · bloom filter懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- 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,原書這樣做會吃掉多少記憶體?
10 億 × 100 bytes = 1,000 億 bytes ≈ 100 GB,一台機器很吃緊。bloom filter 約 1.2 GB(左邊的計算機),代價是少量誤判。
「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 億個),會出什麼事?
每個 thread 都要佔記憶體,CPU 也要在它們之間來回切換。thread 數該看什麼,左邊是 Triton 在別的題目講的原則。
文組翻譯
館員要請幾位,看「每抄一本有多少時間在等」和「辦公室有幾張桌子」(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懂的人可以跳過
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- 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 故意放慢下載,會出什麼事?
新連結一直進來,下載卻故意放慢,清單只會變長。全放記憶體,遲早塞爆(左邊 030 的原話)。
🔭 推論 為什麼爬蟲特別中這一條
- 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
- URL
- QPS
- queue
- DNS
- hash
- BFS / DFS
- thread
- politeness
- priority
- buffer
- robots.txt
- bloom filter
- MQ
到這裡你已經會了:Triton 的三個原則怎麼套進爬蟲
- bloom filter 只會說「一定沒看過」或「可能看過」;少量誤判沒關係,還能 OR 合併。
- thread 數看 CPU 和等待時間,不看 frontier 裡有幾億個 URL。
- 會一直變長的 queue,放真正的 MQ,不放 Redis。
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
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
<a href> 是一條連結給工程師的重點出處與標籤
引述來源與原書對照
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。圖書館是虛構的示範情境;書號、館員人數、燈號規則等都是示意數字。