Protocolo de confirmação de duas fases - Two-phase commit protocol

No processamento de transações , bancos de dados e rede de computadores , o protocolo two-phase commit ( 2PC ) é um tipo de protocolo de confirmação atômica (ACP). É um algoritmo distribuído que coordena todos os processos que participam de uma transação atômica distribuída para confirmar ou abortar (reverter) a transação (é um tipo especializado de protocolo de consenso ). O protocolo atinge seu objetivo mesmo em muitos casos de falha temporária do sistema (envolvendo falhas de processo, nó de rede, comunicação, etc.) e, portanto, é amplamente utilizado. No entanto, não é resiliente a todas as configurações de falha possíveis e, em casos raros, a intervenção manual é necessária para remediar um resultado. Para acomodar a recuperação de uma falha (automática na maioria dos casos), os participantes do protocolo usam o registro dos estados do protocolo. Os registros de log, que normalmente são lentos para gerar, mas sobrevivem a falhas, são usados pelos procedimentos de recuperação do protocolo . Existem muitas variantes de protocolo que diferem principalmente em estratégias de registro e mecanismos de recuperação. Embora normalmente não seja usado com frequência, os procedimentos de recuperação compõem uma parte substancial do protocolo, devido a muitos cenários de falha possíveis a serem considerados e suportados pelo protocolo.

Em uma "execução normal" de qualquer transação distribuída única (ou seja, quando nenhuma falha ocorre, que normalmente é a situação mais frequente), o protocolo consiste em duas fases:

A fase de solicitação de confirmação (ou fase de votação), na qual um processo coordenador tenta preparar todos os processos participantes da transação (participantes nomeados, coortes ou trabalhadores) para tomar as medidas necessárias para confirmar ou abortar a transação e votar, seja "Sim": confirmar (se a execução da parte local do participante da transação foi finalizada corretamente) ou "Não": abortar (se um problema foi detectado com a parte local), e
A fase de confirmação, na qual, com base na votação dos participantes, o coordenador decide se compromete (apenas se todos votaram "Sim") ou aborta a transação (caso contrário), e notifica o resultado a todos os participantes. Os participantes então seguem com as ações necessárias (confirmar ou abortar) com seus recursos transacionais locais (também chamados de recursos recuperáveis; por exemplo, dados do banco de dados) e suas respectivas partes na outra saída da transação (se aplicável).

O protocolo two-phase commit (2PC) não deve ser confundido com o protocolo two-phase locking (2PL), um protocolo de controle de concorrência .

Premissas

O protocolo funciona da seguinte maneira: um nó é um coordenador designado, que é o site mestre, e o resto dos nós na rede são designados os participantes. O protocolo pressupõe que haja armazenamento estável em cada nó com um log write-ahead , que nenhum nó trava para sempre, que os dados no log write-ahead nunca são perdidos ou corrompidos em uma falha e que quaisquer dois nós podem se comunicar com uns aos outros. A última suposição não é muito restritiva, já que a comunicação de rede pode ser normalmente redirecionada. As duas primeiras suposições são muito mais fortes; se um nó for totalmente destruído, os dados podem ser perdidos.

O protocolo é iniciado pelo coordenador após a última etapa da transação ter sido atingida. Os participantes então respondem com uma mensagem de acordo ou uma mensagem de cancelamento, dependendo se a transação foi processada com sucesso no participante.

Algoritmo básico

Fase de solicitação (ou votação) de confirmação

O coordenador envia uma consulta para enviar mensagem a todos os participantes e espera até receber uma resposta de todos os participantes.
Os participantes executam a transação até o ponto em que serão solicitados a confirmar. Cada um deles grava uma entrada em seu log de desfazer e uma entrada em seu log de redo .
Cada participante responde com uma mensagem de concordância (o participante vota Sim para confirmar), se as ações do participante foram bem-sucedidas, ou uma mensagem de aborto (o participante vota Não, não para confirmar), se o participante experimentar uma falha que tornará impossível cometer.

Fase de confirmação (ou conclusão)

Sucesso

Se o coordenador recebeu uma mensagem de acordo de todos os participantes durante a fase de solicitação de confirmação:

O coordenador envia uma mensagem de confirmação para todos os participantes.
Cada participante conclui a operação e libera todos os bloqueios e recursos mantidos durante a transação.
Cada participante envia um agradecimento ao coordenador.
O coordenador conclui a transação quando todas as confirmações foram recebidas.

Fracasso

Se algum participante votar Não durante a fase de solicitação de confirmação (ou o tempo limite do coordenador expirar):

O coordenador envia uma mensagem de rollback para todos os participantes.
Cada participante desfaz a transação usando o log de desfazer e libera os recursos e bloqueios mantidos durante a transação.
Cada participante envia um agradecimento ao coordenador.
O coordenador desfaz a transação quando todas as confirmações foram recebidas.

Fluxo de mensagens

Coordinator                                          Participant
                             QUERY TO COMMIT
                 -------------------------------->
                             VOTE YES/NO             prepare*/abort*
                 <-------------------------------
commit*/abort*               COMMIT/ROLLBACK
                 -------------------------------->
                             ACKNOWLEDGMENT          commit*/abort*
                 <--------------------------------  
end

Um * próximo ao tipo de registro significa que o registro é forçado para armazenamento estável.

Desvantagens

A maior desvantagem do protocolo two-phase commit é que ele é um protocolo de bloqueio. Se o coordenador falhar permanentemente, alguns participantes nunca resolverão suas transações: Depois que um participante enviar uma mensagem de acordo ao coordenador, ela será bloqueada até que um commit ou rollback seja recebido.

Implementando o protocolo two-phase commit

Arquitetura comum

Em muitos casos, o protocolo 2PC é distribuído em uma rede de computadores. É facilmente distribuído pela implementação de vários componentes 2PC dedicados semelhantes entre si, normalmente chamados de gerenciadores de transações (TMs; também chamados de agentes 2PC ou monitores de processamento de transações), que realizam a execução do protocolo para cada transação (por exemplo, The Open Group ' s X / Abrir XA ). Os bancos de dados envolvidos com uma transação distribuída, os participantes, tanto o coordenador quanto os participantes, se registram para fechar TMs (normalmente residindo nos respectivos nós da rede que os participantes) para encerrar essa transação usando 2PC. Cada transação distribuída possui um conjunto ad hoc de TMs, as TMs nas quais os participantes da transação se registram. Um líder, o coordenador TM, existe para cada transação para coordenar 2PC para ela, normalmente o TM do banco de dados do coordenador. No entanto, a função de coordenador pode ser transferida para outro TM por motivos de desempenho ou confiabilidade. Em vez de trocar mensagens 2PC entre si, os participantes trocam as mensagens com seus respectivos TMs. As TMs relevantes comunicam-se entre si para executar o esquema de protocolo 2PC acima, "representando" os respectivos participantes, para encerrar aquela transação. Com essa arquitetura, o protocolo é totalmente distribuído (não precisa de nenhum componente de processamento central ou estrutura de dados) e aumenta com o número de nós da rede (tamanho da rede) de maneira eficaz.

Essa arquitetura comum também é eficaz para a distribuição de outros protocolos de comprometimento atômico além de 2PC, uma vez que todos esses protocolos usam o mesmo mecanismo de votação e propagação de resultados para os participantes do protocolo.

Otimizações de protocolo

A pesquisa de banco de dados foi feita sobre maneiras de obter a maioria dos benefícios do protocolo two-phase commit, reduzindo custos por meio de otimizações de protocolo e operações de protocolo, economizando em certas suposições de comportamento do sistema.

Abortamento presumido e confirmação presumida

Abortamento presumido ou confirmação presumida são essas otimizações comuns. Uma suposição sobre o resultado das transações, seja consolidar ou anular, pode salvar mensagens e operações de registro pelos participantes durante a execução do protocolo 2PC. Por exemplo, quando o procedimento de recuperação é abortado, se durante a recuperação do sistema da falha nenhuma evidência registrada para confirmação de alguma transação for encontrada, então ele assume que a transação foi abortada e age de acordo. Isso significa que não importa se os abortos são registrados, e esse registro pode ser salvo sob esta suposição. Normalmente, uma penalidade de operações adicionais é paga durante a recuperação de uma falha, dependendo do tipo de otimização. Assim, a melhor variante de otimização, se houver, é escolhida de acordo com as estatísticas de falha e resultado da transação.

Protocolo Tree two-phase commit

O protocolo Tree 2PC (também denominado Nested 2PC ou Recursive 2PC) é uma variante comum do 2PC em uma rede de computadores , que utiliza melhor a infraestrutura de comunicação subjacente. Os participantes em uma transação distribuída são normalmente chamados em uma ordem que define uma estrutura em árvore, a árvore de chamada, onde os participantes são os nós e as bordas são as chamadas (links de comunicação). A mesma árvore é comumente utilizada para completar a transação por um protocolo 2PC, mas também outra árvore de comunicação pode ser utilizada para isso, em princípio. Em uma árvore 2PC o coordenador é considerado a raiz ("topo") de uma árvore de comunicação (árvore invertida), enquanto os participantes são os outros nós. O coordenador pode ser o nó que originou a transação (chamado recursivamente (transitivamente) dos outros participantes), mas também outro nó na mesma árvore pode assumir a função de coordenador. As mensagens 2PC do coordenador são propagadas "para baixo" na árvore, enquanto as mensagens para o coordenador são "coletadas" por um participante de todos os participantes abaixo dele, antes de enviar a mensagem apropriada "para cima" na árvore (exceto uma mensagem de aborto, que é propagado "para cima" imediatamente após recebê-lo ou se o participante atual iniciar o aborto).

O protocolo Dynamic two-phase commit (Dynamic two-phase commit, D2PC) é uma variante do Tree 2PC sem coordenador predeterminado. Inclui várias otimizações que foram propostas anteriormente. Mensagens de acordo (votos sim) começam a se propagar de todas as folhas, cada folha ao completar suas tarefas em nome da transação (ficando pronta). Um nó intermediário (não folha) envia pronto quando uma mensagem de acordo para o último (único) nó vizinho do qual a mensagem de acordo ainda não foi recebida. O coordenador é determinado dinamicamente por mensagens de acordo de corrida ao longo da árvore de transação, no local onde eles colidem. Eles colidem em um nó da árvore de transação, para ser o coordenador, ou na borda de uma árvore. No último caso, um dos dois nós da aresta é eleito como coordenador (qualquer nó). D2PC é o tempo ideal (entre todas as instâncias de uma árvore de transação específica e qualquer implementação de protocolo Tree 2PC específica; todas as instâncias têm a mesma árvore; cada instância tem um nó diferente como coordenador): Ao escolher um coordenador ideal, o D2PC confirma ambos os coordenadores e cada participante no tempo mínimo possível, permitindo a liberação o mais precoce possível dos recursos bloqueados em cada participante da transação (nó da árvore).

Languages

In other projects