Sistemas Distribuı́dos e Exclusão Mútua
Tolerante a Falhas
Luiz A. Rodrigues
UNIOESTE/UFPR/LIP6/INRIA
[email protected]
5 de abril de 2013
CiPET - UNIOESTE - Cascavel
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
1 / 33
Luiz A. Rodrigues
1
Interesses
Redes de Computadores, Tolerância a Falhas, Sistemas Distribuı́dos e
Programação de Sistemas
2
Formação
Bacharelado em Informática (UNIOESTE - 1999/2003)
Tı́tulo: Uma Ferramenta para Comparação dos Mecanismos de
Controle de Congestionamento em Redes TCP/IP Utilizando o NS
Mestrado em Ciência da Computação (UFRGS - 2004/2006)
Tı́tulo: Extensão do Suporte para Simulação de Defeitos no Neko
Doutorado em Informática (UFPR - 2010/atual)
Tema: Exclusão Mútua em Sistemas Distribuı́dos
Sanduı́che no LIP6 (UPMC - Paris)
3
Atuação
1
2
CELEPAR (2006-2007) - Área técnica de Redes de Computadores
UNIOESTE (2007-atual) - Professor na área de Redes de
Computadores
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
2 / 33
Sistema Distribuı́do
Definição: Um Sistema Distribuı́do
(SD) é um conjunto de processos que
se comunicam usando troca de
mensagens
A
Objetivo: Cooperação para realização
de uma tarefa especı́fica
Tarefas: Sistemas bancários, comércio
eletrônico, sistemas operacionais, banco
de dados, etc.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
B
C
D
E
5 de abril de 2013
3 / 33
Caracterı́sticas Importantes de um SD
Compartilhamento de Recursos: hardware e software
Escalabilidade: atende um único usuário, uma empresa, uma cidade,
o mundo todo
Transparência: usuário não precisa saber se o sistema é centralizado
ou distribuı́do
Confiabilidade: confiança no serviço ou tolerância a falhas
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
4 / 33
Tolerância a Falhas
“Organizações e suas redes tem se tornado indistinguı́veis”
Um sistema Tolerante a Falhas funciona corretamente mesmo que
alguns dos seus componentes estejam falhos
Taxonomia de Falhas:
Defeito
Erro
Falha
Figura: Taxonomia de Falhas
Falha (fault): componente apresenta
comportamento fora da especificação (nı́vel
fı́sico)
Erro (error ): falha é ativada e o componente
produz uma saı́da fora da especificação (nı́vel
da informação)
Defeito (failure): o erro se propaga para a
saı́da do sistema (nı́vel do usuário)
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
5 / 33
Classificação de Falhas
Parada (crash): o componente não
produz saı́da
Omissão: o componente produz saı́da
para algumas entradas, mas não todas
Bizantinas
Temporização
Omissão
crash
Temporização: o componente
responde cedo demais ou tarde demais
(sistemas de tempo real)
Bizantinas: comportamento arbitrário
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
Figura: Classes de Falhas
5 de abril de 2013
6 / 33
O Consenso
C
At
!
Tr
a
Recuar!
T1
id
or
T2
C
X
Tr
a
id
or
L
V
X
Tr
a
T2
X
(X,L,V)
id
or
L
T1
L
Todos os generais leais executam a
mesma ordem
Se o comandante é leal, todos os
tenentes leais executam a sua ordem
Para f traidores, N ≥ 3f + 1
ar
ac
ac
ar
!
At
No consenso processos não falhos
devem entrar em acordo sobre a
execução de uma tarefa;
Algoritmo dos Generais Bizantinos1 ;
V
V
(X,L,V)
T3
(X,L,V)
1
Lamport, L., Shostak, R. e Pease, M. (1982) “The Byzantine Generals
Problem”. ACM Trans. Program. Lang. Syst. 4(3):382-401.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
7 / 33
Modelos de SD
Sı́ncronos: limite de tempo máximo conhecido para execução de
tarefas e transmissão de mensagens
Consenso é possı́vel mesmo com falhas arbitrárias
Assı́ncronos: limites não existem!
Impossibilidade FLP1 : o consenso é impossı́vel para falhas de sequer
um único processo
Detectores de defeitos não-confiáveis2
Parcialmente Sı́ncronos3 : limites existem mas não são conhecidos.
GST: Global Stabilization Time
O consenso é possı́vel se a maioria dos processos é sem-falha
1
Fischer, M., Lynch, N. e Paterson, M. (1985) “Impossibility of Distributed
Consensus with one Faulty Process”. J. ACM. 32(2):374-382.
2
Chandra, T. D. e Toueg, S. (1996) “Unreliable Failure Detectors for
Reliable Distributed Systems”. J. ACM. 43(2):225-267.
3
Dwork, C., Lynch, N., and Stockmeyer, L. (1988). “Consensus in the
Presence of Partial Synchrony ”. J. ACM, 35(2):288-323.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
8 / 33
Roteiro
1
Exclusão Mútua em Sistemas Distribuı́dos
Abordagens
Métricas de Avaliação de Desempenho
Algoritmos de 1-Exclusão Mútua
Algoritmos de k-Exclusão Mútua
2
Uma Solução Robusta para k-Exclusão Mútua
Motivação
Estratégia de Monitoramento
Algoritmo de Disseminação
Solução Proposta
3
Desafios Futuros
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
9 / 33
Roteiro
1
Exclusão Mútua em Sistemas Distribuı́dos
Abordagens
Métricas de Avaliação de Desempenho
Algoritmos de 1-Exclusão Mútua
Algoritmos de k-Exclusão Mútua
2
Uma Solução Robusta para k-Exclusão Mútua
Motivação
Estratégia de Monitoramento
Algoritmo de Disseminação
Solução Proposta
3
Desafios Futuros
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
10 / 33
Exclusão Mútua em Sistemas Distribuı́dos
Como organizar o acesso aos recursos compartilhados por um SD?
Segurança (safety ): nada de errado acontece
Progressão (liveness): algo de bom acontece
Duas Abordagens1
Pedido de Permissão
1
Passagem de token
Processo deve solicitar a
permissão aos demais
Mensagem especial (token) é
repassada entre os processos
Solicitante deve aguardar
respostas de todos ou de um
conjunto (quórum)
Processo que detém o token
pode acessar o recurso
Variação: k-exclusão mútua → k recursos compartilhados
Raynal, M. (1991). “A Simple Taxonomy for Distributed Mutual Exclusion
Algorithms”. SIGOPS Oper. Syst. Rev., 25(2):47-50.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
11 / 33
Métricas de Avaliação de Desempenho
Complexidade de Mensagens
Tolerância a Falhas
Atraso de Sincronização (SD)
Disponibilidade
Tempo de Resposta
throughput: 1/(SD + E )
Carga Baixa
1
Carga Alta
pi envia
requisições
pi obtém
recurso
pi libera
recurso
pj obtém
recurso
tempo
Tempo de Execução
Atraso de Sincronização
Tempo de Resposta
1
E =tempo médio de utilização do recurso por cada processo
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
12 / 33
Principais Soluções de Exclusão Mútua
1
Pedido de Permissão
Algoritmo de Lamport
Algoritmo de Ricart-Agrawala
Algoritmo de Maekawa
2
Passagem de token
Algoritmo de Suzuki-Kassami
Algoritmo de Raymond
3
Soluções de k-Exclusão Mútua
Algoritmo de Raymond
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
13 / 33
Algoritmo de Lamport1
Solicitante envia broadcast e aguarda n − 1 respostas
Fila local ordenada por timestamps controla prioridade
Solicitante acessa recurso quando:
Recebeu uma mensagem com timestamp maior que o seu de todos os
demais
A sua solicitação é a primeira da fila
1
2
Ao liberar o recurso, envia RELEASE a todos
Total de mensagens: 3(n − 1)
REQUEST
p1 obtém
recurso
p1
[(1,1)]
[(1,1),(2,1)]
p1 libera p2 obtém
recurso recurso
p2 libera
recurso
REPLY
[(2,1)]
[]
RELEASE
(1,1)
(2,1)
p2
p3
[(2,1)]
[(2,1)]
[(1,1),(2,1)]
[(1,1), (2,1)]
[(2,1)]
[(2,1)]
[]
[]
1
Lamport, L. (1978) “Time, Clocks and the Ordering of Events in a
Distributed System”. Commun. ACM. 21(7):558-565.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
14 / 33
Algoritmo de Ricart-Agrawala1
Otimização do Algoritmo de Lamport
Envia requisição e aguarda n − 1 respostas
Respostas são adiadas se processo que recebe requisição está utilizando
o recurso ou tentando obtê-lo com maior prioridade
Total de mensagens: 2(n − 1)
p1
(1,1)
p1 retém
resposta para p2
p1 obtém
recurso
p1 libera
recurso
p2 obtém
o recurso
(2,1)
p2
p3
1
Ricart, G., Agrawala, A. k. (1981) “An Optimal Algorithm for Mutual
Exclusion in Computer Networks”. Commun. ACM. 24(1):9-17.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
15 / 33
Algoritmo de Maekawa1
Solução baseada em quóruns (conjuntos de processos com elementos
em comum)
Solicita permissão apenas para os processos do quórum
√
Total de mensagens: 3 n
6
1
4
7
Bloqueado por p1,
na fila
C1={1,2,4}
C2={2,3,5}
C3={3,4,6}
C4={4,5,7}
C5={5,6,1}
C6={6,7,2}
C7={7,1,3}
3
5
3
2
Bloqueado
5
(a) Plano projetivo de Fano
(b) Exemplo
1
√
Maekawa, M. (1985) “A N Algorithm for Mutual Exclusion in
Decentralized Systems”. ACM Trans. Comput. Syst. 3(2)145-159.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
16 / 33
Algoritmo de Suzuki-Kasami1
Cada processo i mantém localmente:
Número de sequência sni
Vetor de requisições RNi
Solicitação de recurso
1
2
3
Incrementar sni
Enviar broadcast REQUEST(i,sni )
Aguardar o token
token mantém
Vetor LN
Fila de requisições pendentes
Quando libera recurso, processo envia token para o próximo na fila
Total de mensagens por requisição: n
1
Suzuki, I., Kasami, T. (1985) “A Distributed Mutual Exclusion
Algorithm.”. ACM Trans. Comput. Syst., 3(4):344-349
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
17 / 33
Algoritmo de Raymond1
Utiliza estrutura lógica de árvore
Cada processo i mantém localmente
Atributo HOLDER
Fila Qi de requisições pendentes
2
2
1
4
3
6
5
(c) token em p1
2
1
4
3
6
5
(d) token em p4
1
4
3
6
5
(e) token em p6
1
Raymond, K. (1989) “A Tree-Based Algorithm for Distributed Mutual
Exclusion”. Trans. Comput. Syst., 7:61-77.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
18 / 33
Algoritmo de Raymond1
Solução para o problema da k-exclusão mútua
Baseada no algoritmo de Ricart e Agrawala
Envia requisição aos n − 1 outros processos e aguarda por, no mı́nimo,
n − k respostas
Tolera k − 1 falhas, mas cada falha degrada a solução
p1 obtém
recurso
p1
p2
p3
p2 obtém
recurso
(1,1)
p1 libera
recurso
p2 libera
recurso
x
(2,2)
p3 obtém
o recurso
(3,3)
1
Raymond, K. (1989) “A Distributed Algorithm for Multiple Entries to a
Critical Section”. Inf. Process. Lett., 30:189-193.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
19 / 33
Roteiro
1
Exclusão Mútua em Sistemas Distribuı́dos
Abordagens
Métricas de Avaliação de Desempenho
Algoritmos de 1-Exclusão Mútua
Algoritmos de k-Exclusão Mútua
2
Uma Solução Robusta para k-Exclusão Mútua
Motivação
Estratégia de Monitoramento
Algoritmo de Disseminação
Solução Proposta
3
Desafios Futuros
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
20 / 33
Uma Solução Robusta para k-Exclusão Mútua
Solução tolerante a falhas de k-exclusão mútua distribuı́da baseada
no modelo com permissão de Raymond
Aumenta a eficiência para até n − 1 processos falhos
Suporte utilizado
1
2
Estratégia de Monitoramento
Mecanismo de disseminação de mensagens
Resultados publicados em:
Rodrigues, L. A., Duarte, E. e Arantes, L. Exclusão Mútua Distribuı́da
e Robusta para k Recursos Compartilhados. SBRC 2012 - WTF, Ouro
Preto, MG, abril de 2012.
Rodrigues, L. A., Cohen, J., Duarte, E. e Arantes, L. A Robust
Permission-Based Hierarchical Distributed k-Mutual Exclusion
Algorithm. ISPDC’13, Bucharest, Romênia, jun. 2013.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
21 / 33
Algoritmo Hi-ADSD
Hierarchical Adaptive Distributed System-Level Diagnosis 1
Testes são executados seguindo um hipercubo virtual
Nodos são agrupados em clusters
0
1
001
000
2
100
4
110
6
010
101
3
011
5
7
0
1
4
5
2
3
6
7
111
1
Duarte, E. P. E Nanya, T. (1998) “A Hierarchical Adaptive Distributed
System-Level Diagnosis Algorithm”. IEEE Trans. on Comp. 47(1):34-45.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
22 / 33
Algoritmo Hi-ADSD (cont.)
Nodos testam o cluster até encontrar um nodo sem falha ou até
testar todos os nodos como falhos
4
3
0
1
1
4
5
3
6
7
2
2
Intervalo de detecção: log N
Quantidade de mensagens por rodada: N log N
Latência de diagnóstico: log2 N
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
23 / 33
Broadcast no processo pi
Tarefa 1: Initiator
send mensagem hs, msg i para o primeiro processo correto pj (se
existe) em cada cluster ci ,s , s = 1, .., log 2 n
2: espera por todos os acks
1:
3:
4:
5:
6:
7:
8:
Tarefa 2: Outros processos
receive mensagem hs ′ , msg i do processo pj
se msg é nova, deliver a mensagem para a aplicação
send hs, msg i para o primeiro processo correto pk (se existe) em cada
cluster ci ,s , s = 1, .., s ′ − 1
espera por todos os acks
send ack para pj
Executado por todos os processos
se a falha do processo pk é detectada, para cada ack pendente de pk ,
retransmitir a mensagem para o próximo processo correto no mesmo
cluster de pk (se existe)
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
24 / 33
Detalhando o Algoritmo - Funções
clusteri (j) =s
neighbori (s) =j
1
2
s=1
neighborhoodi ={j | j ∈ neighbori (s),
4
1
1 ≤ s ≤ d}
2
s=3
neighborhoodi (j) ={k | k = neighbori (s),
6
1 ≤ s < clusteri (j)}
1
7
cluster4 (0) =3
cluster1 (0) =1
neighbor4 (1) =5
neighbor4 (2) =6
neighbor4 (3) =0
3
neighborhood0 ={1, 2, 4}
neighborhood1 (0) =∅
neighborhood2 (0) ={3}
neighborhood4 (0) ={5, 6}
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
25 / 33
Exemplo de Disseminação
0
0
1
2
3
s=1
4
4
1
2
s=3
6
6
1
7
7
(f) sem-falhas
(g) nodo 4 falho
Figura: Árvore geradora no hipercubo de 3 dimensões.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
26 / 33
Algoritmo de k-Exclusão Mútua Proposto
Adaptação do algoritmo de Raymond
Objetivo: aumentar a eficiência em cenários com falhas
Principais modificações:
1
2
3
Aguardar REPLY de, no mı́nimo, n − k − f , f total de processos falhos
Verificar estado do processo emissor antes de processar mensagens
recebidas
Quando ocorre falha, ajusta total de mensagens recebidas se processo
que falhou já havia enviado REPLY
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
27 / 33
Avaliação Experimental - Cenário 1
16 processos (n = 16)
5 cópias do recurso (k = 5)
2
(2,1)
2
3
3
(2,2)
0
(1,1)
0
1
1
(4,4)
10
11
(4,2)
(4,1)
(4,3)
(4,2)
15
14
14
12
13
12
10
8
9
8
(4,1)
(4,1)
11
9
(4,1)
15
13
(3,3)
6
6
7
(3,1)
7
(3,2)
4
5
(a) ligações lógicas
4
(3,1)
5
(b) árvore a partir de
n0
Figura: Hipercubo de 4 dim. e a árvore quando todos os nodos estão sem-falha.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
28 / 33
Avaliação Experimental - Resultados
400
Algoritmo de Raymond
Algoritmo Proposto
Algoritmo Proposto + Monitoramento
50
70
350
Mensagens enviadas
300
250
200
150
100
50
0
0
5
10
15
20
25
30
35
40
45
55
60
65
75
80
85
90
95
100
Tempo
(a) Total de Mensagens
5
Algoritmo Proposto
Algoritmo de Raymond
Recursos em uso
4
3
2
1
0
0
5
10
15
20
25
30
35
40
45
50
55
60
65
70
75
80
85
90
95
100
Tempo
(b) Eficiência
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
29 / 33
Avaliação Experimental - Cenário 2
2
3
4
Variação na quantidade de processos
k = 3 recursos compartilhados
Carga alta: todos solicitam recursos
RAY e BAS usam todos-para-todos; PROPO usa spanning-tree
Total of Resources Allocated
3000
RAY
BAS
PROPO
2500
# Resources allocated
1
2000
1500
1000
500
0
8
16
32
64
# Processes
128
256
512
Figura: Recursos alocados
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
30 / 33
Roteiro
1
Exclusão Mútua em Sistemas Distribuı́dos
Abordagens
Métricas de Avaliação de Desempenho
Algoritmos de 1-Exclusão Mútua
Algoritmos de k-Exclusão Mútua
2
Uma Solução Robusta para k-Exclusão Mútua
Motivação
Estratégia de Monitoramento
Algoritmo de Disseminação
Solução Proposta
3
Desafios Futuros
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
31 / 33
Desafios Futuros
1
Soluções com menor latência e escalabilidade
2
Outras aplicações: Reliable Broadcast, Publish/Subscribe, etc.
Viabilidade em Redes dinâmicas
3
MANETs, VANETs, redes de sensores
Mobilidade gera o caos!
Redes móveis herdam todos os problemas das redes cabeadas e sem-fio
e adicionam outros
Roteamento, energia, segurança, qualidade de serviço, diagnóstico, etc.
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
32 / 33
Perguntas?
Merci!
Nossos computadores estão fora
do ar, e por isso estamos fazendo
tudo manualmente...
Luiz A. Rodrigues
[email protected]
Luiz A. Rodrigues (UNIOESTE/UFPR/LIP6/INRIA [email protected]
Sis. Distr. e Mutex
)
5 de abril de 2013
33 / 33