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
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 16.Affidabilità dei sistemi software distribuiti


Failures

Un fallimento, failure, è definito come l’evento in corrispondenza del quale il sistema cessa di fornire un servizio corretto.

Classificazione dei failures

In generale un sistema non fallisce sempre alla stessa maniera: le modalità di fallimento prendono il nome di failure modes ed implicano la non correttezza del servizio secondo diversi punti di vista.

Classificazione dei failures

  • dominio (domain)
  • rilevabilità (detectability)
  • percezione (consistency)
  • conseguenze (severity)

Classificazione dei failures in base al dominio


Classificazione dei failures in base alla rilevabilità

FAILURES

  • signaled failures
    • guasti rilevati a livello utente e opportunamente segnalati da un messaggio di errore;
  • unsignaled failures
    • guasti non rilevati a livello utente e di conseguenza non segnalati da opportuni messaggi di errore.

Classificazione dei failures in base alla percezione

FAILURES

  • consistent failures
    • guasti percepiti alla stessa maniera da tutti gli utenti del sistema;
  • inconsistent failures (Byzantine)
    • guasti che possono essere percepiti in maniera diversa dagli utenti del sistema.

Classificazione dei failures in base alla severità

FAILURES

  • catastrophic failures
    • guasti le cui conseguenze sono incommensurabilmente più grandi del beneficio fornito dal servizio in assenza di fallimento;
  • minor failures
    • guasti le cui conseguenze sono dello stesso ordine di grandezza del beneficio fornito dal servizio in assenza di fallimento.

Un sistema in cui si verificano esclusivamente fallimenti benigni (minor failures) è un sistema fail-safe.

Propagazione delle minacce

L’attivazione di un guasto provoca la transizione del sistema da uno stato di corretto funzionamento (correct behavior) ad uno stato improprio (error);

La rilevazione di un errore e le opportune operazioni di ripristino riportano il sistema ad operare in maniera corretta.

Un errore può degenerare in un fallimento mediante propagazione all’interfaccia utente.


Propagazione delle minacce


Dependability means

Esistono diversi approcci per incrementare il grado di dependability di un sistema: la scelta di una particolare tecnica è legata alla natura del sistema e al particolare attributo di dependability che si è interessati a massimizzare.

Fault Avoidance

	Le tecniche di fault avoidance sono orientate a minimizzare la probabilità di occorrenza dei fallimenti.

Le tecniche di fault avoidance sono orientate a minimizzare la probabilità di occorrenza dei fallimenti.


Fault tolerance

Le tecniche di fault tolerance mirano alla minimizzazione delle conseguenze dei guasti sul sistema e dunque ad evitare che essi possano degenerare in fallimenti (failure avoidance).

Un sistema fault tolerant è un sistema in grado di continuare ad essere operativo, pur se in condizioni degradate, nonostante l’occorrenza di guasti.

Fault tolerance


Fault tolerance

Rimozione dell’errore

  • Rollback: il sistema è ricondotto all’ultimo stato stabile in cui permaneva prima dell’errore;
  • Rollforward: il sistema, senza errori, è portato in un nuovo stato;
  • Compensation: utilizzata in sistemi ridondanti per il mascheramento dell’errore.

Fault tolerance

Fault handling

  • Diagnosis, individuazione dell’errore in termini spazio-temporali;
  • Isolation: esclusione del componente fallito dal resto del sistema;
  • Reconfiguration: ovvero la riassegnazione dei task in corso al momento dell’errore a componenti integri;
  • Reinizialization: il ripristino totale del normale comportamento del sistema mediante l’aggioramento delle informazioni modificate dalle operazioni precedenti.

Alle procedure di fault handling seguono operazioni di manutenzione correttiva, corrective maintainance, per riparare -offline- i componenti isolati perchè guasti.

Fault removal

   Le tecniche di fault removal mirano all’individuazione degli errori ed alla rimozione di eventuali guasti.

Le tecniche di fault removal mirano all'individuazione degli errori ed alla rimozione di eventuali guasti.


Fault forecasting

Ha l’obiettivo di stimare il numero corrente, la futura incidenza e le conseguenze dei fault.

Fault forecasting approaches

  • Deterministico, mira a comprendere quali siano gli effetti dei guasti sul malfunzionamento del sistema;
  • Probabilistico, mira a stimare i parametri di dependability.

Fault tolerance techniques


Replicazione

  • Miglioramento delle prestazioni
    • Il carico del sistema viene distribuito su più repliche
    • Un client può contattare la replica “più vicina”
  • Miglioramento dell’availability*
    • 1 – probability(all RM failed) = 1 – pn
  • Miglioramento della tolleranza ai guasti

*nel caso di fallimenti indipendenti delle repliche. L’isolamento fisico ed elettrico dei processori in un sistema distribuito assicura l’indipendenza dei fallimenti delle repliche.

Replicazione

Introduce nuove problematiche

  • Consistenza delle repliche. le repliche devono essere identiche in ogni istante (stesso stato). Si pensi a più utenti che condividono e/o modificano uno stesso oggetto replicato.
  • Determinismo dello stato delle repliche. Ogni replica
    • Deve ricevere le stesse richieste e nello stesso ordine temporale;
    • Deve evolvere in maniera deterministica. Due repliche che all’istante t sono nello stato S0 e ricevono una richiesta r, devono evolvere in un tempo finito verso lo stesso Stato S1.

Replication – modello architetturale

RM: mantiene le copie fisiche degli oggetti replicati.
FE: gestisce le richieste dei client e contatta gli RM
Failure model: Crashes only.

RM: mantiene le copie fisiche degli oggetti replicati. FE: gestisce le richieste dei client e contatta gli RM Failure model: Crashes only.


Esecuzione di una richiesta

  • L’espletamento di una richiesta ad un oggetto replicato avviene in 5 fasi;
  • Tipologie di richiesta
    • Read
    • Update without read;
  • Obiettivi
    • Agreement tra le repliche
    • Garanzie di consistenza tra le repliche.

Five phases in performing a request

  • FE invia una richiesta
    • FE può
      • Inviare la richiesta ad un singolo RM che provvederà poi ad inoltrarla agli altri RM;
      • Può utilizzare un protocollo di multicast (reliable e atomico) a tutte le altre repliche;
  • coordination
    • gli RMs decidono se soddisfare la richiesta e l’ordinamento temporale delle richieste (FIFO, causale o total ordering);
    • In caso di failure la richiesta potrà non essere eseguita.

Five phases in performing a request

  • execution
    • Gli RM tentano di eseguire la richiesta;
  • agreement
    • Gli RM devo raggiungere un agreement sulla risposta alla richiesta;
  • response
    • Uno o più RM eseguono la richiesta inviando la risposta al FE
      • per sistemi caratterizzati da high availability si restituisce la prima risposta al client;
      • Per tollerare byzantine faults, viene eseguita una procedura di voting.

The passive (primary-backup) model for fault tolerance

There is at any time a single primary RM and one or more secondary (backup, slave) RMs.

FEs communicate with the primary which executes the operation and sends copies of the updated data to the result to backups.

if the primary fails, one of the backups is promoted to act as the primary.


Passive (primary-backup) replication (discussion)

Se la replica primaria fallisce, il sistema è ancora consistente se una delle repliche diventa primaria

La replicazione passiva non è scalabile. La replica primaria costituisce un “bottleneck” dell’intero sistema.
Alcune strategie di miglioramento delle prestazioni consistono nel ridurre il carico della replica primaria inviando le richieste di read direttamente alle repliche di backup.

13.3.2. Active replication for fault tolerance

Ogni replica deve avere un comportamento deterministico.
Tutte partono dallo stesso stato ed eseguono le stesse richieste nello stesso ordine.all start in the same state and perform the same in the same order so that their state remains identical.
Un fallimento di un replica non ha alcun effetto sulle prestazioni del sistema poiché le altre continuano normalmente la loro esecuzione.
Gli FE possono implmentare strategie di aggiudicazione (voting), potendo tollerare fault bizantini.


Active replication – discussion

  • Vincoli:
    • RM devono essere deterministici. Lo schema funziona per repliche che possono essere ricondotte a macchine a stati (state machine)
  • È richiesto l’utilizzo di un protocollo di reliable e atomic multicast (non solo tutte le repliche devono ricevere gli stessi messaggi nello stesso ordine, ma i messaggi devono essere consegnati o a tutte le repliche oppure a nessuna)
    • In particolare si può utilizzare uno dei seguenti schemi
      • FIFO-ordered
      • Causally-ordered
      • Totally-ordered

Un esempio: I sistemi N_MR


Strategie di aggiudicazione


State machine [F.B. Schneider 1990]

Un metodo generale per l’implementazione di servizi tolleranti ai guasti nei sistemi distribuiti

Si basa sull’assunzione che ogni replica possa essere modellata come una state machine.
Una state machine consiste di un insieme di variabili di stato e di un insieme di comandi. Ogni comando è implementato da un programma deterministico. L’esecuzione di un comando è atomica rispetto agli altri.

State machine

Dalla definizione segue:
L’output di una state machine è completamente determinato dalla sequenza di richieste che essa processa in maniera indipendente dal tempo e da altre attività nel sistema.

In altre parole, il comportamento di una state machine è deterministico (e quindi indipendente dal carico del sistema e dal tempo di trasmissione delle richieste).

Failure Model

Si considerano due tipologie di fallimento di un componente del sistema distribuito:

  • Byzantine failures: il componente può esibire un comportamento arbitrario o malizioso, anche in accordo con altri componenti faulty del sistema;
  • Fail-stop failures: all’occorrenza di un fallimento il componente si ferma, ponendosi in uno stato “speciale” che permetterà di rilevare il fallimento a tutti gli altri componenti del sistema.

Sistemi distribuiti t Fault-tolerant

Nei sistemi distribuiti è difficile esprimere la capacità di un sistema di tollerare i guasti attraverso misure quali MTBF, MTTF ed altre misure statistiche [Sieworek and Swarz 1982].

Per tali sistemi si utilizza un modo alternativo. In particolare un sistema distribuito su un insieme di componenti si dirà t fault tolerant se esso soddisfa le sue specifiche anche nel caso in cui si verifichi il fallimento di t componenti in un dato intervallo di tempo.

Fault-tolerant State Machine

Un versione t fault tolerant di una state machine(sm) può essere realizzata mediante l’utilizzo della replicazione (si parla in questi casi quasi sempre di replicazione attiva);

Al fine di tollerare fallimenti Bizantini, una t fault tolerant sm dovrà essere costituita da almeno 2t+1 repliche (3t+1 nei sistemi parzialmente sincroni). A tal uopo si utilizzerà un algoritmo di voting di maggioranza;

Se i componenti esibiscono solamente fail-stop failure, allora saranno necessarie t+1 repliche.

State Machine Replication


Requisiti

Al fine di implementare un sm t fault tolerant bisogna assicurare il seguente requisito:

  • Replica Coordination: Tutte le repliche ricevono ed elaborano la stessa sequenza di richieste. Tale vincolo può essere decomposto in due requisiti:
    • Agreement: tutte le sm non faulty ricevono tutte le richieste;
    • Order: tutte le sm non faulty elaborano le richieste che ricevono nello stesso ordine (relativo).

Requisiti

L’Agreement governa il comportamento di un client nell’interazione con le repliche.

L’Order governa, invece, il comportamento delle repliche nel processare le richieste dei client.

Si noti che:

  • Il requisito di Agreement può essere “rilassato” per richieste di tipo “read-only” nel caso in cui siano considerato solo componenti fail-stop
  • Il requisito di Order può essere “rilassato” per le richieste che “commutano”. Due richieste r e r’ commutano in una sm se la sequenza degli output e lo stato finale della sm è indipendente dall’ordine in cui le richieste r e r’ verranno eseguite.

Agreement

L’agreement può essere realizzato da un qualunque protocollo che permette ad un Transmitter di inviare ad un insieme di Processor dei messaggi rispettando i seguenti vincoli:

  • Tutti i Processor non-faulty raggiungono l’accordo su uno stesso valore (della richiesta);
  • Se il Transmitter è non faulty, allora tutti i Processor utilizzano il suo valore come valore di riferimento.

Esempi

  • Reliable Multicast;
  • Protocolli di agreement.

Order

L’Order può essere assicurato assegnando un identificativo unico a tutte le richieste ed assicurando che le richieste vengano processate mediante lo ordine relativo agli ID. Inoltre bisogna assicurare che o tutte le repliche ricevono una richiesta o nessuna (atomicità).

Tecniche implementative

  • Utilizzando i Logical CLocks;
  • Sincronizzazione dei Clock Real Time;
  • Utilizzando Identificatori generati dalle repliche.

Discussione

Sebbene l’approccio delle state machine costituisca una pietra miliare nel campo della fault tolerance dei sistemi distribuiti esso è di difficile applicazione.
È applicabile solo a programmi (repliche) relativamente semplici che sono eseguiti in Sistemi Operativi “scariche” o comunque da caratterizzati da un comportamento deterministico.

Sfortunatamente Il comportamento puramente deterministico è difficilmente riscontrabile nella pratica. Sorgenti di non determinismo possono trovarsi nell’utilizzo di timer locali, system call di SO, funzioni specifiche di un processore, primitive di condivisione della memoria, multithreading… [Felber and Narasimhan 2003].

Discussione

Sebbene l’approccio delle state machine costituisca una pietra miliare nel campo della fault tolerance dei sistemi distribuiti esso è di difficile applicazione.
È applicabile solo a programmi (repliche) relativamente semplici che sono eseguiti in Sistemi Operativi “semplici” o comunque caratterizzati da un comportamento deterministico.

Sfortunatamente Il comportamento puramente deterministico è difficilmente riscontrabile nella pratica. Sorgenti di non determinismo possono trovarsi nell’utilizzo di timer locali, system call di SO, funzioni specifiche di un processore, primitive di condivisione della memoria, multithreading… [Felber and Narasimhan 2003].

Discussione

Il non determinismo è un problema inevitabile e “challenging” per la realizzazione di sistemi fault tolerant.

Per la replicazione attiva esso è di cruciale importanza al fine di mantenere consistente lo stato delle repliche.

La replicazione passiva è quella che spesso viene percepita come la soluzione da applicare al caso di applicazioni non deterministiche (ma ciò non è sempre possibile soprattutto se il comportamento dei componenti dipende da eventi esterni alle repliche).

  • 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