1999.04.30TFD - Réplicas em máquinas de estados 1 Gestão de Réplicas usando a aproximação da Máquina de Estados (Replication Management using the State-Machine

1999.04.30 TFD - Réplicas em máquinas de estados

1

Gestão de Réplicas usando a aproximação da Máquina de Estados

(Replication Management using the State-Machine Approach, Fred Schneider, 1990)

Apresentação (Grupo 2):

Nuno Pimentel

Simão Onofre


2

Máquinas de estados

Características:– Variáveis de estado

• codificam o estado

– Comandos• são executados a pedido dos clientes

• transformam o estado e produzem resultados

– Resultados são enviados para:• actuador,

• dispositivo periférico

• ou cliente que solicitou o pedido


3

Máquinas de estados (cont.)

Requisitos– comandos concretizados por programas determinísticos– a execução de cada comando é atómica com respeito aos

outros comandos Caracterização semântica

– Os resultados (output) de uma máquina de estados são completamente determinados pela sequência de pedidos por ela processados, independentemente do tempo e de qualquer outra actividade no sistema.


4

Máquinas de estados (cont.)

Pedidos processados, um de cada vez, numa ordem potencialmente causal

– Clientes podem assumir:• O1: Pedidos R(C, M) e R’(C, M) são processados pela

máquina de estados M pela ordem em que foram solicitados.

• O2: Se R’(C’, M) puder ter sido causado por R(C, M) então M processa R antes de R’.


5

Coordenação de réplicas

Replicação - tipos– activa: aproximação da máquina de estados– passiva: primário-secundário

Aproximação da máquina de estados– Todas as réplicas recebem e processam a mesma sequência

de pedidos• Acordo

– Todas as réplicas não faltosas recebem todos os pedidos

• Ordem– Todas as réplicas não faltosas processam os pedidos que

recebem na mesma ordem relativa


6

Acordo

Transmissor– processador que dissemina valor pelos outros processadores

Protocolo deve garantir:– IC1: Todos os processadores não faltosos acordam no

mesmo valor– IC2: Se um transmissor é não faltoso então todos os

processadores não faltosos usam o valor do transmissor como o valor acordado


7

Acordo (cont.)

Falha do transmissor– Falhas bizantinas

• Strong and Dolev [1983]

– Falhas por paragem• Gries and Schlichting [1984]

Perda ou corrupção do pedido– Cliente é transmissor

• é irrelevante

– Cliente não é transmissor• monitorizar difusão do pedido


8

Ordem e Estabilidade

A cada pedido é atribuido um identificador único (uid) Réplicas ordenam pedidos seguindo uma relação de

ordem total entre os uid Um pedido é estável se não puder ser recebido nenhum

outro pedido (de um cliente correcto) com um uid menor

Uma réplica processa de seguida o pedido estável com o menor uid (Concretização da Ordem)


9

Utilização de Relógios Lógicos

Sistemas em que processos/mensagens podem sofrer atrasos arbitrários, sem se poder assumir a sua falha:

– Falhas bizantinas • está provado que é impossível estabelecer o acordo

• possibilidade de definir teste de estabilidade e ordem é irrelevante

– Falhas por paragem• garantir canal FIFO entre cada par de processadores

• pode assumir-se que um processador P apenas detecta a falha de um proc. P’ após ter recebido a ultima msg que lhe foi enviada por este


10

Utilização de Relógios Lógicos

Teste de estabilidade com tolerância a falhas por paragem:

– Cada cliente Ci efectua periodicamente algum pedido (eventualmente nulo) à máquina de estados M

– Um pedido P é estável na réplica Mj se já foi recebido um pedido com timestamp superior de cada cliente executado num processador não faltoso


11

Utilização de Relógios Físicos uids formados por Tp(e)+<id_processador> Para garantir O1 e O2:

– O1 - cada cliente não pode fazer mais do que um pedido entre dois ticks sucessivos do relógio do respectivo processador

– O2 - o grau de sincronização dos relógios tem de ser melhor do que o tempo mínimo de entrega de mensagens

Testes de estabilidade – Um pedido (R) é considerado estável numa réplica Mi a ser

executada no processador P se• I) o relógio local em P ler T e uid(R) < (T - ) ou

• II) já foi recebido um pedido com uid superior de cada cliente


12

Identif. gerados pelas réplicas

Fases– 1ª: cada réplica Mi propõe identificador candidato

cuid(Mi,R)

– 2ª: é seleccionado um dos cuid(Mi,R) que passa a uid(R)

Vantagens– a única comunicação necessária é entre o processador que

executa o cliente e os processadores que executam as réplicas


13

Identif. gerados pelas réplicas (cont.)

Definições– Visto(Mi, R): réplica Mi recebeu pedido R e propôs

cuid(Mi,R)

– Aceite(Mi, R): réplica Mi conhece a decisão uid(R)

Restrições– UID1: uid(R) cuid(Mi,R)

– UID2: Se Visto (Mi, R’) depois de Aceite (Mi, R) então cuid(Mi, R’) > uid(R)


14


Teste de estabilidade– Aceite(Mi, R) é estável desde que não exista R’ tal que:

• Visto(Mi, R’)

• não esteja Aceite(Mi, R’)

• e cuid(Mi, R’) uid(R)

Para assegurar O1 e O2:– O cliente só efectua novamente comunicações quando cada

réplica tiver recebido o pedido


15


Protocolos de geração de uids e cuids devem assegurar:– UID1 e UID2– Se R R’ então uid(R) uid(R’)– Todo Visto(M, R) eventualmente passa a Aceite(M, R)

Cada réplica Mi mantém duas variáveis:– VISTOi - maior cuid(Mi, R) atribuído a qualquer pedido R

até ao momento visto por Mi

– ACEITEi - maior uid(R) atribuído a qualquer pedido R até ao momento aceite por Mi


16


Falhas por paragem– Ao receber um pedido R, cada réplica:

• calcula cuid(Mi, R) = max (VISTOi, ACEITEi) +1 +I

• dissemina cuid(Mi, R)

• aguarda recepção cuid(Mj, R) das réplicas não faltosas (NF)

• calcula uid(R) = maxMjNF ( cuid(Mj, R) )

• e Aceita(Mi, R)

– Optimizações• ISIS ABCAST

– cuids enviados para cliente, que calcula uid

– réplica única substitui cliente faltoso


17


Falhas bizantinas– Necessário garantir sincronização de relógios físicos– Detecção de falhas

• cada réplica utiliza timeouts para evitar ficar eternamente à espera de réplicas eventualmente faltosas

• quando réplica Mi suspeita da falha de Mj, envia a todas as réplicas a msg ‘Mj timeout’

• NF - conjunto de todas as réplicas excepto aquelas que tenham sido assinaladas como ‘Mj timeout’ por t+1 ou mais réplicas

• Eventual corrupção de cuids não tem implicações


18

Faltas de dispositivos de saída

Resultados usados fora do sistema– Falhas de votador e/ou dispositivo de saída

• Replicação de votadores e dispositivos de saída– falhas bizantinas - 2t+1 pares votador/dispositivo

– falhas por paragem - t+1 pares votador/dispositivo

• Votador crítico é externo ao sistema– flap com actuadores hidráulicos

– humano utilizador de écran de computador


19

Faltas de dispositivos de saída

Resultados usados dentro do sistema– Dispositivo de saída no cliente

• votador está no cliente

• falha do votador– cliente tambem falha

• falha no envio de mensagens– falhas bizantinas - aguardar t+1 respostas iguais

– falhas por paragem - aguardar primeira resposta que aparece

– Cliente numa réplica• optimizações na quantidade de mensagens


20

Faltas de Clientes

Replicar cliente– Votador na máquina de estados

• testar e ordenar– pedidos iguais com uids diferentes

– pedidos supostamente iguais com contextos diferentes

Programação defensiva– Efectuar testes sintácticos e semânticos nos comandos

• evitar corrupção da máquina de estados

– Estabelecer mecanismos de timeout• não receber um pedido pode ser tão prejudicial como receber

um errado


21

Utilização do tempo para efectuar pedidos implícitos

Vantagem– diminuição do nº de mensagens

Desvantagem– não permite passagem de parâmetros

Exemplos– release automático, voto por defeito


22

Reconfiguração Possíveis falhas bizantinas

– Condição de combinação• Proc(t) - Falt(t) > Proc(t)/2

– Em situação de falha• Problema: Falt(t) aumenta, diminuindo Proc(t) - Falt(t)• Solução: retirar processadores faltosos antes da condição ser violada

Apenas falhas por paragem– Condição de combinação:

• Proc(t) - Falt(t) > 0

– Em situação de falha• Problema: Falt(t) aumenta, diminuindo Proc(t) - Falt(t)• Solução: reparar ou substituir processadores faltosos antes da

condição ser violada


23

Gestão da configuração

Detecção de faltas– Um configurador por componente– Requisitos de um configurador não faltoso

• C1: Apenas é removido da configuração um elemento faltoso

• C2: Apenas é adicionado à configuração um elemento não faltoso

– Exemplo: monitorização comparativa de comportamentos– Condição de Combinação:

• configNF(elemF) + configF(elemNF) t


24

Reintegração de Objectos

Consistência com estado do sistema– e[Ri] - estado da componente e depois de processar pedidos

R0 a Ri

– elemento a reintegrar tem de adquirir estado e[Rjoin] antes de poder participar no sistema

Elementos auto-estabilizadores– estado definido pelos últimos k inputs


25

Reintegração de Objectos

Elementos não auto-estabilizadores, assumindo falhas por paragem e usando relógios lógicos

– Se Cliente ou Dispositivo de saída:• Mi envia as variáveis de estado relevantes antes de enviar

resultados de pedidos com uid(R) > uid(Rjoin)

– Se Réplica Mnew da Maquina de estados:

• Mi envia variáveis de estado e pedidos pendentes a Mnew

• e faz o relay de todas os pedidos subsequentes recebidos de cada cliente tal que uid(R) < uid(Rc), representando Rc o primeiro pedido recebido por Mnew directamente do cliente


26

Comunicação em grupo ISIS ABCAST - (Atomic Broadcast)

– Mantém a ordem de entrega dos pedidos, em todas as réplicas, mesmo que essa ordem não seja premeditada

– Protocolo síncrono CBCAST - (Casual Multicast)

– Mais fraco que o ABCAST em sincronização distribuída– Mantém a ordem causal dos pedidos na entrega – 3 a 5 vezes mais rapido que o ABCAST mas está sujeita a

atrasos– Protocolo Síncrono ou Assíncrono

ABCAST+CBCAST = Casual Atomic Multicast– Sincronia virtual


27

Trabalho associado

Trabalhos de– Lamport [1978a] e [1978b]– Schneider [1982] e [1985]

ISIS Toolkit– ABCAST– CBCAST

outros


28

Conclusões

Aproximação da Máquina de estados– Método para concretizar um serviço tolerante a faltas,

através da:• replicação de servidores

• execução das réplicas em processadores que falhem individualmente

• coordenação interacções dos clientes com as réplicas

– Bancada de trabalho adequada para compreender e definir protocolos de gestão de réplicas

«We have not yet encountered an application that could not be programmed cleanly in terms of state machines and clients»


29

Referências

“Replication Management using the State-Machine Approach” - Fred B. Schneider (1990)

RFC 992 - Kenneth Birman, T. A. Joseph (1986) “The ISIS project: Real experience with a fault tolerant

programming system”, Kenneth Birman, Robert Cooper

Documents

1999.04.30TFD - Réplicas em máquinas de estados 1 Gestão de Réplicas usando a aproximação da Máquina de Estados (Replication Management using the State-Machine