FT attraverso le comunicazioni di gruppo

Una tecnica utilizzata per il FT è la replicazione dei dati. Per mantenere la consistenza tra dati replicati, può essere usata la comunicazione di gruppo, nella quale ognuno degli n membri può mandare un messaggio all’intero gruppo. Sebbene esista l’hardware che supporta le comunicazioni broadcast, la maggior parte dei sistemi operativi distribuiti non supporta le comunicazioni di gruppo, la principale ragione è che un sistema di questo tipo che sia sicuro, è lento.

In questo capitolo vedremo in nuovo sistema molto efficiente, che ha ridotto il numero di messaggi inviati (per avere sicurezza che il messaggio sia arrivato a tutti, bastano in media 2 soli messaggi), la cui semantica delle primitive di sistema è semplice [6].

2. Comunicazioni di gruppo

Supponiamo di lavorare con un sistema distribuito che consiste di un insieme di nodi che possono comunicare tra loro mediante una LAN. Il protocollo descritto in seguito è compilato nel kernel. Ogni membro del gruppo, in ogni istante, può decidere di mandare un messaggio broadcast al proprio gruppo. É compito del kernel e del protocollo, di garantire un broadcast sicuro, perfino in caso di comunicazioni insicure, pacchetti persi, buffer pieni, e caduta dei nodi. Si assume che non appaiano guasti "bizantini" (cioè che un processo mandi messaggi contraddittori o spuri). Se la LAN in questione supporta il broadcast o il multicast, il protocollo utilizzerà questa opzione, ma essa non è essenziale per il corretto funzionamento del protocollo.

(per la descrizione delle primitive v. tabella)

Il protocollo di base funziona nel modo seguente.

Quando un membro chiama una SendToGroup per inviare un messaggio, manda il messaggio M al kernel e si blocca. Il kernel incapsula M in un ordinario messaggio point-to-point e lo manda ad un membro speciale chiamato sequencer. Questo sequenziatore contiene lo stesso codice degli altri membri, l’unica differenza è un flag che gli dice di processare il messaggio in modo differente.

Quando il sequencer riceve il messaggio contenente M, alloca il prossimo numero di sequenza s e invia in modo broadcast un pacchetto contenente M e s. Tutti i messaggi broadcast sono quindi inviati dal sequencer. Supponendo che non ci siano pacchetti persi, è facile vedere che se due membri vogliono accedere contemporaneamente al broadcast, uno verrà etichettato con un numero di sequenza e l’altro con quello successivo. Solo quando un broadcast è completato, si può partire con un altro. Il sequencer serve così ad ordinare globalmente tutti i messaggi.

Quando il kernel che ha inviato M, riceve lui stesso il messaggio dalla rete, riconosce che il broadcast è avvenuto con successo; a questo punto sblocca il membro che aveva chiamato la SendToGroup e gli ritorna il valore s.

Supponiamo che adesso un nodo abbia perso un pacchetto broadcast (per errore nelle comunicazioni o buffer pieno all’arrivo del pacchetto), quando arriva il pacchetto successivo, il kernel si accorge della discrepanza dei numeri (si aspettava s e gli è arrivato s+1) e capisce che si è perso un pacchetto.

A questo punto il kernel manda al sequencer un messaggio point-to-point richiedendo la copia del messaggio mancante (o dei messaggi, se sono più di uno). Il sequencer deve quindi mantenere in memoria (history buffer) una copia di tutti i messaggi broadcast inviati. A questo punto il sequencer invia al kernel i messaggi da lui richiesti con un messaggio point-to-point.

In pratica, esiste uno spazio finito nell’history buffer, e non si possono tenere i messaggi per sempre, così bisogna tenere traccia dei messaggi arrivati a destinazione con successo, così da poterli cancellare dal buffer. Esistono vari modi per avere questa informazione. Ad esempio ogni messaggio point-to-point al sequencer contiene, nel campo di intestazione, il numero di sequenza dell’ultimo messaggio broadcast ricevuto da chi ha inviato il messaggio (piggyback). Questa informazione è anche contenuta nei messaggi dal sequencer ad altri kernel. Così ogni kernel può tenere una tabella indicizzata del numero del membro, indicante che messaggi ha ricevuto quel nodo; in ogni momento il kernel può trovare quale è il numero più basso nella tabella e cancellare dal buffer quel messaggio.

Ovviamente se un nodo non invia messaggi per un certo periodo, le informazioni relative a quel nodo non saranno aggiornate; per fare arrivare questa informazione, il nodo che non ha inviato niente per un certo tempo t , manda al sequencer uno speciale pacchetto di acknowledge di tutti i pacchetti broadcast ricevuti. Inoltre può essere il sequencer stesso che richiede questa informazione, se è a corto di spazio.

4. Protocollo per fallimenti di un processatore

Il fallimento di un processatore è rilevato dal kernel, che cerca di raggiungere un altro kernel per mandare il messaggio. Se dopo un certo numero di tentativi, nessuno risponde, il membro in esecuzione su quel kernel, assume che sia morto (anche se il kernel potrebbe rispondere dopo una settimana).

Dopo che si sia rilevata la caduta di un membro, tutte le altre primitive di gruppo falliscono (si ritorna uno stato di errore). Ogni membro sopravvissuto, può invocare la ResetGroup, la quale cerca di costruire un nuovo gruppo, partendo da quello precedente. La ricostruzione avviene in due fasi.

Nella prima fase, invita tutti i membri sopravvissuti a creare un nuovo gruppo. Ogni membro risponde con il più alto numero di sequenza che lui ha ricevuto.

A questo punto si conosce chi è vivo e si elegge chi ha mandato il numero più alto come nuovo sequencer.

Nella seconda fase, il nuovo sequencer manda a tutti i membri l’informazione che lui è il nuovo sequencer. Ogni membro manda un acknowledge e si riparte con le operazioni consuete.

Questo però non garantisce che tutti i membri sopravvissuti ricevano tutti i messaggi che sono stati inviati. Bisogna così ispezionare le tabelle contenute nei kernel, e questo porta ad un piccolo overhead che diminuisce la performance.

5. Conclusioni

Questo protocollo può essere anche utilizzato per applicazioni parallele, databases, il che dà a questo protocollo un ulteriore merito, in aggiunta alla semplicità e alla potenza delle primitive.