Data & Infrastructure১৪ মিনিট পাঠ

সার্চ ইঞ্জিন ডিজাইন

বিলিয়ন বিলিয়ন ওয়েব পেজ ইনডেক্স করা এবং কয়েক মিলিসেকেন্ডে প্রাসঙ্গিক ফলাফল প্রদান

scope:রিয়েল-ওয়ার্ল্ড সিস্টেম (Real-World System)difficulty:অ্যাডভান্সড (Advanced)

সমস্যাটি বোঝা (Understanding the Problem)

গুগল (Google) কীভাবে বিলিয়ন বিলিয়ন ওয়েব পেজ ইনডেক্স করে এবং ২০০ মিলিসেকেন্ডেরও কম সময়ের মধ্যে সবচেয়ে প্রাসঙ্গিক ফলাফল দেখায়? চলুন একদম শুরু থেকে একটি সার্চ ইঞ্জিন ডিজাইন করি।

ফাংশনাল প্রয়োজনীয়তা (Functional Requirements):

ক্রল (Crawl): ওয়েব ক্রলিং করা — ইন্টারনেট থেকে বিলিয়ন বিলিয়ন পেজ আবিষ্কার ও ডাউনলোড করা।
ইনডেক্স (Index): ক্রল করা কনটেন্ট 인ডেক্স করা — র (Raw) এইচটিএমএল (HTML) থেকে একটি সার্চযোগ্য ডেটা স্ট্রাকচার (data structure) তৈরি করা।
সার্চ কোয়েরি (Search queries): টেক্সট কোয়েরি (query) গ্রহণ করা এবং এর সাথে মিলে যাওয়া ডকুমেন্টস বা পেজগুলো খুঁজে বের করা।
র‍্যাঙ্ক রেজাল্ট (Rank results): প্রাসঙ্গিকতা (Relevance), কর্তৃত্ব (Authority), এবং নতুনত্ব (Freshness)-এর ওপর ভিত্তি করে ফলাফলগুলো সাজানো।
স্নিপেট (Snippets): প্রতিটি ফলাফল কেন মিলছে তা বোঝানোর জন্য একটি ছোট প্রিভিউ জেনারেট করা।

নন-ফাংশনাল প্রয়োজনীয়তা (Non-Functional Requirements):

নিম্ন ল্যাটেন্সি (Low latency): কোয়েরি থেকে রেজাল্ট পাওয়ার সময়কাল ২০০ মিলিসেকেন্ডের কম হতে হবে। ব্যবহারকারীরা এর চেয়ে বেশি অপেক্ষা করতে পছন্দ করেন না।
ফ্রেসনেস বা নতুনত্ব (Freshness): নতুন এবং আপডেট করা কনটেন্ট কয়েক সপ্তাহ নয়, বরং কয়েক ঘণ্টার মধ্যেই সার্চ রেজাল্ট-এ আসা উচিত।
প্রাসঙ্গিকতা (Relevance): শীর্ষ ১০টি (Top 10) ফলাফল যেন ইউজারের কাছে সবচেয়ে "সঠিক" মনে হয় — এটিই সবচেয়ে কঠিন কাজ।
স্কেল বা পরিধি (Scale): পিক টাইমে (Peak) প্রতি সেকেন্ডে ১০০ হাজারের বেশি কোয়েরি (100K+ QPS) হ্যান্ডেল করার সক্ষমতা থাকতে হবে।

▸ মূল ধারণা: ক্রল → ইনডেক্স → সার্চ → র্যাঙ্ক

অ্যাস্টিমেশন (Estimation)

চলুন এই বিশাল সিস্টেমের সাইজ বা ক্যাপাসিটি পরিমাপ করি:

৫০ বিলিয়ন ইনডেক্স করা পেজ — দৃশ্যমান ওয়েব জগৎ বিশাল এবং এর শেষ নেই।
প্রতিদিন ১০ বিলিয়ন কোয়েরি — এর মানে গড়ে প্রায় ১১৫,০০০ QPS (Queries Per Second), আর পিকে (Peak) তা ~২০০,০০০ QPS-এ পৌঁছায়।
ইনডেক্সের সাইজ: ১০০ পেটাবাইটের (PB) বেশি — শুধুমাত্র ইনভার্টেড ইনডেক্সই (inverted index) বেশিরভাগ ডেটাবেসের চেয়ে অনেক বড়।
প্রতিটি কোয়েরি: সেরা ১০টি রেজাল্টে নামিয়ে আনার আগে প্রতিটি কোয়েরি গড়ে প্রায় ১ মিলিয়ন ক্যান্ডিডেট ডকুমেন্টস স্ক্যান বা স্পর্শ (touches) করে।

এটি বর্তমানে বিদ্যমান সবচেয়ে ডিমান্ডিং (Demanding) সিস্টেমগুলোর মধ্যে একটি। এখানকার আসল কৌশলটি বা ইনসাইটটি হলো: আমরা ইনডেক্স করার সময়ই সবকিছু প্রি-প্রসেস (preprocess) বা প্রস্তুত করে রাখি, যাতে কোয়েরি করার সময় অত্যন্ত দ্রুত ফলাফল দেওয়া যায়।

ইনভার্টেড ইনডেক্স (The Inverted Index)

প্রতিটি সার্চ ইঞ্জিনের কোর (Core) ডেটা স্ট্রাকচার হলো ইনভার্টেড ইনডেক্স: এটি একটি ম্যাপিং (Mapping), যেখানে প্রতিটি শব্দকে (word) সেই শব্দ যুক্ত ডকুমেন্টের লিস্টের সাথে ম্যাপ করা হয়।

প্রতিটি শব্দের জন্য, আমরা একটি পোসটিং লিস্ট (posting list) সংরক্ষণ করি: এটি (docId, position, frequency) এর একটি সর্টেড লিস্ট (sorted list)। এর মাধ্যমে আমরা জানতে পারি কোন ডকুমেন্টে শব্দটি রয়েছে, ডকুমেন্টের কোথায় সেটি আছে এবং কতবার শব্দটি ব্যবহৃত হয়েছে।

ক্রল করা কনটেন্ট থেকে ইনডেক্স তৈরি করার ধাপগুলো হলো:

টোকেনাইজেশন (Tokenization): পুরো টেক্সটকে শব্দে ভাগ করা, ছোট হাতের বা বড় হাতের (Case) পার্থক্য দূর করা এবং অপ্রয়োজনীয় শব্দ (stop words) বাদ দেওয়া।
পোসটিং লিস্ট তৈরি (Posting list construction): প্রতিটি টোকেন বা শব্দের জন্য, (docId, position, freq) এন্ট্রি (entry) যোগ করা।
টিএফ-আইডিএফ স্কোরিং (TF-IDF scoring): বেসিক প্রাসঙ্গিকতার জন্য টার্ম ফ্রিকোয়েন্সি (Term frequency) × ইনভার্স ডকুমেন্ট ফ্রিকোয়েন্সি (inverse document frequency) আগে থেকেই হিসাব করে রাখা। যদি কোনো শব্দ একটি নির্দিষ্ট ডকুমেন্টে বারবার আসে, কিন্তু সামগ্রিকভাবে সব ডকুমেন্টে কম দেখা যায়, তবে সেটি একটি শক্তিশালী সিগন্যাল (Signal)।

ইনভার্টেড ইনডেক্স যেকোনো সার্চ কোয়েরিকে "প্রতিটি ডকুমেন্ট স্ক্যান করা"-এর বদলে "একটি শব্দ লুকআপ (lookup) করা এবং লিস্ট নিয়ে আসা"-তে রূপান্তর করে — যা একটি \(O(N)\) সমস্যাকে \(O(1)\) লুকআপ এবং \(O(K)\) ইন্টারসেকশনে (intersection) পরিবর্তন করে।

▸ ইনভার্টেড ইনডেক্স: ডকুমেন্ট থেকে সার্চ

Click chart to zoom

সার্চ কোয়েরি ফ্লো: ইনডেক্স শার্ডগুলোতে ছড়িয়ে দেওয়া হয়, সেখান থেকে রেজাল্ট সংগ্রহ করা হয় এবং মার্জ (Merge) করা ক্যান্ডিডেটগুলোকে র্যাঙ্ক (Rank) করা হয়

র‍্যাঙ্কিং পাইপলাইন (Ranking Pipeline)

ডকুমেন্ট খুঁজে বের করা সহজ। সেগুলোকে র্যাঙ্ক (Rank) করা বা সাজানোই সবচেয়ে কঠিন কাজ। আধুনিক সার্চ ইঞ্জিনগুলো দুই-ধাপের র‍্যাঙ্কিং (two-phase ranking) পদ্ধতি ব্যবহার করে:

প্রথম ধাপ — রাফ স্কোরিং (Rough scoring - ইনডেক্স সার্ভারে):

বিএম২৫ (BM25): এটি TF-IDF-এর উন্নত ভার্সন যা ডকুমেন্টের দৈর্ঘ্য এবং টার্ম স্যাচুরেশন (term saturation) হিসাব করে। টেক্সটের প্রাসঙ্গিকতা বিচারে এটি প্রধান হাতিয়ার।
প্রতিটি ইনডেক্স শার্ড (shard) তার স্থানীয় ক্যান্ডিডেটদের স্কোর করে এবং টপ-K (যেমন, শীর্ষ ১,০০০) ফলাফল গ্যাদার বা সংগ্রহ (gather) লেয়ারে পাঠায়।

দ্বিতীয় ধাপ — ফাইন র‍্যাঙ্কিং (Fine ranking - র‍্যাঙ্কিং সার্ভারে):

পেজর‍্যাঙ্ক (PageRank): এটি লিঙ্কের কর্তৃত্ব (authority) পরিমাপ করে। যদি কোনো পেজকে অনেক বেশি কর্তৃত্বপূর্ণ (authoritative) পেজ লিঙ্ক (link) করে, তবে সেটিও কর্তৃত্বপূর্ণ হিসেবে বিবেচিত হয়। এটি আগে থেকেই একটি ইটারেটিভ গ্রাফ অ্যালগরিদম (iterative graph algorithm) ব্যবহার করে অফলাইনে হিসাব করে রাখা হয়।
এমএল রি-র‍্যাঙ্কিং (ML re-ranking): এটি একটি লার্নড মডেল (Learned model) যা শত শত সিগন্যাল একত্রিত করে তৈরি হয়: যেমন ক্লিক-থ্রু রেট (click-through rate), কনটেন্টের নতুনত্ব (freshness), পেজ কোয়ালিটি স্কোর (page quality score), ডুয়েল টাইম (dwell time) (কতক্ষণ ছিল), ভৌগলিক প্রাসঙ্গিকতা (geographic relevance) ইত্যাদি।
এই ধাপটি প্রতি ডকুমেন্টের জন্য বেশ ব্যয়বহুল, তাই এটি শুধুমাত্র মার্জ (merge) করা শীর্ষ-K ক্যান্ডিডেটদের (প্রায় ১,০০০ - ৫,০০০ ডকুমেন্ট, মিলিয়ন নয়) ওপরেই চালানো হয়।

এই দুই-ধাপের পদ্ধতিটি অত্যন্ত গুরুত্বপূর্ণ: আপনি ২০০ মিলিসেকেন্ডের মধ্যে ১ মিলিয়ন ডকুমেন্টের ওপরে এমএল মডেল চালাতে পারবেন না, কিন্তু আপনি মিলিয়ন ডকুমেন্টের ওপরে BM25 চালাতে পারবেন এবং শুধুমাত্র হাজারখানেক ডকুমেন্টের ওপরে এমএল ব্যবহার করে ফাইন র‍্যাঙ্কিং (Fine ranking) সম্পন্ন করতে পারবেন।

▸ র‍্যাঙ্কিং পাইপলাইন: ক্যান্ডিডেট থেকে রেজাল্ট

ইনডেক্স পার্টিশনিং এবং আর্কিটেকচার (Index Partitioning and Architecture)

৫০ বিলিয়ন ডকুমেন্টের কারণে কোনো একটি সার্ভার বা মেশিনে পুরো ইনডেক্স ধারণ করা সম্ভব নয়। আমরা এটিকে ডকুমেন্ট (document) অনুযায়ী পার্টিশন বা ভাগ করি: প্রতিটি শার্ড (shard) ডকুমেন্টের একটি নির্দিষ্ট সাবসেটের (subset) জন্য সম্পূর্ণ ইনভার্টেড ইনডেক্স সংরক্ষণ করে।

স্ক্যাটার-গ্যাদার (Scatter-gather) কোয়েরি এক্সিকিউশন (Query execution):

একটি কোয়েরি কোয়েরি সার্ভিস (Query Service) এ পৌঁছায়, যা এটিকে পার্স (parse) করে এবং রিরাইট (rewrite) করে।
কোয়েরিটি একইসাথে সমস্ত ইনডেক্স শার্ডগুলোতে স্ক্যাটার (scatter) বা ছড়িয়ে দেওয়া হয়।
প্রতিটি শার্ড তার লোকাল (local) ডকুমেন্টগুলোতে BM25 রান (run) করে এবং তার টপ-K (Top-K) ফলাফল রিটার্ন করে।
এই ফলাফলগুলো গ্যাদার (gather) বা সংগ্রহ করে মার্জ (merge) করা হয়, এরপর সেগুলোকে ফাইন স্কোরিংয়ের জন্য র‍্যাঙ্কিং সার্ভিসে (Ranking Service) পাঠানো হয়।

রেপ্লিকেশন (Replication): অ্যাভিলিবিটি বা সিস্টেমকে উচ্চ-উপলব্ধ (availability) রাখার জন্য এবং লোড ডিস্ট্রিবিউট (load distribution) করার জন্য প্রতিটি শার্ড ৩-৫ বার রেপ্লিকেট (replicate) বা অনুলিপি করা হয়। যদি একটি রেপ্লিকা ধীর হয়ে যায় বা ডাউন হয়, তবে কোয়েরিটি অন্য রেপ্লিকা থেকে সফলভাবে কাজ করে।

ব্যাকগ্রাউন্ড পাইপলাইন (Background pipeline): ওয়েব ক্রলার (Web Crawler) ক্রমাগত নতুন পেজগুলো আবিষ্কার করে। ইনডেক্সার (Indexer) র (raw) এইচটিএমএল (HTML)-কে টোকেন এবং পোসটিং লিস্টে (posting lists) রূপান্তর করে। ইনডেক্স বিল্ডার (Index Builder) নতুন ইনডেক্স সেগমেন্ট তৈরি করে, যা ইনডেক্স সার্ভারগুলোতে পুশ (push) করা হয় — এটি অবিরত হতে থাকে, একসাথে বিশাল কোনো ব্যাচ (batch) হিসেবে নয়।

▸ পূর্ণাঙ্গ আর্কিটেকচার

Note: ইন্টারভিউ টিপস: এখানে দুইটি মূল প্যাটার্নের ওপর জোর দিতে হবে (১) শার্ডগুলো থেকে ইনডেক্স লুকআপ-এর জন্য সমান্তরাল স্ক্যাটার-গ্যাদার (scatter-gather) টেকনিক, এবং (২) দুই-ধাপের র‍্যাঙ্কিং (Two-phase ranking) — সস্তা ইনডেক্স সার্ভারে রাফ স্কোরিং (rough scoring) ও ব্যয়বহুল র‍্যাঙ্কিং সার্ভারে এমএল (ML) দিয়ে ফাইন র‍্যাঙ্কিং (fine ranking)। এটি প্রমাণ করে যে আপনি জানেন কীভাবে বিলিয়ন ডকুমেন্টের মধ্যে ২০০ মিলিসেকেন্ডের ল্যাটেন্সি বাজেট ঠিক রাখতে হয়।