Failure detector
Un failure detector fornisce una stima del funzionamento di un processo, poiché non può essere preciso in un sistema asincrono, in cui i messaggi hanno tempi di consegna non definiti.
L'implementazione tipica di un failure detector prevede l'utilizzo di messaggi “heart beat” che periodicamente informano gli altri processi che compongono il sistema dello stato del processo che invia il messaggio. Ogni processo mantiene un timer per ciascuno degli altri processi, quando il timer scade per un processo, significa che non e' stato ricevuto il messaggio di “heart beat” da quel processo, che quindi e' considerato “suspected”, ossia probabilmente fallito.
Per aumentare la precisione della stima del failure detector si adopera un meccanismo di timeout adattativi, in base alle condizioni della rete di comunicazione. In questo modo si tenta di garantire che un processo non venga dichiarato suspected solo perché è la rete di comunicazione che sta subendo dei rallentamenti.
Un failure detector si compone dunque di due parti:
La realizzazione del failure detector si compone di vari passi. Il primo è certamente la definizione del sistema di comunicazione fra i processi. Si deve infatti definire non solo il protocollo di comunicazione, ma anche quali sono le assunzioni fatte sulla rete di comunicazione e i meccanismi di quest'ultima utilizzati. Nei prossimi paragrafi si analizzano queste tematiche.
Communication system
Come detto in precedenza, è necessario fare alcune assunzioni sulla rete di comunicazione sottostante, in particolare, si assume che la rete sia basata sullo stack protocollare TCP/IP. Chiarito questo fondamentale punto, rimane da specificare il protocollo di trasporto che verrà adoperato per trasportare i messaggi del failure detector.
La scelta ricade su UDP per i seguenti motivi:
- UDP è molto leggero in termini di risorse, il che è una caratteristica desiderabile in un sistema di supporto alle applicazioni come un failure detector;
- TCP include una serie di controlli non utili per le necessità di un failure detector. Ad esempio, TCP include tutta la dinamica legata al controllo di congestione, che non è affatto necessaria nel nostro caso.
Tuttavia, UDP presenta degli svantaggi, fra cui l'assenza di affidabilità nella consegna dei pacchetti e nessuna garanzia sulla replicazione degli stessi. Queste sono problematiche che devono essere dunque gestite direttamente dal protocollo del failure detector.
FDProtocol
Table of contents
- PT - Packet Type
- SN - Serial Number
- T - Timeout
- Reliability
Per supportare le operazioni di un
failure detector che adoperi timeout adattativi, è necessario definire almeno due messaggi per il
failure detector protocol (FDP):
Il primo messaggio, ALIVE, indica ad un processo ricevente che il processo mittente non è soggetto a failure. Il secondo messaggio è la risposta al primo, ed indica che il messaggio ALIVE è stato correttamente ricevuto.
Questo secondo messaggio si rende necessario poiché il protocollo di trasporto adoperato è UDP, che non garantisce la consegna affidabile.
Il formato dei pacchetti è il seguente:
Come si può vedere il fomato è molto semplice, i campi sono soltanto 3:
- PT: indica il tipo di messaggio, può valere ALIVE o ACK;
- SN: indica il numero di messaggio, si adopera per ragioni di affidabilità;
- T: è presente solo nel messaggio di tipo ALIVE ed indica ogni quanto il processo invia messaggi ALIVE.
PT - Packet Type
Il campo PT ha dimensione un byte e contiene soltanto il codice identificativo del tipo di messaggio. Attualmente sono definiti soltanto due tipi:
SN - Serial Number
Il campo SN è anch'esso lungo un byte, e contiene un numero di serie per identificare univocamente un pacchetto. Il SN è necessario per associare un messaggio di ALIVE con il corrispondente ACK.
Alla ricezione di un messaggio ALIVE, il processo ricevente genera un messaggio di risposta ACK contenente lo stesso SN del messaggio ALIVE ricevuto. Ogni messaggio ALIVE inviato deve avere il SN incrementato esattamente di una unità rispetto al SN del precedente messaggio ALIVE inviato.
La generazione dei SN comincia da 0x00, fino ad arrivare a 0xFF. Dopo aver raggiunto il SN 0xFF, i SN successivi verranno generati ripartendo da 0x00.
T - Timeout
Il campo T è impostato dal processo che invia il messaggio ALIVE per indicare ogni quanti ms invia un messaggio ALIVE. Questa informazione consente di calcolare il tempo di propagazione del messaggio sulla rete. Il processo ricevente controlla di quanto differisce il valore di T dal delay riscontrato fra due messaggi successivi ALIVE provenienti da quel processo. In questo modo ottiene l'esatto tempo di percorrenza del messaggio, in base al quale può adattare i suoi timeout.
Reliability
L'affidabilità nella consegna dei messaggi ALIVE è garantita attraverso un sistema di ACK e RETRY. Definiamo i seguenti termini:
- ACK-TIMEOUT: è lo scadere del tempo di attesa massimo per la ricezione di un ACK di un precedente messaggio ALIVE inviato;
- RETRY: è l'invio di un nuovo messaggio ALIVE a seguito di un ACK-TIMEOUT;
Il funzionamento del sistema è piuttosto semplice, quando viene inviato il messaggio ALIVE il processo fa partire un timer per controllare l'ACK-TIMEOUT. Se prima dell'occorrenza dell'ACK-TIMEOUT non è stato ricevuto l'ACK per il messaggio inviato, si procede ad un RETRY. Il messaggio ALIVE che costituisce il RETRY avrà il suo campo SN incrementato di una unità, poiché costituisce a tutti gli effetti un nuovo messaggio.
Sia la dimensione dell'ACK-TIMEOUT, che il numero di RETRY sono parametri configurabili in base alle condizioni della rete.
Nel seguito sono presentate alcune tipiche situazioni della dinamica del protocollo:
FD Design
In questo paragrafo si esaminano nel dettaglio il funzionamento del failure detector che intendiamo realizzare. Come abbiamo già precedentemente affermato, un FD (failure detector) deve avere due moduli per gestire da un lato l'invio del messaggio agli altri processi, dall'altro il controllo su quali processi sono sospetti di fallimento.
Liveness communicator
Il modulo che si occupa dell'invio del messaggio ALIVE è decisamente il più semplice, poiche' deve solo inviare il messaggio ALIVE ad intervalli di tempo regolari. Anche la gestione dell'affidabilita' della consegna del messaggio e' demandata al protocollo FDP, quindi questo modulo deve soltanto occuparsi di calcolare il tempo di invio del successivo messaggio ALIVE a partire dal momento in cui e' stato inviato l'ultimo messaggio ALIVE che ha ricevuto un ACK.
Quest'ultimo comportamento e' quello riportato nella seguente figura:
Processes monitor
Il modulo che si occupa del monitoring dei processi deve valutare se i messaggi di ALIVE giungono nei tempi giusti. In particolare, deve verificare che l'arrivo di due consecutivi messaggi di ALIVE avvenga in un tempo inferiore a quello del LIVENESS TIMEOUT, ossia, il tempo oltre il quale il processo si considera failed. Inoltre, il modulo deve adattare il LIVENESS TIMEOUT iniziale in base alle mutevole condizioni del delay della rete.
Per calcolare queste condizioni si adoperano le informazioni che i processi inviano assieme al messaggio ALIVE, ossia, l'intervallo di tempo di invio dei loro messaggi ALIVE.
Nelle seguenti figure si chiarisce il meccanismo adoperato:
Per ogni processo viene impostato come timeout il valore di timeout impostato nel messaggio di ALIVE inviato da quel processo, corretto di un termine D, calcolato come media degli ultimi 5 ritardi di trasmissione. Il valore di D e' sempre positivo, quando si ha una riduzione del tempo di trasmissione, quindi, il delay viene impostato a 0 per il computo della media.
La media viene in ogni caso depurata del valore minimo e di quello massimo, per garantire maggiore precisione.
Implementation
La realizzazione del failure detector segue l'impostazione indicata nei precedenti paragrafi, con la distinzione delle due parti: Liveness Communicator e Processes Monitor.
La precedente figura mostra l'organizzazione delle classi che realizzano il FD. La classe FailureDetector incapsula l'intero componente, offrendo l'interfaccia per accedere alle operazioni del FD. La classe si occupa anche di creare le istanze di LivenessCommunicator e ProcessesMonitor, che svolgono il ruolo specificato per gli omonimi componenti nel paragrafo sul design. Le operazioni per la comunicazione su rete sono demandate al FDPManager che realizza il protocollo FDP, adoperando i servizi del CommunicationChannel per accedere al canale di comunicazione fisico.
La gestione dei messaggi in arrivo e' fatta in multithreading, garantendo continua reattivita' al sistema.
FailureDetector class
La classe FailureDetector contiene diverse categorie di operazioni per offrire tutte le funzionalita' del FD in modo integrato:
- Initialization and disposure: sono operazioni che consentono di creare ed avviare il modulo FD;
- Configuration: permettono di impostare i parametri di configurazione che riguardano le operazioni legate al FD ed al canale di comunicazione, come ad esempio l'impostazione del liveness timeout, o dell'ack timeout;
- Monitoring: sono operazioni che consentono di ottenere informazioni sui processi monitorati e di registrare listeners per gli eventi generati dal FD;
- Process Adding and Removing: operazioni che permettono di aggiungere od eliminare processi dal monitoring.
Questa classe realizza l'intera istanziazione del modulo FD, occupandosi della corretta gestione delle risorse da questo utilizzate.
LivenessCommunicator class
La classe LivenessCommunicator si occupa di inviare un messaggio ALIVE secondo il periodo specificato tramite il liveness timeout. La classe realizza un thread che periodicamente si abilita, invia il messaggio ALIVE tramite le funzioni messe a disposizione dalla classe FDPManager, e si autosospende per un tampo pari al liveness timeout, prima di rieseguire l'operazione.
I processi cui inviare il messaggio sono prelevati dal ProcessRepository.
ProcessesMonitor class
La classe ProcessesMonitor controlla la liveness dei processi. Il ProcessMonitor e' in ascolto degli eventi generati dal FDPManager, in particolare, e' in ascolto della ricezione dei messaggi ALIVE.
Quando un messaggio ALIVE e' ricevuto per un processo p, si imposta il tempo entro il quale deve essere ricevuto un nuovo messaggio per quel processo, calcolandolo come somma di 4 addendi:
- timestamp di ricezione dell'ultimo ALIVE
- LivenessTimeout di p
- Eventuale tolleranza impostata nella configurazione del FD
- Fattore correttivo D, calcolato dalla classe AdaptiveDelayManager
Questa somma fornisce un valore temporale entro il quale il prossimo ALIVE deve essere ricevuto. I processi sono organizzati dal ProcessesMonitor in una coda di priorita' ordinata in base a tali valori temporali, dal piu' prossimo al piu' remoto.
Il ProcessesMonitor sospende la sua esecuzione quando non ha operazioni da compiere, impostando il ProcessMonitorTimer per riattivare l'esecuzione del processo di monitoring, quando si raggiunge il timestamp del primo processo nella coda di priorita'. L'esecuzione puo' essere ripresa prima dello scadere di questo timer, all'arrivo di un messaggio di ALIVE, che comporta l'aggiornamento del valore di timestamp di uno dei processi nella coda di priorita', con conseguente riorganizzazione della stessa e reimpostazione del ProcessMonitorTimer.
Puo' essere utile specificare che la riattivazione del ProcessesMonitor da parte del timer avviene solo quando c'e' un processo sospetto di fallimento. In questo caso, viene generato un evento di SUSPECTED, che raggiunge la classe FailureDetector e da qui viene propagato a tutti i listener che si sono registrati per la notifica di tale evento.
Se opportunamente configurato il ProcessesMonitor puo' provvedere ad inserire automaticamente nel ProcessRepository i processi da cui riceve messaggi ALIVE, qualora questi non fossero presenti. Tale procedura viene detta autodiscovery.
CommunicationChannel class
La classe CommunicationChannel fornisce le funzionalita' per accedere al canale di comunicazione e, quindi, per inviare e ricevere messaggi.
La classe realizza un thread costantemente in ascolto per nuovi messaggi in arrivo sulla Socket adoperata per la comunicazione. All'arrivo di un messaggio, viene generato un thread FDPMessageHandler che compie le seguenti operazioni:
- Riconosce la validita' del messaggio;
- Riconosce il tipo di messaggio FDP;
- Propaga l'evento di ricezione del messaggio identificato.
La gestione dei dettagli implementativi del protocollo, con il controllo degli ack timeout e' lasciata alla classe FDPManager che adopera le funzionalita' messe a disposizione dal CommunicationChannel.
