fb面经题web crawler讨论

在面经版看到这道系统设计题出现在很多fb面经里，看大家的讨论交流还是有一些不懂的地方，有大牛可以讲解一下思路吗？

给你10K个机器，然后1B的url，机器之间不能通信，问你怎么样每个机器才能平均的分任务

http://www.1point3acres.com/bbs/thread-268942-1-1.html
帖子的楼主在3楼说了一下面试时被面试官引导的方向
“思路就是每台机器都从起始点开始，然后对拿到的url做hash，事先规定好每台机器都只做那些hash value的job，如果hash的值跟当前机器的预定值不一样就skip，一样才继续crawl”

10k机器，都从起点开始，可是起点hash之后只会对应到一台机器，按照^说的方向，那其他所有机器都不用爬就一直空闲下去了？

我理解其实就是一致性哈希啊。但是在分配任务之前，需要找到这1B个link，对它们做hash啊。这个事情并不能分布式的做。

所以这玩意能叫去中心的？概念上还是需要控制部件而且互相之间还要去重

consistent hashing..   look at dynamo paper

谢谢分享，虽然有段时间了还是回复下。
如果只能遍历所有数据，一共10K台机器，一起遍历，没有数据库能承受这么大的load。有两种解决方法：
1 分拆数据库，按照hash range拆分，然后每一百个机器对应一个数据库instance
2 在crawler之前加一层，叫dispatcher，有比如100个，每个dispatcher负责一个range，分配任务给下面的crawler。

当然还要继续考虑dispatcher down了怎么办 。。。

觉得有用请给点米，新人需要

这是经典的distributed hash table 问题. 从root url开始，下载webpage,从这个page里提取embedded url links, distribute 每个link 到对应负责任的machine. In general, 毎个机器接收url links from peers, 看是否已经访问过，没有的话，放入work queue, 有个thread 专门从queue取url, download page, extract urls, distributes to other machines.

swxe 发表于 2019-1-5 05:22
谢谢分享，虽然有段时间了还是回复下。
如果只能遍历所有数据，一共10K台机器，一起遍历，没有数据库能承 ...

谢谢分享啊，请问能再详细一点吗？

小狗雪碧 发表于 2019-1-19 02:19
谢谢分享啊，请问能再详细一点吗？

比如有1 billion url需要定期的crawl。简单的做法，每个url一个hash，hash的取值范围就是1 到 1billion。把hash分成10K个组，每个组一个range。这个range就是一个partition，或者叫shard。每台机器就负责一个shard。

更好的做法可以参考consistency hash，或者直接用cassandra存取这些URLs。可以到几百上千的node，支持10K机器没啥问题。

希望对你有用

swxe 发表于 2019-1-19 05:26
比如有1 billion url需要定期的crawl。简单的做法，每个url一个hash，hash的取值范围就是1 到 1billion。 ...

哦好的 谢谢了！很有帮助

不能通信连 DHT都不行，完全没法handle delete/add nodes的情况