System Design: Web Crawler
资料整理来源：
- https://www.jiuzhang.com/qa/871/
- https://zhuanlan.zhihu.com/p/20821699
Crawler实质是一个BFS的过程。从某个网站的主页开始作为起点，进行BFS。对每一个页面含有的URL都放入队列当中。再进行迭代。
我们可以把整个过程抽象成为一幅有向图的BFS。但是，爬虫可以在BFS的基础上产生更多的问题。比如，每个页面还有很多的URL，但是否每个URL都那么重要？是否应该先遍历重要的URL？
如果页面更新了怎么办呢？
再比如，为了加速爬虫，使用了多线程甚至分布式去爬取，怎么协调？
下面我将一个一个问题进行阐述及提出可能的思路：
对于URL分权重问题，我们可以使用PriorityQueue的大根堆作为BFS的队列buffer，根据页面的权重进行排序。优先抓取权重较高的网页。对于权重的设定，考虑的因素有：链接长度或者如同PageRank算法一样通过引用数（link到该网页的网页的权重以及该网页被指向的次数）来确定一个URL 的重要程度。关于PageRank的介绍详情可以看：
https://blog.csdn.net/rubinorth/article/details/52215036#6-pagerank%E7%AE%97%E6%B3%95%E7%9A%84%E7%BC%BA%E7%82%B9
简而言之，就是rank的实质是一个概率。其被引用的概率。一开始是1/N，N是网页的总数。假设A网页有网页B和网页C两个网站链接，而网页B上有4个外链接，网页C上有3个外链接。那么网页A的PR(A) = PR(B) / 4 + PR(C) / 3. 为了满足马尔科夫链的收敛定律，如果某个自私的网页上没有别的外链接，我们假设其对每个网页都有链接，但是外加一个阻尼系数来判断用户有多大可能停留在相同的网页而不会再重新在地址栏上输入新的地址。
针对网页更新的问题，网页如果被抓下来以后，有的网页会持续变化，有的不会。这里就需要对网页的抓取设置一些生命力信息。当一个新的网页链接被发现以后，他的生命力时间戳信息应该是被发现的时间，表示马上需要被抓取，当一个网页被抓取之后，他的生命力时间戳信息可以被设置为x分钟以后，那么，等到x分钟以后，这个网页就可以根据这个时间戳来判断出，他需要被马上再抓取一次了。一个网页被第二次抓取以后，需要和之前的内容进行对比，如果内容一致，则延长下一次抓取的时间，如设为2x分钟后再抓取，直到达到一个限制长度如半年或者三个月（这个数值取决于你爬虫的能力）。如果被更新了，则需要缩短时间，如，x/2分钟之后再抓取。
架构设计，从简单到复杂，下属内容参考文章开头的知乎专栏：
如果我们要爬取一个新闻网站的所有新闻页面，我们我们需要得到这些页面的url，这也是通过crawlers来获取的（从HTML页面中提取出来）。所以我们可以设计两种crawler，一种负责获取更多的url，一种负责爬取页面内容。
Links Of News就是BFS的Buffer队列，而Pages of News则是爬出来的内容。
接着，针对不同的网站我们进行不同的BFS。所以，我们可以对不同的网站分别建立1个List Crawler线程和N个 News crawler线程。由于Buffer队列和内容数据结构都是多线程共享的内存，所以需要临界区数据保护。
在这里，list crawler就是生产者，news crawler就是消费者。links of news就是生产、消费队列。Page of news则是写锁临界区。是一个排它锁。
但是这个架构有一个问题，如果163的新闻比较少，sina最多，那么163的爬虫爬完了会闲置浪费，而不能帮忙爬sina。所以升级版是设计通用的爬虫，每个Crawler任务不同，有的爬页面，有的爬url，这些爬虫都通过一个scheduler统一调度，这种架构减少了冗余浪费，性能更优。
关于调度crawler可以是通过条件锁的生产者消费者问题，可以参考我的博客：https://blog.csdn.net/firehotest/article/details/60455811
以上讲的是单机多线程的设计，那如果推到分布式的爬虫呢？
最经典的架构就是Task&Pages在中心，Crawler分布在四周，每个Crawler和一个Connector相对应。
注意，此时connector变成了消费者。news crawler只是一个干活的。
这个架构好像Connector太多了，我们真的需要这么多Connector吗？我们可以实现一个一对多的架构，由统一的Sender给Crawler发任务，统一的Receiver接收结果。用多一个table去记录crawlers的状态，只能由sender和receiver去修改。pages由receiver统一去修改。这个架构其实并没有减少Crawler和中心的连接数，可是这种架构方便统一管理，免去了协调过多Connector的麻烦，也符合当下微架构的设计模式。
但是总是要锁来锁去有点麻烦，能不能避开锁的问题呢？我们可以利用数据库来解决，直接从数据库里获取数据存放数据数据，让数据库来解决同步机制。