Abordagens de Consistência e Replicação

Prévia do material em texto

AULA Nº 14
SISTEMAS DISTRIBUÍDOS
Abordagens de Consistência e Replicação
Os slides são baseados no livro de Sistemas Distribuídos de TANENBAUM, A. S. e STEEN, M. V.
Conteúdo desta aula
Aula anterior
• Replicação, motivação para consistência e 
consistência.
Conteúdo desta aula
• Abordagens de consistência
• Gerenciamento de réplicas
Consistência Sequencial (a)
1. P
1 
executa W(x)a para x. 
2. Depois, o processo P
2 
ajusta o valor de x para b. 
3. Os processos P
3 
e P
4 
primeiro lêem o valor b e;
4. A operação de escrita do processo P
2 
parace ter ocorrido 
antes da de P
1
Todos processos - a mesma intercalação (e.g. b e depois a).
Consistência Sequencial (b)
• Neste caso, não há consistência sequencial.
• Porque nem todos os processos vêem a mesma 
sequência de operações de escrita. 
• Para o processo P
3 
parece que o item de dados foi 
primeiro alterado para b, e mais tarde para a. 
• Por outro lado, P
4 
concluirá que o valor final é b.
Consistência Sequencial
• Três processos executando concorrentemente P
1
, P
2,
P
3.
• Os itens de dados são x,y,z. 
• Cada variável é inicializada com 0. Uma atribuição é uma 
escrita, e um print é uma operação de leitura.
• Várias combinações possíveis.
Consistência Sequencial
• Em (a) P
1
, P
2,
P
3 .
são executados em ordem. 
• (b), (c), (d) intercalações diferentes, mas válidas.
• Devem aceitar todos os resultados válidos.
• Um programa que funciona somente com um subconjunto 
de resultados está incorreto.
Consistência Causal
Neste exemplo:
• Há consistência causal e não há consistência sequencial.
• As escritas W
2
(x)b e W
1
(x)c são concorrentes, assim
• Não é exigido que todos os processos vejam escritas de b 
e c na mesma ordem.
• Temos W
2
(x)b potencialmente dependente de W
1
(x)a.
• Porque b pode ser resultado de um cálculo que envolva
o valor lido por R
2
(x)a. 
• As duas escritas são relacionadas por causalidade, 
portanto, temos uma violação
Consistência Causal (a)
Consistência Causal (b)
• Como a leitura R(x)a foi removida, W
2
(x)b e W
1
(x)a agora 
são escritas concorrentes. 
• Um depósito consistente por causalidade não requer 
que escritas concorrentes sejam ordenadas globalmente.
Gerenciamento de Réplicas -
Problemas
• Decidir onde, quando e por quem as réplicas devem ser 
posicionadas.
• Mecanismos para manter as réplicas consistentes.
Problema de Posicionamento
Pode ser subdividido em dois subproblemas:
• Posicionar servidores de réplicas
• Posicionar conteúdo
Posicionar servidores de réplicas: achar as melhores 
localizações para colocar um servidor que pode hospedar 
um depósito de dados (encontrar o local).
Posicionamento de conteúdo: achar os melhores 
servidores para colocar conteúdo (encontrar o servidor).
Primeiro posicionar o servidor para depois posicionar o 
conteúdo.
Posicionamento do Servidor de Réplicas
• Há vários modos de calcular o melhor posicionamento de 
servidores de réplicas.
• Problema de otimização, no qual as melhores K de N 
posições precisam ser selecionadas → heurística.
• Em (Qiu et al – 2001): distância entre clientes e 
localizações
Posicionamento do Servidor de 
Réplicas – Algumas soluções
Em (Qiu et al – 2001): distância entre clientes e localizações
• Pode ser medida em termos de latência ou largura de 
banda.
• A posição é definida baseada na métrica de que a 
distância média entre o servidor e os seus clientes é 
mínima.
• É uma solução cara, pois o cálculo pode levar dezenas de 
minutos.
Em (Radoslav et al – 2001): (a) Ignorar a localização dos 
clientes e (b) apenas considerar os sistemas autônomos
(AS) – topologia da Internet
• Rede na qual os nós executam o mesmo protocolo de 
roteamento, que é gerenciada por uma única organização
• Consideram o maior AS e colocam um servidor no 
roteador com maior número de enlaces.
• Os ASs são escolhidos em ordem de tamanho.
• Solução cara também.
Posicionamento do Servidor de 
Réplicas – Algumas soluções
Em(Szymaniak et al – 2006): identificar rapidamente uma 
região para o posicionamento de réplicas:
• Uma região é identificada como um conjunto de nós que 
acessam o mesmo conteúdo;
• Primeiramente, selecionamos as regiões mais exigentes 
(críticas) com o maior número de nós;
• E depois, seleciona-se um servidor para ser o 
coordenador de réplicas.
Posicionamento do Servidor de 
Réplicas – Algumas soluções
Replicação e Posicionamento de 
conteúdo
Três tipos diferentes de réplicas organizadas logicamente
• Réplicas permanentes
• Réplicas iniciadas por servidor
• Réplicas iniciadas por cliente
Replicação e Posicionamento de 
conteúdo
Posicionamento de conteúdo (e.g. arquivos de um site, 
banco de dados, etc.)
Réplicas Permanentes
• Conjunto inicial de réplicas que constituem um depósito 
de dados distribuído.
• Número de réplicas permanentes é pequeno.
• Ex.: Site Web
• Arquivos são replicados para um número limitado de 
servidores que estão em uma única localização.
• Espelhamento de sites Web.
Réplicas Iniciadas por Servidor
Cópias de arquivos criadas por iniciativa do proprietário do
depósito para melhorar o desempenho.
Exemplo:
• Considere um servidor em São Carlos - SP. 
• Pode acontecer uma rajada de requisições não planejada
que vêm de uma localização longe do servidor. 
• Talvez valha a pena instalar umas réplicas temporárias
próximas das regiões com a rajada.
Réplicas Iniciadas por Cliente
• São mais conhecidas como caches (de cliente).
• Recurso de armazenamento local, usado por um cliente 
• Guarda temporariamente uma cópia dos dados que ele 
acabou de requisitar.
• Melhorar desempenho (tempo de acesso aos dados).
• Gerenciamento cabe inteiramente ao cliente.
• Depósito de dados “original” nada tem a ver com a 
manutenção e a consistência da cache.
Concluindo
Nesta aula:
• Consistência e Replicação
Estes slides estão baseados na bibliografia
Sistemas Distribuídos de TANENBAUM, A. S. e 
STEEN, M. V. (2ª edição)
Boa Prova!
AULA Nº 14
SISTEMAS DISTRIBUÍDOS
Abordagens de Consistência e Replicação
Os slides são baseados no livro de Sistemas Distribuídos de TANENBAUM, A. S. e STEEN, M. V.