Sistemas Distribuídos - Cap (7,8 e 9)

Prévia do material em texto

7
CONSISTÊNCIA E REPLICAÇÃO
Uma questão importante em sistemas distribuídos é a replicação de dados. Os dados geralmente são replicados para 
aumentar a confiabilidade ou melhorar o desempenho. Um dos principais problemas é manter as réplicas consistentes. 
Informalmente, isso significa que quando uma cópia é atualizada, precisamos garantir que as outras cópias também 
sejam atualizadas; caso contrário, as réplicas deixarão de ser as mesmas. Neste capítulo, examinaremos mais de perto 
o que realmente significa consistência de dados replicados e as diferentes maneiras de obter essa consistência.
Começamos com uma introdução geral que explica por que a replicação é útil e como ela se relaciona com a 
escalabilidade. Em seguida, continuamos com o que realmente significa consistência. Uma classe importante do que 
conhecemos como modelos de consistência pressupõe que vários processos acessem dados compartilhados 
simultaneamente. Nessas situações, a consistência pode ser formulada em relação ao que os processos podem esperar ao 
ler e atualizar os dados compartilhados, sabendo que outros processos estão acessando esses dados também.
Modelos de consistência para dados compartilhados geralmente são difíceis de implementar em sistemas 
distribuídos de grande escala. Além disso, em muitos casos é possível usar modelos mais simples, mas também mais 
fáceis de implementar. Uma classe específica é composta de modelos de consistência centrados no cliente, que se 
concentram na consistência da perspectiva de um único cliente (possivelmente móvel). Em uma seção separada, 
explicaremos os modelos de consistência centrados no cliente.
A consistência é apenas metade da história. Devemos também considerar como ele é implementado. Existem 
basicamente duas questões, mais ou menos independentes, que devemos ter
273
274 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
presente. Em primeiro lugar, começaremos nos concentrando no gerenciamento de espelho, que leva em consideração não 
apenas a localização dos servidores espelho, mas também como o conteúdo é distribuído para esses servidores.
O segundo problema é como as réplicas permanecem consistentes. Na maioria dos casos, os aplicativos 
exigem uma forma forte de consistência. Informalmente, isso significa que as atualizações se espalharão mais ou 
menos imediatamente entre as réplicas. Existem várias alternativas para implementar consistência forte, que 
explicaremos em uma seção separada. Também veremos protocolos de cache, que constituem um caso especial de 
protocolos de consistência.
7.1 INTRODUÇÃO
Nesta seção, começamos explicando os motivos importantes para desejar a replicação de dados. Nós nos 
concentramos na replicação como uma técnica útil para alcançar escalabilidade e entender por que raciocinar 
sobre consistência é tão importante.
7.1.1 Razões para replicação
Existem dois motivos principais para replicar dados: confiabilidade e desempenho. Primeiro, os dados são replicados para 
aumentar a confiabilidade de um sistema. Se um sistema de arquivos foi replicado, é possível continuar trabalhando depois 
que uma réplica falhar, simplesmente alternando para uma das outras réplicas. Além disso, manter várias cópias torna 
possível fornecer melhor proteção contra dados corrompidos. Por exemplo, suponha que haja três cópias de um arquivo e 
cada operação de leitura e gravação seja executada em cada cópia. Podemos nos proteger contra uma operação de 
gravação defeituosa, se considerarmos que o valor retornado por pelo menos duas cópias está correto.
O outro motivo para replicar dados é o desempenho. A replicação é importante para o desempenho quando o sistema 
distribuído precisa ser dimensionado em números e área geográfica. Por exemplo, a escala em números ocorre quando um 
número crescente de processos precisa acessar dados que são gerenciados por um único servidor. Nesse caso, o 
desempenho pode ser melhorado replicando o servidor e subsequentemente dividindo o trabalho.
O dimensionamento em relação ao tamanho de uma área geográfica também pode exigir replicação. A ideia básica é 
que, ao colocar uma cópia dos dados bem próxima ao processo que os usa, o tempo de acesso aos dados diminui. 
Conseqüentemente, o desempenho percebido desse processo aumenta. Este exemplo também mostra que pode ser difícil 
avaliar os benefícios de desempenho da replicação. Embora um processo do cliente possa perceber um melhor 
desempenho, também pode ser o caso de que mais largura de banda da rede seja consumida para manter todas as 
réplicas atualizadas.
SEÇÃO 7.1 INTRODUÇÃO 275
Se a replicação ajudar a melhorar a confiabilidade e o desempenho, quem será contra ela? Infelizmente, há um 
preço a pagar quando os dados são replicados. O problema com a replicação é que ter muitas cópias pode causar 
problemas de consistência. Sempre que uma cópia é modificada, ela se torna diferente das outras cópias. Portanto, 
para garantir a consistência, modificações devem ser feitas em todas as cópias. O preço da replicação é determinado 
exatamente por quando e como essas modificações devem ser feitas.
Para entender o problema, considere melhorar os tempos de acesso à página da web. Se nenhuma medida especial for 
tomada, às vezes a solicitação de uma página de um servidor da Web remoto pode levar vários segundos. Para melhorar o 
desempenho, os navegadores da web armazenam uma cópia de uma página solicitada anteriormente localmente (ou seja, eles 
procuram uma página da Web). Se um usuário exigir essa página novamente, o navegador retornará automaticamente a 
cópia local. O tempo de acesso percebido pelo usuário é excelente. No entanto, se o usuário sempre deseja a versão mais 
recente de uma página, ele pode estar sem sorte. O problema é que se a página foi modificada nesse ínterim, as 
modificações não serão propagadas para as cópias em cache, o que tornará essas cópias desatualizadas.
Uma solução para o problema de devolver uma cópia antiga ao usuário é, primeiro, proibir o navegador de 
manter cópias locais e deixar que o servidor cuide totalmente da replicação. No entanto, essa solução pode causar 
tempos de acesso ruins se uma réplica não for colocada perto do usuário. Outra solução é deixar o servidor da web 
invalidar ou atualizar cada cópia em cache, mas isso requer que o servidor controle todos os caches e envie 
mensagens para eles. Isso, por sua vez, pode degradar todo o desempenho do servidor. Voltaremos aos problemas 
de desempenho mais tarde versus escalabilidade.
7.1.2 Replicação como uma técnica de escalonamento
A replicação e o armazenamento em cache para desempenho são amplamente usados como técnicas de dimensionamento. 
Os problemas de escalabilidade geralmente aparecem na forma de problemas de desempenho. Colocar cópias de dados perto 
dos processos que os utilizam pode melhorar o desempenho, reduzindo o tempo de acesso, resolvendo problemas de 
escalabilidade.
Uma compensação necessária é que manter as cópias atualizadas requer uma largura de banda de rede 
maior. Considere um processo P que acessa um espelho local N vezes por segundo, enquanto a réplica é atualizada 
M vezes por segundo. Suponha que uma atualização atualize completamente a versão anterior do espelho local. 
sim N << M, ou seja, a velocidade de acesso à atualização é muito baixa, situação ocorre em que o processo P Ele 
nunca acessa muitas versões atualizadas do espelho local, o que torna a comunicação de rede inútil para essas 
versões. Neste caso, pode ter sido melhor não instalar um espelho local próximo P, ou aplique uma estratégia 
diferente para atualizar a réplica. Voltaremos a essas questões mais tarde.
No entanto, um problema ainda mais sério é que manter várias cópias consistentes pode, por si só, estar 
sujeito a sérios problemas de escalabilidade. Por intuição, uma coleção de
276 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
cópias é consistente quando as cópias são sempre as mesmas. Isso significa que uma operação de leiturarealizada em 
qualquer cópia sempre retornará o mesmo resultado. Conseqüentemente, quando uma operação de atualização é executada 
em uma cópia, a atualização deve ser propagada para todas as cópias antes que uma operação subsequente ocorra, 
independentemente de em qual cópia a operação foi iniciada ou executada.
Este tipo de consistência é às vezes informalmente (e imprecisamente) chamado de consistência hermética, como 
no caso da chamada replicação síncrona. (Na próxima seção, daremos definições precisas de consistência e 
apresentaremos uma variedade de modelos de consistência.) A ideia principal é que uma atualização seja realizada em 
todas as cópias como uma única operação atômica ou transação. Infelizmente, a implementação de atomicidade 
envolvendo um grande número de réplicas, que podem ser amplamente dispersas em uma rede de grande escala, é 
inerentemente difícil quando as operações precisam ser concluídas rapidamente.
As dificuldades surgem do fato de que precisamos sincronizar todas as réplicas. Em essência, isso significa que 
todos os espelhos precisam primeiro concordar exatamente quando uma atualização local ocorrerá. Por exemplo, as 
réplicas podem precisar decidir uma ordem global de operações, usando carimbos de data / hora Lamport ou deixar que 
um coordenador atribua o pedido. A sincronização global simplesmente requer muito tempo de comunicação, 
especialmente quando as réplicas estão espalhadas por uma rede de longa distância.
Agora enfrentamos um dilema. Por um lado, os problemas de escalabilidade podem ser reduzidos aplicando 
replicação e armazenamento em cache, o que resulta em melhor desempenho. Por outro lado, manter todas as cópias 
consistentes geralmente requer sincronização global e isso é inerentemente caro em termos de desempenho. A cura pode 
ser pior do que a doença.
Em muitos casos, a única solução real é reduzir as restrições de consistência. Em outras palavras, se pudermos 
relaxar o requisito de que as atualizações precisam ser executadas como operações atômicas, talvez possamos evitar 
sincronizações globais (instantâneos) e talvez também aumentar o desempenho. O preço a pagar é que as cópias 
podem não ser as mesmas em todos os lugares. Obviamente, até que ponto relaxar a consistência depende muito dos 
padrões de acesso e atualização dos dados replicados, bem como da finalidade de usar esses dados.
Nas seções a seguir, primeiro consideramos uma variedade de modelos de consistência e fornecemos 
definições precisas do que realmente significa consistência. Em seguida, continuamos com uma explicação das 
diferentes maneiras de implementar esses modelos, por meio do que é conhecido como protocolos de distribuição e 
consistência. Diferentes métodos para classificar consistência e replicação podem ser encontrados em Gray et al. 
(1996) e em Wiesmann et al. (2000).
7.2 MODELOS DE CONSISTÊNCIA CENTRADOS EM 
DADOS
Tradicionalmente, a consistência é explicada no contexto de operações de leitura e gravação em dados compartilhados, 
disponíveis por meio da memória compartilhada (distribuída), um banco de dados compartilhado (distribuído) ou um 
sistema de arquivos (distribuído). Nesta seção, usamos
SEÇÃO 7.2 MODELOS DE CONSISTÊNCIA CENTRADOS EM DADOS 277
Usamos o termo mais amplo chamado Armazem de dados. Um data warehouse pode ser fisicamente distribuído em várias 
máquinas. Em particular, presume-se que qualquer processo que possa acessar os dados do warehouse tenha uma cópia 
local (ou próxima) disponível de todo o warehouse. As operações de gravação se propagam para as outras cópias, conforme 
mostrado na Figura 7-1. Uma operação de dados é classificada como uma operação de gravação quando altera os dados, 
caso contrário, é classificada como uma operação de leitura.
Processo
Processo Processo
Cópia local
Armazém de dados distribuído
Figura 7-1. Organização geral de um data warehouse lógico, fisicamente distribuído e replicado 
por meio de múltiplos processos.
UMA modelo de consistência é basicamente um contrato entre os processos e o data warehouse. Este contrato diz 
que se os processos concordarem em obedecer a certas regras, o warehouse promete funcionar corretamente. Em geral, 
um processo que executa uma operação de leitura em um item de dados espera que a operação retorne um valor que 
mostra os resultados da última operação de gravação nos dados.
Na ausência de um relógio global, é difícil definir precisamente qual é a última operação de gravação. Como 
alternativa, precisamos fornecer outras definições, o que nos leva a uma variedade de modelos de consistência. Cada 
modelo restringe efetivamente os valores que uma operação de leitura pode retornar em um item de dados. Como 
você pode esperar, os modelos com mais restrições são mais fáceis de usar, por exemplo, ao desenvolver aplicativos, 
enquanto aqueles com menos restrições são mais difíceis. A desvantagem é, claro, que os modelos fáceis de usar não 
têm um desempenho tão bom quanto os mais difíceis. Assim é a vida.
7.2.1 Consistência contínua
Pelo que explicamos até agora, deve ficar claro que não há nada que possa ser considerado a melhor solução para 
replicar dados. A replicação de dados tem problemas de consistência que não podem ser resolvidos com eficiência de 
uma maneira geral. Somente se relaxarmos a consistência, podemos esperar encontrar soluções eficientes. Infelizmente, 
também não existem regras gerais para afrouxar a consistência: exatamente o que pode ser tolerado depende, em 
grande parte, das aplicações.
278 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
Existem diferentes maneiras de os aplicativos especificarem as inconsistências que podem tolerar. Yu e Vahdat 
(2002) consideram um método geral para diferenciar três eixos independentes para definir inconsistências: desvio nos 
valores numéricos entre as réplicas, desvio na deterioração entre as réplicas e desvio no que diz respeito à ordem das 
operações de atualização. Yu e Vahdat referem-se a esses desvios como intervalos de consistência contínua.
A medição da inconsistência em termos de desvios numéricos pode ser usada em aplicativos para os 
quais os dados têm semântica numérica. Um exemplo óbvio é a replicação de registros contendo preços de 
ações. Nesse caso, um aplicativo pode especificar que duas cópias não devem desviar mais de $ 0,02, o que 
seria um desvio numérico absoluto. Alternativamente, um desvio numérico relativo, que afirma que duas cópias 
não devem diferir mais do que, digamos, 0,5%. Em ambos os casos, veríamos que se um estoque subir (e uma 
das réplicas for atualizada imediatamente) sem violar os desvios numéricos especificados, as réplicas ainda 
serão consideradas mutuamente consistentes.
O desvio numérico também pode ser entendido em termos do número de atualizações que foram aplicadas a uma 
determinada réplica, mas ainda não foram vistas por outras réplicas. Por exemplo, um cache da web pode não ter visto 
um lote de operações realizadas por um servidor da web. Neste caso, o desvio associado ao valor também conhecido 
como su pesagem.
Desvios antigos estão relacionados à última vez em que uma réplica foi atualizada. Para alguns aplicativos, é 
tolerável que um espelho forneça dados antigos, desde que não seja
também velho. Por exemplo, os relatórios meteorológicos costumam permanecer razoavelmente precisos por algum 
tempo, digamos algumas horas. Nesses casos, um servidor primário pode receber atualizações oportunas, mas decidir 
propagar as atualizações para as réplicas de tempos em tempos.
Por último, existem classes de aplicativos em que a ordem das atualizações pode ser diferente em várias 
réplicas, desde que as diferenças sejam limitadas. Uma maneira de visualizar essas atualizações é aplicá-las 
provisoriamente a uma cópia local, dependendo do acordo global de todas as réplicas. Consequentemente, algumas 
atualizações precisarão ser repetidas e aplicadas em uma ordem diferente antes de se tornarem permanentes.Por 
intuição, a ordenação dos desvios é muito mais difícil de entender do que as outras duas métricas de consistência. 
Posteriormente, forneceremos exemplos que esclarecerão as coisas.
A ideia de um conito
Para definir inconsistências, Yu e Vahdat apresentaram uma unidade de consistência, abreviada como
conit. Um conit especifica a unidade pela qual a consistência será medida. Assim, em nosso exemplo de bolsa de valores, um 
conito poderia ser definido como um registro que representa uma única ação. Outro exemplo é um boletim meteorológico 
individual.
Para dar um exemplo de um conito e, ao mesmo tempo, ilustrar os desvios numéricos e de ordenação, considere 
as duas réplicas mostradas na Figura 7-2. Cada réplica Eu mantém um
relógio vetorial bidimensional, VC Eu, como os relógios descritos no Capítulo 6. Usamos a notação t, eu para expressar uma 
operação que foi realizada pela réplica Eu no (seu) tempo lógico t.
SEÇÃO 7.2 MODELOS DE CONSISTÊNCIA CENTRADOS EM DADOS 279
Réplica A
Conit
x = 6; y = 3
Réplica B
Conit
x = 2; y = 5
Operação Resultado Operação Resultado
<5, B> x: = x + 2 <8, A> 
y: = y + 2 <12, A> y: = y 
+ 1 <14, A> x: = y * 2
[x = 2]
[y = 2]
[y = 3]
[X = 6]
<5, B> X: = X + 2 <10, 
B> y: = y + 5
[x = 2]
[y = 5]
Vector Clock A
Desvio da ordem = 3 Desvio 
numérico = (1, 5)
= (15, 5) Vector Clock B
Desvio da ordem = 2 Desvio 
numérico = (3, 6)
= (0, 11)
Figura 7-2. Exemplo de como rastrear desvios de consistência [adaptado de (Yu e Vahdat, 
2002)].
Neste exemplo, vemos duas réplicas que operam em um conit que contém os elementos de dados x Y Y. Assumimos 
que ambas as variáveis foram inicializadas com 0. A replicação A recebeu a operação
5, B: x ← x + 2
da réplica B, e o tornou permanente (ou seja, a operação foi confirmada em PARA e não pode ser desfeito). A réplica PARA tem 
três operações de atualização provisória: 8, PARA, 12, PARA, e 14, PARA,
o que leva ao seu desvio de ordem para 3. Observe também que, devido à última operação, o relógio vetorial 
de 14, A, A torna-se (15,5).
A única operação de B o que PARA ainda não viu é 10, B, levando seu desvio numérico a 1 em relação às operações. 
Neste exemplo, o peso deste desvio pode ser expresso como a diferença máxima entre os valores (confirmados) de x Y Y no 
PARA, e o resultado das operações em B não visto por PARA. O valor confirmado em PARA isto é ( x, y) = ( 2.0), 
enquanto a operação em B, não visto por PARA, joga uma diferença de y = 5. Raciocínio semelhante mostra que B tem 
duas operações de atualização provisória: 5, B
e 10, B, o que significa que ele tem um tipo de desvio de 2. Porque B você ainda não viu uma única operação de 
PARA, seu relógio vetorial torna-se (0,11). O desvio numérico é 3 com um peso total de 6. Este último valor 
vem do fato de que o valor confirmado de B
isto é ( x, y) = ( 0,0), enquanto as operações provisórias em PARA eles já vão levar 6 em x.
Observe que há compensações entre manter os conitos de granulação fina e os conitos de granulação grossa. Se 
um conit representar muitos dados, como um banco de dados inteiro, as atualizações se aplicam a todos os dados 
contidos no conit. Conseqüentemente, isso pode fazer com que as réplicas entrem em um estado de inconsistência mais 
rapidamente. Por exemplo, suponha
280 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
que na Figura 7-3 duas réplicas podem diferir em não mais do que uma atualização pendente. Nesse caso, quando 
cada um dos itens de dados na Figura 7-3 (a) tiver sido atualizado uma vez na primeira réplica, a segunda réplica 
também precisará ser atualizada. Este não é o caso quando um conito menor é escolhido, como mostra a Figura 7-3 
(b). Lá, as réplicas ainda são consideradas atualizadas. Em particular, este problema é importante quando os 
elementos de dados contidos em um conit são usados de forma completamente independente, caso em que diz
o que compartilhar falsamente o conit.
Conit Elemento de dados
Melhoria
Propagação
de
atualizações
Melhoria
Adiamento
da
propagação do
atualizações
Melhoria Melhoria
Réplica 1 Réplica 2 Réplica 1 Réplica 2
(para) (b)
Figura 7-3. Escolher a granularidade certa para um conito. (a) Duas atualizações levam à 
disseminação de atualizações. (b) Nenhuma atualização é necessária (ainda).
Infelizmente, implementar conits muito pequenos não é uma boa ideia, pelo simples motivo de que o número total de conits 
que precisam ser tratados também aumenta. Em outras palavras, existe uma sobrecarga relacionada ao tratamento de conitos que 
deve ser levada em consideração. Essa sobrecarga, por sua vez, pode afetar adversamente todo o desempenho, o que deve ser 
levado em consideração.
Embora de um ponto de vista conceitual os conits constituam um meio atraente de capturar os requisitos de 
consistência, há dois pontos importantes que devemos abordar antes de colocá-los em prática. Primeiro, para reforçar 
a consistência, precisamos de protocolos. Explicaremos esses protocolos posteriormente neste capítulo.
Um segundo ponto é que os desenvolvedores de programas devem especificar os requisitos de consistência 
necessários para seus aplicativos. A prática indica que a obtenção de tais requisitos pode ser extremamente difícil. 
Normalmente, os programadores não estão acostumados a lidar com replicação, deixando de fora o que significa 
fornecer informações detalhadas sobre consistência. Portanto, é muito importante que existam interfaces de 
programação simples e fáceis de entender.
A consistência contínua pode ser implementada como um conjunto de ferramentas que aparece para os 
desenvolvedores apenas como outra biblioteca para vincular a seus aplicativos. Um conit é simplesmente declarado 
próximo a uma atualização de item de dados. Por exemplo, o trecho de pseudo-código
AffectConit (ConitQ, 1, 1);
adicione a mensagem m à fila Q;
SEÇÃO 7.2 MODELOS DE CONSISTÊNCIA CENTRADOS EM DADOS 281
definido para adicionar uma mensagem à fila Q pertence a um conit denominado "ConitQ". Além disso, as operações 
agora podem ser declaradas dependentes de conits:
DependsOnTheConit (ConitQ, 4, 0, 60);
lê a mensagem m do chefe da fila Q;
Neste caso, a chamada para DependsOfLaConit () especifica que o desvio numérico, o desvio de classificação e o desvio 
antigo devem ser limitados aos valores 4, 0 e 60 (segundos), respectivamente. Isso pode ser interpretado como que deve 
haver no máximo 4 operações de atualização não vistas em outras réplicas, que não deve haver nenhuma tentativa de 
atualização local e que a idade da cópia local de Q ele deve ter sido verificado há não mais de 60 segundos. Se esses 
requisitos não forem satisfeitos, o middleware subjacente tentará transportar a cópia local do Q a um estado tal que a 
operação de leitura possa ser realizada.
7.2.2 Ordenação consistente de operações
Além da consistência contínua, desde a última década, tem havido um grande corpo de trabalho dedicado a modelos de 
consistência centrados em dados. Uma classe importante de modelos vem do campo da programação simultânea. 
Diante do fato de que na computação paralela e distribuída, vários processos precisarão compartilhar recursos e 
acessá-los simultaneamente, os pesquisadores têm buscado expressar a semântica do acesso concorrente quando 
recursos compartilhados são replicados. Isso levou a pelo menos um modelo de consistência importante que é 
amplamente usado. Agora vamos nos concentrar no que é conhecido como consistência sequencial e também 
explicaremos uma variante mais fraca, chamada consistência causal.
Os modelos que discutimos nesta seção lidam com operações de ordenação consistentes em dados 
compartilhados e replicados. Em princípio, os modelos superam aqueles de consistência contínua no sentido de que, 
quando for necessário comprometer atualizações nas réplicas, eles terão que concordar em uma ordem global dessas 
atualizações. Em outras palavras, eles precisam concordar em uma ordenação consistente dessas atualizações.Os 
modelos de consistência que explicaremos a seguir tratam de como obter classificações consistentes.
Consistência sequencial
A seguir, usaremos uma notação especial na qual traçaremos as operações de um processo ao longo de um eixo de 
tempo. O eixo do tempo é sempre desenhado horizontalmente, aumentando da esquerda para a direita. Os símbolos
W Eu ( para Y R Eu ( x) b
significa que o processo foi escrito respectivamente P Eu sobre o elemento de
dados x com o valor para e uma leitura desse elemento por P Eu devolvendo b. Assumimos que cada item de dados é 
inicialmente NADA. Quando não há confusão sobre qual processo é
acessar os dados, omitimos o subscrito dos símbolos W Y R.
282 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
Q1:
P2:
W (x) a
R (x) NIL R (x) a
Figura 7-4. Comportamento de dois processos operando no mesmo elemento de dados. O 
eixo horizontal representa o tempo.
Como exemplo, na Figura 7-4 P 1 executa uma gravação no elemento de dados x, modificando seu valor para para. Observe 
que, em princípio, esta operação, W 1 ( para, é feito primeiro em uma cópia do armazenamento de dados que é local para P 1, e 
então se espalha para outras cópias locais. Em nosso exemplo, P 2 leia o valor mais tarde NADA, e algum tempo depois li para ( de 
sua cópia local
do armazém). O que vemos aqui é que leva algum tempo para propagar a atualização do x em direção a P 2,
o que é perfeitamente aceitável.
o consistência sequencial é um importante modelo de consistência centrado em dados, que foi definido pela 
primeira vez por Lamport (1979) no contexto de memória compartilhada para sistemas multiprocessadores. Em geral, 
um armazenamento de dados é sequencialmente consistente quando satisfaz a seguinte condição:
O resultado de qualquer execução é o mesmo como se as operações (leitura e gravação) de todos os processos 
realizados no armazenamento de dados fossem executados em alguma ordem sequencial e as operações de cada 
processo individual aparecessem nessa sequência na ordem especificada por seu programa.
O que esta definição significa é que quando os processos estão sendo executados simultaneamente em (talvez) máquinas 
diferentes, qualquer interpolação válida de operações de leitura e gravação é um comportamento aceitável, mas todos os 
processos veem a mesma interpolação de operações.
Observe que nada é dito sobre o tempo; ou seja, não há referência à operação de gravação "mais recente" no item de 
dados. Observe que, neste contexto, um processo "vê" gravações de todos os processos, mas vê apenas suas 
próprias leituras.
Esse tempo não desempenha um papel importante, pode ser visto na Figura 7-5. Vamos considerar quatro
processos operando no mesmo elemento de dados x. Na Figura 7-5 (a), o processo P 1 primeiro desempenho W (x) a para x. Depois 
(em tempo absoluto), o processo P 2 também executa uma operação de gravação, definindo o valor de x para b. No entanto, os 
processos P 3 Y P 4 Primeiro eles lêem o valor b, e então o valor para. Em outras palavras, a operação de gravação do processo P 2 Parece 
ser
aconteceu antes de P 1
Em contraste, a Figura 7-5 (b) viola a consistência sequencial, uma vez que nem todos os processos veem
a mesma interpolação de operações de gravação. Em particular, para o processo P 3, parece
se o elemento de dados foi alterado primeiro para b, e então para para. Por outro lado, P 4 concluir que o valor final é b.
Para especificar ainda mais a ideia de consistência sequencial, vamos considerar os três processos, P 1, P 2,
Y P 3, na execução simultânea, mostrado na Figura 7-6 (Dubois et al., 1988). Os itens de dados neste exemplo são 
constituídos por três variáveis inteiras x, y, Y z, e eles são salvos
em um armazenamento de dados compartilhado sequencialmente consistente (possivelmente distribuído).
SEÇÃO 7.2 MODELOS DE CONSISTÊNCIA CENTRADOS EM DADOS 283
P1: W (x) a
P2:
Q3:
Q4:
P1: W (x) a
P2:
Q3:
Q4:
W (x) b
W (x) b
R (x) b R (x) a
R (x) b R (x) a
R (x) b R (x) a
R (x) a R (x) b
(para) (b)
Figura 7-5. ( a) Armazenamento de dados sequencialmente consistente. (b) Armazenamento de dados que não 
são sequencialmente consistentes.
Processo 1 Processo 2 Processo 3
x ← 1;
imprimir (y, z)
Y ← 1;
imprimir (x, z)
z ← 1;
imprimir (x, y)
Figura 7-6. Três processos em execução simultaneamente.
Assumimos que cada variável é inicializada com 0. Neste exemplo, uma atribuição corresponde a uma operação de 
gravação, enquanto uma instrução de impressão corresponde a uma operação de leitura simultânea de seus dois 
argumentos. Assumimos que todas as instruções são indivisíveis.
Várias sequências de execução interpoladas são possíveis. Com seis instruções independentes, existem 
potencialmente 720 (6!) Sequências de execução possíveis, embora algumas violem a ordem do programa. Vamos 
considerar as 120 (5!) Sequências que começam com x ← 1. Metade tem imprimir (x, z) antes que Y ← 1 e viola a ordem do 
programa. Metade também tem imprimir (x, y) antes que z ← 1, e também violam a ordem do programa. Apenas um quarto das 
120 sequências, ou
30, são válidos. Outras 30 sequências válidas são possíveis começando com Y ← 1 e mais 30 podem começar com z ← 1, 
para um total de 90 sequências de execução válidas. Quatro deles aparecem na Figura 7-7.
Na Figura 7-7 (a), os três processos estão em ordem de execução, primeiro P 1, então P 2, e des-
bem P 3 - Os outros três exemplos mostram interpolações diferentes, mas igualmente válidas, das instruções no 
tempo. Cada um dos três processos imprime duas variáveis. Devido a que
os únicos valores que cada variável pode assumir são o valor inicial (0) ou o valor atribuído (1), cada processo produz 
uma string de 2 bits. Números depois Impressões eles são as saídas reais que aparecem no dispositivo de saída.
Se concatenarmos a saída de P 1, P 2, Y P 3 Nessa ordem, obtemos uma string de 6 bits que caracteriza uma determinada 
interpolação de instruções. Esta string é aquela listada como Empresa no
Figura 7-7. Posteriormente caracterizaremos cada pedido por meio de sua assinatura, ao invés de sua impressão.
Nem todos os 64 padrões de assinatura são permitidos. Como um exemplo trivial, 000000 não é permitido, pois 
significaria que as instruções de impressão executam antes das instruções de atribuição, o que viola o requisito de que 
as instruções sejam executadas na ordem do programa. Um exemplo mais sutil é 001001. Os primeiros dois bits, 00, 
significam que Y Y z eles eram 0
284 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
x ← 1;
imprimir (y, z);
Y ← 1;
imprimir (x, z);
z ← 1;
imprimir (x, y)
x ← 1;
Y ← 1;
imprimir (x, z);
imprimir (y, z);
z ← 1;
imprimir (x, y)
Y ← 1;
z ← 1;
imprimir (x, y);
imprimir (x, z);
x ← 1;
imprimir (y, z)
Y ← 1;
x ← 1;
z ← 1;
imprimir (x, z);
imprimir (y, z);
imprimir (x, y);
Empresa:
Impressões: 001011
001011 Empresa:
Impressões: 101011
101011 Empresa:
Impressões: 110101
010111 Empresa:
Impressões: 111111
111111
(para) (b) (c) (d)
Figura 7-7. Quatro sequências válidas de execução para os processos da Figura 7-6. O eixo 
vertical representa o tempo.
quando P 1 deixou sua impressão. Esta situação só ocorre quando P 1 execute ambas as instruções antes de começarem 
P 2 ou P 3 - Os próximos dois bits, 10, significam que P 2 deve ser executado depois P 1 começou, mas antes P 3 começou. 
Os últimos dois bits, 01, significam que
P 3 deve ser completado antes P 1 começar, mas já vimos isso P 1 deve ir primeiro. Portanto, 001001 não é permitido.
Em resumo, as 90 ordens válidas diferentes produzem uma variedade de resultados de programa diferentes 
(embora menos de 64) que são permitidos sob a suposição de consistência sequencial. O contrato entre os processos 
e o data warehouse compartilhado e distribuído é que o processo deve aceitar todos esses resultados como válidos. 
Em outras palavras, os processos devem aceitar os quatro resultados mostrados na Figura 7-7 e todos os outros 
resultados válidos comorespostas apropriadas e devem funcionar corretamente se algum deles ocorrer. Um programa 
que funciona com alguns desses resultados e outros não viola o contrato do data warehouse e está incorreto.
Consistência causal
O tipo de consistência causal Hutto e Ahamad, 1990) representa uma fraqueza da consistência sequencial, uma vez que 
diferencia entre eventos que são potencialmente relacionados por causalidade e aqueles que não o são. No capítulo 
anterior, quando explicamos os registros de tempo vetorial, já tratamos da causalidade. Se o evento b é causado ou 
influenciado por um evento anterior para, causalidade requer que todos os outros eventos olhem primeiro para para, e então 
para b.
Considere uma interação simples usando um banco de dados distribuído compartilhado. Suponha
que o processo P 1 escrever um item de dados x. Depois de P 2 ler para x e escreve Y. Aqui, lendo x e a escrita de Y estão 
potencialmente relacionados por causalidade, uma vez que o cálculo de Y
pode ter dependido do valor de x quando P 2 leia-o (isto é, o valor escrito por P 1).
SEÇÃO 7.2 MODELOS DE CONSISTÊNCIA CENTRADOS EM DADOS 285
Por outro lado, se dois processos escrevem espontânea e simultaneamente dois itens de dados diferentes, eles não 
estão causalmente relacionados. Operações que não são causalmente relacionadas são consideradas concorrente.
Para que um data warehouse seja considerado causalmente consistente, ele deve obedecer à seguinte 
condição:
Os escritos que estão potencialmente relacionados por causalidade devem ser vistos por todos os processos na 
mesma ordem. As gravações simultâneas podem ser visualizadas em uma ordem diferente em máquinas diferentes.
Como exemplo de consistência causal, considere a Figura 7-8. Aqui temos uma sequência de eventos que é permitida com 
um armazenamento causalmente consistente, mas é proibida com um armazenamento sequencialmente consistente ou com 
um armazenamento estritamente consistente. Ponto a
nota é que as escrituras W 2 ( x) b Y W 1 ( x) c eles são simultâneos, portanto, não é necessário que todos os processos os vejam na 
mesma ordem.
P1: W (x) a
P2:
Q3:
Q4:
W (x) c
R (x) a W (x) b
R (x) a
R (x) a
R (x) c
R (x) b
R (x) b
R (x) c
Figura 7-8. Essa sequência é permitida com um armazenamento causalmente consistente, mas não com 
um armazenamento sequencialmente consistente.
Agora vamos considerar um segundo exemplo. Na Figura 7-9 (a), temos W 2 ( x) b potencialmente dependente de W 1 ( para, 
já que b pode ser o resultado de um cálculo envolvendo o valor lido
por R 2 ( para. Os dois escritos estão causalmente relacionados, portanto, todos os processos devem vê-los na mesma ordem. 
Portanto, a Figura 7-9 (a) está incorreta. Por outro lado, na Figura 7-9 (b)
a leitura foi removida, então W 1 ( para Y W 2 ( x) b eles agora são gravações simultâneas. Um armazenamento causalmente 
consistente não requer gravações simultâneas ordenadas globalmente, então
que a Figura 7-9 (b) está correta. Observe que a Figura 7-9 (b) reflete uma situação que não seria aceitável para um warehouse 
sequencialmente consistente.
P1: W (x) a
P2:
Q3:
Q4:
P1: W (x) a
P2:
Q3:
Q4:
R (x) a W (x) b
W (x) b
R (x) b R (x) a
R (x) a R (x) b
R (x) b R (x) a
R (x) a R (x) b
(para) (b)
Figura 7-9. ( a) Violação de um warehouse causalmente consistente. (b) Sequência correta de eventos em 
um armazenamento causalmente consistente.
A implementação de consistência causal requer o rastreamento de quais processos viram quais gravações. Com efeito, 
isso significa que um gráfico da dependência deve ser construído e mantido
286 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
qual operação depende de quais outras operações. Uma maneira de fazer isso é usando um registrador vetorial de tempo, 
conforme explicamos no capítulo anterior. Posteriormente neste capítulo, retornaremos ao uso de registros de tempo vetorial 
para capturar a causalidade.
Operações de agrupamento
A consistência sequencial e causal são definidas no nível das operações de leitura e gravação. Esse nível de granularidade se 
deve a razões históricas: esses modelos foram inicialmente desenvolvidos para sistemas multiprocessadores de memória 
compartilhada e, na verdade, foram implementados no nível do hardware.
A granularidade fina desses modelos de consistência não coincide em muitos casos com a granularidade fornecida 
pelos aplicativos. O que vemos é que a concorrência entre programas que compartilham dados geralmente é mantida sob 
controle por meio de mecanismos de sincronização para exclusão mútua e transações. Na verdade, acontece que no nível 
do programa, as operações de leitura e gravação são colocadas entre colchetes por meio do par de operações ENTER_CS Y
DEIXE CS, Onde " CS ”Significa seção crítica. Como explicamos no Capítulo 6, a sincronização entre os 
processos é realizada por essas duas operações. Em termos de nosso data warehouse distribuído, isso 
significa que um processo que foi executado com sucesso
ENTER_CS você terá certeza de que os dados em seu warehouse local estão atualizados. Nesse ponto, o processo 
pode executar com segurança uma série de operações de leitura e gravação nesse armazenamento e, em seguida, 
terminar chamando DEIXE CS.
Em essência, acontece que dentro de um programa, os dados tratados por meio de uma série de operações de 
leitura e escrita são protegidos contra acessos simultâneos que causariam uma visão diferente do resultado da 
execução da série como um todo. Dito de outra forma, os colchetes convertem a série de operações de leitura e 
gravação em uma unidade executada atomicamente, aumentando assim o nível de granularidade.
Para chegar a este ponto, precisamos de uma semântica precisa das operações ENTER_CS Y
DEIXE CS. Essa semântica pode ser formulada em termos de variáveis de sincronização compartilhado. Existem 
diferentes maneiras de usar essas variáveis. Veremos um método geral no qual cada variável possui alguns dados 
associados, que podem ser adicionados ao conjunto total de dados compartilhados. Adotamos a convenção de que quando 
um processo entra em sua seção crítica, ele deve adquirir variáveis de tempo importantes; Da mesma forma, quando você 
sair da seção crítica, você deve libertar essas variáveis. Observe que os dados incluídos na seção crítica do processo 
podem ser associados a diferentes variáveis de sincronização.
Cada variável de sincronização tem um proprietário atual, ou seja, o último processo que a adquiriu. O 
proprietário pode entrar e sair repetidamente de seções críticas sem ter que enviar nenhuma mensagem na rede. 
Um processo que atualmente não possui uma variável de sincronização, mas deseja adquiri-la, deve enviar uma 
mensagem ao proprietário atual solicitando sua propriedade e os valores atuais dos dados associados a essa 
variável de sincronização. Também é possível que vários processos tenham simultaneamente uma variável de 
sincronização de forma não exclusiva, o que significa que podem ler, mas não escrever, os dados associados.
SEÇÃO 7.2 MODELOS DE CONSISTÊNCIA CENTRADOS EM DADOS 287
Agora precisamos que os seguintes critérios sejam atendidos (Bershad et al., 1993):
1 Acesso para adquirir uma variável de sincronização em relação a um não-processo
é permitido até que todas as atualizações nos dados compartilhados referentes a esse processo 
sejam feitas.
2 Antes que um processo seja permitido um modo exclusivo de acesso a uma variável
sync, nenhum outro processo pode ter a variável sync, nem mesmo no modo não exclusivo.
3 - Depois de um acesso de modo exclusivo ter sido feito a uma variável em
sincronização, nenhum outro acesso não exclusivo de outro processo àquela variável de 
sincronização pode ser feito, até que tenha sido feito em relação ao dono daquela variável.
A primeira condição afirma que quando um processo faz uma aquisição, a aquisição não pode ser concluída (ou seja, 
retornar o controle para a próxima instrução) até que todos osdados compartilhados salvos tenham sido atualizados. Em 
outras palavras, em uma aquisição, todas as alterações remotas nos dados salvos devem ser tornadas visíveis.
A segunda condição afirma que antes de atualizar um item de dados compartilhados, um processo deve entrar em 
sua seção crítica em modo exclusivo para garantir que nenhum outro processo está tentando atualizar os dados 
compartilhados ao mesmo tempo.
A terceira condição afirma que se um processo deseja entrar em uma região crítica não exclusivamente, ele deve 
primeiro verificar com o proprietário da variável de sincronização que armazena a região crítica para encontrar as cópias 
mais recentes dos dados salvos compartilhados.
A Figura 7-10 mostra um exemplo do que é conhecido como consistência de entrada. Em vez de operar em todos 
os dados compartilhados, neste exemplo, associamos cadeados a cada
elemento de dados. Neste caso, P 1 faz uma aquisição para x, mudança x uma vez, após o qual ele também faz uma 
aquisição para Y. O processo P 2 faz uma aquisição para x mas não para
Y, então vai ler o valor para para x, mas pode ler NADA para Y. Porque o processo P 3 primeiro faça uma aquisição para Y, vai 
ler o valor b quando Y ser lançado por P 1
P1: Acq (Lx) W (x) a Acq (Ly) W (y) b Rel (Lx) Rel (Ly) P2: 
Acq (Lx) R (x) a
Q3: Acq (Ly) R (y) b
R (y) NIL
Figura 7-10. Sequência de eventos válida para consistência de entrada.
Um dos problemas de programação com consistência de entrada é associar dados adequadamente a variáveis 
de sincronização. Um método direto é informar explicitamente ao middleware quais dados acessar, como geralmente 
é feito ao declarar quais tabelas de banco de dados serão afetadas por uma transação. Em um método baseado em 
objeto, podemos associar
288 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
implicitamente, uma variável de sincronização exclusiva com cada objeto declarado, serializando assim com eficácia 
todas as invocações para tais objetos.
Consistência versus coerência
Neste ponto, é útil esclarecer a diferença entre dois conceitos intimamente relacionados. Os modelos que explicamos 
até agora lidam com o fato de que vários processos executam operações de leitura e gravação em um conjunto de 
elementos de dados. UMA modelo de consistência
descreve o que esperar em relação a esse conjunto quando vários processos operam simultaneamente nesses 
dados. Então, o conjunto é considerado consistente se aderir às regras descritas pelo modelo.
Embora a consistência lide com um conjunto de elementos de dados, o modelos de coerência descrever o que 
pode ser esperado de um único item de dados (Cantin et al., 2005). Nesse caso, assumimos que um item de dados é 
replicado em vários lugares; diz-se que é consistente quando as várias cópias aderem às regras definidas pelo seu 
modelo de consistência associado. Um modelo popular é a consistência sequencial, mas agora aplicado a um único 
item de dados. Na verdade, isso significa que, no caso de gravações simultâneas, todos os processos, em algum 
ponto, verão a mesma ordem de atualizações ocorrendo.
7.3 MODELOS DE CONSISTÊNCIA CENTRADOS NO 
CLIENTE
Os modelos de consistência que descrevemos na seção anterior ajudam a fornecer uma visão consistente em todo o sistema 
de um data warehouse. Uma suposição importante é que os processos simultâneos podem atualizar simultaneamente o 
armazenamento de dados e que é necessário fornecer consistência diante de tal simultaneidade. Por exemplo, no caso de 
consistência de entrada baseada em objeto, o armazenamento de dados garante que, quando um objeto é chamado, o 
processo de chamada é fornecido com uma cópia do objeto que reflete todas as alterações feitas no objeto até agora, 
provavelmente por outros processos. Durante a chamada, também é garantido que nenhum outro processo pode interferir; ou 
seja, você recebe acesso mútuo exclusivo ao processo de chamada.
Ser capaz de lidar com operações simultâneas em dados compartilhados, mantendo a consistência 
sequencial, é crítico para sistemas distribuídos. Por motivos de desempenho, a consistência sequencial pode 
provavelmente ser garantida apenas quando os processos usam mecanismos de sincronização, como transações 
ou bloqueios.
Nesta seção, veremos uma classe especial de armazenamentos de dados distribuídos. Os armazenamentos de dados 
que consideramos são caracterizados pela falta de atualizações simultâneas ou, quando essas atualizações ocorrem, podem 
ser facilmente resolvidos. A maioria das operações envolve a leitura de dados. Esses armazenamentos de dados oferecem um 
modelo de consistência muito fraco, denominado consistência momentânea. Ao introduzir modelos especiais de consistência 
centrada no cliente, torna-se aparente que muitas inconsistências podem ser ocultadas de uma maneira relativamente barata.
SEÇÃO 7.3 MODELOS DE CONSISTÊNCIA CENTRADOS NO CLIENTE 289
7.3.1 Consistência momentânea
A extensão em que os processos realmente operam simultaneamente e em que extensão a consistência precisa ser 
garantida pode variar. Existem muitos exemplos em que a simultaneidade aparece apenas de forma restritiva. Por 
exemplo, em muitos sistemas de banco de dados, a maioria dos processos quase nunca executa operações de 
atualização; eles leem principalmente dados do banco de dados. Apenas um ou poucos processos executam 
operações de atualização. Portanto, a questão é quão rápidas atualizações devem estar disponíveis para processos 
somente leitura.
Como outro exemplo, considere um sistema de nomenclatura global como o DNS. O namespace DNS é dividido 
em domínios, onde cada domínio é atribuído a uma autoridade de mapeamento que atua como proprietária desse 
domínio. Apenas essa autoridade tem permissão para atualizar sua parte do namespace. Consequentemente, os 
conflitos entre duas operações que desejam realizar uma atualização nos mesmos dados (ou seja, conflitos de 
escrita-escrita) eles nunca acontecem. A única situação que precisa ser tratada é a conflitos de leitura e gravação, em 
que um processo deseja atualizar um elemento de dados enquanto outro tenta, simultaneamente, ler esse elemento. 
Como resultado, geralmente é aceitável propagar uma atualização lentamente, o que significa que um processo de 
leitura verá uma atualização apenas algum tempo após a atualização ocorrer.
Outro exemplo é a World Wide Web. Em quase todos os casos, as páginas da web são atualizadas por uma única 
autoridade, como um webmaster ou o proprietário real da página. Normalmente, não há conflitos de gravação para resolver. 
Por outro lado, para melhorar a eficiência, os navegadores e proxies da web são frequentemente configurados para manter as 
páginas pesquisadas em um cache local e retorná-las na próxima solicitação.
Um aspecto importante de ambos os tipos de cache da web é que ambos podem retornar páginas da web desatualizadas. Em 
outras palavras, a página armazenada em cache que é retornada ao cliente solicitante é uma versão antiga, em comparação com a 
disponível no servidor da web real. Como resultado, muitos usuários consideram essa inconsistência aceitável (até certo ponto).
Esses exemplos podem ser considerados como casos de bancos de dados replicados e distribuídos (em grande escala) que 
toleram um grau relativamente alto de inconsistência. Eles têm em comum que, se as atualizações não ocorrerem por um longo 
tempo, todas as réplicas se tornarão gradualmente inconsistentes. Esta forma de consistência é conhecida como consistência 
momentânea.
Armazenamentos de dados que são momentaneamente consistentes têm a propriedade de que, na ausência de 
atualizações, todas as réplicas convergem em cópias idênticas umas das outras. Em essência, a consistência momentânea 
requer apenas a garantia de que as atualizações sejam propagadas para todas as réplicas. Os conflitos de 
gravação-gravação são geralmente fáceis de resolver quando se presume que apenas um pequeno grupo de processos 
pode realizar atualizações.A implementação de consistência momentânea é, portanto, barata.
Armazenamentos de dados consistentes funcionam bem momentaneamente, desde que os clientes sempre acessem a 
mesma réplica. No entanto, surgem problemas quando diferentes réplicas são acessadas em um curto período de tempo. Isso 
é mais bem ilustrado considerando um usuário móvel acessando um banco de dados distribuído, conforme mostrado na Figura 
7-11.
290 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
O cliente se muda para outro local 
e se conecta (de forma 
transparente)
com outra réplica
As réplicas precisam
manter uma consistência
centrado no cliente
Rede de longa distância
Operações de leitura e gravação
Banco de dados replicado e distribuído
Notebook
Figura 7-11. O princípio relativo ao acesso de um usuário móvel a diferentes réplicas de um banco 
de dados distribuído.
O usuário móvel acessa o banco de dados conectando-se de forma transparente a uma das réplicas. Em 
outras palavras, o aplicativo em execução no laptop do cliente não percebe em qual espelho está realmente 
operando. Suponha que o usuário execute várias operações de atualização e saia novamente. Posteriormente, 
você acessa o banco de dados novamente, provavelmente após mudar para um local diferente ou usar um 
dispositivo de acesso diferente. Nesse ponto, o usuário pode ser conectado a uma réplica diferente da anterior, 
conforme ilustrado na Figura 7-11. No entanto, se as atualizações feitas anteriormente ainda não foram 
propagadas, o usuário notará um comportamento inconsistente. Em particular, esperamos ver todas as 
mudanças feitas antes,
Este exemplo é típico de armazenamentos de dados momentaneamente consistentes e é causado pelo fato de que os 
usuários às vezes podem operar em réplicas diferentes. O problema pode ser aliviado com a introdução do consistência 
centrada no cliente. Em essência, a consistência centrada no cliente fornece garantias para um único cliente em relação à 
consistência do acesso ao armazenamento de dados desse cliente. Nenhuma garantia é fornecida com relação a acessos 
simultâneos por diferentes clientes.
Modelos de consistência centrados no cliente originaram-se do trabalho em Bayou [por exemplo, ver Terry et al. 
(1994) e Terry et al. (1998)]. Bayou é um sistema de banco de dados desenvolvido para computação móvel, onde se 
assume que a conectividade de rede não é confiável e que está sujeita a vários problemas de desempenho. As redes 
sem fio e aquelas que abrangem grandes áreas, como a Internet, se enquadram nesta categoria.
SEÇÃO 7.3 MODELOS DE CONSISTÊNCIA CENTRADOS NO CLIENTE 291
Bayou distingue essencialmente quatro tipos diferentes de modelos de consistência. Para explicar esses modelos, 
vamos considerar novamente um data warehouse fisicamente distribuído em várias máquinas. Quando um processo 
acessa o armazenamento de dados, ele geralmente se conecta à cópia local (ou mais próxima) disponível, embora em 
princípio qualquer cópia seria adequada. Todas as operações de leitura e gravação são executadas nessa cópia local. As 
atualizações são propagadas, em algum ponto, para as outras cópias. Para manter as coisas simples, assumimos que os 
itens de dados têm um proprietário associado, que é o único processo que tem permissão para modificar esse item. Desta 
forma, evitamos conflitos de escrita-escrita.
Modelos de consistência centrados no cliente são descritos pela seguinte nota-
ção. Estar x Eu [ t] quem denota a versão do elemento de dados x em cópia local eu Eu ao tempo t. A versão x Eu [ t] é o resultado de 
uma série de operações de gravação em eu Eu que ocorre desde a inicialização. Denotamos este conjunto como WS (x Eu [ t]). Se 
as operações em WS (x Eu [ t 1]) também se
feito na cópia local eu j Mais tarde t 2, nós escrevemos WS (x Eu [ t 1]; x j [ t 2]). Se a ordem das operações ou 
sincronização for algo claro no contexto, omitiremos
o índice de tempo.
7.3.2 Leituras monotônicas
O primeiro modelo de consistência centrado no cliente é o de leituras monotônicas. Diz-se que um data warehouse 
fornece consistência de leitura monotônica se a seguinte condição for atendida:
Se um processo lê o valor de um item de dados x, qualquer operação de leitura sucessiva em x fazer esse 
processo sempre retornará o mesmo valor ou um valor mais recente.
Em outras palavras, a consistência de leitura monotônica garante que se um processo viu um valor de x ao tempo t, você 
nunca verá uma versão mais antiga de x Mais tarde.
Como um exemplo de onde as leituras monotônicas são úteis, considere um banco de dados de e-mail 
distribuído. Nesse banco de dados, a caixa de correio eletrônica de cada usuário pode ser distribuída e 
replicada em várias máquinas. O correio pode ser inserido em uma caixa de e-mail em qualquer local. No 
entanto, as atualizações se espalham lentamente (ou seja, sob demanda). Somente quando uma cópia precisa 
de certos dados para consistência, esses dados são propagados para essa cópia. Suponha que um usuário leia 
seu e-mail em San Francisco. Suponha que apenas a leitura de e-mails não afete a caixa de correio, ou seja, as 
mensagens não são excluídas, armazenadas em subdiretórios ou mesmo marcadas como lidas etc. Quando o 
usuário voa para Nova York e reabre sua caixa de correio,
Usando uma notação semelhante à que usamos para modelos de consistência centrados em dados, a consistência 
de leitura monotônica pode ser representada graficamente como mostrado na Figura 7-12. Ao longo do eixo vertical, duas 
cópias locais diferentes do warehouse aparecem.
dados, eu 1 Y eu 2 O tempo aparece ao longo do eixo horizontal, como antes. Em todos os casos, nós
292 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
estamos interessados em operações realizadas por um único processo, P. Essas operações específicas aparecem em negrito e são 
conectadas por uma linha pontilhada que representa a ordem em que você as executa. P.
L1: WS (x 1)
L2: WS (x 1 ;; x 2)
R (x 1) L1: WS (x 1)
L2: WS (x 2)
R (x 1)
R (x 2) R (x 2)
(para) (b)
Figura 7-12. Leia as operações realizadas por um único processo, P, em duas cópias diferentes do 
mesmo armazenamento de dados. (a) Armazenamento de dados com consistência de leitura monotônica. 
(b) Armazenamento de dados que não fornece leituras monotônicas.
Na Figura 7-12 (a), o processo P primeiro execute uma operação de leitura em x no eu 1, e retorna o valor de x 1 ( nesse 
tempo). Este valor resulta de operações de gravação em WS (x 1)
criado em eu 1 Depois de, P executa uma operação de leitura em x no eu 2, mostrado como R (x 2).
Para garantir a consistência de leitura monotônica, todas as operações em WS (x 1) deve ter se espalhado para eu 2 antes 
que a segunda operação de leitura ocorra. Em outras palavras,
precisamos saber com certeza que WS (x 1) Faz parte de WS (x 2), que é expresso como WS (x 1; x 2).
Em contraste, a Figura 7-12 (b) mostra uma situação em que a consistência não é garantida.
leitura monotônica. Após o processo P ler x 1 no eu 1, realizar a operação R (x 2) no eu 2
No entanto, apenas escrever operações em WS (x 2) foram feitos em eu 2 Não há garantia de que este conjunto 
também incluirá todas as operações contidas em WS (x 1).
7.3.3 Escritas monotônicas
Em muitas situações, é importante que as operações de gravação se propaguem na ordem correta para todas as cópias do 
armazenamento de dados. Esta propriedade é expressa em consistência de escrita monotônica. Em um armazém com consistência 
de escrita monotônica, a seguinte condição for atendida:
Uma operação de gravação feita por um processo em um elemento x é concluída antes de qualquer 
outra operação de gravação sucessiva em x feito pelo mesmo processo.
Assim, completar uma operação de gravação significa que a cópia na qual uma operação sucessiva é realizada reflete o 
efeito de uma operação de gravação anterior realizada pelo mesmo processo, independentemente de onde essa operação foi 
iniciada. Em outras palavras, uma operação degravação em uma cópia do elemento x realizada apenas se essa cópia tiver 
sido atualizada por quaisquer operações de gravação anteriores, o que pode ter ocorrido em outras cópias de x. Se 
necessário, a nova escritura deve aguardar o término de outras escrituras anteriores.
SEÇÃO 7.3 MODELOS DE CONSISTÊNCIA CENTRADOS NO CLIENTE 293
Observe que a consistência de gravação monotônica se assemelha à consistência FIFO centrada em dados. O 
básico da consistência FIFO é que as operações de gravação do mesmo processo são realizadas na ordem correta em 
qualquer lugar. Essa restrição de ordenação também se aplica a gravações monotônicas, com a exceção de que agora 
consideramos apenas a consistência para um único processo, em vez de uma coleção de processos simultâneos.
Atualize uma cópia de x não é necessário quando cada operação de gravação sobrescreve completamente o 
valor atual de x. No entanto, as operações de gravação geralmente são executadas em apenas parte do estado de 
um item de dados. Por exemplo, vamos considerar uma biblioteca de software. Em muitos casos, a atualização de 
uma biblioteca desse tipo é feita com a substituição de uma ou mais funções, o que leva a uma próxima versão. Com 
a consistência de gravação monotônica, são fornecidas garantias de que, se uma atualização for feita em uma cópia 
da biblioteca, todas as atualizações anteriores serão feitas primeiro. A biblioteca resultante se tornará a versão mais 
recente e incluirá todas as atualizações que levaram a versões anteriores da biblioteca.
A Figura 7-13 mostra a consistência da escrita monotônica. Na subseção (a) da referida figura,
o processo P executa uma operação de gravação em x em cópia local eu 1, e é apresentado como a operação W (x 1). Depois de, 
P executa outra operação de gravação em x, mas desta vez em eu 2, e mostra como W (x 2). Para garantir a consistência da 
gravação monotônica, é necessário que as operações de gravação anteriores realizadas em eu 1 se espalharam para eu 2 Isso 
explica a operação W (x 1) no eu 2, e por que isso acontece antes W (x 2).
L1:
L2:
W (x 1) L1:
L2:
W (x 1)
MS (x 1) W (x 2) W (x 2)
(para) (b)
Figura 7-13. Operações de gravação realizadas por um único processo P em duas cópias locais 
diferentes do mesmo armazenamento de dados. (a) Armazenamento de dados com consistência de 
escrita monotônica. (b) Armazenamento de dados que não fornece consistência de gravação 
monotônica.
Em contraste, a Figura 7-13 (b) mostra uma situação em que a consistência não é garantida.
escrita monotônica. Comparado com a Fig. 7-13 (a), o que está faltando é a propagação de W (x 1)
copiar eu 2 Em outras palavras, não é possível garantir que a cópia do x, em que a segunda escrita está sendo 
realizada, tem o mesmo valor ou o mais recente no tempo W (x 1) completado
no eu 1
Observe que, por definição de consistência de escrita monotônica, as operações de
escrever o mesmo processo é executado na mesma ordem em que começou. Uma forma um pouco mais fraca de 
gravações monotônicas é aquela em que os efeitos de uma operação de gravação são vistos apenas se todas as 
gravações anteriores foram realizadas, embora talvez não na ordem em que originalmente se originaram. Essa 
consistência é aplicável aos casos em que as operações de gravação são comutativas, de modo que a ordem não é 
realmente necessária. Detalhes podem ser encontrados em Terry et al. (1994).
294 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
7.3.4 Leia suas ações
Um modelo de consistência centrado no cliente que está intimamente relacionado às leituras monotônicas é o seguinte. 
Diz-se que um data warehouse fornece consistência leia suas escrituras se atender à seguinte condição:
O efeito de uma operação de gravação feita por um processo em um item de dados x
sempre será visto por uma operação de leitura sucessiva em x feito pelo mesmo processo.
Em outras palavras, uma operação de gravação sempre é concluída antes de uma operação de leitura sucessiva do 
mesmo processo, independentemente de onde a operação de leitura ocorre.
Às vezes, ocorre uma falta de consistência na leitura de suas gravações ao atualizar documentos da web, 
e os efeitos são vistos posteriormente. As operações de atualização freqüentemente ocorrem por meio de um 
editor padrão ou um processador de texto, os quais salvam a nova versão em um sistema de arquivos que é 
compartilhado pelo servidor web. O navegador da Web do usuário acessa esse mesmo arquivo, provavelmente 
após solicitá-lo do servidor da Web local. No entanto, uma vez que o arquivo foi retirado, o servidor ou o 
navegador geralmente armazenará em cache uma cópia local para acesso posterior. Conseqüentemente, 
quando a página da web for atualizada, se o navegador ou o servidor retornar a cópia em cache em vez do 
arquivo original, o usuário não verá os efeitos.
Efeitos semelhantes ocorrem ao atualizar senhas. Por exemplo, para acessar uma biblioteca digital na 
web, muitas vezes é necessário ter uma conta e sua senha correspondente. No entanto, a alteração de uma 
senha pode levar algum tempo para fazer efeito, fazendo com que a biblioteca fique inacessível ao usuário por 
alguns minutos. O atraso pode ser causado por um servidor separado sendo usado para lidar com senhas e a 
propagação subsequente de senhas (criptografadas) para os diferentes servidores que compõem a biblioteca 
pode levar algum tempo.
A Figura 7-14 (a) mostra um armazenamento de dados que fornece consistência de leitura de suas gravações. Observe 
que a Figura 7-14 (a) é muito semelhante à Figura 7-12 (a), exceto que agora a consistência é determinada pela última 
operação de gravação do processo P, em vez de sua última leitura.
L1:
L2:
W (x 1) L1:
L2:
W (x 1)
WS (x 1; x 2) R (x 2) WS (x 2) R (x 2)
(para) (b)
Figura 7-14. ( a) Armazenamento de dados que fornece consistência na leitura de suas gravações. 
(b) Data warehouse que não o fornece.
Na Figura 7-14 (a), o processo P executou uma operação de escrita W (x 1) e, em seguida, uma operação de leitura em 
uma cópia local diferente. A consistência na leitura de seus atos garante que
SEÇÃO 7.3 MODELOS DE CONSISTÊNCIA CENTRADOS NO CLIENTE 295
Os efeitos da operação de gravação podem ser vistos pela operação de leitura sucessiva. Isto é
expresso através WS (x 1; x 2), que estabelece que W (x 1) Faz parte de WS (x 2). Em contraste, na Figura 7-14 (b) W (x 1) foi 
excluído de WS (x 2), isso significa que os efeitos da operação de gravação anterior do processo P ainda não se espalhou 
para eu 2
7.3.5 Escritas seguem leituras
O modelo de consistência centrado no cliente mais recente é aquele em que as atualizações são propagadas como 
resultado de operações de leitura anteriores. Diz-se que um data warehouse fornece consistência escrituras 
seguem leituras se atender ao seguinte:
É garantido que a operação de gravação de um processo em um elemento de dados x que segue uma operação 
de leitura anterior em x realizado pelo mesmo processo ocorrerá no mesmo valor ou no valor mais recente de x que 
foi lido.
Em outras palavras, qualquer operação sucessiva de um processo em um elemento de dados x será feito em uma cópia de x que 
é atualizado com o valor lido mais recentemente por esse processo.
As gravações de consistência seguem leituras podem ser usadas para garantir que os usuários de uma rede de 
newsgroup vejam o anúncio de uma resposta a um artigo somente após terem visto o artigo original (Terry et al., 1994). 
Para entender o problema, suponha que um usuário leia o artigo primeiro PARA; então reaja e poste a resposta B. Ao exigir 
consistência, as gravações seguem as leituras, B será gravado em qualquer cópia do grupo de notícias somente após PARA 
também está escrito. Observe que os usuários que apenas leem os artigos não precisam necessariamente de um modelo 
de consistência centrado no cliente específico. As gravações de consistência seguem leituras garantem que as reações 
aos artigos sejam armazenadasem uma cópia local somente se o original também estiver armazenado lá.
L1: WS (x 1)
L2: WS (x 1 ;; x 2)
R (x 1) L1: WS (x 1)
L2: WS (x 2)
R (x 1)
W (x 2) W (x 2)
(para) (b)
Figura 7-15. ( a) Armazém de dados com leitura de gravação de consistência. (b) O 
armazenamento de dados não fornece gravações de consistência após leituras.
Esse padrão de consistência aparece na Figura 7-15. Na parte (a) desta figura, um
o processo lê para x em uma cópia local eu 1 As operações de gravação que causaram o valor lido também aparecem 
no conjunto escrito em eu 2, onde o mesmo processo executa uma operação de gravação. (Observe que outros 
processos incluídos no eu 2 eles também veem essas operações de gravação.) Em contraste, a operação realizada em eu
2, como a figura ilustra
ra 7-15 (b), ser feito em uma cópia consistente com a que acabou de ler eu 1
Mais adiante neste capítulo, retornaremos aos modelos de consistência centrados no cliente,
quando explicamos as implementações.
296 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
7.4 ADMINISTRAÇÃO DE RESPOSTAS
Um ponto-chave para qualquer sistema distribuído que ofereça suporte à replicação é decidir onde, quando e por quem 
as réplicas devem ser localizadas e, subsequentemente, quais mecanismos usar para mantê-las consistentes. O 
problema de localização, por si só, deve ser dividido em dois subproblemas: o da localização de servidores espelho, e 
aquele de localização do conteúdo.
A diferença é sutil, mas importante, e as duas questões muitas vezes não são claramente separadas. A localização 
do servidor de réplica trata de encontrar os melhores lugares para colocar um servidor que possa hospedar (parte 
de) um armazenamento de dados. A colocação de conteúdo consiste em encontrar os melhores servidores para 
colocar conteúdo. Observe que isso geralmente significa que estamos procurando o local ideal para um único item 
de dados. Claro, antes que a colocação de conteúdo possa ocorrer, primeiro temos que localizar os servidores. 
Analisaremos esses dois problemas de posicionamento abaixo e continuaremos com uma explicação dos 
mecanismos básicos para gerenciar o conteúdo replicado.
7.4.1 Localização do servidor de réplica
O posicionamento do servidor de réplica não é um problema estudado intensamente, pelo simples motivo de que 
geralmente é mais uma questão comercial e administrativa do que um problema de otimização. No entanto, analisar 
as propriedades do cliente e da rede é útil para tomar decisões informadas.
Existem várias maneiras de calcular a melhor localização do servidor de réplica, mas todas elas se resumem a um 
problema de otimização em que você precisa selecionar o melhor K de entre N Localizações ( K <N). Sabe-se que esses 
problemas são computacionalmente complexos, e que só podem ser resolvidos por heurísticas. Qiu et al. (2001) medem a 
distância entre clientes e locais de um ponto de partida. A distância pode ser medida em termos de latência ou largura de 
banda. Sua solução seleciona um servidor por vez, de forma que a distância média entre esse servidor e seus clientes 
seja mínima, pois k servidores já foram localizados (isto significa que existem N 
k locais descartados).
Como alternativa, Radoslavov et al. (2001) propõem ignorar a posição dos clientes, e apenas tomar a 
topologia da internet como se ela fosse composta por sistemas autônomos. UMA sistema autônomo (AS, por sua 
sigla em inglês) pode ser considerada como uma rede na qual todos os nós executam o mesmo protocolo de 
roteamento e que é gerenciada por uma única organização. Em janeiro de 2006, já havia mais de 20.000 sistemas 
autônomos. Radoslavov et al., Considere primeiro o maior AS e coloque um servidor no roteador que tenha o maior 
número de interfaces de rede (ou seja, links). Esse algoritmo é então repetido com o segundo maior AS e assim 
por diante.
Como resultado, localizar um servidor sem o conhecimento do cliente atinge resultados semelhantes aos obtidos 
com o conhecimento do cliente, partindo do princípio de que os clientes estão uniformemente distribuídos pela Internet 
(com base na topologia existente). Até que ponto essa suposição é verdadeira não está claro; ainda não foi bem 
estudado.
SEÇÃO 7.4 ADMINISTRAÇÃO DE RESPOSTAS 297
Um problema com esses algoritmos é que eles são caros para computar. Por exemplo, os dois algoritmos anteriores 
têm uma complexidade maior que O ( N 2), Onde N é o número de locais a serem inspecionados. Na prática, isso significa 
que, mesmo para alguns milhares de locais, um cálculo pode precisar ser executado por dezenas de minutos. Isso pode ser 
inaceitável, especialmente quando ocorrem multidões instantâneas uma explosão repentina de pedidos de um site 
específico, o que acontece regularmente na Internet). Nesse caso, é essencial determinar rapidamente onde os servidores 
de réplica são necessários, após o que um servidor pode ser selecionado para o local do conteúdo.
Szymaniak e outros (2006) desenvolveram um método pelo qual uma região pode ser rapidamente identificada 
para localizar réplicas. Uma região é identificada como uma coleção de nós que acessam o mesmo conteúdo, mas 
para os quais a latência internodal é baixa. O objetivo do algoritmo é primeiro selecionar as regiões com maior 
demanda, ou seja, aquelas com mais nós, e então deixar um dos nós daquela região atuar como um servidor de 
réplica.
Para tanto, assume-se que os nós estão posicionados em um espaço geométrico m dimensional, como explicamos no 
capítulo anterior. A ideia básica é identificar o K clusters maiores e designar um nó de cada cluster para hospedar o 
conteúdo replicado. Para identificar esses aglomerados, todo o espaço é dividido em células. As K As células densas são 
então escolhidas para acomodar um servidor de réplica. Uma célula nada mais é do que um hipercubo m dimensional. Para 
um espaço bidimensional, isso corresponde a um retângulo.
Obviamente, o tamanho da célula é importante, conforme mostrado na Figura 7-16. Se as células forem escolhidas 
muito grandes, então vários clusters de nós podem ser encontrados na mesma célula. Nesse caso, poucos servidores 
de réplica seriam escolhidos para esses clusters. Por outro lado, a escolha de células pequenas pode fazer com que um 
único cluster se propague em várias células, resultando na escolha de muitos servidores de réplica.
Muito pequeno Demasiado grande
Célula Muito bem
Figura 7-16. Escolher o tamanho apropriado de uma célula para localizar um servidor.
Como resultado, um tamanho de célula adequado pode ser calculado como uma função simples da 
distância média entre dois nós e o número de réplicas necessárias. Com este tamanho de célula, pode-se 
mostrar que o algoritmo se comporta tão bem quanto o quase ótimo descrito por Qiu et al. (2001), mas com um 
grau de complexidade muito menor: O ( N x max { log (N), K}). Para ilustrar o que esse resultado significa: 
experimentos mostram
298 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
calcular as 20 principais localizações de réplicas para uma coleção de 64.000 nós é cerca de 50.000 vezes mais 
rápido. Consequentemente, a localização dos servidores de réplica agora pode ser feita em tempo real.
7.4.2 Localização e replicação de conteúdo
Agora vamos deixar o local do servidor e nos concentrar no local do conteúdo. Quando se trata de replicação e colocação de 
conteúdo, existem três tipos de réplicas organizadas logicamente que podem ser distinguidas, conforme ilustrado na Figura 
7-17.
Réplica iniciada pelo servidor Réplica 
iniciada pelo cliente
Réplicas
permanente
Réplicas iniciadas
pelo servidor
Réplicas iniciadas
para o cliente
clientes
Figura 7-17. Organização lógica de diferentes tipos de cópias de um armazenamento de dados em 
três anéis concêntricos.
Réplicas permanentes
As réplicas permanentes podem ser consideradas o conjunto inicial de réplicas que constituem um armazenamento de 
dados distribuído. Em muitos casos, o número de réplicas permanentes épequeno. Por exemplo, vamos considerar um 
site. O layout de um site geralmente vem em uma de duas formas. A primeira classe de distribuição é aquela em que os 
arquivos que constituem um site são replicados em um número limitado de servidores em um único local. Sempre que 
chega uma solicitação, ela é encaminhada para um dos servidores, por exemplo, por meio de uma estratégia
round-robin ( todos contra todos).
A segunda forma de sites distribuídos é conhecida como espelho. Nesse caso, um site é copiado para um 
número limitado de servidores, chamado sites espelho, que são distribuídos geograficamente pela Internet. Na 
maioria dos casos, os clientes simplesmente escolhem um dos diferentes sites espelho de uma lista oferecida a 
eles. Os sites espelhados têm em comum sites baseados em cluster que têm apenas algumas réplicas, que são 
mais ou menos configuradas estaticamente.
Organizações estáticas semelhantes também são apresentadas com bancos de dados distribuídos (Oszu e Valduriez, 
1999). Novamente, o banco de dados pode ser distribuído e replicado em uma série de servidores que compõem um cluster 
de servidores, geralmente conhecido como arquitetura
SEÇÃO 7.4 ADMINISTRAÇÃO DE RESPOSTAS 299
nada compartilhado, no qual é enfatizado que nem os discos nem a memória principal são compartilhados pelos 
processadores. Como alternativa, um banco de dados é distribuído, e provavelmente replicado, em vários locais 
geograficamente dispersos. Essa arquitetura é muito usada em bancos de dados federados (Sheth e Larson, 1990).
Réplicas iniciadas pelo servidor
Em contraste com as réplicas permanentes, as réplicas iniciadas pelo servidor são cópias de um armazenamento de 
dados que existe para melhorar o desempenho e que são criadas por iniciativa do (proprietário do) armazenamento de 
dados. Por exemplo, considere um servidor da web localizado em Nova York. Normalmente, este servidor pode lidar com 
as solicitações recebidas com muita facilidade, mas pode acontecer que durante alguns dias haja uma explosão repentina 
de solicitações de um local inesperado, longe do servidor. Nesse caso, pode valer a pena instalar várias réplicas 
temporárias nas regiões de onde vêm as solicitações.
O problema de colocar réplicas dinamicamente também está sendo abordado em serviços de hospedagem na 
web. Esses serviços oferecem um conjunto (relativamente estático) de servidores espalhados pela Internet que podem 
manter e fornecer acesso a arquivos da Web pertencentes a terceiros. Para fornecer recursos ideais, esses serviços de 
hospedagem podem replicar arquivos dinamicamente em servidores onde esses arquivos são necessários para 
melhorar o desempenho, ou seja, em clientes solicitantes próximos (grupos). Sivasubramanian et al. (2004b) fornecem 
um tratamento detalhado da replicação em serviços de hospedagem na web, ao qual retornaremos no Capítulo 12.
Uma vez que os espelhos já estão localizados, decidir onde colocar seu conteúdo é mais fácil do que colocar 
no servidor. Um método de implementação de replicação dinâmica de arquivos no caso de um serviço de 
hospedagem na web é descrito por Rabinovich et al. (1999). O algoritmo é projetado para oferecer suporte a páginas 
da web, portanto, assume que as atualizações são relativamente raras em comparação com as solicitações de 
leitura. Ao usar arquivos como unidade dos dados, o algoritmo funciona da seguinte maneira.
O algoritmo de replicação dinâmica leva dois pontos em consideração. Primeiro, a replicação pode ocorrer para 
reduzir a carga em um servidor. Em segundo lugar, os arquivos específicos de um servidor podem ser migrados ou 
replicados para outros servidores localizados nas proximidades de clientes que solicitam muito esses arquivos. Nas páginas 
seguintes, vamos nos concentrar apenas neste segundo ponto. Também omitimos vários detalhes, mas o leitor pode 
encontrá-los em Rabinovich et al. (1999).
Cada servidor controla o número de acessos por arquivo e registra de onde vêm as solicitações de acesso. 
Em particular, presume-se que, dado um cliente C, Cada servidor pode determinar qual dos servidores do serviço 
de hospedagem está mais próximo de C. ( Essas informações podem ser obtidas, por exemplo, nos bancos de 
dados de roteamento.) Se o
cliente C 1 e o cliente C 2 compartilhe o mesmo servidor "mais próximo" P, todas as solicitações de acesso ao arquivo F no servidor Q 
Desde a C 1 Y C 2 estão registrados em conjunto em Q como uma
conta de login único cnt Q ( P, F). Essa situação aparece na Figura 7-18.
Quando no servidor S o número de solicitações de acesso a um arquivo específico F diminui
abaixo de um limite para eliminação del (S, F), esse arquivo pode ser removido de S. Em consequência,
300 CAPÍTULO 7 CONSISTÊNCIA E REPLICAÇÃO
C 2
Servidor sem um
cópia do arquivo F
P
Cliente
Servidor com um
cópia de F
Q
C 1
Arquivo F
O servidor Q conta os acessos de C 1 e C 2 como 
se viessem de P
Figura 7-18. Contagem de solicitações de acesso de diferentes clientes.
o número de réplicas para esse arquivo é reduzido, o que provavelmente resultará em cargas de trabalho maiores em outros 
servidores. Para garantir que haja pelo menos uma cópia de cada arquivo, medidas especiais são tomadas.
Um limite de replicação rep (S, F), que é sempre escolhido acima do limite de exclusão, indica se o número de 
solicitações de acesso a um arquivo específico é tão alto que pode valer a pena replicá-lo em outro servidor. Se o 
número de solicitações cair entre os limites de exclusão e replicação, apenas o arquivo poderá ser migrado. Em outras 
palavras, nesse caso é importante manter pelo menos o mesmo número de réplicas daquele arquivo.
Quando um servidor Q decide reavaliar a localização dos arquivos que armazena, verifica o número de acessos por 
arquivo. Se o número total de solicitações de acesso a F no Q cai abaixo do limite de eliminação, del (Q, F), o servidor irá 
deletar F a menos que esta seja a última cópia.
Além disso, se estiver em qualquer servidor P, cnt Q ( P, F) excede em mais da metade do total de solicitações para F no
Q, para o servidor P você é convidado a assumir F. Em outras palavras, o servidor Q tentará migrar
F em direção a P.
Migração de arquivo F em direção ao servidor P nem sempre tem sucesso, por exemplo, porque P já está muito 
carregado ou não tem espaço em disco. Nesse caso, Q vai tentar replicar F em outros servidores. Claro, a replicação pode 
ocorrer apenas se o número total de solicitações de acesso para F no Q excede o limite de replicação rep (Q, F). O servidor Q verifica 
todos os outros servidores no serviço de hospedagem na web, começando pelo mais distante. Sim, em algum servidor R,
cnt Q ( R, F) excede uma certa fração de todas as solicitações de acesso a F no Q, é feita uma tentativa de replicar F no R.
A replicação iniciada pelo servidor continua a crescer em popularidade com o tempo, especialmente no contexto de 
serviços de hospedagem na web, como o que acabamos de descrever. Observe que, desde que sejam fornecidas garantias 
de que cada item de dados seja hospedado por pelo menos um servidor, isso pode ser suficiente para usar apenas a 
replicação iniciada pelo servidor e não ter réplicas permanentes. No entanto, os espelhos permanentes ainda são úteis 
como ferramentas de backup, ou para serem usados como os únicos espelhos que podem ser alterados para
SEÇÃO 7.4 ADMINISTRAÇÃO DE RESPOSTAS 301
garantir consistência. As réplicas iniciadas pelo servidor são usadas para colocar cópias somente leitura perto dos 
clientes.
Réplicas iniciadas pelo cliente
Um tipo importante de réplica é aquela iniciada por um cliente. Essas réplicas são mais comumente conhecidas como caches 
(cliente). Em essência, um cache é uma ferramenta de armazenamento local usada por um cliente para armazenar 
temporariamente uma cópia dos dados solicitados. Em princípio, o gerenciamento de cache é deixado inteiramente para o 
cliente. O armazenamento de dados do qual eles