Katkat
Back

Design a Low-Latency Typeahead Service

PinterestSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This problem tests the ability to design a high-throughput, low-latency search suggestion system that handles real-time updates and ranking at scale.

Problem Statement

Design a typeahead (autocomplete) service that provides the top 10 search suggestions as a user types. The system must support millions of active users and handle rapid updates to suggestion scores based on trending queries.

Functional Requirements

  • Provide top 10 suggestions given a prefix.
  • Real-time updates: Scores should reflect recent user activity.
  • Deterministic tie-breaking: If two suggestions have the same score, use lexicographical order.

Non-Functional Requirements

  • Latency: P99 latency must be under 50ms.
  • Consistency: Eventual consistency is acceptable, but popular queries should be reflected quickly.
  • Availability: The system must remain highly available during node failures.

Requirements for the design:

  1. Data Model: Propose a schema and storage engine choice (e.g., Trie, Inverted Index, KV store).
  2. Sharding Strategy: Explain how to distribute data across the cluster to minimize cross-shard coordination.
  3. Caching: Define what and where to cache (e.g., CDN, application-level cache, client-side).
  4. Abuse Control: How would you prevent malicious queries or bot-generated trends from polluting the suggestion index?
  5. Normalization: Briefly address how to handle multi-language input and character normalization (e.g., removing accents).

Hints

Hint 1

Consider pre-computing results for common prefixes to shift work from read-time to write-time.

Hint 2

Think about the trade-off between using a Trie structure in memory versus a sorted distributed key-value store like Redis.

Hint 3

For real-time updates, utilize a streaming pipeline (e.g., Kafka) to aggregate click data and update scores asynchronously.

Follow-up questions

  • How would you handle personalizing results based on a user's past search history?
  • If the query index grows significantly larger than available RAM, what partitioning or eviction strategy would you employ?
  • How would you measure the quality of suggestions and detect if the model is returning irrelevant data?