Web Services১১ মিনিট পাঠ

সার্চ অটোকমপ্লিট ডিজাইন

টাইপ করার সাথে সাথেই ইনস্ট্যান্ট সাজেশন — বিশাল স্কেলে

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

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

প্রতিবার যখন আপনি গুগলের সার্চ বারে টাইপ করেন, সাজেশনগুলো প্রায় তাৎক্ষণিকভাবেই আপনার সামনে চলে আসে। এতো বড় স্কেলে এটি কীভাবে কাজ করে? চলুন, একটি সার্চ অটোকমপ্লিট সিস্টেম (Search Autocomplete System) ডিজাইন করি।

প্রথমে, প্রয়োজনীয়তাগুলো পরিষ্কার করা যাক:

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

ইউজার যখন একেকটি ক্যারেক্টার টাইপ করবেন, প্রিফিক্সের (Prefix) উপর ভিত্তি করে সবচেয়ে মানানসই (যেমন ৫টি) কোয়েরির ফলাফল বা সাজেশন রিটার্ন করতে হবে।
সাজেশনগুলোকে জনপ্রিয়তার (কোয়েরির ফ্রিকোয়েন্সি) হিসেবে সাজিয়ে দেখাতে হবে।
শুধু প্রিফিক্স ম্যাচিং — আমরা এখানে ফাজি সার্চ (Fuzzy search) বা স্পেল কারেকশন (Spell correction) নিয়ে কাজ করছি না।

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

নিম্ন ল্যাটেন্সি (Low latency): সাজেশনগুলো অবশ্যই ১০০ মিলিসেকেন্ডের মধ্যে আসতে হবে। এর চেয়ে বেশি সময় লাগলে তা ল্যাগি (Laggy) মনে হবে।
উচ্চ প্রাপ্যতা (High availability): অটোকমপ্লিট একটি কোর (Core) ইউজার এক্সপেরিয়েন্স (UX) ফিচার — এটি সবসময় কাজ করতে হবে।
স্কেলেবল (Scalable): মিলিয়ন মিলিয়ন ইউজারের প্রতিদিন কোটি কোটি কোয়েরি সামলানোর ক্ষমতা থাকতে হবে।

▸ অটোকমপ্লিট যেভাবে কাজ করে: প্রিফিক্স → সাজেশন

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

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

প্রতিদিন ১০ বিলিয়ন কোয়েরি → ~১১৫ হাজার QPS (Queries Per Second), পিকে (Peak) ~২৩০ হাজার QPS
গড় কোয়েরি: ৪টি শব্দ × ৫ ক্যারেক্টার/শব্দ = ২০টি ক্যারেক্টার
প্রতি কোয়েরিতে অটোকমপ্লিটের ট্রিগার হওয়া: ~২০টি রিকোয়েস্ট (কী-বোর্ডে প্রতি ক্যারেক্টারে একবার)
অটোকমপ্লিট QPS: ~২.৩ মিলিয়ন (পিকে) (তবে বেশিরভাগই ক্যাশ থেকে আসে)
রেসপন্সের প্রয়োজনীয়তা: এন্ড-টু-এন্ড (End-to-end) < ১০০ মিলিসেকেন্ড
টপ-k (Top-k) সাজেশন: প্রতি প্রিফিক্সে ৫টি ফলাফল রিটার্ন করা হবে
মোট সংরক্ষিত ইউনিক কোয়েরি: ~৫ বিলিয়ন (ফ্রিকোয়েন্সি কাউন্টসহ)
প্রতি কোয়েরির জন্য স্টোরেজ: গড়ে ~৫০ বাইট → কোয়েরি ডেটাসেটের জন্য ~২৫০ GB
ট্রাই (Trie) স্টোরেজ: ~১০০ GB (অপ্টিমাইজেশনসহ) — ক্লাস্টার জুড়ে মেমোরিতে (RAM) ফিট হয়ে যাবে

এপিআই ডিজাইন (API Design)

একে সহজ রাখা যাক — শুধু একটি এন্ডপয়েন্ট (Endpoint):

সাজেশনগুলো পাওয়া (Get Suggestions)

Endpoint	`GET /api/v1/suggestions?prefix=sys&limit=5`
Response	`{"suggestions": ["system design", "system design interview", "system call", "system architecture", "system programming"]}`
Status	`200 OK`
Latency	< 100ms

ডিজাইন চয়েজ:

GET রিকোয়েস্ট (যযাতে করে আইডিয়ম্পোটেন্ট বা Idempotent হয়, এবং CDN/ব্রাউজার দিয়ে ক্যাশেবেল থাকে)।
প্রিফিক্স ইউআরএল (URL)-এনকোড করে কোয়েরি প্যারামিটারে (Query params) দেওয়া হয়।
বেসিক অটোকমপ্লিটের জন্য (পাবলিক কোয়েরি) কোনো অথেন্টিকেশন (Authentication) লাগে না।
রেসপন্সটি ইচ্ছে করেই ছোট রাখা হয় — শুধুই স্ট্রিংয়ের (Strings) একটি অ্যারে (Array)।

▸ প্রিফিক্স ম্যাচিংয়ের জন্য ট্রাই ডেটা স্ট্রাকচার (Trie Data Structure)

Click chart to zoom

কোয়েরি ফ্লো (Query Flow): CDN বেশিরভাগ রিকোয়েস্ট প্রসেস করে; শুধুমাত্র ক্যাশ মিস হলেরাই রিকোয়েস্টগুলো ট্রাই সার্ভার পর্যন্ত পৌঁছায়

কোর ডেটা স্ট্রাকচার (Core Data Structure): ট্রাই (The Trie)

অটোকমপ্লিটের জন্য একটি ট্রাই বা Trie (প্রিফিক্স ট্রি বা Prefix Tree) হলো সবচেয়ে পারফেক্ট ডেটা স্ট্রাকচার। এর প্রতিটি নোড (Node) একটি ক্যারেক্টারকে নির্দেশ করে, এবং রুট (Root) থেকে নিচের দিকের প্রতিটি নোডের রুট বা পথ একটি একটি প্রিফিক্স তৈরি করে।

মূল পয়েন্ট (Key insight): প্রতিটি নোডে, আমরা আগে থেকেই ওই নোড পেরিয়ে যাওয়া সবচেয়ে জনপ্রিয় টপ-k (Top-k) কোয়েরির ফলাফল ক্যালকুলেট করে তা ক্যাশ বা সংরক্ষণ করে রাখি। এ কারণে যেকোনো প্রিফিক্স খোঁজার সময় তা কেবল একটি ট্রি ট্রাভার্সাল (Tree traversal) হিসেবে কাজ করে — কোয়েরির সময় সার্চ করা ফলাফলে কোনো ধরনের র্যাংঙ্কিং (Sorting) করার প্রয়োজন হয় গঠন (Sorting) করার প্রয়োজন হয় না।

এটি যেভাবে কাজ করে:

প্রিফিক্স ক্যারেক্টারগুলো (যেমন, s → y → s) অনুসরণ করে ট্রাই ট্রাভার্স করুন।
শেষ নোডে, আগে থেকে ক্যাশ করে রাখা টপ-৫ কোয়েরির ফলাফলগুলো রিড করুন।
এগুলো দ্রুত রিটার্ন করুন — O(p) সময়ে, যেখানে p হলো প্রিফিক্সের ক্যারেক্টারের সংখ্যা বা দৈর্ঘ্য।

যদি আগে থেকে ক্যাশ করে না রাখা হয়, তবে আপনাকে প্রিফিক্স নোডের পেছনের সমস্ত সাবট্রি (Subtrees) ঘাটতে হতো যাতে আপনি সবচেয়ে জনপ্রিয় ফলাফল খুঁজে পান, যা মোট n কোয়েরির জন্য O(n) হতে পারে। আগে থেকে ক্যাশ করার মাধ্যমে আমরা এটি O(p) এ নামিয়ে আনি — যা অত্যন্ত লাভজনক একটি ব্যাপার।

▸ ডেটা কালেকশন (Data collection) এবং অ্যাগ্রিগেশন পাইপলাইন (Aggregation pipeline)

ডেটা কালেকশন এবং অ্যাগ্রিগেশন (Data Collection & Aggregation)

বর্তমান সময়ে কোন কোয়েরি কত জনপ্রিয় তা ট্রাই ডেটা স্ট্রাকচারে প্রতিফলিত করা দরকার। নিচের পাইপলাইনটির সাহায্যে সেটি করা যায়:

লগ কোয়েরি (Log queries): প্রতিটি সার্চ কোয়েরির সময় ও তথ্য লগ করা হয়।
স্কেল করে স্যাম্পল নেওয়া (Sample at scale): প্রতিদিন ১০ বিলিয়ন কোয়েরি থাকলে, সবগুলোর হিসেব রাখা সম্ভব হয় না — তাই ১০০টি বা ১,০০০টি কোয়েরির মধ্যে ১টিকে স্যাম্পল হিসেবে নেওয়া হয়।
প্রতি ঘণ্টা/দিনে অ্যাগ্রিগেট (Aggregate): একটি ম্যাপরিডিউস (MapReduce) বা স্পার্ক (Spark) জব নির্দিষ্ট সময়কালের (Time Windows) কোয়েরির ফ্রিকোয়েন্সি গণনা করে (যেমন, শেষের ৭ দিনের তথ্য, পুরোনো ডেটার গুরুত্ব কমানো)।
পুনরায় ট্রাই তৈরি (Rebuild the trie): মাঝে মাঝে (যেমন: প্রতি সপ্তাহে) সব ডেটা ব্যবহার করে পুরো ট্রাইটিকে আবার তৈরি করা হয়। তারপর ব্লু-গ্রিন (Blue-green) ডিপ্লয়মেন্ট টেকনিক ব্যবহার করে নতুন ট্রাইটিকে ট্রাই সার্ভারগুলোতে দেয়া হয়।
রিয়েল-টাইম আপডেট (Real-time updates): হঠাৎ করে ভাইরাল হওয়া বা ট্রেন্ডিং (Trending) কোয়েরিগুলো দেখানোর জন্য একটি ভিন্ন ছোট ও ফার্স্ট পাথ (fast path) — যা মেমোরিতে (in-memory) থাকে, তা ব্যবহার করা হয় এবং খুব দ্রুত রিয়েল-টাইমে আপডেট করা হয়।

এই দুই ধরনের পদ্ধতি (ব্যাচ প্রসেস + রিয়েল-টাইম) একসঙ্গে কাজ করে নির্ভুলতা এবং নতুনত্ব (Freshness) দুটোই ঠিক রাখে।

▸ পূর্ণাঙ্গ আর্কিটেকচার (Full architecture)

Note: ট্রাই অপটিমাইজেশন টিপস: (১) বারবার ব্যবহৃত নোডগুলোতে টপ-k ফলাফল ক্যাশ করে রাখুন — ট্রাইয়ের ওপরের দিকের প্রথম ২ লেভেল বেশিরভাগ কোয়েরি হ্যান্ডেল করে। (২) অনুভূমিক স্কেলিং-এর (Horizontal scaling) জন্য ট্রাইকে প্রিফিক্স রেঞ্জের (Range) ওপর ভিত্তি করে ভাগ করুন (যেমন a-m প্রিফিক্স যুক্ত হবে শার্ড (Shard) ১ এ, n-z হবে শার্ড ২ এ)। (৩) জনপ্রিয় প্রিফিক্সের জন্য সিডিএন (CDN)/এজ (Edge) ক্যাশিং ব্যবহার করুন — 'how', 'what', 'why' ইত্যাদি লক্ষ লক্ষ বার সার্চ করা হয়।

স্কেলিং এবং রিলায়েবিলিটি (Scaling & Reliability)

শার্ডিং (Sharding): প্রিফিক্সের প্রথম ১-২টি ক্যারেক্টারের ওপর ভিত্তি করে ট্রাই-কে শার্ড করুন। উদাহরণস্বরূপ, যে প্রিফিক্সগুলো a থেকে m ক্যারেক্টার দিয়ে শুরু হয় শার্ড ১ সেগুলোকে হ্যান্ডেল করে, আর n থেকে z ক্যারেক্টার দিয়ে শুরু হওয়া প্রিফিক্সগুলো শার্ড ২ হ্যান্ডেল করবে। এতে সমানভাবে ডেটা ডিস্ট্রিবিউট বা লোড ব্যালেন্স (Load balance) হয় এবং যেকোনো শার্ডকে স্বাধীনভাবে স্কেল করা যায়।

রেপ্লিকেশন (Replication): অ্যাভেইলেবিলিটি নিশ্চিত করতে প্রতিটি শার্ডের একাধিক রেপ্লিকা থাকে। একটি রেপ্লিকা কাজ করা বন্ধ করে দিলে তখন ট্রাফিক অন্য রেপ্লিকায় পাঠিয়ে দেওয়া হয়। লিডার-ফলোয়ার (Leader-follower) রেপ্লিকেশন মডেল ব্যবহার করতে পারেন — সব রেপ্লিকা রিড রিকোয়েস্ট সার্ভ করে, শুধু লিডার ট্রাই সার্ভারে আপডেট করে।

সিডিএন ও এজ ক্যাশিং (CDN & Edge Caching): জনপ্রিয় প্রিফিক্সগুলোর ফলাফল সিডিএন (CDN) বা এজ নেটওয়ার্কে (Edge cache) সেভ করে রাখা হয়। যেমন: "how to", "what is", এবং "best" এগুলোর মতো প্রিফিক্সগুলো লক্ষ লক্ষ বার একইভাবে সার্চ করা হয় এবং এদের ফলাফল একই থাকে। একটি ছোট TTL (Time-To-Live) (যেমন, ১ ঘণ্টা) ক্যাশের ফ্রেসনেস (Freshness) এবং ক্যাশ হিট রেট-এর (Cache hit rate) মাঝে চমৎকার একটি সমতা তৈরি করে।

ক্লায়েন্ট-সাইড অপটিমাইজেশন (Client-side optimization): ব্রাউজার চাইলে আগের সার্চ করা সাজেশনগুলো নিজ থেকেই লোকালে ক্যাশ করতে পারে এবং ইউজারের লেখার গতির সাথে তাল মেলাতে ডিবাইন্স (Debounce) (ইউজারের টাইপ করা থামার পর ৫০-১০০ মিলিসেকেন্ড অপেক্ষা করা, তারপর সার্ভারে রিকোয়েস্ট পাঠানো) ব্যবহার করতে পারে। এটি সার্ভারের চাপ চমৎকারভাবে কমিয়ে দেয়।