Cinq étudiants et trois magasins de valeurs clés distribués

Ou comme nous avons écrit la bibliothèque cliente C ++ pour ZooKeeper, etcd et Consul KV

Dans le monde des systèmes distribués, il existe un certain nombre de tâches typiques: stocker des informations sur la composition du cluster, gérer la configuration des nœuds, détecter les nœuds défaillants, choisir un leader, etc. Pour résoudre ces problèmes, des systèmes distribués spéciaux ont été créés - des services de coordination. Nous allons maintenant nous intéresser à trois d'entre eux: ZooKeeper, etcd et Consul. De toutes les riches fonctionnalités de Consul, nous nous concentrerons sur Consul KV.



En fait, tous ces systèmes sont des magasins de valeurs-clés linéarisés à tolérance de pannes. Bien que leurs modèles de données présentent des différences importantes, dont nous parlerons plus loin, ils nous permettent de résoudre les mêmes problèmes pratiques. De toute évidence, chaque application qui utilise le service de coordination est liée à l'une d'entre elles, ce qui peut entraîner la nécessité de prendre en charge plusieurs systèmes qui résolvent les mêmes tâches dans un centre de données pour différentes applications.

L'idée, conçue pour résoudre ce problème, est venue d'une agence de conseil australienne, et nous, une petite équipe d'étudiants, avons dû la mettre en œuvre, dont je vais vous parler.

Nous avons pu créer une bibliothèque qui fournit une interface commune pour travailler avec ZooKeeper, etcd et Consul KV. La bibliothèque est écrite en C ++, mais il est prévu de la porter vers d'autres langages.

Modèles de données

Pour développer une interface commune pour trois systèmes différents, vous devez comprendre ce qu'ils ont en commun et en quoi ils diffèrent. Faisons les choses correctement.

Zookeeper



Les clés sont organisées en arborescence et sont appelées nœuds (znodes). En conséquence, pour le site, vous pouvez obtenir une liste de ses enfants. Les opérations de création de znode (création) et de modification de la valeur (setData) sont distinctes: seules les clés existantes peuvent lire et modifier les valeurs. Les montres peuvent être associées à des opérations de vérification de l'existence d'un nœud, de lecture d'une valeur et d'obtention d'enfants. Watch est un déclencheur unique qui se déclenche lorsque la version des données correspondantes sur le serveur change. Les nœuds éphémères sont utilisés pour détecter les défaillances. Ils sont attachés à la session du client qui les a créés. Lorsqu'un client ferme une session ou cesse de notifier ZooKeeper de son existence, ces nœuds sont automatiquement supprimés. Les transactions simples sont prises en charge - un ensemble d'opérations qui réussissent ou échouent toutes, si au moins l'une d'entre elles est impossible.

etcd



Les développeurs de ce système se sont clairement inspirés de ZooKeeper et ont donc tout fait différemment. La hiérarchie des clés n'est pas là, mais elles forment un ensemble lexicographiquement ordonné. Vous pouvez obtenir ou supprimer toutes les clés appartenant à une certaine plage. Une telle structure peut sembler étrange, mais en fait, elle est très expressive, et la vue hiérarchique à travers elle est facilement émulée.

Il n'y a pas d'opération de comparaison et de définition standard dans etcd, mais il y a quelque chose de mieux - les transactions. Bien sûr, ils sont dans les trois systèmes, mais dans etcd, les transactions sont particulièrement bonnes. Ils se composent de trois blocs: vérification, succès, échec. Le premier bloc contient un ensemble de conditions, les deuxième et troisième - opérations. Une transaction est effectuée atomiquement. Si toutes les conditions sont remplies, le bloc de réussite est exécuté, sinon - échec. Dans l'API version 3.3, les blocs de réussite et d'échec peuvent contenir des transactions imbriquées. Autrement dit, il est possible d'exécuter atomiquement des constructions conditionnelles d'un niveau d'imbrication presque arbitraire. Vous pouvez en savoir plus sur les contrôles et les opérations qui existent dans la documentation .

Les montres existent également ici, bien qu'elles soient un peu plus complexes et réutilisables. Autrement dit, après avoir installé la montre sur une plage de clés, vous recevrez toutes les mises à jour de cette plage jusqu'à ce que vous annuliez la montre, et pas seulement la première. Dans etcd, les baux sont équivalents aux sessions client ZooKeeper.

Consul KV

Il n'y a pas non plus de structure hiérarchique stricte, mais Consul peut créer l'apparence qu'elle existe: vous pouvez recevoir et supprimer toutes les clés avec le préfixe spécifié, c'est-à-dire travailler avec le "sous-arbre" de la clé. Ces requêtes sont appelées récursives. De plus, Consul ne peut sélectionner que les clés qui ne contiennent pas le caractère spécifié après le préfixe, ce qui correspond à la réception immédiate des «enfants». Mais il convient de rappeler que c'est précisément l'apparence d'une structure hiérarchique: il est tout à fait possible de créer une clé si son parent n'existe pas ou de supprimer une clé qui a des enfants, tandis que les enfants continueront d'être stockés dans le système.


Au lieu de montres, il y a des requêtes HTTP bloquantes dans Consul. Il s'agit essentiellement d'appels ordinaires à la méthode de lecture des données, pour lesquels, avec d'autres paramètres, la dernière version connue des données est indiquée. Si la version actuelle des données correspondantes sur le serveur est supérieure à celle spécifiée, la réponse est renvoyée immédiatement, sinon, lorsque la valeur change. Il existe également des sessions qui peuvent être attachées à des clés à tout moment. Il convient de noter que contrairement à etcd et ZooKeeper, où la suppression de sessions entraîne la suppression des clés associées, il existe un mode où la session est simplement détachée d'eux. Les transactions sont disponibles, sans branchement, mais avec toutes sortes de chèques.

Rassemblez tout

ZooKeeper est le modèle de données le plus rigoureux. Les demandes de plage expressive disponibles dans etcd ne peuvent pas être émulées efficacement dans ZooKeeper ou Consul. En essayant de tirer le meilleur parti de tous les services, nous avons obtenu une interface presque équivalente à l'interface ZooKeeper avec les exceptions importantes suivantes:

• les nœuds de séquence, de conteneur et TTL ne sont pas pris en charge
• Les listes de contrôle d'accès ne sont pas prises en charge
• La méthode set crée une clé si elle n'existait pas (dans ZK setData renvoie une erreur dans ce cas)
• Les méthodes set et cas sont distinctes (en ZK, elles sont essentiellement la même chose)
• La méthode d'effacement supprime le sommet avec le sous-arbre (dans ZK, la suppression renvoie une erreur si le sommet a des enfants)
• pour chaque clé, il n'y a qu'une seule version - la version de la valeur (dans ZK il y en a trois )

Le rejet des nœuds séquentiels est dû au fait que dans etcd et Consul, il n'y a pas de support intégré pour eux, et au-dessus de l'interface de bibliothèque résultante, ils peuvent être facilement implémentés par l'utilisateur.

L'implémentation du même comportement lors de la suppression du ZooKeeper supérieur nécessiterait de maintenir un compteur d'enfants séparé dans etcd et Consul pour chaque clé. Comme nous avons essayé d'éviter de stocker des méta-informations, il a été décidé de supprimer l'intégralité du sous-arbre.

Subtilités de mise en œuvre

Examinons plus en détail certains aspects de la mise en œuvre de l'interface de bibliothèque dans différents systèmes.

Hiérarchie dans etcd

Le maintien d'une vue hiérarchique dans etcd a été l'une des tâches les plus intéressantes. Les demandes de plage facilitent l'obtention d'une liste de clés avec un préfixe spécifié. Par exemple, si vous voulez que tout ce qui commence par "/foo" , vous demandez la plage ["/foo", "/fop") . Mais cela retournerait le sous-arbre entier de la clé, ce qui peut ne pas être acceptable si le sous-arbre est grand. Dans un premier temps, nous avions prévu d'utiliser le mécanisme de conversion de clé implémenté dans zetcd . Il s'agit d'ajouter un octet au début de la clé, égal à la profondeur du nœud dans l'arborescence. Je vais vous donner un exemple.

 "/foo" -> "\u01/foo" "/foo/bar" -> "\u02/foo/bar" 

Ensuite, vous pouvez obtenir tous les enfants immédiats de la clé "/foo" en demandant la plage ["\u02/foo/", "\u02/foo0") . Oui, en ASCII, "0" suit immédiatement "/" .

Mais comment alors supprimer un sommet? Il s'avère que vous devez supprimer toutes les plages du formulaire ["\uXX/foo/", "\uXX/foo0") pour XX de 01 à FF. Et puis nous avons rencontré une limite sur le nombre d'opérations au sein d'une même transaction.

En conséquence, un système de conversion de clé simple a été inventé, qui a permis de mettre en œuvre efficacement à la fois le retrait de la clé et la réception d'une liste d'enfants. Il suffit d'ajouter un symbole spécial avant le dernier jeton. Par exemple:

 "/very" -> "/\u00very" "/very/long" -> "/very/\u00long" "/very/long/path" -> "/very/long/\u00path" 

Ensuite, la suppression de la clé "/very" transforme en suppression de "/\u00very" et de la plage ["/very/", "/very0") , et en obtenant tous les enfants dans une demande de clés de la plage ["/very/\u00", "/very/\u01") .

Supprimer une clé dans ZooKeeper

Comme je l'ai déjà mentionné, dans ZooKeeper, vous ne pouvez pas supprimer un nœud s'il a des enfants. Nous voulons supprimer la clé avec le sous-arbre. Comment être Nous le faisons avec optimisme. Tout d'abord, nous parcourons récursivement le sous-arbre, obtenant les enfants de chaque sommet dans une requête distincte. Ensuite, nous construisons une transaction qui essaie de supprimer tous les nœuds de la sous-arborescence dans le bon ordre. Bien sûr, des changements peuvent survenir entre la lecture d'une sous-arborescence et sa suppression. Dans ce cas, la transaction échouera. De plus, le sous-arbre peut changer pendant le processus de lecture. Une requête pour les enfants du nœud suivant peut renvoyer une erreur si, par exemple, ce sommet a déjà été supprimé. Dans les deux cas, nous répétons à nouveau l'ensemble du processus.

Cette approche rend la suppression d'une clé très inefficace si elle a des enfants, et plus encore si l'application continue de fonctionner avec la sous-arborescence, en supprimant et en créant des clés. Cependant, cela nous a permis de ne pas compliquer la mise en œuvre d'autres méthodes dans etcd et Consul.

situé dans ZooKeeper

Dans ZooKeeper, il existe des méthodes distinctes qui fonctionnent avec la structure arborescente (créer, supprimer, getChildren) et qui fonctionnent avec les données des nœuds (setData, getData). De plus, toutes les méthodes ont des conditions préalables strictes: create renvoie une erreur si le nœud est déjà créé, supprimez ou setData - s'il n'existe pas encore. Nous avions besoin de la méthode set, qui peut être appelée sans penser à la clé.

Une option consiste à appliquer une approche optimiste, comme lors de la suppression. Vérifiez si le nœud existe. S'il existe, appelez setData; sinon, créez. Si la dernière méthode a renvoyé une erreur, répétez encore une fois. La première chose à noter est l'inutilité de vérifier l'existence. Vous pouvez immédiatement appeler create. L'achèvement réussi signifie que le nœud n'existait pas et qu'il a été créé. Sinon, create renverra l'erreur correspondante, après quoi setData doit être appelé. Bien sûr, entre les appels, le sommet peut être supprimé par un appel concurrent et setData renvoie également une erreur. Dans ce cas, vous pouvez tout répéter à nouveau, mais cela en vaut-il la peine?

Si les deux méthodes ont renvoyé une erreur, alors nous savons avec certitude qu'il y a eu une suppression concurrente. Imaginez que cette suppression se soit produite après l'appel de set. Peu importe la valeur que nous essayons d'établir, elle est déjà effacée. Vous pouvez donc supposer que l'ensemble a réussi, même si en fait rien n'a été écrit.

Plus de détails techniques

Dans cette section, nous nous éloignons des systèmes distribués et parlons de codage.
L'une des principales exigences du client était la multiplateforme: sous Linux, MacOS et Windows, au moins un des services doit être pris en charge. Initialement, nous avons effectué le développement uniquement sous Linux et dans d'autres systèmes, nous avons commencé à tester plus tard. Cela a causé beaucoup de problèmes, qui pendant un certain temps on ne savait pas trop comment aborder. En conséquence, les trois services de coordination sont désormais pris en charge sous Linux et MacOS, et uniquement Consul KV sous Windows.

Dès le début, nous avons essayé d'utiliser des bibliothèques prêtes à l'emploi pour accéder aux services. Dans le cas de ZooKeeper, le choix s'est porté sur ZooKeeper C ++ , qui n'a finalement pas pu être compilé sur Windows. Cela n'est cependant pas surprenant: la bibliothèque est positionnée uniquement sous Linux. Pour Consul, ppconsul était la seule option. J'ai dû y ajouter un support pour les sessions et les transactions . Pour etcd, une bibliothèque à part entière qui prend en charge la dernière version du protocole n'a jamais été trouvée, nous avons donc simplement généré un client grpc .

Inspirés par l'interface asynchrone de la bibliothèque ZooKeeper C ++, nous avons décidé d'implémenter également l'interface asynchrone. Dans ZooKeeper C ++, les primitives future / promise sont utilisées pour cela. En STL, malheureusement, ils sont mis en œuvre très modestement. Par exemple, il n'y a pas de méthode then qui applique la fonction passée au résultat futur lorsqu'elle sera disponible. Dans notre cas, une telle méthode est nécessaire pour convertir le résultat au format de notre bibliothèque. Pour contourner ce problème, nous avons dû implémenter notre pool de threads simple, car à la demande du client, nous ne pouvions pas utiliser de bibliothèques tierces lourdes, telles que Boost.

Notre implémentation fonctionne alors comme suit. Une fois appelé, une paire promesse / future supplémentaire est créée. Le nouvel avenir est retourné et celui transféré est placé avec la fonction correspondante et une promesse supplémentaire dans la file d'attente. Un thread du pool sélectionne plusieurs futurs de la file d'attente et les interroge à l'aide de wait_for. Lorsque le résultat devient disponible, la fonction correspondante est appelée et sa valeur de retour est transmise à promise.

Nous avons utilisé le même pool de threads pour exécuter les requêtes vers etcd et Consul. Cela signifie que plusieurs threads différents peuvent fonctionner avec les bibliothèques sous-jacentes. ppconsul n'est pas sûr pour les threads, donc les appels à ce dernier sont protégés par des verrous.
Vous pouvez travailler avec grpc à partir de plusieurs threads, mais il existe des subtilités. Les montres Etcd sont implémentées via des flux grpc. Ce sont des canaux bidirectionnels pour certains types de messages. La bibliothèque crée un flux unique pour toutes les surveillances et un flux unique qui traite les messages entrants. Donc grpc interdit le streaming d'enregistrements parallèles. Cela signifie que lorsque vous initialisez ou supprimez la montre, vous devez attendre que l'envoi de la demande précédente soit terminé avant d'envoyer la suivante. Nous utilisons des variables conditionnelles pour la synchronisation.

Résumé

Voyez par vous-même: liboffkv .

Notre équipe: Raed Romanov , Ivan Glushenkov , Dmitry Kamaldinov , Victor Krapivensky , Vitaly Ivanin .