J’ai implémenté l’algorithme de consensus Raft (l’exemple emblématique des algorithmes distribués) en Python. C’est une implémentation plutôt mauvaise ! Mais aussi (plus ou moins) correcte.
Voici quelques notes que je partagerais avec toute personne qui souhaite relever un défi similaire.
Avec le recul, voici les ressources qui m’ont été les plus utiles pour comprendre Raft et l’implémenter correctement.
- L’article sur Raft (à lire jusqu’à la section 5, en vous référant souvent à la figure 2)
- Guide de Raft pour les étudiants
- l’une des implémentations de Raft les plus utilisées
- clonez le dépôt, parcourez rapidement
raft.goet échangez avec un LLM pour comprendre le code et les choix de conception
- clonez le dépôt, parcourez rapidement
- La série d’articles d’Eli Bendersky
Je conseillerais de passer d’abord une heure environ à lire l’article, puis d’ébaucher le code d’un serveur UDP ou TCP qui lit les octets reçus et les ajoute à un tableau. J’ai ensuite suivi l’implémentation d’Eli, en ajoutant des fonctionnalités à mon implémentation de Raft dans le même ordre.
Après avoir réussi à faire fonctionner quelque chose qui ressemble à des élections, j’ai commencé à chercher des bugs et des erreurs dans ma compréhension de l’algorithme. Je faisais des allers-retours entre le guide pour les étudiants, la figure 2 de l’article sur Raft et mon implémentation, en examinant attentivement les points sur lesquels mon implémentation correspondait à ces références (ou s’en écartait). J’ai aussi beaucoup utilisé un LLM pour relire ce code, en ajoutant au contexte des éléments tirés des ressources ci-dessus.
Répétez le processus ci-dessus pour la réplication du journal, la persistance, etc.
à propos de l’implémentation
J’ai fait quelques choix de conception simplificateurs dans mon implémentation. Sans ordre particulier :
- chaque nœud s’exécute et traite les messages dans un seul thread
- utiliser une « horloge logique » pour suivre le « temps » local du système (par exemple, appeler
tick()et incrémenter un compteur propre à chaque nœud au lieu d’utiliser l’heure système) - « rendre moins propre » l’implémentation en regroupant tout dans un seul fichier, par exemple l’analyse des données réseau, le stockage/la persistance, le cœur de l’algorithme Raft et les utilitaires/commandes pour contrôler le nœud lui-même
Le choix 2 me semble judicieux et correct (les horloges logiques sont utilisées dans l’implémentation d’etcd). Le choix 3 est sans doute préférable pour l’apprentissage/la pédagogie. C’est agréable d’avoir tout dans un seul fichier pour pouvoir tout voir d’un coup, et cela donne une bonne implémentation que l’on peut remanier de fond en comble pour voir quelles abstractions conviennent le mieux à l’algorithme.
Le choix 1 me paraît un peu aberrant. Cela simplifie beaucoup l’implémentation (on se soucie moins des interblocages et des mises à jour atomiques de l’état interne du nœud), mais on finit aussi avec quelque chose qui n’est pas tout à fait Raft. Pour une première implémentation, cela me semble acceptable. L’algorithme est suffisamment complexe, et je pense que vous préférerez passer votre temps à déboguer les erreurs de logique au cœur de l’algorithme Raft plutôt qu’à vous débattre avec des mutex.
Je considérerais l’implémentation de Raft de cette façon comme un projet d’environ 30 heures. La première lecture de l’article sur Raft et la consultation des ressources associées devraient prendre quelques heures. J’ai fait le gros du travail de programmation en environ 3 jours pendant les vacances, à raison d’environ 6 à 8 heures de code par jour. Il me reste encore quelques points à peaufiner et à améliorer (par exemple, corriger quelques bugs subtils) dans l’implémentation existante, ce qui pourrait représenter une autre demi-journée de travail.
Au total, ce n’est pas si mal pour comprendre l’un des algorithmes fondamentaux qui font tourner tant d’infrastructures.