Accueil / Articles / De Modulo à Hash Ring : Échellener une flotte de caches Node.js sans subir de tempêtes

Node.jsSystem DesignCachingDistributed SystemsRedisPerformance

De Modulo à Hash Ring : Échellener une flotte de caches Node.js sans subir de tempêtes

Découvrez pourquoi le shardage par hash-mod-N provoque des problèmes dans les bases de données lors du changement de nœuds, comment se comparent les algorithmes de hachage rendez-vous, jump et ring, ainsi que la manière de créer un anneau pondéré équilibré dans Node.js.

4407 mots

Un cluster de cache qui fonctionne correctement depuis des mois peut voir sa base de données tomber en panne en quelques minutes suite à une modification de routine : l’ajout d’un nœud. La cause en est généralement une seule ligne de code client qui sélectionne un serveur à l’aide de hash(key) % N. Ce guide explique précisément pourquoi cette ligne échoue, compare les quatre alternatives sérieuses, crée un anneau de hachage cohérent de qualité professionnelle en Node.js, et énumère les pièges opérationnels auxquels l’algorithme lui-même ne vous protégera pas.

Le schéma des pannes

Imaginez un groupe sain de quatre nœuds de cache avec un taux de réussite de 94 %. Le trafic augmente en prévision d’un pic saisonnier, alors un ingénieur ajoute un cinquième nœud. Il s’agit d’une modification de configuration en deux lignes, déployée avec prudence au milieu de la journée de travail. Environ une minute et demie plus tard, la base de données consomme 100 % de sa puissance CPU et le site devient indisponible.

Nul n’a agi de manière négligente. Le client a simplement routé les clés comme il le faisait toujours :

const node = nodes[hash(key) % nodes.length];

Cette expression répartit les clés de manière très équitable, ce qui la rend apparemment correcte. Le problème réside dans ce qu’elle fait dès que nodes.length change, et c’est là que commence le reste de ce guide. La discussion aborde quatre problèmes distincts, évalue les véritables alternatives, puis construit et mesure un anneau en Node.js.

Quatre problèmes cachés derrière une seule idée

L’hashage cohérent est souvent présenté comme une simple astuce. En pratique, il permet de résoudre quatre problèmes différents, et une implémentation ne traitant que le premier échouera malgré tout en production à cause des trois autres.

Problème 1 : changer N déplace presque toutes les clés

Avec hash(key) % N, changer N ne déplace que quelques clés ; il en déplace presque toutes.

Il est utile d’analyser les chiffres. Une clé avec un hash de 1 000 003 correspond au nœud 3 avec % 4, et il se trouve aussi qu’elle correspond au nœud 3 avec % 5. Une clé avec un hash de 1 000 004 correspond au nœud 0 sous % 4 et au nœud 4 sous % 5. Ces deux correspondances ne sont pas liées entre elles, de sorte qu’une clé reste à sa place uniquement par hasard, avec une probabilité d’environ 1 sur N.

Sur un million de clés, le schéma est évident : passer de 8 à 9 nœuds déplace 88,93 % des clés, et sur un cluster de cent nœuds, l’ajout d’un seul nœud rend inutilisable environ 99 % du cache.

Regardez dans quelle direction se dirige cette tendance. Plus votre système grandit, plus chaque étape d’extension devient dévastatrice. C’est un échec qui guette jusqu’à ce que l’entreprise réussisse.

Chaque clé réaffectée représente une erreur de recherche, chaque erreur déclenche une requête à la base de données, et toutes ces requêtes arrivent en quelques secondes. Une base de données conçue pour gérer 6 % des lectures qui échouent normalement reçoit soudainement presque toutes ces requêtes.

Problème 2 : le même réajustement, non planifié

Le premier problème se produit au moins lorsque l’on décide de mettre à l’échelle le système. Le second est le même événement déclenché par une panne, au moment le moins opportun.

Un nœud épuise sa mémoire, un hôte est arrêté, ou une partition réseau isole un nœud de la moitié du groupe. Le nombre de nœuds passe de 8 à 7, et chaque client, agissant de son propre chef, réaffecte environ 87 % de ses clés aux nœuds restants.

La situation est désormais grave : 12,5 % de la capacité du cache a disparu, la base de données fait face à une tempête de fausses lectures représentant 87 % des cas, et les sept nœuds survivants doivent gérer le trafic du nœud perdu en même temps qu’ils se rechargent avec presque toutes les clés. Un résultat fréquent est l’effondrement d’un deuxième nœud, ce qui force un nouveau remappage complet, entraînant ensuite l’effondrement d’un troisième.

Le routage modulo transforme la panne d’un seul nœud en une panne corrélée affectant tout le cluster, qui se nourrit d’elle-même. C’est cette cascade, et non un cache froid, qui représente le véritable danger.

Problème 3 : un anneau naïf est fortement déséquilibré

La solution évidente au problème 1 consiste à placer les nœuds et les clés dans un même espace numérique et à attribuer chaque clé au nœud qui suit en sens horaire. C’est l’essence du hachage cohérent, et cela élimine effectivement le remaniement massif.

Cependant, lorsqu’il est mis en œuvre de manière naïve, il répartit mal la charge. Les nœuds se trouvent là où aboutissent leurs hachages, de sorte que les espaces entre eux sont aléatoires, et des espaces aléatoires sont rarement égaux. Avec quatre nœuds attribués à chaque hachage, une mesure a montré qu’un seul nœud contrôlait 45% de l’espace des clés, tandis qu’un autre n’en contrôlait que 13%, soit une différence de 3,4 fois sans aucun bug.

Cet déséquilibre est également persistant. Il provient des noms mêmes des nœuds ; ainsi, le même nœud, par exemple cache-04, reste actif tant qu’il n’est pas renommé, et toute personne qui examine le code constate qu’il fonctionne exactement comme écrit.

Au niveau plus élevé, la situation s’aggrave. Avec un point d’anneau par nœud sur 8 nœuds, le nœud le plus sollicité gérait 434% de sa part équitable, tandis que le plus léger ne gérait que 3,7%. Cela revient en pratique à un serveur surchargé et sept serveurs inactifs.

Problème 4 : tous les clients doivent être d’accord

Le problème le moins évident concerne l’autorité. Il faut bien que quelque chose associe une clé à un nœud, et cela doit donner la même réponse sur chaque machine qui pose la demande.

Un service de coordination qui gère la carte des shards autoritaires est une option possible. Dans ce cas, soit chaque recherche nécessite un aller-retour réseau, soit les clients mettent en cache cette carte et il devient alors nécessaire de trouver un moyen de la rendre invalide. Si deux clients possèdent des versions différentes de la carte, ne serait-ce que temporairement, l’un peut écrire user:42 sur le nœud A tandis qu’un autre le lit depuis le nœud B. Rien n’est perdu, ce qui est en réalité pire : il existe désormais deux valeurs plausibles.

Ce que vous souhaitez, c’est une correspondance qui soit une fonction pure de la clé et de la liste actuelle des membres. Aucun coordinateur, aucun service de recherche, aucune état partagé : chaque client effectue les mêmes calculs et obtient le même résultat. Le hachage cohérent offre précisément cela, d’où son avantage sur les tables de recherche malgré leur plus grande flexibilité.

Un scénario concret et les options

Pour rendre cette comparaison concrète, considérez ce système.

Le système. Une API de commerce électronique met en cache les données de session et de profil dans un pool de nœuds Redis. La charge maximale atteint environ 40 000 recherches par seconde sur 25 millions de clés, avec un taux de succès de 94 %. La base de données ne fonctionne que grâce aux 6 % d’appels qui échouent. (Pour un rappel sur les modèles de mise en cache eux-mêmes, consultez Les principes fondamentaux de la mise en cache Redis.)

Les exigences :

  1. Passer de 8 à 12 nœuds avant une vente sans déclencher une tempête d’échecs
  2. Survivre à la perte d’un nœud avec un rayon d’impact limité et tolérable
  3. Maintenir une charge équilibrée, sans que aucun nœud ne dépasse à peu près 120 % de sa part équitable
  4. Éviter que tout coordonnateur ne se trouve sur le chemin des lectures
  5. Gérer un matériel hétérogène : certains nœuds disposent de 64 Go, d’autres de 16 Go, et ils ne doivent pas supporter la même charge

Divers algorithmes peuvent répondre à certains ou à tous ces critères. Ils diffèrent de manière significative, et un mauvais choix s’avère coûteux.

Option A : hachage modulo

hash(key) % N offre un équilibre parfait, ne nécessite qu’une instruction et n’utilise aucune mémoire.

Il ne remplit pas les exigences 1 et 2. Il mérite d’être mentionné car c’est ce que tout le monde écrit en premier, et il fonctionne parfaitement jusqu’au jour où cela cesse d’être le cas.

Choisissez-le lorsque N ne change vraiment jamais, par exemple pour répartir un travail en lot sur un nombre fixe d’agents ou pour le shardage au sein d’un seul processus.

Option B : un coordinateur et une table de recherche

Gérez une correspondance explicite entre les plages de clés et les nœuds dans un stockage tel que etcd ou ZooKeeper. Des systèmes comme Vitess et HBase fonctionnent plus ou moins de cette manière.

L’avantage est réel : un contrôle total. Vous pouvez déplacer une seule particule chaude, rééquilibrer une plage à la fois tout en surveillant les métriques, ou assigner un utilisateur spécifique à du matériel déterminé. Aucune méthode basée sur l’hash ne propose tout cela, et au-delà d’une certaine échelle, vous en aurez besoin.

Le prix à payer est tout aussi réel : un système de consensus à gérer, la difficulté de maintenir à jour toutes les copies en mémoire du plan, ainsi qu’une dépendance obligatoire par rapport au chemin de lecture.

Choisissez-le lorsque vous transférez des données durables plutôt que des entrées de cache jetables, et que vous devez contrôler la migration au lieu de laisser tout changer d’un coup.

Option C : hashing de rendez-vous (HRW)

Le scoring par poids aléatoire le plus élevé compare chaque clé avec tous les nœuds et sélectionne le gagnant :

function rendezvous(key, nodes) {
  let best = null, bestScore = -1;
  for (const node of nodes) {
    const score = mix(hash(key), hash(node));
    if (score > bestScore) { bestScore = score; best = node; }
  }
  return best;
}

C’est là tout l’algorithme. Il n’y a ni anneau, ni nœuds virtuels, ni structure triée, et rien à reconstruire lorsque les membres changent.

Sur les deux métriques les plus importantes, il surpasse également l’anneau. Le passage de 8 à 9 nœuds a déplacé 11,09 % des clés, contre un minimum théorique de 11,11 %, et l’équilibre était presque parfait sans aucune mise au point.

L’inconvénient est un temps de traitement de O(N) par recherche, car chaque clé est hachée par rapport à chaque nœud, et ce coût augmente rapidement à mesure que le nombre de nœuds croît.

Choisissez-le lorsque vous disposez de moins d’environ 30 nœuds. De nombreuses équipes utilisent environ huit nœuds de cache et seraient mieux servies par l’hachage de rendez-vous : il est plus simple à écrire et à comprendre, et permet un meilleur équilibre. L’anneau est la solution plus connue, mais pas nécessairement la meilleure.

Option D : hachage cohérent par saut

Cet algorithme, publié par Google en 2014, se compose d’environ dix lignes, ne nécessite aucune mémoire, équilibre presque parfaitement et déplace le minimum de clés possible.

Son limite est structurelle. Il associe une clé à un numéro de bucket dans [0, N) sans tenir compte de l’identité du nœud. Les buckets ne peuvent être ajoutés ou supprimés qu’à la fin de cette plage ; il n’existe aucun moyen d’enlever le nœud 3 du milieu tout en maintenant la stabilité du reste.

Choisissez-le lorsque les buckets sont interchangeables et que seul leur nombre change, comme lors du partage d’un ensemble de données entre un groupe de travailleurs réglable en taille. Il est peu adapté lorsque des serveurs nommés spécifiques rejoignent ou quittent le système, ce qui correspond précisément au comportement des nœuds de cache.

Option E : un anneau de hachage avec des nœuds virtuels

C’est le design classique. Les nœuds et les clés partagent un espace d’adresses circulaire, et une clé appartient au premier nœud trouvé dans le sens des aiguilles d’une montre à partir d’elle.

Choisissez-le lorsque la flotte est suffisamment grande pour que le coût linéaire des recherches de rendez-vous devienne problématique, et que vous avez également besoin de nœuds pondérés ainsi que de la capacité de supprimer n’importe quel nœud.

Sélectionner celui adapté au scénario

Au vu d’une variation de 8 à 9 nœuds sur un million de clés, les alternatives autres que le modulo se rapprochent toutes du minimum théorique, et l’équilibre de l’anneau dépend fortement du nombre de nœuds virtuels reçus par chaque serveur. Pour ce système de e-commerce, avec du matériel mixte, des nœuds nommés qui peuvent tomber en panne et une flotte prévue à 30 nœuds, l’anneau est le choix approprié. Le reste de ce guide explique comment le mettre en place correctement.

Fonctionnement de l’anneau

Mettons de côté les tableaux et les restes. Imaginez un cercle numéroté de 0 à 2³² − 1 qui se termine par le début.

Deux règles constituent tout l’algorithme :

  1. Hasher chaque nom de nœud sur ce cercle, de sorte que cache-01 se trouve là où son hash le place.
  2. Hasher chaque clé sur le même cercle, puis avancer dans le sens des aiguilles d’une montre. Le premier nœud atteint possède la clé.

L’idée clé est que les nœuds et les clés partagent un seul espace d’adresses. Tout le reste en découle, y compris le fait que l’ajout d’un nœud est peu coûteux.

Pourquoi les changements de membership restent locaux

Lorsqu’on place un nouveau nœud sur le cercle, il se situe entre deux nœuds existants. Il ne prend en charge que l’arc entre lui-même et son voisin dans le sens inverse des aiguilles d’une montre.

Les clés situées en dehors de cet arc ne sont pas affectées et reviennent à leur propriétaire précédent exactement comme avant. Le nouvel arrivant occupe en moyenne 1/(N+1) du cercle, ce qui fait que cette part de clés change. Sur une variation de 8 à 9, cela a représenté 11,06 %, avec un minimum de 11,11 %, contre 88,93 % pour la méthode modulo sur la même variation et le même ensemble de clés.

La suppression fonctionne inversement : l’arc du nœud qui part passe à son successeur dans le sens des aiguilles d’une montre. Une réduction de 8 à 7 nœuds a déplacé 12,60 % des clés, proche de la valeur théorique de 12,50 %. L’impact reste limité et gérable, et les six autres nœuds restent inchangés.

Les nœuds virtuels corrigent le déséquilibre

Revenons au problème 3 : quatre nœuds placés en quatre positions aléatoires génèrent des arcs très inégaux.

La solution est surprenamment simple : ne placez pas chaque nœud qu’une seule fois. Placez-le 160 fois sous 160 noms dérivés tels que cache-01#0 et cache-01#1. Chaque nom dérivé se trouve à un endroit différent, de sorte que chaque nœud physique possède 160 petits arcs dispersés au lieu d’un seul grand arc, et la loi des grands nombres équilibre les choses.

Sur un million de clés réparties sur 8 nœuds, l’équilibre s’améliore progressivement à mesure que le nombre de répliques augmente. 160 est la valeur par défaut habituelle, car c’est à peu près là que la courbe d’amélioration s’aplatit, mais 500 est encore nettement meilleur. Un point de boucle nécessite environ 12 octets (4 octets pour la position plus 8 octets pour la référence du propriétaire) ; donc huit nœuds avec 500 répliques occupent moins de 50 KB. Si l’équilibre est plus important pour vous que cette quantité de mémoire, augmentez ce chiffre ; c’est un calcul que peu d’équipes prennent la peine de faire.

Les nœuds virtuels rendent également le poidsage pratiquement gratuit. Un nœud disposant de deux fois plus de mémoire reçoit deux fois plus de points, et donc approximativement deux fois plus de trafic. Avec des poids de 4:4:1:1, la répartition mesurée était de 40,6 %, 41,1 %, 9,4 % et 9,0 %, contre un idéal de 40/40/10/10.

Mise en œuvre du réseau annulaire dans Node.js

La mise en œuvre se résume à quatre étapes : hacher les noms des nœuds virtuels, les placer, les trier, et utiliser une recherche binaire pour trouver le propriétaire d’une clé. La classe ci-dessous conserve les adhésions dans un Map, reconstruit les tableaux triés lorsque les adhésions changent, et expose get(key) pour effectuer des recherches.

export class ConsistentHashRing {
  #positions = new Uint32Array(0); // sorted ring positions
  #owners = []; // owners[i] owns #positions[i]
  #nodes = new Map(); // id -> { weight, points }

  constructor({ replicas = 160, hash = defaultHash } = {}) {
    if (replicas < 1) throw new RangeError("replicas must be >= 1");
    this.replicas = replicas;
    this.hash = hash;
  }

  addNode(id, weight = 1) {
    if (typeof id !== "string" || id.length === 0)
      throw new TypeError("node id must be a non-empty string");
    if (weight <= 0) throw new RangeError("weight must be > 0");
    if (this.#nodes.has(id)) return this;
    this.#nodes.set(id, {
      weight,
      points: Math.max(1, Math.round(this.replicas * weight)),
    });
    this.#rebuild();
    return this;
  }

  removeNode(id) {
    if (this.#nodes.delete(id)) this.#rebuild();
    return this;
  }

  #rebuild() {
    const pairs = [];
    for (const [id, { points }] of this.#nodes) {
      for (let i = 0; i < points; i++)
        pairs.push([this.hash(`${id}#${i}`), id]);
    }
    pairs.sort((a, b) => a[0] - b[0]);
    this.#positions = Uint32Array.from(pairs, (p) => p[0]);
    this.#owners = pairs.map((p) => p[1]);
  }

  /** Index of the first ring point >= h, wrapping to 0. */
  #successor(h) {
    const pos = this.#positions;
    let lo = 0,
      hi = pos.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (pos[mid] < h) lo = mid + 1;
      else hi = mid;
    }
    return lo === pos.length ? 0 : lo;
  }

  get(key) {
    if (this.#positions.length === 0) return null;
    return this.#owners[this.#successor(this.hash(key))];
  }
}

Trois choix de conception méritent une attention particulière.

Tableaux parallèles plutôt qu’un tableau d’objets. En stockant les positions dans un Uint32Array, on permet à la recherche binaire de fonctionner sur une mémoire compacte et contiguë restant dans le cache du CPU. Avec 8 nœuds et 160 répliques, on compte 1 280 points, soit environ 5 KB, et une recherche nécessite environ 11 comparaisons.

Le problème de rebond dans lo === pos.length ? 0 : lo. Une clé dont l’hash dépasse le dernier point appartient au premier nœud du cercle. Omettre cette condition est la faute la plus fréquente dans les structures circulaires personnalisées : le résultat est correct pour presque toutes les clés, mais inexplicablement faux pour celles situées près du sommet de la plage.

Réconstruction en cas de changement de membre, et non lors d’une recherche. Les changements de membre sont rares, tandis que les recherches ont lieu des dizaines de milliers de fois par seconde ; donc trier 1 280 entrées de temps en temps ne coûte rien d’important.

La réplication, c’est-à-dire la recherche des prochains propriétaires d’une clé, consiste en une progression dans le sens des aiguilles d’une montre qui collecte des nœuds physiques distincts. Le mot « distinct » est important, car les points voisins sur l’anneau appartiennent souvent au même serveur :

getReplicas(key, count = 1) {
  const n = this.#positions.length;
  if (n === 0) return [];
  const wanted = Math.min(count, this.#nodes.size);
  const out = [];
  const start = this.#successor(this.hash(key));
  for (let step = 0; step < n && out.length < wanted; step++) {
    const owner = this.#owners[(start + step) % n];
    if (!out.includes(owner)) out.push(owner);
  }
  return out;
}

Remarquez que la variable wanted est limitée au nombre de nœuds physiques ; par conséquent, demander plus de réplicas que de serveurs ne peut pas durer indéfiniment, et la progression s’arrête après un tour complet dans tous les cas.

Sélectionner soigneusement la fonction de hachage

De nombreux tutoriels omettent cette étape, or c’est elle qui fournit les résultats les plus instructifs de toute l’exercice.

La plupart des implémentations d’anneau utilisent par défaut MD5. Cette méthode fonctionne mais est lente : un anneau l’utilisant n’a atteint que 423 000 recherches par seconde, et les analyses ont montré que presque tout le temps était consacré à l’exécution de MD5.

Le remplacement par FNV-1a, un hachage non cryptographique rapide, a multiplié la capacité de traitement par environ 15 fois. Cependant, l’équilibre s’est effondré : la déviation standard de la charge par nœud est passée de 10,4 % à 30,7 %.

En examinant les positions calculées pour quelques nœuds virtuels, on découvre la cause :

cache-01#0 → 4037809751
cache-01#1 → 4021032132
cache-01#2 → 4071364989
cache-01#3 → 4054587370
cache-01#4 → 3970699275

Toutes ces valeurs se situent dans une bande étroite autour de 4,0 milliards. FNV-1a présente un faible comportement avalanche, ce qui signifie que des entrées similaires produisent des sorties similaires. Les noms des nœuds virtuels ne diffèrent que par un suffixe ; ainsi, au lieu de disperser 160 points autour du cercle, chaque nœud les regroupe en un cluster compact. L’optimisation pour la vitesse a silencieusement ramené le problème 3.

La solution consiste à faire passer la sortie de FNV par un finaliseur de mélange de bits, l’étape finale de MurmurHash3 :

function fnv1a(str) {
  let h = 0x811c9dc5;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}

// Scrambles the bits so near-identical inputs land far apart.
function fmix32(h) {
  h ^= h >>> 16;
  h = Math.imul(h, 0x85ebca6b);
  h ^= h >>> 13;
  h = Math.imul(h, 0xc2b2ae35);
  h ^= h >>> 16;
  return h >>> 0;
}

export const defaultHash = (str) => fmix32(fnv1a(str));

fmix32 alterne des décalages, des opérations XOR et des multiplications afin qu’un changement dans n’importe quel bit d’entrée se propage à tous les bits de sortie. Math.imul effectue une véritable multiplication d’entiers de 32 bits, tandis que >>> 0 convertit le résultat en un nombre entier sans signe de 32 bits adapté à Uint32Array. Grâce à une dizaine d’opérations supplémentaires, ce hash combiné offre un meilleur équilibre que MD5 tout en étant environ 13 fois plus rapide.

Cette leçon s’applique bien au-delà du hashing : lorsque vous remplacez un composant par un plus rapide, mesurez la propriété que vous n’optimisez pas. FNV-1a est un hash tout à fait respectable ; il est simplement le mauvais choix pour cette tâche, et rien dans sa description ne vous avertit de cela.

Transformer le ring en client de cache

Un anneau seul ne constitue pas un client de cache. Le code de production doit faire face aux pannes, et l’anneau propose une stratégie simple : passer au nœud suivant dans le sens des aiguilles d’une montre.

Le wrapper ci-dessous prend un tableau de clients nommés, construit l’anneau à partir d’eux, et lors de chaque appel à get, tente les premiers propriétaires selon la profondeur failoverDepth. Un nœud qui génère une erreur est marqué comme indisponible pendant downtimeMs et retiré de l’anneau, avant d’y être réintégré une fois cette période écoulée.

export class ShardedCache {
  #ring; #clients; #down = new Map();

  constructor(clients, { replicas = 160, failoverDepth = 2, downtimeMs = 10_000 } = {}) {
    this.#clients = new Map(Object.entries(clients));
    this.#ring = new ConsistentHashRing({ replicas });
    for (const id of this.#clients.keys()) this.#ring.addNode(id);
    this.failoverDepth = failoverDepth;
    this.downtimeMs = downtimeMs;
  }

  #markDown(id) {
    this.#down.set(id, Date.now() + this.downtimeMs);
    this.#ring.removeNode(id);
  }

  #reviveExpired() {
    const now = Date.now();
    for (const [id, until] of this.#down) {
      if (now >= until) { this.#down.delete(id); this.#ring.addNode(id); }
    }
  }

  async get(key) {
    this.#reviveExpired();
    for (const id of this.#ring.getReplicas(key, this.failoverDepth)) {
      try {
        return { value: await this.#clients.get(id).get(key), node: id };
      } catch {
        this.#markDown(id);
      }
    }
    return { value: null, node: null, allDown: true };
  }
}

En exécutant cela avec quatre nœuds simulés contenant 10 000 clés, puis en supprimant l’un d’eux, on a obtenu ce résultat :

Keys per node:  cache-01 2213 | cache-02 2462 | cache-03 2923 | cache-04 2402

Killing cache-02...
  served from cache: 7538
  cache misses:      2462
  hard failures:     0
  healthy nodes:     cache-01, cache-03, cache-04

  24.6% of traffic became a miss.

Ce chiffre représente votre plan de capacité. Dans une flotte de quatre nœuds, une panne entraîne un surcroît de 24,6 % de lectures pour la base de données, tandis qu’une flotte de huit nœuds limite cette augmentation à 12,5 %. Si la base de données ne peut pas supporter 1/N de votre charge de lectures arrivant en même temps, le véritable problème réside dans la capacité de la base de données et non dans le cache, et l’hashage cohérent a transformé ce problème d’un échec fatal en un problème visible. Notez également qu’il n’y a eu aucune panne matérielle : les demandes concernant les clés du nœud défaillant ont été redirigées vers le nœud suivant et sont devenues des échecs ordinaires.

Péripéties en production non couvertes par l’algorithme

Plusieurs problèmes échappent à l’algorithme et vous causeront des difficultés quel que soit le cas.

Décalage de version du anneau

La boucle ne fonctionne que si chaque client calcule la même réponse. Mettez en place le changement de composition du groupe progressivement : pendant quelques minutes, la moitié du réseau verra 8 nœuds tandis que l’autre moitié en verra 9. Les deux groupes seront en désaccord concernant environ 11 % des clés. Pour un cache, cela entraîne une légère baisse du taux de réussite des accès ; pour tout système acceptant des écritures, cela signifie des données divergentes. Versionnez l’ensemble des membres du groupe, distribuez-le via un seul canal, et indiquez la version dans vos métriques afin que vous puissiez observer les écarts plutôt que de les deviner.

Éjecter trop rapidement les nœuds

Ne supprimez pas un nœud après une seule délai d’attente. Un nœud qui quitte et rejoint constamment provoque une tempête de churn, car chaque transition déplace 1/N des clés. Exigez plusieurs échecs consécutifs dans une fenêtre de temps avant d’éjecter le nœud, et autorisez son réintégration avec prudence. L’exemple ci-dessus utilise une pénalité fixe de dix secondes ; le code en production devrait utiliser un backoff exponentiel ainsi qu’une vérification de santé avant de permettre à un nœud de revenir.

Les clés chaudes ne sont pas équilibrées

Le hachage cohérent répartit uniformément les clés, mais ne dit rien des demandes. Lorsqu’un produit devient soudainement très populaire, son entrée se trouve sur un seul serveur, ce qui provoque une surchauffe de ce dernier, même si le réseau de hachage fonctionne correctement. Deux solutions existent : un petit cache interne devant le réseau pour les clés les plus fréquentées, ou la variante de hachage cohérent à charges limitées développée par Google, qui limite la quantité de données que chaque nœud peut traiter et envoie l’excédent dans le sens des aiguilles d’une montre.

Le remappage n’est pas une migration

Tout ce qui précède part du principe que la perte d’une clé ne coûte qu’un échec de cache. Si l’anneau achemine des données durables, « 11 % des clés déplacées » signifie que 11 % des données doivent être copiées physiquement sur leur nouveau nœud avant de pouvoir y être lues, généralement avec des lectures ou écritures effectuées dans les deux emplacements jusqu’à ce que la copie soit terminée. L’anneau identifie ce qui doit être déplacé ; il ne fait rien pour le déplacer. C’est précisément pourquoi des systèmes comme Vitess reposent sur un coordinateur : ils doivent contrôler la migration, et non seulement la calculer.

Le nombre de répliques est en fait permanent

Changer la valeur de replicas de 160 à 500 modifie toutes les positions dans l’anneau et réorganise presque toutes les clés, ce qui est tout aussi perturbant qu’un changement de modulo. Considérez cela comme une décision de conception prise une seule fois avant l’arrivée des données réelles, et si vous n’êtes pas sûr, choisissez la valeur la plus élevée.

Lorsque l’anneau n’est pas l’outil adapté

Une partie du jugement d’ingénieur consiste à reconnaître quand la solution impressionnante est en réalité la mauvaise.

  • utilisez le hachage par rendez-vous. Il nécessite moins de code, offre un meilleur équilibre et ne requiert pas d’ajustement du nombre de répliques. L’avantage unique du réseau en anneau est une recherche en O(log N), ce qui reste théorique à cette échelle.
  • Buckets interchangeables où seul le comptage change : utilisez le hachage par saut, avec seulement dix lignes de code et sans consommation mémoire.
  • Données durables nécessitant un déplacement contrôlé : utilisez un coordinateur. Seul un tableau explicite permet de déplacer un shard unique tout en surveillant son impact, ce que le hachage ne peut pas assurer.
  • N qui ne change vraiment jamais : % N convient. Ne créez pas de mécanismes complexes pour un changement qui n’aura jamais lieu.

Une boucle mérite son utilisation lorsque les nœuds sont nommés, hétérogènes, nombreux et sujets à des pannes. Cela décrit presque parfaitement une flotte de caches, d’où le fait que tant de caches distribués soient basés sur ce principe.

Points clés

  • L’idée de base est simple : placer les clés et les serveurs dans un même espace d’adresses, afin qu’un changement de membre ne perturbe qu’une zone limitée plutôt que tout le système.
  • Le routage modulo transforme chaque événement de mise à l’échelle et chaque panne de nœud en un effacement quasi total des caches, et les dommages augmentent avec la taille du cluster.
  • L’hashing de type rendez-vous est souvent le meilleur choix pour de petites flottes ; optez pour la boucle lorsque la taille, le poids des nœuds et leur suppression arbitraire sont importants.
  • Sans nœuds virtuels, un seul serveur peut gérer plusieurs fois sa part légitime. Choisissez à l’avance le nombre de répliques, car en changer ultérieurement remet tout en cause.
  • Un hachage rapide présentant une faible avalanche peut réintroduire silencieusement un déséquilibre ; mesurez toujours la distribution, et non seulement la vitesse.
  • La perte d’un nœud entraîne l’envoi d’environ 1/N des lectures vers la base de données. Dimensionnez donc la base de données en conséquence, gérez les changements de membres avec prudence, éjectez les nœuds de manière conservatrice et traitez séparément les clés fréquemment utilisées.

    • Le réseau en anneau lui-même ne compte que quelques dizaines de lignes de code. L’ingénierie qui assure sa fiabilité en production réside dans tout ce qui l’entoure.

    Lectures complémentaires

    Tous les articlesEnvoyer le brief