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