Web Crawler ডিজাইন

ভাবো তুমি Google-এর মতো একটা search engine বানাচ্ছো। সবার আগে দরকার এমন একটা bot যা ইন্টারনেটের পেজগুলো ঘুরে ঘুরে পড়ে আনবে—এটাই Web Crawler (বা spider)। আজ আমরা ধাপে ধাপে একটা production-grade crawler ডিজাইন করব।

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

প্রথমেই interviewer-কে জিজ্ঞেস করে scope ঠিক করে নাও। ধরে নিলাম আমরা একটা general-purpose crawler বানাচ্ছি search index তৈরির জন্য।

Functional Requirements:

• কিছু seed URL দিয়ে শুরু করে link ধরে ধরে নতুন পেজ আবিষ্কার করা।
• প্রতিটা পেজ fetch (HTML download) করা।
• HTML পার্স করে নতুন link বের করা এবং content store করা।
• একই URL/একই content বারবার crawl না করা (deduplication)।
• HTML content টাইপ প্রায়োরিটি, পরে চাইলে image/PDF যোগ করা যাবে (extensible)।

Non-functional Requirements:

• Scalability: বিলিয়ন পেজ হ্যান্ডেল করতে হবে।
• Politeness: কোনো website-কে DDoS-এর মতো request দিয়ে ফেলা যাবে না; robots.txt মানতে হবে।
• Robustness: broken HTML, timeout, redirect loop—এসব gracefully handle করতে হবে।
• Freshness: পেজ পরিবর্তন হলে আবার crawl করতে হবে (re-crawl policy)।
• Extensibility: নতুন content type/protocol সহজে যোগ করা যাবে।

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

লক্ষ্য: ১ মাসে ১ বিলিয়ন পেজ crawl করা

পেজ প্রতি সেকেন্ডে (QPS):
  1,000,000,000 পেজ / (30 দিন × 24 ঘণ্টা × 3600 সেকেন্ড)
  ≈ 1,000,000,000 / 2,592,000
  ≈ 386 পেজ/সেকেন্ড  → round করে ~400 QPS

peak ধরি 2x → ~800 QPS

প্রতি পেজের গড় সাইজ ≈ 500 KB (HTML)
সেকেন্ডে download: 400 × 500 KB ≈ 200 MB/s ≈ 1.6 Gbps bandwidth

মাসিক raw storage (শুধু HTML):
  1,000,000,000 × 500 KB = 500 TB / মাস
  compression (~5x) ধরলে ≈ 100 TB / মাস

URL metadata (URL seen set):
  1,000,000,000 URL × ~ধরা যাক 100 bytes hash/metadata = 100 GB
  Bloom filter দিয়ে এটা আরও অনেক কমানো যায় (নিচে দেখব)

সংখ্যাগুলো বলে দিচ্ছে—এটা single machine-এর কাজ না। আমাদের distributed architecture, প্রচুর bandwidth, এবং petabyte-scale storage লাগবে।

৩. API ডিজাইন

Crawler বেশিরভাগই internal system, তবু component-গুলোর মধ্যে clean interface থাকা দরকার।

# Frontier-কে নতুন URL দেওয়া
addUrl(url: string, priority: int, discoveredFrom: string) -> bool

# Worker পরবর্তী crawl-যোগ্য URL নেয়
getNextUrl(workerId: string) -> URLEntry | null

# একটা URL crawl শেষ হলে মার্ক করা
markCrawled(url: string, status: int, contentHash: string) -> void

# Politeness: এই host-এ এখন request করা যাবে কিনা
canFetch(host: string) -> bool   # robots.txt + rate limit চেক

# পার্স করা content সংরক্ষণ
storeContent(url: string, html: bytes, parsedAt: timestamp) -> void

৪. ডেটা মডেল

প্রধান কয়েকটা data structure ও store:

Store / Structure	কী রাখে	প্রযুক্তি (Tech)	কেন
URL Frontier	crawl করার অপেক্ষায় থাকা URL queue	Kafka / Redis-backed queue	high-throughput, priority + politeness queue
URL Seen Set	কোন URL আগে দেখা হয়েছে	Bloom Filter + RocksDB	memory-দক্ষ dedup
Content Store	raw HTML, metadata	S3 / HDFS + blob compression	সস্তা, বিশাল, append-heavy
Document Index	parsed text, link graph	Cassandra / Bigtable	wide-column, write-heavy, scalable
robots.txt Cache	per-host crawl rules	Redis (TTL)	বারবার robots.txt না আনতে

Storage choice কেন? Raw HTML হলো বিশাল ও immutable blob—তাই object storage (S3/HDFS) আদর্শ। Metadata ও link graph-এর জন্য wide-column NoSQL (Cassandra/Bigtable) কারণ write প্রচুর, schema flexible, আর horizontal scale সহজ। RDBMS এখানে bottleneck হয়ে যেত।

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

মূল component এবং তাদের মধ্যে flow:

1. Seed URLs → URL Frontier-এ ঢোকানো হয়।
2. URL Frontier → priority ও politeness অনুযায়ী URL সাজায়।
3. Fetcher / Downloader → Frontier থেকে URL নিয়ে HTTP request করে HTML আনে। আগে canFetch() চেক করে (robots.txt + rate limit)।
4. DNS Resolver → host name → IP (caching সহ, কারণ DNS lookup ব্যয়বহুল)।
5. Parser → HTML থেকে text ও সব link (anchor href) extract করে।
6. URL Seen / Dedup → প্রতিটা নতুন link Bloom filter-এ চেক—আগে দেখা না থাকলে Frontier-এ যোগ।
7. Content Dedup → content-এর hash (যেমন SHA-256) মিলিয়ে দেখা—একই content আলাদা URL-এ থাকলে skip।
8. Storage → raw HTML object store-এ, parsed data index-এ।

Seed URLs
   │
   ▼
[URL Frontier] ──► [Fetcher] ──► [DNS Cache]
   ▲                  │
   │                  ▼
[URL Seen?]◄──[Parser: extract links + text]
(Bloom filter)         │
   │                   ▼
   └─────────── [Content Store + Index]

৬. গভীরে (Deep Dive)

৬.১ URL Frontier ও Politeness

Frontier শুধু একটা সাধারণ queue নয়—এর দুটো কাজ একসাথে সামলাতে হয়: priority (গুরুত্বপূর্ণ পেজ আগে) আর politeness (এক host-এ গায়ে গায়ে request নয়)।

একটা প্রচলিত design হলো দুই স্তরের queue:

• Front queues (priority): prioritizer প্রতিটা URL-কে PageRank/freshness দেখে একটা priority band-এ ফেলে (যেমন ১–১০)।
• Back queues (politeness): প্রতিটা back queue একটা নির্দিষ্ট host-এর URL ধরে রাখে। একটা worker thread একটা back queue-ই নেয়, ফলে এক host-এ একসাথে একাধিক request যায় না। প্রতিটা back queue-র সাথে একটা timestamp থাকে—"এই host-এ পরবর্তী request কখন করা যাবে" (যেমন গত response time-এর ১০x পরে, বা fixed 1s gap)।

robots.txt প্রতিটা host-এর জন্য Redis-এ TTL সহ cache করা থাকে; Disallow path-গুলো crawl করা হয় না। Crawl-delay directive থাকলে সেটাও মানা হয়।

৬.২ Deduplication: Bloom Filter

কোটি কোটি URL-এর মধ্যে "এটা কি আগে দেখেছি?" প্রতিবার ডিস্ক/DB-তে query করা ব্যয়বহুল। সমাধান Bloom filter—একটা probabilistic data structure।

• এটা false positive দিতে পারে (বলবে "দেখেছি" যদিও দেখেনি) কিন্তু কখনো false negative দেবে না।
• ফলে কালেভদ্রে একটা নতুন URL ভুলে skip হতে পারে, কিন্তু একই URL দুবার crawl হওয়ার ঝুঁকি কমে যায়।
• ১ বিলিয়ন URL, ১% false positive rate-এর জন্য Bloom filter লাগবে মাত্র ~১.২ GB RAM—যেখানে full hash set লাগত ১০০ GB+।

নিশ্চিত হওয়ার জন্য Bloom filter "দেখেছি" বললে তখন RocksDB-তে confirm করা যায় (দুই স্তরের চেক)। Content-level dedup-এর জন্য পেজের normalized text-এর hash রাখা হয়, যাতে একই খবর আলাদা URL-এ থাকলেও দুবার index না হয়।

৬.৩ Distributed Crawling ও URL Routing

একাধিক crawler worker চালালে প্রশ্ন: কোন URL কে আনবে? সমাধান—host-এর উপর consistent hashing।

• hash(host) % N দিয়ে নয়, বরং consistent hashing ring ব্যবহার করি, যাতে নতুন worker যোগ/বাদ দিলে সব key re-shuffle না হয়।
• একই host সবসময় একই worker-এ যায় → সেই worker সহজেই per-host rate limit ও robots.txt cache সামলাতে পারে।
• worker-গুলো একটা coordinator (যেমন ZooKeeper/etcd) দিয়ে membership ও health track করে।

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

• DNS resolution: প্রতি request-এ DNS lookup করলে সেটাই bottleneck হয়। সমাধান: aggressive DNS caching + নিজস্ব DNS resolver।
• Frontier-এর size: বিলিয়ন URL মেমরিতে রাখা যায় না। সমাধান: disk-backed queue (Kafka/RocksDB), শুধু hot অংশ মেমরিতে।
• Spider trap / infinite URL: ক্যালেন্ডার সাইটের মতো অসীম dynamically-generated URL crawler-কে আটকে দিতে পারে। সমাধান: per-domain URL limit, URL depth limit, এবং pattern detection।
• Hotspot domain: Wikipedia-র মতো বিশাল সাইট এক worker-কে ভারী করে দিতে পারে। সমাধান: বড় host-কে sub-shard করা।
• Bandwidth: ১.৬ Gbps টানতে multiple data center/region-এ fetcher ছড়িয়ে দেওয়া।
• Re-crawl/Freshness: পেজের change frequency estimate করে priority adjust—নিউজ সাইট ঘণ্টায়, static blog মাসে একবার।

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

একটা production crawler-এর মূল স্তম্ভ চারটা: smart URL Frontier (priority + politeness), memory-দক্ষ dedup (Bloom filter), কঠোর politeness (robots.txt + per-host rate limit), এবং distributed coordination (host-based consistent hashing)। Raw HTML object store-এ আর link graph wide-column DB-তে—এই storage split-টাই scale ধরে রাখে।