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.

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.

Quando un nodo, al tempo t, vuole scrivere la coppia chiave-valore (k, v) nel database distribuito il nodo calcola:

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̄,x) si calcola così:

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 messaggio m’ viene così inoltrato:

Il messaggio m’ raggiunge un nodo dentro il gnodo che mirava a raggiungere.

Il messaggio m’ raggiunge la destinazione finale:

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_n il livello del g-nodo comune a n ed x: cioè x ∈ nj_n, x ∉ nj_n-1. Sia j_m il livello del g-nodo comune a m ed x: cioè x ∈ mj_m, x ∉ mj_m-1. Sia j il minore tra j_n e j_m: cioè x ∉ nj-1, x ∉ mj-1. Cioè l'interno del g-nodo xj-1 di livello j-1 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-1.

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 deve cercare di isolare il g-nodo malfunzionante. Se lo facesse basandosi solo sulle sue conoscenze potrebbe solo calcolare x’ = Ht ( hp ( k ), exclude_list=[xj_n-1] ). Ora il nodo m cerca di contattare x per leggere il record con chiave k, vede che il suo tentativo di contattare x fallisce e quindi prova ad isolare il g-nodo malfunzionante. Basandosi solo sulle sue conoscenze calcolerebbe x’’ = Ht ( hp ( k ), exclude_list=[xj_m-1] ). La conseguenza è che se j_m ≠ j_n allora n ed m contattano nodi diversi.

Questo significa che un meccanismo robusto deve prevedere che il nodo n che cerca di contattare il nodo x ∈ nj_n e non vi riesce deve rilevare tutti gli identificativi del g-nodo xε (dal livello j_n-1 al livello ε) in cui il messaggio si è perso. Sarà cura di n, prima di effettuare ulteriori tentativi, di memorizzare questa tupla nel formato adeguato per evitare di giungere nuovamente allo stesso g-nodo. Ad esempio il nodo n sa, a seconda del servizio, se deve memorizzare solo la tupla interna al g-nodo in cui è avvenuta la ricerca (nj_n) oppure aggiungere i suoi identificativi fino ad un certo livello (ad esempio se stava contattando il Coordinator di un certo g-nodo) oppure fino all'ultimo livello.

Modifiche agli algoritmi

Modifichiamo l'algoritmo di instradamento considerando che si deve comunicare al nodo originante del messaggio m’ quali g-nodi sono stati raggiunti correttamente.

Modifichiamo inoltre l'algoritmo di calcolo di Ht considerando che deve essere possibile escludere un set di determinati g-nodi. Questi elementi da escludere possono essere, a seconda del momento come vedremo subito, espressi sotto forma di tuple globali (da l-1 a ε) oppure di tuple interne ad un g-nodo a cui il nodo appartiene.

Sia e_list il set di g-nodi da escludere. In questo set ogni g-nodo è espresso sotto forma di tupla globale. Il nodo n istanzia questo set inizialmente vuoto quando inizia il suo tentativo di contattare l'hash-node x̄.

Per prima cosa il nodo n sceglie dal set e_list quei g-nodi che sono nella sua mappa, cioè quelli che hanno il g-nodo direttamente superiore in comune con il nodo stesso, e li mette nel set my_e_list. Il nodo n calcola Ht(x̄, exclude_list=my_e_list) come prima, aggiungendo il vincolo di esclusione di quei g-nodi. Trova un livello j e un identificativo xj ∈ nj+1. Ora il nodo n sceglie dal set e_list quei g-nodi che sono interni al g-nodo xj (il g-nodo xj sicuramente non era nel set e_list) e li aggiunge al messaggio m’ come membro m’.e_list; in questa lista ogni g-nodo è espresso sotto forma di tupla interna a xj (da j-1 a ε) dove j è il livello del g-nodo obiettivo.

Come avveniva in precedenza, n invia m’ al miglior gateway e questo lo inoltra fino a raggiungere un nodo v dentro il g-nodo obiettivo. Quando v deve calcolare Ht(m’.x̄) prima sceglie dal set m’.e_list quei g-nodi che sono nella sua mappa e li mette nel set my_e_list. Poi calcola Ht(m’.x̄, exclude_list=my_e_list) e può trovarsi in una tra 3 diverse situazioni:

  1. v è la destinazione finale di m’.

  2. v individua un g-nodo interno che diventa il nuovo obiettivo di m’, cioè trova un livello k e un identificativo xk.

  3. v trova che a causa dei vincoli nessun g-nodo al suo interno è più valido come obiettivo per m’.

Nel caso 1 il nodo v si connette via TCP ad n attraverso la tupla m’.n e ne esegue la richiesta, come descritto prima.

Nel caso 2 il nodo v sceglie dal set m’.e_list quei g-nodi che sono interni al g-nodo xk (il g-nodo xk sicuramente non era nel set m’.e_list), li esprime sotto forma di tuple interne a xk (da k-1 a ε) e mette questa lista al posto del vecchio contenuto di m’.e_list; effettua anche le altre modifiche a m’ e lo inoltra verso il suo nuovo obiettivo; subito dopo v si connette via TCP ad n attraverso la tupla m’.n e gli comunica (senza necessitare alcuna risposta) l'identificativo m’.id_msg e la tupla che identifica all'interno di m’.nj+1 il g-nodo nuovo obiettivo.

Nel caso 3 il nodo v si connette via TCP ad n attraverso la tupla m’.n e gli comunica (senza necessitare alcuna risposta) il fallimento indicando l'identificativo m’.id_msg e la tupla che identifica all'interno di m’.nj+1 il g-nodo di v, cioè la tupla che nei suoi prossimi tentativi n dovrà escludere.

Con questi accorgimenti quando il nodo n invia il messaggio m’ al g-nodo xj = Ht ( hp ( k ) ) e si mette in attesa delle risposte possono verificarsi questi casi:

  1. Il nodo n riceve (oltre ad alcuni messaggi intermedi) per tempo una risposta da parte di x. Il messaggio m gli viene consegnato.

  2. Il nodo n riceve un messaggio da parte di un g-nodo xε che gli comunica che al suo interno non ci sono obiettivi validi.

  3. Il nodo n riceve alcuni messaggi (0 o più) che gli segnalano dei g-nodi xk con k < j come nuove destinazioni di m’ e poi più niente fino allo scadere del tempo massimo. In questo caso viene scelto come valore ε il più piccolo tra i messaggi ricevuti, oppure se sono stati ricevuti 0 messaggi lo stesso valore j.

Nei casi 2 e 3 abbiamo un tentativo fallito e un valore xε da escludere nelle future ricerche. Il valore xε è espresso sotto forma di tupla interna a xj, quindi il nodo n è in grado di completare la tupla per renderla globale e poi la inserisce nel set e_list. Il nodo n effettuerà quindi altri tentativi escludendo i g-nodi inadatti come è stato descritto sopra.

L'unico errore (eccezione) definitivo ammissibile per una richiesta ad un servizio peer-to-peer sarà quindi il "nessun nodo nella rete partecipa al servizio" in caso di servizi opzionali. Nei servizi obbligatori invece come minimo il nodo n risponde a se stesso.

Repliche

Quando un nodo v riceve la richiesta di memorizzare (o aggiornare, o rinfrescare) un record con chiave k e valore val nella sua porzione del database distribuito del servizio p 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ù.

Grazie all'introduzione del meccanismo di fault tolerance descritto sopra, scegliere e contattare tali nodi diventa un esercizio banale. Di seguito l'algoritmo:

Note:

  1. Con la dicitura "contatta x = Ht ( x̄, exclude_list=lista_esclusioni )" si intende la sequenza di operazioni descritte negli algoritmi modificati con il meccanismo di fault tolerance. Quindi in realtà il nodo v quando esegue la funzione Ht mette nella exclude_list solo una parte degli elementi presenti in lista_esclusioni, cioè i g-nodi visibili nella sua mappa; poi a seconda di quale g-nodo xj è stato eletto il nodo v prende un sottoinsieme degli altri elementi presenti in lista_esclusioni e li inserisce nel messaggio m’ con cui cerca di contattare x.

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.

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̄). Inoltre va aggiunto al messaggio m’ un campo booleano reverse che impostato a True indica al nodo v di proseguire la ricerca usando H_rev.

Questo è l'algoritmo che esegue n per popolare la sua cache:

Note:

  1. Aggiungere questo requisito all'implementazione della funzione Ht è banale: basta escludere dalla ricerca iniziale fatta dal nodo n tutti i g-nodi esterni al g-nodo nj+1.

  2. 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.

Requisiti

Durante le operazioni del modulo è possibile aggiungere un servizio di tipo opzionale.

Deliverables

Classi e interfacce

La mappa delle rotte è un oggetto di cui il modulo conosce l'interfaccia IPeersMapPaths. Tramite essa il modulo può:

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:

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:

Quando le operazioni del modulo richiedono il calcolo di hp ( k ) 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.