Transações Atômicas
Distribuídas
Prof. Alcides Calsavara
http://www.ppgia.pucpr.br/~alcides
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
2
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.
3
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.
4
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
5
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
6
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.
7
Implementação de transações

Métodos de controle sobre
modificações:
• Espaço de trabalho privado
• Log

Protocolo de commit em duas fases
8
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
9
Private Workspace
a)
b)
c)
Índice de arquivo e blocos de disco para um arquivo
Situação após uma transação ter modificar o bloco 0 e
adicionado o bloco 3
Situação após o commit
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)
11
Writeahead Log
x = 0;
y = 0;
BEGIN_TRANSACTION;
x = x + 1;
y=y+2
x = y * y;
END_TRANSACTION;
(a)
Log
Log
Log
[x = 0 / 1]
[x = 0 / 1]
[y = 0/2]
[x = 0 / 1]
[y = 0/2]
[x = 1/4]
(b)
(c)
a) Um transação
b) – d) O log antes da execução de cada comando
(d)
Protocolo de commit
em 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.
13
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.
14
Fases do 2PC
a)
b)
Máquina de estados do coordenador
Máquina de estados de cada participante
Falhas durante o 2PC

Coordenador pode ficar bloqueado em WAIT, aguardando os
votos dos participantes
•

Participante pode ficar bloqueado em INIT, aguardando um
VOTE_REQUEST do coordenador
•

Decide por abort se todos os votos não chegarem dentro de um certo
tempo.
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.
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;
17
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
senão
se a decisão for
senão
escreva ABORT no
envie VOTE_ABORT
GLOBAL_COMMIT então escreva COMMIT no registro local;
GLOBAL_ABORT
então escreva ABORT
no registro local;
registro local;
para o coordenador;
18
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 */
19
Controle de concorrência
Controle de concorrência
Isolamento ou serializabilidade
BEGIN_TRANSACTION
x = 0;
x = x + 1;
END_TRANSACTION
BEGIN_TRANSACTION
x = 0;
x = x + 2;
END_TRANSACTION
BEGIN_TRANSACTION
x = 0;
x = x + 3;
END_TRANSACTION
22
Escalonamentos (schedules)
Escalon. 1
Escalon. 2
Escalon. 3
x = 0;
x = x + 1;
x = 0;
x = x + 2;
x = 0;
x = x + 3;
x = 0;
x = 0;
x = x + 1;
x = x + 2;
x = 0;
x = x + 3;
x = 0;
x = 0;
x = x + 1;
x = 0;
x = x + 2;
x = x + 3;
Legal
Legal
Ilegal
23
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)
24
Two-Phase Locking

Two-phase locking.
Strict Two-Phase Locking
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
27
Transações distribuídas
a)
b)
A nested transaction
A distributed transaction
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 subtransação.
29
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.
30
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