# 內行人才知道的系統設計面試指南 - CH 9 設計網路爬蟲

## 爬蟲用途
- 搜尋引擎索引編製
- google 搜尋引擎使用 googlebot 爬蟲, [Googlebot 簡介 | Google 搜尋中心  |  Documentation  |  Google for Developers](https://developers.google.com/search/docs/crawling-indexing/googlebot?hl=zh-tw)
- 網路內容歸檔，保存網路資料備用
- 美國國會圖書館、歐盟網路封存服務
- 網路探勘 (web mining)
- 找出可能有用的資料，如金融投資公司會抓各公司股東會議與年度報告
- 網路監控
- 監視版權與商標侵權的情況，如 Digimarc

## 爬蟲特性
- 基本流程
- 給定一組網址，把網址對應的網頁下載下來
- 從這些網頁抓出所有網址
- 添加網址到下載列表中，重複以上步驟
- 需考慮的特性
- 可擴展性
- 可透過平行化的方式，增加 worker 數量，來提高爬蟲速度
- 禮貌性
- 避免在短時間內，向同一主機發送過多的請求 (沒限制一秒可以發出幾千個)
- 一次只從同一主機下載一個頁面，甚至加入延遲間隔
- 每個Host一個Queue，從不同Queue取出要爬的網址
- 優先順序
- 不同內容會有不同的權重，可以根據實用性來判斷，可以透過 PageRank、網站流量、更新頻率等數值來衡量
- 內容新鮮度
- 更新歷史紀錄
- 針對優先序較高且頻繁更新的網頁做頻繁的重新讀取
- 可延伸性
- 可以透過插入模組的方式支援不同的資料格式
- 穩健性
- 具有一致性的雜湊做法，來新增或移除下載伺服器
- 保存擷取狀態與資料，避免出現故障狀況，可以把擷取狀態與資料本身寫到某個儲存系統中，故障後可以重新載入繼續運行
- 妥善處理異常，不要讓系統崩潰
- 資料驗證要做好，可以避免系統錯誤
- 地理位置
- 離目標位置越近傳輸時間越短
## 系統設計
- 需求釐清
- 爬蟲目的是什麼? -> 搜尋引擎索引編製
- 每月需要收集多少網頁 -> 10億個
- 要抓哪些類型的內容? HTML, PDF, Image, ...? -> 只有 HTML
- 是否要考慮新添加或是編輯過的網頁? -> 需要更新
- 是否需要保存擷取到的 HTML 頁面 -> 要，最多保存 5 年
- 重複內容如何處理? -> 忽略
- 估算
- 每月 10 億個網頁
- QPS, 10 億 / 30 天 / 24 小時 / 3600 秒 = 每秒 400 個頁面
- 峰值 QPS = 2 \* QPS = 800
- 短時間內大量新 URL 湧入，所以系統最好可以處理 800 req/s 的流量，確保 queue 不會堆積
- 堆積 → 處理延遲 → 新頁面發現變慢 → 搜尋引擎新鮮度下降 → 用戶體驗變差
- 10 億 * 500kb = 每月 500 TB 的儲存空間
- 資料保留 5 年，500TB \* 12 個月 \* 5 年 = 30 PB
- 高階設計
- 選定種子網址 (Seed URL)，從這個種子擴展出去
- 以地區劃分
- 以主題劃分，購物、運動、醫療等
- 網址邊境 (URL Frontier)
- 把要下載的網址保存起來的資料結構
- 可以以確保禮貌性、網址優先順序、內容新鮮度
- 檢查 Robots.txt 看是否可以下載
- 定義擷取狀態，區分要下載、已下載
- HTML 下載器
- 通常會設計成可以水平擴展
- 快取 DNS 解析器
- 一般DNS會是爬蟲的一個瓶頸，因為爬蟲會大量打出網址
- 在使用瀏覽器時的DNS流程，瀏覽器緩存 -> 系統緩存 -> 路由器緩存 -> ISP DNS
- 但爬蟲服務佈署在 server 上只有，系統緩存 -> ISP DNS
- 一般系統會預設使用 systemd-resolved 提供 DNS 緩存。這是目前最常見的本地緩存機制。
- 不過爬蟲適合使用，主要原因在於淘汰機制的問題
- TTL 過期就丟
- 只有系統快 OOM 才積極淘汰 LRU (Least Recently Used)
- hit rate 可能很低
- 通常會使用像是 dnsmasq, Unbound 會有比較靈活的快取淘汰設定
- 內容解析器
- 解析下載內容
- 檢查是否為看過的內容，有30%網頁是重複的，可以用雜湊或是checksum過濾掉
- 網路蜘蛛陷阱，讓爬蟲陷入迴圈的狀況，www.example.com/foo/bar/foo/bar/...，可以針對長度設定最大值來避免anti-spam
- 資料雜訊，像是廣告，垃圾郵件網址等沒價值的內容，也可以過濾掉
- JavaScript Rendering / Dynamic Content，這類內容只能用 headless browser 渲染後取得內容 (playwright, selenium)
- 成本很高，所以要做 SEO 通常會用 SSR
- URL/Links Extractor
- 抓出 HTML 內的網址
- URL Filter
- 篩選掉不需要的內容，藉由檔案類型、副檔名、黑名單網址、錯誤連結
- 看過的網址
- Bloom or Hash table
- URL Storage, 儲存看過的網址
- 設計細節
- 搜尋方式，DFS or BFS，BFS 適合爬蟲，因為DFS深度可能會很深
- 但 BFS 會專注大量的抓同一個 domain 的內容，這樣可能會導致同一 domain 的內容累積
- 某些網頁可能很大要下載很久，可以將超時時間設短一點，早點釋放資源出來
## Demo
- {%preview https://github.com/RayOct18/web-scraper %}
- 三個設置，跑 3 萬個頁面
- DNS Cache (X), Bloom Filter (X)
- DNS Cache (O), Bloom Filter (X)
- DNS Cache (O), Bloom Filter (O)
- 因為網路關係，所以下載部分用模擬的，設定成 50ms
| 頻寬 | 平均頁面 50KB | 平均頁面 100KB |
|------|--------------|----------------|
| 100 Mbps | 250 QPS | 125 QPS |
| 200 Mbps | 500 QPS | 250 QPS |
| 1 Gbps | 2500 QPS | 1250 QPS |
- 考慮
- 禮貌性，每個 host
- 同時抓 10 個頁面，抓完後等 0.5 秒
- 比較
- DNS Cache (X), Bloom Filter (X)
- DNS Cache (O), Bloom Filter (X)
- QPS 提升
- DNS Cache (O), Bloom Filter (O)
- RAM 使用量下降，下降不多，但量級放大的話就會有很大的差異
- Set vs Bloom Filter (p=0.01，k=7 hashes) 對比
| 資料結構 | 公式 | 1B URLs |
| ----- | ------------------------ | ------- |
| Set | n × (74 + url_len) | 174 GB |
| Bloom | -n × ln(p) / ln(2)² bits | 1.14 GB |