Replicação. Protocolos.
June 2, 2010
Sumário
Arquitectura
Protocolos baseados em Primário
Protocolos de Escrita Replicada
Protocolos para “client-centric consistency”
Leitura Adicional
Sumário
Arquitectura
Protocolos baseados em Primário
Protocolos de Escrita Replicada
Protocolos para “client-centric consistency”
Leitura Adicional
Replicação: Arquitectura Básica
I
Transparência é garantida principalmente pelo front end
I
I
stubs/proxies podem facilitar a transparência, embora . . .
Consistência é garantida através de algoritmos
distribuídos executados pelos replica managers.
Protocolos de Replicação
I
Primary-Copy
I
Replicated-Write
I
Para client-centric consistency
Sumário
Arquitectura
Protocolos baseados em Primário
Protocolos de Escrita Replicada
Protocolos para “client-centric consistency”
Leitura Adicional
Primary-Copy Protocol
I
I
Uma das réplicas é o primário e as outras são de apoio
(backup) – primary-backup.
Todas as operações são submetidas ao primário:
I
I
I
O primário executa a operação e submete-a ou os seus
resultados aos apoios, antes de responder.
Dependendo do modêlo de avarias, o primário poderá ter
que bloquear à espera da resposta dos apoios.
O primário é substituído por um apoio, que passa a ser o
novo primário, no caso de avaria.
Protocolos Primário-Apoio com Leitura Local
Client
Client
Primary server
for item x
W1
Backup server
W5
R1
W4
W4
W3
W3
W2
W4
W1. Write request
W2. Forward request to primary
W3. Tell backups to update
W4. Acknowledge update
W5. Acknowledge write completed
I
I
Data store
W3
R1. Read request
R2. Response to read
Operações de leitura podem ser feitas em qualquer réplica.
Operações de escrita são feitas no primário.
I
I
R2
Como no protocolo base, o primário propaga os resultados
aos apoios.
Permite um melhor desempenho, em especial se as
operações de leitura forem mais frequentes do que as
operações de escrita.
Protocolo Primário-Apoio com Escrita Local
Client
Client
Old primary
for item x
R1
New primary
for item x
R2
W1
W5
W4
W5
W4
W4
Data store
R1. Read request
R2. Response to read
Operações de escrita podem ser feitas em qualquer
réplica.
I
I
W5
W2
W1. Write request
W2. Move item x to new primary
W3. Acknowledge write completed
W4. Tell backups to update
W5. Acknowledge update
I
Backup server
W3
Mas só depois da réplica se tornar primário, i.e. o primário
é itinerante.
Permite melhorar o desempenho se:
I
I
A réplica escolhida estiver próximo do cliente.
A propagação dos resultados às réplicas ocorrer após um
conjunto de operações de escrita.
Sumário
Arquitectura
Protocolos baseados em Primário
Protocolos de Escrita Replicada
Protocolos para “client-centric consistency”
Leitura Adicional
Protocolos de Escrita Replicada
I
Operações de escrita são feitas em mais do que uma
cópia.
I
I
Nos protocolos à base de primário, operações de escrita
são executadas apenas no primário, sendo os resultados
propagados aos apoios.
Alguns protocolos:
I
I
Replicação activa (ou read-one, write-all);
Votação (Quorum Consensus).
Read-one/Write-all Protocol (Active Replication)
I
I
Nos protocolos baseados em primário, o primário tem que
propagar os resultados aos apoios, antes de responder ao
cliente, aumentando a latência do serviço.
No read-one/write-all protocol:
I
I
I
operações de leitura podem ser executadas por qualquer
réplica;
operações de escrita têm que ser executadas por todas as
réplicas, na mesma ordem.
Assume determinismo das réplicas:
I
o estado duma réplica depende apenas do estado inicial e
da sequência de operações que lhe são aplicadas.
Available Copies Protocol
I
No Read-one/Write-all Protocol se uma réplica estiver
avariada, não é possível executar operações de escrita.
I
A ideia no Available Copies Protocol é exigir que as
operações de escrita sejam executadas apenas nas
réplicas operacionais.
O primary-backup e o available copies podem ser usados
em redes que se partem:
I
I
Mas o acesso só é possível na partição com a maioria das
réplicas.
Quorum Consensus Protocols (1/3)
I
Este tipo de protocolos baseia-se no uso de quorums
I
I
conjuntos de réplicas
para realizar operações.
A propriedade fundamental destes quorums é:
I
se 2 operações podem interferir, então os respectivos
quorums devem ter elementos comuns.
Read quorum
A
B
C
D
A
B
C
D
A
B
C
D
E
F
G
H
E
F
G
H
E
F
G
H
I
J
K
L
I
J
K
L
I
J
K
L
NR = 3,
N W = 10
NR = 7,
NW = 6
NR = 1,
N W = 12
Write quorum
(a)
(b)
IMP.: b) não é correcto. Porquê?
(c)
Quorum Consensus Protocols (2/3)
I
I
Cada réplica mantém além do valor do “objecto” replicado
o seu número de versão.
Para realizar uma operação:
I
I
I
envia uma mensagem broadcast solicitando a versão do
objecto;
aguarda a recepção de respostas dum número suficiente
de réplicas
No caso duma operação:
Leitura lê o valor do objecto na réplica com o maior
número de versão;
Escrita escreve o valor do objecto num número suficiente
de réplicas, atribuindo-lhe uma versão superior a
qualquer das versões recebidas
I
É essencial garantir que o valor do objecto é escrito
num número suficiente de réplicas.
Quorum Consensus Protocols (3/3)
I
O Read-one/Write-all Protocol é um caso particular do
Quorum Consensus Protocol, no qual o read-quorum
requer 1 réplica (qualquer) e o write-quorum requer todas
as réplicas.
I
Em princípio, como operações de leitura são mais
frequentes do que operações de escrita, read-quorums
são menores do que write-quorums.
Há muitas variantes deste protocolo, visando
essencialmente:
I
I
I
I
minimizar o tamanho dos quorums para obter uma dada
disponibilidade;
algumas variantes suportam quorum sets dinâmicos.
Quorum Consensus Protocols funcionam com redes que
podem partir.
Sumário
Arquitectura
Protocolos baseados em Primário
Protocolos de Escrita Replicada
Protocolos para “client-centric consistency”
Leitura Adicional
Estado a Manter
WID Cada operação de escrita tem um identificador, atribuído
pelo servidor que aceita a operação, i.e. o primeiro servidor
a aplicar a operação.
Servidor Mantém o conjunto de identificadores de todas as
operações de escrita que conduziram ao estado da réplica.
(WS).
Cliente Mantém 2 conjuntos de WIDs para a sessão:
Read-Set (CRS) contendo os identificadores de todas as
operações de escrita relevantes para os valores lidos
durante a sessão.
I Em cada operação de leitura, o servidor tem que
retornar o conjunto com os WIDs das operações de
escrita relevantes.
Write-Set (CWS) contendo os identificadores das operações
de escrita que realizou durante a sessão.
I Em cada operação de escrita, o servidor tem que
retornar o WID respectivo.
Implementação de “read your writes”
Cliente
Operação de escrita Acrescenta o WID atribuído pelo servidor
ao CWS
Operação de leitura Duas alternativas:
1. Solicita ao servidor o seu WS
I
Se CWS 6⊂ WS, o cliente terá que escolher outro
servidor.
2. Envia o seu CWS ao servidor.
Servidor
No caso 2. acima, deverá verificar se CWS ⊂ WS. Em caso
negativo, tem duas alternativas:
1. Reenviar o pedido para outro servidor.
2. Actualizar o seu estado de modo a satisfazer a condição
acima.
Nota A implementação de “monotonic reads” é semelhante.
Implementação de “writes follow reads”
Cliente
Operação de leitura Actualiza o CRS.
Operação de escrita Duas alternativas:
1. Solicita ao servidor o seu WS
I
Se CRS 6⊂ WS, o cliente terá que escolher outro
servidor.
2. Envia o seu CRS ao servidor.
Servidor
No caso 2. acima, deverá verificar se CRS ⊂ WS. Em caso
negativo, tem 2 alternativas
1. Reenviar o pedido para outro servidor.
2. Actualizar o seu estado de modo a satisfazer a condição
acima.
I
Na propagação de operações de escrita entre servidores,
há que preservar a ordem destas operações.
Nota A implementação de “monotonic writes” é semelhante.
Vectores de Versão (1/2)
Problema: A implementação dos conjuntos de forma explícita
não é eficiente:
I Estado mantido pelos clientes e servidores cresce
indefinidamente.
I Necessidade de transferir alguns destes conjuntos entre
C e S.
Solução: Usar vectores de versão, um vector semelhante a
um vector clock, com um elemento por servidor.
I Cada servidor mantém um contador de versão da
réplica que mantém
I
Este contador deve ser incrementado sempre que o
servidor aceita uma operação de escrita.
Vectores de Versão (2/2)
Servidor
Mantém um vector de versão (Vi ) que representa o estado da
réplica que mantém.
Vi [j] representa as operações aceites pelo servidor j
aplicadas no servidor i
Obs. Vi [i] é o contador de versão do servidor i.
Obs. As operações aceites por um servidor remoto
deverão ser aplicadas pela mesma ordem.
Cliente
Mantém 2 vectores de versão por sessão:
I
Um para para memorizar as suas operações de escrita
(Wi ).
I
Um para memorizar as operações de escrita relevantes
para as suas operações de leitura (Ri )
Implementação de Read Your Writes com VV
Servidor
I
Verifica se Vi domina Wj , i.e. Vi ≥ Wj .
I
I
I
Em caso negativo, deverá actualizar a sua réplica.
A verificação poderia ser feita do lado do cliente.
Retorna um vector com as operações de escrita relevantes
(RW ).
I
Uma aproximação possível é Vi .
I
I
Pode causar dificuldades na localização dum servidor
suficientemente actualizado.
Convém mudar o menos possível de servidor durante uma
sessão.
Verificações da actualidade do servidor
podem ser omitidas após o primeiro pedido.
Cliente
I
Actualiza o seu vector de leitura Rj = max(Rj [i], RW ).
Implementação de Write Follows Reads com VV
Cliente
I
Verifica se Vi ≥ Rj (Assumindo que a verificação é feita no
cliente.)
I
I
Actualiza o seu vector de escrita Wj [i] = v
Efectivamente, o par (i, v ) é o WID da operação.
Servidor
I
Actualiza o seu contador de versão (Vi [i]), e retorna o seu
valor (v ).
Sumário
Arquitectura
Protocolos baseados em Primário
Protocolos de Escrita Replicada
Protocolos para “client-centric consistency”
Leitura Adicional
Leitura Adicional
I
Capítulo 7 de Tanenbaum e van Steen, Distributed
Systems, 2nd Ed.
I
I
I
Subsecção 7.5.2: Primary-based Protocols
Subsecção 7.5.3: Replicated-write Protocols
Secção 7.5.5: Implementing Client-Centric Consistency