System Design · Lesson 16 of 18

Typeahead and Nearby Search

Tries, prefix caches, geohash, quadtrees and proximity queries.

  • Advanced
  • 60 min read
  • 6 objectives

Before this lessonLesson 15: Web Crawler

What you will learn

  • Build a trie that answers top-K suggestions in O(prefix length)
  • Refresh rankings offline with decay, sampling and snapshot swaps
  • Partition, replicate and cache a typeahead fleet, and cut load at the client
  • Explain why lat/lng B-trees fail and fix it with geohash and neighbour cells
  • Build an adaptive QuadTree and choose between grid, geohash, S2 and R-tree
  • Adapt proximity search for moving objects like drivers

Your Progress

0 of 18 lessons 0%

  • Lessons0 / 18
  • Completed0
  • Est. time left~ 16 hours

Progress is saved in this browser. No account needed.

Tip: pressing Next marks this lesson complete automatically.

This lesson covers two designs that interviewers often ask back to back, because they are the same idea underneath: typeahead (search suggestions as you type) and nearby search (the places, or drivers, around a point). In both, a request arrives with a partial key. For typeahead it is a string prefix. For nearby search it is a region of the map. The answer has to be the best few matches out of hundreds of millions, in tens of milliseconds, over and over.

The shared lesson is precompute the answer and make the key the index. You cannot scan 150 million phrases on each keystroke, and you cannot compute the distance to 200 million businesses on each map pan. So in both designs you build a structure offline where the partial key points straight to a small, already-ranked answer: a trie node that holds its own top ten, or a geohash cell that holds its own places. What differs is how the data changes. Suggestions are rebuilt every hour from logs. Places change a few times a second. Drivers move 300,000 times a second, and that one difference changes the whole design, which is why the lesson ends with moving objects as a contrast.

Part A is typeahead, Part B is nearby search, and Part C is what changes when the points move.

Part A — Typeahead suggestions

Step 1 — Clarify the requirements

Functional, in scope

  • As the user types into a search box, return the top 10 completions of the current prefix, ranked by popularity.
  • Popularity is recency-weighted: a phrase that trended in the last few hours should beat one that was popular last year.
  • Suggestions are lightly personalised: the user's own recent searches appear first.
  • A denylist can remove a phrase (legal takedown, hate, spam) and the removal must take effect within minutes, not at the next rebuild.
  • Case-insensitive, prefix match on the whole phrase (typing new y suggests new york weather).

Out of scope (say it out loud)

The search results page itself, spelling correction as a full system (we will mention the edit-distance fallback), mid-word or infix matching (york suggesting new york), and ads in the suggestion list. Each is a real feature, and naming them shows you know where this system's edges are.

Non-functional

  • Latency: suggestions must feel instant. For that the server p99 needs to be under 20 ms, which leaves room for the network and still keeps end-to-end p99 under about 100 ms. A suggestion that shows up after the user has typed the next character is useless.
  • Throughput: hundreds of thousands of suggestion requests per second (see the estimate below). This is one of the highest-QPS endpoints a company runs.
  • Freshness: a new trend should appear within an hour, and a breaking one within about 10 minutes through a fast path. Full rebuilds can be daily.
  • Availability over consistency: suggestions that are a few minutes stale, or that differ slightly between two replicas, are fine. Returning nothing is acceptable too. Search still works without suggestions, so this service must never block the search box.

Step 2 — Back-of-the-envelope estimation

SEARCHES_PER_DAY = 3_000_000_000      # a large search engine / marketplace
SECONDS_PER_DAY  = 86_400
avg_chars        = 18                  # typical finished query length
keystroke_ratio  = 0.35                # after debounce, ~1 request per 3 chars typed

qps_search = SEARCHES_PER_DAY / SECONDS_PER_DAY
qps_suggest = qps_search * avg_chars * keystroke_ratio
print(f"searches: {qps_search:,.0f}/s avg   suggest calls: {qps_suggest:,.0f}/s avg, "
      f"{qps_suggest * 3:,.0f}/s peak")

# --- How many distinct phrases are worth indexing? ---
unique_share   = 0.15                  # most searches repeat
unique_per_day = SEARCHES_PER_DAY * unique_share
kept_phrases   = 150_000_000           # after dropping the long tail (seen < N times)
print(f"unique phrases/day: {unique_per_day/1e6:,.0f}M   indexed: {kept_phrases/1e6:,.0f}M")

# --- Memory for the trie ---
bytes_per_char   = 1                   # UTF-8, mostly ASCII; CJK is 3
nodes            = kept_phrases * 6    # prefix sharing: ~6 new nodes per phrase
node_overhead    = 40                  # child map slot, counts, pointers (compact impl)
top_k            = 10
top_entry_bytes  = 8 + 4               # pointer to terminal node + 32-bit score
trie_gb  = nodes * node_overhead / 1e9
tops_gb  = nodes * top_k * top_entry_bytes / 1e9
text_gb  = kept_phrases * avg_chars * bytes_per_char / 1e9
print(f"nodes: {nodes/1e9:.1f}B   structure: {trie_gb:.0f} GB   "
      f"top-{top_k} lists: {tops_gb:.0f} GB   phrase text: {text_gb:.1f} GB")
print(f"total per full replica: ~{trie_gb + tops_gb + text_gb:.0f} GB")

# --- Offline pipeline input ---
log_bytes = 120                        # query, user/session, locale, ts, clicked?
print(f"raw query log: {SEARCHES_PER_DAY * log_bytes / 1e9:,.0f} GB/day")
Output
searches: 34,722/s avg   suggest calls: 218,750/s avg, 656,250/s peak
unique phrases/day: 450M   indexed: 150M
nodes: 0.9B   structure: 36 GB   top-10 lists: 108 GB   phrase text: 2.7 GB
total per full replica: ~147 GB
raw query log: 360 GB/day

What the numbers decide

  • 650k requests/s at peak is too much for a database lookup per request, but it is easy for an in-memory structure. The trie lives in RAM on the serving boxes, and each box answers from local memory in microseconds.
  • The top-K lists are three times larger than the trie itself. Storing ten completions at every one of 900M nodes is the expensive part. Two fixes follow. First, store pointers to terminal nodes, not copies of the phrase strings. Second, only keep top-K lists for nodes whose subtree has real traffic. Deep nodes like javascript array prototype fla are cheap to compute on demand, because their subtree is tiny.
  • ~150 GB per full copy fits on one large machine, but only just, and it grows. So we partition for memory and replicate for QPS. These are two independent choices, and it helps to keep them apart when you explain the design.
  • 360 GB/day of logs is a batch problem, not a streaming one. Aggregate offline, rebuild, and ship a snapshot.

A common wrong answer is "I will store the phrases in a SQL table and run LIKE 'jav%'". A B-tree can serve a prefix range, but it returns every phrase with that prefix. Ranking them means sorting thousands of rows on each keystroke, and for a one-character prefix it means millions. The whole point of the design is to precompute the ranking.

Step 3 — API

## Global suggestions (cacheable at the CDN, identical for every user in a locale)

GET /api/v1/suggest?q=jav&n=10&locale=en-IN
  -> 200 { q: "jav", v: 812,
           items: [ { text: "javascript", kind: "query" },
                    { text: "java",       kind: "query" },
                    { text: "java tutorial", kind: "query" } ] }
     Cache-Control: public, max-age=60        # 300 for 1-2 character prefixes
     Vary: Accept-Language
  -> 200 { items: [] }      # no match: empty list, never 404
  -> 400                    # q longer than 100 chars, or n > 20
  -> 429 + Retry-After      # per-IP limit (scrapers love this endpoint)

  # q is normalised by the client AND the server: lowercase, NFKC, trim,
  # collapse whitespace. v is the trie snapshot version that served it.

## Personal suggestions (private, never cached at the edge)

GET /api/v1/suggest/personal?q=jav&n=3
  Authorization: Bearer ...
  -> 200 { items: [ { text: "javascript closures", kind: "history",
                      last_used: "2026-09-21T10:02:00Z" } ] }

DELETE /api/v1/suggest/personal/history          # "clear my search history"
  -> 204

## Logging (fire-and-forget, batched by the search service, not the browser)

POST /internal/v1/query-log   [{ q, locale, session_hash, ts, clicked_rank? }]
  -> 202

API decisions worth defending

  • GET with cacheable, normalised keys. Lowercase, trim and collapse spaces before building the URL, so Java, java and java all hit one cache entry. Normalising on the server as well is necessary but not enough, because the CDN keys on the raw URL.
  • A v (snapshot version) in the response. When a request fans out to several shards, the aggregator can see that shards disagree during a rollout. It also lets you tie a bad suggestion to the build that produced it.
  • Personalisation is a separate, uncacheable call (or it is merged at the edge). Mixing a user's history into the global response would make every response private and wipe out the CDN hit rate.
  • 204 or an empty list, never an error, when nothing matches. The client should silently show nothing.

Step 4 — Data model

-- =========================================================
-- IN MEMORY on each trie server (one partition of the trie)
-- =========================================================
Node {
  edge:      bytes            -- compressed (radix) trie: a whole substring per edge
  children:  sorted array of (first_byte, Node*)   -- binary search, not a hashmap:
                                                    -- far smaller for fan-out < 8
  weight:    uint32           -- score if a phrase ends here, else 0
  parent:    Node*            -- lets us rebuild a phrase from its terminal node
  top:       [(uint32 score, Node* terminal)] x 15   -- only on nodes with traffic;
                                                      -- 12 bytes each, not 30+
}

-- =========================================================
-- OFFLINE (warehouse / object store)
-- =========================================================
query_log            -- Kafka topic -> hourly Parquet files, 30-day retention
  ts, locale, q_normalised, session_hash, result_clicked BOOLEAN

phrase_scores        -- the output of the hourly aggregation job
  locale       TEXT,
  phrase       TEXT,
  ema_score    DOUBLE,     -- recency-weighted popularity (see Step 8)
  ctr          REAL,       -- how often the suggestion is picked when shown
  flags        SMALLINT,   -- adult, denied, person_name ...
  updated_at   TIMESTAMP,
  PRIMARY KEY (locale, phrase)

trie snapshots       -- s3://typeahead/en-IN/v812/part-03.bin  (+ manifest.json
                     -- listing parts, key ranges, checksums, build time)

-- =========================================================
-- KEY-VALUE (Redis / Cassandra)
-- =========================================================
sugg:v812:en-IN:javasc      -> serialized response        TTL 300 s
hist:user:48213             -> list of (phrase, ts), newest first, capped at 50
denylist:v37                -> set of normalised phrases + patterns (pushed to boxes)
partition_map:en-IN:v812    -> [("a", "aqz", shard_1), ("ar", "bxa", shard_2), ...]

Why store pointers in the top-K lists rather than strings? A popular phrase like javascript tutorial appears in the top-K list of every one of its 19 prefixes. Storing the 19-byte string 19 times per phrase, across 150M phrases, is where the memory goes. An 8-byte pointer to the terminal node, which has a parent pointer to rebuild the text (or an id into a phrase table), cuts that by more than half.

Why a compressed (radix) trie? Most long phrases have a unique tail. After javascript tutorial f there may be only one path, or beginners. A radix trie merges single-child chains into one edge labelled with the whole substring. In a phrase dictionary this often removes most of the nodes, and it shortens the pointer walk.

Step 5 — The core algorithm: a trie with top-K at every node

The naive trie answers suggest("ja") by walking the whole subtree under ja and sorting. That subtree can hold millions of phrases, and a phrase like system design interview questions is 33 levels deep. Instead, each node caches the best K phrases in its subtree. A query then walks only the prefix, which is at most about 20 hops, and reads a list. Here is the whole idea, with offline build, query, the incremental bump used for trending terms, and the disk snapshot:

STORED = 5     # keep a few spares per node so a denylist filter can still fill SERVED
SERVED = 3

class Node:
    __slots__ = ("children", "weight", "top")
    def __init__(self):
        self.children: dict[str, "Node"] = {}
        self.weight = 0                  # score of the phrase that ENDS here (0 = not a phrase)
        self.top: list[tuple[int, str]] = []   # best-first [(score, phrase)], len <= STORED

def rank(cands):
    # Highest score first; ties broken alphabetically so results are deterministic.
    return sorted(cands, key=lambda t: (-t[0], t[1]))[:STORED]

class Trie:
    def __init__(self):
        self.root = Node()

    # ---------- offline build: insert everything, then fill tops bottom-up ----------
    @classmethod
    def build(cls, scored_phrases):
        t = cls()
        for phrase, score in scored_phrases:
            node = t.root
            for ch in phrase:
                node = node.children.setdefault(ch, Node())
            node.weight += score
        t._fill(t.root, "")
        return t

    def _fill(self, node, prefix):
        cands = [(node.weight, prefix)] if node.weight else []
        for ch, child in node.children.items():
            self._fill(child, prefix + ch)
            cands.extend(child.top)          # a child's top-K is all the parent needs
        node.top = rank(cands)

    # ---------- online read: O(len(prefix)), no subtree walk ----------
    def suggest(self, prefix, deny=frozenset()):
        node = self.root
        for ch in prefix.lower():
            node = node.children.get(ch)
            if node is None:
                return []
        return [p for _, p in node.top if p not in deny][:SERVED]

    # ---------- incremental bump (trending fast path) ----------
    def bump(self, phrase, delta):
        path, node = [self.root], self.root
        for ch in phrase:
            node = node.children.setdefault(ch, Node())
            path.append(node)
        node.weight += delta
        new = node.weight
        for n in reversed(path):             # terminal node back up to the root
            others = [t for t in n.top if t[1] != phrase]
            n.top = rank(others + [(new, phrase)])
            if (new, phrase) not in n.top and len(n.top) == STORED:
                break                        # not good enough here -> not good enough above

    # ---------- snapshot to disk: pre-order "char, weight, child count" ----------
    def dump(self):
        out = []
        def walk(n, ch):
            out.append(f"{ch}{n.weight}/{len(n.children)}")
            for c in sorted(n.children):
                walk(n.children[c], c)
        walk(self.root, "^")
        return "|".join(out)      # "|" because phrases contain spaces

    @classmethod
    def load(cls, blob):
        tokens = iter(blob.split("|"))
        def read():
            tok = next(tokens)
            ch, rest = tok[0], tok[1:]
            weight, kids = map(int, rest.split("/"))
            n = Node(); n.weight = weight
            for _ in range(kids):
                c, child = read()
                n.children[c] = child
            return ch, n
        t = cls(); _, t.root = read()
        t._fill(t.root, "")                   # tops are NOT stored; recompute on load
        return t


logs = [("java", 900), ("javascript", 1400), ("java tutorial", 300),
        ("jaguar", 250), ("japan", 700), ("jam recipe", 120),
        ("jazz", 410), ("jav", 5)]
t = Trie.build(logs)
print("ja   ->", t.suggest("ja"))
print("jav  ->", t.suggest("jav"))
print("jaz  ->", t.suggest("jaz"))
print("xyz  ->", t.suggest("xyz"))
print("ja (deny japan) ->", t.suggest("ja", deny={"japan"}))

t.bump("jaguar", 1500)                        # a new car launch goes viral
print("after bump, ja ->", t.suggest("ja"))

blob = t.dump()
print("snapshot nodes:", blob.count("|") + 1, "  head:", blob[:30])
t2 = Trie.load(blob)
print("reloaded ja ->", t2.suggest("ja"))
Output
ja   -> ['javascript', 'java', 'japan']
jav  -> ['javascript', 'java', 'java tutorial']
jaz  -> ['jazz']
xyz  -> []
ja (deny japan) -> ['javascript', 'java', 'jazz']
after bump, ja -> ['jaguar', 'javascript', 'java']
snapshot nodes: 37   head: ^0/1|j0/1|a0/5|g0/1|u0/1|a0/1|
reloaded ja -> ['jaguar', 'javascript', 'java']

What the code is teaching

  • Bottom-up build is linear. A parent's top-K is the merge of its children's top-K lists plus its own weight. You never look deeper than one level, so the build costs O(nodes × K), not O(nodes × subtree size).
  • The query does no ranking. suggest costs O(len(prefix)) pointer hops plus a list read. That is how you get microseconds.
  • Store a few spares. We keep 5 and serve 3 (in production, keep about 15 and serve 10). When the denylist removes japan, jazz moves up without a rebuild. If you store exactly K, every filtered item leaves a hole.
  • Increments are cheap, decrements are not. bump walks from the terminal node back to the root. It stops as soon as the phrase fails to make a node's list, because if it is not in the top five for jag, it cannot be in the top five for ja. A decrease is different. If a phrase falls out of a list, the replacement could be anywhere in the subtree, and only children's lists can tell you which. This is the real reason trie updates are done as an offline rebuild, and it is worth saying explicitly.
  • The snapshot does not store the top-K lists. A pre-order walk writes each node as its character, weight and child count. That is enough to rebuild the shape, and _fill recomputes every list on load. The file is small, and a server that restarts can load and fill it in minutes.

Step 6 — High-level design

flowchart LR subgraph Online["Online path (per keystroke)"] B[Browser / app
debounce, local cache] --> CDN[CDN edge cache
short-prefix responses] CDN -->|miss| GW[API gateway] GW --> AGG[Suggest aggregator] AGG --> PC[(Prefix cache
Redis)] AGG --> T1[Trie shard A-F
replicas x3] AGG --> T2[Trie shard G-M
replicas x3] AGG --> T3[Trie shard N-Z
replicas x3] AGG --> PH[(Personal history
per user)] AGG --> DL[(Denylist
pushed to every box)] end subgraph Offline["Offline path (hourly / daily)"] SL[Search service] --> K[(Kafka: query log)] K --> AGGJ[Batch aggregation
counts per phrase per hour] AGGJ --> SC[(Phrase scores
EMA table)] SC --> BLD[Trie builder] BLD --> OBJ[(Object store
versioned snapshots)] OBJ -->|load + swap| T1 OBJ -->|load + swap| T2 OBJ -->|load + swap| T3 K --> TR[Trending detector
streaming, 5-min windows] TR -->|bump| T1 end

Reads never touch the offline side. Trie servers only answer queries. They load a finished snapshot and swap it in, and a small streaming path pushes breaking trends between builds.

What each component owns

  • Client: debounces keystrokes, cancels stale requests, caches recent responses, and prefetches. It removes most requests before they are ever sent (see Step 9).
  • CDN edge: caches responses for short prefixes (one to three characters) for 60 to 300 seconds. There are only about 30,000 three-character prefixes, and they get the most traffic.
  • Aggregator: normalises the prefix, looks up the partition map, fans out to one or more trie shards, merges their top-K lists, applies the denylist, and merges in personal history. It is stateless.
  • Trie servers: hold one partition of the trie in RAM and answer top(prefix). They are read-only between snapshot swaps.
  • Prefix cache (Redis): stores the merged, post-denylist responses for hot prefixes that need a fan-out, so the aggregator does not merge the same shards thousands of times per second.
  • Batch aggregation plus EMA table: turns raw logs into one score per phrase (Step 8).
  • Trie builder: builds and fills each partition, validates it (size, spot checks against the old version), and publishes a versioned snapshot.
  • Trending detector: a streaming job that sees a phrase jump, for example 50x its baseline in 5 minutes, and calls the bump fast path on live servers.

Step 7 — Walk one keystroke end to end

sequenceDiagram participant U as User participant C as Client participant E as CDN edge participant A as Aggregator participant R as Prefix cache participant T as Trie shards participant H as Personal history U->>C: types jav, then keeps typing C->>C: debounce 100 ms, check local cache for jav C->>C: abort in-flight request for ja C->>E: GET /suggest?q=jav&n=10&locale=en-IN E-->>C: HIT (short prefix, max-age 120) — done Note over C,E: Longer prefix javasc misses the edge C->>E: GET /suggest?q=javasc E->>A: forward (miss) A->>A: normalise, look up partition map: shard G-M only A->>R: GET sugg:v812:en:javasc R-->>A: miss A->>T: top(javasc, 15) on one replica (hedged after 8 ms) T-->>A: 15 (score, phrase) pairs A->>A: drop denylisted, keep 10 A->>R: SETEX sugg:v812:en:javasc 300 A-->>E: 200 {v: 812, items: [...]} Cache-Control max-age=60 E-->>C: 200 C->>H: GET /suggest/personal?q=javasc (parallel, private) H-->>C: [javascript closures] C->>U: personal first, then global, dedupe

Most keystrokes never reach the origin. They are removed by debounce or the local cache, or answered at the edge. The ones that do reach the origin touch one shard, one cache key and no disk.

The order of operations, and why

  1. Debounce, then abort. The client waits until the user pauses before it sends a request, and it cancels the previous in-flight request so a slow ja response cannot overwrite a fast jav response. Without this, suggestions visibly flicker backwards.
  2. Local cache before network. Backspacing from javas to java should cost nothing, because the client already has that response.
  3. Edge cache for short prefixes. A handful of keys covers a large share of traffic, and they are identical for every user in a locale.
  4. The partition map decides the fan-out. javasc lives on exactly one shard. A single-character prefix like j may span two shards and needs a merge, which is exactly why short prefixes are the ones we cache hardest.
  5. Ask for 15 and serve 10. The spares absorb denylist removals.
  6. Hedge the shard call. If the first replica has not answered in 8 ms, which is about its p95, send the same request to a second replica and use whichever answers first. The request is idempotent and cheap, so hedging cuts the p99 at the cost of about 5% extra load.
  7. Personal history is fetched in parallel and merged on the client. The global response stays cacheable, and the private part never touches a shared cache.

Step 8 — Building and updating the trie offline

Updating the live trie on every search would mean 35,000 writes per second, each one walking up to the root and taking locks that the 650,000 reads per second then wait on. Reads matter more than freshness here, so updates are batched offline.

The pipeline

  1. Log. The search service writes every submitted query to Kafka, including the query text, locale, a hashed session id, the timestamp and whether a result was clicked. Log submitted searches, not keystrokes. Otherwise the suggestions learn to suggest themselves.
  2. Aggregate hourly. A batch job (Spark, or MapReduce in older stacks) groups by (locale, normalised phrase) and counts. It drops phrases below a threshold, such as fewer than 50 distinct sessions per day. That removes typos, private information such as names and phone numbers, and the long tail that would never make a top-10 list anyway.
  3. Score with decay. Rather than re-summing a sliding 30-day window, keep one exponentially weighted moving average per phrase and update it with the latest hour's count.
  4. Build. Build each partition from the score table, fill the top-K lists bottom-up, validate, and write a versioned snapshot to object storage.
  5. Swap. Each trie server loads the new snapshot next to the old one, warms it, and switches a single pointer. If a replica does not have room for two copies, drain it from the load balancer, load the new snapshot, and put it back, one replica at a time. This is the same as a primary/standby flip: the standby loads while the primary serves.
import math, random

HALF_LIFE_H = 24.0                      # a search's weight halves every day
ALPHA = 1 - 0.5 ** (1 / HALF_LIFE_H)    # per-hour smoothing factor for the EMA

def ema_update(old_score, this_hour_count):
    """One hourly job step. No need to keep the whole history: the old score
    already summarises it, so the job reads old score + one hour of counts."""
    return old_score * (1 - ALPHA) + this_hour_count * ALPHA

# 7 days of hourly counts for two phrases
evergreen = [400] * 168                              # steady every hour
launch    = [0] * 160 + [3000] * 8          # a launch trending for the last 8 hours

s_ever = s_new = 0.0
for hour, (a, b) in enumerate(zip(evergreen, launch)):
    s_ever, s_new = ema_update(s_ever, a), ema_update(s_new, b)
    if hour in (159, 163, 167):
        print(f"hour {hour:3d}: evergreen={s_ever:7.1f}  launch={s_new:7.1f}")

print(f"raw 7-day totals: evergreen={sum(evergreen):,}  launch={sum(launch):,}")

# --- Sampling the log: count 1 in N, then scale back up ---
random.seed(7)
N = 100
true_count = 25_000
sampled = sum(1 for _ in range(true_count) if random.random() < 1 / N)
print(f"sampled 1/{N}: {sampled} hits -> estimate {sampled * N:,} (true {true_count:,})")
rare = sum(1 for _ in range(150) if random.random() < 1 / N)
print(f"a phrase searched 150 times -> {rare} sampled hits (fine: below the index cut-off)")
Output
hour 159: evergreen=  396.1  launch=    0.0
hour 163: evergreen=  396.5  launch=  327.3
hour 167: evergreen=  396.9  launch=  618.9
raw 7-day totals: evergreen=67,200  launch=24,000
sampled 1/100: 262 hits -> estimate 26,200 (true 25,000)
a phrase searched 150 times -> 1 sampled hits (fine: below the index cut-off)

Two results matter here. First, the EMA lets an 8-hour trend overtake a phrase that has three times more searches over the week. A raw 7-day count would never promote it. Second, sampling the log at 1 in 100 estimates popular phrases to within a few percent and cuts pipeline cost by 100x. The phrases it gets wrong are the rare ones, and those are below the index cut-off anyway. You can only sample if you do not need the long tail, so say that condition out loud.

Removing a phrase

A legal takedown cannot wait for tonight's build. Two layers handle it. A denylist filter on every aggregator and trie server applies to results as they are served (this is why we store spares). The denylist is small, is pushed as a config update within a minute, and matches normalised phrases and, optionally, patterns. The next build then drops the phrase from the input, so it is removed from the structure too. The filter stays in place as defence in depth.

Ranking beyond counts

The score that goes into the trie can be any offline-computed number. In practice it blends decayed frequency, click-through rate on the suggestion (a suggestion people ignore should sink), freshness, locale and region (football means different sports in London and Dallas), and a quality penalty for adult or low-value content. Build a separate trie, or a separate score column, per locale. Anything that depends on the individual user is applied at serving time, not baked into the trie.

Step 9 — The client: the cheapest request is the one you never send

The client removes more load than any server-side optimisation. A simulation of one person typing javascript tutorial, with realistic gaps between keystrokes:

# Keystroke timestamps (ms) for someone typing "javascript tutorial":
# quick bursts, one pause after "javascript", a longer think before "tutorial".
gaps = [0, 90, 80, 110, 95, 85, 100, 90, 120, 105,   # j a v a s c r i p t
        380,                                          # (space) - a pause
        140, 95, 90, 100, 85, 110, 95, 90]            # t u t o r i a l
times, t = [], 0
for g in gaps:
    t += g; times.append(t)
text = "javascript tutorial"

def requests_sent(debounce_ms, min_chars=2):
    """A request fires when the user has been idle for debounce_ms.
    Keystrokes before min_chars never fire (1-char prefixes come from a
    prefetched/CDN list instead)."""
    sent = []
    for i, ts in enumerate(times):
        nxt = times[i + 1] if i + 1 < len(times) else float("inf")
        if nxt - ts >= debounce_ms and i + 1 >= min_chars:
            sent.append(text[: i + 1])
    return sent

for d in (0, 50, 100, 150):
    s = requests_sent(d, min_chars=1 if d == 0 else 2)
    print(f"debounce {d:3d} ms -> {len(s):2d} requests  {s if len(s) <= 4 else ''}")
Output
debounce   0 ms -> 19 requests  
debounce  50 ms -> 18 requests  
debounce 100 ms ->  9 requests  
debounce 150 ms ->  2 requests  ['javascript', 'javascript tutorial']

From 19 requests down to 2, with no visible change for the user, because a fast typist does not read suggestions mid-word. The exact debounce value is a product trade-off. At 50 ms almost nothing is saved. At 150 ms or more the suggestions start to feel laggy for slow typists. Most real systems use somewhere between 80 and 150 ms and tune it with an A/B test. The other client techniques:

  • Minimum length. Do not call the server for the first character. Ship the top suggestions for all 26 (or all locale-specific) one-character prefixes as a small static file on page load.
  • Cancel in-flight requests with AbortController when a newer keystroke arrives, and discard any response whose prefix no longer matches the input box.
  • Local response cache, keyed by prefix, for the session. This makes backspace free.
  • Prefetch. When the response for jav arrives, the client can speculatively request java, the most likely next prefix. Or the server can return a slightly deeper result set for short prefixes, so the client can filter locally for the next character or two.
  • Warm the connection early. Open the TLS connection, and keep an HTTP/2 connection alive, as soon as the search box gets focus. A cold TLS handshake on the first keystroke costs more than the whole server-side lookup.
  • Local history. Recent searches stored on the device are the most reused suggestions of all, and they need no network call.

Step 10 — Partitioning, replication and caching

The trie needs to be split across machines once one copy no longer fits in memory, or once rebuilding it on one machine takes too long. There are three ways to split it, and interviewers expect you to compare all three.

import bisect, zlib

# Phrases sorted lexicographically, with how much memory each one's subtree costs.
phrases = sorted(["a", "aa", "aab", "aardvark", "abacus", "able", "about", "b", "ba",
                  "bank", "bat", "bxa", "c", "cap", "capital", "captain", "car", "cat",
                  "dog", "door", "e", "egg", "zoo"])
CAPACITY = 6                                   # phrases per server (stand-in for GB)

# --- (b) split by capacity: walk in order, cut when a server is full ---
starts = [phrases[i] for i in range(0, len(phrases), CAPACITY)]
print("range table:", [f"S{i}>={s!r}" for i, s in enumerate(starts)])

def servers_for_prefix(prefix):
    """Every server whose key range could hold a phrase starting with prefix."""
    lo = bisect.bisect_right(starts, prefix) - 1
    hi = bisect.bisect_right(starts, prefix + "￿") - 1
    return list(range(max(lo, 0), hi + 1))

for p in ("a", "ab", "b", "ca", "cap", "d"):
    print(f"  prefix {p!r:6} -> servers {servers_for_prefix(p)}")

# --- (c) hash by phrase: perfectly even, but every prefix fans out ---
N = 4
load = [0] * N
for ph in phrases:
    load[zlib.crc32(ph.encode()) % N] += 1
print("hash partition sizes:", load, "-> every prefix query hits all", N, "servers")
Output
range table: ["S0>='a'", "S1>='about'", "S2>='c'", "S3>='dog'"]
  prefix 'a'    -> servers [0, 1]
  prefix 'ab'   -> servers [0, 1]
  prefix 'b'    -> servers [1]
  prefix 'ca'   -> servers [2]
  prefix 'cap'  -> servers [2]
  prefix 'd'    -> servers [2, 3]
hash partition sizes: [4, 7, 4, 8] -> every prefix query hits all 4 servers
SchemeHow it routesGoodBad
Static range by first letter (A-F, G-M, …)First character decides the shardTrivial routing, one shard per queryBadly skewed. English has far more phrases starting with s than x. Merging rare letters helps a little but does not fix it.
Range by capacity (cut when a shard fills)Range table, like the example aboveEven memory use, and most prefixes of three or more characters hit a single shardShort prefixes span shards and need a merge. The range table must be rebuilt each time the trie is. Traffic skew remains: the shard holding ca… gets far more queries than its share of phrases.
Hash of the full phrasePhrase hash → shardPerfectly even memory and no hot shardEvery query fans out to every shard and has to be merged. p99 becomes the p99 of the slowest of N shards.

Pick capacity-based ranges. Handle traffic skew with replication, giving the ca… shard six replicas instead of three, and handle short-prefix fan-out with caching. Hash partitioning looks elegant, but it throws away the property that makes a trie useful, which is that one prefix lives in one place.

Replication and load balancing

Every shard has at least three replicas across availability zones. The aggregator holds the partition map, a small versioned table from range to replica set, and does client-side load balancing, picking the least-loaded replica rather than round-robin. Because trie servers are read-only, replicas never need to coordinate. Each one loads the same snapshot file, so they are identical by construction.

Caching

A few prefixes carry a large share of the traffic, so a cache in front of the tries earns its keep at three levels: the client's local cache, the CDN for short prefixes, and Redis for merged multi-shard responses. Put the snapshot version in every cache key (sugg:v812:…). A new build then creates new keys that start cold, and nothing ever has to be invalidated. The same versioned-key trick appears in the caching lesson and the food-delivery capstone. For a one-hour build cycle, the cold start is visible as a brief rise in shard traffic. Pre-warm the top 100k prefixes from the new snapshot before the flip.

Fault tolerance

  • A replica dies: the aggregator's health checks remove it within seconds, and the other replicas absorb its share. Nothing is lost, because the server has no unique state.
  • A replica restarts: it pulls the latest snapshot from object storage, runs load and _fill, and rejoins. Budget minutes, not hours, and keep the snapshot on local SSD so a restart does not depend on object storage.
  • A bad build ships (for example, empty results for a whole locale): the builder's validation step should catch it, by comparing the top 1,000 prefixes against the previous version and refusing to publish if they differ by more than 30%. If it gets through anyway, rollback is simply pointing servers at the previous snapshot version.
  • The whole suggest service is down: the client times out after about 150 ms and shows nothing. Search still works. This is why it must be a separate service with its own failure domain.

Step 11 — Personalisation

Keep a small per-user list, the last 50 or so searches with timestamps, in a key-value store keyed by user id, with a copy cached on the device. At serving time, filter that list by the prefix, rank by recency, and place up to three matches ahead of the global results, removing duplicates. Personal results come first because a user's own history has by far the highest click-through rate. Do this merge at the edge or on the client so the global response stays cacheable. Heavier personalisation, such as re-ranking the global list by a user's interests, belongs in a small re-ranking model that runs on the 15 candidates after retrieval. The trie is for retrieval. It is not where per-user logic belongs.

Part B — Nearby search (Yelp / proximity server)

Step 12 — Requirements

Functional

  • Given a location and a radius (or a map viewport), return places within it, filtered by category and optionally by a text query, and sorted by distance, rating or relevance.
  • Business owners add, update and delete places. Users add reviews with text, a rating and photos.
  • Show the place details page: info, rating summary, photos and recent reviews.

Non-functional

  • Read-dominated: tens of thousands of searches per second against a handful of place edits per second.
  • Latency: search p99 under 200 ms, because a map that pans and redraws slowly feels broken.
  • Freshness: a new place should be searchable within minutes, and a rating change within hours. Nothing here needs strong consistency.
  • Growth: about 20% per year in both places and traffic.
places        = 200_000_000      # businesses worldwide
growth        = 0.20             # per year, places and traffic
search_qps    = 60_000           # peak "nearby" queries
writes_day    = 400_000          # new/edited places per day
reviews_day   = 3_000_000

print(f"read:write ~ {search_qps * 86_400 / writes_day:,.0f}:1")

# --- The full place record lives in a DB; the index only needs id + position ---
place_row = 8 + 200 + 8 + 8 + 600 + 2 + 50       # id, name, lat, lng, description, category, misc
index_entry = 8 + 4 + 4                           # id + lat/lng as float32 (~1 m precision)
print(f"place rows: {places * place_row / 1e9:,.0f} GB   "
      f"geo index entries: {places * index_entry / 1e9:,.1f} GB")

# --- Fixed grid with 5 km cells ---
earth_land_km2 = 149_000_000
cell_km = 5
cells = earth_land_km2 / cell_km ** 2
print(f"5 km grid: {cells/1e6:.1f}M land cells, avg {places / cells:.0f} places/cell")
print("  ...but a dense downtown at ~1,500 places/km2 has "
      f"{1500 * cell_km**2:,} places in ONE cell")

# --- QuadTree with a leaf limit ---
LEAF_MAX = 400
leaves = places / LEAF_MAX
internal = leaves / 3                              # a 4-ary tree has ~1/3 as many internal nodes
ptr_bytes = 8
tree_mb = internal * 4 * ptr_bytes / 1e6
print(f"quadtree: ~{leaves/1e3:,.0f}k leaves, ~{internal/1e3:,.0f}k internal nodes, "
      f"pointers {tree_mb:,.1f} MB + entries {places * index_entry / 1e9:.1f} GB")

years = 5
print(f"in {years} years: {places * (1 + growth) ** years / 1e6:,.0f}M places, "
      f"{search_qps * (1 + growth) ** years:,.0f} peak QPS")
Output
read:write ~ 12,960:1
place rows: 175 GB   geo index entries: 3.2 GB
5 km grid: 6.0M land cells, avg 34 places/cell
  ...but a dense downtown at ~1,500 places/km2 has 37,500 places in ONE cell
quadtree: ~500k leaves, ~167k internal nodes, pointers 5.3 MB + entries 3.2 GB
in 5 years: 498M places, 149,299 peak QPS

Read the numbers. The geo index, which holds only the id and position, is a few gigabytes and fits in RAM on every search node. The full place records (175 GB) and reviews do not need to be in the index. They live in a database and cache, and are looked up by id after the index has picked the few dozen winners. Separating "find the ids" from "fetch the details" is the structural decision in this design, in the same way that the trie returns pointers rather than strings.

Step 13 — API and data model

## Search

GET /api/v1/places/nearby?lat=12.9720&lng=77.5950&radius_m=1500
      &category=cafe&q=filter+coffee&sort=relevance|distance|rating
      &open_now=true&limit=20&cursor=<opaque>
  -> 200 { results: [ { id, name, lat, lng, distance_m, category,
                        rating: 4.6, review_count: 812, price_band: 2,
                        is_open: true, thumb_url } ],
           next_cursor, searched_radius_m: 1500 }
  -> 400 radius_m > 50000 | invalid lat/lng
  # searched_radius_m tells the client if we widened the search (rural areas).

GET /api/v1/places/in-viewport?ne=13.00,77.62&sw=12.95,77.57&zoom=15&category=
  -> 200 { results: [...], clusters: [ { lat, lng, count } ] }
  # At low zoom return CLUSTERS per cell, not 40,000 pins.

## Places and reviews

POST  /api/v1/places                 { name, lat, lng, category, hours, ... }
  -> 201 { id }     # searchable in ~seconds-minutes (async index update)
PATCH /api/v1/places/{id}            -> 200 | 409 (version mismatch)
GET   /api/v1/places/{id}            -> 200 PlaceDetails  ETag: "p-{id}-v{n}"
POST  /api/v1/places/{id}/reviews    { rating 1-5, text, photo_ids[] }
  Headers: Idempotency-Key
  -> 201 | 409 ALREADY_REVIEWED

## Data model

places (                               -- source of truth, sharded by id
  id           BIGINT PRIMARY KEY,     -- 8 bytes: 4 would fit 4B, but plan for growth
  name         TEXT NOT NULL,
  lat          DOUBLE PRECISION NOT NULL,
  lng          DOUBLE PRECISION NOT NULL,
  geohash9     CHAR(9) NOT NULL,       -- ~5 m cell; prefix scans at any coarser level
  category     SMALLINT NOT NULL,      -- also a bitmask in the index for filtering
  description  TEXT,
  hours        JSONB,
  rating_avg   NUMERIC(2,1),           -- rollup, recomputed in batch
  rating_count INT,
  version      INT NOT NULL            -- optimistic concurrency for owner edits
);
CREATE INDEX ON places (geohash9);     -- makes LIKE 'tdr1v%' a range scan

reviews (
  place_id BIGINT, review_id BIGINT, user_id BIGINT,
  rating SMALLINT, text TEXT, photo_ids BIGINT[], created_at TIMESTAMPTZ,
  PRIMARY KEY (place_id, review_id)     -- "latest reviews for a place" = one partition
);

-- In the geo index (RAM), per entry: id 8 B + lat/lng float32 8 B + category 2 B
-- + score 2 B  ~= 20 B.  Nothing else. Names, photos and reviews are NOT here.

Step 14 — Why the obvious SQL query fails

Most candidates start with WHERE lat BETWEEN ? AND ? AND lng BETWEEN ? AND ? and an index on each column. It is correct, and it is slow. A B-tree on lat returns a band of latitude that wraps the whole planet. A B-tree on lng returns a band of longitude that runs pole to pole. The database either scans one band and filters, or intersects two large id lists. A composite index on (lat, lng) does not help either, because a B-tree can only range-scan its first column. Here is a simulation:

import random, bisect, math
random.seed(1)

# 300k places spread over a 1,000 km x 1,000 km country (coordinates in km).
N, SIDE, R = 300_000, 1_000.0, 5.0
pts = [(random.uniform(0, SIDE), random.uniform(0, SIDE)) for _ in range(N)]
qx, qy = 500.0, 500.0

# What "INDEX(lat)" + "INDEX(lng)" gives you: each index answers a BAND, not a box.
by_x = sorted(p[0] for p in pts)
band_x = bisect.bisect_right(by_x, qx + R) - bisect.bisect_left(by_x, qx - R)
band_y = sum(1 for _, y in pts if qy - R <= y <= qy + R)
box = sum(1 for x, y in pts if abs(x - qx) <= R and abs(y - qy) <= R)
circle = sum(1 for x, y in pts if math.hypot(x - qx, y - qy) <= R)

print(f"rows in lat band : {band_x:6,}   (index range scan #1)")
print(f"rows in lng band : {band_y:6,}   (index range scan #2)")
print(f"rows in the box  : {box:6,}   (the intersection you wanted)")
print(f"rows in radius   : {circle:6,}   (the answer)")
print(f"work wasted      : {band_x / circle:,.0f}x more rows touched than returned")
Output
rows in lat band :  3,073   (index range scan #1)
rows in lng band :  3,038   (index range scan #2)
rows in the box  :     24   (the intersection you wanted)
rows in radius   :     17   (the answer)
work wasted      : 181x more rows touched than returned

To return 17 places, the database reads about 3,000 index rows. This gets worse as the dataset grows, because the band grows with it, while the answer only depends on how dense places are near the user. What we need is an index where "near in space" means "near in the key", so one short range scan returns a small, local set. There are three ways to build that: fixed grids, geohash (a hierarchical grid in a string) and quadtrees (an adaptive grid in a tree).

Step 15 — Fixed grids, and why they need to adapt

Divide the map into equal squares and store a grid_id on each place, with an index on it. If the cell size is at least the search radius, any circle is covered by the user's cell and its 8 neighbours, so a query becomes nine equality lookups instead of a planet-wide band scan. In memory, this is a hash map from cell id to a list of place ids. With 6M land cells and 200M places, it is about 3 GB.

The flaw is density. The estimate above gives an average of 34 places per 5 km cell. A downtown cell holds tens of thousands, and an ocean cell holds none. Queries in a dense area filter a huge list, and the empty cells waste memory. Using one cell size everywhere guarantees that some areas will be wrong. Adapt the cell size to density: subdivide where it is crowded. Geohash lets you choose the resolution per query. A quadtree chooses it per region, automatically.

Step 16 — Geohash: a grid you can range-scan

A geohash repeatedly halves the world, alternating longitude and latitude, and writes down one bit per halving. The bits are interleaved and grouped in fives as base-32 characters. Each extra character makes the cell 32 times smaller, and a shared prefix means a shared cell. So "places in this cell" becomes WHERE geohash LIKE 'tdr1v%', a single B-tree range scan, in any ordinary database, Redis sorted set or search engine. Here is an encoder, the neighbour computation, and a working radius query over a sorted index:

import math
from collections import defaultdict

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"   # no a, i, l, o

def encode(lat, lng, precision=6):
    """Interleave bits: even bits halve longitude, odd bits halve latitude.
    Every 5 bits become one base-32 character."""
    lat_lo, lat_hi, lng_lo, lng_hi = -90.0, 90.0, -180.0, 180.0
    out, bits, ch, even = [], 0, 0, True
    while len(out) < precision:
        if even:
            mid = (lng_lo + lng_hi) / 2
            if lng >= mid: ch, lng_lo = (ch << 1) | 1, mid
            else:          ch, lng_hi = ch << 1, mid
        else:
            mid = (lat_lo + lat_hi) / 2
            if lat >= mid: ch, lat_lo = (ch << 1) | 1, mid
            else:          ch, lat_hi = ch << 1, mid
        even, bits = not even, bits + 1
        if bits == 5:
            out.append(BASE32[ch]); bits, ch = 0, 0
    return "".join(out)

def bbox(gh):
    lat_lo, lat_hi, lng_lo, lng_hi = -90.0, 90.0, -180.0, 180.0
    even = True
    for c in gh:
        v = BASE32.index(c)
        for shift in range(4, -1, -1):
            bit = (v >> shift) & 1
            if even:
                mid = (lng_lo + lng_hi) / 2
                lng_lo, lng_hi = (mid, lng_hi) if bit else (lng_lo, mid)
            else:
                mid = (lat_lo + lat_hi) / 2
                lat_lo, lat_hi = (mid, lat_hi) if bit else (lat_lo, mid)
            even = not even
    return lat_lo, lat_hi, lng_lo, lng_hi

def neighbours(gh):
    """The 8 surrounding cells: step one cell-width from the centre and re-encode."""
    lat_lo, lat_hi, lng_lo, lng_hi = bbox(gh)
    dlat, dlng = lat_hi - lat_lo, lng_hi - lng_lo
    clat, clng = (lat_lo + lat_hi) / 2, (lng_lo + lng_hi) / 2
    out = []
    for dy in (1, 0, -1):
        for dx in (-1, 0, 1):
            if dx == dy == 0: continue
            lat = max(min(clat + dy * dlat, 89.999999), -89.999999)
            lng = (clng + dx * dlng + 180) % 360 - 180          # wrap the antimeridian
            out.append(encode(lat, lng, len(gh)))
    return out

def haversine_m(a, b):
    (la1, lo1), (la2, lo2) = map(lambda p: (math.radians(p[0]), math.radians(p[1])), (a, b))
    h = math.sin((la2 - la1) / 2) ** 2 + math.cos(la1) * math.cos(la2) * math.sin((lo2 - lo1) / 2) ** 2
    return 2 * 6_371_000 * math.asin(math.sqrt(h))

# Cell size per precision near the equator (width x height).
for p in (4, 5, 6, 7):
    la0, la1, lo0, lo1 = bbox(encode(0.1, 0.1, p))
    print(f"precision {p}: ~{haversine_m((0, lo0), (0, lo1)) / 1000:6.3f} km x "
          f"{haversine_m((la0, 0), (la1, 0)) / 1000:6.3f} km")

print("sanity check:", encode(57.64911, 10.40744, 11))     # known reference value

# The boundary trap: two cafes ~50 m apart, either side of a cell edge.
a, b = (12.9716, 77.5962), (12.9716, 77.5967)
print("cafe A", encode(*a, 6), " cafe B", encode(*b, 6),
      f" distance {haversine_m(a, b):.0f} m")

# ---- A nearby index = a SORTED list of (geohash, ...): exactly what a B-tree gives you ----
import bisect
STORE_PRECISION = 9                       # store fine hashes once; query at any coarser level
places = {
    "Filter Coffee Co": (12.97160, 77.59430), "Dosa Corner":   (12.97160, 77.59670),
    "Brew Lab":         (12.97480, 77.59990), "Idli Express":  (12.96650, 77.58710),
    "Far Away Diner":   (13.03500, 77.59700), "Chai Point MG": (12.97550, 77.60640),
}
index = sorted((encode(lat, lng, STORE_PRECISION), name, lat, lng)
               for name, (lat, lng) in places.items())
keys = [row[0] for row in index]

def precision_for(radius_m):
    """Longest prefix whose cell is still at least `radius` tall and wide, so the
    centre cell plus its 8 neighbours is guaranteed to cover the whole circle."""
    for p in range(STORE_PRECISION, 0, -1):
        la0, la1, lo0, lo1 = bbox(encode(12.97, 77.59, p))
        if min(haversine_m((la0, lo0), (la1, lo0)), haversine_m((la0, lo0), (la0, lo1))) >= radius_m:
            return p
    return 1

def nearby(lat, lng, radius_m, k=10, with_neighbours=True):
    p = precision_for(radius_m)
    centre = encode(lat, lng, p)
    cells = [centre] + (neighbours(centre) if with_neighbours else [])
    cands = []
    for c in cells:                                      # one range scan per cell
        lo, hi = bisect.bisect_left(keys, c), bisect.bisect_left(keys, c + "~")
        cands.extend(index[lo:hi])
    hits = [(haversine_m((lat, lng), (r[2], r[3])), r[1]) for r in cands]
    return p, len(cells), len(cands), sorted(h for h in hits if h[0] <= radius_m)[:k]

me = (12.9720, 77.5950)
print("300 m, centre cell only:", [n for _, n in nearby(*me, 300, with_neighbours=False)[3]])
for radius in (300, 1500):
    p, cells, cands, res = nearby(*me, radius)
    print(f"radius {radius} m -> precision {p}, {cells} range scans, "
          f"{cands} candidates, {len(res)} hits")
    for d, name in res:
        print(f"  {d:5.0f} m  {name}")
Output
precision 4: ~39.092 km x 19.546 km
precision 5: ~ 4.886 km x  4.886 km
precision 6: ~ 1.222 km x  0.611 km
precision 7: ~ 0.153 km x  0.153 km
sanity check: u4pruydqqvj
cafe A tdr1v9  cafe B tdr1vc  distance 54 m
300 m, centre cell only: ['Filter Coffee Co']
radius 300 m -> precision 6, 9 range scans, 5 candidates, 2 hits
     88 m  Filter Coffee Co
    190 m  Dosa Corner
radius 1500 m -> precision 5, 9 range scans, 6 candidates, 5 hits
     88 m  Filter Coffee Co
    190 m  Dosa Corner
    616 m  Brew Lab
   1052 m  Idli Express
   1295 m  Chai Point MG

What to point out

  • The boundary trap. Cafe A and cafe B are 54 m apart but in different cells, so a lookup of the centre cell alone finds only one place. You must search the centre cell plus its 8 neighbours. Candidates who say "just prefix-match the user's geohash" have missed this. The trap is worse at big boundaries. Two points either side of the equator or the prime meridian can share no prefix at all.
  • Choose precision from the radius. Pick the longest prefix whose cell is at least as tall and wide as the radius. Then nine cells are guaranteed to cover the circle. Store the fine hash once, at 9 characters, and query at whichever coarser length the radius needs. One index serves every zoom level.
  • Cells are not square, and they shrink toward the poles. Odd precisions are roughly square. Even ones are twice as wide as they are tall. Longitude degrees also get shorter away from the equator. This is why the helper measures the real cell with haversine instead of using a lookup table.
  • Always finish with an exact distance filter. Nine cells cover more area than the circle, so the index returns candidates and haversine decides the answer.
  • This is what Redis GEO does. GEOADD stores a 52-bit interleaved geohash as a sorted-set score, and GEOSEARCH … BYRADIUS performs this nine-cell range scan and filter. The same idea sits behind Elasticsearch geo_point and PostGIS's geohash functions. PostGIS's main index is an R-tree, covered below.

Step 17 — QuadTree: a grid that adapts itself

A quadtree starts with one cell for the whole region. When a cell holds more than a fixed number of places (say 400), it splits into four equal quadrants and pushes its places down. Dense areas become deep and fine-grained. Empty areas stay as one big leaf. Only leaves hold places, and a query descends only into cells that intersect the search circle.

import math, random

class QuadTree:
    """A region quadtree over a square. A leaf holds up to `cap` points; the insert
    that would overflow it splits the leaf into 4 equal quadrants and pushes its
    points down. Dense areas get deep, small cells; empty areas stay one big leaf."""
    def __init__(self, x, y, size, cap=4, depth=0):
        self.x, self.y, self.size, self.cap, self.depth = x, y, size, cap, depth
        self.points = []            # only leaves hold points
        self.kids = None            # [SW, SE, NW, NE] once split

    def _child_for(self, px, py):
        half = self.size / 2
        i = (1 if px >= self.x + half else 0) + (2 if py >= self.y + half else 0)
        return self.kids[i]

    def insert(self, px, py, pid):
        if self.kids is not None:
            return self._child_for(px, py).insert(px, py, pid)
        self.points.append((px, py, pid))
        if len(self.points) > self.cap and self.depth < 12:     # depth cap: duplicates
            half = self.size / 2
            self.kids = [QuadTree(self.x + dx * half, self.y + dy * half, half,
                                  self.cap, self.depth + 1)
                         for dy in (0, 1) for dx in (0, 1)]
            pts, self.points = self.points, []
            for p in pts:
                self._child_for(p[0], p[1]).insert(*p)

    def query(self, cx, cy, r, stats):
        # Prune any cell whose square cannot intersect the circle.
        nx = min(max(cx, self.x), self.x + self.size)
        ny = min(max(cy, self.y), self.y + self.size)
        if math.hypot(nx - cx, ny - cy) > r:
            return []
        stats["nodes"] += 1
        if self.kids is None:
            stats["leaves"] += 1
            return [p for p in self.points if math.hypot(p[0] - cx, p[1] - cy) <= r]
        return [p for k in self.kids for p in k.query(cx, cy, r, stats)]

    def leaves(self):
        if self.kids is None:
            yield self
        else:
            for k in self.kids:
                yield from k.leaves()

# ---- Step 1: watch one leaf split ----
t = QuadTree(0, 0, 100, cap=4)
for i, (x, y) in enumerate([(10, 10), (80, 15), (20, 70), (60, 60), (62, 58)]):
    t.insert(x, y, i)
    print(f"insert #{i} ({x},{y}) -> leaves: {sum(1 for _ in t.leaves())}")
print("after split:", [(l.x, l.y, len(l.points)) for l in t.leaves()])

# ---- Step 2: a skewed city - a dense downtown in one corner, sparse suburbs ----
random.seed(3)
city = QuadTree(0, 0, 64.0, cap=50)          # a 64 km x 64 km square
pid = 0
for _ in range(9_000):                        # downtown: 9k places in ~4 km x 4 km
    city.insert(random.gauss(10, 1.2) % 64, random.gauss(10, 1.2) % 64, pid); pid += 1
for _ in range(1_000):                        # suburbs: 1k places over the rest
    city.insert(random.uniform(0, 64), random.uniform(0, 64), pid); pid += 1

leaves = list(city.leaves())
deep = [l for l in leaves if l.depth >= 6]
print(f"{pid:,} places -> {len(leaves)} leaves, depth {min(l.depth for l in leaves)}"
      f"..{max(l.depth for l in leaves)}; smallest cell {min(l.size for l in leaves)*1000:.0f} m,"
      f" largest {max(l.size for l in leaves):.0f} km")
print(f"leaves at depth >= 6 (downtown): {len(deep)}, holding "
      f"{sum(len(l.points) for l in deep):,} places")

for name, (cx, cy) in {"downtown": (10, 10), "suburb": (45, 45)}.items():
    st = {"nodes": 0, "leaves": 0}
    hits = city.query(cx, cy, 0.5, st)
    print(f"{name:8}: 500 m radius -> visited {st['nodes']} nodes / {st['leaves']} leaves, "
          f"{len(hits)} hits")
Output
insert #0 (10,10) -> leaves: 1
insert #1 (80,15) -> leaves: 1
insert #2 (20,70) -> leaves: 1
insert #3 (60,60) -> leaves: 1
insert #4 (62,58) -> leaves: 4
after split: [(0.0, 0.0, 1), (50.0, 0.0, 1), (0.0, 50.0, 1), (50.0, 50.0, 2)]
10,000 places -> 475 leaves, depth 2..9; smallest cell 125 m, largest 16 km
leaves at depth >= 6 (downtown): 402, holding 8,920 places
downtown: 500 m radius -> visited 110 nodes / 66 leaves, 755 hits
suburb  : 500 m radius -> visited 4 nodes / 1 leaves, 0 hits

Reading the result

  • 90% of the places sit in 402 small leaves downtown, some only 125 m across, while the suburbs are covered by a few large leaves up to 16 km. Every leaf holds at most 50 places, so no query ever filters a huge list. A fixed grid cannot do this.
  • The same 500 m query visits 110 nodes downtown and 4 in the suburbs. Work is proportional to how many places are near you, not to how many places exist in total.
  • Memory is tiny. With 200M places and 400 per leaf, you get 500k leaves and about 167k internal nodes. The internal nodes' child pointers total a few megabytes. Almost all of the memory is the place entries themselves, about 3 GB, so the whole tree fits comfortably on one server and is replicated.
  • Finding neighbours. To expand a search when the user's leaf has too few results, walk up through parent pointers and back down into siblings, or link the leaves in a doubly-linked list in space-filling-curve order. Both let you grow the search ring until you have K results or reach the maximum radius.
  • Insertions are a descent plus an occasional split, which is fine at 5 edits per second. It is not fine at 300,000 per second (Part C).
IndexHow it adapts to densityWhere it is usedWatch out for
Fixed gridIt does notSimple in-memory match loops within one cityHot cells downtown, and wasted empty cells
GeohashPer query (prefix length)Redis GEO, Elasticsearch, DynamoDB geo librariesEdge effects (always add the 8 neighbours), and non-square cells
QuadTreePer region (splits)In-memory proximity servers, map tile systemsRebalancing under heavy writes, and it is custom code you have to operate
S2 (Google) / H3 (Uber)Hierarchical cells on a sphereGoogle Maps, Uber dispatch and surgeLibrary dependency. H3 hexagons have uniform neighbour distances, which is good for surge pricing.
R-treeBounding boxes adapt to the dataPostGIS (GiST), SQLite R*Tree, Oracle SpatialSlower to update, but best for polygons (delivery zones), not just points

In an interview, choose geohash or S2 cells in an existing store for a Yelp-style directory. Explain the quadtree to show you understand adaptive density, and use it where you control an in-memory service. Saying "I would use PostGIS" is a fine production answer only if you can explain what its index is doing.

Step 18 — High-level design and one nearby query end to end

flowchart TB APP[Mobile / web client] --> GW[API gateway + LB] GW --> SRCH[Search / aggregator service] GW --> PLC[Place service
writes, details] GW --> REV[Review service] SRCH --> QT1[Geo index shard 1
replicas] SRCH --> QT2[Geo index shard 2
replicas] SRCH --> QTN[Geo index shard N
replicas] SRCH --> PCACHE[(Place card cache
LRU, Memcached/Redis)] PCACHE -->|miss| PDB[(Places DB
sharded by place_id)] PLC --> PDB REV --> RDB[(Reviews DB)] REV --> OBJ[(Photo object store + CDN)] PDB -->|CDC| K[(Kafka)] RDB -->|CDC| K K --> IDX[Index updater] IDX --> QT1 IDX --> QT2 IDX --> QTN K --> RATE[Rating rollup
batch, 1-2x per day] RATE --> PDB IDX --> MAP[(Index-server map
shard to place ids)]

The geo index answers only one question: which place ids are near here, with their scores. Details come from a cache by id. Writes flow through CDC into the index asynchronously, so a new place appears within seconds to minutes.

sequenceDiagram participant C as Client participant G as Gateway participant S as Search aggregator participant I as Geo index shards participant P as Place cache participant D as Places DB C->>G: GET /places/nearby?lat=12.972&lng=77.595&radius_m=1500&category=cafe G->>S: forward (auth, rate limit) S->>S: precision_for(1500 m) = 5, centre cell + 8 neighbours S->>S: region routing: which shards own these 9 cells? par each owning shard S->>I: candidates(cells, category=cafe, top=50 by score) I-->>S: [(place_id, lat, lng, rating, popularity)] end S->>S: haversine filter, then rank: distance + rating + popularity S->>S: keep top 20, build next_cursor S->>P: MGET place:card:{id} x 20 P-->>S: 18 hits, 2 misses S->>D: SELECT ... WHERE id IN (2 ids) D-->>S: rows S->>P: SET the 2 cards (TTL 1h) S-->>C: 200 {results: [PlaceCard x 20], next_cursor}

Two phases: the geo index finds and ranks candidate ids in memory, and then a batch read by id fills in the display fields. Neither phase scans anything proportional to the size of the dataset.

The order of operations, and why

  1. Compute the cells before routing. The radius decides the precision, and the precision decides the nine cells. Only then do you know which shards to ask, often just one.
  2. Filter by category inside the index. Store a category bitmask next to each entry, so "cafes near me" does not return 50 candidates that are mostly dentists.
  3. Each shard returns its own top N with a score. The aggregator merges them. This is the same top-K merge as the typeahead fan-out, and the same one used for ranking popular places across partitions.
  4. Exact distance and final ranking happen after the merge, on a few hundred candidates, so the scoring formula can be as elaborate as you like.
  5. Batch-fetch details by id with one MGET. Places are read far more often than they are edited, so an LRU cache of place cards has a very high hit rate. The database only sees misses.
  6. Too few results? Widen the search, either to the next ring of cells or one precision coarser, and repeat, up to a maximum radius. Do not return an empty map because the user is in a rural area.

Step 19 — Partitioning, replication, caching and ranking

Partitioning: by region or by place id?

Shard by region (city, geohash prefix)Shard by place_id hash
Query fan-outUsually one shard, since a radius rarely crosses a region borderEvery shard, every query, followed by a merge
BalanceSkewed. Manhattan's shard is much bigger and busier than rural Montana's.Even, by construction
Hot spotsA festival or a New Year's Eve crowd hits one shardSpread across all shards
RebalancingSplit a region, which needs a routing-table changeConsistent hashing moves about 1/N of the data
Tree shape per shardOne contiguous treeEvery shard has its own sparse tree over the whole map

Many textbook answers choose place-id hashing for its balance. That is defensible, but name the cost: every query becomes an N-way scatter-gather, and tail latency grows with N. The stronger answer is region sharding with adaptive boundaries. Use geohash-prefix or S2-cell ranges sized by load rather than by area, the same capacity-based cutting as the trie, and a routing table the aggregator caches. A dense city gets several shards and a rural country gets one. Hot spots are handled by adding replicas to the busy shard, not by spreading every query across the whole fleet. When the index fits on one machine, which at 3 to 12 GB it does, the simplest answer is no partitioning, just replicas. Say so, and give the growth number that would change your mind.

Replication and rebuilding a dead index server

Each shard has a primary that applies index updates and replicas that serve reads. A replica may be a few seconds behind, which is fine for "a new cafe appears". If every replica of a shard dies, a new server must rebuild the index. Scanning 200M database rows to find the ones that hash to this shard is slow. Keep an index-server map, a small service mapping shard to the set of (place_id, lat, lng) it owns, and a fresh server bulk-loads from it in minutes. The map is itself replicated, and it can always be rebuilt from the database as a last resort. Better still, have index servers write periodic snapshots to object storage, just like trie servers.

Caching

Cache place cards by id with LRU. A small fraction of places (famous restaurants, landmarks) takes most of the detail views. Cache whole search responses for popular (cell, category) pairs, such as "coffee near Times Square", with a short TTL. Snap the user's location to the cell so everyone standing in the same 150 m cell shares one key. Never cache by raw lat/lng, because no two phones report the same coordinates.

Ranking

Distance alone gives poor results. The closest place is often the worst one. Score is a blend: w1 · proximity + w2 · rating (with a Bayesian prior, so a single 5-star review does not win) + w3 · popularity + w4 · text relevance + w5 · open now. Ratings and popularity change slowly and are expensive to rewrite in a live index, so a batch job recomputes them once or twice a day in a quiet period and publishes them to the index shards. "Top 100 popular places within 5 km" is each shard returning its local top 100 and the aggregator merging them.

Part C — When the points move (Uber, nearby friends)

Everything above assumes places sit still. Drivers do not.

drivers_online = 1_200_000
ping_s         = 4
places_writes  = 400_000 / 86_400          # the Yelp side, for contrast

ping_rate = drivers_online / ping_s
print(f"driver pings: {ping_rate:,.0f}/s   vs place edits: {places_writes:.1f}/s "
      f"-> {ping_rate / places_writes:,.0f}x more writes")

# Latest-position hash table: driver_id -> (lat, lng, heading, ts, status)
entry = 8 + 8 + 8 + 2 + 4 + 1
print(f"latest-position table: {drivers_online * entry / 1e6:,.0f} MB  (fits in RAM on one box)")

# How many pings actually move a driver to a different ~600 m cell?
speed_kmh, cell_m = 30, 600
metres_per_ping = speed_kmh * 1000 / 3600 * ping_s
p_cross = metres_per_ping / cell_m
print(f"{metres_per_ping:.0f} m per ping -> ~{p_cross:.0%} of pings change cell "
      f"= {ping_rate * p_cross:,.0f} index moves/s")

# Riders watching the map: push vs poll
watchers, cars_on_screen = 2_000_000, 8
push_bytes = 40
print(f"push to {watchers/1e6:.0f}M open maps: "
      f"{watchers * cars_on_screen * push_bytes / ping_s / 1e6:,.0f} MB/s outbound")
print(f"poll every 5 s instead: {watchers / 5:,.0f} nearby queries/s")
Output
driver pings: 300,000/s   vs place edits: 4.6/s -> 64,800x more writes
latest-position table: 37 MB  (fits in RAM on one box)
33 m per ping -> ~6% of pings change cell = 16,667 index moves/s
push to 2M open maps: 160 MB/s outbound
poll every 5 s instead: 400,000 nearby queries/s

At 65,000 times more writes than the directory, the quadtree's weakness shows. Each position update is a move: find the old leaf, remove the driver, find the new leaf, insert, and perhaps split or merge. Doing that 300,000 times per second on a shared tree means lock contention on the read path. The design changes in four ways:

  • Split "latest position" from "spatial index". Each ping overwrites one entry in a hash map keyed by driver id, a 37 MB table sharded by driver id. The spatial index is refreshed from that table every 10 to 15 seconds, and only for the roughly 6% of pings that actually crossed a cell boundary. A driver shown on the map 10 seconds late is acceptable. A lock-contended index is not.
  • Prefer fixed cells to an adaptive tree. For moving objects, a flat map from geohash or H3 cell to driver set per city, or Redis GEO keyed per city, beats a quadtree. A cell move is two set operations, and nothing ever rebalances. If you do keep a quadtree, add hysteresis: let a leaf grow 10 to 20% beyond its limit before splitting, and merge only well below it, so a busy intersection does not split and merge every few seconds.
  • Push or pull to the viewer. Pushing each nearby driver's movement to 2M open maps is about 160 MB/s of fan-out, plus the complexity of subscribing viewers to drivers as cars enter and leave the viewport. Having the client poll nearby every 5 seconds is 400k simple, cacheable queries per second, and they can share a cell-keyed cache. Most systems poll for the "cars on the map" view and push only for the one driver on your active trip, where accuracy matters. That push goes over the same WebSocket tier as chat.
  • Matching is a write, not a read. Choosing a driver needs an atomic claim so that two riders cannot get the same car. That is a compare-and-set on driver state, walked through in the food-delivery capstone. The nearby query only produces candidates.

"Nearby friends" is the same problem at lower write rates (phones report every 30 to 60 s) and with a privacy twist. You only index users who have opted in, you compute friend-distance only among friend pairs, and you round locations before showing them.

Step 20 — Failure modes and degradation

What failsWhat the user seesMechanism
Trie replica slow or deadNothingHedged request to a second replica after the p95; health checks remove the dead one
Whole suggest service downNo suggestions; search still worksClient timeout of about 150 ms, fail silent, separate failure domain
Bad trie build (garbage or empty)Nothing, if caughtPre-publish diff against the previous version; one-command rollback to snapshot N-1
Offensive suggestion goes viralGone within about a minuteDenylist pushed as config; served-time filter plus spares; removed from the next build
Aggregation pipeline stallsSuggestions a few hours staleKeep serving the last good snapshot; alert on snapshot age, not on job failure alone
Geo shard loses all replicasSparse results in one regionRebuild from snapshot or the index-server map; meanwhile the aggregator widens the search to neighbouring shards
Place cache cluster downSlower resultsFall through to database replicas, with per-key request coalescing to prevent a stampede
CDC lag into the geo indexA new place is missing for minutesAcceptable by requirement; alert when lag exceeds 15 minutes
Driver location shard downCars freeze on the mapReplica takeover; drivers re-send their position within 4 s anyway, so the state rebuilds itself

Step 21 — Observability

  • Typeahead: suggestion click-through rate (the business signal), keystrokes saved per search, p99 by prefix length, CDN and Redis hit rate, snapshot age per shard, and the share of responses that had to be filled from spares after the denylist.
  • Nearby: zero-result rate by region (this catches index holes), candidates scanned per query (this catches hot cells), p99 by shard, CDC lag, and place-card cache hit rate.
  • Moving objects: location age at match time (how stale the chosen driver's position was), pings per second per shard, and cell-move rate.

The trade-off summary — how to close

  • Precomputed top-K in the trie, not ranking at query time. We pay about 3x memory to make the read path a pointer walk, the only way to serve 650k QPS in single-digit milliseconds.
  • Offline rebuild plus a trending fast path, not live updates. Increments are cheap and decrements are not, so correctness comes from the rebuild and freshness from bump.
  • Capacity-based range partitions, not hash. One prefix lives in one place. Skew is solved with replicas and short-prefix fan-out with caches.
  • The client is part of the design. Debounce, abort, local cache and prefetch remove most requests before they exist.
  • Geohash or S2 cells in an existing store for places, not a lat/lng B-tree. "Near in space" has to mean "near in the key". Always query nine cells, then filter exactly.
  • Quadtree for adaptive density where you own the service. Flat cells and a latest-position hash for moving objects. The write rate decides the structure.
  • Index returns ids, cache returns details. Both designs keep the hot structure tiny by storing pointers, not payloads.
// Write your solution here
// Write your solution here
// Write your solution here

Finished reading? Mark this lesson complete to track your progress.

Up next · Lesson 17Notification SystemPush, SMS, email fan-out, templates, preferences, retries and dedupe.