System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

• Given a small set of seed URL, the system will be able to traverse the internet web following hyperlinks, and download content of each unique URL.
• The crawler will run every month.

Non-Functional:

List non-functional requirements for the system...

• The system should be able to handle 50 billion webpages.
• The content of pages should be stored for 5 years.
• Crawling don't need to be completed super fast, a few days should be okay.
• The system should be able to function upon failures of machines or networks.
• All pages should be crawled and stored.

Capacity estimation

Estimate the scale of the system you are going to design...

Assume: 50 billion webpages, average size of each page is 50kb;

10M new pages are created everyday.

The storage needed should be:

(50B + (10M * 365 * 5))*50kb = 3.4 PB

API design

Define what APIs are expected from the system...

This will be offline work and no API is needed.

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

• Page Metadata Table

key: url string

value: s3 url for page content , string

The table schema is quite simple, and data will be queries and indexed by key. In this case a nosql database like dynamodb would satisfy our needs, while providing more flexible scaling compared to sql database. The db can be easily sharded by url string.

• Page Content (blob storage like S3)

This db stores content of a page, which is html file and may have large size. So a blob storage suits our use case. The data will be indexed, sharded and retried by url generated by the blob storage.

• TaskQueue

key: url string

value: page_count integer - representing the number of pages that points to this url

This is a in-memory key-value data structure, sorted by page_count in reverse order. To guarantee durability, data is persisted in WAL file before updating in-memory structure, which is replicated across data centers. A in-memory queue like Redis should meed our requirements. Data can be indexed, sharded and retrieved by url string, and each shard maintains its own sorted data structure independently.

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

• Workers continuously fetch tasks from task queue, which are essentially a set of new urls that need to be crawled.
• Workers crawl the page content, and detect new urls based on hyperlink.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Task Queue

• The urls will be sorted by popularity , aka the number of pages that reference this page.
• The data will be stored in memory and sequence is updated realtime.
• Task Queue assigns urls to workers and remove the urls from the queue, while take new urls from workers.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

• The system will use a Breadth First Search , instead of Depth First Search, to traverse the web, which is more appropriate for distributed process.
• We'll crawl popular pages first, assuming they have more connections with other pages, and will results in more pages in shorter period of crawling process . This will better utilize the crawler worker resources by maximize parallel processing.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

• Urls maybe doubly sent to two or more workers due to lost network response.
• If workers fail to finish processing new urls, assigned urls will be lost from the system.
• If workers fail to finish sending new urls to task queue, the new urls will be lost.
• A page's content may be duplicated in s3 store due to lost network response.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?