Consistent Hashing

Du deployst einen neuen Cache-Node. Alles sieht gut aus. Dann rastet dein Monitoring aus. Cache Hit Rate: 0%. Deine Datenbank sieht plötzlich den kompletten Traffic. 10 Minuten lang.

Oder andersrum: ein Node stirbt. Selbes Ergebnis. Alles invalidiert. Alles neu von der DB. Und du fragst dich: warum trifft ein einzelner Node-Ausfall alle Keys?

Die Antwort ist simpel. Dein Cache nutzt hash(key) % N um zu entscheiden, welcher Node einen Key speichert. N ist die Anzahl der Nodes. Wenn N sich ändert — egal ob hoch oder runter — ändert sich das Ergebnis für fast jeden Key. Nicht nur für die Keys des ausgefallenen Nodes. Für alle.

Das ist kein Edge Case. Das ist Mathematik.

Entfern einen Node und schau was passiert:

Links: Modulo Hashing. ~80% der Keys werden umverteilt. Rechts: Consistent Hashing. Nur die Keys des entfernten Nodes wandern zum nächsten Nachbarn. Der Unterschied ist, ob deine DB den Spike überlebt oder nicht.

Der Ring

Die Idee hinter Consistent Hashing: statt hash % N platzierst du sowohl Nodes als auch Keys auf einem Ring (0° bis 360°, oder genauer: auf dem Wertebereich deiner Hashfunktion). Jeder Key gehört dem nächsten Node im Uhrzeigersinn.

Wenn ein Node wegfällt, wandern nur seine Keys zum nächsten Node. Alle anderen Keys bleiben wo sie sind. Kein globales Reshuffling.

Das klingt trivial. Ist es auch — konzeptionell. Aber die Konsequenz ist enorm: statt O(N) Key-Migrationen bei einer Topologie-Änderung hast du O(K/N), wobei K die Gesamtzahl der Keys ist. Bei einem Cluster mit 10 Nodes und einer Million Keys ist das der Unterschied zwischen einer Million Cache Misses und hunderttausend.

Virtual Nodes

Consistent Hashing hat ein Problem: mit wenigen physischen Nodes ist die Verteilung schlecht. Wenn du drei Nodes hast, die zufällig bei 10°, 15° und 20° landen, bekommt ein Node fast den gesamten Ring.

Fix: jeder physische Node bekommt mehrere virtuelle Positionen auf dem Ring. Statt einem Punkt pro Node hast du 50, 100 oder 200. Je mehr, desto gleichmäßiger die Verteilung.

Zieh den Slider und schau wie sich die Verteilung verändert:

Bei einem Virtual Node pro Physical Node: die Verteilung ist katastrophal. Ein Node kriegt vielleicht 60% der Keys, ein anderer 10%. Ab 15-20 Virtual Nodes wird die Verteilung fast perfekt. Die Standardabweichung geht gegen null.

In der Praxis nutzen die meisten Systeme 100-200 Virtual Nodes pro Physical Node. Der Overhead ist minimal, du speicherst nur ein paar hundert Einträge mehr in einer sortierten Map.

Implementation

Der Kern von Consistent Hashing passt in 30 Zeilen:

import { createHash } from 'crypto';

class HashRing<T> {
  private ring = new Map<number, T>();
  private sorted: number[] = [];

  constructor(private replicas = 150) {}

  private hash(key: string): number {
    const h = createHash('md5').update(key).digest();
    return h.readUInt32BE(0);
  }

  add(node: T) {
    for (let i = 0; i < this.replicas; i++) {
      const pos = this.hash(`${node}-${i}`);
      this.ring.set(pos, node);
    }
    this.sorted = [...this.ring.keys()].sort((a, b) => a - b);
  }

  remove(node: T) {
    for (let i = 0; i < this.replicas; i++) {
      const pos = this.hash(`${node}-${i}`);
      this.ring.delete(pos);
    }
    this.sorted = [...this.ring.keys()].sort((a, b) => a - b);
  }

  get(key: string): T | undefined {
    if (this.sorted.length === 0) return undefined;
    const h = this.hash(key);
    // Binary search for next node clockwise
    let lo = 0, hi = this.sorted.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      this.sorted[mid] < h ? (lo = mid + 1) : (hi = mid);
    }
    const idx = lo >= this.sorted.length ? 0 : lo;
    return this.ring.get(this.sorted[idx]);
  }
}

replicas sind die Virtual Nodes. 150 ist ein guter Default. Die get-Methode macht eine Binary Search: O(log N) statt O(N). Bei tausenden Virtual Nodes macht das einen Unterschied.

Wann brauchst du das?

Distributed Caches. Memcached und Redis Cluster nutzen Consistent Hashing. Wenn ein Node ausfällt, betrifft der Cache Miss nur 1/N der Keys statt alle.

Load Balancer. Wenn du Session Affinity brauchst (gleicher User, gleicher Backend-Server), löst Consistent Hashing das Problem. Node geht weg? Nur die Sessions dieses Nodes werden umverteilt.

Datenbank-Sharding. Wenn du horizontal partitionierst und Shards hinzufügst oder entfernst, willst du nicht die gesamte Datenbank umschaufeln.

Wenn du eine feste Anzahl an Nodes hast die sich nie ändert, ist hash % N einfacher und reicht völlig.

Jede Caching-Bibliothek die hash % N nutzt und nicht mindestens eine Warnung ausgibt, hat dieses Problem eingebaut. Du merkst es nicht beim Entwickeln. Du merkst es nicht im Staging. Du merkst es um 3 Uhr morgens, wenn ein Node stirbt und deine DB 10 Minuten lang unter Volllast steht.