Katkat
Back

Design Real-Time Search Autocomplete with Top-10 Popularity-Ranked Prefix Suggestions

PinterestSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSystem Design

Last updated

Design a distributed search autocomplete system capable of returning the top 10 popularity-ranked queries for any prefix with sub-30ms latency. The problem evaluates your ability to handle massive read throughput, partition heavily skewed prefix workloads, and merge streaming popularity signals with batch historical baselines.

Scenario

You are tasked with designing the search autocomplete system for a large-scale visual discovery and social platform like Pinterest. As users type in the search bar, the client fires a request on almost every keystroke to fetch the top 10 most relevant, popularity-ranked query completions. The system must adapt quickly to real-time viral trends while maintaining robust historical baselines and near-instant response times.

Requirements

Functional Requirements

  • Return the top 10 completions matching an exact text prefix string.
  • Rank suggestions using a score that combines long-term historical popularity with real-time trending spikes (freshness within 2–5 minutes).
  • Support filtering or suppression of malicious, adult, or banned terms.

Non-Functional Requirements

  • Latency: p99 read latency < 30ms globally.
  • Availability: 99.99% uptime; search autocomplete failure should degrade gracefully without breaking search.
  • Scalability: Support 1 billion total users and hundreds of millions of daily active searchers.
  • Freshness: Breaking trends and viral spikes should reflect in autocomplete within minutes.

Scale & Traffic Estimations

  • DAU: 500 million users conducting an average of 4 searches per day.
  • Query Volume: An average search query has ~15 characters, generating ~5 autocomplete requests per search (after client-side debouncing). This yields ~10 billion autocomplete requests per day (~115,000 QPS average, ~300,000 QPS peak).
  • Vocabulary: ~100 million unique valid query terms tracked globally.

Key Areas to Cover

  1. Data Model & Serving Engine: Evaluate in-memory Prefix Trees (Tries) versus precomputed Key-Value lookups (prefix -> top_10_list). Address memory footprints and read/write trade-offs.
  2. Hybrid Freshness Pipeline: Architecture to merge batch historical scores (e.g., daily Spark jobs) with real-time sliding window counts (e.g., Kafka + Flink).
  3. Sharding & Hot Key Mitigation: Strategy for handling extreme read skew on 1-to-2-letter prefixes (e.g., "d", "diy", "h", "home") across distributed storage nodes.
  4. Replication & Synchronization: How data updates propagate across replicas without triggering latency spikes or inconsistent ordering.

Hints

Hint 1

Evaluate whether performing trie traversals dynamically during every read query is necessary, or if precomputing the top 10 results for each prefix into a key-value store offers better tail latency.

Hint 2

To capture breaking news or viral trends without corrupting historical baselines, separate score computation into a decaying moving average or an additive streaming delta layer.

Hint 3

Short prefixes have high cardinality completions and disproportionate traffic; consider handling prefixes of length <= 3 through dedicated, heavily replicated edge caches.

Follow-up questions

  • How would you personalize autocomplete results based on a user's recent pin history, gender, or locale without sacrificing the 30ms latency budget?
  • If a sudden global event generates millions of searches for a brand new phrase that does not exist in the batch dictionary, how does your streaming pipeline detect, validate, and index it safely?
  • How would you implement circuit breakers and cache fallback strategies to survive a 4x unexpected traffic spike during a major holiday season?