cap07

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 1 Hélio Crestana Guardia - 2011
Consistência e Replicação
 Replicação de dados é importante em SDs
 Replicação ocorre para melhorar confiabilidade ou aumentar desempenho
 Manutenção da consistência das réplicas é problema
 Consistência implica atualizar demais cópias quando uma delas é alterada
 Questões:
– O que significa consistência de dados replicados?
– Como pode ser obtida?
– Para que serve consistência e como se relaciona com escalabilidade?
 Modelos de consistência
– Data-centric consistency 
– Client-centric consistency 
 Gerenciamento de réplicas: 
– Posicionamento e distribuição dos conteúdos
– Consistência
 Formas de consistência
 Cache e consistência
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 2 Hélio Crestana Guardia - 2011
Razões para replicação
 Razões para replicação: confiabilidade e desempenho
 Confiabilidade: 
 Réplica permite continuidade de operação se uma cópia falha, apenas 
redirecionando os acessos
 Existência de múltiplas cópias também provê proteção contra 
corrupção dos dados
 Replicação favorece a escalabilidade numérica e de abrangência geográfica
 Escalabilidade numérica obtida replicando dados e particionando 
acessos
 Aumento da abrangência geográfica obtido com a replicação e o 
posicionamento dos dados próximos aos usuários, reduzindo tempos de 
acesso e melhorando desempenho
 Aumendo de desempenho pode ser difícil de avaliar: melhora nos tempos de 
resposta é gerada ao custo de aumento de trasmissões para garantir 
consistência
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 3 Hélio Crestana Guardia - 2011
Replicação
 Existência de múltiplas cópias pode ocasionar problemas de consistência
 Alteração numa cópia a torna diferente das demais, que precisam ser 
atualizadas
 Quando e como as atualizações são realizadas determina o custo da 
replicação
Ex.: cache WWW
 Para melhorar tempos de resposta, navegador WWW pode manter cópias de páginas 
em cache. Requisições subsequentes podem ser fornecidas rapidamente a partir da 
cópia local
 Modificações não são propagadas ao cliente, tornando cópia inconsistente
 Solução (?): 
 Desabilitar cache
 Usar cópias controladas pelo servidor (podem não estar próximas ao cliente...)
 Fazer servidor invalidar cópias: requer manutenção de informações sobre todas 
as cópias no servidor e envios de informações de invalidação
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 4 Hélio Crestana Guardia - 2011
Replicação como técnica de escalabilidade
 Replicação e técnicas de cache são comumente usadas para prover 
escalabilidade
 Questões de escalabilidade associadas a problemas de desempenho
 Posicionamento de cópias dos dados próximas dos (processos) usuários 
pode prover aumento de desempenho com redução dos tempos de acesso
 Atualização das cópias pode requerer aumento no consumo da largura de 
banda de transmissão
 Compromisso entre atualizações e uso do meio de transmissão:
 Supondo processo P que acessa réplica local dos dados N vezes por segundo
 Réplicas são atualizadas M vezes por segundo
 Atualizações renovam completamente as cópias dos dados
 Se N << M (taxa de acesso por atualizações é muito pequena), muitas 
atualizções podem não ser visíveis por P
 Manutenção de cópia próxima a P não é vantajosa, ou deve-se usar outra 
política de atualizações
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 5 Hélio Crestana Guardia - 2011
Replicação como técnica de escalabilidade
 Manutenção da consistência das cópias pode gerar implicações na 
escalabilidade
 Alterações de uma cópia devem ser propagadas antes que outras operações 
sejam realizadas
 Alterações são realizadas como uma única operação atômica, ou transação
 Implementação de operações atômicas envolvendo grandes números de 
cópias é complexa, tendo e vista os requisitos de velocidade
 Réplicas devem sincronizar-se para atualização
 Dificuldade para determinar quando uma atualização deve ser aplicada 
localmente
 Réplicas podem decidir sobre ordenação de eventos usando timestamps de 
Lamport, ou usando coordenador
 Sincronizações envolvem tempo significativo para comunicação, 
especialmente em ambiente de redes de longa distância
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 6 Hélio Crestana Guardia - 2011
Replicação como técnica de escalabilidade
 Dilema: escalabilidade pode ser obtida com replicação e melhora no tempo 
de resposta, mas manutenção de consistência implica sincronização custosa 
em termos de desempenho
 Para garantir que réplicas estarão consistentes é preciso gantir que 
operações conflitantes sejam realizadas na mesma ordem em todo lugar
 Operações conflitantes:
 Leitura-escrita (read–write): leitura e escrita ocorrendo concorrentemente
 Escrita-escrita (write–write): duas (ou mais) operações de escrita simultâneas
 Solução: relaxar restrições de consistência
 Relaxar requisitos de atualizações usando operações atômicas, evitando 
sincronizações globais e gerando ganho de desempenho
 Preço: cópias podem não ser as mesmas em todos os lugares
 Grau de relaxamento da consistência depende dos padrões de acesso e 
atualizações dos dados replicados e do propósito a que os dados servem
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 7 Hélio Crestana Guardia - 2011
Modelos de consistência centrados em dados
Data-centric consistency
 Consistência é comumente discutida em termos de operações de leitura e escrita de 
dados compartilhados, acessíveis via memória (distribuída) compartilhada, base de 
dados (distribuída) compartilhada, ou sistema de arquivos compartilhados 
 Termo depósito de dados (data store) é comumente utilizado para indicar dados 
distribuídos em múltiplas máquinas
 Cada processo que pode acessar os dados do depósito possui cópia local (ou 
próxima) disponível
 Operações de escrita são propagadas para as outras cópias
 Operações são classificadas como escrita quando alteram os dados; nos demais 
casos, são consideradas de leitura
 Modelo de consistência é um contrato entre processos e o depósito de dados
 Processo que realiza leitura, normalmente, espera obter valor correspondente à 
última operação de escrita realizada
 Sem relógio global, é difícil definir precisamente qual operação de escrita é a última
 Diferentes modelos de consitência restringem os valores que uma operação de 
leitura de um item de dados pode retormar
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 8 Hélio Crestana Guardia - 2011
Depósito de dados distribuídos
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 9 Hélio Crestana Guardia - 2011
Consistência contínua
 Não existe solução claramente superior para replicação de dados
 Replicação de dados gera problemas de consistência não triviais
 Relaxamento da consistência favorece aumento de desempenho
 Grau de relaxamento depende das aplicações
 Diferentes formas podem ser usadas para especificar as inconsistências 
toleradas (grau de consistência) pelas aplicações:
 Desvios em valores numéricos entre réplicas: para aplicações em que os dados têm 
semântica numérica. Ex.: preço de ações, variando em valor absoluto ($0.02) ou relativo 
(0.5%). Dentro da faixa definida, réplicas são consideradas mutualmente consistentes.
 Desvios numéricos também podem ser considerados em função do número de atualizações 
ainda não aplicacas a réplica. Nesse caso,
desvio no valor indica o seu peso (weight).
 Desvio em idade entre as réplicas. Ex.: aplicação meteorológia aceita previsões de tempo 
com atualizações dentro de um período (algumas horas). Réplicas podem ser propagadas 
apenas uma vez a cada intervalo de tempo.
 Desvio em relação ao número e à ordenação das atualizações também pode ser tolerado.
 Valores formam faixas de consistência contínua
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 10 Hélio Crestana Guardia - 2011
Conit: consistency unit
 Yu e Vahdat propõem unidade de consistência (Consistency Unit – 
Conit), que especifica a unidade de dados sobre a qual consistência 
deve ser medida
Ex.:
 Conit contém variáveis x e y, sincronizadas em 0 nas réplicas A e B 
 Cada réplica mantém um Vector Clock VCi
 B envia operação [⟨5, B⟩: x := x + 2]; para A
 A realizou essa operação de forma permanente e não pode desfazê-la 
(roll back)
 A tem 3 operações pendentes <8,A>, <12,A> e <14,A>:
 Desvio de ordenação (order deviation) = 3
 A ainda não recebeu de B a operação [⟨10, B⟩: y := y + 5]: 
 Desvio numérico em relação ao número de operações = 1
 Peso (weight) = máxima diferença entre valores salvos de x e y 
em A e operações em B não vistas por A: y=5 (A(2,0); B(2,5))
 B tem 2 operações pendentes <5,B> e <10,B> e ainda não recebeu as 
operações de A.
– Ordering deviation de B = 2
– Numerical deviation de B é 3, com peso = 6 
(B: (x,y)=(0,0), A: (6,3)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 11 Hélio Crestana Guardia - 2011
Conit: consistency unit
 Deve haver um compromisso entre fine-grained e coarse-grained conits
 Se conit representa uma grande porção de dados, como uma BD, atualizações são 
agregadas para todos os dados no conit.
 Manter conit muito pequena não é boa estratégia, à medida que número de conits a 
gerenciar pode tornar-se muito grande
 Fragmentação das conits ajuda prevenir falso compartilhamento (false sharing), 
em que itens de dados são manipulados de forma independente mas, por estarem 
numa conit, desempenho e disponibilidade são afetados
 Na figura a seguir, suponha que réplicas podem diferir em no máximo 1 atualização:
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 12 Hélio Crestana Guardia - 2011
Conit: consistency unit
• Necessidade de protocolos e primitivas para especificar replicações e consistências
• Primitivas para especificação de consistência contínua devem ser simples
• Conit pode ser declarada junto com comando de atualização
Ex.:
AffectsConit(ConitQ, 1, 1);
Append message m to queue Q; // inclua msg m na fila Q
• Operações podem ser declaradas como dependentes de conits.
• Indica que a inserção de mensagem na fila Q pertence à conit ConitQ.
DependsOnConit(ConitQ, 4, 0, 60);
Read message m from head of queue Q; // leia msg m do início da fila Q
• DependsOnConit( ) indica que desvio numérico (numerical deviation), ordering 
deviation, e staleness devem ser limitados aos valores 4, 0 e 60, respectivamente
– Pode haver no máximo 4 operações não aplicadas às outras réplicas, não deve haver 
atualização provisória local (tentative local updates) e a idade da cópia local de Q não pode 
ser mais antiga que 60 segundos. 
– Middleware deve atualizar cópia de Q sempre que condições estabelecidas não são 
satisfeitas
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 13 Hélio Crestana Guardia - 2011
Ordenação consistente de operações
• Consistência sequencial e consistência causal ampliam modelo de 
consistência contínua, de forma que réplicas deverão estar de acordo sobre 
ordem (sequência) dos eventos quando for preciso efetivar atualizações 
provisórias nos dados replicados
• Depósito de dados é sequencialmente consistente quando satisfaz a seguinte 
condição:
– O resultado de qualquer execução é o mesmo que seria se as operações (de leitura 
e escrita) de todos os processos fossem executadas na mesma ordem sequencial, 
e as operações de cada processo individual aparecessem nesta sequência na 
ordem especificada por seu programa.
Comportamento de dois processos que operam sobre o 
mesmo item de dados. Eixo horizontal representa o tempo.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 14 Hélio Crestana Guardia - 2011
Consistência sequencial
• Todos os processos veem a mesma intercalação de operações
• Tempo de ocorrência não é relevante nesse caso
• Processos não precisam ver a cópia mais recente de um item de dados
• Processos veem as operações de escrita de todos os demais mas 
apenas suas próprias leituras
• Na figura 7.5, escrita de P2 parece ter ocorrido antes da de P1
• 7.5b viola a consistência sequencial pois nem todos os processos veem a mesma 
intercalação dos eventos
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 15 Hélio Crestana Guardia - 2011
Consistência sequencial
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 16 Hélio Crestana Guardia - 2011
Consistência sequencial
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 17 Hélio Crestana Guardia - 2011
Consistência causal
• Enfraquecimento da consistência sequencial, distinguindo eventos que são 
potencialmente relacionados por causalidade
• Se evento b é causado ou influenciado por evento a, causalidade requer que todos 
vejam primeiro a e depois b
• Escritas potencialmente relacionadas por causalidade devem ser vistas na mesma 
ordem por todos os processos
• Escritas concorrentes (de itens não relacionados) podem ser vistas em ordem 
diferente pelos processos
• Na figura 7.8, escritas W2(x)b e W1(x)c são concorrentes e não precisam ser vistas 
por todos os processos na mesma ordem
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 18 Hélio Crestana Guardia - 2011
Consistência causal
• Na figura 7.9, escrita W2(x)b provavelmente depende de W1(x)a, uma vez que b pode 
ser um resultado de cálculo envolvendo o valor lido por R2(x)a
• Escritas são relacionadas por causalidade e precisam ser vistas na mesma ordem por 
todos os processos
• 7.9 a está incorreta
• 7.9b está correta, já que leitura foi removida e eventos de escrita tornam-se 
concorrentes
• 7.9b não estaria correta com consistência sequencial
• Relógios vetoriais podem ser usados para determinar causalidade
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 19 Hélio Crestana Guardia - 2011
Operações de agrupamento
 Consistências sequencial e causal são definidas nas operações de leitura e escrita
 Em muitos programas, consistência é mantida em nível de granularidade mais alto, 
utilizando mecanismos de sincronização baseados em exclusão mútua e transações
 Operações de leitura e escrita são comumente encapsuladas em operações de 
regiões críticas: ENTER_CS e LEAVE_CS – Critical Section
 Ao executar com sucesso ENTER_CS, cópias dos dados estão atualizadas e 
processo pode realizar operações de leitura e escrita.
 Região crítica aumenta a granularidade das operações, provendo que sejam 
executadas de maneira atômica
 Primitivas para entrada e saída de região crítica podem ser definidas em termos de 
variáveis de sincronização (synchronization variables).
 Variáveis devem ser adquiridas (acquired) e liberadas (released) na entrada e na 
saída da seção crítica.
 Cada variável possui um dono corrente, que a adquiriu mais recentemente. 
Proprietário pode entrar e sair da seção crítica.
 Processo que deseja entrar na seção crítica deve enviar mensagem ao proprietário, 
solicitando
posse e valores correntes associados à variável de sincronização.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 20 Hélio Crestana Guardia - 2011
Operações de agrupamento
 Processos podem possuir variável de sincronização em modo não 
exclusivo, que permite várias leituras, mas nenhuma escrita
 Aspectos de operação das variáveis:
 Aquisição só pode ser efetivada quando todas as atualizações do atual dono 
sobre os dados compartilhados tenham sido efetivadas: dados estão atualizados
 Para que um acesso exclusivo seja concedido a uma variável de sincronização, 
nenhuma outra concessão pode estar ativa
 Depois de um acesso exclusivo, nenhum outro acesso não exclusivo à variável 
associada pode ser realizado antes de atualizações serem efetivadas pelo dono 
daquela variável
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 21 Hélio Crestana Guardia - 2011
Consistência de entrada
 Figura 7.10 mostra exemplo de consistência de entrada 
 Bloqueios são associados a cada item de dados
 Problema da consistência de entrada é a associação adequada dos dados com 
variáveis de sincronização
 Abordagem para implementação de consistência de entrada: avisar o 
middleware sobre quais dados serão acessados numa transação
 Em modelo orientado a objeto, uma variável de sincronização poderia ser 
associada a cada objeto declarado, serializando as suas invocações
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 22 Hélio Crestana Guardia - 2011
Consistência versus coerência
 Diversos processos podem realizar operações de leitura e de escrita sobre dados
 Modelo de coerência descreve o que se pode esperar em relação a um item de dado 
específico
 Dado pode ser replicado por vários locais
 Dado está coerente se suas várias cópias aderem ao modelo de coerência 
associado
 Modelo de consistência descreve o que se pode esperar quando múltiplos processos 
manipulam um conjunto de dados compartilhados concorrentemente
 Dados são considerados consistentes se aderem às regras descritas pelo modelo
 Coherence defines the behavior of reads and writes to the same memory location.
 A coherency protocol is a protocol which maintains the consistency between all the caches in a system of 
distributed shared memory.
 Coherence concerns only one memory location
 Consistency concerns apparent ordering for all locations
 A Memory System is Coherent if 
 can serialize all operations to that location such that, 
 operations performed by any processor appear in program order
 value returned by a read is value written by last store to that location
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 23 Hélio Crestana Guardia - 2011
Modelos de consistência centrados no cliente
Client-centric consistency models
 Modelos de consitência abordados proveem visão consistente do armazenamento 
dos dados
 Processos concorrentes podem realizar atualizações simultaneamente
 Acesso mutuamente exclusivo é provido sobre os dados
 Sistema mantém consistência sequencial
 Mecanismos de sincronização, como transações ou bloqueios, podem ser usados para 
prover consistência sequencial
 Em certos casos, contudo:
 Maioria das operações não envolve atualizações simultâneas ou estas podem ser 
realizadas de maneira simples
 Maioria dos acessos são apenas de leitura
 Nesses casos, consistência pode ser centrada no cliente
 Objetivo: evitar consistência global, focando nos dados desejados pelos clientes, ao 
invés de no que deve ser mantido pelos servidores
 Modelos: consistência eventual (eventual consistency), leitura monotônicas, escritas 
monotônicas, leia-suas-escritas (read your writes), writes follow reads
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 24 Hélio Crestana Guardia - 2011
Consistência eventual
 Operação concorrente de processos sobre dados e grau de consistência 
podem variar
Ex.:
 Bancos de Dados
 Acessos são predominantemente de leitura
 Nesses casos, é relevante saber quão rapidamente as atualizações devem ser 
disponibilizadas para os leitores
 DNS
 Apenas autoridade de um domínio pode realizar operações de escrita
 Não há concorrência na escrita, apenas conflitos de leitura-escrita
 Atualizações podem ocorrer de maneira lenta (lazy), em que dados são 
disponibilizados para leitura apenas um tempo depois da escrita
 WWW
 Atualizações praticamente só ocorrem pelo webmaster do domínio
 Navegadores e Proxies mantêm cópias locais das páginas acessadas
 Dados dos caches podem estar desatualizados
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 25 Hélio Crestana Guardia - 2011
Consistência eventual
 Aplicações citadas toleram graus relativamente altos de inconsistência
 Se atualizações não ocorrem por longos intervalos, cópias gradualmente 
tornam-se consistentes: consistência eventual
 Na ausência de atualizações, todas as réplicas convergem para cópias 
idênticas
 Atualizações devem obrigatoriamente propagar-se para todas as cópias
 Conflitos de escrita são relativamente fáceis de resolver, uma vez que 
apenas um pequeno grupo realiza atualizações
 Consistência eventual funciona bem se clientes sempre acessam a mesma 
réplica
 Problema associado a acesso de cliente móvel, que pode obter dados a partir 
de diferentes réplicas:
 Cliente realiza atualizações e muda ponto de acesso à rede
 Cliente se move e retoma acesso via outro ponto de acesso
 Atualizações podem não ter sido propagadas entre réplicas
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 26 Hélio Crestana Guardia - 2011
Consistência centrada no cliente
 Consitência centrada no cliente (client-centric): provê garantia para um único 
cliente, considerando a consistência dos dados que esse cliente armazenou
 Cliente acessa réplica local, ou a mais próxima
 Leituras e escritas são, então, 
realizadas nessa cópia
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 27 Hélio Crestana Guardia - 2011
Leituras monotônicas (monotonic reads)
 Modelo de consistência centrada no cliente (client-centric)
Condição:
Se um processo lê o valor de um item de dados x, qualquer operação de 
leitura subsequente de x por aquele processo irá sempre retornar 
aquele valor ou um mais recente
Ex.: E-mail distribuído:
 Cliente acessa lista de mensagens num local, sem remoção ou alteração
 Acesso posterior em outro local deverá prover a mesma visão da lista de 
mensagens
Notação:
 WS(xi[t]) is the set of write operations (at Li) that lead to version xi of x (at time t) 
 WS(xi[t1];xj[t2]) indicates that it is known that WS(xi[t1]) is part of WS(xj [t2])
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 28 Hélio Crestana Guardia - 2011
Leituras monotônicas
(a)
 Processo P lê dados de x em L1, obtendo x1, resultante de WS(x1) realizado em L1
 Posteriormente, P lê x em L2 – R(x2)
 Para garantir consistência de leituras monotônicas, todas as operações em WS(x1) 
devem ter sido propagadas para L2 antes da segunda operação de leitura
(b)
 Depois de ler x1 em L1, P lê R(x2) em L2
 Não há garantias que WS(x2) contém operações associadas a WS (x1)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 29 Hélio Crestana Guardia - 2011
Escritas monotônicas (monotonic writes)
 Operações de escrita devem ser propagadas na ordem correta para todas as 
cópias
Condição:
Uma operação de escrita por um processo em um item de dados x, é concluída 
antes de qualquer operação
de escrita subsequente de x pelo mesmo 
processo
 Concluir operação de escrita significa que cópia sobre a qual operação 
subsequente é realizada, pelo mesmo processo, reflete o efeito de alteração 
anterior, independentemente de onde essa operação foi feita
 Consistência provida assemelha-se a FIFO centrada em dados, de forma 
que, para o mesmo processo, ordem correta das operações é garantida
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 30 Hélio Crestana Guardia - 2011
Escritas monotônicas
(a)
 P realiza escrita em x na cópia local L1: W(x1)
 Posteriormente, P executa outra escrita em x, agora em L2: W(x2)
 Para garantir consistência de escrita monotônica, L1 deve ter sido propagada para 
L2: W(x1) em L2
(b)
 Consistência de escrita monotônica não é garantida; falta propagação de W(x1) para 
cópia em L2
 Não há garantia que cópia de x na qual segunda escrita está sendo realizada tem 
valor mais recente no tempo W(x1) 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 31 Hélio Crestana Guardia - 2011
Leia suas escritas (read your writes)
 Modelo de consistência centrado no cliente, relacionado com leituras 
monotônicas
Condição:
O efeito de uma operação de escrita por um processo no item de dados x 
sempre será visto por uma operação de leitura sucessiva em x pelo mesmo 
processo
 Operação de escrita é sempre concluída antes de uma operação de leitura 
sucessiva pelo mesmo processo, independente de onde essa operação de 
leitura ocorrerá
 Ex.: atualização de página Web por editor integrado ao navegador faz com 
que requisição posterior seja buscada do servidor ao invés de ser provida do 
cache desatualizado
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 32 Hélio Crestana Guardia - 2011
Leia suas escritas (read your writes)
(a) 
 Processo P realizou operação de escrita W(x1) e, mais tarde, uma operação de leitura 
em uma cópia local diferente.
Consistência “leia suas escritas” garante que efeitos da escrita podem ser vistos pela 
leitura subsequente: WS(x1; x2) declara que W(x1) é parte de WS(x2)
(b) 
 W(x1) foi deixada fora de WS(x2), o que significa que efeitos da operação de escrita 
de P não foram propagados para L2.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 33 Hélio Crestana Guardia - 2011
Escritas seguem leituras (writes follow reads)
 Último modelo de consistência centrado no cliente
 Atualizações são propagadas como resultado de operações de leitura 
precedentes
Condição:
Garante-se que uma operação de escrita por um processo em um item de dados 
x, em seguida a uma operacão de leitura em x pelo mesmo processo, ocorre 
sobre o mesmo valor ou sobre o valor mais recente de x que foi lido
 Modelo de consistência pode ser usado para garantir que usuários de um 
grupo de discussão em rede vejam o resultado de uma reação a um artigo 
somente depois de terem visto o artigo original
 Por exemplo, reações a artigo são armazenadas localmente somente se o 
artigo original também estiver ali
 Usuários que apenas leem artigos não precisam de modelo de consistência
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 34 Hélio Crestana Guardia - 2011
Escritas seguem leituras (writes follow reads)
(a)
 Processo lê x na cópia local L1
 Operações de escrita que levaram ao valor que acabou de ser lido também aparecem 
no conjunto de escrita em L2, onde o mesmo precesso realiza uma operação de 
escrita mais tarde
(b)
 Não há garantia de que operação em L2 é realizada sobre cópia consistente com a 
que acabou de ser lida em L1
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 35 Hélio Crestana Guardia - 2011
Gerenciamento de réplicas
Questões: 
 Como decidir onde, quando e por quem as réplicas devem ser 
posicionadas?
 Quais mecanismos usar para manter réplicas consistentes?
 Posicionamento:
 Localização de servidores de réplicas: achar as melhores localizações 
para hospedar depósito de dados
 Posicionamento de conteúdos: achar os melhores servidores para 
colocar um conteúdo
Duas questões de posicionamento nem sempre são tratadas separadamente
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 36 Hélio Crestana Guardia - 2011
Posicionamento de servidor de réplicas
 Posicionamento é normalmente tratado do ponto de vista mais gerencial e 
comercial do que como um problema de otimização
 Otimização: selecionar melhores K de N localizações (K<N)
 Solução ótima é complexa, normalmente tratada com alguma heurística
 Heurísticas:
 Distância (latência e largura de banda) entre clientes e localizações
 Seleção de um servidor por vez, minimizando distância média entre servidor e 
seus clientes
 Na Internet, posicionamento pode ser realizado ignorando a posição dos clientes 
e posicionando o servidor no nó com maior número de interfaces de rede, no 
maior sistema autônomo (autonomous system – AS). 
Algoritmo é repetido com o 2o maior AS e, assim, sucessivamente
 Problema: complexidade – O (N2) – torna as abordagens inadequadas, como no 
caso de flash crowds (multidões instantâneas) de acesso a site específico 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 37 Hélio Crestana Guardia - 2011
Posicionamento de servidor de réplicas
Heurísticas:
 Determinação de região para posicionamento de réplicas: conjunto de nós que 
acessam mesmo conteúdo, com baixa latência entre os nós. 
 Meta: selecionar regiões com maiores demandas e permitir que um nó nessa região 
sirva réplicas
 Nós estão posicionados em espaço geométrico m-dimensional
 Ideia é identificar K maiores clusters de nós e designar um nó de cada cluster para 
hospedar o conteúdo replicado
 Espaço total é particionado em células; K células mais densas são escolhidas para 
conter as réplicas
 Tamanho das células é relevante para prover bom balanceamento 
 Select best location out of N − K for which the average distance to clients is minimal. Then choose the next 
best server. (Note: The first chosen location minimizes the average distance to all clients.) 
Computationally expensive.
 Select the K-th largest autonomous system and place a server at the best-connected host: computationally 
expensive. 
 Position nodes in a d-dimensional geometric space, where distance reflects latency. Identify the K regions 
with highest density and place a server in every one: computationally cheap.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 38 Hélio Crestana Guardia - 2011
Posicionamento de servidor de réplicas
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 39 Hélio Crestana Guardia - 2011
Replicação e posicionamento de conteúdo
Replicação de conteúdo pode ocorrer segundo 3 organizações:
 Réplicas permanentes
 Réplicas iniciadas por servidor
 Réplicas iniciadas por clientes
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 40 Hélio Crestana Guardia - 2011
Replicação e posicionamento de conteúdo
Réplicas permanentes: conjunto inicial de réplicas que constituem depósito de 
dados distribuído
2 abordagens:
 Replicação de conteúdo em servidores presentes na mesma localização 
(cluster)
 Balanceamento de carga é comumente usado para distribuir as 
solicitações aos servidores locais
 Espelhamento: site é copiado para um número limitado de servidores 
geograficamente espalhados 
 Clientes escolhem um dos sites (ou são direcionados por consultas 
DNS)
A. S. Tanenbaum,
M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 41 Hélio Crestana Guardia - 2011
Replicação e posicionamento de conteúdo
Réplicas iniciadas por servidor
 Cópias criadas sob demanda pelo proprietário dos dados para aumento do 
desempenho
 Instalação de cópias temporárias nas regiões de onde as requisições estão sendo 
geradas
 Conjuntos de servidores estão espalhados na Internet, podendo receber cópias de 
dados para prestação de serviços Web próximos aos clientes (ex. Akamai)
 Replicação pode ocorrer para reduzir carga de um servidor
 Arquivos específicos de um servidor podem ser migrados ou replicados para 
servidores próximos aos clientes desses arquivos
 Cada servidor monitora contagens de acesso por arquivo e de onde vêm as 
requisições de acesso
 Para um dado cliente, servidor pode determinar qual servidor está mais próximo dele 
(usando BD de roteamento)
 Limiar de número de acessos determina se cópia deve ser removida de servidor ou se 
deve ser replicada em outro 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 42 Hélio Crestana Guardia - 2011
Réplicas iniciadas por servidor
 Keep track of access counts per file, aggregated by considering server closest to 
requesting clients 
 Number of accesses drops below threshold D ⇒ drop file 
 Number of accesses exceeds threshold R ⇒ replicate file 
 Number of access between D and R ⇒ migrate file
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 43 Hélio Crestana Guardia - 2011
Réplicas iniciadas por cliente
 Conhecidas como caches (de cliente)
 Recurso de armazenamento local usado para conter cópias temporárias dos dados 
requisitados
 Gerenciamento do cache cabe ao cliente e não ao depósito de dados
 Depósito de dados pode informar ao cliente quando dados no cache estão 
desatualizados
 Caches usados para melhorar tempo de acesso aos dados
 Dados são trazidos da cópia mais próxima, normalmente o cache local
 Esquema funciona bem quando dados não foram modificados
 Manutenção dos dados no cache ocorre por tempo limitado, para evitar que fiquem 
muito antigos ou para dar lugar a novos dados
 Cache hit ocorre quando dados solicitados podem ser providos do cache
 Caches podem ser compartilhados entre clientes para melhorar utilização
 Caches de clientes são posicionados diretamente em cada um deles ou em alguma 
máquina compartilhada entre clientes na rede local
 Caches podem também ser posicionados em pontos específicos de uma rede
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 44 Hélio Crestana Guardia - 2011
Distribuição de conteúdo
 Gerenciamento de réplicas também trata da propagação de conteúdo 
(atualizado)
 O que deve ser propagado?
 Somente notificações de atualização: protocolos de invalidação (usada 
para caches)
 Dados de uma cópia para outra (como no caso de BDs distribuídas)
 Operação de atualização para outras cópias (replicação ativa)
 Abordagem depende da largura de banda disponível e da relação 
leitura/escrita nas réplicas
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 45 Hélio Crestana Guardia - 2011
Estado versus operações
Protocolos de invalidação propagam notificação
• Outras cópias são informadas que atualização ocorreu e dados que elas 
contêm não são mais válidos
• Invalidação pode indicar partes alteradas, permitindo acesso às demais
• Nada é propagado além da notificação
• Quando uma operação é requisitada sobre cópia invalidada, atualização 
deve ocorrer antes, dependendo do modelo de consistência em uso
• Vantagem dos protocolos de invalidação: 
– Usam pouca largura de banda
– Envio apenas de indicação de quais dados estão inválidos
• Invalidações são adequadas quando há muitas atualizações em comparação 
com operações de leitura: razão leitura / escrita é pequena
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 46 Hélio Crestana Guardia - 2011
Estado versus operações
• Transferência dos dados modificados é adequada quando razão leitura / 
escrita é relativamente alta 
– Probabilidade de atualização ser efetiva é maior: dados modificados 
serão lidos antes de nova modificação
– Também é possível transferir apenas informações sobre as alterações 
ocorridas (diffs), para economizar capacidade de transmissão
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 47 Hélio Crestana Guardia - 2011
Estado versus operações: replicação ativa
 Atualizações também podem ocorrer enviando não dados modificados, mas 
informações sobre operações de atualização que devem ser realizadas: 
replicação ativa 
 Cada réplica, nesse caso, é representada por um processo capaz de manter 
ativamente atualizados os dados
 Replicação em geral requer envio de poucas informações, correspondentes 
aos parâmetros das operações a realizar
 Réplicas podem tem que apresentar maior capacidade de processamento
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 48 Hélio Crestana Guardia - 2011
Protocolos Pull e Push
• Atualizações podem ser buscadas (pulled) ou enviadas (pushed) 
Push-based, ou server-based approach (baseada no envio ou no 
servidor): atualizações são propagadas para outras réplicas sem que 
essas as tenham solicitado
• Comumente utilizadas entre réplicas permanentes e iniciadas por servidor
• Também podem ser usadas para enviar atualizações a caches de clientes
• Útil quando réplicas precisam grau de consistência elevado (idênticas)
• Réplicas permanentes e iniciadas por servidor costumam ser compartilhadas por 
múltiplos clientes, com acesso principalmente de leitura
• Razão leitura / atualização é alta: atualizações são úteis
• Questão: servidor precisa manter informações de estado (stateful) de todos os 
(caches) clientes
• Manutenção de informação de estado (stateful) tornam abordagem server push menos 
tolerante a falhas 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 49 Hélio Crestana Guardia - 2011
Protocolos Pull e Push
Pull-based ou client-based approach (baseada em recuperação ou no 
cliente)
 servidor ou cliente solicita que outro servidor lhe envie atualizações 
existentes
 Costumam ser usadas em caches de cliente
 Ao receber solicitações de dados que estão no cache local, clientes 
verificam com servidor se dados locais ainda estão atualizados
 Em caso de alterações, dados são primeiro trazidos para o cache antes de 
serem fornecidos à aplicação
 Abordagem é eficiente quando razão leitura / atualização é baixa
 Tempo de resposta é elevado em caso de cache miss 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 50 Hélio Crestana Guardia - 2011
Pull versus Push
• Possibilidade de sobrecarga de processamento e comunicação com o envio 
de notificações para manutenção dos estados
Abordagem híbrida para propagação de atualização: leases 
• Leases fazem com que servidor enviem (push) atualizações aos clientes 
apenas por período de tempo determinado
• Ao final do tempo, clientes passam a solicitar dados ou negociam novos 
leases (concessões)
• 3 tipos de leasing:
– Baseados em idade (age-based): atribuídos a itens de dados em função de suas 
últimas datas de atualização
• Dados não modificados por longo período tendem a permanecer inalterados
• Leases longos significam menor número de mensagens de atualização
– Baseado na frequência em que cliente solicita atualização de sua cópia em cache:
• Leases longos para clientes que solicitam pedidos de atualização frequentes
– Baseado na sobrecarga de espaço de estado
no servidor: diminuição da duração 
dos leases, gerando redução numérica à medida que expiram
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 51 Hélio Crestana Guardia - 2011
Protocolos Pull e Push
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 52 Hélio Crestana Guardia - 2011
Unicast versus multicast
• Trasmissão de atualizações pode ocorrer com unicast ou multicast 
• Unicast: replicação de mensagens
• Multicast: envio para múltiplos receptores (réplicas)
– Em redes locais, possibilidade de uso de broadcast 
– Eficiente no modelo de atualizações baseado no envio (push)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 53 Hélio Crestana Guardia - 2011
Protocolos de consistência
• Descrevem a implementação de modelos de consistência
– Consistência contínua
– Protocolos baseados em primário
– Protocolos de escrita replicada
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 54 Hélio Crestana Guardia - 2011
Protocolos de consistência contínua
• Limitação de desvio numérico, mantendo-o dentro de limites
• Escrita tem peso (weight) associado, que representa valor pelo qual x é 
atualizado: W(x) > 0
• Considere item de dados x e seja weight (peso) a mudança de seu valor depois de uma 
operação de escrita W
• ∀W: weight (W) > 0
• W é incialmente encaminhado para uma das N réplicas, chamada de origin (W)
• Cada servidor mantém registro das operações de escrita (Li) que realizou em sua 
cópia de x
• TW[i, j] são as escritas executadas pelo servidor Si, originadas de Sj:
TW [i, j] = ∑ { weight(W) | origin(W) = Sj & W ∈ Li } 
• TW[i,i] representa as escritas agregadas submetidas ao servidor Si
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 55 Hélio Crestana Guardia - 2011
Protocolos de consistência contínua
• Valor efetivo de x: v(t) x:
• Valor vi de x na réplica i:
• Problema: garantir que v (t) − vi < δi para todo servidor Si.
• Abordagem: todo servidor Sk mantém uma visão TWk [i, j] do que imagina ser o 
valor de TW [i, j]
• Visão pode ser propagada (gossiped) quando uma atualização é propagada
• Nota: 0 ≤ TWk [i, j] ≤ TW [i, j] ≤ TW [j, j]
• Solução: Sk envia operações de seus registros (logs) para Si quando percebe que TWk 
[i, k ] está se distanciando de TW [k , k], particularmente, quando TW [k, k] − TWk 
[i, k ] > δi /(N − 1)
• Nota: Staleness pode ser tratada de maneira análoga, essencialmente mantendo 
registro do que foi visto mais recentemente de Si.
v t =vinit∑
k=1
N
TW [k , k ]
vi=vinit∑
k=1
N
TW [i ,k ]
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 56 Hélio Crestana Guardia - 2011
Limitação de desvio de ordenação
• Desvio de ordenação em consistência são causados pelo fato de que servidor 
de réplicas aplica provisoriamente atualizações que lhe foram apresentadas
• Como consequência, cada servidor possui uma fila local de atualizações 
provisórias
• Ordem definitiva para aplicação das atualizações precisa ser definida 
quando tamanho da fila excede limite (ordering deviation)
• Nesse caso, servidor não mais aceita novos pedidos de escrita enquanto não 
efetivar (commit) atualizações pendentes 
• Efetivação depende de negociação com outros servidores de réplicas sobre a 
ordem para aplicação das atualizações
• Protocolos usuais para negociação da ordenação:
– Primary-based (baseados em primário)
– Quorum-based (baseados em quórum)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 57 Hélio Crestana Guardia - 2011
Primary-based protocols
• Aplicações distribuídas geralmente usam modelos de consistência simples 
para limitar desvios de idade (staleness) e de valor (numeric) 
• Consistência sequencial é comumente aplicada para prover a ordenação de 
operações, usando agrupamento e bloqueios, ou transações
• Protocolos baseados em primário (primary-based) são os mais utilizados
• Cada item de dado x no depósito de dados tem um (servidor) primário 
associado, que é responsável por coordenar as operações sobre x
• Primário pode ser fixo num servidor remoto, ou pode ser levado ao processo 
onde uma operação de escrita é iniciada
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 58 Hélio Crestana Guardia - 2011
Primary-based: remote-write protocols 
• Todas as operações de escrita devem ser encaminhadas a um servidor fixo
• Operações de leitura podem ser realizadas localmente
• Estratégia conhecida como primary-backup protocol 
• Processo que deseja relizar operação de escrita sobre x encaminha operação 
ao servidor primário de x
• Servidor primário realiza atualização sobre sua cópia de x e propaga a 
atualização para os servidores de backup 
• Cada servidor de backup realiza a atualização e envia notificação 
(acknowledgment) ao primário
• Quando todos os backups responderem, primário envia acknowledgment para 
o processo inicial
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 59 Hélio Crestana Guardia - 2011
Primary-based: remote-write protocols 
• Problema: possível baixo desempenho, devido à demora até que cliente que 
inciou a atualização possa prosseguir
– Atualização é realizada de maneira bloqueante
• Abordagem não bloqueante: servidor primário pode enviar ack ao cliente 
assim que tiver realizado a atualização local; backups são atualizados a 
seguir
– Aumento de desempenho ao custo de perda de tolerância a falhas
• Cada servidor primário pode ordenar escritas de forma global
• Todos os processos veem todas as operações de escrita na mesma ordem
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 60 Hélio Crestana Guardia - 2011
Primary-based: remote-write protocols 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 61 Hélio Crestana Guardia - 2011
Primary-based protocols
• Example primary-backup protocol: Traditionally applied in distributed 
databases and file systems that require a high degree of fault tolerance. 
• Replicas are often placed on same LAN.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 62 Hélio Crestana Guardia - 2011
Primary-based: local-write protocols 
 Variação do protocolo primary-based backup, cópia primária migra para o 
processo que deseja realizar uma operação de escrita
 Processo que deseja atualizar um item x, localiza a cópia primária de x e a 
move para sua localização
 Vantagem da abordagem: 
 Múltiplas operações de escrita sucessivas podem ser executadas localmente
 Processos leitores podem acessar suas cópias locais
 Requer uso de protocolo não bloqueante, seguido pelas atualizações propagadas 
para as cópias depois que primário conclui atualizações locais
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 63 Hélio Crestana Guardia - 2011
Primary-based: local-write protocols 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 64 Hélio Crestana Guardia - 2011
Primary-based: local-write protocols 
 Pode ser aplicado a computadores móveis que operam no modo 
desconectado 
 Antes da desconexão, computador móvel se torna primário para todos os itens 
de dado que deseja atualizar
 Enquanto desconectado, operações de atualização são aplicadas localmente
 Outros processos podem realizar leituras
 Posteriormente, ao ser reconectado, primário propaga atualizações aos backups, 
restaurando a consistência do sistema
 Usados em sistemas de arquivos distribuídos
em geral
 Servidor central fixo, que realiza todas as operações de escrita
 Servidor permite que réplicas realizem blocos de atualizações locais, 
visando ao aumento de desempenho
 Ao concluir atualizações, réplica as propaga ao servidor central, que as 
distribui aos demais servidores de réplica
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 65 Hélio Crestana Guardia - 2011
Protocolos de escrita replicada
 Diferentemente dos protocolos primary-based, protocolos com 
escrita replicada permitem que operações de escrita sejam realizadas 
em múltiplas réplicas 
 Abordagens:
 Replicação ativa
 Protocolos baseados em quórum
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 66 Hélio Crestana Guardia - 2011
Protocolos de escrita replicada
Replicação ativa
 Cada réplica tem um processo que realiza as atualizações
 Atualizações são propagadas na forma das operações de escrita a realizar
 Operações precisam ser realizadas na mesma ordem em todas as réplicas
 Necessário mecanismo de broadcast completamente ordenado
 Relógios lógicos de Lamport 
– Implementação não tem boa escalabilidade
 Ordenação total também pode ser obtida com coordenador central 
(sequencer)
– Abordagem: encaminhar operações ao sequenciador, que atribui número 
sequencial e a encaminha às réplicas
– Operações realizadas na ordem dos números sequenciais
– Operação se assemelha a protocolos de consistência baseados em primário
– Uso do sequencer não resolve problema da escalabilidade
– Combinação de relógios lógicos e sequencer pode ser empregada
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 67 Hélio Crestana Guardia - 2011
Protocolos de escrita replicada
Protocolos baseado em quórum
 Escritas replicadas tratadas por mecanismo de votação
 Clientes devem solicitar e adquirir permissões de múltiplos servidores 
(réplicas) antes de ler ou escrever item de dados replicado
 Ex.: Sistema de arquivos distribuído em que arquivo é replicado por N 
servidores
 Para atualizar um arquivo, cliente deve contactar ao menos metade do número 
de servidores mais um (maioria) e fazê-los concordar com atualização
 Obtida a maioria, arquivo pode ser alterado, recebendo um novo número de 
versão, que é o mesmo para todos os novos arquivos atualizados
 Para ler arquivo repliado, cliente também deve contactar ao menos metade mais 
um servidores e solicitar os números de versão associados ao arquivo. 
 Se todos os números são os mesmos, essa deve ser a versão atual do arquivo, já 
que escrita com outro valor iria falhar sem a maioria
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 68 Hélio Crestana Guardia - 2011
Protocolos de escrita replicada
Protocolos baseado em quórum
 Para ler arquivo que contém N réplicas, cliente deve reunir um quórum de leitura 
com NR servidores ou mais
 Para modificar arquivo, quórum de escrita é necessário com NW servidores
 Condições:
1. NR + NW > N : previne read-write conflicts
2. NW > N/2 : previne write-write conflicts 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 69 Hélio Crestana Guardia - 2011
Protocolos de escrita replicada
Protocolos baseado em quórum
a) OK
b) Possível conflito de escrita; NW <= N/2
c) Qualquer réplica pode ser usada para leitura, já que todas estão atualizadas
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 70 Hélio Crestana Guardia - 2011
Protocolos de coerência de cache
Cache coherence prototols
 Caches formam caso especial de replicação controlada por clientes
 Protocolos de coerência de cache semelhantes aos de consistência
 Implementações comumente apoiam-se em mecanismos de hardware para 
detecção de alteração (snooping) e para broadcast eficiente
 2 critérios são comumente usados para classificar os protocolos de cache:
 Estratégia de detecção de coerência (coherence detection strategy): quando 
inconsistências são efetivamente detectadas
− Em soluções estáticas, compilador é encarregado das análises e da detecção de quais 
dados podem levar a inconsistências por estarem em cache
− Soluções dinâmicas são comumente aplicadas em sistemas distribuídos, detectando 
inconsistências em tempo de execução (runtime), através da consulta de servidores
 Estratégia de imposição (enforcement) de coerência; determina como caches 
são mantidos consistentes com as cópias dos servidores
− Estratégia simples: não autorizar que dados compartilhados sejam mantidos no cache
− Dados compartilhados mantidos em servidores, que usam protocolos primary-based 
ou replication-write
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 71 Hélio Crestana Guardia - 2011
Protocolos de coerência de cache
 Quando dados compartilhados são mantidos em cache, há 2 abordagens para 
impor a coerência:
 Fazer servidor enviar invalidações para todos os caches quado há modificações
 Propagar as atualizações
 Outro aspecto relevante: o que fazer quando cliente altera dados no cache?
 Para caches somente de leitura, operações de escrita são realizadas apenas pelos 
servidores, que propagam atualizações
 Protocolo de distribuição garante que atualizações são propagadas aos caches
 Abordagem pull-based é comumente usada
 Também é possível que clientes alterem dados diretamente no cache e 
propaguem atualizações para servidores
 Estratégia comum em write-through caches 
 Usada em sistemas de arquivos distribuídos, em abordagem semelhante a primary-based 
ou local-write protocol, em que cliente se transforma em primário temporário
 Cliente deve receber permiss˜so exclusiva de escrita para evitar conflitos write-write
 Oferecem bom desempenho já que todas as operações podem ser feitas localmente
 Propagações de atualizações podem ser postergadas, permitindo diversas escritas antes de 
informar aos servidores: estratégia conhecida como write-back 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 72 Hélio Crestana Guardia - 2011
Resumo
 Replicação realizada para aumentar a confiabilidade de um SD e para aumento de 
desempenho
 Replicação introduz problema de consistência
 Consistência das réplicas requer propagação de atualizações de forma que 
inconsistências temporárias não são percebidas
 Relaxamento da consistência é necessário para evitar perdas de desempenho
 Diferentes modelos de consistência existem
 Para consistência contínua, limita-se o desvio entre as réplicas
 Ordenação consistente das operações é usada nos modelos de consistência
 Consistência sequencial faz com que todos os processos vejam as operações de 
escrita na mesma ordem
 Na consistência causal, operações potencialmente dependentes são vistas na ordem 
dessa dependência
 Modelos de consistência centrados no cliente consideram que clientes conectam-se a 
diferentes réplicas, atualizadas no momento do acesso
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos – Cap 7: Consistência e Replicação / 73 Hélio Crestana Guardia - 2011
Resumo
 Diferentes estratégias podem ser empregadas para propagação de atualizações
 Aspectos:
 O que é propagado: notificações, operações ou estados
 Para quem atualizações são divulgadas; e
 Quem inicia as atualizações
 Decisão sobre quais réplicas atualizar e quando é tratada pelo protocolo de 
distribuição
 Atualizações podem ser propagadas (pushed) pelos servidores ou solicitadas (pulled) 
pelos clientes
 Protocolos de consistência descrevem implementações de modelos de consistência
 Para consistência sequencial, primary-based protocols usam servidores para 
controlar
e propagar atualizações e replicated-write propagam atualizações para 
diversas cópias ao mesmo tempo. A ordenação das operações é complexa nesse caso.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73