Le hachage cohérent est une technique de hachage qui se comporte vraiment bien lorsqu’elle est exploitée dans un environnement dynamique où le système distribué augmente et diminue fréquemment. Le concept de base du hachage cohérent a été présenté dans l’article Consistent Hashing and RandomTrees : Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, mais il a gagné en popularité après le célèbre article présentant DynamoDB – Dynamo : Amazon’s Highly Available Key-value Store. Depuis lors, le hachage cohérent a gagné en popularité et a trouvé une tonne de cas d’utilisation dans la conception et la mise à l’échelle efficace des systèmes distribués. Les deux exemples célèbres qui utilisent cette technique de manière exhaustive sont Bit Torrent, pour ses réseaux peer-to-peer, et Akamai, pour ses caches web. Dans cet article, nous plongeons profondément dans le besoin de Consistent Hashing, les internes de celui-ci, et plus important encore le long du chemin l’implémenter en utilisant des tableaux et la recherche binaire.

Avant de sauter dans la technique de base de Consistent Hashing, nous devons d’abord clarifier quelques choses, dont l’une est les fonctions de hachage. Les fonctions de hachage sont toutes les fonctions qui mappent la valeur d’un domaine de taille arbitraire à un autre domaine de taille fixe, généralement appelé l’espace de hachage. Par exemple, la mise en correspondance d’URL avec des entiers de 32 bits ou du contenu HTML de pages Web avec une chaîne de 256 octets. Les valeurs générées en sortie de ces fonctions de hachage sont généralement utilisées comme clés pour permettre des recherches efficaces de l’entité originale.

Un exemple de fonction de hachage simple est une fonction qui mappe un entier de 32 bits dans un espace de hachage d’entier de 8 bits. La fonction pourrait être mise en œuvre en utilisant l’opérateur arithmétique modulo et nous pouvons y parvenir en prenant un modulo 256 qui donne des nombres dans la plage prenant 8-bits pour sa représentation. Une fonction de hachage, qui fait correspondre les clés à un tel domaine d’entiers, applique le plus souvent le modulo N de manière à restreindre les valeurs, ou l’espace de hachage, à une plage .

Une bonne fonction de hachage a les propriétés suivantes

• La fonction est efficace du point de vue du calcul et les valeurs générées sont faciles à consulter
• La fonction, pour la plupart des cas d’utilisation générale, se comporte comme un générateur pseudo-aléatoire qui répartit les données uniformément sans corrélation notable

Maintenant que nous avons vu ce qu’est une fonction de hachage, nous jetons un coup d’œil sur la façon dont nous pourrions les utiliser et construire un système distribué quelque peu évolutif.

Construire un système de stockage distribué

Disons que nous construisons un système de stockage distribué dans lequel les utilisateurs peuvent télécharger des fichiers et y accéder à la demande. Le service expose les API suivantes aux utilisateurs

• upload pour télécharger le fichier
• fetch pour récupérer le fichier et retourner son contenu

Dans les coulisses, le système a des nœuds de stockage sur lesquels les fichiers sont stockés et accessibles. Ces nœuds exposent les fonctions put_file et fetch_file qui mettent et obtiennent le contenu du fichier vers/depuis le disque et envoient la réponse au serveur API principal qui, à son tour, la renvoie à l’utilisateur.

Pour soutenir la charge initiale, le système a 5 nœuds de stockage qui stockent les fichiers téléchargés de manière distribuée. Le fait d’avoir plusieurs nœuds permet de s’assurer que le système, dans son ensemble, n’est pas submergé, et que le stockage est distribué presque uniformément à travers.

Lorsque l’utilisateur invoque la fonction upload avec le chemin du fichier, le système doit d’abord identifier le nœud de stockage qui sera responsable de la détention du fichier et nous le faisons en appliquant une fonction de hachage au chemin et en obtenant à son tour l’index du nœud de stockage. Une fois le nœud de stockage obtenu, nous lisons le contenu du fichier et plaçons ce fichier sur le nœud en invoquant la fonction put_file du nœud.

# storage_nodes holding instances of actual storage node objectsstorage_nodes = def hash_fn(key): """The function sums the bytes present in the `key` and then take a mod with 5. This hash function thus generates output in the range . """ return sum(bytearray(key.encode('utf-8'))) % 5def upload(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we put the file on the node and return return node.put_file(path)def fetch(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we fetch the file from the node and return return node.fetch_file(path)

La fonction de hachage utilisée ici additionne simplement les octets et prend le modulo par 5 (puisqu’il y a 5 nœuds de stockage dans le système) et génère ainsi la sortie dans l’espace de hachage . Cette valeur de sortie représente maintenant l’index du moteur de stockage qui sera responsable de la rétention du fichier.

Disons que nous avons 5 fichiers ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ si nous appliquons la fonction de hachage à ceux-ci, nous trouvons qu’ils sont stockés sur les nœuds de stockage E, A, B, C et D respectivement.

Les choses deviennent intéressantes lorsque le système gagne un peu de traction et qu’il doit être mis à l’échelle à 7 nœuds, ce qui signifie maintenant que la fonction de hachage devrait faire mod 7 au lieu d’un mod 5. Changer la fonction de hachage implique de modifier le mappage et l’association des fichiers avec les nœuds de stockage. Nous devons d’abord administrer les nouvelles associations et voir quels fichiers ont dû être déplacés d’un nœud à l’autre.

Avec la nouvelle fonction de hachage, les mêmes 5 fichiers ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ seront maintenant associés aux nœuds de stockage D, E, F, G, A. Ici, nous voyons que le changement de la fonction de hachage nous oblige à déplacer chacun des 5 fichiers vers un nœud différent.

Si nous devons changer la fonction de hachage chaque fois que nous augmentons ou diminuons l’échelle et si cela nous oblige à déplacer non pas toutes mais même la moitié des données, le processus devient super coûteux et à plus long terme infaisable. Nous avons donc besoin d’un moyen de minimiser le mouvement de données requis lors des scale-ups ou scale-downs, et c’est là que le Consistent Hashing entre en jeu et minimise le transfert de données requis.

Consistent Hashing

Le principal point douloureux du système ci-dessus est qu’il est sujet à des événements comme les scale-ups et les scale-downs car il nécessite beaucoup de modifications dans les associations. Ces associations sont purement pilotées par la fonction de hachage sous-jacente et donc si nous pouvions d’une manière ou d’une autre rendre cette fonction de hachage indépendante du nombre de nœuds de stockage dans le système, nous remédions à ce défaut.

Le hachage cohérent remédie à cette situation en gardant l’espace de hachage énorme et constant, quelque part dans l’ordre de et le nœud de stockage et les objets correspondent tous deux à l’un des emplacements de cet énorme espace de hachage. Contrairement au système traditionnel où le fichier était associé au nœud de stockage à l’indice où il a été haché, dans ce système les chances de collision entre un fichier et un nœud de stockage sont infiniment petites et donc nous avons besoin d’une manière différente pour définir cette association.

Au lieu d’utiliser une approche basée sur la collision, nous définissons l’association comme – le fichier sera associé au nœud de stockage qui est présent à la droite immédiate de son emplacement haché. Définir l’association de cette manière nous aide à

• maintenir la fonction de hachage indépendante du nombre de nœuds de stockage
• maintenir les associations relatives et non pilotées par des collisions absolues

Le hachage cohérent ne nécessite en moyenne que k/n unités de données à migrer pendant la montée et la descente en charge ; où k est le nombre total de clés et n est le nombre de nœuds dans le système.

Une façon très naïve d’implémenter ceci est d’allouer un tableau de taille égale à l’espace de hachage et de mettre les fichiers et le nœud de stockage littéralement dans le tableau sur l’emplacement haché. Afin d’obtenir l’association, nous itérons de l’emplacement haché de l’élément vers la droite et trouvons le premier nœud de stockage. Si nous atteignons la fin du tableau et ne trouvons pas de nœud de stockage, nous retournons à l’index 0 et continuons la recherche. Cette approche est très facile à mettre en œuvre mais souffre des limitations suivantes

• nécessite une mémoire énorme pour contenir un tableau aussi grand
• trouver l’association en itérant chaque fois vers la droite est O(hash_space)

Une meilleure façon de mettre cela en œuvre est d’utiliser deux tableaux : un pour contenir les nœuds de stockage, appelé nodes et un autre pour contenir les positions des nœuds de stockage dans l’espace de hachage, appelé keys. Il existe une correspondance biunivoque entre les deux tableaux – le nœud de stockage nodes est présent à la position keys dans l’espace de hachage. Les deux tableaux sont maintenus triés selon le tableau keys.

Fonction de hachage dans le hachage cohérent

Nous définissons total_slots comme la taille de cet espace de hachage entier, typiquement de l’ordre 2^256 et la fonction de hachage pourrait être implémentée en prenant SHA-256 suivi d’un mod total_slots. Puisque total_slots est énorme et une constante, l’implémentation de la fonction de hachage suivante est indépendante du nombre réel de nœuds de stockage présents dans le système et reste donc non affectée par des événements tels que les scale-ups et scale-downs.

def hash_fn(key: str, total_slots: int) -> int: """hash_fn creates an integer equivalent of a SHA256 hash and takes a modulo with the total number of slots in hash space. """ hsh = hashlib.sha256() # converting data into bytes and passing it to hash function hsh.update(bytes(key.encode('utf-8'))) # converting the HEX digest into equivalent integer value return int(hsh.hexdigest(), 16) % total_slots

Ajout d’un nouveau nœud dans le système

Lorsqu’il y a un besoin de mettre à l’échelle et d’ajouter un nouveau nœud dans le système, dans notre cas un nouveau nœud de stockage, nous

• trouvons la position du nœud où il réside dans l’espace de hachage
• peupler le nouveau nœud avec les données qu’il est censé servir
• ajouter le nœud dans l’espace de hachage

Lorsqu’un nouveau nœud est ajouté dans le système, cela n’affecte que les fichiers qui hachent à l’emplacement à gauche et associés au nœud à droite, de la position dans laquelle le nouveau nœud s’insérera. Tous les autres fichiers et associations ne sont pas affectés, ce qui minimise la quantité de données à migrer et la cartographie à modifier.

D’après l’illustration ci-dessus, nous voyons que lorsqu’un nouveau nœud K est ajouté entre les nœuds B et E, nous changeons les associations des fichiers présents dans le segment B-K et les assignons au nœud K. Les données appartenant au segment B-K pourraient être trouvées au nœud E auquel elles étaient précédemment associées. Ainsi, les seuls fichiers affectés et qui nécessitent une migration sont dans le segment B-K ; et leur association change du nœud E au nœud K.

Pour mettre en œuvre cela à un bas niveau en utilisant le tableau nodes et keys, nous obtenons d’abord la position du nouveau nœud dans l’espace de hachage en utilisant la fonction de hachage. Nous trouvons ensuite l’index de la plus petite clé supérieure à la position dans le tableau keys trié en utilisant la recherche binaire. Cet indice sera l’endroit où la clé et le nouveau nœud de stockage seront placés respectivement dans le tableau keys et nodes.

def add_node(self, node: StorageNode) -> int: """add_node function adds a new node in the system and returns the key from the hash space where it was placed """ # handling error when hash space is full. if len(self._keys) == self.total_slots: raise Exception("hash space is full") key = hash_fn(node.host, self.total_slots) # find the index where the key should be inserted in the keys array # this will be the index where the Storage Node will be added in the # nodes array. index = bisect(self._keys, key) # if we have already seen the key i.e. node already is present # for the same key, we raise Collision Exception if index > 0 and self._keys == key: raise Exception("collision occurred") # Perform data migration # insert the node_id and the key at the same `index` location. # this insertion will keep nodes and keys sorted w.r.t keys. self.nodes.insert(index, node) self._keys.insert(index, key) return key

Suppression d’un nouveau nœud du système

Lorsqu’il est nécessaire de réduire la taille et de supprimer un nœud existant du système, nous

• trouverons la position du nœud à retirer de l’espace de hachage
• peuplerons le nœud à droite avec les données qui étaient associées au nœud à retirer
• retirerons le nœud de l’espace de hachage

Lorsqu’un nœud est retiré du système, cela n’affecte que les fichiers associés au nœud lui-même. Tous les autres fichiers et associations ne sont pas affectés, ce qui minimise la quantité de données à migrer et le mappage nécessaire à modifier.

D’après l’illustration ci-dessus, nous voyons que lorsque le nœud K est supprimé du système, nous changeons les associations des fichiers associés au nœud K vers le nœud qui se trouve à sa droite immédiate c’est-à-dire le nœud E.Ainsi, les seuls fichiers affectés et nécessitant une migration sont ceux associés au noeud K.

Pour mettre en oeuvre ceci à un bas niveau en utilisant le tableau nodes et keys, nous obtenons l’index où le noeud K se trouve dans le tableau keys en utilisant la recherche binaire. Une fois que nous avons l’indice, nous supprimons la clé du tableau keys et le nœud de stockage du tableau nodes présent sur cet indice.

def remove_node(self, node: StorageNode) -> int: """remove_node removes the node and returns the key from the hash space on which the node was placed. """ # handling error when space is empty if len(self._keys) == 0: raise Exception("hash space is empty") key = hash_fn(node.host, self.total_slots) # we find the index where the key would reside in the keys index = bisect_left(self._keys, key) # if key does not exist in the array we raise Exception if index >= len(self._keys) or self._keys != key: raise Exception("node does not exist") # Perform data migration # now that all sanity checks are done we popping the # keys and nodes at the index and thus removing the presence of the node. self._keys.pop(index) self.nodes.pop(index) return key

Associer un élément à un nœud

Maintenant que nous avons vu comment le hachage cohérent aide à garder la migration des données, pendant les scale-ups et les scale-downs, au strict minimum ; il est temps de voir comment nous pouvons efficacement trouver le « nœud à droite » pour un élément donné. L’opération pour trouver l’association doit être super rapide et efficace car c’est quelque chose qui sera invoqué pour chaque lecture et écriture unique qui se produit sur le système.

Pour implémenter cela à bas niveau, nous prenons à nouveau le levier de la recherche binaire et effectuons cette opération dans O(log(n)). Nous passons d’abord l’élément à la fonction de hachage et récupérons la position où l’élément est haché dans l’espace de hachage. Cette position est ensuite recherchée binairement dans le tableau keys pour obtenir l’index de la première clé qui est plus grande que la position (obtenue à partir de la fonction de hachage). s’il n’y a pas de clés plus grandes que la position, dans le tableau keys, nous faisons le tour et retournons le 0e index. L’indice ainsi obtenu sera l’indice du nœud de stockage dans le tableau nodes associé à l’élément.

def assign(self, item: str) -> str: """Given an item, the function returns the node it is associated with. """ key = hash_fn(item, self.total_slots) # we find the first node to the right of this key # if bisect_right returns index which is out of bounds then # we circle back to the first in the array in a circular fashion. index = bisect_right(self._keys, key) % len(self._keys) # return the node present at the index return self.nodes

Le code source avec la mise en œuvre du hachage cohérent en Python pourrait être trouvé à github.com/arpitbbhayani/consistent-hashing.

Conclusion

Le hachage cohérent est l’un des algorithmes les plus importants pour nous aider à mettre à l’échelle horizontalement et à gérer tout système distribué. L’algorithme ne fonctionne pas seulement dans les systèmes sharded mais trouve également son application dans l’équilibrage de charge, le partitionnement des données, la gestion des sessions collantes basées sur le serveur, les algorithmes de routage, et bien d’autres. Un grand nombre de bases de données doivent leur échelle, leurs performances et leur capacité à gérer l’énorme charge à Consistent Hashing.

• Fonctions de hachage – Wikipédia
• Consistent Hashing – Wikipédia
• Consistent Hashing – Stanford
• Consistent Hashing and RandomTrees
• Dynamo : Amazon’s Highly Available Key-value Store

Autres articles qui pourraient vous intéresser :

• Python met en cache des entiers
• Fractional Cascading – Speeding up Binary Searches
• Copy-on-Write Semantics
• What makes MySQL LRU cache scan resistant
• Building Finite State Machines with Python Coroutines

Cet article a été initialement publié sur mon blog – Consistent Hashing.

Si vous avez aimé ce que vous avez lu, abonnez-vous à ma newsletter et recevez le post directement dans votre boîte de réception et donnez-moi un shout-out @arpit_bhayani.

.