Melhor resposta
Este artigo fornece uma explicação e prova surpreendentemente claras: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Tentarei fornecer um resumo claro aqui:
O objetivo do O algoritmo Paxos é para um certo número de pares chegarem a um acordo sobre um valor. O Paxos garante que se um par acreditar que algum valor foi acordado pela maioria, a maioria irá nunca concorda com um valor diferente. O protocolo é projetado para que qualquer acordo deve ir através da maioria dos nós. Quaisquer tentativas futuras de acordo, se bem-sucedidas, também devem passar por pelo menos um desses nós. Assim: Qualquer nó que propõe após uma decisão ter sido alcançada deve comunicar-se com um nó na maioria. O protocolo garante que ele aprenderá o ag reed sobre o valor dessa maioria.
Veja como funciona:
Suponha que temos 3 nós, A, B e C. A gostaria de propor o valor “Foo.”
O algoritmo opera em 3 fases. Em cada fase, a afirmação da maioria dos nós deve ser alcançada.
Primeiro, temos a fase de preparação. A envia uma solicitação de preparação para A, B e C. Paxos depende de números de sequência para alcançar suas garantias. A solicitação de preparação pede a um nó que prometa: “Nunca aceitarei nenhuma proposta com um número de sequência menor que o da solicitação de preparação.” Os nós respondem com qualquer valor com o qual concordaram anteriormente (se houver). (E isso é extremamente importante): O Nó A deve propor o valor que recebe com o maior número de sequência. Esta ação fornece a garantia de que os valores previamente acordados serão preservados.
A seguir, temos a fase de aceitação. A envia uma solicitação de aceitação para A, B e C. A solicitação de aceitação afirma: ” Você aceita foo? ” Se o número de sequência que o acompanha não estiver abaixo do que o nó havia prometido anteriormente ou a solicitação que o nó aceitou anteriormente, ele aceitará o novo valor e número de sequência.
Se o nó A receber aceitações de a maioria dos nós, o valor é decidido. Esta rodada de Paxos nunca concordará com outro valor.
A terceira fase não é estritamente necessária, mas é crucial otimização em qualquer implementação Paxos produtiva. Depois que A recebe a maioria de aceitações, ele envia decidido mensagens para A, B e C. Essas mensagens permitem que todos os pares saibam que um valor foi escolhido e aceleram o final do processo de decisão.
Sem essa mensagem, os outros pares teriam que tentar propor um valor para saber do acordo. Na fase de preparação, eles aprenderiam sobre o valor previamente acordado. Uma vez que o acordo fosse levado à conclusão, o nó reconheceria o acordo.
Eu encostei algumas questões-chave aqui:
- Todos os números de sequência devem ser monotonicamente crescentes e exclusivos por nó . Isso quer dizer que A e B não podem enviar uma mensagem com o número de seqüência k. Todas as mensagens enviadas no protocolo incluem números de sequência. Um nó deve rastrear a solicitação de aceitação mais alta que viu, bem como o valor mais alto que prometeu na fase de preparação.
- Condições de falha. É bem possível que uma rodada de Paxos falhe. Em caso de falha, um nó simplesmente tenta propor novamente com um número de sequência maior.
- Condições de finalização. A versão do Paxos que descrevi não necessariamente termina. Alguns ajustes são necessários para uma prova formal de rescisão.
Resposta
Visto que o Paxos atinge o consenso, ele também pode ser usado para replicar gravações em um banco de dados distribuído conforme ele pode garantir uma ordem consistente de eventos entre todos os nós de um grupo. Chubby by Google usa Paxos para veicular arquivos fortemente consistentes. É daí que vem a confusão. Qual é então a relação entre a sincronia da visão e os paxos se ambos podem ser usados para replicação?
Pouca história: Lamport introduziu o conceito de replicação de máquina de estado no início dos anos 80. A replicação da máquina de estado significa que um sistema entrega eventos na mesma ordem para todos os nós e eles são processados deterministicamente garantindo estados consistentes em todos os nós do grupo. No entanto, na época em que esse conceito foi introduzido, ele envolvia todos os tipos de suposições, incluindo a rede ser síncrona.Portanto, a replicação da máquina de estado permaneceu apenas uma ferramenta teórica sem uso prático. A sincronia de visão foi introduzida neste ponto e visava alcançar consistência ao não fazer tais suposições. A meta era ter um sistema prático que oferecesse essas garantias.
A publicação do Paxos aconteceu enquanto o trabalho na sincronia das visões estava em andamento. O Paxos poderia atingir a replicação da máquina de estado, pois as réplicas agora podiam concordar com a ordem de execução das solicitações do cliente usando esse algoritmo de consenso. Paxos não fez suposições de rede síncrona ou falhas. Paxos também forneceu um protocolo de associação de grupo. As diferenças que agora permaneciam entre a sincronia de visão e o Paxos estavam apenas na forma como as abstrações eram formuladas. Ambos fornecem associação dinâmica e tratam as falhas de maneira semelhante. As diferenças estão realmente apenas no modelo. Algumas diferenças que podem ser destacadas são:
- O Virtual Synchrony tem um protocolo de associação de grupo simples em comparação com o Paxos. O Virtual Synchrony executa a associação ao grupo como um serviço separado.
- O Paxos pode progredir em certos casos de partição em que a sincronização virtual bloqueia.
- O Virtual Synchrony é mais rápido do que o Paxos contemporâneo.
Ambos os sistemas evoluíram e convergiram . Do jeito que está hoje, é muito difícil traçar quaisquer diferenças significativas entre os dois.
Lalith explica claramente o protocolo Virtual Synchrony e corretamente aponta que Paxos ou qualquer outra variante de consenso pode ser usado na sincronia de visão. O Paxos, além do consenso, oferece associação a grupos e outros recursos que a sincronização virtual já oferece. Visto que a sincronia virtual e o Paxos oferecem as mesmas garantias e foram desenvolvidos na mesma época, a especificação da sincronia virtual não usa o Paxos para consenso. O modelo de sincronia virtual, entretanto, usa o protocolo de envio totalmente ordenado (também conhecido como ABCAST) para obter transmissão atômica e outro protocolo para atualizar visualizações de grupo e estes podem ser vistos como a variante de consenso ele usa.
Pode ser interessante notar que o modelo de tempo de execução ISIS-2 combina o modelo Paxos com o modelo de sincronia Virtual, não por consenso, mas para fatorar a associação de grupo como um serviço separado no Paxos. Isso torna o Paxos mais rápido nos casos em que a associação não muda dinamicamente. Ao combinar o Virtual Synchrony e o Paxos, o ISIS2 é capaz de pular algumas etapas que o Paxos típico precisa executar. Em essência, Paxos e Virtual Synchrony são modelos diferentes para atingir a mesma funcionalidade e podem ser combinados entre si para obter variantes ou otimizações.