Localizzare un
nodo, in una
rete nel quale si è
mappato un particolare
dato,è diventato un problema d'interesse, nell'ambito dei
SISTEMI DISTRIBUITI.
Questo problema, è diventato un
caso di studio, dei
SISTEMI CHORD: esso va a
mappare la
chiave di un
dato all'interno di un
nodo in modo che essi possano essere facilmente localizzati.
In particolare, i
CHORD, sono
SISTEMI PEER TO PEER DISTRIBUITI strutturati che gestiscono le
entrate ed
uscite dei
nodi.
La
caratteristica più
importante dei
SISTEMI CHORD è che sono costituiti dal
CONSISTENT HASHING che va a garantire l'uniformità del
sistema: i singoli
nodi sono informati su tutti i
nodi del
sistema in modo tale da gestire l'
entrata ed
uscita dei
nodi.
Quando un N-esimo
nodo entra o esce dalla
rete, solo una frazione
O(1/N) di
chiavi viene mossa in una diversa locazione, il che è necessario per mantenere un carico bilanciato.
Inoltre, in una
rete di N-nodi, ogni nodo mantiene informazioni su circa
O(logN)messaggi.
Queste informazioni, vengono date attraverso un'informazione di
routing.
In particolare, l'identificativo di un
nodo è scelto calcolando l'
hash dell'
indirizzo IP del
nodo.
Il
Consistent Hashing assegna le
chiavi ai
nodi, nel seguente modo: gli
identificatori dei
nodi sono ordinati in un modulo 2^m.
La
chiave k, viene
mappata nel
nodo costituito dal più piccolo
identificatore id>=k, diventando quindi il suo
successore e denotato come
successor(k).
La
Figura mostra un “
identifier circle” con m=3. Il circle ha tre nodi: 0, 1, e 3. Il
successore dell’identificativo 1 è 1, così la chiave 1 dovrebbe essere allocata al nodo
1.
Similmente la chiave 2 dovrebbe essere allocata al nodo 3, e la chiave 6 al nodo 0.
All'interno di un SISTEMA CHORD, i nodi posso entrare o uscire dal sistema ad ogni momento.
Proprio per questo motivo, le FINGER TABLE devono essere corrette.
Per semplificare i meccanismi di entrata e
uscita, ogni nodo in Chord mantiene un puntatore al predecessore. Il puntatore al
predecessore di un nodo contiene il Chord identifier e l’indirizzo IP dell’immediato
predecessore di tal nodo, e può essere usato per percorrere in senso antiorario l’
“identifier circle”.
In particolare, l'entrata di un nodo nell'anello si svolge in tre passi:
Join: operazione che si connette al nodo conosciuto ed invia la richiesta di find_successor a tale nodo, che, in modo del tutto simile a quello descritto al caso in cui si cerca la
locazione di una chiave, trovando il predecessore dell’identificativo del nodo
specificato, restituisce se stesso e il suo successore permettendo così al nodo di
settare il suo predecessore (il nodo stesso) e il suo successore.
Aggiornamento:nella fase di aggiornamento il nodo deve permettere alle finger table degli altri nodi di aggiornarsi;
Trasferimento dati: il nodo si connette al suo succesore, il quale al momento attuale tiene la responsabilità di tutti i dati che devono essere spostati.
Il nodo invece lascia il sistema, attraverso l'operazione leave:le fasi sono le stesse utilizzate per gestire l'uscita di un nodo.
Il SISTEMA CHORD, è una struttura ad anello nel quale ogni nodo ha questa struttura:
-Successore: nodo responsabile della chiave che si è mappato in esso
-Predecessore: nodo che precede il nodo selezionato
-Finger Table: tabella di m elementi che servono per l'efficienza dell'algoritmo
-Vettor delle chiavi di cui il nodo è respondabile
