Bird
Raised Fist0

Typeahead Autocomplete - Trie vs Prefix Hash vs Elasticsearch

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
🏗️
Typeahead Autocomplete - Trie vs Prefix Hash vs Elasticsearch
Designing a scalable typeahead autocomplete system comparing Trie, Prefix Hash, and Elasticsearch approaches
mediumSearch and IndexingFreq: common
Prerequisites:Inverted IndexElasticsearch
⚙️
Functional Requirements
  • Provide real-time autocomplete suggestions as users type prefixes
  • Support prefix search with low latency (sub-100ms P99) for top-k suggestions
  • Update autocomplete index with new entries and deletions in near real-time
  • Rank suggestions by popularity or relevance
  • Support multi-language and Unicode characters
  • Handle typo tolerance or fuzzy matching (optional enhancement)
📊
Non-Functional Requirements
  • Support 2 billion daily active users (DAU)
  • Handle peak write QPS of ~1 million updates per second
  • Serve read QPS of ~10 million autocomplete queries per second
  • Ensure 99.99% availability with 100ms P99 latency on autocomplete queries
  • Index size growth capped to petabyte scale with efficient storage
❓
Clarifying Questions to Ask
  • What is the expected average and peak QPS for autocomplete queries and index updates?
  • What is the maximum acceptable latency for autocomplete suggestions (P99)?
  • How frequently does the autocomplete index update with new entries or deletions?
  • Are typo tolerance and fuzzy matching required or optional?
  • What languages and character sets must be supported?
  • Is ranking based on static popularity or dynamic user behavior?
Out of Scope
✗ Full-text search beyond prefix matching
✗ Complex natural language understanding or semantic search
✗ User personalization or session-based ranking
✗ Offline batch analytics or reporting
📌
Assumptions
  • 2 billion DAU
  • Each user performs 20 autocomplete queries per day on average
  • Each autocomplete query returns top 10 suggestions
  • Each suggestion entry is approximately 100 bytes
  • Index updates occur at 5% of query volume (1 update per 20 queries)
⚡
QPS Calculation
read qps2B × 20 / 86400 ≈ 462,963 queries/sec
write qps462,963 × 0.05 ≈ 23,148 updates/sec
peak write qpsAssuming 5× peak factor: 23,148 × 5 = 115,740 updates/sec
💾
Storage Estimate
daily index size462,963 queries × 10 suggestions × 100 bytes ≈ 462.96 MB/day
daily update size115,740 updates × 100 bytes ≈ 11.57 MB/day
retention days30
total storage(462.96 + 11.57) MB × 30 days ≈ 14.3 GB
with replication14.3 GB × 3 replicas ≈ 42.9 GB total
🖥️
Server Estimate
indexing serversAssuming 1 server handles 5,000 updates/sec, need 115,740 / 5,000 ≈ 24 servers
query serversAssuming 1 server handles 10,000 queries/sec, need 462,963 / 10,000 ≈ 47 servers
🏗️
Architecture Diagram
Architecture Diagram
User
  |
  v
Load Balancer
  |
  v
Query API Servers
  |
  +----------+
  |          |
  v          v
Autocomplete Index Store
Update Processor
  |          |
  v          v
Elasticsearch Cluster / Trie Store / Prefix Hash Store
  |
  v
Ranking Service (optional)
  |
  v
Response to User
🧩
Components
Load Balancer
Distributes incoming autocomplete queries evenly across query API servers
Why thisUse AWS ELB or NGINX for proven high throughput and low latency load balancing
Why notDNS round-robin lacks health checks and fine-grained load distribution
Query API Servers
Handle autocomplete query requests, fetch suggestions from index, and return results
Why thisStateless REST/gRPC servers scale horizontally and cache hot prefixes locally
Why notMonolithic servers limit horizontal scaling and increase latency under load
Autocomplete Index Store
Stores prefix-to-suggestions mappings; supports fast prefix search and updates
Why thisElasticsearch provides inverted index with prefix search, scalability, and built-in ranking
Why notTrie requires large memory and complex sharding; Prefix Hash lacks fuzzy search and ranking
Update Processor
Processes incoming index updates asynchronously and applies them to the index store
Why thisKafka streams with consumer groups ensure ordered, scalable, and fault-tolerant updates
Why notDirect synchronous writes cause high latency and reduce availability
Ranking Service
Ranks autocomplete suggestions by popularity or relevance before returning to users
Why thisDedicated microservice allows flexible ranking algorithms and offline model updates
Why notEmbedding ranking logic inside index store limits flexibility and increases complexity
🔄
Data Flow
1
User → Load Balancer
Send autocomplete query with prefix
Load balancer evenly distributes queries to API servers
2
Load Balancer → Query API Servers
Forward query request
API servers handle query logic and caching
3
Query API Servers → Autocomplete Index Store
Fetch prefix matches
Use Elasticsearch prefix query or Trie traversal
4
Autocomplete Index Store → Ranking Service
Send raw suggestions for ranking
Ranking service applies popularity or relevance scores
5
Ranking Service → Query API Servers
Return ranked suggestions
API servers prepare final response
6
Query API Servers → User
Send autocomplete suggestions
Response latency must meet 100ms P99
7
Update Processor → Autocomplete Index Store
Apply incremental index updates
Updates processed asynchronously to avoid query latency impact
8
Data Sources → Update Processor
Send new entries and deletions
Update processor ingests changes from upstream systems

Practice

(1/5)
1. In a gRPC streaming call, at step 4 the server-side stream handler checks the client connection status before sending a message. What happens if the client has disconnected at this step?
easy
A. The server immediately cancels the stream and releases resources
B. The server buffers the message indefinitely until the client reconnects
C. The server retries sending the message up to 3 times before dropping it
D. The server switches to unary RPC mode to deliver the message

Solution

  1. Step 1: Understand server stream handler behavior

    When client disconnects, server detects cancellation via context and stops streaming.
  2. Step 2: Trace server reaction at step 4

    Server cancels the stream and frees resources immediately; it does not buffer or retry indefinitely.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Client disconnect -> server cancels stream and frees resources [check]
Hint: Disconnected client -> server cancels stream immediately [check]
Common Mistakes:
2. In a server-side service discovery flow, at step 4 the API Gateway queries the service registry for available instances. What happens if the registry returns stale data at this step?
easy
A. The API Gateway routes requests to possibly unavailable instances causing failures
B. The API Gateway caches the stale data but marks instances as unhealthy
C. The API Gateway falls back to client-side discovery automatically
D. The API Gateway retries the request until fresh data is received

Solution

  1. Step 1: Trace API Gateway behavior at step 4

    The API Gateway relies on the registry response to route requests; stale data leads to routing to unavailable instances.
  2. Step 2: Eliminate other options

    The API Gateway retries the request until fresh data is received is incorrect as retries are not automatic; The API Gateway falls back to client-side discovery automatically is false since fallback is not built-in; The API Gateway caches the stale data but marks instances as unhealthy is incorrect because caching stale data without health checks causes failures.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    API Gateway routes based on stale registry data causing failures [check]
Hint: Stale registry data routes to dead instances causing failures [OK]
Common Mistakes:
3. If the Road Graph Service's update pipeline fails to process live traffic changes, what is the exact failure observed in ETA computation?
medium
A. ETA computations continue using outdated traffic data, causing inaccurate arrival times
B. Users receive error messages indicating routing data is unavailable
C. Routing Engine crashes due to missing graph updates, causing system downtime
D. The system automatically switches to a backup graph with no traffic data, causing longer routes

Solution

  1. Step 1: Understand Road Graph update pipeline failure impact

    Without updates, live traffic data is stale; system must handle this gracefully.
  2. Step 2: Trace failure effect on ETA computation

    Routing Engine does not silently use stale data (A) or crash (B); it returns errors (C) to avoid misleading ETAs; no automatic backup switch (D).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Update pipeline failure causes routing errors, not silent stale data use [check]
Hint: Update failure triggers routing errors, not silent stale data use [check]
Common Mistakes:
4. At 10x scale, which Kafka component is most lik
medium
A. Broker
B. Consumer
C. Producer
D. Zookeeper

Solution

  1. Step 1: Identify scaling bottleneck

    Consumers handle message processing and scale with load.
  2. Step 2: Assess component impact

    At 10x scale, consumers need to scale out to handle increased throughput.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Consumers scale with load; brokers and producers less impacted [check]
Hint: Consumers scale most at high load [OK]
Common Mistakes:
5. Without a latency percentile monitoring system, what exactly breaks in detecting performance issues in a distributed service?
medium
A. The system can't detect any latency issues, so all requests appear fast.
B. Slow requests in the tail go unnoticed, causing user experience degradation without alerts.
C. The system misclassifies failed requests as slow requests.
D. Average latency spikes cause false alarms, overwhelming the ops team.

Solution

  1. Step 1: Role of latency percentile monitoring

    Latency percentiles detect tail latency spikes that average latency misses, enabling targeted alerts.
  2. Step 2: Failure without percentile monitoring

    Without it, only average latency is visible, which can spike due to outliers or noise, causing false alarms and missing tail issues.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Without percentiles, average latency spikes cause false alarms [check]
Hint: No percentiles -> false alarms from average spikes [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard