Facciamo un piccolo test
• Quanti successori ha un nodo nel protocollo Chord?
(m) (1) (log N) (nessun prec.)
• Aumentando il numero di identificatori in un anello,
le performance del protocollo
(+) (-) (=) (nessun prec.)
Sistemi P2P
Facciamo un piccolo test
• Dato l’anello in figura mostrare i passi della procedura lookup
da 56 a 38
• Mostrare la tabella dei finger del nodo 48
• Quanti messaggi impiega la procedura lookup?
(2) (O(m)) (log N-1) (nessun prec)
m=6
nodi
Giustificare la risposta
1
8
risorse
56
54
51
48
21
42
Sistemi P2P
10
38
38
35
24
28 26
Facciamo un piccolo test
• Chernoff Bound
Siano X1, X2, …,Xn prove ripetute indipendenti tali che per 1 ≤ i ≤ n, Pr[Xi=1]=pi,
Pr[Xi=0]=1-pi con 0 < pi < 1.
Se X 
n
 X i ,   E[ X ]  i 1 pi ,   0
i 1
allora
n



e
Pr[ X  (1   )  ]  
(1 ) 
(
1


)


Inoltre se >2e-1  4,43, allora
F ( ,  )  2

Sistemi P2P
  (1 )

Facciamo un piccolo test
• Supponiamo di lanciare 6000 volte un dado “perfetto” a sei
facce:
– Quale è la probabilità di beccare il 3 almeno 2001 volte?
– Quanto vale ?
(100) (1000) (600) (nessuna delle precedenti)
– Quanto vale ?
(2000)(2)(1)(1000)(nessuna delle precedenti)
– Quale formula applicare?
– Se invece del 3 consideriamo il 4, cambia qualcosa?
Sistemi P2P
Facciamo un piccolo test
• Supponiamo estrarre una carta da un mazzo di 40 carte
napoletane (ripetiamo l’esperimento 400 volte)
– Quale è la probabilità di beccare il 7 “bello” almeno 61 volte?
– Quanto vale ?
(100) (10) (40) (nessuna delle precedenti)
– Quanto vale ?
(5)(2)(1)(1000)(nessuna delle precedenti)
– Quale formula applicare?
Sistemi P2P
Join e Stabilization
Crea Anello Vuoto
Join
n=N26,
n’=qualunque nodo attivo
Stabilize
n=N26
n=N21
Sistemi P2P
Join e Stabilization
• Altre operazioni periodiche ma utilizzate con
frequenza minore sono fix.finger e check.predecessor
Sistemi P2P
Chord: Join
• Abbiamo visto che la procedura join appena definita non
completa l’aggiornamento di tutti i link necessari.
• Al fine di aggiornare tutti i link del nodo sono necessari alcuni
runs di stabilize (che comprende inoltre la notify) e m (O(log
N) whp) runs della procedura fix.finger (sia da parte del nodo
che ha effettuato la join sia da parte di altri nodi che devono
aggiornare uno dei finger al nuovo nodo)
– Chord non è simmetrico (Se un nodo n ha un finger su n’ non è detto
che n’ ha un finger su n)
• Non è possibile avvertire i nodi che devono aggiornare i fingers
• E’ inoltre necessario far migrare le risorse al nuovo
responsabile (il protocollo Chord non gestisce questo
problema e lo rimanda all’applicazione).
Sistemi P2P
Chord: Join
• La correttezza dei link al successore basta a
garantire la correttezza delle lookup
• Lazy Join
– Inizializza solo il successore
– Periodicamente verifica successore e predecessore
– Periodicamente (ma meno spesso) rinfresca il
contenuto della tavola dei finger
Sistemi P2P
Chord: Join e Lookup
• Cosa succede alla lookup a seguito di
operazioni di Join?
– L’operazione di Join è completamente terminata ->
nessun problema
– L’operazione di Join è parzialmente terminata -> la
lookup potrebbe essere rallentata
– L’operazione di Join è incompleta (puntatori errati
oppure le risorse si trovano in una posizione
inconsistente rispetto ai link nella rete) -> la
lookup potrebbe fallire
Sistemi P2P
Chord: Risultati Join
n
Vale il seguente lemma:
x
p
s
y
Se al tempo t esiste una path tra x ed y, allora per ogni
t’>t ci sara’ una path tra x ed y
Per induzione sul tempo.
Supponiamo che dopo t il nodo n effettua una join tra p e s due nodi nella
path da x a y. 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 (stabilize di p)
da s ad n. Questo avviene perchè p ha contattato s ed s gli ha detto di n.
Inoltre p<n<s.
Sistemi P2P
Chord: Risultati Join
n
x
p
s
y
s ha saputo di n ad un tempo precedente e questo può essere
avvenuto solo perchè s è stato un successore diretto di n (cioè
dopo la stabilize di n).
Per ipotesi induttiva se esisteva un path tra n ed s, esiste un path
tra n ed s in tutti gli istanti successivi.
In particolare nell’istante in cui p cambia il successore. Essendo
p<n<s il cambiamento del successore di p non influisce in alcun
modo sulla path tra p ed s.
Inoltre anche dopo il cambiamento esiste una path tra p ed s.
Sistemi P2P
Chord: Risultati Join
Tutti le path 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
successore saranno corretti per tutti i nodi
Sistemi P2P
Chord: Risultati Join
E’ possibile mostrare il seguente teorema:
Se ogni operazione di join è 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.
Sistemi P2P
Chord: Risultati Join
E’ possibile mostrare il seguente teorema:
Se abbiamo una rete stabile con N nodi ed effettuiamo N join
alla rete, e se tutti i puntatori ai successori sono corretti, allora il
Lookup di una risorsa avrà necessità di O(log N) hops con alta
probabilità.
In altre parole se il tempo richiesto per aggiustare tutti i fingers è
minore del tempo richiesto dalla rete per raddoppiare in taglia
allora la lookup non viene asintoticamente rallentata.
Sistemi P2P
Chord: Risultati Join
Dim
Se utilizziamo i vecchi finger arriviamo in O(log N) hops al
vecchio predecessore della risorsa. In media ogni due nodi
contattati uno è vecchio e quindi ha la tabella di routing corretta.
Se i successori dei nuovi nodi sono corretti, in al più O(log N)
passi la risorsa sarà raggiunta.
Sistemi P2P
Chord: Failure and Replication
• Abbiamo detto che la correttezza del routing è garantita dal
fatto che ogni nodo conosce in ogni istante il proprio
successore
• Tuttavia questa invariante può essere compromessa dal fatto
che i nodi possono “cadere”
• Per migliorare la robustezza del protocollo ogni nodo utilizza
una lista di r successori (di solito r=log N)
• Quando il successore di un nodo n cade, n sostituisce tale
successore con la seconda entry nella tabella dei successori e
successivamente provvede a ricercare il successore r-esimo.
• In particolare, è possibile “rompere” il sistema solo se tutti e r i
successori di un nodo cadono quasi contemporaneamente
Sistemi P2P
Chord: Failure and Replication
• Assumiamo che p sia la probabilità che un nodo cade
all’istante t. La probabilità che r successori cadono
contemporaneamente è pr
• La presenza della tabella dei successori richiede
alcuni cambiamenti nel protocollo:
– La procedura stabilize si deve preoccupare di mantenere corretta la
tabella dei successori
• Il nodo n copia la tabella dei successori dal suo successore s ignora
l’ultima entry e aggiunge in testa a tale tabella il proprio successore
s
• Quando qualche successore fallisce il nodo n contatta il primo
successore vivo s’ e successivamente ripristina la tabella dei
successori utilizzando la tabella di s’
Sistemi P2P
Chord: Failure and Replication
– E possibile inoltre modificare la procedura closest preceding
finger in modo da valutare oltre alla tabella dei fingers anche i
successori. (si ottengono miglioramenti ma il costo della
lookup rimane O(log N))
– Inoltre è necessario modificare la procedura lookup
(findsuccessor) che fallisce se incontra un successore down (la
procedura infatti viene rilanciata dopo un breve intervallo di
tempo, che dovrebbe servire a ripristinare il link al successore)
Sistemi P2P
Chord: Failure and Replication
Risultati
• Assumiamo che la lista dei successori è lunga
r=(log N)
• Teorema
– In una rete inizialmente stabile, se assumiamo che
ciascun nodo cade con probabilità ½, allora la lookup
sarà corretta
Dim
Affinchè la lookup sia corretta è necessario che l’anello
non sia rotto. L’anello si rompe con probabilità
(1/2)r=1/Nk se r= k log N
Sistemi P2P
Altamente
improbabil
Chord: Failure and Replication
Risultati
• Assumiamo che la lista dei successori è lunga
r=(log N)
• Teorema
– In una rete inizialmente stabile, se assumiamo che
ciascun nodo cade con probabilità ½, allora WHP la
lookup impiega O(log N) msg
Dim sketch
Se ogni nodo è caduto con probabilità 1/2 , ogni due link ne
funziona almeno 1,
Se il finger di cui abbiamo necessità è caduto possiamo usare un
finger più corto: invece di dimezzare la distanza la riduciamo a
circa ¾ della distanza precedente. Ma log4/3 N = O(log N).
Sistemi P2P
Chord: Failure and Replication
• Consisten Hashing
– Il fatto che l’assegnazione degli ID avviene utilizzando consistent
hashing, non è possibile per un avversario creare dei nodi in una
posizione prefissata del ring.
• Non è possibile appropriarsi di una risorsa
• Non è possibile rompere l’anello utilizzando r nodi fittizi
• Siccome abbiamo visto che gli r successori di un nodo n cadono
contemporaneamente con bassissima probabilità è naturale pensare
a questi nodi per le repliche delle risorse gestite dal nodo n.
– Altre possibilità
• Diverse funzioni hash
• Repliche in posizioni speculari (Es r repliche)
(ID, ID+2m/r mod 2m, ID+2 2m/r mod 2m, , ID+(r-1) 2m/r mod 2m)
Sistemi P2P
Chord: Leave
• Siccome il protocollo descritto finora è corretto anche in
caso di fallimenti per i nodi potremmo gestire la leave
come un fallimento, tuttavia è preferibile, per migliorare
le prestazioni del sistema, adottare alcuni accorgimenti,
quando un nodo si disconnette volontariamente dalla rete
– Il nodo che lascia la rete
• trasferisce le proprie risorse al suo successore
• notifica ai propri vicini (predecessore e successore) che sta
uscendo dal sistema. In particolare comunica il predecessore
al suo successore e il successore al suo predecessore, in
questo modo i due vicini possono connettersi senza utilizzare
la stabilize/notify
Sistemi P2P
Chord: Realistic Analysis
• Il sistema appena descritto è un sistema dinamico
particolarmente difficile da analizzare analiticamente
(senza esemplificazioni). In particolare tutte le
dimostrazioni analizzate partono da una configurazione
stabile, tuttavia:
“a Chord ring will never be in a stable state;
instead, joins and departures will occur continuously,
interleaved with the stabilization algorithm. The ring
will not have time to stabilize before new changes
happen.”
Sistemi P2P
Chord: Valutazione
• Lookup veloci in sistemi di grandi dimensioni
• Variazione contenuta del costo di lookup
• Robusto rispetto a molti tipi di fallimento
• Gli esperimenti confermano i risultati teorici
Sistemi P2P
Chord: Valutazione
il costo è O(log N) come previsto dalla teoria
Average Messages per Lookup
la costante è 1/2
Sistemi P2P
Number of Nodes
Conclusioni
• A differenza dei sistemi precedenti, Chord si adatta
ad ambienti dinamici (tipici dei sistemi P2P)
• Based on theoretical work (Consistent Hashing)
• Proximity-based routing
• Chord è uniforme (routing greedy è ottimale)
• Chord non è simmetrico
– Alcune procedure causano utilizzo di banda anche se non ci
sono cambiamenti nella rete
• La Join costa O(log2 N)
Sistemi P2P
Riferimenti
•
•
•
•
•
http://www.pdos.lcs.mit.edu/chord/
http://www.napster.com/
http://www.gnutella.com/
http:// www.openp2p.com/
S. Ratnasamy, S. Shenker, and I. Stoica. “Routing
algorithms for DHTs: Some open questions”. In 1st
International Peer To Peer Systems Workshop (IPTPS’02).
• I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F.
Kaashoek, F. Dabek, H. Balakrishnan, “Chord: A Scalable
Peer-to-peer Lookup Protocol for Internet
Applications”. In IEEE/ACM Trans. on Networking, 2003.
Sistemi P2P
Facciamo un piccolo test
• Partendo dalla figura, descrivere la procedura Join
• Descrivere le varie tecniche di replicazione e
analizzarne vantaggi e svantaggi
• In una rete inizialmente stabile, se assumiamo che
ciascun nodo cade con probabilità ½, allora la lookup
impiega
(N) (½ log N) (m) (nessuna prec.)
c
a
Sistemi P2P
b
Consistent Hashing [Karger et al 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
Sistemi P2P
Consistent Hashing [Karger et al 97]
Sistemi P2P
Consistent Hashing [Karger et al 97]
• Nasce come una tecnica per replicare i dati nei
sistemi C/S
• Problema: memorizzare una copia dei dati
messi a disposizione dal Server su un pool di
Client
– Load balancing
– Fast recovery
• Le funzioni Hash mappano chiavi (risorse) in
interi.
Sistemi P2P
Consistent Hashing [Karger et al 97]
• Con N Client una possibile funzione è
x -> ax+b (mod N)
• Cosa accade se varia N?
– Buona parte dei dati va riposizionata
• Se la usassimo in un sistema P2P?
– N varia continuamente
– nessuno sa precisamente quanto vale N
Sistemi P2P
Consistent Hashing [Karger et al 97]
x -> ax+b (mod N)
• In particolare se varia N:
– è 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
Sistemi P2P
Consistent Hashing [Karger et al 97]
• Desiderata
– Vogliamo che quando N varia (cioè un nodo entra
o esce dal sistema)
• la quantità di dati che viene rimappata nel sistema è
bassa
• le posizioni in cui un generico dato (risorsa) è mappato
sono limitate
• i dati vengono assegnati in maniera bilanciata su tutti i
nodi
Sistemi P2P
Consistent Hashing [Karger et al 97]
In altre parole, per definizione un Consistent
Hashing deve godere di opportune proprietà:
Bilanciamento
Monotonicità
Spread
Carico
Sistemi P2P
Consistent Hashing [Karger et al 97]
• Sia I l’insieme delle risorse e B l’insieme delle
possibili posizioni
• Ovviamente le possibili configurazioni del
sistema sono 2B
• Quello che cerchiamo è una funzione
f:2B  I -> B
• Se V è una configurazione (V2B) è ovvio che
f(V,id)  V, per qualsiasi id
Sistemi P2P
Consistent Hashing [Karger et al 97]
Bilanciamento:
Per ogni sottoinsieme V di posizioni (nodi) ed |I| dati, il numero
di dati per ogni posizione è O(|I|/|V|) con alta probabilità.
Monotonicità:
I dati si devono
muovere solo se è
necessario
Se al variare di N 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\V1, ma non a V1 .
Se V1  V2, f(V2, i) V1 allora f(V1, i) = f(V2, i)
Sistemi P2P
Consistent Hashing [Karger et al 97]
Spread:
Al variare di N, il numero di posizioni che un dato può assumere
è limitato.
Carico:
Al variare di N, il numero di dati che una posizione accoglie è
limitato.
Sistemi P2P
Consistent Hashing [Karger et al 97]
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
F: La chiave i viene memorizzata nel nodo j se la differenza
|K(i)-N(j)| è la minima su tutti i nodi j.
Sistemi P2P
Consistent Hashing [Karger et al 97]
0
F precedentemente definito:
Bilanciamento ?
Monotonicità ?
Spread ?
Carico ?
Sistemi P2P
1