Jawaban singkat untuk pertanyaan yang paling sering diajukan pembaca tentang topik ini.
Bagaimana mendesain web crawler yang scalable? Desain lengkap: URL frontier, robots.txt menurut RFC 9309, dedup, DNS caching, crawler trap dan jadwal recrawl.
Matthews Wong
Software Engineer
Ringkasan Utama
Untuk mendesain web crawler yang scalable, pisahkan URL frontier menjadi priority queue dan politeness queue per host, patuhi robots.txt menurut RFC 9309, normalisasi URL dan fingerprint konten untuk membuang duplikat, cache DNS, batasi crawler trap dengan budget depth dan host, lalu jadwalkan recrawl sesuai laju perubahan. Hitung semuanya dari pages per second.
Versi pertama sebuah crawler selalu berupa loop: ambil URL, fetch, ekstrak link, masukkan kembali ke antrean. Ini jalan di situs demo, tetapi gagal di web sungguhan dengan empat cara yang mudah ditebak. Ia membanjiri satu host, mengambil halaman yang sama dari enam alamat, tersesat di kalender yang tidak pernah berakhir, dan sudah basi begitu selesai berjalan.
Ini desain berbasis perhitungan, bukan laporan benchmark, dan saya belum pernah menjalankan crawler miliaran halaman. Setiap angka di bawah diturunkan dari asumsi yang disebut di awal, fakta protokolnya berasal dari RFC 9309, RFC 3986 dan buku Stanford IR, dan bagian yang paling layak dibangun pertama di satu VPS, yaitu politeness queue, ditulis dalam TypeScript dan sudah dijalankan pada beberapa URL untuk memeriksa perilakunya.
Crawler adalah empat loop yang saling terhubung: pilih URL, fetch dengan sopan, ekstrak link dan konten, lalu putuskan apa yang di-fetch berikutnya dan kapan halaman itu di-fetch lagi. Skala datang dari perhitungan seluruh loop, jadi tulis asumsinya dulu. Di sini crawler harus menjaga index satu miliar halaman tetap segar, dengan 10% halaman berubah harian, 30% mingguan dan 60% bulanan.
Assumed inputs (a design exercise, not a measurement):
index size = 1,000,000,000 pages
average page (HTML) = 100 KB
fetch latency = 0.5 s (DNS cached, connection setup included)
change classes = 10% daily, 30% weekly, 60% monthly (30 days)
stored copy, compressed = 25% of raw
Fetches per day (every page revisited at its own cadence)
daily class = 100,000,000 / 1 = 100,000,000
weekly class = 300,000,000 / 7 = 42,857,143
monthly class = 600,000,000 / 30 = 20,000,000
total = 162,857,143 per day
Rate
average pages / s = 162,857,143 / 86,400 = 1,885
connections in flight = 1,885 x 0.5 s = 942 (Little's law: rate x latency)
bandwidth = 1,885 x 100 KB = 188.5 MB/s = 1.51 Gbit/s
raw ingest per day = 162,857,143 x 100 KB = 16.3 TB
Storage
snapshot, raw = 1e9 x 100 KB = 100 TB
snapshot, compressed = 100 TB x 25% = 25 TBBentuk hasilnya lebih penting daripada angkanya. Hanya 10% halaman yang berubah harian, tetapi mereka menghasilkan 100 juta dari 162,9 juta fetch per hari, sekitar 61%, jadi kebijakan recrawl, bukan discovery, yang menentukan biaya Anda. Dan 942 koneksi in flight berarti fetcher kebanyakan menunggu jaringan, sehingga lebih cocok dijalankan sebagai banyak worker ringan daripada sedikit worker berat.
Ini asumsi yang saya pilih untuk latihan desain, bukan hasil pengukuran crawler nyata. Ubah satu dan blok di atas bisa dihitung ulang dalam semenit: kecilkan rata-rata halaman jadi 50 KB maka bandwidth turun separuh menjadi sekitar 94 MB/s, dan gandakan frekuensi revisit setiap kelas maka fetch rate ikut berlipat dua.
URL frontier adalah struktur data yang menjawab apa yang harus di-fetch berikutnya. Buku Stanford IR membaginya dua: front queue menangani prioritas dan back queue menangani politeness. Sebuah prioritiser memberi tiap URL angka bulat 1 sampai F, misalnya dari seberapa sering halaman berubah, lalu URL mengalir dari front queue ke back queue, yang masing-masing hanya berisi URL dari satu host.
Back queue dipasangkan dengan heap yang menyimpan waktu paling awal sebuah host boleh dihubungi lagi. Worker mengambil root, menunggu bila perlu, fetch, lalu memasukkan kembali queue dengan waktu baru. Buku itu menyarankan jeda sekitar sepuluh kali durasi fetch terakhir dari host tersebut. Snippet di bawah adalah versi ringkas dari ide itu: satu queue per host, jeda minimum, aturan 10x, dan host yang sedang dikerjakan ditandai tidak tersedia sampai done dipanggil, sehingga dua worker tidak pernah menghantam host yang sama bersamaan.
type HostQueue = { host: string; urls: string[]; nextAllowedAt: number };
export class PolitenessScheduler {
private hosts = new Map<string, HostQueue>();
private minGapMs: number;
private gapFactor: number;
// Gap after a fetch = max(minGapMs, gapFactor x how long that fetch took).
constructor(minGapMs = 1000, gapFactor = 10) {
this.minGapMs = minGapMs;
this.gapFactor = gapFactor;
}
enqueue(url: string): void {
const host = new URL(url).host;
const q = this.hosts.get(host) ?? { host, urls: [], nextAllowedAt: 0 };
q.urls.push(url);
this.hosts.set(host, q);
}
// Returns a URL, or how long to sleep, or null when everything is drained.
// Linear scan for clarity; at scale this is a min-heap keyed on nextAllowedAt.
next(now: number): { url: string } | { waitMs: number } | null {
let earliest = Infinity;
for (const q of this.hosts.values()) {
if (q.urls.length === 0) continue;
if (q.nextAllowedAt <= now) {
// In flight: unavailable until done() runs, so two workers never share a host.
q.nextAllowedAt = Infinity;
return { url: q.urls.shift()! };
}
earliest = Math.min(earliest, q.nextAllowedAt);
}
return earliest === Infinity ? null : { waitMs: earliest - now };
}
done(url: string, fetchMs: number, now: number): void {
const q = this.hosts.get(new URL(url).host);
if (!q) return;
q.nextAllowedAt = now + Math.max(this.minGapMs, this.gapFactor * fetchMs);
if (q.urls.length === 0) this.hosts.delete(q.host);
}
}
// Run against a.com/1, a.com/2, b.com/1 with a 500 ms fetch finishing at t = 500:
// next(0) -> a.com/1 next(0) -> b.com/1 next(0) -> null
// next(600) -> { waitMs: 4900 } (a.com is cooling down for 5,000 ms)
// next(5500) -> a.com/2Sekarang hitung ukurannya. Jumlah back queue adalah titik di mana frontier diam-diam gagal, jadi turunkan dari rate dan jeda sebelum memilih angka.
Politeness gap = 10 x 0.5 s fetch = 5 s -> each host serves 1 / 5 = 0.2 pages per second
Back queues needed = 1,885 pages/s x 5 s = 9,425
Mercator rule of thumb = 3 x 942 threads = 2,826 queues
what those can sustain = 2,826 x 0.2 = 565 pages/s (30% of the target)
With a fixed 1 s gap = 1,885 pages/s x 1 s = 1,885 queuesBlok itu menunjukkan jebakan sizing. Aturan praktis Mercator yang dikutip buku itu adalah sekitar tiga back queue per thread crawler, tetapi dengan jeda 10x rasio itu terlalu kecil untuk beban ini: 2.826 queue hanya sanggup 565 halaman per detik, 30% dari target 1.885. Hitung jumlah queue dari rate dikali jeda, lalu cocokkan dengan jumlah host berbeda yang benar-benar siap, karena frontier yang penuh satu situs besar akan membuat yang lain kelaparan.
Aturan sizing: jumlah back queue yang dibutuhkan sama dengan target pages per second dikali politeness gap dalam detik. Periksa ini lebih dulu, karena frontier yang terlalu sempit terlihat persis seperti jaringan yang lambat.
robots.txt adalah request pertama ke setiap host, dan RFC 9309 mendefinisikan apa yang harus dilakukan crawler untuk setiap kemungkinan respons. Fetch file itu sebelum hal lain di host tersebut, cache hasilnya, dan perlakukan status respons sebagai bagian dari aturan, bukan error yang di-retry begitu saja.
| Respons | Kata RFC 9309 | Yang dilakukan crawler |
|---|---|---|
| 2xx, file ditemukan | Parse file itu; batas parsing HARUS minimal 500 kibibyte | Terapkan grup untuk product token Anda, kalau tidak ada pakai grup bintang; aturan yang paling spesifik menang |
| 3xx, redirect | SEBAIKNYA mengikuti minimal lima redirect berturut-turut | Ikuti sampai lima lompatan; lebih dari itu file BOLEH dianggap tidak tersedia |
| 4xx, tidak tersedia | Crawler BOLEH mengakses semua resource di server | Crawl seolah tidak ada aturan |
| 5xx atau tidak terjangkau | Crawler HARUS menganggap semuanya dilarang | Jangan fetch apa pun dari host itu sampai request robots.txt berhasil |
Pencocokan memakai kespesifikan: match dengan octet terbanyak HARUS dipakai, dan grup user-agent dipilih lewat product token tanpa membedakan huruf besar kecil, dengan fallback ke grup bintang. RFC menyebut crawler SEBAIKNYA tidak memakai salinan cache lebih dari 24 jam kecuali file tidak terjangkau, jadi jadwalkan refresh, jangan cache selamanya. Pada contoh di bawah, Allow /cart/help (10 octet) mengalahkan Disallow /cart/ (6 octet).
# https://shop.example/robots.txt
User-agent: MWBot
Disallow: /cart/
Allow: /cart/help
Disallow: /search
User-agent: *
Disallow: /private/
Sitemap: https://shop.example/sitemap.xml
# MWBot asks for /cart/help: Allow (10 octets) beats Disallow /cart/ (6 octets) -> allowed.
# MWBot asks for /cart/items: only Disallow /cart/ matches -> blocked.
# Any other bot falls back to the * group: /private/x is blocked, /search is allowed.RFC 9309 tidak mendefinisikan Crawl-delay, jadi jeda per host adalah kebijakan Anda sendiri, bukan bagian protokol; jeda dari bagian frontier tadi adalah tempat kebijakan itu berada. Parse seperlunya juga: batasnya minimal 500 kibibyte, jadi file yang lebih besar boleh dipotong oleh crawler.
robots.txt adalah konvensi untuk crawler yang mau bekerja sama, bukan access control. File itu publik dan memuat persis path yang ingin dihindari pemiliknya, jadi apa pun yang harus tetap privat butuh authentication, bukan baris Disallow.
Ada dua pertanyaan di sini: apakah saya sudah melihat alamat ini, dan apakah saya sudah melihat konten ini di alamat lain. Jawab yang pertama dengan murah dan sedini mungkin lewat normalisasi URL. RFC 3986 mendefinisikan kesetaraan yang terlewat oleh perbandingan string biasa: scheme dan host tidak membedakan huruf besar kecil, path kosong setara dengan satu slash, dot-segment diselesaikan, port default boleh dibuang, dan karakter unreserved yang di-percent-encode seperti %7E dan tilde menunjuk resource yang sama.
const DROP_PARAMS = /^(utm_[a-z]+|fbclid|gclid|sessionid|phpsessid)$/i;
// RFC 3986 section 6.2.2.2: %7E and ~ are the same resource, and hex digits are
// case-insensitive. The URL parser leaves both alone, so do it by hand.
const UNRESERVED = /[A-Za-z0-9._~-]/;
function normalisePercent(s: string): string {
return s.replace(/%([0-9a-fA-F]{2})/g, (_, hex: string) => {
const ch = String.fromCharCode(parseInt(hex, 16));
return UNRESERVED.test(ch) ? ch : "%" + hex.toUpperCase();
});
}
export function normaliseUrl(raw: string, base?: string): string | null {
let u: URL;
try {
u = new URL(raw, base); // resolves relative links against the page they came from
} catch {
return null;
}
if (u.protocol !== "http:" && u.protocol !== "https:") return null; // mailto:, javascript:
u.pathname = normalisePercent(u.pathname);
u.hash = ""; // fragments never reach the server
u.username = "";
u.password = "";
const kept = [...u.searchParams.entries()]
.filter(([name]) => !DROP_PARAMS.test(name))
.sort(([a], [b]) => (a < b ? -1 : a > b ? 1 : 0));
u.search = "";
for (const [name, value] of kept) u.searchParams.append(name, value);
return u.href;
}
// normaliseUrl("HTTP://Example.COM:80/a/./b/../c?b=2&utm_source=x&a=1#top")
// -> "http://example.com/a/c?a=1&b=2"
// normaliseUrl("https://example.com") -> "https://example.com/"
// normaliseUrl("../x?z=1&a=2", "https://example.com/p/q/r")
// -> "https://example.com/p/x?a=2&z=1"
// normaliseUrl("https://example.com/%7euser/%e4") -> "https://example.com/~user/%E4"
// normaliseUrl("mailto:a@b.c") -> nullURL parser bawaan platform menangani huruf host, port default, dot-segment dan path kosong. Snippet menambahkan tiga hal yang tidak ditangani: normalisasi percent-escape, membuang daftar pendek parameter tracking dan session, serta mengurutkan parameter sisanya agar dua urutan menjadi satu. Daftar buang itu adalah pilihan kebijakan. Membuang parameter yang memang mengubah halaman berarti kehilangan konten, jadi kembangkan daftarnya dari trap yang Anda amati, bukan dari tebakan.
| Teknik | Pertanyaan yang dijawab | Yang tertangkap | Yang terlewat |
|---|---|---|---|
| String URL ternormalisasi | Sudahkah saya melihat alamat persis ini? | Huruf besar kecil, fragment, port default, dot-segment, urutan parameter | Alamat berbeda yang menyajikan halaman sama; paling boros memori |
| Fingerprint URL 64-bit | Pertanyaan yang sama dalam 8 byte per URL | Semua yang tertangkap oleh set string | Satu collision diam-diam membuang URL yang asli |
| Bloom filter | Kemungkinan besar sudahkah saya melihat alamat ini? | Sama seperti set, dengan sekitar 15% memori fingerprint | False positive melewatkan sekitar 1% URL baru selamanya; entri tidak bisa dihapus |
| Content hash | Apakah isi ini identik byte demi byte dengan yang saya simpan? | Mirror dan satu halaman yang bisa dibuka lewat banyak URL | Satu byte berubah sudah menggagalkannya, jadi timestamp atau iklan merusaknya |
| Simhash | Apakah isi ini hampir identik dengan yang saya simpan? | Boilerplate, counter dan edit kecil | Butuh ambang Hamming distance yang harus Anda tuning |
Normalisasi memperkecil set, tetapi URL berbeda tetap bisa menyajikan halaman yang sama, jadi fingerprint kontennya juga. Hash dari teks utama hasil ekstraksi menangkap salinan persis, dan simhash menangkap salinan hampir sama. Manku, Jain dan Das Sarma memaparkan simhash untuk deteksi near-duplicate pada web crawling di WWW 2007: dokumen yang mirip menghasilkan fingerprint dengan Hamming distance kecil, sehingga pengujiannya membandingkan bit, bukan teks. Ambangnya adalah keputusan tuning, jadi beri label beberapa ratus pasangan dari crawl Anda sendiri dan pilih ambang dari situ.
Assumed: 10,000,000,000 distinct URLs discovered (10x the 1 billion indexed).
Average URL = 80 bytes (assumed).
Exact set of strings = 10e9 x 80 B = 800 GB
64-bit URL fingerprints = 10e9 x 8 B = 80 GB
Bloom filter, 1% false pos. : bits per URL = -ln(0.01) / (ln 2)^2 = 4.605 / 0.4805 = 9.58
10e9 x 9.58 bits = 95.8e9 bits = 12.0 GB
Page content hash (SHA-256) = 1e9 x 32 B = 32 GB
Page simhash (64-bit) = 1e9 x 8 B = 8 GB
Fingerprint collisions, birthday approximation n^2 / 2N with N = 2^64 = 1.845e19:
(1e10)^2 / (2 x 1.845e19) = 1e20 / 3.69e19 = about 2.7 colliding pairs in 10 billion URLs
Bloom false positives: up to 1% of 10e9 = about 100 million new URLs wrongly skipped.Baris Bloom filter layak mendapat satu kalimat lagi. Ia menukar false-positive rate yang diketahui dengan memori, dan setiap false positive adalah URL yang tidak pernah Anda crawl. Di sini pertukarannya 12 GB lawan 80 GB, yang mungkin cukup untuk search index dan keliru untuk arsip kepatuhan; cara kerja filter di dalamnya di luar cakupan post ini.
Setiap host baru memicu satu DNS lookup, dan fetcher naif membayarnya di setiap request. Cache jawaban per host selama TTL record, simpan negative cache singkat untuk nama yang gagal, dan kelompokkan fetch per host supaya satu lookup melayani banyak halaman, yang sudah dilakukan frontier dengan satu queue per host. Resolve lewat proses Anda sendiri atau local caching resolver agar lookup tidak mengantre di belakang trafik lain.
DNS
no cache, one lookup per fetch = 1,885 lookups / s
per-host cache, 20 pages per host visit = 1,885 / 20 = 94 lookups / s
in flight at an assumed 100 ms per lookup = 94 x 0.1 = about 9
One large site, 1,000,000 pages, one request in flight at a time
1 request per second = 1,000,000 s / 86,400 = 11.6 days
10x gap on a 0.5 s fetch (5 s per page) = 5,000,000 s / 86,400 = 57.9 daysPerhitungan yang sama menjelaskan mengapa politeness, bukan bandwidth, yang membatasi kecepatan crawl satu situs besar. Paralelisme antar host gratis; paralelisme dalam satu host adalah hal yang tidak boleh Anda beli. Banyak hostname juga bisa berbagi satu server, jadi bila Anda menemukan hal itu, kunci rate limit pada alamat IP hasil resolve selain hostname.
Crawler trap adalah bagian situs yang menghasilkan himpunan URL yang praktis tak terbatas, sengaja atau tidak, sehingga crawler menghabiskan budget di sana. Dedup URL tidak membantu karena setiap URL memang baru. Pertahanannya adalah budget, bukan kecerdikan.
| Trap | Bagaimana munculnya | Pertahanan |
|---|---|---|
| Kalender atau pagination tak terbatas | Link bulan berikutnya yang tidak pernah habis | Batas depth dari seed ditambah budget halaman per host |
| Session ID dan parameter tracking | Satu halaman di bawah URL unik tak habis-habis | Buang parameter yang dikenal dan urutkan sisanya di normaliser |
| Segmen path berulang | Bug relative link yang menghasilkan path seperti a, b, a, b, a, b | Batas panjang URL dan batas segmen berulang |
| Halaman hasil generate | Server mengarang konten untuk path apa pun yang diminta | Budget per host ditambah tingkat duplikat dari content hash |
Gabungkan tiga batas: depth maksimum dari seed, jumlah halaman maksimum per host per hari, dan batas panjang URL. Angka 2.048 karakter adalah plafon sembarang yang Anda tuning, bukan standar. Lalu pantau sinyal yang tidak diberikan satu aturan pun, yaitu persentase fetch pada host yang content hash atau simhash-nya cocok dengan yang sudah tersimpan. Saat melewati ambang yang Anda pilih, turunkan prioritas host itu di priority queue alih-alih memblokirnya, sehingga situs yang memang besar kehilangan prioritas tetapi tidak kehilangan coverage.
Jangan recrawl dengan timer tetap. Sesuaikan interval per URL dari apa yang teramati pada tiap fetch: lebih pendek bila konten berubah, lebih panjang bila tidak. Bab frontier Stanford menyebut riwayat fetch, seperti seberapa sering halaman berubah, sebagai input prioritas, yang merupakan sinyal sama dengan yang dipakai di sini.
state per URL: interval (days), content_hash, etag, next_fetch_at
after each fetch:
if status == 304 or content_hash == stored_hash: # unchanged
interval = min(30, interval * 2)
else: # changed
interval = max(1, interval / 2)
next_fetch_at = now + interval
trace, starting interval 7 days:
unchanged, unchanged, unchanged : 7 -> 14 -> 28 -> 30 (capped at 30)
changed, changed, changed : 7 -> 3.5 -> 1.75 -> 1 (floored at 1)Bandingkan content hash dari teks hasil ekstraksi, bukan HTML mentah, atau iklan yang berganti dan timestamp akan membuat setiap halaman tampak berubah. Bila server menyediakan ETag, kirim kembali sebagai If-None-Match: respons 304 Not Modified didefinisikan oleh RFC 9110 dan tidak membawa body, jadi halaman yang tidak berubah hanya memakan header, bukan 100 KB. Faktor pembagi dan pengali dua adalah kebijakan awal yang saya pilih untuk contoh; tuning batasnya terhadap change log Anda sendiri.
Pisahkan tiga penyimpanan karena pola aksesnya berbeda. Frontier berisi record kecil yang ditulis terus-menerus. Page store besar, hampir selalu append, dan jarang dibaca, jadi cocok di object storage sebagai batch terkompresi: 25 TB untuk snapshot di blok kapasitas. Link graph dan metadata per URL, yaitu hash dan status terakhir, melayani dedup dan scoring. Di satu VPS, frontier bisa dimulai sebagai satu tabel Postgres.
CREATE TABLE urls (
url_hash bigint PRIMARY KEY, -- 64-bit fingerprint of the normalised URL
url text NOT NULL,
host text NOT NULL,
next_fetch_at timestamptz NOT NULL,
interval_s integer NOT NULL DEFAULT 604800, -- 7 days
content_simhash bigint,
status smallint NOT NULL DEFAULT 0 -- 0 = idle, 1 = claimed
);
-- Only idle rows are indexed, so claimed and finished rows cost nothing here.
CREATE INDEX urls_due_idx ON urls (next_fetch_at) WHERE status = 0;
-- Each worker claims a batch; SKIP LOCKED means workers never wait on each other.
UPDATE urls SET status = 1
WHERE url_hash IN (
SELECT url_hash FROM urls
WHERE status = 0 AND next_fetch_at <= now()
ORDER BY next_fetch_at
LIMIT 100
FOR UPDATE SKIP LOCKED
)
RETURNING url, host;Partial index itu menjaga query URL yang jatuh tempo tetap murah, dan FOR UPDATE SKIP LOCKED membiarkan beberapa worker mengklaim baris berbeda tanpa saling menunggu. Batas atasnya adalah hitungan jujur: 50 host in flight dengan jeda 1 detik berarti 50 halaman per detik, 4,32 juta halaman per hari, sekitar 2,7% dari 162,9 juta fetch per hari di blok kapasitas. Itu crawler pribadi yang berguna dan masih jauh dari mesin pencari. Sebelum menjalankannya tanpa pengawasan, periksa daftar ini.
Aturan yang saya bawa dari sini: hitung ukuran crawler dari rate dan jeda, bukan dari jumlah halaman. Pages per second dikali politeness gap menghasilkan jumlah queue, pages per day dikali kadens revisit menghasilkan bandwidth, dan setiap duplikat atau trap yang Anda tolak untuk di-fetch adalah bandwidth yang tersimpan untuk halaman yang benar-benar berubah.
Sumber dan bacaan lanjutan