Search autocomplete (typeahead) ডিজাইন
টাইপ করতে করতেই search box মিলিসেকেন্ডে সম্পূর্ণ করার প্রস্তাব দেয়। data structure, ranking ও আপডেট pipeline ডিজাইন করি।
লক্ষ্য: user prefix টাইপ করলে প্রায় ১০০ ms-এর মধ্যে সেরা suggestion (যেমন ৫-১০টি) ফেরত দেওয়া।
Requirement
- টাইপ করা prefix-এর জন্য ranked suggestion (সাধারণত জনপ্রিয়তা অনুযায়ী)।
- খুব কম latency, কারণ প্রায় প্রতিটি কী-স্ট্রোকে চলে।
- Search-এর ট্রেন্ড বদলালে suggestion বদলাবে, তবে তাৎক্ষণিক নয়।
অনুমান
১ কোটি user প্রত্যেকে দিনে ১০টি search করে, আর প্রতিটি search-এ প্রায় ৫টি request হলে দিনে ৫০ কোটি request, প্রায় ৬,০০০ request/s, peak-এ কয়েক গুণ। Read-ই প্রধান, আর data (জনপ্রিয় query) পুরো ওয়েবের চেয়ে অনেক ছোট।
Data structure: trie
Trie (prefix tree) query-কে অক্ষর ধরে ধরে রাখে। প্রতিটি node একটি prefix। "pay"-এর suggestion পেতে সেই node-এ গিয়ে নিচের সেরা completion পড়ুন।
Query-র সময় subtree হাঁটা ধীর, তাই প্রতিটি node নিজের top-K completion রাখে (আগে হিসাব করা, score সহ)। Lookup হয়: prefix অনুসরণ করুন, রাখা তালিকা ফেরত দিন। দ্রুত, তবে বেশি memory লাগে।
বিকল্প: key-value store-এ prefix index (key = prefix, value = সেরা suggestion) বা search engine-এর edge n-gram index।
Ranking
Query-র frequency, সাম্প্রতিকতা (trending boost) এবং অনুমতি থাকলে personalisation ও অবস্থান দিয়ে সাজান। আপত্তিকর, অবৈধ বা অনিরাপদ suggestion blocklist দিয়ে বাদ দিন।
Data তৈরি
Suggestion আসে search log থেকে:
- Query stream-এ log করা।
- Batch (বা streaming) job প্রতি সময়কালে (প্রায়ই ঘণ্টা বা দিন) query-অনুযায়ী গণনা aggregate করে।
- সেরা query থেকে নতুন trie বা prefix table বানানো।
- নতুন সংস্করণ বদলে serving node-এ deploy।
প্রতিটি query-র real-time আপডেট দরকার নেই; নিয়মিত পুনর্নির্মাণ ও আকস্মিক ট্রেন্ডের জন্য দ্রুত পথই যথেষ্ট।
কম latency-তে সার্ভ
- Suggestion server-এ structure memory-তে রাখুন।
- জনপ্রিয় prefix-এর ফল (এমনকি "a" বা "how"-এর মতো ছোটগুলোও) Redis বা CDN-এ cache করুন।
- Browser-এ: কী-স্ট্রোক debounce (প্রায় ১০০-২০০ ms অপেক্ষা), পুরোনো request বাতিল এবং আগের ফল cache।
- ১-২ অক্ষরের পর থেকে suggest শুরু করুন।
Scaling
Structure অনেক server-এ replicate করুন। এক মেশিনে না ধরলে prefix পরিসর দিয়ে shard করুন (a-g, h-n...), কিছু prefix গরম বলে load সামঞ্জস্য রাখুন।
অন্যান্য বিষয়
বানান ভুল (fuzzy matching), বহুভাষিক input (বাংলা ও ইংরেজি), এবং গোপনীয়তা: একজন user-এর private query অন্যদের কাছে suggest করবেন না।
মূল কথা: query log থেকে বানানো, আগে হিসাব করা top-K trie বা prefix table memory-তে, ভারীভাবে cache করা, আর client-এ debounce।
System Design সিরিজ, পর্ব ৩ (case study): 9 নম্বর (মোট 16)। আগের লেখা: Notification সিস্টেম ডিজাইন: push, SMS ও email.
