Probabilistische Strukturen und Consistent Hashing: Bloom Filter und der Hash-Ring

Track Konzepte · Datenstrukturen und Algorithmen · ca. 50 Min.

Was du aus Teil a brauchst

Eine Hashmap verteilt Schlüssel mit einer Hashfunktion auf Buckets, und sie bleibt nur schnell, wenn die Hashfunktion gleichmäßig streut. Big O zählt Schritte, nicht Sekunden, und genau so messen wir auch hier. Falls das neu ist: Teil 1.

Worum es geht

Zwei Probleme aus dem Betrieb. Erstens: Du willst wissen, ob eine Mail-Adresse bei Milliarden Einträgen schon bekannt ist, aber ein Set dafür braucht zu viel Speicher. Zweitens: Du verteilst Cache-Schlüssel auf mehrere Server, ein Server kommt dazu, und plötzlich sind fast alle Einträge am falschen Ort. Beide Probleme haben eine elegante Lösung mit einer Hashfunktion im Zentrum.

Am Ende dieses Teils kannst du:

• einen Bloom Filter (Bloom filter) bauen und sagen, in welche Richtung er sich irrt (Übung 1),
• am Hash-Ring vorhersagen, welcher Server einen Schlüssel bekommt und was bei einem Ausfall wandert (Übung 2),
• mit Consistent Hashing (consistent hashing) erklären, warum beim Hinzufügen eines Servers nur ein Teil der Schlüssel wandert, und es selbst bauen (Übung 3).

Plane ehrlich 50 Minuten ein: etwa 18 Minuten Lesen, 32 Minuten Übungen (drei Stück, die letzte ist die längste). Eine gute Pause ist nach Übung 1.

Von JS/TS her gedacht

Baustein	JS/TS (Node)	Python
Hash eines Textes	crypto.createHash("sha256").update(s).digest()	hashlib.sha256(s.encode()).digest()
Bit-Array	Uint8Array	bytearray oder eine Liste aus 0 und 1
Sortierte Positionen, binäre Suche	von Hand oder Bibliothek	bisect.bisect_right

In beiden Sprachen ist ein Hash nur ein Mittel, Eingaben gleichmäßig auf einen Zahlenbereich zu streuen. Alles Weitere sind kleine Rechnungen mit Positionen, die wir hier mit Python ausführen.

Konzept

Schritt 1: Probabilistische Strukturen und der Bloom Filter

Manchmal ist exakt zu teuer. Eine Frage wie “Habe ich diese Mail-Adresse schon gesehen?” bei Milliarden Einträgen kostet als Set zu viel Speicher. Probabilistische Strukturen (probabilistic data structures) tauschen Genauigkeit gegen Platz, und das Entscheidende ist, wie sie sich irren.

Ein Bloom Filter ist ein Bit-Array der Länge m (am Anfang alles 0) und k Hashfunktionen.

• add(x): berechne k Positionen (je eine pro Hashfunktion) und setze diese k Bits auf 1.
• x in filter: berechne dieselben k Positionen. Ist mindestens ein Bit 0, ist x sicher nicht enthalten. Sind alle k Bits 1, ist x vielleicht enthalten.

Die k Hashfunktionen bekommst du, indem du vor den Wert eine Nummer hängst ("0:anna", "1:anna") und jeweils einen SHA-256 bildest. Ein kleines Beispiel mit m = 16 und k = 2:

Ausgabe:

0001100000000001
anna [4, 15] vielleicht enthalten
cem [5, 3] sicher nicht enthalten
user5 [15, 3] vielleicht enthalten

Gehe es Zeile für Zeile durch. anna hat die Positionen 4 und 15, bora die Positionen 3 und 15. Zusammen sind die Bits 3, 4 und 15 gesetzt. anna wird gefunden, zu Recht. cem hat Position 5, und Bit 5 ist 0: sicher nicht enthalten. user5 hat die Positionen 15 und 3, beide Bits sind 1 (sie stammen von bora und anna), obwohl user5 nie hinzugefügt wurde: ein False Positive (falsch positiv, “vielleicht” war falsch).

Die Fehlerrichtung ist die Antwort auf den Prüfstein:

• Ein Bloom Filter hat nie False Negatives. Wer hinzugefügt wurde, hat seine k Bits gesetzt, und Bits werden nie zurückgesetzt. “Nein” stimmt also immer.
• Er hat False Positives. “Ja” heißt nur “vielleicht”. Die Rate sinkt, wenn m größer wird und wenn k passend gewählt ist, und sie steigt mit der Zahl der eingefügten Elemente.

Daraus folgt der Einsatz: ein billiger Vorfilter vor einer teuren Prüfung. “Nein” des Filters spart den Datenbankzugriff. “Vielleicht” geht trotzdem zur Datenbank, die dann endgültig antwortet. Ein Falsch-Positiv kostet nur einen unnötigen Zugriff, nie ein falsches Ergebnis. Löschen geht in der einfachen Form nicht (ein Bit kann zu mehreren Elementen gehören).

Zwei Verwandte, nur kurz (allgemeines Fachwissen, Zahlen hier nicht gemessen, bitte prüfen, bevor du sie weitergibst): HyperLogLog schätzt die Anzahl verschiedener Elemente (cardinality) mit sehr wenig Speicher und einem kleinen relativen Fehler in beide Richtungen. Count-Min Sketch schätzt Häufigkeiten und kann nur zu hoch schätzen, nie zu niedrig, weil Kollisionen Zähler erhöhen.

Schritt 2: Consistent Hashing, wenn Server dazukommen

Du verteilst Cache-Schlüssel auf N Server. Die naheliegende Regel ist hash(key) % N. Das funktioniert, bis sich N ändert. Wir messen, wie viele von 20000 Schlüsseln einen anderen Server bekommen, wenn ein Server dazukommt:

Ausgabe:

4 -> 5 Knoten: 79.6% der Schlüssel wandern
10 -> 11 Knoten: 90.8% der Schlüssel wandern

Fast alles wandert. Bei einem Cache heißt das: Nach dem Hinzufügen eines Servers sind die meisten Einträge am falschen Ort, fast jede Anfrage geht ins Leere und trifft die Datenbank (ein Cache-Sturm, ähnlich wie ein Thundering Herd aus Lektion 7). Idealer wäre: Ein neuer Server übernimmt etwa 1/(N+1) der Schlüssel (hier 1/5 = 20 Prozent) und nimmt sie nur anderen Servern weg. Alles andere bleibt, wo es ist.

Consistent Hashing erreicht das mit einem Ring:

1. Der Hashraum wird zu einem Kreis (der größte Hashwert schließt wieder an 0 an).
2. Jeder Server bekommt eine Position auf dem Ring (Hash seines Namens).
3. Ein Schlüssel wird ebenfalls gehasht und gehört dem ersten Server im Uhrzeigersinn, also dem nächsten Serverpunkt mit Position größer als der Schlüsselwert. Hinter der letzten Position geht es bei der ersten weiter (Wrap-around).

Ein Rechenbeispiel im kleinen Hashraum 0 bis 99. Server A bei 10, B bei 45, C bei 80. Danach kommt D bei 60 dazu:

Ausgabe:

['A', 'B', 'C', 'C', 'A']
['A', 'B', 'D', 'C', 'A']

Die Schlüssel 5, 30, 47, 70 und 90 liegen auf dem Ring. Die 90 hat hinter sich keinen Server mehr und geht per Wrap-around an A (Position 10). Nach dem Hinzufügen von D ändert sich genau ein Schlüssel: die 47, die jetzt vor D (60) liegt statt vor C (80). Alle anderen bleiben. Es wandern nur Schlüssel im Abschnitt zwischen 45 und 60, und sie wandern zu D, nie zwischen alten Servern.

bisect_right findet in der sortierten Positionsliste den ersten Eintrag hinter dem Hashwert (Suche in O(log n)). % len(...) erledigt den Wrap-around.

Ein Problem bleibt: Mit einer Position pro Server fällt der Ring ungleich auf, ein Server bekommt viel, ein anderer wenig. Die Lösung sind virtuelle Knoten (virtual nodes, vnodes): Jeder Server bekommt viele Positionen, z. B. 100, indem man "name#0", "name#1", … hasht. Das glättet die Verteilung. Gemessen (4 Server n1 bis n4, 20000 Schlüssel key-0 bis key-19999, Positionen als SHA-256 von "name#i"): Mit einer Position je Server lagen die Anteile zwischen 7 und 37 Prozent, mit 100 Positionen zwischen 24 und 26 Prozent.

Eine kurze Randnotiz, ohne Übung: Merkle Trees (Hash-Bäume) hängen Hashes von Blöcken in einem Baum zusammen, sodass zwei Replikate mit wenigen Vergleichen finden, wo sie sich unterscheiden (allgemeines Fachwissen, kommt später in der Replikation vor).

Falle

1. Bloom Filter als Wahrheit behandeln. “Ja” heißt “vielleicht”. Wer aus “ja” direkt handelt (etwa “Mail ist schon registriert”, ohne in der Datenbank nachzusehen), liefert falsche Antworten.
2. % N bei verteilten Caches. Jede Änderung von N verschiebt fast alle Schlüssel (Übung 3).
3. Nur eine Position pro Server auf dem Ring. Die Last fällt ungleich aus. Erst viele virtuelle Knoten glätten sie.

Übungen

Übung 1: Bloom Filter selbst bauen (ca. 10 Min.)

Baue den Bloom Filter aus Schritt 4 als Klasse Bloom(m, k) mit add(item) und dem Operator in (__contains__). Die Hilfsfunktion positionen(item, k, m) aus Schritt 4 steht bereit. Sie liefert die Liste der k Positionen eines Elements.

Der Check fügt 1000 Mail-Adressen in einen Filter mit m=8000, k=7 ein und prüft zwei Dinge:

• Nie ein False Negative: jede hinzugefügte Adresse wird gefunden.
• Die Rate der False Positives bei 5000 fremden Adressen liegt in einem erwartbaren Bereich (Bloom-typisch, nicht null). Wer die Adressen heimlich selbst speichert, fliegt auf.

Die letzte Zeile gibt die Klasse zurück.

Was speichert der Filter überhaupt, und was darf er auf keinen Fall speichern? Beim Prüfen muss ein einziges Bit mit Wert 0 reichen, um “sicher nicht” zu sagen. Wie viele Bits müssen dagegen 1 sein, damit er “vielleicht” sagt?

class Bloom:
    def __init__(self, m, k):
        self.m, self.k = m, k
        self.bits = bytearray(m)

    def add(self, item):
        for p in positionen(item, self.k, self.m):
            self.bits[p] = 1

    def __contains__(self, item):
        return all(self.bits[p] for p in positionen(item, self.k, self.m))

Bloom

add setzt k Bits, in verlangt, dass alle k Bits gesetzt sind. Bits werden nie gelöscht, darum kann ein Element, das hinzugefügt wurde, nie “verschwinden”: keine False Negatives.

Übung 2: Den Ring von Hand lesen (ca. 6 Min.)

Hashraum 0 bis 99, drei Server auf dem Ring: X bei 20, Y bei 55, Z bei 90. Ein Schlüssel gehört dem ersten Server mit einer Position größer als sein Hashwert, hinter der letzten Position geht es bei der ersten weiter (wie in Schritt 2). Die Schlüssel haben die Hashwerte 3, 21, 56, 91, 99, 54 (in dieser Reihenfolge).

Trage ein Tupel (vorher, nachher, wandern) ein:

• vorher: ein String aus sechs Buchstaben, der Server jedes Schlüssels (z. B. "XXYZZX"),
• nachher: derselbe String, nachdem Y ausgefallen und vom Ring entfernt ist,
• wandern: wie viele der sechs Schlüssel dabei den Server wechseln (ganze Zahl).

Die Funktion suche aus dem Text gibt es hier nicht, rechne von Hand oder baue sie dir selbst in die Zelle.

Lege die Positionen sortiert auf einen Kreis und gehe für jeden Hashwert im Uhrzeigersinn zum nächsten Server. Was passiert hinter der größten Position? Und welche Schlüssel gehörten dem ausgefallenen Server: Nur die müssen sich einen neuen suchen, oder alle?

antwort = ("XYZXXY", "XZZXXZ", 2)
antwort

Vorher: 3 liegt vor X (20), 21 vor Y (55), 56 vor Z (90), 91 und 99 haben hinter sich keinen Server mehr und gehen per Wrap-around an X, 54 liegt vor Y (55). Nach dem Ausfall von Y bleiben X (20) und Z (90): 3 bleibt bei X, 21 und 54 (vorher Y) gehen weiter zu Z (90), 56 bleibt bei Z, 91 und 99 bleiben bei X. Es wandern genau die Schlüssel des ausgefallenen Servers, also 2 von 6.

Übung 3: Consistent Hashing messen und bauen (ca. 12 Min.)

Baue die Klasse Ring mit virtuellen Knoten:

• Ring(knoten, vnodes=100): knoten ist eine Liste von Servernamen. Jeder Server bekommt vnodes Positionen auf dem Ring: der Hash (h, steht bereit) von f"{name}#{i}" für i von 0 bis vnodes - 1.
• hinzufuegen(name): nimmt einen weiteren Server mit seinen Positionen auf.
• knoten_fuer(key): liefert den Server, der zum ersten Ring-Punkt mit Position größer als h(key) gehört, hinter der letzten Position geht es wieder bei der ersten los (Wrap-around).

Der Check legt 4 Server und 20000 Schlüssel an, fügt einen fünften Server hinzu und misst, wie viele Schlüssel wandern, wohin sie wandern und wie gleichmäßig die Last verteilt ist.

Die letzte Zeile gibt die Klasse zurück.

Welche Sorte Liste braucht bisect, und was musst du nach jedem hinzufuegen mit ihr tun? Was passiert mit dem Index, wenn der Schlüssel hinter der letzten Position liegt? Und wo soll der Name des Servers zu finden sein, wenn du nur die Position kennst?

class Ring:
    def __init__(self, knoten, vnodes=100):
        self.vnodes = vnodes
        self.punkte = []                      # Liste von (Position, Servername), sortiert
        self.positionen = []                  # nur die Positionen, für bisect
        for name in knoten:
            self._eintragen(name)
        self._sortieren()

    def _eintragen(self, name):
        for i in range(self.vnodes):
            self.punkte.append((h(f"{name}#{i}"), name))

    def _sortieren(self):
        self.punkte.sort()
        self.positionen = [p for p, _ in self.punkte]

    def hinzufuegen(self, name):
        self._eintragen(name)
        self._sortieren()

    def knoten_fuer(self, key):
        i = bisect.bisect_right(self.positionen, h(key)) % len(self.punkte)
        return self.punkte[i][1]

Ring

Die sortierte Positionsliste macht die Suche zu O(log n), % len(...) erledigt den Wrap-around. Beim Hinzufügen kommen nur neue Punkte dazu, die alten bleiben. Darum können Schlüssel nur zum neuen Server wandern.

Merksatz

Ein Bloom Filter irrt sich nur mit “vielleicht” und nie mit “nein”, und Consistent Hashing lässt beim Hinzufügen oder Ausfall eines Servers nur einen Teil der Schlüssel wandern, weil ein Schlüssel dem ersten Server im Uhrzeigersinn gehört.

Prüfstein

Wie beantwortet ein Bloom Filter die Frage “ist enthalten”, wann liegt er falsch, und in welche Richtung?

---

Quelle: quellen/konzeptuebersicht-software-fortgeschritten.docx, Abschnitt “2. Algorithmen und Datenstrukturen im Einsatz” (Probabilistische Strukturen Bloom Filter, HyperLogLog, Count-Min Sketch; Consistent Hashing, Merkle Trees; Prüfstein zum Bloom Filter).

Über die Quelle hinaus (allgemeines Fachwissen): die Aussagen zu HyperLogLog und Count-Min Sketch (Fehlerrichtungen, bitte prüfen), die Erklärung von Merkle Trees, die Faustregel für virtuelle Knoten, das Rechenbeispiel im Hashraum 0 bis 99 und die Regel “erster Server mit Position größer als der Hashwert” (eine Konvention, andere Systeme wählen größer oder gleich). Alle Zahlen und Ausgaben in dieser Lektion stammen aus dem Ausführen des Codes mit Python 3.