Baixe o app para aproveitar ainda mais
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
Compartilhar