Bird
Raised Fist0

Design a Typeahead Suggestion System - Trie at Scale, Ranking, Personalization, Cache

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design a Typeahead Suggestion System - Trie at Scale, Ranking, Personalization, Cache
Design a scalable, low-latency typeahead system with trie-based indexing, personalized ranking, and caching
mediumSearch and DiscoveryFreq: high
Prerequisites:Inverted IndexElasticsearch
⚙️
Functional Requirements
  • Provide real-time typeahead suggestions as users type each character
  • Support prefix-based search using a trie data structure for fast lookup
  • Rank suggestions based on global popularity and personalized user preferences
  • Update suggestions dynamically as new data arrives (near real-time indexing)
  • Support multi-language and typo-tolerant suggestions
  • Expose APIs for querying suggestions with low latency (<100ms P99)
📊
Non-Functional Requirements
  • Support 2 billion daily active users (DAU)
  • Handle peak QPS of ~1 million read requests per second for suggestions
  • Ensure 99.99% system availability with automatic failover
  • Maintain 100ms P99 latency for suggestion queries
  • Data freshness within 1 minute for new or updated suggestions
❓
Clarifying Questions to Ask
  • What is the expected maximum length of the input prefix for suggestions?
  • How frequently do new suggestions or updates arrive in the system?
  • What personalization signals are available (e.g., user history, location)?
  • Are suggestions limited to a fixed dictionary or dynamically generated?
  • What is the SLA for data freshness after updates?
  • Should the system support multi-language or typo tolerance?
Out of Scope
✗ Full-text search beyond prefix matching (e.g., semantic search)
✗ Complex natural language understanding or intent detection
✗ Offline batch analytics or long-term trend analysis
✗ User authentication and authorization
📌
Assumptions
  • 2 billion DAU
  • Each user types on average 40 characters per day triggering suggestions
  • Average suggestion query/request size is 100 bytes
  • Retention period for logs and data is 30 days
⚡
QPS Calculation
write qps2B users × 40 queries/day ÷ 86400 seconds ≈ 925,926 writes/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2.78M writes/sec
read qpsAssuming 5× read-to-write ratio: 925,926 × 5 ≈ 4.63M reads/sec
💾
Storage Estimate
daily storage925,926 writes/sec × 100 bytes × 86400 sec ≈ 8 TB/day
retention storage8 TB/day × 30 days = 240 TB
with replication240 TB × 3 replicas = 720 TB total storage
🖥️
Server Estimate
write nodesAssuming each write node handles 10K writes/sec → 2.78M / 10K = 278 nodes
read nodesAssuming each read node handles 100K reads/sec → 4.63M / 100K = 47 nodes
🏗️
Architecture Diagram
Architecture Diagram
User
  |
  v
API Gateway
  |
  v
Load Balancer
  |
  +----------------------+
  |                      |
Read Service          Write Service
  |                      |
  v                      v
Redis Cache           Kafka Cluster
  |                      |
  v                      v
Trie Index Shards    Indexing Workers
  |                      |
  v                      v
Personalization DB   Suggestion DB (Elasticsearch)
  |                      |
  +----------+-----------+
             |
             v
Ranking Service
             |
             v
Response to User
🧩
Components
API Gateway
Entry point for all user requests, handles authentication, rate limiting, and routing
Why thisEnvoy proxy supports high throughput, low latency, dynamic routing, and service discovery for microservices
Why notNginx lacks native service discovery and dynamic routing capabilities needed at this scale
Kafka Cluster
Durable, scalable message queue for write requests and indexing events
Why thisKafka supports high throughput (millions of writes/sec), partitioning, and fault tolerance
Why notRabbitMQ cannot handle sustained millions of writes/sec and lacks partitioning at scale
Trie Index Shards
Store prefix-based trie data structure sharded by prefix ranges for fast lookup
Why thisCustom trie implementation optimized for prefix search with low memory footprint and fast traversal
Why notElasticsearch inverted index is slower for prefix queries and uses more memory compared to trie structures
Redis Cache
Cache top suggestions per prefix with TTL for sub-100ms P99 latency
Why thisRedis supports sub-millisecond lookups, TTL expiration, and high QPS caching
Why notMemcached lacks native TTL support and is less flexible for complex caching patterns
Personalization DB
Store user-specific signals and preferences for personalized ranking
Why thisCassandra provides scalable, low-latency writes and reads with tunable consistency
Why notPostgreSQL requires complex manual sharding and does not scale linearly at 925K writes/sec
Suggestion DB (Elasticsearch)
Store global suggestion metadata and support full-text search fallback
Why thisElasticsearch supports inverted index, near real-time updates, and multi-language support
Why notSolr has higher latency and less flexible cloud-native scaling compared to Elasticsearch
Ranking Service
Combine global popularity and personalization signals to rank suggestions
Why thisStateless microservice allows A/B testing and easy model updates without downtime
Why notEmbedding ranking logic in DB queries limits flexibility and slows iteration
Indexing Workers
Consume Kafka events to update trie shards and Elasticsearch indices asynchronously
Why thisAllows decoupling of write path and indexing for high throughput and eventual consistency
Why notSynchronous indexing blocks writes and increases latency beyond SLA
🔄
Data Flow
1
User → API Gateway
User types prefix, API Gateway receives suggestion query
Handles authentication, rate limiting
2
API Gateway → Redis Cache
Check cache for prefix suggestions
Sub-millisecond lookup to reduce load downstream
3
Redis Cache → Ranking Service
If cache miss, query trie shards and personalization DB
Combine global and personalized suggestions
4
Ranking Service → API Gateway
Return ranked suggestions to user
Ensure response within 100ms P99 latency

Practice

(1/5)
1. A distributed key-value store must remain operational during network partitions but can tolerate stale reads temporarily. Which system design choice best supports this requirement?
easy
A. Use a CP system that blocks writes during partitions to maintain consistency
B. Use a CA system that rejects requests during partitions to maintain availability and consistency
C. Use a synchronous replication system that waits for all replicas before responding
D. Use an AP system that serves reads and writes with eventual consistency during partitions

Solution

  1. Step 1: Identify CAP constraints

    During network partitions, a system must choose between consistency and availability.

  2. Step 2: Match system behavior

    AP systems prioritize availability and partition tolerance, allowing stale reads but remaining operational.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    AP systems allow availability during partitions with eventual consistency [check]
Hint: AP favors availability over consistency during partitions [check]
Common Mistakes:
2. In the request flow of the leaderboard system, at step 4 the Ranking Worker reads the updated score from Redis Sorted Sets. What state does the Ranking Worker observe if the score update was just written but the TTL expired simultaneously?
easy
A. The Ranking Worker sees no score entry because TTL expired and removed it
B. The Ranking Worker sees a partial score update causing inconsistent rank
C. The Ranking Worker sees the old score because Redis delays TTL eviction
D. The Ranking Worker blocks until Redis confirms the score is present

Solution

  1. Step 1: Understand Redis TTL eviction behavior

    Redis removes keys immediately after TTL expiration, so if TTL expired, the score entry is deleted.

  2. Step 2: Trace Ranking Worker read at step 4

    Ranking Worker reads Redis Sorted Set; if key expired, it finds no entry, not stale or partial data.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Redis TTL expiry deletes keys before read, so no score entry found [check]
Hint: TTL expiry deletes keys before reads, no stale data returned [check]
Common Mistakes:
3. For a high-throughput system where write latency must be minimized and occasional stale reads are acceptable, which caching pattern is the best choice?
medium
A. Write-Behind, to buffer writes and asynchronously update the database
B. Cache Aside, to update cache only on misses and write directly to the database
C. Write-Through, to ensure cache and database are always consistent synchronously
D. Read-Through, to load cache on reads and write directly to the database

Solution

  1. Step 1: Analyze write latency and consistency needs

    Write-Behind buffers writes, reducing write latency but allowing stale reads.

  2. Step 2: Eliminate other options

    Write-Through adds synchronous latency; Cache Aside and Read-Through write directly to DB, no buffering.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Write-Behind buffers writes for low latency, tolerates stale reads [check]
Hint: Write-Behind buffers writes, reduces latency, allows stale reads [check]
Common Mistakes:
4. You need to design an Elasticsearch cluster optimized for low-latency search queries on a read-heavy workload with occasional node failures. Which architecture choice best balances query speed and fault tolerance?
medium
A. Use multiple smaller primary shards with replica shards distributed across nodes
B. Use only replica shards for queries and keep primary shards offline
C. Disable replicas to reduce write overhead and rely on snapshot backups
D. Use a single large shard per index to minimize cross-shard coordination

Solution

  1. Step 1: Evaluate shard size and replication

    Multiple smaller shards allow parallel query execution; replicas provide fault tolerance and load balancing.

  2. Step 2: Eliminate other options

    Single large shard causes query bottleneck; disabling replicas risks data loss and no failover; using only replicas offline is invalid as primaries handle writes.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Multiple shards + replicas balance speed and fault tolerance [check]
Hint: Multiple shards + replicas optimize read speed and fault tolerance [check]
Common Mistakes:
5. At 10x scale, which observability component is most likely to fail first and why?
hard
A. Centralized logging storage, because write throughput and storage costs grow linearly and cause bottlenecks
B. Alerting system, because it cannot process all incoming alerts in real-time at high scale
C. Distributed tracing backend, because the volume of spans grows exponentially with request fan-out, overwhelming storage and query systems
D. Metrics aggregation system, because it cannot shard time-series data effectively across many nodes

Solution

  1. Step 1: Analyze scaling characteristics of observability components

    Tracing volume grows exponentially with request fan-out, causing storage and query bottlenecks.

  2. Step 2: Compare with other components

    Logging scales linearly; metrics systems shard well; alerting scales with metrics, so less likely first failure.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Tracing volume explosion -> backend overwhelmed first [check]
Hint: Tracing volume explodes with fan-out, stressing backend first [check]
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