引用:
系统设计入门
设计一个网页爬虫
第一步:通过讨论,明确限制及用例,确定Scope
支持的用例:
- 系统抓取一系列的网址
- 产生倒排索引
- 产生网页的标题和摘要
- 用户可以输入关键词,系统显示出相关的网页标题及摘要
- 系统高可用 high availability
不支持的用例:
- 不支持搜索结果分析
- 不支持自定义搜索模式
- 不支持Page rank
Constraints and assumptions:
- 访问不均匀
- 搜索速度要快
- 有1 billion个网页需要抓取,每秒1,600次写操作
- 每周重新抓取一次,因此每月需要抓取 4 billion 个网页
- 每个网页平均 500 K
- 每月搜索 100 billion 次,每秒40,000次读操作
计算规模:
- 1 billion个网页占用:500K * 1 billion = 500TB
- 每月网页占用:4 * 500TB = 2PB
- 三年网页占用:72PB
第二步:高层次设计
设计一个网页爬虫第三步:设计核心组件
假设我们有一个初始的网址列表 links_to_crawl
,里面的网址是根据 popularity 排序的。可以使用Redis中的有序集合 sorted sets 来存储。
使用crawled_links
存储已经处理过的网址及对应的网页签名 page signature。可以使用 key - value 的NoSQL数据库来存储。key 是网址,value 是网页签名。
Crawler Service 的主要工作:
- 从
links_to_crawl
取出一个优先级排序最高的网址,检查在crawled_links
有没有相类似网页签名的记录:- 如果有,降低该网址的优先级
- 这样可以防止系统进入死循环
- 如果没有,抓取网页内容:
- 发送任务到 Reverse Index Service 队列,用来产生倒排索引
- 发送任务到 Document Service 队列,产生网页的标题和摘要
- 产生网页签名
- 将该网址从
links_to_crawl
中移除 - 将该网址及网页签名添加到
crawled_links
中 - 将该网页中包含的URL,添加到
links_to_crawl
中
- 如果有,降低该网址的优先级
处理重复:
防止抓取进入一个死循环。需要去除links_to_crawl
中重复的网址。由于数据量很大,我们可以使用 MapReduce 来查询只出现了一次的网址。例如:
class RemoveDuplicateUrls(MRJob):
def mapper(self, _, line):
yield line, 1
def reducer(self, key, values):
total = sum(values)
if total == 1:
yield key, total
何时需要更新抓取结果:
使用timestamp
记录每个网页上一次被抓取的时间。每隔一周需要重新抓取。
或者可以使用一些数据挖掘的方法,来估算每一个网页的更新时间。
搜索功能:提供一个Query REST API
- 解析输入字符串:
- 去除标记 markup
- 分词
- Fix 输入错误 typo
- 规范化大小写
- 调用 Reverse Index Service,获得输入关键字对应的网址列表
- Reverse Index Service会对结果排序,并返回靠前的结果
- 随后调用 Document Service,获得每个网址的标题及摘要信息
返回的结果为JSON格式,例如:
{
"title": "foo's title",
"snippet": "foo's snippet",
"link": "https://foo.com",
},
{
"title": "bar's title",
"snippet": "bar's snippet",
"link": "https://bar.com",
}
第四步:扩展设计
设计一个网页爬虫- 为了同时响应更多请求,对服务器水平扩展,并使用Load Balancer做负载均衡。
- 为了加快搜索效率,使用Memory Cache,存储热门的搜索结果。
- Reverse Index Service 和 Document Service 计算量和吞吐量比较大,可以创建多个实例,并行处理对应的Queue。
- Crawler Service可以维护一个自己的DNS lookup,来减少与外界DNS服务器的通信时间。
网友评论