Algoritmos para Sistemas de
Quóruns Bizantinos
Algoritmo
Multi-Writer Multi-Reader seguro
PUC-PR / PPGIA
Mestrado em Informática Aplicada
Sergio R. Loest
[email protected]
Organização da Apresentação
Introdução
Conceitos Básicos
Tipos de BQS
Funções Básicas
Estrutura Geral dos Algoritmos para BQS
Algoritmos para BQS
Referências Bibliograficas
13/2/2007
PPGIA - PUCPR
2/61
Introdução
Serviço de armazenamento distribuído
através da execução de leituras e escritas de
dados em diferentes conjuntos de servidores
(quóruns) que mantém réplicas (servidores)
em comum
Considera a possibilidade de faltas por
parada e faltas bizantinas nos servidores
13/2/2007
PPGIA - PUCPR
3/61
Introdução
Comunicação ponto-a-ponto [8]
Arquitetura cliente-servidor
Servidor mantém um registrador r
Operações r.write(v) e r.read()
Operações são invocadas remotamente por clientes
Servidores corretos só permitem atualização dos
registradores via protocolos definidos
13/2/2007
PPGIA - PUCPR
4/61
Introdução
Garantia de consistência e disponibilidade
mesmo na ocorrência de falhas bizantinas
em algumas de suas réplicas
Servidores organizam-se em subconjuntos
denominados quóruns
Cada par de quóruns mantém um número
suficiente de servidores corretos em comum
(consistência) [1]
13/2/2007
PPGIA - PUCPR
5/61
Introdução
Existe pelo menos um quórum formado
somente por servidores corretos
(disponibilidade) [2]
Quoruns simétricos => quoruns de leitura e
escrita de mesmo tamanho
Quoruns assimétricos => quoruns de leitura
e escrita de tamanhos diferentes
13/2/2007
PPGIA - PUCPR
6/61
Introdução
Bom desempenho e escalabilidade
Não requer acordo entre as réplicas => não
são suscetíveis à impossibilidade FLP
Somente implementam operações de escrita
e leitura [4]
13/2/2007
PPGIA - PUCPR
7/61
Conceitos Básicos
Modelo de sistema
Sistema formado por dois conjuntos:
servidores - conjunto U
clientes - conjunto Π
Sistema de quorum Q é um conjunto não
vazio de subconjuntos de U (Q ⊆ 2U) [5]
Até ƒ servidores podem falhar
13/2/2007
PPGIA - PUCPR
8/61
Conceitos Básicos
Registradores
Clientes acessam uma variável χ
armazenada em um registrador replicado em
um conjunto U de servidores
A variável χ é um par (valor,timestamp)
Dados auto-verificáveis - assinatura
criptográfica
Dados genéricos - não são digitalmente
assinados
13/2/2007
PPGIA - PUCPR
9/61
Conceitos Básicos
Registradores
Níveis de acesso:
semântica “único escritor”
semântica “vários escritores”
Semântica de consistência:
13/2/2007
semântica segura - leitura com escrita
concorrente pode resultar em qualquer valor
PPGIA - PUCPR
10/61
Conceitos Básicos
Registradores
Semântica de consistência (cont.):
13/2/2007
semântica regular - semântica segura + leitura
com escrita concorrente pode resultar no último
valor escrito ou um dos valores sendo escritos
semantica atômica - semântica regular +
ordenação de leituras e escritas segundo a
relação happens before (→)
PPGIA - PUCPR
11/61
Tipos de BQS
Sistema f-mascaramento
armazenamento de dados genéricos
uso de quoruns simétricos
servidores na interseção 2ƒ + 1
número de servidores n ≥ 4ƒ + 1
quoruns com no mínimo 3ƒ + 1 servidores
13/2/2007
PPGIA - PUCPR
12/61
Tipos de BQS
Sistema f-disseminação
similar a f-mascaramento
armazenamento de dados auto-verificáveis
servidores na interseção ƒ + 1
número de servidores n ≥ 3ƒ + 1
quoruns com no mínimo 2ƒ + 1 servidores
13/2/2007
PPGIA - PUCPR
13/61
Tipos de BQS
Sistema a-mascaramento
armazenamento de dados genéricos
quoruns assimétricos
apenas quoruns de leitura cumprem com requisito
de disponibilidade
servidores na interseção 2ƒ + 1
número de servidores n ≥ 3ƒ + 1
quoruns de leitura com 2ƒ + 1 servidores
quoruns de escrita com 3ƒ + 1 servidores
13/2/2007
PPGIA - PUCPR
14/61
Tipos de BQS
Sistema a-disseminação
armazenamento de dados auto-verificáveis
quoruns assimétricos
quoruns de escrita não cumprem com requisito de
disponibilidade, apenas de leitura
servidores na interseção ƒ + 1
número de servidores n ≥ 2ƒ + 1
quoruns de leitura com ƒ + 1 servidores
quoruns de escrita com 2ƒ + 1 servidores
13/2/2007
PPGIA - PUCPR
15/61
Tipos de BQS
Sistemas “mínimos”
similar ao a-mascaramento
apenas quoruns de escrita cumprem com
requisito de disponibilidade
quoruns de leitura com 3ƒ + 1 servidores
quoruns de escrita com 2ƒ + 1 servidores
13/2/2007
PPGIA - PUCPR
16/61
Funções Básicas
Consulta em um Quorum
Dados sem assinaturas
function query(q)
1:∀s ∈ U, send (s,〈QUERY〉)
2:S[1. . .n]←⊥
3:repeat
4: wait receive (s,〈QUERY-RESPONSE, 〈vs, ts〉〉)
5: S[s]←〈vs, ts〉
6: until #⊥S=n-q
7: return S
end function
13/2/2007
PPGIA - PUCPR
17/61
Funções Básicas
Consulta em um Quorum
Dados com assinaturas
function query_w_sign (q)
1:∀s ∈ U, send (s,〈QUERY〉)
2:S[1. . .n]←⊥
3:repeat
4: wait receive (s,〈QUERY-RESPONSE, 〈vs, ts〉,proof〉)
5: if valid 〈〈vs, ts〉,proof〉 then
6:
S[s] ←〈vs, ts〉
7: end if
8: until #⊥S=n-q
9:return S
end function
13/2/2007
PPGIA - PUCPR
18/61
Estrutura Geral dos Algoritmos
para BQS - leitura
(a) passo de consulta (QUERY/QUERY-RESPONSE)
(b) passo pós-consulta (SOME-ACTION)
(c) passo de devolução (RETURN)
13/2/2007
PPGIA - PUCPR
19/61
Estrutura Geral dos Algoritmos
para BQS - escrita
(a) consulta a um quorum de leitura (possível) +
cálculo de timestamp
(b) passo de escrita (UPDATE)
(c) (opcional) passo de confirmação (ACK)
13/2/2007
PPGIA - PUCPR
20/61
Algoritmos para BQS
Algoritmos para BQS Simétricos
Clientes Corretos
Clientes faltosos
13/2/2007
MWMR Seguro
MWMR Regular
MWMR Atômico
SWMR Seguro
MWMR Seguro
MWMR Atômico
PPGIA - PUCPR
21/61
Algoritmos para BQS (cont.)
Algoritmos para BQS Assimétricos
Clientes Corretos
MWMR Seguro
MWMR Regular
Sistemas com Quoruns Mínimos
Clientes Corretos
13/2/2007
MWMR Atômico
MWMR Regular
PPGIA - PUCPR
22/61
Algoritmos para BQS (cont.)
Sistemas com Quoruns Mínimos (cont.)
Clientes Faltosos
13/2/2007
MWMR Atômico
MWMR Regular
PPGIA - PUCPR
23/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR seguro
quoruns de leitura e escrita de mesmo
tamanho
não tolera clientes faltosos
algoritmos de leitura e escrita em sistema
f-mascaramento
semântica de consistência alcançada é
multi-writer multi-reader segura
13/2/2007
PPGIA - PUCPR
24/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR seguro
Escrita de um cliente c
13/2/2007
PPGIA - PUCPR
25/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR seguro
Leitura de um cliente c
13/2/2007
PPGIA - PUCPR
26/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR seguro
Execução de um servidor s
13/2/2007
PPGIA - PUCPR
27/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR seguro
Complexidade de mensagens - O(n)
4 passos para escrita (seguro para ƒ -1) [7]
13/2/2007
PPGIA - PUCPR
28/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR seguro
Complexidade de mensagens - O(n)
2 passos para leitura (seguro para ƒ -1)
13/2/2007
PPGIA - PUCPR
29/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR regular
quoruns de leitura e escrita de mesmo tamanho
não tolera clientes faltosos
algoritmos de leitura e escrita em sistema
f-disseminação
clientes corretos são responsáveis pela assinatura
dos dados armazenados
semântica de consistência alcançada é multi-writer
multi-reader regular
13/2/2007
PPGIA - PUCPR
30/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR regular
Para cada cliente usa um par de chaves
criptográficas
chave privada => assinatura de suas informações nas
operações de escrita em um quórum
chave pública => verificação das informações assinadas
por aquele cliente nas operações de leitura dos clientes
os clientes devem conhecer as chaves públicas uns
dos outros => afeta a escalabilidade do sistema
13/2/2007
PPGIA - PUCPR
31/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR regular
Escrita de um cliente c
procedure write(ν)
1:S ←query(|Q|)
2:max_ts ←max{S[].ts}
3:t ←min{tc ∈ Tc:max_ts < tc}
4:∀s ∈ U, send (s,〈UPDATE,〈ν,t〉c 〉)
5:wait receive (q,〈ACK〉), ∀q ∈ Q’
end procedure
13/2/2007
PPGIA - PUCPR
32/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR regular
Leitura de um cliente c
13/2/2007
PPGIA - PUCPR
33/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR regular
Execução de um servidor s
13/2/2007
PPGIA - PUCPR
34/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR regular
Complexidade de mensagens:
13/2/2007
executam com complexidade de troca de mensagens de
O(n)
As operações de escrita e leitura realizam-se,
respectivamente, em 4 e 2 passos de comunicação
PPGIA - PUCPR
35/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR atômico
quoruns de leitura e escrita de mesmo tamanho
não tolera clientes faltosos
algoritmos de leitura e escrita em sistema
f-disseminação
clientes corretos são responsáveis pela assinatura
dos dados armazenados
semântica de consistência alcançada é multi-writer
multi-reader atômica
13/2/2007
PPGIA - PUCPR
36/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR atômico
Para cada cliente usa um par de chaves
criptográficas
chave privada => assinatura de suas informações nas
operações de escrita em um quórum
chave pública => verificação das informações assinadas
por aquele cliente nas operações de leitura dos clientes
os clientes devem conhecer as chaves públicas uns
dos outros => afeta a escalabilidade do sistema
13/2/2007
PPGIA - PUCPR
37/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR atômico
Escrita de um cliente c (idêntica a regular)
procedure write(ν)
1:S ←query(|Q|)
2:max_ts ←max{S[].ts}
3:t ←min{tc ∈ Tc:max_ts < tc}
4:∀s ∈ U, send (s,〈UPDATE,〈ν,t〉c 〉)
5:wait receive (q,〈ACK〉), ∀q ∈ Q’
end procedure
13/2/2007
PPGIA - PUCPR
38/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR atômico
Leitura de um cliente c
13/2/2007
PPGIA - PUCPR
39/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR atômico
Execução de um servidor s
13/2/2007
PPGIA - PUCPR
40/61
Algoritmos para BQS Simétricos
Clientes Corretos - MWMR atômico
Complexidade de mensagens - O(n) [6] / 4 passos
para escrita (seguro para ƒ -1) [7]
13/2/2007
PPGIA - PUCPR
41/61
Algoritmos para BQS Simétricos
Clientes Faltosos - SWMR seguro
quoruns de leitura e escrita de mesmo
tamanho
tolera clientes faltosos
algoritmos de leitura e escrita em sistema
f-mascaramento
semântica de consistência alcançada é siglewriter multi-reader segura
13/2/2007
PPGIA - PUCPR
42/61
Algoritmos para BQS Simétricos
Clientes Faltosos - SWMR seguro
Escrita de um cliente c
13/2/2007
PPGIA - PUCPR
43/61
Algoritmos para BQS Simétricos
Clientes Faltosos - SWMR seguro
Leitura de um cliente c
13/2/2007
PPGIA - PUCPR
44/61
Algoritmos para BQS Simétricos
Clientes Faltosos - SWMR seguro
Execução de um servidor s
13/2/2007
PPGIA - PUCPR
45/61
Algoritmos para BQS Simétricos
Clientes Faltosos - SWMR seguro
Complexidade de mensagens:
13/2/2007
escrita: O(n2), leitura: O(n)
operações de escrita e leitura realizam-se,
respectivamente, em 4 e 2 passos de comunicação
PPGIA - PUCPR
46/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR seguro
quoruns de leitura e escrita de mesmo tamanho
tolera clientes faltosos
algoritmos de leitura e escrita em sistema
f-mascaramento
semântica de consistência alcançada é multi-writer
multi-reader segura
cada servidor utiliza um par de chaves privada
(para assinatura) e pública (para verificação)
13/2/2007
PPGIA - PUCPR
47/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR seguro
Escrita de um cliente c
13/2/2007
PPGIA - PUCPR
48/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR seguro
Leitura de um cliente c
13/2/2007
PPGIA - PUCPR
49/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR seguro
Execução de um servidor s
13/2/2007
PPGIA - PUCPR
50/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR seguro
Complexidade de mensagens:
13/2/2007
escrita, leitura e atualização do servidor: O(n)
operações de escrita e leitura realizam-se,
respectivamente, em 6 e 4 passos de comunicação
PPGIA - PUCPR
51/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR seguro
Complexidade de mensagens:
13/2/2007
PPGIA - PUCPR
52/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR atômico
quoruns de leitura e escrita de mesmo tamanho
tolera clientes faltosos
algoritmos de leitura e escrita em sistema
f-disseminação
semântica de consistência alcançada é multi-writer
multi-reader atômica
clientes e servidores mantêm algumas variáveis
locais específicas.
13/2/2007
PPGIA - PUCPR
53/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR atômico
Escrita de um cliente (protocolo normal)
13/2/2007
Para cada passo da escrita, o cliente precisa apresentar um
conjunto de 2 f +1 mensagens assinadas, coletadas de um quórum,
comprovando que é capaz de realizar aquele passo e justificando as
suas próximas ações.
Fase 1: o cliente requisita um conjunto de pares auto-verificáveis
de um quórum Q
Fase 2: cliente prepara um novo par <v, t> e o envia numa
mensagem PREPARE
Fase 3: cliente envia uma mensagem UPDATE com a prova de
preparação obtida na fase 2 e o novo valor
PPGIA - PUCPR
54/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR atômico
Escrita de um cliente (protocolo otimizado)
13/2/2007
2 fases: Primeiro, o cliente tenta efetuar as fases 1 e 2 como uma única
fase. Caso não consiga, executa o protocolo normal de escrita (3 fases).
No caso de execução otimizada, o timestamp é calculado nos servidores
em nome do cliente.
Fase 1: cliente envia mensagem READ-TS-PREP para todos os servidores
com o valor proposto v e sua prova de escrita.
Fase 2: se o cliente receber pares assinados de um quórum de servidores
com o mesmo timestamp, executa imediatamente a fase 3 do protocolo
normal usando S0 como a prova da preparação. Caso contrário, escolhe o
maior timestamp entre as mensagens READPREP-ACK e realiza a fase 2
do protocolo normal.
Fase 3: igual à fase 3 do protocolo normal.
PPGIA - PUCPR
55/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR atômico
Leitura de um cliente
13/2/2007
1 ou 2 fases, depende do cliente realizar ou não uma
reescrita (write back) em um quórum de servidores
Fase 1: cliente requisita um conjunto de pares assinados
a um quórum Q
Fase 2: se os timestamps retornados da fase 1 forem
diferentes, o cliente envia uma mensagem WRITEBACK assinada. A mensagem de reescrita é o que
garante a semântica atômica do protocolo
PPGIA - PUCPR
56/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR atômico
Execução de um servidor - parte 1:
13/2/2007
Quando recebe uma mensagem QUERY, devolve o seu
par armazenado mais o certificado deste par. Quando
recebe uma mensagem válida READ-TS-PREP,
verifica se a prova de escrita do cliente é válida e tenta
preparar a escrita otimizada do cliente
Se a preparação ocorrer com sucesso, ele responde com
uma mensagem READ-PREP-ACK assinada. Caso
contrário, retorna seu par armazenado com o certificado
correspondente (como uma resposta à QUERY)
PPGIA - PUCPR
57/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR atômico
Execução de um servidor - parte 2
13/2/2007
Quando recebe uma mensagem válida PREPARE de um
cliente verifica se o timestamp enviado é válido. O servidor
retorna uma mensagem PREPARE-ACK assinada
Outro caso de execução é quando este recebe uma
mensagem válida UPDATE. Ele verifica se a prova de
preparação do cliente é válida. Tenta atualizar o seu estado
Por fim, ele devolve uma mensagem UPDATEACK assinada
Caso receba uma mensagem WRITE-BACK, o servidor
executa como em uma mensagem UPDATE
PPGIA - PUCPR
58/61
Algoritmos para BQS Simétricos
Clientes Faltosos - MWMR atômico
Complexidade de mensagens:
13/2/2007
todos os algoritmos ocorrem com complexidade de
mensagens na ordem de O(n)
escrita e leitura, se completam, respectivamente, em 6 e
4 passos de comunicação, para o protocolo normal; ou
em 4 e 2 passos de comunicação, respectivamente, para
o protocolo otimizado
PPGIA - PUCPR
59/61
Referências Bibliográficas
[1] W.S.Dantas (2006), Implementação de um arcabouço para avaliação
de algoritmos para Sistemas de Quóruns Bizantinos
13/2/2007
PPGIA - PUCPR
60/61
Dúvidas
[1] Como cada par de quóruns mantém um número
suficiente de servidores corretos em comum?
[2] De que forma pelo menos um quórum formado
somente por servidores corretos é mantido?
[4] Analisar a hipótese de se implementar algum tipo
de mecanismo de segurança (permissões)
[5] Q ⊆ 2U?
[7] Porque ƒ -1?
[8] poderia ser ponto-a-multiponto (multicast)?
13/2/2007
PPGIA - PUCPR
61/61