Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Redo the numbers (20 minutes)
A crawler fetches 3 billion pages per month, 300 KB each, kept for 2 years. Give pages per second, peak, storage per month and total.
Done when: you write about 1,157 per second, 2,315 peak, 900 TB per month and 21.6 PB.
Hint
3,000,000,000 / 2,592,000 seconds in 30 days is about 1,157.
Easy 2: Trace a URL (20 minutes)
Write the eleven workflow steps in your own words, and mark which two are checks that can stop a page or URL.
Done when: eleven steps, with Content Seen? and URL Seen? marked.
Hint
Both checks come after a step that produces something new.
Easy 3: Thread count (20 minutes)
A worker takes 0.4 s per page and waits 2 s between pages of the same host. How many threads give 600 pages per second?
Done when: you write 2.4 s per page, 0.417 pages per second per thread, and 1,440 threads.
Hint
0.4 + 2 = 2.4 seconds per page per thread.
Medium
Medium 1: Draw the frontier (30 minutes)
Draw the front queues, back queues, router, mapping table and selectors. Mark where priority and politeness are enforced.
Done when: a diagram with at least eight labelled parts and the two roles marked.
Hint
Back queues each hold one host.
Medium 2: Bloom filter sizing (30 minutes)
For 10 billion URLs and a 0.1 per cent false positive rate, estimate bits per URL (about 14.4 bits) and total size.
Done when: you write about 14.4 bits per URL and about 18 GB.
Hint
Bits per element is about -ln(p) divided by (ln 2) squared.
Medium 3: Trap rules (30 minutes)
List five rules to limit spider traps, such as a URL length cap, with the cost of each.
Done when: five rules, each with a side effect, such as skipping legitimate long URLs.
Hint
Think about URL length, depth, pages per site and repeated path segments.
Hard
Hard 1: Mini crawler (90 minutes)
Write a crawler for a small local test site you control. It must obey robots.txt, keep one queue per host with a delay, skip seen URLs and duplicate content, and stop after 500 pages.
Done when: it fetches the site with no repeats, respects the delay in a log, and handles a planted trap.
Hint
Use a local test server so no real site is hit.
Hard 2: Re-crawl policy (60 minutes)
Design a re-crawl schedule using update history. Pages that changed in the last 3 visits are visited daily, and stable ones weekly or monthly. Show the load on a million pages.
Done when: a table of classes with page counts, visit intervals and fetches per day.
Hint
Count pages in each class, then divide by the interval.
Hard 3: Mock interview (60 minutes)
Answer "design a web crawler" aloud in 35 minutes and mark yourself on the four steps. List two missed topics.
Done when: a recording, a score on each step, and two named gaps.
Hint
Use the four-step framework as a checklist.