Eu implementei o algoritmo de consenso Raft (um exemplo emblemático dos algoritmos distribuídos) em Python. É uma implementação bem ruim! Mas também (até certo ponto) correta.
Aqui estão algumas notas que eu compartilharia com qualquer pessoa interessada em encarar um desafio parecido.
Olhando para trás, estes foram os recursos mais úteis para aprender sobre Raft e implementá-lo corretamente.
- O artigo sobre Raft (leia até a seção 5 e consulte bastante a figura 2)
- Guia de Raft para estudantes
- uma das implementações de Raft mais usadas
- clone o repositório, leia por alto
raft.goe troque ideias com um LLM para entender a base de código e as decisões de projeto
- clone o repositório, leia por alto
- A série de artigos do blog de Eli Bendersky
Eu sugeriria passar cerca de uma hora lendo o artigo primeiro e depois esboçar o código de um servidor UDP ou TCP que leia os bytes recebidos e os adicione a um array. Depois, acompanhei a implementação do Eli, adicionando funcionalidades à minha implementação de Raft na mesma ordem.
Depois de colocar para funcionar algo parecido com eleições, comecei a procurar bugs e erros na minha compreensão do algoritmo. Eu alternava entre o guia para estudantes, a Figura 2 do artigo sobre Raft e a minha implementação, pensando com cuidado nos pontos em que minha implementação era igual (ou diferente). Também usei bastante um LLM para revisar esse código, adicionando ao contexto material dos recursos acima.
Repita o processo acima para replicação de logs, persistência etc.
sobre a implementação
Fiz algumas escolhas de projeto para simplificar minha implementação. Sem uma ordem específica:
- cada nó roda e processa mensagens em uma única thread
- usar um "relógio lógico" para acompanhar o "tempo" local no sistema (por exemplo, chamar
tick()e incrementar um contador local a cada nó em vez de usar o tempo do sistema) - "bagunçar" a implementação colocando tudo em um único arquivo, por exemplo, parsing dos dados de rede, armazenamento/persistência, o núcleo do algoritmo Raft e utilitários/comandos para controlar o próprio nó
A escolha 2 parece uma decisão de projeto sólida e correta (relógios lógicos são usados na implementação do etcd). Dá para argumentar que a escolha 3 é melhor para o aprendizado/a didática. É bom ter tudo em um único arquivo para conseguir ver tudo de uma vez, e isso resulta em uma boa implementação que você pode desmontar para ver quais abstrações se encaixam melhor no algoritmo.
A escolha 1 me parece um tanto absurda. Ela simplifica bastante a implementação (você se preocupa menos com deadlocks e atualizações atômicas do estado interno do nó), mas também acaba com algo que não é exatamente Raft. Para uma primeira implementação, isso parece aceitável. O algoritmo já é complexo o suficiente, e acho que você vai preferir gastar seu tempo depurando erros de lógica no núcleo do algoritmo Raft a ficar às voltas com mutexes.
Eu consideraria implementar Raft dessa forma um projeto de ~30 horas. A leitura inicial do artigo sobre Raft e a revisão dos materiais relacionados devem levar algumas horas. Fiz a maior parte da programação em ~3 dias durante as férias, mexendo no código por cerca de 6-8 horas/dia. Ainda tenho algumas coisas para refinar e melhorar (por exemplo, corrigir alguns bugs sutis) na implementação atual, o que talvez leve mais meio dia de trabalho.
No fim das contas, nada mal para entender um dos algoritmos fundamentais que sustenta tanta infraestrutura.