Design a search autocomplete in HLD - System Design Exercise

Design: Search Autocomplete System

Design covers backend architecture, data storage, and request flow for autocomplete suggestions. Frontend UI and personalization algorithms are out of scope.

Functional Requirements

FR1: Provide real-time suggestions as users type search queries

FR2: Support at least 10,000 concurrent users

FR3: Return autocomplete suggestions with p99 latency under 100ms

FR4: Handle updates to the suggestion data daily

FR5: Support prefix matching and popular query ranking

FR6: Allow personalization based on user history (optional)

Non-Functional Requirements

NFR1: System must be highly available with 99.9% uptime

NFR2: Suggestions must be relevant and ordered by popularity

NFR3: Data updates should not block user queries

NFR4: Support multi-region deployment for low latency

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

API Gateway or Load Balancer

Autocomplete Query Service

In-memory Cache (e.g., Redis) for fast prefix lookup

Persistent Storage for suggestion data (e.g., NoSQL or Search Engine)

Data Ingestion Pipeline for updating suggestions

Ranking Module for ordering suggestions by popularity

Design Patterns

Trie or Prefix Tree data structure for prefix matching

Caching frequently requested prefixes

Batch processing for data updates

Asynchronous data refresh to avoid query blocking

Sharding or partitioning for scaling

Reference Architecture

Client
  |
  v
API Gateway / Load Balancer
  |
  v
Autocomplete Query Service <--> Cache (Redis) <--> Persistent Storage (NoSQL / Search Engine)
  ^
  |
Data Ingestion Pipeline (Batch updates)

Components

API Gateway / Load Balancer

Nginx / AWS ALB

Distribute incoming autocomplete requests to backend services

Autocomplete Query Service

Node.js / Python microservice

Process user queries, fetch suggestions from cache or storage, apply ranking

In-memory Cache

Redis with Trie or Sorted Sets

Store popular prefixes and suggestions for low latency retrieval

Persistent Storage

Elasticsearch or Cassandra

Store full suggestion dataset and support complex queries

Data Ingestion Pipeline

Apache Kafka + Spark / Batch jobs

Process search logs or curated data to update suggestion dataset daily

Ranking Module

Custom logic in Query Service

Order suggestions by popularity and relevance

Request Flow

1. User types query in client UI

2. Client sends autocomplete request to API Gateway

3. API Gateway forwards request to Autocomplete Query Service

4. Query Service checks Redis cache for prefix matches

5. If cache hit, return top suggestions immediately

6. If cache miss, query Persistent Storage for suggestions

7. Apply ranking logic to order suggestions

8. Return suggestions to client

9. Data Ingestion Pipeline processes new search logs daily

10. Pipeline updates Persistent Storage and refreshes Redis cache asynchronously

Database Schema

Entities: - Suggestion: {id, text, popularity_score, language, last_updated} - PrefixIndex: {prefix, suggestion_ids[]} Relationships: - PrefixIndex maps prefixes to multiple Suggestion ids for fast lookup - Suggestion stores metadata for ranking and filtering

Scaling Discussion

Bottlenecks

Cache size limits for storing all prefixes

High read traffic causing query service overload

Data ingestion pipeline delays affecting freshness

Network latency for global users

Solutions

Shard cache by prefix ranges or user regions

Use horizontal scaling and load balancing for query service

Implement incremental updates and streaming data pipelines

Deploy services in multiple regions with CDN for static assets

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing architecture and data flow, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Clarify data sources and update frequency

Explain choice of cache and persistent storage

Describe prefix matching and ranking approach

Discuss latency and availability targets

Address scaling challenges and solutions

Mention optional personalization and multi-language support

Practice

1. What is the primary purpose of a search autocomplete system in a web application?

easy

A. To display full search results immediately

B. To store user passwords securely

C. To suggest possible search terms as the user types

D. To block unwanted users from searching

Solution

1. Step 1: Understand autocomplete function

   Autocomplete helps users by suggesting search terms while they type, improving speed and experience.

2. Step 2: Eliminate unrelated options

   Options about password storage, blocking users, or showing full results do not match autocomplete's purpose.

3. Final Answer:

   To suggest possible search terms as the user types -> Option C

4. Quick Check:

   Autocomplete = Suggest terms [OK]

Hint: Autocomplete suggests terms as you type [OK]

Common Mistakes:

• Confusing autocomplete with full search results
• Thinking autocomplete handles security
• Assuming autocomplete blocks users

2. Which data structure is most suitable for efficiently storing and searching prefixes in an autocomplete system?

easy

A. Trie (Prefix Tree)

B. Hash Map

C. Stack

D. Queue

Solution

1. Step 1: Identify prefix search needs

   Autocomplete requires fast prefix matching, which means quickly finding all words starting with a given prefix.

2. Step 2: Match data structure to prefix search

   Trie (prefix tree) stores characters in a tree structure, enabling efficient prefix lookups compared to hash maps or linear structures.

3. Final Answer:

   Trie (Prefix Tree) -> Option A

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Prefix search? Use Trie for fast lookup [OK]

Common Mistakes:

• Choosing hash map which is not prefix-optimized
• Using stack or queue which are not for prefix search
• Ignoring prefix search efficiency

3. Consider a search autocomplete system using a Trie. If the user types the prefix "app", which of the following outputs is correct assuming the Trie contains words: ["apple", "app", "application", "apt"]?

medium

A. ["apple", "apt"]

B. ["application", "apt"]

C. ["app", "apt"]

D. ["apple", "app", "application"]

Solution

1. Step 1: Identify words starting with prefix "app"

   From the list, words starting with "app" are "apple", "app", and "application".

2. Step 2: Exclude words not matching prefix

   "apt" starts with "ap" but not "app", so it is excluded.

3. Final Answer:

   ["apple", "app", "application"] -> Option D

4. Quick Check:

   Prefix "app" matches apple, app, application [OK]

Hint: Match prefix exactly, exclude partial matches [OK]

Common Mistakes:

• Including words that don't fully match prefix
• Confusing prefix length
• Ignoring exact prefix matching

4. A search autocomplete system returns no suggestions when the user types "xyz". What is the most likely cause?

medium

A. The prefix "xyz" does not exist in the data store

B. The system cache is full

C. The user has no internet connection

D. The autocomplete service is overloaded

Solution

1. Step 1: Analyze no suggestions for prefix

   No suggestions means no matching entries for the typed prefix in the autocomplete data.

2. Step 2: Evaluate other options

   Cache full or service overload might cause delays but not necessarily zero suggestions; no internet affects connectivity but question focuses on autocomplete output.

3. Final Answer:

   The prefix "xyz" does not exist in the data store -> Option A

4. Quick Check:

   No suggestions = No matching prefix [OK]

Hint: No suggestions? Check if prefix exists in data [OK]

Common Mistakes:

• Assuming cache full causes no suggestions
• Blaming internet without checking data
• Confusing overload with empty results

5. You are designing a scalable search autocomplete system for millions of users. Which combination of components best supports fast prefix search, low latency, and scalability?

hard

A. Monolithic server + No caching

B. Client-side cache + Trie-based service + Distributed cache layer

C. Flat file storage + Server-side rendering

D. Single database with full table scan + Client polling

Solution

1. Step 1: Identify scalable components for autocomplete

   Trie-based service enables fast prefix search; distributed cache reduces latency and load; client-side cache improves responsiveness.

2. Step 2: Eliminate inefficient options

   Full table scans and flat files cause slow searches; monolithic servers without caching do not scale well.

3. Final Answer:

   Client-side cache + Trie-based service + Distributed cache layer -> Option B

4. Quick Check:

   Scalable autocomplete = Trie + caching layers [OK]

Hint: Use Trie + caching layers for scalable autocomplete [OK]

Common Mistakes:

• Ignoring caching for latency
• Using full scans causing slow response
• Relying on monolithic servers only