Contexte

Imaginez que vous ayez trois serveurs de cache, nommés serveur0, serveur1, et serveur2. Vous disposez de 30 millions de clés et souhaitez les distribuer uniformément sur ces trois serveurs. Quelle approche adopteriez-vous ?

Une solution intuitive est l'algorithme de modulo : hash(clé) % N, où N est le nombre de serveurs. En appliquant la fonction de hachage à chaque clé, puis en calculant le reste de la divsiion par 3, vous obtenez un indice (0, 1 ou 2) correspondant directement à un serveur. Cette méthode est simple et efficace pour résoudre le problème initial.

Cependant, l'algorithme de modulo présente une limitation majeure lors de l'ajout ou de la suppression de serveurs. Dans un environnement de production, il est fréquent d'ajuster le nombre de serveurs en fonction de la charge. Si le nombre de serveurs N change, le résultat de hash(clé) % N change également.

Par exemple, si un serveur tombe en panne, la formule passe de hash(clé) % 3 à hash(clé) % 2. Le résultat du hachage pour une clé donnée sera très probablement différent, entraînant la perte de sa donnée mise en cache. Une défaillance massive des caches simultanément, un phénomène appelé "avalanche de caches", peut rendre l'ensemble du système de cache indisponible, ce qui est inacceptable.

Pour pallier ce problème, l'algorithme de hachage cohérent a été développé.

Principe de l'algorithme de hachage cohérent

L'algorithme de hachage cohérent, proposé par le MIT en 1997, est une forme particulière de hachage. Il vise à minimiser les changements dans la relation entre les requêtes de service et les serveurs qui les traitent, lors de l'ajout ou de la suppression d'un serveur. Cet algorithme résout les problèmes de redimensionnement dynamique rencontrés par les algorithmes de hachage simples dans les tables de hachage distribuées (DHT).

Essentiellement, le hachage cohérent est aussi une forme d'algorithme de modulo. Cependant, au lieu de prendre le modulo par le nombre de serveurs, il utilise une valeur fixe, typiquement 2^32. Les adresses IPv4, par exemple, sont composées de quatre groupes de 8 bits binaires, donc 2^32 garantit une correspondance unique pour chaque adresse IP.

Le cercle de hachage

Les valeurs de 0 à 2^32-1 peuvent être conceptualisées comme un cercle. Le point supérieur du cercle représente la valeur 0, et les valeurs augmentent dans le sens des aiguilles d'une montre jusqu'à 2^32-1. Ce cercle, composé de 2^32 points, est appelé le "cercle de hachage".

Mappage des serveurs sur le cercle de hachage

Pour mapper un serveur sur ce cercle, on utilise hash(adresse_IP_serveur) % 2^32. Le résultat, un entier compris entre 0 et 2^32-1, détermine la position du serveur sur le cercle. Les trois serveurs serveur0, serveur1, et serveur2 sont ainsi placés sur le cercle.

Mappage des clés d'objet sur les serveurs

Pour déterminer sur quel serveur une clé d'objet doit être mise en cache, on calcule d'abord son hachage : hash(clé) % 2^32. La fonction de hachage utilisée ici peut être différente de celle employée pour les serveurs, tant qu'elle produit des valeurs dans la même plage (0 à 2^32-1).

La règle de mappage est la suivante : en partant de la position de la clé sur le cercle et en se déplaçant dans le sens des aiguilles d'une montre, le premier serveur rencontré est celui sur lequel l'objet sera mis en cache.

Supposons quatre objets (o1, o2, o3, o4) avec leurs valeurs de hachage (k1, k2, k3, k4) et trois serveurs de cache (CS1, CS2, CS3). Le mappage se fait comme suit :

hash(o1) = k1
hash(o2) = k2
hash(o3) = k3
hash(o4) = k4

Si k1 et k3 sont entre la position de CS1 et CS2, k2 est entre CS2 et CS3, et k4 est entre CS3 et CS1, alors le mappage serait :

k1 => CS1
k4 => CS3
k2 => CS2
k3 => CS1

Le hachage cohérent transforme ainsi un mappage ponctuel en un mappage basé sur des segments d'un cercle.

Scénarios d'ajout et de suppression de serveurs

Suppression d'un serveur

Si le serveur CS3 tombe en panne, les objets qui lui étaient assignés (ici, o4) sont réassignés au serveur suivant dans le sens horaire, qui est CS2. Les autres objets restent sur leurs serveurs respectifs. Seules les données associées aux serveurs CS2 et CS3 sont affectées.

Ajout d'un serveur

Si un nouveau serveur CS4 est ajouté, son emplacement sur le cercle de hachage détermine les objets dont il prendra en charge la mise en cache. Par exemple, s'il est placé entre CS1 et CS2, seuls les objets dont le hachage tombe dans cet intervalle (ici, o3) devront être réassignés à CS4. Les autres objets conservent leur serveur d'origine.

Contrairement à l'algorithme de modulo qui pourrait invalider une grande partie des caches lors de l'ajout d'un serveur, le hachage cohérent ne nécessite la réaffectation que d'une petite fraction des données.

Problèmes de déséquilibre de charge et de performence des serveurs

Déséquilibre des données

Dans les exemples précédents, les serveurs sont répartis uniformément sur le cercle. Cependant, il est difficile de garantir une distribution parfaite avec une fonction de hachage. Avec un petit nombre de serveurs, cela peut entraîner un déséquilibre des données (data skew), où la plupart des objets sont mis en cache sur un seul serveur, surchargent celui-ci et sous-utilisent les autres.

Mise à l'échelle inefficace

Un autre problème survient lors de l'ajout d'un serveur. Par exemple, si CS4 est ajouté entre CS1 et CS2, il ne prend en charge que la charge de CS1. Les serveurs CS2 et CS3 ne voient pas leur charge diminuer. Si CS4 a des performances égales ou supérieures aux serveurs existants, ce résultat n'est pas optimal.

Nœuds virtuels

Pour résoudre ces problèmes, on introduit des "nœuds virtuels". Chaque serveur physique est représenté par plusieurs nœuds virtuels répartis sur le cercle de hachage. Pour trouver le serveur d'un objet, on détermine d'abord son nœud virtuel, puis on remonte au serveur physique correspondant.

Dans le schéma ci-dessous, o1 et o2 sont des objets, v1 à v6 sont des nœuds virtuels, et s1 à s3 sont des serveurs physiques.

Calcul des nœuds virtuels

Le hachage des nœuds virtuels peut être calculé en ajoutant un suffixe numérique à l'adresse IP du serveur physique, par exemple : hash(adresse_IP_serveur#numéro_virtuel) % 2^32.

Si un serveur physique a l'adresse IP 10.24.23.227, ses nœuds virtuels pourraient être hachés comme suit :

• hash("10.24.23.227#1") % 2^32
• hash("10.24.23.227#2") % 2^32
• hash("10.24.23.227#3") % 2^32

Plus le nombre de nœuds virtuels est élevé, plus la distribution sur le cercle de hachage tend à être uniforme. Cependant, l'introduction de nœuds virtuels complexifie la gestion des mappages (objet -> nœud virtuel -> serveur physique).

Cas d'utilisation

Le hachage cohérent est un algorithme de choix pour l'équilibrage de charge dans les systèmes distribués. Il peut être implémenté côté client ou via des middlewares comme Memacched et Redis.

• Memcached utilise le hachage cohérent côté client pour déterminer sur quel serveur placer une clé, car ses serveurs ne communiquent pas entre eux.
• Le concept de "slots" (slots de hachage) dans Redis Cluster est similaire, bien que l'implémentation diffère.
• Les frameworks RPC comme Dubbo l'utilisent pour sélectionner un fournisseur de services.
• Dans les bases de données relationnelles distribuées, il sert à mapper les données aux nœuds lors du partitionnement (sharding).
• Le répartiteur de charge LVS l'utilise également.

Implémentation en Java

Voici une implémentation simplifiée en Java de l'algorithme de hachage cohérent, prenant en compte les nœuds virtuels.

package com.example.hash;

import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Collection;
import java.util.Map;
import java.util.List;
import java.util.ArrayList;
import java.util.Set;

/**
 * Implémentation de l'algorithme de hachage cohérent.
 */
public class ConsistentHashRing {

    private final int numberOfReplicas; // Nombre de répliques (nœuds virtuels) par serveur réel
    private final SortedMap<Integer, String> ring = new TreeMap<>(); // Le cercle de hachage

    /**
     * Constructeur.
     * @param numberOfReplicas Nombre de nœuds virtuels par serveur réel.
     * @param servers Liste initiale des serveurs réels.
     */
    public ConsistentHashRing(int numberOfReplicas, Collection<String> servers) {
        this.numberOfReplicas = numberOfReplicas;
        for (String server : servers) {
            addServer(server);
        }
    }

    /**
     * Ajoute un serveur réel au cercle de hachage.
     * @param server Le nom ou l'identifiant du serveur réel.
     */
    public synchronized void addServer(String server) {
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = hashFunction(server + "#" + i);
            ring.put(hash, server);
        }
    }

    /**
     * Supprime un serveur réel du cercle de hachage.
     * @param server Le nom ou l'identifiant du serveur réel.
     */
    public synchronized void removeServer(String server) {
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = hashFunction(server + "#" + i);
            ring.remove(hash);
        }
    }

    /**
     * Trouve le serveur réel auquel une clé est assignée.
     * @param key La clé à localiser.
     * @return Le nom ou l'identifiant du serveur réel assigné.
     */
    public synchronized String getServer(String key) {
        if (ring.isEmpty()) {
            return null;
        }
        int hash = hashFunction(key);
        // Trouve la première entrée dont la clé est supérieure ou égale au hachage de la clé
        Map.Entry<Integer, String> entry = ring.ceilingEntry(hash);
        if (entry == null) {
            // Si aucune entrée n'est trouvée, on "boucle" au début du cercle
            entry = ring.firstEntry();
        }
        return entry.getValue();
    }

    /**
     * Fonction de hachage interne.
     * Utilise le hachage Java standard et gère les entiers négatifs.
     * @param key La chaîne à hacher.
     * @return La valeur de hachage sous forme d'entier positif.
     */
    private int hashFunction(String key) {
        // Utilise le hachage Java et s'assure que le résultat est positif
        return Math.abs(key.hashCode());
    }

    // Exemple d'utilisation
    public static void main(String[] args) {
        List<String> servers = new ArrayList<>();
        servers.add("serveur_A");
        servers.add("serveur_B");
        servers.add("serveur_C");

        ConsistentHashRing hashRing = new ConsistentHashRing(100, servers); // 100 répliques par serveur

        String key1 = "cle_utilisateur_123";
        String key2 = "cle_produit_456";
        String key3 = "cle_session_789";

        System.out.println("Assignation de " + key1 + ": " + hashRing.getServer(key1));
        System.out.println("Assignation de " + key2 + ": " + hashRing.getServer(key2));
        System.out.println("Assignation de " + key3 + ": " + hashRing.getServer(key3));

        System.out.println("\nAjout de serveur_D...");
        hashRing.addServer("serveur_D");

        System.out.println("Assignation de " + key1 + " après ajout: " + hashRing.getServer(key1));
        System.out.println("Assignation de " + key2 + " après ajout: " + hashRing.getServer(key2));
        System.out.println("Assignation de " + key3 + " après ajout: " + hashRing.getServer(key3));

        System.out.println("\nSuppression de serveur_B...");
        hashRing.removeServer("serveur_B");

        System.out.println("Assignation de " + key1 + " après suppression: " + hashRing.getServer(key1));
        System.out.println("Assignation de " + key2 + " après suppression: " + hashRing.getServer(key2));
        System.out.println("Assignation de " + key3 + " après suppression: " + hashRing.getServer(key3));
    }
}