Uno dei problemi che si riscontra nel progetto di un algoritmo distribuito è decidere quando un determinato processo fallisce (con riferimento a fallimenti per crash).
Un failure detector è un servizio in grado di stabilire se un processo è fallito.
Tale servizio è spesso implementato da un oggetto locale ad ogni processo (sullo stesso nodo di elaborazione).
L’oggetto (detto local failure detector) esegue un algoritmo di detection in congiunzione con le sue controparti eseguite localmente ad altri processi.
N.B.: su assume che i processi falliscano solo per crash, che abbiano canali di comunicazione affidabili, e che il fallimento di un processo non impedisca ad altri di comunicare.
La maggior parte dei failure detector sono inaffidabili.
Un failure detector inaffidabile può restituire uno dei due seguenti risultati sullo stato di fallimento di un processo:
Entrambi i risultati sono da considerarsi suggerimenti: potrebbero non accuratamente riflettere il reale stato del processo.
Un failure detector affidabile è sempre accurato nel determinare il crash di un processo.
Può restituire i risultati:
Un failure detector inaffidabile può essere implementato in un sistema asincrono attraverso il seguente algoritmo (tecnica di heart beat):
La bontà della risposta riportata ad un processo dipende dall’informazione disponibile localmente al processo. Un failure detector potrebbe dare suggerimenti errati a causa di condizioni di comunicazione estremamente variabili.
La scelta dei tempi T e D incide sulle prestazioni del detector.
Tempi brevi portano ad indicare spesso come Suspected processi che in realtà non sono falliti (falsi positivi), e richiedono molta banda di rete per i messaggi “p is here“.
Tempi lunghi portano ad indicare spesso come Unsuspected processi che in realtà sono falliti (falsi negativi).
Una soluzione pratica al problema prevede l’uso di valori adattativi per T e D, che riflettano le reali condizioni di rete.
Se un failure detector riceve un “p is here” in 20 secondi, invece del massimo ritardo atteso di 10 secondi, potrebbe correggere il suo ritardo massimo.
Il failure detector rimane inaffidabile, ma l’accuratezza aumenta.
L’algoritmo di detection presentato diventa affidabile in un sistema sincrono.
Nell’ipotesi di sistema sincrono, D diventa un limite superiore assoluto al ritardo di trasmissione di un messaggio, e non più una stima.
L’assenza di un messaggio “p is here” entro T+D permette al failure detector locale di dichiarare con certezza che p è fallito.
È lecito interrogarsi sull’effettiva utilità dei failure detector.
I failure detector inaffidabili possono generare falsi positivi (possono cioè essere inaccurati) e falsi negativi (possono essere incompleti).
I failure detector affidabili richiedono che il sistema sia sincrono (e pochi sistemi reali lo sono).
D’altra parte, i failure detector aiutano a comprendere la natura dei fallimenti in un sistema distribuito.
Qualsiasi sistema reale progettato per gestire i fallimenti deve poterli rilevare, anche se in maniera imperfetta.
Alcuni sistemi reali utilizzano detectors “affidabili da progetto” per raggiungere il consenso.
I processi si accordano sull’indicare un processo p come Failed se p non risponde per più di un certo tempo nominale massimo, anche in un sistema asincrono.
In realtà, p potrebbe non essere fallito, ma i rimanenti processi agiscono come se lo fosse:
In pratica, ciò equivale a trasformare un sistema asincrono in un sistema sincrono. La tecnica è ad esempio usata in ISIS.
Un altro approccio consiste nell’usare failure detectors inaffidabili.
Il consenso viene raggiunto consentendo ai processi Suspected di agire come corretti e partecipare alla decisione, anziché escluderli.
Chandra e Toueg hanno dimostrato che il consenso può essere raggiunto, anche in un sistema asincrono e usando detectors inaffidabili, se il numero di processi falliti non eccede N/2 e la comunicazione è affidabile.
Il più debole failure detector che può essere usato allo scopo è detto: eventually weak failure detector:
Chandra e Toueg hanno dimostrato che in un sistema asincrono non è possibile implementare un eventually weak failure detector solo attraverso scambio di messaggi.
Tuttavia un detector adattativo (con timeout variabili) va bene in molti casi pratici.
I mezzi per la dependability possono essere utilizzati efficacemente se si conosce il dependability behaviour del sistema.
La FDA attraverso l’esame di dati relativi ai fallimenti, costituisce uno strumento per la valutazione della dependability di un sistema fornendo informazioni utili sia alla formulazione di modelli di riferimento, sia alla progettazione di nuovi sistemi.
L’analisi della dependability di un sistema avviene in quattro fasi successive:
DATA PROCESSING:
Per consentire l’elaborazione dei dati è necessario che essi siano stati preventivamente raccolti mediante operazioni di logging (automatico o manuale) in una quantità tale da poter far sì che i risultati dell’analisi assumano rilevanza statistica→tempi di raccolta sufficientemente lunghi;
I dati raccolti vanno manipolati in quanto le informazioni riportate nei file di log sono spesso ridondanti e solo in parte utili all’analisi. Occorre selezionare i dati di interesse e uniformare il formato delle entry;
Per evitare che dati relativi al medesimo fallimento siano registrati sul log più di una volta occorre compattare le entry (coalescenza temporale o basata sul contenuto);
MODEL IDENTIFYING, MEASURE ACQUIRING:
Avendo a disposizione i dati nel formato e nella quantità opportuna, possibile cominciare ad individuare il modello del si stema e a valutarne i parametri. I modelli più utilizzati in questa fase sono le catene di Markov, e modelli statistici di correlazione error/failure.
MODEL SOLUTION:
In questa fase si procede, se necessario, alla soluzione del modello al fine di ottenere risultati precisi relativamente alla reliability e all’availability del sistema con l’ausilio di strumenti di modellazione e valutazione delle performance (ad esempio SHARPE).
ANALYSIS:
In questa fase si procede all’interpretazione dei risultati adottando metodi di analisi che possono significativamente variare a seconda del sistema e degli scopi dell’analisi.
OBIETTIVI:
“Networked Windows NT System Field Failure Data Analysis”, R.K. Iyer et al., PRDC-99
PARAMETRI DI TEST
Logging automatico gestito dall’Event Logging Subsystem di WinNT:
“Networked Windows NT System Field Failure Data Analysis”, R.K. Iyer et al., PRDC-99
Formato dei dati:
Field → Field Description
Server → Name of the server
Outage Start → Date and time an outage started
Boot time → Date and time the server rebooted. Reboot ends an outage, i.e. it is the Outage End time
Shutdown Type → Clean or dirty
Outage Reason → Cause of the outage/reboot
OpAssist Time → Time an operator made an annotation
OpAssist Tier1 → Operator’s primary reason for the reboot
OpAssist Tier2 → Operator’s secondary reason for the reboot.
Operator Comm → Operator’s freeform notes about the reboot.
“PRDC-99 Networked Windows NT System Field Failure Data Analysis”, R.K. Iyer et al.,
RISULTATI:
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software
G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. XII §1.1 e §5.3), IV ed., 2005.