Comunicação de Grupo
Roteiro:
• Motivação e Aplicações
• Formas de CG mais comuns e uma API típica
• Garantias sobre Atomicidade e Ordem
• Alternativas: Flooding e 2PC
• O Algoritmo Transis
• Pertinência a Grupos
• Sincronia Virtual
• Algumas arquiteturas
Referências:
• Livro do Chow/Johnson: seção 12.2
• Livro do Couloris/Dollimore/Kindberg: seções 4.5, 11.4, 14.2
• K. Birman, A Review of Experiences with Reliable Multicast, Software
Practice & Experience, 29(9), 1999.
• R. Guerraoui et al, Experiences with object group systems, Software
Practice & Experience, 30(9), 2000.
© Markus Endler
1
Comunicação de Grupo (CG)
Comunicação de Grupo é um serviço útil para:
• aplicações com requisitos de tolerância à falha (geralmente
implementados através de um conjunto de servidores
replicados)
• aplicações distribuídas baseado em um estado global
consistente (acoplamento forte entre os estados locais)
(p.ex. que requerem sincronização/ coordenação dos
processos (p.ex. Algoritmo de Ricart & Agrawala)
A principal primitiva é o multicast confiável, que fornece uma
abstração (transparência de replicação) que é muito
conveniente para o desenvolvimento de tais aplicações:
Usa-se send(g, msg), e deliver(g, &msg)
g = {p1,p2,...,pn} que pode ter qualquer numero de
membros,
Aplicação não precisa enviar a msg para cada pi e tem
garantia que todos os membros de g receberam a
mensagem.
© Markus Endler
2
Multicast Confiável
Existem diferentes definições para multicast confiável e
muitas possíveis implementações.
Exemplos:
“Se um membro p  g recebe a mensagem, então …
a) …todos os demais membros de g também
receberão a mensagem.”
b) ...todos membros ativos de g e que consideram p
como membro de g também receberão a
mensagem”
c) ...todos os membros alcançáveis durante o multicast
também receberão a mensagem” (Best effort: tentase entregar a mensagem a todos membros)
© Markus Endler
3
Multicast confiável vs. Não-confiável
Multicast confiável tem que ser implementado através de
comunicação ponto-a-ponto.
Apesar de eventualmente existir suporte para
comunicação multiponto em camadas de enlace ou
rede, como por exemplo
– difusão pelo meio (Ethernet), ou
– IP multicast
esta comunicação multi-ponto não fornece quaisquer
garantias de entrega (confiabilidade), devido a:
• possibilidade de particionamento da rede ou falha
permanebte em um enlace
• perda esporádica de pacotes
• atualização do grupo multicast justamente no
momento de uma difusão
© Markus Endler
4
Comunicação de Grupo (CG)
CG é o termo genérico que engloba dois serviços:
comunicação multicast e gerenciamento de grupos
CG geralmente lidam com falhas do tipo:
• falha permanente ou temporária de um ou mais processos do
grupo
• comunicação ponto-a-ponto não-confiável
• partição da rede (grupos desconectados)
Quase nenhuma trata de falhas bizantinas!
© Markus Endler
5
Alguns Sistemas
•
•
•
•
•
•
V System (Cheriton, Zwaenepoel, 85)
Chorus (Rozier et al., 88)
Amoeba (Kaashoek & Tanenbaum, 91)
Trans/Total (Melliar-Smith, 90)
Delta-4 (Powell, 91)
Isis (Birman, 93)
– Sistema de CG monolítico
• Horus (van Renesse et al., 96)
– sistema de CG modular e extensível
• Totem (Moser et al., 96)
• Transis (Dolev & Malki, 96)
• Ensemble (Birman & van Renesse, 01)
– Biblioteca de protocolos & ferramentas de CG
• CORBA Object Group Service (Felber & Guerraoui,98)
© Markus Endler
6
Diferentes Abordagens para CG
Quanto ao direito de comunicação
• Grupos abertos: processos não-membros podem enviar
mensagens multicast para os membros do grupo
• Grupos fechados: para ser capaz de enviar um multicast, um
processo precisa primeiro entrar no grupo (join)
Quanto à organização interna do Grupo
• com coordenador: este faz a difusão de mensagens para os
demais membros
• sem coordenador: todos têm visão idêntica do grupo e fazem
difusão de msgs
Quanto às garantias de entrega e ordenação (mais detalhes
adiante…)
• Ordem FiFO
• Ordem causal
• Ordem total
© Markus Endler
7
Comunicação de Grupo (CG)
Dado que geralmente o serviço de CG provê garantias
(de entrega e ordenação das mensagens) especiais,
existe a distinção entre:
• recepção pela camada de rede/transporte
• entrega da para a camada de aplicação
Principais primitivas para comunicação:
• mcast(group, m)
• deliver(m)
member 1
mcast
deliver
member 2
mcast
deliver
Serviço de CG
send
receive
send
receive
Network/ Communication System
© Markus Endler
8
Uma API típica de CG
P1
P2
P1
P2
P3
P3
group G1
group G1
send
P5
P1
P2
P4
P3
group G1
grp_join(G1)
P4
grp_create(&gid)
grp_delete(gid)
grp_join(gid)
grp_leave(gid)
grp_reorganize(gid)
grp_send(gid, msg)
grp_deliver(gid, &msg)
grp_info(gid, &status)
P4
criação de um novo grupo
remoção do grupo gid
entrada no grupo
saida do grupo
eleição de novo coordenador
envio de msg ao grupo (multicast)
entrega de uma mensagem do grupo
informação sobre o grupo (nº membros,
coordenador, etc.)
 A identificação do Grupo (gid) deve ter o mesmo status de um processID
 Processos devem usar primitivas send e receive convencionais
 Um processo deve poder pertencer a vários grupos simultaneamente
© Markus Endler
9
Ordem de Entrega de Mensagens de Grupo
Possíveis garantias da CG quanto a ordem de entrega das
mensagens (Definições):
• Ordem Qualquer (Any):
Mensagens são entregues em qualquer ordem
• Ordem FIFO:
Se processo P envia mensagem m antes da mensagem m', então
nenhum membro do grupo irá receber m' antes de m
• Ordem Causal:
Se uma mensagem m precede causalmente outra mensagem m' (m
 m'), então nenhum membro irá receber m' antes de m
• Ordem Total:
Se um membro do grupo entrega m antes de m', então todos os
demais membros entregam também m antes de m‘
• Sincronia Virtual:
Se um processo recebe m na visão vN e participa da criação da
visão vN+1, então todos os processos ativos na visão vN+1 também
entregam m antes da instalação da visão vN+1.
© Markus Endler
10
Confiabilidade de Entrega
Possíveis garantias referentes à confiabilidade da entrega das
mensagens (Definições):
• Melhor esforço (best effort):
Mensagem será recebida por todos os membros que estiverem ativos e
puderem receber a mensagem em um dado período de tempo.
• Resiliência de grau k:
Se pelo menos k membros receberam a mensagem, então pelo menos
k membros irão entregar a mensagem.
• Atomicidade não uniforme (non-uniform atomic multicast):
A mensagem será entregue a todos os membros ativos do grupo ou a
nenhum deles. (  sincronia virtual)
• Atomicidade uniforme (uniform failure atomic multicast):
Se um membro do grupo P entregou a mensagem, então ela
necessariamente será também entregue por todos os demais membros
(independente do estado de P).
Note que atomicidade uniforme:
• dá garantia de entrega mesmo que um membro falhe durante o
protocolo  torna-se necessária quando a entrega de uma mensagem
causa efeitos externos ao grupo
© Markus Endler
11
Exemplos
P1
P1
P2
P2
P1 entregou? Também
entregarei!
P3
P3
P1 tá fora!
Oi!
P1 entregou? Também
entregarei!
P4
P4
P1 entregou? Também
entregarei!
• Atomicidade não-uniforme
• Atomicidade uniforme
Entrega a mensagem
© Markus Endler
12
O Protocolo “Flooding”
Ideia central:
• quando um membro do grupo recebe pela primeira vez uma nova
mensagem, difunde esta mensagem para todos as demais
membros e entrega a mensagem para a aplicação
• Dado que cada mensagem tem uma identificação única (sender,
seq_nr), cada processo sabe se já entregou a mesma para a
aplicação
Este protocolo não é eficiente, mas garante que em algum momento
a mensagem será entregue por todos os processos ativos (desde
o início do multicast).
send(g,M):
{
m’.data = M;
set m'.seq_nr = next_nr;
set m'.sender = self;
log.add(m.sender,m.seq_nr)
forall i  GroupMemList send(i,m');
}
© Markus Endler
When received(i,m)  {
if (notbefore(m.sender,m.seq_nr)) {
log.add(m.sender,m.seq_nr)
forall i GroupMemList send(i,m);
deliver(m.data)
}
13
Multicast como Transação
(Commit em 2 Fases)
Outra possibilidade é implementar o multicast como uma transação,
que é confirmada ou abortada, por exemplo usando um 2-PhaseCommit Protocol (com coordenador fixo ou variável)
Obs: Membros e coordenador guardam estado em memória não-volátil
(disco)
© Markus Endler
14
Multicast como Transação
(Comit em 3 fases)
Coord.
Part A
New m
Fase I
ack
commit/abort
Fase II
ack
free
Fase III
© Markus Endler
• Na Fase I, após receber m,
cada participante avisa que
está pronto p/ entrega e guarda
deliverOK &
cópia de m
Save copy
• se coord. falhar após fase I ou
II, outro membro assume o
deliver
papel de coordenador
• Ao receber uma cópia de m,
cada participante novamente
Remove copy
responde
Assim, evita-se a espera
indefinida pelo coordenador.
Mas os participantes precisam
eleger o novo coord.
Part B
15
Problemas da Atomicidade Uniforme
Multicast como Transação 2PC ou 3PC garantem atomicidade
uniforme, mas...
A garantia de atomicidade uniforme impõe restrições maiores do que
são necessárias para muitas aplicações (p.ex. que apenas
requerem a manutenção de estados sincronizados). Exemplo:
• Quando um membro do grupo falha, não só deixará de receber
algumas mensagens, como também não enviará OKs. Logo,
impossibilitará que qualquer multicast seja commited (ausência
de progresso)
 Em vez disto, o coordenador deveria remover o membro falho
e prosseguir com o multicast para os demais processos ativos.
• Para manter estados sincronizados, ao se recuperar de uma
falha, bastaria que o processo fosse re-inicializado com o estado
consistente dos demais membros ativos.
 Isto poderia ser feito solicitando o estado de um membro
ativo, em vez de reprocessar todos os multicasts perdidos
• Se o coordenador falha, todos os membros ficam bloqueados
esperando este se recuperar (pelo menos no 2PC).
© Markus Endler
18
Usando Causalidade para combinar 2PC e Flooding
Se a relação causal entre mensagens puder ser verificada, é
possível definir um protocolo para multicast que é uma
combinação entre flooding e 2PC.
Idéia central: (seja M um multicast e M.Dest a lista de destinatários)
• Pf difunde M para todos Pi  M.Dest
• Pf e todos os processos que receberam M, mantém M em um
buffer até que “obtenham uma confirmação de que M foi recebida
por todos os P  M.Dest”
• Se Pk notar alguma mudança no grupo (p.ex. Falha), retransmite
todas as mensagens no buffer para todos os Pi  M.Dest
• Em vez de esperar Acks diretos de todos os P  M.Dest (como
no 2PC) pode-se usar confirmações (ACKs) indiretas e
transitivas:
– Junto com cada mensagem de multicast, segue “de carona”
(piggyback) um ACK relativo ao multicast mais recente recebido
pelo remetente
– Se um Pi descobre que deixou de receber um M (através do ACK
vindo em um multicast N, ou seja M  N), então Pi adiciona M a sua
negAckList, e envia esta lista junto com futuros multicasts
(solicitando assim o reenvio de M)
© Markus Endler
19
Exemplo
Sejam M.Dest = {A,B,C,D}
• Processo A difunde a
• Processo B difunde b+ack(a)
• Processo C recebe a e b e depois difunde c+ack(b)
• Processo D só recebe c+ack(b):
• Caso não tenha recebido b, pede retransmissão e quando chegar
b+ack(a) e não tiver recebido a, pede retransmissão de a
• Através do recebimento de c+ack(b) e b+ack(a) D pode deduzir
que:
– C recebeu b
// pois recebeu c+ack(b)
– B recebeu a
// pois recebeu b+ack(a)
– C recebeu também a
// pois senão C teria enviado
// c+ack(b)+negAck(a)
• Ou seja, multicast a foi recebido por todos  portanto pode ser
entregue à camada de aplicação e removida do buffer
© Markus Endler
20
O Protocolo Transis
O Protocolo Transis, proposto por Almir et al [ADKM92] se baseia na
transitividade de confirmações.
• Processo somente adiciona Ack(m) a um multicast m´ se tiver
recebido m, e todas as mensagens causalmente precedentes a m.
• A relação de dependência causal entre os multicasts é “descoberta” e
registrada em um grafo direcionado por cada processo através das
AckLists transmitidas em cada mensagem.
• Cada processo mantém um grafo direcionado com as dependências
causais das mensagens não estáveis (para eventual retransmissões)
e para detectar mensagens não recebidas
• Mensagens são sempre retransmitidas com a AckList original
(negAckList não é retransmitida).
Suposições do Modelo de sistema:
– Mensagens possuem identificação (unívoca): (senderID, seqNr)
– entrega de mensagem é FIFO
– Cada mensagem carrega AckList, e possivelmente negAckList
– Processos não falham, mas mensagens podem ser perdidas
[ADKM92] Almir, Dolev, Kramer, Malki, Transis: A communication subsystem for high
availability, Proc. 22th Intl. Symposium on Fault-Tolerant Computing, 76-84, July 92.
© Markus Endler
21
O Protocolo Transis
Variáveis em cada Processo:
• Tipo MSG com campos
– Data
– Acks
– NegAcks
// mensagem da aplicação
// acks
// negAcks
•
•
•
•
Undelivered
// lista de mensagens ainda a entregar
negAckList
// lista de mensagens não recebidas
AckList
// lista de mensagens a confirmar
G
// Grafo direcionado com mensagens não estáveis
(funciona como buffer)
Funções que operam sobre o Grafo:
• G.add(m)
// insere m com lista de confirmações
• G.Not_duplicate(m) // TRUE se m não esta contida em G
• G.causal(m)
// TRUE se todas as mensagens causalmente
precedentes a m tiverem sido recebidas
• G.stable(m)
// TRUE se todos processos tiverem confirmado
o recebimento de m
© Markus Endler
22
Funcionamento do Transis no processo E
1. Recebeu: b+ack(a)
2. Recebeu: c+ack(b,d)
a
a
b
b
AckList = {}
negAckList ={a}
c
AckList = {}
negAckList ={a,d}
3. Recebeu: a
 Entrega a e b
4. Processo E envia e+ack(b)+nack(d)
 Entrega e
a
a
d
b
AckList = {b}
negAckList ={d}
© Markus Endler
d
c
d
b
c
e
AckList = {e}
negAckList ={d}
OBS: Como c ainda não
foi entregue,  (c  e)
23
O Protocolo Transis
Trans_send(message) {
M = new MSG;
M.Data = message;
for every n  negAckList // lista das mensagens a serem retransmitidas
M.NegAcks.add(n)
for every a  AckList { // lista das mensagens a serem confirmadas
AckList.remove(a);
M.Acks.add(a);
}
AckList.add(M);
// proximas mensagens a serem confirmadas
G.add(M);
// adiciona própria mensagem no grafo
for every p  Dest send(p,M);
}
© Markus Endler
24
O Protocolo Transis
When_received(M) => {
for every n  M.NegAcks
if (n  G) for every p  Dest send(p,n); // retransmite mensagens solicitadas
if G.NotDuplicate(M) {
// se M ainda não estiver no grafo
for every a  M.Acks
if (G.NotDuplicate(a)) negAckList.add(a) // detecta msgs ñ recebidas
if (M  negAckList) negAckList.remove(M);
undelivered.add(M);
// adiciona ao buffer
M.negAckList.clear();
// limpa negAckList para armazenamento
G.add(M);
// procura todas mensagens K que já tenha tido todas as causalmente prec entregues
while ( K, K  undelivered  G.causal(K)) {
undelivered.remove(K);
deliver Trans_recv (K.Data);}
// entrega k
AckList = {N  G | G.causal(N)  ( L (G.causal(L)  L  N.AckList) }
// novo AckList apenas mensagens mais recentes N com causal(N)
for every N  G
if G.stable(N) G.remove(N)
}
}
© Markus Endler
25
Linha Causal e Estabilidade
O predicado G.causal define uma região do grafo G
contendo mensagens que podem ser entregues (região
deliverable).
• cada vez que uma mensagem M é recebida, esta é
inicialmente colocada fora da região deliverable.
• Se todas as mensagens em M.AckList estão dentro da
região deliverable, então M é incluído na região e pode
ser entregue à aplicação.
• Se uma mensagem N dentro da região recebeu
confirmações (diretas ou transitivas) de todos os
membros, então ela é estável e pode ser removida de G.
Portanto, a característica de progresso do algoritmo
Transis se traduz no avanço sucessivo da borda da região
deliverable no grafo G.
© Markus Endler
26
Características do Protocolo Transis
Note as seguintes características:
•
•
•
•
Se uma mensagem multicast é entregue a um processo
que não falha, então em algum momento esta
mensagem será entregue a todos os processos não
falhos
Entrega de mensagens é em ordem causal
Todos os processos estarão descobrindo o mesmo
grafo G (que representa a relação causal entre as
mensagens), mas devido a eventuais atrasos e a ordem
distinta de mensagens concorrentes, a ordem em que
esta descoberta do grafo G ocorre, difere de processo
para processo.
Problema: Se um processo falha, o grafo G em cada um
dos processos aumenta sem parar, pois nenhuma msg
será mais estável (podendo ser removida do Grafo)
© Markus Endler
27
Ordenação
Ordenação FIFO pode ser trivialmente incorporada a um
multicast confiável:
•
Basta associar um nr de sequência para cada
remetente e manter nos processos receptores um vetor
contendo o próximo nr de sequência esperado de cada
membro do grupo
Ordenação Causal pode ser facilmente implementada:
•
adicionando-se vector time-stamps aos processos e
mensagens (e fazendo a entrega conforme visto no
início da disciplina)
Ordenação Total: ??
Sincronia Virtual: ??
© Markus Endler
28
CG com Ordem Total
Existem duas classes de algorítmos:
•
Baseado em sequenciador
•
Baseado em consenso
Em ambos os casos:
•
mensagens recebidas são mantidas em um buffer até
que se saiba a sua ordem de entrega,
•
Entrega-se as mensagens com o menor nr de
sequência
© Markus Endler
29
Ordem Total baseada em Sequenciador
Sejam:
•
p,q processos do grupo G
•
Seq um processo singular (Sequenciador) e
•
id um identificador único de um multicast.
Cada membro mantém um contador R (e Seq o contador F)
Ideia central:
•
Todo membro p é inicializado com R=0 (e Seq com F=0)
•
Membro p difunde new(m, id) para q  G
•
ao receber new(m,id), q armazena (m,i) em buffer
•
Quando Seq recebe new(m,id), este difunde mensagem
order(id,F) e faz F++;
•
Ao receber order(i,O):
– Enquanto ( (m,id)  buffer  O = R + 1) então {
deliver(m); R++;}
© Markus Endler
30
Ordem Total baseada em Sequenciador
Exemplo:
F=6
Seq
P1
order(m1,6)
new(m1)
P2
P3
Armazena no buffer
Define ordem total
© Markus Endler
Entrega a mensagem
31
Ordem Total baseada em Consenso
Cada processo q  G mantém dois contadores:
•
A: o maior nr sequência de observado em G
•
P: o maior nr. sequência proposto por q
•
fila de mensagens ordenadas pelo nr de sequencia proposto
Algoritmo para um membro P de G:
•
P difunde new(m, id) para q  G e coloca em uma fila de entrega local
•
ao receber new(m,id) de P, Q armazena (m,id) em buffer e envia para P a
mensagem vote(id,Q,max(P,A)+1) com a sua proposta de nr sequencia para
id
•
P coleta todas as respostas e escolhe o maior nr sequencia proposto A, e
difunde a mensagem order(id, A)
•
Ao receber order(id,F)
–
Seta A = max(A, F)
–
Atribui F como nr de sequência definitivo à mensagem id, e reordena as
mensagens na fila (com nr sequencias crescentes)
–
Pode entregar a mensagem (m,id,F) no início da fila quando:
•
F é nr-sequencia definitivo, e
•
Quando receber order(id2, X) onde X > F
ou seja, F é o menor nr definitivo menor possível
© Markus Endler
32
Ordem Total baseada em Consenso
Exemplo: Envio concorrente de new(m2) e order(m1)
P0
F=6
P=2
P=2
m2
vote(m2,2)
m1
m1
order(m2,6)
P1
P=4
P=5
F=6
F=5
m1
vote(m2,4)
new(m2)
P=4
P2
P3
order(m2,6)
F=6
F=5
m1
order(m1,5)
P=3 F=5
m1
m1
m1
m1
vote(m2,6)
order(m2,6)
F=6
m2
m1
Em P3 m1 só pode ser entregue, após receber order(m2)
em buffer
Entrega
Define seq. definitiva
© Markus Endler
33
Multicast Confiável com Falhas
Note-se que nenhum dos algoritmos anteriores é tolerante a falhas.
Em vez de bloquear o protocolo por causa de uma falha, é mais razoavel
garantir a entrega da mensagem para todos os processos não falhos.
Não garante atomicidade uniforme.
Principal problema da abordagem:
•
é impossível manter uma visão perfeitamente sincronizada dos
processos não falhos, Ou, em outras palavras, o que fazer se durante
um multicast ocorre a falha do emissor? Alguns processos podem
receber, a mensagem e outros não.
Uma abordagem: definir checkpoints e garantir que:
•
para quaisquer processos que executam checkpoints seguidos CPa e
CPb, estes receberão exatamente o mesmo conjunto de mensagens
antes doCPb.
•
checkpoints devem ser executados sempre que houver uma mudança na
configuração do grupo (mudança de visão).
•
Se algum processo não-falho eventualmente não tiver recebido todas as
mensagens, outro processo ativo pode re-transmiti-las a partir de um log
de mensagens recebidas entre os checkpoints
Um Serviço de Pertinência a Grupos informa ao serviço de multicast sobre
mudanças na configuração do grupo  define a lista de destinatários
para o multicast. Esta lista é garantidamente a mesma para todos os
© Markus Endler
34
O Problema de Group Membership
Trata-se de um problema de acordo sobre lista de processos membros
em um grupo de processos cooperantes
Problema: manter uma visão consistente (idêntica) dos membros
ativos na presença de:
• Falhas tipo fail-stop de processos
• Entradas de processos no grupo
• Saida de processos do grupo
• Falhas na comunicação (perda de mensagens, partições de rede)
O Objetivo do Group Membership Service (GMS) é manter a
informação sobre os membros de G que satsifaça as seguintes
propriedades:
Ricciardi, Birman: Consistent Process Membershio in Asynchronous
Environmente, apítulo 13 em Relible Distributed Computing with the Isis
Toolkit, K. Birman R.v. Renesse, IEEE
© Markus Endler
35
Propriedades
Auto inclusão:
Se processo p entra em grupo g, então p é membro de g.
Acordo sobre visão do grupo:
Se processo p e processo q juntam-se ao mesmo grupo
g, então tanto p como p vêem os mesmos membros de g.
Acordo sobre história do grupo:
Todos os processos partilham a mesma história do grupo
(sequência de visões)
© Markus Endler
36
Serviço de Pertinência (Group Membership Service)
Objetivo:
•
Fazer com que todos os processos ativos mantenham uma visão
idêntica do conjunto atual de membros não-falhos.
•
A cada vez que o conjunto de membros muda, instala-se uma nova
visão do grupo (evento view).
Exemplo:
V1={P1,P2}
V2={P1,P2,P3}
P1
P2
V3={P2,P3}
Join(P3)
P3
Rem(P1)
Requisito: Todos os processos ativos no estabelecimento de uma nova
visão vN devem concordar sobre os membros de vN.
© Markus Endler
37
Group Membership Service
• Cada instância do GMS executa um detector de falhas, que pode
suspeitar da falha de um membro do grupo, f
• Usa-se 2PC para avisar e recolher confirmações da maioria dos
demais membros ativos. Seja C o processo que coordena o processo
de mudança de visão. Qualquer processo pode suspeitar também da
falha do coordenador C (e nesse caso inicia a eleição de novo
coordenador)
C
Sub(-f)
leave(f)
Com(-f)
P2
P3
Suspect(f)
F
Sub(-f) :: anuncia/propõe a remoção de f
Com(-f):: acordo sobre remoção de f
© Markus Endler
38
Group Membership Service
• Quando um novo membro, H, deve ser incorporado (sugestão por
algum processo que detectou atividade de H) o coordenador C envia
também uma mensagem de transferência de estado para o novo
membro, para que ele esteja sincronizado com o grupo.
C
Sub(+h)
Com(+h)
Join(+h)
P2
P3
h is alive
S-transf(g)
h
© Markus Endler
Sub(+h) :: anuncia/propõe a inclusão de h
Com(+h):: confirmação da inclusão de h
S-transf (g) :: cópia do estado de g para h
39
Modelo de Sincronia Virtual
(Virtual Synchrony Model)
Sejam os eventos:
mcast(g,m), deliver(m), e view(g)
Intuitivamente:
• Um sistema implementa sincronia virtual se os eventos
que ocorrem localmente em cada processo parecem
ocorrer simultaneamente em todos os processos do
grupo.
• Ou: A história real de ocorrência dos eventos é
indistinguível (para a aplicação) da história de
ocorrência simultânea dos eventos.
Principal vantagem para a aplicação:
não precisa se preocupar com concorrência entre
multicasts e mudanças de visão (todos membros ativos
terão visões consistentes da ordem relativa entre estes
dois tipos de eventos)
© Markus Endler
40
Modelo de Sincronia Virtual
mb
P1
ma
P2
P3
md
mc
P4
Ordens de entrega:
• P1/2:
• P3:
• P4:
© Markus Endler
del(ma); del(mb); del(mc);view(g); del(md)
del(ma); del(mc); del(mb);view(g); del(md)
view(g); del(md)
41
Virtual Synchrony Model
Alguns sistemas de CG garantem a entrega de mensagens no grupo consistente
com as mudanças de visão no grupo:
A entrega de mensagens View Syncronous:
• Todos os membros de um grupo recebem mensagens idênticas entre duas visões
consecutivas de um grupo
• Todas as mensagens são entregues na visão em que foram geradas
• Ordem de entrega (dentro de uma visão) pode ser fifo, causal, ou total, mas não
podem haver lacunas no recebimento de mensagens
• requer um "protocolo flush" para que as mensagens das difusões inciadas sejam
entregues antes da instalação da nova visão do grupo (esta é a mensagem de
confirmação de mudança de visão).
© Markus Endler
42
Flush Protocol
• Usa-se as mensagens de confirmação (ack), para indicar quais
mensagens naquela visão cada membro recebeu.
• Coordenador compara as listas, e usa Com() para difundir a lista total
de mensagens que precisam ser entregues antes do estabelecimento
da nova visão.
MsgsC
C
Sub(-f)
leave(f)
P2
Com(-f) +
MsgsC MsgsP2
MsgsP3
MsgstP2
MsgstP3
MsgExchg
P3
Suspect(f)
F
MsgExchg:: troca de mensagens que outro não recebeu
© Markus Endler
43
Virtual Synchrony Model
Características do Virtual Synchrony Model:
• Todos os membros enxergam uma sequência identica de visões
• Entrega de mensagens é segundo a ordem "view synchronous": os membros
remanescentes do grupo recebem o mesmo conjunto de mensagens (sem
omissões), de acordo com a ordenação (fifo ou causal)
• Difusão de mensagens pode prosseguir em paralelo com a mudança de visão
do grupo
• Não garante consistência uniforme
Vantagens:
 Muitas aplicações só requerem a consistência interna (atomicidade fraca):
Ex: Escolha de um coordenador, coordenação no acesso a recursos
compartlhados
 Muitas aplicações só requerem atomicidade com relação as falhas, que
justamente é obtida através do Virtual Synchrony Model
 Virtual Synchronous Model é bem mais barato do que ordem total de entrega
© Markus Endler
44
Arquiteturas de Sistemas de CG
A maioria dos serviços de grupo consistem de módulos
(mais ou menos explícitos) que implementam tarefas específicas. A
tendência são arquiteturas de micro-protolos configuráveis.
Atomic Multicast
Recovery
Membership +VS
View Synchrony
Atomic Multicast
Failure Detect.
Membership
Membership
Stability
Unreliable FD
Unreliable FD
Reliable Comm.
Isis
Ensemble
Totem
ORB
Membership
TO Multicast
Consensus
Reliable Multicast
Failure Detect.
© Markus Endler
Reliable Comm.
OGS
45
Conclusão
• Multicast Confiável tem sido usado em aplicações que requerem alto
grau de confiabilidade e tolerância à falhas (redundância de
hardware)
• Suas abstrações facilitam muito a implementação de aplicações
• O maior problema é a escalabilidade do serviço, especialmente
quando o serviço garante sincronia virtual (ou ordenação total)
• Os sistemas com maior sucesso foram os que apresentaram maior
flexibilidade de configuração, podendo ser adaptadas aos requisitos
específicos (desempenho, confiabilidade, numero de máquinas, etc.)
de cada aplicação;
Há duas tendências/alternativas:
• Algoritmos probabilisticos para multicast, que:
– dão garantias equivalentes às soluções deterministicas a um custo
muito menor, e apresentam boa escalabilidade
• Algoritmos de Gossiping
– Difusão eventual e parcial de mensagens, alta latência, porém
escalável
© Markus Endler
46