Chord: A Scalable Peer-to-peer Lookup
Service for Internet Applications
Ion Stoica, Robert Morris, David Karger,
M. Frans Kaashoek, Hari Balakrishnan
MIT and Berkeley
Outline

Motivazioni

Consistent hashing

Chord

Valutazione delle prestazioni

Conclusioni e Discussioni
Motivazioni
Come trovare dati in un sistema distribuito di File
Sharing?
Publisher
Key=“LetItBe”
Value=MP3 data
N2
N1
Internet
N4

N3
il Lookup è il problema fondamentale
N5
Client ?
Lookup(“LetItBe”)
Solutioni Decentralizzate

Routing di messaggi (Freenet, Tapestry, Chord, CAN,…)
Publisher
Key=“LetItBe”
Value=MP3 data
N2
N1
Internet
N4

matching esatto !?!?!
N3
N5
Client
Lookup(“LetItBe”)
Routing

Definire una metrica (utile!!!!)

Mantenere basso il numero di hop
Mantenere bassa la dimensione della tabella di
routing

Mantenere le caratteristiche in presenza di una
variazione rapida del numero di nodi

Per gli autori:

Chord: efficienza e semplicità
Chord Overview

Fornisce un servizio di lookup peer-to-peer:

Lookup(key)  Indirizzo IP

Chord non memorizza dati

Come trova un nodo?

Come mantiene le tabelle di routing ?

Come gestisce l’ingresso e la uscita di nodi?
Caratteristiche di Chord

Efficiente: O(Log N) messaggi per lookup


N è il numero totale di nodi presenti
Scalabile: O(Log N) stati per nodo
Robusto: mantiene le performance anche in presenza
di variazioni notevoli del numero di nodi.

Assume
che non ci siano partecipanti maliziosi
Identificatori in Chord

spazio degli identificatori a m bit sia per le risorse
(Chiavi) che per i nodi

identificatore di Chiave = SHA-1(Chiave)
chiave=“LetItBe”

SHA-1
ID=60
identificatore di Nodo = SHA-1(indirizzo IP)
IP=“198.10.10.1”
SHA-1
ID=123

Entrambi sono distribuiti uniformemente

Come si associano gli ID di Chiave agli ID di nodo?
Consistent Hashing [Karger 97]
0 5
IP=“198.10.10.1”
123
20
ID a 7-bit
101
32
90
Chiave=“LetItBe”
60
Una chiave (risorsa) è memorizzata nel primo nodo che segue in
senso orario

Consistent Hashing
Consistent Hashing

Le funzioni Hash mappano chiavi in interi.
Sono utilizzate, ad es, per memorizzare dati in un
pool di cache


Con p cache una possibile funzione è
x -> ax+b (mod p)
Cosa accade se varia p ?
Se la usassimo in un sistema P2P ?
Consistent Hashing

In particolare se varia p:
è assicurato un Bilanciamento sul numero di dati
per posizione


Molti dati devono cambiare posizione
Il numero di posizioni che un dato può
potenzialmente raggiungere non è limitato

Consistent Hashing
Per definizione un Consistent Hashing deve godere di
opportune proprietà:


Bilanciamento

Monotonicità

Spread

Carico
Consistent Hashing

Bilanciamento:
Per ogni sottoinsieme V di posizioni (nodi) ed n dati, il
numero di dati per ogni posizione è O(n/|V|) con alta
probabilità.

Monotonicità:
Se al variare di p le posizioni (i nodi) disponibili passano
da V1 a V2 con V1  V2, la migrazione dei dati deve
avvenire solo verso posizioni appartenenti a V2 , ma non
a V1 .
Consistent Hashing

Spread:
Al variare di p il numero di posizioni che un dato può
assumere è limitato.

Carico:
Al variare di p il numero di dati che una posizione
accoglie è limitato.
Consistent Hashing

Funzioni Hashing Consistenti esistono ?
Siano K(x) ed N(x) due funzioni casuali che hanno come codominio
l’intervallo [0,1).
Definiamo la seguente funzione Hash:

Utilizziamo K(x) per mappare le chiavi

Utilizziamo N(x) per mappare i nodi
La chiave i viene memorizzata nel nodo j se la differenza
|K(i)-N(j)| è la minima su tutti i nodi j.
Consistent Hashing
0

Bilanciamento ?

Monotonicità ?

Spread ?

Carico ?
1
Lookup

Supponiamo che ogni nodo ha informazioni su tutti gli altri
 richiede informazini globali

Tabelle di routing O(N)

la Lookup O(1)
0
10
Dove è “LetItBe”?
Hash(“LetItBe”) = 60
123
32
“90 ha 60”
60
90
55
Chord: Lookup di Base

Ogni nodo conosce il successore
0
10
123
Dove è “LetItBe”?
Hash(“LetItBe”) = 60
32
“90 ha 60”
60

90
La Lookup O(N)
55
Tavola dei Finger

Ogni nodo conosce altri m nodi nell’anello

la distanza cresce esponenzialmente
112
80 + 25
96
80 + 24
80 + 23
80 + 22
80 + 21
80 + 20
80
16
80 + 26
Tavola dei Finger

il Finger i del nodo n punta alla posizione n+2i-1
 Se
non c’è, punta al nodo subito successivo
120
112
80 + 25
96
80 + 24
80 + 23
80 + 22
80 + 21
80 + 20
80
16
80 + 26
Tavola dei Finger
successor(0)=0
0
1
14
15
0
successor(14)=15
successor(1)=1
1
successor(2)=3
2
14
10
13
2
3
12
4
5
11
6
10
successor(6)=6
successor(10)=13
7
9
successor(9)=9
8
9
6
0
1
14
0
15
i
succ
node
1
2
3
node
2
3
3
14
10
13
12
1
i
succ
1
14
15
3
5
6
2
15
15
4
9
9
3
1
1
4
5
6
11
10
2
2
3
4
i
succ
1
10
13
2
11
13
3
13
13
4
1
1
9
node
5
6
7
8
9
6
Algoritmo Lookup
14
0
15
1
2
14
13
12
i
succ
1
14
15
2
15
15
3
1
1
4
5
6
11
10
node
i
succ
1
10
13
2
11
13
3
13
13
4
1
1
9
i
succ
node
1
2
3
2
3
3
3
5
6
4
9
9
3
4
node
5
6
7
8
Lookup

Vale la seguente proprietà:
Per il protocollo Chord ad m bit in un qualunque
intervallo di ID di ampiezza 2m/N, il numero di
ID di nodi atteso è 1 e O(log N) con alta
probabilità
Lookup

E’ possibile mostrare il seguente teorema:
Il numero di nodi che deve essere contattato
per trovare un successore in una rete con N
nodi è O(log N) con alta probabilità.
A partire da questo risultato si può affermare che il numero di
Hop necessari per effettuare una query è O(log N)
Lookup
Supponiamo che il nodo n debba trovare il successore di k.
Sulla dase dell’algoritmo viene prima cercato l’immediato
predecessore, chiamamolo p, di k e poi viene chiesto a p di
cercare il successore di k
A tale scopo il nodo n contatta il più vicino predecessore di k a lui
noto. Supponiamo il nodo sia f ≠ n e sia l’i-esimo finger per n.
Per definizione di finger, f è a distanza almeno 2i-1 da n.
Poichè l’(i+1)-esimo finger di n supera k, n è a distanza al più 2i da
p ed f è a distanza al più 2i-1 da p.
La distanza tra il nodo che sta processando la query ed
il predecessore p dimezza ad ogni passo.
Lookup

La Lookup impiega O(Log N) hop
5
10
110
20
19
99
32
80
60
Lookup(19)
Lookup
Poichè la distanza iniziale è al più 2m, in m passi raggiungiamo p
In log N passi la distanza tra il nodo che sta processando la chiave
ed il nodo p si riduce a 2m /N.
Poichè le chiavi sono distribuite in maniera uniforme, il numero di
chiavi in un intervallo di ampiezza 2m /N è O(log N) con alta
probabilità.
Sono quindi necessari, con alta probabilità, altri O(log N) passi per
raggiungere p e quindi il successore di p
Join


Processo in tre passi:

Inizializza tutti i finger dei nuovi nodi

Aggiorna i finger dei nodi esistenti

Trasferisci le chiavi dal successore ai nuovi nodi
lazy finger update:

Initializza solo i finger al nodo successore

Periodicamente verifica il successore ed il predecessore

Periodicamente rinfresca il contenuto della tavola dei finger
Joining the Ring - Step 1

Inizializza la nuova tavola dei finger

individua un nodo nella rete

Chiedi al nodo di di cercare i finger del nuovo nodo

Raccogli i risultati
5
20
36
99
1. Lookup(37,38,40,…,100,164)
40
80
60
Joining the Ring - Step 2

Aggiorna i finger dei nodi esistenti
il nuovo nodo chiama una funzione di aggiornamento sui nodi
esistenti

I nodi esistenti possono ricorsivamente aggiornare i finger
di altri nodi
N5

N20
N99
N36
N40
N80
N60
Joining the Ring - Step 3

Trasferisci le chiavi dal successore al nuovo nodo

Vengono trasferite solo le chiavi nel range
5
20
99
36
40
80
60
30
38
30
38
Copia le chiavi 21..36
da 40 to 36
Join di un nodo
26.join(friend)
-> 26.successor = 32
26.stabilize
21.stabilize
-> 32.notify(26) -> 21.successor=26
-> 26.notify(21)
Analisi del protocollo
Vale il seguente lemma:
Se al tempo t esiste un arco tra p ed s, allora
per ogni t’>t ci sara’ un arco tra p ed s
Per induzione sul tempo.
Suppopniamo che dopo t avvenga una join. L’arco tra p
ed s non viene toccato dalla join e quindi permane.
Supponiamo avvenga una stabilize.
Consideriamo il momento in cui il nodo p cambia
successore da s ad a. Questo avviene perchè p ha
contattato s ed s gli ha detto di a. Inoltre p<a<s.
Analisi del protocollo
s ha saputo di a ad un tempo precedente e questo può
essere avvenuto solo perchè s è stato un successore
diretto di a.
Per ipotesi induttiva se esisteva un arco (il successore)
tra a ed s, esiste un arco tra a ed s in tutti gli istanti
successivi.
In particolare nell’istante in cui p cambia il successore.
Essendo p<a<s il cambiamento del successore di p non
influisce in alcun modo sull’arco tra a ed s.
Inoltre anche dopo il cambiamento esiste un arco tra p
ed s.
Analisi del protocollo
Tutti gli archi tra x ed y, che utilizzavano l’arco tra p
ed s, erano tali che p ed s erano interni ad x y. Ma tutti
i nodi aggiunti all’arco p s sono interni a p s ed a
maggior ragione interni ad x y.
Se un nodo è capace di risolvere una query,
sarà sempre capace di farlo in futuro
Ad un tempo prefissato dopo l’ultima join i
puntatori al successare saranno corretti per
tutti i nodi
Analisi del protocollo
E’ possibile mostrare il seguente teorema:
Se ogni operazione di join e` alternata con
quella di stabilizzazione, allora dopo un fissato
tempo dall’ultima join i puntatori al successore
formano un ciclo su tutti i nodi della rete.
Analisi del protocollo
Se due nodi condividono il successore, uno dei due
cambierà il puntatore al successore.
Il suo nuovo successore sarà più vicino del nodo cui
puntava in precedenza.
Ogni operazione di stabilizzazione potrebbe richiedere
al più n passi.
Dopo n2 passi siamo quindi certi che tutti i nodi puntano
al successore ed i puntatori formano un unico ciclo con
tutti i nodi.
Join di un nodo

E’ possibile mostrare il seguente teorema:
Se abbiamo una rete stabile con N nodi ed
effettuiamo N join alla rete,
Se tutti i puntatori ai successori sono corretti,
Allora il Lookup di una risorsa avrà necessità di
O(log N) hops con alta probabilità.
Join di un nodo
Se utilizziamo i vecchi finger arriviamo in O(log N)
hops al vecchio predecessore della risorsa. Con alta
probabilità tra due vecchi nodi ci saranno al più O(log
N) nuovi nodi.
Se i successori dei nuovi nodi sono corretti, in al più
O(log N) passi la risorsa sarà raggiunta.
Gestione dei Fallimenti

I fallimenti dei nodi possono causare lookup scorretti
120
113
10
102
85
Lookup(90)
80

80 non conosce il corretto successore e quindi il lookup fallisce
Gestione dei Fallimenti


Usa la lista dei successori

Ciascun nodo conosce r successori

Dopo il fallimento si utilizza il primo successore rimasto

Si correggono i successori per garantire un corretto lookup
La lookup è corretta con alta probabilità
r può essere scelto in modo da rendere la probabilità di
fallimento della lookup arbitrariamente piccola.

Valutazione

lookup veloci in sistemi di grandi dimensioni

Variazione contenuta del costo di lookup

Robusto rispetto a molti fallimenti

Gli Esperimenti confermano i risultati teorici
Costo del lookup
il costo è O(Log N) come previsto dalla teoria

la costante è 1/2
Average Messages per Lookup

Number of Nodes
Implementazioni attuali

Libreria Chord: 3,000 linee di C++

Include:

concurrent join/fail

Proximity-based routing

controllo di carico per nodi eterogenei

Resistente a spoofed node IDs
Pro

Based on theoretical work (consistent hashing)

Proven performance in many different aspects


“with high probability” proofs
Robust (Is it?)
Contro

NON semplice (confrontato con CAN)

join è complicato

richiede molti messaggi ed aggiornamenti
il meccanismo di aggiornamento leggero non è chiaro con che
velocità converge


La tabella di Routing cresce con il numero di nodi

Il caso peggiore di lookup può essere molto lento