Università degli Studi di Padova
Facoltà di Scienze MM.FF.NN.
Corso di Laurea Specialistica in Informatica
Seminario per il corso di Sistemi Informativi
Studente: Daniele Brognara
Anno Accademico: 2006/2007
Riferimenti Bibliografici
• Libri
 Soumen Chakrabarti, Morgan Kaufmann – Mining the Web –
San Francisco, US, 2003. Disponibile alla Biblioteca di Statistica.
• Articoli e pagine Web
http://oak.cs.ucla.edu/~cho/papers/cho-toit01.pdf
http://gatekeeper.research.compaq.com/pub/DEC/SRC/researc
h-reports/abstracts/src-rr-173.html
 http://oak.cs.ucla.edu/~cho/papers/cho-parallel.pdf
Introduzione
• Il seminario si propone di introdurre i concetti fondamentali relativi alla
raccolta automatica di documenti nel web (crawling).
• Si vedranno gli approcci di base che alcuni software (chiamati crawler o
spider) utilizzano per analizzare ed estrarre automaticamente documenti
testuali e ipertestuali e i vari collegamenti (hyperlinks) tra essi.
• I sistemi di crawling differiscono tra loro in base a:
 Dimensione
 Small-Scale Crawler
 Large-Scale Crawler
 Tipo e numero delle pagine recuperate
 Extensive Crawling
 Focused Crawling
 Incremental Crawling
Funzionamento
• Un crawler, dopo aver raccolto delle pagine, le elabora e grazie agli
hyperlink in esse contenuti cerca di raggiungere altre nuove pagine.
 Si parte da un dato insieme di URLs;
 Progressivamente questi vengono visti e valutati alla ricerca di
nuovi URLs (detti outlinks);
 I nuovi URLs trovati vengono aggiunti alla collezione e il
processo viene ripetuto.
• La collezione aumenta molto velocemente, la nuove informazioni
vengono memorizzate su disco, non c’è garanzia che tutte le pagine della
base documentale vengano recuperate.
• Un crawler ha, fra gli obbiettivi, quello di massimizzare il numero di
pagine ritrovate per unità di tempo.
Pseudo-Codice di un Crawler
Algoritmo:
URL = {seme iniziale} ;
While ( URL ≠ Ø ) {
url ← select(URL);
if (url.isValid) continue;
page ← crawl(url);
store(page);
S ← parse(page); // si estraggono i link
URL ← URL + S;
}
Large-Scale Crawler
• Il recupero di una pagina può richiedere diversi secondi, e quindi
bisogna cercare dei metodi per utilizzare al meglio la banda disponibile
della rete.
• Questo recupero multiplo è possibile solo se l’attività del DNS è
fortemente concorrente e possibilmente suddivisa fra più server DNS.
• La concorrenza realizzata dal S.O. non è quella ottimale: meglio
specificare esplicitamente lo stato di un processo di recupero in
un’apposita struttura dati ed usare dei sockets asincroni che permettano
di completare il job il prima possibile.
• E’ importante che il crawler sia preciso e che eviti di ritrovare pagine
duplicate o “spider traps”, le quali sono mappe di falsi URLs create da
utenti “maligni” che intrappolano il crawler in cicli potenzialmente infiniti.
Struttura di un Large-Scale Crawler
DNS Caching, Prefetching and Resolution
• L’address resolution è un collo di bottiglia significante che ha bisogno di
essere svolto in concomitanza con altre attività per mantenere un
throughput accettabile.
• Per minimizzare questo problema e per poter sfruttare i tempi morti, i
Large-Scale Crawler includono un apposito “DNS personalizzato” per
poter migliorare le performance.
• Questi DNS personalizzati solitamente includono:
 Client personalizzato dedicato all’address resolution;
 Caching Server;
 Prefetching Client.
• Il Prefetching Client, una volta recuperati gli HREF, provvede a trovare
gli hostname e avviare una richiesta di resolution per gli URLs estratti.
Multiple Concurrent Fetches (1/2)
• Un crawler recupera centinaia di pagine al secondo e, visto che il
download di una singola pagina può impiegare diversi secondi, i crawler
necessitano di aprire più connessioni simultanee con più server.
• I due principali approcci per gestire connessioni multiple e concorrenti
sono:
 Multithreading;
 “Nonblocking Sockets and Events Handlers”.
• Nel Multithreading, dopo la name resolution, ogni thread logico crea un
client socket, si connette al server tramite http, invia una richiesta sempre
http e rimane in ascolto sul socket (grazie al comando recv) fino a
quando ci sono caratteri disponibili.
• In questo approccio si utilizzano delle “Blocking System Calls”.
Multiple Concurrent Fetches (2/2)
• Usando i nonblocking socket, ogni chiamata di tipo connect, send, recv,
ecc. ritorna immediatamente senza attendere che tutte le operazioni di
rete siano completate.
• Viene permessa la “Select system call”, che permette di sospendere e
mettere in attesa un’applicazione facendola aspettare fino a quando i dati
non sono stati inviati/ricevuti dal socket.
• Ogni socket attivo può essere associato ad una struttura dati che
mantiene lo stato dei thread che stanno aspettando la terminazione di
un’operazione su quel socket.
• Select è importante perché è un modo di ottenere sincronizzazione e
mutua esclusione senza utilizzare semafori o locks (in particolare
permette la scrittura senza interruzioni anche su blocchi contigui).
Link Extraction and Normalization
• Una volta estratti gli URLs, prima di inserirli nel work pool, questi
devono essere standardizzati e filtrati.
• Il recupero di duplicati non è però inevitabile, in quanto la mappa fra
hostname e indirizzi IP è di tipo molti-a-molti.
• La forma di standardizzazione
“Canonizzazione”
maggiormente
utilizzata
è
la
• Un URL canonico si forma seguendo i seguenti passi:
1. Si scrive l’url come una classica stringa che rispetta dei criteri
standard;
2. L’hostname viene canonizzato;
3. Se necessario, alla fine gli si aggiunge il numero di porta esplicito;
4. Il path viene normalizzato e pulito.
Robot Exclusion
• Una condizione che il crawler deve verificare è se il server non da
accesso a determinati URLs usando il meccanismo del “robots”.
• “robots.txt” è un file in cui sono specificati una lista di cammini delle
pagine che il crawler non dovrebbe tentare di recuperare.
• Il file “robots.txt” si applica solo ed esclusivamente ai crawler, non anche
ai browser.
• In robots.txt si possono inoltre dichiarare (a discrezione del webadministrator) delle stime di frequenza di modifica delle pagine.
# exclude some access-controlled areas
User-agent: *
Disallow: /Team
Disallow: /Project
Disallow: / Systems
Eliminating Already-Visited URLs
• Attraverso il modulo “isUrlVisited?” riusciamo a controllare se un nuovo
url è già presente all’interno del work pool.
• “isUrlVisited?” deve lavorare molto velocemente e solitamente opera nel
seguente modo:
1. Calcola una funzione hash sull’url come MD5;
2. Gli urls così normalizzati vengono memorizzati in un db in memoria
secondaria.
• Problema: usando delle funzioni hash, perdiamo informazioni sulla
località.
Spider-Traps
• Queste trappole esistono per principalmente due motivi:
1. Tentativi di migliorare la propria posizione nei motori di ricerca;
2. Errori di programmazione nelle pagine che generano loop tramite
link dinamici a se stesse.
• Per risolvere questo problema, uno scanning lessicale o i tool di parsing
sono altamente inefficienti.
• Alcune possibili soluzioni potrebbero essere:
 Imporre un numero max di pagine recuperabili per host;
 Controllare la lunghezza dell’url;
 Preparare statistiche sulle esperienze passate di crawling.
Esempio di trappola:
www.troutbums.com/Flyfactory/hatchline/hatchline/hatchline/flyfactory/flyfactory/hatchline/flyfactory/flyfactory/flyf
actory/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/hatchline/hatchline/flyfactory/flyfactory/hatchline/
Avoiding Repeated Expansion of Links on
Duplicate Pages
• Un buon crawler dovrebbe evitare di memorizzare pagine (ad es. u1 e
u2) uguali anche se hanno nomi diversi. Questo per i seguenti motivi:
1. Ridurre la ridondanza nella memorizzazione e il costo per
processarle;
2. Per non aggiungere un outlink (ad es. v) più volte nel work pool.
• Possiamo capire se u1 e u2 sono esatti duplicati procedendo in uno dei
seguenti modi:
 Confrontiamo i digest di una nuova pagina recuperata con
quelli già memorizzati delle altre pagine;
 Rappresentare gli outlink con delle tuple (h(u1),v) e (h(u2),v) e
confrontare tra loro tali valori.
• Problema: anche piccolissime differenze causano la diversità di una
pagina rispetto ad un’altra.
Load Monitor and Manager
• La funzione del Load Monitor è quella di tenere sotto controllo alcuni
parametri e statistiche inerenti la rete. In particolare:
1. Performance della connessione alla WAN, con le stime di
latenza e di bandwidth;
2. Numero massimo di socket aperti che il crawler non deve
eccedere;
3. Numero massimo di socket
contemporaneamente attivi.
che
possono
essere
• Il Load Manager usa tali statistiche per compiere determinate azioni
come:
1. Scelta di quale url si deve estrarre ed elaborare dal work pool;
2. Organizzare le risorse di rete;
3. Se necessario, distribuire le richieste su più ISP.
Pre-Server Work-Queues
• I principali server commerciali devono studiare dei meccanismi per
difendersi da attacchi di tipo Denial of Service (DoS).
• Ci si può difendere ad es. limitando il numero di richieste provenienti da
uno stesso indirizzo IP o penalizzando le risposte a richieste provenienti
dallo stesso indirizzo IP.
• E’ fondamentale che un crawler non venga scambiato per un attacco di
tipo DoS!
• Per non fare troppe richieste contemporanee ad uno stesso server, un
crawler utilizza una “coda FIFO di richieste” per ogni server con cui è
connesso: tale coda viene svuotata secondo precisi intervalli temporali.
• Le scelte sulle tempistiche inerenti le code o sui balzi da compiere tra
server e server sono decise a livello progettuale del crawler.
Text Repository (1/2)
• Le pagine raccolte dal crawler vengono solitamente memorizzare in un
DB, dal quale poi diversi servizi e sistemi accedono per svolgere
esternamente le loro attività.
• Alcune di queste funzioni vengono iniziate all’interno del crawler stesso,
senza quindi la necessità di memorizzare le pagine.
• Le informazioni relative alle pagine vengono memorizzate in due parti:
Metadata e Page Content.
 Metadata: sono solitamente manipolati da software appositi e
memorizzati in DB relazionali, i quali spesso pagano un overhead
per supportare update concorrenti e operazioni di recovery. I
Metadata non hanno bisogno di essere indicizzati.
 Page Content: esprime l’apporto informativo della pagina. I
contenuti delle pagine HTML vengono solitamente memorizzati
compressi (si utilizza spesso l’algoritmo di compressione zlib).
Text Repository (2/2)
• La memorizzazione delle pagine è regolata da un “Custom Storage
Manager” che permette modalità di accesso semplificate in modo che il
crawler possa facilmente aggiungere pagine e che i programmi che
operano sul repository riescano facilmente ad estrarre i documenti.
• Tale DB può essere configurato principalmente in due modi:
 Tavola Hash o B-Albero: permette accesso tramite chiave ma
dispendioso in termini di tempo e di spazio;
 Lista sequenziale di record delle pagine: ha le caratteristiche
duali del B-Albero.
• Per sistemi di grandi dimensioni, il repository può essere distribuito su
più server di memorizzazione collegati al crawler tramite rete locale.
• In pratica, il crawler calcolerà l’hash per ogni URL e lo invierà assieme
ai Page Content ad un server di memorizzazione, il quale farà l’append
sul proprio repository che solitamente è costituito da nastri.
Refreshing Crawled Pages
• Un motore di ricerca deve ovviamente fare periodici cicli di refresh, ed
ovviamente tale azione dovrebbe riflettersi a tutti i documenti già ritrovati
dal crawler.
• Per compiere tali aggiornamenti, un crawler fa in modo di non terminare
mai i propri “job” ma di fermarsi fino a quando non sono state raccolte un
numero sufficiente di informazioni/pagine.
• Poi, grazie all’utilizzo di “Fresh Crawl”, si interrogano i server per
scoprire se sono state aggiornate alcune pagine.
• Quando non si possono utilizzare delle stime per determinare se alcune
pagine sono state modificate, o si rivisita la pagina o ci si avvale di stime
di probabilità sulle modifiche per produrre un rank di fresh da fare.
• I motori di ricerca importanti spesso attivano dei sotto-cicli di refresh
indipendenti per i siti di più rapida modifica.