作者 | 九章算法東邪老師
問題描述：如果讓你來設計一個最基本的Web Crawler，該如何設計？需要考慮的因素有哪些？
解題思路
這個問題是面試中常見的設計類問題。沒有標準答案。需要儘可能的回答出多一點的考慮因素。
實際上如果你沒有做過相關的設計，想要回答出一個讓面試官滿意的結果其實並不是很容易。該問題並不侷限於你在去面試搜索引擎公司時可能會問到。這裡，我們從Junior Level和Senior Level兩個角度來解答這個問題。
本題運用九章算法《系統架構設計》答題技巧則進行拆解，在課程中會有更詳細的講解。
1.如何抽象整個互聯網
- Junior
抽象為一個無向圖，網頁為節點，網頁中的鏈接為有向邊。
- Senior
同上。
2.抓取算法
- Junior
採用BFS的方法，維護一個隊列，抓取到一個網頁以後，分析網頁的鏈接，扔到隊列裡。
- Senior
採用優先隊列調度，區別於單純的BFS，對於每個網頁設定一定的抓取權重，優先抓取權重較高的網頁。對於權重的設定，考慮的因素有：1. 是否屬於一個比較熱門的網站 2. 鏈接長度 3. link到該網頁的網頁的權重 4. 該網頁被指向的次數 等等。
進一步考慮，對於熱門的網站，不能無限制的抓取，所以需要進行二級調度。首先調度抓取哪個網站，然後選中了要抓取的網站之後，調度在該網站中抓取哪些網頁。這樣做的好處是，非常禮貌的對單個網站的抓取有一定的限制，也給其他網站的網頁抓取一些機會。
在我的《系統架構設計》第15章會通過對爬蟲系統設計 (Web Crawler) 與 搜索建議系統設計 (Google Suggestion) 詳細分析如下內容：
- 多線程
- 生產者消費者模型
- 爬蟲系統的演化：單線程，多線程，分佈式
- Trie 結構的原理及應用
- 如何在系統設計中使用 Trie
3.網絡模型
- Junior
多線程抓取。
- Senior
分別考慮單機抓取和分佈式抓取的情況。對於Windows的單機，可以使用IOCP完成端口進行異步抓取，該種網絡訪問的方式可以最大程度的利用閒散資源。因為網絡訪問是需要等待的，如果簡單的同時開多個線程，計算機用於線程間切換的耗費會非常大，這種用於處理抓取結果的時間就會非常少。IOCP可以做到使用幾個線程就完成幾十個線程同步抓取的效果。對於多機的抓取，需要考慮機器的分佈，如抓取亞洲的站點，則用在亞洲範圍內的計算機等等。
4.實時性
- Junior
無需回答
- Senior
新聞網頁的抓取一般來說是利用單獨的爬蟲來完成。新聞網頁抓取的爬蟲的權重設置與普通爬蟲會有所區別。首先需要進行新聞源的篩選，這裡有兩種方式，一種是人工設置新聞源，如新浪首頁，第二種方式是通過機器學習的方法。新聞源可以定義鏈接數非常多，鏈接內容經常變化的網頁。從新聞源網頁出發往下抓取給定層級限制的網頁所得到，再根據網頁中的時間戳信息判斷，就可以加入新聞網頁。
5.網頁更新
- Junior
無需回答。
- Senior
網頁如果被抓下來以後，有的網頁會持續變化，有的不會。這裡就需要對網頁的抓取設置一些生命力信息。當一個新的網頁鏈接被發現以後，他的生命力時間戳信息應該是被發現的時間，表示馬上需要被抓取，當一個網頁被抓取之後，他的生命力時間戳信息可以被設置為x分鐘以後，那麼，等到x分鐘以後，這個網頁就可以根據這個時間戳來判斷出，他需要被馬上再抓取一次了。一個網頁被第二次抓取以後，需要和之前的內容進行對比，如果內容一致，則延長下一次抓取的時間，如設為2x分鐘後再抓取，直到達到一個限制長度如半年或者三個月（這個數值取決於你爬蟲的能力）。如果被更新了，則需要縮短時間，如，x/2分鐘之後再抓取。
6.總結
一般來說，上述5點是你可以去回答如何設計一個爬蟲的5個角度。
九章算法，程序員的職場必修課。硅谷頂尖科技公司和國內一線互聯網大廠IT工程師在線授課。課程類型豐富，涵蓋算法類、項目實戰類、小班訓練營、VIP1對1私人服務等課程，幫助10w+學員成功拿到國內外頂尖大廠offer。