Web crawler
Design a web crawler that scrapes a large set of links, generates reverse indices, and serves search results — without crawling the same page twice or getting stuck in loops.
- 1 billion links to crawl
- Pages recrawled on a schedule by popularity
- Duplicate content must be deduplicated
- Support 5 billion searches a month
- Results ranked by relevance
- High availability
Crawl a list of links, generate a reverse index and page titles, serve search results with relevance ranking and pagination.
1 billion links at an average page size of 500 KB is 500 TB of content. The crawl rate, not the storage, is the constraint that shapes the design.
Gather requirements and scope the problem. Ask questions to clarify use cases and constraints. Discuss assumptions.
Without an interviewer to address clarifying questions, we'll define some use cases and constraints.
Use cases
We'll scope the problem to handle only the following use cases
- Service crawls a list of urls:
- Generates reverse index of words to pages containing the search terms
- Generates titles and snippets for pages
- Title and snippets are static, they do not change based on search query
- User inputs a search term and sees a list of relevant pages with titles and snippets the crawler generated
- Only sketch high level components and interactions for this use case, no need to go into depth
- Service has high availability
Out of scope
- Search analytics
- Personalized search results
- Page rank
Constraints and assumptions
State assumptions
- Traffic is not evenly distributed
- Some searches are very popular, while others are only executed once
- Support only anonymous users
- Generating search results should be fast
- The web crawler should not get stuck in an infinite loop
- We get stuck in an infinite loop if the graph contains a cycle
- 1 billion links to crawl
- Pages need to be crawled regularly to ensure freshness
- Average refresh rate of about once per week, more frequent for popular sites
- 4 billion links crawled each month
- Average stored size per web page: 500 KB
- For simplicity, count changes the same as new pages
- 100 billion searches per month
Exercise the use of more traditional systems - don't use existing systems such as solr or nutch.
Calculate usage
Clarify with your interviewer if you should run back-of-the-envelope usage calculations.
- 2 PB of stored page content per month
- 500 KB per page * 4 billion links crawled per month
- 72 PB of stored page content in 3 years
- 1,600 write requests per second
- 40,000 search requests per second
Handy conversion guide:
- 2.5 million seconds per month
- 1 request per second = 2.5 million requests per month
- 40 requests per second = 100 million requests per month
- 400 requests per second = 1 billion requests per month