Comprendre la mise en œuvre de Raft par etcd : une plongée approfondie dans le journal de Raft

Introduction

Cet article présentera et analysera la conception et la mise en œuvre du module Raft Log dans Raft d'etcd, à partir du journal dans l'algorithme de consensus Raft. L'objectif est d'aider les lecteurs à mieux comprendre la mise en œuvre de Raft d'etcd et de fournir une approche possible pour mettre en œuvre des scénarios similaires.

Aperçu du journal de radeau

L'algorithme de consensus Raft est essentiellement une machine à états répliquée, dans le but de répliquer une série de journaux de la même manière sur un cluster de serveurs. Ces journaux permettent aux serveurs du cluster d'atteindre un état cohérent.

Dans ce contexte, les logs font référence au Raft Log. Chaque nœud du cluster possède son propre journal Raft, composé d'une série d'entrées de journal. Une entrée de journal contient généralement trois champs :

• Index : L'index de l'entrée du journal
• Terme :Le terme du leader lors de la création de l'entrée de journal
• Données : Les données contenues dans l'entrée du journal, qui peuvent être des commandes spécifiques, etc.

Il est important de noter que l'index du Raft Log commence à 1, et seul le nœud leader peut créer et répliquer le Raft Log vers les nœuds suiveurs.

Lorsqu'une entrée de journal est stockée de manière persistante sur la majorité des nœuds du cluster (par exemple, 2/3, 3/5, 4/7), elle est considérée comme validée.

Lorsqu'une entrée de journal est appliquée à la machine d'état, elle est considérée comme appliquée.

Présentation de l'implémentation du radeau d'etcd

etcd raft est une bibliothèque d'algorithmes Raft écrite en Go, largement utilisée dans des systèmes comme etcd, Kubernetes, CockroachDB et autres.

La principale caractéristique d'etcd raft est qu'il n'implémente que la partie centrale de l'algorithme Raft. Les utilisateurs doivent implémenter eux-mêmes la transmission réseau, le stockage sur disque et les autres composants impliqués dans le processus Raft (bien qu'etcd fournisse des implémentations par défaut).

Interagir avec la bibliothèque raft etcd est assez simple : elle vous indique quelles données doivent être conservées et quels messages doivent être envoyés à d'autres nœuds. Votre responsabilité est de gérer les processus de stockage et de transmission réseau et de l’informer en conséquence. Il ne se préoccupe pas des détails de la manière dont vous mettez en œuvre ces opérations ; il traite simplement les données que vous soumettez et, sur la base de l'algorithme Raft, vous indique les prochaines étapes.

Dans l'implémentation du code d'etcd raft, ce modèle d'interaction est parfaitement combiné avec la fonctionnalité de canal unique de Go, rendant la bibliothèque etcd raft vraiment distinctive.

Comment implémenter le journal de radeau

journal et log_unstable

Dans etcd raft, l'implémentation principale de Raft Log se trouve dans les fichiers log.go et log_unstable.go, les structures principales étant raftLog et unstable. La structure instable est également un champ dans raftLog.

• raftLog est responsable de la logique principale du Raft Log. Il peut accéder à l'état de stockage des journaux du nœud via l'interface de stockage fournie à l'utilisateur.
• unstable, comme son nom l'indique, contient des entrées de journal qui n'ont pas encore été conservées, c'est-à-dire des journaux non validés.

etcd raft gère les journaux au sein de l'algorithme en coordonnant raftLog et unstable.

Champs principaux de raftLog et unstable

Pour simplifier la discussion, cet article se concentrera uniquement sur la logique de traitement des entrées de journal, sans aborder la gestion des instantanés dans etcd raft.

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

Champs principaux de raftLog :

• stockage : Une interface de stockage implémentée par l'utilisateur, utilisée pour récupérer les entrées de journal déjà conservées.
• instable : Stocke les journaux non persistants. Par exemple, lorsque le Leader reçoit une demande d'un client, il crée une entrée de journal avec son terme et l'ajoute aux journaux instables.
• commit : Connu sous le nom de commitIndex dans l'article Raft, il représente l'index de la dernière entrée de journal validée connue.
• application : L'indice le plus élevé d'une entrée de journal actuellement appliquée.
• appliqué : Connu sous le nom de lastApplied dans l'article Raft, il s'agit de l'indice le plus élevé d'une entrée de journal qui a été appliqué à la machine d'état.

type unstable struct {
    entries []pb.Entry
    offset uint64
    offsetInProgress uint64
}

Champs centraux d'instable :

• entrées : Les entrées de journal non persistantes, stockées en mémoire sous forme de tranche.
• décalage : Utilisé pour mapper les entrées du journal dans les entrées du journal Raft, où entrées[i] = Raft Log[i offset].
• offsetInProgress : Indique les entrées actuellement conservées. Les entrées en cours sont représentées par des entrées[:offsetInProgress-offset].

Les champs principaux de raftLog sont simples et peuvent facilement être liés à la mise en œuvre dans l'article Raft. Cependant, les champs instables peuvent sembler plus abstraits. L'exemple suivant vise à aider à clarifier ces concepts.

Supposons que nous ayons déjà 5 entrées de journal persistantes dans notre journal de radeau. Maintenant, nous avons 3 entrées de journal stockées dans unstable, et ces 3 entrées de journal sont actuellement conservées. La situation est la suivante :

offset=6 indique que les entrées du journal aux positions 0, 1 et 2 dans unstable.entries correspondent aux positions 6 (0 6), 7 (1 6) et 8 (2 6) dans le journal du radeau réel. Avec offsetInProgress=9, nous savons que unstable.entries[:9-6], qui inclut les trois entrées de journal aux positions 0, 1 et 2, sont toutes conservées.

La raison pour laquelle offset et offsetInProgress sont utilisés dans unstable est que unstable ne stocke pas toutes les entrées du journal Raft.

Quand interagir

Puisque nous nous concentrons uniquement sur la logique de traitement du journal Raft, « quand interagir » fait ici référence au moment où etcd raft transmettra les entrées de journal qui doivent être conservées par l'utilisateur.

Côté utilisateur

etcd raft interagit avec l'utilisateur principalement via les méthodes de l'interface Node. La méthode Ready renvoie un canal qui permet à l'utilisateur de recevoir des données ou des instructions du raft etcd.

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

La structure Ready reçue de ce canal contient les entrées de journal qui doivent être traitées, les messages qui doivent être envoyés à d'autres nœuds, l'état actuel du nœud, et plus encore.

Pour notre discussion sur Raft Log, nous devons uniquement nous concentrer sur les champs Entries et ComendedEntries :

• Entrées : Entrées de journal qui doivent être conservées. Une fois ces entrées conservées, elles peuvent être récupérées à l'aide de l'interface de stockage.
• ComshedEntries : Entrées de journal qui doivent être appliquées à la machine d'état.

type unstable struct {
    entries []pb.Entry
    offset uint64
    offsetInProgress uint64
}

Après avoir traité les journaux, messages et autres données transmis via Ready, nous pouvons appeler la méthode Advance dans l'interface Node pour informer etcd raft que nous avons terminé ses instructions, lui permettant de recevoir et de traiter le prochain Ready.

etcd raft propose une option AsyncStorageWrites, qui peut améliorer les performances des nœuds dans une certaine mesure. Cependant, nous n'envisageons pas cette option ici.

Côté du radeau, etc.

Du côté de l'utilisateur, l'accent est mis sur la gestion des données dans la structure Ready reçue. Du côté du radeau etcd, l'accent est mis sur la détermination du moment où transmettre une structure Ready à l'utilisateur et des actions à entreprendre par la suite.

J'ai résumé les principales méthodes impliquées dans ce processus dans le schéma suivant, qui montre la séquence générale des appels de méthode (notez que cela ne représente que l'ordre approximatif des appels) :

Vous pouvez voir que l'ensemble du processus est une boucle. Ici, nous décrirons la fonction générale de ces méthodes, et dans l'analyse du flux d'écriture ultérieure, nous examinerons comment ces méthodes fonctionnent sur les champs principaux de raftLog et unstable.

• HasReady : Comme son nom l'indique, il vérifie s'il existe une structure Ready qui doit être transmise à l'utilisateur. Par exemple, s'il existe des entrées de journal non persistantes dans unstable qui ne sont pas actuellement en cours de persistance, HasReady renverra true.
• readyWithoutAccept : Appelée après que HasReady ait renvoyé true, cette méthode crée la structure Ready à renvoyer à l'utilisateur, y compris les entrées de journal qui doivent être conservées et celles marquées comme validées.
• acceptReady : Appelé après que etcd raft ait transmis la structure Ready créée par readyWithoutAccept à l'utilisateur. Il marque les entrées de journal renvoyées dans Ready comme étant en cours de persistance et d'application, et crée un « rappel » à appeler lorsque l'utilisateur appelle Node.Advance, marquant les entrées de journal comme persistantes et appliquées.
• Advance : Exécute le « rappel » créé dans acceptReady après que l'utilisateur appelle Node.Advance.

Comment définir engagé et appliqué

Il y a deux points importants à considérer ici :

1. Persisté ≠ Engagé

Telle que définie initialement, une entrée de journal est considérée comme validée uniquement lorsqu'elle a été conservée par la majorité des nœuds du cluster Raft. Ainsi, même si nous conservons les entrées renvoyées par etcd raft via Ready, ces entrées ne peuvent pas encore être marquées comme validées.

Cependant, lorsque nous appelons la méthode Advance pour informer etcd raft que nous avons terminé l'étape de persistance, etcd raft évaluera l'état de persistance sur les autres nœuds du cluster et marquera certaines entrées de journal comme validées. Ces entrées nous sont ensuite fournies via le champ ComendedEntries de la structure Ready afin que nous puissions les appliquer à la machine à états.

Ainsi, lors de l'utilisation d'etcd raft, le timing de marquage des entrées comme validées est géré en interne et les utilisateurs doivent uniquement remplir les conditions préalables de persistance.

En interne, l'engagement est obtenu en appelant la méthode raftLog.commitTo, qui met à jour raftLog.commit, correspondant au commitIndex dans le document Raft.

2. Engagé ≠ Appliqué

Une fois la méthode raftLog.commitTo appelée dans etcd raft, les entrées de journal jusqu'à l'index raft.commit sont considérées comme validées. Cependant, les entrées dont les indices sont compris dans la plage lastApplied < index <= commitIndex n’a pas encore été appliqué à la machine à états. etcd raft renverra ces entrées validées mais non appliquées dans le champ ComendedEntries de Ready, nous permettant de les appliquer à la machine à états. Une fois que nous appellerons Advance, etcd raft marquera ces entrées comme appliquées.

Le timing de marquage des entrées telles qu'appliquées est également géré en interne dans etcd raft ; les utilisateurs doivent uniquement appliquer les entrées validées de Ready à la machine d'état.

Un autre point subtil est que, dans Raft, seul le Leader peut valider les entrées, mais tous les nœuds peuvent les appliquer.

Flux de traitement d'une demande d'écriture

Ici, nous allons relier tous les concepts évoqués précédemment en analysant le flux de etcd raft lorsqu'il gère une demande d'écriture.

État initial

Pour discuter d'un scénario plus général, nous commencerons par un Raft Log qui a déjà validé et appliqué trois entrées de journal.

Dans l'illustration, vert représente les champs raftLog et les entrées de journal stockées dans Storage, tandis que rouge représente les champs instables et les entrées de journal non persistantes stockées dans les entrées.

Puisque nous avons validé et appliqué trois entrées de journal, les deux entrées de journal validées et appliquées sont définies sur 3. Le champ d'application contient l'index de l'entrée de journal la plus élevée de l'application précédente, qui est également 3 dans ce cas.

À ce stade, aucune requête n'a été initiée, donc unstable.entries est vide. L'index de journal suivant dans le journal Raft est 4, ce qui donne un décalage de 4. Puisqu'aucun journal n'est actuellement conservé, offsetInProgress est également défini sur 4.

Émettre une demande

Maintenant, nous lançons une demande pour ajouter deux entrées de journal au journal du radeau.

Comme le montre l'illustration, les entrées de journal ajoutées sont stockées dans unstable.entries. A ce stade, aucune modification n'est apportée aux valeurs d'index enregistrées dans les champs principaux.

Est prêt

Vous vous souvenez de la méthode HasReady ? HasReady vérifie s'il existe des entrées de journal non persistantes et, si c'est le cas, renvoie true.

La logique pour déterminer la présence d'entrées de journal non persistantes est basée sur le fait que la longueur de unstable.entries[offsetInProgress-offset:] est supérieure à 0. Clairement, dans notre cas :

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

indiquant qu'il existe deux entrées de journal non persistantes, donc HasReady renvoie vrai.

prêtSansAccepter

Le but de readyWithoutAccept est de créer la structure Ready à renvoyer à l'utilisateur. Puisque nous avons deux entrées de journal non persistantes, readyWithoutAccept inclura ces deux entrées de journal dans le champ Entries du Ready renvoyé.

accepterPrêt

acceptReady est appelé une fois la structure Ready transmise à l'utilisateur.

acceptReady met à jour l'index des entrées de journal en cours de persistance à 6, ce qui signifie que les entrées de journal comprises dans la plage [4, 6) sont désormais marquées comme étant persistantes.

Avance

Une fois que l'utilisateur a conservé les entrées dans Ready, il appelle Node.Advance pour avertir etcd raft. Ensuite, etcd raft peut exécuter le "callback" créé dans acceptReady.

Ce "rappel" efface les entrées de journal déjà persistantes dans unstable.entries, puis définit le décalage sur Storage.LastIndex 1, qui est 6.

Valider les entrées du journal

Nous supposons que ces deux entrées de journal ont déjà été conservées par la majorité des nœuds du cluster Raft, nous pouvons donc marquer ces deux entrées de journal comme validées.

Est prêt

Poursuivant notre boucle, HasReady détecte la présence d'entrées de journal validées mais pas encore appliquées, elle renvoie donc true.

prêtSansAccepter

readyWithoutAccept renvoie un Ready contenant les entrées de journal (4, 5) qui sont validées mais n'ont pas été appliquées à la machine à états.

Ces entrées sont calculées comme étant faibles, élevées := appliquant 1, engagées 1, dans un intervalle ouvert à gauche et fermé à droite.

accepterPrêt

acceptReady marque ensuite les entrées de journal [4, 5] renvoyées dans Ready comme étant appliquées à la machine d'état.

Avance

Une fois que l'utilisateur a appelé Node.Advance, etcd, raft exécute le "rappel" et les mises à jour appliquées à 5, indiquant que les entrées de journal à l'index 5 et antérieurs ont toutes été appliquées à la machine d'état.

État final

Ceci termine le flux de traitement d'une demande d'écriture. L'état final est celui indiqué ci-dessous, qui peut être comparé à l'état initial.

Résumé

Nous avons commencé par un aperçu du Raft Log, pour comprendre ses concepts de base, suivi d'un premier aperçu de l'implémentation du raft etcd. Nous avons ensuite approfondi les modules de base de Raft Log dans etcd raft et examiné des questions importantes. Enfin, nous avons tout lié grâce à une analyse complète d’un flux de requêtes d’écriture.

J'espère que cette approche vous aidera à acquérir une compréhension claire de la mise en œuvre du raft etcd et à développer vos propres idées sur le journal du raft.

Cela conclut cet article. S'il y a des erreurs ou des questions, n'hésitez pas à nous contacter par message privé ou à laisser un commentaire.

BTW, raft-foiver est une version simplifiée de etcd raft que j'ai implémentée, conservant toute la logique de base de Raft et optimisée selon le processus décrit dans l'article Raft. Je publierai prochainement un article séparé présentant cette bibliothèque. Si vous êtes intéressé, n'hésitez pas à Star, Fork ou PR !

Référence

• https://github.com/B1NARY-GR0UP/raft
• https://github.com/etcd-io/raft

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!