RedisBloom: Probabilistische Datenstrukturen jenseits von HyperLogLog

1. Wo HyperLogLog an seine Grenzen stößt

HyperLogLog beantwortet eine einzige Frage sehr effizient: Wie viele unterschiedliche Elemente wurden gesehen. Für die häufig ebenso wichtige Frage, ob ein konkretes einzelnes Element bereits gesehen wurde, ist HyperLogLog nicht gedacht, es liefert nur die Kardinalität einer Menge, keine Mitgliedschaftsauskunft über ein einzelnes Element.

RedisBloom schließt genau diese Lücke mit einer Familie probabilistischer Datenstrukturen, die jeweils für unterschiedliche Fragestellungen optimiert sind: Wurde dieses Element schon gesehen, welche Elemente kommen am häufigsten vor, und wie lässt sich ein Mitgliedschaftstest auch wieder rückgängig machen, was mit klassischen Bloom-Filtern grundsätzlich nicht möglich ist.

2. Bloom-Filter: Grundprinzip und Falsch-Positive-Rate

Ein Bloom-Filter ist eine Bitmap fester Größe zusammen mit mehreren Hashfunktionen. Beim Hinzufügen eines Elements werden mehrere Bit-Positionen anhand der Hashfunktionen gesetzt, bei einer Abfrage wird geprüft, ob alle relevanten Bits gesetzt sind. Sind sie es nicht, war das Element garantiert nicht enthalten, sind sie es doch, war das Element wahrscheinlich enthalten, aber eben nicht sicher, weil unterschiedliche Elemente dieselben Bits gesetzt haben können.

Diese Unsicherheit wird als Falsch-Positive-Rate bezeichnet und lässt sich beim Anlegen des Filters gezielt konfigurieren: Eine niedrigere Falsch-Positive-Rate erfordert mehr Bits pro Element und damit mehr Speicherverbrauch, eine höhere Rate spart Speicher, riskiert aber häufigere falsche Treffer. RedisBloom erlaubt es, diese Fehlerrate explizit beim Erstellen des Filters festzulegen, statt sie implizit hinzunehmen.

redis-cli BF.RESERVE gesehene_artikel:user4711 0.01 100000

redis-cli BF.ADD gesehene_artikel:user4711 artikel:9981

redis-cli BF.EXISTS gesehene_artikel:user4711 artikel:9981
# 1

redis-cli BF.EXISTS gesehene_artikel:user4711 artikel:1234
# 0 oder 1 (bei 1 möglich falsch positiv, mit Rate 0.01)

3. Praxisbeispiel: Wurde dieser Artikel schon gesehen

Ein klassischer Anwendungsfall im E-Commerce ist die Frage, ob ein Nutzer ein bestimmtes Produkt bereits angesehen hat, etwa um bereits gesehene Empfehlungen nicht erneut anzuzeigen oder um Wiederholungsbesuche für Retargeting-Zwecke zu erkennen. Bei Millionen Nutzern und Produkten wäre ein exaktes Set pro Nutzer speicherintensiv, ein Bloom-Filter pro Nutzer benötigt dagegen nur wenige Kilobyte, selbst bei zehntausenden gesehenen Artikeln.

Die Falsch-Positive-Rate ist für diesen Anwendungsfall meist gut tolerierbar: Wird ein noch nicht gesehener Artikel gelegentlich fälschlich als gesehen eingestuft und deshalb aus einer Empfehlung ausgeschlossen, ist der Schaden gering, verglichen mit dem Speicheraufwand eines exakten Sets über alle Nutzer und Artikel hinweg. Genau in solchen Fällen mit tolerierbarer Fehlerrate spielt ein Bloom-Filter seinen Speichervorteil voll aus.

4. Cuckoo-Filter: Bloom-Filter-Alternative mit Lösch-Unterstützung

Ein grundlegendes Problem klassischer Bloom-Filter ist, dass sich einzelne Elemente nicht wieder entfernen lassen, ohne dabei versehentlich auch andere Elemente, die dieselben Bits nutzen, aus dem Filter zu löschen. Für Anwendungsfälle, in denen Elemente wieder entfernt werden müssen, etwa ein zeitlich begrenztes Sichtbarkeitsfenster für gesehene Artikel, ist ein klassischer Bloom-Filter deshalb ungeeignet.

Cuckoo-Filter lösen dieses Problem, indem sie statt gesetzter Bits kompakte Fingerabdrücke der Elemente in einer Hashtabelle mit Cuckoo-Hashing speichern. Ein einzelnes Element lässt sich gezielt entfernen, indem sein Fingerabdruck aus der entsprechenden Bucket-Position gelöscht wird, ohne andere Elemente zu beeinträchtigen. Der Preis dafür ist ein etwas höherer Speicherbedarf pro Element im Vergleich zu einem gleich genauen Bloom-Filter.

redis-cli CF.RESERVE gesehene_artikel_temp:user4711 100000

redis-cli CF.ADD gesehene_artikel_temp:user4711 artikel:9981

redis-cli CF.DEL gesehene_artikel_temp:user4711 artikel:9981

5. Top-K: Die häufigsten Elemente ohne vollständiges Zählen

Während Bloom- und Cuckoo-Filter reine Mitgliedschaftstests beantworten, löst die Top-K-Struktur eine andere Frage: Welche Elemente kommen in einem Datenstrom am häufigsten vor, ohne dass jedes einzelne Element exakt gezählt werden muss. Das ist etwa für die meistgesuchten Begriffe in einer Shop-Suche oder die meistgeklickten Produkte innerhalb eines Zeitfensters relevant, bei sehr hoher Anzahl unterschiedlicher Begriffe.

Intern arbeitet TOPK mit einem festen Speicherbudget für eine begrenzte Anzahl von Kandidaten und approximiert damit die tatsächliche Rangfolge, statt eine exakte Zählung über alle jemals gesehenen Begriffe zu führen. Für die meisten Anwendungsfälle, in denen nur die Spitze der Häufigkeitsverteilung interessiert, etwa die zehn meistgesuchten Begriffe des Tages, liefert das eine sehr gute Approximation bei konstantem, vorhersehbarem Speicherverbrauch.

redis-cli TOPK.RESERVE top_suchbegriffe 10 2000 7 0.9

redis-cli TOPK.ADD top_suchbegriffe "sommerjacke" "sommerjacke" "wanderschuhe"

redis-cli TOPK.LIST top_suchbegriffe WITHCOUNT

6. Falsch-Positive-Rate richtig dimensionieren

Die Wahl der Falsch-Positive-Rate ist keine rein technische Entscheidung, sondern hängt vom konkreten Schaden ab, den ein falscher Treffer verursacht. Bei einer Duplikaterkennung, die verhindern soll, dass dieselbe E-Mail zweimal versendet wird, ist eine niedrige Fehlerrate wichtig, weil ein falsch positiver Treffer eine berechtigte E-Mail unterdrücken würde. Bei einer reinen Anzeige-Optimierung wie bereits gesehenen Produktempfehlungen ist eine höhere Fehlerrate meist unproblematisch.

RedisBloom erlaubt es, diese Abwägung explizit beim Anlegen des Filters über den gewünschten Fehlerrate-Parameter zu treffen, statt sie einer festen, unveränderlichen Implementierung zu überlassen. Wichtig dabei: Die Fehlerrate gilt für die beim RESERVE angegebene erwartete Kapazität, wird diese deutlich überschritten, steigt die tatsächliche Falsch-Positive-Rate spürbar über den konfigurierten Wert.

7. Speicherverbrauch realistisch abschätzen

Der Speichervorteil probabilistischer Strukturen gegenüber exakten Sets ist der zentrale Grund für ihren Einsatz, sollte aber nicht blind vorausgesetzt werden. Ein Bloom-Filter für hunderttausend Elemente mit einer Falsch-Positive-Rate von einem Prozent benötigt üblicherweise nur wenige hundert Kilobyte, ein exaktes Set mit denselben Elementen als vollständige Strings kann dagegen leicht mehrere Megabyte belegen, abhängig von der durchschnittlichen Elementlänge.

Bei sehr vielen kleinen Filtern, etwa einem Bloom-Filter pro einzelnem Nutzer bei Millionen Nutzern, summiert sich jedoch selbst ein kleiner Overhead pro Filter schnell auf einen erheblichen Gesamtspeicherbedarf. In solchen Fällen lohnt sich vorab eine realistische Hochrechnung mit MEMORY USAGE auf einer repräsentativen Stichprobe, statt sich allein auf die theoretische Platzersparnis pro einzelnem Filter zu verlassen.

redis-cli MEMORY USAGE gesehene_artikel:user4711 SAMPLES 0

8. Abgrenzung zu Count-Min Sketch und HyperLogLog

RedisBloom bringt neben Bloom-, Cuckoo- und Top-K-Filtern auch eine Count-Min-Sketch-Struktur mit, die im Gegensatz zu Top-K nicht nur die häufigsten Elemente liefert, sondern für jedes beliebige Element eine approximierte Häufigkeit schätzt. Das eignet sich für Fragestellungen wie wie oft wurde dieser konkrete Suchbegriff angefragt, während Top-K eher für die Frage was sind die häufigsten Begriffe insgesamt gedacht ist.

HyperLogLog bleibt dabei als eigener, im Redis-Kern eingebauter Datentyp bestehen und deckt weiterhin ausschließlich die Kardinalitätsschätzung ab. Wer sowohl wissen möchte, wie viele unterschiedliche Nutzer einen Artikel gesehen haben, als auch, ob ein bestimmter einzelner Nutzer ihn gesehen hat, kombiniert in der Praxis häufig HyperLogLog für die erste und einen Bloom- oder Cuckoo-Filter für die zweite Fragestellung.

9. Praktische Einsatzgrenzen von RedisBloom

Alle Strukturen aus RedisBloom sind bewusst approximativ, sie eignen sich nicht für Fälle, in denen absolute Korrektheit zwingend erforderlich ist, etwa bei Finanztransaktionen oder Bestandsführung. Für solche Anwendungsfälle bleiben exakte Datentypen wie Sets, Sorted Sets oder relationale Datenbanken die richtige Wahl, unabhängig vom Speichervorteil probabilistischer Strukturen.

Ein weiterer praktischer Punkt: Wie RedisJSON und RediSearch ist auch RedisBloom kein Bestandteil des Standard-Redis-Servers, sondern muss als Modul über Redis Stack oder eine entsprechende Managed-Umgebung bereitgestellt werden. Vor dem produktiven Einsatz lohnt sich deshalb ein Blick in die Modulliste der genutzten Redis-Instanz, um Überraschungen bei fehlenden BF.*-, CF.*- oder TOPK.*-Befehlen zu vermeiden.

redis-cli MODULE LIST

10. Zusammenfassung

11. FAQ: RedisBloom: Das Wichtigste auf einen Blick