[System Design and Scalability] interview questions #3

[rygh4775]

Web Crawler: If you were designing a web crawler, how would you avoid getting into infinite loops?

[rygh4775]

How an infinite loop might occur

• Web = A graph of links
• Infinite loop with a cycle graph

Definitions

• Web graph
  • Edges can be directed ot not
  • Graph is higinly danamic
  • Nodes and edges are added/deleted often
  • Content of existing nodes is also subject to change
  • Pages and hyperlinks created on the fly
• Signature
  • URL + Section

Solution

• Have a database which stores a list of items we need to crawl
• Select the highest priority page to crawl

1. Open up the page and create a signature
2. Query the database to see whether anything with this signature has been crawled recently.
3. If something with this signature has been recently crawled, insert this page back int to the database at low priority.
4. If not, crawl the page and insert its links into the database.