Nella sezione precedente abbiamo messo in luce le limitazioni delle architetture a due livelli rispetto alla asincronia dei sistemi aperti a larga scala, notando che queste architetture comunemente indeboliscono le garanzie di consistenza per affrontare l’asincronia del sistema. Le architetture a tre livelli, invece, consentono di distribuire i client e le repliche su un sistema aperto a larga scala, garantendo nello stesso tempo consistenza forte.
Le idee alla base delle architetture a tre livelli sono le seguenti:
• i sistemi a larga scala possono essere verosimilmente considerati come
l’in-terconnessione di diversi sottosistemi a piccola scala tramite canali con latenza elevata e ritardi impredicibili;
• alcuni di questi sistemi consentono di ottenere elevata copertura dei requisiti
di sincronia parziale;
• di conseguenza, `e possibile sfruttare questi sottosistemi per risolvere i
prob-lemi di agreement.
Idee simili sono state proposte anche in [VCF00] per massimizzare la copertura delle assunzioni di sincronia nell’ambito dei sistemi real-time.
Le architetture a tre livelli per la replicazione software si basano inoltre sul concetto di evitare che i client e le repliche partecipino ai protocolli di agreement per prendere decisioni concernenti la consistenza. Questo si ottiene (i) facendo in modo che questi protocolli siano eseguiti in un sottosistema con garanzie di elevata copertura delle assunzioni di sincronia parziale, che pu`o essere distribuito indipendentemente dai client e dalle repliche, e (ii) propagando le informazioni alle repliche e ai client usando comunicazioni punto-punto.
Di conseguenza, i client e le repliche non necessitano di eseguire protocolli complessi e della copertura delle assunzioni di sincronia parziale, per cui possono essere distribuiti su un sistema che fornisce poche garanzie rispetto alle assunzioni temporali, come per esempio Internet.
Il risultato `e una architettura a tre livelli per la replicazione software (vedi Figura 3.2). In una architettura siffatta i client e le repliche non interagiscono
middle-t ier en d-t ier c lien t -t ier C1 C2 Cm R1 R2 Rn Sistema distribuito parzialmente sincrono con ampie garanzie di copertura Sistema distribuito asincorno Sistema distribuito asincrono Logica di replicazione
middle-t ier en d-t ier
c lien t -t ier C1 C2 Cm R1 R2 Rn Sistema distribuito parzialmente sincrono con ampie garanzie di copertura Sistema distribuito asincorno Sistema distribuito asincrono Logica di replicazione
Figura 3.2: Una architettura a tre livelli per la replicazione software.
tra di loro, ma piuttosto interagiscono con un middle-tier ad alta disponibilit`a e tollerante ai guasti, che da un punto di vista logico `e interposto tra i client (client-tier ) e le repliche (end-tier ), gestendo le repliche e imponendo consistenza forte. In altre parole il middle-tier implementa la logica di replicazione.
Il middle-tier riceve le richieste dei client e le inoltra alle repliche, insieme ad informazioni che consentono a ciascuna di esse di eseguire indipendentemente le richieste in modo tale da imporre la consistenza forte. Le repliche inviano il risultato al middle-tier, che infine lo restituisce ai client.
Per non introdurre una singola fonte di guasti, il middle-tier `e replicato. Nel seguito considereremo il caso in cui il middle-tier sia replicato tramite replicazione software, per cui avremo un insieme di repliche del middle-tier. Queste repliche mantengono uno stato interno riguardante il processamento delle richieste da parte delle repliche dell’end-tier, cio`e delle repliche che effettivamente implemen-tano il servizio. Per evitare violazioni nella consistenza delle repliche dell’end-tier, deve essere garantita consistenza forte per lo stato interno delle repliche del middle-tier. Ci`o richiede l’esecuzione di un protocollo di agreement, e quindi necessita di un sistema parzialmente sincrono. Tuttavia solo il middle-tier deve essere distribuito in un tale sistema, mentre le repliche dell’end-tier e i client possono essere distribuiti su un sistema asincrono.
Notiamo inoltre che le architetture a tre livelli per la replicazione software in-troducono una netta separazione tra la gestione della replicazione e la reale
imple-mentazione del servizio. Questo disaccoppiamento comporta i seguenti ulteriori
vantaggi:
• Client e server “leggeri”. I client sono aumentati solo con un
sem-plice meccanismo di ritrasmissione delle richieste, uno strumento necessario per affrontare guasti del middle-tier e ritardi arbitrari nella trasmissione
3.2. UNA ARCHITETTURA A TRE LIVELLI PER LA REPLICAZIONE
SOFTWARE 29
dei messaggi. Questo permette di rendere trasparenti ai client i guasti e la replicazione, ed aumenta lo spettro dei dispositivi che possono os-pitare tali client, per esempio telefoni cellulari, PDA, ecc. Allo stesso modo le repliche dell’end-tier implementano semplici funzionalit`a, come il filtraggio dei duplicati, oltre a fornire effettivamente il servizio. Inoltre, i client e le repliche possono comunicare con il middle-tier tramite primitive punto-punto, seguendo un semplice schema asincrono richiesta/risposta. Di conseguenza, una tecnica di replicazione che soddisfa queste propriet`a e caratteristiche permette di implementare i client e le repliche su tecnologie standard basate su TCP, come IIOP e SOAP.
• Disaccoppiamento tra client e repliche. I client e le repliche sono lascamente accoppiati: non si ha uno scambio di messaggi tra di essi. Questo
favorisce la scalabilit`a delle architetture a tre livelli rispetto al numero di client e di repliche gestite dal middle-tier. Inoltre, il disaccoppiamento della logica di replicazione dalle repliche consente di estendere e modificare facilmente la logica di replicazione senza impattare sul codice del client. `E inoltre possibile pensare a cambiamenti automatici “al volo” della logica di replicazione, per esempio passando da una replicazione attiva ad una passiva per le repliche dell’end-tier, in modo da supportare anche repliche non-deterministiche [BM01].
• Disaccoppiamento della disponibilit`a del servizio dalla soprav-vivenza dei dati. La separazione della logica di replicazione dall’effettiva implementazione del servizio permette di preservare i dati nonostante eventi catastrofici che provocano la distruzione di un intero sito1. La disponibilit`a del servizio `e garantita finch´e il middle-tier funziona correttamente, mentre la sopravvivenza dei dati non dipende da guasti del middle-tier, poich´e le repliche sono distribuite in remoto. Di conseguenza, `e possibile mettere a punto il sistema rispetto alla disponibilit`a del servizio e alla sopravvivenza dei dati, selezionando indipendentemente il numero di repliche del middle-tier (determinando il livello di disponibilit`a del servizio) e il numero di repliche dell’end-tier (determinando il livello di integrit`a dei dati).
• Estendibilit`a del middle-tier. Il middle-tier si comporta come un com-ponente centralizzato altamente affidabile. Questo semplifica l’introduzione di altre utili funzionalit`a, come ad esempio il bilanciamento di carico
rispet-1I cluster di workstation non sono in grado di sopravvivere ad un guasto dell’intero sito: se
l’intero sito si guasta a causa di un evento catastrofico, come un incendio, si perdono sia la disponibilit`a del servizio che i dati memorizzati.
to alle richieste dei client per migliorare le prestazioni, con un impatto minimo sul codice delle repliche.
Le architetture a tre livelli per la replicazione software consentono quindi di configurare il sistema in modo tale che un numero elevato di client possa accedere ad un servizio implementato da un numero elevato di repliche distribuite in una WAN attraverso un piccolo numero di repliche del middle-tier, distribuite in un sistema con elevate garanzie. Il prezzo da pagare per questi vantaggi `e rappre-sentato da un salto addizionale nell’interazione client/server.
Nel seguito di questo capitolo verr`a presentata una architettura a tre livelli specializzata per gestire una replicazione attiva delle repliche dell’end-tier.
3.3 Replicazione attiva a tre livelli
In questa sezione verr`a introdotta la specifica formale della replicazione attiva. Verr`a poi descritta una architettura a tre livelli specializzata per la gestione di questa tecnica di replicazione software.
3.3.1 Specifica
La replicazione attiva [Sch93, GS97a] pu`o essere specificata prendendo in con-siderazione due tipi di giocatori, ossia un insieme finito di client {c1, . . . , cl} e
un insieme finito di repliche deterministiche {r1, . . . , rm}. I client invocano oper-azioni su un servizio replicato inviando richieste. Un messaggio di richiesta req `e
una coppia hid, opi, in cui req.id `e un identificatore unico della richiesta (unico per ogni richiesta distinta inviata da ogni client distinto), e req.op `e l’operazione che il servizio deve effettivamente eseguire. Una richiesta raggiunge tutte le repliche disponibili, le quali processano la richiesta (cio`e eseguono l’operazione contenuta nella richiesta). Astraiamo il processamento deterministico specifico del servizio effettuato da una replica generica per una richiesta req tramite il metodo
com-pute(op), che prende come parametro di ingresso una operazione e restituisce un
risultato (res). Il determinismo delle repliche implica che il risultato restituito da compute(op) dipende solo dallo stato iniziale della replica e dalla sequenza delle richieste processate. Un messaggio di risposta rep `e una coppia hid, resi, in cui rep.id `e l’identificatore univoco della richiesta req inviata dal client, cio`e
rep.id = req.id, mentre rep.res `e il risultato del processamento di req. Due
richi-este req1 e req2 sono uguali, cio`e req1 = req2 se e solo se req1.id = req2.id, e req1 = req2 ⇒ req1.op = req2.op.
3.3. REPLICAZIONE ATTIVA A TRE LIVELLI 31
Una implementazione corretta di un servizio deterministico replicato attiva-mente deve soddisfare le seguenti propriet`a2:
Termination. Se un client invia una richiesta req ≡ hid, opi allora alla fine riceve una risposta rep ≡ hid, resi, a meno che non si guasti.
Uniform Agreed Order. Se una replica processa una richiesta req, cio`e esegue
compute(req.op), come i-esima richiesta, allora le repliche che processano
la i-esima richiesta devono processare req come i-esima richiesta.
Update Integrity. Per ogni richiesta req, ogni replica esegue compute(req.op) al massimo una volta, e solo se un client ha inviato req.
Response Integrity. Se un client invia una richiesta req e consegna una risposta
rep, allora rep.res `e stato calcolato da qualche replica tramite l’esecuzione
di compute(req.op).
Queste propriet`a assicurano consistenza forte di un servizio deterministico replicato. In particolare, la propriet`a di Uniform Agreed Order implica che le repliche processano tutte le richieste nello stesso ordine. Dal momento che le repliche sono deterministiche, ci`o assicura che esse producano lo stesso risultato per ciascuna richiesta. Ci`o soddisfa la linearizzabilit`a. La propriet`a di
Termina-tion assicura la continuit`a dell’interazione client/server, ossia cattura la elevata
disponibilit`a del servizio. La propriet`a di Update Integrity assicura che le repliche calcolino le risposte solo nel momento in cui ricevono per la prima volta la richi-esta del client. Infine la propriet`a di Response Integrity garantisce che le risposte che arrivano ai client siano state effettivamente generate dal servizio.
3.3.2 Panoramica sull’architettura
Le architetture a tre livelli per la replicazione software sono basate su un middle-tier interposto tra client asincroni (client-middle-tier) e repliche asincrone (end-middle-tier). Nel caso della replicazione attiva, il middle-tier `e incaricato di accettare le richieste dei client, stabilire un ordine totale su di esse, e inviarle verso l’end-tier. Le repliche processano le richieste in base all’ordine stabilito dal middle-tier, ed in-viano i risultati a quest’ultimo, il quale poi li trasmette ai client. All’interno del middle-tier separiamo il problema di definire un ordine totale sulle richieste dei client, necessario per soddisfare la propriet`a di Uniform Agreed Order, dal prob-lema di fare in modo che tutte le repliche dell’end-tier ricevano tali richieste. Il
2Queste propriet`a sono una specializzazione al caso della replicazione attiva delle propriet`a
primo problema `e trattato da un Sequencer Service, mentre il secondo `e trattato dal componente del middle-tier denominato Active Replication Handler (ARH). Per soddisfare la propriet`a di Termination di una interazione client/server in pre-senza di guasti, il middle-tier deve essere fault-tolerant, cio`e sia il Sequencer che l’Active Replication Handler devono essere replicati.
La Figura 3.3 mostra i componenti della architettura a tre livelli per la repli-cazione attiva. Nel seguito di questo sezione diamo una breve descrizione fun-zionale di ciascun componente.
h2 h1 hn cl c1 c2 r1 r2
client-tier middle-tier end-tier
RR RR RR FO FO ARH rm FO Sistema parzialmente sincrono Sisterma distribuito asincrono DSS DSS DSS Sequen cer Service h2 h1 hn cl c1 c2 r1 r2
client-tier middle-tier end-tier
RR RR RR FO FO ARH rm FO Sistema parzialmente sincrono Sisterma distribuito asincrono DSS DSS DSS Sequen cer Service
Figura 3.3: Una architettura a tre livelli per la replicazione software attiva
Retransmission/Redirection (RR). Per affrontare i guasti delle repliche del componente ARH e l’asincronia dei canali di comunicazione, cio`e per as-sicurare la propriet`a di Termination, ciascun processo client c1, . . . , cl `e equipaggiato con un gestore di messaggi RR. I client invocano le operazioni tramite RR, che invia richieste univocamente identificate ad ARH. Dopo il trascorrere di un timeout inizializzato al momento dell’invio della richiesta, RR la ritrasmette, finch´e alla fine non riceve un risultato.
Active Replication Handler (ARH). Il componente ARH `e il cuore della logica di replicazione: sfruttando il Sequencer Service, esso ordina tutte
3.3. REPLICAZIONE ATTIVA A TRE LIVELLI 33
le richieste entranti dei client e assicura che almeno una copia di ciascu-na richiesta ordiciascu-nata sia alla fine consegciascu-nata ad ogni replica dell’end-tier disponibile. Le richieste sono inviate alle repliche dell’end-tier insieme al numero di sequenza assegnato loro dal Sequencer. Le repliche dell’end-tier eseguono le richieste in base ai numeri di sequenza (vedi Filtering and
Ordering sotto). Appena le repliche restituiscono un risultato, l’ARH lo
restituisce ai client. Per assicura la propriet`a di Termination nonostante i guasti, il componente ARH `e implementato da un insieme di repliche
h1, . . . , hn.
Sequencer Service. Il Sequencer Service `e disponibile per ogni replica ARH. In particolare, ciascuna replica ARH ha accesso alla classe Distributed Se-quencer Service (DSS), che rappresenta una implementazione distribuita e fault-tolerant del Sequencer Service. Questo servizio restituisce un numero di sequenza unico e consecutivo per ogni distinta richiesta dei client, e cos-tituisce l’elemento di base per soddisfare la propriet`a di Uniform Agreed
Order della replicazione attiva. Inoltre esso consente di reperire una
richi-esta (se esiste) associata ad un dato numero di sequenza. Questo consente di imporre la propriet`a di Termination nonostante i guasti delle repliche ARH.
Filtering and Ordering (FO). FO `e un gestore di messaggi posto di fronte a ciascuna replica dell’end-tier, con lo scopo di (i) assicurare l’esecuzione delle richieste in accordo ai numeri di sequenza assegnati ad esse dall’ARH, e (ii) evitare di ripetere l’esecuzione della stessa richiesta (che pu`o essere stata inviata di nuovo dall’ARH). Le caratteristiche precedenti permettono di assicurare le propriet`a di Uniform Agreed Order e Update Integrity sulle repliche dell’end-tier.
Nel seguito verr`a introdotto il modello di sistema assunto, e verr`a poi descritto pi`u in dettaglio il Sequencer Service. Infine si illustrer`a il protocollo eseguito dal middle-tier per gestire la replicazione attiva delle repliche dell’end-tier.
3.3.3 Modello di sistema
Consideriamo un sistema distribuito composto da un insieme di processi Π =
{p1, . . . , pq} che comunicano tramite scambio di messaggi.
Processi. I processi sono classificati in tre tipi disgiunti: un insieme C =
{c1, . . . , cl} di processi client (client-tier), un insieme H = {h1, . . . , hn} di repliche
deterministiche dell’end-tier. Siccome il middle-tier `e logicamente separato dai client e dalle repliche dell’end-tier, assumiamo H∩C = H∩R = ∅. Inoltre assumi-amo che le repliche dell’end-tier non possano invocare altri processi per rispondere a una richiesta di un client, cio`e l’esecuzione del metodo compute(req.op) `e ese-guita localmente a ciascun processo che rappresenta una replica dell’end-tier. Di conseguenza assumiamo C ∩ R = ∅.
Per quanto riguarda i guasti dei processi, assumiamo il modello crash per i processi in Π (vedi Sezione 2.1.2). Ci`o significa che i processi si comportano in accordo alla loro specifica finch´e non si guastano, mentre dopo un guasto smettono di eseguire qualsiasi azione. Un processo `e corretto se non `e mai soggetto a un crash, altrimenti `e guasto.
Canali di comunicazione. I processi comunicano attraverso canali unicast asincroni quasi-affidabili [BCBT96], modellati tramite le primitive send(m, pj) e deliver(m, pj). La primitiva send(m, pj) `e invocata da un processo pi ∈ Π
per inviare un messaggio m ad un processo pj ∈ Π. La primitiva deliver(m, pj) `e invece eseguita in un processo pi alla ricezione di un messaggio m inviato dal processo pj a pi. I canali soddisfano le seguenti propriet`a:
Channel Validity. Se un processo riceve un messaggio m, allora m `e stato inviato da qualche processo.
Channel No Duplication. I messaggi sono consegnati ai processi al massimo una volta.
Channel Termination. Se un processo corretto invia un messaggio m ad un processo corretto, quest’ultimo alla fine consegna m.
Avendo assunto il modello crash per i guasti dei processi, questi canali pos-sono essere implementati su canali che soffrono di guasti di tipo omission tramite ritrasmissione dei messaggi [BCBT96].
Le propriet`a precedenti stabiliscono che i processi sono distribuiti in un
sis-tema asincrono. Tuttavia questo `e solo un modello base della computazione, nel
senso che dovranno essere aggiunte ulteriori assunzioni per quelle regioni in cui si rende necessaria una elevata copertura delle ipotesi di sincronia.
3.3.4 Il Sequencer Service
Il Sequencer Service `e specificato in termini di due primitive, ossia i metodi Get-Seq() e GetReq(). Il primo metodo prende come parametro di input una
3.3. REPLICAZIONE ATTIVA A TRE LIVELLI 35
richiesta req e restituisce un numero di sequenza intero positivo #seq. Il secondo metodo prende come parametro di input un intero positivo #seq e restituisce la richiesta req a cui precedentemente era stato assegnato #seq come numero di sequenza (se tale richiesta esiste), oppure il valore null altrimenti. Pi`u for-malmente, denotiamo con GetSeqi() = v (rispettivamente GetReqi() = v) la generica invocazione del metodo GetSeq() (rispettivamente GetReq()) ese-guita dalla generica replica ARH hi che si conclude con la restituzione del valore
v.
Le propriet`a che una corretta implementazione del Sequencer Service deve soddisfare sono le seguenti:
(S1) Termination. Se hi `e corretta, GetSeqi() e GetReqi() alla fine resti-tuiscono un valore v;
(S2) Agreement. ∀ (GetSeqi(req) = v, GetSeqj(req0) = v0), req = req0 ⇒ v = v0;
(S3) Uniqueness. ∀ (GetSeqi(req) = v, GetSeqj(req0) = v0), v = v0 ⇒ req = req0;
(S4) Consecutiveness. ∀ GetSeqi(req) = v, v ≥ 1 ∧ v > 1 ⇒ ∃ req0 t.c. GetSeqj (req0) = v − 1.
Le propriet`a precedenti stabiliscono che, invocando il metodo GetSeq() del Sequencer, le repliche ARH assegnino lo stesso insieme di numeri di sequenza unici e consecutivi alle richieste dei client.
In particolare, la propriet`a di Termination (S1) assicura la continuit`a dell’in-terazione con il servizio; la propriet`a di Agreement (S2) evita che due repliche ARH ottengano numeri di sequenza diversi per la stessa richiesta di un client; la propriet`a di Uniqueness (S3) evita che due repliche ARH ottengano lo stesso numero di sequenza per due richieste diverse; infine la propriet`a di
Consecutive-ness garantisce che le repliche ARH che invocano il metodo GetSeq() ottengano
numeri interi positivi e consecutivi, cio`e che la sequenza di richieste dei client or-dinate in accordo ai numeri di sequenza ottenuti dalle repliche ARH non presenti “buchi”.
Le propriet`a precedenti caratterizzano solo i valori restituiti alle repliche ARH in seguito all’invocazione del metodo GetSeq(). Le seguenti propriet`a invece caratterizzano il metodo GetReq().
(S5) Reading Integrity. ∀ GetReqi(#seq) = v ⇒ ((v = null) ∨ (v = req t.c. GetSeqj(v) = #seq));
(S6) Reading Validity. ∀ GetSeqi(req) = v ⇒ GetReqi(v − k) = v0, 0 ≤
k < v, v0 6= null.
La propriet`a di Reading Integrity (S5) definisce l’insieme dei possibili valori restituiti dal metodo GetReq(). Notiamo che una implementazione del metodo che restituisca sempre null soddisfa questa propriet`a. Per evitare questo com-portamento non desiderato, la propriet`a di Reading Validity (S6) stabilisce che se una replica ARH hi invoca il metodo GetSeqi(req), e questo ritorna un valore
v = #seq, allora hi sar`a in grado di reperire tutte le richieste req1, . . . , req#seq alle quali era stato assegnato un numero di sequenza #seq0tale che 1 ≤ #seq0 ≤ #seq.
Questa specifica pu`o essere implementata in vari modi. Nel seguito assumer-emo che il Sequencer sia implementato sulla base di una primitiva di total order multicast, tramite la quale le repliche ARH {h1, . . . hn} possono comunicare tra di
esse3. In particolare, `e necessario utilizzare una primitiva di strongest total order
multicast, definita nella Sezione 2.3.2 (vedi anche Capitolo 4). I lettori interessati
possono trovare maggiori dettagli su questa implementazione in [Mar02]. Possi-amo comunque notare che, indipendentemente dall’implementazione, il Sequencer
necessita di un sistema parzialmente sincrono. Ci`o `e facilmente intuibile dal fatto
che esso risolve un problema di agreement (vedi la propriet`a di Agreement (S2)), ma `e anche dimostrato dal fatto che la specifica del Sequencer `e equivalente al problema del consenso uniforme [Mar02]. Ci`o implica che il modello di sistema