FROM TOTAL ORDER TO DATABASE
REPLICATION
Yair Amir & Ciprian Tutu
Tolerância a faltas distribuídas
José Carlos Faria – José Carlos Correia
Abril 2003
INTRODUÇÃO
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.
José Carlos Faria – José Carlos Correia
Abril 2003
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)
Em WAN’s as falhas são ainda mais comuns.
José Carlos Faria – José Carlos Correia
Abril 2003
TRABALHO EXISTENTE
Os protocolos Two-phase commit mantém-se como a principal
técnica para fornecer consistência numa base de dados distribuída.
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.
José Carlos Faria – José Carlos Correia
Abril 2003
TRABALHO EXISTENTE
Keidar propõe a utilizaçao do Extended Virtual Synchrony
(EVS) num algoritmo que suporta partições e retomas na rede.
Kemme e Alonso provaram a correcção de alguns protocolos de
replicação.
José Carlos Faria – José Carlos Correia
Abril 2003
MODELO DE SISTEMA
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
José Carlos Faria – José Carlos Correia
Abril 2003
MODELO DE COMUNICAÇÃO E
FALHA
• Os nós comunicam por troca de mensagens.
• As mensagens podem perder-se.
• Servidores podem crashar.
• Podem ocorrer falhas na rede.
Não é assumido:
• corrupção de mensagens;
• faltas Bizantinas.
José Carlos Faria – José Carlos Correia
Abril 2003
MODELO DE COMUNICAÇÃO E
FALHA
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ó.
José Carlos Faria – José Carlos Correia
Abril 2003
MODELO DE COMUNICAÇÃO E
FALHA
É utilizado uma camada de serviço de comunicação com multidistribuiçã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.
José Carlos Faria – José Carlos Correia
Abril 2003
MODELO DE SERVIÇO
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
José Carlos Faria – José Carlos Correia
Abril 2003
MODELO DE SERVIÇO
Um serviço de replicação mantém uma base de dados replicada
num sistema distribuído.
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.
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO DE REPLICAÇÃO
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ãoprimários.
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.
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO DE REPLICAÇÃO
Cada servidor marca as acções entregues a ele com uma das
seguintes cores para indicar o nível de conhecimento associado:
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO CONCEPTUAL
Uma réplica pode estar num dos seguintes quatro estados:
1- PRIM STATE
2- NONPRIM STATE
3- EXCHANGE STATE
4- CONSTRUCT STATE
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO CONCEPTUAL
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.
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO CONCEPTUAL
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.
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO CONCEPTUAL
3- EXCHANGE STATE: Um servidor muda para este estado ao
receber uma mensagem de alteração de view.
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO CONCEPTUAL
4- CONSTRUCT STATE: Neste estado todos os servidores no
componente tem o mesmo conjunto de acções e podem instalar o
componente primário.
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO CONCEPTUAL
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.
José Carlos Faria – José Carlos Correia
Abril 2003
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.
José Carlos Faria – José Carlos Correia
Abril 2003
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.
José Carlos Faria – José Carlos Correia
Abril 2003
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.
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO DE REPLICAÇÃ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
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO DE REPLICAÇÃO
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.
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO DE REPLICAÇÃO
O diagrama do diapositivo n.º XX sofre a seguinte transformação:
José Carlos Faria – José Carlos Correia
Abril 2003
ALGORITMO DE REPLICAÇÃO
Na 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 regular
0 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.
José Carlos Faria – José Carlos Correia
Abril 2003
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.
José Carlos Faria – José Carlos Correia
Abril 2003
CORRECÇÃO DO ALGORITMO
Pode 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.
José Carlos Faria – José Carlos Correia
Abril 2003
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.
José Carlos Faria – José Carlos Correia
Abril 2003
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.
José Carlos Faria – José Carlos Correia
Abril 2003