Search Autocomplete (Typeahead) ডিজাইন

তুমি Google search box-এ "ঢা" লিখতেই "ঢাকা আবহাওয়া", "ঢাকা টু চট্টগ্রাম ট্রেন" ভেসে ওঠে—মিলিসেকেন্ডের মধ্যে। এই typeahead বা autocomplete feature দেখতে সহজ, কিন্তু কোটি কোটি query-র মধ্যে সঠিকটা এত দ্রুত আনা একটা মজার system design সমস্যা। চলো ইন্টারভিউ-এর কাঠামোয় এটা সমাধান করি।

১. সমস্যা বোঝা (Requirements)

Functional requirements:

• ব্যবহারকারী prefix টাইপ করলে top suggestion দেখানো (সাধারণত ৫-১০টা)।
• Suggestion popularity দিয়ে সাজানো—যা বেশি মানুষ খোঁজে তা উপরে।
• নতুন জনপ্রিয় query সময়ের সাথে suggestion-এ যোগ হবে (যেমন breaking news)।

Non-functional requirements:

• অতি কম latency: প্রতিটি keystroke-এ ১০০ ms-এর কম সময়ে উত্তর। এটাই সবচেয়ে কঠিন শর্ত।
• High availability: search box কখনো ফাঁকা থাকা যাবে না।
• Scalability: কোটি কোটি query, লক্ষাধিক QPS।
• Eventual freshness: suggestion সাথে সাথে নয়, কয়েক ঘণ্টায় আপডেট হলেই চলে।

লক্ষ করো এখানে আমরা latency-র জন্য freshness ছেড়ে দিচ্ছি—suggestion ১ ঘণ্টা পুরোনো হলেও সমস্যা নেই, কিন্তু ধীর হলে সমস্যা।

২. স্কেল আন্দাজ (Estimation)

দৈনিক search query   = 100 কোটি (10 億 / 1,000,000,000)
প্রতি search-এ গড়ে keystroke = 4টি (4টি autocomplete request)
মোট autocomplete request/দিন = 4 × 10^9 = 400 কোটি

QPS (গড়)  = 4,000,000,000 / 86,400 ≈ 46,000/sec
QPS (peak) = ~3x ≈ 138,000/sec   ← খুব বেশি!

Unique query (suggestion candidate):
  ধরা যাক ~10 কোটি unique query
  প্রতি query গড়ে 20 bytes + count
  raw ≈ 2 GB → Trie-তে আরও বেশি, কিন্তু একটা machine-এ আঁটানো সম্ভব (বা shard)

Debounce-এর প্রভাব:
  client 200ms debounce দিলে 4 → ~2 request/search
  → QPS অর্ধেক হয়ে যায়! তাই client optimization বিশাল।

মূল কথা: এটা প্রচণ্ড read-heavy, write খুব কম (suggestion দিনে কয়েকবার আপডেট হয়)। তাই আমরা সব কিছু read-এর জন্য অপ্টিমাইজ করব।

৩. API ডিজাইন

GET /v1/autocomplete?q=ঢা&limit=10
  → {
      "suggestions": [
        { "text": "ঢাকা আবহাওয়া",       "score": 98000 },
        { "text": "ঢাকা টু চট্টগ্রাম ট্রেন", "score": 75000 }
      ]
    }

API-টা ইচ্ছাকৃতভাবে অত্যন্ত সরল—একটাই GET endpoint, যাতে aggressively cache করা যায় (CDN পর্যন্ত)। এর পেছনে background-এ থাকে suggestion আপডেট করার আলাদা pipeline।

৪. ডেটা মডেল

Storage	প্রধান field	কাজ
Trie (in-memory)	prefix node → top-K list	দ্রুত prefix lookup ও suggestion
query_logs	query_text, timestamp, user_region	কাঁচা search log
query_counts	query_text, count, last_updated	aggregated popularity

SQL নাকি NoSQL? আসল serving-এর জন্য কোনোটাই নয়—in-memory Trie ব্যবহার হয়, কারণ disk DB ১০০ ms-এর কমে দিতে পারবে না। তবে background pipeline-এ:

• query_logs → বিশাল append-only data, তাই NoSQL / data lake (যেমন S3 + Spark)।
• query_counts → aggregation result, key-value store (Redis/Cassandra)-এ রাখা সুবিধাজনক, পরে এ থেকে Trie বানানো হয়।

আসল lookup memory থেকে হয় বলেই autocomplete এত দ্রুত।

৫. হাই-লেভেল ডিজাইন

মূল components দুটো ভাগে:

A) Serving path (read, fast):

1. Client — debounce করে request পাঠায়।
2. CDN / Cache — জনপ্রিয় prefix-এর উত্তর edge-এ cache।
3. Autocomplete service — in-memory Trie থেকে suggestion দেয়।

B) Update path (write, slow, background): 4. Logging — প্রতিটি সম্পন্ন search log হয়। 5. Aggregator (Spark/MapReduce) — log থেকে query count বের করে। 6. Trie builder — count থেকে নতুন Trie বানিয়ে serving server-এ deploy করে।

Request flow ধাপে ধাপে:

1. User "ঢা" টাইপ করে; client debounce করে (টাইপ থামার ২০০ ms পর) request পাঠায়।
2. CDN/cache-এ "ঢা"-র উত্তর থাকলে সাথে সাথে ফেরত।
3. না থাকলে autocomplete service Trie-তে "ঢা" node খুঁজে তার precomputed top-K list ফেরত দেয়।
4. আলাদাভাবে, সম্পন্ন search query log হয়; প্রতি কয়েক ঘণ্টায় aggregator count আপডেট করে নতুন Trie বানায়।

৬. গভীরে (Deep Dive)

Top-K precomputation

শুধু Trie থাকলে প্রতিবার "ঢা" node-এর নিচের হাজারো শব্দ ঘুরে top-10 বের করতে হতো—ধীর। তাই আমরা প্রতিটি node-এ ওই prefix-এর Top-K suggestion আগেই হিসাব করে cache করে রাখি। Top-K মানে সবচেয়ে জনপ্রিয় K-টি (যেমন ১০টি) ফলাফল।

ফলে query-time-এ শুধু prefix-এর শেষ node খুঁজে তার stored list সরাসরি ফেরত দিই—O(prefix length), node-এর নিচে কত শব্দ তাতে কিছু যায় আসে না। এটাই autocomplete-এর গতির মূল রহস্য।

Popularity-ভিত্তিক ranking ও log থেকে আপডেট

কোন suggestion উপরে থাকবে তা ঠিক হয় count (কতবার খোঁজা হয়েছে) দিয়ে। কিন্তু কাঁচা count যথেষ্ট নয়—কালকের viral query আজও উপরে থাকলে পুরোনো লাগে। তাই time-decay যোগ করি: পুরোনো count-এর ওজন কমে, সাম্প্রতিক বেশি।

আপডেট pipeline: প্রতিটি search log → কয়েক ঘণ্টা পর পর Spark job count aggregate করে → নতুন count দিয়ে Trie পুনর্নির্মাণ → atomically swap করে নতুন Trie চালু। যেহেতু freshness requirement শিথিল, এই batch approach যথেষ্ট।

Sharding the Trie

পুরো Trie যদি একটা machine-এ না আঁটে, বা QPS এক machine সামলাতে না পারে, তাহলে shard করি। সহজ উপায়: prefix range দিয়ে sharding—যেমন "অ–ক" এক server-এ, "খ–চ" আরেকটায়। একটা lightweight router request-কে সঠিক shard-এ পাঠায়। তবে অজনপ্রিয় ও জনপ্রিয় অক্ষর সমানভাবে ভাগ না হওয়ায় load uneven হতে পারে—তাই popularity দেখে shard balance করা ভালো।

৭. বটলনেক ও স্কেলিং

• বিশাল read QPS: CDN + edge cache-এ জনপ্রিয় prefix রাখলে বেশিরভাগ request server পর্যন্ত আসেই না। জনপ্রিয় prefix সংখ্যায় কম, তাই cache hit rate অনেক বেশি।
• Client debounce + caching: প্রতি keystroke-এ নয়, থেমে request—QPS অর্ধেক বা তারও কম।
• Memory: Trie বড় হলে shard, আর কম-জনপ্রিয় শব্দ ছেঁটে (pruning) আকার কমানো।
• Hot shard: জনপ্রিয় অক্ষরের shard-এ বেশি replica রাখো।
• Freshness vs cost: খুব দ্রুত আপডেট চাইলে খরচ বাড়ে; এখানে eventual freshness যথেষ্ট বলে batch pipeline সস্তা ও সরল।

৮. সারসংক্ষেপ

আমরা একটা autocomplete system বানালাম যেখানে—in-memory Trie-র প্রতিটি node-এ precomputed top-K suggestion রাখা, popularity (time-decay সহ) দিয়ে ranking, client-side debounce আর CDN cache দিয়ে read চাপ কমানো, এবং search log থেকে batch pipeline-এ Trie রিবিল্ড করে atomic swap। read-heavy বলে সব কিছু read-এর জন্য অপ্টিমাইজড।