[Web Crawler] Backqueue Selector的实现问题

系统设计
1

请问老师backqueue selector是如何consume 每个single host queue 来支持politeness crawling的？我有以下两种对于实现方案的理解，希望老师指正：
1，基于min heap，每当有新的url，selector根据当前时间窗口内该host已经进行爬取任务数，结合domain policy确定timestamp gap,然后放入min heap。另有一个线程不断的从min heap中pop URL并分配给fetcher。这个方案应该可以保证爬取频率的问题，但是如何保证对于同时爬取连接数不超过限制？如果domain规定1秒可以爬10次，但是只能一个bot来爬，那当堆顶10个URL都是同一个domain的话，这个selector需要再refer domain policy然后将10个URL都分配个同一个fetcher吗？那这样是否又需要维护一个domain -> fetcher的map？

2，不用min heap，每个或者几个single host queue对应一个worker线程，worker线程内部实现类似rate limiter的逻辑来控制爬取的速率。

好像为了保证遵循爬取连接数的policy，不论哪种方案都需要维护domain -> fetchers的map。

希望老师能帮助回答上面两个方案的可行性，我在学习过程中一直感觉对back queue selector具体实现的理解不能落地，谢谢老师！

2

你对 heap 在这题里的使用理解有点小偏差 - 堆里放的信息不是 URL，而是 Single Host Queue ID 以及对应的下次最早爬取时间。每个 domain 只会在 heap 里出现一次，就没有你提到的堆顶10个URL同一个domain的问题。
不知道是不是回答你的问题。要是还有问题可以再 followup。

4

谢谢！这块确实是思考的时候忘记了，如果是single host queue id，就make sense了！然后关于如何将host queue中的URL交给fetcher我觉得可以如下做，请老师看看是否可行：

1 当栈顶元素的timestamp早于当前时间就就pop出来，然后从对应的single host queue中拿URL来交给fetcher去做
2 取多少个URL要结合两个元素考虑：
a) Domain policy 规定时间窗口内最多能爬取的网页数量
b) 当前还在执行的爬取任务数，可以用一个Redis/或者查看craw history DB来查看任务情况、
c) a) - b)得到当前可以新爬的URL数
3 另外还要再结合Domain Policy来确定应该用几个fetcher来同时爬取，此处也可以用redis来维护一个host - fetcher的列表

5

Step 1 没问题。
Step 2 如果要非常严格遵守 domain policy 的话需要做到 b)，因为 fetch 是 async。但是我觉得实际操作中不一定需要这么精确，可以假设之前开始的 crawl 已经完成了。这样系统复杂度可以降低一些。
Step 3 不太明白你的意思。每个 URL 都会是交给不同 fetcher 来 fetch的。

6

谢谢老师！Step3是我对politeness的理解有误，我以为网站也会明确限制crawler的并发连接数，所以假设我们需要限制对一个host的并发连接。经过学习发现这方面没有明确的限制协议。所以应该只限制爬取的频率就可以了。