Questo capitolo `e dedicato ad un’analisi di alcuni tra i group toolkit esistenti, al fine di trovare quello pi`u adatto all’implementazione del Sequencer Service, definito nella Sezione 3.3.4. Al meglio della nostra conoscenza, la letteratura non presenta alcun confronto riguardante le prestazioni dei group toolkit, n´e tan-tomeno un tentativo di classificazione rispetto alla specifica dei servizi supportati e dei protocolli utilizzati. Dal momento che esistono molti protocolli per il total order, e possono essere date specifiche diverse del servizio, risulta importante in-dividuare il comportamento e le garanzie offerte dai vari group toolkit rispetto a questa primitiva, al fine di fornire un supporto adeguato agli sviluppatori che devono scegliere un group toolkit da utilizzare per le loro applicazioni.
Il resto del capitolo `e organizzato come segue. La Sezione 4.1 descrive gli aspetti legati al servizio di total order multicast, fornendo una classificazione delle varie specifiche alternative, e discutendo i principali algoritmi usati per l’implementazione. La Sezione 4.2 introduce una descrizione dell’architettura dei group toolkit, fornisce una classificazione di alcuni group toolkit esistenti, sia rispetto alle differenze nell’architettura, sia rispetto alle differenze nella specifica dei servizi di total order da essi offerti, e presenta infine un’analisi delle prestazioni di tali group toolkit.
4.1 Il total order multicast
La crescente attenzione per il supporto alla tolleranza ai guasti nei sistemi dis-tribuiti ha portato ad un crescente interesse verso protocolli che forniscano garan-zie di ordinamento totale sui messaggi consegnati. Ci`o `e legato soprattutto alla
necessit`a di implementare la tecnica di replicazione attiva, che rappresenta uno degli approcci pi`u importanti alla tolleranza ai guasti nei sistemi distribuiti. In questa sezione vedremo le possibili alternative alla specifica per il total order mul-ticast data nella Sezione 2.3.2, e considereremo poi alcuni tra gli algoritmi pi`u rappresentativi che vengono usati per implementare questo servizio.
4.1.1 Specifiche alternative
Come detto nella Sezione 2.3.2, la specifica del total order viene data rispetto a quattro propriet`a, ossia (i) Validity, la quale garantisce che tutti i messaggi che sono stati inviati in multicast da processi corretti saranno sempre consegnati, (ii)
Integrity, la quale garantisce che non vengano mai consegnati messaggi spuri o
duplicati, (iii) Agreement, la quale garantisce un accordo tra i processi rispetto alla decisione di consegnare un messaggio, e (iv ) Order, che definisce l’ordine sui messaggi consegnati. A parte la propriet`a di Validity, per la quale si ha un’unica definizione, corrispondente a quella vista nella Sezione 2.3.2, le altre propriet`a possono essere definite in diversi modi, a seconda che si consideri o meno il comportamento dei processi non corretti. Ci`o porta ad avere diverse specifiche, tra le quali la pi`u forte `e quella di strongest total order data nella Sezione 2.3.2. Questa specifica assicura una evoluzione consistente di tutti i processi del sistema, mentre le specifiche pi`u deboli consentono il verificarsi di una o pi`u forme di inconsistenza1. Nel seguito descriveremo le alternative legate ad una diversa definizione delle propriet`a di Agreement e Order. Per la propriet`a di
Integrity invece assumeremo valida la definizione di Uniform Integrity data nella
Sezione 2.3.2, in quanto essa `e facilmente implementabile e pu`o quindi considerarsi sempre soddisfatta in tutti i casi pratici.
La propriet`a di Agreement. Una prima alternativa per indebolire la specifica di strongest total order consiste nel sostituire la propriet`a di Uniform Agreement con la seguente versione non uniforme:
Non-uniform Agreement. Se un processo corretto consegna un messaggio m, allora tutti i processi corretti in Dest(m) alla fine consegneranno m. La proriet`a di Non-uniform Agreement consente ai processi non corretti di consegnare dei messaggi che invece non saranno mai consegnati dai processi cor-retti. In altre parole, i processi non corretti possono decidere autonomamente se
1La nozione di inconsistenza `e strettamente legata allo scenario applicativo. Ci`o che pu`o
es-sere inconsistente per una applicazione pu`o non esserlo per altre. Di contro, garantire propriet`a
4.1. IL TOTAL ORDER MULTICAST 43 processi corretti processo non corretto processi corretti processo non corretto
(a) Inconsistenza per consegna au-tonoma dovuta all’uso della propriet`a di Non-uniform Agreement processi corretti processo non corretto processi corretti processo non corretto
(b) Uno scenario che non soddisfa alcuna propriet`a di Agreement
Figura 4.1: Scenari che violano la propriet`a di Uniform Agreement
consegnare o meno un messaggio, mentre i processi corretti sono ancora costretti a raggiungere un accordo sulla decisione di consegnarlo. Ci`o rende possibile uno scenario in cui un processo p non corretto invia un messaggio m, consegna tale messaggio e successivamente si guasta, mentre nessun altro processo (corretto o meno) consegna m. Questo scenario `e illustrato in Figura 4.1(a), e consente il verificarsi di una inconsistenza esterna se p, prima di guastarsi, esegue un aggior-namento su un processo q esterno al gruppo di processi coinvolti nel multicast senza che questi si accorgano di tale azione. Inoltre, l’inconsistenza interna tra p e gli altri processi del gruppo, dovuta alla consegna di m da parte di p, pu`o poi portare alla contaminazione degli altri processi se p esegue il multicast di qualche altro messaggio prima di guastarsi. Infatti nel momento in cui un processo cor-retto consegna un messaggio inviato da un processo inconsistente, esso altera il proprio stato sulla base di informazioni non corrette, diventando quindi a sua volta inconsistente.
La Figura 4.1(b) mostra invece uno scenario che non rispetta alcuna propriet`a di Agreement, in quanto i due processi corretti non consegnano lo stesso insieme di messaggi. Questo tipo di scenario `e comunque reso impossibile da ogni specifica di total order.
Notiamo infine che la sostituzione della propriet`a di Uniform Agreement con la versione non uniforme comporta automaticamente l’impossibilit`a di soddisfare la propriet`a di Prefix Order, presente nella specifica dello strongest total order. Infatti se si ammette che un processo p non corretto possa consegnare un messag-gio m che non sar`a consegnato dai processi corretti, allora per qualsiasi processo corretto q non si ha n´e che h(p) `e un prefisso di h(q) n´e che h(q) `e un prefisso di
h(p), violando quindi la prorpiet`a di Prefix Order. Siccome `e difficile formalizzare
specifica che rinuncia alla propriet`a di Uniform Agreement indebolisce anche la propriet`a di Order, sostituendo la versione Prefix Order con le alternative discusse di seguito.
La propriet`a di Order. La specifica di strongest total order pu`o essere inde-bolita sostituendo alla propriet`a di Prefix Order una delle seguenti alternative: Uniform Total Order. Se due processi p e q consegnano entrambi i messaggi
m1 e m2, allora p consegna m1 prima di m2 se e solo se q consegna m1 prima di m2.
Non-uniform Total Order. Se due processi corretti p e q consegnano entrambi i messaggi m1e m2, allora p consegna m1 prima di m2 se e solo se q consegna
m1 prima di m2. processi corretti processo non corretto m1 m2 m3 processi corretti processo non corretto m1 m2 m3
(a) Inconsistenza per omissione dovu-ta ad un mancato uso della propriet`a di Prefix Order processi corretti processo non corretto m1 m2 processi corretti processo non corretto m1 m2
(b) Inconsistenza per inversione dovu-ta all’uso della propriet`a di Non-uniform Total Order
Figura 4.2: Problemi dovuti ad un indebolimento della proriet`a di Order nella specifica del total order multicast
La differenza tra Uniform e Non-uniform Total Order `e come al solito legata al fatto che la seconda considera solo il comportamento dei processi corretti. Di conseguenza, la propriet`a di Uniform Total Order `e pi`u forte dell’altra, poich´e esistono scenari che soddisfano la seconda ma non la prima. Tuttavia entrambe sono pi`u deboli della propriet`a di Prefix Order, in quanto rendono possibile il verificarsi dello scenario mostrato in Figura 4.2(a). In questo scenario il processo non corretto p omette la ricezione del messaggio m2, ma riceve il messaggio m3, diventando inconsistente rispetto agli altri processi nel gruppo. Ci`o pu`o com-portare una contaminazione di tali processi, nel caso in cui p esegua il multicast di un nuovo messaggio m4 prima di guastarsi, oppure pu`o comportare delle
4.1. IL TOTAL ORDER MULTICAST 45
esterno q prima di guastarsi. Inoltre, una specifica che utilizzi la propriet`a di
Non-uniform Total Order rende possibile anche lo scenario riportato in Figura
4.2(b), in cui il processo non corretto p consegna i messaggi m1 e m2 in un ordine diverso rispetto ai processi corretti, risultando quindi inconsistente rispetto ad essi. Anche in questo caso `e possibile che p contamini gli altri processi nel grup-po o crei una inconsistenza su un processo esterno q, inviando nuovi messaggi o aggiornamenti prima di guastarsi.
non-uniform strong total order
weak total order uniform
weak total order
strong total order strongest total order
non-uniform strong total order
weak total order uniform
weak total order
strong total order strongest total order
Figura 4.3: Gerarchia delle specifiche per il total order multicast
Specifica Propriet`a Problemi
Strongest Prefix Order Nessuno
total order Uniform Agreement
Strong Uniform Total Order Inconsistenza per omissione
total order Uniform Agreement
Non-uniform strong Uniform Total Order Inconsistenza per consegna
total order Non-uniform Agreement autonoma e per omissione
Uniform weak Non-uniform Total Order Inconsistenza per inversione
total order Uniform Agreement e per omissione
Weak Non-uniform Total Order Inconsistenza per inversione, per
total order Non-uniform Agreement omissione e per consegna autonoma
Tabella 4.1: Specifiche per il total order multicast
La combinazione delle precedenti alternative per le propriet`a di Order e
Agree-ment porta alla definizione di varie specifiche alternative per il total order
presenta una serie di fonti di inconsistenza, dovute ad una diversa definizione delle due propriet`a considerate. In particolare, (i) ogni specifica che fa uso della propriet`a di Non-uniform Agreement consente il verificarsi di inconsistenze per consegna autonoma (Figura 4.1(a)), (ii) ogni specifica che utilizza la propriet`a di Uniform Total Order ammette scenari in cui i processi non corretti omettono la ricezione di alcuni messaggi (Figura 4.2(a)), e (iii) ogni specifica che utilizza la propriet`a di Non-uniform Total Order consente il verificarsi di inconsistenze per inversione nell’ordine dei messaggi ricevuti (Figura 4.2(b)). Queste specifiche formano quindi una gerarchia (vedi Figura 4.3), poich´e ognuna di esse ammette solo un sottoinsieme degli scenari ammessi dalle specifiche ad un livello inferiore della gerarchia. Una simile classificazione `e stata effettuata anche da Wilhelm e Schiper in [WS95] e successivamente da D´efago in [D´ef00], in cui viene consider-ata anche la versione non uniforme della propriet`a di Integrity.
4.1.2 Algoritmi di total order
La letteratura fornisce molti di algoritmi di total order multicast. Questi al-goritmi possono essere classificati prendendo in considerazione il modo in cui viene definito l’ordinamento dei messaggi, in particolar modo l’entit`a preposta alla definizione di tale ordine. Da questo punto di vista, una interessante classi-ficazione degli algoritmi di total order pu`o essere trovata in [D´ef00]. Nel seguito tuttavia ci concentreremo solo sulle classi di algoritmi che pi`u comunemente ven-gono utilizzati in pratica, ossia gli algoritmi basati su sequencer, quelli basati su
token e quelli basati sul protocollo di Skeen.
Algoritmi basati su sequencer. Gli algoritmi di questo tipo prevedono che un processo sia eletto come sequencer e si occupi di definire l’ordinamento dei mes-saggi. La responsabilit`a non viene trasferita ad altri processi a meno di guasti del sequencer. Di conseguenza `e necessario utilizzare un servizio di group mem-bership (vedi Sezione 2.3.1) che comunichi a ciascun processo eventuali guasti al sequencer, e che assicuri che in ogni istante di tempo esista al pi`u un processo responsabile dell’ordinamento dei messaggi. L’ordinamento viene stabilito asseg-nando dei numeri di sequenza ai messaggi, in modo che i destinatari possano consegnarli in base all’ordine definito da questi numeri di sequenza. Ci`o pu`o essere fatto secondo diversi schemi di comunicazione:
Broadcast-Broadcast. Questa alternativa `e illustrata in Figura 4.4(a): quando un processo desidera inviare un messaggio m, lo manda in broadcast a tutti i processi destinatari, compreso il sequencer. Ricevuto il messaggio, il
4.1. IL TOTAL ORDER MULTICAST 47 1 2 sequencer seq(m) m (a) Broadcast-Broadcast 1 2 sequencer <m, seq(m)> m (b) Send-Broadcast 1 sequencer <m, seq(m)> seq(m) ask(m) 3 2 (c) Ask-Broadcast
Figura 4.4: Varianti comuni degli algoritmi basati su sequencer
sequencer manda a sua volta in broadcast un numero di sequenza seq(m), che sar`a usato dai processi per consegnare il messaggio nel corretto ordine. Questa alternativa consente di diminuire il carico sul sequencer, rende pi`u semplice tollerare i guasti del sequencer e risulta particolarmente utile in reti che forniscono un servizio di hardware multicast.
Send-Broadcast. In questo caso, illustrato in Figura 4.4(b), il mittente invia il messaggio m solo al sequencer, che si fa carico di rimandare in broadcast
m e il numero di sequenza assegnato seq(m) a tutti i processi destinatari.
Questo schema impiega meno messaggi del precedente ed `e quindi preferito se la rete non supporta un servizio di hardware multicast.
Ask-Broadcast. Questa alternativa prevede che il mittente di un messaggio
m chieda un numero di sequenza seq(m) al sequencer, per poi mandare
in broadcast la coppia hm, seq(m)i. Questo schema, illustrato in Figura 4.4(c), richiede un passo aggiuntivo rispetto alle precedenti alternative, ma `e preferibile quando il messaggio m da inviare `e di grandi dimensioni.
Gli algoritmi basati su sequencer sono penalizzati dall’elevato carico a cui `e soggetto il processo che svolge il ruolo di sequencer. In linea teorica questi algorit-mi dovrebbero dare una buona latenza, ma in pratica possono essere penalizzati dalla elevata contesa che si ha sulla rete.
Algoritmi basati su token. Gli algoritmi di questo tipo prevedono che i pro-cessi siano organizzati in un anello logico, facendo circolare un token tra di essi. Il token controlla di fatto l’accesso alla rete, per cui solo il processo che corrente-mente possiede il token pu`o trasmettere dei messaggi. Ad ogni messaggio inviato viene associato un numero di sequenza che viene dedotto dal token, e incremen-tato per ogni messaggio inviato. In questo modo i processi possono consegnare i messaggi in accordo all’ordine imposto dai numeri di sequenza. In genere esiste un meccanismo che impedisce ad un processo di tenere il token per un tempo indefinito. Tale meccanismo pu`o essere basato sul controllo di flusso, su un time-out, oppure su esplicita richiesta da parte di altri processi (nel qual caso si parla di token asking). Inoltre si possono avere diverse alternative rispetto al compor-tamento dei processi che ricevono il token, ma non hanno messaggi da inviare: il token pu`o essere rilasciato immediatamente oppure essere soggetto anche in questo caso ad uno dei meccanismi precedenti.
Gli algoritmi basati su token sono progettati per fornire un throughput elevato per quelle applicazioni in cui ogni partecipante invia costantemente dei messaggi agli altri partecipanti. Inoltre la rotazione del token fornisce un bilanciamento del carico ed evita la contesa sulla rete. Tuttavia, nel caso peggiore, un messaggio pu`o attendere una rotazione completa del token prima di vedersi assegnare un numero di sequenza. Ci`o pu`o essere molto svantaggioso soprattutto quando il numero dei processi che inviano messaggi `e molto inferiore al numero dei processi partecipanti. In generale quindi, siccome il numero di passi di comunicazione `e una funzione della dimensione del sistema, gli algoritmi di questo tipo sono poco scalabili.
Algoritmi basati sul protocollo di Skeen. Gli algoritmi di questo tipo prevedono che l’ordinamento dei messaggi venga eseguito dai processi destinatari. I messaggi vengono infatti ricevuti senza alcuna informazione addizionale riguar-dante l’ordinamento: sono poi i destinatari a scambiarsi informazioni per or-dinare i messaggi. Questi algoritmi sono basati su clock logici [Lam78], e operano secondo i seguenti passi:
1. per inviare in multicast un messaggio m, il mittente invia m a tutti i desti-natari. Alla ricezione di m, ogni destinatario usa il proprio clock logico per associare un timestamp ad m;
2. i processi destinatari comunicano il timestamp al sistema, e viene calco-lato un timestamp globale sn(m) che viene poi inviato a tutti i processi destinatari;
4.2. I GROUP TOOLKIT 49
3. un messaggio m pu`o essere consegnato quando possiede un timestamp globale sn(m). I messaggi di questo tipo vengono poi consegnati nell’or-dine definito dai loro timestamp globali, una volta stabilito che non esista un messaggio non ancora consegnato m0 che possa ricevere un timestamp globale pi`u piccolo sn(m0).
Nella versione classica dell’algoritmo di Skeen, i timestamp locali sono inviati al mittente del messaggio, che provvede a calcolare il timestamp globale e a inviarlo ai destinatari (Figura 4.5(a)). Un’altra variante prevede tuttavia che il timestamp globale venga calcolato in maniera decentralizzata. In questo caso, ogni processo destinatario invia il timestamp locale a tutti gli altri, in modo che ognuno sia in grado di calcolare autonomamente il timestamp globale (Figura 4.5(b)). p1 p2 p3 p4 ts2(m) m ts3(m) ts4(m) sn(m)
(a) Algoritmo di Skeen cen-tralizzato p1 p2 p3 p4 ts2(m) ts3(m) ts4(m) m
(b) Algoritmo di Skeen de-centralizzato
Figura 4.5: Varianti degli algoritmi basati sul protocollo di Skeen
Gli algoritmi basati sul protocollo di Skeen generano un numero molto eleva-to di messaggi. Per queseleva-to motivo generalmente non forniscono buoni risultati per quanto riguarda throughput e latenza, ma hanno tuttavia il vantaggio di distribuire bene il carico di lavoro.
4.2 I group toolkit
Lo scopo di questa sezione `e di effettuare una analisi di alcuni tra i group toolkit esistenti al fine di individuare la specifica da essi offerta per quanto riguarda il servizio di total order multicast e le loro prestazioni nell’utilizzo di tale servizio. Abbiamo infatti visto nella Sezione 2.3 come i group toolkit siano uno strumen-to utilissimo per la realizzazione di applicazioni distribuite affidabili, grazie ai vari servizi messi a disposizione da essi. Tuttavia esistono una grande quantit`a
di group toolkit, ciascuno dei quali fornisce una propria semantica per i servizi offerti. In particolare abbiamo visto nella sezione precedente quante possibili specifiche si possono avere per il total order, e quanti algoritmi esistono per im-plementarle. Se una applicazione necessita quindi di un servizio di total order multicast, diventa molto importante (i) individuare le garanzie minime necessarie da soddisfare per il total order in modo da assicurare il corretto funzionamento dell’applicazione; tali garanzie si mappano nella scelta di una tra le specifiche viste nella sezione precedente; (ii) individuare il group toolkit che fornisce un servizio di total order multicast conforme a tali specifiche, possibilmente scegliendo quello dalle prestazioni migliori.
Questa analisi si pone dunque come guida per gli sviluppatori di applicazioni distribuite che intendono utilizzare un group toolkit, e ci consentir`a inoltre di individuare il group toolkit pi`u appropriato per l’implementazione del Sequencer Service descritto nella Sezione 3.3.4. Notiamo che un tale group toolkit dovr`a nec-essariamente fornire un servizio di total order che soddisfi la specifica di strongest
total order (vedi Sezione 2.3.2). Infatti, per quanto visto nella sezione
prece-dente, l’uso di una specifica pi`u debole pu`o portare alla violazione di alcune delle propriet`a che specificano il Sequencer Service, come per esempio le propriet`a di
Agreement (S2) e Uniqueness (S3).
Nel seguito considereremo quattro group toolkit, cio`e Appia [MPR01], Spread [AS98], JavaGroups [Ban98] e Ensemble [Hay98]. La scelta di questi group toolkit `e dovuta al fatto che essi forniscono interfacce Java.
4.2.1 Classificazione rispetto all’architettura
Come detto in precedenza, i group toolkit forniscono un ricco insieme di servizi e primitive che aiutano gli sviluppatori ad introdurre specifiche propriet`a nelle loro applicazioni. Il modo in cui ci`o pu`o essere fatto `e strettamente legato al-l’architettura del group toolkit. In generale, da un punto di vista architetturale, possiamo considerare un group toolkit come costituito da due blocchi fondamen-tali, ossia (i) le API e (ii) il sistema centrale (core), come mostrato in Figura 4.6(a). La API rappresentano l’insieme delle interfacce usate dall’applicazione per utilizzare i servizi del group toolkit, mentre il core `e la parte che realmente