Enhancing P2P File-Sharing
with an
Internet-Scale Query Processor
di Boon Thau Loo, Joseph M. Hellerstein, Ryan Huebsch,
Scott Shenker e Ion Stoica
(University of Berkeley)
Presentazione di:
Marco Andolfo
Claudio Campeggi (rel.)
Alessio Gaeta
Sistemi Informativi LS A.A. 2005-2006
Gruppo
Sommario
 Problema
del lookup
 Caratteristiche
della ricerca di
documenti nella rete gnutella
 Un
nuovo approccio di ricerca: DHT e
PIERSearch
 Soluzione
ibrida proposta: pro e contro
della scelta individuata
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
2
Problema del lookup
 Introduzione
e sviluppo dei sistemi di
condivisione dei file che utilizzano reti
Peer-to-Peer (P2P)
Problema del lookup:
Dato un oggetto memorizzato in un certo
insieme dinamico di nodi, trovarlo
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
3
Problema del lookup
Si possono applicare tecniche di query simili
a quelle dei DB distribuiti?

Principali cause
Dimensioni elevate della rete P2P
Alta scalabilità della rete ed eterogeneità
delle macchine coinvolte
Agli occhi dell’utilizzatore appare un unico
sistema di query
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
4
La rete gnutella
Architettura
Numero
Uso
Le
macchine
del flooding
elevatissimo
del
sono
sistema
per
connesse
effettuare
di nodi:
molto
in
rete
le
eterogenea
ricerche
una
semplice
rete ad hoc
di dimensioni
non strutturata
globali
Un utente può entrare ed uscire dalla
rete liberamente senza causarne la
caduta
I file memorizzati su un nodo sono
condivisi con gli altri
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
5
Come avviene la ricerca
1.
2.
3.
4.
5.
10/03/2006
Attraverso un’applicazione client (es. LimeWire)
l’utente si collega alla rete e specifica una
keyword per eseguire la ricerca
La ricerca avviene per flooding: partendo dai nodi
più vicini si propaga la query da nodo a nodo
Se un nodo risponde in modo affermativo riporta il
suo ID e i file che fanno match alla sorgente
Al termine della ricerca viene riportato il result set
complessivo
La ricerca non è esaustiva: viene fissato un timeto-live (TTL) che permette solo di esplorare una
frazione della rete!
Sistemi Informativi LS A.A. 2005-2006
6
Come avviene la ricerca: esempio
Ha inizio la ricerca!
Orizzonte di ricerca
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
7
Considerazioni

La rete utilizza una tecnica di ricerca semplice
La ricerca di un file che presenta molte copie (file
popolari) darà sempre ottimi risultati
E se sono presenti poche copie?
C’è il forte rischio che non sia presente nessuna
copia dentro la frazione di rete!
Una copia esiste ma purtroppo è presente in una
frazione non raggiungibile!
L’algoritmo di ricerca risulta essere
poco efficiente e occorre introdurre
dei miglioramenti
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
8
Alternative

Aumentare il valore di TTL
Questo comporta ampliare il numero di nodi che la
query dovrà visitare
Tuttavia si rischia di allungare (anche
drasticamente) il tempo di risposta (il protocollo
prevede che al max sia di 60 sec.)

Introdurre gli ultrapeers: gruppo di peer al
quale il client si lega per spedire i messaggi
Il flooding avviene tra ultrapeers
Indicizzare i contenuti?
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
9
PIERSearch
è un’applicazione che
consente di pubblicare e ricercare oggetti
nell’ambito di una rete P2P
 PIERSearch
 Il
suo motore di ricerca e il meccanismo
di pubblicazione si appoggiano ad una
rete strutturata basata su Distributed
Hash Table (DHT)
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
10
Distributed Hash Table
N1
Il lookup avviene per
Ogni nodo
è responsabile
di un
avvicinamenti
successivi
insieme di chiavi
“vicine” al suo ID
all’obiettivo
K54 N56
lookup(54)
N8
Ad ogni nodo viene assegnato un ID
N51
N14
La rete ha una struttura ad anello
N48
Ogni nodo conosce un certo numero
di suoi vicini
N21
Il nodo N8 cerca
l’oggetto con
chiave K54
N42
N38
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
11
Pubblicazione di un contenuto

Per fornire la possibilità di query testuali su un
overlay DHT PIERSearch fa uso di Inverted
Index
ITEM
fileID
Filename
filesize
ipAddress
port
INVERTED
Il fileID è generato mediante
una funzione di hash su tutti
gli altri campi
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
keyword
fileID
12
Ricerca con PIER
Risultati
Query sui termini
T1 e T2
fileID
fileID
Item(fileID,…)
fileID
10/03/2006
keyword = T1
keyword = T2
Inverted
Inverted
Sistemi Informativi LS A.A. 2005-2006
13
Ricerca
Risultati
Query ottimizzata
sui termini T1 e T2
(InvertedCache)
fileID
fileID
Item(fileID,…)
keyword = T2
keyword = T1
INVERTEDCACHE
keyword
fileID
fulltext
InvertedCache
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
14
DHT: utilizzabile?

PIERSearch, usando DHT, garantisce recall
deterministici
tuttavia…

La fase di pubblicazione è complessa e può
avere un overhead non trascurabile

La fase di ricerca può consumare notevoli
quantità di banda
Occorre trasferire tra i peers le intere tabelle
Inverted con tutti i risultati (parziali) della query
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
15
Infrastruttura ibrida di ricerca

Una soluzione possibile per limitare l’overhead è
creare un’infrastruttura ibrida gnutella-PIERSearch

In questo modo:
 Inizialmente si adotta il flooding (trovo i file “popolari”)
 Se il flooding fallisce (dopo un timeout prefissato) scatta la
ricerca con PIERSearch
Si costruisce un indice parziale per trovare i file rari
Nel DHT si tiene traccia solo dei nodi ultrapeer
Ma quali contenuti indicizzare?
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
16
Politiche di pubblicazione [1]

Query Result Size (QRS)
I file rari sono quelli presenti in result set piccoli
Si definisce il parametro Result Size Threshold
Oggetti rari non cercati non finiscono in cache

Term Frequency (TF)
Ogni nodo ibrido raccoglie statistiche temporali dal
traffico di ricerca per determinare la frequenza delle
keyword
Si definisce il parametro Term Frequency Threshold
Problema di file raro con keyword popolare
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
17
Politiche di pubblicazione [2]

Term Pair Frequency (TPF)
Analoga alla precedente, ma che considera coppie
di termini
Si definisce il parametro Term Pair Frequency Threshold

Sampling (SAM)
Si campionano i nodi vicini per stimare un limite
inferiore del numero di repliche di ogni file
Si definisce il parametro Sample Threshold
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
18
Test [1]
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
19
Test [2]
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
20
Problemi di modello
 Tutti
i nodi partecipano al query
processing
 Distribuzione
random delle repliche e dei
link tra i nodi. Repliche identiche non
risiedono sullo stesso nodo
 Costi
totali del sistema sono dominati
dall’overhead della comunicazione
(misurato in n° di messaggi scambiati)
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
21
Problemi di modello
 L’orizzonte
di ricerca è identico per tutte
le query, indipendentemente dal numero
di risultati ottenuti
 Flooding
“ideale”: broadcast efficiente che
necessita di n-1 messaggi per
raggiungere n nodi
 Rete
statica: non entrano né escono
nuovi nodi
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
22
Conclusioni



gnutella ottimizza la ricerca di file che hanno molte
copie
PIERSearch al contrario ottimizza la ricerca di file rari
Creazione di un sistema ibrido di ricerca
 Sfrutta le potenzialità migliori dei due sistemi
 I test eseguiti verificano la fattibilità dell’approccio introdotto

Possibili miglioramenti
 Rendere la rete strutturata
 Migliorare il flooding
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
23
Bibliografia

gnutella: http://gnutella.wego.com

Limewire: http://www9.limewire.com

PlanetLab: http://www.planet-lab.org/

OpenDHT: Fixing the Embarrassing Slowness of
OpenDHT on PlanetLab di Sean Rhea, Byung-Gon
Chun, John Kubiatowicz, and Scott Shenker

Funzionamento DHT: A Scalable ContentAddressable Network di Sylvia Ratnasamy, Paul
Francis, Mark Handley, Richard Karp and Scott
Shenker
10/03/2006
Sistemi Informativi LS A.A. 2005-2006
24

10/03/2006
Fai 13! Votaci!
Sistemi Informativi LS A.A. 2005-2006
25