sistemas distribuídos

Tolerância a falhas em sistemas distribuídos UFRGS Taisy Silva Weber 2005

Níveis - [Jalote 94]

diversidade blocos de recuperação tratamento de exceções

software tolerante a falhas resiliência de processos serviços

resiliência de dados ações atômicas recuperação para um estado consistente

blocos básicos

difusão confiável e atômica, multicast, membership processador fail-stop, armazenamento estável, consenso bizantino, comunicação confiável sistema distribuído sem memória compartilhada sem relógio global

Taisy Weber

2

Sistema distribuído modelo físico estações de usuários

Interface de Programação Middleware: replicação, resiliência, recuperação, comunicação de grupo

rede

estações de processamento

Taisy Weber

dual storages servidor

Sistema Operacional

modelo lógico: processos distribuídos, troca de mensagens

3

Modelos de tempo 9 sistema assíncrono

modelos síncrono e assíncrono podem ser considerados extremos teóricos, outros modelos misturam características desses extremos

9 não existem limites de tempo impossível alcançar consenso em sistemas assíncronos

9 sistema síncrono 9existe um limite de tempo finito e conhecido

sistema correto opera dentro desse limite

9falha de componente pode ser deduzida pela ausência de resposta 9timeout detecção de defeitos em nodos e perdas de mensagens Taisy Weber

4

Classificação de falhas (Cristian) sem resposta para algumas entradas

parada ou perda do estado interno

crash

omissão

temporização

respostas incorretas para algumas entradas

resposta arbitrária

resposta adiantada ou retardada comportamento totalmente arbitrário e imprevisível Taisy Weber

5

Exemplos de falhas 9 processador: 9 crash ou bizantinas 9 rede de comunicação: 9 todos os tipos 9 clock: 9 temporização ou bizantinas

9 meio de armazenamento 9 temporização, omissão ou resposta 9 software: 9 resposta

o modelo de falhas é uma simplificação da realidade, na literatura existem vários outros modelos de falhas sugeridos para sistemas distribuídos

Taisy Weber

6

Sistemas distribuídos: modelo físico NODO relógio local

memória local

processador

armazenamento não volátil

Taisy Weber

interface de rede

R COM EDE D E UN I CAÇ ÃO men sage ns

7

Modelo lógico 9 aplicação distribuída 9 conjunto de processos concorrentes 9 processos cooperativos 9cada processo é seqüencial 9cada processo pode estar em um nodo diferente 9 progresso finito 9nada pode ser dito sobre velocidades relativas 9todos os processos avançam na execução

Taisy Weber

8

Modelo lógico 9 rede completamente conectada 9topologia não é considerada 9 processos 9 canais 9existe um canal entre quaisquer dois processos que interagem, com buffer infinito e livre de erros 9canais entregam mensagens na ordem que foram enviadas 9 características não necessariamente válidas para o meio físico

Taisy Weber

9

Canal cb a

pi

ordem de mensagens preservada no canal

processo

can al

cb

a

pj

Modelo lógico Taisy Weber

10

Canal xy

pa

pc

mxyn

xy ordem parcial preservada ordem total não preservada

mn

pb

mn

pd

xmny

Modelo lógico Taisy Weber

11

Ordenação de eventos 9 dificuldade de determinar relações temporais 9 RAZÃO: inexistência de clock global 9 problema 9 determinar ordenação temporal de eventos que ocorrem em nodos diferentes, medidos por relógios diferentes 9 relação: a “aconteceu antes de” b : a → b

Taisy Weber

12

Ordenação de eventos 9 ordem parcial 9 se a e b são eventos do mesmo processo e a é executado antes de b então a → b 9 se a é send e b é receive da mesma mensagem então a → b 9 a → b e b → c então a → c 9 eventos concorrentes: é possível estabelecer 9nem a → b, nem b → a uma ordem total não temporal com relógios lógicos

Taisy Weber

13

Clocks lógicos 9 Lamport 78 9meio de assinalar um número a um evento 9 nenhuma relação com o tempo físico

9 sistema de clock lógico 9um sistema de clock lógico é correto se é consistente com a relação → 9 clock lógico 9carimba um evento de forma que a relação de ordem parcial é mantida exemplo: timestamp T Taisy Weber

14

Blocos básicos software tolerante a falhas resiliência de processos serviços

resiliência de dados ações atômicas recuperação para um estado consistente

blocos básicos

difusão confiável e atômica, multicast, membership processador fail-stop, armazenamento estável, consenso bizantino, comunicação confiável sistema distribuído sem memória compartilhada sem relógio global

Taisy Weber

15

Concordância bizantina 9 problema dos generais bizantinos 9 alcançar consenso na presença de traidores 9 defeitos bizantinos 9 quando um sistema apresenta defeito, seu comportamento pode ser totalmente arbitrário 9nodo pode enviar informações diferentes para os diferentes componentes com quem se comunica

Taisy Weber

16

Problema dos generais bizantinos 9 generais sitiam cidade inimiga 9alguns generais são traidores 9devem chegar a consenso sobre atacar ou recuar 9generais traidores não devem poder atrapalhar o consenso 9 ou seja, traidores não podem provocar divisão (alguns atacam e outros recuam)

9 concordância bizantina 9consenso na presença de falhas arbitrárias

Taisy Weber

17

Objetivo básico 9 consenso entre todos os nodos sem defeitos (não traidores) 9 não traidores devem tomar a mesma decisão 9devem obter o mesmo conjunto de valores e 9executar o mesmo algoritmo sobre os valores 9 traidores podem enviar valores diferentes para nodos diferentes

Taisy Weber

18

Requisitos formais 9 todos os nodos não traidores usam o mesmo valor v(i) para o nodo i 9não necessariamente o valor recebido do nodo i 9 se o nodo transmissor i é não traidor 9 então todo nodo não traidor usa o valor v(i) transmitido por i 9não interessa os valores que os traidores usam 9idem valores transmitidos por traidores

Taisy Weber

19

Comentários 9 um nodo traidor pode agir maliciosamente atrapalhando o consenso 9 traidores podem enviar valores diferentes para diferentes nodos 9 mensagens de confirmação podem ser falsificadas pelos traidores

9 consenso é impossível em sistemas assíncronos 9mesmo com um único traidor 9mesmo quando só ocorrem falhas de crash Lamport não chegou a provar para qualquer falha, apenas para falhas bizantinas Taisy Weber

20

Algoritmos de Lamport 9 Lamport 82 (Lamport, Shostak e Pease) 9 solução para: 9sistemas síncronos 9sistema totalmente conectado 9 mensagens orais: n ≥ 3 m +1 9algoritmo de consistência interativa (ICA) 9 mensagens assinadas: n ≥ m + 2 9 grande número de rodadas: m + 1 9 grande número de mensagens: O(nm)

Taisy Weber

21

Protocolo para mensagens orais 9 mensagens comuns, sem assinatura 9 n nodos, m traidores 9 solução possível para n ≥ 3m+1 9 premissas: 9A1: toda mensagem enviada é recebida corretamente 9A2: o receptor sabe quem enviou a mensagem 9A3: a ausência de uma mensagem pode ser detectada (time-outs)

Taisy Weber

22

Algoritmo 9 ICA(0) 9o general envia o seu valor para os outros n-1 nodos 9cada nodo usa o valor recebido, ou default se não recebeu nenhum valor 9 (fim da recursão)

Taisy Weber

23

Algoritmo 9 ICA(m), m>0 9o general envia o seu valor para os outros n-1 nodos 9nodo i 9 v(i) (valor recebido pelo nodo i ou default), 9 nodo i atua como general em ICA(m-1) enviando v(i) para os demais n-2 nodos (confirmação do valor)

9para cada nodo i: 9 v(j) valor recebido do nodo j (j≠i) 9 nodo i usa valor maioria(v(1), ..., v(n-1))

Taisy Weber

24

ICA(m) general

ICA(m) deve ser usado por todos os nodos para alcançar consenso

rodada 1 ICA(0)

ICA(1) no máximo um traidor usando ICA(m) em cada nodo, cada nodo do sistema terá o mesmo valor assumido para todos os outros nodos Taisy Weber

rodada 2 25

Concordância bizantina 9 algoritmos de Lamport 9ótimo em relação ao número de rodadas 9mas exigem número exponencial de mensagens 9 outros algoritmos foram propostos 9alguns mais eficientes em relação ao número de mensagens 9alguns suportam sistemas não totalmente conectados 9alguns suportam sistemas assíncronos através de procedimentos randômicos Taisy Weber

26

Relógios sincronizados facilitaria a implementação de serviços tolerantes a falhas importante em sistemas de tempo real

9 ordem total temporal 9sincronização externa

Network Time Protocol

NTP não é solução

9 manter clocks com desvio máximo em relação a referência externa de tempo

9sincronização interna

GPS não evita a necessidade de algoritmos de sincronização

9 manter clocks com desvio relativo máximo aceitável entre si ordenação total não temporal pode ser alcançada com relógios lógicos de Lamport a partir de ordenação parcial de eventos Taisy Weber

27

Sincronização: problemas 9relógios diferentes podem marcar tempos diferentes e ter velocidades diferentes 9 valores de cada relógio devem ser comunicados para haver sincronização

retardo na rede de comunicação pode variar randomicamente

Exemplo de protocolo de sincronização: Lamport (85) semelhante ao algoritmo de mensagem orais em consenso bizantino a sincronização de relógios de tempo real é uma tarefa de alto custo, pois envolve grande quantidade de mensagens, e deve ser evitada se possível a maior parte dos problemas de ordenação em sistemas convencionais, inclusive ordenação total, pode ser resolvida com clocks lógicos (Lamport)

Taisy Weber

28

Global positioning system sincronização externa

9 rede de satélites que difunde valores altamente acurados de tempo real desenvolvido para suporte a sistemas de localização

9 baixo custo 9 modelo de falhas do GPS 9usual: crash 9distorções atmosféricas 9problemas com antenas (recepção do sinal) GPS não dispensa protocolos de sincronização

Taisy Weber

29

Armazenamento estável essencial em vários esquemas de suporte a tolerância a falhas

9 parte do estado do sistema permanece disponível mesmo após defeito do sistema 9 conteúdo é preservado apesar de falhas 9 um disco magnético não é armazenamento estável

9 exemplos de implementação: 9 sombreamento de disco 9 conjunto de imagens idênticas em dispositivos separados 9 2 discos - espelhamento Tandem 9 RAID: Redundant Array of Inexpensive Disks I pode ser também Independent Taisy Weber

30

Defeitos em discos discos não são suficientemente robustos: dependendo do sistema de arquivos, um único setor perdido pode inutilizar todo o disco (por exemplo nos sistemas FAT)

9 exemplos: 9 transientes 9 bad sector 9 defeito na controladora 9dados no meio magnético não são perdidos 9 defeito de disco 9o conteúdo não pode ser mais recuperado

sistemas de arquivo mais robustos usando journaling tem sido implementados com sucesso, exemplo: ReiserFS, JFS, ext3fs, XFS, NTFS, mas ainda não podem ser considerados como armazenamento estável Taisy Weber

31

Exemplos de implementação 2 discos = espelhamento

9 sombreamento de disco 9conjunto de imagens idênticas de um disco em dispositivos separados 9 RAID 9Redundant Array of Inexpensive Disks 9 propostos inicialmente para diminuir custos de armazenamento e prover alta velocidade

9bit interleaving: entrelaçamento de bits 9 aumenta velocidade permitindo operação em paralelo, mas diminui confiabilidade; colocando mais discos ou mais código de recuperação de erros esse problema pode ser contornado Taisy Weber

32

RAID 0, 1 e 2

http://pt.wikipedia.org/wiki/RAID

9 RAID 0 9não é array 9 RAID 1 9dois discos idênticos espelhados 9método mais caro (100% redundância) 9 RAID 2 9bits entrelaçados palavra + código JUNÇÃO DE DOIS OU MAIS DISCOS EM UM ÚNICO DISCO VIRTUAL

9 capacidade de correção de 1 bit ou detecção de 2 bits

9número de discos depende do algoritmo de correção de erros Taisy Weber

33

RAID 3 e 4 9 RAID 3 9bits entrelaçados + disco extra para paridade 9só permite verificação de paridade 9 RAID 4 9como RAID 3, mas com setores entrelaçados 9vantagem para o SO 9pode ser implementado em um único disco físico

Taisy Weber

34

RAID 5 e 6

existem combinações

o mais popular

9 RAID 5 9como RAID 3 mas sem disco de paridade 9 paridade é distribuída pelos discos do sistema

9pode ser implementado a partir de dois discos além da paridade distribuída 9 RAID 6 9como RAID 5, mas com mais um disco de paridade 9 dois discos podem falhar sem perda de dados 9 pode trocar drive defeituoso com sistema em operação

9degrada para RAID 5 quando 1 disco está defeituoso HOJE (2006): RAID 10 e RAID 50.

Taisy Weber

35

Processadores fail-stop 9 em caso de defeito, nodo cessa operação sem realizar qualquer ação incorreta 9comportamento fail-stop assumido por grande parte dos esquemas de TF 9 processadores reais não são por natureza fail-stop 9 processadores reais com defeito se comportam de maneira arbitrária

9nodos aproximadamente fail-stop podem ser construídos a partir de processadores reais (k failstop) exemplo: Stratus Taisy Weber

36

k fail-stop

comporta-se como um processador fail-stop a menos que k+1 ou mais componentes falhem

processadores comuns com comportamento bizantino

P1

clocks sincronizados e na mesma Pk velocidade

armazenamento estável k+1 mensagens sincronizadas

Pk+1 executam mesma seqüência de requisições para Ps

Taisy Weber

nunca falha e detecta falta de mensagem ou discordância de ordem ou conteúdo

Ps falha em qualquer processador bloqueia operações sobre o armazenamento estável rede confiável e origem da mensagem pode ser autenticada pelo receptor 37

Entrega confiável de mensagens processo

aplicação

cb

a b c

a

pi

SEND

nodos e links sujeitos a falhas

DESEJÁVEL: conteúdo preservado (confiabilidade) ordem das mensagens preservada (ordenação)

devem valer em caso de defeitos em nodos ou links, devem valer mesmo no caso de particionamento da rede

RECEIVE

DELIVERY

cba

pj

protocolo de comunicação assegura confiabilidade mesmo com rede não confiável; exemplo: numeração de mensagens e retransmissão Taisy Weber

38

Difusão de mensagens software tolerante a falhas resiliência de processos serviços

resiliência de dados ações atômicas recuperação para um estado consistente

blocos básicos

difusão confiável e atômica, multicast, membership processador fail-stop, armazenamento estável, consenso bizantino, comunicação confiável sistema distribuído sem memória compartilhada sem relógio global

Taisy Weber

39

Tipos de difusão 9 broadcast 9envio de mensagens a todos os nodos do sistema multicast envolve o conceito de grupo

9 multicast 9envio de mensagens a alguns nodos do sistema 9 sensível a falhas de nodo e comunicação em broadcast ou multicast sobre comunicação ponto a ponto: um nodo pode falhar após ter iniciado difusão, assim alguns nodos podem ter recebido a mensagem e outros não

também existem problemas com redes de broadcast e multicast não confiável Taisy Weber

40

Propriedades na difusão valem tanto para broadcast como multicast

9 confiabilidade 9 mensagem deve ser recebida por todos os nodos operacionais

9 ordenamento consistente

ordenamento consistente é diferente de ordenamento temporal

9 diferentes mensagens enviadas para nodos diferentes são entregues na mesma ordem em todos os nodos

9 preservação de causalidade 9 a ordem na qual mensagens são entregues é consistente com a relação causal de envio das mensagens mensagens sem relação causal poderiam ser entregues em qualquer ordem Taisy Weber

41

Primitivas de difusão 9 difusão confiável 9 uma mensagem enviada é recebida em todos os nodos não falhos na rede, mesmo na presença de falhas

9 difusão atômica 9 suporta difusão confiável e ordenação

9 difusão causal 9 assegura ordenação causal

9cada primitiva tem sua aplicação 9 mensagens isoladas: difusão confiável 9 banco de dados: difusão atômica 9 uma mensagem depende de outra: difusão causal Taisy Weber

42

Trans: protocolo de Melliar-Smith 9primitiva confiável baseada em broadcast não confiável Q

Melliar-Smith, Moser e Agrawala (1990)

ex: meio físico Ethernet ou protocolo de broadcast não confiável em comunicação ponto a ponto

P difunde m1 P

m1

1

R Taisy Weber

43

Trans 9 cada mensagem transporta: 9 identidade do transmissor e número de seqüência unívoco 9 acks e nacks na carona de mensagens difundidas P

Q difunde m2 e ack de m1 Q

m2 ackm1 2

1

R Taisy Weber

44

Trans 9 o receptor, a partir de acks e nacks, determina 9 que mensagens ele não precisa reconhecer (ack) 9 quais ele precisa pedir retransmissão 9 quais ele deve retransmitir P

Q

2

R recebeu m1 e m2 R não envia ackm1 pois Q já enviou

1

R Taisy Weber

45

Trans 9 se o receptor R determina que não recebeu m1 9 deve pedir retransmissão 9 qualquer nodo pode atender um pedido de retransmissão (não apenas o originador) P

1

sem ordenação: mensagens podem ser recebidas em cada nodo em uma ordem diferente (no exemplo m1 chegará em R após m2 ) Q

2

R não recebeu m1 R envia nackm1 pedindo 3 retransmissão m3 ackm2 nackm1 R

Taisy Weber

46

Exemplo Trans 9 A, B, C, D = mens

9 9 9 9 9 9 9

a, b, c, d = acks, a, b, c, d = nacks

A trans. de B reconhece A A Ba A Ba Cb trans. de C reconhece B, não precisa rec. A A Ba Cb Dc A Ba Cb Dc Ecd trans. de E viu por Dc que não recebeu C A Ba Cb Dc Ecd Cb A Ba Cb Dc Ecd Cb Fec algum nodo retransmite C(sem novos acks)

t Taisy Weber

47

Bibliografia 9 Jalote, P. Fault tolerance in distributed systems. Prentice Hall, Englewood Cliffs, New Jersey, 1994 9OBS: nas notas de aulas da disciplina, um roteiro básico pode ser encontrado com um resumo dos tópicos discutidos neste item.

http://www.inf.ufrgs.br/~taisy/disciplinas/textos/indiceroteiro.htm

Taisy Weber

48