Universidade Federal de Santa Catarina
Programa de Pós-Graduação em Ciência da Computação
Lazy Database Replication with Ordering
Guarantees
Khuzaima Daudjee and Kenneth Salem
School of Computer Science
University of Waterloo
ICDE'04
Apresentação por Rodrigo Gonçalves
Lazy Database Replication with Ordering
Guarantees
1.
2.
3.
4.
5.
Introdução
Strong Session Serializability
Arquitetura
Testes
Conclusão
Lazy Database Replication with Ordering
Guarantees
1.
2.
3.
4.
5.
Introdução
Strong Session Serializability
Arquitetura
Testes
Conclusão
Lazy Database Replication with Ordering
Guarantees
Introdução


Replicação

Performance

Disponibilidade
Formas de replicação


Eager replication
 Uma transação
Lazy replication
 Duas ou mais transações
Lazy Database Replication with Ordering
Guarantees
Introdução

Lazy Replication

Ordem das transações


Dados inválidos
Serialização


Não resolve completamente o problema
T2 pode não ver os efeitos de T1, mesmo
sendo executada após T1
Lazy Database Replication with Ordering
Guarantees
Introdução

Serialização forte


Garante ordem
Problemática para Lazy Replication


Atualização completa antes do uso
Proposta

Strong Session Serializability

Serialização forte parcial
Lazy Database Replication with Ordering
Guarantees
1.
2.
3.
4.
5.
Introdução
Strong Session Serializability
Arquitetura
Testes
Conclusão
Lazy Database Replication with Ordering
Guarantees
Strong Session Serializability

Serialização forte


Garante ordem a um alto custo
Reduz disponibilidade das réplicas


Aguardam transações anteriores
Cria dependências entre transações

Muitas vezes desnecessárias
Lazy Database Replication with Ordering
Guarantees
Strong Session Serializability

Strong session serializability

Dependências apenas onde for necessário


Sessão



Diminui dependências entre transações
Conjunto de transações
Existe dependência
Garante-se serialização forte na Sessão
Lazy Database Replication with Ordering
Guarantees
1.
2.
3.
4.
5.
Introdução
Strong Session Serializability
Arquitetura
Testes
Conclusão
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Sistema básico

Arquitetura “Lazy Master”


Um nodo primário
Vários nodos secundários



Independentes
Transações de leitura executadas em
nodos secundários
Transações de escrita somente no nodo
primário
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Sistema básico

Arquitetura “Lazy Master”

Escalonável



Adição de nodos secundários
Consultas
Nodo primário




Serializa transações
Número seqüencial
Replicação seqüencial
“Lazy propagation”
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Sistema básico
Lazy Database Replication with Ordering
Guarantees
Arquitetura

O sistema básico



Garante serialização global
Não garante “strong session
serializability”
Um gerenciador de sessões

Garante “strong session serializability”
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Sistema básico

Nodos secundários



FIFO
Refresh Transactions
Seqüencial



Gerado na aplicaçaõ de uma “Refresh
Transaction”
Necessário pelo Gerenciador de Sessão
seq(DB)
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Gerenciador de Sessão




Garante Strong Session Serializability
Um por nodo secundário
Transações de um cliente
Supõe-se


Transações executadas em um único nodo
Transações seqüenciais
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Gerenciador de Sessão

Seqüencial por sessão - seq(s)



Último estado do BD
Algorítimo BLOCK
Algorítimo FORWARD
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Gerenciador de Sessão

Algorítimo BLOCK


Transações (T) de leitura executam somente
quando o estado do nodo secundário é
compatível com a transação
seq(DB) >= seq(s)
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Gerenciador de Sessão

Algorítimo BLOCK

Para transações de escrita:
Inicie T no nodo primário
Execute as operações de T no nodo primário
Complete ou aborte T no nodo primário
Obtenha o seq(T) do nodo primário
Se T completada então
seq(s) ← seq(T)
FimSe
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Gerenciador de Sessão

Algorítimo BLOCK

Para transações de leitura:
AGUARDE ATÉ seq(DB) ≥ seq(s) no nodo secundário
Inicie T no nodo secundário
Execute as leituras de T no nodo secundário
Aborte ou complete T no nodo secundário
Se T completada então
seq(s) ← seq(DB)
FimSe
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Gerenciador de Sessão

Algorítimo FORWARD


Gerencia atualizações como BLOCK
Transações de leitura


Redirecionadas para o nodo primário
Evita espera pela atualização do nodo secundário
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Gerenciador de Sessão

Algorítimo FORWARD
Se seq(DB) ≥ seq(s) no nodo secundário então
Inicie T no nodo secundário
Execute as operações de T no nodo secundário
Complete ou aborte T no nodo secundário
Se T completada então
seq(s) ← seq(DB)
FimSe
Senão
Inicie T no nodo primário
Execute as operações de T no nodo primário
Complete ou aborte T no nodo primário
Obtenha seq(T) do nodo primário
Se T completada então
seq(s) ← seq(T)
FimSe
FimSe
Lazy Database Replication with Ordering
Guarantees
Arquitetura

Gerenciador de Sessão

Algorítimo BLOCK



Distribui carga das operações de leitura
Pode retardar uma transação de leitura
Algorítimo FORWARD


Pode sobrecarregar o nodo primário
Mais eficiente para operações de leitura
Lazy Database Replication with Ordering
Guarantees
1.
2.
3.
4.
5.
Introdução
Strong Session Serializability
Arquitetura
Testes
Conclusão
Lazy Database Replication with Ordering
Guarantees
Testes

Modelo de simulação

Comparar métodos Forward e Block

Pacote de simulação CSIM

Simula um sistema distribuído completo
Lazy Database Replication with Ordering
Guarantees
Testes

Modelo de simulação
Parâmetro
Descrição
num_clients
Número de clientes
num_sec
Número de nodos secundários
think_time
Tempo médio de processamento do cliente
session_time
Duração média de uma sessão
update_tran_prob Probabilidade de uma transação de escrita
conflict_prob
Probabilidade de conflito na transação
tran_size
Número médio de operações por transação
op_service_time Tempo de serviço por operação
update_op_prob Probabilidade de operação de atualização
propagation_dealy Tempo de propagação
Padrão
Variado
5
7s
15 min.
20,00%
20,00%
10
0.02s
30,00%
10s
Lazy Database Replication with Ordering
Guarantees
Testes

Análise de performance

Objetivos



Custo em termos de transação
Comparar o modelo geral de serialização
com o strong session serializability
Comparar os algorítimos Forward e Block
Lazy Database Replication with Ordering
Guarantees
Testes

Análise de performance

Dois algorítimos adicionais na comparação

ALG-1SR



Serialização global simples
Não bloqueia transações
ALG-STRONG-SITE-1SR



Algorítimo Block com apenas uma sessão por
nodo secundário
Mais restritivo que strong session serializability
porém menos que strong serializability
Equivalente ao strong serializability em custo
Lazy Database Replication with Ordering
Guarantees
Testes

Metodologia



Simulações com 35 minutos de duração
5 minutos para warm up
Resultados tomados da média de 5
simulações
Lazy Database Replication with Ordering
Guarantees
Testes

Testes com a configuração padrão
Lazy Database Replication with Ordering
Guarantees
Testes

Testes com a configuração padrão
Lazy Database Replication with Ordering
Guarantees
Testes

Testes com a configuração padrão
Lazy Database Replication with Ordering
Guarantees
Testes

Testes com a configuração padrão

Leituras



Tempo de propagação


Forward mais eficiente em baixa carga
Block mais constante
Torna métodos equivalentes
ALG-Strong-Site-1SR pior que Block

Demonstra necessidade de evitar
dependências desnecessárias
Lazy Database Replication with Ordering
Guarantees
Testes

Escalabilidade

Número de nodos secundários e clientes
variando

Mantendo-se em média 20 clientes por nodo
Lazy Database Replication with Ordering
Guarantees
Testes

Escalabilidade
Lazy Database Replication with Ordering
Guarantees
Testes

Escalabilidade
Lazy Database Replication with Ordering
Guarantees
Testes

Escalabilidade
Lazy Database Replication with Ordering
Guarantees
Testes

Escalabilidade



Forward tem baixo desempenho
Block demonstrou-se equivalente ao Alg1SR em performance
Reduzindo o percentual de transações de
escrita, a escalabilidade melhorou
consideravelmente
Lazy Database Replication with Ordering
Guarantees
1.
2.
3.
4.
5.
Introdução
Strong Session Serializability
Arquitetura
Testes
Conclusão
Lazy Database Replication with Ordering
Guarantees
Conclusão





Adaptação de um sistema 1SR
Garante serialização em sessões
Dependências
Tempos de propagação
Método escalável e aplicável a
sistemas distribuídos
Download

Lazy Database Replication with Ordering Guarantees Testes