Katkat
Back

Design a Typeahead Suggestion System

PinterestSoftware Engineer · Onsite
EasySoftware EngineerOnsiteSystem Design

Last updated

Design a low-latency, real-time typeahead suggestion system that handles prefix search, query ranking, aggressive caching, and stale response mitigation.

Scenario

Design the autocomplete/typeahead suggestion service for a discovery and bookmarking platform like Pinterest. As a user types into the search bar (e.g., "wed..." or "farmh..."), the system should present a list of 5 to 10 highly relevant query completions in real time to guide user exploration.

Requirements

Functional Requirements

  • Prefix Search: Return top $K$ (e.g., $K = 5$ to $10$) suggested query strings matching the user's typed prefix.
  • Ranking: Suggestions must be ranked by popularity, frequency, and trending relevance.
  • Client Consistency: Ensure the client interface gracefully handles network latency and avoids rendering stale out-of-order responses (e.g., results for "c" arriving after results for "cup").
  • Index Freshness: Continuously update search phrase popularity and remove prohibited or spam terms.

Non-Functional Requirements

  • Ultra-low Latency: p99 response time under 30ms so suggestions feel instantaneous.
  • High Availability: 99.99% uptime.
  • High Throughput: Designed for global scale.

Scale Assumptions

  • Daily Active Users (DAU): 500 million.
  • Daily Searches: 2 billion total searches, averaging 4 prefix queries per search session (8 billion autocomplete requests per day).
  • Peak Traffic: Average ~90,000 requests per second (RPS), with peak traffic reaching ~250,000 RPS.
  • Vocabulary: 100 million unique searchable query terms.

What to Cover

  1. API Design: Define the endpoint for fetching completions, including client-side query sequence tracking.
  2. Data Structure & Storage: Choose and justify the core data structure for prefix matching (e.g., Trie, Radix Tree, or FST). Detail how top suggestions are stored to avoid deep traversal at read time.
  3. System Architecture: Diagram the flow from client, CDN/Edge, suggestion serving layer, in-memory caches, to offline index generation pipelines.
  4. Update Strategy: Contrast offline batch re-indexing with streaming pipelines for trending queries, explaining how indexes are swapped safely in production.
  5. Client Optimizations: Address client debouncing, caching, and handling of out-of-order asynchronous responses.

Hints

Hint 1

Precomputing and storing the top K results directly on each trie node or prefix bucket eliminates the need to traverse descendant subtrees during runtime queries.

Hint 2

On the client, use monotonically increasing sequence IDs or cancellation tokens (such as AbortController in browsers) to discard responses that correspond to outdated prefix states.

Hint 3

Decouple the serving path from the update path by generating immutable trie snapshots via an offline analytics pipeline and swapping them into memory atomically.

Follow-up questions

  • How would you personalize suggestions based on a user's recent activity or followed boards without exceeding your 30ms latency budget?
  • How would you handle sudden breaking trends or the immediate removal of sensitive/copyrighted terms without waiting for a full offline index rebuild?
  • If the trie exceeds the RAM capacity of a single machine, how would you partition the dataset across multiple nodes?