Protocolos de Controle de Concorrência

Protocolos de controle de concorrência são os métodos — bloqueio (locking), ordenação por carimbo de data/hora (timestamp ordering), validação otimista e multiversionamento — que agendam transações concorrentes para que o resultado seja equivalente a uma execução serial.

Definition

Um protocolo de controle de concorrência é um conjunto de regras que governa como transações concorrentes adquirem acesso a dados, de modo que cada agendamento permitido seja serializável (ou satisfaça um nível de isolamento mais fraco escolhido), preservando assim o isolamento sem forçar as transações a serem executadas uma de cada vez.

Scope

Este tópico abrange os protocolos que impõem a serializabilidade sob concorrência: bloqueio em duas fases e sua variante estrita, com detecção e prevenção de "deadlock"; protocolos de ordenação por carimbo de data/hora; controle de concorrência otimista com fases de leitura-validação-escrita; e controle de concorrência multiversão, incluindo isolamento de "snapshot". Ele trata de como cada protocolo garante agendamentos corretos e as "trade-offs" entre bloqueio, abortos e "throughput". Exclui a definição de serializabilidade em si e os mecanismos de recuperação que complementam o controle de concorrência.

Core questions

• Como o bloqueio em duas fases garante agendamentos serializáveis?
• Como os "deadlocks" são detectados, prevenidos ou resolvidos?
• Como os protocolos de ordenação por carimbo de data/hora e otimistas diferem do bloqueio?
• Como o controle de concorrência multiversão permite que os leitores evitem bloquear os escritores?
• Quais são as "trade-offs" de "throughput" entre métodos pessimistas e otimistas?

Key concepts

• bloqueio em duas fases
• 2PL estrito e rigoroso
• bloqueios compartilhados e exclusivos
• detecção e prevenção de "deadlock"
• ordenação por carimbo de data/hora
• controle de concorrência otimista
• controle de concorrência multiversão
• isolamento de "snapshot"

Key theories

Bloqueio em duas fases

Se cada transação adquire todos os seus bloqueios antes de liberar qualquer um (uma fase de crescimento seguida por uma fase de encolhimento), todos os agendamentos resultantes são serializáveis por conflito; o bloqueio estrito em duas fases adicionalmente mantém os bloqueios de escrita até o "commit" para garantir a recuperabilidade.

Controle de concorrência otimista

As transações são executadas sem bloqueio e são validadas no momento do "commit" contra transações concorrentes; transações conflitantes são abortadas e repetidas, o que funciona bem quando a contenção é baixa.

Controle de concorrência multiversão

Ao manter múltiplas versões de cada item de dados, o sistema permite que as leituras acessem um "snapshot" consistente sem bloquear as escritas; o isolamento de "snapshot" é um esquema multiversão amplamente utilizado, embora possa permitir certas anomalias não serializáveis.

Clinical relevance

Os protocolos de controle de concorrência determinam como um banco de dados se comporta sob carga: o bloqueio é robusto, mas pode causar "deadlocks" e contenção; métodos otimistas e multiversão permitem alta concorrência de leitura; e a escolha do protocolo molda diretamente o "throughput" e a latência de sistemas transacionais de alto tráfego.

History

O bloqueio em duas fases e os bloqueios de predicado foram formalizados por Eswaran e colegas no System R em 1976; Kung e Robinson introduziram o controle de concorrência otimista em 1981; e a monografia de Bernstein, Hadzilacos e Goodman de 1987 unificou a teoria. Métodos multiversão e isolamento de "snapshot" tornaram-se posteriormente dominantes em sistemas de banco de dados amplamente utilizados devido ao seu comportamento favorável à leitura.

Debates

Isolamento de "snapshot" versus serializabilidade

O isolamento de "snapshot" oferece alta concorrência ao permitir que os leitores vejam um "snapshot" consistente, mas permite anomalias como "write skew" que a serializabilidade completa proíbe; os profissionais debatem quando sua garantia mais fraca é aceitável e quando variantes serializáveis são necessárias.

Key figures

• Jim Gray
• Philip Bernstein
• H. T. Kung

Seminal works

• eswaran1976
• kung1981
• bernstein1987

Frequently asked questions

O que causa um "deadlock" e como ele é tratado?

Um "deadlock" ocorre quando duas ou mais transações cada uma detém um bloqueio que a outra precisa, de modo que nenhuma pode prosseguir. Os sistemas o tratam por detecção — construindo um grafo de espera, encontrando um ciclo e abortando uma transação vítima — ou por esquemas de prevenção que ordenam a aquisição de bloqueios ou usam carimbos de data/hora para decidir qual transação espera versus aborta.

Quando o controle de concorrência otimista é uma boa escolha?

Métodos otimistas brilham quando os conflitos são raros, porque as transações são executadas sem sobrecarga de bloqueio e apenas ocasionalmente falham na validação e tentam novamente. Sob alta contenção, eles desperdiçam trabalho em abortos e novas tentativas, então o bloqueio pessimista ou métodos multiversão são geralmente preferidos para cargas de trabalho com muitas escritas e propensas a conflitos.