Paxos em seu coração é muito simples

o algoritmo Paxos, quando apresentado em inglês simples, é muito simples. — Leslie Lamport 2001

vou tentar explicar o único Decreto Paxos de uma forma, espero, que seja fácil de entender.

até hoje, IMO, palestra de John Ousterhout sobre Paxos ainda é o melhor lá fora. O material neste post empresta fortemente da palestra do Prof. Ousterhout. Com o Acordo de John Ousterhout, usei alguns de seus slides para ajudar a explicar Paxos.

consenso

Paxos como protocolo, está tentando resolver o problema do consenso. Colocar em inglês simples, ele está tentando resolver um problema que um sistema só vai escolher um valor quando um ou mais servidores podem propor valor(S) diferente (s).O exemplo do mundo real seria algo como uma eleição. As pessoas podem votar em um presidente diferente. Mas apenas um presidente pode ser escolhido.

Paxos é projetado para lidar com fail-stop / crash (não-Bizantino) e mensagem de atraso/perda. Além disso, há um requisito de vivacidade de que algum valor proposto seja eventualmente escolhido, desde que a maioria dos servidores esteja em execução. Isso é para evitar soluções desinteressantes como nunca aceitar qualquer valor. Se você não fizer nada, não fará nada de errado. Da mesma forma, você não quer que mais de um presidente seja eleito e você quer ter um presidente, eventualmente, enquanto as pessoas estão votando.

em uma nota lateral, para ser honesto, acho que tentar usar a votação como exemplo para explicar Paxos, no documento original do Parlamento a tempo parcial é muito natural. Mas de alguma forma não funcionou muito bem. Lamport também disse em uma entrevista que é um fracasso total, o que é lamentável.

aceitador único

Screen-Shot-2018-11-13-at-11.17.43-PM
com um cluster de servidores 2F+1, o que acontece se sempre fizermos uma determinada caixa para aceitar propostas. E qualquer proposta que seja aceita por essa caixa é escolhida.

o problema dessa abordagem é que uma única caixa pode tornar o serviço indisponível. Mas o requisito diz que o serviço precisa estar em funcionamento enquanto a maioria dos servidores estiver em execução (F+1 neste caso).

observe que este é efetivamente um único modelo de replicação mestre. E é exatamente por isso que o tempo de inatividade é inevitável com a replicação mestre-escravo.

Quorum

portanto, se ter um único aceitador não funcionar, talvez devêssemos esperar até que vários servidores aceitem uma proposta antes de reivindicar um valor sendo escolhido.

quantos?

se os aceitadores forem corrigidos e for <=F, novamente, não toleramos servidores com falha F. Se os aceitadores puderem ser qualquer servidor e for <=F, em um cluster de 2F+1 servidores, podemos ter duas propostas diferentes indo para dois conjuntos de aceitadores separados, fazendo com que dois valores sejam escolhidos.

portanto, o número de aceitadores deve ser >=F+1. Como menos aceitadores, melhor, vamos apenas com F+1. E pode ser qualquer F+1 servidores no cluster.

já fizemos algum progresso! Se alguma proposta for aceita por servidores F+1, ela será escolhida.

aceitar propostas

agora vamos ver como os aceitadores devem decidir se aceitam uma proposta ou não.

aceitar apenas a primeira proposta?
Screen-Shot-2018-11-13-at-11.17.27-PM

não funcionaria, porque podemos acabar nunca tendo nenhum valor escolhido como o caso acima. Isso viola a exigência de vivacidade.

não faz sentido dizer aceitar segunda proposta ou algo assim porque você nunca sabe se alguma vez haverá uma segunda proposta.

portanto, temos que aceitar a primeira proposta, mas talvez não apenas a primeira proposta.

aceitar todas as propostas?
Screen-Shot-2018-11-13-at-11.31.11-PM
isso violaria o requisito de segurança, pois podemos acabar tendo mais de um valor escolhido.

Core

aqui vem o truque, que eu acho que é a parte mais interessante do Paxos.

uma vez escolhido um valor, propostas futuras devem propor o mesmo valor.

isso significa que um protocolo de duas fases seria necessário. Na primeira fase, os proponentes precisam descobrir se algum valor já foi escolhido. E propor na segunda fase.

se você é um veterano do sistema distribuído, você já deve ter notado uma palavra-chave na declaração anterior. E é “futuro”. Eu revisei o tempo e o pedido antes. O sistema distribuído tem tudo a ver com pedidos. “futuro” aqui implica ordenação (acontecer-antes do relacionamento). Portanto, temos que encomendar todas as propostas. Então, no exemplo abaixo, podemos rejeitar red porque sabemos que blue é escolhido e red é uma proposta antiga.

Screen-Shot-2018-11-13-at-11.39.37-PM

número de cédula

uma maneira fácil de solicitar propostas é ter um número de cédula exclusivo para cada proposta na forma de <seq_id, server_id>. Para garantir o pedido, seq_id deve ser persistido travando/reiniciando. Portanto, deve ser armazenado localmente de forma durável.

Paxos

agora estamos todos configurados para descrever o protocolo Paxos bifásico real. Vamos chamar a primeira fase a fase prepare e a segunda fase a fase accept. prepare Fase serve dois propósitos em uma viagem de ida e volta.

  1. aprender sobre qualquer valor que já está escolhido
  2. evitar aceitantes aceitar mais propostas (muito parecido com o de RESERVA passo na consolidação de Duas fases)

Screen-Shot-2018-11-13-at-11.53.52-PM
Acceptor tem a durabilidade de armazenamento de algumas coisas

  • minProposal
  • acceptedProposal
  • acceptedValue
    Observe que, em vez de “broadcast para todos os servidores”, deve ser “transmissão de pelo menos F+1 servidores”. E o proponente deve enviar a mensagem accept para o mesmo conjunto de servidores F+1 da fase de preparação.

vamos dar uma olhada em cada passo.

fase de Preparação

nesta fase, o proponente tenta obter uma promessa do aceitante de não aceitar propostas mais antigas que a dele. Ao mesmo tempo, os aceitantes informarão aos proponentes quais valores já foram aceitos até agora.

na etapa 3 e 4, um proponente mudará sua proposta para a última proposta Aceita dos aceitadores com quem conversou. Parece ser muito conservador porque você pode obter uma proposta aceita que não é escolhida e o proponente acaba desistindo de sua proposta. Mas tudo bem, já que só nos preocupamos com o consenso. Na primeira fase, é difícil para o proponente saber se um valor é escolhido ou não. Um valor aceito pode não ser escolhido. Mas um valor escolhido deve ser aceito pela maioria dos servidores! E os aceitadores rejeitam propostas mais antigas (etapa 6). Com dois invariantes, sabemos que a última proposta aceita devolvida à proposta na fase um já foi escolhida ou nenhum valor foi escolhido no momento. De qualquer forma, é seguro propor esse valor.

por que acompanhar minProposal?
pode haver duas propostas de corrida na fase de preparação, enquanto nada foi aceito ainda. Isso significa que ambos se moverão para aceitar a fase. Graças ao pedido total que temos para todas as propostas e ao requisito F+1, pelo menos um aceitante verá a proposta mais recente e rejeitará a mensagem accept da proposta perdida/antiga. O invariante aqui é que minProposal >= acceptedProposal.

Screen-Shot-2018-11-14-at-12.28.11-AM

este é provavelmente o caso mais interessante, já que o segundo proponente não viu o valor aceito anterior e um valor não foi escolhido no momento da fase de preparação. Nesse caso, ele irá em frente e enviará accept(Y) para outros servidores. Porque S3 prometeu que só aceitará propostas depois de 4.5, rejeita X. Se não acompanharmos minProposal, X será aceito por S3. Então, tanto X quanto Y teriam sido aceitos por três servidores e considerados escolhidos, o que viola o requisito de segurança.

lá você tem isso. Este é o único Decreto Paxos. Dito isto, a implementação de Paxos provou ser muito difícil.

  1. Paxos simples https://lamport.azurewebsites.net/pubs/paxos-simple.pdf ↩︎

  2. O Parlamento https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf ↩︎

  3. Paxos é feito ao vivo https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf ↩︎

Deixe uma resposta

O seu endereço de email não será publicado.