Design a web crawler
A BFS frontier, politeness delays per host, and dedup with a bloom filter - crawl a tiny web without hammering any one domain.
9 min read
A crawler is a breadth-first search with two guards and one set of manners. The search is the easy part. The guards stop it looping forever, and the manners stop every site you touch from blocking you.
Follow every link and you never stop
The core loop fits on a napkin: take a URL off the frontier queue, download it, pull out its links, put the new ones on the back of the queue. The web is a graph full of cycles, though, and two pages linking to each other is enough to make that loop run forever.
The visited set stops you fetching the same URL twice, which is what makes the crawl end. The content-seen check stops you storing the same page twice, which is a different problem: page G here serves the same content as C under another URL, and a large share of the web is duplicated this way. At real scale both are bloom filters, because an exact set of billions of URLs does not fit in memory.
A correct crawler is indistinguishable from a denial of service
BFS has no idea whose server it is talking to. With 500 workers pulling from one shared queue, a site whose pages entered the queue together gets hit by the whole pool at once, and from the other side that looks exactly like an attack.
Politeness is measured in requests per second and coverage in pages per day, and they are the same number. The only way to be both fast and polite is to crawl thousands of sites in parallel, each slowly. So a real frontier is not one queue: a front set of queues ranks URLs by priority (a news site is revisited far more often than an archive), and a back set has one queue per site with one worker bound to each, plus a delay taken from robots.txt where it is given. The BFS is still in there, wearing a scheduler.
Some pages exist only to waste your crawler's time
A crawler meets hostile, broken and effectively infinite input, and most of the code in a production crawler is not the search but the defences. The classic example is a calendar whose “next month” link goes on forever.
That spider trap beats both guards: every URL really is new, and every page really is different. Depth limits only help if the trap is deep rather than wide. The defences that work are blunt, like per-site budgets, and they sit alongside a handful of other hazards every crawler has to handle.
The graph traversal is an afternoon of work. The year of work is the scheduler, the politeness, the duplicate detection, the trap budgets, the robots.txt cache, the recrawl policy and the storage. That ratio, a trivial core and an enormous perimeter, is what makes a crawler a system design question.
The short version
- A crawler is BFS over a frontier queue; a visited set makes it terminate.
- A content check catches the same page under different URLs.
- Use one queue and one worker per site, with a delay, so you never flood anyone.
- Spider traps defeat both guards; per-site URL budgets stop them.