Controle de concorrência é um método usado para garantir que as transações sejam executadas de uma forma segura e sigam as regras ACID. Os SGBD devem ser capazes de assegurar que nenhuma ação de transações completadas com sucesso (committed transactions) seja perdida ao desfazer transações abortadas (rollback).
Uma transação é uma unidade que preserva consistência. Requeremos, portanto, que qualquer escalonamento produzido ao se processar um conjunto de transações concorrentemente seja computacionalmente equivalente a um escalonamento produzindo executando essas transações serialmente em alguma ordem. Diz-se que um sistema que garante esta propriedade assegura a seriabilidade.
Técnicas de locking podem ser utilizadas para garantir seriabilidade e recuperabilidade nos escalonamentos das transações do banco de dados. Um escalonamento conflito-serializável é um escalonamento equivalente a alguma execução serial das transações.
Propriedades ACID de Transações
Vamos revisar aqui rapidamente os conceitos de ACID, que pode ser visto neste artigo.
- Atomicidade: A execução de uma transação deve ser atômica, ou todas as ações são executadas, ou nenhuma é;
- Consistência: Cada transação executada isoladamente deve preservar a consistência do banco de dados;
- Isolamento: Cada transação deve ser isolada dos efeitos da execução concorrente de outras transações;
- Durabilidade: Toda transação que for finalizada de forma bem-sucedida deve persistir seus resultados em banco mesmo na presença de falhas no sistema.
Consistência e Isolamento
É o usuário quem deve garantir a consistência da transação. Exemplo: Transferência de fundos entre contas não alteram a quantia total de dinheiro nas contas.
O isolamento deve garantir que duas transações, executadas concorrentemente, devem ter o mesmo resultado se executadas em ordem serial. Exemplo: T1 concorrente com T2 T1, T2 ou T2, T1.
Atomicidade das Transações
As falhas em uma transação podem ter como motivo:
- Interrupção do SGBD;
- Queda do sistema;
- Detecção de uma situação inesperada.
Uma transação interrompida ao meio pode deixar o banco de dados em um estado inconsistente. O banco de dados deve prover recursos para remoção dos efeitos de transações incompletas para garantir a atomicidade.
O SGBD mantém um registro (log) das ações executadas pelo usuário para que estas possam ser desfeitas caso ocorra alguma falha em uma transação. O log também é utilizado para garantir a durabilidade. Se ocorrer queda do sistema antes que todas as mudanças tenham sido feitas em disco, o log é usado para restaurar o estado do banco de dados quando o sistema for reiniciado.
Escalonamento de Transações
Um escalonamento é uma lista de ações de um conjunto de transações. Representa uma seqüência de execução que deve conservar a mesma ordem de execução das ações das transações presentes nele.
- Escalonamento completo: O escalonamento insere, para todas as transações, as ações de abort ou commit;
- Escalonamento serial: O escalonamento não intercala as ações de transações diferentes;
- Escalonamento equivalente: Para qualquer estado da base de dados, o efeito de executar um primeiro escalonamento é idêntico ao efeito de executar um segundo escalonamento;
- Escalonamento serializável: Escalonamento equivalente a alguma execução serial das transações.
Se cada transação preserva a consistência, todo escalonamento serializável preserva a consistência.
Recuperação de Falhas
O Gerenciador de Recuperação de Falhas garante a atomicidade e a durabilidade das transações.
- Atomicidade: Desfazendo as ações das transações que não realizaram o commit.
- Durabilidade: Todas as ações das transações que fizeram commit serão persistentes.
O Gerenciador é responsável por recuperar a consistência, após uma queda do sistema.
Há 3 fases no algoritmo de recuperação de ARIES:
- Analisar: Percorre o log para frente (a partir do ponto de verificação mais recente) para identificar todas as transações que estavam ativas, e todas as “páginas sujas” no momento da falha.
- Refazer: Refaz todas as atualizações das “páginas sujas”, quando necessário, para garantir que todas as atualizações registradas no log foram realizadas e escritas no disco.
- Desfazer: As escritas de todas as transações que estavam ativas no momento da falha são desfeitas (recuperando o valor anterior à atualização registrado no log da atualização), varrendo o log de trás para frente.
Falhas no Sistema
Dada a complexidade dos equipamentos e programas modernos, é ponto pacífico que falhas ocorrerão, quer sejam problemas de “hardware”, quer sejam defeitos de “software”. Estas falhas têm como efeito indesejável comprometer a integridade do BD. Para que seja de alguma utilidade prática, O SGBD deve, portanto, incorporar mecanismos que garantam sua integridade, quando não pelo menos na presença daquelas falhas que ocorrem com mais freqüência. Desta forma, o SGBD pode ser mantido em operação por longos períodos de tempo sendo, quando muito, interrompido por curtos intervalos para que os mecanismos de controle de integridade sanem inconsistências causadas por eventuais falhas. Esta seção sevirá de introdução à área de controle de integridade em SGBD, onde os principais problemas e as soluções mais importantes serão mencionadas de forma simplificada. Em capítulo posterior, esta problemática será analisada em maiores detalhes.
Intuitivamente, a única maneira do SGBD se proteger contra falhas, que podem destruir parte dos dados, é criar e manter certa redundância no sistema. Desta forma, quando parte do BD e danificado, sua “cópia redundante” pode ser revivida para recuperar os dados perdidos e restabelecer a operação normal. Inclusive, em sistemas que requeiram alta confiabilidade, as partes mais críticas do próprio “hardware” podem ser duplicadas de forma redundante. Note que, se a “cópia” de um objeto não é recente, então deve-se manter também um histórico das operações efetuadas sobre este objeto, de tal modo que o SGBD possa refazer estas operações e trazer esta “cópia” ao estado mais recente, idêntico àquele da “cópia” original antes da falha. Caso contrário, transações executadas entre o instante de criação da “cópia” e o momento atual serão perdidas.
Tipos de falhas
Um nó qualquer, quando em operação normal, depende de um padrão de interligações complexas entre vários elementos. Para efeito de examinar a ocorrência e danos causados por falhas nestes componentes é conveniente agrupá-los da seguinte forma
- procedimentos;
- processadores;
- memórias;
- no caso distribuído, comunicação de dados;
Por procedimentos entende-se a totalidade dos módulos e programas aplicativos (“software”) que compõem o SGBD, podendo-se incluir aqui também os utilitários do sistema operacional usados pelo SGBD. Os processadores correspondem tanto ao processador, ou processadores, central como as demais unidades de controle de periféricos, terminais, “modems”, etc. As memórias, onde reside o BD, aqui entendido como dados mais programas, são de crucial importância. É lá que será acomodada toda redundância introduzida para fins de controle de integridade. Todos os mecanismos de proteção contra falhas prestam especial atenção ao tratamento dispensado aos vários tipos de memórias com que o sistema interage e, em última análise, se fiarão na boa característica de resistência a falhas que tais elementos oferecem. Para que se possa conduzir uma análise mais detalhada, as memórias manipuladas pelo sistema serão subdivididas em:
- memória principal
- memória secundária imediatamente disponível
- memória secundária dormente
A memória principal corresponde a memória associada aos processadores, isto é, memória dos processadores centrais, memórias tipo cache, “buffers” de entrada/saída, espaço de paginação, etc. Há certos tipos de falhas às quais o conteúdo da memória principal não sobrevive, devendo ser considerado como irremediavelmente perdido. Estes defeitos serão cognominados de falhas primárias. Interrupção no fornecimento de energia elétrica, defeito nos processadores ou procedimentos do sistema podem causar este tipo de falha. Por não sobreviver a este tipo de falha mais comum, diz-se que a memória principal é volátil.
O termo memória secundária imediatamente disponível, ou memória secundária ativa, referem-se à memória de massa, geralmente discos magnéticos, onde o BD é residente e que está a disposição do SGBD a todo instante. O conteúdo da memória secundária ativa não é afetado por falhas primárias que o sistema venha a sofrer. Porém, panes nos cabeçotes de leitura/escrita dos discos ou partículas de poeira que assentem sobre a superfície dos mesmos podem danificar os delicados mecanismos dos cabeçotes e provocar danos irrecuperáveis à superfície magnética destruindo, em todo ou em parte, o conteúdo da memória secundária ativa. Isto se verificando, diz-se que o sistema sofreu uma falha secundária. Fitas magnéticas também podem ser usadas como memória secundária ativa, se bem que cuidados devem ser tomados para que a eficiência do sistema não seja por demais comprometida. Partes raramente usadas do BD, cópias antigas de parte ou da íntegra do sistema, além de aplicativos ativados com pouca freqüência, são candidatos naturais a residirem em fita. Nunca dicionários, catálogos e outros elementos freqüentemente acessados.
Como um último recurso, e em casos realmente catastróficos, o controle de integridade do SGBD pode apelar para a memória secundária dormente (“off-line”). Entende-se como memória secundária dormente toda memória fisicamente desconectada do sistema. Geralmente, devido à sua grande capacidade de armazenamento de dados, fitas magnéticas são empregadas para este fim. Em BD de grandes proporções, toda uma fitoteca pode ser necessária. É comum armazenar os componentes da memória secundária dormente em locais próprios, distantes do centro onde opera o sistema. A preocupação básica é evitar que catástrofes sobre um dos lugares, tais como incêndios ou furtos, não afete o outro. De qualquer maneira, eventos que destruam ou inutilizem o conteúdo da memória secundária dormente do sistema serão chamados de falhas terciárias.
Existem situações que exigem ações por parte do sistema de controle de integridade do BD, embora não se configurem propriamente como falhas em componentes do sistema. O caso típico é quando, sob operação normal, surje a necessidade de se cancelar transações. Isto pode ocorrer tanto por erro ou a pedido do usuário, como podem ser ações forçadas pelo SGBD como última instância para evitar bloqueio na execução de transações que competem por certos recursos do sistema. Estes casos serão rotulados como pseudo-falhas do sistema. Agora, não está em cheque o conteúdo de nenhuma das memórias ou a sanidade dos processadores ou procedimentos associados ao sistema. A cooperação do controle de integridade, porém, é necessária para invocar a transação que inverte o efeito das ações elementares executadas em benefício da transação a ser cancelada. Deste modo, o BD permanece em um estado consistente, além do que é forçada a liberação dos recursos que foram seqüestrados pela transação.
A discussão acima desloca-se a partir de falhas nos componentes mais nobres, isto é, com menor tempo de acesso, para os menos nobres, com tempos de acesso consideravelmente maiores. É importante ter em mente uma noção da freqüência com que os vários tipos de falhas costumam ocorrer na prática, bem como do tempo necessário para que o controle de integridade restaure a operação normal do BD em cada caso.
Controle de Concorrência
Um SGBD, suportando bancos de dados com várias aplicações, deverá necessariamente permitir acesso concorrente aos dados. É intuitivo que, em tese, quanto maior for o nível de concorrência permitido, tanto melhor será o tempo de resposta do sistema como um todo. Em tese porque, forçosamente, os mecanismos que controlam o acesso concorrente ao banco impõem um ônus adicional sobre o desempenho do SGBD. Os procedimentos que harmonizam o paralelismo no seio do SGBD serão conhecidos por mecanismos de controle de concorrência.
Num cenário de BDs distribuídos, ou mesmo de BDs centralizados com acesso distribuído, a implementação de paralelismo torna-se uma necessidade imperiosa. Com relação ao caso centralizado, hoje são conhecidas técnicas que equacionam os problemas a contento, apoiadas em um tratamento teórico preciso e confirmadas por implementações reais. No que concerne ao caso distribuído, a situação é mais confusa. Isto é devido, em grande parte, ao fato de que os nós da rede operam de forma bastante independente, embora o controle de concorrência deva ser efetivado de forma global, abrangendo informação que pode estar espalhada por vários nós. Aqui, muitos dos aspectos do problema ainda se encontram em fase de pesquisa e experimentação.
Exemplificando o problema
Quando transações manipulam dados concorrentemente, certos problemas, chamados de anomalias de sincronização, poderão ocorrer. Exemplos são acessos a dados inconsistentes, perdas de atualizações e perda da consistência do banco. Por exemplo, considere duas transações, T1 e T2, ambas debitando uma determinada quantia a um saldo S. Seja a seqüência de ações:
1) T1 lê o saldo S;
2) T2 lê o saldo S;
3) T2 debita a quantia, escrevendo o novo valor de S;
4) T1 debita a quantia, escrevendo o novo valor de S;
O valor final do saldo neste caso refletirá apenas a quantia debitada por T1, sendo a atualização submetida por T2 perdida.
O exemplo acima também serve para ilustrar porque controle de concorrência, embora semelhante, não é equivalente ao dilema de gerenciar acesso a recursos partilhados em um sistema operacional. De fato, na seqüência acima, cada transação respeita o princípio de acesso exclusivo ao objeto partilhado S. Porém, isto claramente não é suficiente pois uma atualização é perdida. Assim sendo, um mecanismo de controle de concorrência não deverá se limitar a implementar acesso exclusivo a objetos do banco de dados.
O problema fundamental a ser resolvido pelos métodos de controle de concorrência é colocado da seguinte forma. Assuma que todas as transações preservam a consistência lógica do banco de dados e terminam, quando executadas seqüencialmente. Um método de controle de concorrência deverá, então, garantir que em toda execução concorrente das transações:
1) cada transação termina;
2) cada transação é executada sem interferência das outras, e sem que anomalias de sincronização ocorram.
Estes objetivos deverão ser atingidos permitindo-se um máximo de concorrência possível, de forma transparente para os usuários, e para qualquer conjunto de transações acessando qualquer parte do banco de dados.
Note que o controle de concorrência e a gerência de transações são tarefas que se complementam. Cabe ao gerente de transações escalonar as ações de uma transação de tal forma que esta seja processada corretamente, conforme a especificação do usuário. Por outro lado, cabe ao mecanismo de controle de concorrência arbitrar a intercalação das ações de transações diferentes de tal forma a que todas as transações terminem, sejam processadas sem que uma interfira com a outra e sem que anomalias de sincronização ocorram.
A idéia do critério de correção comumente aceito é bem simples. Seja T um conjunto de transações. Inicialmente observa-se que uma execução seqüencial ou serial das transações em T, ou seja, uma execução em que as transações são processadas uma após a outra terminar, em uma ordem qualquer, é necessariamente correta. Isto é fácil ver pois em uma execução serial não há processamento concorrente.
O próximo passo é postular que uma execução concorrente E das transações em T será considerada correta se for computacionalmente equivalente a alguma execução serial das transações. A execução E será chamada neste caso de serializável. A noção de equivalência computacional usada aqui exige que o estado final do banco de dados seja o mesmo em E e S e que as transações leiam os mesmos dados em E e S (assumindo que E e S começam no mesmo estado inicial do banco de dados) e, portanto, executem a mesma computação em E e S.
A postulação deste critério de correção para execuções concorrentes é justificada pois, como S é serial, as transações em T são naturalmente executadas sem que uma interfira com a outra. É fácil justificar que anomalias de sincronização não ocorrem em S. Como E é computacionalmente equivalente a S, as transações são executadas em E sem que uma interfira com a outra e sem que anomalias de sincronização ocorram. Os próximos exemplos ilustrarão estes conceitos.
Suponha que P e C representem os saldos da poupança e da conta corrente de um determinado cliente (armazenadas em um banco de dados centralizado, por simplicidade). Considere duas transações cujos efeitos desejados são:
T1: se houver saldo suficiente na poupança, transfira $5.000,00 da poupança para a conta corrente;
T2: se houver saldo suficiente na conta corrente, debite um cheque de $10.000,00. Suponha que a seqüência de ações elementares sobre o banco de dados gerada pela execução
da transação T1 (supondo que haja saldo suficiente) seja: T11: leia o saldo P para X;
X := X – 5.000; T12: leia o saldo C para Y;
Y := Y + 5.000; T13: escreva o novo saldo Y em C; T14: escreva o novo saldo X em P.
Apenas aquelas ações que acessam o banco de dados receberam rótulos pois são estas que nos interessarão a seguir. Suponha que a seqüência de ações elementares sobre o banco de dados gerada pela execução da transação T2 (supondo que haja saldo suficiente) por sua vez seja:
T21: leia o saldo C para Z; Z := Z – 10.000;
T22: escreva o novo saldo Z em C.
Primeiro considere uma execução puramente serial em que T2 é processada antes de T1. Esta execução pode ser abstraída pela seguinte seqüência de rótulos das operações sobre o banco de dados:
S = T21 T22 T11 T12 T13 T14
Considere agora uma execução concorrente abstraída pela seguinte seqüência de rótulos:
L = T11 T21 T22 T12 T13 T14
Esta execução L não é serial, porém é serializável por ser equivalente a S. Isto é fácil de ver pois a ação T11 em L pode ser comutada com T21 e T22 sem que o resultado do processamento de T1 seja alterado e sem que o estado final do banco de dados seja modificado. De fato, T11 lê o saldo P enquanto as ações de T2 afetam apenas o saldo C. Logo, T11 lê o mesmo saldo P em L e em S.
Por fim, considere uma execução concorrente abstraída pela seguinte seqüência de rótulos:
N = T11 T12 T21 T22 T13 T14
Esta execução N não é serial e também não é serializável por não ser equivalente nem a S, nem a uma execução serial S’ em que T1 é processada antes de T2. De fato, T12 lê o saldo inicial C, que é posteriormente escrito por T13. Desta forma, a atualização expressa por T2 é perdida e o banco de dados final (em N) não reflete a execução de T2. Logo N não pode ser equivalente à S ou à S’, ou seja, não é serializável.
Parabéns pela iniciativa, seria interessante se você pudesse colocar a bibiografia que você vem usando para criar os “posts.
Abraços