Servizio per la ricerca distribuita basato sul
protocollo
Rossi Daniele
193074
Reti L-S 2005
Architettura
Interfaccia per effettuare la ricerca
Area in cui viene mostrato il risultato
WebServer layer
eBiblioServer layer
ChordNode layer
Reti L-S 2005
Architettura
WebServer layer
eBiblioServer layer
ChordNode layer
WebServer basato sul progetto Cassini
Si pone in ascolto sulla porta 80 del nodo locale
Interpreta le richieste provenienti dall’interfaccia Web
Interroga il livello sottostante e fornisce una rappresentazione
del risultato come pagina html
Supporta l’interrogazione a partire dal codice ISBN di un’opera
Si pone in ascolto sulla porta 6001 del nodo locale
Gestisce la replicazione delle informazioni sui nodi della rete
Interroga il livello sottostante per individuare il nodo della rete che
mantiene l’informazione cercata
Supporta l’interrogazione a partire dalla chiave di una risorsa
Implementa il protocollo di rete CHORD
Si pone in ascolto sulla porta 6000
Gestisce bilanciamento di carico, disponibilità e scalabilità
Gestisce join e leave multiplo di nodi
Reti L-S 2005
Introduzione P2P: cos’è?
“Peer-to-peer systems and applications are distributed systems without any
centralized control or hierarchical organization, where the software running at
each node is equivalent in functionality.” [SMK+01]
Usi comuni:
Archiviazione ridondante
Permanenza
Ricerca
Autenticazione
Naming gerarchico
Computazione Distribuita (ad es. SETI@Home)
Reti L-S 2005
Tipologie di lookup
Lookup centralizzato (Napster)
Architettura ibrida.
Più server centrali risolvono le ricerche.
Search
Publish
Publish
Flooded queries (Gnutella)
Peer to Peer puro non strutturato
Ogni nodo invia ricorsivamente la richiesta
ai propri vicini.
Routed Queries
Architettura pura strutturata.
Ogni peer attua politiche di routing
Reti L-S 2005
Protocollo scalabile per il lookup di chiavi in un sistema peer-to-peer con frequente
arrivo e abbandono di nodi.
Un nodo può entrare o uscire dalla rete in ogni momento
0
7
Ad ogni nodo e risorsa è assegnata una chiave univoca tramite un
algoritmo di consistent hasing
Ogni chiave è mappata in un dato instante su un unico nodo della rete
Load balance
Decentralization
6
2
Scalability
La responsabilità di una chiave può spostarsi da un nodo all’altro
quando i nodi si disconnettono.
Availability
La gestione delle risorse associate alle chiavi è lasciata a protocolli di
livello applicativo
La chiave k viene assegnata al
primo nodo attivo il cui id è uguale
o maggiore all’identificativo k della
chiave. O(N) per il lookup
1
5
3
4
Utilizzo di una tabella di Routing
riduce fino a O(log(N)) il numero di
nodi contattati in un lookup
Reti L-S 2005
Routing : Finger Table
Notazione
Definizione
Finger[k].start
(n+2k-1) mod 2m, 1≤k ≤m
.interval
[finger[k].start,finger[k+1].start)
.node
first node≥n.finger[k].start
successor
the next node on the identifier circle
finger[1].node
predecesor
the previous node on the identifier circle
Ogni nodo ha una forte conoscenza dei
nodi a lui vicini nell‘ anello e una
conoscenza sempre più vaga sui nodi
distanti.
80+25
80+24
L’ i-esima riga della finger table del
nodo n contiene l’identificatore del
nodo che lo segue di almeno 2 (i-1)
posizioni nell’anello
80+23
L’idea è quindi quella di
raddoppiare ad ogni passo la
distanza a cui si cerca il nodo
responsabile di una chiave.
80+22
80+21
80+20
Reti L-S 2005
N80
Multiple Node Join
La Multiple Join NON notifica al resto della rete l’ingresso del nodo n
Ogni nodo esegue periodicamente un protocollo di stabilizzazione per mantenere aggiornato il
proprio successore e predecessore
Stabilize()
Chiede al suo successore, il predecessore
x = (finger[1].node).Find_Predecessor();
if ( x in [ n , finger[1].node )
finger[1].node = x;
(finger[1].node).Notify(n);
Se la rete non è stabilizzata, x potrebbe essere
il nuovo successore. In tal caso aggiorna
l’informazione
Notifica al successore (eventualmente aggiornato)
che n potrebbe essere il suo nuovo predecessore
Notify(n’)
if ( predecessor is null or n’ in [ predecessor , n )
predecessor = n’;
Se non c’è predecessore (es. nodo in
corso di join) o n’ è il nuovo
predecessore, aggiorna l’informazione
Algoritmo Utilizzato nel progetto
Reti L-S 2005
Lookup e fallimento di nodi
Un lookup effettuato prima che la stabilizzazione abbia finito può terminare:
1) Correttamente: tutte le finger table sono ragionevolmente corrette nonostante
il cambiamento dell’anello
2) Correttamente ma dopo molto tempo: le finger tables sono inaccurate ma i nodi
successori sono corretti.
3) Fallendo: l’anello è in uno stato inconsistente al momento del lookup
Gestione di fallimenti multipli
Chord prevede che ogni nodo k mantenga anche una lista
degli O (log(N)) successori.
Se il nodo n si accorge che il suo successore è fallito, lo
sostituisce con la prima entry valida nella sua lista dei
successori.
Ogni nodo è in grado di recuperare dal fallimento degli
r-1 nodi a lui successivi
Reti L-S 2005
TCP – Implementazione ricorsiva
lookup
??
La richiesta di lookup si propaga
lungo il percorso di routing fino ad
individuare il nodo responsabile della
chiave.
Ogni nodo esegue, se necessario, il forward
della richiesta scegliendo il nodo più
opportuno tra quelli presenti nella sua finger
table.
Una volta individuato il successore della
chiave cercata, la risposta viene propagata
in backward
lookup
lookup
PROBLEMA
Sia il nodo di origine, sia i nodi
intermedi rimangono a lungo impegnati
in attesa della risposta
uso di meccanismi sincroni non
bloccanti (?)
Reti L-S 2005
TCP – Implementazione iterativa
La richiesta di lookup non si propaga.
??
Il nodo che deve eseguire il lookup, contatta
iterativamente nodi sempre più prossimi a
quello responsabile della chiave.
L’algoritmo, a livello implementativo, cerca
il predecessore più prossimo del nodo
responsabile della chiave e, una volta
individuato, lo interroga per conoscere il
suo successore (cioè il nodo effettivamente
cercato).
successor
Ogni nodo a cui viene domandato il
predecessore della chiave, restituisce il
nodo che, limitatamente alle informazioni in
suo possesso, pensa che sia il predecessore.
successor
L’algoritmo termina quando il predecessore
restituito nP è tale per cui key appartiene
all’intervallo
predecessor
( key , key.successor ]
Reti L-S 2005
Acquisizione delle risorse
Successore di N
N
Ipotesi di Single Fail
Le risorse associate alle chiavi del nodo N, sono attualmente
allocate sul successore di N
N le richiede al suo successore non appena entra in rete
L’azione di richiesta è a carico del nuovo nodo
Il successore di N già dispone delle risorse replicate
Non è garantita persistenza della informazioni se N e il suo
successore dovessero andare in crash nello stesso momento
Reti L-S 2005
Replicazione
Nuovo successore
N
Le risorse associate alle chiavi del nodo N, vengono replicate sul
nuovo successore
In caso di crash di N il nuovo successore è in grado di rispondere
correttamente
Ipotesi di Single Fail
N
N1
Le risorse associate alle chiavi del nodo N1 sono ora di competenza di N
(precedentemente replicate da N1 su N)
N deve ora replicare le risorse associate alle nuove chiavi di sua
competenza sul suo successore
Reti L-S 2005
Conclusioni finali
Il progetto realizzato
fornisce un esempio di applicazione di ricerca di informazioni su rete distribuita
utilizza un protocollo di rete (CHORD) efficiente e robusto, trattando in particolare gli
aspetti di scalabilità, bilanciamento di carico e disponibilità
introduce un livello superiore al protocollo di rete per trattare la replicazione delle
informazioni distribuite sui nodi
Sviluppi futuri
estensione del protocollo CHORD per gestire il recovery in caso di network partition
miglioramento della replicazione, estendendola al caso di fallimento di più nodi
consecutivi contemporaneamente
ampliamento della interfaccia lato utente e della gestione delle informazioni sui
singoli nodi
Reti L-S 2005