Upload
internet
View
107
Download
0
Embed Size (px)
Citation preview
Transações Atômicas Distribuídas
Prof. Alcides Calsavarahttp://www.ppgia.pucpr.br/~alcides
2
Conteúdo
Armazenamento em memória estável Primitivas de transação Propriedades de transações Implementação de transações
• Espaço de trabalho privado• Log• Protocolo de commit em duas fases
Controle de concorrência
• Locking• Controle otimista
Transações encaixadas e distribuídas Memória estável
3
Transações em SD
Abstração em alto nível para ocultar:
• uso de semáforos para controle de concorrência
• prevenção de deadlocks
• recuperação de falhas Vantagem: programadores concentram-se nos
algoritmos das aplicações. Sinônimos: atomic transaction, transaction,
atomic action.
4
Exemplo de transação
Um cliente, em um PC ligado por modem, faz transferência de fundos de uma conta bancária para outra, em dois passos:
(1) Saque(quantia, conta1)
(2) Deposite(quantia, conta2) Se a ligação telefônica cair entre os passos (1) e (2) o
dinheiro desaparece! Solução: passos (1) e (2) devem ocorrer como uma
transação atômica (como se fosse um único passo); se a ligação telefônia cair entre os passos (1) e (2), os efeitos do passo (1) devem ser cancelados.
5
Primitivas de transação
BEGIN_TRANSACTION: marca o início da transação END_TRANSACTION: termina a transação e tenta fazer
o commit ABORT_TRANSACTION: destrói a transação; restaura
os valores anteriores (do início da transação) READ: lê dados de um objeto (por exemplo, um arquivo) WRITE: escreve dados em um objeto
6
Exemplos de primitivas
BEGIN_TRANSACTION
reserve São Paulo - Salvador
reserve Salvador - Brasília
reserve Brasília - São Paulo
END_TRANSACTION
BEGIN_TRANSACTION
reserve São Paulo - Salvador
reserve Salvador - Brasília
reserve Brasília - São Paulo => ABORT_TRANSACTION
7
Propriedades de transações:ACID
Atomicidade: para o mundo externo, a transação ocorre de forma indivisível.
Consistência: a transação não viola invariantes de sistema.
Isolamento: transações concorrentes não interferem entre si (serializable).
Durabilidade: os efeitos de uma transação terminada com commit são permanentes.
8
Implementação de transações
Métodos de controle sobre modificações:• Espaço de trabalho privado
• Log
Protocolo de commit em duas fases
9
Espaço de trabalho privado
Um processo que começa uma transação cria um espaço contendo cópias de todos os objetos manipulados pela transação.
Se ocorrer commit, a transação repassa os novos valores dos objetos para os seus originais.
Problema: alto custo! Otimização: shadow blocks
Private Workspace
a) Índice de arquivo e blocos de disco para um arquivob) Situação após uma transação ter modificar o bloco 0 e adicionado o bloco 3c) Situação após o commit
11
Log
Writeahead log ou intentions list Os objetos originais são modificados durante a transação Antes de cada modificação, um registro é escrito em um
arquivo de log (em memória estável) Cada registro de log informa o valor anterior e o valor novo
de um objeto, além de informar que transação fez a modificação no objeto
Se ocorrer commit um registro apropriado é inserido no log Se ocorrer abort todas as operações efetuadas pela
transação são desfeitas com base no log, começando pelo último registro (rollback)
Writeahead Log
a) Um transaçãob) – d) O log antes da execução de cada comando
x = 0;
y = 0;
BEGIN_TRANSACTION;
x = x + 1;
y = y + 2
x = y * y;
END_TRANSACTION;
(a)
Log
[x = 0 / 1]
(b)
Log
[x = 0 / 1]
[y = 0/2]
(c)
Log
[x = 0 / 1]
[y = 0/2]
[x = 1/4]
(d)
13
Protocolo de commitem duas fases Two-phase commit protocol: 2PC A ação de commit deve ser “instantânea” e indivisível. Pode ser necessária a cooperação de muitos processos,
em máquinas distintas, cada qual com um conjunto de objetos envolvidos na transação.
Um dos processos é designado como coordenador (normalmente o próprio cliente que inicia a transação).
Os demais processos são designados como participantes.
Toda ação é registrada em log, armazenado em memória estável, para o caso de falha durante o protocolo.
14
Fases do 2PC
Fase 1: Votação• O coordenador envia mensagem VOTE_REQUEST para
todos os participantes e aguarda as respostas.• Cada participante responde VOTE_COMMIT ou
VOTE_ABORT para o coordenador. Fase 2: Decisão
• Se todos os participarem tiverem respondido VOTE_COMMIT, o coordenador envia para todos os participantes um GLOBAL_COMMIT senão envia um GLOBAL_ABORT.
• Cada participante confirma ou aborta a sua transação local, conforme receba GLOBAL_COMMIT ou GLOBAL_ABORT, respectivamente.
Fases do 2PC
a) Máquina de estados do coordenadorb) Máquina de estados de cada participante
Falhas durante o 2PC Coordenador pode ficar bloqueado em WAIT, aguardando os
votos dos participantes• Decide por abort se todos os votos não chegarem dentro de um certo
tempo. Participante pode ficar bloqueado em INIT, aguardando um
VOTE_REQUEST do coordenador• Vota por abort se o VOTE_REQUEST não chegar dentro de um certo
tempo. Participante pode ficar bloqueado em READY, aguardando a
decisão do coordenador• Se a decisão não chegar dentro de um certo tempo, consulta outros
participantes para descobrir qual foi a decisão.• Caso um participante consultado esteja bloqueado em INIT, a decisão é
por abort.• Caso todos os participantes estejam bloqueados em READY, o
protocolo bloqueia até que o coordenador se recupere.
17
Coordenador
escreva INIT no registro local;multicast VOTE_REQUEST para todos os participantes;escreva WAIT no registro local;
enquanto nem todos os votos dos participantes chegarem espere algum voto chegar; se temporização esgotar então escreva ABORT no registro local; multicast GLOBAL_ABORT para todos os participantes; termine; senão registre o voto que chegou;
se todos os participantes enviaram VOTE_COMMIT e o coordenador vota commit então escreva COMMIT no registro local; multicast GLOBAL_COMMIT para todos os participantes; senão escreva ABORT no registro local; multicast GLOBAL_ABORT para todos os participantes;
18
Participante: thread principal
escreva INIT no registro local;
espere VOTE_REQUEST do coordenador;se temporização esgotar então escreva ABORT no registro local; envie VOTE_ABORT para o coordenador; termine;se o participante vota commit então escreva READY no registro local; envie VOTE_COMMIT para o coordenador; espere decisão do coordenador; se temporização esgotar então multicast DECISION_REQUEST para outros participantes; espere até que uma decisão seja recebida; /* permaneça bloqueado */ se a decisão for GLOBAL_COMMIT então escreva COMMIT no registro local; senão se a decisão for GLOBAL_ABORT então escreva ABORT no registro local; senão escreva ABORT no registro local; envie VOTE_ABORT para o coordenador;
19
Participante: thread para atender requisições de decisão vindas de outros participantes
faça para sempre espere até receber alguma DECISION_REQUEST; /* permaneça bloqueado */ leia o último estado escrito no registro local; se o estado for COMMIT então envie GLOBAL_COMMIT ao participante requisitante; senão se o estado for ABORT ou INIT então envie GLOBAL_ABORT ao participante requisitante; senão não faça nada /* estado é READY */
Controle de concorrência
Controle de concorrência
22
Isolamento ou serializabilidade
BEGIN_TRANSACTIONx = 0;x = x + 1;
END_TRANSACTION
BEGIN_TRANSACTIONx = 0;x = x + 2;
END_TRANSACTION
BEGIN_TRANSACTIONx = 0;x = x + 3;
END_TRANSACTION
23
Escalonamentos (schedules)
Escalon. 1 Escalon. 2 Escalon. 3
x = 0; x = 0; x = 0;x = x + 1; x = 0; x = 0;x = 0; x = x + 1; x = x + 1;x = x + 2; x = x + 2; x = 0;x = 0; x = 0; x = x + 2;x = x + 3; x = x + 3; x = x + 3;
Legal Legal Ilegal
24
Locking
Um gerente centralizado ou distribuído registra todos os locks e rejeita pedidos de lock em objetos já alocados a outros processos
lock para escrita deve ser exclusivo, mas lock para leitura pode ser compartilhado
Quanto menor a granularidade do lock maior a chance de paralelismo, mas também maior é a chance de deadlock
Lock em duas fases:
• growing: todos os locks são adquiridos
• shrinking: todos os locks são liberados Strict two-phase locking: a fase shrinking ocorre
“instantaneamente” (previne cascade aborts)
Two-Phase Locking
Two-phase locking.
Strict Two-Phase Locking
27
Controle Otimista
• Não há locking
• Os objetos são modificados sem preocupação com concorrência até o fim da transação
• Quando chegar o momento de commit, a transação verifica se outra transação modificou os mesmos objetos que ela tenha modificado
• Se não há conflito, então o commit é feito (repasse de objetos do espaço de trabalho privado), senão é feito um abort
Transações distribuídas
a) A nested transactionb) A distributed transaction
29
Transações encaixadas
A transação top-level cria sub-transações que executam em paralelo, em processadores distintos: melhor desempenho e programação mais simples.
Se uma transação top-level abortar, então todas as suas sub-transações também devem abortar.
Uma sub-transação herda todos os objetos controlados pela transação top-level.
Uma sub-transação faz cópia local de todos os objetos herdados e só repassa os novos valores destes objetos à transação top-level em caso de commit da sub-transação.
30
Memória estável
Informação armazenada em RAM é perdida se faltar energia ou se a máquina falhar.
Informação armazenada em disco é perdida se a cabeça do disco falhar.
Informação armazenada em memória estável sobrevive a tudo, exceto enchentes, terremotos, ...
Implementação típica: disco replicado.
Memória estável
(a) Memória estável: unidades 1 e 2 (escritas ocorrem nessa ordem)(b) Crash da unidade 2 após a unidade 1 ser atualizada(c) Bad spot