Abril 2003José Carlos Faria – José Carlos Correia Tolerância a faltas distribuídas Yair Amir & Ciprian Tutu FROM TOTAL ORDER TO DATABASE REPLICATION

Abril 2003José Carlos Faria – José Carlos Correia

Tolerância a faltas distribuídas

Yair Amir & Ciprian Tutu

FROM TOTAL ORDER TO DATABASE REPLICATION


Replicação de bases de dados é uma ferramenta critica para:

• fornecimento de elevada disponibilidade;• elevada performance nas aplicações de bases de dados.

A abordagem assegura que as bases de dados replicadas estão ao inicio e mantém-se consistentes enquanto forem aplicadas as

mesmas acções.

INTRODUÇÃO


Mesmo em redes locais (LANs) falhas na rede ocorrem regularmente, sejam provocadas por hardware (ex: switches temporariamente desligados) ou software (ex: servidores sobrecarregados)

INTRODUÇÃO

Em WAN’s as falhas são ainda mais comuns.


Os protocolos Two-phase commit mantém-se como a principal técnica para fornecer consistência numa base de dados distribuída.

TRABALHO EXISTENTE

Os protocolos Three-phase commit resolvem alguns dos problemas dos protocolos Two-phase, com o custo de rondas adicionais de comunicação.

Atomic Broad no contexto do Sincronismo Virtual emerge como uma ferramenta promissora para a resolução do problema da replicação.


Keidar propõe a utilizaçao do Extended Virtual Synchrony (EVS) num algoritmo que suporta partições e retomas na rede.

TRABALHO EXISTENTE

Kemme e Alonso provaram a correcção de alguns protocolos de replicação.


O modelo consiste numa série de nós (servidores)S = {S1, S2, ..., Sn}Onde cada um guarda uma cópia de toda a base de dados

MODELO DE SISTEMA


• Os nós comunicam por troca de mensagens.• As mensagens podem perder-se.• Servidores podem crashar.• Podem ocorrer falhas na rede.

MODELO DE COMUNICAÇÃO E FALHA

Não é assumido:• corrupção de mensagens;• faltas Bizantinas.


Um servidor que crash recupera nas seguintes condições:• detém o seu antigo identificador;• os dados estáveis


Cada nó executa vários processos:• servidor de base de dados;• motor de replicação;• camada de comunicação para a rede

O crash de um destes componentes é detectado pelos outros e é tratado como um crash global do nó.


É utilizado uma camada de serviço de comunicação com multi-distribuição de mensagens de confiança com garantias de ordenação (FIFO, causal, ordem total).

Esta camada também fornece um serviço de notificação de membros, informando o motor de replicação de quais os nós que podem ser atingidos no componente actual.


A notificação ocorre de cada vez que a conectividade é alterada, um servidor crasha/recupera ou uma saída/entrada voluntária ocorre.


Base de dados – colecção organizada e relacionada de dadosque pode ser acedida e manipulada através do sistema de gestão de base de dados.

Os clientes acedem aos dados submetendo transacções.

Transacções – conjunto de comandos e segue as propriedades ACID

MODELO DE SERVIÇO


Um serviço de replicação mantém uma base de dados replicada num sistema distribuído.

MODELO DE SERVIÇO

O estado inicial da base de dados é idêntico em todos os servidores.

Uma acção define a transição do estado corrente da base de dados para o estado seguinte. As acções tem uma componente de query e outra de update, podendo faltar uma delas.


Na presença de partições na rede, a camada de replicação identifica um único componente do grupo de servidores como o componente primário, sendo os restantes componentes não-primários.

ALGORITMO DE REPLICAÇÃO

Uma alteração na associação de um componente é reflectida na entrega de uma mensagem de alteração de view a cada servidor nesse componente.

Cada servidor constrói o seu próprio conhecimento sobre a ordem das acções do sistema.


Cada servidor marca as acções entregues a ele com uma das seguintes cores para indicar o nível de conhecimento associado:



Uma réplica pode estar num dos seguintes quatro estados:

ALGORITMO CONCEPTUAL

1- PRIM STATE

2- NONPRIM STATE

3- EXCHANGE STATE

4- CONSTRUCT STATE



1- PRIM STATE: o servidor pertence ao componente primário. Quando um cliente submete um pedido, é difundido utilizando o grupo de comunicação para todos os servidores no componente. Quando uma mensagem é entregue pelo sistema de comunicação do grupo para a camada de replicação, a acção é imediatamente marcada como verde e é imediatamente aplicada à base de dados.



2- NONPRIM STATE: o servidor pertence ao componente não primário. As acções do cliente são ordenadas pelo sistema de comunicação de grupo e quando uma mensagem é entregue pelo mesmo, é marcada a vermelho.



3- EXCHANGE STATE: Um servidor muda para este estado ao receber uma mensagem de alteração de view.



4- CONSTRUCT STATE: Neste estado todos os servidores no componente tem o mesmo conjunto de acções e podem instalar o componente primário.



A maior parte da execução do algoritmo é feita com os servidores a residirem no estado primário ou não-primário.

Há que assegurar que dois componentes diferentes não aplicam acções contraditórias na base de dados:• utiliza-se um mecanismo de quorum que elege um único componente primário;• apenas servidores no componente primário tem permissão para aplicar acções à base de dados;• com o dynamic linear voting o componente que contém a maioria do ultimo componente primário torna-se o novo componente primário.


DATABASE REPLICATION

Grupos de comunicações baseados na Sincronia Virtual não garantem a entrega de mensagens aquando de falhas na rede ou crash de servidores.

Neste algoritmo é importante saber se uma mensagem que foi entregue a um servidor antes de ocorrer uma alteração de uma view, também foi entregue aos restantes destinatários.

O algoritmo está incorrecto se um servidor decidir que o componente primário está instalado e outro decidir o contrário.


EXTENDED VIRTUAL SYNCHRONY

Para contornar a inabilidade de perceber quem recebeu as ultimas mensagens é utilizado o paradigma Extended Virtual Synchrony (EVS).

EVS divide a notificação de view-change em duas notificações:1. Messagem de alteração de configuração transicional;2. Messagem de alteração de configuração regular.


EXTENDED VIRTUAL SYNCHRONY

O EVS permite outra forma de entrega de mensagens, a safe delivery, que mantém a propriedade de ordem total.

Consegue-se assim três valores/situações possíveis:1. A safe message é entregue na configuração regular;2. A safe message é entregue na configuração transaccional;3. A safe message foi enviada antes de uma falha ocorrer, mas

não foi recebida pela camada de comunicação.



Os dois estados vulneráveis são o Prim e o Construct

• No estado Prim apenas acções que são entregues como seguras durante a configuração regular são aplicadas à base de dados.

• As acções entregues na configuração transicional não podem ser marcadas como verdes e aplicadas à base de dados antes da próxima configuração regular determinar o componente primário do sistema



O estado Prim é dividido em dois estados:

• Regprim• TransPrim

e criada uma nova cor associada a TransPrim: Amarelo – acção entregue em configuração transicional

de um componente primário.

A passagem de amarelo a verde é feita assim que o servidor encontra outro que marcou a acção a verde ou quando ele adere ao componente primário.



O diagrama do diapositivo n.º XX sofre a seguinte transformação:


ALGORITMO DE REPLICAÇÃONa presença de alterações na rede, o processo de instalação de um componente primário pode ser interrompido por uma alteração na configuração.A evolução da recuperação, com introdução do estado Amarelo, leva o servidor a evoluir nos ciclos:1b Action - Transição para uma configuração regular0 Reg Conf - O servidor está perante uma configuração regular entregue pelo layer de comunicações, mas não pode mudar para a transição;? Reg Conf – Recuperação em estado vulnerável até completo conhecimento do estado da configuração dos restantes servidores, porque o servidor não tem a certeza da entrega da mesma.


ENTRADAS E SAÍDAS DINÂMICAS

A entrada e saída dinâmica de servidores num grupo é tratada da seguinte forma:

Persistent_Join – gera uma acção de notificação de mudança de conectividade, isto é, uma view change, seguida de uma entrada, em estado vulnerável, do novo servidor no grupo até ele construir um completo conhecimento do estado do sistema (aplicação de logs, transferencia da base de dados, etc.);

Persistent_Leave – gera uma acção de notificação de mudança de conectividade, isto é, uma view change.


CORRECÇÃO DO ALGORITMOPode ser provada a correcção do algoritmo apresentado através

dos seguintes lemas, partindo de uma configuração igual e mantendo as propriedades FIFO e Ordem Total Global:

1. Se dois servidores efectuam a mesma acção N, o resultado é igual nos dois;

2. Se um servidor processa uma acção gerada por outro, processou todas as que ele gerou anteriormente;

3. Se um servidor solicita o processamento de uma acção aos membros do grupo e não há falha de comunicação ou processo, então os membros do grupo processarão a acção.

tanto estática como dinâmica.


SEMÂNTICA DAS APLICAÇÕES

A consistência absoluta dada pelo algoritmo pode ser ultrapassada através da adição ao modelo de acessos em consulta:

• Weak querys - consistentes mas obsoletos• Dirty querys - inconsistentes mas recentes

ou em modo de update.


ANÁLISE DE DESEMPENHO

Os testes de desempenho a que foi submetido o algoritmo, em comparação com os algoritmos de two-phase commit e COReL provou o seu maior rendimento.

Foi utilizado o mesmo sistema para os três casos:

14 replicas, correndo cada uma Linux sobre Pentium III-667, ligados numa LAN de 100Mbits/seg.

Documents

Abril 2003José Carlos Faria – José Carlos Correia Tolerância a faltas distribuídas Yair Amir & Ciprian Tutu FROM TOTAL ORDER TO DATABASE REPLICATION