Modulo PeerServices - Analisi Funzionale
Instrada i messaggi (ricevuti da altri nodi o generati dal nodo stesso) che sono destinati ad un dato hash-node.
Mantiene le informazioni necessarie.
Idea generale
Il funzionamento dei servizi peer-to-peer si basa sulla definizione di una funzione che associa ad una chiave k univocamente un nodo esistente nella rete al quale indirizzare delle richieste. Si può opzionalmente aggiungere il requisito che il nodo sia "partecipante" al servizio.
Sia S lo spazio di indirizzi validi per i nodi della rete.
Sia Vt il set di nodi nella rete al tempo t.
Sia αt : S → Vt la funzione suriettiva che al tempo t associa ad un indirizzo il nodo che lo detiene. E' suriettiva in quanto ogni nodo ha almeno un indirizzo. E' una funzione non completamente definita in S poiché un indirizzo potrebbe non essere stato assegnato ad alcun nodo.
Definiamo una funzione che al tempo t assegni ad ogni indirizzo in S un indirizzo nel dominio di αt. Cioè dato un indirizzo valido che potrebbe non essere stato assegnato tale funzione ritorna un indirizzo assegnato.
Ht : S → dom(αt)
DHT: Distributed Hash Table
Sia p un servizio, sia K lo spazio delle chiavi definito da questo servizio. Il servizio p definisce una funzione di hash che mappa lo spazio delle chiavi sullo spazio degli indirizzi.
hp : K → S
Quando un nodo, al tempo t, vuole scrivere la coppia chiave-valore (k, v) nel database distribuito il nodo calcola:
hash_node(k) = αt ( Ht ( hp ( k ) ) )
Contatta quindi il nodo hash_node(k) e chiede di memorizzare la coppia (k, v).
Analogamente il nodo che vuole reperire il dato associato alla chiave k, calcola hash_node(k) e chiede di leggere il dato associato a k.
Questo procedimento realizza un database distribuito, perché ogni nodo mantiene solo una porzione delle associazioni chiave-valore.
Fondamentale è la funzione Ht. Definiamo la funzione Ht(x) come l'indirizzo x’ associato ad un nodo esistente (x’ ∈ dom(αt)) che minimizza la distanza x - x’, in modo più rigoroso minargx’∈dom(αt)dist(x,x’). La funzione dist rappresenta in modo intuitivo la distanza tra due indirizzi, ma è definita in modo che la funzione Ht "cerchi" il primo indirizzo valido "procedendo verso destra" fino al gsize per poi ripartire da 0. Questo comportamento ci ritornerà utile in seguito. Precisamente la funzione dist(x,y) si calcola così:
x è formato da x0·x1·...·xl-1.
y è formato da y0·y1·...·yl-1.
- distanza = 0;
- Per j da l-1 a 0:
se xj == yj:
- distanza += 0;
altrimenti se yj > xj:
distanza += yj - xj;
- altrimenti:
distanza += yj - xj + gsize[j];
se j>0:
- distanza *= gsize[j-1];
HDHT: Hierarchical DHT
In una struttura gerarchica come Netsukuku un nodo non ha la conoscenza di tutti i nodi esistenti nella rete, quindi non può da solo computare la funzione Ht in quanto non conosce per intero dom(αt). L'implementazione avviene in modo distribuito.
Sia n un nodo che vuole inviare un messaggio m all'hash-node della chiave k per il servizio p. Il nodo n usa la funzione hp definita da p per calcolare dalla chiave k l'indirizzo x. A questo punto dovrebbe calcolare x’=Ht(x). Procede così:
Il nodo n ha indirizzo n0·n1·...·nl-1. Ha inoltre conoscenza di:
tutti i nodi appartenenti a n1,
tutti i g-nodi di livello 1 appartenenti a n2,
- ...
tutti i g-nodi di livello l-2 appartenenti a nl-1,
- tutti i g-nodi di livello l-1.
Questa conoscenza la possiamo chiamare domn(αt), cioè il dominio della funzione αt secondo le conoscenze di n.
x è formato da x0·x1·...·xl-1.
Il nodo n calcola Ht(x) secondo le sue conoscenze, cioè trova un livello j e un identificativo yj tali che:
yj ∈ nj+1, oppure j == l-1.
Il gnodo yj è quello, fra le conoscenze di n, che minimizza la funzione dist(x, yj).
yj ≠ nj.
se j == 0 allora n ha trovato con le sue sole conoscenze y0 = Ht(x).
come caso estremo n potrebbe trovare che esso stesso è il definitivo Ht(x). In questo caso l'algoritmo termina e si passa subito all'esecuzione del messaggio m.
Se j > 0 allora il nodo n non conosce l'interno del gnodo yj. Ma la sua esistenza implica che nella rete esistono uno o più nodi al suo interno e tra questi senz'altro quello che ha l'indirizzo y che minimizza la funzione dist(x,y).
Il nodo n e il nodo y (il destinatario del messaggio m) hanno in comune il g-nodo nj+1. Tutto il percorso che il messaggio deve fare è all'interno di questo g-nodo; quindi ogni singolo nodo intermedio che riceve il messaggio non necessita, per inoltrarlo, di identificativi a livelli maggiori di j.
Il nodo n prepara un messaggio m’ da inoltrare al gnodo yj. Questo messaggio contiene:
n: la tupla n0·n1·...·nj. Questo dettaglio fa in modo che il coordinatore di un gnodo G sia perfettamente raggiungibile da qualsiasi nodo all'interno di G anche mentre G sta gradualmente migrando.
x: la tupla x0·x1·...·xj-1.
lvl, pos: le coordinate del g-nodo che miriamo a raggiungere, cioè j e yj.
pid: l'identificativo del servizio p.
id_msg: un identificativo generato a caso per questo messaggio.
Il nodo n invia il messaggio m’ al suo miglior gateway verso il gnodo yj. Questo invio viene fatto in modo asincrono con protocollo reliable (TCP).
- Il nodo n tiene a mente per un certo periodo l'id del messaggio in attesa di una risposta. Se passa un certo tempo si considera fallito l'invio del messaggio m all'hash-node della chiave k. Cioè è lanciata una eccezione al metodo p2p.
Il messaggio m’ viene così inoltrato:
Il nodo v riceve un messaggio m’.
- Il nodo v confronta il proprio indirizzo con le coordinate presenti in m’. Se v.pos[m’.lvl] == m’.pos allora il messaggio è giunto al g-nodo che mirava a raggiungere (vedi sotto il proseguimento dell'algoritmo).
- Altrimenti il nodo v inoltra m’ al suo miglior gateway verso il g-nodo (m’.lvl, m’.pos) in modo asincrono con protocollo TCP.
Il messaggio m’ raggiunge un nodo dentro il gnodo che mirava a raggiungere.
- Se m’.lvl == 0 allora il messaggio è giunto alla destinazione finale (vedi sotto il proseguimento dell'algoritmo).
Il nodo v calcola Ht(m’.x) secondo le sue conoscenze relative al suo g-nodo di livello m’.lvl, cioè trova un livello k e un identificativo yk. Sicuramente k < m’.lvl.
Se il nodo v trova che esso stesso è Ht(m’.x) allora il messaggio è giunto alla destinazione finale (vedi sotto il proseguimento dell'algoritmo).
- Il nodo v modifica i seguenti membri del messaggio m’:
- lvl diventa k.
pos diventa yk.
x diventa x0·x1·...·xk-1.
- Il nodo v inoltra m’ al suo miglior gateway verso il g-nodo (m’.lvl, m’.pos) in modo asincrono con protocollo TCP. L'algoritmo prosegue come detto prima con il prossimo nodo che riceve m’.
Il messaggio m’ raggiunge la destinazione finale:
Il nodo v prepara uno stub TCP per connettersi al nodo originante tramite percorso interno (vedi trattazione dei percorsi interni ad un g-nodo nel documento livelli e bits) attraverso la tupla m’.n.
- Una volta realizzata la connessione TCP tra n e v il dialogo consiste in:
- v comunica a n m’.id_msg;
- Se n aveva rinunciato ad attendere la risposta a questo messaggio lo comunica a v e qui si interrompe.
- Altrimenti n comunica a v la chiave k.
v verifica di essere esso stesso, in base alle sue conoscenze, il risultato di Ht ( hp ( k ) ). Se non è così, v lo comunica a n e chiude la comunicazione. n sarà libero di riprovare da capo.
- Altrimenti v conferma a n di essere il destinatario corretto; n comunica a v l'intero messaggio m.
- v elabora il messaggio e risponde a n. Poi la comunicazione si chiude.
- Il nodo n completa il metodo p2p che aveva generato il messaggio, eventualmente ritornando un risultato.
Fault tolerance
Siano n ed m due nodi che conoscono una certa chiave k per un servizio p. Entrambi sono in grado di calcolare x = Ht ( hp ( k ) ) e di contattare x. Sia j il livello massimo tale che x ∉ nj, x ∉ mj. Cioè l'interno del g-nodo xj di livello j a cui appartiene il nodo x è sconosciuto per n e per m. Supponiamo ora che per qualche motivo i messaggi instradati dal modulo PeerServices si perdano all'interno del g-nodo xε (con ε piccolo a piacere), ε < j.
Pur essendo questa anomalia circoscritta ad un g-nodo piccolo a piacere, questo impedirebbe ai nodi n ed m di scrivere e leggere dati con chiave k nel servizio p.
Dopo che n vede fallire il suo tentativo di contattare x per salvare un record con chiave k, n può cercare di isolare il g-nodo malfunzionante; cioè n calcola x’ = Ht ( hp ( k ), exclude_list=[x] ) TODO
Repliche
Quando un nodo v riceve la richiesta di memorizzare (o aggiornare, o rinfrescare) un record con chiave k nella sua porzione del database distribuito si occupa di replicare questo dato su un numero q di nodi replica. L'obiettivo è fare sì che se il nodo muore o si sconnette dalla rete, alla prossima richiesta di lettura del dato venga comunque data la risposta corretta. Quindi v deve scegliere i nodi che saranno contattati per la chiave k quando lui non parteciperà più.
Scelta dei g-nodi di replica
Ovviamente il nodo v verifica di essere il risultato di Ht ( h ( k ) ).
Poi v calcola quale sarebbe stato il secondo miglior candidato, in sua assenza. Anche in questo caso quello che può computare il nodo v è un g-nodo u di livello j, con la funzione Ht ( h ( k ), exclude_list=[v] ) 1 . Riguardo al g-nodo u, v sa che al suo interno esiste almeno un nodo ("partecipante") ma non sa quali e quanti.
Quindi v invia al g-nodo u la richiesta di replicare il record in un massimo di q nodi. Vedremo di seguito come viene comunicato questo messaggio da v ad u, come u lo esegue, come u risponde a v indicando quante repliche ha potuto salvare. Per ora assumiamo che v riceve la risposta da parte del g-nodo u, che gli comunica di aver effettuato w repliche (w <= q) oppure che passato un certo tempo massimo (che dipende dalla dimensione di u, p. es. 2 secondi per il numero di nodi stimati nel g-nodo u) il nodo v consideri il g-nodo u non in grado di soddisfare alcuna replica.
Il nodo v sottrae da q il numero w (oppure 0 se u non ha risposto) e se q > 0 reitera le operazioni partendo dal calcolo di Ht ( h ( k ), exclude_list=[v, u] ). Le operazioni si considerano concluse quando q diventa 0 oppure quando Ht ( h ( k ), exclude_list) non è in grado di restituire altri g-nodi, vale a dire se nella rete ci sono meno di q partecipanti al servizio.
Note:
- Nella funzione che cerca i candidati per le repliche è possibile che la ricerca venga ristretta ad un certo g-nodo; questo è a discrezione del servizio: ad esempio il Coordinator di un g-nodo non sarà mai contattato all'esterno del g-nodo stesso, quindi sarebbe inutile replicare i record di sua pertinenza su nodi esterni.
Salvataggio delle repliche
Vediamo come fa il nodo generico v a richiedere il salvataggio di max. q repliche di un record r del servizio pid all'interno del g-nodo u.
Sia l'indice j tale che il g-nodo vj+1 è il minimo g-nodo comune tra v ed u. Similmente a quanto visto prima, la richiesta che viene inviata al g-nodo u fa un percorso interno a vj+1 ed è costituita da un messaggio m’ che contiene la tupla v: v0·v1·...·vj, le coordinate lvl e pos del g-nodo che si vuole raggiungere, un identificativo id_msg generato per il messaggio. Quando il messaggio viene ricevuto da un nodo u0 appartenente ad u questo realizza una connessione TCP con il nodo v tramite percorso interno al g-nodo vj+1.
Una volta realizzata la connessione TCP tra v e u0 il dialogo consiste in:
- u0 comunica a v l'identificativo m’.id_msg;
- se v aveva rinunciato ad attendere la risposta a questo messaggio lo comunica a u0 e qui si interrompe.
- v comunica a u0:
il record r da memorizzare,
il numero q di repliche richieste,
il pid del servizio,
la tupla x: x0·x1·...·xj-1,
- u0 esegue le operazioni descritte di seguito per memorizzare fino a q repliche; poi risponde a v con il numero di repliche che è riuscito a mettere all'interno del g-nodo u. La connessione TCP viene chiusa.
Per memorizzare le repliche dentro il g-nodo u, u0 procede così:
- exclude_list = []
mentre q > 0:
Dalla tupla m.x calcola Ht (x, exclude_list). Ottiene un g-nodo z.
- Se z è lo stesso u0:
- esegue un salvataggio nel nodo stesso.
- decrementa q di 1.
- aggiunge u0 a exclude_list.
- Altrimenti:
Si applica la ricorsione di questo stesso algoritmo: u0 richiede il salvataggio di max. q repliche del record r del servizio pid all'interno del g-nodo z. La risposta ottenuta è il numero di salvataggi effettuati s.
- decrementa q di s.
- aggiunge z a exclude_list.
Popolamento della cache al bootstrap
Quando un nodo n entra nella rete (oppure quando inizia a partecipare ad un servizio) può venirgli assegnato un indirizzo prossimo a qualche chiave precedentemente salvata nel database distribuito. Deve svolgere quindi alcune operazioni per reperire e memorizzare i record di sua pertinenza.
Nell'analisi dell'algoritmo delineato di seguito si tenga conto che queste operazioni non sono strettamente necessarie al funzionamento del servizio. Se queste non vengono effettuate con precisione l'eventuale inconsistenza nel database distribuito sarà comunque temporanea. E' quindi di proposito che si è cercato un trade-off tra la rigorosità del risultato e la leggerezza dell'implementazione. Ad esempio l'inoltro dei messaggi verso i nodi viene svolto dagli hop intermedi senza garantire il successo né l'identificazione del punto esatto in cui si può essere perduto il messaggio.
Prerequisito di queste operazioni è che il nodo sia maturo, cioè abbia piena conoscenza dei nodi e g-nodi presenti nella rete che sono di sua visibilità. In caso di servizio opzionale deve anche avere piena conoscenza della mappa di nodi partecipanti al servizio.
Abbiamo visto che la funzione Ht cerca l'indirizzo che minimizza la funzione dist e che la funzione dist introduce una sorta di "direzione a destra" nella ricerca dell'indirizzo. Definiamo ora la funzione H_revt(x) = minargx’∈dom(αt)dist_rev(x,x’) dove la funzione dist_rev implementa la "direzione a sinistra" nella ricerca dell'indirizzo. Per farlo basta definire dist_rev(x,x’) = dist(x’,x).
Questo è l'algoritmo che esegue n per popolare la sua cache:
Il nodo n ha indirizzo n0·n1·...·nl-1.
Per ogni livello j da 0 a l-1:
exclude_list = [nj]
- dx_done = false
- Mentre not dx_done:
Il nodo n calcola Ht ( n, exclude_list ) circoscritto al g-nodo nj+1 ed ottiene il g-nodo gn_dx, che potrebbe essere null.
- Se gn_dx è null:
- dx_done = true
- Altrimenti:
Il nodo n contatta (di seguito è descritto come questo avviene) il nodo n_dx appartenente a gn_dx più prossimo a destra rispetto a n0·...·nj-1. Se j == 0 allora n_dx = gn_dx. Contattatolo gli chiede la sua cache per il servizio p.1
- Se n non riesce a contattare n_dx:
- Aggiunge gn_dx a exclude_list.
- Altrimenti:
- dx_done = true
- Aggiunge gn_dx a exclude_list.
- sx_done = false
- Mentre not sx_done:
Il nodo n calcola H_revt ( n, exclude_list ) circoscritto al g-nodo nj+1 ed ottiene il g-nodo gn_sx, che potrebbe essere null.
- Se gn_sx è null:
- sx_done = true
- Altrimenti:
Il nodo n contatta il nodo n_sx appartenente a gn_sx più prossimo a sinistra rispetto a n0·...·nj-1. Se j == 0 allora n_sx = gn_sx. Contattatolo gli chiede la sua cache per il servizio p.
- Se n non riesce a contattare n_sx:
- Aggiunge gn_sx a exclude_list.
- Altrimenti:
- sx_done = true
Note:
- Come il nodo n utilizzi la cache reperita dai vari singoli nodi dipende dal servizio. Di norma n memorizza tutti i record nella sua cache.
Con questo algoritmo il nodo n, dato il g-nodo gn_dx appartenente a nj+1, contatta il nodo n_dx:
Il nodo n prepara il messaggio m’ da inoltrare al gnodo gn_dx. Questo messaggio contiene:
n: la tupla n0·n1·...·nj.
lvl, pos: le coordinate del g-nodo gn_dx.
pid: l'identificativo del servizio p.
id_msg: un identificativo generato a caso per questo messaggio.
- Il nodo n invia il messaggio m’ al suo miglior gateway verso gn_dx. Questo invio viene fatto in modo asincrono con protocollo reliable (TCP).
- Il nodo n tiene a mente per un certo periodo l'id del messaggio in attesa di una risposta. Se passa un certo tempo (p. es. 2 secondi per il numero di nodi stimati nel proprio g-nodo di livello j) si considera fallito il tentativo di contattare n_dx.
Il messaggio m’ viene così inoltrato:
Il nodo v riceve un messaggio m’.
- Il nodo v confronta il proprio indirizzo con le coordinate presenti in m’. Se v.pos[m’.lvl] == m’.pos allora il messaggio è giunto al g-nodo gn_dx (vedi sotto il proseguimento dell'algoritmo).
- Altrimenti il nodo v inoltra m’ al suo miglior gateway verso il g-nodo (m’.lvl, m’.pos) in modo asincrono con protocollo TCP.
Il messaggio m’ raggiunge un nodo dentro il g-nodo gn_dx.
j = m’.lvl
n_target = m’.n0·m’n1·...·m’nj-1.
Il nodo v calcola Ht ( n_target ) circoscritto al g-nodo vj ed ottiene il g-nodo di livello k e identificativo yk. Sicuramente k < j.
- Se k == -1 allora il messaggio è giunto alla destinazione finale (vedi sotto il proseguimento dell'algoritmo).
- Il nodo v modifica i seguenti membri del messaggio m’:
- lvl diventa k.
pos diventa yk.
x diventa x0·x1·...·xk-1.
- Il nodo v inoltra m’ al suo miglior gateway verso il g-nodo (m’.lvl, m’.pos) in modo asincrono con protocollo TCP. L'algoritmo prosegue come detto prima con il prossimo nodo che riceve m’.
Il messaggio m’ raggiunge la destinazione finale:
Il nodo v prepara uno stub TCP per connettersi al nodo originante tramite percorso interno (vedi trattazione dei percorsi interni ad un g-nodo nel documento livelli e bits) attraverso la tupla m’.n.
- Una volta realizzata la connessione TCP tra n e v il dialogo consiste in:
- v comunica a n m’.id_msg;
- Se n aveva rinunciato ad attendere la risposta a questo messaggio lo comunica a v e qui si interrompe.
- Altrimenti n conferma la richiesta.
- v comunica a n tutta la sua cache. Poi la comunicazione si chiude.
Requisiti
- Mappa delle rotte note.
- Factory per aprire una connessione TCP con un percorso interno ad un proprio g-nodo verso un nodo di cui si conosce l'identificativo interno.
Set dei servizi peer-to-peer. Ogni servizio è una istanza di una classe che deriva dalla classe comune PeerService. Ogni servizio ha un identificativo numerico univoco.
- a
Durante le operazioni del modulo è possibile aggiungere un servizio di tipo opzionale.
Deliverables
Viene definita una classe base (PeerService) che può essere derivata per implementare ogni specifico servizio peer-to-peer.
Classi e interfacce
La mappa delle rotte è un oggetto di cui il modulo conosce l'interfaccia IPeersMapPaths. Tramite essa il modulo può:
- leggere il numero di livelli della topologia (metodo 'i_peers_get_levels');
- leggere la gsize di ogni livello (metodo 'i_peers_get_gsize');
- leggere il numero di nodi stimato all'interno del proprio g-nodo a ogni livello (metodo 'i_peers_get_nodes_in_my_group');
- leggere l'identificativo del proprio nodo a ogni livello (metodo 'i_peers_get_my_pos');
determinare se un certo g-nodo esiste nella rete – cioè se appartiene a domn(αt) (metodo 'i_peers_exists');
- leggere il numero di nodi stimato all'interno di un certo g-nodo (metodo 'i_peers_get_nodes_in_group').
- ottenere uno stub per inviare un messaggio al miglior gateway verso un certo g-nodo (metodo 'i_peers_gateway').
In alcuni casi sarà necessario realizzare una comunicazione TCP verso un nodo originante di un messaggio. In tali casi si vuole raggiungere il nodo attraverso un percorso interno al proprio g-nodo di un dato livello. L'oggetto fornito al modulo a questo scopo implementa l'interfaccia IPeersBackConnectionFactory, la quale permette di:
- realizzare una connessione TCP con un certo nodo (metodo 'i_peers_open_tcp_inside').
Le tuple che il modulo elabora per il calcolo della funzione Ht sono istanze di una classe nota al modulo. Anche se rappresentano degli indirizzi di nodi (all'interno della rete o all'interno di un g-nodo) non viene usata la stessa classe che rappresenta un Netsukuku address (Naddr) o una sua interfaccia.
La classe usata in questo modulo è PeerTuple. Si tratta di una classe serializzabile in quanto le tuple vanno comunicate nei messaggi da inoltrare.
La classe che implementa un servizio deriva da PeerService.
La classe base non sa come ottenere da una chiave k la tupla x, questo procedimento spetta alla classe derivata. Tuttavia molte operazioni saranno uguali nella maggior parte dei servizi. Quindi la classe base cerca di fornire i servizi comuni senza tuttavia essere di impedimento alla classe derivata se vuole usare altre modalità di calcolo. Per fare questo la classe base fornisce:
- un metodo virtuale 'perfect_tuple' che riceve a parametro la chiave (Object k) e restituisce la tupla x.
- un metodo astratto 'hash_from_key' che riceve a parametro la chiave (Object k) e un intero (top) e restituisce un intero tra 0 e top.
Quando le operazioni del modulo richiedono il calcolo di h ( x ) su un certo servizio p, il metodo 'perfect_tuple' viene richiamato sull'istanza di PeerService, quindi tale metodo deve essere pubblico.
Se tale metodo non viene ridefinito dalla classe derivata, il suo comportamento è il seguente. L'istanza conosce le dimensioni dei g-nodi ad ogni livello (gsizes) quindi calcola la dimensione dello spazio degli indirizzi validi. Poi richiama il metodo 'hash_from_key' passando oltre alla chiave k il numero massimo dell'hash (la dimensione dello spazio di indirizzi meno uno). In questo metodo la classe derivata deve occuparsi di associare alla chiave un valore di hash (di norma uniformemente distribuito) compreso tra 0 e il valore massimo (inclusi). Questo metodo è demandato alla classe derivata e quindi è definito astratto. Inoltre deve essere usato solo con la modalità sopra descritta, quindi può essere definito protetto.
Poi, nel metodo 'perfect_tuple', l'istanza usa il valore di hash per produrre una tupla sulla base della sua conoscenza di gsizes.
Se invece la classe derivata ridefinisce il metodo 'perfect_tuple' è libera di calcolare direttamente la tupla x a partire dalla chiave e dalle sue conoscenze.