Sistemas Distribuídos
Francisco Brasileiro
Aula 4: Tolerância a Falhas em Sistemas Distribuídos
Agenda
• Motivação
• Conceitos básicos e definições
• Mecanismos básicos
– Acordo Bizantino
– Sincronização de relógios
– Armazenagem estável
– Entrega confiável de mensagens
– Nodos com semântica de falha controlada
Motivação
• Necessidade de tolerância a faltas
– aumento do uso de computadores
– diversificação do uso de computadores
– aumento da dependência no correto
funcionamento dos sistemas computacionais
Motivação
• Exemplos de aplicações com requisitos de
confiança no funcionamento
– Sistemas críticos envolvendo risco de vida
• controle de vôo em aeronaves
– Sistemas envolvendo perdas financeiras
• transações bancárias e do mercado financeiro
– Sistemas envolvendo desastres ambientais
• controle de usinas nucleares
Motivação
• Quando é que um sistema falha?
– Qual é o serviço adequado de um sistema?
– Vamos assumir que a especificação é correta
– Importância de se tratar faltas em sistemas
distribuídos
• em um sistema distribuído a probabilidade de um
componente falhar é maior
• aplicações críticas
Conceitos Básicos e Definições
• Serviços de um sistema computacional
• Confiança no funcionamento (dependability)
• Atributos de confiança no funcionamento
– Fiabilidade (reliability)
– Disponibilidade (availability)
– Segurança
• prevenção contra catástrofes (safety)
• prevenção contra acesso não autorizado (security)
Conceitos Básicos e Definições
• Tratamento de faltas
– Prevenção
• minimizar, por construção, a probabilidade da
ocorrência de faltas
– Tolerância
• prover o serviço, ainda que ocorram faltas
• introduz redundância no sistema
– física
– temporal
Conceitos Básicos e Definições
• Características de prevenção de faltas
– ausência de redundância
– falhas ocasionais do sistema
– manutenção assistida por humanos
• Problemas com a abordagem
– atraso longo quando há necessidade de reparo
– possível inacessibilidade para efetuar reparo
– custos excessivos na manutenção e com o
processamento perdido
Conceitos Básicos e Definições
• Combinando prevenção e tolerância
– As duas técnicas são complementares
– Algumas aplicações devem necessariamente
tolerar faltas
– A introdução de redundância física possibilita a
substituição do reparo manual
– Outros pontos importantes
• diagnóstico de faltas
• validação dos mecanismos do sistema para
tolerância a faltas
Conceitos Básicos e Definições
• Modelando sistemas
– Visão externa
– Visão interna
– Comportamento do sistema
– Especificação de serviços
– Características desejáveis em uma
especificação
• completa
• consistente
• correta
Conceitos Básicos e Definições
• Falha ou defeito (failure)
– Desvio da especificação
• Erro (error)
– Estado ou transição interna ilegais
• Falta (fault)
– Causa dos erros e falhas
• Relação entre falta, erro e falha
Conceitos Básicos e Definições
• Tipos de faltas
– Quanto à duração
• permanentes, transientes, intermitentes
– Quanto à natureza
• físicas, interação
– Quanto à fase de introdução
• projeto, operação
Conceitos Básicos e Definições
• Semântica de falha de componentes
– domínio do valor
– domínio do tempo
– tipos de falhas
•
•
•
•
•
silenciosa (crash, fail-stop)
omissão
temporização (desempenho)
valor
arbitrária (Bizantina)
– Bizantina com autenticação
Conceitos Básicos e Definições
• Sistemas tolerantes a faltas
– Evitam a falha do sistema, mesmo na presença
de faltas em alguns dos componentes do
sistema
– Mesmo que alguns componentes falhem, o
sistema ainda é consistente com a sua
especificação
• redução de desempenho (graceful degradation)
– Introdução de redundância é o princípio básico
Conceitos Básicos e Definições
• Fases na tolerância a faltas
– Detecção de erros
– Contenção e avaliação de estragos
– Recuperação de erros
– Tratamento de faltas e continuidade do serviço
• diagnóstico de faltas
• reconfiguração do sistema
Conceitos Básicos e Definições
• Detecção de erros
– Dedução de faltas e falhas
– Propriedades de um detetor de erros ideal
• completude e corretude
• independência de projeto
– Principais tipos de detetores de erros
•
•
•
•
replicados
temporizadores (watchdogs)
códigos e redundância estrutural
testes de aceitação e diagnósticos
Conceitos Básicos e Definições
• Contenção e avaliação de estragos
– Latência
– Disseminação de erros
– Análise do fluxo de informação
– Portas “corta-fogo”
– SRU’s (smallest replacement units)
Conceitos Básicos e Definições
• Recuperação de erros
– Abordagem pessimista (backward recovery)
•
•
•
•
pontos de salvaguarda (checkpoint)
implementação razoavelmente simples
custo alto
efeito “dominó“
– Abordagem otimista (forward recovery)
• ações corretivas
• considerações sobre a natureza dos erros
• normalmente é dependente da aplicação ou do
sistema
Conceitos Básicos e Definições
• Tratamentos de faltas e continuidade do
serviço
– Identificação de componentes defeituosos
– Localização do erro
– Reparo do sistema
• on-line
• reconfiguração
• componentes suplentes (spares)
– passivos (cold-spares) e ativos (hot-spares)
Conceitos Básicos e Definições
• Modelagem de sistemas distribuídos
– Modelo físico
• Principais componentes
–
–
–
–
processadores
rede de comunicação
dispositivos de armazenagem não voláteis
software
– Modelo lógico
• Aplicações implementadas por processos
cooperantes
• Comunicação via troca de mensagens
• Sistemas síncronos versus sistemas assíncronos
Conceitos Básicos e Definições
• Tipos de sistemas distribuídos
– Sistemas síncronos
• atraso máximo conhecido para escalonamento e
troca de mensagens
• oferecem framework mais simples
• mais difíceis de serem implementados
– Sistemas assíncronos
• timed-related x time-free
• mais fáceis de serem implementados
Mecanismos Básicos
• Suportes para construção de sistemas
distribuídos tolerantes a faltas
– Como disseminar informação de forma
consistente e confiável?
– Como ordenar eventos?
– Como prover um sistema de tempo global?
– Como armazenar informação de forma estável?
– Como restringir a semântica de falha de
componentes?
Mecanismos Básicos:
Acordo Bizantino
• Como atingir consenso na presença de
componentes com semântica de falha
arbitrária?
– O problema dos generais Bizantinos
• decisão final é baseada nas decisões locais
• alguns generais podem ser traidores
– Como garantir que todos os generais leais
decidirão pelo mesmo plano?
• os generais devem receber as mesmas informações
• os generais devem usar a mesma função de decisão
Mecanismos Básicos:
Acordo Bizantino
• Como entrar em um acordo sobre qual valor
usar para a decisão de um general traidor?
– Todos os generais leais devem chegar a um
consenso sobre que valor usar para a decisão
de cada general
• Consistência interativa
– todos os generais leais usam o mesmo valor v(i) para o
general i
– se o general i é leal, então todos os generais leais devem
usar o valor v(i) que o general i envia
Mecanismos Básicos:
Acordo Bizantino
• Requisitos para obter consistência interativa
– Várias rodadas de troca de informação
– Sistema de comunicação síncrono
– Número limitado de generais traidores
• Há solução para o caso de 3 generais, onde
um deles pode ser um traidor?
– os generais podem tomar apenas duas
decisões (atacar ou esperar)
Mecanismos Básicos:
Acordo Bizantino
G1 (T)
atacar
atacar
G2 (R)
G3 (R)
esperar
O que fazer?
Mecanismos Básicos:
Acordo Bizantino
G1 (T)
atacar
esperar
G2 (R)
G1 (R)
esperar
O que fazer?
Mecanismos Básicos:
Acordo Bizantino
• Resultados teóricos
– Número mínimo de rodadas
• k+1
– Relação mínima entre componentes
corretos/defeituosos
• n/k>3
– Número mínimo de canais de comunicação
disjuntos
• 2k+1
Mecanismos Básicos: Acordo Bizantino
• Algoritmo recursivo para consistência interativa
• ICA(k), k>0
– 1. O transmissor envia o seu valor para os outros n-1 receptores
– 2. Seja v o valor recebido pelo general i, ou o valor default se
nada for recebido. O general i se comporta como transmissor no
algoritmo ICA(k-1) para enviar v para os outros n-2 receptores
– 3. Para cada general i, seja vj o valor recebido de j (i¡). O
general i usa o valor da maioria dos valores recebidos para i
• ICA(0)
– 1. O transmissor envia seu valor para os outros n-1 receptores
– 2. Cada general usa o valor recebido do transmissor ou o valor
default se nada for recebido
Mecanismos Básicos:
Acordo Bizantino
• Consistência interativa com mensagens
assinadas
– Mensagens repassadas por generais traidores
não podem ser modificadas sem que isso seja
detectado por generais leais
• assinaturas digitais
– Resultados teóricos
• número de rodadas: k+1
• número máximo de generais traidores: n>k
• número de canais de comunicação disjuntos: k+1
Mecanismos Básicos:
Sincronização de Relógios
• Como estabelecer um referencial de tempo
global em um sistema distribuído?
– Cada nodo tem seu relógio local
– Relógios desviam do tempo real
– Tempo global e ordenação de eventos
• relógios lógicos
• sincronização de relógios
– sincronização interna
– sincronização externa
Mecanismos Básicos:
Sincronização de Relógios
• A relação “aconteceu antes” () e a
ordenação de eventos
– Para dois eventos a e b:
• se a e b são eventos no mesmo processo e a vem
antes de b, então a b
• se a é o evento de envio de uma mensagem m e b é
o evento de recepção de m, então a b
• se existe um terceiro evento c, tal que a b e b 
c, então a c
Mecanismos Básicos:
Sincronização de Relógios
• Relógios lógicos implementam a relação
“”
– Um relógio lógico é um contador que serve para
associar valores a eventos e cada processo
tem um relógio lógico
• Ci<a> é o valor associado ao evento a pelo processo
i onde a ocorreu
• Para dois eventos a e b: se a  b, então C(a) < C(b)
• Como implementar relógios lógicos?
– Relógio é incrementado entre dois eventos
Mecanismos Básicos:
Sincronização de Relógios
• Aspectos a serem considerados na
sincronização de relógios físicos
– Relógios corretos operam em diferentes
velocidades
– Necessidade de re-sincronização periódica
– Troca de mensagens com valores das leituras
dos relógios introduz incerteza
– Falhas nos relógios e nos canais de
comunicação
Mecanismos Básicos:
Sincronização de Relógios
• Definição do problema:
– Sejam Ci(t) a leitura de Ci no tempo real t e ci(T)
o tempo real quando o i-ésimo relógio lê o valor
T
• assumindo que os relógios são contínuos:
– para um relógio correto, |d(Ci/dt)-1| < r
• existem dois requisitos básicos para sincronização
de relógios:
– a todo instante a leitura de dois relógios corretos deve ser
bastante próxima (|Ci(t)-Cj(t)|  b)
– um relógio correto só pode ser adiantado/atrasado de um
Mecanismos Básicos:
Sincronização de Relógios
• Tipos de protocolos
– Determinísticos
• sempre garantem a precisão da sincronização
• assumem um limite máximo no atraso para a
transmissão de mensagens
– Probabilísticos
• nenhuma restrição sobre o atraso na troca de
mensagens
• garantem a precisão da sincronização apenas dentro
de uma probabilidade pré-definida
Mecanismos Básicos:
Sincronização de Relógios
• Protocolos determinísticos
– Uma possível solução é:
• cada nodo lê o seu relógio e o relógio dos outros
nodos
• atribui ao seu relógio a mediana dos valores lidos
– Em que circunstâncias esse protocolo
funciona?
• a maioria dos nodos (e seus relógios) são corretos
• nodos e relógios não sofrem falhas arbitrárias
– O que fazer na presença de falhas
arbitrárias?
• dois nodos corretos quaisquer devem obter
Mecanismos Básicos:
Sincronização de Relógios
• Uma solução com mensagens orais
• Número de nodos é pelo menos 3k+1
• C(t)=H(t)+CORR(t)
• Inicialmente os relógios estão sincronizados em e
• Existe dmin e dmax para o atraso na transmissão
• Quando Ci(t)=T o nodo i dissemina “a hora é T”
• Guarda tempo das recepções de mensagens dos
outros nodos por um período de (e+dmax)(1+r)
• Com os tempos de recepção recalcula CORR(t)
– joga fora os k maiores e os k menores
– CORR(t)=d + mediana dos valores restantes
Mecanismos Básicos:
Sincronização de Relógios
• Protocolos probabilísticos
– Algoritmo de Cristian
• tolera falhas de desempenho
• não assume atraso máximo, mas assume um atraso
mínimo
• nodo j requisita o valor do relógio de um nodo i e
corrige esse valor com base no atraso de leitura
Mecanismos Básicos:
Sincronização de Relógios
• Protocolos probabilísticos
– Algoritmo de Cristian
• seja T o valor do relógio i quando a requisição de j é
recebida e 2D o tempo de transmitir o pedido para i e
receber a resposta:
– quando j recebe a mensagem o relógio de i lê um valor no
intervalo [T+dmin(1-r), T+2D(1+2r)-dmin(1+r)]
– o valor médio do intervalo minimiza o erro
– o erro máximo dá a precisão da leitura
– quanto menor D maior a precisão
» para uma precisão e é preciso descartar todas as
leituras com atraso maior que 2U, onde U=(1-
Mecanismos Básicos:
Armazenagem Estável
• Qual a necessidade de se ter armazenagem
estável?
– Ter acesso à informação depois que uma falha
ocorre
• uso de dispositivos de armazenagem não voláteis
– Recuperação para trás
• leitura de pontos de salvaguarda
– Aumentar a fiabilidade de discos “de prateleira”
Mecanismos Básicos:
Armazenagem Estável
• Definição do problema
– Toda informação que é gravada com sucesso
no tempo T, pode ser lida no tempo T’, T’>T
• mesmo que falhas ocorram durante a operação
• mesmo que os dispositivos sofram faltas físicas
– Cada bloco do disco tem um valor e um estado
• o estado pode ser correto ou defeituoso
– Primitivas básicas de acesso ao disco
• write(endereço, dado), retorna sucesso ou fracasso
• read(endereço), retorna (estado, valor)
Mecanismos Básicos:
Armazenagem Estável
• Como tratar faltas em discos?
– A maior parte pode ser tratada por meio de
codificação
– Algumas faltas não podem ser tratadas assim
•
•
•
•
falta transiente
setor defeituoso
falha da controladora
falha do disco
Mecanismos Básicos:
Armazenagem Estável
• Tratando os efeitos das faltas
– Ao invés de enumerar todas as possíveis faltas,
é melhor estudar o impacto das mesmas
• prover métodos para esconder/reverter os erros
– Eventos que ocorrem em um disco
• leitura, gravação e espontâneos
• desejáveis e não desejáveis
– É preciso mascarar os efeitos de eventos não
desejáveis
Mecanismos Básicos:
Armazenagem Estável
• Eventos indesejáveis da operação read
– Erro temporário
• bloco correto mas operação retorna bloco defeituoso
– Erro persistente
• bloco correto mas operação retorna bloco
defeituoso, mesmo depois de sucessivas tentativas
– Erro não detectado
• bloco está defeituoso mas operação retorna bloco
correto, ou bloco correto mas operação retorna um
valor diferente do conteúdo do bloco
Mecanismos Básicos:
Armazenagem Estável
• Eventos indesejáveis da operação write
– Escrita nula
• o bloco não é mudado
– Escrita incompleta
• o bloco se torna defeituoso após a escrita
Mecanismos Básicos:
Armazenagem Estável
• Eventos espontâneos indesejáveis
• Corrupção
– o bloco muda de correto para defeituoso
• Recuperação
– o bloco muda de defeituoso para correto
• Erro não detectado
– o bloco muda de valor
Mecanismos Básicos:
Armazenagem Estável
• Armazenagem estável usando um único
disco
– Primitivas básicas
• CarefulRead(e)
– elimina erros temporários
• CarefulWrite(e, d)
– elimina escrita nula e escrita incompleta
– Dividir disco em pares de blocos
• informação duplicada
• independentes em relação a eventos espontâneos
Mecanismos Básicos:
Armazenagem Estável
• Primitivas de acesso ao disco
– StableRead(e)
• faz CarefulRead(e) em um dos pares; se não tiver
sucesso, faz CarefulRead(e) no outro par
– StableWrite(e, d)
• faz CarefulWrite(e, d) em um dos pares; quando a
operação retorna sucesso, faz CarefulWrite(e, d) no
outro par
– Cleanup()
• faz a consistência do disco após uma falha do nodo
(normalmente na inicialização do sistema)
Mecanismos Básicos:
Armazenagem Estável
• Eventos indesejáveis mascarados
– erro de leitura temporário e persistente
– escrita nula e defeituosa
– corrupção de um bloco
• Eventos não mascarados
– erros não detectados
– quedas do disco ou do nodo
Mecanismos Básicos:
Armazenagem Estável
• Armazenagem estável usando replicação
– Pares de blocos são organizados em discos
distintos
– Discos espelhados
• Mascaram falhas do disco, controladora ou nodo
• Boa aproximação de uma unidade de armazenagem
estável
– só não mascara erros não detectados
– RAID’s
Mecanismos Básicos:
Entrega Confiável de Mensagens
• Definição do problema
– Uma mensagem enviada de i para j é recebida
por j corretamente
– Mensagens enviadas por i são entregues a j na
ordem em que foram enviadas
• Implementação
– Detecção de erros
– Ordenação e garantia de entrega
– Tratamento de falhas
Mecanismos Básicos:
Entrega Confiável de Mensagens
• Como fazer comunicação um-para-muitos?
– Broadcast
– Multicast
• Propriedades de interesse
– Fiabilidade
– Ordenação consistente
– Causalidade
Mecanismos Básicos:
Entrega Confiável de Mensagens
• Caracterização do sistema
– Comunicação via troca de mensagens
– Sistema síncrono (d)
– Relógios são sincronizados (e)
– Semântica de falha arbitrária para os nodos
– Até k nodos e l canais de comunicação podem
falhar
– Não há partições da rede
Mecanismos Básicos:
Entrega Confiável de Mensagens
• O objetivo é garantir as seguintes
propriedades:
– terminação: todo valor disseminado por um
transmissor correto no tempo t é entregue a
todos os nodos corretos no tempo t+D
– atomicidade: qualquer mensagem disseminada
no tempo t ou é entregue por todos os nodos
corretos no tempo t+D ou não é entregue a
nenhum nodo;
– ordem: as mensagens entregues são entregues
Mecanismos Básicos:
Entrega Confiável de Mensagens
• Protocolo de Cristian (protocolo-D)
– Implementado por três processos
• Transmissor: inicia a transmissão de mensagens
• Repetidor: difunde mensagens recebidas
• Entregador: ordena e entrega mensagens estáveis
– Mensagens estáveis
• Para tolerar faltas por omissão: D=kd+Dk,l+e
• Para tolerar faltas de desempenho ou arbitrárias:
D=k(d+e)+Dk,l+e
• Para redes completamente conectadas:
Mecanismos Básicos:
Entrega Confiável de Mensagens
• Outros protocolos
– Sistemas síncronos
• Protocolos baseados em temporizadores ao invés de
relógios sincronizados
– Nodos Voltan e Seljuk
– Sistemas assíncronos (time-related)
• Ordenação causal
– Isis, Horus e Ensemble
– Transis
– NewTOP
Mecanismos Básicos:
Nodos com Semântica de Falha
Controlada
• Por que restringir a semântica de falhas de
componentes?
– Simplificação de projetos
• Como se escolhe a semântica de falha de
componentes?
– Qualidade do componente
– Requisitos da aplicação
– Tempo de missão
Mecanismos Básicos:
Nodos com Semântica de Falha
Controlada
• Como implementar nodos com semântica
de falha controlada
– Replicando processadores com semântica de
falha menos restritiva
– Máquina de estados
• processamento determinístico
• submeter réplicas às mesmas entradas
• validar saídas
Mecanismos Básicos:
Nodos com Semântica de Falha
Controlada
• Nodos com semântica de falha por parada
(fail-stop)
– Propriedades de um nodo fail-stop
• falha silenciosa
• armazenagem estável é mantida após a parada do
nodo
• qualquer nodo pode detectar a falha de um nodo
fail-stop
Mecanismos Básicos:
Nodos com Semântica de Falha
Controlada
• Implementação com armazenagem estável
– Um nodo fail-stop k-resiliente é composto por
k+1 processadores convencionais e um nodo
confiável implementando armazenagem estável
– Assinatura digital para autenticar origem
– Comunicação é feita via armazenagem estável
– Pedidos de leitura/gravação são enviados por
cada processador para o nodo de
armazenagem
– Qualquer diferença entre os valores para o
Mecanismos Básicos:
Nodos com Semântica de Falha
Controlada
• Implementação sem armazenagem estável
– Um nodo fail-stop k-resiliente é composto por
k+1 processadores convencionais
– O nodo de armazenagem estável é
implementado por 2k+1 processadores
convencionais
– Para escrever na armazenagem estável, um
acordo Bizantino é iniciado com o nodo de
armazenagem; qualquer diferença nos valores
do mesmo pedido indicam uma falha do nodo
Mecanismos Básicos:
Nodos com Semântica de Falha
Controlada
• Implementação em hardware de um nodo
com semântica de falha silenciosa (crash)
entrada
processador
saída
comparador
processador
Mecanismos Básicos:
Nodos com Semântica de Falha
Controlada
• Implementação em software
DMQ
Servidor
PMQ
Links
Ordenador
Remetente
Sim
RMQ
deve ser
ordenada?
Não
ECL
Links
Validador
VMQ
Links
Receptor
Mensagens originadas da rede
Links
ICL
Transmissor
Mensagens destinadas à rede
Mecanismos Básicos:
Nodos com Semântica de Falha
Controlada
• Vantagens dos nodos hard
– Impacto mínimo no desempenho
– Impacto mínimo no projeto do software
• Vantagens dos nodos soft
– Possibilidade de uso de diversidade no
projeto
– Uso de componentes off-the-shelf
– Facilidade de expansão
– Maior robustez contra a ocorrência de faltas
geradas por uma causa comum
Mecanismos Básicos:
Nodos com Semântica de Falha
Controlada
• Como proceder?
– A escolha não é clara, porém ...
– O tempo de projeto de nodos hard é longo
(entre 1 e 2 anos), e enfrenta alguns
problemas sérios
– Para algumas aplicações, o impacto no
desempenho introduzido nos nodos soft pode
não ser muito grande
Mecanismos Básicos:
Replicando Componentes
• Estratégias de replicação
– Replicação ativa
• modelo da máquina de estados
– determinismo de réplicas
– ordenação das entradas
• grau de replicação
– sistema k-resiliente
– semântica de falhas assumida
Mecanismos Básicos:
Replicando Componentes
• Estratégias de replicação
– Replicação passiva
•
•
•
•
•
•
primária e cópias
pontos de salvaguarda + detecção de falhas
mais simples quando não ocorrem falhas
réplicas podem ser não-determinísticas
recuperação mais lenta
só tolera faltas de componentes com semântica de
falha silenciosa
Mecanismos Básicos:
Replicando Componentes
• Estratégias de replicação
– Replicação semi-ativa
• tenta prover as vantagens das outras duas
abordagens
– recuperação rápida
– tratamento de não-determinismo
• só tolera faltas de componentes com semântica de
falha silenciosa