StefanoCimmino Implementazioneeanalisidiunprotocolloperlareplicazioneattiva IngegneriaInformatica Universit`adegliStudidiRoma“LaSapienza”Facolt`adiIngegneria

Universit` a degli Studi di Roma “La Sapienza”

Facolt` a di Ingegneria

Tesi di Laurea in

Ingegneria Informatica

Dicembre, 2002

Implementazione e analisi di un protocollo per la

replicazione attiva

Stefano Cimmino

Universit` a degli Studi di Roma “La Sapienza”

Facolt` a di Ingegneria

Tesi di Laurea in Ingegneria Informatica Sessione Autunnale – Dicembre, 2002

Implementazione e analisi di un protocollo per la

replicazione attiva

Stefano Cimmino

Relatore Prof. Roberto Baldoni . . . . Co-Relatore Ing. Carlo Marchetti

. . . .

Revisore Ing. Andrea Vitaletti . . . .

Viale Spagna, Cond. Sagittario 03100 Frosinone, ITALIA

e-mail: [email protected]

Indice

1 Introduzione 1

2 Il problema della replicazione 7

2.1 Modelli di sistema . . . 7

2.1.1 Sincronia . . . 8

2.1.2 Modelli di guasto . . . 8

2.2 Replicazione software . . . 10

2.2.1 Criteri di consistenza . . . 10

2.2.2 Tecniche di replicazione . . . 11

2.3 Comunicazioni di gruppo . . . 13

2.3.1 Servizi di group membership . . . 13

2.3.2 Servizi di multicast . . . 15

2.3.3 Servizi di state transfer . . . 17

2.4 Consenso e problemi di agreement . . . 18

2.4.1 Il problema del consenso . . . 18

2.4.2 Risolvere il consenso . . . 19

3 Replicazione attiva a tre livelli 23 3.1 Motivazioni . . . 24

3.1.1 Architetture a due livelli per la replicazione software . . . 24

3.1.2 Replicazione software nei sistemi a larga scala . . . 25

3.2 Una architettura a tre livelli per la replicazione software . . . 27

3.3 Replicazione attiva a tre livelli . . . . 30

3.3.1 Specifica . . . 30

3.3.2 Panoramica sull’architettura . . . 31

3.3.3 Modello di sistema . . . 33

3.3.4 Il Sequencer Service . . . 34

3.3.5 Il protocollo del middle-tier . . . 36

3.3.6 Discussione . . . 39 i

4 Il total order multicast nei group toolkit 41

4.1 Il total order multicast . . . 41

4.1.1 Specifiche alternative . . . 42

4.1.2 Algoritmi di total order . . . 46

4.2 I group toolkit . . . 49

4.2.1 Classificazione rispetto all’architettura . . . 50

4.2.2 Classificazione rispetto al total order multicast . . . 53

4.2.3 Analisi delle prestazioni . . . 55

4.2.4 Discussione . . . 60

5 Interoperable Replication Logic 63 5.1 Una panoramica su CORBA . . . 64

5.1.1 La Common Object Request Broker Architecture . . . 64

5.1.2 Fault Tolerant CORBA . . . 68

5.2 Panoramica sull’architettura di IRL . . . 70

5.3 Il prototipo di IRL . . . 73

5.3.1 Una interazione client/server in IRL . . . 74

5.3.2 Outgoing Request GateWay . . . 76

5.3.3 Object Group Handler . . . 78

5.3.4 Incoming Request GateWay . . . 82

5.4 Analisi delle prestazioni . . . 84

5.4.1 Piattaforma di test ed esperimenti preliminari . . . 84

5.4.2 Parametri degli esperimenti . . . 85

5.4.3 Prestazioni dell’ORGW e della replicazione stateless . . . . 85

5.4.4 Prestazioni della replicazione stateful . . . 86

5.4.5 Osservazioni rilevanti . . . 93

5.5 Discussione . . . 94

6 Conclusioni 97 6.1 Contributi . . . 97

6.2 Sviluppi futuri . . . 98

Elenco delle figure

2.1 La tecnica di replicazione attiva . . . 11

2.2 La tecnica di replicazione passiva . . . 12

2.3 Spiegazione del view synchronous multicast . . . 16

3.1 Una architettura a due livelli per la replicazione software . . . 25

3.2 Una architettura a tre livelli per la replicazione software. . . 28

3.3 Una architettura a tre livelli per la replicazione software attiva . . 32

3.4 Una esecuzione priva di guasti del protocollo per la replicazione attiva a tre livelli . . . 37

3.5 Una esecuzione in presenza di guasti del protocollo per la repli- cazione attiva a tre livelli . . . 38

4.1 Scenari che violano la propriet`a di Uniform Agreement . . . 43

4.2 Problemi dovuti ad un indebolimento della proriet`a di Order nella specifica del total order multicast . . . 44

4.3 Gerarchia delle specifiche per il total order multicast . . . 45

4.4 Varianti comuni degli algoritmi basati su sequencer . . . 47

4.5 Varianti degli algoritmi basati sul protocollo di Skeen . . . 49

4.6 Architettura dei group toolkit . . . 51

4.7 Schema di interazione usato nei test dei group toolkit . . . 56

4.8 Prestazioni dei group toolkit in funzione di R e C . . . 57

4.9 Prestazioni dei group toolkit in funzione di C per R=2 . . . 59

5.1 Componenti principali dell’architettura CORBA . . . 65

5.2 Operazioni one way e callback . . . 66

5.3 Client e Server Portable Request Interceptor . . . 67

5.4 L’architettura di IRL . . . 71

5.5 Un esempio di distribuzione dei componenti di IRL . . . 73

5.6 Una interazione client/server priva di guasti in IRL . . . 75

5.7 Confronto tra un client CORBA standard e un client IRL . . . 76

5.8 Architettura del componente Object Group Handler . . . 78 iii

5.9 Passi principali della computazione di una replica OGH . . . 80 5.10 Architettura interna di un membro di un object group . . . 83 5.11 Prestazioni della replicazione stateless (C=1, M=2) . . . 86 5.12 Prestazioni della replicazione stateful in funzione di M (C=1, H=2) 87 5.13 Prestazioni della replicazione stateful in funzione di H (C=1, M=2) 88 5.14 Latenza introdotta dal Sequencer in funzione di H (C=1, M=2) . 89 5.15 Prestazioni della replicazione stateful in funzione di C (M=2, H=2) 90 5.16 Latenza dovuta al Sequencer in funzione di C (M=2, H=2) . . . . 92

Elenco delle tabelle

2.1 Classi di failure detector . . . 21

4.1 Specifiche per il total order multicast . . . 45

4.2 Classificazione dei group toolkit rispetto alla loro architettura . . 53

4.3 Specifica del total order multicast supportata dai group toolkit . . 55

5.1 Replicazione dei componenti di IRL . . . 74

5.2 Prestazioni di una interazione client/server base . . . 85

5.3 Parametri degli esperimenti . . . 85

5.4 Prestazioni di IRL in funzione di M . . . 87

5.5 Prestazioni di IRL in funzione di H . . . 88

5.6 Tempo impiegato dal Sequencer in funzione di H . . . 89

5.7 Prestazioni di IRL in funzione di C (approccio primary) . . . 90

5.8 Prestazioni di IRL in funzione di C (approccio active) . . . 91

5.9 Latenza del Sequencer in funzione di C . . . 92

v

Capitolo 1

Introduzione

L’utilizzo di servizi automatizzati `e aumentato sensibilmente negli ultimi an- ni. Basti pensare per esempio ai servizi di commercio elettronico, ai servizi per transazioni bancarie, al controllo industriale, ecc. Data questa diffusione, si ri- tiene ormai inaccettabile che un servizio sia reso indisponibile a causa di un guasto. In particolare, qualit`a come affidabilit`a e disponibilit`a sono considerate fondamentali per qualsiasi sistema. L’affidabilit`a `e definita come il tempo medio tra due guasti consecutivi, mentre la disponibilit`a rappresenta la probabilit`a che, in un qualsiasi momento, il sistema sia funzionante. Esistono diverse tecniche che consentono di raggiungere tali qualit`a. Una di esse `e la tolleranza ai guasti, la quale, basandosi sull’assunzione che i guasti possono sempre verificarsi nonos- tante il tentativo di prevenirli, propone soluzioni che permettono la continuit`a del servizio anche in presenza di tali eventi indesiderati.

Tolleranza ai guasti tramite replicazione software. La replicazione soft- ware `e una delle possibili soluzioni per ottenere tolleranza ai guasti. L’idea `e quella di replicare i componenti software di un sistema, ossia creare diverse copie dello stesso componente, allo scopo di aumentarne il grado di affidabilit`a e disponi- bilit`a. Il modello di interazione considerato `e il modello client/server, secondo il quale un programma client, per usufruire di un determinato servizio, invia una richiesta verso una applicazione remota, il server, che implementa tale servizio. Il server si fa carico di processare la richiesta, eventualmente modificando il proprio stato interno, ed invia poi il corrispondente risultato al client. In questo contesto, per aumentare affidabilit`a e disponibilit`a, il servizio viene replicato, creando varie copie dell’applicazione server, chiamate repliche, le quali vengono distribuite su diversi host. Il sistema deve assicurare che lo stato di ciascuna replica rimanga consistente con quello delle altre, in modo da consentire al client di accedere ad una replica qualsiasi per usufruire del servizio. In particolare, si parla di consis-

1

tenza forte quando il sistema fornisce al client l’illusione di comunicare con una singola entit`a logica.

Tecniche di replicazione. Le tecniche di replicazione consentono di garantire consistenza tra le repliche di un servizio. Negli ultimi venti anni sono state proposte varie tecniche di replicazione che consentono di ottenere consistenza forte delle repliche, come per esempio la tecnica di replicazione attiva (chiamata anche approccio state-machine) [Lam78, Sch93], quella passiva (chiamata anche approccio primary-backup) [BSTM93], la semi-passiva [DSS98] e la semi-attiva [Pow91]. Le tecniche principali sono quella attiva e quella passiva.

• Replicazione attiva. Nella replicazione attiva, tutte le repliche effettuano le stesse operazioni nello stesso ordine, mantenendo perci`o identico il loro stato. Il vantaggio principale di questa tecnica di replicazione consiste nel basso tempo di risposta, anche in presenza di guasti. Tuttavia le repliche devono necessariamente essere deterministiche: il risultato di una richiesta deve dipendere solo dalla richiesta stessa e dallo stato corrente della replica che la processa. In altre parole, ci`o significa che la replica si comporta come una macchina a stati finiti deterministica. Questa condizione `e necessaria per fare in modo che tutte le repliche producano lo stesso risultato per una data richiesta.

• Replicazione passiva. Nella replicazione passiva, una particolare repli- ca (chiamata primary) riceve tutte le richieste dei client, definisce l’ordine della loro esecuzione e aggiorna le altre repliche (chiamate backup), per mantenere consistente il loro stato. In caso di guasto del primary, il pro- cessamento delle richieste si arresta fino all’elezione di un nuovo primary, che viene scelto tra le repliche backup. Per questa ragione, la replicazione passiva pu`o comportare un tempo di risposta pi`u basso in caso di guasti del primary. Tuttavia questa tecnica richiede una quantit`a minore di risorse di calcolo rispetto alla replicazione attiva e consente di avere repliche non- deterministiche, in quanto solo il primary processa le richieste, inviando i corrispondenti aggiornamenti dello stato alle repliche backup.

I group communication toolkit. L’implementazione delle tecniche di repli- cazione pone diverse difficolt`a, legate soprattutto alla necessit`a di mantenere la consistenza delle repliche. I group communication toolkit rappresentano un con- veniente strumento per risolvere questo tipo di problemi: utilizzando l’astrazione di gruppo, ossia un insieme di processi cooperanti, detti membri, essi forniscono un insieme di servizi e primitive di comunicazione che semplificano l’implemen- tazione delle tecniche di replicazione software. Per esempio, il servizio di group

3

membership permette a ciascun membro del gruppo di sapere l’attuale compo- sizione della vista (view ), ossia l’insieme dei membri attivi e partecipanti alla com- putazione, mentre varie primitive di comunicazione uno-a-molti (cio`e multicast) permettono ai membri di scambiarsi messaggi con varie garanzie di ordinamento e affidabilit`a. In particolare, la primitiva di total order multicast assicura che tutti i membri consegneranno lo stesso insieme di messaggi nello stesso ordine, e pu`o quindi essere utilizzata per implementare la replicazione attiva. Allo stesso modo, la replicazione passiva necessita di (i) un servizio di group membership, che permetta alle repliche backup di individuare il guasto del primary ed eleg- gerne uno nuovo, e (ii) una primitiva di view synchronous multicast, che assicura che un messaggio inviato all’interno di una vista verr`a consegnato nel contesto della stessa vista da tutti o da nessun membro, evitando quindi che un vecchio primary aggiorni erroneamente una replica backup dopo che un nuovo primary `e gi`a stato eletto.

Il problema del consenso. In generale, ogni tecnica di replicazione che deve assicurare consistenza forte delle repliche, richiede di risolvere un problema di agreement, cio`e di accordo, come il total order multicast o il view synchronous multicast. Si pu`o dimostrare (vedi [CT96, GS97b, GS01]) che risolvere il problema di ottenere un total order multicast o un view synchronous multicast, necessari per l’implementazione della replicazione attiva e passiva, rispettivamente, equiv- ale a risolvere il problema del consenso. Nel problema del consenso, ogni processo propone un valore e tutti i processi non guasti devono essere d’accordo nel decidere uno stesso valore, che deve essere scelto tra quelli proposti. Tuttavia il risultato di impossibilit`a, noto come “FLP”, stabilisce che se si considera un sistema in cui i processi possono guastarsi e in cui non si possono fare assunzioni sui tempi di (i) trasmissione dei messaggi scambiati tra diverse entit`a distribuite, e di (ii) es- ecuzione delle richieste, il problema del consenso non pu`o essere risolto [FLP85].

Ci`o significa che per poter implementare una qualsiasi tecnica di replicazione che richieda consistenza forte, le entit`a coinvolte nella soluzione del problema di agreement devono necessariamente essere distribuite in un sistema che presenti un qualche livello di sincronia, come ad esempio una LAN. In particolare, se le uniche entit`a presenti sono i client e le repliche del servizio, come accade nelle architetture a due livelli, non `e possibile distribuire entrambi su una rete WAN, come Internet, in cui i tempi di ritardo dei messaggi e di esecuzione delle richi- este sono finiti ma non predicibili. Esistono diverse soluzioni per la replicazione software che assumono un sistema asincrono, ma possono per`o essere utilizzate solo per applicazioni che richiedono minori garanzie di consistenza. Per esempio, i group toolkit basati su un servizio di group membership partizionabile consentono il partizionamento del gruppo e il progresso della computazione in ciascun sot-

togruppo, aumentando la disponibilit`a di varie applicazioni che non richiedono consistenza forte.

Architetture a tre livelli per la replicazione software. Le architetture a tre livelli per la replicazione software consentono di distribuire i client e le repliche anche su una WAN con basse garanzie di predicibilit`a riguardo i ritardi nella trasmissione e nel processamento dei messaggi. Ci`o `e reso possibile evitando che i client e le repliche partecipino ad algoritmi per la soluzione di problemi di agreement. In una architettura a tre livelli per la replicazione software, i client e le repliche sono disaccoppiati, cio`e non interagiscono direttamente tra di loro, ma piuttosto comunicano attraverso uno strato software intermedio (middle-tier ) altamente affidabile e tollerante ai guasti. In particolare il middle-tier riceve le richieste dei client (client-tier ) e le inoltra verso le repliche (end-tier ), insieme ad altre informazioni che consentono a ciascuna replica di eseguire le richieste indipendentemente dalle altre repliche, ma in modo tale da garantire consistenza forte. Le repliche inviano poi il risultato al middle-tier, che lo inoltra verso i client. In questo modo, n´e i client n´e le repliche prendono parte ad algoritmi per la soluzione di problemi di agreement. Al contrario, `e il middle-tier a risolvere tali problemi, per esempio stabilendo un ordine totale sulle richieste, nell’ambito di una tecnica di replicazione attiva, oppure definendo il primary tra le repliche, nell’ambito di una tecnica di replicazione passiva. Ci`o significa che solamente il middle-tier deve quindi essere distribuito in un sistema con qualche livello di sincronia, mentre invece i client e le repliche possono essere distribuiti anche in sistemi asincroni, come Internet, preservando comunque le garanzie di consistenza forte.

Contributo. Il contributo di questa tesi consiste (i) nell’aver effettuato una classificazione ed una valutazione delle prestazioni di alcuni tra i group toolkit attualmente disponibili, e (ii) nell’aver utilizzato il pi`u adatto di tali group toolkit per la realizzazione di un prototipo di una infrastruttura software per la tolleran- za ai guasti denominata Interoperable Replication Logic (IRL), che adotta una architettura a tre livelli per la replicazione software.

Pi`u in dettaglio, i group toolkit sono stati classificati rispetto alle caratter- istiche architetturali e al servizio di total order multicast offerto, su cui si `e poi basata l’analisi delle loro prestazioni. Inoltre `e stato definito il design di alcu- ni componenti di IRL, la cui implementazione ha poi consentito di esaminare, tramite una accurata analisi prestazionale, le caratteristiche del protocollo per la replicazione attiva a tre livelli adottato dal prototipo.

5

Organizzazione della tesi. La tesi `e strutturata come segue. Il Capitolo 2 introduce i concetti generali usati nel seguito della dissertazione. Il Capitolo 3 mo- tiva e introduce le architetture a tre livelli per la replicazione software, illustrando in particolare un protocollo per la replicazione attiva a tre livelli. Il Capitolo 4 tratta il problema del total order multicast, e fornisce una classificazione rispetto a tale servizio di alcuni tra i group toolkit attualmente disponibili, sui quali viene eseguita una analisi delle prestazioni. Il Capitolo 5 descrive una infrastruttura per la tolleranza ai guasti, chiamata Interoperable Replication Logic, che adotta una architettura a tre livelli per la replicazione software. In particolare viene illustrato il design del prototipo attuale, del quale viene riportata una accurata analisi delle prestazioni. Infine il Capitolo 6 conclude la dissertazione, mettendo in luce i principali risultati del lavoro svolto.

Capitolo 2

Il problema della replicazione

Negli ultimi anni c’`e stata una notevole diffusione di servizi “on-line”. Diversi settori, come la finanza, le telecomunicazioni, booking-reservation ecc, forniscono servizi attraverso Internet, ai quali accedono un numero sempre crescente di client.

Ci`o ovviamente comporta un aumento dei requisiti di alta disponibilit`a e affid- abilit`a di tali servizi. Una soluzione per raggiungere questi obiettivi consiste nello sviluppare software su hardware replicato tollerante ai guasti. Sebbene questa soluzione sia adatta per alcune classi di applicazioni e sia stata perseguita con successo da alcune compagnie come Tandem e Stratus, fattori economici hanno spinto a cercare una soluzione meno costosa basata sul software. L’idea `e quella di creare pi`u copie del servizio, chiamate repliche, distribuite su diversi host. Il sistema deve assicurare che lo stato delle repliche rimanga consistente, in modo da consentire al client di accedere ad una replica qualsiasi per ottenere una risposta.

Questo capitolo introduce vari concetti legati al problema della replicazione software. In particolare, la Sezione 2.1 introduce i modelli di sistema per i sis- temi distribuiti e i modelli di guasto. La Sezione 2.2 tratta il problema della replicazione, descrivendo i criteri di consistenza e le due tecniche principali per la replicazione software, ossia quella attiva e quella passiva. La Sezione 2.3 descrive alcuni servizi utili per la replicazione, offerti dai sistemi per la comunicazione di gruppo (i group toolkit). Infine la Sezione 2.4 tratta il problema del consenso e la sua relazione con i problemi di agreement, legati alla replicazione software.

2.1 Modelli di sistema

Un sistema distribuito basato su scambio di messaggi `e definito come un insieme finito di processi Π = {p1. . . pn}. I processi possono comunicare inviando e ricevendo messaggi attraverso dei canali di comunicazione (o link). I processi e

7

i canali possono essere modellati rispetto (i) alle “garanzie di sincronia” che essi forniscono e (ii) ai tipi di guasto che possono essere osservati nel sistema.

2.1.1 Sincronia

La sincronia di un modello di sistema distribuito `e espressa in termini di assun- zioni temporali (o assunzioni di sincronia) che caratterizzano il comportamento dei processi e dei canali rispetto al tempo da essi impiegato per completare i loro compiti.

In un sistema sincrono le assunzioni temporali definiscono un limite massimo noto sia sul tempo impiegato da un processo per completare un proprio compito, sia sul ritardo di trasmissione dei messaggi. Si assume che il sistema soddisfi sempre questi vincoli.

Al contrario, in un sistema asincrono non esiste alcun limite noto (e di con- seguenza nessuna assunzione temporale) sul tempo impiegato dai processi e dai canali per effettuare le proprie azioni. Si assume solo che il sistema alla fine completer`a i compiti che sono stati richiesti.

I modelli di sistema sincrono e asincrono rappresentano i due estremi di una collezione di modelli, che possono essere ottenuti indebolendo le assunzioni tem- porali di un modello di sistema sincrono. Questi sistemi vengono chiamati parzial- mente sincroni. Per esempio, `e possibile assumere che esistano dei limiti massimi non noti sulle velocit`a relative dei processori e sul tempo di trasmissione dei mes- saggi, che valgono in ogni istante, oppure che questi limiti alla fine saranno per sempre validi. I sistemi parzialmente sincroni sono particolarmente adatti per la soluzione di problemi che non possono essere risolti nei sistemi asincroni. Noti- amo inoltre che molti approcci pratici di solito assumono un sistema parzialmente sincrono nel quale la maggior parte dei messaggi verosimilmente viene trasmessa entro una durata δ nota, e la maggior parte dei processi verosimilmente completa il proprio compito entro un tempo τ noto [CMA97, FC99a, FC99b]. In questi sistemi, i processi e i canali alternano periodi di stabilit`a, cio`e periodi durante i quali i processi e i canali si comportano in accordo ai vincoli temporali, e periodi di instabilit`a, cio`e periodi in cui i vincoli temporali non sono rispettati da qualche processo o canale.

2.1.2 Modelli di guasto

In generale, sia i processi che i canali di un sistema distribuito possono esibire guasti, cio`e possono iniziare ad avere un comportamento non conforme alla loro specifica.

2.1. MODELLI DI SISTEMA 9

Un processo si dice guasto se il suo comportamento si discosta da quello prescritto dall’algoritmo che sta eseguendo; altrimenti si dice corretto. Un modello di guasto specifica il modo in cui un processo guasto si pu`o discostare dal proprio algoritmo. I modelli di guasto sono i seguenti [HT93]:

• Crash: un processo guasto smette per sempre di funzionare, cio`e termina l’esecuzione di ogni attivit`a e in particolare smette di inviare e ricevere messaggi;

• Send omission: un processo guasto termina prematuramente, oppure omet- te occasionalmente di inviare messaggi che era supposto inviare;

• Receive omission: un processo guasto termina prematuramente, oppure omette occasionalmente di ricevere messaggi che gli sono stati inviati;

• General omission: un processo guasto termina prematuramente, oppure omette occasionalmente di inviare e ricevere messaggi;

• Arbitrary (detto anche Byzantine o malicious): un processo guasto pu`o esi- bire un comportamento arbitrario, per esempio pu`o inviare messaggi caotici agli altri processi;

• Arbitrary con message authentication: un processo guasto pu`o esibire un comportamento arbitrario, ma `e disponibile un meccanismo di autenti- cazione dei messaggi (per esempio la firma digitale). Questo consente ai pro- cessi corretti di validare le asserzioni di altri processi riguardo alla attuale ricezione di messaggi inviati da processi corretti.

I modelli di guasto che vanno dal modello crash al modello general omission vengono comunemente chiamati modelli di guasto benigni. Inoltre i processi di un sistema sincrono possono essere soggetti anche al seguente modello di guasto:

• Timing failure: un processo guasto si discosta dalla propria specifica tem- porale, per esempio eccedendo il tempo massimo predefinito per eseguire uno step (nel qual caso si ha una performance failure).

Allo stesso modo, i canali di comunicazione possono esibire guasti, per esempio scartando ogni messaggio (guasti di tipo crash), oppure omettendo il trasporto di qualche messaggio (guasti di tipo omission), o comportandosi maliziosamente alterando il contenuto di qualche messaggio (guasti di tipo arbitrary).

2.2 Replicazione software

L’idea alla base della replicazione software `e quella di mettere in esecuzione di- verse repliche di un dato servizio in processi differenti di un sistema distribuito, consentendo a un processo client di accedere ad ognuna di esse, aumentando cos`ı la probabilit`a di ottenere una risposta. Un servizio pu`o mantenere uno stato interno (servizio stateful) o meno (servizio stateless). Nell’ultimo caso il risul- tato di una richiesta dipende solo dal contenuto della richiesta stessa, per cui per incrementare la disponibilit`a del servizio `e sufficiente consentire al client di accedere al pi`u elevato numero possibile di repliche. Nel caso pi`u generale, cio`e quando si ha un servizio stateful, nasce il problema di mantenere la consistenza delle repliche.

2.2.1 Criteri di consistenza

Mantenere la consistenza tra un insieme di repliche di un dato servizio richiede di definire un criterio di consistenza. Un criterio di consistenza definisce il com- portamento di un insieme di processi interagenti attraverso oggetti concorrenti condivisi [HW90], per esempio definisce i risultati restituiti dalle repliche di un servizio a fronte di una richiesta di un client. Sono stati proposti diversi criteri di consistenza nella letteratura, come ad esempio la consistenza causale [AHN⁺94], la consistenza sequenziale [Lam79], la serializzabilit`a [BHG87], e la linearizzabilit`a [HW90]. Questi criteri possono essere suddivisi in forti e deboli. I criteri di con- sistenza forte consentono di fornire al client l’illusione di interagire con un servizio non replicato. Al contrario, i criteri di consistenza debole richiedono ai client di conoscere l’esatta semantica del servizio replicato, riducendo quindi la trasparen- za della replicazione del servizio. La consistenza sequenziale, la serializzabilit`a e la linearizzabilit`a sono criteri di consistenza forte¹. Nel seguito considereremo la linearizzabilit`a come nostro criterio di consistenza forte, essenzialmente per mo- tivi pratici. La linearizzabilit`a `e infatti pi`u facile da implementare rispetto agli altri criteri di consistenza.

Per essere in grado di progettare tecniche generiche di replicazione che assicuri- no consistenza forte, `e quindi necessario definire delle condizioni sufficienti che assicurino la linearizzabilit`a per un generico servizio stateful replicato. `E possibile mostrare che per assicurare linearizzabilit`a di un servizio replicato `e sufficiente che le repliche siano d’accordo sul loro stato interno quando viene restituito un

1Si pu`o dimostrare che assicurare linearizzabilit`a implica anche assicurare consistenza se- quenziale e causale, per cui la linearizzabilit`a `e un criterio pi`u forte degli altri due. Al contrario, la linearizzabilit`a e la serializzabilit`a sono difficili da confrontare a causa del loro diverso campo di applicazione [HW90, AW94].

2.2. REPLICAZIONE SOFTWARE 11

risultato per una richiesta di un client. Informalmente, ci`o si pu`o ottenere facendo in modo che le repliche aggiornino il loro stato in una maniera (i) ordinata e (ii) atomica. Atomicit`a significa che tutte o nessuna delle repliche corrette esegue un aggiornamento dello stato, mentre ordinamento significa che ciascuna replica esegue gli aggiornamenti del proprio stato nello stesso ordine prima di guastarsi.

Queste condizioni saranno formalizzate nel contesto della replicazione attiva nella Sezione 3.3.1.

2.2.2 Tecniche di replicazione

Negli ultimi venti anni sono state proposte diverse tecniche di replicazione in grado di assicurare consistenza forte delle repliche. Esempi sono la replicazione attiva (o approccio state-machine) [Lam78, Sch93], passiva (o primary-backup) [BSTM93], coordinator-cohort [BJRA85], semi-passiva [DSS98], e semi-attiva [Pow91].

Nel seguito descriveremo le tecniche di replicazione attiva e passiva, che sono quelle pi`u utilizzate.

Replicazione attiva. Nella replicazione attiva tutte le repliche eseguono lo stesso insieme di richieste nello stesso ordine prima di guastarsi. In particolare, ogni richiesta `e eseguita da ogni replica, la quale restituisce un risultato per essa (Figura 2.1). Per assicurare consistenza forte `e necessario che (i) ogni replica processi ciascuna richiesta dei client nello stesso ordine delle altre repliche prima di guastarsi, e che (ii) le repliche siano deterministiche. Il determinismo delle repliche assicura che le repliche abbiano uno stato identico dopo aver completato il processamento di una richiesta, senza richiedere ulteriori comunicazioni tra di esse.

servizio replicato

processamento deterministico client

replica

replica

replica

servizio replicato

processamento deterministico client

replica

replica

replica

Figura 2.1: La tecnica di replicazione attiva

Il vantaggio principale di questa tecnica di replicazione consiste nel basso tempo di risposta in caso di guasti. Inoltre la replicazione attiva permette di

tollerare guasti arbitrari. Infatti, se il servizio `e replicato da n repliche, e si assume che esistano almeno d<sup>n+1</sup><sub>2</sub> e repliche corrette, `e sufficiente che il client aspetti dⁿ⁺¹₂ e risposte identiche per tollerare guasti arbitrari. Lo svantaggio di questa tecnica riguarda invece la necessit`a di un numero elevato di risorse di calcolo, dal momento che tutte le repliche processano ogni richiesta. Inoltre pu`o essere utilizzata solo se le repliche sono deterministiche.

Replicazione passiva. Nella replicazione passiva (Figura 2.2) una particolare replica (chiamata primary) riceve tutte le richieste dei client e definisce l’ordine della loro esecuzione. In particolare, nel momento in cui riceve una richiesta di un client, il primary processa la richiesta, raggiungendo un nuovo stato interno, e successivamente invia dei messaggi di aggiornamento alle altre repliche (chiamate backup), per imporre la consistenza. `E facile vedere che se il primary `e corretto la replicazione passiva garantisce consistenza forte. Per preservare la consisten- za anche in presenza di guasti del primary, il primary stesso deve eseguire gli aggiornamenti assicurando atomicit`a, cio`e che nessuna o tutte le repliche back- up ricevano l’aggiornamento dello stato corrispondente al processamento di una richiesta di un client. Il primary deve inoltre restituire un risultato al client solo se tutte le repliche backup sono state aggiornate. In questo modo, nel caso in cui il primary si guasti, il nuovo primary pu`o evitare di eseguire una seconda volta la computazione relativa ad una richiesta, cosa che avrebbe condotto ad una vi- olazione della consistenza. Nel momento in cui il primary si guasta, le repliche backup devono eleggere un nuovo primary tra di esse. A questo scopo, le repliche backup devono monitorare il primary per individuarne i guasti. Inoltre, quando viene individuato un guasto del primary, si deve assicurare che una sola replica venga eletta nuovo primary. In altre parole, in ogni istante di tempo deve esistere al pi`u un primary.

client

replica primary

replica backup

servizio replicato replica

backup

aggiornamento atomico client

replica primary

replica backup

servizio replicato replica

backup

aggiornamento atomico

Figura 2.2: La tecnica di replicazione passiva

La necessit`a di eleggere un nuovo primary pu`o comportare un tempo di rispos- ta lento in caso di guasti del primary. Tuttavia, siccome solo il primary processa

2.3. COMUNICAZIONI DI GRUPPO 13

le richieste dei client e invia aggiornamenti alle repliche backup, la replicazione passiva richiede una quantit`a inferiore di risorse di calcolo rispetto alla repli- cazione attiva, e inoltre tollera repliche non-deterministiche. Infine, a differenza della replicazione attiva, la replicazione passiva non `e in grado di tollerare guasti arbitrari.

2.3 Comunicazioni di gruppo

Varie esperienze [KT91, Bir93, Pow96, GS97a, CKV01] hanno dimostrato che il paradigma delle comunicazioni di gruppo rappresenta un potente strumento per la implementazione di servizi replicati. La nozione alla base di questo paradig- ma `e quella di gruppo, cio`e una collezione di processi di un sistema distribuito (chiamati membri) che in qualche modo cooperano tra di loro. Grazie all’as- trazione di gruppo, un processo pu`o inviare un messaggio ad un gruppo, senza dover nominare esplicitamente tutti i membri che lo compongono.

Esistono due diversi tipi di gruppi: gruppi statici e gruppi dinamici. Un gruppo `e statico se l’insieme dei suoi membri (cio`e la membership) non cambia nel tempo. Ci`o implica che anche se un membro si guasta, da un punto di vista logico esso rimane sempre un membro del gruppo. In un gruppo dinamico invece, la membership evolve nel tempo, per esempio modificandosi a causa di guasti. Inoltre tipicamente i gruppi dinamici offrono la possibilit`a di aggregarsi al gruppo o di abbandonarlo, permettendo quindi di gestire dinamicamente l’insieme dei processi che prendono parte al gruppo stesso.

Un’altra distinzione riguarda i gruppi aperti e i gruppi chiusi. In un gruppo chiuso, solo i membri del gruppo possono inviare messaggi ad altri membri del gruppo, mentre invece in un gruppo aperto qualsiasi processo del sistema pu`o inviare messaggi ai membri del gruppo.

Nel seguito di questa sezione verranno brevemente descritti alcuni dei servizi pi`u importanti messi a disposizione dai sistemi per la comunicazione di gruppo (group communication toolkit). Per una descrizione pi`u formale di questi ed altri aspetti riguardanti i group toolkit si rimanda a [CKV01].

2.3.1 Servizi di group membership

Il servizio di group membership `e alla base dei sistemi di comunicazione di grup- po che supportano gruppi dinamici (detti anche view-oriented). Esso consente infatti di tenere traccia dei membri del gruppo, che sono rappresentati tramite una vista (view), cio`e una collezione univocamente identificata degli identificatori dei membri del gruppo. Una vista pu`o cambiare perch´e un processo si aggrega

al gruppo, o perch´e un membro abbandona il gruppo, o infine perch´e un membro

`e escluso dal gruppo. Nei primi due casi c’`e una richiesta esplicita del processo, mentre il terzo caso `e determinato dal servizio stesso, che si fa carico di moni- torare i membri per individuarne i guasti, e in tal caso escluderli dal gruppo. I membri ricevono notifica del cambiamento della membership tramite un evento di cambiamento di vista. Alla ricezione di tale evento, i membri installano una nuova vista.

Un servizio di membership pu`o essere partitionable oppure primary compo- nent:

Primary component membership service. In questo tipo di servizi, per es- empio [BvR93, MFSW95], gli identificatori delle viste installate da tutti i membri di un gruppo sono totalmente ordinate. In altre parole, tutti i membri di un gruppo installano la stessa sequenza di viste. Questo implica che tutti i membri devono essere d’accordo sulla composizione del gruppo per ciascun cambiamento di vista.

Partitionable membership service. In questo tipo di servizi, per esempio [ADKM92a, BDMS98, DMS95, MAMSA94, BDM01], gli identificatori delle viste installate dai processi di un gruppo sono parzialmente ordinati. In al- tre parole, i membri possono partizionarsi in sottogruppi (un sottogruppo per ogni partizione). Solo i membri dello stesso sottogruppo devono essere d’accordo sulla composizione del sottogruppo stesso.

Notiamo che anche in un servizio di group membership di tipo primary par- tition i membri possono partizionarsi, per esempio a causa di un partiziona- mento fisico della rete. Tuttavia, in questo tipo di servizi, solo un sottogrup- po, cio`e la partizione primaria, pu`o continuare la propria esecuzione, mentre i membri degli altri sottogruppi o si “suicidano” (come accade in Isis [BvR93]) oppure rimangono bloccati in attesa di una fusione delle partizioni (come ac- cade in Phoenix [MFSW95]). Notiamo inoltre che la necessit`a di imporre con- sistenza forte delle repliche richiede un servizio di group membership di tipo pri- mary component, poich´e consentire il progresso in due o pi`u sottogruppi pu`o causare la violazione delle propriet`a di ordinamento e atomicit`a. Di conseguen- za, le applicazioni che richiedono consistenza forte delle repliche (per esempio [ADMSM94, GS95, GS97a, Kem02]) comunemente assumono un servizio di tipo primary component. In particolare, un servizio di membership primary compo- nent pu`o essere utilizzato per implementare la replicazione passiva: per esempio se si assume che i membri siano ordinati all’interno di una vista in accordo ad una regola deterministica, le repliche possono eleggere un primary semplicemente scegliendo il primo membro che compare nella vista.

2.3. COMUNICAZIONI DI GRUPPO 15

2.3.2 Servizi di multicast

I group toolkit forniscono diversi servizi di multicast con differenti garanzie di af- fidabilit`a e ordinamento. Si va infatti dal semplice multicast non affidabile al mul- ticast affidabile con ordinamento causale e totale [HT93, BvR93, CKV01]. Nel se- guito ci concentreremo sulle primitive di total order multicast e view synchronous multicast.

View Synchronous multicast. Le comunicazioni di tipo “view synchronous”

sono state introdotte in Isis [BJ87, BvR93]. Considerando group toolkit view- oriented, un messaggio viene consegnato a un membro nel contesto di una vista.

L’idea alla base delle comunicazioni view synchronous `e quella di ordinare la consegna dei messaggi rispetto alla installazione di una vista. Rispetto a questa idea, sono state proposte diverse specifiche per il view synchronous multicast (o VScast). Tra di esse, la pi`u restrittiva richiede che un messaggio inviato usando un VScast sia ricevuto da tutti o nessuno dei membri nel contesto della vista in cui `e stato inviato [CKV01]. Questa propriet`a `e stata indicata in diversi modi, per esempio sending view delivery in [CKV01], view synchrony in [BDGS95, MS95]

e strong virtual synchrony in [FvR95]. La Figura 2.3 illustra alcuni scenari per spiegare questa definizione. Questi scenari mostrano un gruppo di tre processi p1, p2, p3, ciascuno dei quali ha ricevuto dal servizio di membership la vista vi = {p₁, p₂, p₃}. p₁invia poi un messaggio m al gruppo, tramite un VScast nel contesto della vista v_i. Successivamente il servizio di membership informa p₂ e p₃ che p₁ ha lasciato il gruppo², cosicch´e p2 e p3 installano una nuova vista vi+1= {p2, p3}.

Lo Scenario 1 soddisfa la definizione data di VScast, poich´e tutti i membri di v_i consegnano m nel contesto di v_i. Al contrario, p₂ consegna m nel contesto di vi+1 nello Scenario 2, mentre omette di ricevere m nello Scenario 3, per cui entrambi questi scenari non soddisfano la definizione. Infine, anche lo Scenario 4 non soddisfa la definizione, poich´e p₂ e p₃ consegnano m nel contesto di una vista diversa rispetto a quella in cui m era stato inviato. Notiamo che anche uno scenario in cui m non `e consegnato da nessun processo soddisfa la definizione.

Il view synchronous multicast garantisce atomicit`a per quanto riguarda la con- segna dei messaggi nel contesto di una vista. Questa propriet`a `e necessaria nella replicazione passiva per garantire atomicit`a nella consegna degli aggiornamenti inviati dal primary alle repliche backup, ossia per imporre consistenza forte.

Siccome il soddisfacimento della propriet`a di view synchrony richiede di bloc- care l’invio e la ricezione dei messaggi durante i cambiamenti di vista, diversi group toolkit implementano propriet`a pi`u deboli, come per esempio la same view delivery³ [CKV01], evitando di dover bloccare l’invio e la ricezione di messaggi e

2La ragione per cui p1 non fa pi`u parte del gruppo non `e influente in questi esempi.

gruppo p₁

p₂

p₃

v_i={p₁,p₂,p₃} v_i+1={p₂,p₃} m

gruppo p₁

p₂

p₃

v_i={p₁,p₂,p₃} v_i+1={p₂,p₃} m

(a) Scenario 1

gruppo p₁

p₂

p₃

v_i={p₁,p₂,p₃} v_i+1={p₂,p₃} m

gruppo p₁

p₂

p₃

v_i={p₁,p₂,p₃} v_i+1={p₂,p₃} m

(b) Scenario 2

gruppo p₁

p₂

p₃

v_i={p₁,p₂,p₃} v_i+1={p₂,p₃} m

gruppo p₁

p₂

p₃

v_i={p₁,p₂,p₃} v_i+1={p₂,p₃} m

(c) Scenario 3

gruppo p₁

p₂

p₃

v_i={p₁,p₂,p₃} v_i+1={p₂,p₃} m

gruppo p₁

p₂

p₃

v_i={p₁,p₂,p₃} v_i+1={p₂,p₃} m

(d) Scenario 4

Figura 2.3: Spiegazione del view synchronous multicast

ottenendo cos`ı prestazioni migliori. Tuttavia queste propriet`a non sono sufficienti a garantire consistenza forte delle repliche.

Total Order multicast. La propriet`a di view synchrony riguarda l’ordinamen- to dei messaggi rispetto agli eventi relativi alla installazione delle viste. Tuttavia essa non dice niente riguardo all’ordinamento dei messaggi consegnati ai processi nel contesto di una singola vista, o tra i membri di un gruppo statico. In questo contesto, diverse garanzie di ordinamento e affidabilit`a sono state proposte nella letteratura, per esempio il causal multicast e il total order (o atomic) multicast [BSS91, HT93]. Nel nostro caso ci concentriamo sul total order multicast. Ques- ta primitiva assicura che i messaggi saranno consegnati nello stesso ordine totale ai processi. Nel seguito indicheremo come Dest(m) l’insieme dei destinatari del messaggio m. La specifica del total order multicast viene data rispetto a quattro propriet`a: Validity, Integrity, Agreement e Order. Ciascuna di queste propriet`a, eccetto la Validity, pu`o essere considerata uniforme o meno, dove per uniforme si intende il fatto che la specifica considera tutti i processi, siano essi corretti o

3La propriet`a di same view delivery richiede che se due processi consegnano entrambi un messaggio m, lo fanno nella stessa vista v, che pu`o essere diversa dalla vista in cui il messaggio

`e stato inviato. Lo Scenario 4 in Figura 2.3 soddisfa questa propriet`a.

2.3. COMUNICAZIONI DI GRUPPO 17

meno. Questo implica varie alternative per la specifica del total order multicast.

Siccome considerare una propriet`a uniforme significa eliminare la possibilit`a che si possano verificare alcuni scenari che possono portare ad inconsistenze, una speci- fica che considera propriet`a uniformi `e pi`u forte rispetto ad una che considera propriet`a non uniformi. La specifica pi`u forte, che chiamiamo quindi strongest total order, `e la seguente:

Validity. Se un processo corretto esegue il multicast di un messaggio m, allora qualche processo corretto in Dest(m) alla fine consegner`a m;

Uniform Integrity. Per qualsiasi messaggio m, ogni processo p consegna m al massimo una volta, e solo se (i) m `e stato precedentemente inviato da qualche processo e (ii) p `e un processo in Dest(m);

Uniform Agreement. Se un processo consegna un messaggio m, allora tutti i processi corretti in Dest(m) alla fine consegneranno m;

Prefix Order. Sia h(p) la storia dei messaggi consegnati dal processo p, ossia la sequenza ordinata dei messaggi consegnati da p. Allora, per qualsiasi coppia di processi p e q, o h(p) `e un prefisso di h(q) o viceversa.

Notiamo che queste propriet`a, dovendo valere anche per processi non corretti, possono essere soddisfatte solo se si assumono modelli di guasto benigni per i processi, per esempio guasti di tipo crash.

Nel Capitolo 4 discuteremo alcune alternative pi`u deboli e vedremo come la specifica viene implementata nei group toolkit.

2.3.3 Servizi di state transfer

Un altro importante servizio offerto dai group toolkit `e lo state transfer. Questo servizio permette di trasferire lo stato di un membro ad un altro, ed `e particolar- mente utile quando un nuovo processo si aggrega al gruppo, e il suo stato deve essere allineato con quello dei membri gi`a esistenti. Lo state transfer pu`o essere bloccante o meno⁴. Durante uno state transfer bloccante, nessun messaggio `e inviato o ricevuto dai membri del gruppo, mentre durante uno state transfer non bloccante i membri possono inviare e consegnare messaggi. Questo pu`o com- portare una violazione della consistenza. Tuttavia in alcune applicazioni il fatto di sapere come evolve lo stato interno di una replica a fronte della consegna dei messaggi consente di utilizzare uno state transfer non bloccante, ottenendo un

4Lo state transfer bloccante e non-bloccante sono anche denotati sincrono e asincrono, rispettivamente [VB98].

miglioramento delle prestazioni.

Come detto in precedenza, l’uso dei group toolkit semplifica enormemente la realizzazione di applicazioni distribuite, come per esempio un servizio reso altamente affidabile tramite la replicazione software. Per questo motivo, il campo delle comunicazioni di gruppo `e stato oggetto di una intensa ricerca negli ultimi dieci anni. Questi sforzi hanno prodotto numerosi group toolkit, tra cui Isis [BvR93], Horus [vRBH94, vRBM96], Phoenix [MFSW95], Totem [AMMS⁺95, MMSA⁺95, MMSA⁺96], Transis [ADKM92b, DM96], Ensemble [Hay98], Spread [AS98], Jgroup [BDM01], solo per nominarne alcuni.

2.4 Consenso e problemi di agreement

Nella sezione precedente sono state introdotte varie primitive e servizi legati al- l’implementazione delle tecniche di replicazione che impongono consistenza forte.

Ognuno di questi strumenti rappresenta un problema di agreement. In generale, imporre la consistenza forte delle repliche implica la soluzione di un problema di agreement. Si pu`o dimostrare che problemi di agreement come il servizio di group membership, il total order e il view synchronous multicast sono equivalenti al problema del consenso [CT96, GS97b, GS01]. L’equivalenza di due problemi A e B `e definita tramite il concetto di riduzione: un problema B si riduce ad un problema A se esiste un algoritmo R_AB che trasforma ogni algoritmo che risolve A in un algoritmo che risolve B. Due problemi A e B sono equivalenti se A si riduce a B e viceversa. Quindi se due problemi sono equivalenti, uno pu`o essere risolto se e solo se anche l’altro pu`o essere risolto. Ci`o implica che per risolvere il problema di ottenere un total order multicast, o un view synchronous multicast, o un servizio di group membership, `e necessario poter risolvere il problema del consenso.

2.4.1 Il problema del consenso

Il problema del consenso [PSL80, Sch85, CT96] `e definito su un insieme Π di processi. Ciascun processo p_i ∈ Π propone un valore v_i e tutti i processi corretti devono essere d’accordo su una singola decisione, scelta tra i valori proposti.

Pi`u formalmente, i processi hanno accesso a due primitive, cio`e propose(v) e decide(v), invocate da un processo per proporre un valore v e per decidere un valore v, rispettivamente. Quando un processo esegue propose(v), diciamo che esso propone il valore v. Allo stesso modo, quando un processo esegue decide(v), diciamo che esso decide il valore v. Il consenso `e definito dalle propriet`a seguenti.

2.4. CONSENSO E PROBLEMI DI AGREEMENT 19

Termination. Ogni processo corretto alla fine decide qualche valore.

Agreement. Non esistono due processi corretti che decidono diversamente.

Validity. Se un processo decide v, allora v era stato proposto da qualche pro- cesso.

La propriet`a di Agreement consente ai processi non corretti di decidere in modo diverso dai processi corretti. Ci`o potrebbe essere inaccettabile per alcune applicazioni, perch´e consente a un processo di propagare una decisione non corret- ta nel sistema prima di guastarsi. Questa situazione `e evitata da una specifica pi`u restrittiva, chiamata consenso uniforme, che si ottiene sostituendo alla propriet`a di Agreement la seguente propriet`a di Uniform Agreement.

Uniform Agreement. Non esistono due processi (corretti o meno) che decidono differentemente.

2.4.2 Risolvere il consenso

La soluzione ad un problema in un sistema distribuito dipende dal modello di sis- tema assunto, ossia dalle assunzioni di sincronia e dai modelli di guasto ammessi per processi e canali. Esistono diversi algoritmi che permettono di risolvere il problema del consenso in sistemi sincroni, assumendo vari modelli di guasto per processi e canali. Tuttavia nel nostro caso ci concentriamo sui sistemi asincroni.

Nel 1985 Fischer, Lynch e Paterson hanno dimostrato che non esiste un algo- ritmo deterministico in grado di risolvere il consenso in un sistema asincrono se anche un solo processo pu`o guastarsi. Questo risultato (noto come risultato di impossibilit`a “FLP”) pu`o essere giustificato intuitivamente notando che in un sistema asincrono non esiste alcuna nozione di tempo, per cui i processi non sono in grado di stabilire se un altro processo si `e guastato, o `e diventato “lento”, op- pure i canali sono diventati “lenti”. Il risultato FLP implica che non `e possibile implementare tecniche di replicazione con garanzie di consistenza forte in sistemi asincroni. Negli ultimi venti anni sono state proposte varie soluzioni che cercano di aggirare questa impossibilit`a, essenzialmente restringendo il modello di sistema asincrono tramite assunzioni addizionali. Queste assunzioni estendono i processi o i canali mediante o (i) randomizzazione, o (ii) failure detector, o (iii) ulteriori assunzioni temporali.

Tecniche di randomizzazione. Le tecniche di randomizzazione permettono di risolvere il consenso, sebbene vi sia una probabilit`a trascurabile di violare la

propriet`a di terminazione. Ci`o si ottiene dotando i processi di particolari oper- azioni che restituiscono un valore a caso in accordo ad una certa distribuzione di probabilit`a [Asp02, CD89]. Siccome siamo interessati ad algoritmi deterministici, non considereremo queste tecniche nel seguito.

I failure detector. Un failure detector `e un oracolo distribuito che fornisce suggerimenti (anche non corretti) a proposito dei processi che hanno subito dei guasti [CT96, CHT96]. Ogni processo p<sub>i</sub> del sistema ha accesso ad un modulo lo- cale F D<sub>i</sub>, che monitora gli altri processi nel sistema e mantiene l’insieme di quelli che sospetta essersi guastati. Questa informazione pu`o essere non corretta (ad esempio viene sospettato un processo non guasto) e pu`o essere inconsistente (ad esempio F D<sub>i</sub>sospetta al tempo t un processo p<sub>k</sub>mentre nello stesso istante di tem- po t un altro modulo F D<sub>j</sub> non sospetta p<sub>k</sub>). I failure detector sono caratterizzati in termini di due propriet`a, chiamate completeness e accuracy.

Completeness. La completezza di un failure detector `e relativa alla sua abilit`a di individuare i processi guasti. La completezza `e caratterizzata da una delle seguenti propriet`a.

Strong Completeness. Ogni processo guasto alla fine `e sospettato da tutti i processi corretti.

Weak Completeness. Ogni processo guasto alla fine `e sospettato da qual- che processo corretto.

Accuracy. L’accuratezza di un failure detector restringe i sospetti non corretti che esso pu`o fare. L’accuratezza `e caratterizzata da una delle seguenti propriet`a.

Strong Accuracy. Nessun processo `e sospettato prima che si guasti.

Weak Accuracy. Qualche processo corretto non `e mai sospettato.

Eventual Strong Accuracy. C’`e un tempo dopo il quale nessun processo corretto `e mai sospettato da alcun processo corretto.

Eventual Weak Accuracy. C’`e un tempo dopo il quale qualche processo corretto non `e mai sospettato da alcun processo corretto.

Le otto combinazioni delle propriet`a di completezza e accuratezza descritte sopra definiscono le otto classi di failure detector descritte nella Tabella 2.1.

Si pu`o dimostrare che, assumendo canali affidabili e un modello di tipo crash per i guasti dei processi, la classe ♦S `e la pi`u debole classe che rende possibile la soluzione del consenso in un sistema asincrono con una maggioranza di processi

2.4. CONSENSO E PROBLEMI DI AGREEMENT 21 accuracy

completeness Strong Weak Eventual Strong Eventual Weak Strong Perfect Strong Eventually Perfect Eventually Strong

P S ♦P ♦S

Weak Weak Eventually Weak

Q W ♦Q ♦W

Tabella 2.1: Classi di failure detector

corretti⁵ [CHT96]. Un algoritmo che risolve il consenso sotto queste assunzioni `e descritto in [CT96].

Assunzioni temporali aggiuntive. Il consenso pu`o essere risolto nonostante il risultato FLP introducendo assunzioni temporali aggiuntive al modello, in modo da escludere la possibilt`a di violare la propriet`a di terminazione. Alcuni modelli di sistema parzialmente sincrono sono stati introdotti in [DLS88]. In questi modelli di sistema si assume un limite superiore sul tempo di trasmissione dei messaggi, che per`o non `e noto ai processi, oppure si assume un limite noto ai processi, che per`o `e valido solo alla fine. Un altro esempio `e dato dal modello Timed Asynchronous introdotto in [CMA97, CF98, FC99b]. Questo modello assume che i processi abbiano accesso ad un clock locale, con drift limitati rispetto al tempo reale, in modo che i processi possano misurare il passare del tempo. Inoltre si assume un limite noto per quanto riguarda il tempo impiegato dai processi e dai canali per svolgere i loro compiti. Questi limiti sono validi solo durante i periodi di stabilit`a, mentre durante i periodi di instabilit`a il sistema si comporta come un sistema asincrono. Si assume che i periodi di stabilit`a abbiano una durata sufficiente a consentire la terminazione degli algoritmi.

Gli algoritmi progettati in questi sistemi fanno uso di timeout per individ- uare i guasti. Ovviamente ci`o richiede degli esperimenti preliminari sul sistema per poter stimare parametri quali il tempo di trasmissione dei messaggi, ritardi dovuti allo scheduling dei processi, ecc.

La differenza fondamentale tra un sistema asincrono aumentato con failure detector inaffidabili e i sistemi parzialmente sincroni risiede nel fatto che gli algo- ritmi basati su failure detector sono completamente liberi da qualsiasi nozione di tempo, che invece deve essere considerata per progettare algoritmi che risolvano il consenso in sistemi parzialmente sincroni. Tuttavia l’implementazione dei fail- ure detector `e comunque basata su timeout, per cui anche un sistema aumentato

5In realt`a questo risultato `e stato dimostrato per la classe ♦W. Tuttavia le classi ♦S e ♦W sono equivalenti [CT96].

con failure detector inaffidabili deve comportarsi come un sistema parzialmente sincrono per risolvere il consenso. In questo senso, possiamo dunque dire che la progettazione di algoritmi che risolvano il consenso e i problemi di agreement richiedono sincronia parziale per essere efficaci.

Capitolo 3

Replicazione attiva a tre livelli

Come descritto nel capitolo precedente, la necessit`a di imporre consistenza forte delle repliche richiede la soluzioni di problemi di agreement. Per esempio, nella replicazione attiva, c’`e bisogno di un agreement sull’ordine di esecuzione delle richieste e sull’atomicit`a di tale esecuzione. Nelle classiche architetture a due liv- elli, questi problemi sono risolti da protocolli piuttosto complessi che esibiscono vari problemi se utilizzati in sistemi asincroni. Questo capitolo introduce una architettura a tre livelli per la replicazione software attiva. Nel contesto della replicazione software, le architetture a tre livelli consentono di distribuire i client e le repliche di un servizio replicato in sistemi aperti a larga scala, ossia in sis- temi asincroni. Ci`o `e ottenuto grazie all’introduzione di un livello intermedio, il middle-tier, logicamente interposto tra i client e le repliche del servizio, con il compito di gestire la replicazione utilizzando dei protocolli di agreement a cui per`o non partecipano n´e i client n´e le repliche del servizio. In particolare, in una architettura a tre livelli per la replicazione attiva, il middle-tier ha il compito di definire un ordinamento totale sulle richieste inviate dai client, e di inoltrarle ver- so le repliche del servizio, insieme ad informazioni che consentiranno alle repliche stesse di eseguire le richieste nell’ordine stabilito.

Il resto del capitolo `e organizzato come segue. La Sezione 3.1 analizza i prob- lemi dei sistemi attuali per la replicazione software nell’ambito dei sistemi a larga scala, motivando l’approccio a tre livelli. La Sezione 3.2 introduce le architetture a tre livelli per la replicazione software, discutendo i loro vantaggi. Infine la Sezione 3.3 formalizza il problema della replicazione attiva e presenta una architettura a tre livelli specializzata per la gestione di questa tecnica di replicazione, descriven- do il modello di sistema adottato, un particolare servizio utilizzato per definire l’ordinamento sulle richieste dei client e il protocollo utilizzato per implementare la replicazione attiva.

23

3.1 Motivazioni

Nel capitolo precedente (Sezione 2.4) abbiamo visto come sia possibile risolvere il consenso considerando vari modelli di sistema. In particolare, l’introduzione di al- cune assunzioni aggiuntive consente di progettare algoritmi che in effetti risolvono il consenso. Tuttavia questi algoritmi non possono garantire anche efficienza: in particolare questi algoritmi risultano inefficienti durante i periodi di instabilit`a del sistema. Infatti, per salvaguardare tutte le propriet`a richieste dal consenso, questi algoritmi non assicurano il progresso della computazione durante i periodi di in- stabilit`a: dal punto di vista di un osservatore esterno essi si bloccano, in attesa che il sistema si stabilizzi per poter continuare la computazione. Ci`o significa che l’efficienza degli algoritmi che risolvono il consenso dipende dalla copertura delle assunzioni di sincronia parziale da parte della piattaforma sottostante. Questa copertura pu`o essere definita come il rapporto tra il tempo in cui il sistema `e stabile e quello in cui `e instabile. Una bassa copertura delle assunzioni, ossia una frequenza elevata di periodi di instabilit`a, fa decrescere drammaticamente l’effi- cienza di tali algoritmi. A causa della equivalenza tra il consenso e i problemi di agreement, ci`o si riflette anche su problemi come total order e view synchronous multicast, e quindi anche sulle tecniche di replicazione che cercano di imporre consistenza forte delle repliche.

Un esempio significativo in questo contesto si pu`o trovare in [Bir99], dove l’autore descrive come le prestazioni di un gruppo di processi siano influenzate negativamente dall’introduzione di fonti di asincronia nel sistema. In partico- lare, viene mostrato come l’instabilit`a del sistema crei dei falsi sospetti, causando l’esecuzione di un protocollo di agreement per decidere la nuova vista. Questo protocollo rallenta il sistema e in alcune situazioni pu`o provocare altri falsi sospet- ti, creando un effetto a cascata. La probabilit`a di incorrere in tali problemi pu`o essere ridotta usando dei timeout pi`u ampi per l’individuazione dei guasti, ma ci`o rallenta il sistema in caso di guasti reali. Questo esempio dimostra che in generale le applicazioni che devono risolvere problemi di agreement, come la replicazione software con consistenza forte, richiedono una elevata copertura delle assunzioni di sincronia parziale per preservare la disponibilit`a del servizio.

3.1.1 Architetture a due livelli per la replicazione software

A causa delle ragioni discusse sopra, molte delle soluzioni esistenti che provve- dono alta disponibilit`a tramite replicazione software con garanzie di consisten- za forte, per esempio [ADMSM94, FH02, FV97, Kei94, KA98, KD96, LM97, MMSN98], comunemente vengono distribuite su cluster di workstation, cio`e un

3.1. MOTIVAZIONI 25

insieme di workstation co-locate interconnesse da una rete locale (LAN), che pu`o essere configurata per assicurare un’alta copertura delle assunzioni di sincronia parziale, consentendo cos`ı di ottenere prestazioni eccellenti e alta disponibilit`a per il servizio replicato.

RL Replica

Processo replica

RL Replica

Processo replica

RL Replica

Processo replica

RL Client

Processo client

OS/Platform OS/Platform OS/Platform OS/Platform

Rete

Piattaforma

Client-tier End-tier

RL Replica

Processo replica

RL Replica

Processo replica

RL Replica

Processo replica

RL Client

Processo client

OS/Platform OS/Platform OS/Platform OS/Platform

Rete

Piattaforma

Client-tier End-tier

Figura 3.1: Una architettura a due livelli per la replicazione software Una generica architettura che cattura gli aspetti rilevanti di tali sistemi `e mostrata in Figura 3.1. L’architettura `e a due livelli, poich´e i client interagiscono direttamente con le repliche server. Come mostrato, ogni replica possiede uno strato sottostante (RL) che implementa la logica di replicazione, cio`e l’insieme dei protocolli, meccanismi e strutture dati necessarie per imporre la consisten- za delle repliche. Parte di questa logica influenza anche il client, per esempio per ritrasmettere le richieste verso un’altra replica dopo un guasto. La logica di replicazione impone l’agreement sulle informazioni replicate tramite l’implemen- tazione di qualche tecnica di replicazione: per esempio nel caso della replicazione attiva impone che tutti i messaggi siano consegnati nello stesso ordine utilizzando una primitiva di total order multicast (vedi Sezione 2.3). Quindi nelle architetture a due livelli le repliche sono strettamente accoppiate, e la logica di replicazione implementa protocolli di agreement che risultano danneggiati da una bassa coper- tura delle assunzioni di sincronia parziale. Questo rende difficile applicare queste architetture nei sistemi a larga scala, come descritto nella sezione seguente.

3.1.2 Replicazione software nei sistemi a larga scala

Ottenere una alta copertura delle assunzioni di sincronia parziale nei sistemi a larga scala `e piuttosto difficile. Infatti questi sistemi vengono distribuiti su reti chiamate wide area network (WAN) che soffrono dei seguenti problemi:

Latenza elevata. I ritardi nel trasporto dei messaggi tendono ad essere non predicibili e pi`u elevati nelle WAN rispetto alla relativa stabilit`a e predi- cibilit`a che si ottiene nelle LAN. Inoltre le WAN sono soggette a perdita di messaggi, a causa del fatto che un messaggio pu`o attraversare diverse reti inaffidabili prima di raggiungere la sua destinazione. Questo `e invece un evento estremamente raro per una LAN. La perdita di messaggi causa ritrasmissioni, introducendo ulteriori ritardi.

Instabilit`a. A causa dei guasti nei collegamenti e della congestione, lo stato dei canali di comunicazione pu`o variare frequentemente in una WAN. In presenza di tali eventi i ritardi di comunicazione possono aumentare di diversi ordini di grandezza.

Assenza di supporto per il multicast. Diversi protocolli per la soluzione dei problemi di agreement sono basati sull’uso di primitive di comunicazione uno-a-molti, che invece sono raramente supportate dalle WAN. Questo costringe gli implementatori a simulare un multicast tramite un insieme di unicast (comunicazioni punto-punto), che rallentano ulteriormente l’im- plementazione.

Inoltre i sistemi a larga scala sono generalmente sistemi aperti, cio`e sistemi in cui non `e possibile predire il numero di utenti che cercano concorrentemente di accedere ad un servizio offerto dal sistema. Questo pu`o comportare dei picchi di carico non predicibili, che saturano il sistema e rallentano i processi. Questi fattori rendono estremamente difficile stimare il comportamento del sistema, che quindi deve essere considerato asincrono. Ci`o implica una bassa copertura delle assunzioni di sincronia parziale. Di conseguenza, nei sistemi a larga scala l’uso di una architettura a due livelli per replicare un servizio con garanzie di consis- tenza forte pu`o comportare una bassa disponibilit`a del servizio, nonostante la replicazione.

Per questa ragione, le soluzioni esistenti al problema della replicazione soft- ware nei sistemi a larga scala rinunciano alle garanzie di consistenza forte. In genere questi approcci tendono a considerare l’intero sistema come asincrono, cio`e tale che non esiste alcuna regione in cui `e possibile ottenere una elevata coper- tura di qualche assunzione temporale. Tuttavia possiamo modellare un sistema asincrono a larga scala come il risultato dell’interconnessione di diversi sistemi, qualcuno dei quali fornisce elevata copertura delle assunzioni di sincronia parziale.

Ci`o permette di realizzare una architettura in cui solo un sottoinsieme dei processi richiede la copertura delle assunzioni di sincronia parziale, in modo che sia possi-