FAN YOURSS

系统设计[实战篇-BotNet Web Crawler]

题目是设计 web crawler，每个web crawler都是一个被hack的device（这里有坑），crawler的内容无所谓，有一个初始页面然后，crawl当前页面以及link的页面。

居然是高频题。。。我要被雷死了。。

Facebook | System Design | A web crawler that will crawl Wikipedia - LeetCode Discuss

Clarification:

  • Can the number of crawler change?
  • Consistent hashing handle node failures (redistribute crawled urls)

这个就是考察consistent hashing，没想到的基本gg咯。

居然还有论文

嵌入内容

论文分为两块，P2P protocol和Peer本身内部的代码。

P2P protocol

P2P主要是两个功能，1. Task Distribution (用DHT, distributed hash table 去找应该handle 这个url的node) 2. Duplicate Check (同样用DHT去找指定node去重)

比较有意思的是:

  1. url不应该是整个去做key，而只取domain，这样一个node总是负责所有domain下的url，会简化设计并且提供更好的locale
  2. 一个DHT不够，domain需要一个，content也需要一个，content那个用来去重，原因是可能有不同的url的内容是一样的，如果处理domain的node同时去重的话，就会漏掉这种情况
  3. 加减node还是需要一个bootstrap service (但是这题并没有提到加减node的情况)
  4. Bloom Filter 还是常用手段，主要以极低的Memory去快速查询membership
  5. 注意DHT的lookup是log(N)，简单理解就是hash完的value需要binary search才能找到谁去handle他

Peer Internal Architecture

Node 主要maintain 5 个东西

  1. Crawl Jobs (URL to crawl)
  2. Processing Jobs (URL to extract)
  3. Seen URLs (Bloom Filter)
  4. Seen Content (Bloom Filter)
  5. Routing Table (DHT，知道URL和Content分别该去找哪个node)

Open Question

  1. Security, expose http endpoint, anyone can call, but does it matter?
  2. Node failure，被动node exit，notify bootstrap service，进行node的exit程序，或者也可以introduce一个额外的hash，找寻node进行backup