Buscar

Tolerância a Falhas em Sistemas Distribuídos

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 65 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 65 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 65 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 1 Hélio Crestana Guardia - 2011
Tolerância a falha
• Sistemas distribuídos podem apresentar falha parcial (partial failure)
• Falha parcial ocorre quando um componente falha
• Falha parcial pode afetar operação de outros componentes de um SD mas, 
eventualmente, não todos
• Falha em sistema com uma única máquina, normalmente, pode inviabilizar 
a operação completa do sistema
• Sistemas distribuídos normalmente são construídos de forma a recuperar-se 
de falhas parciais, sem afetar severamente o desempenho global
• Em caso de falha, SD deve continuar em operação, de forma aceitável, até 
que reparo seja realizado
• Aspectos:
– Resiliência de processo: possibilidade de falha sem perturbar seriamente os demais
– Multicast confiável: entrega confiável de mensagens a grupos de processos
– Atomicidade de operações, com protocolos de consolidação (commit) distribuídos
– Recuperação de falhas 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 2 Hélio Crestana Guardia - 2011
Conceitos
• Técnica fundamental para tratamento de falhas: redundância
• Tolerância a falhas está relacionada à confiabilidade (dependability) 
de um sistema
• Requisitos para confiabilidade:
– Disponibilidade (availability)
– Confiabilidade (reliability)
– Segurança (safety)
– Capacidade de manutenção (maintainability) 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 3 Hélio Crestana Guardia - 2011
Conceitos
Disponibilidade (availability)
• Indica que um sistema está pronto para uso imediato
• Refere-se à probabilidade de que sistema está operando corretamente num dado 
instante e está disponível para executar suas funções
• Alta disponibilidade indica que sistema muito provavelmente estará funcionando num 
dado instante
Confiabilidade (reliability)
• Refere-se à propriedade que um sistema irá operar continuamente sem falha
• É definida em termos de um intervalo de tempo, ao invés de num dado instante 
como ocorre com a disponibilidade
• Sistema confiável é aquele que muito provavelmente irá operar sem interrupção 
durante um período relativamente longo de tempo
Disponibilidade x Confiabilidade
• Sistema que falha por 1 milissegundo a cada hora: disponibilidade alta, acima de 99.9999 %; 
confiabilidade baixa
• Sistema que nunca cai (crashes) mas é desligado por 2 semanas no ano: alta confiabilidade; 
apenas 96 % de disponibilidade
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 4 Hélio Crestana Guardia - 2011
Conceitos
Segurança (safety)
• Refere-se às consequências da falha de um sistema em operar corretamente
• Sistemas críticos devem prover alto grau de segurança
Capacidade de manutenção (maintainability)
• Indica a facilidade para que um sistema que falhou seja reparado 
• Sistema com alta capacidade de manutenção normalmente também apresenta 
alto grau de disponibilidade, especialmente se falhas podem ser detectadas e 
reparadas automaticamente
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 5 Hélio Crestana Guardia - 2011
Conceitos
• Jean-Claude Laprie, “Dependable computing and fault tolerance: concepts 
and terminology”. In Proc. 15th IEEE Int. Symp. On Fault Tolerant 
Computing (TDCS-15), Ann Arbor, Michigan, June 1985, pp 2-11.
• Computer system dependability is the quality of the delivered service such that reliance can 
justifiably be placed on this service.
• The service delivered by a system is the system behaviour as it is perceived by another special 
system(s) interacting with the considered system: its user(s).
• A system failure occurs when the delivered service deviates from the specified service, where the 
service specification is an agreed description of the expected service. 
• The failure occurred because the system was erroneous: an error is that part of the system state 
which is liable to lead to failure, i.e. to the delivery of a service not complying with the specified 
service. The cause – in its phenomenological sense – of an error is a fault.
• Upon occurrence, a fault creates a latent error, which becomes effective when it is activated; 
when the error affects the delivered service, a failure occurs. State in other terms, an error is 
the manifestation in the system of a fault, and a failure is the manifestation on the service of an 
error. 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 6 Hélio Crestana Guardia - 2011
Conceitos (Laprie 1985)
• Achieving a dependable computing system calls for the combined utilization of a set 
of methods which can be classed into:
– Fault-avoidance: how to prevent, by construction, fault occurrence;
– Fault-tolerance: how to provide, by redundancy, service complying with the 
specification in spite of faults having occurred or occurring;
– Error-removal: how to minimize, by verification, the presence of latent errors;
– Error-forecasting: how to estimate, by evaluation, the presence, the creation and 
the consequences of errors
• Fault-avoidance and fault-tolerance may be seen as constituting dependability 
procurement(*): 
– how to provide the system with the ability to deliver the specified service; 
• Error-removal and error-forecasting may be seen as constituting dependability 
validation: 
– how to reach confidence in the system ability to deliver the specified service.
(*) aquisição, obtenção
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 7 Hélio Crestana Guardia - 2011
Conceitos (Laprie 1985) 
• The life of a system is perceived by its users as an alternation between two states of 
the delivered service with respect to the specified service:
– Service accomplishment, where the service is delivered as specified,
– Service interruption, where the delivered service is different from the specified 
service
• The events which constitute the transitions between these two states are the failure 
and the restoration.
• Quantifying this accomplishment-interruption alternation leads to the two main 
measures of dependability:
– Reliability: a measure of the continuous service accomplishment (or, 
equivalently, of the time to failure) from a reference initial instant;
– Availability: a measure of the service accomplishment with respect to the 
alternation of accomplishment and interruption.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 8 Hélio Crestana Guardia - 2011
Conceitos (Laprie 2004) 
 Availability
 Reliability
 Safety
 Attributes Confidentiality
 Integrity
 Maintainability
Dependability
 Faults
 Threats Errors
Failures
 Fault Prevention
 Fault Tolerance
 Means Fault Removal
 Fault Forecasting
 
The dependability tree: a taxonomy for fault-tolerance
• A. Avizienis, J.-C. Laprie, and B. Randell. Dependability and its threats – a taxonomy. In IFIP 
congress topical sessions, pages 91–120, 2004.
• J.-C. Laprie and B. Randell. Basic concepts and taxonomy of dependable and secure computing. 
IEEE transaction dependable security computer, 1(1):11–33, 2004.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 9 Hélio Crestana Guardia - 2011
Conceitos
• Sistema falha quando não pode manter seus compromissos
• Ex.: se um sistema é projetado para prover alguns serviços, falha se não 
consegue prover um ou mais desses serviços
• Um erro é uma parte do estado de um sistema que pode levar a uma falha
• Ex. pacotes podem ser recebidos com erro no destino. 
– Causa do erro é chamada de falta (fault).
– Determinação do que causou o erro é importante; nesse caso, um cabo 
defeituoso, que pode ser trocado, ou as condições atmosféricas (não alteráveis :)
• A construção de sistemas confiáveis (dependable) está relacionada ao 
controle das faltas (faults)
• Faltas podem ser prevenidas, removidas e previstas.
• Tolerância a faltas (fault tolerance)significa que um sistema pode prover 
seus serviços mesmo na presença de faltas
– Sistema pode tolerar faltas e continuar operando normalmente
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 10 Hélio Crestana Guardia - 2011
Conceitos
 Componente provê serviço aos clientes
 Para prover serviço, componente pode requerer serviços de outros 
componentes (um componente pode depender de outros componentes)
 Um componente C depende de C* se a correção do funcionamento de C 
depende da correção do comportamento de C*
 Componentes podem ser processos ou canais de comunicação
 Availability: disponibilidade para uso
 Reliability: continuidade da realização de serviço
 Safety: pouca probabilidade de catástrofe em caso de falha
 Maintainability: quão facilmente um sistema com falha pode ser reparado
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 11 Hélio Crestana Guardia - 2011
Conceitos
 Falha: situação em que um componente não está provendo um serviço de 
acordo com suas especificações
 Erro: parte do estado de um componente que pode levar a uma falha
 Falta: causa de um erro
Como tratar faltas:
 Fault prevention: prevenir a ocorrência de faltas
 Fault tolerance: construir componente que possa mascarar a presença de 
faltas
 Fault removal: reduzir a presença, o número e a gravidade (seriousness) de 
faltas
 Fault forecasting: estimar a situação atual e futura de faltas e as 
consequências de suas ocorrências
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 12 Hélio Crestana Guardia - 2011
Conceitos
 Faltas podem ser classificadas como:
 Transientes: ocorrem uma vez e desaparecem
 Intermitentes: podem ocorrer e desaparacer inúmeras vezes
 Permanentes: continuam a existir até que componente em falta (faulty) 
é substituído
(Fault) falta → erro → falha (failure)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 13 Hélio Crestana Guardia - 2011
Modelos de falha
 Sistema que falha não está provendo os serviços previstos
 Falha pode significar que servidores, meios de comunicação, ou possivelmente 
ambos não estão operando como esperado
 Falta pode não estar no provedor do serviço em falha, mas em outros servidores que 
lhe prestam serviço
 Ex.: falha num disco pode ser sentida por um servidor de arquivos, que atua num 
serviço de banco de dados distribuído
(Crash failure)
(Omission failure)
(Response failure)
(Arbitrary failure)
(Timing failure)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 14 Hélio Crestana Guardia - 2011
Modelos de falha
 Crash failure: ocorre quando servidor para de funcionar prematuramente, 
depois de estar operando corretamente até então
 Ao parar de funcionar, servidor fica incomunicável
 Ex. sistema operacional travado, recuperável apenas com reiniciamento
 Omission failure: ocorre quando servidor deixa de responder a requisições
 Falha no recebimento de pedidos
 Falha no processamento de requisições (hang)
 Falha no envio de respostas
 Timing failure: resposta recebida fora do intervalo de tempo especificado
 Response failure: servidor retorna resposta incorreta
 Value failure: resposta incorreta para um pedido
 State transition failure: servidor reage de maneira inesperada a um pedido, por 
exemplo, mudando de estado para um estado desconhecido
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 15 Hélio Crestana Guardia - 2011
Modelos de falha
 Byzntines failure ou falhas arbitrárias: são difíceis de serem 
tratadas, podendo ser resultado de operação fraudulenta produzida 
intencionalmente. 
 Nomenclatura refere-se ao período do império Bizantino (330-1453), nos 
Bálcãs, atualmente Turquia, durante o qual eram comuns conspirações e intrigas 
que aparentemente eram comuns nos círculos de poder
 Falhas arbitrárias estão relacionadas com crash failures 
 Fail-stop failures: quando servidor simplesmente para de responder, de 
forma que seu silêncio pode ser detectado por outros processos. 
Servidor pode, em alguns casos, notificar que vai parar de operar.
 Fail-silent failures: servidor para de responder ou está inesperadamente 
lento, com problemas de desempenho
 Fail-safe: servidor falha produzindo resultados aleatórios, que podem 
ser identificados como desprezíveis (junk) pelos demais processos
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 16 Hélio Crestana Guardia - 2011
Mascaramento de falha por redundância
 Para ser tolerante a falhas, sistema deve tentar esconder a 
ocorrência de falhas dos demais processos
 Técnica: redundância
 Tipos de redundância:
 Redundância de informação (information redundancy): bits extra são 
adicionados para recuperação em caso de erros (ex. Hamming code)
 Redundância de tempo (time redundancy): operações são repetidas, se 
necessário (ex. transações). É útil para falhas transientes ou 
intermitentes.
 Redundância física (physical redundancy): usa equipamentos ou 
processos extras para tolerar a perda ou o mal funcionamento de alguns 
componentes. Pode ser realizada por hardware ou software.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 17 Hélio Crestana Guardia - 2011
Mascaramento de falha por redundância
 Triple Modular Redundance: TMR
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 18 Hélio Crestana Guardia - 2011
Resiliência de processo
 Proteção contra falha de processos: obtida com replicação de processos em 
grupos
 Diversos processos idênticos são organizados num grupo
 Quando uma mensagem é enviada para um grupo, todos os processos 
membros deste grupo a recebem
 Se um processo no grupo falha, outro pode assumir
 Grupos podem ser dinâmicos, criados e destruídos por demanda
 Processos podem entrar e sair de grupos em tempo de execução e podem 
pertencer a vários grupos simultaneamente
 Mecanismos devem existir para gerenciamento de grupos e processos
 Grupos permitem tratar com vários processos usando uma abstração
 Mensagens podem ser enviadas para grupos sem saber informações sobre 
componentes
Resilience: resiliência, elasticidade, ...
1. The ability to recover quickly from illness, change, or misfortune;
2. The property of a material that enables it to resume its original shape or position after being bent, stretched, or 
compressed; elasticity.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 19 Hélio Crestana Guardia - 2011
Resiliência de processo
 Grupos de processos podem ser estruturados de forma simples (plana 
– flat) ou de acordo com alguma hierarquia
 Flat group: 
– Simétrico, sem um ponto único de falha
– Tomada de decisão é mais complexa
– Entrada e saída de membros no grupo feitas através de mensagens 
multicast (confiáveis); pode ocorrer fail-stop 
 Hierarchical group: 
– Comunicação ocorre via coordenador;
– Não completamente tolerante a falhas e escalável, mas de fácil 
implementação
– Servidor de grupo (group server) gerencia entrada e saída de membros 
no grupo
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 20 Hélio Crestana Guardia - 2011
Resiliência de processo: grupos
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 21 Hélio Crestana Guardia - 2011
Resiliência de processo
 Processos podem ser replicados e organizados num grupo (tolerante a 
faltas) para substituir um processo único (vulnerável) 
 Existência de processos idênticos num grupo permite mascarar a falha de 
um ou mais processos nesse grupo
 Replicação pode ocorrer através de protocolos baseados em primário 
(primary-based) ou com escrita replicada (replicated-write)
– Primary-based: grupo é organizado de forma hierárquica e processo 
primário coordena todas as operações de escrita
• Seprimário falha, processos backup executam algoritmo de eleição para 
escolha de um novo primário
– Operação na forma de replicação ativa, ou de protocolos baseados em 
quórum (quorum-based)
• Processos idênticos operam em organização flat com coordenação distribuída
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 22 Hélio Crestana Guardia - 2011
Resiliência de processo
 Questão: quanta replicação é necessária?
 Sistema é dito k fault tolerant (k-tolerante a faltas) se pode sobreviver a 
faltas em k componentes e ainda cumprir suas especificações
 Se componentes (processos) falham silenciosamente, k+1 processos 
remanescentes são suficientes para prover k-tolerância a faltas 
 Nesse caso, se k processos falharem, processo restante provê a 
resposta desejada
 Se processos apresentam falhas Bizantinas, continuando em execução e 
enviando resultados espúrios, um mínimo de 2k+1 processos são 
necessários para prover k-tolerância a falhas
 Em caso de falha, k processos poderiam gerar o mesmo resultado 
incorreto, acidentalmente ou intencionalmente, mas k+1 restantes 
proveriam a maioria suficiente para determinar o resultado correto.
 Análise estatística pode ser necessária para confirmar resultados
 Todas as requisições devem chegar nos servidores na mesma ordem: 
atomic multicast problem 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 23 Hélio Crestana Guardia - 2011
Acordo em sistemas com falta (faulty systems)
 Organização de processos replicados em grupo aumenta a tolerância a faltas
 Supondo que um cliente toma decisões usando mecanismo de votação, é 
possível tolerar que k processos de 2k+1 forneçam resultados errados
 Em geral, contudo, supõe-se que processos não se agrupem para fornecer 
resultado incorreto
 Situação é mais complexa quando grupo deve entrar em acordo:
 Ex.: eleição de coordenador, decisão sobre efetivação de uma transação 
(commit), divisão de tarefas entre trabalhadores, sincronização.
 Algoritmos de acordo distribuído (distributed agreement algorithms) visam 
a fazer os processos não faltosos entrarem em acordo sobre algo, 
estabelecendo um consenso num número definido de passos
 Aspectos:
 Processos podem operar de maneira síncrona (lockstep) ou assíncrona
 Atraso de comunicação (communication delay) pode ser limitado (bounded), em que 
apresenta tempo máximo determinado, ou não (unbounded) 
 Entrega das mensagens pode ser ordenada ou não. Msgs do mesmo emissor são, então, 
entregues na mesma ordem de envio, ou não se pode garantir
 Transmissão de mensagem pode ocorrer via unicast ou multicast
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 24 Hélio Crestana Guardia - 2011
Acordo em sistemas com falta (faulty systems)
Condições necessárias para obtenção de acordo: 
 Processos: Synchronous ⇒ operate in lockstep 
 Atrasos: Are delays on communication bounded? 
 Ordenação: Are messages delivered in the order they were sent? 
 Transmissão: Are messages sent one-by-one, or multicast?
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 25 Hélio Crestana Guardia - 2011
Acordo em sistemas com falta (faulty systems)
 Cada processo reporta o seu valor para os demais
 Todos constroem um vetor V de tamanho N. Se processo i não tem falta, V[i]=vi; 
senão, V[i] é indefinido.
 (a) 3 propaga valores incorretos (x,y,z); (c) 3 propaga os vetores com todos os 
valores incorretos novamente (a, b, ..., k, l).
 Ao final da etapa (c), processos entram em acordo sobre valores v1, v2 e v4. Valor 
de v3 não pode ser decidido, mas isso não é relevante
 Objetivo do acordo Bizantino é que consenso seja obtido para os processos que não 
têm faltas 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 26 Hélio Crestana Guardia - 2011
Acordo em sistemas com falta (faulty systems)
 Nesse caso, na etapa (c), não é possível obter acordo para os valores 1, 2 ou 3
 Para suportar falta em k nós, acordo só é possível se 2k+1 processos não têm faltas
 Nesse caso, se mais de 2/3 dos processos estão operando de maneira adequada 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 27 Hélio Crestana Guardia - 2011
Detecção de falha
 Mascaramento de falha requer sua identificação prévia
 Membros do grupo que não têm falta devem ser capazes de detectar quem ainda é 
membro do grupo e quem apresentou falta e deve ser removido
 Mecanismos:
 Envio de msg: “are you alive?” entre os nós, e espera por resposta – ping ativo
 Espera passiva até que mensagens cheguem dos diferentes processos (viável 
apenas se há comunicação suficiente (frequente) entre os nós
 Mecanismo de timeout é usado para verificar se processo tem falta
 Problema: ausência de resposta pode indicar erroneamente que processo tem falta
 Implementação pode considerar mecanismo de gossiping, em que nó propaga 
informações do seu estado aos vizinhos
 Detecção de faltas também pode ser feita como um efeito colateral do uso de 
gossiping para troca de informações entre os vizinhos, propagando informações 
sobre os estados dos nós
 Eventualmente, todo processo terá informações suficientes para decidir sobre o 
estado dos demais e se há processos com falta
 Necessidade de distinguir falha da rede e falha de um processo
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 28 Hélio Crestana Guardia - 2011
Comunicação confiável entre cliente e servidor
• Tolerância a falta normalmente concentra-se na detecção de falta de processo
• Faltas na comunicação também devem ser consideradas
• Modelos de falha também se aplicam aos canais de comunicação: crash, 
omissão, timing e arbitrárias.
• Construção de canais de comunicação normalmente foca no mascaramento 
de falhas do tipo crash e omissões
• Falhas arbitrárias podem ocorrer na forma de mensagens duplicadas, 
resultantes de armazenamento temporário e retransmissões
• Na comunicação ponto-a-ponto, confiabilidade é obtida com o uso de 
protocolos de transporte confiável, como TCP
– Mensagens de reconhecimento e retransmissões mascaram omissões
– Falhas na conexão TCP podem ser tratadas permitindo que SD tente 
estabelecer uma nova conexão
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 29 Hélio Crestana Guardia - 2011
Falhas em RPC
• RPCs visam esconder detalhes da comunicação, tornando chamadas remotas 
semelhantes às chamadas locais
• Falhas possíveis:
1. Cliente não consegue localizar o servidor
2. Mensagem do cliente não chega ao servidor (pedida)
3. Servidor cai (crashes) depois de receber pedido
4. Resposta do servidor ao cliente é perdida
5. Cliente cai (crashes) depois de enviar pedido
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 30 Hélio Crestana Guardia - 2011
Falhas em RPC
1. Cliente não consegue localizar o servidor
• Servidores todos podem ter caído (down) 
• Cliente pode estar usando versão stub antiga incompatível com versão atual 
do servidor
– Erro pode gerar exceção (exception – Java, ou sinal específico – C)
– Nem toda linguagem tem suporte
2. Mensagem do cliente não chega ao servidor (pedida)
• Pode ser tratada com timer mantido plo SO ou pelo client stub 
• Expiração de timeout antes de resposta ou reconhecimento gera 
retransmissão 
• Servidor pode precisar diferenciar retransmissões de novas chamadas
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 31 Hélio Crestana Guardia - 2011
Falhas em RPC
3. Servidor cai (crashes) depois de receber pedido
 Possíveis tratamentos dependem do que é esperado pelo cliente:
● Semântica at-least-once (ao menos uma vez): sistema cliente continua tentando 
(retransmitindo pedido) até uma resposta seja recebida. Nesse caso, RPC terá sido 
executada ao menos 1 vez.
● Semântica at-most-once (no máximo uma vez): clientedesiste imediatamente e 
retorna indicação de falha. RPC terá sido executada no máximo 1 vez, mas 
possivelmente nenhuma.
● Semântica exactly once (exatamente uma vez)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 32 Hélio Crestana Guardia - 2011
Falhas em RPC
3. Servidor cai (crashes) depois de receber pedido (exemplo)
Eventos: 
● (M): envio de mensagem de conclusão de serviço pelo servidor
● (C): crash 
● (P): impressão
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 33 Hélio Crestana Guardia - 2011
Falhas em RPC
4. Resposta do servidor ao cliente é perdida
● Ausência de resposta pode gerar retransmissões depois da expiração de 
temporizadores
● Problema: como saber se servidor recebeu pedido (e realizou serviço)?
● Solução: tentar tornar operações idempotentes (repetíveis sem efeitos 
indesejados)
● Para operações não idempotentes pode-se atribuir número de sequência para 
requisições de cada cliente
● Números permitem ao servidor diferenciar pedido de retransmissões. Servidor 
tem que manter informações de estado.
● Mensagens podem conter (bit) identificador de retransmissão: novos pedidos 
podem ser realizados imediatamente. Retransmissões requerem tratamento.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 34 Hélio Crestana Guardia - 2011
Falhas em RPC
5. Cliente cai (crashes) depois de enviar pedido
● Problema: servidor está realizando solicitação e mantendo recursos por nada
● Computação órfã gera desperdício de recursos de processamento
● Pode haver bloqueio de recursos
● Soluções:
● Client stub salva registro (log) em disco (persistente) antes de realizar chamada 
RPC. Depois de um reinício (reboot) computação órfã é explicitamente 
encerrada (or rolled back): orphan extermination 
– Possibilidade de surgimento de grandorphans, e atrasos para acesso ao 
disco antes de RPCs tornam proposta não interessante
● Tempo é dividido em épocas; ao reiniciar, cliente divulga uma mensagem às 
demais máquinas declarando nova época. Ao receber mensagem, nó remove 
todas as computações anteriores daquele cliente. Falha na rede pode gerar 
órfãos ativos. Estratégia conhecida como reencarnação (reincarnation).
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 35 Hélio Crestana Guardia - 2011
Falhas em RPC
5. Cliente cai (crashes) depois de enviar pedido (cont)
● Soluções (cont.):
● Gentle reincarnation: ao receber mensagem de nova época, servidor tenta 
localizar todos os clientes remotos associados. Na ausência de comunicação, 
computações são encerradas.
● Expiration: cada RPC recebe um tempo (T) para conclusão. Se não for 
concluída nesse tempo, RPC deve negociar novo prazo. Em caso de reiniciação, 
servidor pode encerrar requisições órfãs depois de tempo T.
● Problemas:
● Encerramento das computações órfãs pode ter consequência imprevistas
● Requisições podem ter bloqueado recursos 
● Requisições podem ter iniciado outras requisições...
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 36 Hélio Crestana Guardia - 2011
Comunicação em grupo confiável
Reliable multicasting
● Multicast confiável é importante para garantir que mensagens sejam entregues a 
todos os processos replicados num grupo
● Protocolos de transporte oferecem comunicação confiável apenas ponto-a-ponto 
● Possível abordagem para multicast confiável consiste em criar-se vários canais 
unicast, um para cada receptor: solução ineficiente
● Situações envolvem diferentes aspectos se processos membros do grupo podem 
variar, saindo por falha, ou ingressando no grupo, durante transmissão de mensagem
● Como garantir que mensagem seja entregue aos processos do grupo apenas se todos 
receberem?
● Transmissor associa número a cada mensagem transmitida
● Mensagens são transmitidas em sequência
● Mensagens transmitidas são mantidas em buffer no transmissor até que todos os 
destinatários confirmem recebimento
● Receptores conseguem identificar mensagens fora de ordem e geram 
reconhecimento negativo (negative acknowledgment) solicitando retransmissão
● Transmissor também pode manter temporizador que indica necessidade de 
retransmissão em caso de ausência de resposta
● Reconhecimentos podem ser enviados “de carona” em mensagens
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 37 Hélio Crestana Guardia - 2011
Comunicação em grupo confiável
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 38 Hélio Crestana Guardia - 2011
Comunicação em grupo confiável
● Abordagem usando reconhecimento não é adequada para grande 
número de receptores (não escalável)
● Possibilidade de envio apenas de reconhecimento negativo: 
● Diminuição das mensagens de confirmação
● Transmissor precisa manter mensagens em buffer, por tempo 
indeterminado
● Ausência de reconhecimento pode dever-se a falha
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 39 Hélio Crestana Guardia - 2011
Comunicação em grupo confiável
Controle de reconhecimento (feedback) não hierárquico
● Proposta: Scalable Reliable Multicasting (SRM)
● Receptores geram notificações apenas para mensagens não recebidas
● Identificação de mensagem não recebida é deixada a cargo da aplicação
● Ao detectar falha, receptor notifica os demais processos no grupo via 
multicast
● Outros membros do grupo com falha não precisam gerar notificações 
também
● Supondo que m processos podem ter falha de recebimento, uso de 
multicast gera economia de transmissões
● Atraso aleatório é introduzido antes do envio da mensagem de feedback
● Algoritmo tem boa escalabilidade, mas pode fazer com que processos 
tenham que tratar transmissões de mensagens já recebidas.
● Possibilidade de criação de sub-grupos; requer gerenciamento eficiente de 
grupos
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 40 Hélio Crestana Guardia - 2011
Comunicação em grupo confiável
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 41 Hélio Crestana Guardia - 2011
Comunicação em grupo confiável
Controle de reconhecimento (feedback) hierárquico
● Escalabilidade no envio de mensagens para grandes grupos requer 
abordagem hierárquica
● Receptores são particionados em subgrupos e organizados na forma de uma 
árvore.
● Dentro de cada subgrupo, qualquer mecanismo de entrega, adequado para 
pequenos grupos, pode ser usado.
● Cada subgrupo determina um coordenador local, que passa a ser 
responsável pelos envios de pedidos de retransmissão deste subgrupo
● Coordenador local tem seu próprio buffer de histórico de transmissões. 
Mensagens recebidas por todos no subgrupo podem ser descartadas.
● Questão: dificuldade para construção da árvore.
● Normalmente, roteador multicast no grupo é usado como coordenador
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 42 Hélio Crestana Guardia - 2011
Comunicação em grupo confiável
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 43 Hélio Crestana Guardia - 2011
Multicast atômico
● Comunicação multicast confiável implica que mensagens sejam 
entregues a todos os processos ou a nenhum
● Mensagens também devem ser entregues na mesma ordem a todos os 
processos
● Considerando que operações são replicadas em vários processos de 
um grupo, aplicação das operações depende de processos estarem em 
acordo sobre quem participa do grupo (está ativo), de forma que ou 
todos realizem as operações, ou nenhum
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 44 Hélio Crestana Guardia - 2011
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 45 Hélio Crestana Guardia - 2011
Sincronia Virtual
● Há apenas uma situação em que entrega de mensagem pode falhar: 
quando participação no grupomuda como resultado do emissor da 
mensagem m quebrar (crash)
● Nesse caso, m deve ser entregue a cada um dos processos restantes, 
ou pode ser ignorada por todos os membros do grupo, como se o 
emissor tivesse quebrado antes do envio
● Multicast confiável com essas características é denominado 
virtualmente síncrono (virtually synchronous) 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 46 Hélio Crestana Guardia - 2011
Sincronia Virtual
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 47 Hélio Crestana Guardia - 2011
Ordenação de mensagens
● Estratégias para ordenação de mensagens multicast:
● Multicasts não ordenados
● Multicasts ordenados em FIFO
● Multicasts ordenados por causalidade
● Multicasts totalmente ordenados
● Multicast confiável não ordenado é um multicast virtualmente síncrono 
sem garantias sobre a ordem em que mensagens recebidas são entregues aos 
diferentes processos
● Com multicasts ordenados em FIFO, camada de comunicação deve entregar 
as mensagens aos processos na mesma ordem em que foram enviadas
● Multicast confiáveis ordenados por causalidade entregam mensagens de 
forma que potenciais causalidades entre mensagens diferentes é preservada
● Com multicasts totalmente ordenados, independente de ordenações entre 
as mensagens, todos os processos as recebem na mesma ordem
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 48 Hélio Crestana Guardia - 2011
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 49 Hélio Crestana Guardia - 2011
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 50 Hélio Crestana Guardia - 2011
Implementação de sincronia virtual
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 51 Hélio Crestana Guardia - 2011
Implementação de sincronia virtual
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 52 Hélio Crestana Guardia - 2011
Comprometimento (commit) distribuído
● Comprometimento (commit) distribuído trata de fazer com que uma 
operação seja executada por cada membro de um grupo, ou por nenhum
● No cado do multicast confiável, operação é a entrega de mensagem
● Com transações distribuídas, operação pode ser o comprometimento de uma 
transação
● Commit distribuído é normalmente estabelecido por meio de um 
coordenador. 
● One-phase commit protocol: coordenador diz aos processos envolvidos 
quando realizar as operações
● Two-phase commit protocol:
● Three-phase commit protocol: 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 53 Hélio Crestana Guardia - 2011
Two-phase commit (2PC)
Comprometimento de duas fases
● Participação de vários processos executando em máquinas diferentes
● Duas fases: fase de votação e fase de decisão
● The client who inititated the computation acts as coordinator; processes required to 
commit are the participants
● Phase 1a: Coordinator sends vote-request to participants (also called a pre-write) 
● Phase 1b: When participant receives vote-request it returns either vote-commit or 
vote-abort to coordinator. If it sends vote-abort, it aborts its local computation
● Phase 2a: Coordinator collects all votes; if all are vote-commit, it sends global-
commit to all participants, otherwise it sends global-abort 
● Phase 2b: Each participant waits for global-commit or global-abort and handles 
accordingly.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 54 Hélio Crestana Guardia - 2011
Comprometimento de 2 fases
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 55 Hélio Crestana Guardia - 2011
Two-phase commit (2PC)
Comprometimento de duas fases – falha de participante
Ausência de resposta é identificada com timeout e gera mensagem para abortar 
(Global-abort / coordenador, Vote-abort / processo)
Scenario: participant crashes in state S, and recovers to S 
● Initial state: No problem: participant was unaware of protocol
● Ready state: Participant is waiting to either commit or abort. After 
recovery, participant needs to know which state transition it should make ⇒ 
log the coordinator’s decision
● Abort state: Merely make entry into abort state idempotent, e.g., removing 
the workspace of results
● Commit state: Also make entry into commit state idempotent, e.g., copying 
workspace to storage.
Observation: when distributed commit is required, having participants use 
temporary workspaces to keep their results allows for simple recovery in the 
presence of failures.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 56 Hélio Crestana Guardia - 2011
Two-phase commit (2PC)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 57 Hélio Crestana Guardia - 2011
Two-phase commit (2PC)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 58 Hélio Crestana Guardia - 2011
Two-phase commit (2PC)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 59 Hélio Crestana Guardia - 2011
Three-phase commit (3PC)
Comprometimento de 3 fases
● Evita que participantes tenham que esperar pela recuperação do coordenador quando 
este falha
Model (Again: the client acts as coordinator)
● Phase 1a: Coordinator sends vote-request to participants
● Phase 1b: When participant receives vote-request it returns either vote-commit or 
vote-abort to coordinator. If it sends vote-abort, it aborts its local computation
● Phase 2a: Coordinator collects all votes; if all are vote-commit, it sends prepare-
commit to all participants, otherwise it sends global-abort, and halts
● Phase 2b: Each participant waits for prepare-commit, or waits for global-abort after 
which it halts
● Phase 3a: (Prepare to commit) Coordinator waits until all participants have sent 
ready-commit, and then sends global-commit to all
● Phase 3b: (Prepare to commit) Participant waits for global-commit
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 60 Hélio Crestana Guardia - 2011
Three-phase commit (3PC)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 61 Hélio Crestana Guardia - 2011
Three-phase commit (3PC)
3C – Failing participant
● Basic issue: Can P find out what it should it do after crashing in the ready or pre-
commit state, even if other participants or the coordinator failed?
Reasoning
● Essence: Coordinator and participants on their way to commit, never differ by more 
than one state transition
● Consequence: If a participant timeouts in ready state, it can find out at the 
coordinator or other participants whether it should abort, or enter pre-commit state
● Observation: If a participant already made it to the pre-commit state, it can always 
safely commit (but is not allowed to do so for the sake of failing other processes)
● Observation: We may need to elect another coordinator to send off the final 
COMMIT
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 62 Hélio Crestana Guardia - 2011
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 63 Hélio Crestana Guardia - 2011
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 64 Hélio Crestana Guardia - 2011
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 8: Tolerância a falha / 65 Hélio Crestana Guardia - 2011
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65

Outros materiais

Materiais relacionados

Perguntas relacionadas

Materiais recentes

130 pág.

Perguntas Recentes