Qu'est-ce que le hachage cohérent ?

Question

Accepted Answer

**Le hachage cohérent** est une technique pour distribuer les données sur des nœuds (serveurs) qui **minimise la redistribution lorsque des nœuds sont ajoutés ou supprimés** — contrairement au hachage simple, qui remappage la plupart des clés lorsque le nombre de nœuds change. C'est important pour les caches distribués, les bases de données et la distribution de charge.

## Le problème avec le hachage simple

```text
Simple approach: node = hash(key) % N  (N = number of nodes)
  ✗ when N CHANGES (add/remove a node), N changes → MOST keys remap to different nodes →
    massive data movement / cache invalidation (almost everything moves!)
→ adding/removing a server causes huge disruption → bad for dynamic distributed systems.
```

## Comment fonctionne le hachage cohérent

```text
Map both NODES and KEYS onto a HASH RING (a circle of hash values):
  → a key belongs to the FIRST node clockwise from it on the ring
  → adding/removing a node only affects keys in ONE segment of the ring (its neighbors) →
    only a SMALL fraction of keys move (≈ K/N, not most of them)
→ minimal redistribution when nodes change → much better for dynamic systems.
```

## Nœuds virtuels et cas d'usage

```text
✓ VIRTUAL NODES → each physical node maps to MANY points on the ring → EVEN distribution
  (avoids uneven load from few nodes/uneven placement) → handles heterogeneous capacity
USES:
  → distributed CACHES (e.g. memcached clusters) — add/remove cache nodes without mass
    invalidation
  → distributed DATABASES (Cassandra, DynamoDB) — partition data across nodes
  → load balancers; any system distributing data/load across a changing set of nodes
```

## Pourquoi c'est important

Comprendre le hachage cohérent est une connaissance précieuse au niveau senior car c'est une **technique fondamentale pour distribuer les données dans des systèmes distribués dynamiques**, utilisée dans de nombreux systèmes réels, ce qui en fait un élément important pour la conception de systèmes distribués.

Le problème qu'il résout est réel et important : **le hachage simple** (`hash(key) % N`) provoque **le remappage de la plupart des clés lorsque le nombre de nœuds change** (ajouter ou supprimer un serveur déplace presque toutes les données — causant un mouvement massif de données ou une invalidation de cache), ce qui le rend terrible pour les systèmes distribués dynamiques où des nœuds sont ajoutés et supprimés. **Le hachage cohérent** résout ce problème en mappant à la fois les nœuds et les clés sur un **anneau de hachage** (une clé appartenant au premier nœud dans le sens des aiguilles d'une montre), de sorte que **ajouter ou supprimer un nœud ne déplace qu'une petite fraction de clés** (celles d'un segment d'anneau, ≈ K/N) plutôt que la plupart — minimisant la redistribution et les perturbations lorsque l'ensemble des nœuds change.

Comprendre cela — comment l'anneau fonctionne et pourquoi il minimise le mouvement des clés — est la clé de cette compréhension.

Comprendre les **nœuds virtuels** (mapper chaque nœud physique à de nombreux points d'anneau pour une distribution uniforme, en évitant la charge inégale que quelques nœuds ou des nœuds mal placés causent, et en gérant la capacité hétérogène) reflète comment le hachage cohérent fonctionne bien en pratique.

Comprendre les **cas d'usage** — caches distribués (ajouter/supprimer des nœuds de cache sans invalidation massive), bases de données distribuées (Cassandra, partitionnement de données DynamoDB) et équilibreurs de charge — clarifie son importance, car il est utilisé dans de nombreux systèmes réels et largement adoptés.

Le hachage cohérent est une technique classique et importante de systèmes distribués qui apparaît fréquemment dans les discussions sur la conception de systèmes.

Étant donné que distribuer les données sur un ensemble dynamique de nœuds (avec une disruption minimale lorsque les nœuds changent) est un besoin courant dans les systèmes distribués et que le hachage cohérent le résout (là où le hachage simple échoue gravement), et puisqu'il est utilisé dans les systèmes réels (caches distribués et bases de données) et que sa compréhension reflète la connaissance des systèmes distribués, comprendre le hachage cohérent est une connaissance précieuse au niveau senior — une technique fondamentale pour la distribution de données dans les systèmes distribués dynamiques, utilisée dans de nombreux caches et bases de données réels, résolvant le problème de redistribution des clés du hachage simple, et un concept classique de systèmes distribués reflétant la profondeur attendue pour les rôles senior concevant des systèmes distribués.