Web crawling i indeksy

Podstawowe operacje
clawrera



Zacznij od znanych “ziaren” URL-i



Pobierz je do pamięci i parsuj



Pobierz URL-e, na które wskazują



Umieść pobrane URL-e w kolejce



Pobierz każdy URL z kolejki i
powtarzaj

Obraz crawlingu

Web

URL-e pobrane
i parsowane

Graniczne URL-e

Ukryty Web

Strony

ziarna

Prosty obraz – komplikacje



Web crawling nie jest wykonalny za pomocą jednej

maszyny



Wszystkie powyższe etapy są rozproszone



Złośliwe strony



Strony ze spamem



Pułapki na pająki – również te generowane dynamicznie



Nawet niezłośliwe strony stawiają wyzwania



Czas oczekiwania/pasmo dla zdalnych serwerów się

zmienia



Warunki webmasterów



Jak “głęboko” możesz wchodzić w hierachię URL-i strony?



Zwierciadła stron i duplikaty stron



Uprzejmość – nie trafiaj w dany serwer zbyt często

Co każdy serwer musi robić



Być Uprzejmym: Respektować
pośrednie i bezpośrednie uprzejme
czynniki



Wykonywać crawling tylko
udostepnionych stron



Respektować robots.txt (później
będzie)



Być Mocnym: Być odpornym na pułapki
na pająki i inne złośliwe zachowania ze
strony serwerów webowych

Co każdy crawler powinien
robić



Być przygotowany do rozproszonych
operacji: zaprojektowany do
przetwarzania na wielu rozproszonych
maszynach



Być skalowalny: zaprojektowany wzrost
intensywności crawlingu przez
dodawanie dodatkowych maszyn



Wydajność/efektywność: pozwolić na
pełne wykorzystanie dostępnych
procesów i zasobów sieciowych

Co każdy clawler powinien
robić



Pobierać jako pierwsze strony
“wysokiej jakości”



Ciągłe operacje: Kontynuować
pobieranie nowych kopii
sprowadzanych już stron



Rozszerzać możliwości: adaptować
się do nowych formatów danych,
protokołów

Uaktualniony obraz crawlingu

URL-e pobierane
i parsowane

Ukryty Web

Strony ziarna

Graniczne

URL-e

Nić pająków

Graniczne URL-e



Mogą zawierać wiele stron z tego
samego hosta



Muszą unikać próby pobierania ich
w tym samym czasie



Muszą próbować obciążać
wszystkie nitki pająków

Uprzejmość explicite i implicite



Uprzejmość explicite: specyfikacja
przez webmasterów, które obszary
strony mogą być crawlowane



robots.txt



Uprzejmość implicite: nawet przy
braku specyfikacji unikaj trafiania
na daną stronę zbyt często

Robots.txt



Protokół ograniczający dostęp pająków
(“robots”) pochodzi z roku 1994



www.robotstxt.org/wc/norobots.html



Strona webowa określa swoje
wymagania co może (nie może) być
pobierane



Dla URL tworzony jest zbiór
URL/robots.txt



Tan zbiór określa ograniczenia dostępu

Przykład robots.txt



Żaden robot nie może odwiedzać URL-i
zaczynających się "/yoursite/temp/” za
wyjątkiem robota o nazwie
“searchengine":

User-agent: *
Disallow: /yoursite/temp/

User-agent: searchengine
Disallow:

Kroki przetwarzania w
crawlingu



Wybierz URL z granicznych URL-i



Pobierz dokument z tego URL-a



Parsuj tenURL



Pobierz linki od niego do innych docs (URLs)



Sprawdź czy URL ma już przejrzaną treść



Jeśli nie to dodaj do indeksu



Dla każdego pobranego URL-a



Upewnij się, że przeszedł on test dla filtru URL-a



Sprawdź, czy jest już w granicy (eliminacja
duplikatów URL-i)

Np.: only crawl .edu,

obey robots.txt, etc.

Który?

Podstawowa architektura
crawlera

WWW

DNS

Parsuj

Zawartość

znana?

Doc

FP’s

Elim.

Dupl.

URL

Zbiór
URL-i

Frontowe URL

Filtr

URL-a

Filtry

robotów

Pobierz

DNS (Domain Name Server)



Usługa przeglądania Internetu



Dla danego URL-a znajduje jego adres IP



Usługa udostępniana przez rozproszony zbiór
serwerów – więc opóźnienie przeglądania może
być duże (nawet sekundy)



Powszechnie stosowane implementacje OS
przeglądania DNS są blokowane: tylko
jedno szczególne żądanie za jednym razem



Rozwiązania



Caching DNS



Batch DNS resolver – grupowanie zgłoszeń i
wysyłanie ich razem

Parsowanie: normalizacja URL-i



Podczas, gdy pobierany dokument jest
parsowany niektóre linki względnymi URL-ami



Np.: na http://en.wikipedia.org/wiki/Main_Page

występuje względny link do

/wiki/Wikipedia:General_disclaimer który jest
taki sam jak bezwzględny

http://en.wikipedia.org/wiki/Wikipedia:General_disclaimer



W trakcie parsowania takie względne URL-e
muszą być znormalizowane (rozszerzone)

Czy treść była przeglądana?



Duplikaty są rozpowszechnione
w Web



Jeśli strona właśnie pobierana
jest już w indeksie nie
przetwarzaj jej dalej



Jest to weryfikowane za
pomocą odcisków dokumentów
lub n-gramów

Filtry i robots.txt



Filtry – wyrażenia regularne dla
URL-i crawling/nie



Jeśli zbiór robots.txt został
pobrany ze strony nie trzeba go
pobierać ponownie



Inaczej mamy burns pasma
prowadzącego do serwera Web



Cache zbiory robots.txt

Eliminacja duplikatów URL



Dla nieciągłego (one-shot)
crawlingu, testuj czy pobrany +
przefiltrowany URL już przedtem
przeszedł do granicy



Dla ciągłego crawlingu – zbadaj
szczegóły implementacji granicy

Rozproszenie crawlera



Przetwarzaj liczne nici crawlera w
różnych procesach – potencjalnie w
różnych węzłach



Geograficznie rozproszonych węzłach



Przydziel badane hosty do węzłów



Do podziału stosujemy haszing



Jak się te węzły komunikują?

Komunikacja między węzłami



Wyjście filtra URL w każdym węźle jest
przesyłane do Eliminat. Zdublowanych
URL-i we wszystkich węzłach

WWW

Pobierz

DNS

Parsuj

Znana

zawartość?

URL

filter

Dup

URL

elim

Doc

FP’s

URL

set

Frontowe URL-e

robots

filters

Host

splitter

To
other
hosts

Od innych
hostów

Graniczne URL-e: dwa główne
czynniki



Uprzejmość: nie trafiaj na serwer

webowy zbyt często



Aktualność: odwiedzaj pewne strony

częściej niż inne



Np.: strony (takie jak News sites) których

treść zmienia się często

Te cele mogą być sprzeczne.
(Np.: prosta kolejka priorytetowa może być

zła – wiele linków ze strony idzie do

własnej witryny co powoduje skoki

dostępów do tej strony.)

Uprzejmość – wyzwania



Nawet jeśli ograniczymy się tylko
do jednej nici pobierającej z hosta
– trafienia mogą się powtarzać



Zwykła heurystyka: ustaw czasowy
odstęp między kolejnymi
żądaniami do hosta jako >> czasu
ostatniego pobrania z tego hosta

Crawler Mercator



Projekt Mercator jest podstawą konstrukcji
wielu naukowych i komercyjnych
crawlerów



Publikacje: Najork and Heydon 2001, 2002

24

Tylny selektor kolejki

B tylnych kolejek

Pojedynczy host na każdej

Nić crawlerów żądających URL

Granica URL-i: schemat
Mercatora

Biased front queue selector

Router koncowych kolejek

System priorytetu

K frontowych kolejek

URL-e

Granica URL-i Mercatora



URL-e wpływają z wierzchołka do frontu



Frontowe kolejki

zarządzają

priorytetami



Końcowe kolejki

zapewniają uprzejmość



Wszystkie kolejki są FIFO

Frontowe kolejki

System priorytetu

1

K

Wstępny selektor kolejki frontowej

Router końcowej kolejki

Kolejki frontowe



System priorytetu przypisuje do URL-a
liczbę całkowitą priorytetu między 1 i K



Dołącza URL do odpowiedniej kolejki



Heurystyki dla przypisania priorytetu



Odtwórz intensywność zbadaną dla
poprzednich pobrań



Specyficzna dla aplikacji (np.: “badaj
strony wiadomości częściej”)

Wstępny selektor kolejki
frontowej



Gdy

tylna kolejka

żąda URL-a (w

opisanej sekwencji): pobierz

frontową

kolejkę,

z której wyciągnij URL



Ten wybór może być round robin
wstępnie dla kolejek o wyższym
priorytecie lub jakiś bardziej
skomplikowany wariant



Może być losowo

Końcowe kolejki

Wstępny selektor frontowej kolejki

Router końcowej kolejki

Selektor końcowej kolejki

1

B

Sterta

Niezmiennie dla końcowej
kolejki



Każda końcowa kolejka jest utrzymywana
niepusta w trakcie procesu crowlingu



Każda końcowa kolejka zawiera jedynie
URL-e z pojedynczego hosta



Utrzymuj tablicę hosty-końcowe kolejki

Nazwa hosta

Końcowa
kolejka

…

3
1
B

Sterta

końcowej kolejki



Jedno wejście dla każdej końcowej kolejki



Wejście jest najwcześniejszym czasem t

e

kiedy host odpowiadający tej końcowej
kolejce może być odwiedzony ponownie



Ten najwcześniejszy czas jest określony
przez



Ostatni dostęp do tego hosta



Jakiś czas wybranej przez nas heurystyki
buforowania

Przetwarzanie końcowej kolejki



Nić pająków szuka URL-a do pobrania:



Znajdź korzeń sterty



Pobierz URL z czoła odpowiedniej końcowej
kolejki q (znajdź w tabeli)



Sprawdź czy kolejka q jest teraz pusta – jeśli
tak, ściągnij URL v z frontowych kolejek



Jeśli istnieje już końcowa kolejka dla hosta v , dodaj v
doq i pobierz inny URL z frontowych kolejek,
powtarzaj



W przeciwnym przypadku dodaj v do q



Jeśli q jest niepusta, twórz dla niej wejście do
sterty

Liczba końcowych kolejek B



Utrzymuj wszystkie nici zajęte stosując
jednocześnie uprzejmość



Rekomendacja Mercatora: Trzy razy
więcej końcowych kolejek niż nici
crawlerów

Serwer połączeń



Wsparcie dla szybkich pytań na grafie webowym



Które URL-e wskazują na dany URL?



Na które URL-e wskazuje dany URL?

Pamięta odwzorowanie w pamięci



URL do linków wyjściowych, URL do linków wejściowych



Zastosowania



Sterownie crawlingiem



Analiza grafu Web



Połączenia, optymizacja crawllngu



Analiza linków

Najważniejsze opublikowane
prace



Boldi and Vigna



http://www2004.org/proceedings/docs/1p595.p
df



Webgraph – zbiór algorytmów i
implementacji w javie



Podstawowy cel – Utrzymywanie list
sąsiednich węzłów w pamięci



Dlatego, kompresowanie list sąsiedztwa
jest krytycznym elementem

Listy sąsiedztwa



To zbiór sąsiadów jakiegoś węzła



Przyjmijmy, że każdy URL jest
reprezentowany przez liczbę całkowitą



Np.: dla 4 miliardów stron webowych
potrzebujemy 32 bitów na węzeł



Nie, wymaga to 64 bitów do
reprezentacji każdego hiperlinka

Kompresja listy sąsiedztwa



Własności wykorzystywane w
kompresji:



Podobieństwo (między listami)



Lokalność (wiele linków z danej
strony idzie do “bliskich” stron)



Używa się kodowania odstępów dla
posortowanych list



Rozkład wartości odstępów

Pamięć



Boldi/Vigna obniżyli średni wynik do ~3
bits/link



(URL to URL edge)



Jak

?

Dlaczego jest to ważne?

Główne idee Boldi/Vigna



Rozpatrzmy listy URL-i uporządkowane
leksykograficznie np.:



www.stanford.edu/alchemy



www.stanford.edu/biology



www.stanford.edu/biology/plant



www.stanford.edu/biology/plant/copyright



www.stanford.edu/biology/plant/people



www.stanford.edu/chemistry

Boldi/Vigna



Każdy z tych URL-i ma jakąś listę sąsiedztwa



Główna idea: zgodnie z szablonem, lista taka dla
węzła jest podobna do jednego z 7
poprzedzających URL-i w porządku
leksykograficznym



Wyraź listę sąsiedztwa w odniesieniu do jednego z
nich



Np.: rozpatrzmy takie listy sąsiedztwa



1, 2, 4, 8, 16, 32, 64



1, 4, 9, 16, 25, 36, 49, 64



1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144



1, 4, 8, 16, 25, 36, 49, 64 (ten czwarty wiersz kodujemy:
taki jak drugi-ale..)

Koduj jak (-2), usuń 9, dodaj

8

dlaczego7

?

Kodowanie przerw



Dla uporządkowanej listy liczb
całkow. x, y, z, …, reprezent. przez
x, y-x, z-y, …



Kompresuj każdą liczbę stosując kod



 code – Liczba bitów

= 1 + 2 lg x



 code: …



Ograniczenie z teorii informacji: 1 + lg

xbits



 code:

działa dobrze dla całkowitych z

prawa potęgowego

Boldi Vigna DCC 2004

Główne zalety BV



Bazuje jedynie na lokalności w uporządkowaniu

Porządek lesykograficzny sprawdza się w Web



Sąsiednie pytania mogą być przetwarzane

bardzo efektywnie



Aby pobierać sąsiadów – śledzi się do tyłu łańcuch

prototypów



Ten łańcuch jest zwykle krótki (ponieważ

podobieństwo jest głównie w obrębie hosta)



Może również bezpośrednio ograniczać długość

łańcucha w trakcie kodowania



To łatwy w implem. jedno-przejściowy algorytm

literatura



Mercator: A scalable, extensible web crawler
(Heydon et al. 1999)



A standard for robot exclusion



The WebGraph framework I: Compression
techniques (Boldi et al. 2004)