Hachage cohérent

Le hachage cohérent est un type particulier de hachage. Lorsque la table de hachage change de taille et que le hachage cohérent est employé, seulement clés ont besoin d’être redistribuées en moyenne, où est le nombre de clés et est le nombre d'éléments dans la table de hachage. En comparaison, dans une table de hachage classique, un changement dans le nombre d'éléments de la table a pour conséquence la réorganisation de l'ensemble ou presque des clés. À l'origine conçue par Karger et coll. au Massachusetts Institute of Technology, afin d’être utilisée dans un système de cache distribué, cette notion est apparue dans d'autres domaines. Une publication dans un article de 1997 introduit le terme hachage cohérent comme un moyen de répartir les requêtes sur un ensemble de serveurs web en constante évolution. Chaque emplacement est représenté par un nœud d'un système réparti. L'ajout (arrivée), ou la suppression (départ/défaut) d'un des nœuds ne requiert la répartition que de objets lorsque le ratio emplacements/nœuds change. Le hachage cohérent a aussi été utilisé pour réduire l'impact de défaillances partielles d'un système dans de grandes applications Web, permettant la mise au point d'un système de cache robuste sans engendrer d'indisponibilité générale dans le cas d'une défaillance isolée. Le concept de hachage cohérent peut être appliqué à la conception des tables de hachage distribuées (DHTs). Les DHTs utilisent le hachage cohérent pour fragmenter un espace de clés sur un ensemble de nœuds, et fournissent également une surcouche réseau qui connecte des nœuds tel que chaque nœud responsable d'une clé peut être localisé de manière efficace. Le , conçu dans la même période que le hachage cohérent, poursuit le même but en utilisant un algorithme très différent appelé Highest Random Weight (HWR). Lorsque l'on fait fonctionner des ensembles de machines de cache, certaines limitations apparaissent. Une méthode courante pour équilibrer la charge sur machines de cache est de mettre l'objet dans la machine numéro .