|
Il coordinamento tra i Replica Manager è basato sull'algoritmo gossip descritto in [LLSG92].
Un'operazione di posting richiesta da un Client ad un Front End e propagata da quest'ultimo ad uno o più Replica Manager ha una semantica di tipo exactly-once. In altre parole, per un Client, o l'operazione non è andata a buon fine, e di questo viene avvisato in modo esplicito, oppure il posting ha avuto successo e nel bulletin board deve essere presente una sola copia del messaggio pubblicato. Un Replica Manager può ricevere più richieste di posting dello stesso messaggio poiché un Front End può inoltrare la richiesta a più Replica Manager e poiché durante il protocollo di coordinamento necessario per allineare le copie attive di bulletin board, avviene lo scambio dei messaggi che ogni Replica Manager ha pubblicato per conto di un Front End. Per evitare la duplicazione dei messaggi pubblicati ed ottenere una semantica exactly-once, i Front End associano ad ogni richiesta di posting un identificatore che la rende globalmente unica. Tale identificatore è detto call identifier o cid.
Per garantire l'ordinamento causale tra i messaggi pubblicati, senza propagare immediatamente ogni modifica dello stato del bulletin board di un Replica Manager a tutti gli altri, è necessario tenere traccia della "visione" che ogni Client ha del bulletin board. Associando questa informazione ad ogni operazione che un Client richiede, ogni Replica Manager può decidere localmente se può soddisfare o no una richiesta in base al confronto tra il suo stato e la visione che ne ha il Client. Nel caso il Client abbia una visione meno aggiornata, il Replica Manager può soddisfare tranquillamente la richiesta senza violare nessun vincolo di causalità. Nel caso, invece, il Client abbia una visione più aggiornata perché, ad esempio, ha comunicato con diversi Replica Manager, il Replica Manager cui è richiesta un'operazione, non può eseguirla se non dopo aver portato il suo stato ad essere aggiornato tanto quanto quello percepito dal Client. L'aggiornamento del Replica Manager deve poi avvenire rispettando i vincoli di causalità.
E’ necessario quindi un sistema compatto ed efficiente per rappresentare la "visione" dello stato del bulletin board: una struttura adatta allo scopo è il multipart timestamp (o vector timestamp). Un multipart timestamp t è un vettore t = <t1,…,tn> di dimensione n pari al numero di Replica Manager presenti nel sistema. Ogni elemento tk del vettore è un contatore intero non negativo che rappresenta il numero di eventi significativi riflessi nello stato del Replica Manager di indice k. Gli eventi significativi che causano l'incremento dei contatori dei multipart timestamp sono legati alle operazioni di posting di messaggi e saranno descritti in seguito.
Esiste una relazione di ordine parziale che lega i multipart timestamp:
t £ s º ( t1 £ s1 Ù … Ù tn £ sn )
Di due multipart timestamp si può effettuare il merge:
merge(u,v)k = max (u k,v k) " k = 1,2,…,n.
Per far sì che le operazioni richieste da un Client rispettino l'ordinamento causale, ogni Front End tiene traccia della visione dello stato del bulletin board in un multipart timestamp che invia insieme alle richieste dei Client ai Replica Manager. Una risposta di un Replica Manager ad una query è sempre accompagnata da un multipart timestamp che riflette lo stato del bulletin board. Una risposta ad un post è invece accompagnata da un multipart timestamp che identifica univocamente l'operazione di posting. Il Front End effettua il merge del multipart timestamp ottenuto in risposta con il suo, tenendo così traccia della visione dello stato del Replica Manager percepita dai suoi Client.
I Replica Manager ricevono dai Front End richieste di operazioni per conto dei Client (call messages) e scambiano anche informazioni con altri Replica Manager (gossip messages). Sulla base del multipart timestamp allegato ad ogni call message, ogni Replica Manager decide se eseguire immediatamente o no l'operazione che gli è richiesta. Le informazioni necessarie a questo fine sono mantenute nello stato di ogni Replica Manager.
Di seguito si dà una descrizione delle strutture logiche contenute nello stato di ogni Replica Manager.
prev £ val_ts. |
|
|
<rnode,ts,cid> in cui rnode è l'indice del Replica Manager che ha ricevuto l'ack, ts è il suo replica timestamp e cid è l'identificatore globale del posting cui si riferisce l'ack. Un cid può essere tolto da inval se è già stato ricevuto l'ack corrispondente e nel log non è presente nessuna operazione che si riferisce allo stesso cid. |
Vediamo ora più in dettaglio il meccanismo che consente ad ogni Replica Manager di servire le richieste rispettando i vincoli di causalità. Lo stato iniziale di ogni Replica Manager è tale che ogni multipart timestamp ha contatori nulli e ogni insieme è vuoto. Distinguiamo quattro casi: query, posting, ricezione di un ack per un posting già richiesto e ricezione di un gossip message.
Query: una richiesta di tipo query è sempre accompagnata da un multipart timestamp che riflette lo stato del bulletin board percepito dal Client. Detto val_ts il value timestamp del Replica Manager e prev il multipart timestamp allegato alla richiesta, la query può essere eseguita immediatamente se:
prev £ value_ts
cioè se la visione che il Client ha dello stato del bulletin board non è più aggiornata di quella del Replica Manager. La query non può essere eseguita fino a che la precedente condizione non è soddisfatta. Il Replica Manager può attendere un aggiornamento del proprio stato che avverrà attraverso i gossip messages o può sollecitarlo direttamente alla copia che secondo lui è più aggiornata. Ad esempio, se value_ts è (4,8,8) e prev è (4,7,9), il Replica Manager può inferire che non ha ancora ricevuto un posting che la copia di indice 3 ha invece già accettato e quindi può sollecitare l'allineamento del suo stato comunicando con il server di indice 3. Evidentemente, il Front End che aveva sottoposto una query con multipart timestamp (4,7,9) si era rivolto in precedenza ad un altro Replica Manager più aggiornato.
Una volta che la query è stata eseguita, il Replica Manager restituisce il risultato e il suo value multipart timestamp. Il Front End provvede ad effettuare il merge con il proprio multipart timestamp in modo da riflettere lo stato del bulletin board che i Client percepiscono.
Posting: una richiesta di posting, con multipart timestamp prev, è scartata se risulta che sia già stata servita, cioè se l'insieme inval contiene già il relativo cid oppure se l'insieme log contiene un record con lo stesso cid. Se la richiesta è accettata allora il Replica Manager di indice i:
|
|
|
|
|
Ack: l'invio di un ack da un Front End ad un Replica Manager di indice i non è accompagnato dal un multipart timestamp come per le altre operazioni, bensì dal cid che identifica il posting cui l'ack si riferisce. Il Replica manager incrementa di uno il contatore i-esimo nel suo replica timestamp, costruisce l'ack-record associato e lo aggiunge al log. Nessun risultato è rispedito al Front End.
Gossip message: i gossip message sono scambiati tra Replica Manager per l'allineamento dello stato del bulletin board. Ogni Replica Manager può decidere di effettuare lo scambio periodicamente scegliendo dinamicamente il partner oppure può sollecitare l'allineamento su necessità e scegliere la copia che, secondo lui, è più aggiornata. Ogni gossip message (m) contiene il multipart timestamp (m.ts) e l'insieme log (m.new) del mittente. La ricezione di un gossip message da un Replica Manager di indice j provoca lo svolgimento di tre attività:
1) effettua il merge del log remoto con il proprio poiché potrebbe contenere informazioni che non sono ancora note localmente:
|
2) aggiorna lo
stato locale sulla base delle nuove informazioni ricevute:
|
3) elimina dagli
insiemi log e inval le informazioni ritenute non più
indispensabili:
|