🥇O Gato de Schrödinger sem caixa: o problema do consenso em sistemas distribuídos

Vamos imaginar. Na sala, cinco gatos estão trancados, e para ir acordar o dono, eles precisam se acertar entre si, pois a porta só pode ser aberta se todos se empilharem juntos. Se um dos gatos for o gato de Schrödinger, e os outros não souberem de sua decisão, a pergunta é: "Como eles podem fazer isso?"

Neste artigo, vou explicar de forma simples a parte teórica do mundo dos sistemas distribuídos e os princípios que regem seu funcionamento. Também abordarei de maneira superficial a ideia principal que fundamenta o Paxos.

Quando os desenvolvedores utilizam infraestruturas em nuvem, diferentes bancos de dados e trabalham em clusters com muitos nós, eles têm a confiança de que os dados estarão íntegros, seguros e sempre disponíveis. Mas de onde vêm essas garantias?

Essencialmente, as garantias que temos são as garantias do fornecedor. Elas estão descritas na documentação mais ou menos assim: "Este serviço é suficientemente confiável, tem um SLA definido, não se preocupe, tudo funcionará de forma distribuída como você espera."

Tendemos a acreditar no melhor, pois os homens sábios de grandes empresas nos garantiram que tudo ficará bem. Não nos questionamos: por que isso realmente pode funcionar? Existe algum fundamento formal para a correção do funcionamento desses sistemas?

Recentemente, eu fui a uma escola de computação distribuída e fiquei muito inspirado com esse tema. As palestras na escola pareciam mais aulas de análise matemática do que algo relacionado a sistemas computacionais. Mas foi assim que, em seu tempo, os algoritmos mais importantes que usamos todos os dias foram provados, sem que nós percebêssemos.

Na maioria dos sistemas distribuídos modernos, utiliza-se o algoritmo de consenso Paxos e suas várias modificações. O mais interessante é que a justificativa e, basicamente, a própria possibilidade de existência desse algoritmo podem ser provadas simplesmente com uma caneta e papel. Ao mesmo tempo, esse algoritmo é aplicado na prática em grandes sistemas, operando em um número imenso de nós na nuvem.

Uma leve ilustração do que será discutido a seguir: o problema dos dois generais.Vamos, para começar, analisar o problema dos dois generais..

Temos dois exércitos – o ruivo e o branco. As tropas brancas estão baseadas na cidade sitiada. As tropas ruivas, lideradas pelos generais A1 e A2, estão posicionadas em dois lados da cidade. A tarefa dos ruivos é atacar a cidade branca e vencer. No entanto, o exército de cada general ruivo individualmente é menor que o exército dos brancos.

As condições de vitória para os ruivos: ambos os generais devem atacar ao mesmo tempo para ter uma vantagem numérica sobre os brancos. Para isso, os generais A1 e A2 precisam entrar em um acordo entre si. Se cada um atacar separadamente, os ruivos perderão.

Para negociar, os generais A1 e A2 podem enviar mensageiros um ao outro através do território da cidade branca. O mensageiro pode chegar com sucesso ao general aliado ou pode ser interceptado pelo inimigo. Pergunta: existe uma sequência de comunicações entre os generais ruivos (a sequência de envio de mensageiros de A1 para A2 e vice-versa de A2 para A1), na qual eles garantidamente concordam em atacar na hora X. Aqui, por garantias, entendemos que ambos os generais terão uma confirmação clara de que o aliado (o outro general) definitivamente atacará no horário designado X.

Suponha que A1 envia um mensageiro para A2 com a mensagem: “Vamos atacar hoje à meia-noite!”. O general A1 não pode atacar sem uma confirmação do general A2. Se o mensageiro de A1 chegou, então o general A2 envia uma confirmação com a mensagem: “Sim, vamos derrubar os brancos hoje.” Mas agora o general A2 não sabe se seu mensageiro chegou ou não, ele não tem garantias de que o ataque será simultâneo. Agora, o general A2 precisa novamente de uma confirmação.

Se detalharmos ainda mais a comunicação deles, descobrir-se-á o seguinte: não importa quantos ciclos de troca de mensagens ocorram, não há como garantir que ambos os generais sejam notificados de que suas mensagens foram recebidas (supondo que qualquer um dos mensageiros possa ser interceptado).

O problema dos dois generais é uma excelente ilustração de um sistema distribuído muito simples, onde há dois nós com comunicação não confiável. Significa que não temos 100% de garantia de que eles se sincronizem. Sobre problemas semelhantes, mas em uma escala maior, se falará mais adiante no artigo.

Introduzimos o conceito de sistemas distribuídos.

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

Como as mensagens são especificamente implementadas e quais protocolos são usados não nos interessam neste contexto. O importante é que os nós de um sistema distribuído podem trocar dados entre si enviando mensagens.

A própria definição não parece muito complicada, mas é preciso considerar que um sistema distribuído possui uma série de atributos que serão importantes para nós.

Atributos de sistemas distribuídos

Concorrência – a possibilidade de ocorrência de eventos simultâneos ou concorrentes no sistema. Além disso, consideraremos que eventos que ocorreram em dois nós diferentes são potencialmente concorrentes até que tenhamos uma ordem clara de ocorrência desses eventos. E, geralmente, não temos.
Ausência de relógios globais. Não temos uma ordem clara de eventos devido à ausência de relógios globais. No mundo cotidiano, estamos acostumados a ter relógios e um tempo absoluto. Tudo muda quando se trata de sistemas distribuídos. Mesmo os relógios atômicos mais precisos têm desvios, e podem ocorrer situações em que não conseguimos dizer qual dos dois eventos ocorreu primeiro. Portanto, não podemos depender do tempo.
Falhas independentes dos nós do sistema. Há outro problema: algo pode dar errado simplesmente porque nossos nós não são eternos. Um disco rígido pode falhar, uma máquina virtual na nuvem pode reiniciar, a rede pode piscar e as mensagens podem ser perdidas. Além disso, podem ocorrer situações onde os nós estão funcionando, mas trabalham contra o sistema. Essa última classe de problemas até recebeu um nome especial: o problema dos Generais Bizantinos. O exemplo mais popular de um sistema distribuído com esse problema é o Blockchain. Mas hoje não vamos considerar essa classe específica de problemas. Estaremos interessados em situações em que apenas um ou mais nós podem falhar.
Modelos de comunicação (modelos de intercâmbio de mensagens) entre nós. Já esclarecemos que os nós se comunicam através da troca de mensagens. Existem dois modelos conhecidos de troca de mensagens: síncrono e assíncrono.

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

Modelo Síncrono – sabemos exatamente que existe uma delta de tempo finita conhecida, pela qual a mensagem chega garantidamente de um nó a outro. Se esse tempo se esgotar e a mensagem não chegar, podemos afirmar com segurança que o nó falhou. Nesse modelo, temos um tempo de espera previsível.

Modelo Assíncrono – nos modelos assíncronos, consideramos que o tempo de espera é finito, mas não existe uma delta de tempo após a qual é possível garantir que o nó falhou. Ou seja, o tempo de espera para uma mensagem de um nó pode ser indefinidamente longo. Essa é uma definição importante, e falaremos sobre isso mais adiante.

O conceito de consenso em sistemas distribuídos

Antes de definir formalmente o conceito de consenso, vamos considerar um exemplo de situação em que ele é necessário, nomeadamente – Replicação de Máquina de Estado.

Temos um certo log distribuído. Gostaríamos que ele fosse consistente e contivesse dados idênticos em todos os nós do sistema distribuído. Quando algum dos nós souber um novo valor que pretende gravar no log, sua tarefa é propor esse valor a todos os outros nós, para que o log seja atualizado em todos os nós e o sistema transite para um novo estado consistente. É importante que os nós cheguem a um acordo entre si: todos os nós concordaram que o novo valor proposto está correto, todos os nós aceitaram esse valor, e somente assim todos podem gravar o novo valor no log.

Em outras palavras: nenhum dos nós contestou que tem informações mais atualizadas, e que o valor proposto é incorreto. O acordo entre os nós e o consenso sobre um único valor aceito e correto é o consenso em um sistema distribuído. A seguir, discutiremos algoritmos que permitem que um sistema distribuído alcance o consenso de forma garantida.

De uma forma mais formal, podemos definir o algoritmo de consenso (ou simplesmente algoritmo de consenso) como uma função que transforma um sistema distribuído do estado A para o estado B. E esse estado é aceito por todos os nós, e todos os nós podem confirmá-lo. Como se revela, essa tarefa não é tão trivial quanto parece à primeira vista.

Propriedades do algoritmo de consenso

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

Acordo – todos os nós que estão funcionando corretamente devem aceitar o mesmo valor (neste contexto, essa propriedade é frequentemente referida como propriedade de segurança). Todos os nós que estão atualmente operacionais (não falharam e não perderam conexão com os demais) devem chegar a um acordo e aceitar um valor comum final.
É importante entender que os nós no sistema distribuído que estamos considerando desejam chegar a um acordo. Ou seja, estamos falando de sistemas onde alguma coisa pode falhar (por exemplo, algum nó pode falhar), mas nesse sistema, definitivamente não há nós que estejam intencionalmente trabalhando contra os outros (o problema dos generais bizantinos). Graças a esta propriedade, o sistema permanece consistente.
Integridade — se todos os nós que estão funcionando corretamente propuserem o mesmo valor v, então cada nó que está funcionando corretamente deve aceitar esse valor v.
Término – todos os nós que estão funcionando corretamente eventualmente aceitarão algum valor (propriedade de vivacidade), o que permite que o algoritmo tenha progresso no sistema. Cada nó individual que está funcionando corretamente deve, mais cedo ou mais tarde, aceitar um valor final e confirmá-lo: "Para mim, este valor é verdadeiro; eu concordo com todo o sistema."

Exemplo de funcionamento do algoritmo de consenso

Embora as propriedades do algoritmo possam não ser totalmente compreensíveis, vamos ilustrar com um exemplo quais etapas o algoritmo de consenso mais simples passa em um sistema com um modelo de troca de mensagens síncrono, onde todos os nós funcionam como deveriam, as mensagens não são perdidas e nada quebra (será que isso realmente acontece?).

Tudo começa com a proposta de um pedido de casamento (Propose). Suponha que um cliente se conectou ao nó chamado "Nó 1" e iniciou uma transação, passando ao nó um novo valor – O. Desde este momento, chamaremos de "Nó 1". proposer. Como proposer, o "Nó 1" agora deve notificar todo o sistema que possui novos dados, enviando mensagens a todos os outros nós: "Vejam! Recebi o valor 'O', e quero registrá-lo! Por favor, confirmem que vocês também registrarão 'O' em seus logs."
A próxima etapa é a votação pelo valor proposto (Voting). Para que serve isso? Pode acontecer que outros nós tenham recebido informações mais recentes, e eles têm dados sobre essa mesma transação.

Quando o nó "Nó 1" envia sua proposta, os outros nós verificam em seus logs os dados sobre esse evento. Se não houver contradições, os nós declaram: "Sim, não tenho outros dados sobre esse evento. O valor 'O' é a informação mais recente que temos."
Em qualquer outro caso, os nós podem responder ao "Nó 1": "Ouça! Tenho dados mais recentes sobre essa transação. Não 'O', mas algo melhor."
Na fase de votação, os nós chegam a uma decisão: ou todos aceitam um único valor, ou alguém deles vota contra, indicando que possui dados mais recentes.
Se a rodada de votação for bem-sucedida, e todos estiverem "a favor", o sistema avança para uma nova etapa – a aceitação do valor (Accept). O "Nó 1" reúne todas as respostas dos outros nós e comunica: "Todos concordaram com o valor 'O'! Agora declaro oficialmente que 'O' é nosso novo valor, único para todos! Anotem em suas agendas, não esqueçam. Registrem em seus logs!"
Os outros nós enviam a confirmação (Accepted), de que registraram o valor 'O', sem que novas informações tenham chegado nesse meio tempo (uma espécie de commit em duas fases). Após esse evento significativo, considera-se que a transação distribuída foi concluída.

Assim, o algoritmo de consenso, em seu caso simples, consiste em quatro etapas: propose, votação (voting), aceitação (accept), confirmação da aceitação (accepted).

Se em algum passo não conseguimos alcançar um consenso, o algoritmo reinicia, considerando as informações que os nós que se recusaram a confirmar o valor proposto fornecerão.

O algoritmo de consenso em um sistema assíncrono

Até aqui, tudo estava bem, já que estávamos falando sobre um modelo síncrono de troca de mensagens. Mas sabemos que, no mundo moderno, estamos acostumados a fazer tudo de forma assíncrona. Como, então, um algoritmo análogo funciona em um sistema com um modelo assíncrono de troca de mensagens, onde acreditamos que o tempo de espera pela resposta de um nó pode ser indefinidamente longo (a propósito, a falha de um nó também pode ser vista como um exemplo em que um nó pode responder por tempo indeterminado).

Agora que sabemos, de forma geral, como funciona o algoritmo de consenso, uma questão para os leitores curiosos que chegaram até aqui: quantos nós em um sistema de N nós com um modelo de mensagens assíncrono podem falhar, para que o sistema ainda consiga alcançar consenso?

A resposta correta e a explicação estão na seção de spoilers.A resposta correta: 0. Se pelo menos um nó em um sistema assíncrono falhar, o sistema não conseguirá alcançar consenso. Esta afirmação foi provada no teorema FLP, que é conhecido em certos círculos (1985, Fischer, Lynch, Paterson, link para o original no final do artigo): "Impossibilidade de alcançar consenso distribuído na falha de pelo menos um nó".

Pessoal, então temos um problema, estamos acostumados a que tudo seja assíncrono. E agora isso. Como iremos seguir em frente?

Estávamos falando agora sobre teoria, sobre matemática. O que significa "o consenso não pode ser alcançado", traduzindo da linguagem matemática para a nossa – engenharia? Isso significa que "nem sempre pode ser alcançado", ou seja, existe um caso em que o consenso não é alcançável. E qual seria esse caso?

Isso é exatamente a violação da propriedade de liveness, descrita acima. Não temos um consenso comum, e o sistema não pode ter progresso (não pode se completar em um tempo finito) quando não temos resposta de todos os nós. Porque em um sistema assíncrono não temos um tempo de resposta previsível, e não podemos saber se um nó falhou ou apenas está demorando a responder.

Mas na prática, podemos encontrar uma solução. Vamos supor que nosso algoritmo possa funcionar por muito tempo em caso de falhas (potencialmente pode funcionar indefinidamente). Mas na maioria das situações, quando a maioria dos nós funciona corretamente, teremos progresso no sistema.

Na prática, lidamos com modelos de comunicação parcialmente síncronos. A parcialidade da sincronia é entendida como: de maneira geral, temos um modelo assíncrono, mas formalmente introduz-se o conceito de "tempo de estabilização global" em um determinado momento.

Esse momento pode não ocorrer por um tempo indefinido, mas um dia ele deve ocorrer. Soará um despertador virtual, e a partir desse momento podemos prever a delta de tempo pela qual as mensagens chegarão. Nesse ponto, o sistema passa de assíncrono para síncrono. Na prática, lidamos exatamente com esses tipos de sistemas.

O algoritmo Paxos resolve problemas de consenso.

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

Mas a prova se revelou longe de ser trivial. A primeira publicação foi lançada apenas em 1998 (33 páginas) com uma descrição do algoritmo. Como se mostrou, era extremamente difícil de entender, e em 2001 foi publicada uma explicação do artigo, que ocupou 14 páginas. O volume das publicações é mencionado para mostrar que, na verdade, o problema do consenso não é simples, e por trás de tais algoritmos existe um enorme esforço dos mais brilhantes pensadores.

Curiosamente, o próprio Leslie Lamport, em sua palestra, observou que há uma afirmação, uma linha (não especificou qual), na segunda artigo de explicação que pode ser interpretada de várias maneiras. E devido a isso, um grande número de implementações modernas do Paxos não funciona de maneira totalmente correta.

Uma análise detalhada do funcionamento do Paxos não caberia em um único artigo, portanto, tentarei transmitir de forma muito breve a ideia central do algoritmo. Nos links no final do meu artigo, você encontrará materiais para um aprofundamento nesse tema.

Papéis no Paxos.

No algoritmo Paxos, existe o conceito de papéis. Vamos considerar três principais (há modificações com papéis adicionais):

Proposers (também podem ser chamados de líderes ou coordenadores).. Esses são os caras que descobrem um novo valor a partir do usuário e assumem o papel de líder. A sua tarefa é iniciar um ciclo de proposta de um novo valor e coordenar as ações subsequentes dos nós. Além disso, o Paxos permite a presença de múltiplos líderes em determinadas situações.
Aceitadores (Votantes). Esses são os nós que votam pela aceitação ou rejeição de um determinado valor. O papel deles é muito importante, pois depende deles a decisão: para qual estado o sistema irá (ou não) transitar após a próxima etapa do algoritmo de consenso.
Aprendizes. Nós que simplesmente aceitam e registram o novo valor aceito quando o estado do sistema muda. Eles não tomam decisões, apenas recebem dados e podem fornecê-los ao usuário final.

Um nó pode combinar múltiplos papéis em diferentes situações.

O conceito de quórum

Suponhamos que temos um sistema com N nós. E, destes, no máximo F nós podem ficar fora de operação. Se F nós ficarem fora de operação, então deve haver, no mínimo, 2F + 1 nós aceitadores.

Isso é necessário para que sempre, mesmo na pior situação, os nós 'bons' e funcionando corretamente tenham a maioria. Ou seja, F + 1 nós 'bons' que concordaram, e o valor final será aceito. Caso contrário, pode ocorrer uma situação em que diferentes grupos locais aceitem valores diferentes e não consigam entrar em acordo. Portanto, precisamos de uma maioria absoluta para vencer a votação.

A ideia geral do funcionamento do algoritmo de consenso Paxos

O algoritmo Paxos envolve duas grandes fases, que são divididas em dois passos cada uma:

Fase 1a: Preparar. Na fase de preparação, o líder (proposer) informa todos os nós: «Estamos começando uma nova fase de votação. Temos uma nova rodada. O número desta rodada é n. Agora começaremos a votar». Por enquanto, ele apenas informa o início de um novo ciclo, mas não comunica um novo valor. A tarefa desta fase é iniciar uma nova rodada e informar a todos seu número único. O número da rodada é importante, pois deve ser um valor maior do que todos os números anteriores de votações feitas por líderes anteriores. É graças ao número da rodada que os outros nós no sistema entenderão quão atualizados estão os dados do líder. Provavelmente, outros nós já possuem resultados de votações de rodadas muito mais recentes e simplesmente dirão ao líder que ele está defasado.
Fase 1b: Promessa. Quando os nós-acceptors recebem o número da nova fase de votação, duas coisas podem acontecer:
- Se o número n da nova votação for maior do que o número de qualquer votação anterior em que o acceptor participou, o acceptor envia ao líder uma promessa de que não participará mais de nenhuma votação com um número menor do que n. Se o acceptor já votou em algo (ou seja, está na segunda fase e aceitou algum valor), ele anexa ao seu compromisso o valor aceito e o número da votação em que participou.
- Caso contrário, se o acceptor já souber de uma votação com um número maior, ele pode simplesmente ignorar a fase de preparação e não responder ao líder.
Fase 2a: Aceitar. O líder precisa aguardar a resposta do quórum (maioria dos nós no sistema) e, se o número necessário de respostas for recebido, ele tem duas opções:
- Alguns dos acceptors enviaram valores pelos quais já votaram. Nesse caso, o líder escolhe o valor da votação com o número máximo. Vamos chamar este valor de x e ele envia a todos os nós uma mensagem do tipo: «Accept (n, x)», onde o primeiro valor é o número da votação de seu próprio passo Propose e o segundo valor é aquilo pelo qual todos estavam se reunindo, ou seja, o valor pelo qual, efetivamente, estamos votando.
- Se ninguém dos acceptor' s enviou nenhum valor e apenas prometeram votar nesta rodada, o líder pode sugerir que eles votem pelo seu próprio valor, aquele pelo qual ele se tornou líder. Vamos chamá-lo de y. Ele envia a todos os nós uma mensagem do tipo: "Accept (n, y)", de forma análoga ao resultado anterior.
Fase 2b: Aceito. Então, os nós-acceptor, ao receberem a mensagem "Accept(…)" do líder, concordam com ele (enviam a todos os nós uma confirmação de que concordam com o novo valor) apenas se não prometeram a algum (outro) líder participar das votações com o número da rodada n’ > n, caso contrário, ignoram o pedido de confirmação.
Se a maioria dos nós respondeu ao líder e todos confirmaram o novo valor, então o novo valor é considerado aceito. Hurra! Se a maioria não for alcançada ou houver nós que se recusaram a aceitar o novo valor, tudo começa de novo.

Assim funciona o algoritmo Paxos. Cada uma dessas etapas tem muitas sutilezas, praticamente não abordamos as várias formas de falhas, problemas com múltiplos líderes e muito mais, mas o objetivo deste artigo é apenas, em um nível superficial, introduzir o leitor ao mundo da computação distribuída.

Também é importante notar que Paxos não é o único de seu tipo, existem outros algoritmos, como Raft, mas esse já é um assunto para outro artigo.