Aula 21 - SD - Replicação de dados

Prévia do material em texto

Sistemas Distribuídos 
Aula 21 – Replicação de Dados
Carla Rodrigues Figueiredo Lara
DECSI/ICEA UFOP
Introdução
• Aprimorar a confiabilidade ou melhorar o desempenho.
• Alta disponibilidade e tolerância a falhas
• Um dos principais problemas é manter as réplicas
consistentes.
• Isso significa que, quando uma cópia é atualizada,
precisamos assegurar que as outras também sejam
atualizadas; caso contrário, as réplicas não serão mais
iguais.
DECSI/ICEA UFOP
2
Introdução
• A alta disponibilidade é um tópico de crescente
interesse, principalmente com a atual tendência em
direção à computação móvel e à operação
desconectada.
• Exemplo: um usuário de notebook que salva seus
arquivos para usar durante uma viagem de trem, e
em alguns momentos fica sem conexão. Uma
agenda compartilhada poderia gerar conflitos.
DECSI/ICEA UFOP
3
Melhorando serviços com dados 
replicados
A replicação é o segredo da eficácia dos sistemas 
distribuídos, pois pode fornecer melhor 
desempenho, alta disponibilidade e tolerância a 
falhas.
DECSI/ICEA UFOP
4
Melhorando serviços com dados 
replicados – Melhoria de desempenho
• Balanceamento de carga
• carga de trabalho é compartilhada entre servidores 
amarrando-se vários IPs a um único nome de DNS. 
DECSI/ICEA UFOP
5
Melhorando serviços com dados 
replicados – Melhoria de desempenho
• Uso de cache em clientes e servidores proxies.
• Evitar a latência de busca de dados nos servidores
• Dados imutáveis x mutáveis (dinâmicos, como a 
web)
• Protocolos para garantir que os clientes recebem 
dados atualizados.
• Existem limites para a eficácia da replicação como 
uma técnica de melhoria de desempenho.
DECSI/ICEA UFOP
6
Melhorando serviços com dados 
replicados – Maior disponibilidade
• Alta disponibilidade
• a proporção do tempo durante a qual o serviço 
está acessível com tempo de resposta razoável 
deve ser próxima de 100%. 
• Fatores relevantes para a alta disponibilidade são:
• Falhas no servidores;
• Particionamento da rede operação desconectada 
(as desconexões da comunicação, maioria não 
planejada, são um efeito colateral da mobilidade 
do usuário.
DECSI/ICEA UFOP
7
Melhorando serviços com dados 
replicados – Maior disponibilidade
• Aumento da disponibilidade
- Se cada um de n servidores tiver uma probabilidade
independente p de falhar (ou se tornar inacessível) então a
disponibilidade é:
1 – Pn: disponibilidade do serviço
- Por exemplo, se p = 5% e se existem 2 servidores, então:
a disponibilidade do serviço = 1 - 0,052 = 1 – 0,0025 = 99,75%
• 1 – Pn: por exemplo, se P = 5%, n = 3
=> serviço está disponível 99.875% do tempo
DECSI/ICEA UFOP
8
Melhorando serviços com dados 
replicados – Maior disponibilidade
• Uma diferença importante entre os sistemas que
usam cache e a replicação do servidor é que as caches
não contêm necessariamente conjuntos de objetos,
como arquivos, em sua totalidade.
• Uso de cache não melhora necessariamente a
disponibilidade no nível de aplicação – um usuário
pode ter um arquivo necessário, mas outro não.
DECSI/ICEA UFOP
9
Melhorando serviços com dados 
replicados – Tolerância a falhas 
• Dados de alta disponibilidade não são necessariamente
dados rigorosamente corretos
• Por exemplo, dois usuários em lados opostos de uma rede que
foi particionada podem fazer atualizações conflitantes e que
precisem ser resolvidas.
• Um serviço tolerante a falhas sempre garante
comportamento rigorosamente correto, apesar de certo
número e tipo de falhas.
• A correção está relacionada ao caráter atual dos dados
fornecidos para o cliente e aos efeitos das operações dos
clientes sobre os dados.
DECSI/ICEA UFOP
10
Modelo arquitetural básico para o 
gerenciamento de dados replicados
• Objetos são conjuntos de itens.
• Um arquivo ou um objeto java, por exemplo.
• Cada objeto lógico é implementado por um
conjunto de cópias físicas chamadas de réplicas.
• As réplicas de determinado objeto não são
necessariamente idênticas o tempo todo.
• Componentes descritos por meio de suas funções.
• não necessariamente implementados por processo (ou
hardware) distintos.
• Réplicas são mantidas por gerenciadores distintos.
DECSI/ICEA UFOP
11
Modelo arquitetural básico para o 
gerenciamento de dados replicados
FE
Requisições 
e respostas
C
GerenciadoresC
Serviço
Clientes Front Ends
de réplicas
RM
RM
FE
RM
Transparência de replicação
usuário/cliente não precisa saber que existem diversas cópias do recurso
Consistência de replicação
os dados são consistentes entre todas as réplicas, ou estão no processo de se
tornarem consistentes
DECSI/ICEA UFOP
12
Modelo arquitetural básico para o 
gerenciamento de dados replicados
• Em geral, o GR é um servidor;
• Pode ser empregado em aplicativos
• Processos aplicativos podem atuar como clientes e GR
• Exemplo: um aplicativo no notebook do usuário do trem
• Um conjunto de GR´s fornece serviço
• Os clientes recebem acesso (agenda, conta bancária)
• Solicitam operações de leitura e atualização de objetos
• Requisições são inicialmente manipuladas pelos FE´s.
• Função de comunicar com os GR´s usando troca de
mensagem
• Os FE´s tornam a replicação transparente.
DECSI/ICEA UFOP
13
Gerenciamento de Replicação
• 5 Fases que afetam o desempenho de acesso a 
objetos replicados
• Requisição
• Coordenação
• Execução
• Acordo
• Resposta
DECSI/ICEA UFOP
14
Gerenciamento de Replicação
• Requisições
- requisições podem ser feitas a um GR 
- via multicast a múltiplos GR
• Coordenação: os GR´s devem decidir:
- se a requisição será aplicada
- a ordem em que as requisições serão aplicadas
ordem FIFO: se um FE envia uma requisição r e então uma 
requisição r’, então toda GR deve tratar r e depois r’
ordem causal: se a requisição r “happens-before” r’, então 
toda GR deve tratar r e depois r’
ordem total: se um GR trata r e depois r’, então todas as GR 
devem tratar r e depois r’
DECSI/ICEA UFOP
15
Gerenciamento de replicação
• Execução: Tentativas de executar a requisição
• De forma que possam desfazer seus efeitos posteriormente
• Acordo/Consenso: 
• as GR´s tentam alcançar o consenso sobre o efeito da requisição
• exemplo: Two-phase commit através de um coordenador
• se bem sucedido, a requisição se torna permanente
• Resposta: 
• um ou mais GR respondem ao FE
• o FE retorna a primeira resposta obtida
• A ordem das fases e o conteúdo pode variar de acordo 
com as necessidades da aplicação.
DECSI/ICEA UFOP
16
Comunicação de Grupos
• Grupos estáticos: membros são pré-definidos
• Grupos dinâmicos: membros podem entrar (join) e 
sair (leave) do grupo
• Um serviço de gerenciamento de membros em um 
grupo mantém visões de grupo (views):
• listas dos membros atuais do grupo
• não é uma lista mantida por um membro, mas cada 
membro possui sua view local
DECSI/ICEA UFOP
17
Modo de Visualização - Views
• Uma view Vp(g) é o entendimento do processo p
de seu grupo (lista de membros)
Exemplo: Vp.0(g) = {p}, Vp.1(g) = {p, q}, Vp.2 (g) = {p, q, r}, Vp.3 (g) = {p,r}
• Uma nova view é disseminada através do grupo
sempre que um membro entra ou sai do grupo
• membros que detectarem uma falha de um outro
membro, envia um multicast confiável notificando a
mudança da view (requer ordem total para o multicast)
• Mensagens enviadas em uma view devem ser
enviada a todos os membros do grupo
DECSI/ICEA UFOP
18
Modo de Visualização - Views
• Requisitos para entrega de uma view
• Ordem: se p entrega uma v(g), e depois v’(g), então 
nenhum outro processo q ≠p entrega v’(g) antes de v(g)
Garantia de consistência
• Integridade: se o processo p envia v(g), então p está na 
view v(g), ou seja, p  v(g).
Garantia de sanidade
• Não trivialidade: se o processo q entra em uma view e 
se torna acessível a partir de um processo p ≠q, então, q
estará sempre presente nas views entregues a p.
Previne soluções triviais
DECSI/ICEA UFOP
19
Modo de Visualização - Views
• O primeiro desses requisitos está relacionado ao fato de dar ao
programadoruma garantia de consistência, certificando-se de
que as alterações no modo de visualização sempre ocorrem na
mesma ordem em diferentes processos.
• O segundo requisito é uma “verificação de sanidade mental”.
• O terceiro previne-se contra soluções triviais. Por exemplo, um
serviço de participação de membro que informa a cada
processo, independentemente de sua conectividade, que ele
está sozinho em um grupo, não tem muito interesse. A
condição de não trivialidade diz que, se dois processos que
entraram no mesmo grupo podem se comunicar, então cada
um deles deve ser considerado membro desse mesmo grupo.
DECSI/ICEA UFOP
20
Comunicação em grupo com modo 
de visualização síncrono 
• Um sistema de comunicação em grupo com modo de
visualização síncrono dá garantias adicionais, em relação
às anteriores, sobre a ordem de distribuição das
notificações de modo de visualização, a respeito da
entrega de mensagens multicast.
• A comunicação com modo de visualização síncrono
amplia a semântica de multicast confiável.
• As garantias oferecidas pela comunicação em grupo com
modo de visualização síncrono são as seguintes:
DECSI/ICEA UFOP
21
Comunicação em grupo com modo 
de visualização síncrono 
• Acordo/Consenso: processos corretos entregam a mesma
sequência de modos de visualização (começando a partir do
modo de visualização em que eles entram no grupo) e o
mesmo conjunto de mensagens em qualquer modo de
visualização dado. (se um processo entrega m em v(g), todos os
outros entregam m também no modo v(g).
• Integridade: se p enviou a mensagem m, p não irá enviar m
novamente, e p  grupo(m), e o processo que enviou m está no
modo de visualização em que p entrega m.
• Validade (grupos fechados): processos corretos sempre
entregam todas as suas mensagens que enviam. Se o sistema
deixar de entregar uma mensagem para um processo q, ele
notificará os processos sobreviventes entregando um novo
modo de visualização com q excluído.
DECSI/ICEA UFOP
22
Grupos de comunicação
DECSI/ICEA UFOP
23
• Considere um grupo com três processos p, q e r.
Suponha que p envie uma mensagem m enquanto está no modo de 
visualização (p, q, r), mas falhe após enviar m, enquanto q e r estão 
corretos. 
• p pode falhar antes de m ter chegado a qualquer processo. 
• q e r entregam, cada um, o novo modo de visualização (q,r), 
mas nenhum entregará m. 
• m pode chegar a pelo menos um dos dois processos sobreviventes, 
quando p falha.
• q e r entregam primeiro m e depois o modo de visualização 
(q,r), não é permitido inverter essa ordem.
Grupos de comunicação
DECSI/ICEA UFOP
24
p
q
r
p crashes
view (q, r)
view (p, q, r)
p
q
r
p crashes
view (q, r)
view (p, q, r)
a (Permitido). b (Permitido).
Grupos de comunicação
p
q
r
p crashes
view (q, r)
view (p, q, r)
p
q
r
p crashes
view (q, r)
view (p, q, r)
a (Permitido). b (Permitido).
p
q
r
view (p, q, r)
p
q
r
p crashes
view (q, r)view (p, q, r)
c (Proibido). d (Proibido).
p crashes
view (q, r)
DECSI/ICEA UFOP
25
Grupos de comunicação
• A entrega de um novo modo de visualização define uma
linha imaginária no sistema e toda mensagem entregue
é consistentemente distribuída em um lado ou outro
dessa linha.
• permite ao programador tirar conclusões úteis a respeito do
conjunto de mensagens que outros processos corretos
entregaram ao distribuir um novo modo de visualização,
baseado apenas na ordem local.
DECSI/ICEA UFOP
26
Serviços Tolerantes a Falhas
• Como fornecer um serviço correto quando ocorrer 
falhas?
• Supõe-se que cada gerenciador de réplica se comporta
de acordo com a especificação da semântica dos objetos
que gerencia.
• Exemplo: contas bancárias incluiria a garantia de que os
fundos transferidos entre as contas nunca poderia
desaparecer, apenas depósitos e saques afetam o saldo.
DECSI/ICEA UFOP
27
Serviços Tolerantes a Falhas
• Considere dois gerenciadores de réplica nos
computadores A e B mantêm, cada um, réplicas de
duas contas bancárias x e y.
• Os clientes leem e atualizam as contas no GR´s
locais, mas tentam usar outro GR, se o local falha.
• Os GR´s propagam em background as atualizações
entre si, após responderem aos clientes.
DECSI/ICEA UFOP
28
Serviços Tolerantes a Falhas -
Exemplo
• O cliente 1 atualiza para $1 o saldo de x em seu
gerenciador de réplica local B e, depois, tenta atualizar para
$2 o saldo de y, mas descobre que B falhou.
• Portanto, em vez disso, o cliente 1 aplica a atualização em
A. Agora, o cliente 2 lê os saldos em seu gerenciador de
réplica local A e descobre primeiro que y tem $2 e depois
que x tem $0 – a atualização de B na conta bancária x não
chegou, pois B falhou.
• A situação está mostrada a seguir, e as operações são
rotuladas de acordo com o computador em que elas
ocorreram primeiro:
DECSI/ICEA UFOP
29
Serviços Tolerantes a Falhas
• Inicialmente, x = y = 0
• Cliente 1 atualiza objeto x em uma réplica B
• Réplica B falha
DECSI/ICEA UFOP
30
Houve atualização 
de X no servidor B
X não foi atualizado 
no servidor A
Comportamento correto: 
Capacidade de linearização
• Um serviço de compartilhamento de objetos replicado é dito
linearizável se:
• Obedecem à especificação de uma única cópia correta do
objeto;
• É consistente com os tempos reais com que cada
operação ocorreu durante a execução.
DECSI/ICEA UFOP
31
Capacidade de Linearização
• A capacidade de linearização diz respeito à
interposição de operações individuais e não se
destina a ser transacional.
• Uma execução que pode ser linearizada pode violar
as noções de consistência específicas da aplicação,
caso não seja aplicado controle de concorrência.
DECSI/ICEA UFOP
32
Capacidade de Linearização
• O exemplo anterior não pode ser linearizado
• Não há interposições das operações que leve ao 
resultado correto
DECSI/ICEA UFOP
33
Capacidade de Linearização
• Linearização é difícil (ou quase impossível) de ser alcançada 
em sistemas reais.
• Um critério menos restritivo é o de consistência sequencial.
DECSI/ICEA UFOP
34
Consistência Sequencial
• Um serviço de compartilhamento de objetos
replicado é sequencialmente consistente se, para
qualquer execução (real) existe alguma intercalação
de operações do cliente (virtual) que:
• A sequência interposta de operações satisfaz a
especificação de uma única cópia correta dos objetos;
• A ordem das operações de interposição é consistente
com a ordem do programa no qual cada cliente
individual as executou.
DECSI/ICEA UFOP
35
Consistência Sequencial
• Não exige ordenação total ou tempo absoluto.
• Única noção de ordem relevante é a ordem dos
eventos em cada cliente separado (ordem do
programa).
• A interposição de operações pode embaralhar, em
qualquer ordem, a sequencia de operações de um
conjunto de clientes, desde que a ordem de cada cliente
não seja violada e que o resultado de cada operação seja
consistente, em termos da especificação dos objetos, com
as operações que a precederam.
• Semelhante a embaralhar vários maços de cartas para que
elas se misturem de maneira tal que preservem a ordem
original de cada maço.
DECSI/ICEA UFOP
36
Consistência Sequencial
• Todo serviço que pode ser linearizado também tem
consistência sequencial.
• Pois a ordem do tempo real reflete a ordem do
programa de cada cliente, o inverso não é
verdadeiro.
• Como garantir consistência sequencial: garantindo
que todas as réplicas de um objeto sejam
consistentes.
DECSI/ICEA UFOP
37
Consistência Sequencial
DECSI/ICEA UFOP
38
Um exemplo de execução de um serviço que tem consistência sequencial, 
mas não pode ser linearizado, aparece a seguir:
Essa execução é possível sob uma estratégia de replicação simples,
mesmo que nenhum dos computadores A ou B falhe, mas se a
atualização de x feita pelo cliente 1 em B não tiver chegado a A
quando o cliente 2 a ler.
O critério do tempo real para a capacidade de linearização não é
satisfeito, pois getBalanceA(x)→ 0 ocorre depois de setBalanceB(x,1);
Consistência Sequencial
DECSI/ICEAUFOP
39
A interposição a seguir satisfaz os dois critérios da 
consistência sequencial:
- A sequência interposta de operações satisfaz a especificação de uma
única cópia correta dos objetos;
- A ordem das operações de interposição é consistente com a ordem do
programa no qual cada cliente individual as executou.
Cliente 1 Cliente 2
setBalanceB(x, 1), 
setBalanceA(y, 2).
getBalanceA(y) → 0
getBalanceA(x) → 0
Modelo de tolerância à falhas baseado 
em replicação passiva (backup primário)
FEC
FEC
RM
Primary
Backup
Backup
RM
RM
DECSI/ICEA UFOP
40
Replicação passiva (backup primário)
• Um único GR trabalha como primário e os demais
como secundários – backups ou escravos.
• Os FE se comunicam somente com o GR primário.
• GR primário executa as operações e envia cópias dos
dados atualizados para os backups.
• Se o primário falhar, um dos backups será promovido
para atuar como primário.
• A sequência de eventos quando um cliente solicita
uma operação é:
DECSI/ICEA UFOP
41
Replicação passiva (backup primário)
• Requisição: é encaminhada pelo FE para o RM primário e possui um
único identificador de requisição.
• Coordenação: o RM primário trata todas as requisições atomicamente,
em ordem, checa o id (reenvia resposta se não é novo identificador).
• Execução: RM primário executa as requisições e armazena as respostas.
• Acordo/Consenso: se é atualização, RM primário envia estado
atualizado/resultado do objeto, identificador de requisição e resposta
para todos os RM de backups. Os GR´s de backup enviam uma
confirmação.
• Resposta: RM primário envia resposta ao FE, que envia resposta de volta
para o cliente.
DECSI/ICEA UFOP
42
Tolerância à falhas na replicação 
passiva
• Implementa linearização;
• Se GR primário falha, um backup se torna o líder por
eleição e as GR´s que sobreviveram concordam sobre o
conjunto de operações que foram realizados até o
ponto em que o novo líder assume
• requisito é alcançado se as GR estão organizadas como um
grupo e a réplica primária utiliza visão síncrona de grupo para
comunicar updates
• O sistema permanece linearizável após a queda do
servidor primário.
DECSI/ICEA UFOP
43
Replicação passiva - desvantagens
• Acarreta sobrecargas relativamente grandes;
• A comunicação de modo de visualização síncrono
exige várias rodadas de comunicação por multicast
e, se o GR primário falhar, ainda mais latência será
acarretada.
DECSI/ICEA UFOP
44
Replicação Ativa
FE CFEC RM
RM
RM
DECSI/ICEA UFOP
45
Replicação Ativa
• Os GR´s são máquinas de estado que desempenham papéis
equivalentes e são organizados como um grupo.
• Os FE´s enviam suas requisições por multicast para o grupo
de GR´s, e todos processam a requisição
independentemente, mas de forma idêntica, e respondem.
• Se qualquer GR falhar, isso não tem nenhum impacto sobre
o desempenho do serviço, pois o GR´s restantes continuam
a responder normalmente.
• A sequência de eventos após uma solicitação é a seguinte:
DECSI/ICEA UFOP
46
Replicação Ativa
1. Requisição: contém um identificador único e é enviada pelo FE
por multicast confiável ordenado a todos os GR.
2. Coordenação: comunicação de grupo garante que as
requisições são entregues a cada GR na mesma ordem (pode
ser em instantes físicos diferentes)
3. Execução: cada réplica executa a requisição (réplicas corretas
retornam a mesma resposta). A resposta contém o
identificador de requisição exclusiva do cliente.
4. Acordo/consenso: não é necessário acordo, devido às
primitivas semânticas do multicast.
5. Resposta: cada GR envia a resposta diretamente para o FE.
DECSI/ICEA UFOP
47
Tolerância à falhas na Replicação Ativa
• GR´s exercem papeis equivalente -> respondem a uma
sequencia de requisições da mesma forma.
• Se alguma GR cai, o estado é mantido pelas demais GRs
corretas.
• Ordenação total de requisições garante que todas as réplicas
executem a mesma sequência de requisições.
• Cada requisição do FE é executada na ordem FIFO, porque o FE
espera pela resposta para fazer nova requisição, que é igual à
ordem do programa. Isso garante a consistência sequencial.
DECSI/ICEA UFOP
48
Consistência Sequencial – Replicação Ativa
• O sistema de replicação ativa não obtém capacidade de
linearização. Isso porque a ordem total na qual os
gerenciadores de réplica processam as requisições não
é necessariamente igual à ordem de tempo real na qual
os clientes as fizeram.
• Em um sistema síncrono com relógios
aproximadamente sincronizados, a ordem total na qual
os gerenciadores de réplica processam requisições
pode ser baseada na ordem dos carimbos de tempo
físicos fornecidos pelos front-ends em suas requisições.
• Isso não garante a capacidade de linearização, pois os
carimbos de tempo não são perfeitamente precisos;
mas se aproxima disso.
DECSI/ICEA UFOP
49
Estudos de caso de 
Serviços de Alta Disponibilidade
Próxima aula
DECSI/ICEA UFOP
50
Dúvidas???
DECSI/ICEA UFOP
carla.lara@ufop.edu.br
51