Design a search autocomplete in HLD - Scalability & System Analysis

Scalability Analysis - Design a search autocomplete

Growth Table: Search Autocomplete Scaling

Users	Requests per Second (QPS)	Data Size	Latency Requirement	System Changes
100 users	~50 QPS	Thousands of keywords	<1 second	Single server, in-memory trie, simple cache
10,000 users	~5,000 QPS	Millions of keywords and queries	<200 ms	Load balancer, multiple app servers, Redis cache, read replicas
1,000,000 users	~500,000 QPS	Hundreds of millions keywords, user personalization data	<100 ms	Sharded databases, distributed cache, CDN for static assets, async updates
100,000,000 users	~50 million QPS	Billions of keywords, global personalization	<50 ms	Global data centers, multi-level caching, advanced sharding, ML model serving clusters

First Bottleneck

The first bottleneck is the database that stores keywords and query statistics. At low scale, a single database can handle autocomplete queries. As users grow, the database query rate and data size increase, causing slow response times and connection limits.

Scaling Solutions

• Read Replicas: Add read-only database replicas to distribute query load.
• Caching: Use in-memory caches (Redis, Memcached) to store popular autocomplete results.
• Horizontal Scaling: Add more application servers behind a load balancer to handle concurrent requests.
• Sharding: Partition the keyword data by prefix or user region to reduce single database load.
• CDN: Cache static autocomplete assets globally to reduce latency.
• Asynchronous Updates: Update autocomplete indexes asynchronously to avoid blocking queries.

Back-of-Envelope Cost Analysis

At 10,000 users with 5,000 QPS, assuming each autocomplete request is ~1 KB, bandwidth needed is ~5 MB/s. A Redis instance can handle ~100K ops/sec, so a few Redis nodes suffice. Database must handle 5K QPS; multiple read replicas needed. Storage for millions of keywords and user data can be tens of GBs. Network and CPU scale with request volume.

Interview Tip

Start by clarifying scale and latency needs. Identify bottlenecks step-by-step: database, cache, network. Propose solutions matching bottlenecks: caching for read-heavy, sharding for data size, horizontal scaling for concurrency. Discuss trade-offs and monitoring strategies.

Self Check Question

Your database handles 1000 QPS. Traffic grows 10x to 10,000 QPS. What do you do first?

Answer: Add read replicas to distribute read queries and reduce load on the primary database. Also, implement caching for popular autocomplete results to reduce database hits.

Key Result

The database is the first bottleneck as user requests grow; adding read replicas and caching are the primary scaling steps before moving to sharding and global distribution.

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