Sistemas de Gerenciamento de Bancos de Dados José Maria Monteiro Universidade Federal do Ceará Departamento de Computação [email protected]

Sistemas de Gerenciamento de Bancos de Dados

José Maria MonteiroUniversidade Federal do CearáDepartamento de Computação

[email protected]

© José Maria Monteiro. 2

Sumário Processamento de Transações Controle de Concorrência Recuperação (Reconstrução após Falha) Armazenamento de Dados Processamento de Consulta Otimização de Consulta Projeto Físico e Tuning de Banco de Dados Segurança


Processamento de Transações


Processamento de Transações

Introdução ao Processamento de Transações

O Conceito de Transação Propriedades das Transações Execução Correta de Transações

Concorrentes O Conceito de Schedule Schedules Serializáveis O Teorema da Serializabilidade Confiabilidade de Schedules


Introdução ao Processamento de

Transações Banco de Dados

Coleção de objetos que representam entidades do mundo real

Cada objeto do BD tem um nome e um valor• Ex: Conta A com valor de 5.000

Estado do BD Conjunto de valores de todos os objetos do BD

em um dado instante de tempo



Transações Estado do BD

O estado de um banco de dados representa uma visão instantânea do mundo real

Reflete apenas seus aspectos estáticos As mudanças que ocorrem no mundo real

devem ser refletidas no BD Transição de Estados

Representa o saldo de um estado para outro



Transações Transição de Estados

São realizadas pelos programas aplicativos • Executam operações de leitura e escrita sobre os

objetos do BD Restrições de Consistência

O mundo real impõe certas restrições sobre o BD• Ex: Uma conta bancária não pode ter saldo negativo

Logo, os bancos de dados devem capturar estas restrições, chamadas restrições de consistência



Transações Consistência

Se todos os objetos de um banco de dados, em um dado instante,

satisfazem todas as restrições de consistência dizemos que o estado do banco de dados é

consistente.



Transações Execução Concorrente

As aplicações executam em modo concorrente Através do entrelaçamento das operações de

diferentes programas Pode levar a mudanças inconsistentes

P1 P2 __ Read(A)

Read(A) Write(A, A- 100)

Write (A, A-200)

Tem

po



Transações

A execução concorrente de programas aplicativos deve ser

monitorada e controlada.

Esta funcionalidade é chamada controle de concorrência.



Transações Modelo Transacional Clássico

Nem todas as operações de um programa são relevantes, somente

as operações sobre o banco de dados necessitam ser

consideradas.




Uma transação é uma abstração que representa uma seqüência de operações sobre o banco de dados

(leitura e escrita) resultante da execução de um programa

aplicativo.




A execução concorrente de um conjunto de transações é realizada através do entrelaçamento das operações que compõem as várias transações

Alguns entrelaçamentos podem produzir estados inconsistentes

Quando uma execução concorrente de um conjunto de transações esta corretamente entrelaçada ??? Ou seja, resulta em estados consistentes ???




Um estado consistente do banco de dados representa uma visão

coerente do mundo real.




Critério de Corretude: Uma execução de transações

concorrentes é correta se ela produz um estado consistente do

banco de dados.




A primeira vista este critério de corretude parece bastante razoável

Infelizmente• Nas aplicações reais nem todas as restrições de

consistência são conhecidas• Torna inviável a identificação de um estado

consistente




Em geral, a única informação disponível sobre as restrições de consistência é que uma aplicação

(transação) preserva a consistência do banco de dados.




Se o estado do BD estava consistente antes do início da

transação ele será consistente após o término da transação. Estados

intermediários podem estar incoerentes.




A execução de uma transação é correta, ou seja, preserva a

consistência do BD, se a transação é executada por completo e de forma

isolada das demais transações.




Desde que a execução de uma transação seja correta, é fácil

mostrar, usando indução sobre o número de transações, que qualquer execução serial de um conjunto de

transações é correta.




Serializabilidade: Se uma execução concorrente de um conjunto de

transações é equivalente à alguma execução serial das mesmas

transações, então ela também é correta.




Serializabilidade• Proporciona a ilusão que a execução concorrente de

múltiplas transações acontece de forma serial• Ilusão de que a execução de uma transação consiste

em uma ação atômica• Uma transação é considerada uma unidade de

execução atômica


Definição

Uma transação é uma abstração que representa uma seqüência de operações sobre o banco de dados

(leitura e escrita) resultante da execução de um programa

aplicativo.

O Conceito de Transação


O Conceito de Transação

Transações Transações são usadas para representar as

operações sobre o banco de dados executadas pelas aplicações

Indicam a ordem na qual as operações sobre o banco de dados devem ser executadas


O Conceito de Transação Operações

ri(x)• A transação Ti lê o item de dado chamado x para

uma variável de programa wi(x)

• Escreve o valor de uma variável de programa no item de dado x

r1(x);x:=x-n;w1(x);r1(y);y:=y+n;w1(y);

r2(x);x:=x+m;w2(x);

T1T2


O Conceito de Transação Ações Transacionais

begin_transaction: início da execução de uma transação

read ou write: modificam os dados da base end_transaction: limite final da execução de

uma transação commit: final da transação com sucesso. Torna

permanente as modificações nos dados rollback: efeitos da transação sobre os dados

devem ser desfeitos


O Conceito de Transação Diagrama de Estados

Ativa

begin transaction

Parcialmente Validada

end transaction

Validadacommit

FinalizadaFalha

rollback

rollback

read, write


O Conceito de Transação Notação

OP(Ti)• Representa o conjunto de todas as operações

executadas pela transação Ti

Commit (ci)• Indica que a transação Ti encontra-se no estado

parcialmente executado e que deseja passar para o estado executado (commited)

Abort (ai)• Indica que a transação Ti deseja entrar no estado

de falha (aborted)


O Conceito de Transação Notação

Uma transação Ti deverá conter após todas as operações de leitura e escrita uma operação commit (ci) ou abort (ai), mas não ambas


O Conceito de Transação Definição

Mais formalmente podemos definir uma transação Ti como uma ordem com relação de ordem <i onde:(1) OP(Ti) {ri(x), wi(x) | x é um item de dado}

{ai, ci}

(2) ai Ti se e somente se ci Ti

(3) Seja t ci ou ai, para qualquer operação p Ti , p <i t e

(4) Se ri(x), wi(x) Ti, então ri(x) <i wi(x) ou wi(x) <i ri(x)

A relação de ordem <i representa a precedência entre duas operações de uma

transação Ti.


Objetivo do Controle de Concorrência

Transações Concorrentes

Maximizar a concorrência entre as transações ao mesmo tempo em

que garante a consistência do banco de dados.


Execução de Transações Concorrentes


A execução concorrente de um conjunto de transações é realizada

através do entrelaçamento das operações que compõem as várias

transações.


História ou Schedule Uma história ou schedule indica a ordem na

qual as operações de um conjunto de transações são executadas com relação uma com as outras, ou seja, ela representa uma execução concorrente

A ordem das operações em uma transação deve ser preservada• Se pi precede qi, na transação Ti (isto é, pi <i qi), então

a execução de pi deve acontecer antes de qi em qualquer schedule contendo Ti.

A execução de um schedule representa o mapeamento de um estado do banco de dados para outro



Notação OP(S)

• Representa o conjunto das operações executadas no schedule S

p <s q• Indica que a operação p foi executada antes da

operação q no schedule S• Ex:

ri(x) <s rj(y) representa o fato de que a operação ri(x) Ti precede rj(y) Tj, no schedule S, onde S é executado sobre um conjunto de transações T e Ti, Tj T



Notação Seja S um schedule sobre o conjunto G L de

transações, onde G e L são conjutos disjuntos de transações. A projeção do schedule S sobre o conjunto G é um schedule S’ para o qual as seguintes condições devem ser satisfeitas:(1) S’ contem somente as operações das transações

pertencentes ao conjunto G. (2) p,q OP(S’) p, q OP(S)(3) p,q OP(S’), p <s’ q p <s q



Schedule Serial Um schedule S é serial se, para cada par de

transações Ti, Tj S, todas as operações de Ti aparecem antes de todas as operações de Tj ou vice-versa.

Assim podemos denotar um schedule serial sobre T1, T2, T3, ..., Tn como Ti1, Ti2, Ti3, ...., Tin onde i1, i2, ...., in é uma permutação de 1, 2, ... , n.



Schedule Serial Não permite entrelaçamento entre as

operações das transações Processamento ineficiente: perda

desnecessária de tempo de CPU Premissa: A execução de uma transação simples,

de forma completa e isolada das demais transações, preserva a consistência do banco de dados




Schedule Serial É fácil mostrar usando indução, que qualquer

execução serial de (schedule serial) de um conjunto de transações é correta, ou seja, preserva a consistência do banco de dados

Se um schedule tem n transações então teremos (n)! schedules seriais corretos



Schedule Não-Serial Na prática, as transações são executadas em modo

concorrente Entrelaçamento entre as operações das transações Aumenta o throughput: maior número de transações

por espaço de tempo Interferência entre as transações pode gerar

inconsistências no banco de dados O número de schedules não-seriais é enorme



Exemplos de Schedules

T1 T2

read(x)x:=x-nwrite(x)read(y)y:=y+nwrite(y)

read(x)x:=x+nwrite(x)

Schedule Serial

T1 T2

read(x)x:=x-n

read(x)x:=x+n

Schedule Não-Serial Incorreto

write(x)read(y)

write(x)y:=y+nwrite(y)

T1 T2

read(x)x:=x-nwrite(x)


Schedule Não-Serial Correto

read(y)y:=y+nwrite(y)



Critério de Corretude Se uma execução concorrente de um conjunto de

transações T é equivalente a alguma execução serial de T então ela também é correta

Um schedule S é serializável se ele for equivalente a algum schedule serial Ss . Logo, um schedule serializável é correto.



Critério de Corretude Desta forma, reduzimos o problema de identificar

schedules corretos ao problema de definir equivalência entre schedules

Existem três noções de equivalência entre schedules• Equivalência por estado final• Equivalência por visão• Equivalência por conflito



Equivalência por Estado Final Dois schedules executados sobre o mesmo conjunto

de transações T são ditos equivalentes por estado final se:(i) possuem as mesmas operações pertencentes às

transações em T, e(ii) produzem o mesmo estado do banco de dados, caso

sejam executadas a partir do mesmo estado inicial



Equivalência por Estado Final Classe mais genérica de equivalência entre schedules Idéia:

Identificar schedules que realizam a mesma transição de estados quando são executados a partir do mesmo estado inicial

Dois schedules equivalentes por estado final produzem o mesmo efeito sobre o banco de dados


Transações Concorrentes Equivalência por Visão

Dois schedules S e S’ executados sobre o mesmo conjunto de transações T são ditos equivalentes por visão se:(i) envolvem as mesmas operações pertencentes às

transações em T,

(ii) para toda operação ri(x) de uma transação Ti T, o valor lido por ri deve ser o mesmo nos dois schedules, e

(iii) se wi(x) é a última operação sobre um objeto x em S, então wi(x) é também a última operação de escrita sobre x em S



As operações de leitura em schedules equivalentes por visão têm a mesma visão do BD

Como o resultado de uma operação de escrita é uma função de todos os valores lidos anteriormente pela transação, a condição (iii) garante que a última operação de escrita nos dois schedules produzem o mesmo efeito sobre o banco de dados

Schedules equivalentes por visão produzem o mesmo efeito sobre o banco de dados



Observe a condição (ii): representa uma restrição sobre a classe de schedules

equivalentes por estado final requer que schedules equivalentes por estado final

tenham a mesma visão do banco de dados A equivalência por visão é um caso especial de

equivalência por estado final A classe de schedules equivalentes por visão é um

subconjunto da classe de schedules equivalentes por estado final



Dois schedules equivalentes por visão são também equivalentes por estado final


Transações Concorrentes Equivalência por Conflito

Duas operações de diferentes transações conflitam (ou estão em conflito) se e

somente se elas acessam o mesmo objeto do banco de dados e pelo menos uma

delas é uma operação de escrita.



De acordo com a definição de conflito: uma operação ri(x) sempre conflita com wj(x) e wi(x) conflita com rj(x) e wj(x), onde i j. wi(x) não conflita com wj(y) ri(x) não conflita com rj(x)



Dois schedules S e S’ executados sobre o mesmo conjunto de transações T são ditos equivalentes por conflito se:(i) envolvem as mesmas operações pertencentes às

transações em T,

(ii) para toda operação pi(x) OP(Ti) que conflita com uma operação qj OP(Tj) , com i j, se pi <s qj, então pi <s’ qj



Dois schedules são equivalentes por conflito se as operações que conflitam estão na mesma ordem

Podemos distinguir três conceitos de schedules corretos: Serializabilidade por estado final (FSR) Serializabilidade por visão (VSR) Serializabilidade por conflito (CSR)


Transações Concorrentes Três conceitos de schedules corretos:

Serializabilidade por estado final (FSR)• Um schedule S é serializável por estado final se ele é

equivalente por estado final a algum schedule serial. Serializabilidade por visão (VSR)

• Um schedule S é serializável por visão se ele é equivalente por visão a algum schedule serial.

Serializabilidade por conflito (CSR)• Um schedule S é serializável por conflito se ele é

equivalente por conflito a algum schedule serial.



Cada noção de corretude representa um grau de concorrência diferente• Pode permitir um maior ou menor entrelaçamento entre as

operações das diferentes transações• Quanto maior for entrelaçamento permitido menos

restritivo será o critério de corretude

• FSR VSR CSR• Um schedule S é serializável por conflito se ele é

equivalente por conflito a algum schedule serial.



Serializabilidade por estado final• Baseia-se nos conceitos de estado inicial e final do banco,

os quais não são capturados pelo conceito de schedule Serializabilidade por visão

• Verificar se um schedule é serializável por visão é um problema NP-Completo

Serializabilidade por conflito• Podemos verificar se um schedule é serializável por

conflito em tempo polinomial• Quase todos os trabalhos práticos implementam a

serializabilidade por conflito como critério de corretude


Transações Concorrentes Serializabilidade por Conflito

Verificando se um schedule S é serializável por conflito• A idéia básica consiste em verificar se um grafo direcionado,

chamado grafo de serialização, possui ou não ciclos


Transações Concorrentes Grafo de Serialização

Seja S um schedule sobre um conjunto de transações T = {T1, T2, ... , Tn}.

O grafo de serializaçãoo para S, representado por GS(S), é definido como:• O grafo direcionado GS(S) = (N,A)• Cada nó em N representa uma transação em T• O conjunto A contém as arestas na forma Ti Tj , se e

somente se Ti, Tj N e existem duas operações p OP(Ti) e q OP(Tj), onde p conflita com q e p <S q


Transações Concorrentes Serializabilidade por Conflito

O conceito de grafo de serialização proporciona um método eficiente para identificar schedules CSR

Teorema• Um schedule S é serializável por conflito se e somente se o

grafo de serialização para S é acíclico.


Transações Concorrentes Propriedade “prefix-closed”

Temos analisado a corretude de schedules completos• Os quais são representados através da execução completa

das transações• Ambientes dinâmicos considerar schedules incompletos

“prefix-closed”• Se um schedule S é correto então qualquer prefixo de S

também é correto• Nem todo critério de corretude é “prefix-closed”

Teorema:• A serializabilidade por conflito é “prefix-closed”


Transações Concorrentes Protocolos para Controle de Concorrência

Potocolos Pessimistas (Controle Contínuo)• Verificação antes de executar operação sobre a base• A verificação contínua penaliza o desempenho das transações

Protocolos Otimistas• Não há qualquer verificação durante a execução das

transações• Serializabilidade verificada em um único instante

No momento da validação• Pouca interferência -> Ótimo desempenho• Muita interferência -> Descartes demais



Protocolos Otimistas• Fase de Leitura

As transações fazem acesso à base mas atualizam cópias em um espaço particular de trabalho

• Fase de Validação Verifica se as modificações realizadas pela transação não

violam a serializabilidade• Fase de Atualização

Se a validação tem sucesso a base é atualizada, caso contrário as modificações são descartadas



Protocolos Otimistas

Validação de T

Conjunto de objetos de T:

readSet e writeSet

OK se não há conflito de acesso entre os objetos de T e objetos de T’



Potocolos Baseados em Lock• Bloqueio

Protocolos Não Baseados em Lock• Teste do Grafo de Serialização (TGS)• Ordenação por “timestamp”


Transações Concorrentes Protocolo do Teste do Grafo de Serialização

Idéia:

Evitar (prevenir) a ocorrência de ciclos no grafo

Ciclo Schedule não é serializável por conflito

Estratégia:

Monitoramento e gerenciamento dinâmico de um grafo que deve ser sempre acíclico


Transações Concorrentes Funcionamento do TGS

Inicialmente o GS é criado como um grafo vazio Quando o escalonador recebe a primeira operação de

uma transação Ti, um nó representando Ti é inserido no grafo

Para cada operação pi(x) OP(Ti) que o escalonador recebe, ele checa se existe qj(x) OP(Tj) que conflita com pi(x) e já escalonada.

Caso qj(x) exista:

é incluída uma aresta da forma Tj Ti


Transações Concorrentes Funcionamento do TGS

Em seguida, o escalonador verifica se a nova aresta introduz um ciclo no grafo

Em caso afirmativo, o escalonador rejeita a operação pi(x), desfaz o efeito das operações de Ti e remove a

aresta inserida

Caso contrário, pi(x) é aceita e escalonada


T2 T5

T1 T3

Servidorde BD

Cliente A Cliente BT1=rT1

(IBM) rT1

(SUN)

T2=wT2(IBM) CT2

T3=rT3(IBM)

rT3

(SUN)

T4= wT4(SUN) CT4

T5= wT5(SUN) CT5

IBM SUN

T4



T1 T2 T3 T4 T5

C3r1(IBM) w2(IBM) C2w5(SUN) C5 r3(IBM) r3(SUN) w4(SUN) C4 r1(SUN) C1



Transações Concorrentes Problemas de Acesso Concorrente

Perda de Atualização

T1 T2

read(x)x:=x-n

read(x)x:=x+n

A atualização de T1 sobre x é perdida

write(x)read(y)

write(x)y:=y+nwrite(y)

Tem

po



Leitura Suja

T1 T2



read(y)abort

Se T1 abortar, x em T2 estará incorreto

Tem

po



Leitura Não Repetitível

T1 T2


read(x)

read(y)

read(x)

Novo acesso a x em T2 não corresponde ao anterior

Tem

po


Transações Concorrentes Protocolos Baseados em Bloqueio

Idéia:

Evitar (prevenir) a formação de ciclos no grafo

Estratégia:

Assegura a serializabilidade controlando o acesso aos dados

Enquanto uma transação acessa um item de dado, nenhuma outra transação pode modificar este item

Utiliza o conceito de bloqueio



Tipos de Bloqueio

Bloqueio Compartilhado ou Partilhado

Se uma transação Ti obteve um bloqueio no modo compartilhado sobre o item q, então Ti pode ler este item, mas não pode gravar q

Bloqueio Exclusivo

Se uma transação Ti obteve um bloqueio no modo exclusivo sobre o item q, então Ti pode ler e gravar q



O acesso aos dados é dirigido por bloqueios

Antes de manipular um objeto, uma transação deve obter a permissão através de um bloqueio

O lock manager mantém uma tabela de bloqueios

Função de Compatibilidade

Verdadeiro Falso

Falso Falso

S

S X

X

S Bloqueio Compartilhado

X Bloqueio Exclusivo



Operações lock-S(q) Bloqueio compartilhado sobre o item q lock-X(q) Bloqueio exclusivo sobre o item q unlock(q) Libera bloqueios sobre o item q

Funcionamento (Prot. Bloqueio Básico) Antes que um item q seja acessado (leitura ou escrita)

por uma transação Ti esta deve bloquear q Se q já está bloqueado em modo incompatível Ti deve

esperar até que o item q esteja desbloqueado ou bloqueado em modo compatível


T1 T2

lock-X(b)read(b)write(b)

lock-S(A)read(A)lock-S(b)espera unlock de b ...

DEADLOCK

lock-X(a)espera...

Tem

po


Exemplo



Deadlock ou Impasse Uma transação T1 espera por um objeto bloqueado por

T2 enquanto T2 espera por um objeto bloqueado por T1


T1 T2

lock-S(y)read(y)unlock(y) lock-S(x)

read(x)unlock(x)lock-X(y)read(y)y = x + ywrite(y)unlock(y)lock-X(x)

read(x)x = x + ywrite(x)unlock(x)

Tem

po


Exemplo

Schedule correto ?

Schedule serializável por conflito ?



Exemplo Assuma os seguintes valores iniciais: x = 20 e y = 10 O schedule anterior resulta em: x = 30 e y = 30 Execução serial T1 T2 resulta em: x = 30 e y = 40 Execução serial T2 T1 resulta em: x = 40 e y = 30



Prot. Bloqueio Básico Resolve

Perda de Atualização Leitura Suja

Não garante a serializabilidade por conflito



Bloqueio em Duas Fases (2PL)

Transações são divididas em duas fases

Fase de expansão

Uma transação Ti pode obter bloqueios

Ti não pode liberar objetos (desbloqueio)

Fase de encolhimento

Ti libera objetos (desbloqueio)

Ti não pode obter novos bloqueios



Bloqueio em Duas Fases (2PL)

Funcionamento

Inicialmente, uma transação está na fase de crescimento.

A transação adquire tantos bloqueios quantos forem necessários.

Uma vez que a transação libera um bloqueio, ela entra na fase de encolhimento e não pode mais emitir requisições de bloqueio.


T1 T2

lock-S(y)read(y)lock-X(x) lock-S(x)

espera ...unlock(y)read(x)x = x + ywrite(x)unlock(x)

Tem

po


Exemplo

Schedule correto ?

Schedule serializável por conflito ?read(x)

unlock(x)lock-X(y)read(y)y = x + ywrite(y)unlock(y)


T1 T2

lock-X(b)read(b)write(b)

lock-S(A)read(A)lock-S(b)espera unlock de b ...

DEADLOCK

lock-X(a)espera...

Tem

po


Exemplo



Prot. Bloqueio em Duas Fases (2PL) Assegura a serializabilidade por conflito Não esta livre de deadlock (não é deadlock-free)


Transações Concorrentes Resolvendo Impasses (Deadlock)

Existem dois métodos principais para tratar com o problema de impasse: Prevenção de Impasse

Assegura que o sistema nunca entrará no estado de impasse

Detecção de Impasses + Recuperação Permite que o sistema entre num estado de impasse Uma vez detectado um impasse então tenta

recuperar



As duas estratégias podem resultar em transações refeitas (aborts)

Possibilidade de aborts em cascata



Prevenção de Deadlocks Protocolo Conservative 2PL ou Static 2PL

Requer que cada transação bloqueie todos os seus itens de dados antes de iniciar a execução

Ou bloqueia todos os itens necessários ou não bloqueia nada

Estratégia mais simples (prevenção de deadlocks) Assegura a serializabilidade Está livre de deadlocks (deadlock-free) Não evita aborts em cascata



Prevenção de Deadlocks Protocolo Conservative 2PL ou Static 2PL

Desvantagens A utilização de um item de dado pode ser muito

baixa, uma vez que os itens bloqueados podem passar longos períodos sem serem utilizados

“Itens populares” uma transação pode esperar indefinidamente (enfraquecimento)



Prevenção de Deadlocks Apropriação + Reexecução de Transações

Baseado no conceito de timestamp Timestamp ordem total entre as transações Representação: TS(Ti) Se Ti começa a executar antes de Tj então

TS(Ti) < TS(Tj) Duas Técnicas Principais

Wait-Die Wound-Wait



Prevenção de Deadlocks Wait-Die (Espere-Morra)

Situação: Ti tenta bloquear um objeto já bloqueado por Tj

Funcionamento:

Se TS(Ti) < TS(Tj)

Então Ti espera

Caso contrário abortar Ti



Prevenção de Deadlocks Wait-Die (Espere-Morra)

Transações mais velhas podem esperar Transações mais jovens são abortadas e

reinicializadas com o mesmo timestamp



Prevenção de Deadlocks Wound-Wait (Machuque-Espere)

Situação: Ti tenta bloquear um objeto já bloqueado por Tj

Funcionamento:

Se TS(Ti) < TS(Tj)

Então abortar Tj

Caso contrário Ti espera



Prevenção de Deadlocks Wound-Wait (Machuque-Espere)

Transações mais velhas liquidam as mais jovens que são reinicializadas com o mesmo timestamp

Transações mais jovens podem esperar



Prevenção de Deadlocks A prevenção deve ser usada quando temos muito acesso

aos dados fazendo com que a probabilidade de ocorrência de deadlocks seja alta

Os dois esquemas evitam enfraquecimento



Detecção + Recuperação de Impasses Funcionamento

Um algoritmo que examina o estado do sistema é invocado periodicamente para determinar se um impasse ocorreu,

Em caso afirmativo, o sistema precisa recuperar-se do impasse

Necessita manter informações sobre a alocação dos itens de dados



Detecção de Impasses Grafo Wait-For

Os impasses podem ser descritos precisamente em termos de um grafo direcionado chamado grafo de espera.


Grafo Wait-For Seja S um schedule sobre um conjunto de transações

T = {T1, T2, ... , Tn}. O grafo de espera para S, representado por G(S), é

definido como:• O grafo direcionado G(S) = (N,A)• Cada nó em N representa uma transação em T• O conjunto A contém as arestas na forma Ti Tj , se e

somente se a transação Ti está esperando por Tj .



Transações Concorrentes Grafo Wait-For

Funcionamento:

Quando Ti requer um item de dado que está sendo mantido pela transação Tj. Então uma aresta na forma Ti Tj é inserida no grafo de espera.

Esta aresta é removida apenas quando a transação Tj não mantiver nenhum item de dado requisitado por T i.



Detecção de Impasses Teorema:

Um impasse existe no sistema se e somente se o grafo de espera (wait-for) apresenta um ciclo.

Algoritmo

Verificar a existência de ciclo no grafo.



Detecção de Impasses

Quando invocar o algoritmo de detecção ???

Com que freqüência ocorrem os conflitos ?

Quantas transações serão afetadas por um conflito ?



Recuperação de Impasse

Quando o algoritmo de detecção determina que existe um impasse (ciclo no grafo), o sistema precisa recuperar-se.

Solução :

Reiniciar uma das transações envolvidas no ciclo



Resolvendo Impasses (Deadlock)

Recuperação de Impasse

Selecionar uma vítima

Determinar a transação que resultaria em um custo mínimo.

Perigo de Enfraquecimento (livelock)

Incluir o número de repetições no fator custo



Strict 2PL Uma transação Ti não libera nenhum bloqueio até

executar seu commit ou abort Nenhuma transação pode ler ou escrever um item que foi

“escrito” por Ti até que Ti commit ou abort A liberação dos bloqueios é realizada globalmente no fim

da transação Assegura a serializabilidade por conflito Evita aborts em cascata Não esta livre de deadlock a não ser que seja combinado

com o protocolo conservative 2PL


Transações Concorrentes Protocolos Baseados em Marcadores de Tempo

Ordenação por Timestamp (TO) Utiliza marcadores de tempo a fim de ordenar a

execução das transações gerando um schedule equivalente a algum schedule serial

A ordem de execução das transações é determinada pela ordem em que as transações são iniciadas

Timestamp – TS(T) É um identificador único criado pelo SGBD para

identificar uma transação Em geral, os valores são gerados na ordem em que

as transações são submetidas ao sistema



Ordenação por Timestamp (TO) Geração dos Timestamps

Número seqüencial (1,2,3...) Data+Hora

O schedule gerado é equivalente a um determinado (particular) schedule serial Corresponde a ordem dos timestamps



Ordenação por Timestamp (TO) Funcionamento

O algoritmo associa a cada item X do BD dois timestamps: Read_TS(X): Maior entre todos os timestamps

de transações que leram o item X. Write_TS(X): Maior entre todos os timestamps

de transações que modificaram o item X Quando uma transação Ti deseja ler ou escrever

sobre o item X, o algoritmo compara o timestamp de Ti com o Read_TS(X) e Write_TS(X)



Ordenação por Timestamp (TO) Protocolo

1. T solicita uma operação write(x)

Se Read_TS(X) > TS(T) ou Write_TS(X) > TS(T)

Então abortar T

Se não executar write(x) e fazer TS(x) = TS(T)

2. T solicita uma operação read(x)

Se Write_TS(X) > TS(T)

Então abortar T

Se não executar read e fazer Read_TS(x) = Max(Read_TS(x), TS(T))



Ordenação por Timestamp (TO) Serializabilidade

Operações conflitantes sempre são executadas na ordem dos timestamps das transações

Não utiliza bloqueios Deadlocks não podem ocorrer (deadlock-free)

Não evita aborts em cascata


Transações Concorrentes Confiabilidade de Schedules Propriedades das Transações

Recuperação em Sistemas de Bancos de

Dados

José Maria MonteiroUniversidade Federal do CearáDepartamento de Computação

[email protected]


Visão Geral

Introdução Conceitos Básicos Atualização Adiada Atualização Imediata Páginas Sombra Conclusões


Introdução


Introdução

Um sistema de computador está sujeito a falhas

Uma falha pode ter diferentes causas Defeito no disco (HD) Queda de energia Erros de software Sabotagem

Em caso de falha As informações armazenadas no SGBD são

perdias Leva o SGBD a um estado inconsistente


Conceitos Básicos

© José Maria Monteiro.

Esquema de Recuperação

Módulo do SGBD responsável pela detecção de falhas e pela

restauração do banco de dados a um determinado estado consistente

anterior à ocorrência da falha.


Classificação das Falhas

Falha de mídia (caótica) Falha no disco Incêndio,...

Falha de execução (base inconsistente) Erros lógicos Erros do sistema Queda e energia


Algoritmos de Recuperação

Em geral, apresentam duas partes.

1. Ações tomadas durante o processamento normal das transações. Assegurar que informações suficientes existam

para permitir a recuperação do banco após a ocorrência de uma falha.

2. Ações tomadas após a ocorrência da falha. Assegurar a consistência do banco de dados.


Recuperando Falhas de Mídia

Copiar periodicamente o conteúdo inteiro do banco de dados para meio estável (backup)

Reconstruir uma cópia da base a partir de arquivo morto (quando ocorrer uma falha) A cópia mais recente deve ser utilizada na

restauração O banco de dados volta a um determinado

estado consistente anterior à ocorrência da falha


Recuperando Falhas de Execução

Estratégias baseadas em LOG Atualização Adiada Atualização Imediata

Páginas Sombra ou Paginação Imagem


Estratégias Baseadas em LOG


Transação

Lê e atualiza os itens de um banco de dados

Unidade de Consistência ou Atomicidade Exemplo:

Transferência de saldo entre duas contas Transação abortada Desfazer ações

(RollBack) O BD precisa der restaurado ao estado

que se encontrava logo antes da transação ter sido iniciada


Transação

Solução inicial Reexecutar a transação abortada Não reeexecutar a transação abortada

As duas opções levam a estados inconsistentes


O Jornal

Codnome: LOG Mantém registro das ações

transacionais Informações usadas para reconstrução

após falha Armazenado em disco Backup periódico


O Jornal

Toda vez que uma transação executa uma escrita É necessário que o registro Log esteja gravado

(persistente) antes que o banco seja modificado Problemas

O volume do Log Quando é seguro apagar informações no Log ??


Entradas do Jornal

[Ti , Start]

[Ti , Item , Valor_Antigo , Valor_Novo]

[Ti , Item , Valor_Lido]

[Ti , Commit]

[Ti , Abort] [Checkpoint]


Atualização Adiada



Durante a execução das transações Modificações sobre os itens de dados são

realizadas em espaço de trabalho particular Modificações são registradas no jornal Adia-se a execução das operações de

escrita de uma transação até que esta esteja parcialmente executada


Funcionamento

Antes que Ti inicie sua execução, um registro [Ti , Start] é escrito no log

A cada operação de escrita write(X, Xj) Ti um novo registro é gravado no log

Quando Ti é parcialmente executada, um registro [Ti, Commit] é escrito no log

Em seguida, os registros associados a Ti no log são usados para atualizar o BD e Ti entra no estado executado



Algoritmo no-undo/redo

1. Usar duas listas de transações- Transações Validadas ([Ti, Start] + [Ti , Commit])

- Transações Ativas Somente ([Ti, Start])

2. Aplicar redo às modificações das transações validadas seguindo a ordem de gravação no jornal

3. Re-iniciar as transações ativas



Redo

1. Examinar registros no jornal: [Ti , X, Valor_Antigo , Valor_Novo]

2. Atualizar X na base usando Valor_Novo

NB. A operação Redo deve ser idempotente.


Atualização Imediata


Atualização Imediata

Durante a execução das transações Modificações sobre os itens de dados são

realizadas diretamente sobre o banco de dados (Modificações descomprometidas)

Modificações são registradas no jornal Em caso de falha

O log é utilizado para restaurar os itens de dados modificados aos valores que tinham antes do início da transação


Funcionamento

Antes que Ti inicie sua execução, um registro [Ti , Start] é escrito no log

A cada operação de escrita write(X, Xj) Ti um novo registro é gravado no log

Quando Ti é parcialmente executada, um registro [Ti, Commit] é escrito no log



Algoritmo undo/redo

1. Usar duas listas de transações- Transações Validadas e Transações Ativas

2. Aplicar undo às transações ativas - Seguindo a ordem inversa de gravação no jornal

3. Aplicar redo às transações validadas- Seguindo a ordem de gravação no jornal


Undo

1. Examinar registros no jornal: [Ti , X, Valor_Antigo , Valor_Novo]

2. Atualizar X na base usando Valor_Antigo

NB. A operação Undo deve ser idempotente.



Checkpoint

Quando uma falha ocorre é necessário consultar o log para determinar as transações validadas e ativas

Em princípio, o log inteiro precisa ser percorrido Este processo consome tempo Grande parte das transações validadas já têm

suas atualizações escritas no banco de dados


Checkpoint

1. Suspende a execução de todas as transações

2. Força a gravação em disco dos efeitos das operações das transações validadas

3. Escreve uma entrada [Checkpoint] no jornal

4. Força a gravação do jornal em disco5. Re-ativa transações suspensas


Checkpoint

[Ti , Commit] antes de [Checkpoint] :

Não há necessidade de refazer Ti

Quando efetuar o Checkpoint ???TempoNúmero de transações validadas


Páginas Sombra


Páginas Sombra

O BD é dividido em determinado número de blocos com comprimento fixo, os quais são chamados de páginas

Para encontrar uma determinada página Utiliza uma tabela de páginas (Índice) com “n”

entradas, uma para cada página Cada entrada contém um ponteiro para uma

página no disco


Páginas Sombra

Idéia básica: Manter duas tabelas de páginas durante a vida

de uma transação• Tabela de Página Corrente• Tabela de Página Sombra ou Imagem

Quando a transação inicia as tabelas de página são idênticas


Páginas Sombra

A tabela de página sombra nunca é alterada durante a execução de uma transação

A tabela de página corrente é alterada quando uma transação executa uma operação de escrita

Leituras e escritas usam a tabela corrente A tabela de página sombra é armazenada em

meio estável para que o estado do banco possa ser recuperado em caso de falha


Páginas Sombra

Quando a transação validar• A tabela de página corrente será gravada no

disco • A tabela de página corrente torna-se a nova

torna-se a nova tabela de página imagem Em caso de falha

O estado do banco é recuperado utilizando-se a página imagem


Páginas Sombra

Considerações: Sob certas circunstâncias, pode requerer

menos acesso a disco do que os métodos baseados em log

Em caso de falha a recuperação é mais rápida Desvantagens

Fragmenteção de dados Mais difícil de implementar em ambientes de

transações concorrentes


Conclusões

O esquema de recuperação é um módulo essencial em Sistemas de Bancos de Dados

A escolha da estratégia de recuperação a ser utilizada é influenciada pelas características das aplicações

Documents

Sistemas de Gerenciamento de Bancos de Dados José Maria Monteiro Universidade Federal do Ceará Departamento de Computação [email protected]