Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 19.Failure Detectors


Sommario

  • Failure Detector
  • Detector Inaffidabili e Affidabili
  • Note implementative

Failure Detector

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.

Failure Detector inaffidabili

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:

  • Unsuspected: il detector ha di recente avuto prova che il processo non è fallito.
    • Un messaggio è stato ricevuto di recente dal processo; tuttavia, ciò non esclude la possibilità che il processo sia fallito da allora.
  • Suspected: il detector ha indicazioni sul fatto che il processo potrebbe essere fallito.
    • Il processo non riceve messaggi per un tempo maggiore del massimo nominale; tuttavia, il processo potrebbe funzionare correttamente, ma non rispondere a causa di partizionamenti di rete o eccessivi rallentamenti nell’esecuzione.

Entrambi i risultati sono da considerarsi suggerimenti: potrebbero non accuratamente riflettere il reale stato del processo.

Failure Detector affidabili

Un failure detector affidabile è sempre accurato nel determinare il crash di un processo.

Può restituire i risultati:

  • Unsuspected: come nel caso di detector inaffidabili, rappresenta solo un suggerimento.
  • Failed: il detector determina con certezza che il processo è fallito. Il processo non eseguirà alcuna azione ulteriore (per definizione, un processo fallito per crash permane nel suo stato, senza eseguire altri passi di elaborazione).

Implementazione di un detector inaffidabile

Un failure detector inaffidabile può essere implementato in un sistema asincrono attraverso il seguente algoritmo (tecnica di heart beat):

  • Ogni processo p invia un messaggio “p is here” a ciascun altro processo nel sistema distribuito, ogni T secondi;
  • Il failure detector adotta una stima del massimo tempo di trasmissione di un messaggio, pari a D secondi;
  • Se il failure detector locale al processo q non riceve un “p is here” entro T+D secondi, allora riporta al processo q che il processo p è Suspected;
  • Se successivamente riceve un “p is here”, corregge la sua stima, riportando a q che il processo p è Unsuspected.

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.

Implementazione di un detector inaffidabile

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.

Implementazione di un detector affidabile

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.

Considerazioni

È 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.

Consenso con failure detectors

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:

  • essi fanno diventare p “fail-silent”, scartando tutti i messaggi che ricevono da esso.

In pratica, ciò equivale a trasformare un sistema asincrono in un sistema sincrono. La tecnica è ad esempio usata in ISIS.

Consenso con failure detectors

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:

  • Eventually weakly complete: ogni processo fallito è prima o poi reso Suspected in maniera permanente da qualche processo corretto;
  • Eventually weakly accurate: dopo un certo tempo, almeno un processo corretto non è mai considerato Suspected dagli altri processi corretti.

Consenso con failure detectors

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.

Failure Data Analysis (FDA)

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.

Failure Data Analysis (FDA)


Field Failure Data Analysis (FFDA)

L’analisi della dependability di un sistema avviene in quattro fasi successive:

  1. elaborazione dei dati;
  2. identificazione del modello e stima dei parametri;
  3. soluzione del modello;
  4. analisi del modello e misure;

FFDA: Data Processing

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);


FFDA: Data Processing

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.

FDDA case study: WINDOWS NT

OBIETTIVI:

  • Comprendere la natura dei fallimenti in sistemi Windows NT per incrementarne availability e reliability;
  • Caratterizzare il dependability behavoiur di
    1. un server Window NT;
    2. un dominio di rete;
  • Comprendere le dipendenze tra i fallimenti e le catene di propagazione;
  • Individuare i dependability bottleneck;

“Networked Windows NT System Field Failure Data Analysis”, R.K. Iyer et al., PRDC-99

FDDA case study: parametri di test

PARAMETRI DI TEST

Logging automatico gestito dall’Event Logging Subsystem di WinNT:

  • Application events;
  • System events;
  • Security events;

“Networked Windows NT System Field Failure Data Analysis”, R.K. Iyer et al., PRDC-99


FDDA case study: formato dei dati

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.,

FDDA case study: risultati

RISULTATI:

  • Gli errori Software/Hardware incidono maggiormente sul downtime del sistema (22% e 10%);
  • Il recovery da errori applicazione è più veloce del recoverry da errori del software di base;
  • Spesso è necessario più di un reboot per ripristinare il comportamento del sistema in seguito ad un fallimento;
  • L’availability media di un server supera il 99%;
  • La propagazione degli errori in un dominio è significativa;
  • Per il 58% dei reboot non è possibile individuare la causa dunque la strategia di logging va migliorata;
  • Il 24% del tempo di downtime è imputabile ad operazioni di manutenzione e configurazione del sistema.

FDDA case study: distribuzione TBF


I materiali di supporto della lezione

G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. XII §1.1 e §5.3), IV ed., 2005.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion