logo
CHEATSHEETSTOOLSABOUT中文

System Design - Search Typeahead (Autocomplete)

Designing a real-time Search Typeahead (or Autocomplete) system—such as Google or Amazon search suggestions—is a classic interview problem testing prefix trees (Tries), data pipeline aggregation, caching at the edge, and distributed partitioning.

1. Requirements & Scope

Functional Requirements

  • Prefix Matching: Given a prefix string typed by a user (e.g. "sys"), return the top 5 to 10 most relevant completed search suggestions (e.g. ["system design", "system design interview", "system architecture"]).
  • Ranking / Relevance: Suggestions are ranked by historical popularity, query frequency, or personal relevance.

Non-Functional Requirements

  • Ultra-Low Latency: Suggestions must appear as the user types within < 100ms (ideally < 30ms server-side response time).
  • High Availability: If the suggestion service is temporarily degraded, search itself should not fail.
  • Scalability: System must handle high write/read throughput across millions of concurrent search sessions.

2. Capacity Estimations

  • Traffic:
    • 1 billion search queries per day.
    • Average query is 20 characters long. With every keystroke sending an autocomplete request, that represents up to 20 requests per query: 20 billion requests/day ≈ 230,000 QPS (Peak ≈ 500,000 QPS)
  • Data Scale:
    • Assume 100 million unique search phrases.
    • Average query length: 20 characters ≈ 20 bytes.
    • Storage for raw strings: 100M × 20 bytes ≈ 2 GB. Even with Trie node pointers and frequency scores, the active dataset easily fits in memory (around 20 GB - 50 GB).

3. Data Structure: The Enhanced Trie

A standard database query with WHERE query LIKE 'sys%' ORDER BY frequency DESC LIMIT 5 is far too slow for 200k+ QPS. The standard data structure for prefix queries is a Trie (Prefix Tree):

          (root)
         /      \
       [s]      [a]
        │
       [y]
        │
       [s] ───► Node "sys"
      /   \
    [t]   [p]

The Standard Trie Bottleneck

In a basic Trie, once you reach the prefix node "sys", you must traverse all child subtrees to find the leaf words, collect their frequencies, and sort them to get the top 5. In the worst case, this subtree scan visits thousands of nodes on every keystroke.

The Optimization: Storing Precomputed Top-K at Every Node

To achieve O(1) lookup time at query time, store the top 5 suggestions and their frequency scores directly inside each node:

Node: "sys"
Top-5 Precomputed:
  1. "system design" (score: 9500)
  2. "system design interview" (score: 8200)
  3. "systems engineering" (score: 6100)
  4. "sysadmin" (score: 4300)
  5. "system analysis" (score: 3100)
  • Query Complexity: Traversing to node "sys" takes O(L) where $L$ is prefix length (e.g., 3 hops). Fetching the suggestions from that node is O(1)!
  • Space Trade-off: Storing the top 5 pointers at each node increases memory usage by a small constant factor, but keeps latency under 5ms.

4. End-to-End Architecture

A search suggestion system decouples Query Serving (Read Path) from Frequency Updating (Write Path):

[ User Keystroke ("sys") ]
          │
          ▼ (Client Debouncing: 200-300ms)
[ Global CDN / Edge Cache ] ───► (Cache Hit for popular prefixes)
          │
          ▼ (Cache Miss)
[ Load Balancer ]
          │
          ▼
[ Autocomplete Query Service ]
          │
          ▼
[ Distributed Trie In-Memory Cluster ] ◄─── (Periodic Snapshot Reload)
                                                        ▲
════════════════════════════════════════════════════════╪══════════════════════════
[ Asynchronous Analytics Pipeline (Offline) ]           │
                                                        │
[ Search Log Events ]                                   │
          │                                             │
          ▼                                             │
[ Message Stream (Kafka) ]                              │
          │                                             │
          ▼                                             │
[ Aggregation Workers (Flink / Spark) ]                 │
(Aggregates query counts in 1-hour / 24-hour windows)   │
          │                                             │
          ▼                                             │
[ Analytics Database (ClickHouse / DynamoDB) ]          │
          │                                             │
          ▼                                             │
[ Trie Builder Service ] ───────────────────────────────┘
(Constructs new weekly/daily Trie index snapshot)

5. Scaling & Distributed Partitioning

When the number of search queries or languages exceeds a single server's capacity, shard the Trie:

Sharding Strategy 1: Alphabetical Partitioning

  • Shard 1 holds prefixes starting with a-m, Shard 2 holds n-z.
  • Drawback: Skewed traffic. In English, letters like s, t, and c receive exponentially more queries than x or z.

Sharding Strategy 2: Consistent Hashing on Prefix

  • Compute hash(prefix) % num_shards (or use consistent hashing).
  • Evenly distributes load across servers, preventing hot nodes.

6. Client-Side & Network Optimizations

At 500,000 peak QPS, client and network optimizations prevent massive server traffic:

  1. Debouncing: Delay firing the HTTP request until the user pauses typing for 200–300 milliseconds. This eliminates unnecessary requests for intermediary characters.
  2. Client-Side In-Memory Cache: The client caches results for previously typed prefixes. If a user types "system", backspaces to "sys", and retypes "system", the app uses the browser cache with zero network calls.
  3. CDN / Edge Caching: Short prefixes ("a", "am", "b", "we") rarely change their top suggestions. Cache their responses at the CDN edge with a TTL of 1 hour.
  4. Trending & Filtering:
    • Filter inappropriate, hateful, or sensitive terms using an explicit blacklist before displaying suggestions.
    • Blend real-time breaking news spikes by mixing long-term historical query logs with a small streaming top-k buffer.
Loading...