CHORD Progettazione e realizzazione di un protocollo per la locazione di dati nel distribuito
description
Transcript of CHORD Progettazione e realizzazione di un protocollo per la locazione di dati nel distribuito
Presentazione del progetto di:Reti di calcolatori L-S
Matteo CorbelliMatteo Corbelli
SommarioSommarioObiettivi
Descrizione del Sistema
Implementazione
Conclusioni
ObiettiviObiettiviRealizzazione un’infrastruttura per la
locazione di file nel distribuitoAssegnamento di una chiave per ogni fileRicerca per tale chiave del nodo responsabile e
allocazione
Implementazione delle operazioni di gestione dei nodi del sistemaJoinLeave
Architettura del SistemaArchitettura del SistemaL’architettura è quella di un anello “identifier
circle”La posizione di un nodo è data dall’identificativo
assegnatole dalla funzione hashOgni chiave k viene assegnata al primo nodo il
cui identificativo è uguale o segue k nello spazio degli identificativi
Struttura di un nodoStruttura di un nodoOgni nodo ha la seguente struttura
• Successore• Predecessore• Finger Table: tabella di m elementi (serve per l’efficienza dell’algoritmo)• Vettore delle chiavidi cui il nodo è responsabile
I-esimo elemento della finger tableFinger[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 SistemaFunzionalità del SistemaLocazione di una chiave
Join di un nodo n
Leave di un nodo
Locazione di una chiaveLocazione di una chiaveOgni id di una chiave k viene assegnato al nodo
successore successor(k)
Le richieste possono essere passate lungo l’anello attraverso i successori
Inefficienza (potrebbe richiedere di esplorare tutto l’anello)
Utilizzo delle Finger Table
Cosa succede se il nodo n non conosce il successore di k?Es. nodo 3 vuole trovare successor(1)
Implementazione della locazioneImplementazione della locazioneAllocazione 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
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)
Caso 1: keyId non compreso tra l’id del nodo e l’id del suo successore
n restituisce l’i-esimo finger per cui
keyId appartiene a finger[i].interval a
cui inoltrare una nuova richistaredirect_request(n.finger[i])
Join di un nodo nJoin di un nodo nOgni nodo n che entra nel sistema deve eseguire
tre fasi:1. Inizializzare predecessore, successore e Finger Table2. Aggiornare Finger Table, successori e predecessori per
riflettere l’aggiunta di n3. 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 JoinImplementazione del JoinInizializzazione predecessore, successore e Finger
Table da parte del nodo con identificativo nodeId attraverso il nodo conosciuto n1. Richiesta find_predecessor(nodeId) al nodo n per trovare il
predecessore di nodeId2. Ricezione del nodo che precede e del suo successore find(n,
n.successor)3. Inizializzazione del predecessore a n e del successore a
n.successor4. Aggiornamento del predecessore set_successor(this)5. Aggiornamento del successore set_predecessor(this)6. Inizializzazione della Finger Table
Anticipati per evitare
overhead di comunicazione
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 JoinImplementazione del JoinAggiornamento 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
2.l’i-esimo finger del nodo p succede n
Calcola id=n-2i-1 e ricerca il suo predecessorefind_predecessor(id)
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)
Verifica positiva1.Modifica dell’i-esimo finger2.Restituzione del predecessore(iterazione dell’operazione)Verifica negativa1.Terminazione
Implementazione del JoinImplementazione del JoinNotifica 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 implementazioneLeave di nodo e implementazioneOgni 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)
ConclusioniConclusioniE’ stato sviluppato un sistema per la
locazione di file nel distribuito
Sviluppi Futuri1. Tolleranza alla caduta di un nodo non
volontaria2. 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