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 adescriven-dottato, un particolare servizio utilizzato per definire l’ordinamento sulle richieste dei client e il protocollo utilizzato per implementare la replicazione attiva.
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 un3.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 influenconsisten-za 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-3.2. UNA ARCHITETTURA A TRE LIVELLI PER LA REPLICAZIONE
SOFTWARE 27
bile distribuire i client e le repliche in sistemi asincroni a larga scala, garantendo nello stesso tempo la terminazione dei protocolli che impongono consistenza forte.