™️ 👷 🤰 Distribution de données dans Apache Ignite 📬 🤐 👌🏻

salut! Ce message est une version légèrement abrégée de ma conférence éponyme lors de la réunion de la communauté Apache Ignite . Vous pouvez regarder la version vidéo complète avec des questions et réponses ici , et télécharger les diapositives ici . Dans le rapport, j'ai essayé de montrer par des exemples comment les données sont distribuées dans Apache Ignite.

Pourquoi avez-vous besoin de distribuer quoi que ce soit

Un historique assez standard du développement de tout système nécessitant le stockage et le traitement de données est la réalisation d'un certain plafond. Soit il y a beaucoup de données et elles ne sont pas physiquement placées sur le périphérique de stockage, soit la charge augmente à un rythme tel qu'un serveur n'est plus en mesure de traiter un tel nombre de demandes. Il y a des cas fréquents où les deux se produisent.

En règle générale, ils parviennent à l'une des deux solutions: soit le partage du stockage existant, soit le passage à une base de données distribuée. Les deux solutions ont un certain nombre de caractéristiques communes, la plus évidente étant l'utilisation de plusieurs nœuds pour travailler avec des données. De plus, de nombreux nœuds que j'appellerai topologie.

Le problème de la distribution des données entre les nœuds de topologie peut être formulé comme un ensemble d'exigences auxquelles notre distribution doit satisfaire:

Un algorithme est nécessaire qui permettra à tous les nœuds de la topologie et des applications clientes de parvenir à la même conclusion sur le ou les nœuds sur lesquels l'objet (ou la clé) se trouve.
Uniformité de distribution. Plus les données sont réparties uniformément entre les nœuds, plus la charge sur ces nœuds sera répartie de manière uniforme. Ici, je fais l'hypothèse que nos nœuds ont approximativement les mêmes ressources.
. , , . , , , .

Atteindre les deux premières exigences est assez facile.

Une approche familière, souvent utilisée lors de l'équilibrage de la charge entre des serveurs fonctionnellement équivalents, divisant le module N, où N est le nombre de nœuds dans la topologie et nous avons une correspondance biunivoque entre le numéro de nœud et son identifiant. Il suffit ensuite de représenter la clé de l'objet sous forme de valeur numérique à l'aide d'une fonction de hachage et de prendre le reste de la division par N de la valeur obtenue.

Le diagramme montre la répartition de 16 clés sur 3 nœuds. On peut voir que cette distribution est uniforme, et l'algorithme d'obtention du nœud pour l'objet est simple et garantit que si tous les nœuds de la topologie utilisent cet algorithme, alors le même résultat sera obtenu pour la même clé et le même N.

Mais que se passe-t-il si nous introduisons le 4e nœud dans la topologie?

Notre fonction a changé, maintenant nous prenons le reste de la division par 4, pas par 3. Et si la fonction a changé, alors la distribution a changé, et beaucoup.

Ici, l'emplacement précédent des objets pour la version précédente de la topologie de trois nœuds est affiché en rouge et la position des objets pour la nouvelle version de la topologie de quatre nœuds est respectivement verte. C'est très similaire aux fichiers diff habituels, mais au lieu de fichiers, nous avons des nœuds.

Il est facile de voir que les données ont été déplacées non seulement vers le nouveau nœud, mais également qu'il y a eu un échange de données entre les nœuds qui étaient déjà dans la topologie. Ceux. nous observons un trafic parasite entre les nœuds et l'exigence d'un changement minimal de distribution n'est pas remplie.

Voici deux façons courantes de résoudre le problème de la distribution des données en tenant compte de ces exigences:

Hachage cohérent
Le plus grand algorithme de poids aléatoire (HRW), également connu sous le nom de hachage Rendezvous.

Ces deux algorithmes sont très simples. Leurs descriptions sur Wikipédia tiennent en plusieurs phrases. Bien qu'il soit difficile de les appeler évidents. Pour ceux qui sont intéressés, je recommande de lire les articles originaux Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web and A Name-BasedMapping Scheme for Rendezvous . Le plus compréhensible, à mon avis, l'idée d'un algorithme de hachage cohérent est véhiculée dans ce cours de Stanford .

Examinons ces algorithmes plus en détail.

Hachage cohérent

L'astuce sous-jacente à l'algorithme de hachage cohérent consiste à mapper les nœuds et les objets stockés sur le même espace d'identifiant. Cela rend nos entités, objets et nœuds apparemment différents comparables.

Pour obtenir un tel mapping, on applique simplement la même fonction de hachage aux clés des objets et aux identifiants des nœuds. Le résultat de la fonction de hachage pour le nœud sera appelé un jeton, cela nous sera utile plus tard.

Nous représentons notre espace identifiant sous la forme d'un cercle, c'est-à-dire nous supposons simplement que la valeur d'identifiant maximale suit immédiatement la valeur d'identifiant minimale.

Maintenant, afin de déterminer sur quel nœud réside l'objet, vous devez obtenir la valeur de la fonction de hachage à partir de sa clé, puis simplement vous déplacer dans le sens des aiguilles d'une montre autour du cercle jusqu'à ce que nous rencontrions le jeton d'un nœud sur le chemin. La direction du mouvement est sans importance, mais elle doit être fixe.

Le mouvement imaginaire dans le sens des aiguilles d'une montre est fonctionnellement équivalent à une recherche binaire dans un tableau trié de jetons de nœud.

Dans le diagramme, chaque secteur d'une couleur particulière reflète l'espace identifiant dont un nœud particulier est responsable.

Si nous ajoutons un nouveau nœud, alors ...

... il divisera l'un des secteurs en deux parties et reprendra complètement les clés correspondantes.

Dans cet exemple, le nœud 3 a repris une partie des clés du nœud 1.

Comme vous pouvez le voir, cette approche donne une distribution assez inégale des objets entre les nœuds, car il dépend fortement des identifiants des nœuds eux-mêmes. Comment cette approche peut-elle être améliorée?

Vous pouvez affecter plusieurs jetons aux nœuds (généralement des centaines). Cela peut être réalisé, par exemple, en introduisant de nombreuses fonctions de hachage pour le nœud (une par jeton) ou en appliquant de manière répétée la même fonction de hachage au jeton obtenu à l'étape précédente. Mais il ne faut pas oublier les collisions. Il ne doit pas y avoir deux nœuds avec le même jeton.

Dans cet exemple, chaque nœud possède 4 jetons.

Quoi d'autre est important à mentionner: si nous voulons garantir la sécurité des données en cas de sortie d'un nœud de la topologie, nous devons stocker les clés sur plusieurs nœuds (ce que l'on appelle des répliques ou des sauvegardes). Dans le cas de l'algorithme de hachage cohérent, les répliques seront les N-1 nœuds suivants sur le cercle, où N est le facteur de réplication. Bien sûr, l'ordre des nœuds doit être déterminé par un jeton spécifique (par exemple, par le premier), car lors de l'utilisation de plusieurs jetons pour chacun d'eux, la disposition des nœuds peut différer. Faites attention au schéma: il n'a pas de schéma clair de répétition des nœuds.

Quant à l'exigence d'un changement minimal de la distribution lors du changement de topologie, elle est satisfaite car l'ordre mutuel des nœuds sur le cercle est inchangé. Ceux. la suppression d'un nœud de la topologie ne changera pas la relation d'ordre entre les nœuds restants.

Hachage de rendez-vous

L'algorithme de hachage Rendezvous semble encore plus simple que le hachage cohérent. L'algorithme est basé sur le même principe d'invariance des relations d'ordre. Mais au lieu de rendre les nœuds et les objets comparables, nous ne faisons que des nœuds pour un objet spécifique. Ceux. nous déterminons la relation d'ordre entre les nœuds pour chaque objet indépendamment.

Encore une fois, le hachage nous aide. Mais maintenant, afin de déterminer le poids du nœud N pour un objet O donné, nous mélangeons l'identifiant de l'objet avec l'identifiant du nœud et prenons le hachage de ce mélange. Après avoir effectué cette opération pour chaque nœud, nous obtenons un ensemble de poids selon lequel nous trions les nœuds.

Le nœud qui s'est avéré être le premier et sera responsable du stockage de l'objet.

Étant donné que tous les nœuds de la topologie utilisent les mêmes données d'entrée, le résultat pour eux sera identique. Ce qui satisfait la première exigence.

Prenons un exemple. Ici, nous avons une relation d'ordre entre trois nœuds pour quatre clés différentes. Le jaune indique le nœud avec le poids le plus élevé, c'est-à-dire le nœud qui sera finalement responsable d'une clé particulière.

Ajoutez un autre nœud à la topologie.

Je l'ai délibérément placé sur la diagonale pour prendre en compte toutes les options possibles. Ici, le nœud 3, affiché en vert, est entré dans la topologie. Par conséquent, la répartition du poids des nœuds pour chacune des clés a changé. Le rouge indique les nœuds qui ont changé leur emplacement dans la liste pour une clé particulière, car les poids de ces nœuds étaient inférieurs au poids du nœud ajouté. Cependant, cette modification n'a affecté qu'une seule des clés, K3.

Dérivons perfidement un nœud d'une topologie.

Encore une fois, les changements n'ont affecté qu'une seule touche, cette fois K1. Les objets restants n'ont pas été affectés. La raison, comme dans le cas du hachage cohérent, est l'invariance de la relation d'ordre entre n'importe quelle paire de nœuds. Ceux. l'exigence d'un changement minimal de distribution est satisfaite et il n'y a pas de trafic parasite entre les nœuds.

La distribution des rendez-vous semble assez bonne et ne nécessite pas de trucs supplémentaires par rapport au hachage cohérent comme les jetons.

Dans le cas où nous voulons prendre en charge la réplication, le nœud suivant de la liste sera le premier réplica de l'objet, le nœud suivant sera le deuxième réplica, etc.

Utilisation du hachage de rendez-vous dans Apache Ignite

La fonction dite d'affinité est responsable de la distribution des données dans Apache Ignite (voir l'interface AffinityFunction ). L'implémentation par défaut est le hachage de rendez-vous (voir la classe RendezvousAffinityFunction ).

La première chose à laquelle vous devez faire attention est qu'Apache Ignite ne mappe pas directement les objets stockés aux nœuds de topologie. Au lieu de cela, un concept supplémentaire est introduit - la partition.

Une partition est un conteneur d'objets et une unité de réplication. De plus, le nombre de partitions pour un cache particulier (il s'agit d'un analogue de la table dans les bases de données familières) est défini au stade de la configuration et ne change pas pendant le cycle de vie du cache.

Ainsi, nous pouvons afficher des objets sur des partitions en utilisant une division modulo efficace, et utiliser le hachage de rendez-vous pour afficher des partitions sur des nœuds.

Parce que le nombre de partitions pour le cache est une constante, alors nous pouvons calculer la distribution de partition par nœuds une fois et mettre en cache le résultat jusqu'à ce que la topologie soit modifiée.

Chaque nœud calcule cette distribution indépendamment, mais sur tous les nœuds avec les mêmes données d'entrée, cette distribution sera identique.

La partition peut avoir plusieurs copies, nous les appelons des sauvegardes. La partition principale est appelée la partition principale.

Pour la meilleure répartition des clés entre les partitions et les partitions par nœuds, la règle suivante doit être respectée: le nombre de partitions doit être considérablement supérieur au nombre de nœuds, à son tour, le nombre de clés doit être considérablement supérieur au nombre de partitions.

Les caches dans Ignite sont partitionnés et répliqués.

Dans un cache partitionné, le nombre de sauvegardes est défini lors de la création du cache. Les partitions - primaires et sauvegardes - sont réparties uniformément entre les nœuds. Un tel cache est le mieux adapté pour travailler avec des données opérationnelles, comme fournit les meilleures performances d'écriture, qui dépendent directement du nombre de sauvegardes. En général, plus il y a de sauvegardes, plus les nœuds doivent confirmer l'enregistrement de clé.

Dans cet exemple, le cache a une sauvegarde. Ceux. nous pouvons perdre un nœud et ne pas perdre de données, car Les sauvegardes de partition ne sont jamais stockées sur le même nœud que la partition principale ou son autre sauvegarde.

Dans le cache répliqué, le nombre de sauvegardes est toujours égal au nombre de nœuds de topologie moins 1. Autrement dit, chaque nœud contient toujours des copies de toutes les partitions.

Un tel cache est le mieux adapté pour travailler avec des données rarement modifiées (par exemple, des répertoires) et offre la plus grande disponibilité, car nous pouvons perdre N-1 nœuds (dans ce cas 3) sans perdre de données. Toujours dans cette option, nous obtiendrons des performances de lecture maximales si nous permettons de lire les données à la fois des partitions principales et des sauvegardes.

Colocation de données dans Apache Ignite

La collocation est un concept important à garder à l'esprit pour de meilleures performances. La colocation est le placement de tout objet au même endroit. Dans notre cas, les objets sont des entités stockées dans le cache et un lieu est un nœud.

Si les objets sont distribués par des partitions de la même fonction d'affinité, il est logique que les objets avec la même clé d'affinité tombent dans la même partition, et donc sur le même nœud. Dans Ignite, cela s'appelle la colocation par affinité.

Par défaut, une clé d'affinité est la clé primaire d'un objet. Mais dans Ignite, vous pouvez utiliser n'importe quel autre champ d'un objet comme clé d'affinité.

La collocation réduit considérablement la quantité de données envoyées entre les nœuds pour effectuer des calculs ou des requêtes SQL, ce qui entraîne naturellement une réduction du temps consacré à ces tâches. Considérez ce concept par l'exemple.

Soit notre modèle de données composé de deux entités: ordre (Order) et position de l'ordre (OrderItem). Une commande peut correspondre à de nombreux articles. Les identifiants de commande et d'élément de campagne sont indépendants, mais l'élément de campagne possède une clé étrangère qui fait référence à la commande correspondante.

Supposons que nous devons effectuer une tâche qui, pour chaque commande, doit effectuer des calculs pour les positions de cette commande.

Par défaut, une clé d'affinité est une clé primaire. Par conséquent, les ordres et les positions seront répartis entre les nœuds conformément à leurs clés primaires, qui, je le rappelle, sont indépendantes.

Sur le diagramme, les ordres sont représentés par des carrés et des positions en cercles. La couleur indique que l'article appartient à la commande.

Avec cette distribution de données, notre tâche hypothétique sera envoyée au nœud où se trouve l'ordre souhaité, puis elle devra lire les positions de tous les autres nœuds, ou envoyer une sous-tâche à ces nœuds et obtenir le résultat du calcul. Il s'agit d'une interaction réseau inutile qui peut et doit être évitée.

Et si nous disons à Ignite que les articles de la commande doivent être placés sur les mêmes nœuds que les commandes elles-mêmes, c'est-à-dire collecter des données?

Comme clé d'affinité pour la position, nous prendrons la clé étrangère OrderId et ce champ sera utilisé lors du calcul de la partition à laquelle appartient l'enregistrement. De plus, à l'intérieur de la partition, nous pouvons toujours trouver notre objet par la clé primaire.

Maintenant, si les deux caches (Order et OrderItem) utilisent la même fonction d'affinité avec les mêmes paramètres, nos données seront à proximité et nous n'aurons pas besoin de faire le tour du réseau pour les articles commandés.

Configuration d'affinité dans Apache Ignite

Dans l'implémentation actuelle, un objet de fonction d'affinité est un paramètre de configuration de cache.

La fonction d'affinité elle-même prend les arguments suivants lors de la création:

Nombre de partitions;
Le nombre de sauvegardes (en fait, c'est aussi le paramètre de configuration du cache);
Filtre de sauvegarde;
Flag excludeNeighbors.

Ces paramètres ne peuvent pas être modifiés.

Avec le nombre de partitions et de sauvegardes, tout semble clair. Je parlerai du filtre de sauvegarde et du drapeau excludeNeighbors un peu plus tard.

Au moment de l'exécution, la fonction d'affinité d'entrée reçoit la topologie de cluster actuelle - essentiellement une liste de nœuds de cluster - et calcule la distribution de partition par nœuds selon les exemples que j'ai montrés lorsque j'ai parlé de l'algorithme de hachage de rendez-vous.

Quant au filtre de sauvegarde, il s'agit d'un prédicat qui vous permet d'interdire aux fonctions d'affinité d'affecter des partitions de sauvegarde à un nœud pour lequel le prédicat a renvoyé false.

Par exemple, supposons que nos nœuds physiques - serveurs - sont situés dans le centre de données dans des racks différents. En règle générale, chaque rack a sa propre alimentation indépendante ...

... et si nous perdons le rack, nous perdons les données.

Dans cet exemple, nous avons perdu la moitié des partitions.

Mais si nous définissons le bon filtre de sauvegarde, la distribution changera de telle manière ...

... que si le rack est perdu, les données ne seront pas perdues et elles seront toujours disponibles.

L'indicateur excludeNeighbors remplit une fonction similaire, et en fait c'est une abréviation pour un cas spécifique.

Souvent, plusieurs nœuds Ignite s'exécutent sur le même hôte physique. Ce cas est très similaire à l'exemple avec des racks dans le centre de données, seulement maintenant nous combattons la perte de données avec la perte de l'hôte, pas les racks.

Le reste est le même. Vous pouvez implémenter ce comportement à l'aide d'un filtre de sauvegarde. Ce drapeau est un héritage historique et pourrait être supprimé dans la prochaine version majeure d'Ignite.

Il semble que j'ai parlé de la fonction d'affinité et de la distribution des données tout ce qu'un développeur utilisant Apache Ignite doit savoir.

En conclusion, regardons un exemple de répartition de 16 partitions selon la topologie de 3 nœuds. Pour plus de simplicité et de clarté, nous pensons que les partitions n'ont pas de sauvegarde.

Je viens de prendre et d'écrire un petit test qui m'a apporté la vraie distribution:

Comme vous pouvez le voir, l'uniformité de la distribution n'est pas idéale. Mais l'erreur sera sensiblement plus faible avec une augmentation du nombre de nœuds et de partitions. La règle principale à respecter est que le nombre de partitions est nettement supérieur au nombre de nœuds. Désormais, dans Ignite, le nombre de partitions par défaut pour un cache partitionné est 1024.

Ajoutez maintenant un nouveau nœud à la topologie.

Une partie des parties s'est déplacée vers lui. Dans le même temps, l'exigence d'un changement minimal de distribution a été observée: le nouveau nœud a reçu une partie des partitions, tandis que les autres nœuds n'ont pas échangé de partitions.

Nous supprimons de la topologie le nœud qui y était présent à l'étape initiale:

maintenant toutes les partitions qui étaient associées au nœud zéro ont été redistribuées vers d'autres nœuds de la topologie, sans violer nos exigences de distribution.

Comme vous pouvez le voir, la solution à des problèmes complexes repose souvent sur des idées assez banales, quoique pas tout à fait évidentes. Les solutions décrites sont utilisées dans la plupart des bases de données distribuées et font du bon travail. Mais ces décisions sont aléatoires et donc l'uniformité de la distribution est loin d'être idéale. L'uniformité peut-elle être améliorée sans sacrifier les performances et autres exigences de distribution? La question reste ouverte.