Qu'est-ce qu'un hachage cohérent

L'algorithme de hachage cohérent a été proposé par le MIT en 1997. Il s'agit d'un algorithme de hachage spécial qui vise à résoudre le problème de la mise en cache distribuée. Lors de la suppression ou de l'ajout d'un serveur, il est possible de modifier légèrement le mappage. entre les demandes de service existantes et les serveurs qui les gèrent.

L'algorithme de hachage cohérent a été proposé par le MIT en 1997. Il s'agit d'un algorithme de hachage spécial conçu pour résoudre le problème du cache distribué. Lors de la suppression ou de l'ajout d'un serveur, le mappage entre les demandes de service existantes et les serveurs traitant les demandes peut être modifié le moins possible. Le hachage cohérent résout les problèmes de mise à l'échelle dynamique des algorithmes de hachage simples dans les tables de hachage distribuées (DHT).

Introduction :

L'algorithme de hachage cohérent a été proposé dans l'article Consistenthashing and random Trees en 1997 et est largement utilisé dans les systèmes distribués. Le hachage cohérent est un algorithme de hachage. En termes simples, lorsqu'un serveur est supprimé ou ajouté, cet algorithme peut modifier le moins possible la relation de mappage entre les demandes de service existantes et le serveur de traitement des demandes et satisfaire autant que possible les exigences sexuelles. . Dans un cluster distribué ordinaire, il existe une correspondance biunivoque entre les demandes de service et les serveurs de demandes de traitement, c'est-à-dire que la relation de mappage entre les demandes de service et les serveurs de traitement est fixe et qu'une certaine demande est traitée par un serveur fixe. . Cette méthode ne peut pas équilibrer la charge de l'ensemble du système et peut rendre certains serveurs trop occupés pour traiter de nouvelles requêtes. Alors que d'autres serveurs sont trop inactifs, l'utilisation des ressources du système global est faible et lorsqu'un serveur du cluster distribué tombe en panne, certaines demandes de service ne pourront directement pas être traitées.

D'autres améliorations peuvent utiliser des algorithmes de hachage pour cartographier la relation entre les demandes de service et les serveurs de traitement afin d'obtenir une allocation dynamique. La demande de service est convertie via l'algorithme de hachage et le résultat converti est calculé modulo sur la valeur du nœud du serveur. La valeur modulo est le serveur de traitement de la demande correspondant à la demande de service. Cette méthode peut faire face à la défaillance d'un nœud lorsqu'un nœud de cluster distribué tombe en panne, les demandes de service peuvent être redistribuées vers d'autres serveurs disponibles via l'algorithme de hachage. Cela évite la situation où la demande ne peut pas être traitée.

Cependant, les inconvénients de cette méthode sont également évidents. Si les données correspondant à la demande de service sont stockées sur le serveur, alors si la valeur de hachage de la demande est recalculée, un grand nombre de demandes seront redirigées. vers différents serveurs. Les données à utiliser dans la requête ne sont pas valides, ce qui est très mauvais dans un système distribué. Un système distribué bien conçu doit avoir une bonne monotonie, c'est-à-dire que l'ajout et la suppression de serveurs ne provoqueront pas un grand nombre de déplacements de hachage, et un hachage cohérent peut exactement résoudre ce problème.

L'algorithme de hachage cohérent mappe l'ensemble de l'espace de valeurs de hachage dans un anneau virtuel, et la plage de valeurs de l'ensemble de l'espace de hachage est de 0 à 232-1. L’ensemble de l’espace est organisé dans le sens des aiguilles d’une montre. Les directions 0~232-1 coïncident au point zéro. Ensuite, utilisez l'algorithme suivant pour mapper la demande de service, utilisez l'algorithme de hachage pour calculer la valeur de hachage correspondante de la demande de service, puis recherchez dans le sens des aiguilles d'une montre le long du cercle en fonction de la position de la valeur de hachage. Le premier serveur rencontré est le correspondant. serveur de traitement de la demande. Lorsqu'un nouveau serveur est ajouté, les données affectées sont uniquement les données entre le serveur nouvellement ajouté et le serveur précédent dans son espace en anneau (c'est-à-dire le premier serveur rencontré dans le sens inverse des aiguilles d'une montre). Les autres données ne seront pas affectées. En résumé, l'algorithme de hachage cohérent n'a besoin que de déplacer une petite partie des données dans l'espace de l'anneau pour augmenter ou diminuer le nombre de nœuds, et présente une bonne tolérance aux pannes et une bonne évolutivité.

Caractéristiques :

• Extensibilité. L'algorithme de hachage cohérent garantit des modifications minimes dans le stockage des données lors de l'ajout ou de la suppression de serveurs, ce qui permet d'économiser considérablement les frais de déplacement des données par rapport aux algorithmes de hachage traditionnels.

• Mieux s'adapter à la croissance rapide des données. Un algorithme de hachage cohérent est utilisé pour distribuer les données. Lorsque les données continuent de croître, certains nœuds virtuels peuvent contenir beaucoup de données, ce qui entraîne une répartition inégale des données sur les nœuds virtuels. À ce stade, les nœuds virtuels contiennent beaucoup de données. peut être divisé. Cette division est uniquement le nœud virtuel d'origine est divisé en deux, et il n'est pas nécessaire de re-hacher et de diviser toutes les données. Une fois les nœuds virtuels divisés, si la charge sur les serveurs physiques est toujours déséquilibrée, il vous suffit d'ajuster la répartition du stockage de certains nœuds virtuels entre les serveurs. Cela peut augmenter dynamiquement le nombre de serveurs physiques à mesure que les données augmentent, et le coût est bien inférieur à la redistribution de toutes les données avec des algorithmes de hachage traditionnels.

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!