Requirements

Functional Requirements:

• Return suggestions that begin with the user's input
• Return a small list of the most relevant/popular suggestions
• Suggestions update as user types -> real-time

Non-Functional Requirements:

• Low latency <100ms
• Highly available: 99.9% uptime
• Highly scalable
• Eventual consistency for tredning updates

Capacity Estimation

• DAU: 50M
• Seaches/user/day:10
• Total searches/day: 500M
• QPS: ~6k
• Peak x10 traffic - 60k/sec

-> Storage:

• 20M unique queries
• Avg size: ~30-50 bytes
• Total raw: ~2-5gb
• Index size = 10-30gb after expansion

API Design

Suggest API

GET /suggest?q=

res {

query,

suggestions[]

}

Store user query for index building and trending updates

POST /query

req {

query,

timestamp,

geolocation

}

High-Level Design

API Gateway

Acts as the entry point for all client requests.

Responsibilities:

• Authentication (if required)
• Rate limiting - Applied using token bucket per IP to prevent fraudulent or bot views
• Request routing

Load Balancer

Distributes traffic across multiple instances of all services to improve scalability and availability.

Typeahead service

Responsbility:

• Read path
• Recieves user query
• fetches index from Redis
• If found -> returns
• if miss -> fall back to the inverted index

Query Processing service

Responsibility

• recieves raw user query
• emits the query to kafka

Kafka

• Event backbone for user query
• Uses query string as partition key
• Gurantees at least once delivery

Flink streaming

Responsibility

• Consumes event from kafka
• Deduplication
• Normalizes query
• Spam filters and cleanup

Query Aggreation store

Responsibilities:

• Aggregates all user query and stores stats -> frequency, recency score
• Detects hot queries

Index builder job

Responsiblities:

• Batch processing job running periodically
• Fetches query from query aggreation store
• Generates prefixes for each query
• Ranks and compute topk per prefix
• Stores it in Inverted index and in redis

Inverted index

Responssibilties

• Stores index and its top ranked suggestions
• eg: "app" -> ["apple", "appstore", "apple watch"]

Redis

• Caching layer
• Stores hot index-> uses LFU

Database Design

we dont use relational DB for this, instead we use:

• Inverted index - storing indexes with suggestions
• Redis - caching hot indexes for fast lookups
• Cassandra - Query stats store
• Datalake - storing raw user queries

Detailed Component Design

We will now deep dive into these topics:

How Index is build?

-> The high level flwo is

User query -> kafka -> Flink streaming -> Query agg store -> index builder job -> inverted index

• User types something
• Quiery processing service emits an event to kafka
• Flinks reads that and it:
  • Deduplicates
  • Normalizes
  • Spam filters and cleanup
• Query aggreation store -> aggreates data and stats about each query:
  • eg:

Index builder job

• batch jobs or incremental update for hot keys only
• Turns raw aggreated data into index for suggestions

-> how does it work

1. Read stats from aggregation store
2. Generates prefixes:
   1. for each query: "apple", it genrates
      1. "a", "ap", "app", "appl".....
   2. Builds inverted mapping
      1. convert query -> prefixes into prefix -> list of queries
         1. eg: "app" -> apple, apple watch, ...
   3. Rank suggestions per prefix and keeps top k
   4. finally indexes are built and stored in an inverted idnex and redis

Ranking System

Each query is scored using:

Trending score:

• computed from:
  • 10 sec window
  • 1 min window
  • velocity (rate of change)

Real-time updates/Hot key detection:

-> how does it work

• Query agg service-> immediately update stats
• Hot key detection
  • Query agg service idenities hot queriers based on:
    • count_10s > threshold OR
    • velocity spike > baseline (z-score anomaly)
• for hot keys -> bypass batch update and trigger incremental index update

Update process after query is detected as hot query:

1. Fetch current prefix entry:

1. Update ranking scores based on new trend:

1. Re-sort top-K:

1. Write back to:

• Redis (fast serving layer)
• Inverted index store

Handling cache miss

-> If redis misses:

• • Fallback to inverted index store
  • Try a shorter prefix
  • Fallback to trending queries

Scaling strategies:

• Sharding queries
  • By prefix range: a-f, g-m, n-z
  • Or consistent hashing on prefix
• Hot key optimization
  • frequency accessed prefixes stored in redis

Consistency Model

• Write path: eventual consistency
• Hot keys: near real-time (seconds)
• Batch index: source of truth
• Redis: ephemeral acceleration layer

Conflict resolution:

• timestamp/version-based overwrite