Transações
Uma transação é uma sequência de operações sobre dados que tem um início e um fim.
Uma transação é a execução sequencial de operações de leitura e gravação. O final da transação pode ser a confirmação das alterações (commit) ou a reversão das alterações (rollback). Em relação a bancos de dados, uma transação é um conjunto de solicitações tratadas como uma única solicitação.
As transações devem satisfazer às propriedades ACID.
Atomicidade. Uma transação é executada completamente ou não é executada de forma alguma.
Consistência. Ao finalizar a transação, as restrições impostas aos dados não devem ser violadas (como as constraints em um banco de dados). A consistência implica que o sistema deve ser transferido de um estado válido para outro estado válido.
Isolamento. Transações executadas em paralelo não devem interferir umas nas outras, por exemplo, alterando 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.
Durabilidade. Após a confirmação, as alterações não devem ser perdidas.
Registro de transações
O registro armazena as alterações realizadas pelas transações, garantindo a atomicidade e a durabilidade 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 Write-ahead log exige que uma entrada sobre os valores anteriores seja adicionada ao log antes do início, e os finais após a conclusão da transação. Caso o sistema seja interrompido repentinamente, o banco de dados lê o log em ordem inversa e reverte as alterações feitas pelas transações. Ao encontrar uma transação interrompida, o banco de dados executa-a e registra as mudanças no log. Quando em um estado no momento da falha, o banco de dados lê o log em ordem direta e reverte as alterações realizadas pelas transações. Isso preserva a durabilidade das transações já confirmadas e a atomicidade da transação interrompida.
Simplesmente repetir transações com erro não é suficiente para a recuperação.
Exemplo. O usuário tem 500$ na conta e decide retirar esse valor através de um caixa eletrônico. Duas transações são realizadas. A primeira lê o valor do saldo e, se houver fundos suficientes, libera o dinheiro para o usuário. A segunda subtrai a quantia do saldo. Suponha que ocorreu uma falha no sistema e a primeira operação não foi concluída, enquanto a segunda foi. Nesse caso, não podemos liberar novamente o dinheiro para o usuário sem restaurar o sistema ao seu estado original com saldo positivo.
Níveis de isolamento
Leitura de dados fixos (Read Committed)
O problema da leitura suja (Dirty Read) é que uma transação pode ler um resultado intermediário de outra transação.
Exemplo. O saldo inicial é 0$. T1 adiciona 50$ ao saldo. T2 lê o saldo (50$). T1 reverte as alterações e finaliza. T2 continua a execução possuindo dados incorretos sobre o saldo.
A solução é a leitura de dados fixos (Read Committed), que proíbe a leitura de dados que foram alterados por outra transação. Se a transação A alterou um determinado conjunto de dados, a transação B deve esperar a conclusão da transação A para acessar esses dados.
Leitura repetível (Repeatable Read)
O problema das atualizações perdidas (Lost Updates). T1 salva alterações sobre as alterações de T2.
Exemplo. O saldo inicial é 0$ e duas transações aumentam o saldo simultaneamente. T1 e T2 lêem um saldo de 0$. Em seguida, T2 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$.
O problema da leitura não repetível (Unrepeatable read). Uma leitura repetida dos mesmos dados retorna valores diferentes.
Exemplo. T1 lê um saldo de 0$. Depois, T2 adiciona 50$ ao saldo e finaliza. T1 lê os dados novamente e encontra uma discrepância com o resultado anterior.
Leitura repetível (Repeatable Read) garante que uma leitura repetida retornará o mesmo resultado. Os dados lidos por uma transação não podem ser alterados por outras até que a transação seja concluída. Se a transação A leu um determinado conjunto de dados, a transação B deve esperar a conclusão da transação A para acessar esses dados.
Leitura ordenada (Serializable)
Problema de leitura fantasma (Phantom Reads). Duas consultas que selecionam dados com base em uma determinada condição retornam valores diferentes.
Exemplo. T1 consulta a quantidade de todos os usuários cujo saldo é superior a 0$ mas inferior a 100$. T2 deduz 1$ do usuário com saldo de 101$. T1 executa a consulta novamente.
Leitura ordenada (Serializable). Transações são executadas como totalmente sequenciais. É proibido atualizar e adicionar registros que se enquadram nas condições da consulta. Se a transação A solicitou os dados de toda a tabela, a tabela inteira é congelada para as demais transações até a conclusão da transação A.
Agendador (Scheduler)
Determina a ordem em que as operações devem ser executadas durante transações que ocorrem em paralelo.
Garante um nível de isolamento especificado. Se o resultado da execução das operações não depende da sua ordem, então essas operações são comutativas (Permutable). Operações de leitura e operações sobre dados diferentes são comutativas. Operações de leitura-escrita e escrita-escrita não são comutativas. A tarefa do agendador é alternar as operações realizadas por transações paralelas de modo que o resultado seja equivalente à execução sequencial das transações.
Mecanismos de controle de tarefas paralelas (Concurrency Control)
Otimista baseado na detecção e resolução de conflitos, pessimista na prevenção de conflitos.
No enfoque otimista, vários usuários recebem cópias dos dados. O primeiro a terminar a edição salva as alterações, enquanto os demais devem realizar a fusão das alterações. O algoritmo otimista permite que um conflito ocorra, mas o sistema deve se recuperar após o conflito.
No enfoque pessimista, o primeiro usuário a capturar os dados impede que os outros acessem os dados. Se os conflitos são raros, é razoável escolher uma estratégia otimista, pois ela proporciona um nível mais alto de paralelismo.
Bloqueio (Locking)
Se uma transação bloqueou os dados, as demais transações que tentarem acessar os dados devem aguardar a liberação.
Um bloqueio pode ser aplicado a um banco de dados, tabela, linha ou atributo. Um bloqueio compartilhado (Shared Lock) pode ser imposto a um mesmo dado por várias transações, permitindo que todas as transações (incluindo a que aplicou) leiam, mas proibindo alterações e bloqueios exclusivos. Um bloqueio exclusivo (Exclusive Lock) pode ser aplicado apenas por uma transação, permitindo qualquer ação da transação que impôs, mas proibindo qualquer ação das demais.
Um deadlock é uma situação em que as transações ficam em um estado de espera 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.
A solução otimista para problemas de deadlock permite que o deadlock aconteça, mas então restaura o sistema revertendo uma das transações envolvidas no deadlock.
Com uma certa periodicidade, é realizada a busca por deadlocks. Um dos métodos de detecção é baseado no tempo, ou seja, considerar que um deadlock ocorreu se uma transação está sendo executada por tempo demais. Quando um deadlock é encontrado, uma das transações é revertida, permitindo que outras transações envolvidas no deadlock sejam concluídas. A escolha da vítima pode ser baseada no custo das transações ou na sua antiguidade (esquemas Wait-Die e Wound-wait).
A cada transação T é atribuída uma marca temporal. TS contendo o tempo de início da execução da transação.
Wait-Die.
Se TS(Ti) < TS(Tj), então Ti aguarda, caso contrário Ti é revertida e reiniciada com a mesma marca temporal.
Se uma transação jovem capturou um recurso, e uma transação mais antiga solicita o mesmo recurso, então a transação mais velha pode aguardar. Se uma transação mais antiga capturou um recurso, então a transação jovem que está solicitando esse recurso será revertida.
Wound-wait.
Se TS(Ti) < TS(Tj), então Tj é revertida e reiniciada com a mesma marca temporal, caso contrário Ti aguarda.
Se uma transação mais jovem capturou um recurso e uma transação mais antiga solicita o mesmo recurso, a transação mais jovem será revertida. Se uma transação mais antiga capturou o recurso, a transação mais jovem solicitando esse recurso é permitida a esperar. A escolha da vítima baseada na antiguidade previne o surgimento de deadlocks, mas reverte transações que não estão em estado de deadlock. O problema é que transações podem ser revertidas muitas vezes, já que uma transação mais antiga pode manter o recurso por um longo tempo.
Uma solução pessimista para o problema de deadlocks não permite que uma transação comece a execução se houver risco de um deadlock.
Para detectar deadlocks, um gráfico (gráfico de espera, wait-for-graph) é construído, em que os vértices são transações e as arestas apontam de transações que aguardam a liberação de dados para a transação que capturou esses dados. Considera-se que um deadlock ocorreu se o gráfico tiver ciclicidade. A construção do gráfico de espera, especialmente em bancos de dados distribuídos, é um procedimento dispendioso.
O bloqueio em duas fases — evitar deadlocks capturando todos os recursos utilizados pela transação no início e os liberando no final.
Todas as operações de bloqueio devem preceder a primeira operação de desbloqueio. Possui duas fases — a Fase de Crescimento, na qual ocorre a acumulação de capturas, e a Fase de Redução, na qual ocorrem as liberações. Caso não seja possível capturar um dos recursos, a transação inicia novamente. É possível que uma transação não consiga capturar os recursos necessários, por exemplo, se várias transações competirem pelos mesmos recursos.
O commit em duas fases garante a execução do commit em todas as réplicas do banco de dados.
Cada banco de dados registra informações sobre os dados que serão alterados em um log e responde ao coordenador com um OK (Fase de Votação). Após todos responderem OK, o coordenador envia um sinal obrigando todos a realizarem o commit. Após o commit. servidor respondem com OK; se algum não responder OK, o coordenador envia um sinal de cancelamento das alterações para todos os servidores (Fase de Conclusão).
Método de carimbo de tempo.
Uma transação mais antiga é revertida ao tentar acessar dados envolvidos em uma transação mais jovem.
Cada transação recebe um timestamp TS que corresponde ao tempo de início da execução. Se Ti mais velho Tj, então TS(Ti) < TS(Tj).
Quando a transação é revertida, recebe um novo timestamp. Cada objeto de dados Q envolvido na transação é marcado com dois timestamps. W-TS(Q) — o timestamp da transação mais recente que fez uma gravação sobre Q. R-TS(Q) — o timestamp da transação mais recente que fez uma leitura sobre Q.
Quando a transação T solicita a leitura de dados Q são possíveis duas opções.
Se TS(T) < W-TS(Q), ou seja, se os dados foram atualizados por uma transação mais nova, a transação T é revertida.
Se TS(T) >= W-TS(Q), então a leitura é feita e R-TS(Q) torna-se MAX(R-TS(Q), TS(T)).
Quando a transação T solicita a alteração de dados Q são possíveis duas opções.
Se TS(T) < R-TS(Q), ou seja, se os dados já foram lidos por uma transação mais nova e, se a alteração for feita, ocorrerá um conflito. A transação T é revertida.
Se TS(T) < W-TS(Q), ou seja, se a transação tenta regravar um valor mais novo, a transação T é revertida. Nos demais casos, a alteração é realizada e W-TS(Q) torna-se igual a TS(T).
Não há necessidade de construção cara do grafo de espera. Transações mais velhas dependem de transações mais novas, portanto, não há ciclos no grafo de espera. Não há deadlocks, pois as transações não esperam, mas reagem imediatamente. Reversões em cascata são possíveis. Se Ti foi revertida, e Tj leu dados que alterou Ti, então Tj também deve ser revertida. Se durante isso Tj já foi confirmada, ocorrerá uma violação do princípio de consistência.
Uma das soluções para reversões em cascata. A transação realiza todas as operações de gravação no final, e as outras transações devem esperar a conclusão dessa operação. As transações aguardam a confirmação antes da leitura.
A regra de escrita de Thomas — uma variação do método dos timestamps em que dados atualizados por uma transação mais nova não podem ser sobrescritos por uma transação mais antiga.
A transação T solicita a alteração de dados Q. Se TS(T) < W-TS(Q), ou seja, se a transação tenta regravar um valor mais novo, a transação T não é revertida como no método dos timestamps.
Fonte: habr.com
