skip to content

When a web crawler's URL frontier uses priority front queues and per-host back queues, how does it stay polite without losing prioritisation?

level: middleimportance: must knowfreq 55%

answer

  1. two tiers, in and out
  2. front: one queue per priority
  3. back: one host per queue
  4. heap keyed by next allowed time
  5. delay scales with last fetch duration

basics

~20 s

Priority front queues feed back queues that each hold one host, pulled with a bias toward high priority. A heap keyed by each host's next allowed fetch time picks the host to serve, so no host is hit concurrently or too soon.

solid answer

~40 s

The frontier has two tiers. **Front queues** are one queue per priority level; a prioritiser assigns each new URL a level from signals such as link-based importance and change rate. **Back queues** each hold URLs of exactly one host, and a table maps host to queue. A **min-heap** holds one entry per host, keyed by the earliest time that host may be fetched again. A fetcher pops the heap, waits until that time, takes the head URL, and when the fetch finishes the host goes back on the heap at `now + delay`, often a multiple of the last fetch's duration. When a back queue runs empty, it is refilled from the front queues, biased toward high priority. Priority decides *what* reaches the back tier; the heap decides *when* each host is touched.

code

pseudocode · 27 lines
pseudocode
function nextUrl():
  loop:
    (readyAt, host) = readyHeap.peekMin()
    if now() < readyAt:
      waitUntil(readyAt)
      continue
    readyHeap.popMin()              // host leaves heap while in flight
    return backQueues[host].popHead()

function onFetchDone(host, elapsed):
  nextAllowed[host] = now() + max(minDelay, k * elapsed)
  if backQueues[host].isEmpty():
    delete backQueues[host]
    refillOneBackQueue()
  else:
    readyHeap.push((nextAllowed[host], host))

function refillOneBackQueue():
  while not frontQueues.allEmpty():
    url = frontQueues.popBiasedTowardHighPriority()
    h = hostOf(url)
    if h in backQueues:
      backQueues[h].append(url)
    else:
      backQueues[h] = newQueue(url)
      readyHeap.push((max(now(), nextAllowed.getOrDefault(h, 0)), h))
      return

go deeper

for a junior

Remember the shape: priority queues on the way in, one queue per host on the way out, and a timer per host.

for a middle

Walk through the fetch cycle: pop the heap, wait, fetch, push the host back at now plus delay, and refill a back queue when one empties.

for a senior

Show operational judgment: delay proportional to response time, per-IP caps for shared hosting, cached robots.txt, and back-queue count sized against fetcher threads.

for a principal

Discuss how the priority bias and per-host budgets together decide crawl coverage, and how host-based partitioning removes cross-node coordination for politeness.

## The problem the two tiers solve A web crawler's **URL frontier** must satisfy two goals that conflict: - **Prioritisation**: fetch the most valuable URLs first, because the fetch budget is finite. - **Politeness**: never open more than one connection to a host at a time, and leave a gap between fetches so the crawler does not overload anyone's server. A single priority queue fails politeness, because the top of the queue may be a hundred URLs from one important site. A round-robin over hosts fails prioritisation, because it treats a junk host like a major one. The classic answer is a **two-tier frontier**: priority on the way in, per-host timing on the way out. ## Front queues: priority The front tier is a set of **F front queues**, one per priority level. - A **prioritiser** gives each newly admitted URL a level, using signals such as link-based page importance, the page's observed change rate, the quality of its host, and whether it is a new discovery or a recrawl. - The URL is appended to the front queue for that level. - A **front-queue selector** pulls from these queues with a bias toward high priority, for example by picking a queue at random with probability weighted toward the top levels. The bias matters: strict priority would starve low levels forever, while weighted selection still lets them move. ## Back queues: one host each The back tier is a set of **B back queues** with two invariants: 1. Each back queue is kept **non-empty**: once its last URL has been fetched, it is released and a queue for another host takes its place. 2. Each back queue holds URLs from **exactly one host**. A **host table** maps each host to its back queue. When the selector pulls a URL whose host already has a back queue, the URL is simply appended to that queue. When the host has no queue, the URL starts one. A **min-heap** holds one entry per back queue, keyed by the **earliest time** that queue's host may be contacted again. That heap is what enforces politeness. ## The fetch cycle 1. A fetcher thread pops the heap entry with the smallest time. 2. If that time is still in the future, it waits until then. 3. It takes the head URL from that host's back queue and fetches it. While the fetch is in flight, the host is not in the heap, so no other thread can reach it. 4. When the fetch completes, the host's next allowed time is set to `now + delay`. 5. If the back queue still has URLs, the host goes back on the heap with that time. If it is empty, the queue is released and the selector refills a back queue by pulling from the front queues until it finds a URL for a host that has no back queue yet. A common heuristic sets the delay to a **multiple of the last fetch's duration** (for example ten times), with a floor. A slow response suggests a loaded server, so it automatically earns a longer pause. Some crawlers also honour a nonstandard `Crawl-delay` line from `robots.txt` when a site declares one. ## Sizing and edge cases | Parameter | Effect if too small | Effect if too large | |---|---|---| | number of back queues B | fetchers sit idle waiting on few hosts | memory and heap overhead, and priority is diluted | | politeness delay | servers get hammered | throughput per host collapses | | number of priority levels F | coarse ordering | selector overhead with little benefit | A common rule of thumb keeps **B at a few times the number of fetcher threads**, so there is nearly always some host whose timer has expired. Other points worth raising: - **robots.txt** is fetched once per host and cached, and each URL is checked against it before fetching, not refetched for every page. - **Host versus IP.** Many virtual hosts share one server address, so large crawlers often add a per-IP concurrency cap on top of the per-host one, backed by a DNS cache. - **Huge hosts.** A host with millions of queued URLs just has a long back queue; its throughput is capped by the delay, which is why per-host crawl budgets matter. - **Distribution.** When the frontier is partitioned by host across machines, each node owns its hosts' heaps entirely, so no cross-node coordination is needed for politeness. The result: priority determines **which URLs reach the back tier and in what order within a host**, while the heap determines **when each host is touched**. Neither goal is sacrificed.

  • How does robots.txt fit into a frontier with per-host back queues?
    It is fetched once per host (per scheme, host and port) and cached, and every URL is checked against the cached rules before it is fetched. The robots.txt standard says a 4xx response means no restrictions, while a server error or unreachable file means assume everything is disallowed. It also says a cached copy should generally not be used for more than about a day, so the crawler refreshes it on that schedule.
  • Why do large crawlers often cap concurrency per IP address as well as per host?
    Many virtual hosts can sit behind one server address on shared hosting. Per-host politeness alone could send one fetch to each of hundreds of those hosts at the same moment, all landing on the same machine. Resolving hosts through a DNS cache and adding a per-IP connection cap protects the physical server as well as each site name.
  • What stops strict priority from starving low-priority front queues forever?
    The front-queue selector is biased, not strict: it picks a queue with probability weighted toward higher levels, so lower levels still get pulled occasionally. Some designs also age URLs upward over time. Strict priority would leave low-level URLs untouched as long as high-level ones keep arriving, which on the web is always.

It works like a clinic with triage and doctors' appointment books: triage decides which patients are most urgent, but each doctor still sees one patient at a time and needs a short break between appointments.

saying these in an interview costs you the question

  • A single priority queue can enforce politeness on its own.
  • Politeness just means a fixed global sleep between all fetches.
  • Several fetcher threads may pull from one host's queue at the same time.
  • Front queues are per host and back queues are per priority level.
  • robots.txt must be fetched again before every page request.