corso di laurea specialistica in ingegneria informatica ...unina.stidue.net/sistemi...
TRANSCRIPT
1
Università degli Studi di Napoli Federico II Facoltà di IngegneriaCorso di Laurea Specialistica in Ingegneria Informatica
Corso di
Sistemi DistribuitiProf. Stefano Russo
Comunicazionidi gruppo
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 2
Sommario
• Comunicazioni di gruppo • Multicast• Reliable multicast• Ordinamenti
- FIFO multicast- Causal multicast- Total multicast
• Implementazione
Riferimenti:
G. Coulouris et al.: Distributed Systems: Concepts and Design, Cap. 12 §4eccetto “Reliable multicast over IP multicast”, IV ed., 2005.
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 3
Comunicazioni di gruppo
Gruppo ApertoGruppo Chiuso
Gruppo chiuso: solo i membri possono inviare messaggi in multicastal gruppoGruppo aperto: anche i non membri possono inviare messaggi in multicastal gruppo
2
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 4
Comunicazioni di gruppo tolleranti ai guasti e/o ordinate
�Obiettivo�Assicurare che i processi possano scambiare messaggi
di gruppo anche in presenza di fallimenti dei canali dicomunicazione e/o dei processi stessi.
e/o�Assicurare che i messaggi inviati a un gruppo siano
ricevuti in maniera ordinata
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 5
Consegna affidabile dei messaggi
�Principali strategie:�Error Masking
⌧ridondanza spaziale
⌧ridondanza temporale
�Error Detection and Recovery⌧basata suacknowledgements(acks) e timeout
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 6
Error Masking (1/3)
�Ridondanza Spaziale: I processi sono connessi concollegamenti ridondanti
�Per mascherarek omissioni, occorronok+1 collegamenti
3
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 7
Error Masking (2/3)
�Ridondanza temporale: il messaggio viene inviato più volte
�Per mascherarek omissions, il messaggio deve essere inviatok+1 volte
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 8
Error Masking (3/3)
�In entrambi i casi si pone il problema dei messaggiduplicati: essi devono essere scartati dal ricevente
�È difficile in generale trovare il giusto compromessotra semplicità direcoverye consumo di banda.
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 9
Error detection e recovery
�Gli ackpossono essere inviati quando:� Un messaggio viene ricevuto (positive ack, v. figura)� Un timeoutscade al ricevente, che decreta la perdita di un
messaggio (negative ack)
4
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 10
Schemi per l’invio dei messaggi ack (1/2)
�Nello schema con positive ack, un messaggio viene ritrasmesso se non viene ricevuta una conferma al mittente entro un timeoutpredefinito. � La failure viene individuata più rapidamente in caso di
traffico sporadico
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 11
Schemi per l’invio dei messaggi ack (2/2)
�Nello schema con negative acks, il ricevente richiede una ritrasmissione inviando un acknegativo�Minimizza il traffico di rete ma richiede
l’implementazione di uno dei seguenti meccanismi:⌧Numerazione dei messaggi, in maniera tale da poter richiedere
la ritrasmissione di un particolare messaggio (se ad esempio viene ricevuto il messaggio i ma non il messaggio i-1)
⌧Una strategia time-triggered in maniera tale che il ricevente sappia quando deve ricevere un messaggio.
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 12
Livelli di affidabilità
�Livelli di affidabilità in comunicazioni multicast: �Unreliable multicast– Nessuno sforzo per superare
failures dei canali di comunicazione; il multicast èaffidabile se lo sono i canali e il mittente.
�Best-effort multicast– Il mittente compie qualche azione per assicurare la consegna del messaggio, come ad esempio ritrasmettere lo stesso, ma non ci sono garanzie
�Reliable multicast– I partecipanti (membri del gruppo) si coordinano per garantire che il messaggio venga consegnato a tutti i destinatari corretti.
5
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 13
Basic Multicast
�2 primitive: B-multicaste B-deliver�Garantiscono che un processo corretto prima o poi riceverà il
messaggio, a patto che il mittente non fallisca�La primitiva di B-multicastpuò essere implementata
utilizzato una primitiva per la comunicazione punto-punto su canale affidabile:� B-multicast(g,m):for each process p ∈∈∈∈ g, send(p,m)� B-receive(m) at p:B-deliver(m) at p
� Soffre del problema dell’ack-implosion� Spreca larghezza di banda� … e comunque il mittente può fallire in ogni istante
durante l’esecuzione del B-multicast!
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 14
Reliable Multicast
�Hadzilacos e Toueg (1994), Chandra e Toueg (1996)
�Soddisfa le seguenti proprietà:� Integrity – un processo correttop riceve m al più un
volta. Inoltre, p ∈∈∈∈ group(m)e m è stato inviato via multicast da sender(m)
� Validity – se un processo corretto p invia m in multicast, prima o poi riceveràm
� Agreement– se un processo corretto riceve m, allora tutti i processi corretti in group(m)prima o poi riceverannom
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 15
Uniform reliable multicast
�Le definizioni delle proprietà del reliable multicastfanno riferimento a processi corretti (cioè che non falliscono mai).
�Una proprietà valida a prescindere dal fatto che i processi siano corretti o meno si dice uniforme.
�In particolare si ha:� Uniform agreement– se un processo (corretto o
meno) ricevem, allora tutti i processi corretti in group(m)prima o poi riceverannom
6
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 16
Implementazione del Reliable Multicast con B-multicast (1/3)
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 17
Implementazione del Reliable Multicast con B-multicast (2/3)
• Questa implementazione è corretta in un sistema asincrono, ma inefficiente (il messaggio è inviato |g| volte a ciascun processo)
L’implementazione soddisfa le proprietà del reliable multicast:Integrità : discende dall’integrità dei canali di comunicazioneValidità : è evidente che un processo corretto prima o poi fa il B-delivera sé stessoAccordo: discende dal fatto che ogni processo corretto esegue B-multicastdopo B-deliver. Se dunque un processo corretto non effettua R-deliver, ciò può essere dovuto solo al fatto che non ha fatto B-deliver; ciò può sussistere solo se nessun altro processo corretto ha fatto il B-deliver: in tal caso nessuno faràR-deliver
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 18
Implementazione del Reliable Multicast con B-multicast (3/3)L’implementazione soddisfa anche la proprietà di uniform agreementSe ad esempio un processo non è corretto e va in crashdopo aver effettuato R-deliver, poiché in precedenza ha sicuramente effettuato B-deliver, nondimeno dunque tutti i processi corretti riceveranno il messaggio.
N.B.: Se si invertono le istruzioni ‘R-deliver m’ e ‘ if(q≠p) then B-multicast(g,m) endif’, l’implementazione non soddisfa più la proprietà di uniform agreement.
7
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 19
Ordinamento FIFO
�Se un processo corretto invia in multicasti messaggim e poim’ , allora ogni processo corretto che riceveràm’ avrà già ricevutom
�Versione uniforme: idem senza ‘corretto’
F3
F1
F2
P1 P2 P3
tempo
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 20
Ordinamento causale (1/2)
�Semulticast(g,m) →multicast(g,m’), dove → è la relazione happened-before nell’ambito del gruppo g, allora ogni processo correttoche riceveràm’ avràgià ricevutom
�Versione uniforme: idem senza ‘corretto’P 1 P2 P 3
C3
C1
C2 tempo
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 21
Ordinamento causale (2/2)
�L’ordinamento causale implica quello FIFO, poichégli invii di uno stesso processo sono in relazione HB
�L’ordinamento causale estende l’ordinamento FIFO con l’ordinamento della ricezione dei messaggi che, pur inviati da processi diversi, sono in relazione di potenziale causalità� Se un processo p invia in multicastun messaggio m ed
un processo p’≠p riceve m prima di inviare in multicastm’ , allora nessun processo corretto riceve m’ a meno che non abbia già ricevuto m
8
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 22
Ordinamento totale
�Se un processo corretto riceve i messaggi m e poim’ , allora ogni altro processo corretto che ricevem’ avràgià ricevutom
�Uniform Version:idem senza ‘corretto’
�L’ordinamento totale nonimplica quello FIFO néquello causale
T2
T1
P1P2 P3
tempo
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 23
Confronto degli ordinamenti
tempo
� NB: nell’esempio i messaggi TO sono ricevuti nell’ordine opposto rispetto all’invio: la definizione di TOM richiede infatti che l’ordine sia lo stesso per tutti, ma può essere arbitrario
F3
F1
F2
T2
T1
P1 P2 P3
C3
C1
C2
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 24
Un approccio modulare ai protocolli di multicast
ReliableMulticast
FIFO ReliableMulticast
CausalReliable Multicast
AtomicMulticast
FIFO AtomicMulticast
Causal AtomicMulticast
[ da Hadzilacos e Toueg - 1994 ]
Total Order
Total Order
Total Order
FIFO Order FIFO Order
Causal Order Causal Order
9
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 25
Esempio: bulletin board
Bulletin board: OS
Item From Subject
23 A.Hanlon Mach
24 G.Joseph Microkernels
25 A.Hanlon Re: Microkernels
26 T.L’Heureux RPC performance
27 M.Walker Re: Mach
end
Un gruppo per argomento; gli utenti si sottoscrivono agli argomenti di interesse.Un utente invia un messaggio su un argomento � broadcastal gruppo.Serve la semantica del reliable multicastse si vuole garanzia che tutti gli iscritti ricevano i messaggi.Serve la semantica dell’ordinamento FIFO se si vuole che tutti i messaggi inviati da uno stesso utente siano ricevuti nell’ordine di invio.Serve la semantica dell’ordinam. causalese si vuole, ad es., che il messaggio “Re: Microkernels” sia ricevuto dopo il messaggio “Microkernels” cui si riferisce.Serve la semantica dell’ordinam. totale se si vuole che la numerazione dei messaggi sia la stessa per tutti gli utenti.
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 26
Implementazione dell’ordinamento FIFO
� L’ordinamento si realizza mediante l’utilizzo di numeri di sequenza
� Assunzione: i gruppi nonsi sovrappongono
� Sp – contatore dei messaggi inviati dal processo p al gruppogRq - numero di sequenza dell’ultimo messaggio deliveredda p, inviato a g da q.
� Hold-Back-Queue(p) – coda dei messaggi fuori sequenza in attesa di essere ricevuti da p
To FO-multicast(m,g):piggy-.back Sp onto m;B-multicast(m,g);Sp = Sp +1;
To FO-deliver(q,m) with m bearingS= Rq +1:
FO-deliver(q,m);Rq = S ;
To FO-deliver(q,m) with m bearingS> Rq +1:
put m in Hold-Back-Queue;wait until S(m) = Rq +1;FO-deliver(q,m);
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 27
Implementazione del FIFO Reliable Multicast
�Si può usare la stessa implementazione del FIFO multicast, usando R-multicastal posto di B-multicast
To FO-multicast(m,g):piggy-.back Sp onto m;R-multicast(m,g);Sp = Sp +1;
To FO-deliver(q,m) with m bearingS= Rq +1:
FO-deliver(q,m);Rq = S ;
To FO-deliver(q,m) with m bearingS> Rq +1:
put m in Hold-Back-Queue;wait until S(m) = Rq +1;FO-deliver(q,m);
10
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 28
Implementazione dell’ordinamento causale (1/3)
�L’implementazione tiene conto solo delle relazioni HB tra i messaggi multicast, non di quelle tra messaggi diretti (one-to-one) scambiati tra i processi
�Si può far uso di orologi vettoriali (Vector Clocks)�l’elemento i-esimo conta il numero di messaggi inviati dal
processo i-esimo in relazione HB con il prossimo messaggio
�Assunzione: gruppi chiusi non sovrapposti
�Per effettuare il CO-multicast, un processo incrementa il “proprio” elemento nel vettore ed esegue B-multicastal gruppo g del messaggio marcato col vector clock
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 29
Implementazione dell’ordinamento causale (2/3)
�Quando pi fa il B-deliverdi un messaggio inviato da pj, prima di effettuare il CO-deliver deve inserirlo nella hold-back queuefinché non ha fatto il CO-deliver di tutti i messaggi in relazione HB con esso
�Pi deve perciò verificare di aver fatto:�il CO-deliverdi tutti i messaggi precedenti inviati da pj, e:
�il CO-deliverdi tutti i messaggi di cui pj aveva fatto il CO-deliverprima di inviare il messaggio in questione
�Queste condizioni possono essere verificate esaminando i vector timestamps dei messaggi ricevuti
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 30
Implementazione dell’ordinamento causale (3/3)
NB: il CO-deliverdi un proprio messaggio può essere effettuato immediatamente
11
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 31
Implementazione di Causal Reliable Multicast
�Il multicast con ordinamento causale affidabile può essere implementato a partire dalla implementazione del Causal Multicast, usando R-multicastal posto di B-multicast
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 32
Implementazione dell’ordinamento totale (1/4)� Basata sulla marcatura dei messaggi con identificatori totalmente
ordinati, in modo che tutti i processi possano prendere le stesse decisioni
� Il deliveryè come per l’ordinamento FIFO, ma i numeri di sequenza si riferiscono al gruppo, non al processo
� Primo metodo: implementazione mediante processo sequenziatore�un messaggio m è inviato sia a g sia a sequencer(g),etichettato con un id
univoco id(m)
�sequencer(g)può coincidere con un membro di g
�sequencer(g)gestisce un numero di sequenza per il gruppo sg, con cui marca i messaggi di cui effettua B-deliver
�sequencer(g)annuncia i numeri di sequenza inviando messaggi di ordinamentoa g tramite B-multicast
�un messaggio resta nella hold-back queuefinché non può esserne effettuato il TO-deliver, in base al suo numero di sequenza
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 33
Implementazione dell’ordinamento totale (2/4)
TO-multicastcon sequenziatore
12
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 34
Implementazione dell’ordinamento totale (3/4)
� Secondo metodo: Algoritmo ISIS (Birman, 1987), valido per gruppi aperti o chiusi
� I processi concordano collettivamente sui numeri di sequenza, con un algoritmo distribuito
1
1
2
2
1 Message
2 Proposed Seq
P2
P3
P1
P4
3 Agreed Seq
3
3Ogni ricevente propone il numero di sequenza al multicaster, che genera il numero “agreed”
Ogni processo q di g possiede:Aq
g: il più alto numero di sequenza finora convenuto Pq
g: il più alto numero di sequenza finora proposto dallo stesso q
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 35
Implementazione dell’ordinamento totale (4/4)Ogni ricevente propone:
Pqg:=Max(Aq
g,, Pqg)+1
e assegna temporaneamente al messaggio il numero proposto, inserendolo nella hold back queue; questa è ordinata con il valore più piccolo in testa.
Il multicasterraccoglie le proposte e seleziona il valore maggiore a, quindi effettua B-multicast<i,a> (i è l’id univoco con cui il multicaster ha etichettato m)
Ogni ricevente assegna:Aq
g:=Max(Aqg, a)
e associa il valore a al messaggio, quindi riordina la hold-back queue se il valore convenuto è diverso da quello proposto. Quando al messaggio in testa alla coda viene assegnato lo stesso numero proposto, viene inserito in una delivery queue.
Corso di Sistemi Distribuiti, prof. S. Russo Comunicazioni di gruppo 36
Implementazione del Causal Total Multicast
�Se si combina l’algoritmo per l’ordinamento causale (CO) con quello per il multicasttotalmente ordinato (TO) basato sul sequencersi ottiene un ordinamento che è ordinato sia causalmente sia totalmente (C&TO)�il sequenziatore deve fare il deliverysecondo l’ordinamento causale, e il
multicastdei numeri di sequenza dei messaggi nell’ordine con cui li riceve
�i processi nel gruppo di destinazione non effettuano il deliverprima di aver ricevuto un messaggio orderdal sequenziatore eil messaggio è il prossimo nella sequenza
�in tal modo, poiché il sequencereffettua il deliver in ordine causale, e tutti gli altri processi lo effettuano nell’ordine del sequencer, l’ordinamento è sia totale sia causale