Part 2 of 7 · 2 min read
Requirements and numbers
Fetch pages, follow links, repeat.
Think of a librarian who wants a catalogue of every book in a huge city of libraries. She starts at a few known libraries, copies down what is on the shelves, notes the other libraries mentioned in each book, and visits those next. She must not annoy any one library by visiting too often, must skip books she already copied, and must avoid a maze that leads in circles.
A web crawler, also called a robot or spider, does this for web pages. The book lists uses: search engine indexing (the most common), web archiving, web mining and web monitoring for copyright or trademark misuse.
The basic algorithm is simple:
- Take a set of URLs and download their pages.
- Extract the URLs found in those pages.
- Add the new ones to the list to be downloaded, and repeat.
The real system is hard because of scale and the nature of the web.
Questions and the answers assumed here (from the book's sample talk).
- Purpose? Search engine indexing.
- How many pages? 1 billion per month.
- Which content? HTML only.
- New and changed pages? Yes, they must be found.
- Store the pages? Yes, for up to 5 years.
- Duplicate pages? Ignore them.
Four qualities of a good crawler.
- Scalable: the web has billions of pages, so crawl in parallel.
- Robust: the web is full of bad HTML, silent servers, crashes and malicious links.
- Polite: do not hit a site with many requests in a short time.
- Extensible: adding a new content type should need little change.
Numbers.
- Pages per second: 1,000,000,000 / 30 / 24 / 3,600 = about 386, which the book rounds to 400. Peak is taken as double, 800.
- Average page size 500 KB (the book's assumption). One month is 1,000,000,000 × 500 KB = 500 TB.
- Five years: 500 TB × 12 × 5 = 30,000 TB, which is 30 PB.
Web crawler
A web crawler is a program that downloads web pages, finds the links in them, and follows those links to download more pages.
Example: the program a search engine uses to collect pages before it builds its index.
Check yourself: 1. Name two uses of a crawler besides search. 2. How many pages per second is 1 billion per month? 3. Why is the storage figure in petabytes?