Presentazione del progetto di:
Reti di calcolatori L-S
Matteo Corbelli
Sommario
 Obiettivi
 Descrizione del Sistema
 Implementazione
 Conclusioni
Obiettivi
 Realizzazione un’infrastruttura per la locazione di file
nel distribuito
 Assegnamento di una chiave per ogni file
 Ricerca per tale chiave del nodo responsabile e
allocazione
 Implementazione delle operazioni di gestione dei nodi
del sistema
 Join
 Leave
Architettura del Sistema
 L’architettura è quella di un anello “identifier circle”
 La posizione di un nodo è data dall’identificativo
assegnatole dalla funzione hash
 Ogni chiave k viene assegnata al primo nodo il cui
identificativo è uguale o segue k nello spazio degli
identificativi
Struttura di un nodo
 Ogni nodo ha la seguente struttura
• Successore
• Predecessore
• Finger Table: tabella di m elementi
(serve per l’efficienza dell’algoritmo)
• Vettore delle chiavi
di cui il nodo è responsabile
 I-esimo elemento della finger table
 Finger[i].start = (n+2i-1)mod 2m
 Finger[i].interval = [finger[i].start,finger[i+1].start)
 Finger[i].node = primo nodo maggiore o uguale a finger[i].start
Funzionalità del Sistema
 Locazione di una chiave
 Join di un nodo n
 Leave di un nodo
Locazione di una chiave
 Ogni id di una chiave k viene assegnato al nodo successore
successor(k)
Le richieste possono essere passate
lungo l’anello attraverso i successori
Utilizzo delle Finger Table
Cosa succede se il nodo n
non conosce il successore di k?
Es. nodo 3 vuole trovare successor(1)
Inefficienza (potrebbe richiedere
di esplorare tutto l’anello)
Implementazione della locazione
 Allocazione di un dato, con identificativo keyId, attraverso
l’indirizzo di un nodo n della rete conosciuto
Richiesta find_successor_key(keyId) al nodo n
per trovare il successore di keyId
n restituisce l’i-esimo finger per cui
keyId appartiene a finger[i].interval a
cui inoltrare una nuova richista
redirect_request(n.finger[i])
Caso 1: keyId non compreso tra l’id
del nodo e l’id del suo successore
Caso 2: keyId compreso tra l’id del
nodo e l’id del suo successore
1.
n restituisce il successore
find(n.successor)
2. viene effettuato sul nodo restituito il
trasferimento del dato transfer(keyId)
Join di un nodo n
 Ogni nodo n che entra nel sistema deve eseguire tre fasi:
1.
2.
3.
Inizializzare predecessore, successore e Finger Table
Aggiornare Finger Table, successori e predecessori per riflettere
l’aggiunta di n
Notificare a livello software più alto in modo che si possa trasferire
lo stato associato alle chiavi di cui il nodo n ora è responsabile
Implementazione del Join
 Inizializzazione predecessore, successore e Finger Table da
parte del nodo con identificativo nodeId attraverso il nodo
conosciuto n
1.
2.
3.
4.
5.
6.
Richiesta find_predecessor(nodeId) al nodo n per trovare il predecessore di
nodeId
Ricezione del nodo che precede e del suo successore find(n, n.successor)
Inizializzazione del predecessore a n e del successore a n.successor
Aggiornamento del predecessore set_successor(this)
Anticipati per
Aggiornamento del successore set_predecessor(this)
evitare overhead di
comunicazione
Inizializzazione della Finger Table
n controlla se l’i-esimo finger è anche l’i+1-esimo finger corretto, per ogni i. Questo avviene
quando finger[i].interval non contiene alcun nodo, e quindi finger[i].node >= finger[i+1].start
Implementazione del Join
 Aggiornamento delle Finger Table dei nodi del sistema
Il nodo n diventerà l’i-esimo finger del nodo p se e solo se:
1. p precede n di almeno 2i-1
Calcola id=n-2i-1 e ricerca il suo predecessore
find_predecessor(id)
2. l’i-esimo finger del nodo p succede n
Verifica positiva
1. Modifica dell’i-esimo finger
2. Restituzione del predecessore
(iterazione dell’operazione)
Verifica negativa
1.
Terminazione
Al nodo restituito invia la richiesta di aggiornamento
update_finger_table(this,i)
Il nodo verifica se l’i-esimo finger deve essere
modificato
(l’id del nuovo nodo è compreso tra il proprio id
e quello dell’i-esimo finger)
Implementazione del Join
 Notifica per il trasferimento di file
1.
Connessione al successore (attuale responsabile di tutte le chiavi
che potrebbero migrare nel nodo n) update_vector_key(this.id)
2.
Il successore per ogni chiave che detiene verifica se è ancora
sotto la sua responsabilità o meno
3.
In caso non sia più suo compito tenere la chiave si passa al
trasferimento transfer(keyId)
Leave di nodo e implementazione
 Ogni nodo n quando lascia il sistema deve:
1.
Rimuovere se stesso da successore e predecessore di altri nodi
set_predecessor(this.successor) set_successor(this.predecessor)
2.
Rimuovere i riferimenti a se dalle Finger Table (procedura simile a
quella di aggiornamento)
delete_me_from_finger_table(this.id,i,this.successor)
3.
Trasferimento di tutti i propri dati al successore
transfer_key(keyId)
Conclusioni
 E’ stato sviluppato un sistema per la locazione di file
nel distribuito
 Sviluppi Futuri
1. Tolleranza alla caduta di un nodo non volontaria
2. Implementazione di un algoritmo meno invasivo ma
più efficiente in cui le finger table non vengono
aggiornate ad ogni join ma ad istanti di tempo