Cap. 8
Processamento de Transacções,
Recuperação de Dados e Controlo
de Concorrência
“I always say, keep a diary and someday it’ll keep you.”
-- Mae West
Abel J.P. Gomes
Bibliografia:
1. R. Ramakrishnan and J. Gehrke. “Database Management Systems”. Addison-Wesley,
2003 (cap.18, 19 e 20).
1
1. Sumário















Introdução às transacções. Propriedades ACID.
Requisitos para a consistência duma base de dados.
Transacção como unidade de recuperação de dados.
Situações que requrem recuperação de dados.
Recuperação a partir duma falha numa transacção.
Estados da transacção. Entradas no system log.
Execução duma transacção. Operações de R/W duma transacção.
Checkpoints no system log. Logging com escrita à cabeça
(Write Ahead Logging).
Transacção como unidade de concorrência.
Algoritmos de escalonamento de transacções.
Escalas de transacções. Métodos de seriação/seriabilidade.
Técnicas de trancamento (Locking) para controlo de concorrência.
Tipos de fechos/trancamentos. Fechos e seriabilidade.
“Deadlocks” e “livelocks”.
Outras estratégias de controlo da concorrência e recuperação de
dados.
2
2. O que é uma transacção?

Uma transacção é uma unidade lógica básica de execução
num sistema de informação. É uma sequência de operações
que são executadas como um todo que leva uma base de
dados dum estado consistente para outro.

Uma unidade indivisível de processamento
base de dados num
estado consistente
Account A Fred Bloggs £1000
base de dados num
estado consistente
Transfer £500
Account B Sue Smith £0
begin Transaction
Account A Fred Bloggs £500
Account B Sue Smith £500
execution of Transaction
end Transaction
A base de dados pode
ficar temporariamente
num estado inconsistente
durante a execução
3
3. Propriedades ACID das transacções
Para preservar a integridade dos dados, o DBMS tem de assegurar:
Atomicidade. Uma transacção é unidade atómica de processamento
que é realizada completamente ou, simplesmente, não é
realizada.
Consistência. A execução isolada duma transacção (i.e. com
nenhuma outra transacção a executar concorrentemente)
preserva a consistência da base de dados.
Isolamento/Independência. As actualizações feitas por uma
transacção são obrigatoriamente invisíveis para outras
transacções enquanto não atinje o estado COMMITTED (o que
resolve o problema da actualização temporária ou temporary
update problem)
Durabilidade. Se uma transacção altera a base de dados e é
COMMITTED, as alterações nunca se perdem mesmo que ocorra
uma falha posterior.
Seriabilidade. Várias transacções são consideradas serializáveis se o
efeito de executá-las duma forma entrelaçada é equivalente a
executá-las em série segundo alguma ordem. Esta propriedade é
importante para garantir a consistência dos dados.
4
4. Requisitos para a consistência duma base
de dados

Controlo da Concorrência




A maioria dos DBMSs são sistemas multi-utilizador.
A execução concorrente de transacções submetidas por vários
utilizadores tem de ser organizada de tal modo que cada
transacção não interfere com as restantes, pois só assim se
pode garantir que não há resultados incorrectos.
A execução concorrente de transacções tem de ser tal que cada
transacção pareça estar a executar isoladamente.
Recuperação de Dados

Falhas do sistema, quer por hardware quer por software, não
poderão deixar a base de dados num estado inconsistente.
5
5. Transacção como Unidade de
Recuperação de Dados

Se um erro ou crash de hardware/software ocorre entre o
início e o fim duma transacção, a DB ficará inconsistente









Falha do computador (crash do sistema)
Um erro do sistema ou da transacção
Erros locais ou condições de excepção detectadas pela
transacção
Reforço do controlo da concorrência
Falha do disco
Problemas físicos e catástrofes
A DB é restaurada de volta a algum estado anterior correcto
—perto do instante da falha— de forma a poder refazer as
operações após o instante da falha.
O DBMS assegura que se a transacção executa algumas
actualizações e depois ocorre uma falha antes do seu
término, então aquelas actualizações são desfeitas.
As instruções COMMIT e ROLLBACK (ou seus equivalentes)
garantem a atomicidade da transacção
6
6. Recuperação de Dados

Duplicação de Dados (Mirroring)


Salvaguarda Periódica de Dados (Backup)


Manter duas cópias da DB simultaneamente
Salvaguardar (dump) periodicamente uma cópia da DB num
suporte de memória terciária (fita magnética, DVDs, etc)
Registo de Transacções c/ Actualizações (System Logging)

O log regista todas as operações envolvidas numa transacção que
afectam os dados duma DB. O log é guardado em disco de tal
forma que ele não é afectado por falhas, com excepção das
falhas do próprio disco e das catástrofes.
7
7. Recuperação a partir duma Falha numa
Transacção
Falha Catastrófica



Restaura uma cópia anterior da DB a partir dum backup arquivado
Aplica o transaction log à cópia para reconstruir a DB desde o estado
corrente arquivado na cópia até ao instante da falha. É óbvio que só
as transacções COMMITTED registadas no log serão refeitas.
Dump incremental + log cada transacção
Falha Não-Catastrófica



Inverte as operações que causaram inconsistência, desfazendo-as e,
possivelmente, refazendo alterações legítimas que se perderam.
As entradas ou verbetes registados no system log são consultadas
durante a recuperação de dados.
Não há necessidade de usar uma cópia completa de arquivo da DB.
8
8. Estados da Transacção







Veja-se diagrama
mais à frente!
Para efeitos de recuperação de dados, o sistema precisa de
registar quando uma transacção começa, é consignada
(committed) e termina.
Begin_Transaction: marca o início de execução da transacção;
End_Transaction: especifica que as operações de R/W
terminaram e marca o fim de execução da transacção (mas
pode ser ser abortada pelo controlo da concorrência);
Commit_Transaction: assinala o fim bem-sucedido duma
transacção. Quaisquer actualizações executadas pela
transacção podem ser consignadas (committed) para a DB
com segurança e não serão desfeitas;
Rollback (ou Abort): assinala que a transacção chegou ao fim
sem sucesso. Quaisquer alterações que a transacção tenha
causado na DB serão desfeitas;
Undo: semelhante ao estado ROLLBACK, mas aplica-se a
uma só operação em vez de uma transacção como um todo;
Redo: especifica que certas operações duma transacção têm
de ser refeitas para garantir que todas as operações duma
transacção consignada (committed) foram aplicadas com 9
sucesso a uma DB;
9. Entradas no System Log
Qualquer transacção tem um transaction-id
único gerado pelo sistema.

[start_transaction, transaction-id]: o
o início de execução duma transacção é
identificado pelo transaction-id.

[read_item, transaction-id, X]: a
transacção identificada pelo transaction-id
lê o valor do item X da DB. É opcional em
alguns protocolos.

[write_item, transaction-id, X,
old_value, new_value]: a transacção
identificada pelo transaction-id altera o
valor do item X da DB de old_value para
new_value.

[commit, transaction-id]: a transacção
identificada pelo transaction-id completou
todos os acessos à DB com sucesso e o
seu efeito pode ser gravado
permanentemente (committed).

[abort, transaction-id]: a transacção
identificada pelo transaction-id abortou.
Credit_labmark (sno NUMBER,
cno CHAR, credit NUMBER)
old_mark NUMBER;
new_mark NUMBER;
SELECT labmark INTO old_mark
FROM enrol
WHERE studno = sno and
courseno = cno FOR UPDATE OF
labmark;
new_ mark := old_ mark +
credit;
UPDATE enrol SET labmark =
new_mark WHERE studno = sno
and courseno = cno ;
COMMIT;
EXCEPTION
WHEN OTHERS THEN
ROLLBACK;
END credit_labmark;
10
10. Execução duma Transacção
Uma transacção atinge o seu commit point quando todas as
operações que acedem à DB estão completas e o resultado
gravado no log. Ela então escreve um [commit, transaction-id].
BEGIN
TRANSACTION
active
READ, WRITE
END
TRANSACTION
partially
committed
ROLLBACK
COMMIT
committed
ROLLBACK
failed
terminated
Se ocorre uma falha do sistema, procura e rollback as transacções que
tinham sido gravadas no log com
[start_transaction, transaction-id]
[write_item, transaction-id, X, old_value, new_value]
mas não gravadas com [commit, transaction-id]
11
11. Operações de R/W duma Transacção

read_item(X):

Lê um item X duma DB para uma variável X dum programa:
1. encontra o endereço do bloco em disco que contém o item X
2. copia aquele bloco em disco para um buffer em memória principal
3. copia item X do buffer para a variável X do programa

write_item(X):

Escreve o valor da variável X do programa para o item X da DB:
1. encontra o endereço do bloco em disco que contém o item X
2. copia aquele bloco em disco para um buffer em memória principal
3. copia item da variável X do programa para a sua localização corrente
no buffer e armazena o bloco actualizado no disco (este passo
actualiza a DB em disco)
X:=
X
12
12. Checkpoints no System Log




Um registo de [checkpoint] é escrito
periodicamente no log quando o sistema
escreve para a DB em disco o efeito de todas
as operações de escrita (WRITE) de
transacções consignadas (committed
transactions).
Todas as transacções cujas entradas ou
verbetes [commit, transaction-id] podem
ser encontradas no system log não requererão
que as suas operações WRITE sejam refeitas
no caso de haver um system crash.
Antes de uma transacção atingir o commit
point, força-se a escrita do ficheiro log para o
disco.
Acções que constituem um checkpoint:




suspensão temporária da execução da transacção
escrita forçada para disco de todos os blocos
actualizados da DB existentes nos buffers em
RAM
escrita de um registo de [checkpoint] para o log e
escrita forçada do log para o disco
retoma da execução da transacção
data
log
13
13. Logging com Escrita à Cabeça
(Write Ahead Logging)
Actualização Imediata :
Actualização Deferida:

1.
2.
3.
4.
Nenhuma actualização real
da DB antes da transacção
atingir o seu commit point

Actualizações gravadas no log
Transaction commit point
Força log para o disco
Actualiza DB
FALHA!
•Refaz (REDO) base de
dados a partir das
entradas no log.
•Não é necessário
qualquer operação de
desfazer (UNDO) porque
a DB não foi alterada.
1.
2.
3.
4.
3.
4.
A DB pode ser actualizada
por algumas operações duma
transacção antes dela atingir
o seu commit point.
Actualiza X gravado no log
Actualiza X na DB
Actualiza Y gravado no log
Transaction commit point
Força log para o disco
Actualiza Y na DB
FALHA!
REDO Y
FALHA!
UNDO X
• desfaz na ordem inversa do log
• refaz na ordem do log committed
• usa a entrada write_item do log 14
14. Transacção como Unidade de
Concorrência

Account B Sue Smith £0
T1
Transfere £500
de A para B
Account A Fred Bloggs £500
Account B Sue Smith £500
Account A Fred Bloggs £1000
Account C Jill Jones £700
T2
Transfere £300
de C para A
Account A Fred Bloggs £800
Account C Jill Jones £400
Execução Simultânea
Transacções têm de ser sincronizadas correctamente para garantir a
consistência da DB
Resultado Final
Account A 800
Account B 500
Account C 400
15
15. Algoritmos de Escalonamneto de
Transacções

Seriabilidade de Transacções

A execução de qualquer número de transacções em paralelo tem
de ter o mesmo efeito sobre uma DB que executá-las em série.
≡

Problemas resultantes da execução concorrente de
transacções:



Problema da Actualização Perdida (The Lost Update Problem)
Problema da Leitura Irrepetida (The Incorrect Summary or
Unrepeatable Read Problem)
Problema da Actualização Temporária (The Temporary Update
Problem or Dirty Read Problem)
16
15.1 Problema da Actualização Perdida

Duas transacções que acedem ao mesmo item X duma DB
têm as suas operações entrelaçadas de tal forma que tornam
o item incorrecto.
T1: (joe)
T2: (fred)
read_item(X);
X:= X - N;
X
4
2
read_item(X);
X:= X + M;
write_item(X);
read_item(Y);


4
7
2
8
write_item(X);
Y:= Y + N;
write_item(Y);
Y
7
10
10
O item X tem valor incorrecto porque a sua actualização em
T1 “perde-se” por efeito de re-escrita (overwritten).
T2 lê o valor de X antes de T1 mudá-lo na DB e daí resulta a
perda do seu valor actualizado na DB.
17
15.2 The Incorrect Summary or
Unrepeatable Read Problem


One transaction is calculating an aggregate summary function on a
number of records while other transactions are updating some of
these records.
The aggregate function may calculate some values before they are
updated and others after.
T1:
read_item(X);.
X:= X - N;
write_item(X);
T2:
sum:= 0;
read_item(A);
sum:= sum + A;
.
.
T1

Sum
0
4
4
4
2
2
read_item(X);
sum:= sum + X;
read_item(Y);
sum:= sum + Y;
read_item(Y);
Y:= Y + N;
write_item(Y);
T2
2
6
8
14
8
10
10
T2 reads X after N is subtracted and reads Y before N is added, so a wrong
18
summary is the result
15.3 Dirty Read
or The Temporary Update Problem

One transaction updates a database item and then the transaction
fails. The updated item is accessed by another transaction before it is
changed back to its original value
T1: (joe)
Joe books seat on flight X
T2: (fred)
read_item(X);
X:= X - N;
write_item(X);
Database
4
2
2
read_item(X);
X:= X- N;
write_item(X);
Joe cancels
failed write (X)
4
Fred books
seat on flight
X because Joe
was on Flight
X


Log
old
Log
new
4
2
2
-1
-1 2
-1
rollback T1
log
transaction T1 fails and must change the value of X back to its old
value
19
meanwhile T2 has read the “temporary” incorrect value of X
16. Escalas de Transacções



Uma escala S de n transacções é uma sequência das
operações destas transacções.
 as transacções podem ser entrelaçadas
Uma escala mantém a ordem das operações dentro de cada
transacção.
 Para cada transacção T, se a operação a é realizada em T
antes da operação b, então a será realizada antes de b em
S.
Duas operações são conflituosas se elas pertencem a
diferentes transacções, e acedem ao mesmo item de dados e
uma delas é uma operação de escrita.
S
T1
T2
read x
write x
read x
write x
read x
read x
write x
write x
20
16. Escala Seriada
e Escala Não-Seriada

Uma escala S é em seriada se, para qualquer transacção T
que participa na escala, todas as operações de T são
executadas consecutivamente em S; caso contrário, diz-se
que a escala é não-seriada.

Nas escalas não-seriadas, as transacções são entrelaçadas.
Existem muitas ordens possíveis or escalas.

A teoria da seriabilidade tenta determinar a 'correcção' das
escalas.

Uma escala S de n transacções é serializável se é equivalente
a alguma escala serial das mesmas n transacções.
21
16.1 Exemplos de Escalas Seriadas
Escala A
T1:
read_item(X);
X:= X - N;
write_item(X);
read_item(Y);
Y:=Y + N;
write_item(Y);
Escala B
T2:
T1:
read_item(X);
X:= X + M;
write_item(X);
read_item(X);
X:= X - N;
write_item(X);
read_item(Y);
Y:=Y + N;
write_item(Y);
T2:
read_item(X);
X:= X + M;
write_item(X);
22
16.2 Exemplos de Escalas Não-Seriada
Escala C
T1:
read_item(X);
X:= X - N;
T2:
read_item(X);
X:= X + M;
Escala D
T1:
read_item(X);
X:= X - N;
write_item(X);
read_item(X);
X:= X + M;
write_item(X);
write_item(X);
read_item(Y);
write_item(X);
Y:=Y + N;
write_item(Y);
T2:
read_item(Y);
Y:=Y + N;
write_item(Y);
Temos de determinar se uma escala é equivalente a
uma escala serial ou não
i.e. as leituras e escritas estão na ordem certa
23
17. Métodos de Seriação/Seriabilidade




Multi-versão. As técnicas de controlo de concorrência mantêm
os antigos valores do item de dados quando o item é
actualizado.
Selos de Tempo (timestamps). São identificadores únicos para
cada transacção e são gerados pelo sistema. As transacções
podem então ser ordenadas segundo os seus selos de tempo
de forma a garantir a seriabilidade.
Protocolos. Se forem seguidos por todas as transacções, os
protocolos asseguram a seriabilidade de todas as escalas em
que as transacções participam. Podem usar técnicas de
locking dos itens de dados para impedir que as várias
transacções acedam aos dados concorrentemente.
Controlo Pessimista da Concorrência
 Verifica se os itens de dados estão fechados (locked), ou
verifica os seus selos de tempo, antes de os ler ou
escrever em consequência de alguma operação que é
realizada sobre a DB.
24
18. Técnicas de Trancamento (Locking) para
Controlo de Concorrência





O conceito de trancamento de itens de dados é usado
numa das técnicas principais de controlo da execução
concorrente de transacções.
Um fecho (lock) é uma variável associada a um item
numa DB. Em geral, existe um fecho para cada item
numa DB.
Um fecho descreve o estado do item em relação a
possíveis operações que lhe podem ser aplicadas. É
usado para sincronizar o acesso de transacções
concorrentes transactions a itens da DB.
Uma transacção tranca um objecto antes de o usar.
Quando um objecto é trancado por uma transacção,
qualquer outra transacção que lhe tente aceder tem
obrigatoriamente de esperar que o objecto seja
libertado.
25
19. Tipos de Fechos



Fechos binários têm dois estados possíveis:
1. locked (através da operação lock_item(X)) e
2. unlocked (através da operação unlock_item(X))
Fechos multi-modo permitem o acesso concorrente ao
mesmo item por várias transacções. Têm três estados
possíveis:
1. read locked ou shared locked (outras transacções
podem ler o item)
2. write locked ou exclusive locked (uma única
transacção retém o item trancado) e
3. unlocked.
Os fechos são guardados numa tabela de fechos.
 upgrade lock: operação que comuta de read lock
para write lock
 downgrade lock: operação que comuta de write lock
para read lock
26
20. Os fechos não garantem seriabilidade:
caso da actualização perdida
T1: (joe)
T2: (fred)
write_lock(X)
read_item(X);
X:= X - N;
unlock(X)
Y
4
2
write_lock(X)
read_item(X);
X:= X + M;
unlock(X)
write_lock(X)
write_item(X);
unlock(X)
write_lock(Y)
read_item(Y);
X
4
7
2
8
write_lock(X)
write_item(X); 7
unlock(X)
Y:= Y + N;
write_item(Y);
unlock(Y)
10
10
27
21. Os fechos não garantem seriabilidade
X=20, Y=30
T1
read_lock(Y);
read_item(Y);
unlock(Y);
write_lock(X);
read_item(X);
X:=X+Y;
write_item(X);
unlock(X);
Y é destrancado demasiado cedo


T2
read_lock(X);
read_item(X);
unlock(X);
write_lock(Y);
read_item(Y);
Y:=X+Y;
write_item(Y);
unlock(Y);
X é destrancado demasiado cedo
Escala 1: T1 seguida por T2 ⇒ X=50, Y=80
Escala 2: T2 seguida por T1 ⇒ X=70, Y=50
28
22. Como assegurar a seriabiliade?:
Trancamento em Duas Fases (Two-Phase
Locking - 2PL)


Todas as operações de trancamento (read_lock, write_lock)
precedem a primeira operação de destrancamento nas
transacções.
Duas fases:


fase
mas
fase
mas
de expansão: novos fechos sobre itens podem ser activados,
nenhum pode ser libertado;
de contracção: os fechos existentes podem ser libertados,
nenhum pode ser activado.
X=20, Y=30
T1
read_lock(Y);
read_item(Y);
write_lock(X);
unlock(Y);
read_item(X);
X:=X+Y;
write_item(X);
unlock(X);
T2
read_lock(X);
read_item(X);
write_lock(Y);
unlock(X);
read_item(Y);
Y:=X+Y;
write_item(Y);
unlock(Y);
29
23. Trancamento em Duas Fases
(Two-Phase Locking - 2PL)

2PL básico:

quando uma transacção liberta um fecho, ela pode ou não
requerer outro fecho
lock point
number
of locks
Phase 1
BEGIN

obtain lock
release lock
Phase 2
END
2PL conservador ou 2PL estático:
 uma transacção tranca todos os itens que ela acede
antes do início da sua execução
30
 pré-declarando os conjuntos de reads e writes
23. Trancamento em Duas Fases
(cont.)

2PL estrito:


uma transacção não liberta nenhum dos seus fechos até
que ela consigne (commits) ou aborte
conduz a uma escala estrita para recuperação de dados
obtain lock
release lock
number
of locks
BEGIN
period of data END
item use
Transaction
duration
31
24. Deadlock: um problema resultante do
trancamento

Cada uma das duas ou mais transacções está à espera que
outra liberte um item. Também designado pelo abraço da
morte.
T1
read_lock(Y);
read_item(Y);
T2
read_lock(X);
read_item(X);
write_lock(X);
write_lock(Y);
32
25. Deadlocks e Livelocks

Protocoolo de prevenção de deadlocks:



Detecção de deadlock (se a carga da transacção é leve ou as
transacções são curtas e só tranca alguns poucos itens)




2PL conservador
Selos nas transacções (transacções mais recentes abortadas)
 nenhuma espera
 espera cautelosa
 esgotamento de tempo (time outs)
Grafo do tipo espera-por para detecção de deadlock
Selecção de víctima
Recomeça ciclicamente
Livelock: uma transacção não pode prosseguir por um período
indefinido de tempo enquanto outras transacções continuam
normalmente.

Esquemas de espera justa (i.e. first-come-first-served)
33
26. Granularidade do Trancamento

Um item duma base de dados pode ser:





um registo
o valor dum campo dum registo
um bloco do disco
a base de dados no seu todo
Compromissos (trafe-offs)


granularidade lata
 quanto maior o tamanho do item, menor é o grau da
concorrência
granularidade fina
 quanto menor o tamanho do item, maior número de
fechos são necessários gerir e armazenar e mais
operações de lock/unlock são necessárias.
34
Outras Estratégias de Controlo da Concorrência e
Recuperação de Dados
35
27. Recuperação de Dados:
Técnica de Paginação na Sombra




Os dados não são
actualizados ‘in place’
Para efeitos de recuperação
de dados, a base de dados é
vista como sendo constituída
por um número n de páginas
ou blocos de tamanho fixo.
Uma tabela de páginas com
n entradas é construída de
tal modo que a i-ésima
entrada na tabela aponta
para a i-ésima página da
base de dados em disco.
A tabela de páginas corrente
aponta para as páginas
correntes mais recentes da
base de dados em disco.
Database data
pages/blocks
page 5
Page table
1
2
3
4
5
6
page 1
page 4
page 2
page 3
page 6
36
27. Recuperação de Dados:
Técnica de Paginação na Sombra (cont.1)

Quando uma
transacção começa a
executar:




Database data pages (blocks)
a tabela de páginas Current page table
corrente é copiada
(after updating pages
para uma tabela de 2,6)
páginas na sombra
a tabela de páginas
1
na sombra é então
2
salvaguardada
3
a tabela de páginas
4
5
na sombra nunca é
6
alterada durante a
transacção
operações de
escrita— nova cópia
duma página é criada
e a entrada na tabela
corrente é modificada
de modo a apontar
para a nova
página/bloco do disco
page 5 (old)
page 1
Shadow page table
(not updated)
page 4
1
2
3
4
5
6
page 2 (old)
page 3
page 6
page 2 (new)
page 5 (new)
37
27. Recuperação de Dados:
Técnica de Paginação na Sombra (cont.2)



Para recuperar duma falha:
 o estado da DB antes
Database data pages (blocks)
da transacção está
disponível na tabela de Current page table
page 5 (old)
Shadowpage table
(after
updating
pages
páginas na sombra
(not updated)
2,6)
page 1
 liberta páginas
modificadas
page 4
1
1
2
 descarta tabelas de
2
3
page 2 (old)
3
páginas corrente
4
4
5
5
 Aquele estado é
page
3
6
6
recuperado por cópia
da tabela na sombra
page 6
para a tabela corrente
page 2 (new)
Consignar (commiting) uma
transacção
page 5 (new)
 descartar anterior
página na sombra
 libertar antigas tabelas
que ela referencia
38
Garbage collection
27. Conclusões
A gestão de transacções lida com dois requisitos chave
de qualquer sistema de bases de dados:

Resiliência


na capacidade dos dados sobreviverem a crashes de
hardware e erros de software sem perdas e sem ficar
inconsistente
Controlo de Acesso

na capacidade de permitir acesso simultâneo aos dados
por vários utilizadores duma forma consistente e só com
acesso autorizado
39 FIM