Então, vamos imaginar. Há 5 gatos trancados no quarto, e para ir acordar o dono todos precisam combinar isso entre si, pois só conseguem abrir a porta com cinco deles encostados nela. Se um dos gatos é o gato de Schrödinger e os outros gatos não sabem da sua decisão, surge a pergunta: “Como podem fazer isso?”
Neste artigo contarei em termos simples sobre o componente teórico do mundo dos sistemas distribuídos e os princípios de seu funcionamento. Também examinarei superficialmente a ideia principal subjacente ao Paxos.
Quando os desenvolvedores usam infraestruturas em nuvem, vários bancos de dados e 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 disponíveis. Mas onde estão as garantias?
Essencialmente, as garantias que temos são garantias do fornecedor. Eles são descritos na documentação da seguinte forma: “Este serviço é bastante confiável, tem um determinado SLA, não se preocupe, tudo funcionará de forma distribuída conforme você espera”.
Tendemos a acreditar no melhor, porque os espertos das grandes empresas nos garantiram que tudo ficará bem. Não fazemos a pergunta: por que, de fato, isso pode funcionar? Existe alguma justificativa formal para o correto funcionamento de tais sistemas?
Recentemente fui para e fiquei muito inspirado por este tópico. As palestras na escola pareciam mais aulas de cálculo do que algo relacionado a sistemas de computador. Mas foi exatamente assim que os algoritmos mais importantes que usamos todos os dias, mesmo sem saber, foram comprovados de uma só vez.
A maioria dos sistemas distribuídos modernos usa o algoritmo de consenso Paxos e suas diversas modificações. O mais legal é que a validade e, em princípio, a própria possibilidade da existência desse algoritmo podem ser comprovadas simplesmente com papel e caneta. Na prática, o algoritmo é usado em grandes sistemas executados em um grande número de nós nas nuvens.
Uma leve ilustração do que será discutido a seguir: a tarefa de dois generaisVamos dar uma olhada para um aquecimento .
Temos dois exércitos - vermelho e branco. As tropas brancas estão baseadas na cidade sitiada. As tropas vermelhas lideradas pelos generais A1 e A2 estão localizadas em dois lados da cidade. A tarefa dos ruivos é atacar a cidade branca e vencer. No entanto, o exército de cada general vermelho individualmente é menor que o exército branco.
Condições de vitória dos vermelhos: ambos os generais devem atacar ao mesmo tempo para terem vantagem numérica sobre os brancos. Para fazer isso, os generais A1 e A2 precisam chegar a um acordo entre si. Se todos atacarem separadamente, os ruivos perderão.
Para chegar a um acordo, os generais A1 e A2 podem enviar mensageiros entre si através do território da cidade branca. O mensageiro pode alcançar com sucesso um general aliado ou ser interceptado pelo inimigo. Pergunta: existe tal 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), em que eles têm a garantia de concordar com um ataque na hora X. Aqui, garantias significam que ambos os generais terão uma confirmação inequívoca de que um aliado (outro general) atacará definitivamente na hora marcada X.
Suponha que A1 envie um mensageiro para A2 com a mensagem: “Vamos atacar hoje à meia-noite!” O General A1 não pode atacar sem a confirmação do General A2. Se o mensageiro de A1 chegou, o General A2 envia a confirmação com a mensagem: “Sim, vamos matar os brancos hoje”. Mas agora o General A2 não sabe se o seu mensageiro chegou ou não, não tem garantias se o ataque será simultâneo. Agora o General A2 precisa novamente de confirmação.
Se analisarmos ainda mais as suas comunicações, descobrimos que não importa quantas rondas de mensagens possam existir, não há forma de garantir que ambos os generais sejam notificados de que as suas mensagens foram recebidas (assumindo que qualquer um dos mensageiros possa ser interceptado).
O Problema dos Dois Generais é uma ótima ilustração de um sistema distribuído muito simples onde existem dois nós com comunicação não confiável. Isso significa que não temos 100% de garantia de que eles estejam sincronizados. Problemas semelhantes são discutidos apenas em maior escala posteriormente neste artigo.
Apresentamos o conceito de sistemas distribuídos
Um sistema distribuído é um grupo de computadores (doravante os chamaremos de nós) que podem trocar mensagens. Cada nó individual é algum tipo de entidade autônoma. Um nó pode processar tarefas por conta própria, mas para se comunicar com outros nós ele precisa enviar e receber mensagens.
Como exatamente as mensagens são implementadas, quais protocolos são usados – isso não nos interessa neste contexto. É importante que os nós de um sistema distribuído possam trocar dados entre si através do envio de mensagens.
A definição em si não parece muito complicada, mas devemos levar em conta 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 eventos que ocorrem em dois nós diferentes como potencialmente simultâneos, desde que não tenhamos uma ordem clara de ocorrência desses eventos. Mas, via de regra, não temos.
- Sem relógio global. Não temos uma ordem clara dos acontecimentos devido à falta de um relógio global. No mundo comum das pessoas, estamos acostumados com o fato de que temos relógios e horas absolutamente. Tudo muda quando se trata de sistemas distribuídos. Mesmo os relógios atômicos ultraprecisos sofrem desvios e pode haver situações em que não possamos dizer qual dos dois eventos aconteceu primeiro. Portanto, também não podemos confiar no tempo.
- Falha independente de nós do sistema. Há outro problema: algo pode dar errado simplesmente porque nossos nós não duram para sempre. O disco rígido pode falhar, a máquina virtual na nuvem pode reiniciar, a rede pode piscar e as mensagens serão perdidas. Além disso, pode haver situações em que os nós funcionam, mas ao mesmo tempo trabalham contra o sistema. A última classe de problemas recebeu até um nome separado: problema . O exemplo mais popular de sistema distribuído com esse problema é o Blockchain. Mas hoje não consideraremos esta classe especial de problemas. Estaremos interessados em situações em que simplesmente um ou mais nós podem falhar.
- Modelos de comunicação (modelos de mensagens) entre nós. Já estabelecemos que os nós se comunicam por meio da troca de mensagens. Existem dois modelos de mensagens bem conhecidos: síncronos e assíncronos.
Modelos de comunicação entre nós em sistemas distribuídos
Modelo síncrono – sabemos com certeza que existe um delta de tempo finito conhecido durante o qual é garantido que uma mensagem chegue de um nó a outro. Se esse tempo passou e a mensagem não chegou, podemos dizer com segurança que o nó falhou. Neste modelo temos tempos de espera previsíveis.
Modelo assíncrono – em modelos assíncronos consideramos que o tempo de espera é finito, mas não existe tal delta de tempo após o qual possamos garantir que o nó falhou. Aqueles. O tempo de espera por uma mensagem de um nó pode ser arbitrariamente longo. Esta é uma definição importante e falaremos sobre ela mais adiante.
O conceito de consenso em sistemas distribuídos
Antes de definir formalmente o conceito de consenso, consideremos um exemplo de situação em que precisamos dele, a saber - Replicação de máquina de estado.
Temos algum log distribuído. Gostaríamos que fosse consistente e contivesse dados idênticos em todos os nós do sistema distribuído. Quando um dos nós aprende um novo valor que irá gravar no log, sua tarefa passa a ser oferecer esse valor a todos os outros nós para que o log seja atualizado em todos os nós e o sistema passe para um novo estado consistente. Neste caso, é 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 este valor, e somente neste caso todos podem escrever o novo valor no log.
Ou seja: nenhum dos nós objetou que possuía informações mais relevantes e o valor proposto estava incorreto. A concordância entre os nós e a concordância sobre um único valor correto aceito é consenso em um sistema distribuído. A seguir, falaremos sobre algoritmos que permitem garantir que um sistema distribuído alcance o consenso.
Mais formalmente, podemos definir um algoritmo de consenso (ou simplesmente um algoritmo de consenso) como uma determinada função que transfere um sistema distribuído do estado A para o estado B. Além disso, este estado é aceito por todos os nós, e todos os nós podem confirmá-lo. Acontece que esta tarefa não é tão trivial como 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 progresso na mudança de estado para estado:
- Acordo – todos os nós operando corretamente devem ter o mesmo valor (nos artigos esta propriedade também é chamada de propriedade de segurança). Todos os nós que estão funcionando atualmente (que não falharam ou perderam contato com os outros) devem chegar a um acordo e aceitar algum valor final comum.
É importante entender aqui que os nós do sistema distribuído que estamos considerando querem concordar. Ou seja, estamos falando agora de sistemas em que algo pode simplesmente falhar (por exemplo, algum nó falha), mas neste sistema definitivamente não há nós que trabalhem deliberadamente contra outros (a tarefa dos generais bizantinos). Devido a esta propriedade, o sistema permanece consistente.
- Integridade — se todos os nós funcionando corretamente oferecerem o mesmo valor v, o que significa que todo nó operando corretamente deve aceitar este valor v.
- Terminação – todos os nós operando corretamente acabarão por assumir um determinado valor (propriedade de vivacidade), o que permite ao algoritmo progredir no sistema. Cada nó individual operando corretamente deve, mais cedo ou mais tarde, aceitar o valor final e confirmá-lo: “Para mim, esse valor é verdadeiro, concordo com todo o sistema”.
Um exemplo de como funciona o algoritmo de consenso
Embora as propriedades do algoritmo possam não ser totalmente claras. Portanto, ilustraremos com um exemplo quais etapas passa o algoritmo de consenso mais simples em um sistema com modelo de mensagens síncronas, em que todos os nós funcionam conforme o esperado, as mensagens não são perdidas e nada quebra (isso realmente acontece?).
- Tudo começa com uma proposta de casamento (Propor). Vamos supor que um cliente se conectou a um nó chamado “Nó 1” e iniciou uma transação, passando um novo valor para o nó - O. A partir de agora chamaremos de “Nó 1” propor. Como proponente, o “Nó 1” deve agora notificar todo o sistema que possui dados novos e enviar mensagens para todos os outros nós: “Olha! O significado “O” veio até mim e quero anotar! Por favor, confirme que você também registrará “O” em seu registro.”
- A próxima etapa é a votação do valor proposto (Votação). Para que serve? Pode acontecer que outros nós tenham recebido informações mais recentes e possuam dados sobre a mesma transação.
Quando o nó “Nó 1” envia sua proposta, os outros nós verificam seus logs em busca de dados sobre este evento. Se não houver contradições, os nós anunciam: “Sim, não tenho outros dados para este evento. O valor “O” é a informação mais recente que merecemos.”Em qualquer outro caso, os nós podem responder ao “Nó 1”: “Ouça! Tenho dados mais recentes sobre esta transação. Não 'O', mas algo melhor."
Na fase de votação, os nós tomam uma decisão: ou todos aceitam o mesmo valor, ou um deles vota contra, indicando que possui dados mais recentes.
- Se a votação foi bem-sucedida e todos foram a favor, o sistema passa para uma nova etapa – Aceitação do valor. O “Nó 1” coleta todas as respostas dos demais nós e informa: “Todos concordaram com o valor “O”! Agora declaro oficialmente que “O” é o nosso novo significado, igual para todos! Escreva no seu livrinho, não se esqueça. Anote no seu diário!
- Os restantes nós enviam a confirmação (Aceito) de que anotaram o valor “O”; nada de novo chegou durante este tempo (uma espécie de commit de duas fases). Após este evento significativo, consideramos que a transação distribuída foi concluída.
Assim, o algoritmo de consenso em um caso simples consiste em quatro etapas: propor, votar (votar), aceitar (aceitar), confirmar aceitação (aceito).
Se em algum momento não conseguirmos chegar a um acordo, então o algoritmo recomeça, tendo em conta as informações fornecidas pelos nós que se recusaram a confirmar o valor proposto.
Algoritmo de consenso em um sistema assíncrono
Antes tudo corria bem, pois estávamos falando de um modelo de mensagens síncronas. Mas sabemos que no mundo moderno estamos acostumados a fazer tudo de forma assíncrona. Como funciona um algoritmo semelhante em um sistema com modelo de mensagens assíncronas, onde acreditamos que o tempo de espera por uma resposta de um nó pode ser arbitrariamente longo (aliás, a falha de um nó também pode ser considerada um exemplo quando um nó pode responder por um tempo arbitrariamente longo).
Agora que sabemos como o algoritmo de consenso funciona em princípio, uma pergunta para os leitores curiosos que chegaram até aqui: quantos nós em um sistema de N nós com um modelo de mensagem assíncrona podem falhar para que o sistema ainda possa chegar ao consenso?
A resposta correta e a justificativa estão por trás do spoiler.A resposta correta é: 0. Se pelo menos um nó em um sistema assíncrono falhar, o sistema não será capaz de chegar a um consenso. Esta afirmação é comprovada no teorema FLP, bem conhecido em certos círculos (1985, Fischer, Lynch, Paterson, link para o original no final do artigo): “A impossibilidade de alcançar um consenso distribuído se pelo menos um nó falhar .”
Pessoal, então estamos com um problema, estamos acostumados com tudo ser assíncrono. E aqui está. Como continuar a viver?
Estávamos conversando sobre teoria, sobre matemática. O que significa “consenso não pode ser alcançado”, traduzindo da linguagem matemática para a nossa - engenharia? Isto significa que “nem sempre pode ser alcançado”, ou seja, Há um caso em que o consenso não é alcançável. Que tipo de caso é esse?
Esta é exatamente a violação da propriedade de vivacidade descrita acima. Não temos um acordo comum e o sistema não pode ter progresso (não pode ser concluído em um tempo finito) caso não tenhamos resposta de todos os nós. Porque em um sistema assíncrono não temos tempo de resposta previsível e não podemos saber se um nó travou ou apenas está demorando para responder.
Mas na prática podemos encontrar uma solução. Deixe nosso algoritmo ser capaz de funcionar por muito tempo em caso de falhas (potencialmente pode funcionar indefinidamente). Mas na maioria das situações, quando a maioria dos nós estiver funcionando corretamente, teremos progresso no sistema.
Na prática, lidamos com modelos de comunicação parcialmente síncronos. A sincronia parcial é entendida da seguinte forma: no caso geral, temos um modelo assíncrono, mas é formalmente introduzido um certo conceito de “tempo de estabilização global” de um determinado momento.
Este momento pode não chegar por muito tempo, mas deve chegar um dia. O despertador virtual tocará e a partir desse momento poderemos prever o delta de tempo para o qual as mensagens chegarão. A partir deste momento o sistema passa de assíncrono para síncrono. Na prática, lidamos precisamente com esses sistemas.
O algoritmo Paxos resolve problemas de consenso
é uma família de algoritmos que resolve o problema de consenso para sistemas parcialmente síncronos, sujeito à possibilidade de falha de alguns nós. O autor de Paxos é . Ele propôs uma prova formal da existência e correção do algoritmo em 1989.
Mas a prova acabou por estar longe de ser trivial. A primeira publicação foi lançada apenas em 1998 (33 páginas) descrevendo o algoritmo. No final das contas, era extremamente difícil de entender e, em 2001, foi publicada uma explicação do artigo, que ocupava 14 páginas. O volume de publicações é dado para mostrar que na verdade o problema do consenso não é nada simples, e por trás de tais algoritmos está uma enorme quantidade de trabalho das pessoas mais inteligentes.
É interessante que o próprio Leslie Lamport tenha notado em sua palestra que no segundo artigo explicativo há uma afirmação, uma linha (ele não especificou qual), que pode ser interpretada de diferentes maneiras. E por causa disso, um grande número de implementações modernas do Paxos não funciona totalmente corretamente.
Uma análise detalhada do trabalho de Paxos exigiria mais de um artigo, por isso tentarei transmitir muito brevemente a ideia principal do algoritmo. Nos links no final do meu artigo você encontrará materiais para se aprofundar neste tópico.
Funções na Paxos
O algoritmo Paxos possui um conceito de funções. Consideremos três principais (existem modificações com funções adicionais):
- Proponentes (podem também ser utilizados os termos: líderes ou coordenadores). São esses caras que aprendem algum novo valor com o usuário e assumem o papel de líder. Sua tarefa é lançar uma rodada de propostas para um novo valor e coordenar futuras ações dos nós. Além disso, o Paxos permite a presença de vários líderes em determinadas situações.
- Aceitadores (eleitores). Estes são nós que votam para aceitar ou rejeitar um determinado valor. Seu papel é muito importante, pois depende deles a decisão: para qual estado o sistema irá (ou não) após a próxima etapa do algoritmo de consenso.
- Alunos. Nós que simplesmente aceitam e escrevem o novo valor aceito quando o estado do sistema muda. Eles não tomam decisões, apenas recebem os dados e podem fornecê-los ao usuário final.
Um nó pode combinar diversas funções em diferentes situações.
O conceito de quórum
Supomos que temos um sistema de N nós E deles o máximo F nós podem falhar. Se os nós F falharem, então devemos ter pelo menos 2F+1 nós aceitadores.
Isto é necessário para que tenhamos sempre a maioria, mesmo na pior situação, de “bons” nós que funcionam corretamente. Aquilo é F+1 nós "bons" que concordaram, e o valor final será aceito. Caso contrário, poderá surgir uma situação em que os nossos diferentes grupos locais assumam significados diferentes e não consigam chegar a acordo entre si. Portanto, precisamos de maioria absoluta para ganhar a votação.
A ideia geral de como funciona o algoritmo de consenso Paxos
O algoritmo Paxos envolve duas grandes fases, que por sua vez são divididas em duas etapas cada:
- Fase 1a: Preparação. Durante a fase de preparação, o líder (proponente) informa a todos os nós: “Estamos iniciando uma nova fase de votação. Temos uma nova rodada. O número desta rodada é n. Agora vamos começar a votar." Por enquanto, simplesmente informa o início de um novo ciclo, mas não informa um novo valor. A tarefa desta etapa é iniciar uma nova rodada e informar a todos o seu número único. O número redondo é importante, deve ser um valor maior que todos os números de votação anteriores de todos os líderes anteriores. Porque é graças ao número redondo que outros nós do sistema entenderão o quão recentes são os dados do líder. É provável que outros nós já tenham resultados de votação de rodadas muito posteriores e simplesmente digam ao líder que ele está atrasado.
- Fase 1b: Promessa. Quando os nós aceitadores recebem o número da nova etapa de votação, dois resultados são possíveis:
- O número n da nova votação é maior que o número de qualquer votação anterior da qual o aceitante participou. Em seguida, o aceitante promete ao líder que não participará de mais votações com número inferior a n. Se o aceitante já votou em algo (ou seja, já aceitou algum valor na segunda fase), então ele anexa à sua promessa o valor aceito e o número da votação em que participou.
- Caso contrário, se o aceitante já tiver conhecimento do voto de maior número, pode simplesmente ignorar a etapa de preparação e não responder ao líder.
- Fase 2a: Aceitar. O líder precisa aguardar uma resposta do quorum (a maioria dos nós do sistema) e, se o número necessário de respostas for recebido, ele tem duas opções para o desenvolvimento de eventos:
- Alguns dos aceitantes enviaram valores nos quais já haviam votado. Neste caso, o líder seleciona o valor da votação com o número máximo. Vamos chamar esse valor de x, e ele envia uma mensagem para todos os nós como: “Aceitar (n, x)”, onde o primeiro valor é o número de votação de sua própria etapa de Proposição, e o segundo valor é o que todos reuniram, ou seja o valor pelo qual realmente votamos.
- Se nenhum dos aceitantes enviou quaisquer valores, mas simplesmente prometeram votar nesta rodada, o líder pode convidá-los a votar no seu valor, valor pelo qual ele se tornou líder em primeiro lugar. Vamos chamá-lo de y. Envia uma mensagem para todos os nós como: “Aceitar (n, y)”, semelhante ao resultado anterior.
- Fase 2b: Aceito. Além disso, os nós aceitadores, ao receberem a mensagem “Aceitar(...)” do líder, concordam com ela (enviam confirmação a todos os nós de que concordam com o novo valor) somente se não tiverem prometido algum (outro)) líder participará da votação com número redondo n' > n, caso contrário, eles ignorarão a solicitação de confirmação.
Se a maioria dos nós responderam ao líder e todos confirmaram o novo valor, então o novo valor é considerado aceito. Viva! Se a maioria não for alcançada ou houver nós que se recusaram a aceitar o novo valor, tudo recomeça.
É assim que funciona o algoritmo Paxos. Cada uma dessas etapas possui muitas sutilezas, praticamente não consideramos vários tipos de falhas, problemas de múltiplos líderes e muito mais, mas o objetivo deste artigo é apenas apresentar ao leitor o mundo da computação distribuída em alto nível.
Vale ressaltar também que Paxos não é o único do gênero, existem outros algoritmos, por exemplo, , mas este é um assunto para outro artigo.
Links para materiais para estudo adicional
Nível iniciante:
- , Preethi Kasireddy, artigo do blog no Medium
- , Adi Kancherla, artigo do blog no Medium
- , Ittai Abraão, blog
- , Ittai Abraham, artigo do blog
Nível de Leslie Lamport:
- , Fischer, Lynch e Paterson, artigo de pesquisa, 1985
- , Leslie Lamport, artigo de pesquisa, 1998
- , Leslie Lamport, artigo de pesquisa, 2001
Fonte: habr.com