Transações
Uma transação é uma sequência de operações em dados que tem um começo e um fim.
Uma transação é a execução sequencial de operações de leitura e gravação. O final de uma transação pode ser salvar as alterações (commit) ou cancelar as alterações (rollback). Em relação a um banco de dados, uma transação consiste em diversas solicitações que são tratadas como uma única solicitação.
As transações devem satisfazer as propriedades ACID
Atomicidade. A transação foi concluída completamente ou não foi concluída.
Consistência. Ao concluir uma transação, as restrições impostas aos dados (por exemplo, restrições no banco de dados) não devem ser violadas. A consistência implica que o sistema será transferido de um estado correto para outro estado correto.
Isolamento. As transações executadas em paralelo não devem influenciar umas às outras, por exemplo, alterar dados usados por outra transação. O resultado da execução de transações paralelas deve ser o mesmo que se as transações fossem executadas sequencialmente.
Sustentabilidade. Uma vez confirmadas, as alterações não devem ser perdidas.
Log de transações
O log armazena as alterações feitas pelas transações, garante a atomicidade e a estabilidade dos dados em caso de falha do sistema
O log contém os valores que os dados tinham antes e depois de serem alterados pela transação. A estratégia de log write-ahead requer a adição de uma entrada de log sobre os valores anteriores antes do início e sobre os valores finais após a conclusão da transação. Em caso de parada repentina do sistema, o banco de dados lê o log na ordem inversa e cancela as alterações feitas pelas transações. Tendo encontrado uma transação interrompida, o banco de dados a executa e faz alterações no log. Estando no estado no momento da falha, o banco de dados lê o log em ordem direta e retorna as alterações feitas pelas transações. Dessa forma, a estabilidade das transações já cometidas e a atomicidade da transação interrompida são preservadas.
A simples reexecução de transações com falha não é suficiente para a recuperação.
Exemplo. O usuário tem $ 500 em sua conta e decide sacar em um caixa eletrônico. Duas transações estão em andamento. O primeiro lê o valor do saldo e se houver saldo suficiente no saldo, emite dinheiro para o usuário. O segundo subtrai o valor necessário do saldo. Digamos que o sistema travou e a primeira operação falhou, mas a segunda falhou. Neste caso, não podemos reemitir dinheiro ao usuário sem retornar o sistema ao seu estado original com saldo positivo.
Níveis de isolamento
Leitura confirmada
O problema do Dirty Read é que uma transação pode ler o resultado intermediário de outra transação.
Exemplo. O valor do saldo inicial é $ 0. T1 adiciona $ 50 ao seu saldo. T2 lê o valor do saldo ($50). T1 descarta as alterações e sai. T2 continua a execução com dados de saldo incorretos.
A solução é ler dados fixos (Read Committed), o que proíbe a leitura de dados alterados pela transação. Se a transação A alterou um determinado conjunto de dados, então a transação B, ao acessar esses dados, é forçada a aguardar a conclusão da transação A.
Leitura repetível
Problema de atualizações perdidas. T1 salva as alterações além das alterações de T2.
Exemplo. O valor do saldo inicial é $ 0 e duas transações reabastecem simultaneamente o saldo. T1 e T2 apresentam um saldo de $ 0. T2 então adiciona $200 a $0 e salva o resultado. T1 adiciona $100 a $0 e salva o resultado. O resultado final é $ 100 em vez de $ 300.
Problema de leitura irrepetível. Ler os mesmos dados repetidamente retorna valores diferentes.
Exemplo. T1 lê um valor de saldo de $ 0. T2 então adiciona $ 50 ao saldo e encerra. T1 lê novamente os dados e encontra uma discrepância com o resultado anterior.
A leitura repetível garante que uma segunda leitura retornará o mesmo resultado. Os dados lidos por uma transação não podem ser alterados em outras até que a transação seja concluída. Se a transação A leu um determinado conjunto de dados, então a transação B, ao acessar esses dados, é forçada a aguardar a conclusão da transação A.
Leitura ordenada (serializável)
Problema de leitura fantasma. Duas consultas que selecionam dados com base em uma determinada condição retornam valores diferentes.
Exemplo. T1 solicita o número de todos os usuários cujo saldo é maior que US$ 0, mas menor que US$ 100. T2 deduz US$ 1 de um usuário com saldo de US$ 101. T1 reemite o pedido.
Leitura ordenada (serializável). As transações são executadas completamente sequenciais. É proibido atualizar ou adicionar registros que se enquadrem nos termos da solicitação. Se a transação A solicitou dados de toda a tabela, toda a tabela será congelada para outras transações até que a transação A seja concluída.
Agendador
Define a ordem na qual as operações devem ser executadas durante transações paralelas.
Fornece um nível especificado de isolamento. Se o resultado das operações não depende de sua ordem, então tais operações são comutativas (Permutáveis). As operações de leitura e as operações em dados diferentes são comutativas. As operações de leitura-gravação e gravação-gravação não são comutativas. A tarefa do escalonador é intercalar as operações realizadas por transações paralelas para que o resultado da execução seja equivalente à execução sequencial de transações.
Mecanismos de controle de jobs paralelos (Controle de Simultaneidade)
O otimista baseia-se na detecção e resolução de conflitos, o pessimista baseia-se na prevenção do surgimento de conflitos.
Na abordagem otimista, vários usuários têm cópias dos dados à sua disposição. A primeira pessoa a concluir a edição salva as alterações, enquanto as demais devem mesclar as alterações. Um algoritmo otimista permite que ocorra conflito, mas o sistema deve se recuperar do conflito.
Com uma abordagem pessimista, o primeiro usuário a capturar os dados impede que outros os recebam. Se os conflitos forem raros, é aconselhável escolher a estratégia optimista, uma vez que proporciona um nível mais elevado de simultaneidade.
Bloqueio
Se uma transação tiver dados bloqueados, outras transações deverão esperar até que sejam desbloqueadas ao acessar os dados.
Um bloco pode ser sobreposto a um banco de dados, tabela, linha ou atributo. O bloqueio compartilhado pode ser imposto aos mesmos dados por diversas transações, permite a leitura de todas as transações (inclusive aquela que o impôs), proíbe modificação e captura exclusiva. O bloqueio exclusivo pode ser imposto por apenas uma transação, permite quaisquer ações da transação imposta, proíbe quaisquer ações de terceiros.
Um impasse é uma situação em que as transações terminam em um estado pendente que dura indefinidamente.
Exemplo. A primeira transação aguarda a liberação dos dados capturados pela segunda, enquanto a segunda aguarda a liberação dos dados capturados pela primeira.
Uma solução otimista para o problema do impasse permite que o impasse ocorra, mas depois recupera o sistema revertendo uma das transações envolvidas no impasse.
Os deadlocks são procurados em determinados intervalos. Um dos métodos de detecção é por tempo, ou seja, considerar que ocorreu um deadlock caso a transação demore muito para ser concluída. Quando um impasse é encontrado, uma das transações é revertida, permitindo que outras transações envolvidas no impasse sejam concluídas. A escolha da vítima pode basear-se no valor das transações ou na sua antiguidade (esquemas Wait-Die e Wound-wait).
Cada transação T um carimbo de data/hora é atribuído TS contendo a hora de início da transação.
Espere-morra.
Se TS(Ti) < TS(Tj)em seguida Ti espera, caso contrário Ti reverte e começa novamente com o mesmo carimbo de data/hora.
Se uma transação nova tiver adquirido um recurso e uma transação mais antiga solicitar o mesmo recurso, então a transação mais antiga poderá esperar. Se uma transação mais antiga adquiriu um recurso, a transação mais recente que solicitou esse recurso será revertida.
Ferida, espere.
Se TS(Ti) < TS(Tj)em seguida Tj reverte e começa novamente com o mesmo carimbo de data/hora, caso contrário Ti esperando.
Se uma transação mais recente adquiriu um recurso e uma transação mais antiga solicitar o mesmo recurso, a transação mais recente será revertida. Se uma transação mais antiga adquiriu um recurso, então a transação mais jovem que solicita esse recurso poderá esperar. A seleção de vítimas baseada em precedência evita conflitos, mas reverte transações que não estão em conflito. O problema é que as transações podem ser revertidas muitas vezes porque... uma transação mais antiga pode reter o recurso por muito tempo.
Uma solução pessimista para o problema do impasse não permite que uma transação comece a ser executada se houver risco de impasse.
Para detectar um impasse, é construído um gráfico (gráfico de espera, gráfico de espera), cujos vértices são transações, e as arestas são direcionadas das transações que aguardam a liberação dos dados para a transação que capturou esses dados. Considera-se que ocorreu um deadlock se o grafo tiver um loop. Construir um gráfico de espera, especialmente em bancos de dados distribuídos, é um procedimento caro.
Bloqueio em duas fases - evita conflitos capturando todos os recursos usados por uma transação no início da transação e liberando-os no final
Todas as operações de bloqueio devem preceder a primeira de desbloqueio. Possui duas fases - Fase de Crescimento, durante a qual as garras se acumulam, e Fase de Encolhimento, durante a qual as garras são liberadas. Caso seja impossível capturar um dos recursos, a transação é reiniciada. É possível que uma transação não consiga adquirir os recursos necessários, por exemplo, se várias transações competirem pelos mesmos recursos.
Uma confirmação em duas fases garante que a confirmação seja executada em todas as réplicas do banco de dados
Cada banco de dados insere informações sobre os dados que serão alterados no log e responde ao coordenador OK (Fase de Votação). Após todos terem respondido OK, o coordenador envia um sinal obrigando todos a se comprometerem. Após o commit, os servidores respondem OK; se pelo menos um não responder OK, o coordenador envia um sinal para cancelar as alterações para todos os servidores (Fase de Conclusão).
Método de carimbo de data/hora
Uma transação mais antiga é revertida ao tentar acessar dados envolvidos por uma transação mais recente
Cada transação recebe um carimbo de data/hora TS correspondente ao horário de início da execução. Se Ti sobre Tjem seguida TS(Ti) < TS(Tj).
Quando uma transação é revertida, é atribuído um novo carimbo de data/hora. Cada objeto de dados Q envolvido na transação é marcado com dois rótulos. W-TS(Q) — timestamp da transação mais recente que completou com sucesso um registro ao longo Q. R-TS(Q) — timestamp da transação mais recente que executou um registro de leitura em Q.
Quando a transação T solicitações para ler dados Q Existem duas opções.
Se TS(T) < W-TS(Q), ou seja, os dados foram atualizados por uma transação mais jovem, então a transação T reverte.
Se TS(T) >= W-TS(Q), então a leitura é realizada e R-TS(Q) está se tornando MÁX(R-TS(Q), TS(T)).
Quando a transação T solicita alterações de dados Q Existem duas opções.
Se TS(T) < R-TS(Q), ou seja, os dados já foram lidos por uma transação mais jovem e caso seja feita alguma alteração, surgirá um conflito. Transação T reverte.
Se TS(T) < W-TS(Q), ou seja, a transação tenta sobrescrever um valor mais recente, a transação T é revertida. Em outros casos, a mudança é realizada e W-TS(Q) torna-se igual TS(T).
Nenhuma construção dispendiosa de gráfico de espera é necessária. As transações mais antigas dependem das mais recentes, portanto não há ciclos no gráfico de espera. Não há impasses porque as transações não são esperadas, mas revertidas imediatamente. Reversões em cascata são possíveis. Se Ti rolou para longe e Tj Eu li os dados que alterei Tiem seguida Tj também deve reverter. Se ao mesmo tempo Tj já foi cometido, então haverá uma violação do princípio da estabilidade.
Uma das soluções para reversões em cascata. Uma transação conclui todas as operações de gravação no final, e outras transações devem aguardar a conclusão dessa operação. As transações esperam para serem confirmadas antes de serem lidas.
Regra de gravação de Thomas - uma variação do método de carimbo de data / hora em que os dados atualizados por uma transação mais recente são proibidos de serem substituídos por uma mais antiga
Transação T solicita alterações de dados Q. Se TS(T) < W-TS(Q), ou seja, a transação tenta sobrescrever um valor mais recente, a transação T não é revertida como no método timestamp.
Fonte: habr.com