Complex Systems · Phase 4: High-Level Design (HLD)
Distributed Search Autocomplete & Typeahead Engine
Design a low-latency typeahead service with bounded prefix lookup, versioned immutable indexes, safe ranking, debouncing, cancellation, and atomic rollout.
Primary specification: Meta Engineering: The Life of a Typeahead Query
Lesson 33 of 33
1d streakThe Architectural Question
Executing an unbounded prefix scan and ranking query for every keystroke makes latency depend on corpus size and sends superseded work downstream.
Core Engineering Objectives
- Prefix search algorithms: Ternary Search Trees vs Prefix Hash Tables vs Inverted Index vs Trie with pre-computed top-K
- Offline vs Online processing: Offline MapReduce/Spark frequency computation; Online read-only serialized Trie querying
- Edge caching: Caching popular 1-letter, 2-letter, and 3-letter prefix suggestions at CDN edge nodes
1. Typeahead Is Retrieval Under a Human Latency Budget
1. Browser
Debounces input and cancels superseded requests.
2. Edge cache
Serves safe popular short-prefix results.
3. Query service
Normalizes locale, applies policy, and selects shards.
4. Versioned index
Returns precomputed Top-K candidates for the prefix.
5. Merger
Combines, filters, and returns one ranked response.
Heavy frequency aggregation and index construction happen offline; the online path stays bounded by K and shard count.
Typeahead returns a small ranked set while the user is still typing. It is not the final search results page: late answers are often useless, the candidate set is intentionally bounded, and ranking must combine prefix match with popularity, freshness, locale, safety, and sometimes personalization. The core design is to precompute expensive work so the online path performs a bounded lookup.
Prefix index
A structure that maps a normalized prefix to candidate completions.
Top-K materialization
Precomputing only the best K suggestions at an index state, avoiding subtree scans during reads.
FST
A compact finite-state transducer representation that shares common prefixes and suffixes for fast weighted lookup.
Debounce
Waiting briefly after input before sending a request, reducing superseded work while adding controlled delay.
2. Define Relevance, Privacy, and Freshness
| Requirement | Worked-example target | Design consequence |
|---|---|---|
| Latency | p99 service time below 50 ms | In-memory bounded lookup; cancel stale requests |
| Results | At most 8 suggestions | Precompute Top-K and cap fanout |
| Freshness | Popular-query updates within 15 minutes | Versioned incremental index publication |
| Safety | Block disallowed or low-support queries | Policy filtering before publication and again at serve time |
| Locale | Separate normalized indexes per language/market | Do not mix incompatible normalization or ranking statistics |
| Privacy | No raw rare-query promotion | Aggregation thresholds, retention limits, and access controls |
Use it when
Use a dedicated completion index when prefix traffic is high, result count is small, and predictable latency matters more than arbitrary query expressiveness.
Reconsider when
Use the normal search engine with prefix fields when the corpus is modest, updates must be immediately searchable, or suggestions require rich filters that would explode a precomputed prefix map.
3. Estimate Requests After Debouncing
Given 50 million daily active users, 10 search sessions/user/day, four typed states per session after client debouncing, a 10x peak factor, and a 700-byte response, compute the serving envelope. The assumptions are illustrative.
| Dimension | Arithmetic | Result |
|---|---|---|
| Requests/day | 50M × 10 × 4 | 2 billion |
| Average request rate | 2B / 86,400 | ≈23,148 requests/s |
| Peak request rate | 23,148 × 10 | ≈231k requests/s |
| Peak response payload | 231k × 700 B | ≈162 MB/s before protocol/compression |
| Without debounce, 8 states/session | 50M × 10 × 8 | 4 billion requests/day |
| Debounce saving in example | (4B - 2B) / 4B | 50% fewer requests |
Do not estimate index memory from phrase count alone. Serialize a representative sample, measure bytes per phrase including Top-K references, then multiply by 100M and add allocator plus rollout headroom. For example, 80 measured bytes per phrase implies about 8 GB of serialized data before replicas and before keeping old and new index versions side by side.
Prefix Popularity Is Extremely Skewed
4. Split Offline Index Building from Online Serving
- 01Event collection: records accepted searches and suggestion selections with privacy controls.
- 02Aggregation: computes counts over time windows and suppresses rare/noisy entries.
- 03Candidate and policy pipeline: normalizes text, applies allow/block rules, computes ranking features, and selects Top-K per prefix.
- 04Index builder: produces an immutable versioned FST, radix tree, or prefix table plus a manifest and checksum.
- 05Publisher: uploads the version, warms replicas, verifies health, then atomically switches the active manifest.
- 06Serving tier: performs bounded in-memory lookup; an aggregator may merge global, local, and personalized sources in parallel.
- 07Client: debounces input, cancels superseded requests, rejects out-of-order responses, and caches safe results briefly.
Architectural Boundary · Do Not Confuse
One mutable global trie
Immutable versioned index
In-place mutation offers fast freshness but complicates concurrency, rollback, and replica consistency. Immutable snapshots make validation, atomic rollout, cache versioning, and rollback straightforward; a small delta index can bridge freshness between rebuilds.
5. Normalize Without Losing Display Quality
SUGGESTION
normalized_key comparison form
display_text user-facing form
locale
entity_id optional stable identity
score_features frequency, recency, quality, safety
policy_version
INDEX MANIFEST
version
locale
object_uri
checksum
built_from_window
created_at
INVARIANTS
every served suggestion passed the active policy version
Top-K order is deterministic for equal inputs
normalization is locale-aware and versioned
a server response carries request_id and index_versionKeep normalized comparison text separate from display text. Lowercasing, Unicode normalization, whitespace folding, and accent handling can improve matching but must not corrupt names or mix scripts. Version normalization so a rebuild and rollback reproduce the same keys.
6. Serve Only the Latest User Intent
onInputChanged(text):
normalized = normalize(text, locale)
cancel pending debounce and in-flight request
if length(normalized) < minimumPrefix: show local defaults
after debounce:
requestId = nextMonotonicClientId()
response = GET /suggest?q=normalized&locale=locale
if response.requestId != latestRequestId: discard
render response.items
serve(prefix, context):
key = (indexVersion, locale, policyVersion, prefix)
global = prefixIndex.lookupTopK(key, 20)
personal = permittedPersonalIndex.lookup(prefix, 10)
merged = rankAndDeduplicate(global, personal, context)
return first 8 policyApproved itemsCancellation Saves More Than Browser Work
7. Handle Hot Prefixes, Bad Indexes, and Poisoned Trends
| Failure | Cause | Mitigation |
|---|---|---|
| Short-prefix hot key | Millions of users request the same prefix | CDN/process cache, request coalescing, replicated shards |
| Partial index rollout | Replicas serve different ranking versions | Version in cache key/response; atomic manifest activation |
| Bad suggestions spread globally | Bots or breaking events manipulate counts | Support thresholds, anomaly detection, policy review, fast blocklist |
| Personal data leaks | Rare queries become public suggestions | Minimum cohort thresholds, aggregation, deletion workflow |
| Shard timeout | One candidate source is slow | Per-source deadline and partial response with stable fallback |
Use it when
Return a partial result when one optional candidate source misses its deadline and the remaining suggestions are safe and useful.
Reconsider when
Fail closed when the unavailable dependency performs mandatory authorization or safety filtering that cannot be reproduced locally.
8. Measure Usefulness, Not Only Latency
Operational metrics include p50/p95/p99 latency by prefix length, cache hit ratio, cancellation rate, index age, rollout version skew, empty-result rate, and dependency timeouts. Product metrics include selection rate, accepted suggestion rank, reformulation, abandonment, and harmful-result reports. A faster irrelevant suggestion is not a better system.
Documented Design Pattern
9. Active Recall
Active Recall Checkpoint
Why cache or precompute Top-K suggestions at prefix nodes instead of scanning the full subtree on every keystroke?
Show answer & explanation
Subtree size grows with corpus vocabulary and makes latency depend on the prefix. Materialized Top-K bounds online work to a lookup plus a small merge, moving expensive aggregation and ranking into the index-build path.
Active Recall Checkpoint
Why must the response include both a client request ID and an index version?
Show answer & explanation
The request ID prevents an older response from replacing newer typed intent. The index version makes rollouts and cache entries observable, prevents mixing incompatible snapshots, and enables deterministic rollback.
Topic sizing snapshot
The four numbers that materially affect this architecture. Use them as bounds, not as a generic calculator embedded in every lesson.
Peak QPS
~231,000 requests/sec under the lesson’s illustrative 10x peak
5-Yr Storage
Versioned indexes plus retained aggregate events; benchmark representation
Bandwidth
~1.3 Gbps response payload before protocol/compression
Working Set RAM
Measure serialized FST/radix index and Top-K payload per locale
Architectural Trade-Off Analysis
Compare latency, throughput, consistency, and operational complexity across core industry alternatives.
Architecture Decision Matrix
Multi-axis engineering evaluation and FAANG interview rules of thumb.
SQL (Postgres / MySQL)
Relational ACID Store
Structured schema, relational joins, ACID transactions, and strict foreign keys.
NoSQL (Cassandra / DynamoDB)
Distributed Non-Relational Store
Horizontal partition keys, denormalized documents/wide-columns, and tunable consistency.
| Evaluation Axis | SQL (Postgres / MySQL) | NoSQL (Cassandra / DynamoDB) | Details |
|---|---|---|---|
Latency | Moderate | Strong | |
Throughput | Moderate | Strong | |
Scalability | Moderate | Strong | |
Consistency | Strong | Moderate | |
Complexity | Strong | Moderate | |
Cost | Moderate | Strong |
When to Choose in an Architecture Interview
Choose SQL when ACID guarantees are non-negotiable (financial ledgers, payment processing, inventory checkout) or when query access patterns are unpredictable and require ad-hoc analytical joins.
Choose NoSQL when write volume exceeds single-node capacity (>20K writes/sec), data is unstructured/hierarchical (logs, telemetry, user feeds), or multi-region active-active replication is mandatory.
Never say "NoSQL is faster than SQL" without qualification. SQL with proper B-Tree indexes on indexed primary keys is lightning fast. NoSQL wins on horizontal write scaling, not inherent single-row read speed.
Production Postmortem & Verification
Production Incident Postmortem
- Trigger / Setup: A search engine executes dynamic SQL wildcard prefix queries on every user keystroke across millions of web clients.
- Production Symptom: I/O and CPU rise with short-prefix fanout while late responses overwrite newer user intent.
- Root Cause & Fix: Move expensive ranking to a versioned build pipeline and keep online lookup, merging, cancellation, and safety filtering bounded.
Acceptance Criteria & Outcomes
- Design an in-memory Trie node storing character, end-of-word flag, and pre-computed Top-5 suggestions.
- Decouple read path from frequency updates using an offline pipeline: Log collector -> Kafka -> MapReduce -> Trie Builder -> Hot reload.
- Implement client-side keystroke debouncing (300ms) and CDN caching for 1-char and 2-char prefixes.
Architectural & Technical Interview Review
Core FAANG Interview Questions
Q01How do you justify introducing Distributed Search Autocomplete & Typeahead Engine into a high-scale production architecture?Click to reveal model answer →Hide answer ↑Requirements & Design Brief
Introduce Distributed Search Autocomplete & Typeahead Engine only when measured scale, data size, or failure boundaries exceed single-node capacity. State the exact bottleneck, evaluate operational overhead, and verify that the trade-offs justify the added moving parts.
Q02What is the primary trade-off and hidden operational cost of Distributed Search Autocomplete & Typeahead Engine?Click to reveal model answer →Hide answer ↑Architecture Trade-offs
It improves scalability and availability, but introduces network hops, serialization overhead, and eventual consistency or coordination complexity.
Q03How do you handle catastrophic failure or dependency degradation in Distributed Search Autocomplete & Typeahead Engine?Click to reveal model answer →Hide answer ↑Failure Review & Recovery
Implement connect/read timeouts, exponential backoff with jitter, and fallback defaults so downstream degradations do not cause cascading outages.
Production Pitfalls & Anti-Patterns
Critical Failure Anti-Patterns
Premature Distributed Complexity
Scattering distributed components before identifying concrete write, read, or storage limits creates accidental points of failure and operational debt.
Production Mitigation: Start with the simplest modular design that satisfies requirements, evolving it only as measured constraints dictate.
Unbounded Retries and Cascading Storms
When a dependency degrades, immediate synchronized retries multiply downstream traffic, turning a minor slowdown into a total fleet outage.
Production Mitigation: Enforce strict retry budgets, exponential backoff, and full randomized jitter on all client calls.
Neglecting Observability and Metrics
Deploying architecture without distributed tracing or p99 tail latency alerts leaves engineers blind when partial partitions occur.
Production Mitigation: Export metrics for request rate, error rate, p95/p99 duration, and saturation at every service boundary.