问个web crawler的题

非常常见的题，尤其是FB的design面试10K个machine 来crawler整个web


我有两个疑问
1. url需要dedup， 很多youtube或者blog的设计里面都用Database或者bloom filter. 可是10billion 的url不是可以fit 进distributed cache吗？大概100GB左右， 比如redis cluster

2. 通常要求worker load balance， 为何不用message queue？ 比如rabbitmq. dedup之后直接塞进去mq然后worker sub不行吗



这两个疑问困扰我很久了,先谢过

如果是Facebook的那个web crawler的话，我觉得应该用distributed hash table， 完全decentralized。
在这个p2p的架构下，每个machine有自己的storage和cache，每个机器可以有自己的dedup hash table（当然每个机器用bloom filter也行，更省空间，但是我觉得没必要，毕竟有false positive）。
关于workload balance，可以用consistent hashing的概念，每个机器map到多个virtual node，然后尽量均匀地hash到一个ring上，每个crawling job也map到这个ring上，这样workload能尽量平均。

这题我看地理的讨论都是说要p2p 要用到Distributed hash table

用redis判重，用kafka存url，多个消费者读mq作bfs，完全可以。在内存不够大，mq不够快的古代，会被认为不现实。

补充内容 (2020-8-1 11:31):
我也同样困扰，期待高手标准答案。

sweetkonfyt 发表于 2020-07-31 20:30:20
用redis判重，用kafka存url，多个消费者读mq作bfs，完全可以。在内存不够大，mq不够快的古代，会被认为不现实。

补充内容 (2020-8-1 11:31):

我之前也想用Kafka做message queue，但是那样的话要做到10K partition来match machine. 每个partition没法load balance

ninjax 发表于 2020-07-31 21:56:06
我之前也想用Kafka做message queue，但是那样的话要做到10K partition来match machine. 每个partition没法load balance

能不能这样-
如果有10k host，我们可以有5000个 producer/consumer(同一台机器)， 2500个broker (一主一备)。每个broker 10个partition，每个consumer listen to 5个partition.

感兴趣关注一下

Clarification:
1. p2p架构还是centralized architecture? 实现方式差别好多的。

pxuu 发表于 2020-09-13 16:27:03
如果是Facebook的那个web crawler的话，我觉得应该用distributed hash table， 完全decentralized。
在这个p2p的架构下，每个machine有自己的

请问用p2p的主要原因是为了load更平均对吗？

tm1234 发表于 2020-9-19 23:15
请问用p2p的主要原因是为了load更平均对吗？

用p2p主要是因为Facebook的这个面试题的题目限定，要不然用centralized的方法（比如task queue）应该也可以实现不错的load balance