How Google finishes your search before you do

1 Approaching a design problem

Before we touch a single trie or cache, we need to know how to attack an open-ended design question. This is a skill of its own — and it's very different from a coding (DSA) interview.

DSA interviews vs design interviews

In a design interview your job is to (1) figure out what you're supposed to build — i.e. what the interviewer actually wants, (2) build that solution, and (3) deliberately take on sufficiently complex things so you can showcase your skills and impress the interviewer.

The 5-step design approach

A reliable script for the 45 minutes. Roughly the first half is about understanding, the second half about building.

Step 1 — Problem statement: reason by analogy

When the statement is vague, reason by analogy: find existing companies or systems that offer a similar product/feature. This gives you an overview of the umbrella of different scopes you could consider.

• Typeahead is a specific form of autocomplete — literally trying to type ahead of the user.
• Examples: typeahead in Google, typeahead in Amazon.
• Typeahead & Search are different products, but typeahead is always followed by some form of search.

Functional requirements & the MVP mindset

Functional requirements (FR) start from a Minimal Viable Product (MVP):

• Minimal: the minimal set of features to achieve viability.
• Viable: should demonstrate the core features & usability.
• Product: solve a genuine problem.

Always keep "minimal" in mind — MVP features is not a feature-suggestion competition. Features fall into three buckets:

typeahead(partial_query) => suggestions_list   # user-facing
log_search(search_query)  => void              # internal

2 Requirements & scale

Before designing anything, a good engineer writes down what the system must do. We split this into two buckets. Functional requirements are the features — what the user can see and do. Non-functional requirements are the qualities — how fast, how reliable, how big. Autocomplete is a fascinating case study because its features are tiny but its quality bar is brutal.

There's exactly one actor to keep in mind here: the end user — the person doing the Google search.

Functional requirements (what it does)

Stated as complete user-perspective sentences: "As the user is typing in the search box, we should auto-complete their search query — we should show typeahead suggestions."

• Prefix suggestions. Given a prefix / partial_query (the letters typed so far, like "how to ti"), return a list of complete queries that start with those letters — the user-facing API typeahead(partial_query) => suggestions_list.
• Suggestions are popular past searches. The list comes from searches other people made before, captured via the internal API log_search(search_query) => void.
• Ranking by popularity (top 5, relevant). We show only the top 5 relevant suggestions. Relevant = the suggestion is a prefix match with the partial_query. Top 5 = we track how many times each search_query has been searched globally, and among prefix matches we show those with the highest count.
• Update on every keystroke. With every letter the user types, the suggestions change — we send a new API request with every letter typed.
• Clicking a suggestion triggers a search (frontend).

Scope boundaries we picked

• Start at ≥ 3 letters. We only start showing suggestions after the user has typed at least 3 letters — fewer than that gives irrelevant results.
• Cap at 50 letters. If a query is longer than ~50 letters, the user has most likely fallen asleep on the keyboard.

The qualities (latency, consistency, availability) and the numbers (QPS, storage, sharding) are big enough to deserve their own sections — see §4 Non-functional requirements and §5 Scale estimation below. First, though, we sketch the API and where the data comes from.

3 API & data flow

For each feature, decide its API — its input & output (the interface) — and its protocol — how the communication happens (REST / RPC / …). Those are two different things.

typeahead(partial_query) => suggestions_list      # user-facing
log_search(search_query)  => void                 # internal

GET /typeahead?partialQuery={...}                 # the HTTP shape

Where do the suggestions come from?

Users are constantly searching on Google. The data flow that feeds typeahead:

Crucially, step 3 is asynchronous — the user's search isn't slowed down by logging. The /typeahead microservice is fed by the /search microservice rather than living on the search path.

4 Non-functional requirements

Non-functional requirements (NFR) are our design goals. The right tool to reason about them is PACELC: in a Partition, choose Availability or Consistency; Else (normal operation), choose Latency or Consistency. Do NOT jump to an answer — reason it out.

Consistency vs Availability

Q: What is the data? Past search queries and their corresponding counts.

Q: What does eventual consistency mean here? When is the data changing? Every time someone searches, some entry's count changes, and the top-5 for some partial_query may change. It's possible for a new count to reflect in the top-5 with a delay — for some time the true count of Query1 may exceed Query2, yet we still show Query2 first.

Q: What does data loss mean here? If someone searched but, for whatever reason, we failed to increment that query's count (it didn't get logged), the counts will be off by a small amount:

Consistency vs Latency

Other NFRs (briefly)

• Security: do NOT roll your own unless you're a security expert — "99% of security issues happen because non-experts try to do security."
• Observability, rate limits, idempotency, and delivery guarantees are worth a mention.

5 Scale estimation

The scale dictates our design choices. We want to know: the amount of data (is sharding needed?), and the amount of load (requests/second per API, peak vs average, read- vs write-heavy). Those guide the choice of database, cache and sharding.

Step 1 — Daily Active Users

Handy reference numbers: world population ~8 billion; internet users ~5 billion; India ~1.4 billion; USA ~350 million. And the Pareto principle (80/20): only ~20% of users are active. (For social media it extends to 80-20-1: 80% passively browse, 20% interact, 1% create.)

# Assumption: Google has 5 billion users.
DAU            = 20% of 5 billion        = 1 billion users

# Assumption: 20 searches / active user / day
searches/day   = 20 * 1 billion          = 20 billion searches/day

# 1 day = 86,400 s ~= 10^5 s
searches/sec   = 20*10^9 / 10^5          = 200,000 searches/sec
# note: these go to the SEARCH api, not typeahead

# Assumption: ~10 typeahead calls per search
# (avg query ~10 letters, start at letter 3 => 10-3=7 ~ 10)
typeahead/sec  = 200,000 * 10            = 2,000,000 typeaheads/sec

log_search/sec = 1 per search            = 200,000 req/sec

# Peak load ~= 5x average
peak typeahead = 5 * 2,000,000           = 10,000,000 typeaheads/sec

Step 2 — Amount of data

The data is past search queries & their counts (avg query size 10 letters, assumed earlier). How many entries? Not one per search — repeated searches just update a count; only new (never-seen-before) unique queries add rows.

# Assumption: ~10% of searches are brand-new queries
new entries/day = 10% of 20 billion      = 2 billion entries/day

# ~10 bytes per entry
data/day        = 10 bytes * 2 billion   = 20 GB / day

# over 20 years (365 ~= 400 days)
total           = 20 GB/day * 20*400 days
                = 16 * 10^4 GB           = 160 TB

Step 3 — Read-heavy or write-heavy?

Reads are 10× writes, so we call this read-heavy — even though the writes are themselves significant.

6 The Trie data structure

A trie (pronounced "try," from retrieval — also called a prefix tree) is a tree where each edge represents one character and each path from the root spells out a prefix. It's the natural fit for autocomplete because finding "all words starting with P-R-E" is just "walk to the node at the end of PRE, then look below."

How terms are stored

Every node in the trie holds a map from a character to a child node. To store the word "cat," we walk/create children c → a → t and mark the final node as the end of a real word. To store "car" too, it shares the c → a path and only branches at the third letter. Shared prefixes = saved space.

Insertion and lookup

Insertion: walk the word letter by letter, creating any missing child nodes, and mark the last node as a word-end. Lookup of a prefix: walk the prefix letter by letter from the root; if you ever can't find the next child, there are no matches. If you reach the end of the prefix, the node you land on is the root of a subtree containing every word with that prefix.

# Python — trie with per-word frequency + top-k prefix query
import heapq

class TrieNode:
    def __init__(self):
        self.children = {}        # char -> TrieNode
        self.is_word  = False
        self.word     = None      # full word, set at the end node
        self.freq     = 0         # search frequency of this word

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

    def insert(self, word, freq=1):
        node = self.root
        for ch in word:                 # walk/create the path
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True
        node.word    = word
        node.freq   += freq               # aggregate repeated inserts

    def _find(self, prefix):              # walk to the prefix node
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None          # no words with this prefix
            node = node.children[ch]
        return node

    def suggest(self, prefix, k=5):
        node = self._find(prefix)
        if node is None:
            return []
        matches = []
        stack = [node]
        while stack:                       # gather every word under the prefix
            cur = stack.pop()
            if cur.is_word:
                matches.append((cur.freq, cur.word))
            stack.extend(cur.children.values())
        # top-k by frequency (descending)
        best = heapq.nlargest(k, matches)
        return [(w, f) for f, w in best]

# --- demo ---
t = Trie()
for w, f in [("cat", 8), ("car", 5), ("card", 3),
              ("care", 9), ("dog", 4)]:
    t.insert(w, f)
print(t.suggest("ca", 3))    # [('care', 9), ('cat', 8), ('car', 5)]

// C++ — trie with per-word frequency + top-k prefix query
#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;  // char -> child
    bool   isWord = false;
    string word;                              // set at the end node
    long   freq  = 0;                          // search frequency
};

struct Trie {
    TrieNode* root = new TrieNode();

    void insert(const string& word, long freq = 1) {
        TrieNode* node = root;
        for (char ch : word) {              // walk/create the path
            if (!node->children.count(ch))
                node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isWord = true;
        node->word   = word;
        node->freq  += freq;                  // aggregate repeated inserts
    }

    TrieNode* find(const string& prefix) {  // walk to the prefix node
        TrieNode* node = root;
        for (char ch : prefix) {
            auto it = node->children.find(ch);
            if (it == node->children.end()) return nullptr;
            node = it->second;
        }
        return node;
    }

    vector<pair<string, long>> suggest(const string& prefix, int k = 5) {
        vector<pair<string, long>> matches;
        TrieNode* start = find(prefix);
        if (!start) return matches;
        vector<TrieNode*> stack{start};
        while (!stack.empty()) {              // gather every word under the prefix
            TrieNode* cur = stack.back(); stack.pop_back();
            if (cur->isWord) matches.push_back({cur->word, cur->freq});
            for (auto& [c, child] : cur->children) stack.push_back(child);
        }
        // top-k by frequency (descending)
        sort(matches.begin(), matches.end(),
             [](const auto& a, const auto& b){ return a.second > b.second; });
        if ((int)matches.size() > k) matches.resize(k);
        return matches;
    }
};

int main() {
    Trie t;
    t.insert("cat", 8); t.insert("car", 5); t.insert("card", 3);
    t.insert("care", 9); t.insert("dog", 4);
    for (auto& [w, f] : t.suggest("ca", 3))
        cout << w << " " << f << "\n";  // care 9 / cat 8 / car 5
}

// Java — trie with per-word frequency + top-k prefix query
import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();  // char -> child
    boolean isWord = false;
    String  word;                                       // set at the end node
    long    freq = 0;                                    // search frequency
}

class Trie {
    private final TrieNode root = new TrieNode();

    void insert(String word, long freq) {
        TrieNode node = root;
        for (char ch : word.toCharArray())            // walk/create the path
            node = node.children.computeIfAbsent(ch, c -> new TrieNode());
        node.isWord = true;
        node.word   = word;
        node.freq  += freq;                            // aggregate repeated inserts
    }

    private TrieNode find(String prefix) {            // walk to the prefix node
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            node = node.children.get(ch);
            if (node == null) return null;       // no words with this prefix
        }
        return node;
    }

    List<Map.Entry<String, Long>> suggest(String prefix, int k) {
        List<Map.Entry<String, Long>> matches = new ArrayList<>();
        TrieNode start = find(prefix);
        if (start == null) return matches;
        Deque<TrieNode> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {                      // gather every word under the prefix
            TrieNode cur = stack.pop();
            if (cur.isWord)
                matches.add(Map.entry(cur.word, cur.freq));
            for (TrieNode child : cur.children.values()) stack.push(child);
        }
        // top-k by frequency (descending)
        matches.sort((a, b) -> Long.compare(b.getValue(), a.getValue()));
        return matches.subList(0, Math.min(k, matches.size()));
    }
}

public class Demo {
    public static void main(String[] args) {
        Trie t = new Trie();
        t.insert("cat", 8); t.insert("car", 5); t.insert("card", 3);
        t.insert("care", 9); t.insert("dog", 4);
        System.out.println(t.suggest("ca", 3));
        // [care=9, cat=8, car=5]
    }
}

The clever bit: store top-k at each node

Here's the trick that makes autocomplete fast. The naive way is: walk to the prefix node, then explore the whole subtree below it to gather all matching words and sort them by popularity. For a popular prefix like "a," that subtree is enormous — far too slow per keystroke.

Instead, we precompute and cache the top-k suggestions directly on every node (the top_k list above). When we build the trie offline, each node already carries a ready-made answer: the k most popular complete queries that pass through it. Now a lookup is just "walk to the node, read its list." No subtree exploration at request time.

node["how to ti"].top_k = [
    ("how to tie a tie",   980000),
    ("how to tie shoes",   540000),
    ("how to title a paper",120000),
    ("how to time a roast", 30000),
]

Complexity (the Big-O)

The beautiful part: lookup cost depends only on how long the prefix is, not on how many millions of queries are stored. Typing 9 characters costs 9 steps whether the trie holds a thousand words or a billion. That's why a trie hits our latency target.

7 Ranking & data collection

In Section 2 we waved our hands and said each node "knows" its top-k. Now we earn that. Where do the popularity numbers come from, and how do we keep them current?

Ranking by frequency and recency

The simplest signal is frequency: how many times has each full query been searched? More searches → higher rank. But pure frequency makes the list stale — an all-time favorite would cling to the top forever. So we add recency: recent searches should count for more than ancient ones.

A common technique is a time-decayed score: every day, multiply all existing counts by a factor like 0.95, then add today's fresh counts. Old popularity gently fades; trending queries rise. The final rank for a query is just this decayed score.

# score_today = score_yesterday * decay + searches_today
Day 1:   0      * 0.95 + 100  = 100
Day 2:   100    * 0.95 +  50  = 145
Day 3:   145    * 0.95 +   0  = 138   # no searches: fades
Day 4:   138    * 0.95 + 900  = 1031  # goes viral: jumps up

How query logs feed popularity

Every search a user runs is recorded in a query log — append-only lines of "this query was searched at this time." At our scale that's billions of lines a day, far too much to count live on the serving path. Instead the logs stream into a message queue (think of a conveyor belt like Kafka) and pile up in cheap storage for batch processing.

The offline aggregation pipeline

This is the offline pipeline — a scheduled job (say, hourly) that turns raw logs into a fresh trie. "Offline" means it runs separately from live traffic; users never wait on it.

Step 3 is typically a MapReduce-style job: "map" each log line to (query, 1), then "reduce" by summing per query and applying decay. Step 4 builds a fresh trie and, while building, computes each node's top-k by merging the top-k of its children (a child's best suggestions are candidates for the parent). Step 5 atomically swaps the new trie in for the old one.

# A node's best suggestions come from merging its
# children's best suggestions, plus its own word if any.
def compute_top_k(node, k=5):
    candidates = []
    if node.is_word:
        candidates.append((node.word, node.score))
    for child in node.children.values():
        compute_top_k(child, k)          # bottom-up
        candidates.extend(child.top_k)
    # keep only the k highest-scoring
    node.top_k = sorted(candidates, key=lambda x: -x[1])[:k]

8 Serving at scale

We now have a fast trie (Section 2) kept fresh by an offline pipeline (Section 3). The last job is delivering it to ~400k QPS with sub-100 ms latency. We reuse the big HLD building blocks from earlier sessions.

Caching hot prefixes

A tiny fraction of prefixes accounts for a huge fraction of traffic — single letters and common starts like "f," "you," "how to." We put a cache (a fast in-memory key→value store like Redis, recall the caching session) in front of the trie, keyed by prefix. The first lookup of "how to" computes the answer; the next million read it straight from cache.

Sharding the trie

Our 10 GB trie fits in one machine's RAM, but one machine can't handle 400k QPS alone. So we shard (split the data across machines, recall the sharding session). The natural key is the prefix's first letter(s): shard A handles prefixes starting "a," shard B handles "b," and so on. A request for "how to ti" is routed to the "h" shard.

CDN and edge

The fastest request is the one that never reaches your servers. A CDN (Content Delivery Network — a fleet of caches physically close to users) and edge nodes can cache the suggestions for the most common prefixes right next to the user, in their region. Latency is dominated by physical distance, so answering "how to" from a city 50 km away instead of a data center 5,000 km away is a giant win for our latency budget.

Debouncing on the client

Half of our scaling problem can be solved in the browser. Debouncing means: don't fire a request on every keystroke — wait until the user pauses typing (say 150–300 ms) and only then send the latest prefix. A fast typer entering "how to tie" generates one request instead of ten.

let timer;
input.addEventListener("input", () => {
  clearTimeout(timer);                  // cancel the pending request
  timer = setTimeout(() => {            // wait for a pause
    fetchSuggestions(input.value);      // only the latest prefix is sent
  }, 200);                            // 200 ms of quiet
});

The end-to-end request flow

Putting every block together, here's the journey of one keystroke from your keyboard to a dropdown:

Each layer is an opportunity to answer early: the request stops at the first layer that already knows the answer. Most requests never reach the trie at all — they're caught at the edge or in the cache. That layered, "answer as early as possible" shape is the heart of serving any read-heavy system at scale.

★ Putting it all together

You just designed a real, production-grade system end to end. Here's the one-paragraph story that connects all four topics:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original class notes / handout (Google Doc) — open the shared class material for this session.
• Class handout: "[SST-2028] Case Study: Google Search Typeahead".

Papers, docs & deep dives

• 📄 The System Design Primer — widely-used reference covering caching, sharding, and load balancing.
• 📄 Trie (prefix tree) — Wikipedia — the data structure at the heart of autocomplete, with complexity analysis.
• 📄 Design a Search Autocomplete System — write-up — an end-to-end typeahead design with tries, ranking, and serving.
• 📄 Apache Kafka documentation — the message queue used to stream query logs into the offline aggregation pipeline.