In a web crawler handling billions of URLs, how do URL normalisation and a seen-URL set keep it from fetching the same URL twice?
answer
- many spellings, one resource
- safe rules from the URI standard
- per-host rules for query parameters
- fixed-size hash, not the string
- filter false positive means a skip
basics
~20 sNormalisation rewrites each URL into one canonical spelling (lowercase scheme and host, no default port or fragment, resolved dot segments, no session parameters); the crawler then checks a fingerprint of that form against a seen-URL set before admitting it to the frontier.
solid answer
~50 sLinks spell the same address in many ways, so the crawler first **normalises**. The URI standard makes some rules safe: lowercase the scheme and host, drop default ports like `:80` and `:443`, remove the `#fragment`, resolve `.` and `..` segments, and normalise percent-encoding. Other rules are heuristics that can merge different pages, such as stripping or sorting query parameters or dropping `www.`, so they are applied per host where observed content shows they are safe. The **seen-URL set** then stores a fixed-size hash of the normalised URL, not the string: 10 billion URLs at 8 bytes each is about 80 GB, against about 1 TB of raw 100-byte URLs. A bloom filter in front answers most lookups in memory; its rare false positives mean a new URL is skipped, a loss crawlers accept. Different URLs serving the same content are left to content fingerprinting.
go deeper
Recall that one page can have many URL spellings, and that the crawler cleans them up and remembers what it has already queued.
List the safe normalisation rules, explain why the seen set stores fixed-size hashes, and say what a filter false positive costs.
Show judgment on risky rules learned per host, batched sorted lookups against disk, and feeding content-fingerprint evidence back into normalisation.
Weigh the memory and disk budget of the seen set against the acceptable rate of skipped URLs, and decide where normalisation ends and content dedup begins.
## Why the same URL arrives in many spellings A web crawler discovers URLs by extracting links from pages, and the web is not consistent about how it writes them. All of these can point at one resource: - `HTTP://Example.COM/a/b` - `http://example.com:80/a/b` - `http://example.com/a/./c/../b` - `http://example.com/a/b#comments` - `http://example.com/a/b?sessionid=8f3a` Without cleanup, the crawler would treat each as new and fetch the same page several times, wasting its budget and the site's capacity. Two mechanisms work together: **URL normalisation** (make equivalent spellings identical) and a **seen-URL set** (remember every normalised URL already admitted). ## Normalisation: safe rules and risky rules The generic URI syntax standard defines equivalences that are always safe to apply: 1. Lowercase the **scheme** and the **host** (both are case-insensitive). 2. Remove a **default port** (`:80` for `http`, `:443` for `https`). 3. Remove the **fragment** (`#...`), which never reaches the server. 4. Resolve **dot segments** (`.` and `..`) in the path. 5. Decode percent-encoded **unreserved** characters and uppercase the hex digits of the rest. 6. Resolve **relative links** against the page's base URL. Other common rewrites change meaning on some sites and are only heuristics: | Rewrite | Why it helps | How it can go wrong | |---|---|---| | lowercase the path | merges case variants | paths are case-sensitive; two different pages collapse into one | | strip session and tracking parameters | removes endless variants | a parameter that looks like tracking may select content | | sort query parameters | merges reordered links | some applications treat order or repeats as meaningful | | drop `www.` or a trailing slash | merges host and directory variants | the two forms may be different sites or resources | A robust crawler applies the safe set everywhere and learns risky rules **per host**, for example by noticing that URLs differing only in a parameter keep producing identical content fingerprints. ## The seen-URL set at scale The seen set answers one question for every extracted link: *have we already admitted this URL?* At billions of URLs the representation matters. - **Store fingerprints, not strings.** A 64-bit hash of the normalised URL takes 8 bytes. For 10 billion URLs that is 80 GB, compared with about 1 TB if URLs average 100 bytes. With 64-bit hashes, collisions among 10 billion keys are possible but rare enough to accept. - **Arrange for locality.** Some designs build the fingerprint as a host hash followed by a path hash, so URLs of the same host sort together on disk and batched lookups read neighbouring blocks. - **Batch the lookups.** Rather than one random disk read per link, extracted URLs are buffered, sorted, and merged against the sorted on-disk set in a single sequential pass. - **Put a bloom filter in front.** Treated as a black box, a bloom filter answers *definitely not seen* in memory for most new URLs. When it answers *maybe seen*, the crawler either confirms against the disk set or simply treats the URL as seen. In the second case a false positive means a genuinely new URL is **skipped**, never fetched twice, which a crawler with more URLs than budget readily accepts. ## Where the check happens The check sits **before** admission to the frontier: 1. Extract a link and resolve it against the page. 2. Normalise it. 3. Fingerprint the normalised form. 4. If the fingerprint is in the seen set, drop the link. 5. Otherwise add the fingerprint to the set and enqueue the URL. Because the set remembers every admitted URL, including ones fetched long ago and no longer queued, scanning the frontier itself would not be enough. Recrawls are scheduled deliberately by a separate refresh policy, not by rediscovering a link. Keeping those two concerns apart matters: if rediscovery could re-admit a URL, every popular page linked from thousands of other pages would be queued thousands of times, and the refresh schedule would be driven by link counts instead of change rates. ## What this does not catch Normalisation compares **addresses**, not **content**. Mirrors, printer-friendly versions, and pages that differ only in an ad or a timestamp all have different URLs after normalisation. Those are caught by **content fingerprints** computed after the fetch, and the result often feeds back: when many URLs on a host keep producing the same fingerprint, the crawler learns a normalisation rule for that host or lowers its priority.
- What goes wrong if a crawler sorts query parameters as a global normalisation rule?Most servers ignore parameter order, but some applications treat order or repeated parameters as meaningful, so sorting can merge two different pages and one of them is never crawled. The safer approach is to learn the rule per host: if reordered variants keep returning identical content fingerprints, sorting is safe there.
- Why do crawlers batch seen-set lookups instead of checking each link as it is extracted?A seen set of tens of gigabytes lives mostly on disk, and one random read per link would cap throughput at the disk's seek rate. Buffering extracted fingerprints, sorting them, and merging them against the sorted on-disk set turns millions of random reads into one sequential pass, at the cost of a short delay before new URLs are admitted.
saying these in an interview costs you the question
- Lowercasing the entire URL, path included, is a safe normalisation.
- Storing full URL strings in the seen set is fine at billions of URLs.
- Normalisation alone catches every duplicate page on the web.
- Stripping every query parameter is always safe because they are just tracking.
- A bloom-filter false positive makes the crawler fetch a page twice.