Search Autocomplete System Design (HLD & LLD)

Functional Requirements

1. Show suggestions as the user types.
2. Suggestions should appear within 50-100 ms.
3. Rank suggestions by:
   • Popularity
   • Relevance
   • Recency
4. Support millions of queries per second.
5. Update suggestions periodically.

Example:

User types:
iph

Suggestions:
iphone 15
iphone charger
iphone case
iphone 14

High-Level Architecture

flowchart TD
    U[User] --> CDN[CDN / Edge Cache]
    CDN --> GW[API Gateway]
    GW --> AS[Autocomplete Service]
    AS --> R[(Redis Cache)]
    AS --> IDX[(Trie / Elasticsearch)]
    AS --> RS[Ranking Service]
    RS --> QA[Query Analytics]
    QA --> DP[Data Pipeline]
    DP --> DB[(Database)]

Request Flow

sequenceDiagram
    participant User
    participant API as API Gateway
    participant S as Autocomplete Service
    participant C as Redis
    participant I as Search Index

    User->>API: GET /search/suggest?q=iph
    API->>S: Forward request
    S->>C: Lookup prefix
    alt Cache Hit
        C-->>S: Suggestions
    else Cache Miss
        S->>I: Prefix search
        I-->>S: Suggestions
    end
    S-->>User: Top suggestions

Request:

GET /search/suggest?q=iph

Response:

[
  "iphone 15",
  "iphone charger",
  "iphone case",
  "iphone 14"
]

Design Considerations

Low Latency

Target response time: <100 ms

Optimizations:

• Redis cache
• Trie prefix search
• CDN caching
• Edge compute

Read-Heavy Workload

Reads: 10000
Writes: 1

Optimize primarily for reads.

Data Sources

• Historical search queries
• Product catalog
• Trending searches

Data Storage

SearchQueries
-------------------------
query
frequency
last_searched_at

Example values:

iphone
iphone charger
iphone case

Redis Cache

Key: prefix:iph

Value:
[
 "iphone 15",
 "iphone charger",
 "iphone case"
]

TTL: 5-30 minutes

Search Index Options

Option	Advantages	Use Case
Trie	Fast prefix lookup	Pure autocomplete
Elasticsearch	Prefix search, fuzzy search, ranking	Large-scale search

Trie Structure

flowchart TD
    R[root] --> I[i]
    I --> P[p]
    P --> H[h]
    H --> O[o]
    O --> N[n]
    N --> E[e]
    E --> C[case]
    E --> CH[charger]

Each node stores:

prefix
top_k_suggestions
frequency

Low-Level Design

Suggestion

class Suggestion {
    String query;
    int frequency;
}

TrieNode

class TrieNode {

    Map<Character, TrieNode> children;
    boolean isWord;

    List<Suggestion> topSuggestions;

    TrieNode() {
        children = new HashMap<>();
        topSuggestions = new ArrayList<>();
    }
}

Trie

class Trie {

    private TrieNode root = new TrieNode();

    public void insert(String word) {

        TrieNode node = root;

        for(char c : word.toCharArray()) {

            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);

        }

        node.isWord = true;
    }

    public List<String> searchPrefix(String prefix) {

        TrieNode node = root;

        for(char c : prefix.toCharArray()) {

            if(!node.children.containsKey(c))
                return new ArrayList<>();

            node = node.children.get(c);
        }

        return getSuggestions(node);
    }

    private List<String> getSuggestions(TrieNode node) {

        List<String> result = new ArrayList<>();

        dfs(node, result);

        return result;
    }

    private void dfs(TrieNode node, List<String> result) {

        if(node.isWord)
            result.add("");

        for(Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
            dfs(entry.getValue(), result);
        }
    }
}

Autocomplete Service

class AutocompleteService {

    private Trie trie;

    public List<String> getSuggestions(String prefix) {

        return trie.searchPrefix(prefix);

    }

}

Ranking

score =
    w1 * frequency
  + w2 * recency
  + w3 * click-through-rate

Example:

score = 0.6*freq + 0.3*recency + 0.1*ctr

Scaling

Assumptions:

100M daily users
20 searches/user/day
2B searches/day
10 autocomplete requests/search
20B autocomplete requests/day
~230K requests/sec

Distributed Deployment

flowchart TD
    LB[Load Balancer]
    LB --> A1[Autocomplete Service]
    LB --> A2[Autocomplete Service]
    LB --> A3[Autocomplete Service]
    A1 --> RC[(Redis Cluster)]
    A2 --> RC
    A3 --> RC
    RC --> ES[(Search Index)]

Performance Optimizations

• Prefix cache
• Top-K suggestions stored at each Trie node
• Client-side debounce (300 ms)

Updating Suggestions

flowchart TD
    L[Search Logs] --> K["Analytics Pipeline (Kafka + Spark)"]
    K --> F[Update Frequency]
    F --> I[Rebuild Index]

Typo Handling

• Levenshtein distance
• Elasticsearch fuzzy search

Example:

iphoen -> iphone

Bottlenecks

Hot prefix:

i

Mitigations:

• Heavy caching
• CDN

Security

• Rate limiting
• CAPTCHA
• IP throttling

Interview Focus

1. Trie for prefix search
2. Top-K suggestions at each Trie node
3. Heavy caching
4. Analytics pipeline
5. Distributed architecture

Summary

• Trie provides efficient prefix lookup, while Elasticsearch adds advanced search capabilities.
• Redis caching and precomputed Top-K suggestions enable sub-100 ms responses.
• Separate analytics pipelines continuously refresh ranking and suggestion quality.
• Horizontal scaling, distributed caches, and sharded indexes support hundreds of thousands of requests per second.
• Ranking combines frequency, recency, and engagement metrics for relevant suggestions.