Transações e Concorrência

Daniela Barreiro ClaroMATA-60

UFBA

2

◻Transação: programa em execução que forma uma unidade lógica de processamento que consiste de uma ou mais operações.

⬜ Exemplo: uma transferência de dinheiro entre duas contas executa uma transação consistente em duas atualizações, uma para cada conta.

Conceito de Transação

◻ É fundamental que todas as ações da transação sejam executadas completamente

◻ Caso contrário, os efeitos parciais devem ser desfeitos

◻ Ou seja, ou a transação inteira é executada ou nenhuma parte dela é executada

Conceito de Transação

3

◻ Para garantir a integridade dos dados, é necessário que o sistema de banco de dados mantenha as seguintes propriedades das transações:⬜ Atomicidade⬜ Consistência⬜ Isolamento⬜ Durabilidade

Propriedades ACID

4

◻ Atomicidade: todas as operações da transação são persistidas no banco de dados, ou nenhuma delas

◻ Consistência: a execução de uma transação mantém a consistência do banco de dados após sua execução

Propriedades ACID

5

◻ Isolamento: mesmo várias transações executando simultaneamente, o sistema garante que uma transação não interfere em outras. Cada transação é isolada.

◻ Durabilidade: depois que uma transação é completada com sucesso, as mudanças devem ser persistidas no banco de dados, não podendo ser desfeita

Propriedades ACID

6

Exemplo: transação bancária de 50 reais da conta A para a conta B, as operações seriam (Ti):

◻ read(A);◻ A = A - 50;◻ write(A);◻ read(B);◻ B = B + 50;◻ write(B);

Propriedades ACID

7

Exemplo: transação bancária de 50 reais da conta A para a conta B, as operações seriam (Ti):

◻ read(A);◻ A = A - 50;◻ write(A);◻ read(B);◻ B = B + 50;◻ write(B);

Propriedades ACID

8

Atomicidade

Suponha que antes de executar a transação Ti os valores

de A e B são R$ 100 e R$ 500, respectivamente. Durante

a execução de Ti acontece uma falha (energia, hardware

ou software) que impede Ti de completar com sucesso. A

falha acontece após a operação write(A), mas antes da

operação write(B). O que vai ocorrer?

- componente de gerenciamento de transação

Exemplo: transação bancária de 50 reais da conta A para a conta B, as operações seriam (Ti):

◻ read(A);◻ A = A - 50;◻ write(A);◻ read(B);◻ B = B + 50;◻ write(B);

Propriedades ACID

9

Consistência

O requisito de consistência é que a soma de A e B sejam

inalterados pela execução da transação. Qual o exemplo

que poderia causa inconsistência nos dados?

- programador de aplicação

- Restrições de integridade (SGBD)

Exemplo: transação bancária de 50 reais da conta A para a conta B, as operações seriam (Ti):

◻ read(A);◻ A = A - 50;◻ write(A);◻ read(B);◻ B = B + 50;◻ write(B);

Propriedades ACID

10

Isolamento

Considere que a transação Tj esteja efetuando um saque

de R$ 100 na conta A simultaneamente a transação Ti e

as contas não podem ficar com saldo negativo (Conta

Poupança). Caso Ti inicie antes de Tj e após read(A),

mas antes de write(A), a transação Tj seja completada

com sucesso, o que vai ocorrer?

- componente de controle de concorrência

Exemplo: transação bancária de 50 reais da conta A para a conta B, as operações seriam (Ti):

◻ read(A);◻ A = A - 50;◻ write(A);◻ read(B);◻ B = B + 50;◻ write(B);

Propriedades ACID

11

Durabilidade

O sistema deve garantir que os dados, mesmo após uma

falha, sejam persistidos no disco. No nosso exemplo, se o

usuário for notificado que a transação foi realizada com

sucesso, os dados devem ser armazenados no disco,

garantindo que em caso de falha no sistema

(principalmente por falta de energia) os dados não sejam

perdidos.

- componente de gerenciamento de recuperação

Estado da transação

12

Ativa

Parcialmente

confirmada

Falha Abortada

Confirmada

Enquanto estiver

executando

rollback

commit

Encerrada

◻ Quando ocorre uma falha na transação, ela é considerada abortada

◻ Quando há mudanças causadas por uma transação abortada tiverem sido desfeitas, dizemos que a transação foi revertida

◻ Uma transação que completa sua execução com sucesso é considerada confirmadaTransação confirmada só é desfeita por uma outra transação de compensação.

Estado da transação

13

◻ É muito mais fácil executar transações serialmente, ou seja, uma de cada vez

◻ Vantagens da execução concorrente:⬜ Aumento do número de transações executadas⬜ Melhor uso dos recursos computacionais⬜ Tempo de espera reduzido

◻ É preciso garantir a execução simultânea correta

Execuções simultâneas

14

◻ Representam a ordem cronológica em que as instruções são executadas

◻ Devem preservar a ordem em que as instruções aparecem em cada transação individual

◻ O schedule S de n transações T1, T2, ...Tn⬜ As operações em S devem ocorrer na mesma ordem

que em Ti

Planos de Execução (schedules)

15

◻ Um plano S com n transações é serializável se ele for equivalente a um plano serial.

◻ Um plano não-serializável não se garante que o mesmo seja correto.

◻ Exemplo: Transferência bancária entre duas contas, conta A com R$ 1000,00 e conta B com R$ 2000,00.⬜ Transação 1: A transfere R$ 50,00 para B⬜ Transação 2: A transfere 10% do valor da conta para B

Planos de Execução

16

Planos seriais (sequenciais)

17

T1 T2

read(A)

A = A - 50

write(A)

read(B)

B = B + 50

write(B)

read(A)

temp = A * 0.1

A = A - temp

write(A)

read(B)

B = B + temp

write(B)

A = 1000

A = 1000 - 50

A = 950

B = 2000

B = 2000 + 50

B = 2050

A = 950

temp = 950 * 0.1

A = 950 - 95

A = 855

B = 2050

B = 2050 + 95

B = 2145

T3 T4

read(A)

A = A - 50

write(A)

read(B)

B = B + 50

write(B)

read(A)

temp = A * 0.1

A = A - temp

write(A)

read(B)

B = B + temp

write(B)

A = 900

A = 900 - 50

A = 850

B = 2100

B = 2100 + 50

B = 2150

A = 1000

temp = 1000 * 0.1

A = 1000 - 100

A = 900

B = 2000

B = 2000 + 100

B = 2100

A = 1000

B = 2000

Soma = 3000

A = 855

B = 2145

Soma = 3000

A = 850

B = 2150

Soma = 3000

Planos não seriais (intercalados)

T1 T2

read(A)

A = A - 50

write(A)

A = 950

temp = 950 * 0.1

A = 950 - 95

A = 855

read(B)

B = B + 50

write(B)

B = 2050

B = 2050 + 95

B = 2145

A = 1000

A = 1000 - 50

A = 950

read(A)

temp = A * 0.1

A = A - temp

write(A)

B = 2000

B = 2000 + 50

B = 2050

read(B)

B = B + temp

write(B)

T3 T4

read(A)

A = A - 50

A = 1000

temp = 1000 * 0.1

A = 1000 - 100

A = 900

B = 2000

write(A)

read(B)

B = B + 50

write(B)

B = 2050 + 100

B = 2150

A = 1000

A = 1000 - 50

read(A)

temp = A * 0.1

A = A - temp

write(A)

read(B)

A = 900

B = 2000

B = 2000 + 50

B = 2050

B = B + temp

write(B)

A = 1000

B = 2000

Soma = 3000

A = 855

B = 2145

Soma = 3000

A = 900

B = 2150

Soma = 3050

Serializável ou não?

T1 T2

read(A)

A = A - 50

write(A)

A = 950

temp = 950 * 0.1

A = 950 - 95

A = 855

read(B)

B = B + 50

write(B)

B = 2050

B = 2050 + 95

B = 2145

A = 1000

A = 1000 - 50

A = 950

read(A)

temp = A * 0.1

A = A - temp

write(A)

B = 2000

B = 2000 + 50

B = 2050

read(B)

B = B + temp

write(B)

T3 T4

read(A)

A = A - 50

A = 1000

temp = 1000 * 0.1

A = 1000 - 100

A = 900

B = 2000

write(A)

read(B)

B = B + 50

write(B)

B = 2050 + 100

B = 2150

A = 1000

A = 1000 - 50

read(A)

temp = A * 0.1

A = A - temp

write(A)

read(B)

A = 900

B = 2000

B = 2000 + 50

B = 2050

B = B + temp

write(B)

A = 1000

B = 2000

Soma = 3000

A = 855

B = 2145

Soma = 3000

A = 900

B = 2150

Soma = 3050

serializável não serializável

◻ Como as transações são programas - é difícil determinar exatamente que operações são realizadas e como interagem

◻ Considera-se apenas duas operações:⬜ read e write

◻ Com isso, entre as duas operações em um item de dado Q, pode haver uma sequência qualquer de operações

Operações críticas

20

◻ Serialização de conflito: quando duas instruções referem-se a diferentes itens de dados, podem ser invertidas

◻ Serialização de visão - três condições:⬜ Se ler o valor inicial do mesmo item de dado em um plano, deve ler em

outro⬜ Se ocorrer uma escrita no mesmo item de dado, os dois planos devem ler

o valor⬜ Se ocorrer uma escrita final no mesmo item de dado, os dois planos

devem escrever o valor

Opções de Serialização

21

Exemplos

22

T1 T2

read(A)

A = A - 50

write(A)

read(B)

B = B + 50

write(B)

read(A)

temp = A * 0.1

A = A - temp

write(A)

read(B)

B = B + temp

write(B)

T3 T4

read(A)

A = A - 50

write(A)

write(B)

temp = A * 0.1

A = A - temp

write(A)

write(B)

T5

read(B)

B = B + 50

write(B)

◻ O isolamento é fundamental para garantir a consistência do banco de dados, mas com várias execuções simultâneas essa propriedade pode não ser preservada

◻ Para garantir essa propriedade, o sistema precisa controlar as interações por técnicas de controle de concorrência

Controle de Concorrência

23

◻ Motivação:⬜ Melhor throughput e utilização dos recursos⬜ Tempo de espera reduzido

Controle de Concorrência

24

◻ As técnicas para controle de concorrência servem para assegurar a serialização de planos de execução usando PROTOCOLOS (conjunto de regras):⬜ Protocolos baseado em bloqueio, timestamp, gráficos,

validação, etc

Controle de Concorrência

25

◻ Impedir que múltiplas transações acessem os itens concorrentes (armazena uma variável à Ti)⬜ SE a transação precisar de um item bloqueado⬜ ENTÃO é forçada a esperar até que o item seja liberado

◻ Bloquear

⬜ lock_item(Q) ou lock(Q)

◻ Desbloquear

⬜ unlock_item(Q) ou unlock(Q)

Bloqueio binário

26

T1: lock_item(A); T2: lock_item(A);read(A); read(A);A <- A - 50; unlock_item(A);

write(A); lock_item(B);unlock_item(A); read(B);lock_item(B); unlock_item(B);read(B); display(A+B);B <- B + 50;write(B);unlock_item(B);

Exemplo - Serial

27

Exemplo - Concorrente

28

T1 T2

lock_item(A)

read(A)

A <- A - 50

write(A)

unlock_item(A)

lock_item(A)

read(A)

unlock_item(A)

lock(B)

read(B)

unlock_item(B)

display(A+B)

gerenciador de controle de concorrência

grant(A,T1)

grant(A,T2)

grant(B,T2)

Continuação - Concorrente

29

T1 T2

lock_item(B)

read(B)

B <- B + 50

write(B)

unlock_item(B)

gerenciador de controle de concorrência

grant(B,T1)

Há algum problema? Sugestão sobre como

resolver?

Exemplo - Concorrente

30

T1 T2

lock_item(A)

read(A)

A <- A - 50

write(A)

unlock_item(A)

lock_item(A)

read(A)

unlock_item(A)

lock(B)

read(B)

unlock_item(B)

display(A+B)

gerenciador de controle de concorrência

grant(A,T1)

grant(A,T2)

grant(B,T2)

Exemplo - Concorrente

31

T1 T2

lock_item(B)

read(B)

B <- B + 50

write(B)

unlock_item(B)

gerenciador de controle de concorrência

grant(B,T1)

Causa impasse (deadlock)

◻ Compartilhado (leitura)⬜ Pode apenas ler, mas não escrever⬜ lock-s(Q) ou read_lock(Q)

◻ Exclusivo (escrita)⬜ Pode ler e escrever⬜ lock-x(Q) ou write_lock(Q)

◻ Desbloquear⬜ unlock(Q)

Bloqueio compartilhado/exclusivo

32

T1: lock-x(A); T2: lock-s(A);read(A); read(A);A <- A - 50; unlock(A);

write(A); lock-s(B);unlock(A); read(B);lock-x(B); unlock(B);read(B); display(A+B);B <- B + 50;write(B);unlock(B);

Exemplo - Serial

33

◻ Bloqueios não garantem a serialização e nem a prevenção de deadlock

◻ Deve-se ter um protocolo adicional relacionado ao posicionamento das operações de bloqueio e desbloqueio

◻ O mais conhecido é o 2PC –Two Phase Commit

Bloqueios

34

◻ Um protocolo que assegura a seriação e consiste em duas fases:⬜ Fase de crescimento: uma transação pode obter bloqueios, mas não pode

liberar qualquer bloqueio

⬜ Fase de encolhimento: uma transação pode liberar bloqueios, mas não pode obter novos bloqueios

◻ Inicialmente, a transação está em fase de crescimento e pode obter qualquer bloqueio

◻ Quando a transação libera um bloqueio, ela entra em fase de encolhimento e não pode obter mais bloqueios

Bloqueio de duas fases

35

Exemplo - Duas fases

36

T1 T2

lock-s(A)

read(A)

lock-x(B)

unlock(A)

read(B)

B <- B + A

write(B)

unlock(B)

lock-s(B)

read(B)

lock-x(A)

unlock(B)

read(A)

A <- A + B

write(A)

unlock(A)

◻ 2 fases básico

◻ 2 fases conservador: requer que uma transação bloqueie todos os itens que ela acessa antes que a transação inicie

◻ 2 fases estrito: não libera nenhum de seus bloqueios exclusivos até terminar a execução da transação

◻ 2 fases rigoroso: não libera nenhum de seus bloqueios (exclusivo ou compartilhado) até terminar a execução da transação

◻ Até agora todos os protocolos causam deadlock, como resolver?

Bloqueio de duas fases

37

◻ Timestamp⬜ Identificador único criado pelo SGBD⬜ Podem ser um contador ou data/hora

◻ Cada item de dados Q é associado 2 valores⬜ W-Timestamp(Q): maior timestamp que tenha executado um

write(Q) com sucesso - Transação mais nova⬜ R-Timestamp(Q): maior timestamp que tenha executado um

read(Q) - Transação mais nova.

Baseado em Timestamp

38Estes timestamps são executados sempre que um read(Q) ou write(Q) é executada.

◻ Funcionamento

⬜ Ti emitiu um READ(Q)

■ Se TS(Ti) < W-Timestamp(Q) então

■ Ti precisa ler um valor de Q que já foi modificado por outro.

■ Alguma Tj + nova já teria escrito o valor no item Q antes que Ti tivesse a chance de ter lido Q.

■ Logo, READ(Q) é rejeitada e Ti é revertida

■ Se TS(Ti)>W-Timestamp(Q) então

■ READ(Q) é executada

■ R-timestamp(Q) é definido como TS(Ti)

Baseado em Timestamp

39

◻ Funcionamento

⬜ Ti emitiu um WRITE(Q)

■ Se TS(Ti) < R-Timestamp(Q) então

■ Alguma Tj + nova já leu o valor do item Q antes que Ti tivesse a chance para escrever Q.

■ Logo, WRITE(Q) é rejeitada e Tié revertida

■ Se TS(Ti) < W-Timestamp(Q) então

■ WRITE(Q) é rejeitada e Ti é revertida

■ Alguma Tj + nova já escreveu o valor do item Q antes que Ti tivesse a chance para escrever Q

■ Caso contrário,

Baseado em Timestamp

40

◻ Se Ti for revertida, o sistema atribui um novo timestamp e reinicia.

◻ Este protocolo garante serialização e deadlock-free⬜ Mas não garante a estagnação (starvation)

■ Uma sequência de transações curtas causa o reinício repetido da transação longa.

⬜ Pode-se evitar a estagnação garantindo que■ Não haja outra T mantendo um bloqueio sobre Q em um modo

que entra em conflito■ Não existe outra T que esteja esperando um bloqueio sobre Q

e que fez a solicitação de bloqueio antes de Ti

Baseado em Timestamp

41

Considere as duas transações a seguir:T1: read(A); T2: read(B);

read(B); read(A);if A = 0 then B <- B + 1; if B = 0 then A <- A + 1;write(B) write(A);

Considere que o requisito de consistência seja A = 0 v B = 0, sendo A = B = 0 os valores iniciais.a) Mostre que cada execução serial preserva a consistência.b) Mostre uma execução simultânea não passível de seriação.c) Existe uma execução simultânea passível de seriação?

Exercício

42

Silberschatz, A.; Korth, H. F., Sudarshan, S. Sistema de Bancos de Dados. 5a. Edição, Editora Campus, 2006.

Elmasri, R.; Navathe, S. B. Sistemas de Banco de Dados, 6ed. Pearson Addison Wesley, 2011.

Referências

43