ওয়েব ক্রলার সিস্টেম ডিজাইন

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

একটি ওয়েব ক্রলার (যেমন গুগলবট - Googlebot) ইন্টারনেটের বিলিয়ন বিলিয়ন ওয়েব পেজে প্রতিনিয়ত ভিজিট করে সেগুলোর ডাটা সংগ্রহ করে এবং একটি সার্চ ইনডেক্স (search index) বা ডেটাবেস তৈরি করে। এটি প্রথমে কয়েকটি নির্দিষ্ট URL (Seed URLs) দিয়ে শুরু করে, এরপর সেই পেজগুলো ডাউনলোড করে, সেখান থেকে নতুন লিংক খুঁজে বের করে এবং পুনরায় এই প্রক্রিয়াটি চালাতে থাকে — এভাবেই এটি একটি পেজ থেকে ধীরে ধীরে পুরো ওয়েব গ্রাফকে (web graph) আবিষ্কার করে ফেলে।

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

• জানা পেজগুলো থেকে নতুন লিংক অনুসরণ করে নতুন URL আবিষ্কার করা।
• ওয়েব পেজগুলো ডাউনলোড বা ফেচ (Fetch) করা এবং তাদের কনটেন্ট (content) সেভ করে রাখা।
• নতুন পেজগুলো থেকে আরও URL খোঁজার জন্য লিংক এক্সট্রাক্ট (Extract) করা।
• ইনডেক্সিং, ডেটা এনালাইসিস বা আর্কাইভিংয়ের (archiving) জন্য ক্রল করা কনটেন্ট সংরক্ষণ করা।

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

• পোলাইটনেস (Politeness) বা রেট লিমিটিং (Rate Limiting): কোনো নির্দিষ্ট সার্ভারে একসাথে অনেক রিকোয়েস্ট পাঠিয়ে সেটিকে ডাউন করে দেওয়া যাবে না — robots.txt ফাইলের নিয়ম মেনে চলা এবং প্রতি হোস্টের বা সার্ভারের জন্য রিকোয়েস্ট সীমিত রাখা।
• ডুপ্লিকেট বা একই URL পুনরায় ভিজিট করা এড়ানো (Deduplication): একই URL হাজার হাজার ভিন্ন ভিন্ন পেজে থাকতে পারে। কিন্তু ক্রলারকে সেটি কেবল একবারই ভিজিট করতে হবে।
• ট্র্যাপ বা ফাঁদগুলো (Traps) এড়ানো: কিছু সাইট প্রতিনিয়ত অসীমসংখ্যক (Infinite) URL জেনারেট করে (যেমন: ক্যালেন্ডার, সেশন আইডি)। সিস্টেমকে অবশ্যই এগুলো শনাক্ত করতে হবে এবং তা এড়িয়ে চলতে হবে।
• বিলিয়ন বিলিয়ন পেজের জন্য স্কেলেবিলিটি (Scalability): যেহেতু ইন্টারনেটে বিলিয়ন বিলিয়ন ওয়েবসাইট আছে, সিস্টেমটিকে অবশ্যই হরিজন্টাল স্কেলেবল (horizontally scalable) এবং ফল্ট-টলারেন্ট (fault-tolerant) হতে হবে।

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

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

• প্রতি মাসে ১ বিলিয়ন পেজ ক্রলিং: থ্রুপুট (Throughput) হিসেবে গড়ে ৪০০ পেজ/সেকেন্ড।
• গড় পেজের সাইজ: ~১০০ KB (HTML এবং এর হেডারসহ)।
• প্রতি মাসে স্টোরেজ: ১ বিলিয়ন × ১০০ KB = প্রায় ১০০ TB/মাস স্টোরেজ প্রয়োজন।
• DNS লুকআপ (DNS Lookups): ~৪০০ বার/সেকেন্ড (প্রতিটি পেজ ফেচ করার জন্য একবার, তবে লোকাল ক্যাশিং ব্যবহার করা হলে প্রকৃত এক্সটার্নাল রিকোয়েস্ট অনেক কমে যাবে)।
• URL ফ্রন্টিয়ারের (Frontier) আকার: যেকোনো মুহূর্তে এমন বিলিয়ন বিলিয়ন URL থাকবে যেগুলো সিস্টেম আবিষ্কার করেছে কিন্তু এখনও ক্রল বা ফেচ করেনি।
• ব্যান্ডউইথ (Bandwidth): ৪০০ পেজ/সেকেন্ড × ১০০ KB = ~৪০ MB/সেকেন্ড বা প্রায় ৩২০ Mbps অবিরত ব্যান্ডউইথ।

এই ধরণের সিস্টেম মূলত ডেটা সংরক্ষণ বা স্টোরেজ-হেভি (storage-heavy) এবং I/O-বাউন্ড (I/O-bound)। এর প্রধান কাজ বা প্রতিবন্ধকতাগুলো হলো নেটওয়ার্ক I/O, বারেবারে DNS রেজল্যুশন এবং বিশাল আকারের URL ফ্রন্টিয়ার পরিচালনা করা।

কোর অ্যালগরিদম (Core Algorithm): URL ফ্রন্টিয়ারের সাহায্যে BFS (Breadth-First Search)

একটি ওয়েব ক্রলার মূলত ওয়েব গ্রাফের ওপর একটি বিশাল আকারের ব্রেডথ-ফার্স্ট সার্চ (Breadth-First Search - BFS) চালায়। এর ধাপগুলো হলো:

1. সিড URL (Seed URLs) — খুব পপুলার কিছু হাই-কোয়ালিটি URL দিয়ে শুরু করা হয় (যেমন- জনপ্রিয় সংবাদ মাধ্যম, উইকিপিডিয়া বা সরকারি পোর্টাল)।
2. URL ফ্রন্টিয়ার বা কিউ (URL Frontier - queue) — এটি হলো পরবর্তীতে ক্রল করার জন্য রাখা রিকোয়েস্টগুলোর একটি প্রায়োরিটি কিউ (Priority queue)। সিড URL-গুলো সবার আগে এখানে এসে জায়গা করে।
3. ফেচ (Fetch) — কিউ থেকে একটি URL ডিকিউ (Dequeue) বা তুলে নেওয়া হয়, তারপর এর DNS রেজলভ (Resolve) করে HTTP রিকোয়েস্ট পাঠিয়ে ওয়েব পেজটি ডাউনলোড করা হয়।
4. পার্স (Parse) — ডাউনলোড করা HTML কনটেন্ট পার্স বা পর্যালোচনা করে সার্চ ইন্ডেক্সের জন্য শুধুমাত্র টেক্সটগুলো (Text) আলাদা করা হয়।
5. URL এক্সট্রাক্ট করা (Extract URLs) — পেজটিতে থাকা <a href="#"> ট্যাগগুলো খুঁজে বের করে অন্যান্য নতুন ওয়েবসাইটের লিংক বা URL বের করা হয়।
6. ফিল্টার এবং ডিডুপ্লিকেট (Filter & Deduplicate) — প্রতিটি এক্সট্রাক্ট করা URL আগে কখনো দেখা হয়েছে কিনা তা যাচাই করা। যদি না হয়, তবে সেগুলো আবার URL ফ্রন্টিয়ারে যুক্ত করে দেওয়া হয়।
7. পুনরাবৃত্তি বা রিপিট (Repeat) — আবার ধাপ ৩ থেকে শুরু করা। কিউ বা ফ্রন্টিয়ার খালি না হওয়া পর্যন্ত এটি চলতে থাকে (উন্মুক্ত ইন্টারনেটে এটি আসলে কখনোই খালি হয় না!)।

এখানে URL ফ্রন্টিয়ারই ক্রলারের মূল হার্ট বা মস্তিষ্ক। এটি ঠিক করে কোন পেজগুলো ক্রল করা হবে এবং কখন হবে — সাথে পেজগুলোর ফ্রেশনেস বা নতুনত্ব, গুরুত্ব এবং পোলাইটনেসের (politeness) মাঝে সামঞ্জস্য বিধান করে।

পোলাইটনেস এবং ডিডুপ্লিটকেশন (Politeness and Deduplication)

যে ক্রলার সার্ভারে একটানা ওভারলোড দেয়, সেটি একটি খারাপ ক্রলার। কোনো আইপি ব্যান হওয়া থেকে বাঁচতে এবং ইন্টারনেটের একজন দায়িত্বশীল ভিজিটর হিসেবে আচরণ করতে পোলাইটনেস মেনে চলা অত্যন্ত অপরিহার্য।

পোলাইটনেস (Politeness):

• robots.txt মেনে চলা — প্রতিটি ডোমেইনের /robots.txt ফাইলে নির্দিষ্ট করে বলা থাকে যে, ক্রলাররা ওই ওয়েবসাইটের কোন পেজগুলোতে ভিজিট করতে পারবে বা পারবে না, সাথে Crawl-delay নির্দেশিকাও থাকে। এটি সবসময় মেনে চলতে হবে।
• রেট-লিমিটিং পার-হোস্ট বা প্রতি ডোমেইনে স্পিড লিমিট — প্রতি সেকেন্ডে প্রতিটি ডোমেইনের জন্য গড়ে মাত্র একটি রিকোয়েস্টে সীমাবদ্ধ রাখা উচিত। আলাদা আলাদা ডোমেইনের জন্য আলাদা কিউ (queue) ব্যবহার করতে হবে যাতে আপনি খুব সহজেই থ্রটলিং (Throttling) করতে পারেন।
• প্রায়োরিটি কিউ (Priority Queue) — গভীরে থাকা অজানা লিংকের বদলে সবসময় গুরুত্বপূর্ণ পেজগুলোকে আগে ক্রল করতে হবে (যাদের PageRank বেশি বা প্রায়ই আপডেট হয় এমন পেজগুলোকে আগে ক্রল করা উচিত)।

URL ডিডুপ্লিটকেশন (URL Deduplication):

• ব্লুম ফিল্টার (Bloom Filter) — এটি একটি প্রোব্যাবিলিস্টিক ডেটা স্ট্রাকচার (Probabilistic data structure), যা খুবই স্পেস-ইফিশিয়েন্ট (space-efficient)। এটি নিশ্চিতভাবে বলতে পারে যে একটি URL "আগে কখনো দেখা যায়নি" অথবা "আগে হয়তো দেখা গেছে"। ১ বিলিয়ন URL এবং ১% ফলস-পজিটিভ রেট (False positive rate) সহ এটি মাত্র প্রায় ১.২ GB মেমোরির মতো জায়গা নেয়।
• URL ফিঙ্গারপ্রিন্ট সেট (Fingerprint Set) — প্রতিটি URL-কে হ্যাশ (MD5/SHA) করে একটি সেটে সংরক্ষণ করে রাখা। এটি একটু বেশি মেমোরি নেয় কিন্তু এতে কোনো ফলস-পজিটিভ থাকে না।

কনটেন্ট ডিডুপ্লিটকেশন (Content Deduplication):

• সিমহ্যাস (SimHash) — কাছাকাছি বা একই ধরনের কনটেন্ট শনাক্ত করতে এটি ব্যবহৃত হয় (যেমন মিরর সাইট বা একাধিক ব্লগে শেয়ার করা আর্টিকেল)। দুইটি পেজের URL ভিন্ন হলেও তাদের SimHash ভ্যালুর মাধ্যমে বোঝা যায় যে তাদের কনটেন্টগুলো প্রায় একই।

বিলিয়ন পেজ স্কেল করা (Scaling to Billions of Pages)

একটি মাত্র মেশিন পুরো ওয়েব দুনিয়াকে ক্রল করতে পারে কাশী করতে পারে না। এটি করার জন্য কিভাবে সিস্টেমটিকে স্কেল করতে হবে তা নিচে দেওয়া হলো:

একাধিক ক্রলার ওয়ার্কার (Multiple Crawler Workers): সমান্তরালভাবে (In parallel) শত শত ক্রলার ওয়ার্কার রান করাতে হবে। প্রতিটি ওয়ার্কার স্বাধীনভাবে তাদের পেজ ফেচ-পার্স-এক্সট্রাক্ট লুপ চালাতে থাকবে।

ডিস্ট্রিবিউটেড URL ফ্রন্টিয়ার (Distributed URL Frontier): কনসিস্টেন্ট হ্যাশিং (Consistent hashing) ব্যবহার করে ডোমেইন অনুযায়ী ফ্রন্টিয়ারকে ভাগ করে দিতে হবে। উদাহরণস্বরূপ, example.com-এর সবগুলো URL একই নির্দিষ্ট ফ্রন্টিয়ারে যাবে। এর মাধ্যমে খুব সহজেই প্রতি ডোমেইনের রেট-লিমিটিং (rate limiting) নিশ্চিত করা যায়, কারণ নির্দিষ্ট ওয়ার্কার শুধু তার নিজের ডোমেইনগুলোর হিসেব রাখবে।

চেকপয়েন্টিং এবং ক্র্যাশ রিকভারি (Checkpointing & Crash Recovery): নিয়মিত ফ্রন্টিয়ার স্টেট বা কাজের অগ্রগতি সেভ করে (snapshot) রাখতে হবে। যদি কোনো ওয়ার্কার ক্র্যাশ করে, তবে অন্য একটি ওয়ার্কার ঠিক সেই জায়গা থেকেই কাজ আবার শুরু করতে পারবে। কোনো URL যেন হারিয়ে না যায়, সেজন্য অ্যাট-লিস্ট-ওয়ান্স (At-least-once) ডেলিভারির সাহায্যে মেসেজ কিউ (Message Queues) ব্যবহার করতে হবে।

DNS ক্যাশ (DNS Cache): সাধারণত DNS রেজল্যুশনে সময় বেশি লাগে (প্রায় ১০-১০০ মিলিসেকেন্ড)। ডোমেইনের IP খুব একটা পরিবর্তন হয় না, তাই আগেই DNS রেজাল্টগুলো অ্যাগ্রেসিভলি (aggressively) ক্যাশ বা মেমোরিতে সেভ করে রাখতে হবে।

রি-ক্রল পলিসি (Recrawl Strategy): ওয়েব পেজগুলো সময়ের সাথে সাথে আপডেট হয়। এর জন্য এক্সপোনেনশিয়াল ব্যাকঅফ (exponential backoff) পদ্ধতি ব্যবহার করতে হবে: কোনো একটি পেজে বার বার যাওয়ার পরও যদি সেটিতে কোনো আপডেট আসতে না দেখা যায়, তবে সেই পেজটি রি-ক্রল করার সময় ব্যবধান আরও বাড়িয়ে দিতে হবে। অন্যদিকে প্রতিদিন আপডেট হয় এমন পেজগুলোকে (যেমন নিউজ সাইট) আরও দ্রুত রি-ক্রল করতে হবে।