Part 4 of 7 · 3 min read
The frontier
Breadth first, polite and prioritised.
DFS or BFS. The web is a directed graph: pages are nodes and links are edges. A crawl is a walk through it. Depth-first search can go very deep and get lost, so it is not a good choice. Breadth-first search, with a first-in first-out queue, is the usual choice.
A plain queue has two problems, the book says.
- Impolite. Most links on a page point to the same site. A plain queue would hand many URLs from one host to many parallel downloaders, flooding that host.
- No priority. A forum post about Apple products and the Apple home page are not equally important. A plain queue treats them the same.
A URL frontier solves both, and also handles freshness.
Politeness. The idea is that one host is visited by one worker at a time, with a pause between fetches. The book's design:
- A queue router puts each URL into a queue that holds only URLs of one host.
- A mapping table says which host belongs to which queue.
- Back queues b1 to bn are first-in first-out queues, each holding one host's URLs.
- A queue selector gives each worker thread one queue. The worker takes URLs only from that queue, one at a time, with a delay.
A worked example (made up). A worker takes about 0.5 s to download a page and then waits 1 s before the next page from the same host, so it does one page per 1.5 s, which is 0.67 pages per second. To reach the peak of 800 pages per second, the crawler needs 800 / 0.67 = 1,200 worker threads, each on a different host. If each server runs 100 threads, that is 12 servers. The politeness delay is what forces the large number of threads.
Priority. A prioritiser gives each URL a score from usefulness signals such as PageRank, traffic or how often a page changes. There are front queues f1 to fn, one per priority. A selector picks a queue at random but more often from the high-priority ones.
The frontier has two layers: front queues manage priority, and back queues manage politeness. A URL goes through the prioritiser to a front queue, is picked by the selector, then goes through the router into the back queue for its host.
Freshness. Pages change, so they must be crawled again. Re-crawling everything is costly. The book suggests two ways: use each page's update history, and re-crawl important pages sooner and more often.
Storage of the frontier. There can be hundreds of millions of URLs. Memory alone is not durable or big enough. Disk alone is too slow. The book's answer is hybrid: most URLs on disk, with in-memory buffers for adding and removing, written to disk now and then.
URL frontier
A URL frontier is the structure that holds the URLs still to be downloaded and decides which comes next, balancing priority, politeness and freshness.
Example: front queues ranked by importance, feeding back queues that each hold one website's pages.
Check yourself: 1. Why is DFS a poor choice? 2. How does a back queue enforce politeness? 3. Why does the example need 1,200 threads?