In a web crawler, what job does the URL frontier do beyond holding a list of URLs to fetch?
answer
- scheduler, not just storage
- which URL next, and when
- links cluster on one host
- value signals vs equal treatment
- billions of entries, disk-backed
basics
~20 sThe URL frontier holds every discovered but unfetched URL and decides what to fetch next and when: it orders URLs by priority and spaces out requests to each host, so the crawler stays polite and spends its budget on valuable pages.
solid answer
~40 sA crawler loops: take a URL from the frontier, check robots.txt, fetch, parse, extract links, normalise them, drop the ones already seen, and add the new ones back. A plain FIFO queue gives a breadth-first crawl, but at web scale it fails twice: it treats a spam page's links the same as an important site's, and because pages link mostly within their own site, long runs of the queue belong to one host, so many fetchers would hit that host at once. So the frontier has two jobs: **prioritisation** (which URL is worth fetching next) and **politeness** (one connection per host at a time, with a delay between fetches). It usually sits behind a seen-URL set so each URL is admitted once, and it is disk-backed because it holds billions of entries.
go deeper
Recall the crawl loop and name the frontier's two jobs: choosing what to fetch next and deciding when each host may be fetched again.
Explain why FIFO fails at scale: links cluster on their own host, and a queue has no notion of page value or per-host timing.
Talk about operating it: disk-backed queues with in-memory heads, checkpointing for restarts, and host-based partitioning so politeness stays local to one node.
Frame the frontier as the place where crawl strategy lives, trading coverage of new pages against freshness of known ones under a fixed fetch budget.
## What a web crawler does A **web crawler** (also called a spider) discovers and downloads web pages so that something downstream, usually a search engine's indexer, can process them. It starts from a list of **seed URLs** and follows links outward. The component that remembers which URLs are waiting to be downloaded is the **URL frontier**. The basic crawl loop is: 1. Take the next URL from the frontier. 2. Check the host's `robots.txt` rules to see whether the URL may be fetched. 3. Fetch the page over HTTP. 4. Parse the page and extract its outgoing links. 5. **Normalise** each link into one canonical spelling. 6. Drop links already present in the **seen-URL set**. 7. Add the remaining new URLs to the frontier. Every step in that loop is simple on its own. The frontier is where the hard decisions live, because it decides the *order* and the *timing* of billions of fetches. ## Why a plain FIFO queue is not enough The textbook starting point is a first-in, first-out queue, which produces a breadth-first crawl. That works for a toy crawl of a few thousand pages, but it breaks at web scale for several reasons: - **No notion of value.** A FIFO treats a link found on a spam page exactly like a link found on a major news site. With a finite fetch budget, the crawler wastes capacity on low-value pages. - **Host clustering.** Most links on a page point to the same site. When a page with 500 internal links is parsed, 500 consecutive queue entries belong to one host. Several fetcher threads draining that stretch would hit the same server in parallel, which looks like an attack and can take a small site down. - **No timing control.** A queue says *what* comes next but not *when* it is allowed. Politeness needs a notion of time per host. - **Size.** A web-scale frontier can hold billions of URLs. Assuming an average of about 100 bytes per URL, 5 billion queued URLs is about 500 GB, far more than fits in one machine's memory. ## The two jobs: priority and politeness A real frontier therefore combines two concerns that pull in different directions. | Concern | Question it answers | Typical signals or rules | |---|---|---| | **Prioritisation** | Which URL is most worth fetching next? | link-based importance, how often the page changes, whether it is new or a recrawl, host quality | | **Politeness** | When may this host be contacted again? | at most one open connection per host, a minimum delay between fetches, the host's `robots.txt` rules | Prioritisation alone would send all fetchers to the most important site at once. Politeness alone would spread load evenly but crawl junk as eagerly as valuable pages. A good frontier design, usually built from priority queues feeding per-host queues, lets both hold at the same time: priority decides which URLs move forward, and a per-host clock decides when each one may actually be fetched. ## Scale and persistence Because the frontier is large and the crawl runs for weeks or months, it is built to survive both size and failure: - **Disk-backed queues.** Only the heads of the queues are kept in memory; the bulk lives on disk and is read in large sequential batches. - **Crash recovery.** If a crawler node restarts, it must resume without losing millions of discovered URLs or refetching everything, so the frontier state is persisted and checkpointed. - **Partitioning.** A distributed crawler splits the frontier across machines, typically by hashing the **host name**, so every URL for one host lands on the same node. That keeps politeness decisions local: one node owns each host's clock. ## What the frontier is not It helps to keep the boundaries clear: - It is **not** the deduplication store. The seen-URL set remembers every URL ever admitted, including those already fetched and gone from the queues; scanning the queue itself would miss them. - It does **not** parse pages or build the search index; those are separate stages downstream of the fetcher. - It does **not** detect duplicate *content*. Two different URLs serving the same page are caught later by content fingerprints, not by the frontier. A useful one-line summary for an interview: *the frontier is the crawler's scheduler, deciding which URL to fetch next and when each host may be touched again, at a size that forces it onto disk.*
- Why must a web-scale URL frontier be persistent rather than purely in memory?Two reasons. Size: billions of queued URLs at roughly 100 bytes each run to hundreds of gigabytes, so only queue heads stay in memory while the rest is read from disk in sequential batches. Durability: a crawl runs for weeks, and a node restart must resume without losing discovered URLs or starting over, so the frontier is persisted and checkpointed.
- How does a distributed crawler split the URL frontier across machines?It partitions by host, usually by hashing the host name onto nodes, often with consistent hashing so adding a node moves only a slice of hosts. Every URL for a host lands on the node that owns it, so that node alone tracks the host's politeness clock. A node that extracts a link to a host it does not own forwards the URL to the owning node, typically in batches.
saying these in an interview costs you the question
- A plain FIFO queue of URLs is enough for a web-scale crawl.
- One global delay between all fetches is enough to be polite to every site.
- The whole frontier can live in memory on a single machine.
- Scanning the frontier queue for a URL is enough to avoid refetching it.
- Priority just means crawling shallow URLs before deep ones.