作者 | 东邪老师
编辑 | Jenny

专栏 | 九章算法
Q
问题描述

如果让你来设计一个最基本的Web Crawler，该如何设计？需要考虑的因素有哪些？
A
解题思路
这个问题是面试中常见的设计类问题。没有标准答案。需要尽可能的回答出多一点的考虑因素。
实际上如果你没有做过相关的设计，想要回答出一个让面试官满意的结果其实并不是很容易。该问题并不局限于你在去面试搜索引擎公司时可能会问到。这里，我们从Junior Level和Senior Level两个角度来解答这个问题。
本题运用九章算法《系统设计班》答题技巧则进行拆解，在课程中会有更详细的讲解。
1
如何抽象整个互联网
Junior
抽象为一个无向图，网页为节点，网页中的链接为有向边。
Senior
同上。
2
抓取算法
Junior
采用BFS的方法，维护一个队列，抓取到一个网页以后，分析网页的链接，扔到队列里。
Senior
采用优先队列调度，区别于单纯的BFS，对于每个网页设定一定的抓取权重，优先抓取权重较高的网页。对于权重的设定，考虑的因素有：1. 是否属于一个比较热门的网站 2. 链接长度 3. link到该网页的网页的权重 4. 该网页被指向的次数 等等。
进一步考虑，对于热门的网站，不能无限制的抓取，所以需要进行二级调度。首先调度抓取哪个网站，然后选中了要抓取的网站之后，调度在该网站中抓取哪些网页。这样做的好处是，非常礼貌的对单个网站的抓取有一定的限制，也给其他网站的网页抓取一些机会。
3
网络模型
Junior
多线程抓取。
Senior
分别考虑单机抓取和分布式抓取的情况。对于Windows的单机，可以使用IOCP完成端口进行异步抓取，该种网络访问的方式可以最大程度的利用闲散资源。因为网络访问是需要等待的，如果简单的同时开多个线程，计算机用于线程间切换的耗费会非常大，这种用于处理抓取结果的时间就会非常少。IOCP可以做到使用几个线程就完成几十个线程同步抓取的效果。对于多机的抓取，需要考虑机器的分布，如抓取亚洲的站点，则用在亚洲范围内的计算机等等。
4
实时性
Junior
无需回答
Senior
新闻网页的抓取一般来说是利用单独的爬虫来完成。新闻网页抓取的爬虫的权重设置与普通爬虫会有所区别。首先需要进行新闻源的筛选，这里有两种方式，一种是人工设置新闻源，如新浪首页，第二种方式是通过机器学习的方法。新闻源可以定义链接数非常多，链接内容经常变化的网页。从新闻源网页出发往下抓取给定层级限制的网页所得到，再根据网页中的时间戳信息判断，就可以加入新闻网页。
5
网页更新
Junior
无需回答。

Senior
网页如果被抓下来以后，有的网页会持续变化，有的不会。这里就需要对网页的抓取设置一些生命力信息。当一个新的网页链接被发现以后，他的生命力时间戳信息应该是被发现的时间，表示马上需要被抓取，当一个网页被抓取之后，他的生命力时间戳信息可以被设置为x分钟以后，那么，等到x分钟以后，这个网页就可以根据这个时间戳来判断出，他需要被马上再抓取一次了。一个网页被第二次抓取以后，需要和之前的内容进行对比，如果内容一致，则延长下一次抓取的时间，如设为2x分钟后再抓取，直到达到一个限制长度如半年或者三个月（这个数值取决于你爬虫的能力）。如果被更新了，则需要缩短时间，如，x/2分钟之后再抓取。
6
总结
一般来说，上述5点是你可以去回答如何设计一个爬虫的5个角度。
7
课程推荐
九章算法《系统设计班》，由本文作者东邪老师主讲
免费试听内容：
  • 系统设计中常见的问题是什么

  • 怎样回答系统设计问题
  • 如何设计推特
免费试听时间：
美西时间 3月11日周日 10:00-12:00
美东时间 3月11日周日 13:00-15:00
北京时间 3月12日周一 01:00-03:00(a.m)
长按二维码报名：
更多精彩内容
  • 回复“简历”，查看简历撰写指南，获取“简历模板”
  • 回复“冷冻期”，查看北美各大IT企业冷冻期信息和注意事项
  • 回复“Career”, 查看Caireer Fair 攻略 check list
  • 回复“薪资”，查看北美各大IT企业New Grades Engineer 薪资水平；
  • 回复“项目”，查看7-14天可以搞定的小项目推荐
  • 回复“评分”，查看系统设计评分指南
  • 回复“behavior”，查看behavior interview指南
  • 回复“晋升”，查看Engineer晋升机制 
九章算法 | 帮助更多中国人找到好工作
《硅谷算法求职训练营》
正在报名中！
简历精修
1对1模拟面试
明星公司内推
报名登陆官网 www.jiuzhang.com
或点击文末“阅读原文
继续阅读
阅读原文