R22 — Lookup and discovery: URL shortener, typeahead, proximity search, web crawler

R21 was about moving huge numbers of events. This section is about finding things: a long URL from a short key, the queries that start with what you have typed, the restaurants within two kilometres, the pages that contain a word. These are some of the most common warm-up questions in a design round, and they share one idea.

The format is the same as R18 to R21: the shared problem and its toolkit first, then four walkthroughs, each adding one difficulty to the last.

The shared concern — answer in milliseconds by deciding the answer in advance

Every system here is read-heavy: a short link is created once and clicked thousands of times; a suggestion list is computed for a prefix that millions will type. When reads outnumber writes by a hundred or a thousand to one, the winning move is always the same: do the expensive work once, when the data changes, so that each read is a single cheap lookup. Four problems follow, each from the one before.

Problem 1 — pick a key that makes the read one lookup

The fastest read is fetching a value by its key from a hash table or a key-value store: one hop, no scanning. So the design starts by asking what the key is. For a short link it is the short code itself. For a suggestion list it is the prefix. For "near me" it is the map cell the user is standing in. Once the key is right, storage is easy (R10, R17's key-value store).

Problem 2 — precompute the answer, not just the data

Storing the data is not enough if each read must still sort or filter it. Typeahead does not store all queries and sort them on every keystroke; it stores the top ten for each prefix, ready to return. Proximity search does not compute distances to every restaurant in India; it indexes places by cell, so only a few cells need checking. Precomputed answers trade memory and build time for read speed.

Problem 3 — keep the hot answers close to the reader

Popularity is skewed: a few links go viral, a few prefixes ("w", "wh", "wea") are typed by everyone, a few city centres are searched all day. Caches at every layer — browser, CDN, an in-memory cache in front of the store (R12) — absorb those hot keys, so the store only sees the long tail.

Problem 4 — build and refresh the index without stopping reads

Precomputed indexes go stale. They are rebuilt offline from logs or source data, then swapped in atomically as a new version, while reads continue against the old one. At the far end of this problem is the web crawler, which exists only to build an index: it has to discover and refresh billions of pages politely, without fetching the same page twice or getting trapped.

Rules of thumb for read-heavy lookups

• Choose the key first; the right key makes every read a single fetch.
• Precompute the answer per key — top-k per prefix, places per cell — not just the raw data.
• Cache the skewed head at the edge and in memory; let the store serve the tail.
• Rebuild indexes offline, version them, and swap atomically; never block reads to update.
• Keep the write path (creating links, logging queries) off the read path, connected by a queue.

How the four walkthroughs build on each other

They are ordered so that each adds one difficulty:

1. URL shortener — the simplest possible lookup: one exact key to one value, read a hundred times for every write. The design questions are how to generate short unique keys, how to cache the hot ones, and how to keep analytics off the redirect path.
2. Typeahead — from one exact key to every key with a given prefix, answered on each keystroke. The answer is precomputed per prefix in a trie, built offline from query logs.
3. Proximity search — from one dimension to two. Geohash turns "near this point" back into a prefix question, so the typeahead idea returns in a new form, with the edge of each cell as the new trap.
4. Web crawler — every earlier walkthrough read from an index; this one builds one, for the whole web. Reads disappear and the problems become discovery, politeness, deduplication and freshness.

At a glance

Walkthrough 1 — URL shortener: the simplest lookup at huge scale

Where this starts: the purest read-heavy lookup there is. One short key maps to one long URL. It is written once and then read perhaps a hundred times, by people who expect the redirect to feel instant. There is no search, no ranking and no join — just "given this key, where do I go?" — which makes it the cleanest place to learn the habits the rest of this section builds on: precompute the answer, make the lookup a single key read, cache it at every layer, and keep everything slow off the read path.

Scope and requirements

Interviewer: Design a URL shortener — paste a long link, get a short one, and the short one redirects.

You: The core is a lookup table that must answer billions of reads quickly while a much smaller stream of writes keeps adding to it. Before designing, a few questions:

Interviewer: Custom aliases, yes. Optional expiry; owners can delete. Owners want click analytics, but a few minutes' delay is fine. Both anonymous and signed-in creation. Plan for 100 million new links a month and a read-to-write ratio of about 100 to 1. Users are worldwide.

You: Requirements, then.

Functional:

• Shorten: given a long URL, return a short URL with a unique key, such as https://sh.example/aZ3k9Qx.
• Custom alias: a user may ask for a specific key; it is granted only if nobody has it.
• Redirect: a request for the short URL returns an HTTP redirect to the long URL.
• Expiry and deletion: a link may carry an expiry time; owners may delete or disable their links.
• Analytics: clicks per link over time, with country, device and referrer.

Non-functional:

• Redirects are fast: under 50 ms at p99 at the server, and served close to the user.
• Redirects are highly available. A broken short link in a printed poster or a sent SMS cannot be fixed later; reads must keep working even when creation is degraded.
• A key never points to two different URLs. Once issued, a key means one thing for its whole life.
• Analytics may lag by minutes and may be approximate. Losing a few click events is acceptable; slowing a redirect to record one is not.
• Abuse is contained: links to phishing or malware are blocked, ideally before anyone clicks them.

The redirect is the product: it must be fast and always available, and everything else — analytics, scanning, dashboards — has to stay off its path.

What's being probed: whether you can tell the hot path from everything else and protect it.

Concept — the hot path. The hot path is the code that runs on every request that matters most — here, the redirect. Anything that runs on it adds latency and a way to fail for every single click. So the design question for each feature becomes "does this have to happen during the redirect, or can it happen next to it or after it?" Analytics can happen after; scanning can happen before. R11's split between the write model and the read model is the same instinct.

Takeaway: Name the hot path first, then justify every component that touches it.

Capacity

Interviewer: Size it.

You: Assumptions: 100M new links a month, reads at 100 times writes, peak at five times the average, links kept for ten years, about 500 bytes per stored link once you include the long URL, owner, timestamps and index overhead, and about 200 bytes per click event.

The arithmetic:

Seconds in a month      = 30 × 86,400              = 2,592,000
Writes                  = 100,000,000 / 2,592,000   ≈ 39/s      (peak × 5 ≈ 200/s)
Reads                   = 39 × 100                  ≈ 3,900/s   (peak × 5 ≈ 20,000/s)

Links in ten years      = 100M × 12 × 10            = 12 billion
Storage                 = 12B × 500 bytes           = 6 TB      (× 3 replicas = 18 TB)

Clicks a day            = 3,900/s × 86,400          ≈ 333 million
Click events a day      = 333M × 200 bytes          ≈ 67 GB
Click events at peak    = 20,000/s × 200 bytes      = 4 MB/s

How long must the key be? Each character in base62 — the 26 lower-case letters, 26 upper-case letters and 10 digits, all safe in a URL — gives 62 choices:

62^5 =           916 million   < 12 billion   → too short
62^6 =        56.8 billion     > 12 billion   → just enough, but 21% full after ten years
62^7 =     3,521.6 billion     (3.5 trillion) → 0.34% full after ten years

Therefore:

• Seven characters. Six would fit, but a space that is 21% full makes random keys collide often and lets anyone guess one valid key in five. Seven characters keep the space nearly empty for a decade.
• The write path is tiny — 200 per second is one database's light load. The design effort goes into reads.
• 6 TB does not fit on one machine comfortably, so the store is partitioned by key — which is natural, because every read is by key.
• The hot set is small. If around 10 million distinct links are clicked on a given day, at about 300 bytes each in a cache, that is roughly 3 GB — one Redis node holds it, and replicas share the read load.
• Click events are a stream, not a database write per click. 4 MB/s is easy for Kafka and wasteful as 20,000 random database writes a second.

What's being probed: whether your numbers change the design, rather than decorate it.

Concept — key-space density. A key space is all the keys that could exist; density is how much of it is in use. Low density makes random keys rarely collide and makes guessing a valid key hard. High density does the opposite. It is the same reasoning as a hash table's load factor: a table that is nearly empty has few collisions. Choosing seven characters over six is a choice about density, not just capacity.

Takeaway: Size the key for density, not just count — and let the read-to-write ratio tell you where to spend effort.

API

Interviewer: Sketch the API.

You: Two kinds of traffic: a management API behind the gateway, and the redirect itself on the short domain.

POST /v1/links
Idempotency-Key: 3f1c9e2a-7b44-4d0e-9a61-2c8e5d7f1b03
Authorization: Bearer ...
{ "longUrl": "https://example.com/tickets/final?utm_source=whatsapp",
  "customAlias": "ipl-final", "expiresAt": "2026-12-31T23:59:59Z" }

HTTP/1.1 201 Created
{ "key": "ipl-final", "shortUrl": "https://sh.example/ipl-final",
  "expiresAt": "2026-12-31T23:59:59Z" }

HTTP/1.1 409 Conflict
{ "error": "ALIAS_TAKEN" }

GET /aZ3k9Qx HTTP/1.1
Host: sh.example

HTTP/1.1 302 Found
Location: https://example.com/tickets/final?utm_source=whatsapp
Cache-Control: max-age=0, s-maxage=60

The create call takes an Idempotency-Key (R3): a mobile client that retries after a timeout should get the same short link back, not two links that split the owner's analytics. The redirect needs no key — it is a read. The Cache-Control header lets the CDN keep the redirect for 60 seconds while browsers ask again every time; the redirect deep dive explains why.

Data model

Interviewer: Data model.

You:

The link table is a single-key lookup and nothing else needs to be on the redirect path. No joins, no secondary index, no range scans — exactly the access pattern a partitioned key-value store is built for. R17's key-value store walkthrough is the engine underneath: consistent hashing spreads keys over nodes, each key is replicated, and reads and writes use quorums.

Deleted links keep a tombstone — the key with status DELETED and no URL — so the key stays reserved forever.

High-level design

Interviewer: Draw it.

You: Two separate paths that share only the link store: a small write path that mints keys and checks safety, and a huge read path that is mostly cache hits. Play the flows: creating a link, a redirect on a cache miss, a viral link, a custom-alias race, then a malicious link being taken down.

A redirect, end to end:

1. A user taps https://sh.example/aZ3k9Qx in WhatsApp. DNS sends them to the nearest edge location.
2. The edge has no cached copy, so it forwards to the redirect service in the nearest region.
3. The redirect service checks its small in-process cache, then Redis. On a miss it reads the link store by key and fills Redis.
4. It checks status and expires_at, returns 302 with the Location header, and drops a click event into a local buffer that ships to Kafka in the background.
5. The browser follows the Location. Minutes later the click shows up in the owner's dashboard.

What's being probed: whether the read and write paths are separated, and whether you can say what each layer of caching is for.

Concept — read path and write path. In a read-heavy system you design the two paths separately because they have different shapes: writes are rare and need correctness (unique keys, safety checks), reads are constant and need speed. They meet only at the store. That separation is what lets you scale the redirect fleet to hundreds of instances without touching the create service. R11's CQRS is the general form.

Takeaway: Two paths, one store; the read path is stateless and cached, the write path is small and careful.

Deep dive — generating the short key

Interviewer: How do you generate the seven characters?

You: There are four common approaches. The requirement is: unique, short, cheap to produce at 200 per second across many instances, and not trivially guessable.

1. Hash and truncate. Hash the long URL — with SHA-256, say — encode it in base62 and keep the first seven characters. It needs no coordination, and the same URL can give the same key. But seven characters of a hash are just a random number, and random numbers collide. With 12 billion links in a space of 3.5 trillion, a new key has about a 0.34% chance of hitting an existing one by the end of the decade. So every write must be a conditional insert, and on a collision you rehash with a salt and try again. The "same URL gives the same key" property is usually unwanted anyway: two owners shortening the same URL want separate links and separate analytics, so you end up hashing the owner in too.

2. A global counter in base62. One database sequence, or a Redis INCR, hands out 1, 2, 3, … and you encode each number in base62. No collisions ever. But every create now depends on one counter — a single point of failure and a round trip on every write — and the keys are sequential. Anyone can walk aaaaaab, aaaaaac, … and read every link ever made, including ones the owner meant to share privately. It also reveals how many links you create a day.

3. Pre-allocated ID ranges (range leasing). Keep the counter, but hand it out in blocks. A small allocator — one SQL row, sometimes called a ticket server — gives each create-service instance a block of 10,000 IDs at a time. The instance then counts through its block in memory with no network call at all:

-- Lease the next block of 10,000 IDs; the row lock makes concurrent leases safe
UPDATE id_blocks
   SET next_start = next_start + 10000
 WHERE name = 'short_links'
RETURNING next_start - 10000 AS block_start;

At 200 creates a second spread over ten instances, each block lasts about 500 seconds, so the allocator sees a couple of requests a minute. If an instance crashes, the rest of its block is simply lost — even one crash a day for ten years wastes about 37 million IDs, a thousandth of a percent of the space. If the allocator is down, instances keep issuing from the blocks they already hold.

4. Snowflake-style IDs. Each instance builds a 64-bit ID from a timestamp, its machine number and a sequence (R0). No coordination at all. But a 64-bit number needs eleven base62 characters, because 62^10 is about 8.4 × 10^17 while 2^63 is about 9.2 × 10^18. For a service whose whole job is to be short, that is too long.

My choice is range leasing plus a scramble. The leased number goes through a keyed permutation before encoding — a small Feistel network, a few rounds of mixing with a secret key, that maps every number in [0, 62^7) to a different number in the same range (re-applying it on the rare output that falls outside the range, a trick called cycle-walking). Because it is a one-to-one mapping, unique IDs stay unique, so there are no collisions to handle; but consecutive IDs come out looking random.

String newKey() {
    if (cursor == blockEnd) {                       // block used up: lease another
        long start = allocator.lease(10_000);
        cursor = start; blockEnd = start + 10_000;
    }
    long id = cursor++;
    long scrambled = feistel.permute(id);           // one-to-one on [0, 62^7)
    return Base62.encode(scrambled, 7);             // left-padded to 7 characters
}

A scrambled key is hard to guess, not secret. The permutation stops casual enumeration, but it is not encryption a determined attacker cannot study. A link that must stay private needs access control — sign-in, or a longer random key from a secure random generator — not reliance on obscurity.

What's being probed: whether you can compare ID schemes on uniqueness, coordination, length and predictability — not just pick one.

Concept — range leasing. Instead of asking a central counter for every number, each worker borrows a whole range and spends it locally. The central point is touched once per thousands of IDs, so it is neither a bottleneck nor, for minutes at a time, a dependency. The price is gaps when a worker dies, which a large key space absorbs easily. R0 covers Snowflake IDs as the coordination-free alternative; here their length rules them out.

Takeaway: Lease ranges for uniqueness without coordination, scramble them against enumeration, and keep the key at seven characters.

Deep dive — the redirect: 301 or 302, and the caches

Interviewer: Which redirect status do you return, and why?

You: The choice decides who can cache the redirect, and therefore whether we see each click.

We return 302, because the requirements include analytics and the ability to disable malicious links. Once a browser has cached a 301, we cannot take it back. If an owner explicitly wants a permanent redirect and does not care about analytics, a 301 with a bounded max-age is a reasonable per-link option.

302 does not mean "no caching anywhere". The header Cache-Control: max-age=0, s-maxage=60 tells browsers not to reuse it but lets shared caches — the CDN — keep it for 60 seconds. The CDN sees every click even when it answers from cache, so its request logs feed the same analytics pipeline. Disabling a link then takes at most a minute at the edge, or seconds with an explicit CDN purge.

Behind the edge are three more layers, each with a reason:

sequenceDiagram
    participant B as Browser
    participant E as CDN edge
    participant R as Redirect service
    participant C as Redis
    participant S as Link store
    participant K as Kafka
    B->>E: GET /aZ3k9Qx
    E->>R: cache miss, forward
    R->>C: GET link aZ3k9Qx
    C-->>R: miss
    R->>S: read by key
    S-->>R: long URL, status, expiry
    R->>C: SET with TTL
    R-->>E: 302 Location, s-maxage=60
    E-->>B: 302
    R--)K: click event, async from local buffer

Interviewer: A celebrity posts a link and it gets 200,000 clicks a second.

You: The edge takes almost all of it: with a 60-second shared cache, each edge location asks us roughly once a minute. What reaches us lands on one key, and if every redirect instance asked Redis for it, one Redis shard would carry it all — so the in-process cache answers the hottest keys from memory. When a hot entry expires, many requests would miss at once and stampede the store; single-flight loading — one request fetches, the others wait for its result — prevents that. R12 covers stampedes and hot keys.

The opposite problem is keys that do not exist. A scraper trying random keys misses every cache and hits the store each time — cache penetration. A short negative cache (a "not found" marker for 30 seconds) and per-IP rate limits handle most of it. The negative cache must be short, because a key that does not exist now may be created in the next second.

What's being probed: whether you connect the HTTP status code to caching, analytics and safety.

Concept — who may cache a response. HTTP lets a server say separately how long a browser may reuse a response (max-age) and how long a shared cache such as a CDN may (s-maxage). A response the browser keeps is invisible to you from then on; a response the CDN keeps is still under your control, because you can purge it and read its logs. R12 covers cache layers; this is the same idea at the HTTP level.

Takeaway: Return 302 so every click stays visible and revocable, and let the CDN, not the browser, do the caching.

Deep dive — custom aliases and the race

Interviewer: Two people ask for ipl-final at the same moment.

You: The tempting code is "read the key; if it is free, write it". Both requests read, both see it free, both write, and the second silently overwrites the first — now a link someone already shared points somewhere else, which breaks our rule that a key never changes meaning.

The fix is R19's lesson: put the check inside the write. The insert itself carries the condition "only if this key does not exist", and the store evaluates it atomically on the key's own partition:

PutItem  table = links,  key = "ipl-final"
         item  = { long_url, owner_id, created_at, expires_at, status = ACTIVE }
         condition: attribute_not_exists(short_key)

→ written                 → 201 Created
→ condition check failed  → 409 ALIAS_TAKEN

In SQL the same thing is INSERT ... ON CONFLICT (short_key) DO NOTHING followed by a check that one row was inserted. In a Cassandra-style store it is a lightweight transaction, INSERT ... IF NOT EXISTS, which runs a consensus round and is slower — acceptable at our write rate. Exactly one request wins; the other gets a clear 409 and picks another name.

Three details around it:

• Generated keys use the same conditional insert. A scrambled ID could, in principle, equal a custom alias someone already took. The conditional insert catches it, and the create service just takes the next ID. Alternatively, make the namespaces disjoint — for example, custom aliases must contain a hyphen or be at least eight characters, while generated keys are exactly seven alphanumerics.
• Reserved words. Aliases like login, api, admin or help are refused, so nobody can make sh.example/login point at a phishing page.
• Idempotent retries. If the client times out and retries the same create with the same Idempotency-Key, it must get 201 with its own link, not 409 against itself. The idempotency record is checked before the insert.

What's being probed: check-then-act races, and whether you reach for a lock service when a conditional write is enough.

Concept — the conditional insert. "Insert only if absent" is an atomic operation in almost every serious store. It turns a race between two requests into a clean verdict: one write succeeds, the other is told why it failed. No distributed lock, no lease, no retry loop. R19's introduction calls this putting the check inside the write; BookMyShow uses the same move for seats.

Takeaway: Never read-then-write for uniqueness; let one conditional insert decide.

Deep dive — analytics without slowing the redirect

Interviewer: Owners want clicks by country and referrer. How do you count without slowing redirects?

You: The redirect service never writes analytics to a database. It builds a small event — key, timestamp, country from the IP, device from the user agent, referrer, and a hashed IP — and puts it in an in-memory buffer. A background thread ships batches to Kafka. The redirect returns before any of that happens.

From there it is R21's fan-in pattern, the same shape as Datadog's metric ingestion: hundreds of redirect instances and the CDN's logs all pour into one topic, partitioned by key, and a stream job aggregates.

1. Ingest. Redirect instances and CDN log shippers produce click events to Kafka.
2. Aggregate. A stream job keeps per-key, per-minute counts in memory — total clicks, by country, by device, by referrer — and a HyperLogLog sketch per key for unique visitors, a few kilobytes that estimate distinct counts within about 1%.
3. Write. Each minute it writes the aggregates to a columnar analytics store. A dashboard query for "this link, last 30 days" reads only that link's rows — 43,200 per-minute rows, or 720 once older minutes are rolled up into hours.
4. Filter. Known bots and link-preview crawlers — chat apps fetch a link to build a preview card — are tagged and excluded from the human count.

The trade-offs are deliberate, and match the requirement that analytics may be approximate:

• If Kafka is unreachable, the buffer fills and then drops events rather than blocking redirects. A dropped click is a small error in a chart; a blocked redirect is an outage.
• Kafka delivers at least once (R9), so a retry can count a click twice. Each event carries an ID, and the aggregator ignores IDs it has seen within a short window. For a click counter, that is precise enough.

Analytics is a stream that runs beside the redirect, never a write inside it.

What's being probed: whether you keep a secondary feature from damaging the primary one, and whether you accept approximation where it is allowed.

Concept — fire-and-forget telemetry. Some data is valuable in aggregate but worthless per event: no single click matters. For that data, the right design buffers locally, ships asynchronously, and sheds load when the pipeline is unhealthy. Contrast it with a payment event, which must never be dropped and so goes through an outbox (R4). Knowing which kind of data you have is the design decision. R21 covers fan-in at scale.

Takeaway: Buffer, batch, ship asynchronously, and drop before you block.

Deep dive — abuse, expiry and key reuse

Interviewer: Someone uses you to hide phishing links.

You: Short links are attractive to attackers precisely because they hide the destination. Defence comes in layers, from cheapest to most thorough:

1. At creation, synchronously. Rate limits per user and per IP (R17's rate limiter), CAPTCHA for anonymous creation, a check of the domain against our blocklist and a threat-intelligence feed, and refusal to shorten our own short links, which would create redirect chains and loops. This adds tens of milliseconds to a create, which is fine.
2. After creation, asynchronously. LinkCreated goes to Kafka; the safety scanner fetches the destination in a sandbox, follows its redirects and classifies the page.
3. Over time. A page that was harmless at creation can be swapped for a malicious one a week later. The scanner rescans links on a schedule — popular ones more often — and reacts to abuse reports.
4. On a verdict. The scanner sets status = DISABLED in the store, deletes the Redis entry and purges the CDN. Within seconds every redirect for that key returns a warning page instead of a Location. This only works because we chose 302.

Interviewer: And expiry, deletion — can a key be reused?

You: Expiry is lazy, like BookMyShow's holds: the redirect service checks expires_at on every lookup, so an expired link stops working at the exact second even if no cleanup has run. A background job later turns expired records into tombstones to reclaim the URL's storage, and the store's TTL feature can do the same.

Keys are never reused. A short link lives on in printed posters, old emails and chat histories. If an expired key were reissued, every one of those old clicks would land on a stranger's destination — a gift to phishers. With 3.5 trillion keys and 12 billion used, there is no shortage to justify the risk. Tombstones keep deleted and expired keys reserved forever; they cost a few dozen bytes each. If a business insists on releasing custom aliases, release them only after a long quarantine — a year or more.

Safety rules that keep a shortener from becoming a weapon

• Check before creating, scan after creating, and rescan for the link's whole life.
• Use 302 so a disable takes effect on the next click.
• Never reissue a key; keep a tombstone.
• Reserve words like login and admin; refuse to shorten your own links.
• Rate-limit creation per user and per IP, hardest for anonymous users.

Failures and scale

Interviewer: What breaks, and how?

You:

Multi-region in one paragraph: redirects are reads, so every region keeps a full replica of the link store, filled by asynchronous replication, and DNS routes each user to the nearest region (R13). Generated keys can be created in any region without conflict, because each region leases ID blocks from its own disjoint range. Custom aliases need global uniqueness, so their conditional inserts go to one home region — a few hundred milliseconds of extra latency on a rare operation. When a redirect misses in a far region just after creation, the service asks the home region before answering 404.

Curveballs

Interviewer: An owner wants to change where an existing short link points.

You: Allowed for signed-in owners as a paid feature, but it is a change to a key's meaning, so it is audited, it deletes the Redis entry and purges the CDN, and it goes back through the safety scanner. With 302 and a 60-second edge cache, everyone sees the new destination within a minute. That is another reason not to default to 301.

Interviewer: Why not keep everything in Redis? It is fast enough.

You: As the cache, yes. As the only copy of 6 TB that must never lose a link, no: memory is expensive at that size, and Redis replication is asynchronous, so a failover can lose recent writes (R8, R12). The durable store is the truth; Redis holds the hot fraction.

Interviewer: Show a preview of the destination before redirecting?

You: Make it opt-in, by adding + to the end of the short URL or through a setting: it serves an interstitial page with the destination, the scan verdict and a button. It doubles the clicks for those users, so it is not the default. Disabled links always get the interstitial.

Interviewer: How would you test that keys never collide?

You: Property-test the permutation over sampled ranges to check it is one-to-one, and alarm in production on any conditional-insert failure for a generated key — that should never happen. If it does, something is wrong with block leasing, such as two regions sharing a range.

Quick reference

The 60-second version

A URL shortener is a key-value lookup read a hundred times more often than it is written: about 200 creates and 20,000 redirects a second at peak, 12 billion links and 6 TB over ten years. Seven base62 characters give 3.5 trillion keys, so the space stays nearly empty. Keys come from ID ranges leased in blocks from a small allocator, scrambled by a keyed one-to-one permutation so they are unique without per-write coordination and not sequential; Snowflake IDs would need eleven characters. Custom aliases are claimed with a conditional insert, so exactly one requester wins. Links live in a partitioned, replicated key-value store. Redirects are 302, so every click stays visible and a malicious link can be disabled instantly; the CDN caches redirects for a minute, an in-process cache and Redis take the rest, and single-flight refills stop stampedes on viral links. Click events go from an in-memory buffer to Kafka and a stream aggregator, never blocking the redirect. Links are scanned at creation and rescanned for life, expiry is checked at read time, and keys are never reused. Every region holds a full replica for local redirects.

Walkthrough 2 — Typeahead: suggestions on every keystroke

Building on the URL shortener: the shortener answered one exact key with one value. Typeahead answers a prefix — every query that starts with what you have typed so far — and has to pick the best handful of them, ranked, within about 100 ms, on every keystroke. The habits carry over: precompute the answer, make the lookup a walk through memory rather than a computation, cache it near the user, and keep the slow work offline. What is new is that the precomputed answer is no longer a single value but a ranked list for every possible prefix, and that list has to change as the world changes.

Scope and requirements

Interviewer: Design the search-box suggestions for a large search engine. As the user types, show likely completions.

You: The core is a lookup keyed by prefix, answered from a structure that was mostly built in advance. Before designing, a few questions:

Interviewer: Suggest past queries. Ten suggestions, ranked by popularity. A big news event should show up within about fifteen minutes. Personalisation is a stretch goal. English and Hindi to start, for users in India. Spelling correction is out of scope for now.

You: Requirements, then.

Functional:

• For a prefix the user has typed, return the top 10 completions, ranked by recent popularity.
• Freshness: trending terms appear within about fifteen minutes; the main ranking may be hours old.
• Safety: never suggest offensive, dangerous or defamatory completions, or completions that reveal someone's private information.
• Languages: English, and Hindi typed in Devanagari or in Latin letters.
• Extension: blend in the user's own recent searches.

Non-functional:

• About 100 ms from keystroke to suggestions on screen, at p99. After network time, the server's share is roughly 20 ms.
• Highly available, but optional. If suggestions fail, the search box must still work; an empty dropdown is a degraded experience, not an outage.
• Eventually consistent. Two users seeing slightly different lists for a few minutes is fine.

At 100 ms per keystroke there is no time to compute a ranking — every answer must already exist, waiting to be read.

What's being probed: whether the latency budget drives the architecture from the first minute.

Concept — latency budget. A latency budget splits the total time the user will tolerate across every step: the network there and back, the edge, the server, rendering. Once the server's share is about 20 ms, anything that scans data in proportion to its size is ruled out, and you are pushed to lookups whose cost depends only on the length of the input. R15 covers latency targets and percentiles.

Takeaway: Turn the user's tolerance into a server budget, then rule out every design that cannot meet it.

Capacity

Interviewer: Size it.

You: Assumptions: 1 billion searches a day; about 12 keystrokes per search before the user submits or picks a suggestion; peak at twice the average; 100 million distinct queries worth keeping after filtering, averaging 20 bytes; one serving node handles about 20,000 lookups a second.

The request rate:

Every keystroke sent    = 1B searches × 12            = 12B a day
                        = 12,000,000,000 / 86,400     ≈ 139,000/s    (peak × 2 ≈ 280,000/s)

With debounce and reuse ≈ 6 requests per search       = 6B a day
                        = 6,000,000,000 / 86,400      ≈ 69,000/s     (peak × 2 ≈ 140,000/s)

Edge and browser caches absorb ~40% (assumption: short prefixes repeat a lot)
Origin at peak          = 140,000 × 0.6               ≈ 85,000/s
Serving nodes           = 85,000 / 20,000             ≈ 5 per region, ~8 with headroom

The memory, which the trie deep dive explains:

Query strings           = 100M × 20 bytes             = 2 GB
Scores                  = 100M × 4 bytes              = 0.4 GB
Plain trie, worst case  = 100M × 20 characters        = 2 billion nodes   → too many
Compressed trie         ≤ 2 × 100M                    = 200 million nodes
Per node                = label 8 B + children 16 B + top-10 query IDs 40 B = 64 B
Trie                    = 200M × 64 B                 = 12.8 GB
Total                   ≈ 15 GB    (of which precomputed top-10 lists = 200M × 40 B = 8 GB)

Therefore:

• The whole index fits in one machine's memory. We can replicate it everywhere rather than shard it — sharding is a growth path, not day one.
• 85,000 lookups a second is a fleet of a handful of nodes per region, because each lookup is a short walk through memory.
• Most of the work is in the client and the edge. Halving keystrokes sent and caching short prefixes removes more load than any server optimisation.
• Half the index is precomputed answers. That is the price of meeting the latency budget, and it is worth paying.

What's being probed: whether you size requests per keystroke, not per search, and memory per node, not per query.

Concept — request amplification. One user action can become many requests: one search here is a dozen keystrokes, each a potential request. Sizing per search would undercount by ten times. The fix is partly arithmetic — size what actually hits the server — and partly design: the client decides how many of those keystrokes become requests at all.

Takeaway: Count what reaches the server, then make the client and the edge shrink that number.

API

Interviewer: API?

You: One read endpoint, designed to be cacheable.

GET /v1/suggest?q=ip&market=en-IN&limit=10

HTTP/1.1 200 OK
Cache-Control: public, max-age=300
{ "q": "ip", "version": "2026-10-09T06:00Z",
  "complete": false,
  "suggestions": ["ipl", "ipl live score", "ipl points table", "iphone 17",
                  "ipl schedule", "ip address", "ipl auction", "ipo gmp",
                  "iphone 17 price in india", "ipl final tickets"] }

• market combines language and region, so the cache key separates English-in-India from Hindi-in-India.
• complete: true means the list contains every known completion of this prefix, so the client can filter it locally for longer prefixes without asking again.
• version names the index snapshot that served it, which helps debugging and lets a client discard an answer from an older snapshot.
• There is no user identity in the request. Personal suggestions, if added, come from a separate call or from the device, so this response can be shared by everyone through the CDN.
• No writes, so no idempotency keys. Popularity is learned from submitted searches, which the search service logs — not from suggestion requests.

Data model

Interviewer: Data model.

You:

The serving index is a read-only snapshot built offline; the only thing that changes between snapshots is a small trending set blended in at query time. That split — a big structure that is rebuilt, plus a small one that is updated — is what lets the big one be read without any locks.

High-level design

Interviewer: Draw it.

You: Two halves: a serving path that only reads memory, and a pipeline that turns search logs into new snapshots. Play the flows: a keystroke, the client and edge tricks, the offline rebuild, a trending term, and a bad snapshot. The diagram shows the trie split into two prefix-range shards, the layout it grows into; at today's 15 GB every node could hold the whole trie.

A keystroke, end to end:

1. The user types i, p. The client waits for a short pause in typing, then sends q=ip, cancelling any request still in flight for i.
2. The CDN has ip for en-IN cached from a request a minute ago and answers in a few milliseconds. On a miss it forwards to the suggest service.
3. The suggest service picks the shard that owns ip. The shard walks two nodes, i then p, and reads that node's stored top 10.
4. The suggest service merges in any trending terms starting with ip, drops anything on the blocklist, and returns ten suggestions. The CDN caches the response for five minutes.
5. When the user later submits a search, the search service logs it to Kafka. That is how tomorrow's snapshot learns.

What's being probed: whether serving and building are separate systems, and whether you know which parts must be real time.

Concept — offline index, online lookup. Many lookup systems split into a builder that does expensive work on a schedule and a server that only reads what the builder produced. The server stays simple, fast and stateless apart from a file it loaded; the builder can take an hour and nobody notices. Search engines, recommendation systems and the web crawler later in this section all work this way. R11's read models are the same idea inside one database.

Takeaway: Do the hard work offline into an immutable snapshot, serve the snapshot from memory, and patch freshness in with something small.

Deep dive — the trie with the answers stored inside

Interviewer: Why a trie, and what exactly is stored?

You: A trie (prefix tree) is a tree where each edge is a character and the path from the root to a node spells a prefix. To find everything starting with ip, you walk root → i → p and the whole subtree below is your answer. Finding the node costs as many steps as the prefix has characters — two here — no matter how many queries the trie holds.

But finding the node is not the same as finding the top 10. Everything below ip might be hundreds of thousands of queries. Below s it could be millions — say 8 million, out of 100 million. Ranking them at query time means visiting all of them:

Top 10 at query time for prefix "s"
  visit ~8 million nodes × ~10 ns (if every node were in CPU cache)  ≈ 80 ms
  in practice, scattered memory reads make it several times slower
  at 85,000 requests a second → impossible

So each node stores its own top 10, computed when the trie is built. A lookup becomes: walk to the node, read ten query IDs, look up their strings. Microseconds.

The builder fills those lists bottom-up, in one pass. A node's top 10 is the best 10 among its own query (if a query ends exactly here) and its children's top-10 lists:

build(node):
    candidates = []
    if node.isEndOfQuery: candidates.add((node.queryId, node.score))
    for child in node.children:
        build(child)
        candidates.addAll(child.top10)
    node.top10 = best 10 of candidates by score

Each node merges at most ten entries per child, so the build is roughly linear in the size of the trie.

Two more tricks keep it to the 15 GB in the capacity numbers:

• Compress the chains. Long-tail queries make long single-child chains: i-p-h-o-n-e- -1-7- -p-r-i-c-e. A radix trie collapses each chain into one edge labelled with a whole substring. A radix trie over 100 million queries has at most about 200 million nodes, instead of up to 2 billion.
• Store IDs, not strings. Each top-10 entry is a 4-byte ID into one shared string table, so a popular query that appears in the top 10 of twenty prefixes is stored once.

And where a subtree holds ten queries or fewer, its top 10 is simply the whole subtree, so the client can be told complete: true and stop asking.

Do not rank at query time "because the index is small today". The cost of ranking grows with the number of queries under a prefix, and short prefixes — the ones typed most often — have the most.

What's being probed: precomputation as a deliberate trade of memory for latency, with the arithmetic to justify it.

Concept — materialising the answer. When the same question is asked millions of times and its answer changes slowly, compute the answer once and store it next to the key — here, in the trie node. It is the same move as a materialised view in a database, or a precomputed feed in R21's Instagram fan-out on write. You pay in memory and build time, and in exchange the read is a lookup.

Takeaway: Store the top 10 in every node so that a keystroke costs a walk of prefix length, not a scan of the subtree.

Deep dive — the offline pipeline and snapshots

Interviewer: Where do the scores come from, and how does a new trie reach the servers?

You: A pipeline that runs every few hours:

1. Log. The search service publishes each submitted query — normalised to lower case, trimmed, whitespace collapsed, Unicode normalised — with market, time and a hashed user ID.
2. Aggregate with decay. The count aggregator computes today's count per query and folds it into a running score that fades old popularity, with a seven-day half-life (worked through below).
3. Filter. Drop queries searched by fewer than, say, 50 distinct users — that removes typos, and stops one person's private search, like a name with a phone number, from ever being suggested to others. Drop anything matching the blocklist or flagged by a safety classifier. Discount traffic from known bots, which can otherwise push a term up.
4. Build. The trie builder builds the radix trie and its top-10 lists for each market and writes a compact binary snapshot to object storage, with a version and a checksum.
5. Validate. Before anything serves it, an automated check compares it with the previous version: total size within a few percent, a fixed set of probe prefixes still giving sensible results, nothing from the blocklist present.
6. Deploy. A canary node loads the new snapshot first. If its error rate and latency look normal, the rest follow. Each node loads the new trie beside the old one, swaps a single pointer, and frees the old one later. In-flight requests finish on whichever trie they started on, and no request ever sees a half-built index.

The decay in step 2, concretely. With a seven-day half-life, the daily factor is 0.5^(1/7) ≈ 0.906:

score_today = 0.906 × score_yesterday + count_today

A query searched 10,000 times every day settles at 10,000 / (1 − 0.906) ≈ 106,000.
If it stops completely, its score halves every 7 days.

A run every few hours applies the same rule with the factor for its interval — 0.5^(1/168) ≈ 0.996 per hour elapsed. One running number per query is all the history the pipeline keeps; it never re-reads weeks of logs.

flowchart LR
    A[Search service] --> B[Kafka query log]
    B --> C[Count aggregator]
    C --> D[Trie builder]
    D --> E[Snapshot store]
    E --> F[Canary node]
    F --> G[All trie nodes]
    B --> H[Trending job]
    H --> I[Trending cache]
    I --> J[Suggest service]
    G --> J

A snapshot is immutable: build it, check it, swap it in whole, and keep the last one ready for rollback.

What's being probed: whether you can ship a large derived dataset safely, not just compute it.

Concept — versioned snapshot deploy. Treat a built index like a software release: give it a version, test it, roll it out to one node, then to all, and keep the previous version so you can roll back with a pointer change. Because the snapshot is never modified in place, servers read it with no locks at all. R16 covers zero-downtime change; this is the data-side equivalent.

Takeaway: Build offline, validate, canary, swap atomically, and always be one pointer away from the last good version.

Deep dive — trending terms within minutes

Interviewer: India and Pakistan are playing tonight. "ind vs pak live" should be suggested as soon as people start searching for it.

You: The batch pipeline cannot do that, for two reasons. It runs every few hours. And even when it runs, decay works against a newcomer: a query with 50,000 searches today scores 50,000, below an old favourite sitting at 106,000. So freshness has its own small, real-time path:

1. The trending job reads the same Kafka stream and keeps counts per query in sliding ten-minute windows.
2. It compares each count with what is normal for that query at that hour — from last week's history, or near zero for a brand-new query. A query is trending when its rate is many times its normal rate and above an absolute floor, say 500 searches in ten minutes, so a jump from 2 to 20 does not count.
3. Trending queries pass the same safety checks as the batch, with stricter thresholds, because a sudden spike is exactly how a brigade or a hoax looks.
4. The trending set — a few thousand terms per market, each with a boost — goes to the trending cache, and every suggest-service instance copies it into memory every few seconds.
5. At query time, the suggest service takes the shard's top 10 for the prefix, adds trending terms that start with the prefix, re-ranks by score + boost, removes duplicates and keeps the best 10.

The trending set is small enough that "find trending terms starting with ind" is a scan over a few thousand strings, or a tiny trie of its own. The boost fades as the window moves on, and by the time the spike is over, the next batch snapshot has the term at its proper, decayed rank.

What's being probed: whether you know the batch path cannot be fresh, and can add freshness without rebuilding the big index.

Concept — the speed layer. A common pattern for derived data is a slow, complete batch path plus a fast, partial stream path whose results are merged at read time. The batch is accurate and cheap per record; the stream covers only the last few minutes and only what matters. R21's Datadog walkthrough uses the same split between rollups and recent raw data.

Takeaway: Keep the big index on a batch schedule and blend a small, real-time trending set in at query time.

Deep dive — serving: replicas, shards, caches and the client

Interviewer: How do you serve 140,000 requests a second within budget?

You: Four layers, and the cheapest ones do the most work.

The client. It sends far fewer requests than keystrokes:

• Debounce: wait until typing pauses for roughly 50–100 ms before sending, so a fast typist's i-p-l becomes one request, not three.
• Cancel stale requests: when a new request goes out, abort the previous one. If an old answer arrives late anyway, a sequence number tells the client to ignore it. Otherwise the answer for ip could overwrite the answer for ipl that arrived first.
• Reuse answers: keep a small local cache of prefix → suggestions, so backspacing is instant. If the answer for ip came back complete: true, filter it locally for ipl and send nothing.

The edge. Short prefixes are typed by everyone, and the non-personalised answer for ip in en-IN is the same for every user. So the response is Cache-Control: public with a TTL of a few minutes, and the CDN — and the browser — answer the most popular prefixes without reaching us. The cache key is the prefix plus market. This is why personal suggestions must not be mixed into this response.

The servers: replicate first. At 15 GB, the whole trie fits on every serving node, so each node is a full replica and any node can answer any prefix. Adding capacity is adding nodes. That is the right starting point.

Then shard by prefix range, when it no longer fits — more markets, a longer tail, richer per-query data. Each shard owns a range of prefixes. Two problems come with it:

• Uneven ranges. Queries do not start evenly across the alphabet: in English far more start with s or c than with x or z. So boundaries are drawn from measured size and traffic, not letters — for example a–bz, c–ch, ci–fz, … — and redrawn when the data shifts.
• Short prefixes span shards. If s is split between sa–sh and si–sz, no single shard knows the top 10 for s. So boundaries fall between two-character prefixes, every prefix of two or more characters lives in exactly one shard, and the top 10 for every one-character prefix sits in a tiny head table that the builder copies to every suggest-service instance.

Hot prefixes. During the IPL, the shard owning ip gets a flood. Two defences: that shard gets more replicas than the others, sized from its traffic, and the edge cache absorbs most of the flood, because ip and ipl are the same for everyone.

What's being probed: whether you use the whole path — client, edge, server — rather than only scaling servers.

Concept — replicate before you shard. If the data fits on one machine, copying it everywhere is simpler than splitting it: any node answers any request, there is no routing, and capacity grows by adding identical nodes. Sharding adds routing, uneven load and cross-shard questions, so you do it only when the data outgrows a machine. R10 covers partitioning and its hot-spot problem.

Takeaway: Let the client and the edge remove most requests, replicate the trie while it fits, and shard by measured prefix ranges with a head table when it does not.

Deep dive — safety and languages

Interviewer: How do you stop bad suggestions, and how does Hindi work?

You: Safety is enforced in three places, because each catches what the others miss:

1. At build time. The blocklist, a safety classifier and the distinct-user threshold remove most bad completions before they enter the snapshot. Some categories are suppressed by policy — for example, a person's name followed by an accusation of a crime.
2. At serve time. Some things cannot wait for the next build: a legal removal order, or a tragedy that makes a previously harmless completion hurtful. The suggest service checks every candidate against a small, hot blocklist pushed to it within minutes. It is a set lookup per candidate — microseconds.
3. On the trending path. Higher thresholds, extra classifiers, and human review for sensitive categories, because a sudden spike is the easiest thing to manipulate.

Languages. Each market gets its own trie — en-IN, hi-IN — built from that market's logs, which also keeps one market's popularity from leaking into another's. Within that:

• Normalise consistently. Queries are stored in Unicode NFC form, so the same text typed on two keyboards is the same string. Latin text is lower-cased; Devanagari has no case.
• Index code points, not visible characters. One visible Devanagari syllable can be several code points — क्ष is क, the virama ्, and ष. A trie over code points handles this naturally, as long as builder and client normalise the same way.
• Wait for composition. Phone keyboards and input method editors compose text before committing it. The client sends a request when text is committed, not on each intermediate state.
• Transliteration. Many Hindi speakers type Hindi in Latin letters — cricket score kab hai — with no single agreed spelling: kya, kyaa and kia all mean the same word. The builder groups such variants using a transliteration model and the search logs, and indexes the variants as extra keys that lead to the same suggestions. Results are shown in the script the user is typing in, so someone typing in Latin letters is not suddenly shown Devanagari.

What's being probed: whether you treat safety as a pipeline with a fast override, and handle multilingual input without hand-waving.

Concept — defence in depth for content. A filter that runs only at build time is slow to react; a filter that runs only at serve time cannot afford heavy models. Using both — heavy checks offline, a tiny fast override online — gives thoroughness and speed. It is the same layering the URL shortener used for malicious links: check before, act fast after.

Takeaway: Filter heavily at build time, keep a hot blocklist at serve time, and build one trie per market with consistent normalisation and transliteration variants.

Failures and scale

Interviewer: What breaks?

You:

Suggestions are an aid, not the product: under pressure, serve a slightly stale or shorter answer, and never let the search box wait.

Curveballs

Interviewer: Add personalisation.

You: Keep it out of the shared response. The device keeps the user's recent searches and merges matching ones at the top of the list, so nothing personal touches the CDN. For signed-in users across devices, a per-user store returns their matching recent queries from a separate call, merged in the client. The shared, cacheable answer stays shared.

Interviewer: Users misspell — "iphnoe".

You: Fuzzy matching in the trie is expensive, because the walk branches at every possible edit. The cheap win is offline: logs show people typing iphnoe, getting nothing useful, and retyping iphone. The builder learns those pairs and indexes the common misspelling as an extra key that leads to the correct suggestions. True edit-distance search can come later for the long tail.

Interviewer: Why not use a search engine's built-in completion feature?

You: At smaller scale, that is the right call — search engines such as Elasticsearch ship a completion suggester backed by an in-memory structure. At this scale, owning the trie gives control over ranking with decay, the trending blend, per-market builds, safety filters and the snapshot rollout. The ideas are the same; the question is who operates them.

Interviewer: Suggestions shape what people search, which shapes the suggestions.

You: Yes — a feedback loop. Counting only submitted searches, not suggestions shown, softens it, and so does tracking how often a suggestion is picked versus typed out in full. The decay also stops a term from staying on top only because it is on top.

Quick reference

The 60-second version

Typeahead returns the ten most popular completions of a prefix within about 100 ms per keystroke, which leaves the server roughly 20 ms — no time to rank anything. So the answers are precomputed: a radix trie over the 100 million queries worth keeping, with the top 10 stored at every node, about 15 GB, small enough to replicate whole onto every serving node. A pipeline every few hours turns submitted-search logs into decayed popularity scores, filters out rare, unsafe and bot-driven queries, builds a trie per market, validates it and rolls it out as a versioned snapshot that each node swaps in atomically, keeping the last one for rollback. A real-time trending job spots spiking terms in ten-minute windows and the suggest service blends them in at query time. The client debounces, cancels stale requests and reuses complete answers; the CDN caches popular prefixes per market, which is why personal suggestions are merged separately. When the trie outgrows a machine, shard by measured prefix ranges with a replicated head table for single characters. A hot blocklist removes bad suggestions within minutes, Hindi is handled with NFC normalisation and transliteration variants, and under any failure the system serves a slightly stale answer or none, never a slow one.

Walkthrough 3 — Proximity search: places near me

Building on typeahead: typeahead answered "every key that starts with this prefix" — a lookup along one dimension, the letters of a word. Proximity search asks "everything within 2 km of this point", which is a lookup in two dimensions, latitude and longitude, and ordinary indexes are built for one. The trick of this walkthrough is a geohash: a way of writing a location as a short string so that nearby places share a prefix. That turns the two-dimensional question back into the prefix problem we already know how to answer.

Scope and requirements

Interviewer: Design a "restaurants near me" search — like the local search in a maps or review app.

You: The core is: given a point and a radius, return the best matching places nearby, fast, millions of times an hour. Before designing, a few questions:

Interviewer: Worldwide. Radius search with a default of 2 km, adjustable up to 20 km, and the map-area search too. Results ranked by a mix of distance, rating and relevance, with category and "open now" filters. Profiles with photos and reviews. A new business or an edit can take a few minutes to appear; next day is acceptable for most changes.

You: Requirements, then.

Functional:

• Search nearby: given latitude, longitude, radius and optional filters (category, open now, price), return a ranked page of businesses.
• Search the visible map: given a bounding box, return the businesses in it.
• View a business: profile, hours, photos, rating and reviews.
• Owners add and edit businesses; users write reviews with a 1–5 star rating.

Non-functional:

• Search returns in under 200 ms at p99.
• Very read-heavy: searches outnumber business changes by thousands to one.
• Highly available: a search that returns slightly old data is far better than an error.
• Business changes may take minutes to appear in search (eventual consistency is fine).
• Location data is static — a restaurant does not move between two searches.

Places almost never move and are searched constantly, so we can spend effort building a clever index ahead of time and keep every search cheap.

What's being probed: whether you spot the read/write shape early, because it decides the whole design.

Concept — precompute for the read path. When data changes rarely but is read constantly, do the hard work once at write time (or in a batch job) and make each read a cheap lookup. This is the theme of the whole of R22: the URL shortener precomputes a key, typeahead precomputes the top results per prefix, and here we precompute a spatial index. R11 covers read models in general.

Takeaway: Static data plus heavy reads means build the index offline and keep the query trivial.

Capacity

Interviewer: Size it.

You: These are assumptions, not any company's figures: 200M businesses worldwide, 100M daily active users, 5 searches per user per day, peak traffic three times the average. Owners add or edit about 1M businesses a day; users write 10M reviews a day.

Searches
  100M users × 5 searches       = 500M searches/day
  500M / 86,400 s               ≈ 5,800/s average
  × 3 for the evening peak      ≈ 17,000/s peak

Writes that touch location
  1M adds/edits per day / 86,400 ≈ 12/s
  ratio at peak: 17,000 / 12     ≈ 1,400–1,500 reads per write

Location index (only what search needs)
  per business: id 8 B + lat 8 B + lng 8 B + geohash 8 B + rating 4 B + category 4 B ≈ 40 B
  200M × 40 B                   = 8 GB
  → fits in RAM on one server; replicate it for throughput

Profiles
  200M × ~1 KB                  = 200 GB  → an ordinary sharded database
Reviews
  10M/day × 365 × ~1 KB         ≈ 3.6 TB/year → sharded by business id
Photos
  object store + CDN; never in the database

Therefore:

• The location index is small. We do not need to shard it to fit it; we replicate it, and each replica can serve thousands of searches a second.
• The read path needs replicas and caching; the write path is tiny and can update the index asynchronously.
• Profiles and reviews are a normal sharded-database problem, separate from the spatial question.

What's being probed: whether you size the index separately from the rest of the data.

Concept — the index is not the data. The search only needs id, position and a few ranking fields; the 1 KB profile is fetched later for the twenty results on screen. Keeping the index narrow is what makes it fit in memory. The same split shows up in typeahead (the trie holds phrases and counts, not documents) and in R11's read models.

Takeaway: Size the narrow index on its own; it often fits in memory, which changes every later choice.

API

Interviewer: Sketch the API.

You:

GET /v1/search?lat=12.9352&lng=77.6245&radius=2000&category=restaurant&openNow=true

HTTP/1.1 200 OK
{ "results": [
    { "id": "b_7731", "name": "Udupi Corner", "distanceM": 380, "rating": 4.4, "reviews": 1290 },
    { "id": "b_2210", "name": "Coastal Kitchen", "distanceM": 910, "rating": 4.6, "reviews": 640 }
  ],
  "nextCursor": "eyJvZmZzZXQiOjIwfQ" }

Search is a GET and safe to retry. Writes carry an Idempotency-Key so a retried "add business" does not create two listings (R3). The radius is in metres and capped at 20 km on the server, whatever the client sends.

Data model

Interviewer: Data model.

You:

The database is the truth about each business; the location index is a derived copy, shaped for one question and rebuildable at any time.

High-level design

Interviewer: Draw it.

You: Search and profile reads are separate paths. Search hits a cache or an in-memory geo index; profiles come from a cache over the database; writes flow to the index asynchronously. Play the flows: a search, a cache hit, a search with too few results, a business update, and the nightly rebuild.

A search, end to end:

1. The app sends lat=12.9352, lng=77.6245, radius=2000, category=restaurant.
2. The search service picks geohash precision 5 for a 2 km radius, computes the user's cell tdr1w and its eight neighbours.
3. It checks the result cache for that cell and filter set. On a miss it asks a geo-index replica for every business in the nine cells.
4. The replica returns a few thousand candidates with their positions and ranking fields.
5. The search service drops anything farther than 2 km by exact distance, drops closed or wrong-category places, scores the rest and keeps the top 20.
6. It fetches those 20 profiles from the profile cache, stores the ranked list in the result cache, and replies. Photos load from the CDN.

What's being probed: separating the spatial question from everything else.

Concept — candidate generation, then ranking. Search systems work in two stages: a cheap, coarse step that finds a few hundred or thousand plausible candidates, and a precise, more expensive step that filters and scores only those. The geohash cells are the coarse step; exact distance and ranking are the precise step. Typeahead had the same shape: find the prefix node, then read its precomputed top results.

Takeaway: Make the index good at narrowing; do exact distance and scoring on the small candidate set afterwards.

Deep dive — why two range indexes are slow

Interviewer: Why not just store latitude and longitude in Postgres and write a range query?

You: That is the first thing everyone tries:

SELECT id, name, lat, lng
  FROM business
 WHERE lat BETWEEN 12.917 AND 12.953
   AND lng BETWEEN 77.606 AND 77.643;

With one index on lat and another on lng, the database can use each index to narrow one dimension. The lat range is a thin stripe 4 km tall that runs right around the planet, and the lng range is a stripe 4 km wide from pole to pole. Each stripe crosses many cities and holds a large number of businesses; the answer is the small square where they overlap. The database either scans one stripe and checks the other condition row by row, or reads both and intersects them. Either way it touches far more rows than it returns.

A composite index on (lat, lng) is not much better. A B-tree sorts by lat first, so it can seek to the latitude range, but within it the lng values are scattered, and it has to read the whole stripe.

A B-tree orders rows along one line; two independent ranges cannot both be narrowed by it.

Interviewer: So what do you do?

You: Make a single value that keeps nearby points close together on one line, and index that. That is what a geohash, a quadtree and Google's S2 all do in different ways. Databases also offer spatial indexes built for this — PostGIS uses an R-tree-like GiST index — and for a small system that is a perfectly good answer. At our read rate, though, I want the index in memory on stateless replicas, so it is worth understanding how it works.

Deep dive — geohash

Interviewer: Explain geohash.

You: Take the whole world as a rectangle. Split it down the middle by longitude: west half is bit 0, east half is bit 1. Then split the chosen half by latitude: south is 0, north is 1. Keep alternating — longitude, latitude, longitude — and each bit halves the cell. Group the bits five at a time and write each group as one character from a 32-character alphabet. The result is a short string, and each extra character shrinks the cell about 32 times.

A point in Koramangala, Bengaluru (12.9352, 77.6245):

General precision table (at the equator; cells get narrower east–west towards the poles, by the cosine of the latitude):

The useful property: a longer geohash always starts with the shorter one of the cell that contains it. Every place inside tdr1w has a geohash beginning tdr1w. So "all businesses in this cell" is a prefix query, and a prefix query is a range scan in an ordinary B-tree or sorted key-value store:

-- geohash column holds 12 characters; ordinary B-tree index on it
SELECT id, lat, lng FROM business_geo
 WHERE geohash >= 'tdr1w' AND geohash < 'tdr1x';

That is the bridge from typeahead: the same prefix lookup, now on locations.

Interviewer: What about a restaurant just across the edge of the cell?

You: That is the catch. Two points 54 m apart, at (12.9400, 77.6511) and (12.9400, 77.6516), have geohashes tdr1wgx and tdr1x58 — they share only four characters because a cell boundary runs between them. At the equator it is worse: two points 44 m apart on either side of it share no prefix at all (s0p058 and kpzpgx). Close in the world does not always mean close in the string.

Searching only the user's own cell misses places just across its edge — always search the neighbours too.

The fix is simple: search the user's cell and its eight neighbours. The neighbours of tdr1w are:

tdr1v  tdr1y  tdr1z
tdr1t [tdr1w] tdr1x
tdr1m  tdr1q  tdr1r

Neighbours are computed arithmetically from the cell's bounds — no lookup needed — and the nine prefix scans can run in parallel.

Interviewer: How do you pick the precision?

You: From the radius. If each cell is at least as large as the radius in both directions, then a circle centred anywhere in the middle cell stays inside the 3×3 block. So pick the longest geohash whose cell's shorter side is still at least the radius:

The 3×3 block is larger than the circle, so the search service always applies the exact distance afterwards — the haversine formula, which gives the great-circle distance between two latitude–longitude points:

static double distanceMetres(double lat1, double lng1, double lat2, double lng2) {
    double r = 6_371_000;                       // Earth's mean radius in metres
    double dLat = Math.toRadians(lat2 - lat1);
    double dLng = Math.toRadians(lng2 - lng1);
    double a = Math.sin(dLat / 2) * Math.sin(dLat / 2)
             + Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2))
             * Math.sin(dLng / 2) * Math.sin(dLng / 2);
    return 2 * r * Math.asin(Math.sqrt(a));
}

Interviewer: Suburb at 2 a.m. — only three places open within 2 km.

You: Expand. If the nine cells give fewer than the page size, the search service retries one precision shorter (nine cells of precision 4, roughly 115 km × 60 km of candidates) and filters to a wider radius, say 5 km, then 10 km, up to the 20 km cap. The response says which radius was used, so the app can show "nothing within 2 km; showing results within 5 km". In a dense city centre the opposite happens: precision 5 cells may hold tens of thousands of places, so for small radii we use precision 6, and the index keeps a per-cell count so the search service can choose precision by density as well as by radius.

What's being probed: whether you know the geohash edge problem and how precision follows from the radius.

Concept — space-filling curves. A geohash is a way to walk through two-dimensional space along a single line (a Z-shaped curve) so that most nearby points end up near each other on the line. "Most" is the important word: at cell edges, neighbours on the map can be far apart on the line. Querying the 3×3 block covers that gap. The same idea lets any one-dimensional index — a B-tree, a sorted key-value store like the one in R17, a Redis sorted set — answer spatial queries.

Takeaway: Encode location as a geohash, pick precision from the radius, always query the 3×3 block, then filter by exact distance.

Deep dive — quadtree, S2 and H3

Interviewer: Geohash cells are fixed. Central Bengaluru and a village get the same size cell. Can you do better?

You: That is what a quadtree fixes. A quadtree is a tree in which each node covers a rectangle and has either no children (a leaf, holding a list of businesses) or exactly four children, one per quarter of its rectangle. Build it like this: start with the whole world as one node; while a node holds more than, say, 100 businesses, split it into four. Dense cities split many levels deep into small leaves; empty oceans stay as one large leaf. The cells adapt to density.

build(node):
    if node.businesses.size() <= 100: return            // leaf
    split node's rectangle into NW, NE, SW, SE
    move each business into the child that contains it
    for each child: build(child)

search(point, radius):
    find the leaf containing the point (walk down from the root)
    collect businesses from that leaf and neighbouring leaves
    keep expanding to neighbours until we have enough within radius

Memory, using our numbers:

leaves     ≈ 200M businesses / 100 per leaf  = 2M leaves
internal   ≈ leaves / 3                       ≈ 0.7M nodes
node cost  ≈ 4 bounds + 4 child pointers     ≈ 64 B  → ~170 MB for nodes
ids        200M × 8 B                         = 1.6 GB
total      ≈ 2 GB → fits in memory on each search server

The cost is that a quadtree lives in memory and has to be built. Building it for 200M businesses takes minutes, so a server cannot take traffic until it has loaded or built one. And keeping it balanced under edits is fiddly. Because our edits are rare, the practical approach is: rebuild the whole tree in a batch job every night, write it to the object store as a snapshot, and have each replica load the new snapshot and swap it in atomically. Edits during the day are applied as small inserts into a leaf (allowing it to grow past 100 until the next rebuild).

Two production libraries are worth naming. S2, from Google, projects the sphere onto the six faces of a cube and orders cells along a Hilbert curve, which keeps neighbours together better than geohash's Z-curve; each cell is a 64-bit integer with 31 levels from a cube face down to about a square centimetre, and it can cover any shape — a circle, a polygon — with a handful of cell ranges. H3, from Uber, divides the world into hexagons at 16 resolutions; a hexagon's six neighbours are all the same distance from its centre, which makes "rings" around a point uniform. Both solve the same problem as geohash with fewer distortions.

My choice for this design: geohash, stored in each replica's in-memory sorted map (and also as a column in the business database for rebuilds and debugging), with precision chosen by radius and per-cell density. It is simple to explain, to debug and to rebuild. If uneven density hurts, a quadtree or S2 covering is the upgrade.

Deep dive — ranking, caching and keeping the index fresh

Interviewer: How do you rank, and how do new reviews get in?

You: After the exact-distance filter, each candidate gets a score. A simple, explainable version:

score = 0.5 × distanceScore + 0.35 × ratingScore + 0.15 × relevance

distanceScore = 1 - (distance / radius)                       // 1 next door, 0 at the edge
ratingScore   = (C × m + sum of stars) / (C + number of reviews) / 5
                // a "Bayesian average": with few reviews it stays near m,
                // the overall average; C is how many reviews it takes to trust a place
relevance     = text match on name, category and dishes, 0..1

The Bayesian average stops a place with a single five-star review from outranking one with 4.6 stars over a thousand reviews. In a real product the weights are learned from what people click and visit, but in an interview a clear formula with a reason for each term is what matters.

Reviews arrive at about 115 a second. Each is written to the review store by the business service; the change stream carries it to the rating aggregator, which updates the count and average on the business row. That rating change flows to the index builder like any other edit. A new review affects ranking within a minute or two, which is plenty.

Business edits follow the same path: owner edits → business database → change stream → index builder → every replica. A move is a delete from the old geohash and an insert into the new one. And the nightly snapshot is the safety net: whatever an incremental update missed, the rebuild from the database corrects.

Interviewer: And caching?

You: Two caches, for two kinds of read.

• Result cache, keyed by (geohash6 of the user, category, filters, radius), TTL a few minutes. Everyone standing in the same 1.2 km × 0.6 km cell searching for "restaurants, open now" shares one entry. In a busy area at lunchtime the hit rate is high. Distances are computed against the cell's centre for the cached list, then recomputed for the actual user on the way out, which is cheap for 20 rows.
• Profile cache, keyed by business id, for hydrating results and serving profile pages. Popular places are read constantly and edited rarely, so a long TTL plus invalidation on edit works well.

Snapping the user to a geohash cell turns millions of unique coordinates into a few million shared cache keys.

What's being probed: making a cache work when every request has a slightly different location.

Concept — quantise the key. Raw coordinates are almost never repeated, so caching on them gives a near-zero hit rate. Rounding the input to a cell makes nearby users share a key, at the price of a small error you then fix cheaply. It is the same move as caching typeahead per prefix rather than per keystroke timing. R12 covers TTLs, invalidation and stampedes — a popular cell expiring at lunchtime should be refreshed by one request, not thousands.

Takeaway: Cache by cell, not by coordinate, and fix the small error per user on the way out.

Deep dive — sharding, and how this differs from Uber

Interviewer: Would you shard the location index by region?

You: Not at first. At about 8 GB it fits in memory, so every replica holds the whole world and any replica can answer any search. Throughput comes from adding replicas; there is no cross-shard query at all. That is the simplest design and the one I would start with.

If the index grew too big — many more fields, or far more places — I would shard by region, using geohash prefixes as shard keys: a search for a point in Bengaluru goes to the shard holding tdr…. Two problems come with that:

• Hot regions. Mumbai and Bengaluru are much busier than rural areas. Assign shards by load, not by area: split busy prefixes into finer ones (tdr1, tdr3, …) and merge quiet ones.
• Border searches. A search near a shard boundary needs cells from two shards, so the search service fans out to both and merges. With precision chosen from the radius, that is at most a few shards.

The business database, by contrast, is sharded by businessId from day one, because profiles and reviews are looked up by id, not by place.

Interviewer: You designed Uber's driver matching before. Why not reuse that?

You: The spatial idea is the same — cells, neighbours, nearest candidates — but the data behaves in the opposite way:

Same geometry, opposite workload: Uber's index is built for writes, this one for reads.

What's being probed: whether you can reuse a pattern while noticing that the constraints changed.

Concept — workload decides the structure. For drivers, the index is a fast-changing in-memory map that absorbs a write per driver every few seconds and lets old entries expire. For places, the index is a read-optimised snapshot rebuilt from a durable store. R19 covers driver location; here the read/write ratio is the inverse, and the design follows.

Takeaway: Ask how often the data moves before picking the index; the same cell idea serves both, tuned differently.

Failures and scale

Interviewer: What breaks?

You:

Curveballs

Interviewer: The user drags the map instead of using a radius.

You: Cover the visible rectangle with geohash cells at a precision that gives a few dozen cells for that zoom level, scan each prefix, filter to the exact rectangle, and rank. When zoomed far out, return clusters (counts per cell) rather than individual pins.

Interviewer: "Biryani near me."

You: Text and location together. Store, per business, its category and a small set of dish and keyword tags in the index entry, and filter candidates by them; or use a search engine that supports both text and geo filters, such as Elasticsearch's geo queries, with the same cell-then-distance idea underneath. Location narrows, text filters, ranking orders.

Interviewer: A business is on the boundary of two countries' shards and edits its address.

You: The edit goes to the business database by id, as always. The index builder removes the entry from the old cell and adds it to the new one; if those cells live on different shards, it is a delete on one and an insert on the other, both from the same ordered change event, so a replay is harmless.

Interviewer: Fake businesses and review spam.

You: New listings go through verification (phone or postcard) before they appear in search; reviews run through spam detection before they affect the rating. Both are asynchronous steps on the change stream, which is another reason not to put writes directly into the index.

Quick reference

The 60-second version

Places are static and searched constantly — about 17,000 searches a second against roughly a dozen location changes — so we build a spatial index ahead of time and keep each search cheap. Two separate latitude and longitude indexes are slow because a B-tree narrows only one dimension; a geohash fixes that by interleaving the bits of both into one string so that places in the same cell share a prefix, which makes "near me" a prefix scan, just like typeahead. We pick the precision from the radius (precision 5, about 5 km cells, for a 2 km search), always query the user's cell and its eight neighbours to avoid the edge problem, filter candidates by exact haversine distance, and rank by distance, a Bayesian-averaged rating and text relevance; if too few results come back, we widen to a shorter prefix. The narrow index — id, position, rating, category — is about 8 GB, so every replica holds the whole world in memory; it is updated from the business database's change stream within minutes and rebuilt from scratch every night. Results are cached per geohash cell so nearby users share entries. A quadtree adapts to density and S2 or H3 reduce distortion, but the idea is the same. Unlike Uber's moving drivers, which need an in-memory index built for constant writes, this index is built for reads.

Walkthrough 4 — Web crawler: building the index everyone else searches

Building on the first three: the URL shortener, typeahead and proximity search all read from an index built ahead of time — a key table, a trie, a geohash map. A web crawler is the machine that builds the raw material for the biggest index of all: it downloads the web so a search engine can index it. Fetching one page is trivial. The hard parts are being polite to millions of websites we do not own, not wasting effort on duplicates, and not falling into traps — sites that generate links forever.

Scope and requirements

Interviewer: Design a web crawler for a search engine.

You: A crawler starts from some known pages, downloads them, finds the links inside, and repeats — for ever, because the web keeps changing. Before designing, a few questions:

Interviewer: HTML only, no JavaScript rendering for now. One billion pages a month, a mix of new pages and recrawls of known ones; important pages should be refreshed often. The output goes to the search indexer. Obey robots.txt and never overload a site.

You: Requirements, then.

Functional:

• Start from seed URLs (and sitemaps) and keep discovering new URLs from the links in fetched pages.
• Fetch HTML pages, store them, and hand each new or changed page to the indexer.
• Recrawl known pages, more often for pages that change often or matter more.
• Skip pages we are not allowed to fetch, and pages that are duplicates of ones we already have.

Non-functional:

• Politeness: at most one request at a time to a host, with a delay between requests; obey robots.txt.
• Robustness: survive malformed HTML, slow or hostile servers, and crawler traps.
• Scalability: about 400 pages a second on average, and able to grow ten-fold by adding machines.
• Efficiency: do not fetch the same URL twice in a cycle; do not store the same content twice.
• Freshness: important pages recrawled within days, not months.

A crawler is limited less by its own machines than by how gently it must treat other people's.

What's being probed: whether you see that the constraint is external.

Concept — politeness. A crawler is a guest on millions of servers. A small site may run on one machine; a few hundred requests a second from us would be a denial-of-service attack. So the crawler must limit itself per site: one connection at a time, a pause between requests, and whatever the site's robots.txt asks. This rule, more than raw throughput, shapes the queues. R14's backpressure is the same idea from the other side.

Takeaway: Design the crawler around per-site limits first; throughput comes from crawling many sites in parallel.

Capacity

Interviewer: Size it.

You: Assumptions: 1 billion pages a month; an average HTML page of 100 KB uncompressed; compression of about 5× for storage; 50 links per page; 20 billion URLs known in total (far more than we crawl in a month); keep a year of page versions. Plan for a peak of twice the average.

Fetch rate
  1,000,000,000 pages / (30 × 86,400 s = 2,592,000 s) ≈ 386 pages/s
  × 2 for peaks                                       ≈ 800 pages/s

Bandwidth
  386 pages/s × 100 KB      ≈ 38.6 MB/s ≈ 310 Mbit/s average
  peak                      ≈ 620 Mbit/s → provision ~1 Gbit/s

Storage
  1B × 100 KB               = 100 TB/month raw
  ÷ 5 compression           ≈ 20 TB/month
  × 12 months               ≈ 240 TB  → object store

Links
  386 pages/s × 50 links    ≈ 19,300 link checks/s

Seen-URL set (Bloom filter at 1% false positives needs ~9.6 bits per URL)
  20B × 9.6 bits            ≈ 192 Gbit ≈ 24 GB
  split over 64 partitions  ≈ 375 MB each → fits in memory per worker

URL metadata
  20B URLs × ~200 B          ≈ 4 TB  → sharded key-value store

Concurrency (Little's law: in flight = rate × time per request)
  800 pages/s × ~2 s per fetch (DNS, connect, slow servers) ≈ 1,600 in flight
  an async fetcher holds ~500 connections → 4 machines minimum; run 10–20

Politeness check
  at one request per host every ~2 s, 800 pages/s needs ≥ 1,600 hosts active at once → easy
  but one big site with 10M pages at one page per 2 s = 20M s ≈ 230 days

Therefore:

• The fleet is modest: a handful of fetcher machines, a few cores for parsing. Scale is not the hard part.
• The link stream is 50 times the fetch stream, so the "have we seen this URL?" check must be cheap — hence a Bloom filter in memory.
• Big sites are the bottleneck, not the crawler. Each host gets a crawl budget by importance, and we fetch faster only where the site allows it.

What's being probed: whether the arithmetic changes the design.

Concept — Little's law. The number of requests in flight equals the arrival rate times how long each one takes. Slow servers do not reduce throughput if we keep enough requests in flight; they raise the number of open connections. That is why fetchers use asynchronous I/O — one thread juggling hundreds of sockets — instead of a thread per request. R14 covers timeouts that stop slow servers holding connections for ever.

Takeaway: Size connections with Little's law, size the seen-set by bits per URL, and notice that a single large site, not the fleet, sets the pace.

API

Interviewer: A crawler has no users. What is its API?

You: Two surfaces: an internal admin API for operators, and an output contract with the indexer.

The output is an event on a stream, one per new or changed page:

{ "type": "PageFetched",
  "url": "https://example.in/menu",
  "urlHash": "9f2c81d7a3b04e6f",
  "fetchedAt": "2026-10-09T08:15:22Z",
  "httpStatus": 200,
  "contentHash": "sha256:4b1e…",
  "simhash": "0x8a3f19c2d4e07b65",
  "storageKey": "pages/2026/10/09/9f2c81d7a3b04e6f.warc.gz",
  "outLinks": 47,
  "changed": true }

The page itself is in the object store; the event carries only the key. The indexer may see the same event twice after a crawler retry, so it treats (urlHash, contentHash) as an idempotency key (R3).

Data model

Interviewer: Data model.

You:

Everything about a host lives with the one worker that owns that host, so politeness is a local decision, not a distributed one.

High-level design

Interviewer: Draw it.

You: A loop: the frontier hands out URLs, fetchers download them, the parser extracts content and links, new links go back to the frontier. Play the flows: one page through the loop, politeness, duplicates and traps, a recrawl, and a worker failing.

One page, end to end:

1. The frontier's worker for host example.in sees that the host is due and pops https://example.in/menu.
2. The fetcher resolves the host from the DNS cache and checks the cached robots.txt: the path is allowed.
3. It fetches the page with a 10-second timeout and a size cap, gets 200 OK and 90 KB of HTML.
4. The parser extracts the text and 47 links. Content dedup hashes the page; the hash is new, so the page goes to the page store and a PageFetched event goes to the indexer.
5. The URL filter normalises the 47 links, throws away trap-like ones, and routes each to the partition that owns its host.
6. The owning partition checks each URL against its Bloom filter and the URL store. Twelve are new; they are written to the URL store and added to their host's queue.
7. The host's next allowed fetch time is set, say two seconds from now.

What's being probed: whether the loop is clear before the details.

Concept — the crawl loop. Every crawler is the same loop: pick a URL, fetch, parse, extract links, filter, add new ones. Everything interesting is about which URL to pick next (priority and politeness), which links to keep (normalisation, seen-check, traps), and which pages to keep (dedup). The loop is a pipeline of stages connected by queues, so each stage scales on its own (R9).

Takeaway: State the loop first; then each deep dive is about one arrow in it.

Deep dive — the URL frontier: priority and politeness

Interviewer: Which URL do you fetch next?

You: Two goals pull against each other. Priority says fetch the most important URLs first — a news home page before a forum post from 2009. Politeness says never hit one host twice in quick succession. A single priority queue would fail politeness: the top thousand URLs might all be on one big site. So the frontier has two layers, an idea that goes back to the Mercator crawler design of the late 1990s:

flowchart LR
  N[New and due URLs] --> P["Prioritiser"]
  P --> F1[Front queue high]
  P --> F2[Front queue medium]
  P --> F3[Front queue low]
  F1 --> R["Biased selector"]
  F2 --> R
  F3 --> R
  R --> B1[Host queue example.in]
  R --> B2[Host queue news.site]
  R --> B3[Host queue other hosts]
  B1 --> H["Heap of host ready times"]
  B2 --> H
  B3 --> H
  H --> W[Fetcher]

• Front queues, by priority. A prioritiser scores each URL — how important the page is (links pointing to it, its site's importance), how stale our copy is, how often it changes — and puts it in one of a few priority queues. A selector takes from them with a bias: high priority most often, low priority sometimes, so nothing starves.
• Back queues, one per host. Each URL moves from a front queue to its host's queue. A host has one queue and at most one fetch in flight.
• A heap of ready times. A min-heap holds, for each host, the earliest time we may fetch from it again. The fetcher always takes the host at the top of the heap.

loop:
    (host, readyAt) = heap.peek()
    if readyAt > now: wait until readyAt; continue
    heap.pop()
    url = hostQueue[host].poll()
    if robots(host).disallows(url): mark skipped; reschedule host now; continue
    start async fetch(url); when it finishes, taking `took` seconds:
        delay = max(robots(host).crawlDelay, 10 × took, 1 s)
        if response is 429 or 503: delay = max(delay, Retry-After, 2 × previous delay)
        if hostQueue[host] is empty: refill it from the front queues
        heap.push(host, now + delay)

Making the delay a multiple of how long the last fetch took means a server that slows down under load automatically gets fewer requests from us. A 429 Too Many Requests or 503 makes us back off further, honouring any Retry-After header.

Interviewer: How does that spread across many machines?

You: By hashing the host name to one of, say, 1,024 partitions, and assigning partitions to workers. All URLs of a host — whoever discovered them — are routed to that host's partition, so one worker owns each host's queue, ready time, robots rules, DNS entry and seen-set. No two machines can ever hit the same host at once, and no distributed lock is needed. One refinement: many small sites share one IP address on shared hosting, so the worker also keeps a ready time per IP, and limits fetches per IP as well as per host.

Hash each host to exactly one owner, and politeness becomes a single-machine rule.

What's being probed: whether priority and politeness are reconciled without a global lock.

Concept — partition by the thing you must serialise. If a rule says "one at a time per host", put every request for that host on one machine; then the rule is a local queue, not a coordination problem. R18 uses the same one-owner idea for chat rooms and order books, and BookMyShow's single writer per hot show (R19) is the same trick.

Takeaway: Priority queues decide what matters; per-host queues and a ready-time heap decide what is allowed now; hashing hosts to owners makes it distributed.

Deep dive — DNS, robots.txt and fetching safely

Interviewer: What does the fetcher actually have to worry about?

You: Three things before the request, and several during it.

DNS. Every fetch needs the host's IP address. A DNS lookup can take tens to hundreds of milliseconds, and public resolvers would not appreciate hundreds of lookups a second from us. So each worker caches answers for its own hosts, respecting each answer's time-to-live, and the fleet runs its own caching resolvers. Because a host always lives on the same worker, its cache entry is almost always warm.

robots.txt. Before fetching anything from a host, fetch https://host/robots.txt — a plain-text file in which a site lists the paths crawlers may not fetch, per crawler name. It is standardised as RFC 9309. The rules that matter:

• Cache it per host and refresh it about once a day; the standard says not to rely on a copy older than 24 hours unless the file cannot be fetched.
• If it returns 404 or another 4xx, there are no restrictions.
• If it returns a 5xx or cannot be reached, treat the whole site as disallowed until it comes back — a struggling server should not get crawled.
• Match the most specific rule for our user-agent; honour Crawl-delay where present, even though it is not part of the standard.

The fetch itself. Servers can be slow, huge or hostile, so every fetch has:

• A connect timeout (a few seconds) and an overall timeout (around 10–30 seconds).
• A maximum body size, say 10 MB; anything larger is truncated or skipped.
• A redirect limit (five or so), with each redirect target treated as a new URL that goes through the filter and the seen-check.
• Content-type checks: if it is not HTML, stop reading.
• A clear User-Agent naming the crawler and a URL explaining it, so site owners can identify and contact us.

Deep dive — normalising URLs and the seen-URL check

Interviewer: You extract 19,000 links a second. How do you avoid fetching the same page twice?

You: Two steps: make different spellings of the same URL identical, then check whether we already know it.

Normalisation — rewriting a URL into one standard form:

• Resolve relative links against the page's URL (../menu → https://example.in/menu).
• Lowercase the scheme and host; remove the default port (:443 for https, :80 for http).
• Remove the #fragment — it never reaches the server.
• Remove . and .. path segments; normalise percent-encoding.
• Drop known tracking and session parameters (utm_source, sessionid, jsessionid, sid); sort the remaining query parameters.
• If the page declares <link rel="canonical">, record that as the URL to prefer.

https://Example.IN:443/food/../menu?utm_source=x&b=2&a=1#top
→ https://example.in/menu?a=1&b=2

The seen check. We know 20 billion URLs; a database lookup for every one of 19,000 links a second is possible but wasteful, because most links point to pages we already know. A Bloom filter helps — a compact bit array that answers "definitely not seen" or "probably seen", using a few hash functions per URL. It never says "not seen" for a URL that was added, but it sometimes says "seen" for one that was not (a false positive, about 1% at our size).

check(url):                     // runs on the partition that owns url's host
    h = hash(normalised url)
    if not bloom.mightContain(h):            // definitely new
        bloom.add(h); urlStore.insertIfAbsent(h, url); frontier.add(url)
    else:                                    // probably seen — confirm
        if urlStore.insertIfAbsent(h, url):  // it was a false positive
            bloom.add(h); frontier.add(url)

The Bloom filter skips the store entirely for genuinely new URLs and adds no wrong answers, because a "probably seen" is confirmed against the durable store. If we wanted fewer store reads, we could trust the filter and accept missing about 1% of new URLs — and every link to a missed URL gets the same wrong answer until the filter is rebuilt. Some crawlers accept that loss. I prefer confirming; the store handles a few thousand reads a second easily. The filter is rebuilt from the URL store when a partition moves or restarts.

A Bloom filter cannot delete entries and only grows less accurate as it fills — size it for the URLs you expect, and rebuild it rather than patching it.

What's being probed: cheap membership at very high rate.

Concept — Bloom filter. Picture a long row of switches, all off. To add a URL, hash it a few different ways and turn on the switch each hash points at. To check a URL, look at its switches: if any is off, the URL was never added; if all are on, it probably was — other URLs may have turned them on. About ten bits per item gives about 1% false positives. R12 uses the same filter to stop cache penetration, where requests for keys that do not exist hammer the database.

Takeaway: Normalise first, then let a Bloom filter answer "definitely new" cheaply and a durable store settle the "maybe" cases.

Deep dive — duplicate content and crawler traps

Interviewer: Different URLs, same content?

You: Very common: mirrors, http and https versions, printer-friendly pages, the same article under several categories. Storing and indexing each copy wastes space and pollutes search results. Two checks after every fetch:

Exact duplicates. Compute a checksum (SHA-256, or a 64-bit hash) of the page's main text, after stripping markup and whitespace. Look it up in a table of content hashes; if present, record this URL as a duplicate of the existing page and do not store it again.

Near duplicates. Most copies are not identical — a different date, an advert, a counter. For those we use SimHash, a fingerprint designed so that similar documents get fingerprints that differ in only a few bits:

simhash(page):
    v = array of 64 zeros
    for each feature f in page (e.g. every run of 3 consecutive words), with weight w:
        h = 64-bit hash(f)
        for bit i in 0..63:
            v[i] += (bit i of h is 1) ? w : -w
    fingerprint = for each i, 1 if v[i] > 0 else 0

Two pages are near-duplicates if their fingerprints differ in at most a few bits; a 2007 Google paper on crawling found 64-bit fingerprints with a limit of 3 differing bits practical across billions of pages. Finding such matches fast uses a pigeonhole trick: split the 64 bits into 4 blocks of 16. If two fingerprints differ in at most 3 bits, at least one block must be identical. So keep 4 tables, each keyed by one block, look up the new page's 4 blocks, and compare full fingerprints only for those candidates.

Interviewer: And traps?

You: A crawler trap is a set of pages that generates an endless supply of new URLs, by accident or on purpose:

• An infinite calendar: every month page links to "next month", for ever.
• Session IDs in URLs: every visit produces new URLs for the same pages.
• Faceted navigation: ?colour=red&size=m&sort=price&page=7 — millions of combinations of a few hundred products.
• Relative-link loops that build /a/b/a/b/a/b/….
• Pages that return 200 OK with "not found" content (soft 404s), making every invented URL look real.

A single trap can quietly consume a host's entire crawl budget, or fill the frontier with junk, without any error ever being raised.

No single rule catches all of them, so we layer limits:

• Per-URL: maximum URL length (about 2,000 characters), maximum path depth, no path segment repeated more than a couple of times, known session parameters stripped.
• Per-host budget: a cap on pages per host per crawl cycle, scaled by the site's importance; when it is spent, the rest wait for the next cycle.
• Depth from seed: URLs far from any well-linked page get low priority and eventually are not followed.
• Pattern detection: if a host keeps producing pages that are near-duplicates of each other, or new URLs whose content hash we already have, down-rank that URL pattern for the host.
• Manual rules: operators can block a pattern for a host through the policy API.

What's being probed: defending against an adversarial, unbounded input.

Concept — budgets beat detection. You cannot recognise every trap, but you can bound how much damage any one site can do: a page budget per host, a depth limit, a URL length limit. Detection then improves efficiency, while budgets guarantee safety. It is the same reasoning as rate limiting in R17: cap each tenant so one bad actor cannot starve the rest.

Takeaway: Bound every host with budgets and limits first; use duplicate signals and patterns to spend those budgets well.

Deep dive — recrawling and freshness

Interviewer: About 1 billion fetches a month. How much of that is recrawl, and how do you decide when?

You: As an assumption, about 70% recrawls of known pages and 30% new discoveries. The question is how often to revisit each page. Pages change at very different rates: a news home page changes every few minutes, a company's "about us" page every few years. Recrawling everything equally wastes most fetches.

So each URL gets its own interval, adjusted by what we observe:

after each fetch of url:
    if content changed since last fetch:  interval = max(minInterval, interval / 2)
    else:                                 interval = min(maxInterval, interval × 1.5)
    interval = interval / importanceFactor        // important pages come back sooner
    nextDue = now + interval                      // stored in URL metadata

Three things make recrawls cheap:

• Conditional requests. Send If-None-Match with the page's last ETag, or If-Modified-Since with the last fetch time; an unchanged page answers 304 Not Modified with no body.
• Sitemaps. Many sites publish an XML sitemap with a lastmod date per URL; that is a direct hint about what changed.
• Change detection by fingerprint. If the content hash is unchanged, nothing goes to the indexer.

The recrawl scheduler is a delayed-job problem: millions of URLs, each due at its own time. It is exactly R17's distributed job scheduler — time-bucketed due lists, scanned bucket by bucket, each due URL pushed into the frontier with a recrawl priority. The frontier then applies politeness as usual, so a host with many due URLs is still fetched gently.

Freshness comes from spending fetches where pages actually change, not from crawling faster.

Deep dive — coordination and a worker failing

Interviewer: A worker dies. What happens to its hosts?

You: Each worker holds leases on a set of host partitions, granted by a coordinator such as ZooKeeper or etcd (R8). A lease is a time-limited claim that the worker renews every few seconds. If the worker dies, it stops renewing; the lease expires; the coordinator gives those partitions to other workers.

The new owner rebuilds the partition's state:

1. The frontier for that partition is durable — a log of enqueued URLs plus periodic checkpoints — so it reloads the host queues from the last checkpoint and replays the log.
2. It rebuilds the partition's Bloom filter from the URL store, or loads its last saved copy.
3. Host records (robots rules, ready times) come from the host store; DNS warms up again on demand.
4. URLs that were in flight when the old worker died have no "fetched" record, so they are fetched again. That is at-least-once fetching; the content hash makes the duplicate harmless, and the indexer's idempotency key absorbs a repeated event.

One danger: a worker that was only paused — a long garbage-collection pause, a network blip — may wake up still believing it owns the partition while the new owner is also fetching. Two owners means double the load on those hosts. The fix is a fencing token: every lease grant carries an increasing epoch number, writes to the frontier log and URL store carry it, and stores reject writes from an older epoch. The paused worker's first write fails, and it stops (R8 covers fencing).

Adding capacity is the same mechanism in reverse: start a worker, and the coordinator moves some partitions to it. With many more partitions than workers (1,024 partitions over 20 workers), the load spreads evenly and moves in small pieces, much like consistent hashing in R17's key-value store.

Deep dive — politeness, law and ethics

Interviewer: Beyond robots.txt, what are your obligations?

You: A crawler is welcome only as long as it behaves well. The rules I would build in:

A well-behaved crawler

• Identifies itself: a stable User-Agent with a URL explaining what it is and how to contact the operator or opt out.
• Obeys robots.txt and noindex / nofollow directives in page meta tags and X-Robots-Tag headers.
• Backs off on 429, 503 and rising response times, and honours Retry-After.
• Never logs in, bypasses paywalls or CAPTCHAs, or fetches pages that require accepting terms.
• Gives site owners a way to slow down or stop crawling, and acts on removal requests.
• Treats personal data carefully: keeps only what indexing needs, honours deletion requests, and follows privacy laws such as the EU's GDPR and India's Digital Personal Data Protection Act.
• Respects copyright: storing pages for indexing is not the same as republishing them.

Legal questions — what may be crawled, stored and shown — depend on the country and change over time, so they belong with the legal team; the engineering job is to make every one of these controls easy to apply per host and per pattern.

Failures and scale

Interviewer: What breaks?

You:

Curveballs

Interviewer: Now render JavaScript-heavy pages.

You: A second, separate tier of headless-browser workers, perhaps ten to a hundred times costlier per page. The normal fetcher detects pages that are mostly script with little text and queues them for rendering with their own lower rate. Politeness still applies — a rendered page also fetches its scripts and API calls from the site.

Interviewer: A breaking news story — we need new pages within minutes.

You: A fast lane: a short list of news sites and their sitemaps or feeds polled every minute or two, with high priority in the frontier. Their new URLs skip the normal queue but not the per-host delay.

Interviewer: A site owner complains we are hammering them.

You: Check the logs for that host's request rate. The policy API lets operators set a lower rate or block the host at once; the owning worker picks it up on its next refresh of the host record. Then fix the cause — usually several host names on one server, which is what the per-IP limit is for.

Interviewer: Crawl ten times more pages.

You: Fetching, parsing and storage scale out linearly — more workers, more partitions moved to them, more object storage. The Bloom filter and URL store grow with known URLs, not crawl rate. The limit that does not move is politeness: more pages from the same sites takes longer, so growth means crawling more sites, and spending each site's budget on its most important and most changed pages.

Quick reference

The 60-second version

A crawler is a loop — take a URL from the frontier, fetch it, parse it, keep new links — and at a billion pages a month it needs only about 400 fetches a second, 300 Mbit/s and a small fleet; the hard parts are politeness, duplicates and traps. The frontier puts URLs in priority queues, then into one queue per host, with a heap of the time each host may next be fetched, so important pages go first but no site is hit too often; the delay grows with the server's response time and backs off on 429 or 503. Hosts are hashed to partitions owned by one worker each, under leases with fencing tokens, so politeness, robots.txt, DNS caching and the seen-URL check are all local decisions, and a dead worker's partitions move to another that replays a durable frontier log. Links are normalised and checked against a Bloom filter backed by a durable URL store; content is deduplicated by checksum and by SimHash fingerprints that differ in only a few bits for near-copies. Traps such as endless calendars and session IDs are contained by URL limits and per-host budgets. Recrawls use an adaptive interval per URL, conditional requests and R17's scheduler, and every new or changed page lands in an object store with an idempotent event for the indexer.

What to say in the interview

"Lookup systems are read-heavy, so I decide the answer in advance and make every read one fetch. I start by choosing the key — the short code, the prefix, the map cell — then precompute the answer for each key: the mapping, the top ten per prefix, the places per cell. Hot keys are cached at the edge and in memory, and indexes are rebuilt offline, versioned and swapped without stopping reads. The write side stays off the read path behind a queue: clicks, query logs and business updates flow in asynchronously. And when the job is to build the index itself, as with a crawler, the hard parts move to politeness, deduplication and freshness: one queue per host, a Bloom filter for seen URLs, fingerprints for duplicate content, and recrawls scheduled by how often each page changes."