Bloqueio de duas fases - Two-phase locking

Este artigo é sobre o controle de simultaneidade . Para obter consenso de confirmação em uma transação distribuída, consulte Protocolo de confirmação de duas fases .

Em bancos de dados e processamento de transações , o bloqueio de duas fases ( 2PL ) é um método de controle de simultaneidade que garante a serialização . Ele também é o nome do conjunto resultante de transações de banco de dados horários (histórias). O protocolo usa bloqueios , aplicados por uma transação aos dados, que podem bloquear (interpretados como sinais para interromper) o acesso de outras transações aos mesmos dados durante a vida da transação.

Pelo protocolo 2PL, os bloqueios são aplicados e removidos em duas fases:

  1. Fase de expansão: bloqueios são adquiridos e nenhum bloqueio é liberado.
  2. Fase de encolhimento: os bloqueios são liberados e nenhum bloqueio é adquirido.

Dois tipos de bloqueios são usados ​​pelo protocolo básico: bloqueios compartilhados e exclusivos . Refinamentos do protocolo básico podem usar mais tipos de bloqueio. Usando bloqueios que bloqueiam processos, 2PL pode estar sujeito a deadlocks que resultam do bloqueio mútuo de duas ou mais transações.

Bloqueios de acesso a dados

Um bloqueio é um objeto do sistema associado a um recurso compartilhado, como um item de dados de um tipo elementar, uma linha em um banco de dados ou uma página da memória. Em um banco de dados, um bloqueio em um objeto de banco de dados (um bloqueio de acesso a dados) pode precisar ser adquirido por uma transação antes de acessar o objeto. O uso correto de bloqueios evita operações indesejadas, incorretas ou inconsistentes em recursos compartilhados por outras transações simultâneas. Quando um objeto de banco de dados com um bloqueio existente adquirido por uma transação precisa ser acessado por outra transação, o bloqueio existente para o objeto e o tipo de acesso pretendido são verificados pelo sistema. Se o tipo de bloqueio existente não permitir esse tipo específico de tentativa de acesso simultâneo, a tentativa de acesso da transação será bloqueada (de acordo com um acordo / esquema predefinido). Na prática, um bloqueio em um objeto não bloqueia diretamente a operação de uma transação sobre o objeto, mas impede que a transação adquira outro bloqueio no mesmo objeto, necessário para ser mantido / pertencente à transação antes de executar esta operação. Assim, com um mecanismo de bloqueio, o bloqueio de operação necessário é controlado por um esquema de bloqueio de bloqueio adequado, que indica que tipo de bloqueio bloqueia o tipo de bloqueio.

Dois tipos principais de bloqueios são usados:

  • O bloqueio de gravação ( bloqueio exclusivo ) é associado a um objeto de banco de dados por uma transação (Terminologia: "a transação bloqueia o objeto" ou "adquire bloqueio para ele") antes de gravar (inserir / modificar / excluir) esse objeto.
  • O bloqueio de leitura ( bloqueio compartilhado ) é associado a um objeto de banco de dados por uma transação antes de ler (recuperar o estado) desse objeto.

As interações comuns entre esses tipos de bloqueio são definidas pelo comportamento de bloqueio da seguinte maneira:

  • Um bloqueio de gravação existente em um objeto de banco de dados bloqueia uma gravação pretendida no mesmo objeto (já solicitada / emitida) por outra transação, bloqueando um bloqueio de gravação respectivo de ser adquirido pela outra transação. O segundo bloqueio de gravação será adquirido e a gravação solicitada do objeto ocorrerá (materializará) após o bloqueio de gravação existente ser liberado.
  • Um bloqueio de gravação bloqueia uma leitura pretendida (já solicitada / emitida) por outra transação, bloqueando o respectivo bloqueio de leitura .
  • Um bloqueio de leitura bloqueia uma gravação pretendida por outra transação, bloqueando o respectivo bloqueio de gravação .
  • Um bloqueio de leitura não bloqueia uma leitura pretendida por outra transação. O respectivo bloqueio de leitura para a leitura pretendida é adquirido (compartilhado com a leitura anterior) imediatamente após a leitura pretendida ser solicitada, e então a própria leitura pretendida ocorre.

Existem várias variações e refinamentos desses principais tipos de bloqueio, com as respectivas variações de comportamento de bloqueio. Se um primeiro bloqueio bloqueia outro bloqueio, os dois bloqueios são chamados de incompatíveis ; caso contrário, os bloqueios são compatíveis . Freqüentemente, as interações de bloqueio de tipos de bloqueio são apresentadas na literatura técnica por uma tabela de compatibilidade de bloqueio . A seguir está um exemplo com os principais tipos de bloqueio comuns:

Tabela de compatibilidade de bloqueio
Tipo de bloqueio read-lock bloqueio de escrita
read-lock ✔ X
bloqueio de escrita X X
✔ indica compatibilidade
X indica incompatibilidade, ou seja, um caso em que um bloqueio do primeiro tipo (na coluna da esquerda) em um objeto bloqueia um bloqueio do segundo tipo (na linha superior) de ser adquirido no mesmo objeto (por outra transação). Um objeto normalmente tem uma fila de espera de operações solicitadas (por transações) com os respectivos bloqueios. O primeiro bloqueio bloqueado para operação na fila é adquirido assim que o bloqueio de bloqueio existente é removido do objeto, e então sua respectiva operação é executada. Se um bloqueio para operação na fila não for bloqueado por nenhum bloqueio existente (a existência de vários bloqueios compatíveis em um mesmo objeto é possível simultaneamente), ele é adquirido imediatamente.
Comentário: Em algumas publicações, as entradas da tabela são simplesmente marcadas como "compatível" ou "incompatível" ou, respectivamente, "sim" ou "não".

Bloqueio bifásico e seus casos especiais

Bloqueio bifásico

De acordo com o protocolo de bloqueio de duas fases , uma transação lida com seus bloqueios em duas fases distintas e consecutivas durante a execução da transação:

  1. Fase de expansão (também conhecida como fase de crescimento): os bloqueios são adquiridos e nenhum bloqueio é liberado (o número de bloqueios só pode aumentar).
  2. Fase de redução (também conhecida como fase de contratação): os bloqueios são liberados e nenhum bloqueio é adquirido.

As duas regras de bloqueio de fase podem ser resumidas como: nunca adquira um bloqueio após um bloqueio ter sido liberado. A propriedade de serialização é garantida para uma programação com transações que obedecem a esta regra.

Normalmente, sem conhecimento explícito em uma transação no final da fase 1, ela é determinada com segurança apenas quando uma transação concluiu o processamento e solicitou a confirmação. Neste caso, todos os bloqueios podem ser liberados de uma vez (fase 2).

Travamento conservador de duas fases

A diferença entre 2PL e C2PL é que as transações de C2PL obtêm todos os bloqueios de que precisam antes do início das transações. Isso é para garantir que uma transação que já contém alguns bloqueios não será bloqueada esperando por outros bloqueios. 2PL conservador evita bloqueios .

Bloqueio estrito de duas fases

Para estar em conformidade com o protocolo S2PL, uma transação precisa estar em conformidade com 2PL e liberar seus bloqueios de gravação (exclusivos) somente após ter terminado, ou seja, ser confirmada ou abortada . Por outro lado, bloqueios de leitura (compartilhados) são liberados regularmente durante a fase 2. Este protocolo não é apropriado em árvores B porque causa gargalo (enquanto as árvores B sempre começam a pesquisar a partir da raiz pai).

Bloqueio estrito de duas fases forte

ou Rigorousness , ou Rigorous Scheduling , ou Rigorous two-phase locking

Para cumprir o bloqueio estrito de duas fases forte (SS2PL), o protocolo de bloqueio libera os bloqueios de gravação (exclusivo) e de leitura (compartilhado) aplicados por uma transação somente após o término da transação, ou seja, somente após a conclusão da execução (estando pronto ) e tornando-se confirmado ou abortado . Este protocolo também está em conformidade com as regras S2PL. Uma transação que obedece a SS2PL pode ser vista como tendo a fase 1 que dura toda a duração da execução da transação, e nenhuma fase 2 (ou uma fase 2 degenerada). Assim, apenas uma fase é deixada, e "duas fases" no nome parece ainda ser usado devido ao desenvolvimento histórico do conceito de 2PL, e 2PL sendo uma superclasse. A propriedade SS2PL de uma programação também é chamada de Rigor . É também o nome da classe de horários com esta propriedade, e um horário SS2PL também é denominado "horário rigoroso". O termo "Rigorosidade" está livre do legado desnecessário de "duas fases", além de ser independente de qualquer mecanismo (de bloqueio) (em princípio, outros mecanismos de bloqueio podem ser usados). O respectivo mecanismo de bloqueio da propriedade é às vezes referido como Rigorous 2PL .

SS2PL é um caso especial de S2PL, ou seja, a classe de programações SS2PL é uma subclasse apropriada de S2PL (cada programação SS2PL também é uma programação S2PL, mas existem programações S2PL que não são SS2PL).

SS2PL tem sido o protocolo de controle de concorrência preferido para a maioria dos sistemas de banco de dados e usado desde seus primeiros dias na década de 1970. É provado ser um mecanismo eficaz em muitas situações, e fornece além de serializabilidade também Strictness (um caso especial de recuperação em cascata), que é fundamental para a recuperação eficiente de banco de dados , e também o pedido de compromisso (CO) para participação em ambientes distribuídos onde um CO são empregadas soluções de serialização distribuída e global baseadas em serialização . Sendo um subconjunto de CO, existe uma implementação eficiente de SS2PL distribuído sem um gerenciador de bloqueio distribuído (DLM), enquanto os deadlocks distribuídos (veja abaixo) são resolvidos automaticamente. O fato de SS2PL empregado em sistemas de múltiplos bancos de dados garantir a serialização global já era conhecido há anos antes da descoberta do CO, mas somente com o CO veio a compreensão do papel de um protocolo de comprometimento atômico na manutenção da serialização global, bem como a observação da serialização automática resolução de deadlock distribuída (veja um exemplo detalhado de SS2PL distribuído ). Na verdade, SS2PL herdando propriedades de Recuperabilidade e CO é mais significativo do que ser um subconjunto de 2PL, que por si só em sua forma geral, além de compreender um mecanismo de serialização simples (no entanto, serializabilidade também está implícita em CO), em não conhecido para fornecer SS2PL com quaisquer outras qualidades significativas. 2PL em sua forma geral, bem como quando combinado com Strictness, ou seja, Strict 2PL (S2PL), não são usados ​​na prática. O popular SS2PL não requer a marcação de "fim da fase 1" como 2PL e S2PL e, portanto, é mais simples de implementar. Além disso, ao contrário do 2PL geral, o SS2PL fornece, conforme mencionado acima, as propriedades úteis de ordenação de Restrição e Compromisso .

Existem muitas variantes de SS2PL que usam vários tipos de bloqueio com várias semânticas em diferentes situações, incluindo casos de alteração do tipo de bloqueio durante uma transação. Notáveis ​​são as variantes que usam bloqueio de granularidade múltipla .

Comentários:

  1. SS2PL vs. S2PL: Ambos fornecem serializabilidade e rigidez. Uma vez que S2PL é uma superclasse de SS2PL, pode, em princípio, fornecer mais concorrência. No entanto, nenhuma vantagem de simultaneidade é notada na prática (exatamente o mesmo bloqueio existe para ambos, com praticamente não muito mais liberação de bloqueio para S2PL), e a sobrecarga de lidar com um mecanismo de fim de fase 1 em S2PL, separado do final da transação , não se justifica. Além disso, embora o SS2PL forneça pedidos de compromisso , o S2PL não. Isso explica a preferência de SS2PL sobre S2PL.
  2. Especialmente antes de 1990, mas também depois, em muitos artigos e livros, por exemplo, (Bernstein et al. 1987, p. 59), o termo "Strict 2PL" (S2PL) foi frequentemente definido pelo protocolo de bloqueio "Liberar apenas todos os bloqueios após o término da transação ", que é o protocolo do SS2PL. Assim, "Strict 2PL" não poderia ser o nome da interseção de Strictness e 2PL, que é maior do que a classe gerada pelo protocolo SS2PL. Isso causou confusão. Com uma definição explícita de S2PL como a interseção de Strictness e 2PL, um novo nome para SS2PL e uma distinção explícita entre as classes S2PL e SS2PL, os artigos (Breitbart et al. 1991) e (Raz 1992) pretendem esclarecer o confusão: o primeiro usando o nome de "rigor" e o segundo "SS2PL".
  3. Existe uma propriedade mais geral do que SS2PL (uma superclasse de programação), ordenação de compromisso estrito (CO estrito ou SCO), que também fornece serializabilidade, rigidez e CO, e tem sobrecarga de bloqueio semelhante. Ao contrário de SS2PL, SCO não bloqueia após um conflito de leitura e gravação (um bloqueio de leitura não bloqueia a aquisição de um bloqueio de gravação; SCO e SS2PL têm o mesmo comportamento para conflitos de gravação-leitura e gravação-gravação) ao custo de um possível atraso confirmar, e sobre esse tipo de conflito SCO tem tempo médio de conclusão de transação mais curto e melhor desempenho do que SS2PL. Enquanto SS2PL obedece à tabela de compatibilidade de bloqueio acima, SCO tem a seguinte tabela:
Compatibilidade de bloqueio para SCO
Tipo de bloqueio read-lock bloqueio de escrita
read-lock X
bloqueio de escrita X X
Observe que embora o SCO libere todos os bloqueios no final da transação e esteja em conformidade com as regras de bloqueio 2PL, o SCO não é um subconjunto de 2PL devido à sua tabela de compatibilidade de bloqueio diferente. O SCO permite conflitos de leitura e gravação materializados entre duas transações em suas fases 1, o que 2PL não permite na fase 1 (consulte sobre conflitos materializados em Serializabilidade ). Por outro lado, 2PL permite outros tipos de conflito materializado na fase 2 que a SCO não permite de forma alguma. Juntos, isso implica que as classes de programação 2PL e SCO são incomparáveis ​​(ou seja, nenhuma classe contém a outra classe).

Resumo - Relações entre classes

Programar contenção de classes: Uma seta da classe A para a classe B indica que a classe A contém estritamente B; a falta de um caminho direcionado entre as classes significa que as classes são incomparáveis. Uma propriedade é inerentemente bloqueadora , se puder ser aplicada apenas bloqueando as operações de acesso a dados da transação até que certos eventos ocorram em outras transações. ( Raz 1992 )

Entre quaisquer duas classes de programação (definidas pelas respectivas propriedades de suas programações) que têm programações comuns, uma contém a outra ( contém estritamente se não forem iguais) ou são incomparáveis . Os relacionamentos de contenção entre as classes 2PL e outras classes principais da programação estão resumidos no diagrama a seguir. 2PL e suas subclasses são inerentemente bloqueadoras , o que significa que não existem implementações otimistas para eles (e sempre que "2PL otimista" é mencionado, ele se refere a um mecanismo diferente com uma classe que inclui também agendamentos que não estão na classe 2PL).

Deadlocks em 2PL

Os bloqueios bloqueiam as operações de acesso a dados. O bloqueio mútuo entre as transações resulta em um conflito , em que a execução dessas transações é paralisada e nenhuma conclusão pode ser alcançada. Assim, os impasses precisam ser resolvidos para concluir as execuções dessas transações e liberar os recursos de computação relacionados. Um deadlock é um reflexo de um ciclo potencial no gráfico de precedência , que ocorreria sem o bloqueio. Um impasse é resolvido abortando uma transação envolvida com tal ciclo potencial e interrompendo o ciclo. Muitas vezes, é detectado usando um gráfico de espera (um gráfico de conflitos bloqueados por bloqueios de serem materializados; conflitos não materializados no banco de dados devido a operações bloqueadas não são refletidos no gráfico de precedência e não afetam a serializabilidade ), que indica qual transação está "aguardando" a liberação do bloqueio por meio da transação, e um ciclo significa um conflito. Abortar uma transação por ciclo é suficiente para interromper o ciclo. Se uma transação foi abortada devido à resolução de conflito, caberá ao aplicativo decidir o que fazer a seguir. Normalmente, um aplicativo irá reiniciar a transação desde o início, mas pode atrasar essa ação para dar às outras transações tempo suficiente para terminar a fim de evitar causar outro conflito.

Em um ambiente distribuído, um protocolo de confirmação atômica , normalmente o protocolo Two-phase commit (2PC), é usado para atomicidade . Quando os dados recuperáveis ​​(dados sob controle de transação) particionados entre participantes 2PC (ou seja, cada objeto de dados é controlado por um único participante 2PC), os deadlocks distribuídos (globais), deadlocks envolvendo dois ou mais participantes em 2PC, são resolvidos automaticamente da seguinte forma:

Quando SS2PL é efetivamente usado em um ambiente distribuído, os deadlocks globais devido ao bloqueio geram deadlocks de votação em 2PC e são resolvidos automaticamente por 2PC (consulte Ordenação de compromisso (CO), em Caracterização exata de deadlocks de votação por ciclos globais ; Sem referência exceto os artigos do CO que notam isso). Para o caso geral de 2PL, deadlocks globais são resolvidos de forma semelhante automaticamente pelo protocolo de ponto de sincronização do final da fase 1 em uma transação distribuída (o ponto de sincronização é alcançado por "votação" (notificando o final da fase 1 local), e sendo propagado para o participantes em uma transação distribuída da mesma forma que um ponto de decisão no compromisso atômico; em analogia ao ponto de decisão em CO, uma operação conflitante em 2PL não pode acontecer antes do ponto de sincronização final da fase 1, com o mesmo impasse de votação resultante no caso de um impasse global de acesso a dados; o impasse de votação (que também é um impasse global baseado em bloqueio) é resolvido automaticamente pelo protocolo abortando alguma transação envolvida, com um voto ausente, normalmente usando um tempo limite ).

Comentário :

Quando os dados são particionados entre os participantes do protocolo de comprometimento atômico (por exemplo, 2PC), a resolução de deadlock global automática foi negligenciada na literatura de pesquisa de banco de dados, embora os deadlocks em tais sistemas tenham sido uma área de pesquisa bastante intensa:
  • Para CO e seu caso especial SS2PL, a resolução automática pelo protocolo de confirmação atômica foi observada apenas nos artigos de CO. No entanto, foi observado na prática que em muitos casos os deadlocks globais são detectados com pouca frequência pelos mecanismos de resolução dedicados, menos do que o esperado ("Por que vemos tão poucos deadlocks globais?"). A razão é provavelmente os deadlocks que são resolvidos automaticamente e, portanto, não manipulados e não contados pelos mecanismos;
  • Para 2PL em geral, a resolução automática pelo protocolo de ponto de sincronização de fim de fase um (obrigatório) (que tem o mesmo mecanismo de votação do protocolo de confirmação atômica e o mesmo tratamento de voto ausente no impasse de votação, resultando em resolução de impasse global) tem não foi mencionado até hoje (2009). Praticamente, apenas o caso especial SS2PL é usado, onde nenhuma sincronização de fim de fase um é necessária além do protocolo de confirmação atômica.
Em um ambiente distribuído onde os dados recuperáveis ​​não são particionados entre os participantes do protocolo de confirmação atômica, nenhuma resolução automática existe e os conflitos distribuídos precisam ser resolvidos por técnicas dedicadas.

Veja também

Referências