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.
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. Infatti non serve realizzare una memoria condivisa per il singolo nodo (l = 0). Invece è 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 è l'insieme dei valori che può assumere l.
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.
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.
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.
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. Quanto tempo?
Il primo nodo che costituisce una rete è subito pronto ad accettare richieste come Coordinator del g-nodo di qualsiasi livello, ed è anche subito uscito dalla fase di bootstrap.
Sia n 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 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. Ci saranno perciò dei ritardi per chi volesse accedere alla memoria condivisa del g-nodo di livello k, con k < l.
Riassumendo, il nodo n attende di uscire dalla fase di bootstrap; poi guarda il numero di nodi stimati presenti all'interno del g-nodo in cui ha fatto ingresso e sulla base di tale numero aspetta un altro tempo; dopo si dichiara pronto ad accettare richieste sul servizio Coordinator.
Quando un nodo x vuole fare una richiesta al Coordinator, 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.
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:
name = "reserve"
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.
Nella risposta al nodo richiedente, x segnala:
Il fingerprint di g e dei suoi g-nodi superiori.
La posizione assegnata all'interno di g.
La anzianità della posizione assegnata all'interno di g.
Se nessun posto è disponibile il nodo x lo segnala con una eccezione.
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.
A
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.
B
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.
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
Deliverables