Web Crawler Sistem Tasarımı: URL Frontier, Nezaket ve Tekilleştirme

Bir crawler basit görünür: bir sayfayı indir, linklerini çıkar, onları indir, tekrarla. Döngü olarak yazıldığında bin sayfa için çalışır. Bir milyar sayfada ise öğretici şekillerde çöker: Küçük sitelere yüzlerce paralel istekle yüklenir, aynı sayfayı elli farklı URL altında indirir, sonsuz bir takvimde kaybolur ve zamanının çoğunu DNS beklemekle geçirir.

Bu yazı ölçeklenen ve nazik kalan bir crawler tasarlıyor: kapasite rakamları, öncelik ve host başına kuyruklarla URL frontier, RFC 9309 ile standartlaşan robots.txt, URL ve içerik tekilleştirme, crawler tuzakları ve bunların etrafındaki bileşenler; tüm döngünün diyagramıyla.

Gereksinimler ve rakamlar

Hedef: Bir arama ya da analitik indeksi için ayda yaklaşık bir milyar sayfa taramak, önemli sayfaları daha sık yenilemek ve hiçbir web sitesine aşırı yük bindirmemek.

En önemli satır sonuncusudur. Keşif, indirmeyi büyük bir farkla geride bırakır; bu yüzden crawler sürekli neyi indirmeyeceğini seçer. Önceliklendirme bir optimizasyon değil, temel bir özelliktir.

Tarama döngüsü

1. Frontier'dan sıradaki URL'yi alın.
2. Host'unun robots.txt dosyasını önbellekten kontrol edin.
3. Host adını yerel bir DNS önbelleğinden çözümleyin.
4. Host'un nezaket gecikmesine uyarak sayfayı indirin.
5. Ham yanıtı saklayın.
6. Ayrıştırın, linkleri çıkarın ve normalleştirin.
7. Daha önce görülen linkleri atın; kalanları bir öncelikle frontier'a ekleyin.
8. İçeriğin parmak izini alın ve sonraki işlemlerde neredeyse aynı olanları atlayın.

İlkinden sonraki her adım, saf bir crawler'ın emek israf ettiği ya da zarar verdiği bir yerdir.

URL frontier

Frontier bir crawler'ın kalbidir: aynı anda iki farklı soruyu yanıtlaması gereken bir kuyruk. Hangi URL en önemli? Ve şu anda hangi host'a bağlanabiliriz?

Klasik yanıt, Introduction to Information Retrieval kitabının URL frontier bölümünde anlatılan Mercator tasarımıdır:

• Ön kuyruklar önceliği yönetir. Bir önceliklendirici, her yeni URL'yi sayfanın ne sıklıkla değiştiği, link popülerliği ya da sitesinin önemi gibi sinyallere göre F kuyruktan birine atar.
• Arka kuyruklar nezaketi yönetir. Her arka kuyruk tam olarak tek bir host'un URL'lerini tutar. Bir heap, her host için ona en erken ne zaman yeniden bağlanılabileceğini kaydeder.
• Bir fetcher iş parçacığı heap'in tepesindeki host'u alır, o host'un arka kuyruğundan bir URL indirir ve host'u yeni bir en erken zamanla heap'e geri koyar. Bir arka kuyruk boşaldığında, yüksek önceliklere ağırlık verilerek ön kuyruklardan yeniden doldurulur.

Mercator'un tasarımcıları, iş parçacıklarının nazik davranılması gereken bir host'u nadiren beklemesi için fetcher iş parçacıklarının kabaca üç katı kadar arka kuyruk önerdi.

Ölçekte frontier'ı host'a göre bölümleyin: Bir frontier shard'ı seçmek için host adını hash'leyin; böylece bir host'un tüm URL'leri tek bir yerde durur ve nezaket, koordinasyon gerekmeden yerel olarak uygulanabilir.

Nezaket ve robots.txt

Nazik bir crawler host başına aynı anda tek bir istek gönderir ve istekler arasında bekler. Aynı bölümden yaygın bir sezgisel kural: O host'tan son indirmenin sürdüğünün yaklaşık on katı kadar bekleyin; böylece yavaş sunucular otomatik olarak daha fazla nefes alır. 429 ve 503 yanıtlarında daha da geri çekilin ve varsa Retry-After başlığına uyun.

robots.txt 2022'de RFC 9309 ile standart hâline geldi. Bir crawler'ın doğru yapması gereken kurallar:

4xx ile 5xx arasındaki asimetri insanları şaşırtır: Eksik bir dosya “devam et” anlamına gelir, ama bir sunucu hatası “uzak dur” demektir, çünkü crawler kuralların ne diyeceğini bilemez. Crawl-delay RFC 9309'un parçası değildir ve crawler'lar ona uyup uymama konusunda farklılık gösterir. Crawler'ınızı, iletişim bilgileri içeren bir URL barındıran açıklayıcı bir user agent ile tanıtın.

URL'leri tekilleştirmek

Aynı sayfa birçok URL'nin arkasına saklanır: HTTP://Example.com:80/a/./b?utm_source=x#top ve http://example.com/a/b tek bir sayfadır. Bir URL'nin görülüp görülmediğini kontrol etmeden önce normalleştirin:

• RFC 3986 bölüm 6'yı izleyerek şemayı ve host'u küçük harfe çevirin, varsayılan portları atın, . ve .. segmentlerini çözümleyin ve yüzde kodlamasını normalleştirin.
• Sunucuya hiç ulaşmayan fragmanı atın.
• utm_* gibi bilinen izleme parametrelerini dikkatle kaldırın; diğer parametreler içeriği değiştirebilir.
• İndirdikten sonra rel="canonical" ipuçlarına uyun.

Ardından görülmüş URL kümesini kontrol edin. Milyarlarca URL ile olağan seçim bir Bloom filtresidir. %1 yanlış pozitif oranında bir milyar URL için boyutlandırıldığında URL başına yaklaşık 9,6 bit, toplamda kabaca 1,2 GB ve yedi hash fonksiyonu gerektirir. Yanlış pozitif, aslında görmediğiniz bir URL'yi atlamak demektir; çoğu tarama için %1'de kabul edilebilir bir bedel. Site haritası girdileri gibi kaçırmamanız gereken URL'ler için kesin bir depo tutun.

İçeriği tekilleştirmek

Aynalar, yazdırma dostu sürümler ve oturum parametreleri, farklı URL'ler altında aynı ya da neredeyse aynı sayfalar üretir. Tam kopyalar kolaydır: Normalleştirilmiş içeriği hash'leyip karşılaştırın. Neredeyse aynı olanlar, sayfa az değiştiğinde az değişen bir parmak izi gerektirir. Standart teknik simhash'tir: Benzer dokümanların birkaç bitte farklılaştığı 64 bitlik bir parmak izi. Google araştırmacıları 2007'de, sekiz milyar sayfalık bir depo için üç farklı bit eşiğiyle 64 bitlik simhash parmak izlerinin neredeyse aynı sayfaları tespit etmekte pratik bir ayar olduğunu bildirdi.

Crawler tuzakları

Bazı siteler, çoğu zaman kazara, sonsuz URL uzayları üretir: sonsuza dek “sonraki ay” linki olan takvimler, her URL'de oturum kimlikleri, her filtre kombinasyonuyla yönlü arama ve yolu büyütmeye devam eden göreli linkler. Savunmalar:

• URL uzunluğuna ve yol derinliğine sınır koyun.
• Tarama döngüsü başına host başına sayfa sayısına, host'un önemine göre ölçeklenmiş bir sınır koyun.
• /a/b/a/b/a/b gibi tekrarlanan yol segmentlerini tespit edin.
• İçerik parmak izleri elinizdeki sayfalarla eşleşmeye devam eden URL'lerin önceliğini düşürün.

Site haritaları ters yönde yardımcı olur: Bir sitenin taranmasını istediği URL'leri listeler; site haritası dosyası başına en fazla 50.000 URL ya da sıkıştırılmamış 50 MB, daha fazlası için site haritası indeks dosyaları.

Döngünün etrafında: DNS, depolama ve yeniden tarama

• DNS gizli bir darboğazdır. Saniyede yüzlerce indirmede, fetcher'lara yakın paylaşılan bir önbellekli çözümleyici her sorgunun yukarı akışa gitmesini önler.
• Depolama. Ham yanıtları büyük toplu dosyalar hâlinde nesne depolamaya yazın; ayrıştırılmış metni ve linkleri bir akış üzerinden indekslemeye gönderin.
• Yeniden tarama. Sayfalar farklı hızlarda değişir. Her sayfanın önceki ziyaretlerde ne sıklıkla değiştiğini izleyin ve bir sonraki indirmesini buna göre planlayın; If-Modified-Since ya da ETag ile koşullu istekler, hiçbir şey değişmediğinde bant genişliğinden tasarruf sağlar.
• JavaScript ağırlıklı sayfalar headless bir tarayıcı gerektirir ve bu, sayfa başına çok daha pahalıdır. Yalnızca buna ihtiyaç duyan host'ları render edin.

Web crawler diyagramı

Nasıl okunur:

• Çerçeve URL frontier'dır: Öncelik kuyrukları, nezaketi uygulayan host başına kuyrukları besler.
• Fetcher'lar host başına aynı anda tek bir URL alır, robots.txt önbelleğine ve DNS önbelleğine bakar ve internetten indirir.
• Ham sayfalar nesne deposuna gider. Parser linkleri ve metni çıkarır.
• Yeni linkler görülmüş URL filtresinden geçer, sonra frontier'a döner ve döngü kapanır. İçerik parmak izleri neredeyse aynı sayfaları işaretler.
• Ayrıştırılmış sayfalar sağdaki akış üzerinden indekslemeye akar.
• Markdown bloğu kapasite rakamlarını ve nezaket kurallarını listeler.

Döngülü hatları çizmek

• Döngüyü görünür kılın. Bir crawler bir çevrimdir; onu düz bir hat olarak çizmek, tuzak ve kopya sorunlarına yol açan geri beslemeyi gizler.
• Nezaketin nerede uygulandığını gösterin. Host başına kuyrukları dipnota değil, resmin içine koyun.
• Önbellekleri önbellek olarak işaretleyin. robots.txt ve DNS önbellekleri dış dünyadaki yükü değiştirir; sürelerini etiketleyin.
• Kenarlara rakam koyun: içeri giren saniyedeki sayfa, dışarı çıkan sayfa başına link.

Genel yöntem için sistem tasarımı diyagramı örneğine bakın. Her host'a yönelik hız kontrolü rate limiter sistem tasarımıyla aynı fikirleri kullanır; taramadan sonraki işleme ise veri hattı mimari diyagramına benzer.

Archboard'da oluşturun

1. Google ya da GitHub ile giriş yapın ve bir diyagram oluşturun.
2. URL frontier adlı bir Temel Çerçeve ekleyin ve içine Veri paketinden iki Kuyruk düğümü koyun: öncelik kuyrukları ve host başına kuyruklar.
3. Fetcher'lar için Bulut paketinden bir Hesaplama düğümü, Ağ paketinden bir DNS düğümü ve bir İnternet düğümü, robots.txt önbelleği için de Veri paketinden bir Redis düğümü ekleyin.
4. Ham sayfalar için Veri paketinden bir Nesne deposu ve parser için bir Hesaplama düğümü daha ekleyin.
5. Görülmüş URL filtresi için ikinci bir Redis düğümü, içerik parmak izleri için Bulut paketinden bir Yönetilen veritabanı ve indekslemeye giden sayfalar için Veri paketinden bir Kafka düğümü ekleyin.
6. Döngüyü etiketli kenarlarla çizin ve Temel paketinden rakamları içeren bir Markdown bloğu ekleyin.

Örnek 13 diyagram düğümü kullanıyor ve Free planın sınırları içinde kalıyor.

SSS

URL frontier nedir? Bir crawler'ın sırada neyi indireceğine karar veren veri yapısıdır. URL'leri öneme göre sıralayan öncelik kuyruklarını, crawler'ın hiçbir host'a çok sık bağlanmasını önleyen host başına kuyruklar ve bir zamanlamayla birleştirir.

Crawler'lar nasıl nazik kalır? Host başına aynı anda tek bağlantı, sunucunun yanıt süresiyle büyüyen istekler arası bir gecikme, 429 ve 503 yanıtlarında geri çekilme ve robots.txt'ye uyma.

robots.txt hata döndürürse ne olur? RFC 9309'a göre 4xx durum kodu crawler'ın siteyi tarayabileceği anlamına gelir; 5xx durum kodu ya da ağ hatası ise dosyayı okuyabilene kadar her şeyin yasak olduğunu varsayması gerektiği anlamına gelir.

Crawler'lar aynı sayfayı iki kez indirmekten nasıl kaçınır? URL'leri normalleştirip çoğunlukla bir Bloom filtresi olan görülmüş URL kümesine karşı kontrol ederler; içeriğin de tam hash'ler ve simhash ile parmak izini alarak farklı URL'ler altındaki aynı sayfayı yakalarlar.

Bir milyar URL için Bloom filtresi ne kadar büyük olmalı? %1 yanlış pozitif oranı için URL başına kabaca 9,6 bit ve yedi hash fonksiyonu kullanarak yaklaşık 1,2 GB. Daha düşük hata oranları girdi başına daha fazla bit gerektirir.

Ücretsiz başlayın — tek kullanıcı, kredi kartı gerekmez.