Search — inverted index, ranking, autocomplete আর search cluster

১ · LIKE '%x%' কেন যথেষ্ট নয় — search engine কী যোগ করে

একটি কাল্পনিক অনলাইন বাজারে ২০ লাখ পণ্য। একজন ক্রেতা সার্চ বক্সে লিখলেন “আম”. সবচেয়ে সরল উপায় SQL-এ WHERE title LIKE '%আম%'. তিনটি সমস্যা:

• ধীর: শুরুতে % থাকলে B-tree index-এর সাজানো ক্রম কাজে লাগে না (পর্ব ২১), তাই প্রতিটি খোঁজে সব সারির পুরো লেখা পড়তে হয়। ২০ লাখ পণ্য × গড়ে ৬০ অক্ষর = প্রতি খোঁজে ১২ কোটি অক্ষর।
• ভুল মিল: “আম” অক্ষর দুটি “আমদানি” আর “আমার”-এর ভেতরেও আছে। LIKE অক্ষর মেলায়, শব্দ নয়।
• ক্রম, ভুল বানান আর ভাগ নেই: কোন পণ্য বেশি মানানসই LIKE জানে না। “রাজশাহি” লিখলে “রাজশাহী” আসে না। আর ফলের পাশে “ফজলি (১২০) · ল্যাংড়া (৮৫)”-এর মতো গোনা দেখানোও তার কাজ নয়।

এই খোপের ব্যবস্থাকে বলে inverted index. এর ওপর একটি search index আরও কয়েকটি জিনিস যোগ করে:

২ · Inverted index — tokenization, normalization আর বাংলা লেখা

Index-এ ঢোকার আগে প্রতিটি লেখা একটি analyzer-এর ভেতর দিয়ে যায়। খোঁজার শব্দও হুবহু একই analyzer-এ যায় — নইলে দুই দিকের term মিলবে না।

• Tokenization: ফাঁকা জায়গা আর যতিচিহ্নে লেখা ভাঙা। বাংলার দাঁড়ি “।”-কেও যতিচিহ্ন ধরতে হয়, নইলে “টিকিট।” একটি আলাদা শব্দ হয়ে যায়।
• Normalization: একই জিনিসকে এক রূপে আনা — ছোট হাতের অক্ষর, accent বাদ (café → cafe), Unicode-এর একটি নির্দিষ্ট রূপ।
• Stop word: “আর”, “ও”, the, of-এর মতো প্রায় সব ডকুমেন্টে থাকা শব্দ বাদ। Phrase query-তে এগুলো লাগতে পারে, তাই অনেক ব্যবস্থা রেখে দিয়ে কম ওজন দেয়।
• Stemming বনাম lemmatization: stemming নিয়ম ধরে শেষাংশ কাটে (ইংরেজিতে Porter-এর ১৯৮০ সালের stemmer সবচেয়ে পরিচিত); lemmatization অভিধান দেখে মূল রূপ খোঁজে (গেলাম, যাবে → যাওয়া)। Stemming সস্তা কিন্তু ভুল করে: খেলনা নিয়মে “-কে” কাটলে “থেকে” হয়ে যেত “থে” — over-stemming.

বাংলা লেখার বিশেষ চ্যালেঞ্জ

Index-এর প্রতিটি term-এর তালিকাকে বলে posting list: term → [(docId, tf, [positions])]. DocId-গুলো ছোট থেকে বড় সাজানো থাকে, তাই সংখ্যার বদলে পার্থক্য রাখা যায় — [3, 7, 21, 22] হয়ে যায় [3, 4, 14, 1] (delta encoding), আর ছোট সংখ্যা প্রায়ই ১ byte-এই ধরে। Term-গুলো নিজেরাও একটি সাজানো অভিধানে থাকে, যাতে একটি term দ্রুত খুঁজে পাওয়া যায়।

এবার আটটি কাল্পনিক পোস্টে একটি ছোট index: বেশিরভাগ বাংলা, একটি ইংরেজি, একটি Banglish. Analyzer ইচ্ছা করে খেলনা: NFC, ছোট হাতের অক্ষর, কয়েকটি stop word, কয়েকটি বিভক্তি কাটা আর ছয় শব্দের প্রতিশব্দ-তালিকা।

// Mini inverted index: 8 short posts (Bangla, English, Banglish), a TOY Bangla-aware analyzer.
const DOCS = ["ঢাকার মেট্রো রেলের টিকিট", "মেট্রো রেল স্টেশনগুলোর তালিকা",
  "Dhaka Metro Rail ticket price", "ঢাকা থেকে চট্টগ্রাম ট্রেনের টিকিট",
  "বাসের টিকিট ট্রেনের টিকিট লঞ্চের টিকিট", "dhaka metro rail er ticket koto",
  "চট্টগ্রামের বাস আর ট্রেনের সময়সূচি", "নতুন মেট্রো স্টেশনে ভিড়"]; // ড় = U+09DC
const STOP = new Set(["আর", "ও", "থেকে", "er", "the", "of"]);
const SYN = { dhaka: "ঢাকা", metro: "মেট্রো", rail: "রেল", ticket: "টিকিট", train: "ট্রেন", bus: "বাস" };
const stem = w => {                             // toy: strip -গুলোর, -গুলো, -দের, -এর, -কে, -র (after া)
  const s = w.replace(/(গুলোর|গুলো|দের|ের|কে)$|(?<=া)র$/u, ""); return s.length >= 2 ? s : w; };
const analyze = text => text.normalize("NFC").toLowerCase().split(/[\s,।?!]+/).filter(Boolean)
  .flatMap((w, pos) => STOP.has(w) ? [] : [[SYN[w] || stem(w), pos]]);   // [term, position]
const index = new Map();                        // term -> [[docId, [positions]], ...]
DOCS.forEach((text, i) => {
  const id = i + 1, mine = new Map();
  for (const [t, pos] of analyze(text)) (mine.get(t) || mine.set(t, []).get(t)).push(pos);
  for (const [t, ps] of mine) (index.get(t) || index.set(t, []).get(t)).push([id, ps]);
});
const ids = q => (index.get(analyze(q)[0]?.[0]) || []).map(p => p[0]);
function and(a, b) { const r = []; let i = 0, j = 0;      // two sorted lists, one pass
  while (i < a.length && j < b.length) a[i] === b[j] ? (r.push(a[i]), i++, j++) : a[i] < b[j] ? i++ : j++;
  return r; }
function or(a, b) { const r = []; let i = 0, j = 0;
  while (i < a.length || j < b.length) { const x = j >= b.length || (i < a.length && a[i] <= b[j]) ? a[i] : b[j];
    if (a[i] === x) i++; if (b[j] === x) j++; r.push(x); } return r; }
console.log("doc 4 ->", analyze(DOCS[3]).map(([t, p]) => t + "@" + p).join(" "));
console.log("doc 6 ->", analyze(DOCS[5]).map(([t, p]) => t + "@" + p).join(" "));
let n = 0; for (const ps of index.values()) n += ps.length;
console.log("terms:", index.size, " postings:", n);
for (const t of ["টিকিট", "মেট্রো"]) console.log(t, "->", index.get(t).map(([d, ps]) => d + ":[" + ps + "]").join(" "));
console.log("মেট্রো AND টিকিট ->", and(ids("মেট্রো"), ids("টিকিট")));
console.log("ট্রেন OR বাস     ->", or(ids("ট্রেন"), ids("বাস")));
console.log("metro AND ticket ->", and(ids("metro"), ids("ticket")));
console.log("স্টেশন ->", ids("স্টেশন"), " ভিড় (ড + nukta) ->", ids("ভিড়"));

doc 4 -> ঢাকা@0 চট্টগ্রাম@2 ট্রেন@3 টিকিট@4
doc 6 -> ঢাকা@0 মেট্রো@1 রেল@2 টিকিট@4 koto@5
terms: 16  postings: 34
টিকিট -> 1:[3] 3:[3] 4:[4] 5:[1,3,5] 6:[4]
মেট্রো -> 1:[1] 2:[0] 3:[1] 6:[1] 8:[1]
মেট্রো AND টিকিট -> [ 1, 3, 6 ]
ট্রেন OR বাস     -> [ 4, 5, 7 ]
metro AND ticket -> [ 1, 3, 6 ]
স্টেশন -> [ 2 ]  ভিড় (ড + nukta) -> [ 8 ]

৩ · Query চালানো — posting list মেলানো আর phrase query

AND মানে দুই তালিকার ছেদ, OR মানে মিলন, NOT মানে বাদ। তালিকাগুলো সাজানো, তাই merge sort-এর merge ধাপের মতো (DSA · merge sort) দুই আঙুলে একবার হাঁটলেই হয়: যেদিকের মান ছোট সেই আঙুল এগোয়, সমান হলে মিল। খরচ O(p₁ + p₂) — তালিকার দৈর্ঘ্য, ডকুমেন্টের মোট লেখা নয়।

কয়েকটি তালিকা হলে কোনটি আগে? সবচেয়ে ছোটটি (সবচেয়ে বিরল term) — ৫০টি entry দিয়ে শুরু করলে মধ্যবর্তী ফল ৫০-এর বেশি হয় না। তালিকা খুব অসমান হলে (৫০ বনাম ৮ লাখ) লম্বাটিতে skip pointer বা লাফিয়ে-খোঁজা (galloping, binary search-এর আত্মীয়): খরচ মোটামুটি O(p_ছোট × log p_বড়)।

Phrase query: “মেট্রো রেল” হুবহু চাইলে আগে AND করে doc বাছা হয়, তারপর position দেখা হয় — রেল-এর অবস্থান = মেট্রো-র অবস্থান + ১ কি না। উপরের index-এ doc 1, 2, 3, 6 — চারটিই মেলে। কিন্তু “রেল টিকিট”-এ doc 6 মেলে না: রেল@2, টিকিট@4, কারণ বাদ যাওয়া “er”-এর অবস্থান রয়ে গেছে। অনেক engine-এ slop দিয়ে বলা যায় “মাঝে একটি ফাঁক চলবে”। দাম: position রাখলে index অনেকটা বড় হয়।

৪ · Ranking — TF-IDF থেকে BM25, আর লেখার বাইরের সংকেত

AND-এ লাখ ডকুমেন্ট মিললে প্রথম পাতায় কোন ১০টি? Relevance ranking-এর দুটি পুরোনো অন্তর্দৃষ্টি: (১) একটি ডকুমেন্টে শব্দটি যত বেশিবার — term frequency, tf — তত প্রাসঙ্গিক; (২) যে শব্দ অল্প ডকুমেন্টে আছে, সে বেশি তথ্য বহন করে — inverse document frequency, IDF. আমাদের সংগ্রহে “টিকিট” ৮টির ৫টিতে, “ট্রেন” ৩টিতে; তাই ট্রেন মিলে যাওয়া বেশি দামি। দুটি মিলিয়ে TF-IDF: score = tf × log(N ÷ df).

সরল TF-IDF-এর দুটি দুর্বলতা। প্রথমত, tf সরলরেখায় বাড়ে: “টিকিট টিকিট টিকিট…” লিখে কেউ ওপরে উঠে যেতে পারে। দ্বিতীয়ত, লম্বা ডকুমেন্টে স্বাভাবিকভাবেই শব্দ বেশিবার আসে। BM25 দুটিই সামলায়:

• N = মোট ডকুমেন্ট, n = যতগুলোতে term-টি আছে, |D| = ডকুমেন্টের দৈর্ঘ্য (term-এর সংখ্যা), avgdl = গড় দৈর্ঘ্য।
• k1 (সাধারণত ১.২ থেকে ২.০): tf-এর সম্পৃক্তি। tf যত বাড়ুক, ভগ্নাংশটি k1 + 1-এর বেশি হয় না — keyword ঠেসে দেওয়ার লাভ সীমিত।
• b (০ থেকে ১, সাধারণত ০.৭৫): দৈর্ঘ্যের শাস্তি। b = ০ হলে দৈর্ঘ্য উপেক্ষা; b = ১ হলে পুরো মাত্রায় দৈর্ঘ্য দিয়ে ভাগ।
• IDF-এর রূপ: মূল Robertson–Spärck Jones রূপ ln((N − n + 0.5) ÷ (n + 0.5)) অর্ধেকের বেশি ডকুমেন্টে থাকা term-এ ঋণাত্মক (N = ৮, n = ৫-এ −০.৪৫২); Lucene-এর মতো engine “1 +” যোগ করে তা ঠেকায়। কিছু implementation লবের (k1 + 1)-ও বাদ দেয় — সবার একই গুণক, ক্রম বদলায় না। সংখ্যা মেলানোর আগে রূপটি দেখে নিন।

নিচের stepper-এ প্রশ্ন “ট্রেন টিকিট”, আর অংশ ২-এর doc 5 — “বাসের টিকিট ট্রেনের টিকিট লঞ্চের টিকিট” — হাতে হিসাব করা হলো:

// BM25 over the same 8 posts and the same toy analyzer. k1 = 1.2, b = 0.75.
const DOCS = ["ঢাকার মেট্রো রেলের টিকিট", "মেট্রো রেল স্টেশনগুলোর তালিকা",
  "Dhaka Metro Rail ticket price", "ঢাকা থেকে চট্টগ্রাম ট্রেনের টিকিট",
  "বাসের টিকিট ট্রেনের টিকিট লঞ্চের টিকিট", "dhaka metro rail er ticket koto",
  "চট্টগ্রামের বাস আর ট্রেনের সময়সূচি", "নতুন মেট্রো স্টেশনে ভিড়"];
const STOP = new Set(["আর", "ও", "থেকে", "er", "the", "of"]);
const SYN = { dhaka: "ঢাকা", metro: "মেট্রো", rail: "রেল", ticket: "টিকিট", train: "ট্রেন", bus: "বাস" };
const stem = w => { const s = w.replace(/(গুলোর|গুলো|দের|ের|কে)$|(?<=া)র$/u, ""); return s.length >= 2 ? s : w; };
const analyze = t => t.normalize("NFC").toLowerCase().split(/[\s,।?!]+/).filter(Boolean)
  .flatMap(w => STOP.has(w) ? [] : [SYN[w] || stem(w)]);
const docs = DOCS.map(analyze), N = docs.length, k1 = 1.2, b = 0.75;
const avgdl = docs.reduce((s, d) => s + d.length, 0) / N;
const df = t => docs.filter(d => d.includes(t)).length;
const idf = t => Math.log(1 + (N - df(t) + 0.5) / (df(t) + 0.5));   // Lucene-style, never negative
function bm25(terms, d) {                            // returns per-term contributions
  const K = k1 * (1 - b + b * d.length / avgdl);
  return terms.map(t => { const tf = d.filter(x => x === t).length; return idf(t) * tf * (k1 + 1) / (tf + K); });
}
function rank(query, detail) {
  const terms = analyze(query), rows = [];
  docs.forEach((d, i) => { const parts = bm25(terms, d), s = parts.reduce((a, x) => a + x, 0);
    const tfidf = terms.reduce((a, t) => a + d.filter(x => x === t).length * idf(t), 0);
    if (s > 0) rows.push([i + 1, d.length, parts, s, tfidf]); });
  rows.sort((x, y) => y[3] - x[3] || x[0] - y[0]);
  console.log((detail ? "" : "\n") + `query "${query}"  (N=${N}, avgdl=${avgdl})`);
  if (detail) console.log(terms.map(t => `${t}: df=${df(t)} idf=${idf(t).toFixed(3)}`).join("   "));
  console.log(detail ? "doc len  " + terms.join("   ") + "   BM25   tf*idf" : "doc len  BM25");
  for (const [id, len, parts, s, ti] of rows) console.log(String(id).padStart(3), String(len).padStart(3), " ",
    (detail ? parts.map(p => p.toFixed(3)).join("  ") + "  " : "") + s.toFixed(3) + (detail ? "  " + ti.toFixed(3) : ""));
}
rank("ট্রেন টিকিট", true);
rank("metro rail ticket", false);

query "ট্রেন টিকিট"  (N=8, avgdl=4.5)
ট্রেন: df=3 idf=0.944   টিকিট: df=5 idf=0.492
doc len  ট্রেন   টিকিট   BM25   tf*idf
  5   6   0.831  0.722  1.553  2.422
  4   4   0.989  0.516  1.505  1.437
  7   4   0.989  0.000  0.989  0.944
  1   4   0.000  0.516  0.516  0.492
  3   5   0.000  0.471  0.471  0.492
  6   5   0.000  0.471  0.471  0.492

query "metro rail ticket"  (N=8, avgdl=4.5)
doc len  BM25
  1   4   1.758
  3   5   1.605
  6   5   1.605
  2   4   1.242
  5   6   0.722
  4   4   0.516
  8   4   0.516

লেখার বাইরের সংকেত

শুধু লেখার মিল দিয়ে ভালো ক্রম হয় না। বাস্তবে আরও কয়েকটি সংকেত মেশানো হয়:

• জনপ্রিয়তা: বিক্রি, ক্লিক, rating.
• নতুনত্ব: সংবাদে সময়ের সাথে কমে যাওয়া (time decay) ওজন।
• ব্যক্তিগত প্রসঙ্গ: অবস্থান — চট্টগ্রাম থেকে “বাস” খুঁজলে স্থানীয় রুট আগে; ভাষা; আগের আচরণ।

সাধারণ নকশা দুই ধাপের। প্রথমে BM25-এর মতো সস্তা স্কোরে প্রতিটি shard থেকে কয়েকশো প্রার্থী; তারপর একটি learning-to-rank মডেল সেগুলোকে বহু সংকেতে আবার সাজায়। News feed-এর ranking পর্ব ৫৬-এ দেখবেন। আর ranking ভালো হলো কি না মাপতে লাগে লেবেল করা প্রশ্নের তালিকা (precision আর recall), ক্লিকের হার আর A/B test — অনুমান নয়।

৫ · বড় index-এর ভেতর — immutable segment, merge আর near-real-time

সাজানো, সংকুচিত posting list-এর মাঝখানে একটি নতুন docId ঢোকানো খুব দামি। তাই Lucene-ধাঁচের engine index-কে কখনো জায়গায় বদলায় না। নতুন ডকুমেন্ট আগে memory-র একটি buffer-এ জমে; কিছুক্ষণ পরপর সেই buffer থেকে একটি ছোট, সম্পূর্ণ, আর কখনো না-বদলানো segment তৈরি হয়। একটি index মানে অনেকগুলো segment, আর খোঁজ প্রতিটি segment-এ চলে ফল মেলায়। পেছনে merge ছোট segment-গুলো জুড়ে বড় segment বানায়। পর্ব ১৯-এর LSM-tree-এর সাথে মিলটা স্পষ্ট।

• Refresh আর near-real-time: buffer থেকে segment খোলাকে Elasticsearch বলে refresh; লেখার সময়ে ডিফল্ট প্রায় ১ সেকেন্ড পরপর (সংস্করণভেদে আলাদা)। তাই নতুন লেখা সঙ্গে সঙ্গে নয়, refresh-এর পরে খোঁজে আসে।
• টেকসই হওয়া আলাদা: refresh মানেই disk-এ নিরাপদ নয়। Crash-এর জন্য engine একটি নিজস্ব log (Elasticsearch-এ translog) রাখে, আর মাঝে মাঝে commit-এ fsync করে — write-ahead log-এর একই চিন্তা।
• Delete মানে tombstone: segment বদলানো যায় না, তাই মুছে ফেলা ডকুমেন্ট শুধু চিহ্নিত হয় (segment-প্রতি একটি bitset); খোঁজ তাদের এড়িয়ে যায়, আর merge-এর সময় আসলে বাদ পড়ে। Update মানে পুরোনোটি মোছা আর নতুনটি যোগ।
• কেন এই কষ্ট: না-বদলানো ফাইল পড়তে lock লাগে না, OS-এর page cache-এ নিশ্চিন্তে থাকে, ভালোভাবে সংকুচিত হয়, আর segment-প্রতি cache (যেমন filter-এর ফল) বৈধ থাকে।

৬ · Search cluster — shard, replica আর scatter-gather

একটি যন্ত্রে আর না ধরলে index ভাগ করতে হয় (পর্ব ২৩)। দুটি পথ:

Elasticsearch, OpenSearch, Solr — সবাই প্রথম পথে চলে। ডকুমেন্ট কোন shard-এ যাবে, তা ঠিক করে hash(routing key) mod shard-সংখ্যা; routing key ডিফল্টে ডকুমেন্টের id. এই mod-এর কারণে প্রাথমিক shard-এর সংখ্যা index তৈরির সময়েই ঠিক হয়; পরে বদলাতে split বা পুরো reindex লাগে (সংস্করণভেদে আলাদা; পর্ব ১৬-এর consistent hashing-এর সাথে তুলনা করুন)। Routing key বিক্রেতা হলে query একটি shard-এই সারে, কিন্তু বড় বিক্রেতা hot key হয়ে যায়। প্রতিটি shard-এর এক বা একাধিক replica (পর্ব ২২): যন্ত্র বিকল হলেও খোঁজ চলে, পড়ার চাপও ভাগ হয়।

একটি query-র যাত্রা: query, তারপর fetch

1. যেকোনো node coordinating node হিসেবে প্রশ্ন নেয় আর প্রতিটি shard-এর একটি কপিতে পাঠায় — scatter-gather.
2. প্রতিটি shard নিজের ভেতরে খুঁজে শুধু নিজের সেরা top-k-এর (docId, স্কোর) ফেরত দেয়, পুরো ডকুমেন্ট নয়।
3. Coordinator সাজানো তালিকাগুলো মেলায় — k-way merge, বড় মাপে একটি heap দিয়ে (DSA · heap আর priority queue).
4. বিজয়ী ১০টির পুরো ডকুমেন্ট (শিরোনাম, দাম, ছবি) সংশ্লিষ্ট shard থেকে আনা হয় — fetch ধাপ।

নিচের simulator-এ ২০,০০০টি মিলে যাওয়া ডকুমেন্ট hash দিয়ে ৪টি shard-এ ভাগ। প্রতিটি shard নিজের ফল স্কোরের ক্রমে রাখে; coordinator k-way merge করে। প্রথমে সেরা ৫টি, তারপর পাতা ১, ১০, ১০০ আর ১,০০০-এর (প্রতি পাতায় ১০টি) খরচ:

// Scatter-gather: 20,000 matching docs spread over 4 shards by hash(id). Each shard sends
// back its own best (from + size) hits; the coordinator merges the sorted lists (k-way merge).
function rng(seed) { return () => { seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
function fnv1a(s) { let h = 0x811c9dc5; for (const c of s) { h ^= c.charCodeAt(0); h = Math.imul(h, 0x01000193) >>> 0; } return h; }
const rand = rng(27), S = 4, shards = Array.from({ length: S }, () => []);
for (let i = 1; i <= 20000; i++) {                  // score stands for a BM25 score
  const d = { id: "doc-" + i, score: Math.round(rand() * 1e6) / 1e5 };
  d.shard = fnv1a(d.id) % S; shards[d.shard].push(d);
}
const better = (a, b) => b.score - a.score || (a.id < b.id ? -1 : 1);
shards.forEach(s => s.sort(better));                 // each shard keeps hits in score order
function search(from, size) {
  const lists = shards.map(s => s.slice(0, from + size)), pos = lists.map(() => 0), out = [];
  while (out.length < from + size) {                 // take the best head among the S lists
    let best = -1;
    lists.forEach((l, i) => { if (pos[i] < l.length && (best < 0 || better(l[pos[i]], lists[best][pos[best]]) < 0)) best = i; });
    if (best < 0) break;
    out.push(lists[best][pos[best]++]);
  }
  return { hits: out.slice(from), sent: lists.reduce((n, l) => n + l.length, 0) };
}
console.log("docs per shard:", shards.map(s => s.length).join(", "));
const best5 = search(0, 5);
console.log("top-5:", best5.hits.map(d => `${d.id}@S${d.shard} ${d.score}`).join(" | "));
const all = shards.flat().sort(better).slice(0, 5).map(d => d.id).join();
console.log("same as one global sort?", all === best5.hits.map(d => d.id).join());
console.log("page  from   hits sent to coordinator   kept");
for (const page of [1, 10, 100, 1000]) {
  const r = search((page - 1) * 10, 10);
  console.log(String(page).padStart(4), String((page - 1) * 10).padStart(6), String(r.sent).padStart(18), String(r.hits.length).padStart(10));
}

docs per shard: 4999, 5000, 5001, 5000
top-5: doc-10150@S1 9.99907 | doc-14348@S2 9.9982 | doc-13977@S1 9.9978 | doc-12847@S0 9.99718 | doc-15329@S2 9.99585
same as one global sort? true
page  from   hits sent to coordinator   kept
   1      0                 40         10
  10     90                400         10
 100    990               4000         10
1000   9990              20000         10

Tail latency: প্রতিটি query সব shard-এর উত্তরের অপেক্ষা করে, তাই সবচেয়ে ধীরটিই মোট সময় ঠিক করে (পর্ব ৪)। একটি shard ১% অনুরোধে ধীর হলে, স্বাধীন ধরে, অন্তত একটি ধীর shard ছোঁয়ার সম্ভাবনা 1 − 0.99^N: N = ৪-এ প্রায় ৩.৯%, ২০-এ ১৮.২%, ১০০-এ ৬৩.৪%. প্রতিকার: অপ্রয়োজনে বেশি shard না বানানো (লেখার সময়ে Elastic-এর নির্দেশিকা প্রতি shard মোটামুটি ১০–৫০ GB-এর কথা বলে, সংস্করণভেদে আলাদা), দেরি হলে আরেক replica-তে hedged request, আর সময়সীমা পেরোলে আংশিক ফল দেখানো।

৭ · Primary database আর search index-কে মিলিয়ে রাখা

পণ্যের দাম বদলাল database-এ। সার্চে নতুন দাম কীভাবে পৌঁছাবে? সবচেয়ে সহজ ভাবনা dual write: অ্যাপ আগে database-এ লেখে, তারপর search index-এ। তিনটি চেনা বিপদ:

• আংশিক ব্যর্থতা: database-এ commit হলো, index-এ লেখা ব্যর্থ বা মাঝপথে process বন্ধ — index চিরকাল পুরোনো।
• ক্রম উল্টে যাওয়া: দুই সার্ভার একই পণ্যের দুটি বদল (৫০০ টাকা, তারপর ৪৫০) পাঠাল, index-এ পৌঁছাল উল্টো ক্রমে — পুরোনো দামই জিতে রইল।
• দুই জায়গায় transaction নেই: database আর search engine-কে একসাথে commit করানোর সহজ উপায় নেই (পর্ব ২৫)।

পরিণত নকশা হলো change data capture (CDC): database-এর নিজের log (PostgreSQL-এর WAL, MySQL-এর binlog) পড়ে প্রতিটি commit হওয়া পরিবর্তন একটি event stream-এ পাঠানো, আর একটি indexer সেখান থেকে index হালনাগাদ করে। নিচের ছবিতে লেখার পথ বাঁয়ে, পড়ার পথ ডানে:

• ক্রম আর idempotency: stream-এ partition ঠিক হয় ডকুমেন্টের id দিয়ে, তাই একই পণ্যের event ক্রমে আসে (পর্ব ৩৩)। প্রতিটি লেখায় database থেকে আসা একটি version (যেমন log-এর অবস্থান); index পুরোনো version-এর লেখা ফিরিয়ে দেয়, তাই একই event দুবার এলেও ক্ষতি নেই — idempotency.
• Outbox: টেবিলের সারি-বদলের বদলে অর্থবহ event চাইলে (“পণ্য প্রকাশিত হলো”) একই transaction-এ একটি outbox টেবিলে লেখা হয়, আর CDC সেটি পড়ে — outbox pattern, পর্ব ২৫-এ বিস্তারিত।
• Eventual consistency: মোট দেরি ধরা যাক ১ থেকে ৫ সেকেন্ড। ব্যবহারকারী নিজের নতুন পোস্ট নিজের পাতায় database থেকে দেখবেন (read-your-writes), সার্চে কয়েক সেকেন্ড পরে। খুব জরুরি লেখায় refresh-এর অপেক্ষা করানো যায় (যেমন Elasticsearch-এর refresh=wait_for), কিন্তু সবখানে করলে indexing ধীর হয়।
• Reindex: analyzer বা mapping বদলালে পুরোনো segment কাজে লাগে না। নতুন index বানান database-এর snapshot থেকে, snapshot-এর log-অবস্থান থেকে stream আবার চালান, মিলে গেলে একটি alias এক মুহূর্তে নতুন index-এ সরান (index alias). পুরোনোটি কিছুদিন রাখুন, ফিরে যাওয়ার জন্য।
• মুছে ফেলাও পৌঁছাতে হবে: database-এ মোছা পোস্ট index-এ থেকে গেলে মুছে ফেলা ব্যক্তিগত তথ্য সার্চে বেরিয়ে আসে — গোপনীয়তার ঝুঁকি। তাই delete event, lag-এর metric আর মাঝে মাঝে দুই দিকের ডকুমেন্ট-সংখ্যা মেলানো নকশার অংশ।

৮ · Autocomplete — prefix trie, top-k আর latency বাজেট

সার্চ বক্সে “dha” লিখতেই নিচে “dhaka weather”, “dhanmondi lake” — autocomplete (typeahead). এটি আলাদা একটি সার্ভিস, কারণ চাহিদা আলাদা:

• প্রতিটি অক্ষরে একটি অনুরোধ: client ধরা যাক ১০০–২০০ ms থেমে থাকলে তবেই পাঠায় (debouncing), পুরোনো অনুরোধ বাতিল করে আর আগের উত্তর মনে রাখে।
• বাজেট খুব কম: মানুষের কাছে প্রায় ০.১ সেকেন্ডের মধ্যে উত্তর “তাৎক্ষণিক” লাগে বলে usability-র পুরোনো নিয়ম আছে। মোবাইল network-এর round trip-ই এর বড় অংশ খায়, তাই সার্ভারের ভাগ মোটামুটি কয়েক থেকে কয়েক দশক ms (latency budget).
• উৎস ডকুমেন্ট নয়, মানুষের প্রশ্ন: পরামর্শ আসে query log থেকে — কতজন কী খুঁজেছেন, সময়ের সাথে ওজন কমিয়ে। আপত্তিকর শব্দ, ফোন নম্বরের মতো ব্যক্তিগত তথ্য আর খুব কমজনের খোঁজা প্রশ্ন বাদ দিতে হয়, নইলে একজনের ব্যক্তিগত খোঁজ অন্যের পর্দায় ভেসে ওঠে।

মূল কাঠামো trie (DSA · trie): প্রতিটি edge একটি অক্ষর, একটি node মানে একটি prefix. সাধারণ trie-তে prefix-এর node-এ পৌঁছে নিচের পুরো subtree ঘুরে সেরা ৩টি খুঁজতে হয়। সিস্টেম নকশার কৌশল: প্রতিটি node-এ তার সেরা k-টি পরামর্শ আগে থেকেই রেখে দেওয়া। তখন খোঁজ মানে শুধু prefix-এর দৈর্ঘ্য পর্যন্ত হাঁটা, আর রাখা তালিকাটি পড়া। দাম: memory বাড়ে, আর একটি গণনা বদলালে পথের সব node হালনাগাদ করতে হয়।

// Autocomplete trie: each node stores its top-3 completions, so a lookup walks only the prefix.
// Seed data (assumed): how often each query was searched in a week.
const LOG = [["bangla news", 980], ["data science course", 950], ["dhaka weather", 920],
  ["dhanmondi lake", 900], ["dhakar khobor", 880], ["dhaka metro rail", 870],
  ["bangladesh cricket score", 760], ["dhaka university", 640], ["ajker khobor", 560],
  ["cox's bazar hotel", 520], ["dhaka metro rail ticket", 450], ["chittagong to dhaka bus", 410],
  ["dhaka to chittagong train", 380], ["bus ticket online", 350], ["ajker abohawa", 330],
  ["chittagong port", 330], ["dhaka traffic", 300], ["dhal recipe", 240]];
const K = 3, root = { kids: new Map(), top: [] };
let nodes = 1, refs = 0;
const better = (a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1);   // count desc, then A-Z
function insert(q, count) {
  let node = root;
  for (const ch of q) {
    if (!node.kids.has(ch)) { node.kids.set(ch, { kids: new Map(), top: [] }); nodes++; }
    node = node.kids.get(ch);
    node.top.push([q, count]); node.top.sort(better);
    if (node.top.length > K) node.top.pop();
  }
}
LOG.forEach(([q, c]) => insert(q, c));
function suggest(prefix) {                      // walk len(prefix) nodes, read the stored list
  let node = root;
  for (const ch of prefix) { node = node.kids.get(ch); if (!node) return "(no node: try fuzzy)"; }
  return node.top.map(([q, c]) => `${q} (${c})`).join(" | ");
}
const subtree = n => 1 + [...n.kids.values()].reduce((s, k) => s + subtree(k), 0);
for (const p of ["d", "dh", "dha", "dhak", "dhaka", "dhaka ", "dhaka m", "dhk"])
  console.log(JSON.stringify(p).padEnd(10), "->", suggest(p));
(function count(n) { refs += n.top.length; n.kids.forEach(count); })(root);
const chars = LOG.reduce((s, [q]) => s + q.length, 0);
console.log(`queries ${LOG.length}, characters ${chars}, trie nodes ${nodes}, stored top-k refs ${refs}`);
console.log(`memory if 64 B per node + 8 B per ref: ${((nodes * 64 + refs * 8) / 1024).toFixed(1)} KB`);
console.log(`without stored top-k, "d" must visit its whole subtree: ${subtree(root.kids.get("d"))} nodes`);

"d"        -> data science course (950) | dhaka weather (920) | dhanmondi lake (900)
"dh"       -> dhaka weather (920) | dhanmondi lake (900) | dhakar khobor (880)
"dha"      -> dhaka weather (920) | dhanmondi lake (900) | dhakar khobor (880)
"dhak"     -> dhaka weather (920) | dhakar khobor (880) | dhaka metro rail (870)
"dhaka"    -> dhaka weather (920) | dhakar khobor (880) | dhaka metro rail (870)
"dhaka "   -> dhaka weather (920) | dhaka metro rail (870) | dhaka university (640)
"dhaka m"  -> dhaka metro rail (870) | dhaka metro rail ticket (450)
"dhk"      -> (no node: try fuzzy)
queries 18, characters 295, trie nodes 218, stored top-k refs 265
memory if 64 B per node + 8 B per ref: 15.7 KB
without stored top-k, "d" must visit its whole subtree: 110 nodes

মাপ বাড়লে: cache, হালনাগাদ আর ভাগ

• Hot prefix cache: জনপ্রিয়তা Zipf-ধাঁচের, আর এক-দুই অক্ষরের prefix হাতে গোনা। এদের উত্তর কয়েক মিনিটের TTL-এ CDN-এ রাখা যায় (পর্ব ১৭; cache-এর কৌশল পর্ব ২৮-এ)।
• Offline বনাম online হালনাগাদ: সাধারণত query log থেকে ঘণ্টায় বা দিনে একবার batch কাজে (পর্ব ৩৬) পুরো নতুন trie বানিয়ে এক মুহূর্তে বদল। হঠাৎ জনপ্রিয় খবরের জন্য stream থেকে (পর্ব ৩৩) ছোট একটি “trending” তালিকা, খোঁজের সময় মিশিয়ে। প্রতিটি গণনায় trie-র পথ বদলানো দামি, lock-এর ঝামেলাও আনে।
• ভাগ: ছোট trie প্রতিটি সার্ভারে পুরোটা (replica). বড় হলে প্রথম অক্ষরে ভাগ করলে “d” বা “s”-এ hot spot; বিকল্প prefix-এর hash, বা prefix → top-k তালিকা একটি key-value store-এ। Lucene-এর completion suggester একটি সংকুচিত automaton (FST) memory-তে রাখে।

৯ · Fuzzy matching আর faceted search

Fuzzy matching: “dhk”, “rajshahi”, “রাজশাহি” — ভুল বা ভিন্ন বানানেও ফল চাই। মাপকাঠি edit distance (Levenshtein, ১৯৬৫): ন্যূনতম কতবার একটি অক্ষর যোগ, বাদ বা বদলালে এক শব্দ আরেকটি হয়; Damerau-র রূপে পাশাপাশি দুই অক্ষর অদলবদলও এক ধাপ। হিসাবটি DP (DSA · edit distance), কিন্তু লাখো term-এর প্রতিটির সাথে DP চালানো অসম্ভব। তাই engine সীমা টানে: সর্বোচ্চ ১–২টি edit, প্রথম এক-দুই অক্ষর হুবহু, আর সম্ভাব্য term automaton দিয়ে অভিধানে খোঁজা (Lucene-এর fuzzy query, লেখার সময়ে, Levenshtein automaton ব্যবহার করে)। Elasticsearch-এর fuzziness: AUTO ছোট শব্দে ০, মাঝারিতে ১, লম্বায় ২টি edit দেয় (সংস্করণভেদে আলাদা)।

আরেক কৌশল n-gram: “dhaka”-র trigram dha, hak, aka; বেশি trigram মেলা term কাছের প্রার্থী। এটি বাংলার বানান-ভিন্নতাতেও (সরকারি/সরকারী) কাজে লাগে, তবে অক্ষর গুনতে হয় grapheme cluster ধরে। সতর্কতা: সবসময় fuzzy চালালে ফল এলোমেলো হয়; সাধারণত হুবহু মিল কম হলে তবেই fuzzy, আর হুবহু মিলের স্কোর বেশি।

Faceted search: “শাড়ি” খুঁজলে বাঁ পাশে “জামদানি (১২০) · তাঁত (৮৫) · সিল্ক (৪০)”, “দাম ১,০০০–৩,০০০ (৯৫)” (সংখ্যাগুলো কাল্পনিক)। মিলে যাওয়া প্রতিটি ডকুমেন্টের ক্ষেত্রের মান গুনে এগুলো আসে। দ্রুত গোনার জন্য engine প্রতিটি field-এর মান column-আকারে আলাদা রাখে (doc values), যাতে লাখো ডকুমেন্টের “category” পুরো ডকুমেন্ট না খুলেই পড়া যায়।

• Filter বনাম query: “শুধু ঢাকা জেলা”, “স্টকে আছে” — হ্যাঁ/না প্রশ্ন, স্কোরে প্রভাব নেই। তাই filter-এর ফল bitset হিসেবে cache করা যায়, আর পরের খোঁজে আবার কাজে লাগে।
• বহু shard-এ গোনা: প্রতিটি shard নিজের সেরা মানগুলো পাঠায়, তাই “সেরা ১০টি ব্র্যান্ড”-এর সংখ্যা কখনো আনুমানিক হয় (Elasticsearch এর একটি ত্রুটির মাপও জানায়)। অনেক আলাদা মানের field-এ (যেমন বিক্রেতার id) facet দামি।

১০ · AI-এর যুগে search-এর নকশা যাচাই

“আমাদের সাইটে সার্চ বানাতে চাই” — AI প্রায়ই সোজা বলে “Elasticsearch, Kafka আর Redis বসান, ML দিয়ে ranking করুন।” আসল প্রশ্নগুলো তাতে থাকে না: কতগুলো ডকুমেন্ট, কোন ভাষা, কতটা দেরি চলবে, কী মুছতে হবে। সাধারণ ভুলগুলো:

AI-এর search-পরিকল্পনা হাতে পেলে — যাচাইয়ের চেকলিস্ট

• ডকুমেন্ট-সংখ্যা, index-এর আকার, QPS আর shard-এর হিসাব নিজে আবার করেছি
• নিজের ডেটার আসল প্রশ্নে (বাংলা, ইংরেজি, Banglish) analyzer চালিয়ে token দেখেছি
• লেখার পথে dual write নেই; CDC বা outbox, id ধরে ক্রম, version আর delete আছে
• “নতুন লেখা কত সেকেন্ডে সার্চে আসে” মেপেছি, আর ব্যবহারকারীর কাছে তা লুকাইনি
• Deep pagination, fan-out-এর tail latency আর একটি shard বিকল হলে কী হয়, ভেবে দেখেছি
• প্রতিটি ডিফল্ট মান আর সীমা অফিসিয়াল documentation-এ মিলিয়েছি