System - Web Crawler

Posted at 2022-05-30Updated at 2022-05-30 interview  interview system 

Design a web crawler

# Requirements

# Functional Requirements

• service crawls a list of urls
  • generates reverse index of words to pages containing the search items
  • 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

# Non-Functional Requirements

1. Availability
2. Scalability

# Estimations

# Assumptions

• Traffic is not evenly distributed
  • Some searches are very popular, while others are only executed once
• Support only anonymous users
  • We won’t implement a login system
• Generating search results should be fast
  • Performance
• 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
• Text only

# Estimations

I will have a back-of-the-envelope calculations here

• 2 PB of stored page content per month
  • 500 KB * 4 billion links crawled per month
  • 72 PB of stored page content in 3 years
• 1,600 write requests per second
  • 1 billion / 24 / 7 / 3600 = 1653 ~ 1600
• 40,000 search requests per second
  • 400 * 100, for the peak traffic, 4 times of 80,000 requests per second

# Domain Design

# Core Components

We’ll assume we have an initial list of links_to_crawl ranked initially based on overall site popularity. If this is not a reasonable assumption, we can seed the crawler with popular sites that link to outside content such as Yahoo, DMOZ, etc.

We’ll use a table crawled_links to store processed links and their page signatures.

We could store links_to_crawl and crawled_links in a key-value NoSQL Database. For the ranked links in links_to_crawl, we could use Redis with sorted sets to maintain a ranking of page links. We should discuss the use cases and tradeoffs between choosing SQL or NoSQL.

Why are you choosing NoSQL?

As we don’t need the relations between different records, but simply just store the reverse index to the contents. KV Store would be a reasonable database for that.

The Crawler Service processes each page link by doing the following in a loop:

• Takes the top ranked page link to crawl
• Checks crawled_links in the NoSQL Database for an entry with a similar page signature
  • If we have a similar page, reduces the priority of the page link
    • This prevents us from getting into a cycle
    • Continue
  • Else, crawls the link
    • Adds a job to the Reverse Index Service queue to generate a reverse index
    • Adds a job to the Document Service queue to generate a static title and snippet
    • Generates the page signature
    • Removes the link from links_to_crawl in the NoSQL Database
    • Inserts the page link and signature to crawled_links in the NoSQL Database

Clarify with your interviewer how much code you are expected to write.

TABLE Page:
url
contents
child_urls
signature

# Handling duplicates

We need to be careful the web crawler doesn’t get stuck in an infinite loop, which happens when the graph contains a cycle.

We’ll want to remove duplicate urls:

• For smaller lists we could use something like sort | unique
• With 1 billion links to crawl, we could use MapReduce to output only entries that have a frequency of 1

Detecting duplicate content is more complex. We could generate a signature based on the contents of the page and compare those two signatures for similarity. Some potential algorithms are Jaccard index and cosine similarity.

Or we could just use article embedding to get a similarity vector.

# Determining when to update the crawl results

Pages need to be crawled regularly to ensure freshness. Crawl results could have a timestamp field that indicates the last time a page was crawled. After a default time period, say one week, all pages should be refreshed. Frequently updated or more popular sites could be refreshed in shorter intervals.

Although we won’t dive into details on analytics, we could do some data mining to determine the mean time before a particular page is updated, and use that statistic to determine how often to re-crawl the page.

We might also choose to support a Robots.txt file that gives webmasters control of crawl frequency.

# Reverse Index

• Get the document
• Segmentation, split the whole documents into words by spaces and eliminates non-important characters and words like a, the, this, that
• Count the frequency of each word and insert them into the reverse index table
• word -> document id & frequency

# Use case: User inputs a search term and sees a list of relevant pages with titles and snippets

• The Client sends a request to the Web Server, running as a reverse proxy
• The Web Server forwards the request to the Query API server
• The Query API server does the following:
  • Parses the query
    • Removes markup
    • Breaks up the text into terms
    • Fixes typos
    • Normalizes capitalization
    • Converts the query to use boolean operations
  • Uses the Reverse Index Service to find documents matching the query
    • The Reverse Index Service ranks the matching results and returns the top ones
  • Uses the Document Service to return titles and snippets

# Scale the design

Use DNS, LoadBalancer, Web Server, API Server, Memory Cache

State you would 1) Benchmark/Load Test, 2) Profile for bottlenecks 3) address bottlenecks while evaluating alternatives and trade-offs, and 4) repeat. See Design a system that scales to millions of users on AWS as a sample on how to iteratively scale the initial design.

It’s important to discuss what bottlenecks you might encounter with the initial design and how you might address each of them. For example, what issues are addressed by adding a Load Balancer with multiple Web Servers? CDN? Master-Slave Replicas? What are the alternatives and Trade-Offs for each?

Some searches are very popular, while others are only executed once. Popular queries can be served from a Memory Cache such as Redis or Memcached to reduce response times and to avoid overloading the Reverse Index Service and Document Service. The Memory Cache is also useful for handling the unevenly distributed traffic and traffic spikes. Reading 1 MB sequentially from memory takes about 250 microseconds, while reading from SSD takes 4x and from disk takes 80x longer.1

Below are a few other optimizations to the Crawling Service:

• To handle the data size and request load, the Reverse Index Service and Document Service will likely need to make heavy use sharding and federation.
• DNS lookup can be a bottleneck, the Crawler Service can keep its own DNS lookup that is refreshed periodically
• The Crawler Service can improve performance and reduce memory usage by keeping many open connections at a time, referred to as connection pooling
• Switching to UDP could also boost performance
• Web crawling is bandwidth intensive, ensure there is enough bandwidth to sustain high throughput

# Practical

# ElasticSearch

从原理到应用，Elasticsearch详解

# Lucene

Lucene 倒排索引原理

# Spark

深入浅出 Spark：原理详解与开发实践

# MapReduce

# Embedding

How to build a search engine with word embeddings