Paxos & amp; Protocolos de consenso de balsa

Paxos e Jangada são dois protocolos de consenso bem conhecidos que existem há muito tempo e permanecem vitais para a compreensão da replicação da máquina de estado em sistemas de computador distribuídos. Paxos é na verdade uma família de protocolos que dependem de um grupo de suposições diferentes, dependendo do sistema, enquanto Raft é um consenso alternativo ao Paxos projetado para ser mais compreensível.

Compreender Paxos e Raft é muito útil para aprofundar o conhecimento de como os protocolos de consenso distribuído funcionam em criptomoedas, como prova de trabalho e tolerância a falhas bizantinas práticas.

Paxos & amp; Protocolos de consenso de balsa

Antecedentes em Paxos e Jangadas

O Paxos foi inicialmente proposto em 1989 e se destacou como um método particularmente elegante de provar a segurança para consenso distribuído tolerante a falhas. Apesar de sua novidade inicial, Paxos é muitas vezes visto como difícil de entender devido às suas suposições amplas e comportamento complexo.

Raft foi desenvolvido como uma alternativa mais compreensível ao Paxos, que é essencialmente equivalente ao Paxos em desempenho e garantias de tolerância a falhas. Existem extensos recursos disponíveis tanto no Paxos quanto no Raft, e eles são estudados e usados ​​amplamente em uma variedade de aplicações e sistemas hoje.

Alguns dos usos práticos mais conhecidos do Paxos estão no banco de dados NewSQL do Google Chave inglesa e a IBM SAN Volume Controller para serviços de visualização de armazenamento.

Raft tem vários códigos abertos implementações de referência em várias linguagens, incluindo Go, Java, C ++ e Rust.

O que é Paxos?

O consenso em um sistema tolerante a falhas distribuído é concordar com um resultado entre um grupo de participantes não confiáveis. Paxos é uma família de algoritmos de consenso que fazem várias escolhas entre suposições sobre os processadores, participantes e mensagens em um determinado sistema. O protocolo garante segurança e é frequentemente empregado onde a durabilidade de grandes conjuntos de dados é necessária.

Os protocolos de consenso assíncronos não podem garantir segurança e vivacidade, portanto, todos eles vêm com suas próprias compensações inerentes. Paxos foi um dos primeiros protocolos de consenso tolerantes a falhas distribuído para garantir a segurança e as tentativas de produzir vivacidade, garantindo que um valor proposto seja selecionado pelo grupo de participantes em uma rodada de consenso.

Existem três funções no consenso Paxos, conhecidas como agentes:

  1. Proponentes
  2. Aceitantes
  3. Aprendizes

O objetivo do consenso é que um grupo de participantes chegue a um acordo sobre um único valor para cada rodada. Uma rodada de consenso começa quando um proponente envia um valor proposto a um grupo de aceitantes. Os aceitantes podem aceitar o valor proposto por um determinado proponente e, uma vez que um determinado limite seja atingido, esse valor é aprovado pela rede.

No entanto, para que o consenso funcione corretamente, a primeira condição do Paxos é:

“Os aceitantes devem aceitar o primeiro valor proposto que receberem.”

Isso leva ao problema de vários proponentes enviarem valores propostos que são aceitos pelos aceitantes, mas todos eles não aceitam nenhum valor majoritário, uma vez que estão aceitando o primeiro valor proposto. O Paxos resolve isso indexando de forma única cada valor proposto que um aceitante recebe, o que permite que ele aceite mais de uma proposta.

Um número único define cada proposta, e a rede seleciona um valor assim que um valor proposto específico é aceito pela maioria dos aceitantes, conhecido como escolhido valor. Várias propostas podem ser escolhidas, mas é necessário validar a propriedade de segurança garantindo que todas essas propostas tenham o mesmo valor. De acordo com a definição de Leslie Lamport da segunda condição exigida de Paxos que garante a segurança:

“Se uma proposta com valor v for escolhida, todas as propostas de numeração mais alta escolhidas terão valor v.”

A comunicação na rede é assíncrona, por isso é possível que alguns aceitantes não tenham recebido o valor escolhido, o que está bem desde que as condições 1 e 2 não sejam violadas.

Os proponentes empregam certas restrições como mensagens para conjuntos de aceitantes junto com os valores. Estes são chamados preparar pedidos e contém 2 solicitações principais:

  1. Prometa nunca aceitar uma proposta menor que n (n é o novo número da proposta)
  2. Responda com a proposta com o maior número menor que n que o aceitante aceitou.

De acordo com Lamport:

“Se o proponente receber as respostas solicitadas da maioria dos aceitantes, então ele pode emitir uma proposta com número n e valor v, onde v é o valor da proposta com maior numeração entre as respostas ou é qualquer valor selecionado pelo proponente se os respondentes não relataram nenhuma proposta. ”

Posteriormente, os proponentes enviam um pedido de aceitação que é confirmado pelos aceitantes. O proponente então envia uma mensagem de confirmação aos aceitantes que podem ignorar (sem comprometer a segurança) ou indicar o sucesso da confirmação do valor. Uma vez que um certo limite de aceitantes comprometeu o valor, o protocolo para essa rodada de consenso termina e externaliza o valor.

O design intrincado do Paxos é que ele pode aceitar valores quando a maioria dos nós concorda, apesar de outros nós ignorarem ou negarem um valor proposto. Isso difere das iterações anteriores de consenso que exigiam que todos os nós concordassem e estavam sujeitas ao bloqueio do protocolo devido à falha de nós únicos.

Desde que os números da proposta sejam exclusivos, Paxos pode selecionar um valor que garanta a segurança. É importante observar que um aceitante só precisa se lembrar da proposta com a numeração mais alta que aceitou. Por outro lado, um proponente sempre pode abandonar uma proposta, desde que não emita novamente uma proposta com o mesmo número exclusivo.

A divisão das funções do proponente e do aceitante no protocolo é a seguinte:

Proponente

  • Enviar proposta n aos aceitantes juntamente com a preparação do pedido, aguarde a maioria para responder.
  • Se a maioria do aceitante responder que concorda, responderá com o valor acordado. Se a maioria rejeitar, abandone e reinicie o processo.
  • O proponente posteriormente envia uma mensagem de confirmação com n e valor se a maioria aceitar.
  • Se a maioria dos aceitantes aceitar a mensagem de confirmação, a rodada do protocolo será concluída.

Aceitante

  • Receba a proposta e compare-a com a proposta de maior número já acordada.
  • E se n é maior do que aceitar a proposta, se n for menor, rejeite a proposta.
  • Aceite a mensagem de confirmação subsequente se seu valor for o mesmo de uma proposta aceita anteriormente e seu número de sequência for o maior número acordado.

As propostas podem fazer várias propostas, mas precisam seguir o algoritmo para cada proposta individualmente.

Finalmente, o papel do aprendizes é descobrir que a maioria dos aceitantes aceitou uma proposta dos proponentes. Um aluno distinto é selecionado para propagar o valor escolhido para os outros alunos na rede. Variações deste processo podem ser usadas onde todos os aceitantes informam os alunos correspondentes de suas decisões ou os aceitantes respondem a um conjunto distinto de alunos que então propagam a mensagem para o resto dos alunos.

Formalmente, o algoritmo Paxos distingue um líder (proponente) para cada rodada que é necessária para fazer progresso. Os aceitantes podem reconhecer a liderança de um proponente, o que permite que o Paxos seja usado para selecionar um líder dentro de um grupo de nós. Paxos pode travar se dois proponentes estiverem competindo pela posição de líder sem nenhum acordo sobre qual deles é o líder. É improvável que este estado de não rescisão persista, embora.

O que é jangada?

Raft foi criado como uma versão mais compreensível do Paxos com a mesma tolerância a falhas e garantias de desempenho. Raft também melhora a construção de implementações práticas de protocolos em cima dele. Devido à complexidade do Paxos, não é útil para fornecer uma base sólida para desenvolver em cima. A jangada é semelhante ao Paxos, portanto, comparar os dois requer uma breve análise de como a jangada simplifica o processo Paxos.

Raft emprega um modelo de líder e seguidor baseado na suposição de que um cluster de nós possui apenas um líder eleito. O líder gerencia a replicação do log entre os nós participantes e é substituído assim que falha ou desconecta.

Um líder também é eleito quando o algoritmo começa. Para dar à seleção do líder algum contexto, ela desempenha um papel vital no consenso e é distinguível em algoritmos específicos. Por exemplo, na Prova de Trabalho Nakamoto, a seleção do líder é realizada por meio do processo de mineração semelhante a loteria para cada rodada, que é aproximadamente a cada 10 minutos. Em Practical Byzantine Fault Tolerance (pBFT), a seleção do líder é realizada por meio de um formato de estilo round-robin.

O que é consenso de Nakamoto

Leia: O que é o Consenso de Nakamoto?

Jangada seleciona o líder por meio de um processo iniciado por um nó candidato. Se os candidatos não receberem comunicação durante uma fase conhecida como tempo limite de eleição, então eles votam em si mesmos depois de aumentar seu contador de termo e transmiti-lo para os outros nós. Os candidatos se tornam seguidores de outros candidatos que têm um número de mandatos pelo menos tão grande quanto o deles, e esse efeito cascata continua entre os nós até que um candidato receba a maioria de seguidores.

O líder controla a replicação do log entre os nós onde envia os comandos de solicitação do cliente aos seus seguidores. Se a maioria dos seguidores confirmar a replicação, a solicitação será confirmada. Os seguidores também aplicam os commits em suas máquinas locais de estado.

Raft retém a tolerância a falhas de nós sujeitos a falha ou falha de um líder, tendo um novo líder forçando seus seguidores a duplicar seus próprios logs. Quaisquer entradas que não concordem umas com as outras são excluídas, mantendo a consistência da replicação do log.

Os candidatos a líderes devem ter um registro mais atualizado do que os registros de seguidores. Se o registro de um candidato estiver menos atualizado do que um seguidor em potencial (um eleitor neste contexto), o candidato será rejeitado.

No geral, Raft desconstrói o consenso em 3 subproblemas individuais:

  1. Eleição de Líder
  2. Replicação de Log
  3. Segurança

O protocolo de consenso usa um líder forte, o que significa que o nó líder na jangada exerce influência substancial no processo, embora permaneça restrito pelos limites do protocolo. Como resultado, Raft é mais simples no design do que Paxos.

Conclusão

Paxos e Raft são protocolos de consenso importantes que são componentes centrais de um ecossistema de tolerância a falhas distribuído maior. Embora não sejam empregados diretamente em criptomoedas, os protocolos de consenso usados ​​em redes de criptomoedas derivam muitas de suas suposições características do projeto de ambos Paxos e Raft.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me