Modulo PeerServices - Analisi Funzionale

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.

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.

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), 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.

Memoria esaurita e memoria non esaustiva

Inoltre, nell'implementazione della funzione Ht, occorre dare la possibilità al singolo nodo, una volta che è stato individuato e contattato e gli è stata fatta una richiesta, di rifiutarsi di elaborarla e così di obbligare la stessa funzione Ht a trovare un altro nodo. Ad esempio, questo si rende necessario quando il singolo nodo contattato, chiamiamolo n, non ha più memoria libera.

Se la richiesta era di inserimento il nodo n, se non ha più memoria libera, rifiuta di memorizzare e quindi la funzione Ht trova il prossimo nodo. Allo stesso tempo il nodo n si ricorderà (fin quando permarrà in questo stato) di non avere tutte le informazioni necessarie per rispondere "NOT_FOUND" ad una richiesta di lettura o aggiornamento, cioè di non essere esaustivo.

Se la richiesta era di lettura o aggiornamento il nodo n, se non trova il record per la chiave k nella sua memoria e ricorda di non essere esaustivo, rifiuta di rispondere e quindi la funzione Ht trova il prossimo nodo.

Questo concetto di essere non esaustivo viene usato da un nodo n anche quando è da poco entrato nella rete ed è ancora in attesa di reperire i record di sua pertinenza.

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:

Questa conoscenza la possiamo chiamare domnt), cioè il dominio della funzione αt secondo le conoscenze di n.

L'implementazione della funzione Ht deve dunque avvenire in modo distribuito. Vedremo come nel documento dei dettagli.

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. Il modulo PeerServices saprà a chi indirizzare la richiesta. Infatti, 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.


Un nodo che intende partecipare attivamente ad un servizio, se fa ingresso in una rete esistente, può trovarsi in bisogno di reperire i record che sono di sua pertinenza nel mantenimento del database distribuito, come destinatario principale o come replica. Nell'espletamento di questa mansione il nodo si può avvalere di alcune funzioni helper che il modulo PeerServices fornisce.

Requisiti

Deliverables

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ò:


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:


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:

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.


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.


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 è chiamato a servire una richiesta. Se viene chiamato significa che:

Il metodo exec, dunque, riceve una istanza di IPeersRequest; ma esso è ancora in grado di rifiutarsi di elaborare la richiesta, ad esempio per memoria esaurita o non esaustiva, rilanciando una eccezione PeersRefuseExecutionError.

Inoltre, è in grado di dare istruzione al client di riavviare da capo il calcolo distribuito di Ht, rilanciando una eccezione PeersRedoFromStartError. Lo fa se ritiene plausibile di non essere più il miglior candidato, ad esempio se ha fatto attendere il client per una richiesta di scrittura mentre reperiva il record dal precedente detentore.

Altrimenti, elabora la richiesta e restituisce una istanza di IPeersResponse.

Nell'elaborazione della richiesta la classe del servizio ha a disposizione (come ulteriore argomento del metodo exec) la tupla q0·q1·...·qj-1 parte dell'indirizzo del nodo richiedente q che ha in comune con il nodo corrente il g-nodo di livello j. Si tratta di una lista di interi (List<int>), che può anche essere vuota: significa che il richiedente e il servente coincidono.


La classe PeerClient deve 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:

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)