Transações
Controle de Concorrência
Serializabilidade
Introdução a Transações
• SGBD  sistema de processamento de
operações de acesso ao BD.
• SGBDs são em geral multi-usuários
– processam simultaneamente operações disparadas
por vários usuários
• deseja-se alta disponibilidade e tempo de resposta
pequeno
– execução intercalada de conjuntos de operações
• exemplo: enquanto um processo i faz I/O, outro
processo j é selecionado para execução.
• Operações são chamadas transações
Transação
• Uma transação é uma unidade de execução de
programa que acessa e, possivelmente atualiza
vários itens de dados.
• Uma transação geralmente é resultado da
execução de um programa de usuário escrito em
uma linguagem de manipulação de dados de alto
nível ou em uma linguagem de programação (por
exemplo, SQL, Cobol, C ou Pascal), e é delimitada
por declarações (ou chamadas de funções) da
forma “Inicio da transação” e “Final da
Transação”.
Transação
 De forma abstrata e simplificada, uma transação
pode ser encarada como um conjunto de operações
de leitura(read) e escrita(write) de dados.
 Read(x) – transfere o item X do banco de dados
para um buffer local alocado a transação que
executou a operação de read.
Tx
 Write(x) – transfere o item de dados X do buffer
local da transação que executou a write de volta ao
banco de dados.
Exemplo
• Seja Ti uma transação que transfere 50 dólares da
conta A para conta B. Essa transação pode ser
definida como:
TI: read(A);
A:=A-50;
write(A);
read(B);
B:=B+50;
write(B)
passo a passo
Leitura da Conta A: 1.000
A:=1000-50;
A=950;
Leitura da Conta B: 2.000
B:=2.000+50;
B=2.050
Estados de uma Transação
 Uma transação é sempre monitorada pelo
SGBD quanto ao seu estado
 que operações já fez? concluiu suas operações?
deve abortar?
 Estados de uma transação
 Ativa; Em processo de efetivação; Efetivada; Em
processo de aborto; Concluída.
 Respeita um Grafo de Transição de Estados
Transição de Estados de uma Transação
reads e writes
Em Processo
de Efetivação
iniciar
transação
Ativa
finalizar
transação
transação deve
ser desfeita
encerramento
com sucesso
encerramento
sem sucesso
Efetivada
conclusão
da transação
com sucesso
Em Processo
de Aborto conclusão
da transação
sem sucesso
Concluída
Transição de Estados de uma Transação
reads e writes
Em Processo
de Efetivação
iniciar
transação
Ativa
finalizar
transação
encerramento
com sucesso
transação deve
• estado
inicial de toda
ser desfeita
transação selecionada Efetivada
transação deve para execução
ser desfeita
• enquanto ativa, uma
conclusão
transação executa uma ou
da transação
mais operações read e write
com sucesso
Em Processo
de Aborto conclusão
da transação
sem sucesso
Concluída
Transição de Estados de uma Transação
reads e writes
Em Processo
de Efetivação
iniciar
transação
Ativa
finalizar
transação
encerramento
sem sucesso
• entra nesse estado após
transação deve
executar sua última operação
ser desfeita
(solicitação de COMMIT)
• neste momento, o SGBD
precisa garantir que as suas
atualizações sejam efetivadas
Em Processo
com sucesso (não sofra falhas)
de Aborto
encerramento
com sucesso
Efetivada
conclusão
da transação
com sucesso
conclusão
da transação
sem sucesso
Concluída
Transição de Estados de uma Transação
reads e writes
Em Processo
de Efetivação
iniciar
transação
Ativa
finalizar
transação
encerramento
com sucesso
encerramento
sem sucesso
deve
• entra nesse estadotransação
após o
ser desfeita
SGBD confirmar que todas
as
modificações da transação estão
garantidas no BD (COMMIT OK)
– exemplos: gravação em Log,
Em Processo
descarga de todos os buffers
em disco
de Aborto
Efetivada
conclusão
da transação
com sucesso
conclusão
da transação
sem sucesso
Concluída
Transição de Estados de uma Transação
• entra nesse estado se não puder
prosseguir a sua execução
• pode
passar para esse estado enquanto
reads
e writes
ativa (I) ou em processo de efetivação (II)
Em Processo
iniciar
transação
– exemplo (I): violação de Informações
– exemplo (II): pane no S.O.
de Efetivação
 suas ações já realizadas devem ser desfeitas
finalizar
(ROLLBACK)
Ativa
encerramento
com sucesso
transação
transação
deve
ser desfeita
encerramento
sem sucesso
Efetivada
conclusão
da transação
com sucesso
Em Processo
de Aborto conclusão
da transação
sem sucesso
Concluída
Transição de Estados de uma Transação
• estado final de uma transação
reads
e writes
• indica
uma
transação que deixa o
sistema
Em
iniciar
transação
Processo
– as informações da transação
de Efetivação
mantidas em catálogo podem ser
excluídas
finalizar
 operações feitas, dados
transação
Ativa
manipulados, buffers utilizados,
...
encerramento
sem sucesso
– se a transação não concluiu com
sucesso, ela pode
ser reiniciada
transação
deve
automaticamente
ser desfeita
encerramento
com sucesso
Efetivada
conclusão
da transação
com sucesso
Em Processo
de Aborto conclusão
da transação
sem sucesso
Concluída
Propriedades de uma Transação
• Para assegurar integridade dos dados, exigimos que o
sistema de banco de dados mantenham as seguintes
propriedades das transações: ACID
• A tômicidade: para o mundo externo, a transação ocorre
de forma indivisível.
• C onsistência: a transação não viola invariantes de sistema.
• I solamento: transações concorrentes não interferem entre
si (serializable).
• D urabilidade: os efeitos de uma transação terminada com
commit são permanentes.
Commit - encerra a transação (solicita efetivação das suas ações)
Atomicidade
• Princípio do “Tudo ou Nada”
– ou todas as operações da transação são efetivadas
com sucesso no BD ou nenhuma delas se efetiva
• preservar a integridade do BD
• Responsabilidade do subsistema de
recuperação contra falhas do SGBD
– desfazer as ações de transações parcialmente
executadas
Situação Problema
• Suponhamos que, antes da execução da transação Ti os valores
das contas A e B sejam 1.000 e 2.000 reais, respectivamente.
Agora suponha que, durante a execução da transação Ti uma
falha (falta de energia, falha na máquina e erros de software) aconteceu
impedindo Ti de se completar com sucesso. Suponha que a falha
ocorrida tenha sido depois da operação write(A), mas antes da
operação write(B). Nesse caso os valores das contas A e B
refletidas no banco são A: 950 e B: 2000 reais. Como resultado
da falha sumiram 50 reais.
• Chamamos esse estado de inconsistente. Devemos assegurar que
essas inconsistências sejam imperceptíveis em um banco de
dados
• Se a propriedade de atomicidade for garantida, todas as ações da
transação serão refletidas no banco de dados ou nenhuma delas
o será.
Atomicidade
• Deve ser garantida, pois uma transação pode manter
o BD em um estado inconsistente durante a sua
execução.
Contas
número
saldo
100
1.000
A
200
2.000
B
...
execução
Ti (transferência bancária)
read(A)
A.saldo = A.saldo – 50,00
write(A)
read(B)
B.saldo = B.saldo + 50,00
write(B)
falha!
•A idéia básica por trás da garantia da ATOMICIDADE é a seguinte: O SGBD
matem um registro (em disco) dos antigos valores de quaisquer dados sobre os
quais a transação executa uma gravação e, se a transação não completar, os valores
antigos são restabelecidos para fazer com que pareça que nunca foi executada.
Assegurar a atomicidade é função do próprio sistema de BD.
Consistência
• Uma transação sempre conduz o BD de um
estado consistente para outro estado também
consistente
• Responsabilidade
do
programador
da
aplicação que codifica a transação.
Isolamento
• No contexto de um conjunto de transações
concorrentes, a execução de uma transação Ti deve
funcionar como se Ti executasse de forma isolada
– Ti não deve sofrer interferências de outras transações
executando concorrentemente
• A propriedade de isolamento de uma transação
garante que a execução simultânea de transação
resulte em uma situação no sistema equivalente ao
estado obtido caso as transações tivessem sido
executadas uma de cada vez em qualquer ordem.
Isolamento
T1
T2
read(A)
T1
A = A – 50
read(A)
write(A)
A = A – 50
T2
read(A)
read(A)
A=
A+A*0.1
A = A+A*0.1
write(A)
read(B)
T1 interfere
em T2
B=B-A
B=B-A
write(B)
write(B)
T2 interfere
em T1
write(A)
read(B)
write(A)
B = B + 50
read(B)
write(B)
B = B + 50
read(B)
escalonamento válido
write(B)
escalonamento inválido
Durabilidade ou Persistência
• Deve-se garantir que as modificações
realizadas por uma transação que concluiu
com sucesso persistam no BD
– nenhuma falha posterior ocorrida no BD deve
perder essas modificações
Gerência Básica de Transações
Ações da Aplicação ou Usuário
T1 inicia
T1 submete
operações DML
T1 termina
DML (Linguagem de Manipulação dos Dados)
Permite ao usuário acessar ou manipular os
dados, vendo-os da forma como são definidos
no nível de abstração mais alto do modelo de
dados utilizado.
ROLLBACK - solicita que as ações da
transação sejam desfeitas.
Ações do SGBD
inicia ações para
garantir Atomicidade de T1
executa operações DML,
garantindo Isolamento de T1, e
testa RIs imediatas, com
possível rollback e msg erro, para
garantir Consistência de T1
testa RIs postergadas, com
possível rollback e msg erro, para
garantir Consistência de T1
executa ações para
garantir Durabilidade de T1
confirma o término de T1 para
a aplicação/usuário
Controle de Concorrência - Transações
• SGBD
– sistema multiusuário em geral
• diversas transações executando simultaneamente
• Garantia de isolamento de Transações
– 1a solução: uma transação executa por vez
• Escalonamento serial de transações
• solução bastante ineficiente!
– várias transações podem esperar muito tempo para serem executadas
– CPU pode ficar muito tempo ociosa
» enquanto uma transação faz I/O, por exemplo, outras transações
poderiam ser executadas
• solução mais eficiente
– execução concorrente de transações de modo a preservar o isolamento
» escalonamento (schedule) não-serial e íntegro
Controle de Concorrência - Transações
• As técnicas de controle de concorrência
garantem que várias transações submetidas por
vários usuários não interfiram umas nas outras
de forma a produzir resultados inconsistentes.
• Um schedule (escala) representa uma
seqüência de operações realizadas por
transações concorrentes.
Controle de Concorrência - Transações
•
Os dois schedules(escalas) apresentados são seriais, ou seja, as transações são
executadas de forma seqüencial, uma seguida da outra.
•
Entretanto a execução de schedules seriais limita o acesso concorrente aos
dados e, por conseqüência, diminui o throughput (quantidade de trabalho
realizado em um intervalo de tempo).
T1
T2
T1
T2
read(A)
read(A)
A = A – 50
A = A – 50
write(A)
write(A)
read(B)
read(B)
B = B + 50
B = B + 50
write(B)
write(B)
read(A)
read(A)
temp:=A*0,1
temp:=A*0,1
A:=A – temp
A:=A – temp
write (A)
write (A)
read(B)
read(B)
B:=B+temp
B:=B+temp
write(B)
write(B)
Controle de Concorrência - Transações
• Nem
todas
as
execuções concorrentes
resultam em um estado
correto.
• Esse estado final é um
estado inconsistente,
pois a soma de A + B
não é preservada na
execução das duas
transações
T1
T2
read(A)
A = A – 50
read(A)
temp:=A*0,1;
A := A –temp
write(A)
read(B)
write(A)
read(B)
B = B + 50
write(B)
Escala Concorrente ou execução não-serial
Scheduler
• Responsável pela definição de escalonamentos nãoseriais de transações
• “Um escalonamento E define uma ordem de execução das
operações de várias transações, sendo que a ordem das
operações de uma transação T1 em E aparece na mesma
ordem na qual elas ocorrem isoladamente em T1”
• Problemas de um escalonamento não-serial mal
definido (inválido)
– atualização perdida (lost-update)
– leitura suja (dirty-read)
Atualização Perdida (lost-update)
• Uma transação T1 grava em um dado
atualizado por uma transação T2
T1
T2
read(A)
A = A – 50
read(C)
A = D + 10
write(A)
read(B)
write(A)
E = A + 30
write(B)
a atualização de A
por T1 foi perdida!
Leitura Suja (dirty-read)
• T1 atualiza um dado A, outras transações
posteriormente lêem A, e depois T1 falha
T1
T2
read(A)
A = A – 20
write(A)
read(A)
Neste ponto, a
transação T1 falha
e deve retornar o
valor de A para o
seu valor antigo;
A = A + 10
write(A)
read(Y)
abort( )
T2 leu um valor
de A que
não será mais
válido!
Scheduler
• O padrão Scheduler (selecionador) (Lea, 1997) tem
como objetivo controlar a ordem em que
requisições são escalonadas, encadeando a ordem
de execução das requisições em um processador. A
partir deste padrão, um processador, ao receber
uma requisição, não possui mais controle sobre o
momento de sua execução. Para isto, esta
requisição deve ser repassada a um escalonador
que, ao implementar alguma política de controle
de execução, determinará o momento apropriado
para a execução da requisição no processador.
Scheduler
• Deve evitar escalonamentos inválidos
– exige análise de operações em conflito
• operações que pertencem a transações diferentes
• transações acessam o mesmo dado
• pelo menos uma das operações é write
Scheduler X Recovery
• Scheduler deve cooperar com o Recovery!
• Categorias de escalonamentos considerando o
grau de cooperação com o Recovery
– recuperáveis X não-recuperáveis
– permitem aborto em cascata X evitam aborto em
cascata
– estritos X não-estritos
Transações em SQL
• Uma linguagem de Manipulação de dados deve possui um
construtor para especificar o conjunto de ações que constitui
uma transação.
• Por default, todo comando individual é considerado uma
transação
– exemplo: DELETE FROM Pacientes
• exclui todas ou não exclui nenhuma tupla de pacientes, deve manter o BD
consistente, etc
• SQL Padrão (SQL-92)
– SET TRANSACTION
• inicia e configura características de uma transação
– COMMIT [WORK]
• encerra a transação (solicita efetivação das suas ações)
– ROLLBACK [WORK]
• solicita que as ações da transação sejam desfeitas
Transações em SQL
• Principais configurações (SET TRANSACTION)
– modo de acesso
• READ (somente leitura), WRITE (somente atualização)
ou READ WRITE (ambos - default)
– nível de isolamento
• indicado pela cláusula ISOLATION LEVEL nível
• nível para uma transação Ti pode assumir
– SERIALIZABLE (Ti executa com completo isolamento - default)
– REPEATABLE READ (Ti só lê dados efetivados e outras
transações não podem escrever em dados lidos por Ti) – pode ocorrer
que Ti só consiga ler alguns dados que deseja
– READ COMMITTED (Ti só lê dados efetivados, mas outras
transações podem escrever em dados lidos por Ti)
– READ UNCOMMITTED (Ti pode ler dados que ainda não
sofreram efetivação)
Escalonamento Recuperável
• Garante que, se TA realizou commit (encerra a transação (solicita
efetivação das suas ações)), TA não irá sofrer UNDO (desfazer uma
atualização no BD)
– o recovery espera sempre esse tipo de escalonamento!
• Um escalonamento E é recuperável se nenhuma TA em E for
concluída até que todas as transações que gravaram dados
lidos por TA tenham sido concluídas
T1
T1
T2
read(A)
read(A)
A = A – 20
A = A – 20
write(A)
write(A)
escalonamento
não-recuperável
read(A)
A = A + 10
escalonamento
recuperável
read(A)
A = A + 10
write(A)
write(A)
commit( )
abort( )
T2
commit( )
commit( )
Escalonamento sem Aborto em Cascata
• Um escalonamento recuperável pode gerar abortos de transações em
cascata
– consome muito tempo de recovery!
• Um escalonamento E é recuperável e evita aborto em cascata se uma TA
em E só puder ler dados que tenham sido atualizados por transações
que já concluíram
T1
escalonamento
recuperável
com aborto em
cascata
T2
T1
read(A)
read(X)
A = A – 20
A = A – 20
write(A)
write(A)
read(A)
A = A + 10
write(A)
abort( )
...
escalonamento
commit( )
recuperável
sem aborto em
cascata
T2
read(A)
A = A + 10
write(A)
...
Escalonamento Estrito
• Garante que, se TA deve sofrer UNDO, basta gravar a before
image dos dados atualizados por ela
• Um escalonamento E é recuperável, evita aborto em cascata
e é estrito se uma TA em E só puder ler ou atualizar um dado
A depois que todas as transações que atualizaram A tenham
sido concluídas
T1
T2
read(A)
read(A)
write(A)
escalonamento write(A)
read(B)
A = B + 10
write(A)
commit( )
abort( )
T2
A = A – 20
A = A – 20
recuperável
sem aborto em
cascata e
não-estrito
T1
escalonamento
commit( )
recuperável
sem aborto em
cascata e
estrito
read(B)
A = B + 10
write(A)
commit( )
Teoria da Serializabilidade
 Um schedule serializável nos traz os benefícios da execução
concorrente de transações sem deixar que algum erro possa
ser gerado.
 Na prática, não se testa a serializabilidade de um schedule.
 Na maioria dos sistemas, o que se faz é determinar
métodos que garantam a serializabilidade sem ter que testar
a serializabilidade dos schedules depois de eles terem sido
executados.
 Ao projetar esquemas de controle de concorrência,
devemos mostrar que as escalas geradas por eles são
serializáveis.
Teoria da Serializabilidade
• Garantia de escalonamentos não-seriais válidos
• Premissa
– “um escalonamento não-serial de um conjunto de transações deve
produzir resultado equivalente a alguma execução serial destas
transações”
entrada:
X = 50
Y = 40
T1
T2
read(X)
X = X – 20
entrada:
X = 50
Y = 40
read(X)
X = X – 20
execução
não-serial
serializável
read(Y)
Y = Y + 20
write(Y)
saída:
X = 40
Y = 60
T2
write(X)
write(X)
execução
serial
T1
read(X)
X = X + 10
write(X)
saída:
X = 40
Y = 60
read(X)
X = X + 10
write(X)
read(Y)
Y = Y + 20
write(Y)
Verificação de Serializabilidade
• Para que dois schedules sejam equivalentes, as operações
aplicadas aos dados envolvidos nos dois schedules devem ser
executadas na mesma ordem nos dois schedules.
• Duas principais técnicas
– equivalência de conflito
– equivalência de visão
• Equivalência de Conflito
– “dado um escalonamento não-serial E’ para um conjunto de
Transações T, E’ é serializável em conflito se E’ for equivalente em
conflito a algum escalonamento serial E para T, ou seja, a ordem
de quaisquer 2 operações em conflito é a mesma em E’ e E.”
Equivalência de Conflito - Exemplo
escalonamento serial E
T1
T2
escalonamento não-serial E1
T1
T2
escalonamento não-serial E2
T1
read(X)
read(X)
read(X)
X = X – 20
X = X – 20
X = X – 20
write(X)
write(X)
T2
read(X)
read(Y)
read(X)
X = X + 10
Y = Y + 20
X = X + 10
write(X)
write(Y)
write(X)
read(Y)
read(X)
read(Y)
write(X)
X = X + 10
Y = Y + 20
Y = Y + 20
write(X)
write(Y)
write(Y)
• E1 equivale em conflito a E (o resultado final das operações será o mesmo).
• E2 não equivale em conflito a nenhum escalonamento serial para T1 e T2
• E1 é serializável e E2 não é serializável
Verificação de Equivalência em Conflito
• Construção de um grafo direcionado de
precedência
– nodos são IDs de transações
– arestas rotuladas são definidas entre 2 transações
T1 e T2 se existirem operações em conflito entre
elas
• direção indica a ordem de precedência da operação
– origem indica onde ocorre primeiro a operação
• Um grafo com ciclos indica um
escalonamento não-serializável em conflito!
Grafo de Precedência
escalonamento serializável E1
T1
T2
escalonamento não-serializável E2
T1
read(X)
read(X)
X = X – 20
X = X – 20
write(X)
read(X)
read(X)
X = X + 10
X = X + 10
write(X)
write(X)
read(Y)
read(Y)
write(X)
Y = Y + 20
Y = Y + 20
write(Y)
write(Y)
T1
T2
T2
T1
T2
Equivalência de Visão
• “dado um escalonamento não-serial E’ para um conjunto de
Transações T, E’ é serializável em visão se E’ for equivalente
em visão a algum escalonamento serial E para T, ou seja:
– para toda operação read(X) de uma Tx em E’, se X é
lido após um write(X) de uma Ty em E’ (ou
originalmente lido do BD), então essa mesma seqüência
deve ocorrer em E;
– se uma operação write(X) de uma Tk for a última
operação a atualizar X em E’, então Tk também deve ser
a última transação a atualizar X em E.”
Serializabilidade de Visão
• Idéia básica
– enquanto cada read(X) de uma Tx ler o resultado de uma
mesmo write(X) em E’ e E, em ambos os escalonamentos, Tx
tem a mesma visão do resultado
– se o último write(X) é feito pela mesma transação em E’ e E,
então o estado final do BD será o mesmo em ambos os
escalonamentos
• Exemplo
Hserial = r1(X) w1(X) c1 w2(X) c2 w3(X) c3
Hexemplo = r1(X) w2(X) w1(X) w3(X) c1 c2 c3
Hexemplo não é serializável em conflito, mas é serializável em visão.
Serializabilidade em Conflito de Visão
• A serializabilidade de visão é menos restritiva que a
serializabilidade em conflito.
– um escalonamento E’ serializável em conflito
também é serializável em visão, porém o contrário
nem sempre é verdadeiro.
• A serializabilidade de visão é muito mais complexa
de verificar que a serializabilidade em conflito.
Verificação de Serializabilidade
• Técnicas propostas (em conflito e de visão) são difíceis de
serem testadas
– exige que se tenha um conjunto fechado de transações para
fins de verificação.
• Na prática
– conjunto de transações executando concorrentemente é
muito dinâmico!
• novas transações estão sendo constantemente
submetidas ao SGBD para execução
– logo, a serializabilidade é garantida através de técnicas (ou
protocolos) de controle de concorrência que não precisam
testar os escalonamentos