Please enable JavaScript.
Coggle requires JavaScript to display documents.
Processamento de transações, controle de concorrência e recuperação…
Processamento de transações, controle de concorrência e recuperação
Introdução aos conceitos e teoria de processamento de transações
Introdução ao processamento de transações
Sistemas de monousuário versus multiusuário
Monousuário
Se no máximo um usuário de cada vez pode utilizar o sistema
Restritos a sistemas de computador pessoal
Multiusuário
Se muitos usuários podem acessar o banco de dados simultaneamente.
SGBDs que não são restritos a sistema de computador pessoal
multiprogramação
permite que o SO do computador execute vários processos ao mesmo tempo
Transações, itens de banco de dados, operações de leitura e gravação e buffers do SGBD
transação
programa em execução que forma uma unidade lógica de processamento de banco de dados
uma ou mais operações de acesso ao banco de dados
inserção, exclusão, modificação ou recuperação
um ínico programa pode conter mais de uma transação se tiver vários limites de transação
banco de dados
representado com uma coleção de itens de dados nomeados
granularidade
tamanho de um item de dados
item de dados
registro de banco de dados, ou bloco de disco inteiro
nome único para identificar exclusivamente cada item de dados
operações básicas de acesso ao banco de dados
read_item(X)
lê um item X do banco de dados
write_item(X)
Grava o valor da variável no item de bd X
buffer
em alguns casos, não é imediatamente armazenado no disco, caso mudanças adicionais tenham de ser feitas no buffer
costuma manter o conteúdo de um bloco de disco no banco de dados
se um buffer escolhido tiver de ser modificado, ele precisa ser gravado de volta no disco antes de ser reutilizado
Por que o controle de concorrência é necessário
O problema da atualização perdida
ocorre quando duas transações que acessam os mesmos itens do BD têm suas operações intercaladas de modo que isso torna o valor de alguns itens do BD incorreto.
O problema da atualização temporária
ocorre quando uma transação atualiza um item do banco de dados e depois a transação falha por algum motivo
O problema do resumo incorreto
se uma transação está calculando uma função de reumo de agregação em uma série de itens de banco de dados, enquanto outras estão atualizando alguns desses itens, pode ser calculado alguns valores antes que sejam atualizados.
O problema da leitura não repetitiva
quando uma transação lê o mesmo item duas vezes e o item é alterado por outra transação entre as duas leituras.
Por que a recuperação é necessária
Tipos de falhas
imposição de controle de concorrência
falha de disco
erros locais ou condição de exceção detectadas pela transação
problemas físicos e catástrofes
erro de transação ou do sistema
falha no computador
Conceitos de transações e sistema
Estados de transação e operações adicionais
transação
unidade atômica de trabalho que deve ser concluída totalmente ou não ser feita de forma alguma
operações para recuperação do SGBD
BEGIN_TRANSACTION
READ ou WRITE
END_TRANSACTION
COMMIT_TRANSACTION
ROLLBACK
O log do sistema
recuperar de falhas que afetam transações
registra todas as operações de transação que afetam os valores dos itens do BD, e outras informações que podem ser necessárias para permitir a recuperação de falhas
registros de log
[write_item, T, X, valor_antigo, valor_novo]
[read_item, T, X]
[start_transaction, T]
[commit, T]
[abort, T]
Ponto de confirmação de uma transação
todas as operações que acessam o BD tiverem sido executadas com sucesso
o efeito de todas as operações de transações do BD tiverem sido registradas no log
Propriedades desejáveis de transações
Propriedades ACID
Atomicidade
uma transação é uma unidade de processamento atômica; ela deve ser realizada em sua totalidade ou não ser realizada de forma alguma.
Preservação da consistência
Uma transação deve preservar a consistência, significado que, se for completamente executada do inicio ao fim, deve levar o banco de dados de um estado consistente para outro.
Isolamento
Uma transação deve parecer como se fosse executada isoladamente de outras transações, embora muitas delas estejam sendo executadas de maneira simultânea
Durabilidade ou permanência
As mudanças aplicadas ao BD pela transação confirmada precisam persistir no BD.
Caracterizando schedules com base na facilidade de recuperação
Schedules (históricos) de transações
é uma ordenação das operações das transações
é dificil encontrar schedules completos em um sistema de processamento de transação, pois novas transações estão sendo continuamente submetidas ao sistema.
Um schedule de n transições é considerado um schedule completo se:
As operações em S são exatamente aquelas operações nas transações, incluindo uma operação de confirmação ou cancelamento como ultima operação em cada transação do schedule
Para qualquer par de operações da mesma transação, sua ordem de aparecimento relativa em S é a mesma que sua ordem de aparecimento em T
Para duas operações quaisquer em conflito, uma das duas precisa ocorrer antes da outra no schedule
Caracterizando schedules com base na facilidade de recuperação
para alguns schedules, é fácil recuperar-se de falhas de transação e sistema, enquanto para outros o processo de recuperação pode ser bem complicado.
schedules recuperáveis e não recuperáveis
é importante caracterizar os tipos de schedules para os quais a recuperação é possível, bem como aqueles para os quais a recuperação é relativamente simples
Caracterizando schedules com base na facilidade de serialização
Schedules seriais, não seriais e serializáveis por conflito
schedules seriais
problema com schedules seriais é que limitam a concorrência ao proibir a intercalação de operações
as operações de cada transação são executadas consecutivamente, sem quaisquer operações intercaladas da outra transação
não importa qual transação é executada em primeiro lugar
são considerados inaceitáveis na prática
schedules não seriais
cada sequência intercala operações das duas transações
schedules serializáveis
um schedule S de n transações é serializável se for equivalente a algum schedule serial das mesmas n transações.
schedules equivalentes no resultado
se produzirem o mesmo resultado no banco de dados
dois schedules diferentes podem acidentalmente produzir o mesmo estado final
equivalência de conflito dos schedules
dois chedules são considerados equivalentes em conflito se a ordem de duas operações em conflito quaisquer for a mesma nos dois chedules
um schedule S é serializavel de conflito se ele for equivalente (em conflito) a algum schedule serial S'
Testando a serialização por conflito de um schedule
Para cada caso em S onde T executa um read_item(X) depois de T executar um write_item(X), crie uma aresta (T→T) no grafo de precedência
Para cada caso em S onde T executa um write_item(X) após T executar um read_item(X), crie uma aresta (T→T) no grafo de precedência
Para cada transação T participante no schedule S, crie um nó rotulado com T no grafo precedência
Para cada caso S onde T executa um write_item(X) após T executar um write_item(X), crie uma aresta (T→T) no grafo de precedência
O schedule S é serializável se, e somente se, o grafo de precedência não tiver cliclos
Como a serialização é usada para controle de concorrência
Um schedule serializável oferece os benefícios da execução concorrente sem abrir mão de qualquer exatidão
Quando as transações são submetidas continuamente ao sistema, é difícil determinar quando um schedule começa e quando ele termina
A teoria da serialização pode ser adaptada para lidar com esse problema, considerando apenas a projeção confirmada de um schedule S
Podemos definir um schedule S para serializável se sua projeção confirmada C(S) for equivalente a algum schedule serial, pois apenas transações confirmadas são garantidas pelo SGBD
Equivalência de visão e serialização de visão
Dois schedules S e S' são considerados equivalentes de visão se as condições a seguir forem mantidas
Para qualquer operação r(X) e T em S, se o valor de X lido pela operação tiver sido gravado por uma operação w(X) de T, a mesma condição deve ser mantida para o valor de X lido pela operação r(X) de T em S
Se a operação w(Y) de T for a ultima operação a gravar o item Y em S, então w(Y) de T também deve ser a ultima operação a gravar o item Y em S
O mesmo conjunto de transações participa em S e S', e S e S1 incluem as mesmas operações dessas transações
Um schedule S é considerado serializável de visão
Se for equivalente de visão a um schedule inicial
Suporte para transação em SQL
Transação SQL
Uma unidade lógica de trabalho e tem garantias de ser atômica.
O início da transação é feito implicitamente quando instruções SQL em particular são encontradas
Instrução de fim explícita
COMMIT
ROLLBACK
Características atribuídas a transação
SET TRANSATION
Modo de acesso
READ ONLY
READ WRITE
READ UNCOMITTED
Tamanho da área de diagnóstico
DIAGNOSTIC SIZE n
Nível de isolamento
ISOLATION LEVEL
Sistemas exigem alta disponibilidade e tempo de resposta rápido para centenas de usuários simultâneos
caixas de supermercados
reservas aéreas
sistemas bancários
processamento de cartão de crédito
compras online
mercados de ações
muitas outras aplicações
Técnicas de controle de concorrência
Técnicas de controle de concorrência multiversão
Técnica multiversão baseada na ordenação de rótulo de tempo
os rótulos de tempo são mentidos
read_TS(X)
write_TS(X)
para garantir a facilidade de recuperação, uma transação T não deve ter permissão para confirmar até que todas as transações que gravaram alguma versão que T leu tenha sido confirmadas
Bloqueio em duas fases multiversão usando bloqueios de certificação
três modos de bloqueio
gravação
certificação
não é compatível com os bloqueios de leitura
a transação pode ter que esperar sua confirmação até que todos os itens bloqueados para a gravação sejam liberados por quaisquer transações de leitura, a fim de obter os bloqueios de certificação.
leitura
custo
uma transação pode ter de esperar sua confirmação até que obtenha bloqueios de certificação exclusivos em todos os itens que atualizou
desvantagem
necessidade de mais armazenamento para manter várias versões dos itens do banco de dados
Técnicas de controle de concorrência de validação (otimista)
técnicas de validação ou certificação
nenhuma verificação é feita enquanto a transação está executando
três fases para esse protocolo de controle de concorrência
fase de validação
a verificação é realizada para garantir que a serialização não sera violada se as atualizações de transação forem aplicadas ao banco de dados
fase de gravação
se a fase de validação for bem sucedida, as atualizações da transação são aplicadas ao banco de dados; caso contrário, as atualizações são descartadas e a transação é reiniciada
fase de leitura
uma transação pode ler valores dos itens de dados confirmados com base no banco de dados
Controle de concorrência baseado na ordenação de rótulo de tempo (timestamp)
Rótulos de tempo (timestamp)
é um identificador exclusivo criado pelo SGBD para identificar uma transação
As técnicas de controle de concorrência baseadas na ordenação por rótulo de tempo não usam bloqueios
O algoritmo de ordenação de rótulo de tempo (timestamp)
Ordenar as transações com base em seus rótulos de tempo
precisa garantir que, para cada item acessado pelas operações em conflito no schedule, a ordem em que o item é acessado não viola a ordem do rótulo de tempo
read_TS(X)
O rótulo de tempo de leitura do item X é maior entre todos os rótulos de tempo das transações que leram com sucesso o item X
write_TS(X)
O rótulo de tempo de gravação do item X é maior de todos os rótulos de tempo das transações que gravaram com sucesso o item X
Granularidade dos itens de dados e bloqueio de granularidade múltiplo
Bloqueio com nível de granularidade múltiplo
bloqueios de intenção
são necessários para tornar o bloqueio com nível de granularidade múltiplo prático
uma transação indique, junto com o caminho da raiz até o nó desejado, que tipo de bloqueio ela exigirá de um dos descendentes do nó.
Tipos
Intention-exclusive (IX)
indica que um ou mais bloqueios exclusivos serão solicitados em algum ou alguns nós descendentes
Shared-intention-exclusive (SIX)
indica que o nó atual está bloqueado no modo compartilhado, mas que um ou mais blocos serão solicitados em algum ou alguns nós descendentes
Intention-shared(IS)
indica que um ou mais bloqueios compartilhados serão solicitados em algum ou alguns nós descentendes
Considerações de nível de granularidade para o bloqueio
granularidade do item de dados
granularidade fina
tamanho de item pequenos
granularidade grossa
tamanho de item grandes
quanto maior o tamanho do item de dados, menor o grau de concorrência permitido
quanto menor o tamanho do item de dados, maior é o número de itens no banco de dados
como cada item está associado a um bloqueio, o sistema terá um grande número de bloqueios ativos para serem tratados pelo gerenciador de bloqueio
qual o melhor tamanho de item?
depende dos tipos de transações envolvidas
Técnicas de bloqueio em duas fases para controle de concorrência
Garantindo a serialização pelo bloqueio em duas fases
Se todas as operações de bloqueio precedem a primeira operação de desbloqueio na transação
fase de expansão ou crescimento
novos bloqueios em itens podem ser adquiridos, mas nenhum pode ser liberado
fase de encolhimento
bloqueios existentes podem ser liberado, mas nenhum novo bloqueio pode ser adquirido
Lidando com deadlock e inanição
Deadlock
ocorre quando cada transação T em um conjunto de duas ou mais transações está esperando por algum item que está bloqueado por alguma outra transação no conjunto
Protocolos de prevenção de deadlock
é utilizado no bloqueio de duas fases conservador, requer que cada transação bloqueie todos os itens que precisar com antecedência.
Esquemas que impedem o deadlock
esperar-morrer
tem permissão para esperar, caso contrário aborta T e o reinicia mais tarde com o mesmo rótulo de tempo
ferir-esperar
aborta T e o reinicia mais tarde com mesmo rótulo de tempo, caso contrário, tem permissão de esperar
espera cuidadosa
se T não estiver bloqueada, então T está bloqueada e tem permissão para esperar, caso contrário, aborte T
Detecção de deadlock
o sistema verifica se um estado de deadlock realmente existe
o sistema construa e mantenha um grafo de espera
seleção da vítima
escolher quais transações abortar
selecionar transações que não fiseram muitas mudanças (mais novas)
Timeouts
se uma transação esperar por um periodo maior que o período de timeout definido pelo sistema, o sistema pressupõe que a transação pode entrar em deadlock e a aborta
Inanição
acontece quando uma transação não pode prosseguir por um período indefinido enquanto outras transações no sistema continuam nomalmente
solução: ter um esquema de espera justo
fila (primeiro a chegar primeiro a ser atendido)
Tipos de bloqueios e tabelas de bloqueio do sistema
Bloqueios binários
simples
muito restritivos para fins de controle de concorrência
não são usados na prática
Pode ter dois estados ou valores
bloqueado (1)
desbloqueado (0)
Operações
lock_item(x)
unlock_item(x)
Bloqueios compartilhados / exclusivos(ou de leitura / gravação)
Devemos permitir que várias transações acessem o mesmo item X se todas elas acessarem X apenas para fins de leitura
Operações
write_lock(x)
unlock(x)
read_lock(x)
Três estados possíveis
bloqueado para gravação / exclusivo
desbloqueado
bloqueado para leitura / compartilhamento
Conversão de bloqueios
transação que já mantém um bloqueio no item X tem permissão, sob certas condições de converter o bloqueio de um estado bloqueado para outro
é possível que uma transação T emita um read_lock(x) e, depois faça um upgrade do bloqueio, emitindo uma operação write_lock(x)
Usando bloqueios para controle de concorrência em índices
bloqueios em página de índice até a fase de encolhimento do 2PL pode causar quantidade indevida de bloqueio, pois pesquisar um índice sempre inicia na raiz
A estrutura de árvore do índice pode ser aproveitada quando se desenvolve um esquema de controle de concorrência
B-tree
nós irmãos no mesmo nível são ligados em cada nível
se uma transação quiser inserir um registo, a raiz seria bloqueada de modo exclusivo
todas as outras solicitações de bloqueio em conflito para o índice devem esperar que a transaçao entre na fase de encolhimento
Outras questões de controle de concorrência
Inserção, exclusão e registros fantasma
Quando um novo item de dados é inserido no BD
ele não pode ser acessado antes que o item seja criado e a operação de inserção seja concluida
Operação de exclusão
um bloqueio exclusivo deve ser obtido antes que a transação possa excluir o item
O problema do fantasma
pode ocorrer quando um novo registro que está sendo inserido por alguma transação T satisfaz uma condição que um conjunto de registros acessados por outra transação T1 precisa fazer
Transações interativas
transações interativas leem entrada e gravam saída em um dispositivo interativo, como uma tela de monitor, antes que sejam confirmadas
para lidar com esse problema pode ser adiada a saída de transações para a tela até que elas sejam confirmadas
Latches
são bloqueios mantidos por curta duração
não seguem o protocolo de controle de concorrência normal, como o bloqueio em duas fases
Técnicas de recuperação de banco de dados
Técnicas de recuperação baseadas em atualização imediata
quando uma transação emite um comando e atualização, o banco de dados no disco pode ser atualizado imediatamente, sem qualquer necessidade de esperar que a transação atinja seu ponto de confirmação
devem-se tomar providências para desfazer o efeito das operações de atualização que foram aplicadas ao banco de dados por uma transação com falha
entradas de log tipo UNDO
incluem o valor antigo (BFIM) do item
devem ser armazenadas no log
pode ser necessário durante a recuperação
seguem uma estratégia steal
para decidir quando os buffers da memória principal atualizados podem ser gravados de volta no disco
Paginação de sombra
quando a transação começa a ser executada, o diretório atual é copiado para um diretório de sombra
durante a execução da transação, o diretório sombra nunca é modificado
considera o banco de dados composto de uma série de páginas de disco para fins de recuperação
o estado do BD antes da execução da transação está disponível por meio do diretório de sombra, e esse estado é recuperado ao restaurar o diretório de sombra
Conceitos de recuperação
Esboço da recuperação e categorização dos algoritmos de recuperação
A recuperação de falhas de transação em geral significa que o BD é restaurado ao estado consistente mais recente antes do momento da falha
manter informações sobre as mudanças que foram aplicadas aos itens de dados pelas diversas trasações
atualização imediata
o BD pode ser atualizado por algumas operações de uma transações antes que a transação alcance seu ponto de confirmação
atualização adiada
não atualizam fisicamente o banco de dados no disco até que uma transação atinge seu ponto de confirmação
Caching (buffering) de blocos de disco
é uma função do sistema operacional, mas devido a sua importância para a eficiência dos procedimentos de recuperação, ele é tratado pelo SGBD chamando rotinas de baixo nível do sistema operacional
Um diretório para o cache é usado para acompanhar quais itens de banco de dados estão no buffer
quando o SGBD solicita ação em algum item, o primeiro ele verifica o diretório do cache para determinar se a página de disco que contrém o item está no cache do SGBD
pode ser necessário substituir algum dos buffers de cache para criar espaço disponível para o novo item
Logging write-ahead, stel/no-steal e force/no-force
Quando a atualização no local é utilizada, é necessário usar um log para recuperação
logging write-ahead
o mecanismo de recuperação precisa garantir que BFIM do item de dados esteja registrada na entrada de log apropriada e que a entrada de log seja esvaziada para o disco antes de BFIM ser modificada pela AFIM no banco de dados.
é necessário poder desfazer a operação se isso for exigido durante a recuperação
Terminologia de recuperação de SGBD padrão
especificam as regras que controlam quando uma página do banco de dados pode ser gravada do cache para o disco
steal/no-steal
steal
se o protocolo de recuperação permitir gravar um buffer atualizado antes que a transação confirme
no-steal
se uma página do buffer em cache atualizada por uma transação não puder ser gravada em disco antes que a transação confirme
force/no-force
force
se todas as páginas atualizadas por uma transação forem imediatamente gravadas em disco antes que a transação confirme
no-force
caso contrário
Check pont no log do sistema e check point fuzzy
check point
outro tipo de entrada no log
O gerenciador de recuperação de um SGBD precisa decidir em que intervalos realiza um check point
realiza um chack point: consiste nas seguintes ações
gravar um registro no log e forçar agravação do log em disco
retomar a execução das transações
forçar a gravação em disco de todos os buffers da memória principal que foram modificados
suspender a execução de transações temporariamente
check point fuzzy
o sistema pode retomar o processamento da transação após um registro ser gravado no log sem esperar que a etapa 2 termine
Rollback de transação e rollback em cascata
Pode ser preciso reverter (dar rollback) em uma transação caso ela falhe por um motivo qualquer depois de atualizar o BD
se quaisquer valores tiverem sido alterados pela transação, eles precisam ser restaurados
rollback em cascata
quando uma transação for revertida, qualquer outra transação que tenha lido o valor de algum item de dados gravado na transação também precisa ser revertida, e assim por diante
pode ser muito complexo e demorado
na prática, o rollback em cascata das transações nunca é exigido porque os métodos de recuperação práticos garantem schedules sem cascata ou estritos
Ações da transação que não afetam o banco de dados
uma transação terá ações que não afetam o banco de dados
geração de impressão de imagens
relatório das informações recuperadas do banco de dados
se a transação falhar antes de concluir
podemos não querer que o usuário receba esses relatórios, pois a transação deixou de completar
parte do processo de recuperação teria de informar ao usuário que esses relatórios estão errados
relatórios devem ser gerados apenas depois que a transação atinge seu ponto de confirmação
O algoritmo de recuperação ARIES
um exemplo de algoritmo de recuperação usado em sistemas de banco de dados
é utilizado em muitos produtos relacionados a banco de dados relacional da IBM
possui uma técnica steal/no-force para gravação
é baseado em três conceitos
logging write-ahead
histórico repetitivo durante o redo
significa que o ARIES retraçará todas as ações do sistema de banco de dados antes da falha para reconstruir o estado do BD quando a falha ocorre
mudanças no loging durante o undo
imperidá que o ARIES repita as operações de undo completadas se houver uma falha durante a recuperação, causando um reiniício do processo de recuperação
check point
gravar um registro begin_checkpoint no log
gravar um registro end_checkpoint no log
gravar o LSN no registro begin_checkpoint em um arquivo especial
check point fuzzy
é usado de modo que o SGBD possa continuar a executar as transações durante o check point, para reduzir o custo
Recuperação em sistemas de múltiplos bancos de dados
para manter a atomicidade de uma transação multibanco de dados
é preciso ter um mecanismo de recuperação de dois níveis
gerenciamento de recuperação global
coordenador
costuma seguir um protocolo chamado protocolo de confirmação em duas fases
uma transação multibanco de dados, pode exigir acesso a vários bancos de dados
esses bancos de dados podem ainda ser armazenados em diferentes tipos de SGBD
cada SGBD envolvido na transação multibanco de dados pode ter a própria técnica de recuperação e gerenciador de transação separados daqueles outros SGBD
Backup e recuperação em banco de dados contra falhas catastróficas
as técnicas de recuperação usam as entradas no log do sistema ou no diretório de sombra para se recuperarem da falha ao retornar o banco de dados a um estado consistente
as técnicas se aplicam a falhas não catastróficas
um gerenciador de recuperação de um SGBD também precisa ser equipado para lidar com esse tipo de falha
backup do banco de dados
o banco de dados inteiro e o log são periodicamente copiados para um meio de armazenamento barato
em caso de uma falha catastrófica, a cópia de backup mais recente pode ser recarregada para o disco, e o sistema reiniciado
dados de aplicações críticas são copiados de tempos em tempos em sua totalidade e movidos para locais seguros e fisicamente separados
Recuperação NO-UNDO/REDO baseada em atualização adiada
adiar ou postergar quaisquer atualizações reais para o BD em disco até que a transação termine sua execução com sucesso e atinja seu ponto de confirmação
protocolo de atualização adiada tipico
Uma transação não pode mudar o banco de dados no disco até que atinja seu ponto de confirmação
Uma transação não atinge seu ponto de confirmação até que todas as entradas de log tipo REDO sejam registradas no log e o buffer de log seja gravado a força no disco
se uma transação for abortada por algum motivo ela é simplesmente submetida novamente, pois não alterou o banco de dados no disco
todos os itens bloqueados para a gravação permanecem bloqueados até que a transação atinja seu ponto de confirmação
pode ser exigido um espaço de buffer excessivo para manter todos os itens atualizados até que as transações sejam confirmadas