System requirements

Functional:

1. Web Crawling:
2. The system should be able to initiate HTTP requests to web pages and download their content.
3. It must support different protocols (HTTP, HTTPS) and handle redirects appropriately.
4. The system should support handling various content types such as HTML, images, and other media files.
5. URL Frontier Management:
6. Maintain a dynamic URL frontier to prioritize and manage the order in which URLs are crawled.
7. Implement a mechanism to add new URLs to the frontier and remove them once crawled.
8. Support for scheduling URLs based on predefined rules or priorities.
9. Robots.txt Compliance:
10. The system must fetch and interpret the robots.txt file for each domain to ensure compliance with crawling rules.
11. Respect rules specified in robots.txt, including crawl-delay and disallow directives.
12. Data Extraction:
13. Extract relevant information from web pages, including text, images, links, metadata, etc.
14. Support for parsing and extracting structured data formats such as HTML, XML, or JSON.
15. Content Deduplication:
16. Implement a mechanism to identify and eliminate duplicate content to minimize redundant crawling.
17. Use hash functions or other techniques to compare and identify duplicate content.
18. Crawl Depth Control:
19. Provide a mechanism to customize the depth of crawling, limiting how many levels deep the crawler should follow links.
20. Support for setting depth limits based on domain or URL patterns.
21. Data Storage:
22. Store crawled data in a structured format (database, file system, etc.).
23. Support for efficient retrieval and update operations for the stored data.
24. Regular Crawling:
25. Schedule and perform regular crawls to ensure data freshness.
26. Support for incremental crawling to update only modified or new content.
27. Prevention of Infinite Loop:
28. Implement mechanisms to prevent the crawler from getting stuck in an infinite loop. Maintain state information to track visited URLs and avoid revisiting them unnecessarily.

Non-Functional:

1. Performance:
2. The system should be able to crawl and download content from a large number of web pages within a reasonable time frame.
3. Efficient handling of parallel requests to optimize throughput.
4. Scalability:
5. The system must be scalable to handle the specified workload of 1 billion web pages per month.
6. Reliability:
7. The crawler should operate reliably under normal and adverse conditions, minimizing downtime.
8. Robustness:
9. The system should gracefully handle errors and unexpected situations to ensure continuous operation.
10. Security:
11. Ensure secure handling of crawled content and avoid potential security vulnerabilities.
12. Implement secure communication (HTTPS) when interacting with web servers.
13. Throttling:
14. Throttling mechanisms should be effective in preventing the crawler from overwhelming servers while maintaining efficient crawling.
15. Compliance:
16. The system must comply with legal and ethical standards for web crawling.
17. Respect privacy and legal restrictions on crawling certain types of content.
18. Monitoring and Logging:
19. Implement comprehensive monitoring and logging to track system performance, errors, and crawling statistics.
20. Provide tools for administrators to analyze and troubleshoot issues.

Capacity estimation

Assumptions

• The system crawls 1 billion web pages per month
• Each web page has 10 media files on average
• An average media file size of 1MB

Storage Required for Web Pages:

Let us assume each web page on average has 100KB of data, so we need

Storage = Number of Pages * Average Page size * 12 months

Storage = 1 billion * 100 KB * 12

Storage = 1,000,000,000 * 1,00,000 * 12 = 1.2 PB

So, we would need 1.2 PB storage for 1 year

Storage required for media files

Since each web page can have 10 media files and each media file is 1 MB.

Storage = Number of Pages * 1 media file size * 10 files * 12 months

Storage = 1 billion * 1 MB * 10 * 12

Storage = 1,000,000,000 * 1,000,000 * 10 * 12 = 120 PB

So, we would need 120 PB storage for 1 year

API design

Below is the list of API's required for the system, although this might not be the exhaustive list, this provides a good starting point.

1. /api/addUrl:
2. Description: This API is used to add a new URL to the crawler's queue for processing.
3. Input: The input will be a JSON object containing the URL to be added.
4. Output: The output will be a response indicating the success or failure of the operation.
5. /api/getNextUrl:
6. Description: This API retrieves the next URL from the crawler's queue for crawling.
7. Input: No input parameters are required.
8. Output: The output is the URL to be crawled next or an indication that the queue is empty.
9. /api/crawlPage:
10. Description: Initiates the crawling process for a given URL.
11. Input: JSON object containing the URL and associated crawl parameters.
12. Output: Response indicating the success or failure of the crawling process.
13. /api/getCrawledData:
14. Description: Retrieves the crawled data for a specific URL.
15. Input: JSON object containing the URL or other identification parameters.
16. Output: The output is the crawled data, including text, images, links, etc., in a structured format.
17. /api/setCrawlDepth:
18. Description: Allows customization of the crawl depth for a specific URL or domain.
19. Input: JSON object containing the URL or domain and the desired crawl depth.
20. Output: Response indicating the success or failure of the operation.
21. /api/updateRobotsTxt:
22. Description: Updates the internal representation of robots.txt for a given domain.
23. Input: JSON object containing the domain and the updated robots.txt content.
24. Output: Response indicating the success or failure of the update.
25. /api/getCrawlStatus:
26. Description: Retrieves the current status of the crawling process.
27. Input: No input parameters are required.
28. Output: The output is a summary of the crawling status, including the number of pages crawled, errors encountered, etc.
29. /api/setThrottle:
30. Description: Allows dynamic adjustment of the crawling speed to prevent overloading servers.
31. Input: JSON object containing the throttle parameters (e.g., delay between requests).
32. Output: Response indicating the success or failure of the operation.
33. /api/checkCrawledStatus:
34. Description: Checks if a given URL has already been crawled.
35. Input: JSON object containing the URL.
36. Output: Response indicating whether the URL has been crawled or not.
37. /api/removeUrl:
38. Description: Removes a specific URL from the crawler's queue.
39. Input: JSON object containing the URL to be removed.
40. Output: Response indicating the success or failure of the removal operation.
41. /api/getMediaForUrl:
42. Description: Retrieves media files (images, videos, etc.) associated with a specific URL.
43. Input: JSON object containing the URL.
44. Output: The output is a list of media files with their respective URLs and metadata.

Database design

For tables required for this problem, refer the below diagram.

Database Choice

• Relational Database for URL and Metadata:
• Example: PostgreSQL or MySQL
• CAP Focus: Balanced (Consistency and Availability)
• Reasoning: Relational databases typically offer a balanced approach between consistency and availability. They ensure data integrity through ACID properties (Atomicity, Consistency, Isolation, Durability) while providing reasonable availability.
• Document-oriented Database for HTML and CSS Content:
• Example: MongoDB
• CAP Focus: Balanced (Consistency and Availability)
• Reasoning: Document-oriented databases, while supporting eventual consistency, are designed to provide a balance between consistency and availability. They are suitable for semi-structured data like HTML and CSS content.
• Distributed File System for Media Content:
• Example: Hadoop HDFS or Amazon S3
• CAP Focus: Availability
• Reasoning: Distributed file systems are optimized for availability and partition tolerance, making them suitable for storing large media files. In a web crawling scenario, ensuring availability for continuous crawling is critical.

Application of CAP theorem on the web crawler: Focus on Availability and Partition Tolerance:

• Reasoning: In the context of a web crawler, availability is crucial to handle a large volume of concurrent requests and ensure continuous crawling even in the presence of network partitions. While consistency is essential, a slight delay in updating crawled data due to eventual consistency is acceptable as long as the system remains available for crawling.
• The focus on availability and partition tolerance implies that the system might experience eventual consistency in the data store, meaning that updates to the database may take some time to propagate across the entire system. This trade-off allows the web crawler to continue functioning even in the face of network partitions or temporary database unavailability.

Data Partitioning Strategy:

• Hash-Based Partitioning:
• Reasoning: Hash-based partitioning is the best strategy for this problem, as it evenly distributes URLs across multiple servers, ensuring a balanced workload and efficient utilization of resources. This approach facilitates horizontal scalability and helps avoid hotspots, providing consistent and predictable performance for the web crawling system.
• Algorithm: For URL-based hashing in a web crawler system, a cryptographic hash function such as SHA-256 (Secure Hash Algorithm 256-bit) can be a suitable choice.

Sharding Strategy:

• Hash-Based Sharding:
• Reasoning: Hash-based sharding is the best strategy for this problem, as it distributes URLs, crawled data, and media files across shards based on a consistent hash function. This approach ensures even distribution, minimizes hotspots, and facilitates horizontal scalability, allowing the web crawler system to efficiently handle a large volume of data with balanced workloads.

Read/Write Separation:

• Implementing read/write separation is beneficial. Since web crawling involves heavy read operations for retrieving data, separating read and write operations can enhance performance, allowing the system to scale horizontally for read-intensive tasks without affecting write operations.

High-level design

1. Frontend Component:
2. Responsibility: Provides a user interface to the admin for interacting with the web crawler system, allowing users to initiate crawls using seed URLs, monitor progress, and configure crawling parameters.
3. Technologies: Web framework (e.g., React, Angular), API communication.
4. Crawler Controller:
5. Responsibility: Orchestrates the overall crawling process, manages the URL queue, and coordinates communication between components. This can be a scheduled or a queue based job which keeps polling for new urls in the queue.
6. Technologies: Node.js, Python, or another suitable backend language.
7. URL Queue:
8. Responsibility: Manages the queue of URLs to be crawled, enqueues new URLs, and dequeues URLs for processing.
9. Technologies: Distributed queue system (e.g., RabbitMQ, Apache Kafka).
10. Crawler Worker Nodes:
11. Responsibility: Actively crawls web pages, extracts data, and saves information to the database.
12. Technologies: Node.js, Python, or another suitable language for parallel processing.
13. URL Deduplication Service:
14. Responsibility: This service ensures that duplicate URLs are minimized to avoid redundant crawling.
15. Robots.txt Checker:
16. Responsibility: Checks robots.txt files for compliance with crawling rules before initiating the crawl. This will be used to define boundaries and rules for the crawl job.
17. Data Storage (Relational Database):
18. Responsibility: Stores URLs, crawled data, and metadata in a structured format for further analysis.
19. Technologies: PostgreSQL, MySQL.
20. Media Storage (Distributed File System):
21. Responsibility: Stores media files (images, videos) associated with crawled pages.
22. Technologies: Hadoop HDFS, Amazon S3.
23. Load Balancer:
24. Responsibility: Distributes incoming requests across multiple Crawler Worker Nodes to balance the workload.
25. Technologies: Nginx, HAProxy.
26. Monitoring and Logging:
27. Responsibility: Captures and logs system events, errors, and performance metrics for monitoring and troubleshooting.
28. Technologies: ELK Stack (Elasticsearch, Logstash, Kibana), Prometheus.
29. URL Extractor:
30. Responsibility: Extracts URLs from web pages to identify additional links for crawling.
31. Technologies: HTML parsing libraries (e.g., BeautifulSoup, jsoup).
32. Content Parser:
33. Responsibility: Parses HTML content to extract relevant information such as text, metadata, and links.
34. Technologies: HTML parsing libraries, regular expressions.
35. HTML Downloader:
36. Responsibility: Downloads HTML content from web pages for further processing.
37. Technologies: HTTP client libraries (e.g., axios, requests).
38. DNS Resolver:
39. Responsibility: Resolves domain names to IP addresses for efficient crawling and content retrieval.
40. Technologies: DNS resolution libraries, system-level DNS resolution.

Request flows

Check the below sequence diagram to see how the flow is orchestrated when a new url is being crawled.

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...

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

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

Future improvements

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