Cap. 07 – Consistência e Replicação - Faculdade de …faina/BCC_Crs/GSI028-2014-1S/DL/DS-Ch07.pdf · 7.1.2 Replicação como Técnica de Escalabilidade 7.2 – Modelos de Consistência

Luís F. Faina - 2014 Pg. 1/116

Cap. 07 – Consistência e Replicação

7.1 – Introdução7.1.1 Razões para a Replicação

7.1.2 Replicação como Técnica de Escalabilidade

7.2 – Modelos de Consistência “Data-Centric”7.2.1 Consistência Contínua

7.2.2 Ordenação Consistente de Operações

7.3 – Modelos de Consistência “Client-Centric”7.3.1 Consistência Eventual

7.3.2 Leituras Monotônicas

7.3.3 Escritas Monotônicas


… Cap. 07 – Consistência e Replicação

7.3 – Modelos de Consistência “Client-Centric”...

7.3.4 Leia suas Escritas

7.3.5 Escritas seguem Leituras

7.4 – Gerenciamento de Replicação

7.4.1 Possicionamento do Servidor de Réplica

7.4.2 Localização e Replicação de Conteúdo

7.4.3 Distribuição de Conteúdo


… Cap. 07 – Consistência e Replicação

7.5 – Protocolos de Consistência7.5.1 Consistência Contínua

7.5.2 Protocolo “Primary Based”

7.5.3 Protocolo “Replicated-Write”

7.5.4 Protocolo “Cache-Coherence”

7.5.5 Implementação de Consistência “Client-Centric”


Referências Bibliográficas

● Andrew S. Tanenbaum; Maarten van Steen - Distributed Systems: Principles and Paradigms, Prentice-Hall, 2007, ISBN-10: 0132392275, ISBN-13: 9780132392273

… Lectures dos autores Andrew S. Tanenbaum e Maarteen van Steen (“www.cs.vu.nl” e “www.distributed-systems.net/”)

● George Coulouris; Jean Dollimore; Tim Kindberg – Sistemas Distribuídos: Conceitos e Projeto, Bookman, 4th Edition, 2007, ISBN 9788560031498

● Notas de Aula do Prof. Ricardo Anido do Instituto de Computação (IC) da UNICAMP - www.ic.unicamp.br/~ranido/

http://www.cs.vu.nl/


7 Consistência e Replicação


● Replicação de Dados - consiste em manter múltiplas cópias de dados, chamadas de réplicas, em diferentes computadores.

● “problema” - manter a consistência entre as cópias, ou seja, quando um cópia é atualizada é necessário garantir que todas as outras cópias sejam também atualizadas.

● 1a Abordagem - Leslie Lamport (1978) - “Times, Clocks, and the Ordering of Events in a Distributed System”

● … tema de interesse em sistemas distribuídos e em banco de dados, mas sob diferentes aspectos.



… 7 Consistência e Replicação

● “contexto” - modelos de consistência para dados compartilhados são difíceis de serem implementados eficientemente em sistemas distribuídos de larga escala;

● … duas questões constituem os principais aspectos de projeto de implementação dos modelos de consistência: gerenciamento de réplicas e como réplicas são mantidas.


7 Consistência e Replicação – 7.1 Introdução

7.1.1 Razões para a Replicação

● “reliability” - “dependability, or reliability, describes the ability of a system or component to function under stated conditions for a specified period of time” [Wikipedia 2014]

● “availability” - “the ratio of (a) the total time a functional unit is capable of being used during a given interval to (b) the length of the interval” [Wikipedia 2014]

● São várias as razões para replicação, das quais se destacam:

● “confiabilidade“ - réplicas garantem que não haverá um único ponto de falha no sistema.

● “disponibilidade“ - réplicas propiciam o aumento da disponibilidade do sistema como consequência da confiabilidade.



… 7.1.1 Razões para a Replicação

● … … razões para replicação, das quais se destacam:

● “transparência de falha“ - em caso de falha, o usuário pode ser movido para outra réplica sem notar que a falha ocorreu.

● “desempenho“ - balanceamento de carga, uso de “cache”, escalabilidade geográfica, aumento do sistema.

● “consistência de dados” - processo para manter uma informação uniforme conforme ela se move em uma rede ou entre vários processos de um computador.

● Obs.: … fato de existir múltiplas cópias de dados, objeto de leitura e escrita de vários processos, gera o problema de inconsistência.



7.1.2 Replicação como Técnica de Escalabilidade

● Replicação e “Caching” são largamente utilizadas como técnicas de escalabilidade para efeito de desempenho;

● … questões de escalabilidade normalmente aparecem na forma de problemas de desempenho, assim:

● … disponibilizar cópias de dados próximas aos processos que as utilizam pode melhorar o desempenho pela redução do tempo de acesso e, assim, resolver problemas de escalabilidade.

● “dilema” - modificação desses dados em uma réplica exige que as outras cópias sejam atualizadas para manter a consistência.

● “dilema” - propagar a modificação para cada réplica é um processo caro e pode causar perda de desempenho no sistema.

Luís F. Faina - 2014 Pg. 10/116


… 7.1.2 Replicação como Técnica de Escalabilidade

● … em muitos casos, a única solução é diminuir as restrições de consistência, ou seja, não exigir que a atualização seja executada como uma operação atômica => ganho de desempenho.

● … nesta abordagem, evita-se a sincronização global (instantânea) dos dados => ganho de desempenho.

Luís F. Faina - 2014 Pg. 11/116

7 Consistência e Replicação – 7.2 Modelos de Consistência “Data-Centric”

7.2 Modelos de Consistência “Data-Centric”

● “contexto” - modelos de consistência são analisados tradicional- mente por meio de operações de leitura/escrita sobre dados compartilhados (memória ou banco de dados compartilhado).

● “data store” - pode se encontrar fisicamente distribuído em diferentes máquinas e com as sequintes características:

● cada processo pode acessar dados do repositório através de um cópia local de todo o conteúdo do repositório;

● operações de escrita são propagadas para todas as cópias;

● operação de dados é classificada como escrita quando altera o dado, diferentemente da operação de leitura.

Luís F. Faina - 2014 Pg. 12/116


… 7.2 Modelos de Consistência “Data-Centric”

● Fig. 7.1 – Organização geral de um “Data Store”, fisicamente distribuído e replicado sobre múltiplos processos.

Luís F. Faina - 2014 Pg. 13/116


… 7.2 Modelos de Consistência “Data-Centric”

● “consistency model” - é essencialmente o contraste entre os processos e o repositório de dados, no sentido das regras acordadas entre os mesmos para manter a consistência.

● … processos que realizam a leitura de um dado esperam que o valor retornado seja o valor da última escrita nesse dado;

● … na ausência de um relógio global, é difícil definir qual operação de escrita é a última no contexto de sistemas distribuídos;

● … assim, modelos de consistência restringem os valores que uma operação de leitura pode retornar sobre um item de dados.

Luís F. Faina - 2014 Pg. 14/116


7.2.1 Consistência Contínua

● “Yu e Vehdat” (2002) propõem 03 classes de inconsistências:

● desvio de valores numéricos entre réplicas ;

● desvio de idade entre réplicas;

● desvio em relação à ordenação de operações de escrita.

● “desvio de valor numérico” - … ocorre em aplicações onde os dados possuem semântica numérica.

● “solução óbvia” - definir um desvio numérico absoluto ou relativo entre os valores assumidos pelas cópias, assim:

● ... enquanto os valores estiverem dentro do limite estabelecido de desvio, serão considerados como consistentes.

Luís F. Faina - 2014 Pg. 15/116


… 7.2.1 Consistência Contínua

● “desvio de valor numérico” - também pode ser entendido como o nro. de atualizações aplicadas a uma réplica, mas ainda não disponíveis para as demais réplicas.

● e.g., réplicas de registros de preços de ações

● desvio numérico absoluto - preço de uma ação entre as réplicas não deve variar mais que $ 0,02;

● desvio númerico relativo - diferença entre o valor de duas cópias não deve ser maior 5%.

Luís F. Faina - 2014 Pg. 16/116



● “desvio de idade” - relacionado com a diferença de tempo da data da versão atual para a data da última atualização.

● e.g., … réplica de uma previsão de tempo será considerada consistente por uma hora, independente do número de atualizações que ocorram nesse período.

Luís F. Faina - 2014 Pg. 17/116



● “desvio de ordenação” - ordem das operações de atualização em cada réplica podem ser diferentes dentro de um certo limite.

● … correções são feitas alterando a ordem dessas atualizações antes de persistí-las em definitivo.

● Obs.: … dependência de um acordo global de atualização, pode reverter atualizações já completadas para na sequência aplicá-las em uma ordem diferente de modo que se tornem permanentes.

Luís F. Faina - 2014 Pg. 18/116



● “Yu e Vehdat” (2002) introduziram o conceito de unidade de consistência ou “Consistency Unit” ou “conit” - especifica a unidade sobre a qual a consistência deve ser medida;

● … ou seja, um “conit” pode ser definido como um registro representando 01 estoque único ou relatório individual de tempo.

● e.g., considere 02 réplicas “A” e “B” com um “conit” contendo os itens de dados “x” e “y”;

● … cada réplica contém um relógio vetorial bidimensional VCi (Cap. 06), com a notação “t, i” expressando que uma operação foi realizada pela réplica “i” no tempo lógico “t” (tempo local).

Luís F. Faina - 2014 Pg. 19/116



● Fig. 7.2 – Exemplo do rastreamento do desvio de consistência extraído do artigo “Yu e Vehdat” (2002).

Luís F. Faina - 2014 Pg. 20/116



● Note que há a uma negociação entre “conits” com granularidade fina e “conits” com granularidade grossa;

● e.g. considere um “conit” como um banco de dados completo, assim a atualização de dados está condicionada a todo o conjunto de dados naquele unidade de consistência;

● … como consequência, este cenário pode produzir réplicas rápidas não consistentes – estado inconsistente.

● e.g., considere 02 réplicas que se diferem não mais do que por uma única atualização – contexto de granularidade grossa, ou seja, um “conit” consiste de 02 itens de dados (Fig. 7.3)

Luís F. Faina - 2014 Pg. 21/116



● Fig. 7.3 – Escolha da granularidade correta de um “conit”. a. 02 atualizações disparam uma propagação de atualização.

Luís F. Faina - 2014 Pg. 22/116



● Fig. 7.3 – Escolha da granularidade correta de um “conit”. a. 02 atualizações disparam uma propagação de atualização. b. não há a necessidade de propagação de atualização.

Luís F. Faina - 2014 Pg. 23/116



● “conits” grandes - levam a réplica ao estado de inconsistência mais rápido quando comparada com “conits” pequenos.

● “conits” pequenos - aumentam o número de “conits” que precisam ser gerenciadas e, por consequência, afetam o desempenho.

● Obs.: … para implementação deste mecanismos, faz-se neces- sário criar protocolos de consistência, por outro lado, identificar os seus requisitos não é uma tarefa nada fácil.

Luís F. Faina - 2014 Pg. 24/116


7.2.2 Ordenação Consistente de Operações

● Nesta seção, discutiremos operações ordenadas de forma consistente sobre dados compartilhados e replicados.

● … neste contexto, quando tentativas de atualização em réplicas necessitam ser concluídas, as réplicas terão que acordar quanto a ordenação global destas atualizações.

● … é necessário que as réplicas concordem na ordenação consistente das atualizações para garantir a consistência.

Luís F. Faina - 2014 Pg. 25/116


… 7.2.2 Ordenação Consistente de Operações

● Para melhor entendimento dos modelos a serem discutidos, processos realizam operações de escrita “Wi(x)a” e leitura “Ri(x)a” sobre dados ao longo do tempo, para tanto, seja a notação:

● Wi(x)a – Processo Pi escreve/atualiza o dado “x” com o valor “a”;

● Ri(x)b – Processo Pi lê o dado “x” retornando o valor “b”

● eixo “x” representa o tempo que cresce da esquerda para a direita.

● Fig. 7.4 – Comportamento de 02 processos operando sobre o mesmo item de dado “x” com operações de escrita e leitura.

Luís F. Faina - 2014 Pg. 26/116



● Fig. 7.4 – Comportamento de 02 processos operando sobre o mesmo item de dado “x” com operações de escrita e leitura.

● “Wi(x)a” é inicialmente realizada sobre uma cópia local do reposi- tório de dados para P1 e, subsequentemente, é propagada para as outras cópias do repositório de dados;

● P2 lê mais tarde o valor “NIL” e algum tempo depois o valor “a” da sua cópia local do repositório de dados;

● … leva-se um tempo para propagar a atualização de “x” para P2, o que é perfeitamente aceitável.

Luís F. Faina - 2014 Pg. 27/116



● “consistência sequencial” - importante no modelo de consistên- cia centrado em dados, foi definida por Lamport em 1979 no contexto de memória compartilhada de sist. multiprocessados.

● “definição” - resultado de qualquer execução é o mesmo que seria se as operações de leitura e escrita fossem executadas em alguma ordem sequencial por todos os processos no repositório;

● … onde, as operações de cada processo aparecem nesta sequência em uma ordem especificada pelo seu programa.

● Obs.: … definição sugere que quando processos executam concorrentemente em diferentes máquinas, um entrelaçamento válido de operações de leitura e escrita é aceitável, desde que todos os processos enxerguem o mesmo entrelaçamento.

Luís F. Faina - 2014 Pg. 28/116



● … neste contexto, um processo enxerga “writes” de todos os processos, mas somente seus próprios “reads”.

● Fig. 7.5 – a. consistência sequencial do repositório de dados; b. repositório de dados sem consistência sequencial.

Luís F. Faina - 2014 Pg. 29/116



● a. mostra um depósito de dados sequencialmente consistente, apesar de P3 e P4 terem lido um valor antigo;

● b. mostra um depósito de dados não consistente porque P3 e P4 não enxergam a mesma intercalação de operações de escrita.

● Fig. 7.5 – a. consistência sequencial do repositório de dados; b. repositório de dados sem consistência sequencial.

Luís F. Faina - 2014 Pg. 30/116



● e.g., considere 03 processos executando concorrentemente onde os itens de dados são formados por 03 variáveis “x”, “y” e “z” de um repositório de dados compartilhado.

● variáveis são inicializadas com o valor “0”;

● operação de atribuição corresponde a operação de escrita;

● declaração de impressão corresponde a 02 operações de leitura.

● Fig. 7.6 – 03 processos executando concorrentemente.

Luís F. Faina - 2014 Pg. 31/116



● “análise” - 06 declarações, 720 (6*5*4*3*2*1 = 6!) sequências de execução são possíveis, ainda que algumas sejam inválidas;

● … são 120 (5!) sequências que iniciam com “x ← 1”, ½ das quais tem “print(x,z)” antes de “y ← 1” o que viola a sequência no prog.;

● … ½ das sequências tem “print(x,y)” antes de “z ← 1”, o que também viola a ordem do programa;

● … análise semelhante cabe para sequências iniciadas por “y ← 1” e sequências iniciadas por “z ← 1”;

● … deste total, 90 sequências são válidas, 30 iniciando com “x ← 1”, 30 iniciando com “y ← 1” e 30 com “z ← 1”.

Luís F. Faina - 2014 Pg. 32/116



● Fig. 7.7 – 04 sequências válidas de execução para os processos P1, P2, e P3 como mostrados na Fig. 7.6.

● eixo imaginário na vertical representa a linha do tempo.

Luís F. Faina - 2014 Pg. 33/116



● “signature” - concatenação das saídas de P1, P2, e P3, nesta ordem, formando um “string” de 06 bits que caracteriza uma sequência particular de comandos / declarações.

● … nem todas as 64 combinações de bits são válidas:

● p.ex., 000000 não é permitida pois implica que as declarações “print(y,z)”, “print(x,z)” e “print(x,y)” são executadas antes de “x ← 1”, “y ← 1”, “z ← 1”

● … viola a ordem de execução definida pelos programas.

● p.ex., 001001 também não é permitida, pois se assumirmos que P1 inicia a execução, então os 02 primeiros bits representam “print(y,z)”;

● … os próximos 02 bits “10” significam que P2 deve executar depois de P1 e antes de P3 e os últimos 02 bits “01” significam que P3 deve executar antes de P1 executar, mas já vimos que P1 deve executar primeiro.

Luís F. Faina - 2014 Pg. 34/116



● “consistência causal” - proposto por “Hutto e Ahamad” (1990) representa uma consistência sequencial fraca para garantir concorrência em memória compartilhada distribuída.

● … faz distinção entre eventos potencialmente relacionados por causalidade e os que não são relacionados por causalidade.

● e.g., se o evento “b” é causado ou influenciado por um evento anterior “a”, todos devem ver primeiro “a” e depois “b”.

● Obs.: operações não relacionadas por causalidade são comumente denominadas concorrentes.

Luís F. Faina - 2014 Pg. 35/116



● “consistência por causalidade” - “data store” é considerado consistente por causalidade se satisfaz a seguinte condição:

● … escritas que são potencialmente relacionadas por causalidade devem ser vistas por todos os processos na mesma ordem;

● … escritas concorrentes,ou seja, sem relação de causalidade, podem ser vistas em ordem diferente em máquinas diferentes.

● “implementação” - consistência causal exige que as dependências entre operações seja monitorada, o que pode ser feito com o uso de marcas de tempo vetoriais.

● e.g., como exemplo de consistência causal, considere 04 processos P1, P2, P3 e P4 e uma sequência de eventos.

Luís F. Faina - 2014 Pg. 36/116



● e.g., como exemplo de consistência causal, considere 04 processos P1, P2, P3 e P4 e uma sequência de eventos.

● “W2(x)b” e “W1(x)c” são concorrentes, assim não é exigido que todos os processos enxerguem estas operações na ordem.

● Fig. 7.8 – Sequência de eventos com consistência de causalidade, mas não com consistência sequencial.

Luís F. Faina - 2014 Pg. 37/116



● a. “W2(x)b” potencialmente depende “W1(x)a” porque “b” pode ser um resultado envolvendo o resultado do cálculo de “a” - “R2(x)a”;

● … 02 operações de “write” estão relacionadas pela relação de causalidade, assim todos os processos devem exergar todas estas operações na mesma ordem.

● Fig. 7.9 – a. violação da consistência de causalidade; b. sequên- cia correta de eventos com consistência de causalidade.

Luís F. Faina - 2014 Pg. 38/116



● b. “W2(x)b” potencialmente concorre com “W1(x)a”, pois a operação “R2(x)a” foi removida de P2;

● … consistência de causalidade não requer que escritas concorrentes sejam globalmente ordenadas.

● Fig. 7.9 – a. violação da consistência de causalidade; b. sequên- cia correta de eventos com consistência de causalidade.

Luís F. Faina - 2014 Pg. 39/116



● “consistência causal” e “sequencial” - definidas no nível (granularidade) de operações de leitura e escrita por razões históricas;

● … em muitos casos este nível de granularidade fino não atende a granularide suportada pela aplicações;

● Normalmente, compartilhamento de dados é mantido através de mecanismos de sincronização para sincronização, enquanto as transações mantém o controle de concorrência.

● … ENTER_CS - significa que o dado no armazenamento local está atualizado, ou seja, leituras e escritas podem ser realizadas;

● … ao terminar as operações o processo invoca LEAVE_CS, pro- tegendo as operações do acesso concorrente.

● Obs.: operações são atomicamene executadas como unidades.

Luís F. Faina - 2014 Pg. 40/116



● Neste ponto, é necessário dar semântica às operações ENTER_CS e LEAVE_CS através de variáveis de sincronização;

● … dentre as possíveis maneiras, em uma abordagem geral cada variável tem um dado associado que pode ser equivalente a um conjunto de dados compartilhados;

● … processo deve ter a posse das variáveis de sincronização para executar ENTER_CS, assim como deve liberar as variáveis de sincronização quando for executar LEAVE_CS.

● Obs.: Processos podem simultaneamente compartilhar uma variável de sincronização em modo não exclusivo, ou seja, podem ler mas não escrever no dado associado.

Luís F. Faina - 2014 Pg. 41/116



● 03 critérios devem ser satisfeitos:

01 - aquisição de acesso para uma variável de sincronização não é concedida a um processo até que todas as atualizações referentes aos dados compartilhados seja realizada;

● … ou seja, todas as mudanças para um dado compartilhado devem se tornar visíveis, ou seja, devem ser atualizados.

02 - nenhum outro processo pode manter a variável de sincroni- zação, nem mesmo no modo não exclusivo, antes que o acesso no modo exclusivo para uma variável seja concedido;

● … ou seja, antes de atualizar um dado compartilhado, um processo precisa entrar na região crítica em modo exclusivo.

Luís F. Faina - 2014 Pg. 42/116



● 03 critérios devem ser satisfeitos:

03 - após a concessão do acesso no modo exclusivo para uma variável de sincronização, o acesso ao modo não exclusivo por um outro processo para a variável de sincronização não pode ser realizado até que ele tenha consultado o dono da variável;

● … ou seja, se um processo deseja entrar na região crítica no modo não exclusivo, é necessário primeiro verificar como o proprietário da variável de sincronizaçãoa a mais recente cópia do dado compartilhado.

Luís F. Faina - 2014 Pg. 43/116



● e.g., considere o exemplo de “consistência de entrada”, ou seja, em vez de operar o dado compartilhado por completo, “locks” são associados a cada item do dado compartilhado.

Acq(Lx) – Acquire for “x” Rel(Ly) – Release for “y”

● Fig. 7.10 – Sequência válida de eventos para a consistência de entrada – itens “x” e “y” compondo o dado compartilhado.

Luís F. Faina - 2014 Pg. 44/116



● “problema da consistência de entrada” - associar adequadamente o dado com variáveis sincronização;

● “abordagem simples” - explicitar ao “middleware” quais dados serão acessados, semelhante quando é informado quais tabelas serão afetadas em uma transação.

● “consistência” versus “coerência” - importante entender a diferença entre 02 conceitos que estão relacionados.

● e.g., considere o cenário de um conjunto de processos que executam operações de leitura/escrita em um conj. de dados.

Luís F. Faina - 2014 Pg. 45/116



● e.g., considere o cenário de um conjunto de processos que executam operações de leitura/escrita em um conj. de dados.

● “Modelo de Consistência” - descreve o que se espera de um conjunto de itens de dados quando vários processos operam de forma concorrente.

● “Modelo de Coerência” - descreve o que se espera de um único item de dado replicado em vários lugares quando cada cópia é submetida a um conj. de regras do modelo de coerência.

● e.g., … modelo de consistência sequencial aplicado a um único item de dado, na prática, ocorrendo operações de escritas concorrentes, todos os processos eventualmente verão a mesma ordem de “updates”.

Luís F. Faina - 2014 Pg. 46/116

7 Consistência e Replicação – 7.3 Modelos de Consistência “Client-Centric”

7.3 Modelos de Consistência “Client-Centric”

● Os modelos de consistência descritos anteriormente tem por objetivo prover uma consistência global do repositório de dados;

● … ou seja, a suposição é a de processos concorrentes podem simultaneamente atualizar o repositório e, assim, é necessário consistência face a concorrência entre os mesmos.

● e.g., em modelos baseados em objetos, o repositório garante que uma cópia atual do objeto será fornecida ao processo chamador;

● … durante a chamada, nenhum outro processo pode interferir, ou seja, acesso exclusivo é concedido ao processo chamador.

Luís F. Faina - 2014 Pg. 47/116


… 7.3 Modelos de Consistência “Client-Centric”

● … ou seja, manipular operações concorrentes em dados compartilhados enquanto se mantém a consistência sequencial é fundamental em sistemas distribuídos.

● Por razões de desempenho, consistência sequencial pode ser garantida somente com o uso de mecanismos de sincronização tais como transações e “locks”.

● Nesta seção discutiremos uma classe especial de “data stores” distribuídos caracterizados pela ausência de atualizações simultâ- neas ou quando acontecem podem ser resolvidas facilmente.

● … tais modelos de consistência são denominados “eventualmente consistentes” e de modo geral escondem as inconsistências.

Luís F. Faina - 2014 Pg. 48/116


7.3.1 Consistência Eventual

● Processos podem operar de modo concorrente de diferentes maneiras, bem como pode variar o nível de consistência que deve ser garantido aos dados objetos do compartilhamento.

● e.g., … em muitos sistemas de banco de dados os processos executam muito mais operações de leitura do que de atualização;

● … neste contexto, como atualizações rápidas devem estar disponíveis para processos de leitura?

● e.g., … no DNS só a autoridade nomeada responderá pelo nome;

● … consequentemente, conflitos de atualização nunca existirão, porém, ainda assim existem conflitos de “read-write”.

● solução - processo leitor espera algum tempo após completar a atualização para então executar a operação de leitura.

Luís F. Faina - 2014 Pg. 49/116


… 7.3.1 Consistência Eventual

● e.g., … atualização de páginas na Web se dá por uma única autoridade, tal como o “webmaster” ou proprietário das páginas;

● … ou seja, não há conflitos “write-write”, mas por outro lado, para melhorar o desempenho, “browsers” e “proxies” são configurados para buscar e manter páginas na “cache”;

● … o que pode ocasionar o retorno de páginas não atualizadas, ou seja, a versão da página é uma versão mais antiga do que aquela mantida pelo servidor Web atual.

● Obs.: … exemplos descritos podem ser vistos como casos de repositórios de dados distribuídos e replicados que toleram relativamente um alto grau de inconsistência.

Luís F. Faina - 2014 Pg. 50/116



● Neles, se nenhuma atualização acontecer por um tempo longo, todas as réplicas estarão gradualmente inconsistentes, ou seja, “eventualmente consistente” - o que exige que atualizações sejam propagadas a todas as réplicas.

● … conflitos de atualizações são geralmente mais fáceis e baratos de serem resolvidas, desde que um pequeno grupo de processos executem as operações de escrita.

● Normalmente consistência eventual funciona bem na medida que clientes acessam as mesmas réplicas;

● … entretanto, surgem problemas quando diferentes réplicas são objeto de acesso em um curto período de tempo (Fig. 7.11).

Luís F. Faina - 2014 Pg. 51/116



● Fig. 7.11 – Princípio de um Usuário Móvel acessando diferentes réplicas de um Repositório de Dados Distribuído.

Luís F. Faina - 2014 Pg. 52/116



● “Terry” et al. (1994) (1998) constituem a origem dos trabalhos de modelos de consistência centrados no cliente com o intuito de amenizar os efeitos discutidos no exemplo anterior;

● “client-centric consistency” - provê garantias para um único cliente em relação aos acessos consistentes ao “data store”;

● … no entanto, não dá garantias de consistências para acessos concorrentes de 02 ou mais clientes.

● Terry et al. propõem 4 diferentes modelos de consistência:

** Leituras Monotônicas ** Escritas Monotônicas

** Leia suas Escritas ** Escritas seguem Leituras

Luís F. Faina - 2014 Pg. 53/116



● Terry et al. (1994) (1998) propuseram 04 diferentes modelos de consistência para um repositório de dados fisicamente distribuído em diferentes máquinas e com as seguintes características:

● … quando um processo acessa do “data store”, ele o faz na cópia local ou na cópia mais próxima, embora em princípio, qualquer cópia estaria apta para ser operada/manuseada;

● … operações de leitura e escrita são realizadas na cópia local e atualizações são eventualmente propagadas para todas as cópias

● … cada item de dado tem proprietário associado, ou seja, um processo que tem permissão para modificar aquele item, assim, evita-se conflitos do tipo “escrita-escrita”.

Luís F. Faina - 2014 Pg. 54/116



● Modelos de Consistência “Client-Centric” são descritos utilizando-se a notação a seguir:

● Seja xi[t1] a versão do dado “x” na cópia local “Li” no tempo “t1”;

● … versão xi[t1] é o resultado de uma série de operações de escrita na cópia local “Li” que ocorreram desde a inicialização – conjunto que é denotado por “WS( xi[t1] )”;

● … se as operações em WS(xi[t1]) também forem executadas em uma cópia local “Lj” no tempo “t2”, escrevemos “WS( xi[t1]; xj[t2] )”;

● … se a ordenação de operações ou a temporização estiver clara no contexto, o índice de tempo será omitido.

Luís F. Faina - 2014 Pg. 55/116


7.3.2 Leituras Monotônicas

● “monotonic-read consistency” - se um processo ler o valor de um item de dado “x”, novas operações de leitura de x executadas por este processo retornaram o mesmo valor ou um mais recente.

● … ou seja, se um processo viu o valor de “x” no tempo “t1”, este processo não verá uma versão anterior de “x” em “t2” - “t2 > t1”.

● e.g., considere 02 cópias locais diferentes - “L1” e “L2” do mesmo “data store” e o eixo “x” representando o tempo - “tleft < tright”.

● … em ambos os casos estamos interessados nas operações executadas por um único processo “P”, aqui representadas em negrito enquanto a linha pontilhada representa a ordem em que as operações são executadas - “R(x1)” antes de “R(x2)”.

Luís F. Faina - 2014 Pg. 56/116


… 7.3.2 Leituras Monotônicas

● “P” inicialmente executa uma leitura em “x” na cópia local “L1”, retornando o valor “x1” naquele momento, resultado da operação de escrita “WS(x1)” sobre “L1”;

● … mais tarde, “P” executa uma leitura em “x” na cópia local “L2”, retornando o valor “x2” naquele momento, no contexto onde “WS(x1)” foi propagada para “L2” => “WS(x1,x2)”

● Fig. 7.12 – Operações de leitura executadas por “P” em 02 cópias locais do mesmo “data store”. a) “monotonic-read consistency”

Luís F. Faina - 2014 Pg. 57/116


… 7.3.2 Leituras Monotônicas

● Em contraste, Fig. 7.12 b) mostra que a consistência de leituras monotônicas não é garantida pois “WS(x1)” não se propagou para “L2”, pois apenas “WS(x2)” foi realizada;

● … não há garantias que este conjunto contenha todas as operações contidas em “WS(x1)”.

● Fig. 7.12 – Operações de leitura executadas por “P” em 02 cópias locais do mesmo “data store”. a) “monotonic-read consistency” b) “data store” não garante a leituras monotônicas.

Luís F. Faina - 2014 Pg. 58/116


7.3.3 Escritas Monotônicas

● “monotonic-write consistency” - uma operação de escrita em um dado “x” é completada antes de alguma operação de escrita subsequente do mesmo processo sobre o mesmo dado “x”.

● … ou seja, uma operação de escrita executada significa que a cópia na qual operações sucessivas forem realizadas reflete operações de escrita anteriormente executadas pelo mesmo processo, independente do local onde foi iniciada.


● … em ambos os casos estamos interessados nas operações executadas por um único processo “P”, aqui representadas em negrito enquanto a linha pontilhada representa a ordem em que as operações são executadas - “W(x1)” antes de “W(x2)”.

Luís F. Faina - 2014 Pg. 59/116


… 7.3.3 Escritas Monotônicas

● Fig. 7.13 a) … para garantir a consistência monotônica de escritas, é necessário que as operações de escrita anteriores tenham sido propagadas para as demais cópias.

● Fig. 7.13 b) mostra cenário onde a consistência de escritas mono- tônicas não é garantida, pois “WS(x1)” não foi propagada para “L2”

● Fig. 7.13 – Operações de escritas executadas por “P” em 02 cópias locais do mesmo “data store”. a) “data store” com consistência de escritas monotônicas; b) “data store” que não garante a consistência de escritas monotônicas.

Luís F. Faina - 2014 Pg. 60/116


7.3.4 Leia suas Escritas

● “read-your-wristes consistency” - efeito de operações de escrita por um processo em um item de dado “x” será visto por uma leitura subsequente em “x” pelo mesmo processo.

● … ou seja, operação de escrita é sempre completada antes de uma operação de leitura subsequente executada pelo mesmo processo, independente de onde a operação foi executada.


● … em ambos os casos estamos interessados nas operações executadas por um único processo “P”, aqui representadas em negrito enquanto a linha pontilhada representa a ordem em que as operações são executadas - “W(x1)” antes de “R(x2)”.

Luís F. Faina - 2014 Pg. 61/116


… 7.3.4 Leia suas Escritas

● Fig. 7.14 a) - “P” executa uma operação de escrita “W(x1)” e mais tarde executa uma operação de leitura “R(x2)” em uma outra cópia com a garantia de “W(x1)” foi propagada para “L2” => “W(x1,x2)”

● Fig. 7.14 b) - “W(x1)” foi mantida aparte da atualização “W(x2)”, ou seja, o efeito da operação prévia de escrita não foi propagada.

● Fig. 7.14 a) “data store” que provê “read-your-writes consistency”. b) “data store” que não provê “read-your-writes consistency”.

Luís F. Faina - 2014 Pg. 62/116


7.3.5 Escritas seguem Leituras

● “writes-follow-reads consistency” - uma operação de escrita no item de dado “x” após uma operação de leitura em “x” pelo mesmo processo é realizada em uma cópia de “x” atualizada com o valor mais recentemente lido por aquele processo.


● … em ambos os casos estamos interessados nas operações executadas por um único processo “P”, aqui representadas em negrito enquanto a linha pontilhada representa a ordem em que as operações são executadas - “R(x1)” antes de “W(x2)”.

Luís F. Faina - 2014 Pg. 63/116


… 7.3.5 Escritas seguem Leituras

● Fig. 7.15 a) “P” executa uma operação de leitura “R(x1)” e mais tarde executa uma operação de escrita “W(x2)” em uma outra cópia com a garantia de “W(x1)” é parte de “W(x2)”

● Fig. 7.15 b) – não há garantia de que a operação em “L2” se deu sobre uma cópia que é consistente com aquela lida em “L1”.

● Fig. 7.15 a) “data store” com consistência “writes-follow-reads”. b) “data store” sem consistência “writes-follow-reads”.

Luís F. Faina - 2014 Pg. 64/116

7 Consistência e Replicação – 7.4 Gerenciamento de Réplica

7.4 Gerenciamento de Réplica

● “questão fundamental” - decidir onde, quando e por quem as réplicas devem ser posicionadas e quais mecanismos usar para manter as réplicas consistentes.

● … problema de possicionamento pode ser subdividido em 02 subproblemas: possicionamento de servidores de réplicas e possicionamento de conteúdo;

● … naturalmente que antes de definir o possicionamento do conteúdo, cabe o possicionamento dos servidores de réplicas.

Luís F. Faina - 2014 Pg. 65/116


7.4.1 Possicionamento do Servidor de Réplica

● “possicionamento” - trata-se de um problema de cunho com viez gerencial e/ou comercial do que um problema de otimização;

● … existem diversas maneiras de se calcular a melhor localização do servidor de réplicas, ou seja, como escolher as melhores “k” posições de “n” possíveis localizações.

● “Qui et al” (2001) assume a distância entre o cliente e a locali- zação dos servidores de réplicas como ponto de partida;

● … localizações medidas por latênca ou largura de banda.

● “solução” - escolher um servidor por vez de modo que a distância média entre eles e seus clientes seja a menor possível, dado que “k” servidores tenham sido possicionados de um total de “n” servidores => “n – k” localizações não são contabilizadas.

Luís F. Faina - 2014 Pg. 66/116


… 7.4.1 Possicionamento do Servidor de Réplica

● “Radoslavov et al” (2001) – consideram a topologia dos servidores quanto aos “Autonomous Systems” - ASs desconsiderando a posição dos clientes;

● “autonomous systems” - rede na qual todos os nós executam o mesmo protocolo de roteamento e são mantidos e gerenciados pela mesma organização.

● “proposta” - considera o maior AS e possiciona o servidor no roteador com o maior número de interfaces de rede, na sequên- cia, repete o algoritmo para o segundo maior AS.

● ...considerando que clientes estão distribuídos na rede, o resultado alcançado para clientes que conheçam a localização dos servidores em relação aqueles que não conhece é similar.

Luís F. Faina - 2014 Pg. 67/116



● “desvantagens” - ambos os algoritmos são computacionalmene caros e apresentam complexidade > O(N2), onde “N” representa o número de localizações possíveis de serem inspecionadas;

● … mesmo com alguns milhares de localizações faz-se necessário alguns minutos para encontrar o servidor mais próximo;

● … seu uso torna-se inaceitável, ainda mais na presença de “flash crowd” - rajada de requisições para um “site” específico.

Luís F. Faina - 2014 Pg. 68/116



● “Szymaniak et al.” (2006) - desenvolveram uma maneira de encontrar rapidamente o local onde posicionar as réplicas:

● região é identificada como um coleção de nós de mesmo conteúdo que apresentem baixa latência entre os nós;

● “objetivo” - selecionar a região com maior demanda, ou seja, aquela com o maior nro. de nós e na sequência permitir que um dos nós atue como o servidor de réplicas.

● “idéia” - identificar “k” maiores “clusters” e escolher um nó de cada “cluster” para receber o conteúdo replicado;

● … inicialmente o espaço total é particionado em células e as “k” células mais densas são escolhidas para receber as réplicas.

Luís F. Faina - 2014 Pg. 69/116



● Fig. 7.16 – Escolha do tamanho apropriado de uma célula para possicionamento do servidor de réplicas.

● “células muito grandes” - pode existir diversos clusters e, assim, um nro. pequeno de servidores de réplicas é selecionado;

● “células muito pequenas” - cluster espalhado por varias células e, assim, um nro. grande de servidores de réplicas é selecionado.

Luís F. Faina - 2014 Pg. 70/116



● … tamanho apropriado por ser computado como um função simples da distância média entre 02 nós e o nro. de réplicas;

● … pode ser mostrado que o algoritmo apresenta desempenho tão bom o algoritmo ótimo – descrito por “Qiu et al.” (2001), mas com uma complexidade menor: “O( N * max{ logN, K} )”.

● e.g., … experimentos monstram que encontrar os 20 melhores locais para uma coleção de 64.000 nós é aproximadamente 50.000 vezes mais rápido.

Luís F. Faina - 2014 Pg. 71/116


7.4.2 Possicionamento de Conteúdo

● Quando se trata de possicionamento e replicação de conteúdo, 03 diferentes tipos de réplicas podem ser logicamente organizados.

● Fig. 7.17 – Organização lógica de diferentes tipos de cópias de um “data store” em 03 aneis concêntricos.

Luís F. Faina - 2014 Pg. 72/116


… 7.4.2 Possicionamento de Conteúdo

● “permanent replicas” - podem ser consideradas como o conjunto inicial de réplicas que constituem um “data store”;

● e.g., “sites” Web estão geralmente distribuídos em 02 formas:

● … arquivos que constituem o site são replicados em um nro. restrito de servidores de uma mesma célula, assim, uma requisição é encaminhada para um dos servidores segundo alg. “round-robin”.

● … “site” web é copiado para um nro restrito de servidores espalhados geograficamente pela Internet, assim, clientes simplesmente escolhem um dos sites espelhados

● … semelhança entre ambos é que há um nro. reduzido de réplicas em que a configuração é mais ou menos estática.

Luís F. Faina - 2014 Pg. 73/116



● … organização similar está presente nos bancos de dados distribuídos - “OSZu & Valduriez” (1999);

● … bancos de dados são distribuídos e replicados em servidores que conjuntamente formam um “cluster” de servidores, comumente referenciados como “arquitetura nada-compartilhada”;

● “arquitetura nada-compartilhada” - memória secundária e a memória principal não são compartilhados pelos processadores.

● … ou seja, banco de dados é distribuído e possivelmente replicado em um nro. de “sites” dispersos geograficamente.

Luís F. Faina - 2014 Pg. 74/116



● “server-initiated replicas” - são cópias do “data store” criados pelo proprietário do “data store” para aumentar o desempenho;

● e.g., servidor em Nova York que repentinamente começa a receber uma rajada de requisições de um local distante;

● … talvez, seja necessário o uso de réplicas temporárias no local de origem das requisições ou ao menos próximo;

● … serviços de hospedagem Web oferecem uma coleção relativamente estática de servidores espalhados na Internet que podem manter e prover o acesso aos arquivos Web;

● “Sivasubramanian” et al. (2004) discute a visão geral de replicação em serviços de hospedagem na Web.

Luís F. Faina - 2014 Pg. 75/116



● Uma outra abordagem para Serviço de Hospedagem Web é descrita por “Rabinovich” et al. (1999):

● … algoritmo é projetado para suportar páginas Web para as quais assume-se que operações de atualização são raras comparadas com as operações de leitura;

● e.g., … servidores no serviço de hospedagem “web” podem decidir qual servidor está mais próximo de um cliente “C”, tendo por base as informações dos bancos de dados de roteamento;

● … se “C1” e “C2” compartilham o mesmo servidor mais próximo “P”, todas as requisições de acesso para o arquivo “F” no servidor “Q” vindas de “C1” e “C2” são registradas em “Q” com uma única contagem de acesso “cnt(P,F)” - Fig. 7.18

Luís F. Faina - 2014 Pg. 76/116



● … se “C1” e “C2” compartilham o mesmo servidor mais próximo “P”, todas as requisições de acesso para o arquivo “F” no servidor “Q” vindas de “C1” e “C2” são registradas em “Q” como uma única contagem de acesso “cnt(P,F)” - figura abaixo.

● Fig. 7.18 – Contando requisições de acesso de diferentes clientes.

Luís F. Faina - 2014 Pg. 77/116



● … quando o nro. de requisições para um arquivo “F” no servidor “S” cai abaixo de um limite estabelecido - “del(S,F)”, o arquivo pode ser removido do servidor;

● … como consequência o nro. de réplicas do arquivo “F” cai, possivelmente acarretando um aumento de carga nos servidores;

● … medidas são tomadas para garantir que ao menos um cópia de cada arquivo continue a existir.

● … se o limite de replicação “rep(S,F)” é maior que “del(S,F)”, indica que vale a pena replicá-lo em outros servidores;

● … se o número de requisições estiver entre os limites de replicação e remoção, então para aquele arquivo é permitido somente a migração.

Luís F. Faina - 2014 Pg. 78/116



● Quando um servidor “Q” decide reavaliar os arquivos no seu repositório, ele verifica o contagem de acessos para os arquivos;

● … se o nro de acessos para “F” está abaixo de um limiar, remove-se “F” a menos que seja a última cópia;

● … além disso, se para algum servidor “P”, “cnt Q (P,F) excede em mais da metada do total de requisições para “F” em “Q”, o servidor “P” é solicitado a assumir a cópia de “F”, ou seja, migração.

● … migração do arquivo “F” para o servidor “P” nem sempre ocorre, p.ex., por que “P” está ainda carregado e fora do disco;

● … neste caso, “Q” irá tentar replicar “F” em outros servidores, desde que o nro total de acessos para “F” em “Q” exceda o limite de replicação “rep(Q,F)”.

Luís F. Faina - 2014 Pg. 79/116



● “client-initiated replica” - comumente conhecidas como “cache”, são na essência um armazenamento local utilizado pelo cliente para armazenar temporariamente dados objeto da requisição;

● … “data store” do qual os dados foram lidos não tem nada a ver com a manutenção da consistência dos dados salvaguardados;

● … quando a maior parte das operação são leituras de dados, o cliente pode guardar os dados que são requisitados em uma “cache” local para melhorar o desempenho;

● … essa “cache” está na máquina cliente ou em uma “cache” separada na rede local onde máquina cliente se encontra.

Luís F. Faina - 2014 Pg. 80/116



● … dados são mantidos na “cache” por um tempo limitado, p.ex., para prevenir dados obsoletos sendo usados ou simplesmente abrir espaço para outros dados;

● … para melhorar a taxa de acerto na “cache”, “caches” podem ser compartilhadas entre os clientes, desde que dados requisitados pelo cliente “C1” são também requisitados pelo cliente “C2”.

● … possicionamento de “cache” de cliente é relativamente simples: “cache” é possicionada na mesma máquina que o cliente; “cache” na máquina compartilhada por clientes na rede local;

● … em alguns casos, níveis extras de “cache” são introduzidos entre departamentos ou organizações.

Luís F. Faina - 2014 Pg. 81/116


7.4.3 Distribuição de Conteúdo

● “gerenciamento de réplicas” - trata da propagação e/ou atualização de conteúdo para servidores relevantes de réplicas e envolve vários aspectos:

● “state vs operations” - um importante aspecto de projeto refere-se ao que deve ser propagado:

● propaga somente a notificação de atualização – nada é propagado além de notificações, ou seja, dados não são propagados;

● transferir dados de uma cópia para outra – quando a relação de leituras/ escritas é alta é interessante transferir dados;

● propagar a operação de atualização para as outras cópias – cada réplica recebe apenas parâmetros da operação de atualização.

Luís F. Faina - 2014 Pg. 82/116


… 7.4.3 Distribuição de Conteúdo

● “propagação de notificação” - nada é propagado além de notifi- cações, ou seja, encaminha através do protocolo de invalidação notificação às outras cópias de que o dado não é mais válido;

● … protocolo de invalidação pode especificar que parte do “data store” foi atualizada, assim, apenas uma parte da cópia está atualmente invalidada.

● … principal “vantagem” dos protocolos de invalidação é que utilizam pouca banda da rede, pois a informação transferida é a especificação de quais dados não mais são válidos;

● ... tais protocolos geralmente trabalham bem quando há muitas operações de atualização comparado com as operações de leitura, ou seja, relação leituras/escritas é relativamente pequena.

Luís F. Faina - 2014 Pg. 83/116



● “transferir dados de uma cópia para outra” – utilizada quando a relação de leituras/escritas é relativamente alta;

● … neste contexto, a probabilidade que uma atualização seja efetiva no sentido de que o dado modificado será lido antes da próxima atualização é alta – justicando a transferência;

● … ao invés de propagar os dados modificados é possível salvar - “log” as mudanças e transfera somente aquelas alterações salvas para economizar banda de rede;

● … transferência são sempre concatenadas no sentido de que múltiplas modificações são agrupadas em um única mensagem, economizando “overhead” de comunicação.

Luís F. Faina - 2014 Pg. 84/116



● “propagar a operação de atualização para as outras cópias” - também chamada de “replicação ativa”, cada réplica recebe apenas parâmetros da operação de atualização;

● “vantagem” - pode frequentemente ser propagada com o mínimo gasto de banda de rede, uma vez que os parâmetros associados com uma operação são relativamente pequenos;

● “desvantagem” - maior processamento pode ser exigido em cada um dos servidores de réplica, especialmente onde as operações são relativamente complexas.

Luís F. Faina - 2014 Pg. 85/116



● “protocolos pull vs push” - podem ser subdivididos em “push-based protocols” e “pull-based protocols”.

● “push-based protocols” - servidor inicia a atualização sem que outro servidor ou cliente encaminhe solicitação.

● “pull-based protocols” - servidor ou cliente encaminha solicitação de atualização para um servidor de réplicas.

Luís F. Faina - 2014 Pg. 86/116



● “push-based protocols” ou “server-based protocols” - servidor propaga as atualizações para as réplicas, independente de solicitação por parte das réplicas.

● … envio de atualizações é frequentemente usado entre réplicas permanentes iniciadas pelo servidor, mas pode ser usado para atualização de “cache” de clientes.

● … são normalmente aplicadas quando as réplicas são mantidas sob um alto grau de consistência – réplicas idênticas.

● Alto grau de consistência advém do fato de que réplicas permanentes iniciadas pelo servidor são caracterizadas por operações de leitura;

● … nestes casos, “push-based protocols” são eficientes no sentido de que toda atualização será passível de leitura com alta probabilidade por 01 (um) ou mais leitores.

Luís F. Faina - 2014 Pg. 87/116



● “pull-based protocols” ou “client-based protocols” - servidor ou cliente solicita a um outro servidor que encaminhe quaisquer atualizações que tenha até o momento;

● … frequentemente usada em “caches” de clientes, “pull-based protocols” são eficientes quando a taxa de leituras/escritas é relativamente baixa, p.ex., “nonshared client caches”;

● … entretanto, até mesmo quando há compartilhamento de “cache” entre clientes, a abordagem “pull” pode ser eficiente quando o compartilhamento de itens de dados é raro;

● … principal desvantagem em relação ao “push-based protocols” é que o tempo de resposta cresce nos casos de “cache miss”.

Luís F. Faina - 2014 Pg. 88/116



● “push-based protocols” - servidor rastreia todas as “caches” de clientes e pelo fato do servidor ser menos tolerante a falhas, considerável “overhead” é introduzido no servidor.

● “messages sent” - mensagens são enviadas para cada cliente no protocolo “push-based” para atualização;

● … enquanto no protocolo “pull-based” o cliente irá escolher o servidor e, se necessário, solicitar o dado modificado.

● Fig. 7.19 – Comparação entre protocolos “push-based” e “pull- based” em um cenário com múltiplos clientes e 01 servidor.

Luís F. Faina - 2014 Pg. 89/116



● “response time” - no protocolo “push-based”, servidor envia dados modificados para as “caches” dos clientes, assim, tempo de resposta para o cliente é zero;

● … no protocolo “pull-based” o tempo de resposta é determinado pelo tempo para buscar o dado modificado do servidor.

● Fig. 7.19 – Comparação entre protocolos “push-based” e “pull- based” em um cenário com múltiplos clientes e 01 servidor.

Luís F. Faina - 2014 Pg. 90/116



● “unicasting vs multicasting” - relacionado com envio ou recuperação de atualização pela rede subjacente;

● “unicast communication” - quando um servidor, parte de um “data store” encaminha suas atualizações para “n” outros servidores, isto se dá através de “n” mensagens em separado;

● “multicast communication” - normalmente, a rede subjacente se encarrega de enviar de modo eficiente as mensagens para múltiplos receptores – servidores ou clientes.

● … em muitos casos, é mais barato utilizar “multicast” disponível, embora exceções possam ocorrer.

● e.g., considere que todas as réplicas estão localizadas na mesma rede local e que tenha disponível o “broadcasting”;

Luís F. Faina - 2014 Pg. 91/116



● e.g., considere que todas as réplicas estão localizadas na mesma rede local e que tenha disponível o “broadcasting”;

● … neste caso, “broadcasting” ou “multicasting” não é mais caro que encaminhar mensagens ponto-a-ponto;

● “multicasting” - pode ser com frequência eficiente quando combinado com protocolo “push-based”, pois um servidor simplesmente utiliza um único grupo “multicast”.

● “unicasting” - mais eficiente no protocolo “pull-based”, pois geralmente um único cliente ou servidor é o responsável pela requisição de atualização de suas cópias.

Luís F. Faina - 2014 Pg. 92/116

7 Consistência e Replicação – 7.5 Protocolos de Consistência

7.5 Protocolos de Consistência

● Nesta seção, nos concentramos na implementação dos modelos de consistência através dos protocolos de consistência.

● “consistency protocol” - descreve a implementação de um modelo de consistência específico.

Luís F. Faina - 2014 Pg. 93/116



● “Yu & Vahdat” (2002) - desenvolveram alguns protocolos para tratar as 03 formas de consistência: desvio de valor numérico; desvio de idade e desvio de ordenação de operações.

● “bounding numerical desviation” - deseja-se manter o desvio numérico dentro de limites previamente estabelecidos.

● … cada “W(x)” será associado a um peso que representa o valor numérico para o qual “x” será atualizado, ou seja, “weight( W(x) )” ou simplesmente “weight( W )” com “weight( W )” > 0;

● … “TW[ i,j ]” são escritas executas em no servidor “Si” que tenham sido originadas do servidor “Sj”, ou seja:

Luís F. Faina - 2014 Pg. 94/116



● “TW[ i,j ]” são escritas executas em no servidor “Si” que tenham sido originadas do servidor “Sj”, ou seja:

TW[ i,j ] = Somatório { weight(W) | origin(W) = Sj & W pertence Li } e TW[ i,i ] representa todas as escritas submetidas a Si

● “objetivo” - permitir que o valor “vi” no servidor “Si” desvie dentro de limites do valor “v(t)” de “x”, ou seja:

v(t) = v(0) + Somatóriok=1 até N TW[ k,k ] - v(0) valor inicial de “x”;

vi = v(0) + Somatóriok=1 até N TW[ i,k ] - este valor é determinado por todas as escritas já submetidas no servidor.

Luís F. Faina - 2014 Pg. 95/116



● … dado que “vi <= v(t)” e considerando desvios absolutos, para todo servidor “Si”, associa-se um limite superior “δi” tal que:

v(t) – vi ≤ δi

● … escritas submetidas ao servidor “Si” devem ser propagadas para todos os outros servidores, p.ex., protocolo epidêmico;

● … quando “Si” propagar a escrita originada de “Sj” para “Sk”, “Sk” é capaz de aprender sobre TW[ i,j ] no momento do envio da escrita, ou seja, “Sk” pode manter a visão “TWk[ i,j ]” sobre o que “Si” terá como valor para “TW[ i,j ]” ...

0 ≤ TWk[ i,j ] ≤ TW[ i,j ] ≤ TW[ j,j ]

Luís F. Faina - 2014 Pg. 96/116



● … a idéia é que quando o servidor “Sk” percebe que “Sj” não está no passo de atualização submetida por “Sk”, ele encaminha escritas do seu “log” de escritas para “Si”;

● … este encaminhamento efetivamente avança a visão “TWk[ i,k ]” que “Sk” tem de “TW[ i,k ]” tornando o desvio, ou seja, TW[ i,k ] - TWk[ i,k ] menor, ou seja, “Sk” avança na “view”.

Luís F. Faina - 2014 Pg. 97/116


7.5.2 Protocolo “Primary-Based”

● Na prática, verifica-se que aplicações distribuídas geralmente seguem modelos de consistência fáceis de serem entendidos, p.ex., desvio numérico ou desvio de idade;

● … se considerarmos modelos que tratam a consistência de ordenação de operações ou a consistência sequencial;

● … verifica-se que são populares aqueles modelos nos quais as operações podem ser agrupadas por “locks” ou por transações;

● … a medida que os modelos de consistência tornam-se mais difíceis de serem entendidos pelos desenvolvedores, os mesmos são ignorados ainda que melhorem a performance.

Luís F. Faina - 2014 Pg. 98/116


… 7.5.2 Protocolo “Primary-Based”

● Na consistência sequencial, cada item de dado “x” do “data store” tem um primário associado, que é responsável pela coordenação de operações de escrita em “x” => “primary-based protocols”.

● “Remote-Write Protocols” - … todas as operações de escrita são encaminhadas para servidor único e fixo, enquanto as operações de leitura são mantidas localmente.

● … primário realiza a atualização na sua cópia local para “x” e, na sequência, encaminha a atualização para o servidor de “backup”, que por sua vez informa ao primário a conclusão da atualização.

Luís F. Faina - 2014 Pg. 99/116



● Fig. 7.20 – Princípio dos Protocolos “Primary-Based”

Luís F. Faina - 2014 Pg. 100/116



● “problema potencial” - … processo que iniciou a atualização pode ter que esperar um longo tempo para continuar, pois normalmente a atualização é implementada como operação bloqueante;

● … uma alternativa é o uso de operações não bloqueantes, assim, tão logo tenha atualizado sua cópia local de “x”, o mesmo retorna o reconhecimento para o solicitante;

● … somente depois solicita aos servidores de “backup” que procedam com a atualização em suas cópias locais.

● “problema” - clientes não sabem com certeza que operações de atualização foram de fato complementadas, ou seja, são problemas relacionados a tolerância a falhas.

Luís F. Faina - 2014 Pg. 101/116



● “Local-Write Protocols” - quando um processo quer atualizar um item de dado “x”, ele localiza a cópia primária de “x” e move o item da dado “x” da cópia primária para a sua localização.

● … operações de escrita sucessivas são realizadas localmente, enquanto processos de leitura acessam suas cópias locais;

● … atualizações são propagadas para as réplicas após o primário completar, ou seja, cada cópia local atualizar e retornar.

Luís F. Faina - 2014 Pg. 102/116



● Fig. 7.20 – Protocolo “Primary-Based” no qual o primário migra para o processo que quer realizar a atualização.

Luís F. Faina - 2014 Pg. 103/116



● e.g., computadores móveis que operam em modo disconectado podem utilizar o protocolo “primary-based” com escrita local;

● … antes de se desconectar, o computador torna-se o servidor primário para cada item de dado que ele espera atualizar;

● … enquanto desconectado, todas as atualizações são realizadas localmente, enquanto outros processos podem efetuar leituras nas suas cópias locais, mas nenhuma atualização;

● … mais tarde, atualizações são propagadas para os “backups”, trazendo o “data store” para o estado consistente.

Luís F. Faina - 2014 Pg. 104/116


7.5.3 Protocolos “Replicated-Write”

● “Replicated-Write Protocols” - operações de escrita podem ser realizadas em múltiplas réplicas ao invés de somente uma, como no caso de “primary-based replicas”.

● … distinções podem ser estabelecidas entre replicação ativa, na qual uma operação é encaminhada para todas as réplicas, e protocolos de consistência baseados em votação majoritária.

Luís F. Faina - 2014 Pg. 105/116


… 7.5.3 Protocolos “Replicated-Write”

● “active replication” - cada réplica tem um processo associado que realiza operações de atualização;

● … atualizações são propagadas através das operações de escrita que causam as atualizações, ou seja, operações são enviadas para cada uma das réplicas.

● “problema” - operações precisam ser realizadas na mesma ordem em todas as réplicas - “backups”, exigindo um mecanismo “multicast” totalmente ordenado;

● … ainda que implementado com o relógio lógico de Lamport, o “multicasting” não é escalável em sistemas distribuídos grandes.

Luís F. Faina - 2014 Pg. 106/116



● “quorum-based protocols” - … clientes precisam requerer e adquirir a permissão de múltiplos servidores antes de ler ou escrever um item de dado replicado.

● e.g., considere um sistema de arquivo distribuído e suponha que um arquivo está replicado em “N” servidores;

● … podemos estabelecer que para atualizar o arquivo, um cliente precisa contactar ao menos “½” dos servidores + “1” e solicitá-los que concordem com a atualização;

● … uma vez que tenham concordado, o arquivo é modificado e um novo nro. de versão é associado ao novo arquivo;

● … procedimento análogo é válido para ler um arquivo replicado.

Luís F. Faina - 2014 Pg. 107/116



● e.g., considere 05 servidores e um cliente determina que 03 deles tem a versão 8 de um dado arquivo, é impossível que os outros 02 tenham a versão 9 ?

● … qualquer atualização bem sucedida da versão 08 para a 09 requer que 03 servidores tenham concordado, e não 02;

● … portanto, é impossível que os outros 02 tenham a versão 09!

Luís F. Faina - 2014 Pg. 108/116



● “Gifford's Scheme” - para ler um arquivo com “N” réplicas, um cliente precisa montar um “quorum” de leitura, ou seja, um coleção arbitrária de “NR” servidores ou mais;

● … para escrever em um arquivo, o cliente precisa montar um “quorum” de escrita com ao menos “NW” servidores, de modo que ** “NR + NW > N” e “NW > N/2” sejam satisfeitas.

● 1a restrição previne conflitos de leitura-escrita;

● 2a restrição previne conflitos de escrita-escrita.

● Obs.: somente depois de um nro apropriado de servidores concordarem em participar, pode um arquivo ser lido ou escrito.

Luís F. Faina - 2014 Pg. 109/116



● Fig. 7.22 – 03 exemplos do Algoritmo de Votação. a) Escolha correta de um conjunto de leitura e escrita. b) Escolha que pode conduzir a conflitos de escrita-escrita. c) Escolha correta, conhe- cida como ROWA (Read Once, Write All)

Luís F. Faina - 2014 Pg. 110/116


7.5.4 Protocolos “Cache-Coherence”

● “cache” - caso especial de replicação no sentido que é geralmente controlada pelos clientes e não pelos servidores.

● “cache-coherence protocols” - garantem que a “cache” esteja consistente com réplicas iniciadas pelo servidor e, não são diferentes dos protocolos de consistência vistos anteriormente.

● … soluções de “caching” diferem na sua estratégia de detecção de coerência, ou seja, quando inconsistências aparecem:

● “static solution” - compilador faz a análise necessária antes da execução, para determinar quais dados podem se tornar inconsistentes e, na sequência, simplesmente insere instruções para evitar inconsistências.

● “dynamic solution” - inconsistências na “cache” são detectadas com o servidor em tempo de execução para ver quando durante uma transação um dado na “cache” foi modificado.

Luís F. Faina - 2014 Pg. 111/116


… 7.5.4 Protocolos “Cache-Coherence”

● “coherence enforcement strategy” - variação de protocolos de coerência de “cache”, determina como as “caches” são mantidas consistentes com as cópias armazenadas nos servidores;

● “solução mais simples” - não permitir que dados sejam mantidos em “caches”, ou seja, dados compartilhados são mantidos somente nos servidores que por sua vez mantém a consistência ;

● … se, no entanto, dados compartilhados são mantidos em “cache”, há 02 abordagens para garantir a coerência:

01 – deixar o servidor enviar a invalidação para todas as “caches” quando um item de dado é modificado;

02 – servidor propaga a atualização para todas as “caches” quando um item de dado é modificado.

Luís F. Faina - 2014 Pg. 112/116


… 7.5.4 Protocolos “Cache-Coherence”

● … seja no envio da invalidação ou das atualizações, ambas são frequentemente suportadas por banco de dados dos clientes.

● Também é necessário considerar o cenário no qual um processo modifica itens de dados na “cache”:

● “read-only caches” - operações de atualização podem ser realizadas somente pelos servidores.

● “write-through caches” - permitir que o cliente modifique os dados da “cache” e encaminhe a atualização para o servidor.

Luís F. Faina - 2014 Pg. 113/116


7.5.5 Implementando Consistência “Client-Centric”

● Normalmente, a implementação de consistência tendo por base o cliente é direta, se aspectos de desempenho forem ignorados.

● “naive implementation” - cada operação de escrita recebe um identificador global único, que é atribuído pelo servidor para o qual a operação de escrita foi submetida;

● … para cada cliente, 02 conjuntos de “writes” são mantidos:

● conjunto de leituras para o cliente consiste de escritas relevantes para as operações de leitura realizadas por aquele cliente;

● conjunto de escritas para o cliente consiste de escritas, ou os seus identificadores, realizadas por aquele cliente.

Luís F. Faina - 2014 Pg. 114/116


7.5.5 Implementando Consistência “Client-Centric”

● “monotonic-read consistency” :

● … quando um cliente realiza uma operação de leitura no servidor, o servidor trata o conjunto de leituras do cliente para verificar quais identificador de escrita ocorreram localmente;

● … se não, o cliente contacta outros servidores para garantir que está atualizado antes de realizar a operação de leitura;

● … ocasionalmente, a operação de leitura pode ser encaminhada para o servidor onde a operação de escrita já tenha ocorrido;

● … após a operação de leitura ser completada, a operação de escrita já concluída no servidor selecionado e que é relevante para a operação de leitura é adicionada ao “read set” do cliente.

Luís F. Faina - 2014 Pg. 115/116


… 7.5.5 Implementando Consistência “Client-Centric”

● .. é possível determinar exatamente onde a operação de escrita indentificada no “read set” ocorreu, p.ex., incluindo o identificador do servidor para o qual a operação foi submetida no identificador da operação de escrita - “write identifier”;

● … cabe ao servidor, manter o “log” de operações de escrita para até mesmo repetir em outro servidor;

● … adicionalmente, operações de escrita devem ser realizadas na ordem em que foram submetidas, p.ex., permitindo que o cliente gere nro. de sequência global único e incluí-lo no “write identifier”;

● … como o dado pode ser modificado apenas pelo proprietário, o último pode manter o nro. de sequência.

Luís F. Faina - 2014 Pg. 116/116


… 7.5.5 Implementando Consistência “Client-Centric”

● “monotonic-write consistency” :

● … quando o cliente inicia uma nova operação de escrita, o servidor recebe o “write set” do cliente;

● … na sequência, garante que as operações de escrita identifica- das sejam realizadas primeiro e na ordem correta;

● … após executar a nova operação, o identificador de escrita da operação é adicionado ao “write set”;

● Obs.: Atualizar o servidor com o “write set” do cliente, introduz considerável aumento no tempo de resposta uma vez que o cliente deve esperar a operação ser concluída.

Documents

Cap. 07 – Consistência e Replicação - Faculdade de …faina/BCC_Crs/GSI028-2014-1S/DL/DS-Ch07.pdf · 7.1.2 Replicação como Técnica de Escalabilidade 7.2 – Modelos de Consistência