In this chapter, we focus on web crawler design: an interesting and classic system design interview question. A web crawler is known as a robot or spider. It is widely used by…
- 09.01Design a web crawlerIn this chapter, we focus on web crawler design: an interesting and classic system design interview question. A web crawler is known as a robot or spider. It is widely used by…
- 09.02Step 1 - Understand the problem and establish design scopeThe basic algorithm of a web crawler is simple: Given a set of URLs, download all the web pages addressed by the URLs.Extract URLs from these web pagesAdd new URLs to the list…
- 09.03Back of the envelope estimationThe following estimations are based on many assumptions, and it is important to communicate with the interviewer to be on the same page. Assume 1 billion web pages are…
- 09.04Step 2 - Propose high-level design and get buy-inOnce the requirements are clear, we move on to the high-level design. Inspired by previous studies on web crawling [4] [5], we propose a high-level design as shown in Figure…
- 09.05Step 3 - Design deep diveUp until now, we have discussed the high-level design. Next, we will discuss the most important building components and techniques in depth: Depth-first search (DFS) vs…
- 09.06DFS vs BFSYou can think of the web as a directed graph where web pages serve as nodes and hyperlinks (URLs) as edges. The crawl process can be seen as traversing a directed graph from…
- 09.07URL frontierURL frontier helps to address these problems. A URL frontier is a data structure that stores URLs to be downloaded. The URL frontier is an important component to ensure…
- 09.08HTML DownloaderThe HTML Downloader downloads web pages from the internet using the HTTP protocol. Before discussing the HTML Downloader, we look at Robots Exclusion Protocol first. Robots.txt…
- 09.09RobustnessBesides performance optimization, robustness is also an important consideration. We present a few approaches to improve the system robustness: Consistent hashing: This helps to…
- 09.10ExtensibilityAs almost every system evolves, one of the design goals is to make the system flexible enough to support new content types. The crawler can be extended by plugging in new…
- 09.11Detect and avoid problematic contentThis section discusses the detection and prevention of redundant, meaningless, or harmful content. 1. Redundant content As discussed previously, nearly 30% of the web pages are…
- 09.12Step 4 - Wrap upIn this chapter, we first discussed the characteristics of a good crawler: scalability, politeness, extensibility, and robustness. Then, we proposed a design and discussed key…
References
Step 4 - Wrap up
- US Library of Congress: https://www.loc.gov/websites/
- EU Web Archive: http://data.europa.eu/webarchive
- Digimarc: https://www.digimarc.com/products/digimarc-services/piracy-intelligence
- Heydon A., Najork M. Mercator: A scalable, extensible web crawler World Wide Web, 2 (4) (1999), pp. 219-229
- By Christopher Olston, Marc Najork: Web Crawling. http://infolab.stanford.edu/~olston/publications/crawling_survey.pdf
- 29% Of Sites Face Duplicate Content Issues: https://tinyurl.com/y6tmh55y
- Rabin M.O., et al. Fingerprinting by random polynomials Center for Research in Computing Techn., Aiken Computation Laboratory, Univ. (1981)
- B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Communications of the ACM, vol. 13, no. 7, pp. 422–426, 1970.
- Donald J. Patterson, Web Crawling: https://www.ics.uci.edu/~lopes/teaching/cs221W12/slides/Lecture05.pdf
- L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank citation ranking: Bringing order to the web,” Technical Report, Stanford University, 1998.
- Burton Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), pages 422--426, July 1970.
- Google Dynamic Rendering: https://developers.google.com/search/docs/guides/dynamic-rendering
- T. Urvoy, T. Lavergne, and P. Filoche, “Tracking web spam with hidden style similarity,” in Proceedings of the 2nd International Workshop on Adversarial Information Retrieval on the Web, 2006.
- H.-T. Lee, D. Leonard, X. Wang, and D. Loguinov, “IRLbot: Scaling to 6 billion pages and beyond,” in Proceedings of the 17th International World Wide Web Conference, 2008.