He implementado el algoritmo de consenso Raft (el ejemplo por excelencia de los algoritmos distribuidos) en Python. ¡Es una implementación bastante mala! Pero también es (hasta cierto punto) correcta.
Estas son algunas notas que compartiría con cualquiera que tenga interés en afrontar un reto similar.
En retrospectiva, estos fueron los recursos más útiles para aprender sobre Raft e implementarlo correctamente.
- El artículo de Raft (lee hasta la sección 5 y consulta mucho la figura 2)
- Guía de Raft para estudiantes
- una de las implementaciones de Raft más utilizadas
- clona el repositorio, echa un vistazo a
raft.goy conversa con un LLM para entender el código y las decisiones de diseño
- clona el repositorio, echa un vistazo a
- La serie de artículos del blog de Eli Bendersky
Recomendaría dedicar primero una hora más o menos a leer el artículo y después esbozar el código de un servidor UDP o TCP que lea los bytes entrantes y los añada a un array. Después seguí paso a paso la implementación de Eli, añadiendo funcionalidades a mi implementación de Raft en el mismo orden.
Tras conseguir que funcionara algo parecido a unas elecciones, empecé a buscar fallos en el código y errores en mi comprensión del algoritmo. Iba alternando entre la guía para estudiantes, la figura 2 del artículo de Raft y mi implementación, pensando detenidamente en los puntos en los que mi implementación coincidía (o difería). También recurrí mucho a un LLM para revisar este código, añadiendo al contexto material de los recursos anteriores.
Repite el proceso anterior para la replicación del registro, la persistencia, etc.
sobre la implementación
Tomé algunas decisiones de diseño para simplificar mi implementación. Sin ningún orden en particular:
- cada nodo se ejecuta y procesa los mensajes en un único hilo
- usar un "reloj lógico" para llevar la cuenta del "tiempo" local en el sistema (p. ej., llamar a
tick()e incrementar un contador local de cada nodo en lugar de usar la hora del sistema) - "ensuciar" la implementación poniendo todo en un solo archivo, p. ej., el análisis de los mensajes de red, el almacenamiento/persistencia, el núcleo del algoritmo Raft y las utilidades/comandos para controlar el propio nodo
2 parece una decisión de diseño sólida y correcta (los relojes lógicos son los que se usan en la implementación de etcd). 3 puede ser mejor para aprender y enseñar. Resulta cómodo tenerlo todo en un solo archivo para poder verlo a la vez, y te proporciona una buena implementación que puedes desmontar para ver qué abstracciones encajan mejor con el algoritmo.
La opción 1 me parece un tanto disparatada. Sí que simplifica mucho la implementación (te preocupas menos por los interbloqueos y por las actualizaciones atómicas del estado interno del nodo), pero también acabas con algo que no es del todo Raft. Para una primera implementación, esto me parece bien. El algoritmo ya es bastante complejo, y creo que preferirás dedicar el tiempo a depurar errores lógicos en el núcleo del algoritmo Raft que a pelearte con los mutex.
Diría que implementar Raft de esta manera es un proyecto de ~30 horas. La lectura inicial del artículo de Raft y la revisión de los materiales relacionados deberían llevar unas pocas horas. Hice la mayor parte de la programación en ~3 días durante las vacaciones, programando unas 6-8 horas al día. Aún me quedan algunas cosas por pulir y mejorar (p. ej., corregir algunos fallos sutiles) en la implementación actual, lo que podría suponer otro medio día de trabajo.
En conjunto, no está nada mal para entender uno de los algoritmos fundamentales que sustentan tanta infraestructura.