Algoritmo de consenso Raft (2015)

 (raft.github.io)
3 pontos por GN⁺ 2023-09-04 | 1 comentários | Compartilhar no WhatsApp
  • O Raft foi projetado para tornar o problema de consenso em que vários servidores precisam tomar a mesma decisão em sistemas distribuídos mais fácil de entender, com o objetivo de alcançar tolerância a falhas e desempenho equivalentes ao Paxos
  • O Raft divide a estrutura em subproblemas como eleição de líder, replicação de log e segurança, deixando mais claros os pontos de decisão necessários para implementar uma máquina de estados replicada
  • O sistema pode continuar avançando enquanto a maioria dos servidores estiver viva e mantém a segurança de modo que, mesmo que a maioria desapareça e tudo pare, não produza resultados incorretos
  • O site reúne o RaftScope baseado em navegador, a visualização The Secret Lives of Data, o artigo do Raft, a especificação em TLA+, além de artigos e materiais de palestra sobre verificação e análise
  • Há implementações organizadas em várias linguagens, como Rust, Go, Java, C++, C#, Python e outras, e cada implementação difere no suporte a eleição de líder e replicação de log, persistência, mudança de membros e compactação de log

O problema de consenso que o Raft busca resolver

  • O Raft foi projetado para tornar algoritmos de consenso compreensíveis para um público mais amplo
  • O objetivo é ter tolerância a falhas e desempenho em nível equivalente ao Paxos
  • A principal diferença está na estrutura
    • O problema é dividido em subproblemas relativamente independentes
    • Os componentes necessários para implementar um sistema real são tratados separadamente
  • O objetivo é permitir entender sistemas baseados em consenso com mais facilidade e implementá-los com mais qualidade

Consenso e máquina de estados replicada

  • Consenso (consensus) é o problema fundamental de sistemas distribuídos tolerantes a falhas
  • Vários servidores concordam em um único valor, e um valor decidido uma vez se torna o estado final
  • Um algoritmo de consenso típico avança quando a maioria dos servidores está disponível
    • Em um cluster com 5 servidores, o sistema pode continuar funcionando mesmo se 2 falharem
    • Se mais servidores falharem, o progresso para
    • Mesmo assim, é importante não retornar resultados incorretos
  • O consenso geralmente é usado para construir uma máquina de estados replicada
    • Cada servidor tem uma máquina de estados e um log
    • A máquina de estados pode ser um componente ao qual se deseja dar tolerância a falhas, como uma tabela hash
    • O cliente pode enxergar isso como se estivesse interagindo com uma única máquina de estados confiável, mesmo que alguns servidores falhem
  • Cada máquina de estados recebe comandos do seu próprio log como entrada
    • No exemplo da tabela hash, comandos como set x to 3 entram no log
    • O algoritmo de consenso determina quais comandos entram nos logs dos servidores e em que ordem
    • Se uma máquina de estados aplicou set x to 3 como o enésimo comando, deve ser garantido que outra máquina de estados não aplique um comando diferente na mesma posição
  • Como resultado, todas as máquinas de estados processam a mesma sequência de comandos e chegam à mesma sequência de resultados e estados

Visualizações para entender o Raft

  • É possível manipular diretamente uma visualização de cluster Raft executada no navegador
    • À esquerda são mostrados 5 servidores
    • À direita são mostrados os logs de cada servidor
    • O usuário pode interagir e observar o funcionamento do Raft
  • RaftScope ainda tem bastante coisa a ser refinada, e Pull Requests são bem-vindos
  • The Secret Lives of Data é uma visualização que apresenta o Raft de outra forma
    • Ela é mais guiada e menos interativa
    • Pode ser um ponto de partida mais suave para quem está vendo o tema pela primeira vez

Artigos, especificações e materiais de verificação

Palestras e materiais educacionais

  • Há também uma lista de palestras introdutórias sobre Raft
    • Palestra de John Ousterhout na CS@Illinois Distinguished Lecture Series, agosto de 2016
    • Palestra de Jin Li sobre Raft e a especificação em TLA+ na Dr. TLA+ Series, julho de 2016
    • Palestras de Diego Ongaro na Build Stuff 2015, CoreOS Fest 2015, meetup da Sourcegraph, LinkedIn, USENIX ATC 2014, CraftConf 2014 e RICON West 2013
    • Palestra de Ben Johnson na Strange Loop 2013
    • Aula de John Ousterhout sobre o Raft User Study, março de 2013
  • O Raft também é usado em universidades e cursos como tema de aula ou tarefa de programação
    • Estão incluídos vários cursos de University of Copenhagen, Czech Technical University in Prague, The University of Hong Kong, University of Virginia, UC San Diego, Technical University of Munich, UIUC e outros
    • Alguns cursos oferecem tarefas de programação sobre Raft em Go, Java, Erlang e outras linguagens
    • O MIT 6.824 inclui notas de aula sobre Raft e também indica os textos de Jon Gjengset para instrutores e estudantes
  • Cursos adicionais podem ser adicionados ou atualizados no repositório do site via Pull Request ou issue

Canal de perguntas e lista de implementações

  • Para perguntas sobre o Raft e suas implementações, o local indicado é o raft-dev Google group
  • Algumas implementações têm sua própria mailing list, então é preciso verificar o README de cada uma
  • Também é fornecida uma lista de implementações de Raft com código-fonte público
    • Implementações populares ou atualizadas recentemente ficam no topo da tabela
    • As informações podem ficar desatualizadas com o tempo e podem ser atualizadas via Pull Request ou issue
  • A tabela compara Stars, nome, principais autores, linguagem, licença e suporte a recursos em cada implementação
    • Os itens de recurso são eleição de líder e replicação de log, persistência, mudança de membros e compactação de log
  • Exemplos do topo da lista incluem
    • TiKV: Rust, Apache-2.0, 16,751★, com suporte a eleição de líder e replicação de log, persistência, mudança de membros e compactação de log
    • RethinkDB: C++, Apache-2.0, 27,000★, com suporte a todos os principais recursos
    • Seastar Raft: C++20, AGPL, 15,624★, com suporte a todos os principais recursos
    • hashicorp/raft: Go, MPL-2.0, 9,048★, com suporte a todos os principais recursos
    • hazelcast-raft: Java, Apache-2.0, 6,579★, com suporte a todos os principais recursos
  • A lista inclui implementações em várias linguagens, como Rust, Go, Java, C++, C, Erlang, Python, Scala, C#, JavaScript, Haskell, OCaml, Kotlin, Zig, TypeScript, Elixir, F#, Shell e outras

Leituras relacionadas

1 comentários

 
GN⁺ 2023-09-04
Opiniões no Hacker News

  • O ambiente de prática para aprendizado de sistemas distribuídos Maelstrom, do criador do Jepsen, traz uma implementação simples de verificação de modelo do Raft e um tutorial de implementação muito bons: https://github.com/jepsen-io/maelstrom/
    Raft é um algoritmo simples, mas o artigo original tem muitos detalhes de correção que costumam ser omitidos em implementações de brinquedo
    Quando se leva em conta corrupção de memória/disco em hardware real, falhas cinzentas, SLAs de latência apertados, quóruns flexíveis e membership dinâmica de cluster, uma implementação em produção vira um trabalho longo e pesado
    Só de olhar o histórico de commits do etcd e do hashicorp/raft, dá para ver que até as implementações open source de Raft mais validadas revelam bugs de correção regularmente
    A equipe do TigerBeetle trata em detalhes da realidade dos sistemas distribuídos em hardware imperfeito e em um modelo de sistema não abstraído, e também explica por que escolheu Viewstamped Replication, que é mais antigo que Paxos, mas parece mais parecido com Raft: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...

    • Em relação à parte de que “Viewstamped Replication é mais antigo que Paxos, mas parece mais parecido com Raft”, o artigo Paxos vs Raft, de Heidi Howard e Richard Mortier, coloca lado a lado o Paxos de consenso múltiplo e o Raft de uma forma que os faz parecer muito próximos: https://doi.org/10.1145/3380787.3393681
      Não sei bem que consequências isso traz para as preocupações de implementação, mas o artigo em si é excelente e eu recomendo
      Também há uma apresentação, mas acho o texto melhor para consultar indo e voltando entre as referências: https://www.youtube.com/watch?v=0K6kt39wyH0
    • O artigo de Viewstamped Replication foi surpreendentemente fácil de ler
      Mesmo sem nunca ter visto algoritmos de consenso, depois de ler algumas vezes consegui acompanhar em certa medida: https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
    • Também não dá para esquecer as topologias de rede heterogêneas e o fato de que alguns membros são realmente péssimos se forem escolhidos como líder

  • Recentemente implementei a eleição de líder e a replicação de logs do Raft; não cheguei a snapshots/checkpoints, mas foi um dos projetos mais difíceis que já fiz
    O artigo do Raft é fácil de ler e dá uma boa intuição
    Mesmo que você não implemente diretamente, é bem provável que já use software baseado em Raft, como etcd, Consul, CockroachDB ou TiDB
    Reuni aqui os materiais que foram úteis durante a implementação: https://github.com/eatonphil/goraft#references
    Inclui também a tese de doutorado de Diego Ongaro e a especificação em TLA+
    Há quem diga que “a Figure 2 do artigo do Raft é suficiente”, mas, comparada à especificação em TLA+, ela é muito mais ambígua, então não acho que seja verdade

    • Parece excelente, mas sem uma suíte de testes realmente abrangente, inevitavelmente haverá muitos bugs sutis
      Recomendo conectar isso aos testes de Raft do curso de sistemas distribuídos do MIT: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
      Pelo menos para eleição de líder e replicação de logs, parece possível com apenas um pouco de refatoração
    • Em uma disciplina de programação de redes na graduação, tive que implementar Raft, e tive a mesma experiência de que o artigo é fácil de ler
      É especialmente recomendável para quem está tendo o primeiro contato com algoritmos distribuídos
      A qualidade da implementação não deve ser grande coisa, mas deixei publicado para quem tiver interesse: https://github.com/skowalak/fastapi-raft/
    • A Figure 2 é ótima, mas concordo que, para implementar Raft, é preciso o artigo inteiro
      Há mais alguns detalhes concretos necessários para a implementação dentro do artigo

  • Se você se interessa por algoritmos de consenso, também vale conferir o livro Reasoning about Knowledge, que usei em uma disciplina de teoria de sistemas distribuídos: https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...
    É preciso um certo investimento para aprender lógica modal, mas, depois de passar por essa parte, as provas de por que Raft ou Paxos funcionam ficam muito intuitivas e simples
    É uma forma de empurrar a complexidade da prova para dentro da estrutura lógica usada nela, e mudou minha maneira de enxergar consenso

  • “Raft Consensus Algorithm Failure”, Théodore Géricault, 1819: https://classicprogrammerpaintings.com/post/6141087496359280...

    • Raft tem uma prova em TLA+, então deveria “não ter bugs”; sei que é piada, mas fico curioso se há de fato algum erro

  • Se você não sabe o que a visualização está mostrando, basta notar que é possível clicar em um nó para fazê-lo falhar
    Vale especialmente fazer isso no nó que atualmente é o líder, aquele que envia e recebe todos os pacotes
    Ao clicar no pequeno ícone de pausa ao lado do primeiro controle deslizante para transformá-lo de volta em relógio, a simulação é retomada
    Ainda não sei o que é a planilha à direita; ela está sempre vazia, então parece quebrada
    Os elementos clicáveis que encontrei até agora são os dois controles deslizantes, o ícone de relógio/pausa e os servidores individuais

    • A tabela à direita mostra o estado do log de cada réplica
      Ao clicar no líder e selecionar request, você pode simular o envio de um comando
      Se colocar uma réplica offline, dá para vê-la ficar para trás e depois alcançar as outras quando voltar

  • Alguns anos atrás, eu estava em um ambiente em que um sistema parecido com o Chubby robusto sob carga severa era sempre importante e, naquela época, quando falha não era aceitável, usava-se ZooKeeper
    Mas hoje entendo que as pessoas vêm colocando, há anos, cargas muito pesadas em opções baseadas em Raft como etcd e Consul
    Fico curioso se uma delas já virou a escolha padrão
    A clareza conceitual e a elegância do Raft parecem propensas a se traduzir em desempenho e confiabilidade, mas minha noção dessa área está desatualizada
    Em 2023, fico curioso sobre o que pessoas que não estão presas ao Google ou ao GCP usam como prática recomendada padrão em sistemas de alta criticidade
    Acho que havia uma implementação de Raft em Rust pronta para produção feita pelo pessoal do TiKV, e um servidor de locks robusto e de alto desempenho parece ser uma área que combina bem com Rust; também fico curioso se isso está sendo usado de fato

  • Se esta é a resposta para “O que é Raft?”, depois de ler ainda continuo sem saber
    “Raft é um algoritmo de consenso projetado para ser fácil de entender. Ele é equivalente ao Paxos em tolerância a falhas e desempenho. A diferença é que ele é decomposto em subproblemas relativamente independentes e trata de forma limpa as principais partes necessárias em sistemas práticos. Esperamos que o Raft torne o consenso acessível a um público mais amplo e que esse público possa construir uma variedade maior de sistemas de alta qualidade baseados em consenso do que hoje”
    Esse tipo de coisa não é um problema só deles, mas acho uma pena não dedicarem mais tempo a explicar direito o próprio trabalho

    • Talvez essa explicação seja, na verdade, uma boa explicação
      Porque ela filtra automaticamente os leitores que não sabem o que ela significa
      Para alguém que está construindo sistemas distribuídos e comparando vários algoritmos de consenso, é uma explicação simples e clara; se não for esse o caso, provavelmente não é um algoritmo relevante para essa pessoa de qualquer forma
      Em geral, algoritmos de consenso tentam resolver o problema de haver réplicas de um armazenamento de dados espalhadas por vários dispositivos físicos e decidir o que fazer quando alguns dispositivos ou conexões falham de alguma maneira
      O motivo de se chamar “consenso” é que, em situações de falha, as máquinas precisam chegar a um acordo sobre que decisão tomar em relação a um pedaço de dados
      Por exemplo, se três servidores estão replicando o mesmo banco de dados SQL em uma forma (A) - (B) - (C), quando a conexão de rede entre C e os outros dois cai, A e B podem perceber isso e promover B a nó primário
      Mas C não sabe o que aconteceu e pode continuar recebendo algumas escritas
      Quando a conexão é restaurada, A, B e C agora precisam decidir o que fazer
      Como B e C receberam independentemente conjuntos diferentes de escritas, os servidores precisam concordar sobre como tratar os dados
      É exatamente esse o problema que Raft, Paxos e outros tentam resolver de maneira consistente e com bom desempenho
    • Fico curioso se você leu até o parágrafo seguinte, “Espere, o que é consenso?”
      Alguns conceitos são grandes demais para serem apresentados em um único parágrafo a alguém sem nenhum conhecimento prévio
      Ainda assim, acho que o texto linkado é um excelente material introdutório se você continuar lendo

  • Como pesquisador de protocolos de consenso, acho que, graças à pesquisa em blockchain da última década, consenso ficou muito mais fácil de entender
    Raft, especialmente incluindo as partes sutis, em comparação parece e é implementado como grego
    Se alguém estivesse aprendendo protocolos de consenso pela primeira vez hoje, eu faria começar por Bitcoin e depois passar para Paxos, Tendermint e Simplex, e provavelmente pularia Raft completamente
    Simplex é um artigo meu, uma versão simplificada do PBFT

    • Não sou pesquisador de protocolos de consenso, mas blockchain parece trazer muitos elementos adicionais, complexidade e custo
      Raft parece relativamente simples
      Fico curioso sobre o que blockchain oferece que seja mais fácil de manter e menos propenso a erros do que “eleger um líder e replicar um log”

  • Gosto deste site
    Esta página foi realmente útil quando aprendi e implementei Raft em uma disciplina de sistemas distribuídos
    O próprio artigo também é bem fácil de ler

    • Dou aula de sistemas distribuídos e uso este site como uma das referências
      Obrigado por tornar o Raft tão claro

  • Fico curioso se existem algoritmos de consenso em que uma alteração não precise necessariamente passar pelo líder
    Em muitos sistemas distribuídos, também se quer distribuir o processamento das entradas

    • Existem algoritmos que priorizam alta tolerância a falhas e, para isso, aumentam o número de líderes ou o número mínimo de nós que precisam manter cópias dos dados consultados
      Um deles é o Chord: https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)
      O Chord é um anel P2P em que os nós dividem os valores por hashing consistente
      A rede usa algo chamado “finger table”, que essencialmente armazena informações de replicação em formato de tabela
      As informações dessa tabela podem estar erradas ou desatualizadas, e o peer acessado pode indicar outro peer, normalmente o próximo nó ou um nó sucessor, para que a busca continue até encontrar ou não encontrar o valor
      A razão pela qual esse algoritmo pode ser usado sem um “líder” é que ele funciona até mesmo indo simplesmente a um nó e varrendo todos os nós de forma linear
      A finger table para acelerar consultas não é obrigatória
    • Na literatura, existem protocolos sem líder: EPaxos, Caesar, Tempo etc.
      Esses sistemas normalmente têm um “líder” por transação, mas em operação normal esse papel não é disputado
      O coordenador da transação se declara por conta própria, então só há eleição quando o coordenador falha por algum motivo
      Também pode haver vários líderes simultaneamente para determinados dados ou chaves
      O Cassandra está atualmente desenvolvendo o Accord, um protocolo sem líder dessa família
      Na verdade, o Cassandra já usa um protocolo sem líder em LWT
      É uma variante otimizada do Paxos clássico de consenso único, mas o overhead é considerável quando transações concorrentes para a mesma chave são declaradas ao mesmo tempo
    • Eleger um líder e enviar as alterações por meio dele simplifica o sistema e melhora a vazão e a previsibilidade quando há contenção
      Se as transações estiverem distribuídas por tópicos independentes, é possível fazer sharding dos líderes para distribuir a carga
      A ideia é atribuir faixas do espaço de chaves a líderes diferentes e coordenar as eleições para que cada nó tenha sua parcela adequada de liderança
      Para seguir sem líder, cada escrita pode ser estruturada, na prática, como uma eleição
      No caso de transações provisórias ou transações grandes, a solicitação de transação é transmitida por broadcast para todos os nós e, ao obter um quórum de aceitação, ela vence e faz o commit
      Mas, se vários nós tentarem transações quase ao mesmo tempo, chegar a um consenso pode levar bastante tempo
      Se houver muitos nós e todos tiverem transações pendentes sobre o mesmo tópico, eleger um líder e enviar todas as transações por meio dele é muito mais rápido do que estabelecer um consenso separado para cada transação
    • O Paxos não favorece nenhum nó em relação aos outros
      Porém, se o objetivo é distribuir para ganhar vazão, uma abordagem que precise de apenas um líder, em vez do quórum exigido pelo Paxos, pode ser mais eficiente
      É só uma hipótese
      O Paxos também é mais eficiente quando as chamadas vão sempre para o mesmo lugar
      Isso porque evita contenção, novas votações etc.
    • Também existe a abordagem de usar Paxos por shard e um shardmaster
      Essencialmente, cada shard tem seu próprio consenso Paxos