DBMS Distribuído - Controlando a Concorrência
As técnicas de controle de simultaneidade garantem que várias transações sejam executadas simultaneamente, mantendo as propriedades ACID das transações e a serializabilidade nas programações.
Neste capítulo, estudaremos as várias abordagens para controle de concorrência.
Protocolos de controle de simultaneidade baseados em bloqueio
Os protocolos de controle de simultaneidade baseados em bloqueio usam o conceito de itens de dados de bloqueio. UMAlocké uma variável associada a um item de dados que determina se as operações de leitura / gravação podem ser executadas nesse item de dados. Geralmente, uma matriz de compatibilidade de bloqueio é usada que indica se um item de dados pode ser bloqueado por duas transações ao mesmo tempo.
Os sistemas de controle de simultaneidade baseados em bloqueio podem usar protocolos de bloqueio monofásicos ou bifásicos.
Protocolo de bloqueio monofásico
Neste método, cada transação bloqueia um item antes de usar e libera o bloqueio assim que termina de usá-lo. Este método de bloqueio fornece simultaneidade máxima, mas nem sempre impõe a serialização.
Protocolo de bloqueio de duas fases
Neste método, todas as operações de bloqueio precedem a primeira operação de desbloqueio ou desbloqueio. A transação compreende duas fases. Na primeira fase, uma transação adquire apenas todos os bloqueios de que necessita e não libera nenhum bloqueio. Isso é chamado de expansão ougrowing phase. Na segunda fase, a transação libera os bloqueios e não pode solicitar novos bloqueios. Isso é chamado deshrinking phase.
Cada transação que segue o protocolo de bloqueio de duas fases tem garantia de ser serializável. No entanto, essa abordagem fornece baixo paralelismo entre duas transações conflitantes.
Algoritmos de controle de simultaneidade de carimbo de data / hora
Os algoritmos de controle de simultaneidade baseados em carimbo de data / hora usam o carimbo de data / hora de uma transação para coordenar o acesso simultâneo a um item de dados para garantir a serialização. Um carimbo de data / hora é um identificador exclusivo fornecido pelo DBMS a uma transação que representa a hora de início da transação.
Esses algoritmos garantem que as transações sejam confirmadas na ordem ditada por seus carimbos de data / hora. Uma transação mais antiga deve ser confirmada antes de uma transação mais jovem, visto que a transação mais antiga entra no sistema antes da mais jovem.
As técnicas de controle de simultaneidade baseadas em carimbo de data / hora geram programações serializáveis de forma que a programação serial equivalente seja organizada de acordo com a idade das transações participantes.
Alguns dos algoritmos de controle de simultaneidade baseados em timestamp são -
- Algoritmo básico de ordenação de carimbo de data / hora.
- Algoritmo de ordenação de carimbo de data / hora conservador.
- Algoritmo de multiversão baseado na ordenação de carimbo de data / hora.
A ordenação baseada em carimbo de data / hora segue três regras para forçar a serialização -
Access Rule- Quando duas transações tentam acessar o mesmo item de dados simultaneamente, para operações conflitantes, a prioridade é dada à transação mais antiga. Isso faz com que a transação mais jovem espere que a transação mais antiga seja confirmada primeiro.
Late Transaction Rule- Se uma transação mais jovem gravou um item de dados, uma transação mais antiga não tem permissão para ler ou gravar esse item de dados. Esta regra evita que a transação mais antiga seja confirmada após a transação mais jovem já ter sido confirmada.
Younger Transaction Rule - Uma transação mais jovem pode ler ou gravar um item de dados que já foi gravado por uma transação mais antiga.
Algoritmo de controle de simultaneidade otimista
Em sistemas com baixas taxas de conflito, a tarefa de validar todas as transações para serialização pode diminuir o desempenho. Nesses casos, o teste de serialização é adiado para pouco antes do commit. Como a taxa de conflito é baixa, a probabilidade de abortar transações que não são serializáveis também é baixa. Essa abordagem é chamada de técnica de controle de concorrência otimista.
Nesta abordagem, o ciclo de vida de uma transação é dividido nas seguintes três fases -
Execution Phase - Uma transação busca itens de dados para a memória e executa operações sobre eles.
Validation Phase - Uma transação executa verificações para garantir que a confirmação de suas alterações no banco de dados passe no teste de serializabilidade.
Commit Phase - Uma transação grava de volta no disco itens de dados modificados na memória.
Este algoritmo usa três regras para impor a serialização na fase de validação -
Rule 1- Dadas duas transações T i e T j , se T i estiver lendo o item de dados que T j está escrevendo, então a fase de execução de T i não pode se sobrepor à fase de confirmação de T j . T j pode confirmar somente após T i ter concluído a execução.
Rule 2- Dadas duas transações T i e T j , se T i estiver escrevendo o item de dados que T j está lendo, então a fase de confirmação de T i não pode se sobrepor à fase de execução de T j . T j pode começar a executar somente após T i já ter se comprometido.
Rule 3- Dadas duas transações T i e T j , se T i está escrevendo o item de dados que T j também está escrevendo, então a fase de confirmação de T i não pode se sobrepor à fase de confirmação de T j . T j pode começar a cometer somente após T i já ter se comprometido.
Controle de simultaneidade em sistemas distribuídos
Nesta seção, veremos como as técnicas acima são implementadas em um sistema de banco de dados distribuído.
Algoritmo de bloqueio bifásico distribuído
O princípio básico do bloqueio de duas fases distribuído é o mesmo do protocolo de bloqueio de duas fases básico. No entanto, em um sistema distribuído, existem sites designados como gerenciadores de bloqueio. Um gerenciador de bloqueio controla as solicitações de aquisição de bloqueio dos monitores de transação. A fim de impor a coordenação entre os gerenciadores de bloqueio em vários sites, pelo menos um site recebe autoridade para ver todas as transações e detectar conflitos de bloqueio.
Dependendo do número de sites que podem detectar conflitos de bloqueio, as abordagens de bloqueio distribuído em duas fases podem ser de três tipos -
Centralized two-phase locking- Nesta abordagem, um site é designado como o gerenciador de bloqueio central. Todos os sites no ambiente sabem a localização do gerenciador de bloqueio central e obtêm bloqueio dele durante as transações.
Primary copy two-phase locking- Nesta abordagem, vários locais são designados como centros de controle de eclusas. Cada um desses sites tem a responsabilidade de gerenciar um conjunto definido de bloqueios. Todos os sites sabem qual centro de controle de bloqueio é responsável por gerenciar o bloqueio de qual tabela de dados / item de fragmento.
Distributed two-phase locking- Nesta abordagem, há vários gerenciadores de bloqueio, onde cada gerenciador de bloqueio controla bloqueios de itens de dados armazenados em seu site local. A localização do gerenciador de bloqueio é baseada na distribuição e replicação de dados.
Controle de simultaneidade de carimbo de data / hora distribuído
Em um sistema centralizado, o carimbo de data / hora de qualquer transação é determinado pela leitura do relógio físico. Mas, em um sistema distribuído, as leituras de relógio físico / lógico local de qualquer site não podem ser usadas como carimbos de data / hora globais, uma vez que não são globalmente exclusivos. Portanto, um carimbo de data / hora consiste em uma combinação de ID do site e leitura do relógio desse site.
Para implementar algoritmos de ordenação de carimbo de data / hora, cada site possui um planejador que mantém uma fila separada para cada gerenciador de transações. Durante a transação, um gerenciador de transações envia uma solicitação de bloqueio ao planejador do site. O planejador coloca a solicitação na fila correspondente em ordem crescente de registro de data e hora. As solicitações são processadas na frente das filas na ordem de seus carimbos de data / hora, ou seja, o mais antigo primeiro.
Gráficos de conflito
Outro método é criar gráficos de conflito. Para esta transação são definidas classes. Uma classe de transação contém dois conjuntos de itens de dados chamados conjunto de leitura e conjunto de gravação. Uma transação pertence a uma classe particular se o conjunto de leitura da transação for um subconjunto do conjunto de leitura da classe e o conjunto de gravação da transação for um subconjunto do conjunto de gravação da classe. Na fase de leitura, cada transação emite seus pedidos de leitura para os itens de dados em seu conjunto de leitura. Na fase de gravação, cada transação emite seus pedidos de gravação.
Um gráfico de conflito é criado para as classes às quais pertencem as transações ativas. Ele contém um conjunto de bordas verticais, horizontais e diagonais. Uma borda vertical conecta dois nós em uma classe e denota conflitos dentro da classe. Uma borda horizontal conecta dois nós em duas classes e denota um conflito de gravação / gravação entre classes diferentes. Uma borda diagonal conecta dois nós em duas classes e denota um conflito de leitura-gravação ou leitura-gravação entre duas classes.
Os gráficos de conflito são analisados para verificar se duas transações dentro da mesma classe ou em duas classes diferentes podem ser executadas em paralelo.
Algoritmo de controle de simultaneidade otimista distribuída
O algoritmo de controle de simultaneidade otimista distribuído estende o algoritmo de controle de simultaneidade otimista. Para esta extensão, duas regras são aplicadas -
Rule 1- De acordo com esta regra, uma transação deve ser validada localmente em todos os sites quando for executada. Se uma transação for considerada inválida em qualquer site, ela será abortada. A validação local garante que a transação mantenha a serialização nos sites onde foi executada. Depois que uma transação passa no teste de validação local, ela é validada globalmente.
Rule 2- De acordo com esta regra, após uma transação passar no teste de validação local, ela deve ser validada globalmente. A validação global garante que, se duas transações conflitantes forem executadas juntas em mais de um site, elas devem ser confirmadas na mesma ordem relativa em todos os sites que executam juntas. Isso pode exigir que uma transação espere pela outra transação conflitante, após a validação antes do commit. Esse requisito torna o algoritmo menos otimista, pois uma transação pode não ser capaz de confirmar assim que é validada em um site.