1

Cap. 8Processamento de Transacções,Recuperação de Dados e Controlode Concorrência

Abel J.P. Gomes

Bibliografia:1. R. Ramakrishnan and J. Gehrke. “Database Management Systems”. Addison-Wesley,

2003 (cap.18, 19 e 20).

“I always say, keep a diary and someday it’ll keep you.”-- Mae West

2

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.

3

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çõesque são executadas como um todo que leva uma base dedados dum estado consistente para outro.

Uma unidade indivisível de processamento

base de dados numestado consistente

A base de dados podeficar temporariamentenum estado inconsistentedurante a execução

begin Transaction end Transactionexecution of Transaction

Account A Fred Bloggs £1000

Account B Sue Smith £0 Account B Sue Smith £500

Account A Fred Bloggs £500Transfer £500

base de dados numestado consistente

4

3. Propriedades ACID das transacçõesPara 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. comnenhuma outra transacção a executar concorrentemente)preserva a consistência da base de dados.

Isolamento/Independência. As actualizações feitas por umatransacção são obrigatoriamente invisíveis para outrastransacções enquanto não atinje o estado COMMITTED (o queresolve o problema da actualização temporária ou temporaryupdate problem)

Durabilidade. Se uma transacção altera a base de dados e éCOMMITTED, as alterações nunca se perdem mesmo que ocorrauma falha posterior.

Seriabilidade. Várias transacções são consideradas serializáveis se oefeito de executá-las duma forma entrelaçada é equivalente aexecutá-las em série segundo alguma ordem. Esta propriedade éimportante para garantir a consistência dos dados.

5

4. Requisitos para a consistência duma basede 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 cadatransacção não interfere com as restantes, pois só assim sepode garantir que não há resultados incorrectos.

A execução concorrente de transacções tem de ser tal que cadatransacçã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.

6

5. Transacção como Unidade deRecuperação de Dados

Se um erro ou crash de hardware/software ocorre entre oiní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 asoperações após o instante da falha.

O DBMS assegura que se a transacção executa algumasactualizações e depois ocorre uma falha antes do seutérmino, então aquelas actualizações são desfeitas.

As instruções COMMIT e ROLLBACK (ou seus equivalentes)garantem a atomicidade da transacção

7

6. Recuperação de Dados Duplicação de Dados (Mirroring)

Manter duas cópias da DB simultaneamente

Salvaguarda Periódica de Dados (Backup) 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 talforma que ele não é afectado por falhas, com excepção dasfalhas do próprio disco e das catástrofes.

8

7. Recuperação a partir duma Falha numaTransacçãoFalha 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.

9

8. Estados da Transacção 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 (maspode ser ser abortada pelo controlo da concorrência);

Commit_Transaction: assinala o fim bem-sucedido dumatransacção. Quaisquer actualizações executadas pelatransacção podem ser consignadas (committed) para a DBcom segurança e não serão desfeitas;

Rollback (ou Abort): assinala que a transacção chegou ao fimsem sucesso. Quaisquer alterações que a transacção tenhacausado na DB serão desfeitas;

Undo: semelhante ao estado ROLLBACK, mas aplica-se auma só operação em vez de uma transacção como um todo;

Redo: especifica que certas operações duma transacção têmde ser refeitas para garantir que todas as operações dumatransacção consignada (committed) foram aplicadas comsucesso a uma DB;

Veja-se diagramamais à frente!

10

9. Entradas no System LogQualquer 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]: atransacção identificada pelo transaction-idlê o valor do item X da DB. É opcional emalguns protocolos.

[write_item, transaction-id, X,old_value, new_value]: a transacçãoidentificada pelo transaction-id altera ovalor do item X da DB de old_value paranew_value.

[commit, transaction-id]: a transacçãoidentificada pelo transaction-id completoutodos os acessos à DB com sucesso e oseu efeito pode ser gravadopermanentemente (committed).

[abort, transaction-id]: a transacçãoidentificada pelo transaction-id abortou.

Credit_labmark (sno NUMBER,cno CHAR, credit NUMBER)old_mark NUMBER;new_mark NUMBER;

SELECT labmark INTO old_markFROM enrolWHERE studno = sno andcourseno = cno FOR UPDATE OFlabmark;

new_ mark := old_ mark +credit;

UPDATE enrol SET labmark =new_mark WHERE studno = snoand courseno = cno ;

COMMIT;

EXCEPTION WHEN OTHERS THEN ROLLBACK;

END credit_labmark;

11

10. Execução duma Transacção

active partially committed

committed

failed terminated

BEGIN TRANSACTION

READ, WRITE

END TRANSACTION

ROLLBACK ROLLBACK

COMMIT

Uma transacção atinge o seu commit point quando todas asoperações que acedem à DB estão completas e o resultadogravado no log. Ela então escreve um [commit, transaction-id].

Se ocorre uma falha do sistema, procura e rollback as transacções quetinham 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]

12

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 X2. copia aquele bloco em disco para um buffer em memória principal3. 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 X2. copia aquele bloco em disco para um buffer em memória principal3. copia item da variável X do programa para a sua localização corrente

no buffer e armazena o bloco actualizado no disco (este passoactualiza a DB em disco)

XX:=

13

12. Checkpoints no System Log Um registo de [checkpoint] é escrito

periodicamente no log quando o sistemaescreve para a DB em disco o efeito de todasas operações de escrita (WRITE) detransacções consignadas (committedtransactions).

Todas as transacções cujas entradas ouverbetes [commit, transaction-id] podemser encontradas no system log não requererãoque as suas operações WRITE sejam refeitasno caso de haver um system crash.

Antes de uma transacção atingir o commitpoint, força-se a escrita do ficheiro log para odisco.

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 emRAM

escrita de um registo de [checkpoint] para o log eescrita forçada do log para o disco

retoma da execução da transacção

data

log

14

13. Logging com Escrita à Cabeça(Write Ahead Logging)

Actualização Deferida: Nenhuma actualização real

da DB antes da transacçãoatingir o seu commit point

1. Actualizações gravadas no log2. Transaction commit point3. Força log para o disco4. Actualiza DB

Actualização Imediata : A DB pode ser actualizada

por algumas operações dumatransacção antes dela atingiro seu commit point.

1. Actualiza X gravado no log2. Actualiza X na DB3. Actualiza Y gravado no log4. Transaction commit point3. Força log para o disco4. Actualiza Y na DB

FALHA!•Refaz (REDO) base dedados a partir dasentradas no log.•Não é necessárioqualquer operação dedesfazer (UNDO) porquea DB não foi alterada.

• desfaz na ordem inversa do log• refaz na ordem do log committed• usa a entrada write_item do log

FALHA!UNDO XFALHA!

REDO Y

15

14. Transacção como Unidade deConcorrência

Transacções têm de ser sincronizadas correctamente para garantir aconsistência da DB

Account A Fred Bloggs £1000

Account B Sue Smith £0

Account B Sue Smith £500

Account A Fred Bloggs £500

Transfere £500de A para B

Account C Jill Jones £700Account C Jill Jones £400

Account A Fred Bloggs £800

Transfere £300de C para A

Resultado Final Account A 800Account B 500Account C 400

T1

T2

Execução S

imultânea

16

15. Algoritmos de Escalonamneto deTransacçõ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 detransacçõ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)

≡

17

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 tornamo item incorrecto.

O item X tem valor incorrecto porque a sua actualização emT1 “perde-se” por efeito de re-escrita (overwritten).

T2 lê o valor de X antes de T1 mudá-lo na DB e daí resulta aperda do seu valor actualizado na DB.

T1: (joe) T2: (fred) X Y

read_item(X); 4X:= X - N; 2

read_item(X); 4X:= X + M; 7

write_item(X); 2read_item(Y); 8

write_item(X); 7Y:= Y + N; 10write_item(Y); 10

18

15.2 The Incorrect Summary orUnrepeatable Read Problem

One transaction is calculating an aggregate summary function on anumber of records while other transactions are updating some ofthese records.

The aggregate function may calculate some values before they areupdated and others after.

T2 reads X after N is subtracted and reads Y before N is added, so a wrongsummary is the result

T1: T2: T1 T2 Sumsum:= 0; 0read_item(A); 4sum:= sum + A; 4

read_item(X);. . 4X:= X - N; . 2write_item(X); 2

read_item(X); 2sum:= sum + X; 6read_item(Y); 8sum:= sum + Y; 14

read_item(Y); 8Y:= Y + N; 10write_item(Y); 10

19

15.3 Dirty Reador The Temporary Update Problem

One transaction updates a database item and then the transactionfails. The updated item is accessed by another transaction before it ischanged back to its original value

transaction T1 fails and must change the value of X back to its oldvalue

meanwhile T2 has read the “temporary” incorrect value of X

T1: (joe) T2: (fred) Database Logold

Lognew

read_item(X); 4X:= X - N; 2write_item(X); 2 4 2

read_item(X); 2X:= X- N; -1write_item(X); -1 2 -1

failed write (X) 4 rollback T1log

Joe books seat on flight X

Joe cancelsFred booksseat on flightX because Joewas on FlightX

20

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 cadatransacçã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 emS.

Duas operações são conflituosas se elas pertencem adiferentes transacções, e acedem ao mesmo item de dados euma delas é uma operação de escrita.

read xwrite x

T1

read xwrite x

T2 read xread xwrite xwrite x

S

21

16. Escala Seriadae Escala Não-Seriada

Uma escala S é em seriada se, para qualquer transacção Tque participa na escala, todas as operações de T sãoexecutadas consecutivamente em S; caso contrário, diz-seque 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' dasescalas.

Uma escala S de n transacções é serializável se é equivalentea alguma escala serial das mesmas n transacções.

22

16.1 Exemplos de Escalas Seriadas

Escala BEscala A

T1: T2: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);

T1: T2:read_item(X);X:= X - N;write_item(X);read_item(Y);Y:=Y + N;write_item(Y);

read_item(X);X:= X + M;write_item(X);

23

16.2 Exemplos de Escalas Não-Seriada

Escala DEscala C

T1: T2:read_item(X);X:= X - N;

read_item(X);X:= X + M;

write_item(X);read_item(Y);

write_item(X);Y:=Y + N;write_item(Y);

T1: T2:read_item(X);X:= X - N;write_item(X);

read_item(X);X:= X + M;write_item(X);

read_item(Y);Y:=Y + N;write_item(Y);

Temos de determinar se uma escala é equivalente auma escala serial ou não

i.e. as leituras e escritas estão na ordem certa

24

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 paracada transacção e são gerados pelo sistema. As transacçõespodem então ser ordenadas segundo os seus selos de tempode forma a garantir a seriabilidade.

Protocolos. Se forem seguidos por todas as transacções, osprotocolos asseguram a seriabilidade de todas as escalas emque as transacções participam. Podem usar técnicas delocking dos itens de dados para impedir que as váriastransacçõ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 ouescrever em consequência de alguma operação que érealizada sobre a DB.

25

18. Técnicas de Trancamento (Locking) paraControlo de Concorrência

O conceito de trancamento de itens de dados é usadonuma das técnicas principais de controlo da execuçãoconcorrente de transacções.

Um fecho (lock) é uma variável associada a um itemnuma DB. Em geral, existe um fecho para cada itemnuma DB.

Um fecho descreve o estado do item em relação apossíveis operações que lhe podem ser aplicadas. Éusado para sincronizar o acesso de transacçõesconcorrentes 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 temobrigatoriamente de esperar que o objecto sejalibertado.

26

19. Tipos de Fechos Fechos binários têm dois estados possíveis:

1. locked (através da operação lock_item(X)) e2.unlocked (através da operação unlock_item(X))

Fechos multi-modo permitem o acesso concorrente aomesmo item por várias transacções. Têm três estadospossí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) e3.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

27

20. Os fechos não garantem seriabilidade:caso da actualização perdida

T1: (joe) T2: (fred) X Y

write_lock(X)read_item(X); 4X:= X - N; 2unlock(X)

write_lock(X)read_item(X); 4X:= X + M; 7unlock(X)

write_lock(X)write_item(X); 2unlock(X)write_lock(Y)read_item(Y); 8

write_lock(X)write_item(X); 7unlock(X)

Y:= Y + N; 10write_item(Y); 10unlock(Y)

28

21. Os fechos não garantem seriabilidade

Y é destrancado demasiado cedo X é destrancado demasiado cedo

Escala 1: T1 seguida por T2 ⇒ X=50, Y=80 Escala 2: T2 seguida por T1 ⇒ X=70, Y=50

X=20, Y=30

T1 T2read_lock(Y); read_lock(X);read_item(Y); read_item(X);unlock(Y); unlock(X);write_lock(X); write_lock(Y);read_item(X); read_item(Y);X:=X+Y; Y:=X+Y;write_item(X); write_item(Y);unlock(X); unlock(Y);

29

22. Como assegurar a seriabiliade?:Trancamento em Duas Fases (Two-PhaseLocking - 2PL)

Todas as operações de trancamento (read_lock, write_lock)precedem a primeira operação de destrancamento nastransacções.

Duas fases: fase de expansão: novos fechos sobre itens podem ser activados,

mas nenhum pode ser libertado; fase de contracção: os fechos existentes podem ser libertados,

mas nenhum pode ser activado.

X=20, Y=30

T1 T2read_lock(Y); read_lock(X);read_item(Y); read_item(X);write_lock(X); write_lock(Y);unlock(Y); unlock(X);read_item(X); read_item(Y);X:=X+Y; Y:=X+Y;write_item(X); write_item(Y);unlock(X); unlock(Y);

30

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

2PL conservador ou 2PL estático: uma transacção tranca todos os itens que ela acede

antes do início da sua execução pré-declarando os conjuntos de reads e writes

obtain lockrelease lock

lock point

Phase 1 Phase 2BEGIN END

numberof locks

31

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

BEGIN END

numberof locks

Transactiondurationperiod of data

item use

32

24. Deadlock: um problema resultante dotrancamento

Cada uma das duas ou mais transacções está à espera queoutra liberte um item. Também designado pelo abraço damorte.

T1 T2read_lock(Y);read_item(Y);

read_lock(X);read_item(X);

write_lock(X);write_lock(Y);

33

25. Deadlocks e Livelocks Protocoolo de prevenção de deadlocks:

2PL conservador Selos nas transacções (transacções mais recentes abortadas)

nenhuma espera espera cautelosa esgotamento de tempo (time outs)

Detecção de deadlock (se a carga da transacção é leve ou astransacções são curtas e só tranca alguns poucos itens)

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íodoindefinido de tempo enquanto outras transacções continuamnormalmente. Esquemas de espera justa (i.e. first-come-first-served)

34

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 daconcorrência

granularidade fina quanto menor o tamanho do item, maior número de

fechos são necessários gerir e armazenar e maisoperações de lock/unlock são necessárias.

35

Outras Estratégias de Controlo da Concorrência eRecuperação de Dados

36

27. Recuperação de Dados:Técnica de Paginação na Sombra

Os dados não sãoactualizados ‘in place’

Para efeitos de recuperaçãode dados, a base de dados évista como sendo constituídapor um número n de páginasou blocos de tamanho fixo.

Uma tabela de páginas comn entradas é construída detal modo que a i-ésimaentrada na tabela apontapara a i-ésima página dabase de dados em disco.

A tabela de páginas correnteaponta para as páginascorrentes mais recentes dabase de dados em disco.

page 3

page 2

page 4

page 1

page 5

page 6

21

3456

Database datapages/blocks

Page table

37

27. Recuperação de Dados:Técnica de Paginação na Sombra (cont.1)

Quando umatransacção começa aexecutar: a tabela de páginas

corrente é copiadapara uma tabela depáginas na sombra

a tabela de páginasna sombra é entãosalvaguardada

a tabela de páginasna sombra nunca éalterada durante atransacção

operações deescrita— nova cópiaduma página é criadae a entrada na tabelacorrente é modificadade modo a apontarpara a novapágina/bloco do disco

page 5 (old)

page 1

page 4

page 2 (old)

page 3

page 6

page 2 (new)

page 5 (new)

21

3456

Current page table (after updating pages 2,6)

Database data pages (blocks)

21

3456

Shadow page table (not updated)

38

27. Recuperação de Dados:Técnica de Paginação na Sombra (cont.2)

Para recuperar duma falha: o estado da DB antes

da transacção estádisponível na tabela depáginas na sombra

liberta páginasmodificadas

descarta tabelas depáginas corrente

Aquele estado érecuperado por cópiada tabela na sombrapara a tabela corrente

Consignar (commiting) umatransacção descartar anterior

página na sombra libertar antigas tabelas

que ela referencia Garbage collection

page 5 (old)

page 1

page 4

page 2 (old)

page 3

page 6

page 2 (new)

page 5 (new)

213456

Current page table (after updating pages 2,6)

Database data pages (blocks)

213456

Shadow page table (not updated)

39

27. ConclusõesA gestão de transacções lida com dois requisitos chavede 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 ficarinconsistente

Controlo de Acesso na capacidade de permitir acesso simultâneo aos dados

por vários utilizadores duma forma consistente e só comacesso autorizado

FIM