Upload
gabriel-boechat
View
62
Download
0
Embed Size (px)
Citation preview
1Modelos de Consistncia e Replicao de Dados
Prof. Raul Ceretta Nunes
Curso de Cincia da ComputaoELC1018 - Sistemas Distribudos
2Introduo
SD adequado para replicao de dados Replicas devem ser mantidas consistentes Questes:
hO que significa consistncia de dados replicados?hQuais as maneiras para obter consistncia?hComo o desempenho afetado por diferentes modelos
de consistncia?hComo a consistncia implementada?
Forma de distribuio dos updates para as rplicas Forma de manter a consistncia (forte ou fraca)
3Razes para replicao
Duas razes:hConfiabilidade
colapso de processo dados inconsistentes (usar valor da maioria)
hDesempenho Escalabilidade atravs de servios replicados Reduo de trfego de rede atravs de rplicas mais
prximas Preo a pagar: gerenciamento das rplicas
para manter consistncia
4Objeto Remoto Compartilhado
Organizao composta por um objeto remoto distribudo que compartilhado por dois clientes.
5Objeto Remoto Compartilhado Objetos encapsulam dados e operaes sobre
dados Middleware gerencia distribuio de objetos
remotos (operaes so independentes dos dados)
Como proteger o objeto remoto contra acessos simultneos realizados por mltiplos clientes?hControlar no prprio objeto (ex: synchronized do Java)hControlar no middleware (ex: adaptador de objetos)
6Objeto Remoto Compartilhado
a) Objeto remoto capaz de controlar invocaes concorrentes.b) Objeto remoto que requer um adaptador de objeto para controlar
invocaes concorrentes.
7Replicao de Objeto Remoto
Objeto remoto compartilhado e replicado necessita de sincronizao adicional para garantir que invocaes concorrentes sejam resolvidas na ordem correta em cada rplica.
2 abordagens:hControlar sincronizao no objeto replicado.
Vantagem: uso de protocolo de replicao especfico.hControlar sincronizao no middleware
Vantagem: simplifica tarefa do desenvolvedor de aplicaes
8Replicao de Objeto Remoto
a) Um sistema distribudo para objetos cientes da replicao, quecontrolam sua replicao.
b) Um sistema distribudo responsvel pelo gerenciamento de replicao.
9Modelos de Consistncia
Centrado nos dadosHip: dados compartilhados
p/ mltiplos processos
Fortep/ read/write
Fracap/ srie de read/writevia variveis de sync
Estrita - write p/ ordem total temporal
Linear - write p/ ordem total baseada em relgio global
Seqencial - write p/ ordem total
Causal - write p/ ordem causalFIFO - write p/ ordem causal
Fraca - update p/ operaoRelease - update na liberaoEntry - update na entrada
Centrado no clienteHip: dados atualizados p/
um nico processo
Leituras monotnicas - reads em ordem temporalEscritas monotnicas - writes em ordem temporalLeituras vem escritasEscritas seguem leituras
10
Consistncia Estrita
Operao tem efeito instantneo em todos. Deve manter ordem temporal (relgio fsico). Impossvel de ser implementado.
Comportamento de dois processos operando sobre o mesmo dado:(a) Um armazenamento com consistncia estrita.(b) Um armazenamento que viola a consistncia estrita.
11
Consistncia Seqencial
Todos os processos observam as operaes na mesma ordem (ordem total).
Nada dito sobre o instante temporal fsico. Aplicado em memria compartilhada de sistemas
multiprocessados. Equivalente a serializabilidade transacional
(operao equivale a uma transao). A verificao de consistncia se d atravs da
anlise de histricos locais. Problema: tread + twrite ttransferncia
12
Consistncia Seqencial
(a) Um armazenamento com consistncia seqencial. (b) Um armazenamento com violao de consistncia seqencial.
13
Ex: Consistncia Seqencial
z = 1;print (x, y);
y = 1;print (x, z);
x = 1;print ( y, z);
Process P3Process P2Process P1
y = 1;x = 1;z = 1;print (x, z);print (y, z);print (x, y);
Prints: 111111
Signature:111111
y = 1;z = 1;print (x, y);print (x, z);x = 1;print (y, z);
Prints: 010111
Signature:110101
x = 1;y = 1;print (x,z);print(y, z);z = 1;print (x, y);
Prints: 101011
Signature:101011
(b)
x = 1;print ((y, z);y = 1;print (x, z);z = 1;print (x, y);
Prints: 001011
Signature:001011
(a)
Trs processos executando concorrentemente e 4 execues possveis.
14
Linearizabilidade
Mais fraco do que a consistncia estrita mas mais forte do que a consistncia seqencial.
Todos os processos observam as operaes na mesma ordem (ordem total) + timestamp.
Se ts op1(x) < ts op2(x) ento op1(x) op2(x) Utilizada para assistir verificao formal de
algoritmos concorrentes.
15
Consistncia Causal
Writes potencialmente relacionados devem ser vistos por todos na mesma ordem.
Writes concorrentes podem ser vistos em ordens diferentes.
Implementao via vetor de relgios lgicos.
16
Consistncia FIFO
Observa apenas a ordem das operaes no processo da operao.
Fcil de implementar, pois precisa apenas da incluso de um nmero de seqncia.
Em memria compartilhada distribuda chamado de PRAM Pipelined RAM.
17
Ex: Consistncia FIFO
y = 1;print (x, z);z = 1;print (x, y);x = 1;print (y, z);
Prints: 01
(c)
x = 1;y = 1;print(x, z);print ( y, z);z = 1;print (x, y);
Prints: 10
(b)
x = 1;print (y, z);y = 1;print(x, z);z = 1;print (x, y);
Prints: 00
(a)
18
Problema da Consistncia FIFO
Fraco a ponto de permitir a morte de ambos os processos concorrentes, o que no permitido com consistncia seqencial.
y = 1;if (x == 0) kill(P1);
x = 1;if (y == 0) kill(P2);
Process P2Process P1
19
Consistncia Fraca
Synchronization accesses are sequentially consistent. All synchronization accesses must be performed before a regular data access and vice versa (programmer-imposed consistency).
20
Consistncia Fraca na Sada
Same as weak consistency except that synchronization accesses must only be processor consistent with respect to each other.
21
Eventual Consistency
22
Monotonic Reads
a) A monotonic-read consistent data storeb) A data store that does not provide monotonic reads.
Se o processo l o valor de um item de dado x, qualquer operao de leitura sucessiva de x pelo processo ir retornar sempre o mesmo valor ou um valor mais recente.
The read operations performed by a single process P at two different local copies of the same data store.
23
Monotonic Writes
a) A monotonic-write consistent data store.b) A data store that does not provide monotonic-write consistency.
Uma operao de escrita por um processo sobre um item de dado x completada antes de qualquer operao de escrita sucessiva do mesmo processo.
The write operations performed by a single process P at two different local copies of the same data store
24
Monotonic Writes
Relao com o modelo FIFO:hEm ambos a ordem das operaes nos
processos mantida em qualquer local.hNo modelo FIFO so considerados vrios
processos concorrentes.hNo modelo Monotonic Write considerado
apenas um nico processo (cliente).
25
Read Your Writes
a) A data store that provides read-your-writes consistency.
b) A data store that does not.
O efeito de uma operao de escrita por um processo sobre um item de dado x sempre ser visto pela operao de leitura de x pelo mesmo processo.
26
Writes Follow Reads
a) A writes-follow-reads consistent data storeb) A data store that does not provide writes-follow-reads
consistency
Uma operao de escrita por um processo sobre um item de dado x que sucede uma operao de leitura de x pelo mesmo processo, ser resolvida sobre uma cpia de x que contm o valor lido ou um mais recente.
27
Posicionamento das Rplicas
A organizao lgica dos diferentes conjuntos de cpias de um dado armazenado dentro de trs anis concentricos.
Onde, quando e por quem os dados esto distribudos?
28
Rplicas Permanentes
Normalmente em pequeno nmero. Modelo de replicao esttica Exemplos:
hWeb server: replicao do servidor numa lan; ao chegar uma requisio, ela direcionada a uma das rplicas.
hSite web distribudo (Mirror): site distribudo geograficamente; clientes escolhem um site de uma lista.
hBanco de dados federados: BD distribudo e replicado.
29
Rplicas Iniciadas pelo Servidor
Modelo de replicao dinmica. Rplicas so criadas de acordo com a
necessidade. Ex: para melhorar desempenho No caso de servidor web, so tambm
conhecidas por push caches. Problema: decidir onde e quando rplicas
deveriam ser criadas ou deletadas.
30
Rplicas Iniciadas pelo Servidor
Contando acesso de diferentes clientes. Deciso baseada em threshold del(S,F)| rep(S,F)
31
Rplicas Iniciadas pelo Cliente
A rplica uma cache. A consistncia da rplica por conta do usr. Usado somente para melhorar desempenho. Na web, uma rplica pode ser compartilhada
por mais do que um cliente.
32
Propagao de Atualizaes
Abordagens para decidir o que propagar:hPropagar somente uma notificao de um
update. Muito update pouco read. Ex: protocolos de invalidao
hTransferir os dados de uma cpia para outra. Interessante quando h muitos updates e reads.
hPropagar a operao de atualizao para outras rplicas.
Replicao ativa
33
Pull versus Push Protocols
A comparison between push-based and pull-based protocols in the case of multiple client, single server systems.
Fetch-update timeImmediate (or fetch-update time)Response time at client
Poll and updateUpdate (and possibly fetch update later)Messages sent
NoneList of client replicas and cachesState of server
Pull-basedPush-basedIssue
34
Remote-Write Protocols (1)
Primary-based remote-write protocol with a fixed server to which all read and write operations are forwarded.
35
Remote-Write Protocols (2)
O princpio do protocoloprimrio-backup.
36
Local-Write Protocols (1)
Primary-based local-write protocol in which a single copy is migrated between processes.
37
Local-Write Protocols (2)
Primary-backup protocol in which the primary migrates to the process wanting to perform an update.
38
Active Replication (1)
The problem of replicated invocations.
39
Active Replication (2)
a) Forwarding an invocation request from a replicated object.b) Returning a reply to a replicated object.
40
Quorum-Based Protocols
Three examples of the voting algorithm:a) A correct choice of read and write setb) A choice that may lead to write-write conflictsc) A correct choice, known as ROWA (read one, write all)