Differences between revisions 1 and 11 (spanning 10 versions)
⇤ ← Revision 1 as of 2015-01-09 12:17:30 →
Size: 24700
Editor: lukisi
Comment:
← Revision 11 as of 2015-09-05 09:37:51 → ⇥
Size: 22065
Editor: lukisi
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
Line 2: Line 3:
Instrada i messaggi (ricevuti da altri nodi o generati dal nodo stesso) che sono destinati ad un dato hash-node.

Mantiene le informazioni necessarie.		 <<TableOfContents(4)>>
Line 7: Line 6:
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. Il funzionamento di servizi distribuiti in un modello non centralizzato di rete, che possiamo chiamare servizi peer-to-peer, si basa sul fatto di poter individuare un nodo fra quelli presenti nella rete in un dato momento al quale rivolgere delle richieste. I nodi presenti nella rete cambiano da un momento all'altro, così come cambia la loro identificazione. Si potrebbe anche aggiungere che non tutti i nodi sono disposti a partecipare attivamente al servizio rispondendo alle richieste altrui e anche questo può cambiare nel tempo.

Per ogni servizio occorre definire una funzione che associ ad ogni chiave ''k'' (nel dominio di chiavi definito dal servizio) un nodo esistente nella rete. A tale nodo andranno indirizzate le richieste concernenti la chiave k. Siccome tale nodo dovrà rispondere alle richieste, se il servizio prevede la possibilità che un nodo decida di non partecipare attivamente (chiamiamo questo tipo di servizio un ''servizio opzionale'') va aggiunto il requisito che la funzione associ ad ogni chiave ''k'' un nodo ''partecipante'' al servizio.
Line 13: Line 14:
Sia ''α~-,,t,,-~'' : S → V~-,,t,,-~ 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. Sia ''α~-,,t,,-~'' : S → V~-,,t,,-~ 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.
Line 20: Line 21:
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. Sia ''p'' un servizio distribuito che vuole implementare un database, sia ''K'' lo spazio delle chiavi definito da p per questo database. Il servizio p  definisce una funzione di hash che mappa lo spazio delle chiavi sullo  spazio degli indirizzi.
Line 30: Line 31:
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. Analogamente  il nodo che vuole reperire il dato associato alla chiave k, calcola  hash_node(k), contatta il nodo e chiede di leggere il dato associato a k.
Line 32: Line 33:
Questo procedimento realizza un database distribuito, perché ogni nodo mantiene solo una porzione delle associazioni chiave-valore. Questo  procedimento realizza un database distribuito, perché ogni nodo  mantiene solo una porzione delle associazioni chiave-valore.
Line 34: Line 35:
Fondamentale è la funzione H~-,,t,,-~. Definiamo la funzione H~-,,t,,-~(x) come l'indirizzo x’ associato ad un nodo esistente (x’ ∈ dom(α~-,,t,,-~)) che minimizza la distanza x - x’, in modo più rigoroso minarg,,x’∈dom(α,,~-,,t,,-~,,),,dist(x,x’). La funzione ''dist'' rappresenta in modo intuitivo la distanza tra due indirizzi, ma è definita in modo che la funzione H~-,,t,,-~ "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ì: Fondamentale è la funzione H~-,,t,,-~. Questa funzione è indipendente dal servizio p, può quindi essere definita e implementata una volta sola. Essa è dipendente dalla conoscenza del dominio di α~-,,t,,-~, cioè di quali indirizzi in S sono detenuti da almeno un nodo. Inoltre, in caso di servizi opzionali, è dipendente anche dalla conoscenza di quali indirizzi sono detenuti da nodi che partecipano al servizio.
Line 36: Line 37:
 * x è formato da x~-,,0,,-~·x~-,,1,,-~·...·x~-,,l-1,,-~.
 * y è formato da y~-,,0,,-~·y~-,,1,,-~·...·y~-,,l-1,,-~.
 * distanza = 0;
 * Per j da l-1 a 0:
  * se x~-,,j,,-~ == y~-,,j,,-~:
   * distanza += 0;
  * altrimenti se y~-,,j,,-~ > x~-,,j,,-~:
   * distanza += y~-,,j,,-~ - x~-,,j,,-~;
  * altrimenti:
   * distanza += y~-,,j,,-~ - x~-,,j,,-~ + gsize[j];
  * se j>0:
   * distanza *= gsize[j-1];		 La conoscenza degli indirizzi detenuti dai nodi presenti nella rete è realizzata attraverso il protocollo di routing QSPN. Occorre invece definire un ulteriore meccanismo per giungere alla conoscenza di quali indirizzi sono detenuti da nodi che partecipano ad ognuno dei servizi opzionali.
Line 50: Line 40:
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 H~-,,t,,-~ in quanto non conosce per intero dom(α~-,,t,,-~). L'implementazione avviene in modo distribuito. In una struttura gerarchica come Netsukuku ([[Netsukuku/ita/docs/ModuloQSPN/AnalisiFunzionale#StrutturaGerarchica|dettagli]]) un nodo non ha la conoscenza di tutti i nodi esistenti nella rete, quindi non può da solo computare la funzione H~-,,t,,-~ in quanto non conosce per intero dom(α~-,,t,,-~).
Line 52: Line 42:
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 ''h''~-,,p,,-~ definita da ''p'' per calcolare dalla chiave ''k'' l'indirizzo ''x''. A questo punto dovrebbe calcolare ''x’''=H~-,,t,,-~(x). Procede così: Infatti ogni nodo ''n'' con indirizzo n~-,,0,,-~·n~-,,1,,-~·...·n~-,,l-1,,-~ ha solo conoscenza di:
Line 54: Line 44:
 * Il nodo n ha indirizzo n~-,,0,,-~·n~-,,1,,-~·...·n~-,,l-1,,-~. Ha inoltre conoscenza di:
  * tutti i nodi appartenenti a n~-,,1,,-~,
  * tutti i g-nodi di livello 1 appartenenti a n~-,,2,,-~,
  * ...
  * tutti i g-nodi di livello l-2 appartenenti a n~-,,l-1,,-~,
  * tutti i g-nodi di livello l-1.
 * Questa conoscenza la possiamo chiamare dom~-,,n,,-~(α~-,,t,,-~), cioè il dominio della funzione α~-,,t,,-~ secondo le conoscenze di n.
 * x è formato da x~-,,0,,-~·x~-,,1,,-~·...·x~-,,l-1,,-~.
 * Il nodo n calcola H~-,,t,,-~(x) secondo le sue conoscenze, cioè trova un livello ''j'' e un identificativo ''y''~-,,j,,-~ tali che:
  * y~-,,j,,-~ ∈ n~-,,j+1,,-~, oppure j == l-1.
  * Il gnodo y~-,,j,,-~ è quello, fra le conoscenze di n, che minimizza la funzione dist(x, y~-,,j,,-~).
  * y~-,,j,,-~ ≠ n~-,,j,,-~.
  * se j == 0 allora n ha trovato con le sue sole conoscenze y~-,,0,,-~ = H~-,,t,,-~(x).
  * come caso estremo n potrebbe trovare che esso stesso è il definitivo H~-,,t,,-~(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 y~-,,j,,-~. 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 n~-,,j+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 y~-,,j,,-~. Questo messaggio contiene:
  * ''n'': la tupla n~-,,0,,-~·n~-,,1,,-~·...·n~-,,j,,-~. ~-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 x~-,,0,,-~·x~-,,1,,-~·...·x~-,,j-1,,-~.
  * ''lvl, pos'': le coordinate del g-nodo che miriamo a raggiungere, cioè j e y~-,,j,,-~.
  * ''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 y~-,,j,,-~. 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.		  * tutti i nodi appartenenti a n~-,,1,,-~,
 * tutti i g-nodi di livello 1 appartenenti a n~-,,2,,-~,
 * ...
 * tutti i g-nodi di livello l-2 appartenenti a n~-,,l-1,,-~,
 * tutti i g-nodi di livello l-1.
Line 79: Line 50:
Il messaggio m’ viene così inoltrato: Questa conoscenza la possiamo chiamare dom~-,,n,,-~(α~-,,t,,-~), cioè il dominio della funzione α~-,,t,,-~ secondo le conoscenze di n.
Line 81: Line 52:
 * 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.		 L'implementazione della funzione H~-,,t,,-~ deve dunque avvenire in modo distribuito.
Line 85: Line 54:
Il messaggio m’ raggiunge un nodo dentro il gnodo che mirava a raggiungere. == Ruolo del modulo PeerServices ==
Il modulo fa uso delle [[Netsukuku/ita/docs/Librerie/TaskletSystem|tasklet]], un sistema di multithreading cooperativo.
Line 87: Line 57:
 * Se m’.lvl == 0 allora il messaggio è giunto alla destinazione finale (vedi sotto il proseguimento dell'algoritmo).
 * Il nodo v calcola H~-,,t,,-~(m’.x) secondo le sue conoscenze relative al suo g-nodo di livello m’.lvl, cioè trova un livello ''k'' e un identificativo ''y''~-,,k,,-~. Sicuramente k < m’.lvl.
 * Se il nodo v trova che esso stesso è H~-,,t,,-~(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 ''y''~-,,k,,-~.
  * x diventa x~-,,0,,-~·x~-,,1,,-~·...·x~-,,k-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 modulo fa uso del framework [[Netsukuku/ita/docs/Librerie/ZCD|ZCD]], precisamente appoggiandosi ad una libreria intermedia prodotta con questo framework per formalizzare i metodi remoti usati nel demone ''ntkd''.
Line 96: Line 59:
Il messaggio m’ raggiunge la destinazione finale: Nel modulo !PeerServices il nodo registra i servizi peer-to-peer ai quali intende partecipare, specificando quali di questi sono opzionali.
Line 98: Line 61:
 * 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 [[Netsukuku/ita/docs/ModuloQSPN/LivelliBits|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 H~-,,t,,-~ ( h~-,,p,,-~ ( 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.		 Ogni servizio peer-to-peer ha un intero positivo come suo identificativo, ''p_id''.
Line 108: Line 63:
=== 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'' = H~-,,t,,-~ ( h~-,,p,,-~ ( k ) ) e di contattare x. Sia ''j'' il livello massimo tale che x ∉ n~-,,j,,-~, x ∉ m~-,,j,,-~. Cioè l'interno del g-nodo x~-,,j,,-~ 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.		 Il modulo !PeerServices si occupa di divulgare in tutta la rete (tramite trasmissione di vicino in vicino) la conoscenza della partecipazione del nodo ad ogni servizio opzionale. Questa operazione non è necessaria per i servizi non opzionali, proprio perché ogni nodo esistente nella rete partecipa attivamente ad essi.
Line 111: Line 65:
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. Allo stesso tempo il modulo !PeerServices, nei singoli nodi in cui riceve questa informazione e la propaga, si occupa di mantenere la conoscenza, sempre in forma gerarchica, di tutti i partecipanti a tutti i servizi opzionali esistenti nella rete; questo pur senza necessitare di conoscere a priori quali servizi opzionali esistano. Inoltre, quando un nodo entra in un g-nogo ''g'' (per migrazione o per ingresso iniziale nella rete) il modulo richiede subito ai vicini che erano in ''g'' prima di lui le mappe di tutti i servizi opzionali esistenti nella rete.
Line 113: Line 67:
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''’ = H~-,,t,,-~ ( h~-,,p,,-~ ( k ), exclude_list=[x] ) TODO In ogni momento un nodo può fare al suo modulo !PeerServices una richiesta relativa ad un servizio con un dato ''p_id''. Se il servizio è non-opzionale per definizione esso è fra quelli registrati, quindi il modulo lo conosce, sa che è non-opzionale e non ha bisogno di mappe di partecipazione per ricercare un suo hash_node. Se il servizio pur essendo opzionale è stato registrato, anche in questo caso il modulo lo conosce e sa che deve consultare le mappe di partecipazione (in questo caso almeno il nodo stesso è nelle mappe). Se il servizio opzionale non è stato registrato, cioè il nodo non vi partecipa attivamente possono esservi due casi:
Line 115: Line 69:
== 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ù.		  1. Il modulo è venuto a conoscenza di alcuni nodi nella rete che partecipano. Allora ha le mappe per avviare la ricerca dell'hash_node.
 1. Il modulo non ha mai ricevuto informazioni di partecipazioni al servizio con questo identificativo. Allora deduce che nessun nodo nella rete è partecipante al servizio.
Line 118: Line 72:
=== Scelta dei g-nodi di replica ===
Ovviamente il nodo v verifica di essere il risultato di H~-,,t,,-~ ( h ( k ) ).		 ----
Il modulo !PeerServices si occupa, su richiesta del nodo, di avviare una comunicazione verso un hash_node per la chiave ''k'' di un servizio ''p''; cioè esso avvia il calcolo distribuito di H~-,,t,,-~. Per fare questo il modulo non ha bisogno di conoscere l'implementazione della funzione h~-,,p,,-~ ma soltato il risultato di h~-,,p,,-~ ( k ); d'altra parte questa richiesta arriva dal nodo stesso quindi il nodo conosce l'implementazione della funzione h~-,,p,,-~. Inoltre per fare questa operazione non è necessario che il nodo partecipi al servizio p.
Line 121: Line 75:
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 H~-,,t,,-~ ( 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. Lo stesso modulo, nei nodi intermedi verso la destinazione, si occupa di instradare il messaggio e di proseguire il calcolo distribuito di H~-,,t,,-~. Per fare questo il modulo non ha bisogno di conoscere la logica interna del servizio ''p'', ma deve solo sapere l'identificativo del servizio ''p_id'' e il valore di h~-,,p,,-~ ( k ); questi dati sono contenuti nel messaggio da instradare. Quindi per fare questa operazione il nodo non ha bisogno né di partecipare al servizio p e nemmeno di conoscere nulla sull'implementazione del servizio p.
Line 123: Line 77:
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. Lo stesso modulo, nel nodo destinazione del messaggio, si occupa di ricevere la richiesta del nodo originante e di servirla. Perché il modulo possa servirla, nel modulo deve essere stato registrato il servizio peer-to-peer. Difatti il nodo deve essere partecipante al servizio ''p''. Inoltre il modulo fornisce all'implementazione del servizio p la possibilità di replicare qualsiasi dato che esso memorizza su un numero ''q'' di nodi partecipanti al servizio che sarebbero stati i più prossimi destinatari della richiesta in caso di sua assenza.
Line 125: Line 79:
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 H~-,,t,,-~ ( h ( k ), exclude_list=[v, u] ). Le operazioni si considerano concluse quando q diventa 0 oppure quando H~-,,t,,-~ ( 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:

 1. 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 v~-,,j+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 v~-,,j+1,,-~ ed è costituita da un messaggio ''m''’ che contiene la tupla ''v'': v~-,,0,,-~·v~-,,1,,-~·...·v~-,,j,,-~, 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 v~-,,j+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'': x~-,,0,,-~·x~-,,1,,-~·...·x~-,,j-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 H~-,,t,,-~ (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 H~-,,t,,-~ 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_rev''~-,,t,,-~(x) = minarg,,x’∈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 n~-,,0,,-~·n~-,,1,,-~·...·n~-,,l-1,,-~.
 * Per ogni livello ''j'' da 0 a l-1:
  * exclude_list = [n~-,,j,,-~]
  * dx_done = false
  * Mentre not dx_done:
   * Il nodo n calcola H~-,,t,,-~ ( n, exclude_list ) circoscritto al g-nodo n~-,,j+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 n~-,,0,,-~·...·n~-,,j-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_rev~-,,t,,-~ ( n, exclude_list ) circoscritto al g-nodo n~-,,j+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 n~-,,0,,-~·...·n~-,,j-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:

 1. 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 n~-,,j+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 n~-,,0,,-~·n~-,,1,,-~·...·n~-,,j,,-~.
  * ''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’.n~-,,0,,-~·m’n~-,,1,,-~·...·m’n~-,,j-1,,-~.
 * Il nodo v calcola H~-,,t,,-~ ( n_target ) circoscritto al g-nodo v~-,,j,,-~ ed ottiene il g-nodo di livello ''k'' e identificativo ''y''~-,,k,,-~. 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 ''y''~-,,k,,-~.
  * x diventa x~-,,0,,-~·x~-,,1,,-~·...·x~-,,k-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 [[Netsukuku/ita/docs/ModuloQSPN/LivelliBits|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.		 ----
Il modulo !PeerServices si occupa per un nodo appena entrato nella rete di reperire per tutti i servizi a cui il nodo intende partecipare tutti i record che sono di sua pertinenza nel mantenimento del database distribuito, come destinatario principale o come replica.
Line 242: Line 84:
 * 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.		  * Livello del g-nodo che questo nodo ha formato entrando nella rete.
 * 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.
 * Factory per ottenere uno stub per inviare un messaggio in broadcast (con callback per gli archi in cui il messaggio fallisce) o uno stub per inviare un messaggio su un arco in modo reliable.
Line 249: Line 89:
 * Viene definita una classe base (!PeerService) che può essere derivata per implementare ogni specifico servizio peer-to-peer.  * Viene definita una classe base astratta (!PeerService) che deve essere derivata per implementare ogni specifico servizio peer-to-peer, sia quelli opzionali che quelli non opzionali.
 * Viene definita una classe base astratta (!PeerClient) che deve essere derivata per implementare una classe da usare come client per un servizio peer-to-peer.
 * Emette un segnale quando ha completato (con successo o meno) la fase di reperimento delle mappe di partecipazione ai servizi opzionali.
 * Fornisce un metodo (''register'') per registrare le istanze di classi che rappresentano un servizio a cui il nodo partecipa.
 * Fornisce dei metodi (''begin_retrieve_cache'' e ''next_retrieve_cache'') per i vari servizi registrati perché possano all'avvio recuperare i record di pertinenza del nodo.
 . Per i servizi opzionali, questi vanno chiamati solo dopo che è stato completato il reperimento delle mappe di partecipazione.
 * Fornisce dei metodi (''begin_replica'' e ''next_replica'') per i vari servizi registrati perché possano replicare i record salvati su un numero di nodi replica.
 . Questi vanno chiamati dalle classi che implementano un servizio, appunto quando hanno salvato (o modificato) un record.
 * Fornisce un metodo (''contact_peer'') per effettuare una richiesta ad un servizio peer-to-peer. Sono passate al metodo queste informazioni:
  * l'identificativo del servizio,
  * la tupla obiettivo, cioè il risultato di h~-,,p,,-~ ( k ),
  * l'istanza di IPeersRequest che rappresenta la richiesta da effettuare,
  * il tempo limite per l'esecuzione della richiesta una volta consegnata all'hash_node.
 . Queste informazioni passate al metodo contact_peer lo abilitano ad effettuare la richiesta senza dover conoscere altro sul servizio: infatti per fare una richiesta ad un servizio il nodo non ha bisogno di partecipare attivamente al servizio, quindi il nodo potrebbe non aver passato il servizio in questione al metodo register; basta che il nodo sappia come interfacciarsi con il servizio.
 . Il metodo restituisce una istanza di IPeersResponse che può rappresentare il risultato della richiesta o una eccezione prevista dal servizio stesso.
 . Oppure rilancia una eccezione (!PeersNoParticipantsInNetworkError) se al momento nessun nodo nella rete partecipa attivamente al servizio.
Line 252: Line 107:
La classe HCoord è una classe [[Netsukuku/ita/docs/Librerie/Common|comune]] nota a questo modulo. E' una classe serializzabile, cioè le cui istanze sono adatte al passaggio di dati a metodi remoti (vedi framework [[Netsukuku/ita/docs/Librerie/ZCD|ZCD]]). Una sua istanza contiene le coordinate gerarchiche di un g-nodo nella mappa del nodo: livello e identificativo nel livello.

----
Line 254: Line 112:
 * 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 dom~-,,n,,-~(α~-,,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').		  * Leggere il numero di livelli della topologia (metodo 'i_peers_get_levels');
 * Leggere la gsize di ogni livello (metodo 'i_peers_get_gsize');
 * Leggere l'identificativo del proprio nodo a ogni livello (metodo 'i_peers_get_my_pos');
 * Leggere il numero di nodi stimato all'interno del proprio g-nodo a ogni livello (metodo 'i_peers_get_nodes_in_my_group');
 * Determinare se un certo g-nodo esiste nella rete – cioè se appartiene a dom~-,,n,,-~(α~-,,t,,-~) (metodo 'i_peers_exists');
 * Ottenere uno stub per inviare un messaggio al miglior gateway verso un certo g-nodo, segnalando opzionalmente se si vuole escludere un certo gateway perché era il passo precedente nell'instradamento del messaggio e / o se si vuole escludere e rimuovere un certo gateway che nel tentativo precedente ha fallito la comunicazione (metodo 'i_peers_gateway').
 * Ottenere uno stub per inviare un messaggio ad un mio vicino che appartiene al mio stesso g-nodo di un dato livello (metodo 'i_peers_fellow').
 . All'avvio del nodo, se esso non ha formato una nuova rete ma piuttosto è entrato in un g-nodo, allora usa subito questo metodo per individuare un vicino che fa parte di quello stesso g-nodo in cui è entrato. Userà questo stub per richiedere a tale vicino la mappa corrente dei g-nodi che partecipano a servizi opzionali.
Line 263: Line 122:
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: 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.
Line 265: Line 124:
 * realizzare una connessione TCP con un certo nodo (metodo 'i_peers_open_tcp_inside'). In tutti i casi in cui questo è necessario il dialogo tra i due nodi è molto semplice e prevede sempre uno scambio di richiesta e risposta ad iniziativa del nodo che inizia la connessione. Sarà quindi sufficiente che si ottenga uno stub che realizza la chiamata di un metodo remoto tramite questa connessione TCP.

L'oggetto fornito al modulo a questo scopo implementa l'interfaccia IPeersBackStubFactory, la quale permette di:

 * ottenere uno stub per inviare un messaggio ad un dato nodo mediante connessione TCP interna (metodo 'i_peers_get_tcp_inside').
Line 268: Line 131:
Le tuple che il modulo elabora per il calcolo della funzione H~-,,t,,-~ 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. In alcuni casi sarà necessario inviare una comunicazione ai vicini che appartengono alla mia stessa rete. L'oggetto fornito al modulo a questo scopo implementa l'interfaccia IPeersNeighborsFactory, la quale permette di:
Line 270: Line 133:
La classe usata in questo modulo è !PeerTuple. Si tratta di una classe serializzabile in quanto le tuple vanno comunicate nei messaggi da inoltrare.  * ottenere uno stub per inviare un messaggio a tutti i vicini appartenenti alla nostra rete (metodo 'i_peers_get_broadcast') specificando una istanza di IPeersMissingArcHandler per gestire gli archi su cui non si è ricevuto un acknowledgement.
 * data una istanza di IPeersArc ottenere uno stub per inviare un messaggio reliable su quell'arco (metodo 'i_peers_get_tcp').

Quando il modulo usa il metodo i_peers_get_broadcast sull'oggetto IPeersNeighborsFactory ''"nf"'' fornito dal suo utilizzatore, gli passa un oggetto IPeersMissingArcHandler ''"ah"''. Lo stub che l'utilizzatore fornisce ora al modulo tiene conto di questo "ah". Quando lo stub trasmette un messaggio si aspetta di ricevere, entro un tempo limite, un acknowledgement tramite ognuno degli archi noti al nodo (non sono noti al modulo, ma al suo utilizzatore): se per qualcuno degli archi questo non avviene, allora lo stub si occuperà di richiamare su "ah" il metodo 'i_peers_missing' che riceve un'istanza di IPeersArc. Questa istanza è di un oggetto del tutto oscuro al modulo, che lo può solo passare al metodo i_peers_get_tcp dell'oggetto "nf".
Line 273: Line 139:
La classe che implementa un servizio deriva da !PeerService. L'interfaccia IPeersRequest non specifica nulla. Va implementata da un oggetto serializzabile. Tale oggetto deve contenere le informazioni che possano identificare una chiamata ad un metodo remoto in un certo servizio.
Line 275: Line 141:
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: Il "client" che prepara questo oggetto è specifico di un certo servizio ''p''. Esso può assumere che il "server" che lo riceverà è il server specifico dello stesso servizio ''p''.
Line 277: Line 143:
 * 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.		 Segue un esempio, per nulla vincolante, di cosa questo oggetto potrebbe contenere.
 * Il nome del metodo. Si tratta di una stringa.
 * Gli argomenti del metodo. Si tratta di un array di stringhe che rappresentano in formato JSON gli argomenti del metodo.
Line 280: Line 147:
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. ----
L'interfaccia IPeersResponse non specifica nulla. Va implementata da un oggetto serializzabile. Tale oggetto deve contenere le informazioni che possano rappresentare una risposta fornita da un metodo remoto in un certo servizio.
Line 282: Line 150:
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. Il "server" che prepara questo oggetto è specifico di un certo servizio ''p'' ed è stato invocato su un particolare metodo ''m'' esposto da questo servizio. Esso può assumere che il "client" che lo riceverà è il client specifico dello stesso servizio ''p'' e sa che si tratta di una risposta a quel particolare metodo ''m''.
Line 284: Line 152:
Poi, nel metodo 'perfect_tuple', l'istanza usa il valore di hash per produrre una tupla sulla base della sua conoscenza di gsizes. Segue un esempio, per nulla vincolante, di cosa questo oggetto potrebbe contenere.
 * L'eccezione lanciata. Si tratta di 3 stringhe nullable: error_domain, error_code, error_message.
 * Il valore di ritorno. Si tratta di una stringa. Se le stringhe error_* non sono valorizzate, allora questa stringa rappresenta in formato JSON il risultato della chiamata del metodo.
Line 286: Line 156:
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. ----
Tutte le classi che implementano un servizio derivano da !PeerService. Questa è una classe astratta definita dal modulo.

La classe base ha un membro ''p_id'' che identifica un servizio in tutta la rete. Esso è valorizzato nel costruttore ed è in seguito di sola lettura. L'istanza del servizio è passata come istanza di !PeerService al modulo (!PeersManager) nella chiamata iniziale al metodo di registrazione e questo la memorizza associandola al suo identificativo.

La classe base ha un membro booleano ''p_is_optional'' che dice se il servizio è da considerarsi opzionale. Esso è valorizzato nel costruttore ed è in seguito di sola lettura.

La classe base ha un metodo virtuale ''is_ready()'' che dice se il nodo è pronto a servire. L'implementazione della classe base risponde sempre True. La classe del servizio che la deriva può modificare l'implementazione. In questo caso il nodo può decidere, secondo la logica propria del servizio specifico, di non rispondere in certi momenti alle richieste. Questo nonostante che il nodo sia partecipante a questo servizio, sia esso opzionale o non. Infatti se non fosse partecipante non esisterebbe l'istanza registrata nel modulo !PeersManager.

La classe base ha un metodo astratto ''exec'' che viene richiamato sull'hash_node che deve servire una richiesta. Esso riceve una istanza di IPeersRequest e restituisce una istanza di IPeersResponse.

----
La classe !PeerClient può essere derivata per implementare il client di un servizio, sia esso opzionale o non opzionale.

La classe derivata, per ogni tipo di richiesta che è prevista dal servizio, ha il compito di produrre l'oggetto IPeersRequest che rappresenta la richiesta, di specificare quale sia il tempo massimo di attesa per l'esecuzione, di interpretare l'istanza di IPeersResponse ricevuta come risposta.

La classe base ha la conoscenza della topologia della rete, cioè il numero di livelli e per ognuno la gsize. Oltre a ciò non necessita di conoscere le posizioni del nodo corrente. Ha inoltre conoscenza dell'identificativo del servizio.

La classe base ha un riferimeno all'istanza di !PeersManager che usa per contattare l'hash_node (metodo ''contact_peer'').

Nella classe derivata va definito il calcolo di h~-,,p,,-~. La funzione h~-,,p,,-~ deve associare ad una chiave ''k'' un indirizzo in S, cioè una tupla x̄ = x̄~-,,0,,-~·x̄~-,,1,,-~·...·x̄~-,,l-1,,-~ le cui componenti siano compatibili con la topologia della rete. 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~-,,p,,-~ ( 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 x̄ 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. In questo caso, inoltre, può decidere di restituire una tupla con un numero di elementi inferiore al numero di livelli della rete. In questo caso la tupla x̄ = x̄~-,,0,,-~·x̄~-,,1,,-~·...·x̄~-,,j,,-~ quando viene passata alla funzione H~-,,t,,-~ circoscrive la sua ricerca dell'hash_node al g-nodo n~-,,j+1,,-~ del nodo ''n'' che fa la richiesta.

Modulo PeerServices - Analisi Funzionale

Contents

  1. Modulo PeerServices - Analisi Funzionale
    1. Idea generale
      1. DHT: Distributed Hash Table
      2. HDHT: Hierarchical DHT
    2. Ruolo del modulo PeerServices
    3. Requisiti
    4. Deliverables
    5. Classi e interfacce

Idea generale

Il funzionamento di servizi distribuiti in un modello non centralizzato di rete, che possiamo chiamare servizi peer-to-peer, si basa sul fatto di poter individuare un nodo fra quelli presenti nella rete in un dato momento al quale rivolgere delle richieste. I nodi presenti nella rete cambiano da un momento all'altro, così come cambia la loro identificazione. Si potrebbe anche aggiungere che non tutti i nodi sono disposti a partecipare attivamente al servizio rispondendo alle richieste altrui e anche questo può cambiare nel tempo.

Per ogni servizio occorre definire una funzione che associ ad ogni chiave k (nel dominio di chiavi definito dal servizio) un nodo esistente nella rete. A tale nodo andranno indirizzate le richieste concernenti la chiave k. Siccome tale nodo dovrà rispondere alle richieste, se il servizio prevede la possibilità che un nodo decida di non partecipare attivamente (chiamiamo questo tipo di servizio un servizio opzionale) va aggiunto il requisito che la funzione associ ad ogni chiave k un nodo 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 distribuito che vuole implementare un database, sia K lo spazio delle chiavi definito da p per questo database. 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), contatta il nodo 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. Questa funzione è indipendente dal servizio p, può quindi essere definita e implementata una volta sola. Essa è dipendente dalla conoscenza del dominio di αt, cioè di quali indirizzi in S sono detenuti da almeno un nodo. Inoltre, in caso di servizi opzionali, è dipendente anche dalla conoscenza di quali indirizzi sono detenuti da nodi che partecipano al servizio.

La conoscenza degli indirizzi detenuti dai nodi presenti nella rete è realizzata attraverso il protocollo di routing QSPN. Occorre invece definire un ulteriore meccanismo per giungere alla conoscenza di quali indirizzi sono detenuti da nodi che partecipano ad ognuno dei servizi opzionali.

HDHT: Hierarchical DHT

In una struttura gerarchica come Netsukuku (dettagli) 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).

Infatti ogni nodo n con indirizzo n0·n1·...·nl-1 ha solo 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.

L'implementazione della funzione Ht deve dunque avvenire in modo distribuito.

Ruolo del modulo PeerServices

Il modulo fa uso delle tasklet, un sistema di multithreading cooperativo.

Il modulo fa uso del framework ZCD, precisamente appoggiandosi ad una libreria intermedia prodotta con questo framework per formalizzare i metodi remoti usati nel demone ntkd.

Nel modulo PeerServices il nodo registra i servizi peer-to-peer ai quali intende partecipare, specificando quali di questi sono opzionali.

Ogni servizio peer-to-peer ha un intero positivo come suo identificativo, p_id.

Il modulo PeerServices si occupa di divulgare in tutta la rete (tramite trasmissione di vicino in vicino) la conoscenza della partecipazione del nodo ad ogni servizio opzionale. Questa operazione non è necessaria per i servizi non opzionali, proprio perché ogni nodo esistente nella rete partecipa attivamente ad essi.

Allo stesso tempo il modulo PeerServices, nei singoli nodi in cui riceve questa informazione e la propaga, si occupa di mantenere la conoscenza, sempre in forma gerarchica, di tutti i partecipanti a tutti i servizi opzionali esistenti nella rete; questo pur senza necessitare di conoscere a priori quali servizi opzionali esistano. Inoltre, quando un nodo entra in un g-nogo g (per migrazione o per ingresso iniziale nella rete) il modulo richiede subito ai vicini che erano in g prima di lui le mappe di tutti i servizi opzionali esistenti nella rete.

In ogni momento un nodo può fare al suo modulo PeerServices una richiesta relativa ad un servizio con un dato p_id. Se il servizio è non-opzionale per definizione esso è fra quelli registrati, quindi il modulo lo conosce, sa che è non-opzionale e non ha bisogno di mappe di partecipazione per ricercare un suo hash_node. Se il servizio pur essendo opzionale è stato registrato, anche in questo caso il modulo lo conosce e sa che deve consultare le mappe di partecipazione (in questo caso almeno il nodo stesso è nelle mappe). Se il servizio opzionale non è stato registrato, cioè il nodo non vi partecipa attivamente possono esservi due casi:

  1. Il modulo è venuto a conoscenza di alcuni nodi nella rete che partecipano. Allora ha le mappe per avviare la ricerca dell'hash_node.
  2. Il modulo non ha mai ricevuto informazioni di partecipazioni al servizio con questo identificativo. Allora deduce che nessun nodo nella rete è partecipante al servizio.

Il modulo PeerServices si occupa, su richiesta del nodo, di avviare una comunicazione verso un hash_node per la chiave k di un servizio p; cioè esso avvia il calcolo distribuito di Ht. Per fare questo il modulo non ha bisogno di conoscere l'implementazione della funzione hp ma soltato il risultato di hp ( k ); d'altra parte questa richiesta arriva dal nodo stesso quindi il nodo conosce l'implementazione della funzione hp. Inoltre per fare questa operazione non è necessario che il nodo partecipi al servizio p.

Lo stesso modulo, nei nodi intermedi verso la destinazione, si occupa di instradare il messaggio e di proseguire il calcolo distribuito di Ht. Per fare questo il modulo non ha bisogno di conoscere la logica interna del servizio p, ma deve solo sapere l'identificativo del servizio p_id e il valore di hp ( k ); questi dati sono contenuti nel messaggio da instradare. Quindi per fare questa operazione il nodo non ha bisogno né di partecipare al servizio p e nemmeno di conoscere nulla sull'implementazione del servizio p.

Lo stesso modulo, nel nodo destinazione del messaggio, si occupa di ricevere la richiesta del nodo originante e di servirla. Perché il modulo possa servirla, nel modulo deve essere stato registrato il servizio peer-to-peer. Difatti il nodo deve essere partecipante al servizio p. Inoltre il modulo fornisce all'implementazione del servizio p la possibilità di replicare qualsiasi dato che esso memorizza su un numero q di nodi partecipanti al servizio che sarebbero stati i più prossimi destinatari della richiesta in caso di sua assenza.

Il modulo PeerServices si occupa per un nodo appena entrato nella rete di reperire per tutti i servizi a cui il nodo intende partecipare tutti i record che sono di sua pertinenza nel mantenimento del database distribuito, come destinatario principale o come replica.

Requisiti

  • Mappa delle rotte note.
  • Livello del g-nodo che questo nodo ha formato entrando nella rete.
  • 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.
  • Factory per ottenere uno stub per inviare un messaggio in broadcast (con callback per gli archi in cui il messaggio fallisce) o uno stub per inviare un messaggio su un arco in modo reliable.

Deliverables

  • Viene definita una classe base astratta (PeerService) che deve essere derivata per implementare ogni specifico servizio peer-to-peer, sia quelli opzionali che quelli non opzionali.

  • Viene definita una classe base astratta (PeerClient) che deve essere derivata per implementare una classe da usare come client per un servizio peer-to-peer.

  • Emette un segnale quando ha completato (con successo o meno) la fase di reperimento delle mappe di partecipazione ai servizi opzionali.

  • Fornisce un metodo (register) per registrare le istanze di classi che rappresentano un servizio a cui il nodo partecipa.

  • Fornisce dei metodi (begin_retrieve_cache e next_retrieve_cache) per i vari servizi registrati perché possano all'avvio recuperare i record di pertinenza del nodo.

  • Per i servizi opzionali, questi vanno chiamati solo dopo che è stato completato il reperimento delle mappe di partecipazione.

  • Fornisce dei metodi (begin_replica e next_replica) per i vari servizi registrati perché possano replicare i record salvati su un numero di nodi replica.

  • Questi vanno chiamati dalle classi che implementano un servizio, appunto quando hanno salvato (o modificato) un record.

  • Fornisce un metodo (contact_peer) per effettuare una richiesta ad un servizio peer-to-peer. Sono passate al metodo queste informazioni:

    • l'identificativo del servizio,

    • la tupla obiettivo, cioè il risultato di hp ( k ),

    • l'istanza di IPeersRequest che rappresenta la richiesta da effettuare,
    • il tempo limite per l'esecuzione della richiesta una volta consegnata all'hash_node.
  • Queste informazioni passate al metodo contact_peer lo abilitano ad effettuare la richiesta senza dover conoscere altro sul servizio: infatti per fare una richiesta ad un servizio il nodo non ha bisogno di partecipare attivamente al servizio, quindi il nodo potrebbe non aver passato il servizio in questione al metodo register; basta che il nodo sappia come interfacciarsi con il servizio.
  • Il metodo restituisce una istanza di IPeersResponse che può rappresentare il risultato della richiesta o una eccezione prevista dal servizio stesso.

  • Oppure rilancia una eccezione (PeersNoParticipantsInNetworkError) se al momento nessun nodo nella rete partecipa attivamente al servizio.

Classi e interfacce

La classe HCoord è una classe comune nota a questo modulo. E' una classe serializzabile, cioè le cui istanze sono adatte al passaggio di dati a metodi remoti (vedi framework ZCD). Una sua istanza contiene le coordinate gerarchiche di un g-nodo nella mappa del nodo: livello e identificativo nel livello.

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 l'identificativo del proprio nodo a ogni livello (metodo 'i_peers_get_my_pos');
  • Leggere il numero di nodi stimato all'interno del proprio g-nodo a ogni livello (metodo 'i_peers_get_nodes_in_my_group');

  • Determinare se un certo g-nodo esiste nella rete – cioè se appartiene a domn(αt) (metodo 'i_peers_exists');

  • Ottenere uno stub per inviare un messaggio al miglior gateway verso un certo g-nodo, segnalando opzionalmente se si vuole escludere un certo gateway perché era il passo precedente nell'instradamento del messaggio e / o se si vuole escludere e rimuovere un certo gateway che nel tentativo precedente ha fallito la comunicazione (metodo 'i_peers_gateway').
  • Ottenere uno stub per inviare un messaggio ad un mio vicino che appartiene al mio stesso g-nodo di un dato livello (metodo 'i_peers_fellow').
  • All'avvio del nodo, se esso non ha formato una nuova rete ma piuttosto è entrato in un g-nodo, allora usa subito questo metodo per individuare un vicino che fa parte di quello stesso g-nodo in cui è entrato. Userà questo stub per richiedere a tale vicino la mappa corrente dei g-nodi che partecipano a servizi opzionali.

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.

In tutti i casi in cui questo è necessario il dialogo tra i due nodi è molto semplice e prevede sempre uno scambio di richiesta e risposta ad iniziativa del nodo che inizia la connessione. Sarà quindi sufficiente che si ottenga uno stub che realizza la chiamata di un metodo remoto tramite questa connessione TCP.

L'oggetto fornito al modulo a questo scopo implementa l'interfaccia IPeersBackStubFactory, la quale permette di:

  • ottenere uno stub per inviare un messaggio ad un dato nodo mediante connessione TCP interna (metodo 'i_peers_get_tcp_inside').

In alcuni casi sarà necessario inviare una comunicazione ai vicini che appartengono alla mia stessa rete. L'oggetto fornito al modulo a questo scopo implementa l'interfaccia IPeersNeighborsFactory, la quale permette di:

  • ottenere uno stub per inviare un messaggio a tutti i vicini appartenenti alla nostra rete (metodo 'i_peers_get_broadcast') specificando una istanza di IPeersMissingArcHandler per gestire gli archi su cui non si è ricevuto un acknowledgement.
  • data una istanza di IPeersArc ottenere uno stub per inviare un messaggio reliable su quell'arco (metodo 'i_peers_get_tcp').

Quando il modulo usa il metodo i_peers_get_broadcast sull'oggetto IPeersNeighborsFactory "nf" fornito dal suo utilizzatore, gli passa un oggetto IPeersMissingArcHandler "ah". Lo stub che l'utilizzatore fornisce ora al modulo tiene conto di questo "ah". Quando lo stub trasmette un messaggio si aspetta di ricevere, entro un tempo limite, un acknowledgement tramite ognuno degli archi noti al nodo (non sono noti al modulo, ma al suo utilizzatore): se per qualcuno degli archi questo non avviene, allora lo stub si occuperà di richiamare su "ah" il metodo 'i_peers_missing' che riceve un'istanza di IPeersArc. Questa istanza è di un oggetto del tutto oscuro al modulo, che lo può solo passare al metodo i_peers_get_tcp dell'oggetto "nf".

L'interfaccia IPeersRequest non specifica nulla. Va implementata da un oggetto serializzabile. Tale oggetto deve contenere le informazioni che possano identificare una chiamata ad un metodo remoto in un certo servizio.

Il "client" che prepara questo oggetto è specifico di un certo servizio p. Esso può assumere che il "server" che lo riceverà è il server specifico dello stesso servizio p.

Segue un esempio, per nulla vincolante, di cosa questo oggetto potrebbe contenere.

  • Il nome del metodo. Si tratta di una stringa.
  • Gli argomenti del metodo. Si tratta di un array di stringhe che rappresentano in formato JSON gli argomenti del metodo.

L'interfaccia IPeersResponse non specifica nulla. Va implementata da un oggetto serializzabile. Tale oggetto deve contenere le informazioni che possano rappresentare una risposta fornita da un metodo remoto in un certo servizio.

Il "server" che prepara questo oggetto è specifico di un certo servizio p ed è stato invocato su un particolare metodo m esposto da questo servizio. Esso può assumere che il "client" che lo riceverà è il client specifico dello stesso servizio p e sa che si tratta di una risposta a quel particolare metodo m.

Segue un esempio, per nulla vincolante, di cosa questo oggetto potrebbe contenere.

  • L'eccezione lanciata. Si tratta di 3 stringhe nullable: error_domain, error_code, error_message.
  • Il valore di ritorno. Si tratta di una stringa. Se le stringhe error_* non sono valorizzate, allora questa stringa rappresenta in formato JSON il risultato della chiamata del metodo.

Tutte le classi che implementano un servizio derivano da PeerService. Questa è una classe astratta definita dal modulo.

La classe base ha un membro p_id che identifica un servizio in tutta la rete. Esso è valorizzato nel costruttore ed è in seguito di sola lettura. L'istanza del servizio è passata come istanza di PeerService al modulo (PeersManager) nella chiamata iniziale al metodo di registrazione e questo la memorizza associandola al suo identificativo.

La classe base ha un membro booleano p_is_optional che dice se il servizio è da considerarsi opzionale. Esso è valorizzato nel costruttore ed è in seguito di sola lettura.

La classe base ha un metodo virtuale is_ready() che dice se il nodo è pronto a servire. L'implementazione della classe base risponde sempre True. La classe del servizio che la deriva può modificare l'implementazione. In questo caso il nodo può decidere, secondo la logica propria del servizio specifico, di non rispondere in certi momenti alle richieste. Questo nonostante che il nodo sia partecipante a questo servizio, sia esso opzionale o non. Infatti se non fosse partecipante non esisterebbe l'istanza registrata nel modulo PeersManager.

La classe base ha un metodo astratto exec che viene richiamato sull'hash_node che deve servire una richiesta. Esso riceve una istanza di IPeersRequest e restituisce una istanza di IPeersResponse.

La classe PeerClient può essere derivata per implementare il client di un servizio, sia esso opzionale o non opzionale.

La classe derivata, per ogni tipo di richiesta che è prevista dal servizio, ha il compito di produrre l'oggetto IPeersRequest che rappresenta la richiesta, di specificare quale sia il tempo massimo di attesa per l'esecuzione, di interpretare l'istanza di IPeersResponse ricevuta come risposta.

La classe base ha la conoscenza della topologia della rete, cioè il numero di livelli e per ognuno la gsize. Oltre a ciò non necessita di conoscere le posizioni del nodo corrente. Ha inoltre conoscenza dell'identificativo del servizio.

La classe base ha un riferimeno all'istanza di PeersManager che usa per contattare l'hash_node (metodo contact_peer).

Nella classe derivata va definito il calcolo di hp. La funzione hp deve associare ad una chiave k un indirizzo in S, cioè una tupla x̄ = x̄0·x̄1·...·x̄l-1 le cui componenti siano compatibili con la topologia della rete. 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 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 x̄ 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. In questo caso, inoltre, può decidere di restituire una tupla con un numero di elementi inferiore al numero di livelli della rete. In questo caso la tupla x̄ = x̄0·x̄1·...·x̄j quando viene passata alla funzione Ht circoscrive la sua ricerca dell'hash_node al g-nodo nj+1 del nodo n che fa la richiesta.

Netsukuku/ita/docs/ModuloPeers/AnalisiFunzionale (last edited 2015-11-14 14:57:23 by lukisi)