Banco de Dados 2: Controle de Concorrência

BANCO DE DADOS II – GCC119

Controle de Concorrência

Versão dos slides: 0.773

Prof. Dr.-Ing. Leonardo Andrade Ribeiro

DCC-UFLA, Lavras


Agenda

Introdução e Motivação

Teoria da Serializabilidade

Isolamento Baseado em Bloqueios

Controle de Concorrência e Recuperação

Isolamento Baseado em Timestamps

Isolamento Baseado em Múltiplas Versões

Deadlocks

2


Isolamento e Consistência

Pelo princípio de corretude, temos que toda transação quando executada de maneira isolada (sem a execução concorrente de outras transações), deixará o banco de dados em um estado consistente

Portanto, se um conjunto de transações é executado serialmente, isto é, uma transação de cada vez, então cada transação receberá um estado consistente de sua predecessora e o resultado final será um banco de dados consistente

3

Execução Serial

Podemos sempre garantir a corretude da execução de um conjunto de transações simplemente eliminado a concorrência

Tal medida pode ser adequada... • se todos os programas apresentam tempo de

execução curto • se todos os dados estão localizados na memória

principal • se todos os dados são acessados por um único

processados • se a própria lógica da aplicação não demanda

concorrência

4 Existem muitos “ses” no cenário acima


Concorrência entre Transações

Na maioria da vezes, é essencial que transações possam executar de maneira concorrente por questões de perfomance: • Realização de processamento na CPU em paralelo com

operações de IO − Evita que o processador fique ocioso enquanto um bloco é

lido da memória

• Intercalação de processamento entre transações longas (isto é, transações cujo processamento pode durar bastante tempo) e transações curtas

− Evita que transações curtas fiquem bloqueadas aguardando o processamento de uma transação longa

5


Concorrência vs. Consistência

Mesmo com o princípio de corretude, estados temporários de inconsistência durante a execução das operações de uma transação são permitidos

Uma transação pode ter acesso a estados intermediários inconsistentes causados por outras transações

Por esse motivo, quando várias transações executam concorrentemente, comportamento da transação como um todo pode ser inconsistente

6

Controle de Concorrência Princípio básico: execução concorrente não deve

causar mal funcionamento em programas de aplicação

Garantido pela propriedade de Isolamento em ACID Controle de concorrência é o problema a ser resolvido

para garantir Isolamento Serializabilidade é a teoria que usamos para modelar

este problema Bloqueios, timestamps, e múltiplas versões são as

técnicas, que baseadas na teoria de serializabilidade, “atacam” o problema

Deadlocks são problemas colaterais decorrentes do tratamento do controle de concorrência que também precisam ser resolvidos

7

Problemas de Consistência: Intuição

Transações podem ser vistas como uma sequência de ações de leitura e escrita sobre objetos do banco de dados

Apenas ações de escrita mudam o estado de um objeto Duas operações de leitura sobre um objeto realizadas por

transações diferentes não podem violar consistência porque o estado do objeto não é modificado

Duas operações de escrita sobre um objeto realizadas por uma mesma transação não podem violar consistência porque, pelo princípio de corretude, as ações de uma transação sempre mantêm a consistência

Apenas interações entre transações envolvendo pelo menos uma operação de escrita sobre um mesmo objeto do BD podem violar consistência

8

Anomalias

Grande parte dos problemas de consistência causadas por concorrência podem caracterizados através de quatro tipos de anomalias:

• Atualizações perdidas (lost update)

• Leituras “sujas” (dirty read)

• Leitura não repetível (unrepeatable read)

• Tuplas “fantamas” (phantoms)

9

Atualização Perdida

Na sequência de abaixo, transação 𝑇1 modifica o valor de 𝐴. Após isso, 𝑇2 também modifica o valor de A antes do COMMIT de 𝑇1. Como resultado a atualização feita por 𝑇1 é perdida

10

𝑇1 𝑇2 𝐴

𝑅𝐸𝐴𝐷(𝐴, 𝑡) 25

𝑅𝐸𝐴𝐷(𝐴, 𝑠) 25

𝑡 ← 𝑡 + 100 25

𝑠 ← 𝑠 − 20 25

𝑊𝑅𝐼𝑇𝐸(𝐴, 𝑡) 125

𝑊𝑅𝐼𝑇𝐸(𝐴, 𝑠) 5

tem

po

Escrita Suja

O exemplo anterior ilustra uma atualização perdida causada por uma escrita “suja”:

• escrita sobre um objeto que foi modificado anteriormente por uma transação que ainda não realizou o COMMIT

11

Atualização Perdida: Exemplo 2

12

𝑇1 𝑇2 𝐴


𝑠 ← 𝑠 − 20 25


𝑡 ← 𝑡 + 100 25


𝐶𝑂𝑀𝑀𝐼𝑇 125


Atualizações perdidas podem ocorrer mesmo quando escritas sujas não ocorrem, como no exemplo abaixo

tem

po

Leitura Suja

Leitura suja ocorre quando uma transação lê dados escritos por uma segunda transação que ainda não realizou o COMMIT

Inconsistências podem ocorrer porque a segunda transação pode:

• abortar subsequentemente

• ter deixado o banco em um estado temporariamente inconsistente após a escrita

13

Leitura Suja: Exemplo 1

14

𝑇1 𝑇2 𝐴


𝑠 ← 𝑠 − 20 25



𝑡 ← 𝑡 + 100 5


𝐴𝐵𝑂𝑅𝑇 105

No exemplo abaixo, 𝑇1 lê o valor de 𝐴 escrito por 𝑇2 e também atualiza esse valor. Entretanto, após 𝑇2 abortar, o valor de 𝐴 escrito por 𝑇1 torna-se inconsistente

tem

po

Leitura Suja: Exemplo 2

15

𝑇1 𝑇2 𝐴 𝐵 𝐶

𝑅𝐸𝐴𝐷(𝐴, 𝑡) 100 100 200

𝑡 ← 𝑡 − 50 100 100 200

𝑊𝑅𝐼𝑇𝐸(𝐴, 𝑡) 50 100 200

𝑅𝐸𝐴𝐷(𝐴, 𝑠) 50 100 200

𝑅𝐸𝐴𝐷(𝐵, 𝑢) 50 100 200

𝑝 ← 𝑠 + 𝑢 50 100 200

𝑊𝑅𝐼𝑇𝐸(𝐶, 𝑝) 50 100 150

𝑅𝐸𝐴𝐷(𝐵, 𝑡) 50 100 150

𝑡 ← 𝑡 + 50 50 100 150

𝑊𝑅𝐼𝑇𝐸(𝐵, 𝑡) 50 150 150

No exemplo abaixo, o valor de 𝐶 que representa a soma dos valores de A e B torna-se inconsistente após a segunda escrita de 𝑇1


Leitura Não Repetível

Leitura não repetível ocorre quando uma transação lê o valor de um objeto duas vezes obtendo valores diferentes em cada leitura

16


Leitura Não Repetível: Exemplo

No exemplo abaixo, 𝑇1 obtém valores diferentes nas duas ações de leitura sobre 𝐴

17

𝑇1 𝑇2 𝐴



s ← 𝑠 − 5 5


𝐶𝑂𝑀𝑀𝐼𝑇 0


Seleção de Conjuntos de Objetos

Na discussão sobre as anomalias anteriores, transações foram descritas como ações de leitura e escrita sobre objetos individuais

Em um nível mais alto de abstração, transações são especificadas através de uma linguagem para banco de dados como SQL e conjuntos de tuplas são selecionados para leitura ou modificação através da especificação de predicados

Por exemplo, a consulta abaixo retorna um conjunto de tuplas relacionadas com funcionários cujo salário é maior que 5000

18 predicado

SELECT CPF, Nome

FROM Funcionarios

WHERE Salario > 5000

Tuplas “Fantamas” (Phantom)

Considere a seguinte sequência de ações: • Transação 𝑇1 seleciona um conjunto de tuplas 𝐶1

usando um predicado 𝑃 • Transação 𝑇2 modifica o banco de dados inserindo,

deletando ou modificando um tupla que satisfaz 𝑃 • Transação 𝑇1 realizando outra seleção novamente

baseada em 𝑃 e obtém um conjunto de tuplas 𝐶2

Como resultado da sequência abaixo, teremos uma anomalia onde 𝐶1 ≠ 𝐶2

Tuplas que podem “aparecer” ou “desaparecer” no resultado de uma seleção são chamadas de tuplas fantamas

19

Tuplas Fantasmas: Exemplo

No exemplo abaixo, a consulta de 𝑇1 sobre a tabela Funcionarios irá retornar uma ou duas tuplas, dependendo se a mesma é executada antes ou depois da inserção realizada pela transação 𝑇2

20

809333333

Nome

José Silva

João Rocha

Maria Ribeiro

CPF

111111111

122222222

Salario

9000

4000

3000

SELECT CPF, Nome

FROM Funcionarios

WHERE Salario > 5000

Funcionarios 𝑇1

INSERT INTO Funcionarios VALUES (‘333333’, ’Pedro Silva’, 6000) 𝑇2

Níveis de Isolamento

do Padrão ANSI SQL

O padrão ANSI SQL define quatro níveis de isolamento: • READ UNCOMMITTED

• READ COMMITTED

• REPEATABLE READ

• SERIALIZABLE

Cláusula SQL: • SET TRANSACTION ISOLATION LEVEL “nível de isolamento”

Além disso, é possível informar se transação será apenas de leitura ou de leitura e escrita • SET TRANSACTION {READ ONLY | READ WRITE}

21

Níveis de Isolamento e Anomalias

Níveis de isolamento do padrão ANSI SQL foram definidos à partir das anomalias leitura suja, leitura não repetível e tuplas fantasmas

22

Nível Leitura Suja Leitura Não

Repetível Tuplas

Fantasmas

READ UNCOMMITTED Sim Sim Sim

READ COMMITTED Não Sim Sim

REPEATABLE READ Não Não Sim

SERIALIZABLE Não Não Não

Níveis de Isolamento na Prática

Grande parte dos SGBDs não seguem completamente o padrão ANSI SQL

• Considerável variação na terminologia

Atualizações perdidas são consideradas na prática

• A anomalia “escrita suja” é evitada em todos os níveis para garantir recuperabilidade

• Muitos SGBDs implementam o nível de isolamento chamado CURSOR STABILITY que evita atualizações perdidas enquanto uma tupla estiver sob o cursor

• Entretanto, atualização perdidas só são completamente evitadas a partir de REPEATABLE READ

23

Níveis de Isolamento na Prática (2)

Controle de concorrência baseado na técnica de “snapshot” vem recebendo considerável adoção

• Esta técnica não garante isolação completa e é suscetível às anomalias de tuplas fantasmas e write skew (esta última anomalia será apresentada mais tarde)

• Nível de isolamento SNAPSHOT pode ser invocado explicitamente em alguns SGBDs (ex.: MS SQL Server)

• Alguns SGBDs (ex.: Oracle 10g) usam (erradamente) a técnica de snapshot para implementar o nível de isolamento SERIALIZABLE

24

Níveis de Isolamento na Prática (3)

25

Nível Escrita

Suja Leitura

Suja Atualização

Perdida Leitura Não

Repetível Write Skew

Tuplas Fantasmas

READ UNCOMMITTED

Não Sim Sim Sim Sim Sim

READ COMMITTED

Não Não Sim Sim Sim Sim

CURSOR STABILITY

Não Não Talvez Talvez Talvez Sim

SNAPSHOT Não Não Não Não Sim Talvez

REPEATABLE READ

Não Não Não Não Não Sim

SERIALIZABLE Não Não Não Não Não Não

Talvez = a anomalia é evitada em certas situações, mas em outras não


Agenda







Deadlocks

26


Exemplo de Duas Transações

27

𝑇1 𝑇2

𝑅𝐸𝐴𝐷(𝐴, 𝑡) 𝑅𝐸𝐴𝐷(𝐴, 𝑠)

𝑡 ← 𝑡 + 100 𝑠 ← 𝑠 ∗ 2

𝑊𝑅𝐼𝑇𝐸(𝐴, 𝑡) 𝑊𝑅𝐼𝑇𝐸(𝐴, 𝑠)

𝑅𝐸𝐴𝐷(𝐵, 𝑡) 𝑅𝐸𝐴𝐷(𝐵, 𝑠)

𝑡 ← 𝑡 + 100 𝑠 ← 𝑠 ∗ 2

𝑊𝑅𝐼𝑇𝐸(𝐵, 𝑡) 𝑊𝑅𝐼𝑇𝐸(𝐵, 𝑠)

Restrição de integridade: A = B


Escalonamento

Definição: Um escalonamento é uma sequência de ações realizadas por uma ou mais transações ordenada em relação o tempo de realização de cada atividade

28


Escalonamento Serial

Definição: Um escalonamento é dito serial se não existe intercalação entre operações de diferentes transações

• As ações no escalonamento consistem em todas as ações de uma transação, seguidos por todas transações de outra transação e assim por diante

Temos 𝑛! escalonamentos seriais possíveis para um conjunto de 𝑛 transações

29

Escalonamento Serial 1

30

𝑇1 𝑇2 𝐴 𝐵

𝑅𝐸𝐴𝐷(𝐴, 𝑡) 25 25

𝑡 ← 𝑡 + 100


𝑅𝐸𝐴𝐷(𝐵, 𝑡)

𝑡 ← 𝑡 + 100

𝑊𝑅𝐼𝑇𝐸(𝐵, 𝑡) 125

𝑅𝐸𝐴𝐷(𝐴, 𝑠)

𝑠 ← 𝑠 ∗ 2


𝑅𝐸𝐴𝐷(𝐵, 𝑠)

𝑠 ← 𝑠 ∗ 2

𝑊𝑅𝐼𝑇𝐸(𝐵, 𝑠) 250

S1: escalonamento serial possível para 𝑇1 e 𝑇2. Note que o resultado final é consistente, isto é, 𝐴 = 𝐵

Escalonamento Serial 2

31


𝑅𝐸𝐴𝐷(𝐴, 𝑠) 25 25

𝑠 ← 𝑠 ∗ 2



𝑠 ← 𝑠 ∗ 2


𝑅𝐸𝐴𝐷(𝐴, 𝑡)

𝑡 ← 𝑡 + 100



𝑡 ← 𝑡 + 100


S2: outro escalonamento serial possível para 𝑇1 e 𝑇2. Note que o resultado final é consistente, mas diferente do resultado de S1


Escalonamento Serial

Pelo princípio de corretude de transações, temos que todo escalonamento serial irá preservar a consistência do BD

32


Escalonamento Serializável

Definição: um escalonamento é dito serializável se o efeito no BD causado por este escalonamento é o mesmo efeito de algum escalonamento serial

33


34


𝑅𝐸𝐴𝐷(𝐴, 𝑡) 25 25

𝑡 ← 𝑡 + 100



𝑠 ← 𝑠 ∗ 2



𝑡 ← 𝑡 + 100



𝑠 ← 𝑠 ∗ 2


E1 Escalonamento serializável, mas não serial. Note que o resultado final é consistente, isto é A=B, e igual ao resultado de S1

Escalonamento Não-Serializável

35


𝑅𝐸𝐴𝐷(𝐴, 𝑡) 25 25

𝑡 ← 𝑡 + 100



𝑠 ← 𝑠 ∗ 2



𝑠 ← 𝑠 ∗ 2



𝑡 ← 𝑡 + 100


E2: Escalonamento não-serializável. Note que o resultado final é inconsistente, isto é 𝐴 ≠ 𝐵


Notação para Leitura e Escrita

A seguir, iremos adotar uma notação simplicada para ações de leitura e escrita: • 𝑟1 𝐴 : objeto 𝐴 foi lido pela transação 𝑇1; por

simplicidade, considere que o valor de 𝐴 é armazenado em um variável local também chamada 𝐴

• 𝑤1 𝐴 : variável local 𝐴 foi escrita pela transação 𝑇1 sobre um objeto também chamado 𝐴

Na maior parte da discussão, os valores concretos lidos ou escritos por transações não são importantes para o entendimento e serão omitidos

36


Notação para Transações e

Escalonamentos

Transações:

• 𝑻𝟏: 𝑟1 𝐴 ; 𝑤1 𝐴 ; 𝑟1 𝐵 ; 𝑤1 𝐵

• 𝑻𝟐: 𝑟2 𝐴 ; 𝑤2 𝐴 ; 𝑟2 𝐵 ; 𝑤2 𝐵

Escalonamento contendo 𝑇1 e 𝑇2:

• E3: 𝑟1 𝐴 ; 𝑤1 𝐴 ; 𝑟2 𝐴 ; 𝑤2 𝐴 ; 𝑟1 𝐵 ; 𝑤1 𝐵 ; 𝑟2 𝐵 ; 𝑤2 𝐵

37


Conceito de Conflito

Definição: Um par de ações em um escalonamento estão em conflito se a alteração da ordem das mesmas pode alterar o comportamento de pelo menos uma das transações envolvidas

Condição: quaisquer duas ações estão em conflito se:

1. Estas ações pertencem à mesma transação, ou

2. As ações são pertencem à transações diferentes, e

2.1 envolvem o mesmo objeto do BD, e

2.2 pelo menos uma destas ações é uma escrita

38


Conceito de Conflito

Dado um escalonamento 𝐸, ações consecutivas que não estão em conflito podem ser reordenadas gerando um novo escalonamento 𝐸′ equivalente a 𝐸

39

𝐸: 𝑟1 𝐴 ; 𝑤1 𝐴 ; 𝑟2 𝐴 ; 𝒘𝟐 𝑨 ; 𝒓𝟏 𝑩 ; 𝑤1 𝐵 ; 𝑟2 𝐵 𝑤2 𝐵

𝐸′: 𝑟1 𝐴 ; 𝑤1 𝐴 ; 𝑟2 𝐴 ; 𝒓𝟏 𝑩 ; 𝒘𝟐 𝑨 ; 𝑤1 𝐵 ; 𝑟2 𝐵 𝑤2 𝐵

ações não conflitantes Exemplo:

equivalentes


Escalonamentos

Equivalentes em Conflito

Definição: Dois escalonamentos são ditos equivalentes em conflito se podemos transformar um escalonamento no outro através por uma sequência de trocas de posições entre pares ações adjacentes que não estejam em conflito

40


Escalonamento

Serializável em Conflito

Definição: Um escalonamentos é dito serializável em conflito se este escalonamento é equivalente em conflito a algum escalonamento serial

41


em Conflito: Exemplo

42

𝑟1 𝐴 ; 𝑤1 𝐴 ; 𝑟2 𝐴 ; 𝒘𝟐 𝑨 ; 𝒓𝟏 𝑩 ; 𝑤1 𝐵 ; 𝑟2 𝐵 ; 𝑤2 𝐵

𝑟1 𝐴 ; 𝑤1 𝐴 ; 𝒓𝟐 𝑨 ; 𝒓𝟏 𝑩 ; 𝑤2 𝐴 ; 𝑤1 𝐵 ; 𝑟2 𝐵 ; 𝑤2 𝐵

𝑟1 𝐴 ; 𝑤1 𝐴 ; 𝑟1 𝐵 ; 𝑟2 𝐴 ; 𝒘𝟐 𝑨 ; 𝒘𝟏 𝑩 ; 𝑟2 𝐵 ; 𝑤2 𝐵

𝑟1 𝐴 ; 𝑤1 𝐴 ; 𝑟1 𝐵 ; 𝒓𝟐 𝑨 ; 𝒘𝟏 𝑩 ; 𝑤2 𝐴 ; 𝑟2 𝐵 ; 𝑤2 𝐵

𝑟1 𝐴 ; 𝑤1 𝐴 ; 𝑟1 𝐵 ; 𝑤1 𝐵 ; 𝑟2 𝐴 ; 𝑤2 𝐴 ; 𝑟2 𝐵 ; 𝑤2 𝐵

ações não conflitantes

equ

ivalentes em

con

fito

seri

aliz

ávei

s e

m c

on

flit

o

escalonamento serial


Serializável vs.

Serializável em Conflito

Serializabilidade em conflito é uma condição suficiente para serializabilidade, isto é, um escalonamento que é serializável em confilto também é serializável

Por outro lado, um escalonamento pode ser serializável e, no entanto, não ser serializável em confilto

43

Serializável vs.

Serializável em Conflito: Exemplo

Considerem o seguinte escalonamento serial: • S3: 𝒓𝟏 𝑨 ; 𝒘𝟏 𝑨 ; 𝒘𝟐 𝑨 ; 𝒘𝟑 𝑨

Temos que o escalonamento E4 abaixo irá ter o mesmo efeito que S3 e, portanto, é serializável: • E4: 𝒓𝟏 𝑨 ; 𝒘𝟐 𝑨 ; 𝒘𝟏 𝑨 ; 𝒘𝟑 𝑨

• Intuitivamente, observe que o valor final de 𝐴 será pela escrita da transação 𝑇3

Entretanto, não podemos converter E4 em S3 porque todas ações adjacentes de E4 estão em confilto

Portanto, E4 não é serializável em conflito apesar de ser serializável

44


Conceito de Precedência

Dado um escalonamento 𝐸 envolvendo duas transações 𝑇1 e 𝑇2, dizemos que 𝑇1 tem precedência sobre 𝑇2, denotado por 𝑇1 <𝑃 𝑇2, se existem ações 𝐴1 ∈ 𝑇1 e 𝐴2 ∈ 𝑇2 tal que: • 𝐴1 aparece primeiro que 𝐴2 no escalonamento;

• 𝐴1 e 𝐴2 envolvem o mesmo objeto do BD;

• pelo menos 𝐴1 ou 𝐴2 é uma operação de escrita

Em outras palavras, transação 𝑇1 tem precedência sobre transação 𝑇2 em um escalonamento 𝐸 se existe uma ação 𝐴1 de 𝑇1 conflitante com uma ação 𝐴2 de 𝑇2 e 𝐴1 precede 𝐴2 em 𝐸

45


Conceito de Precedência: Exemplo

Considere o simples escalonamento abaixo:

• 𝐸5: 𝒓𝟏 𝑨 ; 𝑟2 𝐴 ; 𝑟1 𝐵 ; 𝒘𝟐 𝑨

Temos que as ações 𝑟1 𝐴 e 𝑤2 𝐴 de 𝑇1 e 𝑇2, respectivamente, são conflitantes

Como 𝑟1 𝐴 precede 𝑤2 𝐴 em 𝐸5, então 𝑇1 <𝑃 𝑇2

46


Grafo de Precedência

Podemos capturar o relacionamento de precedência as transações de um escalonamento através de um grafo de precedência

Dado um escalonamento 𝐸, o grafo de precedência 𝐺𝐸 de 𝐸 possui o conjunto de vértices formado pelo conjunto de transações em 𝐸, onde o rótulo do vértice associado com a transação 𝑇𝑖 é 𝑖. Existe uma aresta direcionada entre quaisquer vértices 𝑖 e 𝑗 sse 𝑇𝑖 <𝑃 𝑇𝑗

47


Grafo de Precedência: Exercício

Construa o grafo de precedência para o escalonamento abaixo:

48

𝐸6: 𝑟2 𝐴 ; 𝑟1 𝐵 ; 𝑤2 𝐴 ; 𝑟3 𝐴 ;𝑤1 𝐵 ; 𝑤3 𝐴 ; 𝑟2 𝐵 ; 𝑤2 𝐵


Exercício: Resposta

Vamos considerar a primeira escrita, 𝑤2 𝐴 , realizada pela transação 𝑇2

Temos que nenhuma transação além de 𝑇2 leu ou escreveu o objeto 𝐴 antes dessa ação; por outro lado, temos a leitura 𝑟3 𝐴 e a escrita 𝑤3 𝐴 da transação 𝑇3 em 𝐴 após essa ação

Portanto, o grafo de precedência parcial de E6 será:

49

1 2 3

𝐸6: 𝑟2 𝐴 ; 𝑟1 𝐵 ; 𝒘𝟐 𝑨 ; 𝑟3 𝐴 ; 𝑤1 𝐵 ; 𝑤3 𝐴 ; 𝑟2 𝐵 ; 𝑤2 𝐵


Exercício: Resposta (2)

Vamos considerar agora a segunda escrita, 𝑤1 𝐵 , realizada pela transação 𝑇1

Temos que nenhuma transação além de 𝑇1 leu ou escreveu o objeto 𝐴 antes dessa ação; por outro lado, temos a leitura 𝑟2 𝐵 e a escrita 𝑤2 𝐵 da transação 𝑇2 em 𝐵 após esta ação

Portanto, o grafo de precedência parcial de E6 será:

50

1 2 3

𝐸6: 𝑟2 𝐴 ; 𝑟1 𝐵 ; 𝑤2 𝐴 ; 𝑟3 𝐴 ; 𝒘𝟏 𝑩 ; 𝑤3 𝐴 ; 𝑟2 𝐵 ; 𝑤2 𝐵



Vamos considerar a terceira escrita, 𝑤3 𝐴 ,

realizada pela transação 𝑇3 A relação de precedência 𝑇2 <𝑃 𝑇3 devido ao

objeto 𝐴 já está representada no grafo. Observando as operações após 𝑤3 𝐴 , temos que nenhuma transação lê ou escreve 𝐴 após esta operação.

O grafo de precedência permance, portanto, inalterado

51

𝐸6: 𝑟2 𝐴 ; 𝑟1 𝐵 ; 𝑤2 𝐴 ; 𝑟3 𝐴 ; 𝑤1 𝐵 ; 𝒘𝟑 𝑨 ; 𝑟2 𝐵 ; 𝑤2 𝐵



Finalmente, consideramos a operação, 𝑤2 𝐵 , realizada pela operação 𝑇2

A relação de precedência 𝑇1 <𝑃 𝑇2 devido ao objeto B já está representada no grafo e não existem outras operações após 𝑤2 𝐵

Portanto o grafo de precedência final será:

52

1 2 3

𝐸6: 𝑟2 𝐴 ; 𝑟1 𝐵 ; 𝑤2 𝐴 ; 𝑟3 𝐴 ; 𝑤1 𝐵 ; 𝑤3 𝐴 ; 𝑟2 𝐵 ; 𝒘𝟐 𝑩


Grafo de Precedência e

Serializabilidade em Conflito

O grafo de precedência de um escalonamento serializável em conflito não possui ciclos

Além disso, qualquer ordem topológica do grafo de precedência de um escalonamento serializável em conflito representa um escalonamento serial equivalente em conflito

53


Exercício

Considere o escalonamento abaixo:

Construa o grafo de precedência para E7

Este escalonamento é serializável em conflito?

54

𝐸7: 𝑟2 𝐴 ; 𝑟1 𝐵 ; 𝑤2 𝐴 ; 𝑟2 𝐵 ; 𝑟3 𝐴 ; 𝑤1 𝐵 ; 𝑤3 𝐴 ; 𝑤2 𝐵


Exercício: Resposta

Não, pois o grafo de precedência correspondente apresenta um ciclo

55

1 2 3


Serializabilidade em Visão

Como já mencionado, serializabilidade em conflito é uma condição suficiente mas não necessária para serializabilidade

Uma condição suficiente e mais geral para serializabilidade é a chamada serializabilidade em visão

56


Escalonamentos

Equivalentes em Visão

Dois escalonamentos 𝐸1 e 𝐸2 sobre o mesmo conjunto de transações são equivalentes em visão se as três condições abaixo são satisfeitas: 1. Se 𝑇𝑖 lê o valor inicial do objeto 𝐴 em 𝐸1, então 𝑇𝑖

também deve ler o valor de inicial de 𝐴 em 𝐸2

2. Se 𝑇𝑖 lê o valor de 𝐴 escrito por 𝑇𝑗 em 𝐸1, então 𝑇𝑖 também deve ler o valor de 𝑇𝑗 em 𝐸2

3. Para cada objeto 𝐴, se existe uma transação 𝑇𝑖 que realiza a última escrita sobre 𝐴 em E1, então 𝑇𝑖 também deve realizar a última escrita sobre 𝐴 em E2

57


Escalonamento

Serializável em Visão

Definição: Um escalonamentos é dito serializável em visão se este escalonamento é equivalente em visão a algum escalonamento serial

58

Escalonamento

Serializável em Visão: Exemplo

Considere novamente o escalonamento serial S3 e o escalonamento E4: • S3: 𝑟1 𝐴 ; 𝑤1 𝐴 ; 𝑤2 𝐴 ; 𝑤3 𝐴 • E4: 𝑟1 𝐴 ; 𝑤2 𝐴 ; 𝑤1 𝐴 ; 𝑤3 𝐴

Temos que S3 e E4 são equivalentes em visão: 1. 𝑇1 lê o valor inicial de A em S3 e em E4 2. Nenhuma transação em S3 e em E4 lê o valor escrito por

outra transação 3. 𝑇3 escreve o valor final de A em S3 e em E4

Portanto, E4 é serializável em visão Notem que E4 não é serializável em conflito

• Todo escalonamento serializável em conflito também é serializável em visão, mas o oposto não é verdadeiro

59

Serializabilidade Em Visão

na Prática

Apesar de permitir uma condição mais geral para testes de serializabilidade que serializabilidade em conflito, a aplicação do conceito de serializabilidade em visão é bastante custosa computacionalmente

• Pouca utilidade na prática

60


Agenda







Deadlocks

61


Isolamento Usando Bloqueios (Locks)

Bloqueios é um conceito importante para garantir serilizabilidade de escalonamentos

Intuitivamente, uma transação dever obter um bloqueio (lock) sobre um objeto do BD antes de realizar ações de leitura ou escrita sobre esse objeto

O uso de bloqueios impõe restrições de consistência na estrutura de transações e escalonamentos

62

Isolamento Usando Bloqueios (Locks)

Transações: 1. Uma transação pode apenas ler ou escrever um objeto se

a mesma já possui um bloqueio sobre este objeto e ainda não o liberou ainda

2. Se uma transação bloqueia um objeto, a mesma deve libera-lo mais tarde

Escalonamentos: 1. Duas transações não podem manter bloqueios

incompatíveis sobre o mesmo objeto ao mesmo tempo

2. Caso a requisição de bloqueio sobre um objeto não possa ser atendida, por exemplo, porque este objeto já se encontra bloqueado por uma segunda transação, então a transação requisitante deverá aguardar até que essa segunda transação libere o bloqueio

63


Bloqueios: Notação

Inicialmente, vamos considerar primeiramente bloqueios de leitura e escrita • Outros tipos de bloqueio serão vistos mais tarde

Bloqueio de leitura ou compartilhado (shared lock) • 𝒔𝒊 𝑨 : Transação 𝑇𝑖 possui um bloqueio de leitura sobre

o objeto 𝐴

Bloqueio de escrita ou exclusivo (exclusive lock) • 𝒙𝒊 𝑨 : Transação 𝑇𝑖 possui um bloqueio de escrita sobre

o objeto 𝐴

Liberação de bloqueio (unlock) • 𝒖𝒊 𝑨 : Transação 𝑇𝑖 liberou o bloqueio (de leitura ou

escrita) sobre o objeto 𝐴

64


Consistência de Transações

Regras para consistência de transações: 1. Uma ação de leitura 𝑟𝑖 𝐴 deve ser precedida

por 𝑠𝑖 𝐴 ou 𝑥𝑖 𝐴 sem qualquer 𝑢 𝐴 interposto entre as mesmas

2. Um ação de escrita 𝑤𝑖 𝐴 deve ser precedida por 𝑥𝑖 𝐴 sem qualquer sem qualquer 𝑢 𝐴 interposto entre as mesmas

3. Todos operações 𝑠𝑖 𝐴 ou 𝑥𝑖 𝐴 devem ser sucedidas em algum momento por uma operação 𝑢 𝐴

65


Legalidade de Escalonamentos

Regras para legalidade de escalonamentos:

1. Se 𝑥𝑖 𝐴 aparece em um escalonamento, então não pode existir um 𝑥𝑗 𝐴 ou 𝑠𝑗 𝐴 , para 𝑗 ≠ 𝑖,

sem que exista um 𝑢 𝐴 interposto

2. Se 𝑠𝑖 𝐴 aparece em um, então não pode existir um 𝑥𝑗 𝐴 , para 𝑗 ≠ 𝑖, sem que exista um 𝑢 𝐴

interposto

66

Matriz de Compatibilidade

67

𝑠 𝑥

𝑠 Sim Não

𝑥 Não Não Blo

qu

eio

vi

gen

te

Bloqueio requisitado

• Uma matriz de compatibilidade possui uma linha e uma coluna para cada tipo de lock. As linhas correspondem a bloqueios que já existem sobre um objeto e as colunas correspondem a bloqueios requisitados por outras transações

• Os valores nas células indicam se a transação requisitante podem obter o o bloqueio

Bloqueios: Exemplo No exemplo abaixo, a transação 𝑇2 tem que aguardar até

que 𝑇1 libere o bloqueio de escrita sobre 𝐵

68

𝑇1 𝑇2

𝑠1 𝐴

𝑟1 𝐴

𝐵 ← 𝐴 + 100 𝑠2 𝐴

𝑢1 𝐴 𝑟2 𝐴

𝑥1 𝐵 𝑢2 𝐴

𝑤1 𝐵 𝑠2 𝐵 Negado!

𝑢1 𝐵 𝑇2 em espera

𝑠2 𝐵

𝑟2 𝐵

Bloqueios: Exemplo 2

69


𝑥1 𝐴 , 𝑟1 𝐴 25 25

𝐴 ← 𝐴 + 100 𝑥2 𝐴 Negado!

𝑤1 𝐴 ; 𝑢1 𝐴 𝑇2 em espera 125

𝑥2 𝐴 ; 𝑟2 𝐴

𝐴 ← 𝐴 ∗ 2

𝑤2 𝐴 , 𝑢2 𝐴 250

𝑥2 𝐵 , 𝑟2 𝐵

𝑥1 𝐵 Negado! B ← 𝐵 ∗ 2

𝑇1 em espera 𝑤2 𝐵 , 𝑢2 𝐵 50

𝑥1 𝐵 ; 𝑟1 𝐵

B ← 𝐵 + 100

𝑤1 𝐵 , 𝑢1 𝐵 150

E2‘: Escalonamento válido usando bloqueios mas não serializável. Note que o resultado final é inconsistente, isto é 𝐴 ≠ 𝐵


Bloqueio em Duas Fases

( Two-phase Locking, 2PL)

2PL: protocolo para aquisição e liberação de bloqueios

Principio básico: em toda transação, todos as requisições por bloqueios precedem as requisições por unlock

Fase de expansão: bloqueios são adquiridos mas não liberados

Fase de retração: bloqueis são liberados e nenhum novo bloqueio é adquirido

70


Protocolo 2PL: Definição Formal

Um protocolo é dito 2PL se em qualquer transação 𝑇𝑖, nenhuma ação 𝑠𝑖 𝐴 ou 𝑥𝑖 𝐴 pode ser precedida por uma ação 𝑢 𝐵 para qualquer 𝐴 e qualquer 𝐵

71


2PL e Serializabilidade em Conflito

Se um escalonamento 𝐸 é composto apenas por transações que obedecem o protocolo 2PL, então 𝐸 é serializável em conflito

• Um escalonamento serial equivalente em conflito com 𝐸 pode ser obtido através pelo ordenamento das transações de 𝐸 baseando-se nas primeiras requisições de unlock de cada transação

72

Escalonamento Usando 2PL

73


𝑥1 𝐴 , 𝑟1 𝐴 25 25

𝐴 ← 𝐴 + 100 𝑥2 𝐴 Negado!

𝑤1 𝐴 , 𝑥1 𝐵 , 𝑢1 𝐴 125

𝑥2 𝐴 , 𝑟2 𝐴

𝐴 ← 𝐴 ∗ 2

𝑤2 𝐴 , 250

𝑥2 𝐵 Negado!

𝑟1 𝐵

B ← 𝐵 + 100

𝑤1 𝐵 , 𝑢1 𝐵 125

𝑥2 𝐵 , 𝑢2 𝐴 ,𝑟2 𝐵

B ← 𝐵 ∗ 2

𝑤2 𝐵 , 𝑢2 𝐵 250


Upgrade e Downgrade

de Bloqueios

Upgrade de bloqueio: Uma transação mantendo um bloqueio de leitura pode converte-lo em um bloqueio de escrita sem ter que liberar o bloqueio original primeiro

• 𝑇𝑖: 𝑠𝑖 𝐴 → 𝑥𝑖 𝐴

Downgrade de bloqueio: Uma transação mantendo um bloqueio de escrita pode converte-lo em um bloqueio de leitura sem ter que liberar o bloqueio original primeiro

• 𝑇𝑖: 𝑥𝑖 𝐴 → 𝑠𝑖 𝐴

Upgrade e downgrade de bloqueios pode aumentar a concorrência entre transações • Transações podem permanecer mais tempo com o bloqueio de

leitura que permite o acesso compartilhado a objetos do BD

74


Upgrade e Downgrade de

Bloqueios em Transações 2PL

Em uma transação 2PL, upgrade de bloqueios só é permito na fase de expansão, ao passo que downgrade de bloqueios só é permitido na fase de retração

75

Upgrade e Downgrade de

Bloqueios: Exemplo

No escalonamento abaixo, a computação de 𝑇1 e 𝑇2 não poderia ser realizada de maneira concorrente se 𝑇1 tivesse obtido diretamente um bloqueio exclusivo sobre 𝐵

76

𝑇1 𝑇2

𝑠1 𝐴 , 𝑟1 𝐴

𝑠1 𝐵 , 𝑟1 𝐵

𝑠2 𝐴 , 𝑟2 𝐴

𝑠2 𝐵 , 𝑟2 𝐵

𝑢2 𝐴 , 𝑢2 𝐵

𝑥1 𝐵 , 𝑟1 𝐵 , 𝑤1 𝐵

𝑢1 𝐴 , 𝑢1 𝐵

Objetos de Diferentes

Granularidades

Objetos do BD podem ser definidos em diferentes granularidades, relacionados entre si de maneira hierárquica: • Ex.: relações → blocos → tuplas

É desejável que protocolos de bloqueio explorem estes diferentes níveis de granularidade e a hierarquia subjacente

77

relação

bloco 1 bloco 2

tupla 1 tupla 2 tupla 3 tupla 4

Representação gráfica em forma de árvore dos objetos de um BD

Bloqueios com

Diferentes Granularidades

Considere um banco de dados de um sistema bancário, onde as informações da cada conta bancária são mantidas na relação “Conta”

Se relações são tratadas como objetos básicos do BD, então qualquer transação que for alterar o saldo bancário de um cliente terá que bloquear toda a relação “Conta” • Consequentemente, teriamos acesso serial sobre “Conta”

e a concorrência entre as transações seria consideravelmente reduzida

Uma melhor estratégia para aumentar a concorrência seria realizar bloqueios sobre objetos de menor granularidade como blocos ou tuplas

78

Bloqueios com

Diferentes Granularidades (2)

Por outro lado, no caso de transações que irão acessar uma grande parcela das tuplas de relação (por exemplo, uma transação que debita taxas bancárias de cada conta no começo do mês), será custoso manter um bloqueio para cada tupla acessada

Neste caso, é preferível obter um único bloqueio sobre toda a relação “Conta”

79

Bloqueios sobre

Hierarquias de Objetos

Para podermos realizar bloqueios sobre objetos organizados de maneira hierárquica, é necessário uma maneira para “navegar” entre os vértices que representam os objetos • Precisamos mover na árvore no sentido raiz-folha para obter

bloqueios cada vez mais refinados • Precisamos mover na árvore no sentido folha-raiz para liberar os

bloqueios

De maneira geral, um bloqueio explícito sobre um vértice 𝑣 resulta em bloqueios implícitos sobre todos os vértices da subárvore enraizada por 𝑣 do mesmo tipo que o bloqueio explícito (escrita ou leitura)

Um transação pode apenas realizar açoes sobre um objeto representado pelo vértice 𝑣 após obter um bloqueio explícito sobre 𝑣 80


Bloqueios de Intenção

Um bloqueio de intenção sobre 𝑣 representa a “intenção” de realizar uma ação sobre um dos nós da subárvore enraizada por 𝑣

Usados para navegar na árvore de objetos de múltiplas granularidades:

• Bloqueios de intenção devem ser obtidos sobre todos vértices ancestrais (isto é, o caminho do vértice pai até a raiz da árvore) do vértice sobre o qual pretende-se obter o bloqueio explícito

81

Tipos de Bloqueios de Intenção

Bloqueio de intenção de leitura (intention shared lock): • 𝑖𝑠(𝑣): bloqueio de leitura explícito será realizado sobre

algum vértice da subárvore enraizada por 𝑣

Bloqueio de intenção de escrita (intention exclusive lock): • 𝑖𝑥(𝑣): bloqueio de escrita explícito será realizado sobre

algum vértice da subárvore enraizada por 𝑣

Bloqueio de leitura e de intenção de escrita (shared and intention exclusive lock): • 𝑠𝑖𝑥(𝑣): bloqueio de leitura explícito sobre 𝑣 e um bloqueio

de escrita explícito será realizado sobre algum vértice dessa subárvore

82

Bloqueios de Intenção: Exemplos

83

𝑖𝑠

𝑖𝑠

𝑠

Sequência de bloqueios de intenção de leitura até a obtenção de um bloqueio (explícito) de leitura

𝑖𝑥

𝑥

Sequência de bloqueios de intenção de escrita até a obtenção de um bloqueio (explícito) de escrita

𝑠𝑖𝑥

𝑠𝑖𝑥

𝑥

Sequência de bloqueios de leitura e intenção de escrita até a obtenção de um bloqueio (explícito) de escrita.


Bloqueios de Intenção:

Matriz de Compatibilidade

84

𝑖𝑠 𝑖𝑥 𝑠 𝑠𝑖𝑥 𝑥

𝑖𝑠 Sim Sim Sim Sim Não

𝑖𝑥 Sim Sim Não Não Não

𝑠 Sim Não Sim Não Não

𝑠𝑖𝑥 Sim Não Não Não Não

𝑥 Não Não Não Não Não

Matriz de compatibilidade contendo bloqueios de intenção e bloqueios regulares


Bloqueios de Aviso: Regras

Para que uma transação 𝑇𝑖 obtenha um bloqueio sobre um vértice 𝑣, as seguintes regras devem ser obedecidas: 1. 𝑇𝑖 deve bloquear primeiramente a raiz da árvore;

qualquer tipo de bloqueio pode ser usado 2. 𝑇𝑖 pode bloquear 𝑣 em modo 𝑠 ou 𝑖𝑠 somente se𝑇𝑖 já

possui o bloqueio do pai de de 𝑣 em modo 𝑖𝑠 ou 𝑖𝑥 3. 𝑇𝑖 pode bloquear 𝑣 em modo 𝑥, 𝑖𝑥 e 𝑠𝑖𝑥 somente se 𝑇𝑖

possui o bloqueio do pai de 𝑣 em 𝑖𝑥 e 𝑠𝑖𝑥 4. 𝑇𝑖 pode bloquear 𝑣 se a mesma ainda não desbloqueou

nenhum vértice (isto é, 𝑇 é 2PL) 5. Uma transação pode desbloquear um vértice se a mesma

não possui bloqueios sobre nenhum de seus filhos

85

Bloqueios de Intenção em

Escalonamentos

Considere um escalonamento formado pelas transações 𝑇1 e 𝑇2:

• 𝑇1: SELECT * FROM Alunos WHERE ID=2222 OR ID=4444

• 𝑇2: UPDATE Alunos SET fone=9192 WHERE ID=3333

A sequência de bloqueios sobre os objetos nas granularidades relação, bloco e tupla é ilustrada abaixo

86

Alunos 𝑇1: 𝑖𝑠

ID=2222 ID=3333 𝑇1: s 𝑇2: 𝑥

Bloco 1 Bloco 2

ID=4444 𝑇1: s

𝑇2: 𝑖𝑥

𝑇1: 𝑖𝑠 𝑇1: 𝑖𝑠

𝑇2: 𝑖𝑥


Evitando Tuplas Fantasmas Considere uma transação 𝑇 que seleciona um conjunto de tuplas de

uma tabela 𝐴 usando um predicado 𝑃 Uma maneira direta de se evitar tuplas fantasmas é obter um

bloqueio do tipo 𝑥 sobre 𝐴 • Com isso, tuplas não podem ser inseridas ou deletadas

Entretanto, esta abordagem limita bastante a concorrência porque mesmo inserções ou deleções que não são relacionadas com 𝑃 serão impedidas

Uma solução mais sofisticada consiste em usar um índice definido sobre um atributo em 𝑃 • O índice sempre é atualizado quando uma tupla é inserida ou deletada • Obtendo bloqueios somente sobre sobre páginas do índice contendo

tuplas que satisfazem 𝑃 permite evitar tuplas fantasmas sem eliminar a inserção ou deleção de tuplas não relacionadas com 𝑃

Esta técnica é conhecida como bloqueio de índice (index locking) e é um caso especial de um conceito mais geral para bloqueio de predicados (predicate locking)

87


Agenda







Deadlocks

88


Escalonamentos Envolvendo

Transações que Abortaram Até o momento na discussão, consideramos apenas as

ações de transações, mas ignoramos se as mesmas irão concluir com sucesso ou abortar

Como já mencionado na discussão sobre recovery, quando se uma transação aborta podemos ter problemas para recuperar o estado consistente do BD caso outras transações já tenham realizados ações conflitantes com essa transação • Neste caso, podemos ter a situação onde um escalonamento,

mesmo serializável, produz uma sequência de registros no log que é recuperável

Para tratar este problema, vamos estender a notação para consideramos ações de COMMIT e ABORT • 𝑐1: transação 𝑇1 realizou COMMIT • 𝑎1: transação 𝑇1 realiou ABORT

89

Escalonamento

Não Recuperável: Exemplo

90

𝑇1 𝑇2 A Log

100 𝑆𝑇𝐴𝑅𝑇, 𝑇1

𝑥1 𝐴 , 𝑟1 𝐴 𝑆𝑇𝐴𝑅𝑇, 𝑇2

𝐴 ← 𝐴 − 20 𝑥2 𝐴 Negado!

𝑤1 𝐴 , 𝑢1 𝐴 80 𝑇1, 𝐴, 100,80

𝑥2 𝐴 , 𝑟2 𝐴

𝐴 ← 𝐴 ∗ 2

𝑤2 𝐴 , 𝑢2 𝐴 160 𝑇2, 𝐴, 80,160

𝑐2 𝐶𝑂𝑀𝑀𝐼𝑇, 𝑇2

𝑎1 𝐴𝐵𝑂𝑅𝑇, 𝑇1

Após 𝑇1 realizar o ABORT, o processo de recovery é acionado para desfazer sua ação no BD. O undo de 𝑇1 faz com que a ação de 𝑇2 também seja desfeita. Entretanto, isto não pode ocorrer porque 𝑇2 já realizou o COMMIT e suas ações no BD devem ser duráveis


Escalonamento Recuperáveis

Escalonamento recuperável: um escalonamento é recuperável se cada transação 𝑇 realiza o COMMIT apenas depois que todas transações que escreveram dados lidos por 𝑇 tenham realizado o COMMIT

Neste contexto, se uma transação 𝑇1 aborta, então todas transações que leram dados escritos por 𝑇1 também devem abortar

91

Escalonamento

Não Recuperável: Exemplo

92

𝑇1 𝑇2 A Log

100 𝑆𝑇𝐴𝑅𝑇, 𝑇1

𝑥1 𝐴 , 𝑟1 𝐴 𝑆𝑇𝐴𝑅𝑇, 𝑇2

𝐴 ← 𝐴 − 20 𝑥2 𝐴 Negado!

𝑤1 𝐴 , 𝑢1 𝐴 80 𝑇1, 𝐴, 100,80

𝑥2 𝐴 , 𝑟2 𝐴

𝐴 ← 𝐴 ∗ 2

𝑤2 𝐴 , 𝑢2 𝐴 160 𝑇2, 𝐴, 80,160



Agora o ABORT de 𝑇1 faz com que 𝑇2 seja abortada


Escalonamentos Recuperáveis vs.

Escalonamentos Serializáveis

Recuperabilidade e Serializabilidade são conceitos ortogonais

Exemplo de escalonamento serializável e recuperável • 𝐸7: 𝑤1 𝐴 ; 𝑤1 𝐵 ; 𝑤2 𝐴 ; 𝑟2 𝐵 ; 𝑐1; 𝑐2

Exemplo de escalonamento recuperável mas não serializável • 𝐸8: 𝑤2 𝐴 ; 𝑤1 𝐵 ; 𝑤1 𝐴 ; 𝑟2 𝐵 ; 𝑐1; 𝑐2 • Notem que todas todas operações de 𝐸8 estão em conflito

Exemplo de escalonamento serializável mas não recuperável • 𝐸9: 𝑤1 𝐴 ; 𝑤1 𝐵 ; 𝑤2 𝐴 ; 𝑟2 𝐵 ; 𝑐2; 𝑐1 • Notem que 𝑇2 realiza o COMMIT antes de 𝑇1

93


ABORT em Cascata

Como jé mencionado, quando um transação 𝑇 aborta, todas as transações que 𝑈1, … , 𝑈𝑛 que leram valores escritos por 𝑇 devem abortar

Por sua vez, todas transações 𝑉1, … , 𝑉𝑛 que leram valores escritos pelas transações 𝑈1, … , 𝑈𝑛 também devem abortar e assim por diante

Este comportamento é chamado ABORT (ROLLBACK) em cascata

94


ABORT em Cascata: Exemplo

95

𝑇1 𝑇2 𝑇3 𝑇4

𝑤1 𝐴

𝑟2 𝐴

𝑤2 𝐵

𝑟3 𝐵

𝑤3 𝐶

𝑟4 𝐶

𝑎1

𝑎2

𝑎3

𝑎4

O ABORT de 𝑇1 faz com que 𝑇2, 𝑇3 e 𝑇4 sejam abortadas


Escalonamentos que Evitam

ABORT em Cascata

Um escalonamento evita ABORT em cascata (EAC) se transações podem ler apenas valores de transações que já realizaram o COMMIT

• Em outras palavras, um escalonamento é dito recuperável se o mesmo não permite leituras sujas

Claramente, todo escalonamento EAC também é recuperável

96

Problemas com Escrita Suja

No exemploa acima, o gerenciador de recovery não pode realizar o “undo” das ações de 𝑇1 porque senão a ação de 𝑇2 será desfeita

Por outro lado, se as modificações de 𝑇1 não forem desfeitas e𝑇2 abortar subsequentemente, então não será possível retornar o valor original de 𝐴

97

𝑇1 𝑇2 A Log

𝑠1 𝐴 , 𝑟1 𝐴 100

𝐴 ← 𝐴 − 20

𝑥1 𝐴 , 𝑤1 𝐴 𝑇1, 𝐴, 100,80

𝑢1 𝐴 𝐴 ← 160 80

𝑥2 𝐴 , 𝑤2 𝐴 160 𝑇2, 𝐴, 80,160


Bloqueios Longos e Curtos

Para solucionar o problema com escritas sujas, vamos introduzir os conceitos de bloqueios longos e curtos

Bloqueio longo: um bloqueio é dito longo se o mesmo é mantido até que a transação realize o COMMIT ou ABORT

Bloqueio curto: um bloqueio é dito curto se o mesmo é liberado antes que a transação realize o COMMIT ou ABORT

98


Protocolo 2PL Estrito

Um protocolo é dito 2PL se em qualquer transação 𝑇𝑖 , nenhuma ação 𝑠𝑖 𝑋 ou 𝑥𝑖 𝑋 pode ser precedida por uma ação 𝑢 𝑌 para qualquer 𝑌 e todos bloqueios de escrita são longos

Escalonamentos apenas com transações seguindo o protocolo 2PL estrito são chamadados bloqueio estrito são chamados escalonamentos 2PL estritos

Todo escalonamento 2PL estrito é serializável e EAC • O escalonamento é serializável por ser 2PL • O escalonamento é EAC porque leituras sujas não são

possíveis

99

Escalonamento 2PL Estrito

Agora 𝑇2 só obtém o bloqueio de escrita sobre 𝐴 após 𝑇1 abortar e, consequentemente, liberar o bloqueio

100

𝑇1 𝑇2 A Log

𝑠1 𝐴 , 𝑟1 𝐴 100

𝐴 ← 𝐴 − 20 𝑟2 𝐴 , 𝑟2 𝐴

𝑥1 𝐴 , 𝑤1 𝐴 𝐴 ← 𝐴 ∗ 2 𝑇1, 𝐴, 100,80


𝑥1 𝐴 , 𝑤1 𝐴 160 𝑇2, 𝐴, 80,160


Relacionamento entre Classes de

Escalonamentos

101

Serializável

Recuperável EAC

2PL Estrito

Serial

Níveis de Isolamento SQL e

Bloqueios

A tabela mostra uma possível estratégia para implementação dos nívéis de isolamento SQL suando bloqueios

Notem que todos níveis evitam escritas sujas Escalamentos recuperáveis e EAC são garantidos a partir do

nível READ COMMITED 102

Nível Bloqueio de

leitura Bloqueios de

Escrita Bloqueio de Predicados

READ UNCOMMITTED Não Sim, Longos Não

READ COMMITTED Sim, Curtos Sim, Longos Não

REPEATABLE READ Sim, Longos Sim, Longos Não

SERIALIZABLE Sim, Longos Sim, Longos Sim


Agenda







Deadlocks

103



usando Timestamps

Neste tipo de controle de concorrência, um “timestamp“ (registro do tempo) é associado com cada transação

Timestamps de transações que realizaram leitura ou escrita de cada objeto do BD são também registrados

Usando estes timestamps é possível assegurar que o escalonamento das transações será equivalente ao escalonamento serial definido pelo timestamps das transações

104


Timestamps de Transações Um timestamp é associado com uma transação pelo

escalonador no momento em que a mesma é iniciada

Dada uma transação 𝑇, o timestamp de 𝑇 é denotado por 𝑇𝑆(𝑇)

Timestamps devem ser únicos para cada transação e emitidos em ordem ascendente pelo escalonador Timestamps podem ser obtidos usando o relógio do

sistema ou simplesmente definindo um contador que é incrementado sempre que um novo timestamp é solicitado (notem que neste último caso, o timestamp não possui relação com “tempo”)

105


Timestamp de Objetos do BD

e Bit de Commit

Cada objeto 𝑋 do BD possui dois timestamps e um bit de commit: • 𝑅𝑇(𝑋): o tempo de leitura de 𝑋; consiste no

maior timestamp entre as transações que leram 𝑋

• 𝑊𝑇(𝑋): o tempo de escrita de 𝑋; consiste no maior timestamp entre as transações que escreveram 𝑋

• 𝐶(𝑋): bit de commit de 𝑋; este bit é 1 (verdadeiro) se e somente se a última transação que escreveu 𝑋 já realizou o COMMIT

106


Escalonamentos

Fisicamente Irrealizáveis

Temos que a ordem do timestamp de transações define o escalonamento serial, denotado por 𝑆𝑡, ao qual o escalonamento real das transações deverá ser equivalente

A cada operação de leitura ou escrita, o escalonador verifica se é possível o escalonamento atual poderá ser equivalente à 𝑆𝑡

Caso o escalonamento atual não possa ser equivalente a 𝑆𝑡, dizemos que este escalonamento é fisicamente irrealizável

107


Leituras Atrasadas

108

tempo

Início 𝑇 Início 𝑈

𝑈 escreve em 𝑋 𝑇 lê 𝑋

Temos que quando 𝑇 lê 𝑋, o valor de 𝑋 já foi modificado por 𝑈, que iniciou-se após 𝑇; desta forma, 𝑇𝑆 𝑇 < 𝑊𝑇 𝑋

Entretanto, 𝑇 não deveria ler um valor escrito por 𝑈 porque, de acordo com o escalonamento 𝑆𝑡, 𝑈 é executado depois de 𝑇

Portanto, este escalonamento é fisicamente irrealizável e deverá ser evitado abortando T

Tempo em que a transação ocorre teoreticamente


Escritas Atrasadas

Temos que quando 𝑇 escreve 𝑋, o valor de 𝑋 já foi modificado por 𝑈, que iniciou-se após 𝑇; desta forma, 𝑇𝑆 𝑇 < 𝑅𝑇 𝑋

Entretanto, 𝑇 não deveria escrever um novo valor se o valor antigo foi lido por 𝑈 porque, de acordo com o escalonamento 𝑆𝑡, 𝑈 é executado depois de 𝑇

Portanto, este escalonamento é fisicamente irrealizável e deverá ser evitado abortantdo T

109

tempo


𝑈 lê 𝑋 𝑇 escreve 𝑋

Tempo em que a transação ocorre teoreticamente


Leituras “Sujas” (Dirty Reads)

No escalonamento acima, T lê X que foi escrito por U; como U iniciou-se antes de T temos que TS(T)> 𝑊𝑇(𝑋) e, portanto, o escalonamento é fisicamente realizável

Entretanto, a leitura de 𝑇 sobre 𝑋 é “suja” porque U aborta no final

Neste contexto, é necessário usar o bit de commit 𝐶(𝑋) para verificar se a transação que escreveu em 𝑋 por último já realizou o COMMIT

110

tempo

Início 𝑈 Início 𝑇

𝑈 escreve 𝑋 𝑇 lê 𝑋

𝑈 aborta

Thomas Write Rule

No escalonamento acima, 𝑇 inicia-se antes de 𝑈 mas escreve em 𝑋 depois de 𝑈

Desta maneira, a escrita de 𝑇 poderia ser, em princípio, ignorada: • Qualquer transação 𝑈𝑖, onde 𝑇𝑆 𝑈𝑖 < 𝑇𝑆(𝑈), que tentar ler 𝑋

estará na condição de leitura atrasada e será abortada • Qualquer transação 𝑈𝑖, onde 𝑇𝑆 𝑈𝑖 > 𝑇𝑆(𝑈), que tentar ler 𝑋

deverá ler, de acordo 𝑆𝑡, o valor escrito por 𝑈 e não por 𝑇

Notem que como 𝑇 e 𝑈 escrevem diretamente sobre 𝑋 sem realizar uma operação de leitura antes, não temos uma atualização perdida propriamente dita

111

tempo


𝑈 escreve 𝑋 𝑇 escreve 𝑋


Thomas Write Rule: Problema

Seguindo a Thomas Write Rule, a escrita de 𝑇 seria ignorada. Entretanto se U aborta subsequentemente, então o valor escrito deve ser mantido

Uma solução para este problema seria retardar a escrita de 𝑇 até que a transação 𝑈 realize o COMMIT (neste caso a escrita de 𝑇 é ignorada) ou aborte (neste caso a escrita de 𝑇 é realizada)

112

tempo


𝑈 escreve 𝑋 𝑇 escreve 𝑋

𝑈 aborta


Regras para Escalonamento

Em resposta a uma requisão de leitura e escrita de um transação 𝑇, o escalonador poderá:

• Acatar a requisição

• Abortar 𝑇 com um 𝑅𝑂𝐿𝐿𝐵𝐴𝐶𝐾(𝑇) e reiniciar 𝑇 com um novo timestamp

• Deixar 𝑇 em espera; mais tarde a requisição poderá ser atendida ou 𝑇 poderá ser abortada

113


Regras para Leitura

Suponha que o escalonador recebe a requisição 𝑟𝑇 𝑋 1. Se 𝑇𝑆 𝑇 ≥ 𝑊𝑇(𝑋), então a requisição é

fisicamente realizável a. Se 𝐶(𝑋) é verdadeiro, então acate a requisição. Se

𝑇𝑆(𝑇) > 𝑅𝑇(𝑋) , então faça 𝑅𝑇(𝑋) ← 𝑇𝑆(𝑇)

b. Se 𝐶(𝑋) é falso, então deixe T em espera até que 𝐶(𝑋) seja verdadeiro ou até que a transação que escreveu 𝑋 aborte (para evitar leitura suja)

2. Se 𝑇𝑆 𝑇 < 𝑊𝑇(𝑋), então a requisição é fisicamente irrealizável (leitura atrasada). Aborte 𝑇 e a reinicie com um novo timestamp

114

Regras Escrita

Suponha que o escalonador recebe a requisição 𝑤𝑇 𝑋 1. Se 𝑇𝑆(𝑇) ≥ 𝑅𝑇(𝑇) e 𝑇𝑆(𝑇) ≥ 𝑊𝑇(𝑇) então a escrita é

fisicamente realizável a. Escreva o novo valor de X b. Faça W𝑇(𝑋) ← 𝑇𝑆(𝑇) c. Faça 𝐶(𝑋) = falso

2. Se 𝑇𝑆(𝑇) ≥ 𝑅𝑇(𝑇) mas 𝑇𝑆(𝑇) < 𝑊𝑇(𝑇), então a escrita é fisicamente realizável mas existe uma escrita posterior sobre X

a. Se 𝐶(𝑋) é verdadeiro, ignore 𝑤𝑇 𝑋 (Thomas Write Rule) b. Se 𝐶(𝑋) é falso , então deixe T em espera até que 𝐶(𝑋) seja

verdadeiro (neste caso 𝑤𝑇 𝑋 será ignorada) ou até que a transação que escreveu 𝑋 aborte (neste caso 𝑤𝑇 𝑋 será realizada). Este procedimento evita o problema com a Thomas Write Rule

3. Se 𝑇𝑆 𝑇 < 𝑅𝑇(𝑇), então a requisição é fisicamente irrealizável (escrita atrasada). Aborte 𝑇 e a reinicie com um novo timestamp

115


Regras para COMMIT

Suponha que o escalonador recebe uma requisição para COMMIT(T). Então o mesmo terá percorrer todos objetos 𝑋 escritos por 𝑇 e fazer 𝐶(𝑋) = 1

116


Regras para ABORT

Suponha o escalonador recebe uma requisição para abortar uma transação 𝑇 ou o próprio escalonador decide abortar 𝑇 devido à uma violação das condições para leitura e escrita. Então qualquer transação que estava aguardando por um objeto 𝑋 que 𝑇 escreveu deverá repetir sua tentativa de leitura ou escrita sobre 𝑋

117

Prof. Dr.-Ing. Leonardo Andrade Ribeiro 118

Escalonamento usando

Timestamp: Exemplo

𝑇1 𝑇2 𝑇3 𝐴 𝐵 𝐶

𝑇𝑆 𝑇1 = 200 𝑇𝑆 𝑇2 = 150 𝑇𝑆 𝑇2 = 175 𝑅𝑇 = 0 𝑅𝑇 = 0 𝑅𝑇 = 0

𝑊𝑇 = 0 𝑊𝑇 = 0 𝑊𝑇 = 0

𝑟1 𝐵 𝑅𝑇 = 200

𝑟2 𝐴 𝑅𝑇 = 150

𝑟3 𝐶 𝑅𝑇 = 175

𝑤1 𝐵 𝑊𝑇 = 200

𝑤1 𝐴 𝑊𝑇 = 200

𝑐1 𝑤2 𝐶 Abortado!

𝑤3 𝐴 Ignorado


Agenda







Deadlocks

119


Abordagem Pessimista

Protocolos baseados em bloqueios adotam uma abordagem pessimista para lidar com conflitos entre transações: • transações abortam ou são colocadas em modo em

espera para resolver conflitos; • mesmo em escalonamentos com pouca contenção de

dados, por exemplo, escalonamentos onde a maioria das ações é de leitura, bloqueios ainda devem ser obtidos

Em uma abordagem pessimista, é assumido que conflitos irão ocorrer e medidas tomadas são tomadas a priori para evitar esses conflitos

120


Abordagem Otimista

Uma outra opção é adotar uma abordagem otimista, isto é assumir que a maioria das transações não irão conflitar e ser o mais permissivo possível com relação à permitir que transações executem

Conflitos são identificados após todas as ações de uma transação terem sido realizadas, quando a transação entre no estado de COMMIT parcial

• Conflitos são resolvidos abortando transações

121


Controle de Concorrência Baseado

em Múltiplas Versões

Uma abordagem geral para controle de concorrência consiste em manter, conceitualmente, múltiplas versões do BD, uma versão para cada transação

Desta maneira, uma transação nunca irá ler dados modificados por uma transação que ainda não realizou o COMMIT, tampouco podem ocorrer problemas de leituras não repetíveis e boa parte dos problemas com tuplas fantasmas

A seguir, iremos apresentar uma técnica para controle de concorrência baseada em múltiplas versões chamada snapshot isolation que tem recebido ampla adoção por SGBDs atuais

122


Snapshot Isolation

Abordagem otimista para controle de concorrência baseada em múltiplas versões

Seguindo a estratégia geral de abordagens otimistas, a execução de uma transação em snapshot isolation pode ser dividida em três etapas: 1. Leitura e Execução: a transação recebe a última versão

consistente do BD e realiza ações sobre a mesma de maneira isolada de outras transações

2. Validação: após a transação concluir, as ações da mesma são analizadas para identificação e correção de conflitos com outras transações concorrentes e violações de restrições de integridade

3. Escrita: finalmente, após passar pela etapa de Validação, a modificações da transação são escritas no BD

A seguir, iremos detalhar cada uma dessas etapas

123


Etapa de Leitura e Execução

Nesta etapa inicial, a transação recebe (conceitualmente) uma imagem (snapshot) do BD.

Este snapshot representa a última versão consistente, isto é, todos valores de dados foram escritos por transações que já realizaram o COMMIT.

As ações de escritas sobre o snapshot são restritas no espaço privado da transação e não são visíveis para outras transações

Em outras palavras, a transação opera em completo isolamento em relação a outras transações concorrentes

124

Etapa de Validação

Duas transações concorrentes sobre snapshots privados do BD podem atualizar o mesmo objeto

• Como as transações executam isoladamente, então uma transação não “vê” as atualizações realizadas pela outra transação

Se ambas transações realizarem o COMMIT e escreverem as modificações no BD, então a transação que escrever primeiro as modificações sobrescritas pela segunda transação

• Em outras palavras teremos uma atualização perdida

A etapa de validação é usada em snapshot isolation para identificar e corrigir estes e outros tipos problemas

Durante esta etapa, uma transação encontra-se no estado de COMMIT parcial

• Permissão para passar para etapa de escrita e concluir o COMMIT só ocorre após a resolução de potenciais conflitos

125

Transações Concorrentes

Definição: em snapshot isolation uma transação 𝑇1 é dita concorrente com outra transação 𝑇2 se 𝑇2 estava ativa ou no estado de COMMIT parcial em qualquer ponto no intervalo de tempo após o ínicio e antes da conclusão de sua validação de 𝑇1

126

Evitando Atualizações Perdidas

Existem duas estratégias para evitar atualizações perdidas em snapshot isolation quando uma ou mais transações concorrentes modificam o mesmo objeto do BD: • First committer wins: a transação que realizar o

COMMIT primeiro é validada; a demais são abortadas

• First updater wins: a transação que realizar a atualização primeiro é validada; as demais são abortadas

127

First Committer Wins

Na estratégia first committer wins, quando uma transação 𝑇 entra no estado de COMMIT parcial, as seguintes ações são realizadas de maneira atômica: • Um teste é realizado para verificar se alguma transação

que era concorrente com 𝑇 já realizou o COMMIT e escreveu sobre algum objeto do BD que 𝑇 pretende atualizar

• Se for encontrada alguma transação, então 𝑇 aborta e tem que ser reiniciada

• Se nenhuma transação for encontrada, então 𝑇 tem permissão para realizar o COMMIT e passar para a etapa de escrita

128

First Updater Wins

Na estratégia first updater wins, quando uma transação 𝑇 tentar escrever sobre um objeto do BD, as seguintes ações são realizadas:

• Se este objeto já foi modificado por alguma outra transação concorrente, então T aborta e tem que ser reiniciada

• Caso contrário, 𝑇 prossegue com sua execução

129


Etapa de Escrita

Após a transação passar pela etapa de validação e ter permissão para realizar o COMMIT, as modificações realizadas pela mesma são escritas definitivamente no BD

Todas escritas são realizadas como uma única ação atômica

• Desta maneira, qualquer snapshot criado para outra transação conterá todas modificações dessa transação ou nenhuma delas

130


Problemas de Serializabilidade

Escritas e leituras sujas não são possíveis porque cada transação apenas lê e escreve sobre uma imagem consistente do BD

Atualizações perdidas são evitadas na etapa de validação

Leituras não repetíveis também não são possíveis porque modificações realizadas por transações concorrentes não são visíveis para uma transação

Entretanto, snapshot isolation é suscetível a um tipo de anomalia chamada write skew e certos problemas com tuplas tuplas fantasmas

131


Write Skew

Considere duas transações concorrentes, 𝑇1 e 𝑇2, e dois objetos, 𝐴 e 𝐵. Neste contexto, as seguintes ações são realizadas:

• 𝑇1 lê o valor de 𝐴 e 𝐵 e atualiza o valor de 𝐴

• 𝑇2 lê o valor de 𝐴 e 𝐵 e atualiza o valor de 𝐵

Como as transações atualizaram objetos diferentes, então ambas teriam permissão para realizar o COMMIT na etapa de validação

132


Write Skew (2)

Entretanto, o exemplo anterior não é serializável

Notem que existe um ciclo no grafo de precedência de 𝑇1 e 𝑇2: • 𝑇1 lê um valor de 𝐵 que existia antes da escrita de 𝑇2

• 𝑇2 lê um valor de 𝐴 que existia antes da escrita de 𝑇1

133

1 2

𝑇1 lê 𝐵, 𝑇2 escreve 𝐵

𝑇2 lê 𝐴, 𝑇1 escreve 𝐴

Write Skew: Exemplo

Considere duas contas correntes, 𝐶𝐶1 e 𝐶𝐶2, ambas com saldo de $500, e a restrição de integridade de que a soma do saldo das duas contas não pode ser negativo

Considere duas transações concorrentes, 𝑇1 e 𝑇2 que pretendem debitar $700 de 𝐶𝐶1 e 𝐶𝐶2, respectivamente

As seguintes ações são realizadas: • 𝑇1 verifica que a soma do saldo de 𝐶𝐶1 e 𝐶𝐶2 é $1000 e debita

$700 de 𝐶𝐶1 deixando-a com saldo negativo de $-200 • 𝑇2 verifica que a soma do saldo de 𝐶𝐶1 e 𝐶𝐶2 é $1000 e debita

$700 de 𝐶𝐶2 deixando-a com saldo negativo de $-200

O resultado final das ações concorrentes de 𝑇1 e 𝑇2, é que ambas contas estarão com saldo negativo de $-200 e, portanto, a restrição de integridade será violada • Notem que este resultado final não poderia ocorrer em nenhum

escalonamento serial de 𝑇1 e 𝑇2

134

Evitando Write Skew Uma maneira de evitar a anomalia write skew no nível de

aplicação é acrescentando a cláusula FOR UPDATE em consultas SQL

Ex: SELECT Saldo FROM Contas WHERE ID = 2222 FOR UPDATE; No expressão acima, a cláusula “FOR UPDATE” faz com que

a consulta seja intepretada pelo gerenciador de transações como uma operação de escrita

No exemplo anterior, adicionando “FOR UPDATE” nas consultas de 𝑇1 e 𝑇2 que lêem o saldo das contas 𝐶𝐶1 e 𝐶𝐶2 faria com que apenas uma das transações tivesse permissão para realizar o COMMIT porque seria considerado que as duas transações atualizaram 𝐶𝐶1 e 𝐶𝐶2 135


Problemas com Tuplas Fantasmas

Como transações concorrentes executam sobre uma image privada do BD, então problemas com tuplas fantasmas não podem ocorrer diretamente • Seleções usando predicados sempre retornam o

mesmo conjunto de tuplas

Entretanto, anomalias ainda podem ocorrer de maneira indireta, como será exemplificado a seguir

136


Problemas com Tuplas Fantasmas (2)

Considere uma restrição que define que a soma das horas associadas com um conjunto de tarefas, que é determinada por um predicado 𝑃, não pode ser maior que 8 horas

Neste contexto, uma transação 𝑇1 testa 𝑃, verifica que a soma das horas é 7 e acrescenta uma nova tarefa de uma hora

Ao mesmo tempo, outra transação 𝑇2 realiza as mesmas ações que 𝑇1

Desta maneira, o resultado final será soma das horas igual a 9 Este cenário, que é um exemplo da anomalia de tuplas

fantasmas, não poderia ocorrer em qualquer escalonamento serial, mas é possível em snapshot isolation

137


Outros Problemas de Integridade

Execução isolada de transações concorrentes também é suscetível a violações de restrições básicas de integridade, como por exemplo: • Transações concorrentes podem inserir tuplas em um

tabela com a mesma chave primária • Uma transação pode inserir uma tupla que possui

uma chave estrangeira referenciando uma tupla 𝑡, enquanto outra transação deleta 𝑡

Por este motivo, a etapa de validação deve verificar se estas restrições de integridade não estão sendo violadas antes de permitir que uma transação realize o COMMIT

138


Comparação entre Técnicas de


Comparando as técnicas de bloqueios, timestamps e snapshot isolation temos: • Bloqueios atrasam a execução de transações, mas evitam que

transações abortem (com exceção de casos de deadlocks que serão discutidos logo mais). Timestamps e snapshot isolation não atrasam a execução de transações, mas são mais suscetíveis a “aborts” de transações

• Quando a interferência entre transações é baixa, timestamps e snapshot isolation não irão causar muitos “aborts” de transações e podem ser preferíveis a bloqueios porque os mesmos geralmente apresentam menor overhead

• Quando é necessário abortar uma transação, timestamps normalmente identificam problemas mais cedo do que snapshot isolation, que permite que transações executem todas suas ações antes de decidir se uma transação deve abortar ou não na etapa de validação

139


Agenda







Deadlocks

140


Deadlocks

Um sistema encontra-se em um estado de deadlock se existe um conjunto de transações onde cada transação está esperando por um objeto de dados que está bloqueado por outra transações e nenhuma transação consegue fazer progresso

141

Deadlocks: Exemplo 1

No escalonamento abaixo, 𝑇1 e 𝑇2 não podem fazer progresso porque uma está esperando o objeto que se encontra bloqueado pela outra

142

𝑇1 𝑇2

𝑥1 𝐴 , 𝑟1 𝐴

𝑥2 𝐵 , 𝑟2 𝐵

𝑤1 𝐴

𝑤2 𝐵

𝑥1 𝐵 Negado!

𝑥2 𝐴 Negado!

Deadlocks: Exemplo 2

143

No escalonamento abaixo, 𝑇1 e 𝑇2 ficam em deadlock após ambas obterem bloqueios compartilhados sobre A e tentarem o upgrade subsequentemente

𝑇1 𝑇2

𝑠1 𝐴 , 𝑟1 𝐴

𝑠2 𝐴 , 𝑟2 𝐴

𝑥1 𝐴 Negado!

𝑥2 𝐴 Negado!


Lidando com Deadlocks

Existem duas abordagens gerais para lidar com deadlocks: • Deadlocks podem ser detectados e corrigidos

(normalmente abortando uma ou mais transações envolvidas no deadlock)

• Transações podem ser gerenciadas de maneira a evitar que deadlocks ocorram

Iremos ver três abordagens para lidar com deadlocks • Grafos waits-for

• Esquema wait-die

• Esquema wound-wait

144


Grafos Waits-For

A situação em que transações estão aguardando por bloqueios mantidos por outras transações pode ser representada através do chamado grafo waits-for

Ciclos em grafos waits-for caracterizam a ocorrência de deadlocks

Podem ser usado pelo gerenciador de transações para identificar ou evitar deadlocks • identificar: um grafo waits-for é construído

periodicamente; caso existam ciclos, uma ou mais transações são abortadas

• prevenir: um grafo é mantido e ações que possam criar ciclos no grafo não são permitidas

145


Grafos Waits-For: Descrição

Cada transação que possui um bloqueio ou está aguardando por um é representada por um vértice

Existe uma aresta direcionada do vértice representando a transação 𝑇 para o vértice representando a transação 𝑈 se existe um objeto 𝐴 do BD tal que: • 𝑈 mantém um bloqueio sobre 𝐴, • 𝑇 está aguardando por um bloqueio sobre 𝐴, • 𝑇 não pode obter um bloqueio sobre 𝐴 enquanto 𝑈

não libere seu bloqueio sobre 𝐴

146


Grafos Waits-For: Deadlocks

Transações envolvidas em um ciclos em um grafo waits-for não podem progredir com a execução; portanto temos um deadlock

• A solução é abortar uma transação

Se não existem ciclos em um grafo waits-for, então cada transação poderá completar

• Existe pelo menos uma transação que não está esperando por nenhuma outra transação

147

Waits-for Grafo: Exemplo

148

𝑇1 𝑇2 𝑇3 𝑇4

𝑥1 𝐴 , 𝑟1 𝐴

𝑥2 𝐶 , 𝑟2 𝐶

𝑥3 𝐵 , 𝑟3 𝐵

𝑥4 𝐷 , 𝑟4 𝐷

𝑥2 𝐴 , Negado!

1 2

No escalonamento acima, a transação 𝑇2 está aguardando para obter um bloqueio de escrita sobre 𝐴, que está sendo mantido por 𝑇1. Portanto, existe uma aresta do vértice 2 para o vértice 1


Agora, 𝑇3 aguarda por um bloqueio de escrita sobre 𝐶, que está sendo mantido por 𝑇2

149

𝑇1 𝑇2 𝑇3 𝑇4

𝑥1 𝐴 , 𝑟1 𝐴

𝑥2 𝐶 , 𝑟2 𝐶

𝑥3 𝐵 , 𝑟3 𝐵

𝑥4 𝐷 , 𝑟4 𝐷


𝑥3 𝐶 , Negado!

1 2 3


Agora, 𝑇4 também aguarda por um bloqueio de escrita sobre 𝐴, que está sendo mantido por 𝑇1

150

𝑇1 𝑇2 𝑇3 𝑇4

𝑥1 𝐴 , 𝑟1 𝐴

𝑥2 𝐶 , 𝑟2 𝐶

𝑥3 𝐵 , 𝑟3 𝐵

𝑥4 𝐷 , 𝑟4 𝐷




1 2 3 4


Um ciclo é formado quando 𝑇1 requisita um bloqueio de escrita sobre 𝐵, que está sendo mantido por 𝑇3

151

𝑇1 𝑇2 𝑇3 𝑇4

𝑥1 𝐴 , 𝑟1 𝐴

𝑥2 𝐶 , 𝑟2 𝐶

𝑥3 𝐵 , 𝑟3 𝐵

𝑥4 𝐷 , 𝑟4 𝐷




𝑥1 𝐵 , Negado!

1 2 3 4


𝑇1 é abortada e o ciclo eliminado

152

𝑇1 𝑇2 𝑇3 𝑇4

𝑥1 𝐴 , 𝑟1 𝐴

𝑥2 𝐶 , 𝑟2 𝐶

𝑥3 𝐵 , 𝑟3 𝐵

𝑥4 𝐷 , 𝑟4 𝐷




𝑥3 𝐵 , Negado!

𝑎1

2 3 4

Gerenciamento de Deadlocks

usando Timestamps

Timestamps podem ser usados para prevenir deadlocks

Quando uma transação 𝑇 requisita um bloqueio que está sendo mantido por uma transação 𝑈, então os timestamps de 𝑇 e 𝑈 são comparados para identificar qual transação iniciou a execução primeiro • 𝑇𝑆(𝑇) = tempo de ínicio da execução de 𝑇

• 𝑇𝑆 𝑇 < 𝑇𝑆 𝑈 significa que 𝑇 é mais antiga que 𝑈

Existem dois esquemas diferentes para gerenciar transações e detectar deadlocks • Wait-die

• Wound-wait

153

Esquema Wait-Die

Considere que 𝑇 requisita um bloqueio que está sendo mantido por 𝑈

De acordo com o esquema wait-die, a seguinte política é aplicada:

a. Se 𝑇 é mais antiga que 𝑈, então 𝑇 aguarda (waits) até que 𝑈 libere o bloqueio

b. Se 𝑈 é mais antiga que 𝑇, então 𝑇 é abortada (dies)

154

Esquema Wound-Wait

Considere que 𝑇 requisita um bloqueio que está sendo mantido por 𝑈

De acordo com o esquema wound-wait, a seguinte política é aplicada:

a. Se 𝑇 é mais antiga que 𝑈, então 𝑇 faz com que U seja abortada (wounds) e obtém o bloqueio

b. Se 𝑈 é mais antiga que 𝑇, então 𝑇 aguarda (waits) até que 𝑈 libere o bloqueio

155

Timestamps de Transações

Notem que este timestamp é usado apenas para gerenciamento de deadlocks: não confundir com o timestamp usado para controle de concorrência visto anteriormente • Em particular, quando uma transação é abortada

devido ao controle de concorrência, a transação é reiniciada com um novo timestamp, com valor maior que o timestamp original

• Quando uma transação é abortada devido ao gerenciamento de deadlocks, a transação é reiniciada com o mesmo timestamp

156

Wait-Die: Exemplo

157

Passo 𝑇1, 𝑇𝑆 𝑇1 = 1 𝑇2, 𝑇𝑆 𝑇2 = 2 𝑇3, 𝑇𝑆 𝑇3 = 3 𝑇4, 𝑇𝑆 𝑇4 = 4

1 𝑠1 𝐴 , 𝑟1 𝐴

2 𝑥2 𝐴 , 𝐴𝑏𝑜𝑟𝑡!

3 𝑠3 𝐵 , 𝑟3 𝐵

4 𝑥4 𝐴 , 𝐴𝑏𝑜𝑟𝑡!

5 𝑥3 𝐶 , 𝑤3 𝐶

6 𝑢3 𝐵 , 𝑢3 𝐶 , 𝑐3

7 𝑥1 𝐵 , 𝑤1 𝐵

8 𝑢1 𝐴 , 𝑢1 𝐵 , 𝑐1 𝑇4 reinicia

9 𝑇2 reinicia 𝑥4 𝐴 , 𝑠4 𝐷

10 𝑥2 𝐴 , 𝐸𝑚 espera!

11 𝑟4 𝐷 , 𝑤4 𝐴

12 𝑢4 𝐴 , 𝑢4 𝐷 , 𝑐4

13 𝑥2 𝐴 , 𝑠2 𝐶

14 𝑟2 𝐶 , 𝑤2 𝐴

15 𝑢2 𝐴 , 𝑢2 𝐶 , 𝑐2

Wait-Die: Exemplo

Usando o esquema wait-die, os principais eventos no escalonamento anterior são: Passo 1: 𝑇1 obtém um bloqueio sobre 𝐴 Passo 2: 𝑇2 tenta obter um bloqueio sobre 𝐴 e é abortada porque 𝑇1 já possui um bloqueio incompátivel sobre 𝐴 e 𝑇𝑆 𝑇1 < 𝑇𝑆 𝑇2 Passos 4: 𝑇4 também tenta obter um bloqueio sobre 𝐴 e é abortada porque 𝑇1 já possui um bloqueio incompátivel sobre 𝐴 e 𝑇𝑆 𝑇1 <𝑇𝑆 𝑇4 Passo 6: Após obter com sucesso os bloqueios sobre 𝐵 (Passo 3) e 𝐶 (Passo 5), 𝑇3 completa Passo 8: 𝑇1 completa e 𝑇4 reinicia (com o mesmo timestamp) Passos 9: 𝑇4 obtém bloqueio sobre 𝐴; 𝑇2 reinicia Passo 10: 𝑇2 tenta obter um bloqueio sobre 𝐴 e é colocada em espera porque𝑇4 já possui um bloqueio incompátivel sobre 𝐴 e 𝑇𝑆 𝑇2 < 𝑇𝑆 𝑇4 Passos 12 e 15: 𝑇4 e 𝑇2 completam nos passos 12 e 15, respectivamente

158

Wound-Wait: Exemplo

159

Passo 𝑇1, 𝑇𝑆 𝑇1 = 1 𝑇2, 𝑇𝑆 𝑇2 = 2 𝑇3, 𝑇𝑆 𝑇3 = 3 𝑇4, 𝑇𝑆 𝑇4 = 4

1 𝑠1 𝐴 , 𝑟1 𝐴

2 𝑥2 𝐴 , Em espera!

3 𝑠3 𝐵 , 𝑟3 𝐵

4 𝑥4 𝐴 , 𝐸𝑚Espera!

5 𝑥1 𝐵 , 𝑤1 𝐵 𝐴𝑏𝑜𝑟𝑡!

6 𝑢1 𝐴 , 𝑢1 𝐵 , 𝑐1

7 𝑥2 𝐴 , 𝑠2 𝐶

8 𝑟2 𝐶 , 𝑤2 𝐴

9 𝑢2 𝐴 , 𝑢2 𝐶 , 𝑐2

10 𝑥4 𝐴 , 𝑠4 𝐷

11 𝑟4 𝐷 , 𝑤4 𝐴

12 𝑇3 reinicia 𝑢4 𝐴 , 𝑢4 𝐷 , 𝑐4

13 𝑠3 𝐵 , 𝑟3 𝐵

14 𝑥3 𝐶 , 𝑤3 𝐶

15 𝑢3 𝐵 , 𝑢3 𝐶 , 𝑐3

Wound-Wait: Exemplo Usando o esquema wound-die, os principais eventos no

escalonamento anterior são: Passo 1: 𝑇1 obtém um bloqueio sobre 𝐴 Passo 2: 𝑇2 tenta obter um bloqueio sobre 𝐴 e é colocada em espera porque 𝑇1 já possui um bloqueio incompátivel sobre 𝐴 e 𝑇𝑆 𝑇1 < 𝑇𝑆 𝑇2 Passos 4: 𝑇4 também tenta obter um bloqueio sobre 𝐴 e é colocada em espera porque 𝑇1 já possui um bloqueio incompátivel sobre 𝐴 e 𝑇𝑆 𝑇1 < 𝑇𝑆 𝑇4 Passo 5: 𝑇1 obtém um bloqueio sobre 𝐵 e, com isso, 𝑇3 que havia obtido um bloqueio sobre 𝐵 no Passo 3, é abortada porque 𝑇𝑆 𝑇1 < 𝑇𝑆 𝑇3 Passo 6 e 7: 𝑇1 completa no Passo 6, liberando o bloqueio sobre 𝐴, que é obtido por 𝑇2 no Passo 7 Passos 9 e 10: 𝑇2 completa no Passo 9, liberando o bloqueio sobre 𝐴, que é obtido por 𝑇3 no Passo 10 Passos 12 e 15: 𝑇4 completa e 𝑇3 reinicia no passos 12; 𝑇3 completa no Passo 15

160

Wait-Die vs. Wound-Wait

Em wound-wait, uma transação mais nova é abortada sempre que uma transação mais velha requisita um bloqueio mantido pela transação mais nova

Normalmente, uma transação tende a obter bloqueios no estágio inicial de sua execução

Baseando-se na assunção acima, será raro em wound-wait a situação em que uma transação antiga é abortada devido a uma requisição de bloqueio de outra transação ainda mais velha

Portanto, aborts de transações são raros em wound-wait

No caso de wait-die, aborts serão mais frequentes porque quando uma transação requisita um bloqueio mantido por outra transação, é mais provável que a transação que mantém o bloqueio seja mais velha

161

Wait-Die vs. Wound-Wait (2)

Quando um abort ocorre em wait-die, a transação abortada provavelmente estará no estágio inicial e uma quantidade relativamente menor de ações terão que ser desfeitas

Por outro lado, quando um abort ocorre em wound-wait, a transação provalmente já terá realizado uma quantidade maior de ações que terão que ser desfeitas

Portanto, aborts são mais raros em wound-wait do que em wait-die, mas quando estes ocorrem, o overhead com o processo de undo será maior em wound-wait

162

Timestamps vs. Grafo Waits-For

Usando timestamps, transações abortadas sempre reiniciam com o timestamp original

Portanto, tanto em wait-die quanto em wound-wait, uma transação que for abortada irá se tornar mais velha em relação às demais transações ativas quando reiniciar

Portanto, usando timestamps, existe a garantia que todas transações irão completar • Em outras palavras, timestamps não é suscetível ao problema

conhecido como starvation

Usando waits-for para detectar deadlocks, caso nenhuma outra medida seja adotada, uma transação pode indefinidamente ser abortada e reiniciada em uma nova situação de deadlock

163

Timestamps vs. Grafo Waits-For (2)

Wait-die e wound-wait são mais simples de implementar do que a construção periódica grafos waits-for

Por outro lado, usando grafos waits-for, uma transação só é abortada quando a mesma realmente está envolvida em um deadlock; usando timestamps, transações podem ser abortadas mesmo sem estar em situação de deadlock e sem a possibilidade de entrar em deadlock ao longo de sua execução

164

Referências Adicionais

Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, Irving L. Traiger: Granularity of Locks and Degrees of Consistency in a Shared Data Base. IFIP Working Conference on Modelling in Data Base Management Systems 1976: 365-394

165

Software

Banco de Dados 2: Controle de Concorrência