notexOPENOverview
Notex/Systems/Design a web crawler

Design a web crawler

Always free to read

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

DESIGN CASE STUDIES

Design a web crawler

12 LESSONS · 22 MIN
  1. 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…READING2 MIN
  2. 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…READING2 MIN
  3. 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…READING1 MIN
  4. 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…READING5 MIN
  5. 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…READING1 MIN
  6. 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…READING1 MIN
  7. 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…READING3 MIN
  8. 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…READING2 MIN
  9. 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…READING1 MIN
  10. 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…READING1 MIN
  11. 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…READING1 MIN
  12. 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…READING2 MIN

References

Step 4 - Wrap up
  1. US Library of Congress: https://www.loc.gov/websites/
  2. EU Web Archive: http://data.europa.eu/webarchive
  3. Digimarc: https://www.digimarc.com/products/digimarc-services/piracy-intelligence
  4. Heydon A., Najork M. Mercator: A scalable, extensible web crawler World Wide Web, 2 (4) (1999), pp. 219-229
  5. By Christopher Olston, Marc Najork: Web Crawling. http://infolab.stanford.edu/~olston/publications/crawling_survey.pdf
  6. 29% Of Sites Face Duplicate Content Issues: https://tinyurl.com/y6tmh55y
  7. Rabin M.O., et al. Fingerprinting by random polynomials Center for Research in Computing Techn., Aiken Computation Laboratory, Univ. (1981)
  8. 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.
  9. Donald J. Patterson, Web Crawling: https://www.ics.uci.edu/~lopes/teaching/cs221W12/slides/Lecture05.pdf
  10. L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank citation ranking: Bringing order to the web,” Technical Report, Stanford University, 1998.
  11. Burton Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), pages 422--426, July 1970.
  12. Google Dynamic Rendering: https://developers.google.com/search/docs/guides/dynamic-rendering
  13. 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.
  14. 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.
KEEP EXPLORING

One note leads to another.

Back to the library →
⌕
Search across the entire library ⌘ K