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