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 (key-value store like DynamoDB)

key: url

value: s3 url for page content

Page Content (blob storage like S3)

SeedURL (file)

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.

Failure scenarios/bottlenecks

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

• The number or urls might not be able to fit in memory of one Task Queue server.
• Urls maybe doubly sent to two or more workers due to lost network response.
• Data will be lost if Task Queue server crashes.
• 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?