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 $K/n$ clés ont besoin d’être redistribuées en moyenne, où $K$ est le nombre de clés et $n$ 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.

Historique

À 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 $K/n$ 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 hachage Rendezvous (en), 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).

Besoin sous-jacent

Lorsque l'on fait fonctionner des ensembles de machines de cache, certaines limitations apparaissent. Une méthode courante pour équilibrer la charge sur $n$ machines de cache est de mettre l'objet $o$ dans la machine numéro ${\mbox{hash}}(o)\mod n$. Cela ne fonctionnera pas si une machine de cache est ajoutée ou enlevée, car la valeur de $n$ change et tous ses objets vont être hachés vers un nouvel emplacement. Cela peut être désastreux en matière de performances, car les machines fournissant le contenu sont bombardées de requêtes provenant des machines de cache. Le besoin d'un hachage cohérent se fait donc ressentir (afin d’éviter d'inonder de requêtes les serveurs).

Le hachage cohérent place les objets sur la même machine de cache autant que possible. Lorsqu'une machine de cache est ajoutée, elle récupère la part d'objets lui revenant des autres machines de cache et, lorsqu'elle est enlevée, ses objets sont répartis entre les machines restantes.

L’idée derrière l'algorithme de hachage cohérent est d'associer chaque machine de cache à un ou plusieurs intervalles où les frontières des intervalles sont déterminées en calculant le hache de chaque identifiant de cache. La fonction de hachage utilisée pour définir les intervalles n'a pas besoin d’être la même que la fonction utilisée pour hacher les valeurs mises en cache, seul le degré (espace) des deux fonctions doit être identique. Si le cache est supprimé, son intervalle est repris par un cache adjacent. Tous les autres caches restent inchangés.

Technique

Le hachage cohérent est basé sur le principe suivant : on projette chaque objet sur un point d'un cercle (on peut aussi le faire en utilisant les angles à la place des points). On projette également chaque machine disponible (ou ensemble de stockage) sur plusieurs points répartis de manière aléatoire sur ce même cercle.

Pour trouver où un objet se trouve, le système doit trouver l'emplacement de la clé de cet objet sur le cercle, puis naviguer sur le cercle (dans le sens des aiguilles d'une montre) jusqu’à ce qu'il rencontre une machine (ou ensemble de stockage), ou la première machine disponible ayant un angle supérieur. Le résultat est que chaque seau (cache ou sous-ensemble de cache) contient toutes les ressources localisées entre son emplacement et le seau derrière lui.

Si un seau devient indisponible (par exemple parce que la machine sur lequel il réside ne répond plus), alors les angles sur lequel il se trouve sont effacés. Les requêtes des ressources qui auraient en temps normal abouti à ce point sont redirigées vers le point supérieur le plus proche. Comme chaque seau est associé à un nombre aléatoirement réparti de points, les ressources contenues dans ce seau vont maintenant être ré-affectées à d'autres seaux. Les objets contenus dans le seau perdu doivent être redistribués vers les seaux restants, mais les valeurs des autres seaux persistent et n'ont pas besoin d’être changées de place.

Un processus similaire se déroule lors de l'ajout d'un seau. En ajoutant un point correspondant à un nouveau seau, on déplace toutes ressources entre ce seau et celui d'un angle plus petit et adjacent vers le nouveau seau. Ces ressources ne sont à présent plus associées au précédent seau, et chaque valeur précédemment stockée ne sera plus trouvée à cet endroit en utilisant la méthode de sélection.

La portion de clés associée à chaque seau peut être modifiée en altérant l'angle de ce seau.

Clés monotones

S'il est connu que les valeurs de clés vont toujours croître de manière monotone, alors une approche alternative au hachage cohérent est possible.

Propriétés

David Karger et al. listent plusieurs propriétés du hachage cohérent qui le rend très utile dans les systèmes distribués de cache sur Internet :

• étalement ;
• charge ;
• douceur ;
• équilibre ;
• monotonie.

Exemples d'utilisation

Certains systèmes connus utilisent le hachage cohérent :

• OpenStack's Object Storage Service Swift ;
• Partitioning component of Amazon's storage system Dynamo ;
• Data partitioning in Apache Cassandra ;
• Data Partitioning in Voldemort ;
• Akka's consistent hashing router ;
• Riak, a distributed key-value database ;
• GlusterFS, a network-attached storage file system ;
• Skylable, an open-source distributed object-storage system.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Consistent hashing » (voir la liste des auteurs).

Voir aussi

Liens externes

• Understanding Consistent hashing

Implémentation dans divers langages

• C++
• C#
• Erlang
• Go
• PHP
• Python
• Ruby
• Perl