Crawling and graph exploration over services

intermediateCommon atAnthropicOpenAIGoogleMetaRead firstBFSQueuesConcurrencyPractise in the Sandbox →

A crawler is BFS over a graph you discover as you go: a frontier (queue) of URLs to fetch and a seen set keyed by a canonical form of each URL, so every page is fetched once. Real crawls add bounded concurrency (at most k fetches in flight) and politeness (limits per host). Time is O(V + E) fetches and link checks; the practical limits are latency, memory for the seen set, and not hammering anyone’s server.

The idea in plain words

You are exploring a city with no map. At each intersection you can see only the streets leaving it. You keep a notebook of intersections you have already been told about (the seen set) and a to-do list of ones you haven’t visited yet (the frontier). Every time you arrive somewhere, you write down the new streets and add the unfamiliar ones to the list.

Three things make it more than textbook BFS:

• Names are messy. https://A.com/about, https://a.com/about#team and https://a.com/./about are the same page. If your notebook uses raw strings, you visit it three times.
• Visiting is slow. A fetch takes tens or hundreds of milliseconds, so you want many at once, but not unlimited.
• The places are other people’s servers. Ten simultaneous requests to one small site is rude, and may get you blocked.

See it

Run the clock. Yellow nodes are discovered and waiting in the frontier; purple ones are being fetched. Then try: turn normalisation off and watch red duplicate fetches waste workers; move workers from 1 to 4 and compare the finish tick; turn on polite mode and raise the gap.

A crawler over a fake web: frontier, seen set, workers, politeness

run the clock

workers = 3

normalise URLs polite (1 fetch per host)

a.com · 2 ticks/fetchb.com · 3 ticksc.com · 1 tick

in flight

a.com/ → t2(1/3 workers)

frontier

empty

fetched0

wasted_fetches0

links_skipped_as_seen0

max_per_host1

finishedno

not discovereddiscovered, queuedfetchingfetching a duplicatefetched

t = 0. start a.com/ (2 ticks).

↺◀▶ Run▶tick 0 / 9

Notice that with politeness on, extra workers stop helping: the slow host b.com becomes the bottleneck, because only one of its pages can be fetched at a time. That is the real-world shape of crawls: total time is set by the slowest, largest host.

When to reach for it

The problem says…	Why this fits
“starting from X, find everything reachable” through a service/API	Graph exploration where edges are revealed only by calling the service.
“each page / node must be fetched at most once”	A seen set, checked when discovered, not when fetched.
“same URL in different spellings”	Canonicalise before inserting into the seen set.
“fetches are slow; run up to k at once”	A worker pool or a semaphore around the fetch.
“don’t overload any one host”	Per-host limits: one in flight, a minimum gap, or a token bucket per host.
“stop after depth d / N pages”	BFS gives depth for free: store it with each frontier entry.

How it works

1. Canonicalise the start URL, add it to seen, push it on the frontier.
2. While the frontier is non-empty and a worker is free, pop a URL that is allowed to start (politeness), and fetch it.
3. When a fetch completes, extract its links, resolve each against the page’s URL, and canonicalise.
4. For each link that passes your scope filter (same host, allowed scheme, depth limit) and is not in seen: add it to seen and push it on the frontier.
5. Stop when the frontier is empty and nothing is in flight. Either alone is not enough: an in-flight fetch can still discover pages.

Canonical URLs

What counts as “the same page” is a decision, and you should ask about it. The safe, standard steps (RFC 3986, section 6) are: lowercase the scheme and host, drop the default port, remove . and .. segments, drop the fragment. Riskier steps change meaning on some sites: lowercasing the path, removing a trailing slash, sorting or deleting query parameters. Each language’s URL parser does most of the safe work for you.

Python

normalize.py

# Turn a link found on a page into one canonical absolute URL, so the "seen" set dedupes it.
from urllib.parse import urljoin, urlsplit, urlunsplit

DEFAULT_PORTS = {"http": 80, "https": 443}


def remove_dots(path: str) -> str:
    out: list[str] = []
    for seg in path.split("/")[1:]:
        if seg == "..":
            if out:
                out.pop()  # ".." climbs one level, never above the root
        elif seg != ".":
            out.append(seg)
    res = "/" + "/".join(out)
    return res + "/" if path.endswith(("/.", "/..")) and not res.endswith("/") else res


def normalize(base: str, href: str) -> str | None:
    url = urljoin(base, href)  # 1. resolve relative links ("../api") against the page URL
    parts = urlsplit(url)
    scheme = parts.scheme.lower()
    if scheme not in DEFAULT_PORTS:
        return None  # 2. skip mailto:, javascript:, ftp: ...
    host = (parts.hostname or "").lower()  # 3. host names are case-insensitive; paths are not
    if parts.port and parts.port != DEFAULT_PORTS[scheme]:
        host = f"{host}:{parts.port}"  # 4. keep only non-default ports
    path = remove_dots(parts.path or "/")  # urljoin skips this for absolute hrefs
    # 5. drop the fragment: "#top" is the same document
    return urlunsplit((scheme, host, path, parts.query, ""))


if __name__ == "__main__":
    page = "https://a.com/docs/guide/"
    assert normalize(page, "../api?x=1#top") == "https://a.com/docs/api?x=1"
    assert normalize(page, "HTTP://Example.COM:80/a/./b/../c#frag") == "http://example.com/a/c"
    assert normalize(page, "https://a.com") == "https://a.com/"
    assert normalize(page, "//cdn.a.com:8443/x") == "https://cdn.a.com:8443/x"  # scheme-relative
    assert normalize(page, "/Docs") != normalize(page, "/docs")  # paths stay case-sensitive
    assert normalize(page, "mailto:hi@a.com") is None
    print("ok")

TypeScript

normalize.ts

import assert from "node:assert/strict";

// Turn a link found on a page into one canonical absolute URL, so the "seen" set dedupes it.
// The WHATWG URL parser already lowercases the host, drops default ports and resolves "./" and "../".
export function normalize(base: string, href: string): string | null {
  let url: URL;
  try {
    url = new URL(href, base); // 1. resolve relative links against the page URL
  } catch {
    return null; // malformed link: skip it rather than crash the crawl
  }
  if (url.protocol !== "http:" && url.protocol !== "https:") return null; // 2. skip mailto: etc.
  // 3-4. host lowercased and default port removed by the parser
  url.hash = ""; // 5. drop the fragment: "#top" is the same document
  return url.href;
}

const page = "https://a.com/docs/guide/";
assert.equal(normalize(page, "../api?x=1#top"), "https://a.com/docs/api?x=1");
assert.equal(normalize(page, "HTTP://Example.COM:80/a/./b/../c#frag"), "http://example.com/a/c");
assert.equal(normalize(page, "https://a.com"), "https://a.com/");
assert.equal(normalize(page, "//cdn.a.com:8443/x"), "https://cdn.a.com:8443/x"); // scheme-relative
assert.notEqual(normalize(page, "/Docs"), normalize(page, "/docs")); // paths stay case-sensitive
assert.equal(normalize(page, "mailto:hi@a.com"), null);
console.log("ok");

C#

normalize.cs

// Turn a link found on a page into one canonical absolute URL, so the "seen" set dedupes it.
// System.Uri lowercases scheme and host, drops default ports and resolves "./" and "../".
static string? Normalize(string baseUrl, string href)
{
    // 1. resolve relative links against the page URL; malformed links are skipped
    if (!Uri.TryCreate(new Uri(baseUrl), href, out var url)) return null;
    if (url.Scheme != Uri.UriSchemeHttp && url.Scheme != Uri.UriSchemeHttps) return null; // 2.
    // 3-4. host lowercased, default port removed; 5. GetLeftPart(Query) drops the fragment
    return url.GetLeftPart(UriPartial.Query);
}

var page = "https://a.com/docs/guide/";
Check(Normalize(page, "../api?x=1#top"), "https://a.com/docs/api?x=1");
Check(Normalize(page, "HTTP://Example.COM:80/a/./b/../c#frag"), "http://example.com/a/c");
Check(Normalize(page, "https://a.com"), "https://a.com/");
Check(Normalize(page, "//cdn.a.com:8443/x"), "https://cdn.a.com:8443/x"); // scheme-relative
if (Normalize(page, "/Docs") == Normalize(page, "/docs")) throw new Exception("paths are case-sensitive");
Check(Normalize(page, "mailto:hi@a.com"), null);
Console.WriteLine("ok");

static void Check(string? got, string? want)
{
    if (got != want) throw new Exception($"got {got}, want {want}");
}

Mark seen on discovery, not on fetch

If you add a URL to the seen set only when you fetch it, a page linked from ten places sits in the frontier ten times. With concurrency, two workers can even fetch it at the same moment. Insert into seen at the moment you push onto the frontier.

Bounded concurrency

The building block is “run these fetches, at most k at a time”. Python and C# have async semaphores; JavaScript doesn’t, so the idiomatic version is k workers pulling from a shared cursor. In a real crawler the list is not fixed up front, so workers pull from the frontier instead and the crawl ends when the frontier is empty and every worker is idle.

Python

fetch_all.py

# Fetch many URLs concurrently, but never more than `limit` at once.
import asyncio
from collections.abc import Awaitable, Callable


async def fetch_all(urls: list[str], fetch: Callable[[str], Awaitable[str]], limit: int) -> list[str]:
    gate = asyncio.Semaphore(limit)  # 1. `limit` permits; a task must hold one to fetch

    async def one(url: str) -> str:
        async with gate:  # 2. waits here while `limit` fetches are already running
            return await fetch(url)  # 3. permit released on exit, even on an exception

    # 4. gather keeps results in input order, whatever order the fetches finish in
    return await asyncio.gather(*(one(u) for u in urls))


async def main() -> None:
    in_flight = peak = 0

    async def fake_fetch(url: str) -> str:
        nonlocal in_flight, peak
        in_flight += 1
        peak = max(peak, in_flight)
        await asyncio.sleep(0.01 * (len(url) % 3 + 1))  # uneven latency
        in_flight -= 1
        return f"<html>{url}</html>"

    urls = [f"https://a.com/p{i}" for i in range(12)]
    pages = await fetch_all(urls, fake_fetch, limit=3)
    assert peak == 3  # concurrency was used, and capped
    assert pages[5] == "<html>https://a.com/p5</html>"  # order preserved


if __name__ == "__main__":
    asyncio.run(main())
    print("ok")

TypeScript

fetch_all.ts

import assert from "node:assert/strict";

// Fetch many URLs concurrently, but never more than `limit` at once.
// JS has no built-in semaphore; a pool of `limit` workers sharing one cursor does the job.
export async function fetchAll(urls: string[], fetch: (u: string) => Promise<string>, limit: number): Promise<string[]> {
  const results = new Array<string>(urls.length);
  let next = 0; // 1. shared cursor; safe without a lock because JS runs one callback at a time
  const worker = async (): Promise<void> => {
    while (next < urls.length) {
      const i = next++; // 2. claim an index synchronously, before any await
      results[i] = await fetch(urls[i]); // 3. while this waits, other workers run
    }
  };
  // 4. exactly `limit` workers means at most `limit` fetches in flight; results stay in input order
  await Promise.all(Array.from({ length: Math.min(limit, urls.length) }, worker));
  return results;
}

let inFlight = 0, peak = 0;
const sleep = (ms: number) => new Promise<void>((r) => setTimeout(r, ms));
const fakeFetch = async (url: string): Promise<string> => {
  inFlight++;
  peak = Math.max(peak, inFlight);
  await sleep(10 * ((url.length % 3) + 1)); // uneven latency
  inFlight--;
  return `<html>${url}</html>`;
};

const urls = Array.from({ length: 12 }, (_, i) => `https://a.com/p${i}`);
const pages = await fetchAll(urls, fakeFetch, 3);
assert.equal(peak, 3); // concurrency was used, and capped
assert.equal(pages[5], "<html>https://a.com/p5</html>"); // order preserved
console.log("ok");

C#

fetch_all.cs

// Fetch many URLs concurrently, but never more than `limit` at once.
int inFlight = 0, peak = 0;
async Task<string> FakeFetch(string url)
{
    int now = Interlocked.Increment(ref inFlight); // thread-pool continuations: use atomics
    InterlockedMax(ref peak, now);
    await Task.Delay(10 * (url.Length % 3 + 1)); // uneven latency
    Interlocked.Decrement(ref inFlight);
    return $"<html>{url}</html>";
}

var urls = Enumerable.Range(0, 12).Select(i => $"https://a.com/p{i}").ToList();
var pages = await Crawl.FetchAll(urls, FakeFetch, limit: 3);
if (peak != 3) throw new Exception($"peak was {peak}"); // concurrency used, and capped
if (pages[5] != "<html>https://a.com/p5</html>") throw new Exception("order lost");
Console.WriteLine("ok");

static void InterlockedMax(ref int target, int value)
{
    int seen;
    while ((seen = Volatile.Read(ref target)) < value && Interlocked.CompareExchange(ref target, value, seen) != seen) { }
}

static class Crawl
{
    public static async Task<string[]> FetchAll(IReadOnlyList<string> urls, Func<string, Task<string>> fetch, int limit)
    {
        using var gate = new SemaphoreSlim(limit); // 1. `limit` permits
        async Task<string> One(string url)
        {
            await gate.WaitAsync(); // 2. waits while `limit` fetches are running
            try { return await fetch(url); }
            finally { gate.Release(); } // 3. always give the permit back, even on failure
        }
        // 4. WhenAll returns results in input order, whatever order they finish in
        return await Task.WhenAll(urls.Select(One));
    }
}

Politeness

Common rules, often combined:

• At most one (or c) in-flight request per host. Keep a count per host; skip frontier entries whose host is busy, but don’t drop them.
• A minimum delay between requests to a host (Crawl-delay, or a fixed 1 s). Remember each host’s last start time.
• robots.txt: fetch it first for each host; obey Disallow rules for your user agent.
• Back off on 429 Too Many Requests or 503, honouring Retry-After.

Skipping a blocked entry while keeping its place in line matters. A single FIFO where the head is blocked would stall every other host (head-of-line blocking). Large crawlers (Mercator, Heritrix) keep one queue per host plus a heap of “host → next allowed time”, so picking the next fetch is O(log hosts) instead of a scan.

What it costs

	Time	Space	Note
BFS over V pages and E links	O(V + E) seen-set checks	O(V) seen + frontier	Every link costs one hash lookup, even if seen.
Wall-clock, k workers, latency L	about V·L / k, at best	O(k) in flight	Bounded below by the longest discovery chain × L.
With one-at-a-time per host	at least (pages on busiest host) × L		More workers stop helping.
Seen set at web scale		~billions of URLs	Hash the canonical URL to 8 bytes, or use a Bloom filter and accept rare misses.

Two lower bounds explain most crawl times. Depth: you cannot fetch a page before the page that links to it finishes, so a chain of d links costs at least d·L. Hosts: if one host has P pages and you allow one request at a time with gap g, that host alone needs about P·max(L, g).

Variations you’ll meet

• DFS instead of BFS: a stack frontier. Same set of pages, different order; BFS finds shallow, usually more important pages first and gives depth limits for free.
• Priority frontier: a heap by importance (PageRank estimate, freshness), as in focused crawlers.
• Graph exploration over APIs: following “next page” cursors, org charts, service dependency graphs, DNS aliases. Same shape: fetch, extract neighbours, dedupe, bound concurrency.
• Cycle and depth guards: following redirects or aliases needs a hop limit and a visited set per chain, or a loop never ends.
• Distributed crawling: partition URLs by host hash across machines, so each machine owns politeness for its hosts. See load balancing.

Pitfalls

• Termination with workers. “Frontier empty” while a fetch is still running is not done.
• Canonicalisation that’s too aggressive merges different pages; too weak fetches duplicates. Agree the rule.
• Relative links resolved against the wrong base (the start URL instead of the current page).
• Scope leaks: www.a.com vs a.com vs a.com:8080 are different hosts; decide which you treat as “same site”.
• Unbounded growth: calendars and session ids in URLs create infinite pages (“crawler traps”). Cap depth and pages per host.
• Shared state under real threads: with OS threads the seen set and counters need a lock (or a concurrent set); with asyncio or JS, check-then-insert without an await in between is atomic.

In the interview

• Ask: what makes two URLs the same? Stay on one host or follow everything? Is there a page or depth limit? How many fetches at once, and any per-host limit? What order must results come in?
• Say the invariant: “Every URL in the frontier or in flight is already in seen, and nothing in seen is ever pushed again.”
• Show you know the two bottlenecks (latency chain and the busiest host) when asked “how much faster with 10 workers?”.
• Expected follow-ups: add concurrency; add politeness; failures and retries with backoff; crawl at a billion pages (distributed frontier, Bloom-filter seen set, per-host partitioning).

Check yourself

Check yourself

pick one

With 4 workers, a crawl adds a URL to the seen set only when a worker starts fetching it. What can go wrong?

ANothing; it is just slowerBThe same URL can sit in the frontier many times, and duplicates waste workersCPages on other hosts are skipped

Check yourself

pick one

A site has 300 pages, each fetch takes 200 ms, and you allow one request at a time to it. You raise workers from 8 to 64. Roughly how long does that site take now?

AAbout 1 secondBAbout 8 secondsCStill about 60 secondsDIt depends on the frontier order only

Check yourself

pick one

Which pair of URLs should a standard normaliser treat as the same page?

Ahttps://a.com/Docs and https://a.com/docsBhttps://A.com:443/x#intro and https://a.com/xChttps://a.com/x?id=1 and https://a.com/x

Practice on your own

These are classic exercises, not gym questions:

• Crawl a local folder of HTML files (links as relative paths) and print the pages unreachable from index.html.
• Add a depth limit to BFS and return pages grouped by depth.
• Implement robots.txt Disallow prefix matching for one user agent.
• Write an async crawler against a local test server with a global limit of 10 and a per-host limit of 2; assert neither limit is ever exceeded.

Go deeper

• Heydon and Najork (1999), Mercator: A Scalable, Extensible Web Crawler: per-host queues and politeness.
• RFC 3986, section 6: URI normalisation and comparison; RFC 9309 for robots.txt.
• Python asyncio.Semaphore and urllib.parse; .NET SemaphoreSlim and System.Uri; the WHATWG URL standard.
• Manning, Raghavan and Schütze, Introduction to Information Retrieval, ch. 20 “Web crawling and indexes” (free online).

Related

Breadth-first searchThe traversal underneath, with depth and shortest hops.

Concurrency semanticsSemaphores, locks and what's atomic in each runtime.

Rate limitingPoliteness per host is a rate limit you apply to yourself.

Event-driven simulationModel fetches as timed events to reason about wall-clock time.