Thiết kế Search Autocomplete (Typeahead Suggestions). Tối ưu latency và ranking? (Design a Search Autocomplete / Typeahead system. How to optimize latency and ranking?)

Requirements: suggest top-K queries khi user gõ, latency < 100ms, millions of users.

• Data collection: log tất cả search queries; aggregation job (Hadoop/Spark) chạy weekly/daily để tính frequency của mỗi query (hay trending score).
• Trie (Prefix Tree): data structure lý tưởng cho prefix matching – mỗi node đại diện một ký tự, lưu top-K queries tại mỗi node. Query time: traverse trie theo prefix → O(prefix_length).
• Trie storage: serialized trie lưu trong distributed cache (Redis).
• Caching: top-20% prefixes chiếm ~80% traffic → cache aggressively; prefix cache với TTL 24h; browser cache ở client để giảm requests.
• Ranking factors: frequency, freshness (trending queries), personalization (user's search history).
• Trie update: không update real-time (expensive); rebuild offline và swap atomically.
• Scale: shard trie theo first character (26 shards); consistent hashing để route request đến đúng shard.

Filter: cần filter offensive/spam queries trước khi hiển thị. API: GET /autocomplete?q={prefix}&limit=10 → cần < 50ms để UX tốt.