如何设计爬虫系统 | 系统设计高频题解题思路分析

2018 年 3 月 6 日 九章算法 东邪老师

作者 | 东邪老师

编辑 | 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

或点击文末“阅读原文

登录查看更多
0

相关内容

系统设计是新系统的物理设计阶段。根据系统分析阶段所确定的新系统的逻辑模型、功能要求,在用户提供的环境条件下,设计出一个能在计算机网络环境上实施的方案,即建立新系统的物理模型。
专知会员服务
28+阅读 · 2020年5月20日
【实用书】Python数据科学从零开始,330页pdf
专知会员服务
140+阅读 · 2020年5月19日
干净的数据:数据清洗入门与实践,204页pdf
专知会员服务
160+阅读 · 2020年5月14日
【实用书】Python爬虫Web抓取数据,第二版,306页pdf
专知会员服务
115+阅读 · 2020年5月10日
深度神经网络实时物联网图像处理,241页pdf
专知会员服务
76+阅读 · 2020年3月15日
今日头条技术架构分析
互联网架构师
11+阅读 · 2019年8月19日
用户研究:如何做用户画像分析
产品100干货速递
44+阅读 · 2019年5月9日
OOD&系统设计大礼包 | 价值 $199 福利免费领取!
九章算法
12+阅读 · 2019年4月28日
我是一个爬虫
码农翻身
12+阅读 · 2018年6月4日
干货 | Python 爬虫的工具列表大全
机器学习算法与Python学习
10+阅读 · 2018年4月13日
Python 杠上 Java、C/C++,赢面有几成?
CSDN
6+阅读 · 2018年4月12日
设计和实现一款轻量级的爬虫框架
架构文摘
13+阅读 · 2018年1月17日
33款可用来抓数据的开源爬虫软件工具 (推荐收藏)
数据科学浅谈
6+阅读 · 2017年7月29日
Arxiv
8+阅读 · 2019年5月20日
Arxiv
3+阅读 · 2018年4月5日
VIP会员
相关资讯
今日头条技术架构分析
互联网架构师
11+阅读 · 2019年8月19日
用户研究:如何做用户画像分析
产品100干货速递
44+阅读 · 2019年5月9日
OOD&系统设计大礼包 | 价值 $199 福利免费领取!
九章算法
12+阅读 · 2019年4月28日
我是一个爬虫
码农翻身
12+阅读 · 2018年6月4日
干货 | Python 爬虫的工具列表大全
机器学习算法与Python学习
10+阅读 · 2018年4月13日
Python 杠上 Java、C/C++,赢面有几成?
CSDN
6+阅读 · 2018年4月12日
设计和实现一款轻量级的爬虫框架
架构文摘
13+阅读 · 2018年1月17日
33款可用来抓数据的开源爬虫软件工具 (推荐收藏)
数据科学浅谈
6+阅读 · 2017年7月29日
Top
微信扫码咨询专知VIP会员