Peer to Peer Computing e
Distributed Hash Table (DHT)
Giancarlo Ruffo
Dipartimento di Informatica
Università di Torino
P2P e DHT - G. Ruffo
1
Obiettivi del P2P
P2P e DHT - G. Ruffo
2
Obiettivi del Peer-to-Peer
• Riduzione/Condivisione dei costi
– Ogni peer è responsabile dei propri costi
– Napster: riduzione dei costi di memorizzazione
– SETI@home: riduzione dei costi
computazionali
• Miglioramento della scalability/affidabilità
– Nuovi algoritmi (CAN, Chord, etc.) sono stati
progettati a questo scopo
P2P e DHT - G. Ruffo
3
Obiettivi del Peer-to-Peer
• Aggregazione delle risorse
– Ogni peer presta le sue risorse alla rete
– Napster: Condivide file e banda
– Seti@home: Condivide risorse computazionali
• Maggiore autonomia
– Nessun provider centralizzato di servizi
– I task sono eseguiti localmente
P2P e DHT - G. Ruffo
4
Obiettivi del Peer-to-Peer
• Anonimato/Privacy
– Con un server centrale, è difficile garantire
l’anonimato
– I sistemi P2P eseguono locamente i task, così i
peer possono evitare di fornire tutte le
informazioni in loro possesso
– FreeNet: Non è possibile localizzare chi ha
generato una richiesta
– Altri esempi: Tarzan, Publius, etc.
P2P e DHT - G. Ruffo
5
Obiettivi del Peer-to-Peer
• Dinamicità
– Nel P2P i nodi, e quindi le risorse, entrano ed
escono dal sistema continuamente ed in modo
trasparente
• Comunicazioni Ad-hoc
– I membri del sistema possono entrare ed uscire
dal sistema indipendentemente dalla loro
ubicazione e dal loro interesse
P2P e DHT - G. Ruffo
6
Overlay networks
Overlay network
Internet
P2P e DHT - G. Ruffo
7
Misure per le prestazioni
• Degree
– Il numero di vicini (neighbors) con i quali un nodo mantiene contatti
continui
• Hop count
– Il numero di “hops” necessari ad un messaggio per raggiungere una
destinazione qualsiasi da una qualsiasi provenienza
• Il grado di fault tolerance
– Che frazione di nodi può fallire senza che dei dati vengano eliminati o
che venga compromesso un routing efficace
• Il maintenance overhead
– Quanto spesso i nodi vicini si scambiano messaggi per mantenere lo
stato attuale, anche rispetto ai vari “join” e “leave”
• Il grado di load balance
– Quanto uniformemente vengono distribuite le chiavi tra i nodi, e
quanto carico ogni nodo deve sopportare se usato come intermediario
durante un routing
P2P e DHT - G. Ruffo
8
Centralized server
lookup (”xyz”)
Host4
Host1
Object
Object
Object
Host5
download
Network
reply (”host3”)
Host2
Object
Object
Object
Object
Object
Object
Publish (”I have xyz”)
Host3
Server
P2P e DHT - G. Ruffo
Object
Object
Object
9
Esempi
• Napster, WinMx, DC++
P2P e DHT - G. Ruffo
10
Prestazioni
• Solo il server deve mantenere uno stato del
sistema
• Vantaggi
– Lookup veloce (O(1))
• Svantaggi
– Single point of failure (Napster lo ha dimostrato
abbastanza bene)
P2P e DHT - G. Ruffo
11
Flooding (1/2)
• Se non hai quello che vuoi (e.g. file), manda
una query ad n dei tuoi nodi partner.
• Se anche loro non hanno quello che cerchi,
contatteranno n dei loro partner, per un hop
count massimo uguale a k.
– E.g., n = 7, k = 10
• Le richieste vengono mandate in “broacasting”
– In generale, nessuna struttura ad albero
• Il looping viene evitato, ma i pacchetti possono
essere ricevuti più volte.
P2P e DHT - G. Ruffo
12
Flooding (2/2)
Host7
Host4
Host1
Object
Object
Object
Host5
Network
Host2
Object
Object
Object
Host3
Host6
Object
Object
Object
P2P e DHT - G. Ruffo
Object
Object
Object
13
Esempi
• Gnutella
• KaZaa (gerarchico)
P2P e DHT - G. Ruffo
14
Prestazioni
• Nessun limite superiore per lo stato
(degree);
• Nessuna garanzia di trovare la risorsa
cercata (anche se esistente);
• L’overhead per il mantenimento è alto
(fenomeno topology mismatch…)
• Grado di Fault Tolerance: dipende…
– Resistente ai guasti casuali
– Debole contro attacchi mirati (DoS)
P2P e DHT - G. Ruffo
15
Algoritmi P2P:
Tabelle Hash Distribuite
P2P e DHT - G. Ruffo
16
Sommario
• Introduzione
• Casi di studio
– Chord
• Panoramica
• Applicazioni: DHASH, Arpeggio, CFS, The Circle
– Kademlia
• Panoramica
• Applicazioni: eMule, Overnet, RevConnect DC++,
KadC
P2P e DHT - G. Ruffo
17
Distributed Hash Tables (DHTs)
• Le tabelle hash associano Chiavi a Valori
• Le DHTs sono overlay strutturate che offrono:
– Alta scalabilità
– Interfaccia per il lookup hash-table-like
• Un sistema DHT supporta una funzionalità simile
ad una tabella hash su scala Internet-like
• Substrato ideale per molte appliciazioni (P2P)
– file-systems, storage, backups, event-notification, email, chat, databases, sensor networks ...
P2P e DHT - G. Ruffo
18
Distributed Hash Tables (2)
• Il nucleo di ogni sistema DHT:
– Overlay network
– Algoritmo di routing
– Funzione hash
• Problema principale: lookup
– Come trovare (efficientemente) la posizione di un
oggetto (e.g. a file)
– Quando si conosce la posizione, il download è diretto
• Inoltre, si devono suddividere i dati in modo tale
che le operazioni di joins/leaves richiedano uno
lavoro minimo
P2P e DHT - G. Ruffo
19
DHT: schema generale
Key
Valore
K1
V1
Key
Valore
K2
V2
K41
V4
K3
V3
K42
V5
K4
K43
K5
Es. lookup(K431) = V6
Key
Valore
K51
V8
K52
K53
V9
P2P e DHT - G. Ruffo
Key
Valore
K431
V6
K432
V7
Key
Valore
K521
VA
20
Chord
P2P e DHT - G. Ruffo
21
Chord
• Semplice protocollo per lookup distributa
– Una sola operazione: associa una chiave ad un nodo
• Sviluppato al MIT (IRIS Project)
• Ogni nodo mantiene informazioni di routing di circa O(log N)
• Messaggi necessari per trovare un nodo: O(log N)
• Messaggi necessari per aggiornare le informazioni di routing:
O(log2 N)
P2P e DHT - G. Ruffo
22
Chord – Consistent Hashing
• Ad ogni nodo e ad ogni chiave viene
assegnato un id a m bit. (m = 160 per SHA-1)
• n = nodeID = H(IP address)
• k = keyID = H(key)
• ID ordinati in un anello modulo 2m
• successor (k) è il primo nodo con n ≥ k
P2P e DHT - G. Ruffo
23
Chord – Consistent Hashing
m=3
0
7
1
k1 = 1
k2 = 2
k3 = 6
2
6
3
5
4
P2P e DHT - G. Ruffo
24
Chord – Scalable Key Location
• m è la dimensione in bit degli ID
• Ogni nodo n mantiene una finger table con
(max) m entry.
• L’entry i-esima sul nodo n contiene l’ID del
primo nodo s che succeda n di almeno 2i – 1.
• s = successor (n + 2 i – 1)
• s = n.finger[i].node
P2P e DHT - G. Ruffo
25
Chord – Scalable Key Location
• Ogni nodo mantiene informazioni su pochi
altri nodi.
• Una finger table di un nodo NON ha
solitamente informazioni sufficienti per
determinare il successor di una chiave
arbitraria.
P2P e DHT - G. Ruffo
26
Chord: Finger table per il nodo 109
N123
N5
N7
with m = 7
N109
N20
N98 Start
Succ
(109+1)mod128 = 110
123
(109+2)mod128
N90= 111
123
(109+4)mod128 = 113
123
(109+8)mod128 = 117
123
(109+16)mod128 = 125
5
(109+32)mod128 = 13
20
N81
(109+64)mod128= 45
45
N33
N45
N60
P2P e DHT - G. Ruffo
27
Chord – Scalable Key Location
n.find_successor(id)
n’ = find_predecessor(id);
return n’.successor;
finger[k].start
RPC eseguita
sul nodo n
(n + 2k-1) mod 2m
RPC eseguita per
n.find_predecessor(id)
finger[k].interval
[finger[k].start,
cercare la variabile
n’ = n;
finger[k+1].start) “successor” su n’
while (id not in (n’ , n’.successor])
st node ≥ n.finger[k].start
n’ =
finger[k].node
the
1
n’.closest_preceding_finger(id);
I puntatori della finger
return n’;
successor
table, raddoppiando
next node on ID
circle
continuamente le
n.closest_preceding_finger(id)
for i = m downto 1
distanze, causano il
predecessor
prev
node
on
ID
circle
if (finger[i].node in (n, id))
dimezzamento della
return finger[i].node; distanza dall’obiettivo.
return n;
P2P e DHT - G. Ruffo
28
Chord – Scalable Key Location
finger[3].interval = [finger[3].start, 1)
0
7
1
2
6
finger[1].start = 2
finger[1].interval =
3
5
finger[3].start = 5
4
[finger[1].start,
finger[2].start)
finger[2].start = 3
finger[2].interval = [finger[2].start, finger[3].start)
P2P e DHT - G. Ruffo
29
Chord – Scalable Key Location
Finger TABLE
0
Finger TABLE7
Start
Int
Succ
1
2
4
[1,2)
[2,4)
[4,0)
1
3
0
6
1
Start
Int
Succ
2
3
5
[2,3)
[3,5)
[5,1)
3
3
0
KEY = 1
2
KEY = 6
Lookup(1)
5
3
4
P2P e DHT - G. Ruffo
Finger TABLE
Start
Int
Succ
4
5
7
[4,5)
[5,7)
[7,3)
0
0
0
KEY = 2
30
Chord – Node Joins
2 INVARIANTI
• Il successore di ogni nodo è mantenuto
correttamente
• Per ogni k, il nodo successor(k) è
responsabile per k.
P2P e DHT - G. Ruffo
31
Chord – Node Joins
Ogni nodo che entra o esce dal sistema
causa l’invio di O(log2 N) messaggi lungo
l’anello per correggere le finger table.
Predecessor pointer
P2P e DHT - G. Ruffo
32
Chord – Node Joins
n entra nella rete. Occorre:
• Riferirsi ad un nodo di bootstrap (n’)
• Inizializzare predecessor e finger (tramite
lookup apposite eseguite da n’)
• Aggiornare i finger e i predecessori dei nodi
nella rete
• Avvertire il livello sw superiore in modo
che possa spostare le chiavi.
P2P e DHT - G. Ruffo
33
Chord – Node Joins
#define successor finger[1].node
n.update_others()
for i = 1 to m
p = find_predecessor(n – 2i – 1);
p.update_finger_table(n,i);
n.join(n′)
if(n′)
init_finger_table(n′);
update_others();
else
for i = 1 to m
finger[i].node = n;
predecessor = n;
n.update_finger_table(s,i)
if (s in [n, finger[i].node])
finger[i].node = s;
p = predecessor;
p.update_finger_table(s,i);
n.init_finger_table(n′)
finger[1].node = n′.find_successor(finger[1].start);
predecessor = successor.predecessor;
successor.predecessor = n;
for i = 1 to m – 1
if (finger[i + 1].start in [n, finger[i].node))
finger[i + 1].node = finger[i].node
else
finger[i + 1].node = n′.find_successor(finger[i + 1].start);
P2P e DHT - G. Ruffo
34
Chord – Node Joins
Finger TABLE
Finger TABLE
Start
Int
Succ
1
2
4
[1,2)
[2,4)
[4,0)
1
3
0
0
7
1
Start
Int
Succ
2
3
5
[2,3)
[3,5)
[5,1)
3
3
0
KEY = 1
KEY = 6
2
6
Finger TABLE
Start
7
0
2
Int
[7,0)
[0,2)
[2,6)
Succ
3
50
0
3
4
KEY = 6P2P e DHT - G. Ruffo
Finger TABLE
Start
Int
Succ
4
5
7
[4,5)
[5,7)
[7,3)
0
0
0
KEY = 2
35
Chord – Node Joins
Finger TABLE
Finger TABLE
Start
Int
Succ
1
2
4
[1,2)
[2,4)
[4,0)
1
3
6
0
7
1
Start
Int
Succ
2
3
5
[2,3)
[3,5)
[5,1)
3
3
6
KEY = 1
KEY = 6
2
6
Finger TABLE
Start
7
0
2
Int
[7,0)
[0,2)
[2,6)
Succ
3
50
0
3
4
KEY = 6P2P e DHT - G. Ruffo
Finger TABLE
Start
Int
Succ
4
5
7
[4,5)
[5,7)
[7,3)
6
6
0
KEY = 2
36
Chord – Node Leaves
Finger TABLE
Finger TABLE
Start
Int
Succ
1
2
4
[1,2)
[2,4)
[4,0)
1
3
6
0
7
1
Start
Int
Succ
2
3
5
[2,3)
[3,5)
[5,1)
3
3
6
KEY = 1
KEY = 6
2
6
Finger TABLE
Start
7
0
2
Int
[7,0)
[0,2)
[2,6)
Succ
3
50
0
3
4
KEY = 6P2P e DHT - G. Ruffo
Finger TABLE
Start
Int
Succ
4
5
7
[4,5)
[5,7)
[7,3)
6
6
0
KEY = 2
37
Chord – Node Leaves
Finger TABLE
Start
Int
Succ
1
2
4
[1,2)
[2,4)
[4,0)
0
3
6
0
7
1
KEY = 6
2
6
Finger TABLE
Start
7
0
2
Int
[7,0)
[0,2)
[2,6)
Succ
3
50
0
3
4
KEY = 6P2P e DHT - G. Ruffo
Finger TABLE
Start
Int
Succ
4
5
7
[4,5)
[5,7)
[7,3)
6
6
0
KEY = 1,2
38
Chord - Stabilization
stabilization
7
successor
5
6
predecessor
successor
P2P e DHT - G. Ruffo
39
DHash
Layer
Function
Chord
Mappa gli ID nei successor
DHash
Associa i valori con gli ID
Application
File System Interface
P2P e DHT - G. Ruffo
40
DHash
• Chord non fornisce STORAGE
• err_t insert (void *key, void *value)
void *lookup (void *key)
• k = H(key) per produrre un ChordID di 160
bit e memorizzando il valore (value) nel
nodo successor(k)
P2P e DHT - G. Ruffo
41
DHash - Reliability
• Per preservare l’invariante del mantenimento della chiave
sul successor -> callback di Chord.
• Spostamento di O(1/N) chiavi ogni volta che un nodo entra
o esce dal sistema, a cui si deve aggiungere il costo O(log
N)
• Memorizzazione non solo su successor(k) ma anche sui
primi r successor -> redundant storage
P2P e DHT - G. Ruffo
42
DHash - Performance
• I cammini che cercano un determinato successor,
partendo da nodi diversi, tendono ad incrociarsi
tanto più frequentemente quanto più ci si avvicina
al target.
• Per ogni lookup di (k,v) che ha successo il valore v
viene mantenuto in cache dai nodi sul percorso.
• Le lookup successive vanno a cercare il v in cache.
• + popolarità = + diffusione
P2P e DHT - G. Ruffo
43
DHash - DoS
• Inserimento grandi quantità dati inutili —> flush
dei dati interessanti. Contromossa: limitare il
numero di blocks che un nodo può mantenere.
• Un nodo si annuncia come successor e poi non
memorizza il file: controllo di n da parte degli altri
nodi.
• Controllo incrociato per verificare la correttezza
della coppia (successor, predecessor).
P2P e DHT - G. Ruffo
44
DHash – Balancing Load
• Caching
• Layer of indirection: DHash mappa gli ID
dei file in una lista di IP dove il documento
è disponibile (DNS-like).
Problema: caching e redundant storage
devono essere implementati due volte.
P2P e DHT - G. Ruffo
45
DHash – Balancing Load
• Vengono mappati blocks di file invece dei file
interi.
• I file sono inseriti a livello DHash usando come
chiave l’hashing del contenuto del block.
• Meta-data (come inode) per fornire un nome unico
per il file completo.
• I file vengono sparsi su molti server, e quindi c’è
un bilanciamento di carico.
• Aumento affidabilità e performance.
P2P e DHT - G. Ruffo
46
DHash – Balancing Load
• Dal momento che per un file devono essere
contattati più nodi, dobbiamo pagare un
costo in più per i DHash lookup ulteriori.
• Un’implementazione base costa:
(S x L x log N) / B
S (byte) = document size, N = numero server,
B = block size, L = average latency
P2P e DHT - G. Ruffo
47
DHash API
• put_h(block): calcola la chiave del blocco
calcolando il suo hash (key= hash(block)), e
lo spedisce al nodo sucessore (succ(key))
per effettuare lo storage;
• get(key): individua e restituisce il blocco
associato alla chiave Chord specificata.
P2P e DHT - G. Ruffo
48
CFS – Cooperative FS
Layer
Chord
DHash
CFS
Function
Mantiene le tabelle di routing
che servono a trovare i
blocchi
Conserva i blocchi dei dati in
modo affidabile e non
strutturato
Interpreta I blocchi come file,
e si presenta alle applicazioni
come un’interfaccia ad un
filesystem
P2P e DHT - G. Ruffo
49
Ricerca per keyword in una DHT
• Se si conosce l’hash del file, lo si trova in tempo
O(logN);
• Ma se non si conosce l’hash?
• Non banale: l’uso degli hash crittografici complica
tutto (no collisioni, basta cambiare un bit, per
avere un hash completamente diverso …)
• DHT ottime per load balancing, ma pessime per la
ricerca via keyword
P2P e DHT - G. Ruffo
50
Ricerca tramite keyword: Soluzioni
• Avere un server centrale che associ
keywords ad uno o più valori hash (sic!!!)
– Vedi CFS: utilizza un motore Napster per
associare keyword a chiavi Chord
• Creare un livello di indirezione, ovvero
applicare le funzioni get(key) e put(block) a
metadati e non ai file (vedi Arpeggio)
P2P e DHT - G. Ruffo
51
Kademlia
P2P e DHT - G. Ruffo
52
Kademlia
• Ogni nodo è rappresentato da un identificatore di 160 bit;
• Dati due identificatori x e y la distanza fra x e y (d(x,y)) è
definita come x (xor) y;
• XOR è una metrica:
–
–
–
–
–
d(x,x)=0;
d(x,y)>0 se xy;
d(x,y)=d(y,x) (simmetrico);
d(x,y)+d(y,z)d(x,z).
fissato x e una distanza d esiste un solo y tale che d(x,y)=d;
• Per ogni 0  i  160, ogni nodo mantiene una lista di k
(costante) nodi (detta k-bucket) a distanza compresa fra 2i e 2i+1
da se stesso.
P2P e DHT - G. Ruffo
53
Kademlia (2)
• I k-bucket vengono aggiornati e ordinati ad ogni operazione con
una politica detta least-recently seen node;
• Ovviamente a ogni passo l’algoritmo di routing dimezza la
distanza fra il nodo che fa la richiesta e la destinazione (O(log
n) passi);
• La dimensione delle tabelle di routing è k*log n;
• Poiché è simmetrico il sistema si stabilizza da solo. In pratica
durante le lookup le tabelle di routing vengono aggiornate;
P2P e DHT - G. Ruffo
54
Applicazioni
•
•
•
•
Overnet
eMule
Revconnect DC++
KadC – libreria C per pubblicare e
recuperare informazioni su/da la rete
Overnet
P2P e DHT - G. Ruffo
55
eMule
• Siete collegati alla rete Kademlia se:
ED2K:Connesso|KAD:Connesso
• Primo passo: bootstrap
• Ogni nodo calcola la distanza rispetto ai
nodi di cui è a conoscenza
P2P e DHT - G. Ruffo
56
eMule – Bootstrap
P2P e DHT - G. Ruffo
57
eMule – Id e distanze
1. Id del nodo nella lista
2. Distanza XOR
P2P e DHT - G. Ruffo
58
eMule – Condivisione
• Publishing: condivisione dei file
• Viene ripetuta ogni 5 ore per tutti i nostri file
• L’hash di ogni file viene progressivamente
comunicato ad altri client presenti nella lista
• Scelta non casuale: solo ai client con ID “vicino” a
quello dell’hash
• Si distribuisce l’informazione che sto
condividendo un dato file
P2P e DHT - G. Ruffo
59
eMule – Ricerca
• Ogni client ha una lista <chiave, valore>
• Cerco un file tramite il suo hash
• Contatto il nodo con ID più vicino, fino a
quando non trovo una coppia <chiave,
valore> con chiave uguale all’hash cercato
P2P e DHT - G. Ruffo
60
eMule – Crediti
• Viene calcolato
ci = (#Download)/(#Upload)
per ogni client i
• Se un certo numero di client, chiedono un file
posseduto da x, allora x crea una coda assegnando
una priorità in base ai crediti
• Si parte dal client con ci maggiore
• Sistema rudimentale di incentivazione per
combattere il free-riding
P2P e DHT - G. Ruffo
61
Sommario
• CAN: Routing in uno spazio D-dimensionale
• Chord: Routing attorno ad uno cerchio con scorciatoie a
distanza 2i
• Kademlia: Routing in uno spazio metrico basato su XOR
Node state
Route path
length
Add node
CAN
O(D)
(DN1/D)/4
Chord
O(log N)
O(log N)
Kademlia
O(k*log N)
O(log N)
O(DN1/D)
O(log2 N) O(log N)
CAN can achieve O(log N) complexity by setting D=log N / 2
P2P e DHT - G. Ruffo
62
Riferimenti
•
•
•
•
•
I. Stoica, R. Morrise, D. Karger, M. F. Kaashoek and H. Balakrishnan.
"Chord: A scalable peer-to-peer lookup service for Internet
applications". In Proceedings of the SIGCOMM 2001, August 2001.
F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica “Wide-area
cooperative storage with CFS”, in Proc. of ACM SOSP 2001, Banff,
October 2001
P. Maymounkov and D. Mazieres. “Kademlia: A peer-to-peer
information system based on the xor metric”. In Proc. of IPTPS02,
Cambridge, USA, March 2002.
S. Campadello, H. Helin – Dispense del corso “Peer-to-Peer
Computing”, University of Helsinki
Ringraziamenti: Marco Milanesio, Rossano Schifanella
P2P e DHT - G. Ruffo
63