在本章中，我們專注於網路爬蟲（web crawler）設計：一個有趣且經典的系統設計面試題。

網路爬蟲又稱為機器人（robot）或蜘蛛（spider）。它被搜尋引擎廣泛使用以發現網路上新增或更新的內容。內容可以是網頁、圖片、影片、PDF 檔等。網路爬蟲先收集少數幾個網頁，再依循這些網頁上的連結收集新的內容。圖 1 顯示爬取流程的視覺範例。

爬蟲有多種用途：

• 搜尋引擎索引（Search engine indexing）：這是最常見的使用案例。爬蟲收集網頁以建立搜尋引擎的本地索引。例如，Googlebot 是 Google 搜尋引擎背後的網路爬蟲。
• 網頁封存（Web archiving）：這是從網路上收集資訊以保存資料供未來使用的過程。例如，許多國家圖書館執行爬蟲來封存網站，著名的例子有美國國會圖書館 [1] 與歐盟網路檔案 [2]。
• 網頁探勘（Web mining）：網路的爆炸性成長為資料探勘提供了前所未有的機會。網頁探勘有助於從網際網路發掘有用的知識。例如，頂尖金融公司使用爬蟲下載股東會議與年度報告，以了解公司的關鍵舉措。
• 網頁監控（Web monitoring）：爬蟲能幫助監控網際網路上的版權與商標侵權行為。例如，Digimarc [3] 利用爬蟲發現盜版作品並提交報告。

開發網路爬蟲的複雜度取決於我們打算支援的規模。它可以是只需要幾小時就能完成的小型學校專案，也可以是需要專屬工程團隊持續改進的龐大專案。因此，我們將在下方探討要支援的規模與功能。

Step 1 - 理解問題並確立設計範圍#

網路爬蟲的基本演算法很簡單：

1. 給定一組 URL，下載這些 URL 所指向的所有網頁。
2. 從這些網頁中擷取 URL。
3. 將新 URL 加入待下載 URL 清單。重複以上 3 個步驟。

網路爬蟲真的就像這個基本演算法那樣簡單嗎？並非如此。設計一個高度可擴展的網路爬蟲是極其複雜的任務。沒有人能夠在面試時間內完成大型網路爬蟲的設計。

在開始設計之前，我們必須提出問題以理解需求並確立設計範圍：

應徵者：爬蟲的主要用途是什麼？是用於搜尋引擎索引、資料探勘，還是其他用途？

面試官：搜尋引擎索引。

應徵者：爬蟲每月收集多少網頁？

面試官：10 億頁。

應徵者：包含哪些內容類型？只有 HTML，還是也包含 PDF 與圖片等其他內容類型？

面試官：只有 HTML。

應徵者：我們是否需要考慮新增或編輯過的網頁？

面試官：是的，我們應該考慮新增或編輯過的網頁。

應徵者：我們是否需要儲存從網路爬取的 HTML 頁面？

面試官：是的，最多保存 5 年。

應徵者：我們如何處理內容重複的網頁？

面試官：內容重複的頁面應該被忽略。

以上是一些可以詢問面試官的範例問題。理解需求並釐清模糊之處非常重要。即使你被要求設計像網路爬蟲這樣看似簡單的產品，你和面試官也可能持有不同的假設。

除了與面試官釐清功能之外，記下一個良好網路爬蟲應有的下列特性也很重要：

• 可擴展性（Scalability）：網路非常龐大。網路上有數十億個網頁。網路爬取應透過平行化達到極高的效率。
• 強健性（Robustness）：網路充滿陷阱。錯誤的 HTML、無回應的伺服器、當機、惡意連結等都很常見。爬蟲必須處理所有這些邊界情況。
• 禮貌性（Politeness）：爬蟲不應在短時間內對某網站發送過多請求。
• 可擴充性（Extensibility）：系統具備彈性，只需最小變更即可支援新內容類型。例如，未來想爬取圖檔時，不應該需要重新設計整個系統。

粗略估算#

以下估算基於許多假設，與面試官溝通以對齊認知很重要。

• 假設每月下載 10 億個網頁
• QPS：1,000,000,000 / 30 天 / 24 小時 / 3600 秒 = 約每秒 400 頁
• 尖峰 QPS = 2 * QPS = 800
• 假設網頁平均大小為 500k
• 每月儲存空間：10 億頁 x 500k = 每月 500 TB。如果你不清楚數位儲存單位，請再讀一遍「Back-of-the-envelope Estimation」章節中的「2 的次方」一節
• 五年儲存需求：假設資料保存五年，500 TB * 12 個月 * 5 年 = 30 PB

Step 2 - 提出高階設計並取得認可#

需求釐清後，我們就進入高階設計。受先前對網路爬取的研究 [4][5] 啟發，我們提出如圖 2 所示的高階設計。

首先，我們會探討每個設計元件以了解其功能。然後再逐步檢視爬蟲的工作流程。

Seed URLs（種子 URL）#

網路爬蟲使用種子 URL 作為爬取流程的起點。例如，要爬取某大學網站的所有網頁，一個直覺的種子 URL 選擇方式是使用該大學的網域名稱。

要爬取整個網路，我們在挑選種子 URL 時需要有創意。一個好的種子 URL 是一個良好的起點，能讓爬蟲遍歷盡可能多的連結。一般策略是把整個 URL 空間切分為較小的部分：

• 地區性：第一種提出的方法是基於地區性，因為不同國家可能有不同的熱門網站。
• 主題性：另一種方式是依主題挑選種子 URL；例如，可以將 URL 空間切分為購物、運動、醫療等等。

種子 URL 的選擇是個開放性問題。你不必給出完美的答案，只要把想法說出來即可。

URL Frontier#

大多數現代網路爬蟲將爬取狀態切為兩部分：待下載與已下載。儲存待下載 URL 的元件稱為 URL Frontier。你可以將其視為一個先進先出（FIFO）佇列。關於 URL Frontier 的詳細資訊請參考深入探討。

HTML Downloader（HTML 下載器）#

HTML 下載器從網際網路下載網頁。這些 URL 由 URL Frontier 提供。

DNS Resolver（DNS 解析器）#

要下載網頁，URL 必須先被翻譯成 IP 位址。HTML Downloader 呼叫 DNS Resolver 以取得對應 URL 的 IP 位址。例如，URL www.wikipedia.org 在 2019/3/5 時被轉換成 IP 位址 198.35.26.96。

Content Parser（內容剖析器）#

下載網頁後，必須對其進行剖析與驗證，因為格式錯誤的網頁可能引發問題並浪費儲存空間。在爬取伺服器內實作 content parser 會拖慢爬取流程，因此 content parser 是獨立的元件。

Content Seen?（內容看過？）#

線上研究 [6] 顯示，網路上 29% 的網頁是重複內容，這可能導致相同內容被儲存多次。我們引入「Content Seen?」資料結構以消除資料冗餘並縮短處理時間。它有助於偵測先前已儲存於系統中的內容。

要比較兩份 HTML 文件，我們可以逐字元比對。然而這種方法在涉及數十億網頁時非常緩慢且耗時。一個有效的做法是比對兩個網頁的 hash 值 [7]。

Content Storage（內容儲存）#

這是一個用來儲存 HTML 內容的儲存系統。儲存系統的選擇取決於資料類型、資料大小、存取頻率、生命週期等因素。同時使用磁碟與記憶體：

• 大部分內容儲存在磁碟上，因為資料集太大無法全部放入記憶體。
• 熱門內容保存在記憶體中以降低延遲。

URL Extractor（URL 擷取器）#

URL Extractor 從 HTML 頁面中剖析並擷取連結。圖 3 顯示連結擷取流程的範例。相對路徑會藉由加上 “https://en.wikipedia.org” 前綴轉換為絕對 URL。

URL Filter（URL 過濾器）#

URL filter 排除特定內容類型、檔案副檔名、錯誤連結，以及在「黑名單」站點中的 URL。

URL Seen?（URL 看過？）#

「URL Seen?」是一個資料結構，用來追蹤之前已被造訪或已在 Frontier 中的 URL。

「URL Seen?」可避免將相同 URL 多次加入，否則會增加伺服器負載並可能導致無窮迴圈。

Bloom filter 與 hash table 是實作「URL Seen?」元件的常見技術。我們不會在此涵蓋 bloom filter 與 hash table 的詳細實作。更多資訊請參考參考資料 [4][8]。

URL Storage（URL 儲存）#

URL Storage 儲存已造訪過的 URL。

到目前為止，我們已經討論過每個系統元件。接下來我們會將它們組合起來說明工作流程。

網路爬蟲工作流程#

為了更好地逐步說明流程，在設計圖中加入了序號，如圖 4 所示。

• 步驟 1：將種子 URL 加入 URL Frontier。
• 步驟 2：HTML Downloader 從 URL Frontier 取得一份 URL 清單。
• 步驟 3：HTML Downloader 從 DNS resolver 取得這些 URL 的 IP 位址並開始下載。
• 步驟 4：Content Parser 剖析 HTML 頁面並檢查頁面是否格式錯誤。
• 步驟 5：內容剖析並驗證後，傳給「Content Seen?」元件。
• 步驟 6：「Content Seen」元件檢查 HTML 頁面是否已在儲存中。
  • 如果在儲存中，表示相同內容已在不同 URL 下被處理過。在此情況下，丟棄該 HTML 頁面。
  • 如果不在儲存中，表示系統之前未處理過相同內容。內容會被傳到 Link Extractor。
• 步驟 7：Link Extractor 從 HTML 頁面中擷取連結。
• 步驟 8：擷取出的連結傳到 URL filter。
• 步驟 9：連結被過濾後傳到「URL Seen?」元件。
• 步驟 10：「URL Seen」元件檢查 URL 是否已在儲存中，若是表示之前已處理過，無需再做任何處理。
• 步驟 11：如果某個 URL 之前未被處理過，就把它加入 URL Frontier。

Step 3 - 設計深入探討#

到目前為止，我們已經討論過高階設計。接下來我們會深入討論最重要的構成元件與技術：

• 深度優先搜尋（DFS）vs. 廣度優先搜尋（BFS）
• URL frontier
• HTML Downloader
• 強健性
• 可擴充性
• 偵測並避免有問題的內容

DFS vs BFS#

你可以把網路想成一個有向圖，網頁是節點，超連結（URL）是邊。爬取流程可被視為從一個網頁遍歷到其他網頁的有向圖走訪。兩種常見的圖走訪演算法是 DFS 與 BFS。

DFS 通常不是好選擇，因為 DFS 的深度可能非常深。

BFS 常被網路爬蟲使用，並以先進先出（FIFO）佇列實作。在 FIFO 佇列中，URL 依入列順序出列。然而，這種實作有兩個問題：

• 同 host 密集連結：同一網頁的大多數連結會連回相同 host。在圖 5 中，wikipedia.com 的所有連結都是內部連結，使爬蟲忙於處理相同 host（wikipedia.com）的 URL。當爬蟲嘗試平行下載網頁時，Wikipedia 伺服器將被請求灌爆。這被視為「不禮貌」。

• 無優先順序：標準 BFS 並未考慮 URL 的優先順序。網路非常龐大，並非每個頁面都有相同的品質與重要性。因此，我們可能想根據網頁排名（PageRank）、網路流量、更新頻率等對 URL 排優先序。

URL frontier#

URL frontier 有助於解決這些問題。URL frontier 是一個儲存待下載 URL 的資料結構。URL frontier 是確保禮貌性、URL 優先順序與新鮮度的重要元件。一些值得注意的關於 URL frontier 的論文列在參考資料 [5][9]。這些論文的發現如下：

禮貌性（Politeness）#

一般來說，網路爬蟲應避免在短時間內對同一 hosting server 發送過多請求。發送過多請求會被視為「不禮貌」，甚至被視為阻斷服務（denial-of-service, DOS）攻擊。

例如，沒有任何限制下，爬蟲可以每秒向同一個網站發送數千個請求。這會壓垮網頁伺服器。

實施禮貌性的一般概念是同一時間從同一 host 只下載一頁。可以在兩個下載任務之間加入延遲。禮貌性限制是透過維持一個從網站 hostname 到下載（worker）執行緒的對應來實作。每個下載執行緒都有獨立的 FIFO 佇列，並只下載從該佇列取得的 URL。圖 6 顯示管理禮貌性的設計。

• Queue router：確保每個佇列（b1、b2、… bn）只包含來自相同 host 的 URL。

• Mapping table：將每個 host 對應到一個佇列。

  Host	Queue
  wikipedia.com	b1
  apple.com	b2
  …	…
  nike.com	bn

  表 1

• FIFO 佇列 b1、b2 到 bn：每個佇列包含來自相同 host 的 URL。

• Queue selector：每個 worker thread 對應到一個 FIFO 佇列，且只從該佇列下載 URL。佇列選擇邏輯由 Queue selector 處理。

• Worker thread 1 到 N：worker thread 從同一 host 一個一個地下載網頁。可在兩個下載任務之間加入延遲。

優先順序（Priority）#

來自討論論壇關於 Apple 產品的隨機貼文，與 Apple 首頁上的貼文有非常不同的份量。即使兩者都包含「Apple」這個關鍵字，爬蟲先爬取 Apple 首頁是合理的。

我們依據實用性對 URL 排優先序，實用性可由 PageRank [10]、網站流量、更新頻率等衡量。「Prioritizer」是處理 URL 優先順序的元件。關於此概念的深入資訊請參考參考資料 [5][10]。

圖 7 顯示管理 URL 優先順序的設計。

• Prioritizer：以 URL 為輸入並計算優先順序。
• Queue f1 到 fn：每個佇列被指派一個優先順序。較高優先順序的佇列被選中的機率較高。
• Queue selector：隨機選擇一個佇列，但偏好較高優先順序的佇列。

圖 8 呈現 URL frontier 的設計，包含兩個模組：

• Front queues：管理優先順序
• Back queues：管理禮貌性

新鮮度（Freshness）#

網頁不斷地新增、刪除與編輯。網路爬蟲必須定期重新爬取已下載的頁面，以保持資料集的新鮮度。重新爬取所有 URL 既費時又耗資源。一些優化新鮮度的策略列舉如下：

• 根據網頁的更新歷史重新爬取。
• 對 URL 排優先序，並更頻繁地優先重新爬取重要頁面。

URL Frontier 的儲存#

在搜尋引擎的真實世界爬取中，frontier 中的 URL 數量可能達數億 [4]。將所有東西放進記憶體既不持久也無法擴展。把所有東西都放在磁碟上也並不理想，因為磁碟很慢，且容易成為爬取的瓶頸。

我們採用混合方法。大多數 URL 儲存在磁碟上，因此儲存空間不是問題。為了降低從磁碟讀取與寫入的成本，我們在記憶體中維持入列／出列操作的緩衝區。緩衝區中的資料會定期寫入磁碟。

HTML Downloader#

HTML Downloader 使用 HTTP 協定從網際網路下載網頁。在討論 HTML Downloader 之前，我們先看看 Robots Exclusion Protocol。

Robots.txt#

Robots.txt 又稱為 Robots Exclusion Protocol，是網站用來與爬蟲溝通的標準。它指定了爬蟲被允許下載哪些頁面。在嘗試爬取某網站之前，爬蟲應該先檢查其對應的 robots.txt 並遵循其規則。

為避免重複下載 robots.txt 檔，我們會將檔案結果快取。檔案會被定期下載並存到快取中。以下是一段取自 https://www.amazon.com/robots.txt 的 robots.txt 內容。Google bot 被禁止存取像 creatorhub 等部分目錄。

User-agent: Googlebot
Disallow: /creatorhub/\*
Disallow: /rss/people/\*/reviews
Disallow: /gp/pdp/rss/\*/reviews
Disallow: /gp/cdp/member-reviews/
Disallow: /gp/aw/cr/

除了 robots.txt 之外，效能優化是 HTML downloader 另一個重要概念。

效能優化#

以下是 HTML downloader 的效能優化清單。

1. 分散式爬取（Distributed crawl）

為了達到高效能，爬取任務被分散到多台伺服器，每台伺服器執行多個執行緒。URL 空間被切成較小的部分，因此每個下載器只負責 URL 的一個子集。圖 9 顯示分散式爬取的範例。

2. 快取 DNS Resolver

DNS Resolver 是爬蟲的瓶頸，因為許多 DNS 介面是同步的，DNS 請求可能耗時。DNS 回應時間範圍從 10ms 到 200ms。一旦某個 crawler thread 對 DNS 發出請求，其他 thread 在第一個請求完成前都會被阻塞。

維持自有的 DNS 快取以避免頻繁呼叫 DNS，是有效的速度優化技術。我們的 DNS 快取保留網域名稱到 IP 位址的對應，並由 cron job 定期更新。

3. 地區性（Locality）

將爬取伺服器在地理上分散部署。當爬取伺服器距離網站 host 較近時，爬蟲會體驗到較快的下載時間。設計地區性適用於大部分系統元件：爬取伺服器、快取、佇列、儲存等。

4. 短逾時（Short timeout）

部分網頁伺服器回應緩慢或可能完全沒有回應。為避免長時間等待，會指定一個最大等待時間。如果某 host 在預定時間內沒有回應，爬蟲會停止該任務並爬取其他頁面。

強健性#

除效能優化外，強健性也是重要的考量。我們提出幾種改善系統強健性的方式：

• 一致性雜湊（Consistent hashing）：這有助於在下載器之間分散負載。可使用一致性雜湊新增或移除下載器伺服器。詳情請參考「Design consistent hashing」章節。
• 儲存爬取狀態與資料：為防止失敗，爬取狀態與資料會寫入儲存系統。被中斷的爬取可以透過載入儲存的狀態與資料輕易重新啟動。
• 例外處理：在大規模系統中，錯誤是不可避免且常見的。爬蟲必須優雅地處理例外，避免讓系統當機。
• 資料驗證：這是預防系統錯誤的重要措施。

可擴充性#

幾乎每個系統都會演進，其中一個設計目標是讓系統有足夠的彈性去支援新的內容類型。爬蟲可以透過插入新模組來擴充。圖 10 顯示如何加入新模組。

• PNG Downloader 模組被插入用以下載 PNG 檔。
• Web Monitor 模組被加入以監控網路並防止版權與商標侵權。

偵測並避免有問題的內容#

本節討論如何偵測與防止冗餘、無意義或有害的內容。

1. 冗餘內容

如先前所述，網路上將近 30% 的網頁是重複的。Hash 或 checksum 有助於偵測重複 [11]。

2. 蜘蛛陷阱（Spider traps）

蜘蛛陷阱是一個會讓爬蟲陷入無窮迴圈的網頁。例如，無限深的目錄結構如下：http://www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/...

這類蜘蛛陷阱可以藉由設定 URL 的最大長度來避免。然而，沒有一種通用方法能偵測所有蜘蛛陷阱。包含蜘蛛陷阱的網站通常容易識別，因為這類網站上發現的網頁數量異常龐大。要開發自動演算法去避免蜘蛛陷阱很困難，但使用者可以手動驗證並識別蜘蛛陷阱，然後將那些網站從爬蟲中排除，或套用一些自訂的 URL 過濾器。

3. 雜訊資料（Data noise）

某些內容幾乎沒有價值，例如廣告、程式碼片段、垃圾 URL 等。這些內容對爬蟲沒有用處，應盡可能將其排除。

Step 4 - 總結#

在本章中，我們先討論了一個良好爬蟲應有的特性：可擴展性、禮貌性、可擴充性與強健性。然後我們提出設計並討論關鍵元件。建立一個可擴展的網路爬蟲並不簡單，因為網路極其龐大且充滿陷阱。即使我們已經涵蓋許多主題，仍然遺漏了許多相關的討論點：

• 伺服器端渲染（Server-side rendering）：許多網站使用 JavaScript、AJAX 等腳本動態產生連結。如果我們直接下載並剖析網頁，將無法取得動態產生的連結。要解決此問題，我們在剖析頁面前先執行伺服器端渲染（也稱為動態渲染）[12]。
• 過濾不需要的頁面：在儲存容量與爬取資源有限的情況下，反垃圾元件有助於過濾低品質與垃圾頁面 [13][14]。
• 資料庫複寫與分片：複寫與分片等技術用來提升資料層的可用性、擴展性與可靠性。
• 水平擴展：對於大規模爬取，需要數百甚至數千台伺服器來執行下載任務。關鍵是讓伺服器保持無狀態。
• 可用性、一致性與可靠性：這些概念是任何大型系統成功的核心。
• 分析（Analytics）：收集與分析資料是任何系統的重要部分，因為資料是調校的關鍵原料。

恭喜你看到這裡！現在給自己一個鼓勵。做得好！