|
Size: 18035
Comment:
|
Size: 13199
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 13: | Line 13: |
| Il servizio Coordinator è un servizio non opzionale, cioè tutti i nodi partecipano attivamente. | Il servizio Coordinator è un servizio non opzionale, cioè tutti i nodi partecipano attivamente. Si tratta di un servizio che mantiene un database distribuito della tipologia a chiavi fisse. |
| Line 15: | Line 15: |
| Lo scopo del servizio Coordinator è quello di realizzare una sorta di memoria condivisa di un g-nodo ''g'' di livello ''l'', con 0 < ''l'' ≤ ''levels''. Il livello ''l'' è maggiore di 0 poiché non serve realizzare una memoria condivisa per il singolo nodo. Può essere uguale al numero dei livelli, poiché è necessario avere una memoria condivisa anche per l'unico g-nodo di livello ''l'' = ''levels'' che costituisce l'intera rete. | Lo scopo del servizio Coordinator è quello di realizzare una sorta di memoria condivisa di un g-nodo ''g''. Quando un nodo ''n'' vuole accedere alla memoria condivisa del suo g-nodo ''g'' di livello ''l'', con 0 < ''l'' ≤ ''levels'', fa una richiesta al servizio Coordinator usando come chiave il livello ''l''. |
| Line 17: | Line 17: |
| Lo spazio delle chiavi definito dal servizio Coordinator è l'insieme dei valori che può assumere ''l''. | Il livello ''l'' è maggiore di 0 poiché non serve realizzare una memoria condivisa per il singolo nodo. Può essere uguale al numero dei livelli, poiché è necessario avere una memoria condivisa anche per l'unico g-nodo di livello ''l'' = ''levels'' che costituisce l'intera rete. |
| Line 19: | Line 19: |
| La funzione ''h'' definita dal servizio restituisce per la chiave ''l'' il valore ''x̄'' = 0·0·...·0, ''l'' volte. Cioè ''x̄~-,,i,,-~'' = 0, con ''i'' da 0 a ''l'' - 1. | Lo spazio delle chiavi definito dal servizio Coordinator è appunto l'insieme dei valori che può assumere ''l''. |
| Line 21: | Line 21: |
| L'algoritmo distribuito di ricerca dell'hash_node, quindi, effettua sempre una ricerca circoscritta nel g-nodo di livello ''l'' del nodo corrente. In altre parole, il nodo corrente può contattare solo il Coordinator di uno dei suoi g-nodi, ed il Coordinator si trova all'interno del g-nodo stesso. === Nodo pronto a rispondere === Sebbene il servizio sia non opzionale, abbiamo visto come un nodo che partecipa attivamente ad un servizio è in grado di esimersi dal rispondere a richieste. Infatti se ridefinisce il metodo ''is_ready'' della classe base !PeerService può non accettare di servire richieste. L'algoritmo di instradamento in questo caso fa in modo di contattare un altro nodo disposto se c'è. Altrimenti lancerebbe una eccezione !NoParticipantsInNetwork. Fatta questa premessa, consideriamo il fatto che quando un nodo viene scelto come detentore della memoria condivisa di un g-nodo svolge un compito molto delicato. Supponiamo di trovarci in un g-nodo ''g'' alquanto ampio, ad esempio costituito da 100 nodi, qualsiasi sia il livello ''l''. Il nodo che al momento si avvicina di più all'indirizzo dell'hash_node sia ''n_0'', diciamo con dist(''x̄'', ''n_0'') = 200. Il successivo sia ''n_1'' con dist(''x̄'', ''n_1'') = 240. Supponiamo ora che il percorso (interno a ''g'') che collega il nodo ''n_0'' con ''n_1'' sia alquanto lungo. Supponiamo ora che un nuovo nodo ''n_2'' voglia entrare nel g-nodo ''g'' e si trovi fisicamente molto vicino a ''n_0''. Esso contatta il nodo ''n_0'' in qualità di Coordinator e questi gli assegna un indirizzo in ''g'' tale che dist(''x̄'', ''n_2'') = 210. Siccome ''n_2'' è fisicamente vicino a ''n_0'', in pochi istanti ''n_2'' conosce di essere stato ammesso in ''g'' e di avere un indirizzo prossimo al hash_node. In seguito ''n_2'' avvia la trasmissione dell'ETP ''e0'' che comunica la nascita di ''n_2'' agli altri membri di ''g''. Supponiamo che dopo pochi istanti il nodo ''n_0'' muoia. I suoi vicini avviano la trasmissione dell'ETP ''e1'' che informa della morte di ''n_0''. L'ETP ''e1'' raggiunge il nodo ''n_2'' il quale scopre di essere ora il nodo con indirizzo più prossimo al hash_node. Inoltre ''e1'' raggiunge anche ''n_1''. Invece ''e0'' non ha ancora raggiunto ''n_1''. In questo momento il nodo ''n_1'' e tutti quelli nelle sue vicinanze che non hanno ancora ricevuto ''e0'' ritengono che il nodo Coordinator sia ''n_1''. Nello stesso momento i nodi nelle vicinanze di ''n_2'' ritengono che il Coordinator sia ''n_2''. '''__TODO__: Rivedere le conclusioni che seguono alla luce del meccanismo di recupero atomico dei record implementato nel modulo !PeerServices.''' Sia ''n_j'' uno dei nodi nelle vicinanze di ''n_1''. Sia ''n_k'' uno dei nodi nelle vicinanze di ''n_2''. Ora, se ''n_j'' e ''n_k'' vogliono accedere in scrittura alla memoria condivisa del g-nodo ''g'' avremo una situazione di inconsistenza: entrambi i nodi vedrebbero la loro richiesta soddisfatta, ma la modifica apportata da ''n_j'' non sarebbe permanente. Oppure, ''n_j'' accede in lettura alla memoria condivisa e reperisce informazioni diverse da quelle che reperisce ''n_k''. Il problema, a ben vedere, sta nel fatto che un nodo (''n_2'') accetta di servire richieste come Coordinator di un g-nodo quando ancora non tutti i nodi nel g-nodo sono stati informati della sua presenza. Proviamo quindi a delineare una soluzione. Supponiamo che un nodo appena entrato in un g-nodo aspetti un certo tempo prima di accettare richieste per il servizio Coordinator. Vediamo quanto tempo occorre aspettare. Se ''n'' è il primo nodo che costituisce una rete, esso è subito uscito dalla fase di bootstrap, ed è anche subito pronto ad accettare richieste come Coordinator del g-nodo di qualsiasi livello. Entrambe le cose sono segnalate immediatamente al modulo Coordinator: la prima avviando le attività del modulo stesso ~-(cioè istanziando il !CoordinatorManager)-~ e la seconda richiamando il suo metodo ''presence_notified''. Supponiamo invece che ''n'' sia un nuovo nodo che ha fatto ingresso in un g-nodo ''g'' di livello ''l'' di una rete esistente, costituendo un nuovo g-nodo di livello ''l-1''. Questo significa che ha appena contattato il Coordinator di ''g'', cioè esiste in ''g'' almeno un nodo pronto ad accettare richieste come Coordinator. Supponiamo che subito arrivi al nodo ''n'' una richiesta come Coordinator del suo g-nodo di livello ''k'', con ''k'' ≥ ''l''. Significa che il precedente nodo Coordinator per il livello ''k'' era sicuramente all'interno di ''g''. Di conseguenza gli altri nodi che devono avere il tempo di accorgersi della presenza di ''n'' sono solo quelli interni a ''g''. Quindi il nodo ''n'' deve attendere un po' di tempo prima di essere disponibile a rispondere a tali richieste, ma nel frattempo altri nodi interni a ''g'' sono pronti a rispondere, perciò non ci sono ritardi per chi vuole accedere alla memoria condivisa del g-nodo di livello ''k'', con ''k'' ≥ ''l''. Se invece arriva al nodo ''n'' una richiesta come Coordinator del suo g-nodo di livello ''k'', con ''k'' < ''l'', significa che un nodo è interessato ad accedere alla memoria di un g-nodo che è stato costituito proprio da ''n''. Il nodo ''n'' sarebbe quindi perfettamente in grado di rispondere da subito. Purtroppo però il servizio Coordinator è unico e il nodo ''n'' deve rispondere al metodo ''is_ready'' senza avere dettagli sulla richiesta che gli verrà fatta; quindi anche in questo caso il nodo ''n'' non risponderà subito. Se qualcuno volesse accedere alla memoria condivisa del g-nodo di livello ''k'', con ''k'' < ''l'', la sua richiesta verrebbe momentaneamente rifiutata con !NoParticipantsInNetwork. Riassumendo, il nodo ''n'' (non il modulo Coordinator) che ha fatto ingresso nella rete entrando nel g-nodo ''g'' di livello ''l'', attende di uscire dalla fase di bootstrap (evento segnalato dal modulo QSPN); solo dopo questo evento vengono avviate le attività del modulo Coordinator ~-(in quanto solo dopo questo evento viene creata una istanza di !PeersManager e una di !CoordinatorManager)-~, indicando che il g-nodo appena costituito è di livello ''l''-1; poi guarda nella sua mappa (tramite i metodi forniti dal modulo QSPN) il numero di nodi stimati presenti all'interno di ''g'' e (se i costi degli archi sono espressi in latenza) il costo del peggior percorso verso un g-nodo di livello ''l''-1; sulla base di tali informazioni decide quanto tempo deve aspettare per essere sicuro che la sua presenza sia stata notificata tramite ETP a tutti i g-nodi di livello ''l''-1 in ''g''; aspetta questo tempo; poi segnala questo fatto al modulo Coordinator con il suo metodo ''presence_notified''. Il modulo Coordinator del nodo ''n'' dopo aver ricevuto la chiamata al suo metodo ''presence_notified'' saprà che la sua presenza è stata sufficientemente divulgata. Dopo, esso avvia in una tasklet le operazioni per il reperimento dei record di sua competenza. Nel servizio Coordinator il numero delle possibili chiavi è esiguo. Il nodo ''n'' esegue la ricerca ristretta al suo g-nodo di livello ''l'' con la tupla ottenuta con h~-,,p,,-~(k), dove k è la chiave per il Coordinator del g-nodo di livello ''l''. Al nodo contattato richiede tutti i record che riguardano le chiavi ''k'' da ''l'' in su, con il metodo "wait_then_send(k)". Come abbiamo visto nella trattazione del modulo !PeerServices, tale operazione richiede al precedente detentore di attendere alcuni istanti e poi inviare il record per quella chiave. Quando queste operazioni saranno state avviate (in una tasklet) il nodo ''n'' si rende disponibile (metodo ''is_ready'' della classe del servizio) a rispondere alle richieste. Quando arriva una richiesta per il Coordinator al nodo ''n'', se non è stata ancora completata l'operazione di recupero del relativo record, il Coordinator metterà la richiesta in attesa (come abbiamo visto nella trattazione del modulo !PeerServices) finché saprà rispondere. Quando un nodo ''x'' vuole fare una richiesta al servizio Coordinator di un g-nodo ''g'', pur essendo il servizio non opzionale, deve sapere che può ricevere l'eccezione !NoParticipantsInNetwork. In questo caso deve aspettare alcuni istanti e riprovare, fin quando non riesce. Non è possibile che non riesca mai, poché esso stesso è un nodo in ''g'' e prima o poi sarà esso stesso pronto a rispondere alle richieste. |
La funzione ''h~-,,p,,-~'' è definita dal servizio in modo da dare ai dati la visibilità locale circoscritta al g-nodo in esame. In altre parole, il nodo corrente può contattare solo il Coordinator di uno dei suoi g-nodi; sia l'hash-node che il nodo che risponde si trovano all'interno del g-nodo stesso. |
| Line 71: | Line 28: |
* ''name'' = "reserve" |
|
| Line 79: | Line 34: |
| Il nodo che fa la richiesta è un nodo ''n'' che già appartiene al g-nodo ''g''. Questi richiede la prenotazione di un nuovo posto per conto di un altro nodo suo vicino, il quale non è ancora in ''g'' o perfino non è ancora nella rete. | Il nodo che fa la richiesta è un nodo ''n'' che già appartiene al g-nodo ''g''. Questi richiede la prenotazione di un nuovo posto per conto di un altro nodo suo vicino, ''m'', il quale non è ancora in ''g'' o perfino non è ancora nella rete. |
| Line 87: | Line 42: |
| A questo punto il nodo ''n'' comunica queste informazioni al suo vicino che può con esse fare ingresso in ''g'' (e nella rete). | A questo punto il nodo ''n'' comunica queste informazioni al suo vicino ''m'' che può con esse fare ingresso in ''g'' (e nella rete). |
| Line 89: | Line 44: |
| Se nessun posto è disponibile il nodo ''x'' lo segnala con una eccezione. | Se nessun posto è disponibile il nodo ''x'' lo segnala con una eccezione, che viene ricevuta da ''n''. Anche in questo caso ''n'' comunica l'esito al vicino ''m''. |
| Line 98: | Line 53: |
| Si consideri un nodo ''n'' che fa parte di un g-nodo ''g'' di livello ''l''. Il g-nodo ''g'' fa a sua volta parte di un g-nodo ''h'' di livello ''l'' + 1. Supponiamo che il g-nodo ''g'' diventi disconnesso, cioè avviene lo split del g-nodo, mentre ''h'' è ancora connesso. Supponiamo che l'isola in cui si trova ''n'' sia una di quelle che non contengono il nodo più anziano. Supponiamo che ''n'' abbia un vicino ''v'' che appartiene a ''h'' ma non appartiene a ''g''. Per questo il nodo ''n'' riceve da ''v'' l'informazione che tutto il suo g-nodo di livello ''l'' deve cambiare indirizzo. | Si consideri un nodo ''n'' che fa parte di un g-nodo ''g'' di livello ''l''. Il g-nodo ''g'' fa a sua volta parte di un g-nodo ''h'' di livello ''l'' + 1. Supponiamo che il g-nodo ''g'' diventi disconnesso, cioè avviene lo split del g-nodo, mentre ''h'' è ancora connesso. Supponiamo che l'isola in cui si trova ''n'' sia una di quelle che non contengono il nodo più anziano. Supponiamo che ''n'' abbia un vicino ''v'' che appartiene a ''h'' ma non appartiene a ''g''. Per questo il nodo ''n'' riceve da ''v'' l'informazione che tutta la sua isola (di livello ''l'') deve cambiare indirizzo. |
| Line 105: | Line 60: |
| * Il livello a cui il nodo ha costituito un g-nodo nuovo. Durante le sue operazioni, il modulo viene informato quando il nodo ha completato la fase di bootstrap. In quello stesso momento gli vengono forniti: |
|
| Line 107: | Line 65: |
Durante le sue operazioni, il modulo viene informato quando il nodo ha completato la fase di bootstrap e a quale livello ha costituito un nuovo g-nodo. Viene anche informato quando il nodo considera che la notifica della sua presenza abbia ormai raggiunto tramite ETP tutti i membri del g-nodo in cui è entrato. |
|
| Line 113: | Line 69: |
| * Chiedere ad un vicino, dato uno stub per contattarlo, quanti posti vede liberi (nella sua mappa, senza contattare i singoli Coordinator) nei suoi g-nodi. Metodo ''get_neighbor_map''. | * Chiedere ad un vicino ''v'', dato uno stub per contattarlo, quanti posti vede liberi (nella sua mappa, senza contattare i singoli Coordinator) nei suoi g-nodi. Metodo ''get_neighbor_map''. . Questo metodo può rilanciare l'eccezione !CoordinatorStubNotWorkingError se la comunicazione con il vicino non riesce. . Questo metodo può rilanciare l'eccezione !CoordinatorNodeNotReadyError se il vicino ''v'' non ha ancora completato la fase di boostrap (vedi modulo [[Netsukuku/ita/docs/ModuloQSPN/EsplorazioneRete#Rete_completamente_esplorata|QSPN]]). Infatti il nodo ''v'' non è in grado di rispondere alle richieste dell'interfaccia ICoordinatorMap, quindi il modulo Coordinator nel nodo ''v'' non ha ancora ricevuto l'istanza di tale interfaccia. . Se invece non sono rilanciate eccezioni, il metodo restituisce una istanza di ICoordinatorNeighborMap. |
| Line 121: | Line 80: |
| * Dato un livello ''l'', chiedere ad un vicino, dato uno stub per contattarlo, di richiedere al Coordinator del suo g-nodo di livello ''l'' la prenotazione di un posto. Metodo ''get_reservation''. . Se la prenotazione non riesce, potrebbe essere dovuto alle precedenti prenotazioni non ancora confermate da un ETP, quindi avrebbe poco senso chiedere di nuovo al vicino quanti posti vede liberi. Si assuma che al livello ''l'' i posti sono 0 e si continui a ritenere validi i valori per gli altri livelli. |
* Dato un livello ''l'', chiedere ad un vicino ''v'', dato uno stub per contattarlo, di richiedere al Coordinator del suo g-nodo di livello ''l'' la prenotazione di un posto, come nuovo g-nodo di livello ''l'' - 1. Metodo ''get_reservation''. . Questo metodo può rilanciare l'eccezione !CoordinatorStubNotWorkingError se la comunicazione con il vicino non riesce. . Questo metodo può rilanciare l'eccezione !CoordinatorNodeNotReadyError se il vicino ''v'' non ha ancora completato la fase di boostrap (vedi modulo QSPN). Infatti il nodo ''v'' non ha ancora potuto instanziare il suo !PeersManager, né il !CoordinatorService. . Questo metodo può rilanciare l'eccezione !CoordinatorInvalidLevelError, segnalata immediatamente dal vicino, se il livello richiesto non è coerente con la topologia della rete in cui si trova il vicino. . Questo metodo può rilanciare l'eccezione !CoordinatorSaturatedGnodeError, segnalata dal vicino dopo aver comunicato con il servizio Coordinator, se al livello richiesto non è stato possibile riservare un posto. . Di solito questa operazione si fa subito dopo aver ottenuto dallo stesso vicino la lista del numero di posti che vede liberi. Se la prenotazione non riesce, potrebbe essere dovuto alle precedenti prenotazioni non ancora confermate da un ETP, quindi avrebbe poco senso chiedere di nuovo al vicino quanti posti vede liberi. Si assuma che al livello ''l'' i posti sono 0 e si continui a ritenere validi i valori per gli altri livelli, sia superiori che inferiori. . Se invece non sono rilanciate eccezioni, il metodo restituisce una istanza di ICoordinatorReservation. Con i dati contenuti in questa istanza (si veda sotto il dettaglio) il nodo potrà costituire un nuovo g-nodo. |
| Line 126: | Line 90: |
| Il modulo Coordinator si occupa di registrare con il modulo !PeerServices l'implementazione del servizio Coordinator e di segnalarsi come pronto a gestire le richieste appena ciò è possibile. | Il modulo Coordinator si occupa di registrare con il !PeersManager l'implementazione del servizio Coordinator e di usare gli algoritmi forniti dal modulo !PeerServices per il mantenimento del relativo database a chiavi fisse. Cioè, esso crea una istanza della classe !CoordinatorService.!DatabaseDescriptor, che implementa IFixedKeysDatabaseDescriptor. Con questa istanza come parametro, al bisogno, chiama i metodi ''fixed_keys_db_on_startup'' e ''fixed_keys_db_on_request'' di !PeersManager. |
| Line 133: | Line 97: |
| * Leggere il numero di livelli della topologia (metodo 'i_coordinator_get_levels'). * Leggere la gsize di ogni livello ''i'' da 0 a ''l''-1 (metodo 'i_coordinator_get_gsize'). |
* Leggere il numero ''l'' dei livelli della topologia (metodo 'i_coordinator_map_get_levels'). * Leggere la gsize di ogni livello ''i'' da 0 a ''l'' - 1 (metodo 'i_coordinator_map_get_gsize'). |
| Line 136: | Line 100: |
| . Sia ''l'' il numero dei livelli. Per ogni ''i'' da 0 a ''l''-1, ''gsize(i)'' è il numero massimo di g-nodi di livello ''i'' in un g-nodo di livello ''i''+1. * Leggere l'anzianità del mio g-nodo ad ogni livello ''i'' da 0 a ''l''-1 (metodo 'i_coordinator_get_eldership'). * Leggere l'elenco delle posizioni libere in ogni livello ''i'' da 0 a ''l''-1 (metodo 'i_coordinator_get_free_pos'). . Cioè le posizioni nel livello ''i'' che sono libere nel nostro g-nodo di livello ''i''+1. |
. Per ogni ''i'' da 0 a ''l'' - 1, ''gsize(i)'' è il numero massimo di g-nodi di livello ''i'' in un g-nodo di livello ''i'' + 1. * Leggere l'anzianità del mio g-nodo ad ogni livello ''i'' da 0 a ''l'' - 1 (metodo 'i_coordinator_map_get_eldership'). . L'anzianità di un g-nodo è un numero progressivo che viene assegnato al g-nodo. Nel confronto tra due g-nodi di pari livello ''i'' entrambi appartenenti allo stesso g-nodo di livello ''i'' + 1, un valore più alto significa che il g-nodo è arrivato dopo, cioè esso è più giovane. * Leggere la posizione del nodo, cioè la posizione del mio g-nodo ad ogni livello ''i'' da 0 a ''l'' - 1 (metodo 'i_coordinator_map_get_my_pos'). * Leggere l'elenco delle posizioni libere in ogni livello ''i'' da 0 a ''l'' - 1 (metodo 'i_coordinator_map_get_free_pos'). . Cioè le posizioni nel livello ''i'' che sono libere nel nostro g-nodo di livello ''i'' + 1. Questa informazione è quella che si basa sulla mappa del nodo corrente, senza contattare il Coordinator attuale che ha la conoscenza autoritativa delle prenotazioni pendenti. |
| Line 144: | Line 110: |
| * Il numero di livelli nella topologia. * La gsize di ogni livello. * Il numero di posti liberi in ogni livello. |
* ''levels'': Il numero di livelli nella topologia. * ''gsizes[i]'': La gsize per ogni livello, con ''i'' da 0 a ''levels'' - 1. * ''free_pos_count[i]'': Il numero di posti liberi in ogni livello, con ''i'' da 0 a ''levels'' - 1. |
| Line 151: | Line 117: |
| * ''levels'': Il numero di livelli nella topologia. * ''gsizes[i]'': La gsize per ogni livello, con ''i'' da 0 a ''levels'' - 1. |
|
| Line 152: | Line 120: |
| * I valori di anzianità dal livello ''lvl'' in su fino a ''levels - 1'', inclusi. | * ''elderships[i]'': I valori di anzianità per ogni livello ''i'' da ''lvl'' fino a ''levels'' - 1, inclusi. . Per i livelli inferiori a ''lvl'' il nodo, che ha appena costituito un nuovo g-nodo di livello ''lvl'', userà come anzianità il valore 0. |
Modulo Coordinator - Analisi Funzionale
Contents
Il modulo cerca di fare sì che un singolo g-nodo di livello l, sebbene costituito da un numero di singoli nodi, abbia un comportamento coerente come singola entità.
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.
Il modulo fa uso diretto delle classi e dei servizi forniti dal modulo PeerServices. In particolare, esso realizza un servizio peer-to-peer, chiamato appunto Coordinator, per mezzo del quale svolge alcuni dei suoi compiti.
Il servizio Coordinator
Il servizio Coordinator è un servizio non opzionale, cioè tutti i nodi partecipano attivamente. Si tratta di un servizio che mantiene un database distribuito della tipologia a chiavi fisse.
Lo scopo del servizio Coordinator è quello di realizzare una sorta di memoria condivisa di un g-nodo g. Quando un nodo n vuole accedere alla memoria condivisa del suo g-nodo g di livello l, con 0 < l ≤ levels, fa una richiesta al servizio Coordinator usando come chiave il livello l.
Il livello l è maggiore di 0 poiché non serve realizzare una memoria condivisa per il singolo nodo. Può essere uguale al numero dei livelli, poiché è necessario avere una memoria condivisa anche per l'unico g-nodo di livello l = levels che costituisce l'intera rete.
Lo spazio delle chiavi definito dal servizio Coordinator è appunto l'insieme dei valori che può assumere l.
La funzione hp è definita dal servizio in modo da dare ai dati la visibilità locale circoscritta al g-nodo in esame. In altre parole, il nodo corrente può contattare solo il Coordinator di uno dei suoi g-nodi; sia l'hash-node che il nodo che risponde si trovano all'interno del g-nodo stesso.
Servizi previsti
Elenchiamo tutte le richieste che si possono fare al Coordinator.
Prenota un posto
La richiesta r di prenotare un posto può arrivare ad un nodo x come Coordinator di un g-nodo g di livello l, con 0 < l ≤ levels. I membri di r sono:
lvl = livello di g.
Il nodo x valuta se ci sono posti liberi in g considerando la sua mappa dei percorsi. Deve considerare anche le prenotazioni concesse in precedenza, le quali restano valide per un certo tempo anche se ancora non sono nella sua mappa perché non sono ancora state confermate da un ETP.
Se un posto è disponibile il nodo x lo prenota. Questo equivale ad una scrittura nella memoria condivisa, quindi è necessario provvedere anche alle repliche con il meccanismo fornito dal modulo PeerServices.
Il nodo che fa la richiesta è un nodo n che già appartiene al g-nodo g. Questi richiede la prenotazione di un nuovo posto per conto di un altro nodo suo vicino, m, il quale non è ancora in g o perfino non è ancora nella rete.
Nella risposta al nodo n, x segnala:
La posizione assegnata all'interno di g.
La anzianità della posizione assegnata all'interno di g.
L'anzianità di g e dei suoi g-nodi superiori.
A questo punto il nodo n comunica queste informazioni al suo vicino m che può con esse fare ingresso in g (e nella rete).
Se nessun posto è disponibile il nodo x lo segnala con una eccezione, che viene ricevuta da n. Anche in questo caso n comunica l'esito al vicino m.
Richiesta al diretto vicino di accesso al servizio Coordinator
In alcuni casi un nodo n può voler chiedere ad un suo diretto vicino di accedere al servizio peer-to-peer del Coordinator.
Non sono ancora nella rete
Si consideri un nodo n che non ha fatto ancora ingresso in una rete. Comunicando con un suo vicino v, il nodo n apprende che v appartiene al g-nodo g e che in tale g-nodo c'è ancora spazio. Vorrebbe quindi richiedere l'accesso nel g-nodo g. In questo caso n chiede a v di accedere alla memoria condivisa del g-nodo g per cercare di riservargli un posto.
Sono in un isola che deve migrare
Si consideri un nodo n che fa parte di un g-nodo g di livello l. Il g-nodo g fa a sua volta parte di un g-nodo h di livello l + 1. Supponiamo che il g-nodo g diventi disconnesso, cioè avviene lo split del g-nodo, mentre h è ancora connesso. Supponiamo che l'isola in cui si trova n sia una di quelle che non contengono il nodo più anziano. Supponiamo che n abbia un vicino v che appartiene a h ma non appartiene a g. Per questo il nodo n riceve da v l'informazione che tutta la sua isola (di livello l) deve cambiare indirizzo.
In questo momento il nodo n non ha più un indirizzo valido in g e non è sicuro nemmeno che ci sia ancora spazio per un nuovo g-nodo in h.
Supponiamo che a seguito di tale evento, per una strategia che non è di pertinenza di questo modulo, il nodo n voglia accedere alla memoria condivisa del g-nodo h. Se cercasse di farlo autonomamente potrebbe risultare dal calcolo dell'hash_node che esso si trova proprio in g. Ma il nodo n non è più parte del vero g e non può nemmeno avere percorsi nella sua mappa che lo colleghino al vero g. Allora n deve chiedere a v di accedere in vece sua alla memoria condivisa del g-nodo h. Anche se l'hash_node si trova proprio in g il nodo v saprà instradare il messaggio verso il vero g.
Requisiti
- Il livello a cui il nodo ha costituito un g-nodo nuovo.
Durante le sue operazioni, il modulo viene informato quando il nodo ha completato la fase di bootstrap. In quello stesso momento gli vengono forniti:
L'istanza di PeersManager.
- Mappa delle posizioni libere/occupate ai vari livelli.
Deliverables
Fornisce metodi per:
Chiedere ad un vicino v, dato uno stub per contattarlo, quanti posti vede liberi (nella sua mappa, senza contattare i singoli Coordinator) nei suoi g-nodi. Metodo get_neighbor_map.
Questo metodo può rilanciare l'eccezione CoordinatorStubNotWorkingError se la comunicazione con il vicino non riesce.
Questo metodo può rilanciare l'eccezione CoordinatorNodeNotReadyError se il vicino v non ha ancora completato la fase di boostrap (vedi modulo QSPN). Infatti il nodo v non è in grado di rispondere alle richieste dell'interfaccia ICoordinatorMap, quindi il modulo Coordinator nel nodo v non ha ancora ricevuto l'istanza di tale interfaccia.
- Se invece non sono rilanciate eccezioni, il metodo restituisce una istanza di ICoordinatorNeighborMap.
- Dalla risposta deve essere possibile leggere queste informazioni:
- Il numero di livelli nella topologia.
- La gsize di ogni livello.
- Il numero di posti liberi in ogni livello.
Quando un nodo n chiede al vicino v quanti posti liberi vede nella sua mappa, non assumiamo che il nodo v appartenga già alla stessa rete di n; quindi nemmeno che abbiano la stessa topologia.
- La topologia della rete in cui si vuole fare ingresso è importante che sia nota. Infatti il nodo richiedente potrebbe essere un gateway verso una rete privata in cui si vogliono adottare diversi meccanismi di assegnazione di indirizzi e routing. In questo caso il gateway potrebbe volere una assegnazione di un g-nodo di livello tale da poter disporre di un certo spazio (numero di bits) per gli indirizzi interni.
- Il numero di posti liberi in un dato livello potrebbe essere una informazione eccessiva. Probabilmente al nodo richiedente è sufficiente sapere se c'è almeno un posto o no. Per ora manteniamo questa informazione.
Dato un livello l, chiedere ad un vicino v, dato uno stub per contattarlo, di richiedere al Coordinator del suo g-nodo di livello l la prenotazione di un posto, come nuovo g-nodo di livello l - 1. Metodo get_reservation.
Questo metodo può rilanciare l'eccezione CoordinatorStubNotWorkingError se la comunicazione con il vicino non riesce.
Questo metodo può rilanciare l'eccezione CoordinatorNodeNotReadyError se il vicino v non ha ancora completato la fase di boostrap (vedi modulo QSPN). Infatti il nodo v non ha ancora potuto instanziare il suo PeersManager, né il CoordinatorService.
Questo metodo può rilanciare l'eccezione CoordinatorInvalidLevelError, segnalata immediatamente dal vicino, se il livello richiesto non è coerente con la topologia della rete in cui si trova il vicino.
Questo metodo può rilanciare l'eccezione CoordinatorSaturatedGnodeError, segnalata dal vicino dopo aver comunicato con il servizio Coordinator, se al livello richiesto non è stato possibile riservare un posto.
Di solito questa operazione si fa subito dopo aver ottenuto dallo stesso vicino la lista del numero di posti che vede liberi. Se la prenotazione non riesce, potrebbe essere dovuto alle precedenti prenotazioni non ancora confermate da un ETP, quindi avrebbe poco senso chiedere di nuovo al vicino quanti posti vede liberi. Si assuma che al livello l i posti sono 0 e si continui a ritenere validi i valori per gli altri livelli, sia superiori che inferiori.
- Se invece non sono rilanciate eccezioni, il metodo restituisce una istanza di ICoordinatorReservation. Con i dati contenuti in questa istanza (si veda sotto il dettaglio) il nodo potrà costituire un nuovo g-nodo.
Implementa il servizio Coordinator derivando la classe CoordinatorService dalla classe base PeerService.
Il modulo Coordinator si occupa di registrare con il PeersManager l'implementazione del servizio Coordinator e di usare gli algoritmi forniti dal modulo PeerServices per il mantenimento del relativo database a chiavi fisse. Cioè, esso crea una istanza della classe CoordinatorService.DatabaseDescriptor, che implementa IFixedKeysDatabaseDescriptor. Con questa istanza come parametro, al bisogno, chiama i metodi fixed_keys_db_on_startup e fixed_keys_db_on_request di PeersManager.
Deriva la classe CoordinatorClient dalla classe base PeerClient per avviare il contatto del Coordinator di un suo g-nodo e richiederne i servizi.
Classi e interfacce
La mappa delle posizioni libere/occupate ai vari livelli è un oggetto di cui il modulo conosce l'interfaccia ICoordinatorMap. Tramite essa il modulo può:
Leggere il numero l dei livelli della topologia (metodo 'i_coordinator_map_get_levels').
Leggere la gsize di ogni livello i da 0 a l - 1 (metodo 'i_coordinator_map_get_gsize').
- Precisiamo il significato di questo indice, restando coerenti con quanto stabilito nella trattazione del modulo QSPN sebbene i due moduli siano indipendenti.
Per ogni i da 0 a l - 1, gsize(i) è il numero massimo di g-nodi di livello i in un g-nodo di livello i + 1.
Leggere l'anzianità del mio g-nodo ad ogni livello i da 0 a l - 1 (metodo 'i_coordinator_map_get_eldership').
L'anzianità di un g-nodo è un numero progressivo che viene assegnato al g-nodo. Nel confronto tra due g-nodi di pari livello i entrambi appartenenti allo stesso g-nodo di livello i + 1, un valore più alto significa che il g-nodo è arrivato dopo, cioè esso è più giovane.
Leggere la posizione del nodo, cioè la posizione del mio g-nodo ad ogni livello i da 0 a l - 1 (metodo 'i_coordinator_map_get_my_pos').
Leggere l'elenco delle posizioni libere in ogni livello i da 0 a l - 1 (metodo 'i_coordinator_map_get_free_pos').
Cioè le posizioni nel livello i che sono libere nel nostro g-nodo di livello i + 1. Questa informazione è quella che si basa sulla mappa del nodo corrente, senza contattare il Coordinator attuale che ha la conoscenza autoritativa delle prenotazioni pendenti.
Il metodo get_neighbor_map restituisce una istanza di ICoordinatorNeighborMap. Da questa interfaccia si possono leggere:
levels: Il numero di livelli nella topologia.
gsizes[i]: La gsize per ogni livello, con i da 0 a levels - 1.
free_pos_count[i]: Il numero di posti liberi in ogni livello, con i da 0 a levels - 1.
Il metodo get_reservation restituisce una istanza di ICoordinatorReservation. Da questa interfaccia si possono leggere:
levels: Il numero di livelli nella topologia.
gsizes[i]: La gsize per ogni livello, con i da 0 a levels - 1.
La posizione pos e il livello lvl del g-nodo riservato.
elderships[i]: I valori di anzianità per ogni livello i da lvl fino a levels - 1, inclusi.
Per i livelli inferiori a lvl il nodo, che ha appena costituito un nuovo g-nodo di livello lvl, userà come anzianità il valore 0.