Tolerância a Falhas
Carlos Oberdan Rolim
Ciência da Computação
Blocos básicos
Blocos básicos
Concordância bizantina
acordo, consenso
Clocks sincronizados
Armazenamento estável
Processadores fail-stop
Entrega confiável de mensagens
Blocos básicos
Concordância bizantina
problema dos generais bizantinos
alcançar consenso na presença de traidores
defeitos bizantinos
defeito em um componente do
sistema é uma falha no sistema
quando um sistema apresenta defeito, seu comportamento pode ser
totalmente arbitrário
nodo pode enviar informações diferentes para os diferentes
componentes com quem se comunica
Problema dos generais bizantinos
generais sitiam cidade inimiga
alguns generais são traidores
devem chegar a consenso sobre atacar ou recuar
generais traidores não devem poder atrapalhar o consenso
traidores não podem provocar divisão: alguns atacam e outros
recuam
concordância bizantina
consenso na presença de falhas arbitrárias
Objetivo básico
consenso entre todos os nodos sem defeitos (não traidores)
não traidores devem tomar a mesma decisão
devem obter o mesmo conjunto de valores e
executar o mesmo algoritmo sobre os valores
traidores podem enviar valores diferentes para nodos
diferentes
Requisitos formais
todos os nodos não traidores usam o mesmo valor v(i)
para o nodo i
não necessariamente o valor recebido do nodo i
se o nodo transmissor i é não traidor
então todo nodo não traidor usa o valor v(i) transmitido por i
não interessam os valores que os traidores usam
não interessam os valores transmitidos por traidores
Comentários
um traidor pode agir maliciosamente atrapalhando o
consenso
traidores podem enviar valores diferentes para diferentes nodos
mensagens de confirmação podem ser falsificadas pelos traidores
consenso é impossível em sistemas assíncronos
mesmo com um único traidor
mesmo quando só ocorrem falhas de crash
Problema com 3 nodos
Algoritmos de Lamport
Lamport 82 (Lamport, Shostak e Pease)
sistemas síncronos
sistema totalmente conectado
mensagens orais: n ≥ 3 m +1
algoritmo de consistência interativa (ICA)
mensagens assinadas: n ≥ m + 2
grande número de rodadas: m + 1
grande número de mensagens: O(nm)
n = # nodos
m = # traidores
Protocolo para mensagens orais
mensagens comuns, sem assinatura
n nodos, m traidores
solução possível para n ≥ 3m+1
premissas:
A1: toda mensagem enviada é recebida corretamente
A2: o receptor sabe quem enviou a mensagem
A3: a ausência de uma mensagem pode ser detectada (time-out)
sistema é síncrono
Exemplo
quatro nodos
n=4
n ≥ 3m+1
todos os nodos tem um valor a transmitir
cada valor transmitido deve ser confirmado entre os nodos receptores
antes de ser aceito
os valores são resultado de computações diferentes e cada
um sozinho não está certo nem errado
interessa apenas que no final todos os
nodos concordem sobre o mesmo valor
Exemplo
Node2
assume que
resposta é x
Valor
arbitrário
definido pelo
algoritmo
Rodadas
Rodadas
Rodadas
Rodadas
Rodadas
Algoritmo – Interactive Consistency
Algorithm (ICA)
n = número de nodos
ICA(0)
m = número de traidores
o general envia o seu valor para os outros n-1 nodos do sistema
cada nodo usa o valor recebido, ou default se não recebeu
nenhum valor
– (fim da recursão)
Algoritmo
o general envia o seu valor para os
outros n-1 nodos
ICA(m), m>0
nodo i
v(i) (valor recebido pelo nodo i ou default),
nodo i atua como general em ICA(m-1) enviando v(i) para os demais n-2
nodos (confirmação do valor)
para cada nodo i:
v(j) valor recebido do nodo j (j ≠ i)
nodo i usa valor maioria(v(1), ..., v(n-1))
ICA(m)
cada general difunde seu
valor para todos os nodos
do sistema
cada um dos demais nodos será
também general transmitindo seu
valor aos demais na rodada 1
ICA(m)
confirmação do valor
transmitido pelo general
ICA(m)
ICA(m)
Comentários
ICA(m) deve ser usado por todos os nodos para
alcançar consenso
cada nodo é uma vez general na rodada 1
cada nodo participa da confirmação dos valores dos demais nodos
(rodada 2)
usando ICA(m) em cada nodo, cada nodo do sistema
terá o mesmo valor assumido para todos os outros
nodos
não necessariamente o
valor transmitido por cada
nodo
Concordância bizantina
comentários finais
algoritmo de Lamport
ótimo em relação ao número de rodadas
mas exige número exponencial de mensagens
outros algoritmos foram propostos
alguns mais eficientes em relação ao número de mensagens
alguns suportam sistemas não totalmente conectados
alguns suportam sistemas assíncronos através de procedimentos
randômicos
Relógios sincronizados
facilitaria a implementação de serviços tolerantes a falhas
ordem total temporal
importante em
sistemas de tempo real
sincronização externa
manter clocks com desvio máximo em relação a referência
externa de tempo
poderia ser usado GPS
GPS não evita a necessidade de
algoritmos de sincronização
NTP não é solução
sincronização interna
manter clocks com desvio relativo máximo aceitável entre si
Relógios sincronizados
lembrar a inexistência de relógio global
necessários para impor ordem total temporal a eventos
facilitam a implementação de vários serviços
importante em sistemas de tempo real
a sincronização de relógios de tempo real é uma tarefa de alto
custo, pois envolve grande quantidade de mensagens, e deve ser
evitada se possível
a maior parte dos problemas de ordenação em sistemas
convencionais, inclusive ordenação total, pode ser resolvida com
clocks lógicos (Lamport)
Sincronização de clocks
cada nodo tem um relógio
problemas
clocks diferentes podem marcar tempos diferentes e ter velocidades
diferentes
valores de cada clock devem ser comunicados para haver sincronização
retardo na rede de comunicação pode variar randomicamente
maior problema:
clocks com defeito
informam valores
diferentes a cada leitura
Modelo para sincr. interna
hipóteses assumidas:
um clock físico em cada nodo controlado por um processo
o processo informa o valor do seu clock aos demais nodos
falhas no clock podem ser modeladas como falhas do seu processo
controlador
Ci(t) - leitura de Ci no tempo físico t
relógio é contínuo
Comportamento do clock
falho
comportamento arbitrário
sem falha
valor é próximo do tempo físico
desvio é limitado por uma constante ρ
para relógios com cristal:
ρ da ordem de 10-5
Requisitos básicos para sincronização
S1 - a qualquer tempo, o valor de todos os clocks sem
defeito deve ser aproximadamente igual
|Ci(t) - Cj(t)| ≤ β
S2 - existe um pequeno limite Σ no valor que um clock
sem defeito pode ser corrigido a cada nova sincronização
evitar grandes saltos e evitar que
todos os relógios estejam parados
Protocolos de sincronização de clocks
a qualquer tempo, o valor de todos os clocks
sem falha deve ser aproximadamente igual;
existe um pequeno limite Σ no valor que um
clock sem falha pode ser corrigido a cada
resincronização
determinísticos
requisitos S1 e S2 são garantidos
limites são garantidos
requer hipóteses sobre retardo de mensagens
probabilísticos
não requer hipóteses sobre retardo máximo de mensagens
garante precisão com uma determinada probabilidade
Protocolos determinísticos
é garantida a precisão requerida
é assumido um limite máximo para o retardo de mensagens
similar ao problema dos generais bizantinos
cada processo lê todos os clocks do sistema e determina o novo valor do seu
clock como a média de todos os valores
devido a clocks maliciosos, valores lidos não podem ser diretamente usados
necessidade de consenso
Protocolo determinístico de Lamport
Lamport e Melliar-Schmith (1985)
semelhante ao algoritmo de mensagem orais em concordância bizantina
solução possível apenas se o número de clocks falhos é menor que
n/3
sincronização mais próxima que pode ser obtida:
(max - min)(1 - 1/n)
max - maior tempo de retardo,
min - menor tempo de retardo,
n - número de nodos
Protocolos probabilísticos
sincroniza clocks apesar de retardos arbitrários na rede
não requer hipóteses sobre retardo
máximo de mensagens
hipótese: relógios maliciosos não existem
comportamento arbitrário é excluído
assume que relógios bizantinos não existem,
assim o problema não precisa ser tratado
como consenso bizantino
relógios são sincronizados com alta probabilidade
garante precisão com uma determinada
probabilidade
Sincronização externa
necessária referência externa
Global Positioning System (após 1990)
referência externa mundialmente disponível
sincronização da ordem de milisegundos
fortemente recomendado para sistemas de tempo real
infelizmente ainda não totalmente incorporado a sistemas
comerciais
Global positioning system
rede de satélites que difunde valores altamente
acurados de tempo real
desenvolvido para suporte a sistemas de localização
baixo custo
modelo de falhas do GPS
usual: crash
distorções atmosféricas
problemas com antenas (recepção do sinal)
Armazenamento estável
armazenamento estável ideal não pode
ser implementado na prática
TF assume:
parte do estado do sistema permanece disponível mesmo após
defeito do sistema
essencial em vários esquemas de suporte a tolerância a
falhas
armazenamento estável
conteúdo é preservado apesar de falhas
disco magnético não é considerado armazenamento estável
confiável
Defeitos em discos
transientes
bad sector
discos são memórias não voláteis
e muitas vezes usados como se
fossem memórias estáveis
defeito na controladora
dados no meio magnético não são perdidos
defeito de disco
o conteúdo não pode ser mais recuperado
arquivos são facilmente
perdidos em disco
em uma memória estável ideal,
dados gravados jamais são
perdidos ou corrompidos
Implementações de memória estável
aproximações de memória estável
sombreamento de disco
conjunto de imagens idênticas de um disco em dispositivos
separados
caso particular: espelhamento
2 discos
exemplo: computadores Tandem
discos são de porta dual e conectados a dois controladores
RAID
independentes
Redundant Array of Inexpensive Disks
propostos inicialmente para diminuir custos de armazenamento e
prover alta velocidade
bit interleaving
entrelaçamento de bits: aumenta velocidade permitindo operação
em paralelo, mas diminui confiabilidade
solução: mais alguns discos no array
RAID 1, 2 e 3
RAID 1
método mais caro (100% redundância)
dois discos idênticos espelhados
RAID 2
bits entrelaçados palavra + código
correção de 1 bit ou detecção de 2 bits
número de discos depende do algoritmo de correção
só permite verificação de paridade
RAID 3
bits entrelaçados + disco extra para paridade
RAID 4 , 5 e 6
RAID 4
pode ser implementado em um único disco físico
como RAID 3, mas com setores entrelaçados
RAID 5
pode ser implementado a partir de dois discos
como RAID 3 mas sem disco de paridade
mais popular
paridade é distribuída pelos discos do sistema
RAID 6
degrada para RAID 5 quando 1 disco está defeituoso
como RAID 5, mas com mais um disco de paridade (além da paridade
distribuída)
dois discos podem falhar sem perda de dados
pode trocar drive defeituoso com sistema em operação
Processadores fail-stop
em caso de defeito, nodo cessa operação sem realizar qualquer
ação incorreta
comportamento fail-stop assumido por grande parte dos
esquemas de TF
processadores reais não são fail-stop
processadores reais com defeito se comportam de maneira
arbitrária
nodos aproximadamente fail-stop podem ser construídos a
partir de processadores reais (k fail-stop)
exemplo: Stratus
Processadores fail-stop
nodo cessa operação sem realizar qualquer ação
incorreta em caso de defeito
comportamento mais simples possível
facilita a construção de tolerância a falha
efeitos visíveis após defeito
qualquer nodo pode detectar falha em um nodo fail-stop
o nodo pára qualquer execução
o estado interno e a memória volátil são perdidos (sem recuperação), o
estado da memória estável não é alterado
Processadores fail-stop
fail-stop: premissa usual em TF
mas processadores reais com defeito se comportam de maneira arbitrária
nodos fail-stop a partir de processadores reais
é impossível construir sistemas que suportam defeitos de um número
qualquer de componentes
processador k-fail-stop
comporta-se como um processador fail-stop, a não ser que k+1 ou mais
componentes do sistemas falhem
aproximação de um processador
fail-stop ideal
Implementação
importante
o funcionamento do processador fail-stop dependerá da confiabilidade do
dispositivo de armazenamento estável
implementações possíveis:
com armazenamento estável confiável
Fred B. Schneider (1983)
sem armazenamento estável confiável
Fred Schneider (1984)
Com armazenamento estável confiável
hipóteses
processador k-fail-stop:
k+1 processadores comuns
processador Ps
comportamento bizantino
proc. de armazenamento opera
corretamente e não falha
rede confiável
origem da mensagem pode ser autenticada pelo receptor
implementado por assinatura digital
clocks sincronizados e na mesma velocidade
de todos os processadores sem falha e do processador Ps
k-fail-stop
comporta-se como um processador fail-stop a
menos que k+1 ou mais componentes falhem
Implementação
k+1 procs executam o mesmo programa
envio de mensagens a Ps
mensagem requisitando read ou write
procs sem falha executam a mesma sequência de acessos a Ps
detecção de falha por Ps
se pelo menos uma requisição é diferente das demais
se o número de requisições é menor que k+1
dentro de uma janela de tempo
Implementação
após detecção de falha
Ps bloqueia a execução de qualquer read ou write subsequente
bloqueio do armazenamento estável = bloqueio de
processamento
liga variável FAILED
FAILED pode ser lida por outros processadores fail-stop da rede
Comentários
importante
todos os processadores estão com relógios sincronizados
operações são executadas sobre o armazenamento Estável apenas se
todos os k+1 processadores não apresentarem falha
votação por maioria não funciona nesse caso
exemplo: Stratus
k=1
Ps apenas uma interface
Sem armazenamento estável confiável
necessário implementar Ps confiável
processador k-fail-stop:
k+1 processadores comuns Pp
2k+1 processadores Ps
se k falham, sobram k+1 Ps sem falha
clocks sincronizados
mensagens assinadas
solução
concordância bizantina
Entrega confiável de mensagens
comunicação ponto a ponto
linhas de comunicação reais perdem mensagens e introduzem
ruído
exigências:
confiabilidade
mensagem não é corrompida
ordenação
ordem é preservada entre dois nodos
Entrega confiável de mensagens
Delivery
Propriedades
P1. - uma mensagem enviada por i é recebida corretamente por j
P2. - mensagens enviadas por i são entregues (delivered) para j na
ordem em que foram enviadas por i
devem valer mesmo em caso de defeitos em nodos ou links
idealmente devem valer mesmo no caso de particionamento da rede
suportadas por protocolos de comunicação
Detecção de erros
erros de transmissão
inevitáveis
ruído térmico
atenuação de sinal
ruído induzido
cross talk (interferência cruzada)
detecção por codificação
paridade, códigos de correção e detecção e CRC (cyclic redundancy
codes)
Ordenação e entrega
redes de comunicação reais
pacotes podem ser perdidos
protocolo de comunicação
assegura confiabilidade mesmo com rede não confiável
numeração de mensagens
retransmissão de mensagens