Gato de Schrodinger sem caixa: o problema do consenso em sistemas distribuídos

Então, imagine. Cinco gatos estão trancados na sala e, para acordar o proprietário, todos precisam concordar juntos sobre isso, porque só podem abrir a porta apoiando-se em cinco deles. Se um dos gatos é um gato de Schrodinger, e o resto dos gatos não sabe sobre sua solução, surge a pergunta: "Como eles podem fazer isso?"

Neste artigo, vou falar em uma linguagem simples sobre o componente teórico do mundo dos sistemas distribuídos e os princípios de sua operação. E também superficialmente considere a idéia principal subjacente a Paxos'a.



Quando os desenvolvedores usam infraestruturas de nuvem, vários bancos de dados, trabalham em clusters de um grande número de nós, eles têm certeza de que os dados estarão completos, seguros e sempre acessíveis. Mas onde estão as garantias?

De fato, as garantias que temos são as garantias do fornecedor. Eles são descritos na documentação aproximadamente da seguinte maneira: "Este serviço é bastante confiável, possui um SLA predeterminado, não se preocupe, tudo funcionará de maneira distribuída, conforme o esperado".

Temos a tendência de acreditar no melhor, porque tios inteligentes de grandes empresas nos garantiram que tudo ficará bem. Não nos perguntamos: por que, de fato, isso pode funcionar? Existe alguma justificativa formal para a operação correta desses sistemas?

Recentemente, fui para a escola de computação distribuída e fiquei muito inspirado por esse tópico. As aulas na escola pareciam mais aulas de análise matemática do que algo relacionado a sistemas de computador. Mas é exatamente assim que os algoritmos mais importantes que usamos todos os dias sem saber que foram provados ao mesmo tempo.

A maioria dos sistemas distribuídos modernos usa o algoritmo de consenso Paxos e suas várias modificações. O mais interessante é que a validade e, em princípio, a própria possibilidade da existência desse algoritmo podem ser comprovadas simplesmente com caneta e papel. No entanto, na prática, o algoritmo é usado em grandes sistemas que operam em um grande número de nós nas nuvens.

Introduzimos o conceito de sistemas distribuídos

Um sistema distribuído é um grupo de computadores (doravante referidos como nós) que podem trocar mensagens. Cada nó individual é uma entidade autônoma. Um nó pode processar tarefas independentemente, mas para interagir com outros nós, ele precisa enviar e receber mensagens.

Como especificamente as mensagens são implementadas, quais protocolos são usados ​​- isso não é do nosso interesse neste contexto. É importante que os nós de um sistema distribuído possam trocar dados enviando mensagens.

A definição em si não parece muito complicada, mas é necessário considerar que um sistema distribuído possui vários atributos que serão importantes para nós.

Atributos do sistema distribuído

1. Concorrência - a possibilidade de eventos simultâneos ou competitivos no sistema. Além disso, consideraremos que os eventos que ocorreram em dois nós diferentes são potencialmente competitivos, desde que não tenhamos uma ordem clara de ocorrência desses eventos. E, como regra, não temos.
2. A falta de um relógio global . Não temos uma ordem clara de eventos devido à falta de um relógio global. No mundo comum das pessoas, estamos acostumados ao fato de termos horas e horas absolutamente. Tudo muda quando se trata de sistemas distribuídos. Até relógios atômicos ultra-precisos têm um desvio, e pode haver situações em que não podemos dizer qual dos dois eventos aconteceu anteriormente. Portanto, também não podemos confiar no tempo.
3. Falha independente dos nós do sistema . Há outro problema: algo pode não ser tão simples porque nossos nós não são eternos. O disco rígido pode falhar, a máquina virtual na nuvem será reiniciada, a rede poderá piscar e as mensagens serão perdidas. Além disso, situações são possíveis quando os nós funcionam, mas ao mesmo tempo trabalham contra o sistema. A última classe de problemas até recebeu um nome separado: o problema dos generais bizantinos . O exemplo mais popular de um sistema distribuído com esse problema é o Blockchain. Hoje, porém, não consideraremos essa classe específica de problemas. Estaremos interessados ​​em situações nas quais apenas um ou mais nós podem falhar.
4. Modelos de comunicação (modelos de mensagens) entre nós . Já descobrimos que os nós se comunicam por meio de mensagens. Existem dois modelos de mensagens conhecidos: síncrono e assíncrono.

Modelos de comunicação entre nós em sistemas distribuídos

Modelo síncrono - sabemos com certeza que existe um delta de tempo conhecido finito para o qual é garantido que uma mensagem chegue de um nó para outro. Se esse tempo já passou, mas a mensagem não chegou, podemos dizer com segurança que o nó falhou. Nesse modelo, temos um tempo de espera previsível.

Modelo assíncrono - em modelos assíncronos, acreditamos que o tempo de espera é finito, mas não existe um tempo delta após o qual pode ser garantido que o nó está fora de ordem. I.e. o tempo de espera para uma mensagem do nó pode ser arbitrariamente longo. Esta é uma definição importante, e falaremos mais sobre isso.

O conceito de consenso em sistemas distribuídos

Antes de definir formalmente o conceito de consenso, vamos considerar um exemplo da situação em que precisamos, a saber, replicação de máquina de estado .

Temos algum log distribuído. Gostaríamos que fosse consistente e contenha dados idênticos em todos os nós de um sistema distribuído. Quando um dos nós descobre um novo valor que ele irá gravar no log, sua tarefa é oferecer esse valor a todos os outros nós, para que o log seja atualizado em todos os nós e o sistema alterne para um novo estado consistente. É importante que os nós concordem entre si: todos os nós concordam que o novo valor proposto está correto, todos os nós aceitam esse valor e, somente nesse caso, todos podem escrever um novo valor no log.

Em outras palavras: nenhum dos nós objetou ter informações mais relevantes e o valor proposto está incorreto. O acordo entre os nós e o acordo sobre um único valor aceito correto é consenso em um sistema distribuído. Além disso, falaremos sobre algoritmos que permitem que um sistema distribuído alcance consenso com garantia.

Mais formalmente, podemos definir um algoritmo de consenso (ou apenas um algoritmo de consenso) como alguma função que transfere um sistema distribuído do estado A para o estado B. Além disso, esse estado é aceito por todos os nós e todos os nós podem confirmá-lo. Como se vê, essa tarefa não é tão trivial quanto parece à primeira vista.

Propriedades do algoritmo de consenso

O algoritmo de consenso deve ter três propriedades para que o sistema continue a existir e tenha algum tipo de progresso na transição de estado para estado:

1. Contrato - todos os nós que funcionam corretamente devem ter o mesmo valor (nos artigos, essa propriedade também é encontrada como uma propriedade de segurança). Todos os nós que estão funcionando agora (não estão fora de ordem e não perderam o contato com o resto) devem chegar a um acordo e assumir algum tipo de significado geral final.
   
   É importante entender aqui que os nós no sistema distribuído que estamos considerando desejam concordar. Ou seja, agora estamos falando de sistemas que podem falhar (por exemplo, falhar em um nó), mas esse sistema definitivamente não possui nós que intencionalmente funcionem contra os outros (a tarefa dos generais bizantinos). Devido a essa propriedade, o sistema permanece consistente.
2. Integridade - se todos os nós que estiverem funcionando corretamente oferecerem o mesmo valor de v , cada nó que estiver funcionando corretamente deverá aceitar esse valor de v .
3. Término - todos os nós que estão funcionando corretamente eventualmente terão algum valor (propriedade liveness), o que permite que o algoritmo tenha progresso no sistema. Cada nó individual que funciona corretamente deve, mais cedo ou mais tarde, aceitar o valor final e confirmar o seguinte: "Para mim, esse valor é verdadeiro, concordo com todo o sistema".

Exemplo de algoritmo de consenso

Até agora, as propriedades do algoritmo podem não estar totalmente claras. Portanto, ilustramos com um exemplo as etapas pelas quais o algoritmo de consenso mais simples passa em um sistema com um modelo de mensagens síncronas, no qual todos os nós funcionam como esperado, as mensagens não são perdidas e nada é interrompido (isso realmente acontece?).

1. Tudo começa com uma proposta de casamento (Propor). Suponha que um cliente conectado a um nó chamado “Nó 1” e iniciou uma transação, passando um novo valor para o nó - O. A partir de agora, “Nó 1” chamaremos de proponente . Como proponente, o “Nó 1” agora deve notificar todo o sistema que possui dados atualizados e enviar mensagens para todos os outros nós: “Veja! Eu recebi o valor "O" e quero anotá-lo! Por favor, confirme que você também escreverá "O" em seu log. "
   
   
2. A próxima etapa é votar no valor proposto (votação). Para que serve? Pode acontecer que outros nós recebam informações mais recentes e tenham dados na mesma transação.
   
   
   
   Quando o nó "Nó 1" envia sua própria mensagem, os nós restantes verificam os dados para esse evento em seus logs. Se não houver contradições, os nós anunciam: “Sim, não tenho outros dados sobre este evento. O valor "O" é a informação mais recente que merecemos. "
   
   Em qualquer outro caso, os nós podem responder "Nó 1": "Ouça! Eu tenho dados mais recentes sobre esta transação. Não "Oh", mas algo melhor. "
   
   Na fase da votação, os nós tomam uma decisão: ou todos aceitam o mesmo valor ou um deles vota contra, indicando que ele possui dados mais recentes.
3. Se a rodada de votação foi bem-sucedida e todos foram a favor, o sistema passa para uma nova etapa - aceitação do valor (Aceitar). "Nó 1" coleta todas as respostas de outros nós e relatórios: "Todos concordaram com o valor" O "! Agora declaro oficialmente que “O” é o nosso novo significado, o mesmo para todos! Escreva-se em um livreto, não esqueça. Escreva no seu registro! ”
   
   
4. Os nós restantes enviam uma confirmação (Aceito) de que anotaram o valor "O", não conseguiram fazer nada de novo durante esse tempo (uma espécie de confirmação em duas fases). Após esse evento importante, acreditamos que a transação distribuída foi concluída.
   

Assim, o algoritmo de consenso no caso simples consiste em quatro etapas: propor, votar, aceitar, confirmar a aceitação.

Se em algum momento não conseguimos chegar a um acordo, o algoritmo é reiniciado, levando em consideração as informações fornecidas pelos nós que se recusaram a confirmar o valor proposto.

Algoritmo de consenso em um sistema assíncrono

Antes disso, tudo era tranquilo, porque se tratava de um modelo de mensagens síncronas. Mas sabemos que no mundo moderno estamos acostumados a fazer tudo de forma assíncrona. Como um algoritmo semelhante funciona em um sistema com um modelo de mensagens assíncronas, em que acreditamos que o tempo de espera por uma resposta de um nó pode ser arbitrariamente longo (a propósito, a falha de um nó também pode ser considerada como um exemplo quando um nó pode responder por um tempo arbitrariamente longo) )

Agora que sabemos como o algoritmo de consenso basicamente funciona, a pergunta é para os leitores curiosos que chegaram a esse ponto: quantos nós em um sistema de N nós com um modelo de mensagem assíncrono podem falhar para que o sistema ainda possa chegar a um consenso?

Agora estamos falando de teoria, de matemática. O que significa "consenso não pode ser alcançado", traduzindo de uma linguagem matemática para a nossa - engenharia? Isso significa que "nem sempre pode ser alcançado", ou seja, há um caso em que o consenso não é possível. E qual é esse caso?

Isso é apenas uma violação da propriedade liveness descrita acima. Não temos um acordo geral e o sistema não pode progredir (não pode ser concluído em um tempo finito) no caso em que não temos uma resposta de todos os nós. Como em um sistema assíncrono, não temos um tempo de resposta previsível e não podemos saber se o nó está inoperante ou leva apenas um longo tempo para responder.

Mas, na prática, podemos encontrar uma solução. Deixe nosso algoritmo funcionar por um longo tempo em caso de falhas (ele pode funcionar infinitamente). Mas na maioria das situações, quando a maioria dos nós funcionar corretamente, teremos progresso no sistema.

Na prática, estamos lidando com modelos de comunicação parcialmente síncronos. Sincronismo parcial é entendido da seguinte forma: no caso geral, temos um modelo assíncrono, mas formalmente introduzimos um certo conceito de "tempo de estabilização global" de um determinado momento no tempo.

Esse momento pode não durar o tempo que você quiser, mas um dia deve chegar. Um alarme virtual tocará e, a partir de agora, podemos prever o tempo delta para o qual as mensagens chegarão. A partir desse momento, o sistema passa de assíncrono para síncrono. Na prática, estamos lidando exatamente com esses sistemas.

Algoritmo de Paxos resolve problemas de consenso

Paxos é uma família de algoritmos que resolvem o problema de consenso para sistemas parcialmente síncronos, desde que alguns nós possam falhar. O autor de Paxos é Leslie Lamport . Ele propôs uma prova formal da existência e correção do algoritmo em 1989.

Mas a prova não foi de forma alguma trivial. A primeira publicação foi lançada apenas em 1998 (33 páginas) com uma descrição do algoritmo. Como se viu, era extremamente difícil de entender e, em 2001, foi publicada uma explicação para o artigo, com 14 páginas. Os volumes de publicações são apresentados para mostrar que, de fato, o problema do consenso não é nada simples e tais algoritmos estão sujeitos ao enorme trabalho das pessoas mais inteligentes.

É interessante que o próprio Leslie Lamport em sua palestra tenha observado que no segundo artigo-explicação há uma afirmação, uma linha (não especificou qual), que pode ser interpretada de maneira diferente. E por isso, um grande número de implementações modernas do Paxos não funcionam corretamente.

Uma análise detalhada do trabalho de Paxos desenhará mais de um artigo, por isso tentarei transmitir brevemente a idéia principal do algoritmo. Nos links no final do meu artigo, você encontrará materiais para imersão adicional neste tópico.

Funções em Paxos

Paxos tem um conceito de papéis. Vamos considerar três principais (há modificações com funções adicionais):

1. Proponentes (os termos também podem ser usados: líderes ou coordenadores) . Esses são os sujeitos que aprendem sobre algum novo significado do usuário e assumem o papel de líder. Sua tarefa é lançar uma rodada de propostas com um novo significado e coordenar outras ações dos nós. Além disso, Paxos permite a presença de vários líderes em determinadas situações.
2. Aceitadores (Eleitores) . Estes são os nós que votam na adoção ou rejeição de um valor específico. O papel deles é muito importante, porque a decisão depende deles: em que estado o sistema irá (ou não) após o próximo estágio do algoritmo de consenso.
3. Alunos . Nós que simplesmente aceitam e registram o novo valor aceito quando o estado do sistema foi alterado. Eles não tomam decisões, simplesmente recebem dados e podem entregá-los ao usuário final.

Um nó pode combinar várias funções em diferentes situações.

Quorum concept

Assumimos que temos um sistema de N nós. E a partir deles, um máximo de nós F pode falhar. Se os nós F falharem, devemos ter pelo menos 2F + 1 nós aceitadores no cluster.

Isso é necessário para que sempre, mesmo na pior situação, tenhamos uma maioria de nós "boa" e funcionando corretamente. Ou seja, F + 1 nós "bons" que concordaram e o valor final será aceito. Caso contrário, pode haver uma situação em que diferentes grupos locais terão significados diferentes e não serão capazes de concordar entre si. Portanto, precisamos de uma maioria absoluta para ganhar a votação.

A ideia geral do algoritmo de consenso de Paxos

O algoritmo Paxos envolve duas grandes fases, que por sua vez são divididas em duas etapas cada:

1. Fase 1a: Prepare . No estágio de preparação, o líder (proponente) informa todos os nós: “Estamos iniciando um novo estágio de votação. Temos uma nova rodada. O número desta rodada é n. Agora vamos começar a votar. Por enquanto, ele simplesmente informa o início de um novo ciclo, mas não informa um novo valor. A tarefa deste estágio é iniciar uma nova rodada e informar a todos seu número único. O número da rodada é importante, deve ser um valor maior que todos os números de votação anteriores de todos os líderes anteriores. Como é justamente graças ao número da rodada que outros nós no sistema entenderão o quão recente o líder possui dados. Outros nós provavelmente já têm resultados de votação em rodadas muito posteriores e simplesmente dirão ao líder que ele está atrasado.
2. Fase 1b: Promessa . Quando os nós aceitadores receberam o número do novo estágio de votação, dois resultados são possíveis:
   
   • n , , acceptor. acceptor , , n. acceptor - (.. - ), , .
   • , acceptor , .
3. Phase 2a: Accept . ( ) , , :
   
   • acceptor' , . c . x, : «Accept (n, x)», – Propose, – , .. , , .
   • acceptor' , , , , . y. : «Accept (n, y)», .
4. Phase 2b: Accepted . , -acceptor', «Accept(...)», ( , ) , - () n' > n , .
   
   , , . ! , , .

Paxos. , , , .

, Paxos — , , , Raft , .

«»:

• How Does Distributed Consensus Works? , Preethi Kasireddy, blog article on Medium
• Paxos made simple. For real , Adi Kancherla, blog article on Medium
• Decentralized Thoughts , Ittai Abraham, blog
• Synchrony, Asynchrony and Partial synchrony , Ittai Abraham, blog article

« »:

• Impossibility of Distributed Consensus with One Faulty Process (FLP impossibility) , Fischer, Lynch and Paterson, research paper, 1985
• The Part-Time Parliament , Leslie Lamport, research paper, 1998
• Paxos made simple , Leslie Lamport, research paper, 2001