Antworten ohne Gedächtnis: Bloom-Filter, HyperLogLog und die Kunst des kalkulierten Irrtums

Der Aufhänger: Die Frage, die ein Rechenzentrum kostet

Stell dir eine Frage vor, die so banal klingt, dass sie in jedem Produktmeeting in dreißig Sekunden gestellt und in keiner Architektur in dreißig Tagen gelöst wird: „Wie viele verschiedene Nutzer waren letzten Monat auf unserer Plattform?"

Nicht „wie viele Seitenaufrufe" – das ist ein Zähler, eine Addition, trivial. Sondern: wie viele verschiedene. Die Mengenlehre nennt das Kardinalität. Und Kardinalität ist die teuerste Frage der Datenverarbeitung, weil sie ein Gedächtnis verlangt.

Um exakt zu wissen, wie viele verschiedene Nutzer es waren, musst du jeden einzelnen schon gesehenen Nutzer behalten. Du brauchst eine Menge, ein HashSet, einen Index – irgendetwas, das für jedes neue Element nachschlagen kann: „kenne ich dich schon?" Bei 500 Millionen eindeutigen Nutzer-IDs à 16 Byte sind das 8 Gigabyte reine Nutzdaten, in der Praxis mit Hash-Overhead und Pointern eher 30 bis 50 Gigabyte Arbeitsspeicher. Für eine Zahl. Pro Zeitfenster. Pro Dimension, die du aufschlüsseln willst – Land, Gerät, Kampagne, Tarif. Die Kombinatorik frisst dich auf, lange bevor die Daten es tun.

Und jetzt kommt die Pointe, die fast fünfzig Jahre alt ist und trotzdem die meisten Architekten erst dann erreicht, wenn ihr Cluster brennt: Du brauchst das Gedächtnis gar nicht. Du kannst dieselbe Frage mit 12 Kilobyte beantworten – nicht Gigabyte, Kilobyte – und zwar mit einem typischen Fehler von unter einem Prozent. Die Ersparnis ist nicht ein Faktor zehn. Sie ist ein Faktor von mehreren Millionen.

Der Preis dafür ist eine einzige, präzise definierte Konzession: Du gibst die Gewissheit auf und bekommst eine Fehlerschranke zurück. Nicht „irgendwie ungenau", sondern mathematisch beschrieben, beweisbar beschränkt, im Voraus konfigurierbar.

Diese Klasse von Werkzeugen heißt probabilistische Datenstrukturen, im Jargon auch Sketches – Skizzen. Sie sind der Grund, warum APPROX_COUNT_DISTINCT in BigQuery in Sekunden antwortet, wo COUNT(DISTINCT …) Minuten braucht. Sie sind der Grund, warum Cassandra und RocksDB nicht bei jeder Leseanfrage die Festplatte quälen. Und sie sind, so meine These für diesen Artikel, die eleganteste Lektion über Systemdesign überhaupt: dass man einen Fehler entwerfen kann, statt ihn zu erleiden.

Teil 1: Das Grundprinzip – Gewissheit gegen Fehlerschranke tauschen

Das Streaming-Modell

Alle Sketches, über die wir sprechen, leben in einem gemeinsamen Berechnungsmodell: dem Datenstrommodell. Die Annahmen sind streng, und genau diese Strenge macht die Ergebnisse so stark:

• Die Elemente kommen einmal vorbei, in beliebiger Reihenfolge (one pass).
• Der verfügbare Speicher ist sublinear in der Datenmenge, typischerweise logarithmisch oder konstant.
• Die Verarbeitung pro Element ist O(1) oder nahe daran.
• Es gibt kein Zurückspulen. Was du nicht in deinen Sketch geschrieben hast, ist für immer weg.

In diesem Modell ist exaktes Zählen verschiedener Elemente nachweislich unmöglich ohne Speicher proportional zur Kardinalität. Das ist kein Implementierungsproblem, das ist eine informationstheoretische Untergrenze. Wer exakt antworten will, muss sich erinnern können.

Also lockert man die Anforderung – und zwar nicht irgendwie, sondern gezielt.

Die drei Dimensionen der Konzession

Es gibt genau drei Dinge, die ein Sketch opfern kann. Welche davon er opfert, definiert ihn:

1. Exaktheit des Werts (ε): Die Antwort ist nicht die Wahrheit, sondern liegt mit hoher Wahrscheinlichkeit nahe dabei. Beispiel: HyperLogLog liefert eine Kardinalität mit ~1 % relativem Standardfehler.
2. Zuverlässigkeit der Aussage (δ): In einem kleinen Anteil der Fälle liegt die Antwort auch außerhalb der Fehlerschranke. Beispiel: Count-Min Sketch garantiert seine Schranke „mit Wahrscheinlichkeit 1 − δ".
3. Richtung des Fehlers: Dies ist die am meisten unterschätzte Dimension. Ein Sketch kann so gebaut sein, dass er nur in eine Richtung irrt. Der Bloom-Filter sagt niemals „kenne ich nicht" über ein Element, das er kennt. Der Count-Min Sketch schätzt Häufigkeiten niemals zu niedrig.

Diese dritte Dimension ist der eigentliche Hebel für Architekten. Ein einseitiger Fehler ist etwas völlig anderes als ein zweiseitiger Fehler, weil man ihn in ein System einbauen kann, ohne die Korrektheit des Gesamtsystems zu verlieren. Wir werden gleich sehen, wie: Der Bloom-Filter wird zu einem Werkzeug, das nie eine falsche Antwort produziert – nur manchmal unnötige Arbeit.

Teil 2: Der Bloom-Filter – Mitgliedschaft ohne Mitgliederliste

1970: Eine Idee auf fünf Seiten

Burton H. Bloom veröffentlichte 1970 in den Communications of the ACM einen kurzen Aufsatz mit dem programmatischen Titel „Space/Time Trade-offs in Hash Coding with Allowable Errors" (CACM 13(7), 422–426, DOI 10.1145/362686.362692). Der Kern seines Arguments steht schon im Abstract: Wenn man zulässt, dass eine kleine Zahl von Testelementen fälschlich als Mitglied der Menge identifiziert wird, lässt sich ein viel kleinerer Hash-Bereich verwenden, ohne die Antwortzeit zu verschlechtern.

Blooms Anwendungsfall war damals sehr konkret: ein Programm zur automatischen Worttrennung. Die große Mehrheit englischer Wörter folgt einfachen Trennregeln; nur eine Minderheit braucht ein Nachschlagewerk. Der Filter sollte vorab entscheiden, für welche Wörter man überhaupt die (langsame, auf Platte liegende) Ausnahmeliste konsultieren muss.

Diese Problemform – „muss ich den teuren Zugriff überhaupt machen?" – ist seitdem nicht aus der Mode gekommen. Sie ist das Muster schlechthin.

Die Mechanik

Ein Bloom-Filter besteht aus zwei Dingen:

• einem Bit-Array der Länge m, initial komplett auf null,
• k unabhängigen Hash-Funktionen, die jedes Element auf jeweils eine Position in [0, m) abbilden.

Einfügen von Element x: Berechne h₁(x) … h_k(x), setze alle k Bits auf 1.

Abfragen von Element y: Berechne h₁(y) … h_k(y), prüfe alle k Bits.

• Ist mindestens ein Bit 0 → y ist definitiv nicht in der Menge.
• Sind alle Bits 1 → y ist wahrscheinlich in der Menge.

Und hier liegt die ganze Schönheit. Die erste Antwort ist eine Gewissheit. Wäre y eingefügt worden, wären alle seine Bits gesetzt; ein nicht gesetztes Bit beweist die Abwesenheit. Die zweite Antwort ist nur ein Indiz: Die k Bits könnten auch von anderen, zufällig überlappenden Elementen gesetzt worden sein.

Damit gilt:

• Falsch-Negative: ausgeschlossen. Nie. Strukturell unmöglich.
• Falsch-Positive: möglich, mit kalkulierbarer Rate.

Die Formel, die man kennen sollte

Bei n eingefügten Elementen, m Bits und k Hash-Funktionen beträgt die Falsch-Positiv-Rate näherungsweise

p ≈ (1 − e^(−kn/m))^k

Diese Formel ist nicht nur Theorie, sie ist ein Dimensionierungswerkzeug. Zwei Konsequenzen daraus solltest du im Kopf haben:

1. Es gibt ein optimales k. Für gegebenes m und n minimiert

k_opt = (m/n) · ln 2 ≈ 0,693 · (m/n)

die Fehlerrate. Mehr Hash-Funktionen sind nicht besser – ab dem Optimum füllen sie das Array nur schneller mit Einsen.

2. Der Speicherbedarf pro Element ist unabhängig von der Elementgröße. Mit optimalem k braucht man

m/n ≈ −1,44 · log₂(p) Bits pro Element

Das sind in Zahlen:

Lies die Tabelle langsam, denn sie enthält die wichtigste Zahl dieses Artikels: Jede Zehnerpotenz weniger Fehler kostet konstant etwa 4,8 Bits pro Element. Der Zusammenhang ist logarithmisch, nicht linear. Das heißt: Sehr niedrige Fehlerraten sind spottbillig. Und es heißt auch: Egal, ob dein Element eine 16-Byte-UUID oder eine 2-Kilobyte-URL ist – zehn Bits bleiben zehn Bits. Der Bloom-Filter ist gegenüber der Elementgröße blind, und das ist der Grund für die absurden Kompressionsfaktoren.

Was der Bloom-Filter nicht kann

Drei Einschränkungen, die in der Praxis regelmäßig weh tun:

Kein Löschen. Man kann ein Bit nicht einfach auf 0 zurücksetzen, weil es von einem anderen Element mitbenutzt werden könnte – das Zurücksetzen würde ein Falsch-Negativ erzeugen und damit die einzige Garantie der Struktur zerstören. Die klassische Antwort darauf ist der Counting Bloom Filter, eingeführt von Li Fan, Pei Cao, Jussara Almeida und Andrei Broder in „Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol" (IEEE/ACM Transactions on Networking 8(3), 2000): Statt Bits speichert man kleine Zähler (typisch 4 Bit), die beim Einfügen inkrementiert und beim Löschen dekrementiert werden. Preis: der vier- bis achtfache Speicherbedarf.

Keine Elementwiedergewinnung. Ein Bloom-Filter kann dir nicht sagen, was in ihm steckt. Er ist eine Einbahnstraße. Das ist übrigens ein unterschätzter Datenschutzvorteil, zu dem ich später komme.

Keine Flexibilität bei der Größe. Die Dimensionierung geschieht vorab für ein erwartetes n. Wird das überschritten, explodiert die Fehlerrate – darauf kommen wir in Teil 7 zurück.

Der moderne Nachfolger: Cuckoo-Filter

2014 stellten Bin Fan, David G. Andersen, Michael Kaminsky und Michael D. Mitzenmacher auf der CoNEXT'14 den Cuckoo-Filter vor, mit dem herrlich selbstbewussten Titel „Cuckoo Filter: Practically Better Than Bloom". Er speichert nicht Bits, sondern kurze Fingerprints der Elemente in einer Cuckoo-Hashtabelle. Die Autoren halten in ihrem Abstract zwei Vorteile fest: Für Anwendungen, die viele Elemente speichern und moderat niedrige Falsch-Positiv-Raten anstreben, hat der Cuckoo-Filter einen geringeren Speicher-Overhead als ein speicheroptimierter Bloom-Filter – und er unterstützt dynamisches Einfügen und Löschen, bei höherer Performance.

Die Einschränkung, die man dazu wissen muss: Der Cuckoo-Filter kann beim Einfügen scheitern, wenn er zu voll wird (die Cuckoo-Verdrängungskette bricht ab). Er tauscht also die Starrheit des Bloom-Filters gegen eine andere Starrheit – aber eine, die sich explizit meldet, statt stillschweigend die Fehlerrate zu verschlechtern. Ich bin der Meinung, dass das in produktiven Systemen fast immer die bessere Eigenschaft ist: ein Fehler, der laut scheitert, ist einem Fehler überlegen, der leise degradiert.

Teil 3: Zählen, ohne sich zu erinnern – von Flajolet-Martin zu HyperLogLog

Jetzt zurück zur Eingangsfrage: Wie viele verschiedene? Hier wird die Idee noch radikaler, denn hier speichert man nicht einmal mehr Spuren der Elemente, sondern nur noch eine Statistik über ihre Hashwerte.

Die Intuition: Der längste Münzwurf

Stell dir vor, du beobachtest jemanden, der eine faire Münze wirft, und du notierst nur eine einzige Information: die längste beobachtete Serie von Kopf-Würfen.

Wenn die längste Serie 3 war, hat die Person vermutlich etwa acht Würfe gemacht – denn „dreimal Kopf in Folge" tritt mit Wahrscheinlichkeit 1/8 auf. War die längste Serie 10, waren es vermutlich um 1024 Würfe. Du hast die Anzahl der Würfe rekonstruiert, ohne einen einzigen Wurf zu zählen, nur aus der Extremwertstatistik.

Genau das ist der Trick. Man hasht jedes Element zu einem (pseudo-)zufälligen Bitstring. Das Hashing hat hier eine doppelte Funktion, und beide sind essenziell:

1. Es randomisiert: aus Nutzer-IDs werden gleichverteilte Bitfolgen.
2. Es idempotisiert: dasselbe Element ergibt immer denselben Hash. Deshalb zählt ein Element, das millionenfach vorkommt, genau einmal – Duplikate sind automatisch neutralisiert. Das ist der Grund, warum diese Verfahren Kardinalität messen und nicht Volumen.

Dann beobachtet man ein Extremum, etwa die maximale Anzahl führender Nullen über alle Hashwerte, und schließt daraus auf die Zahl der verschiedenen Elemente.

Flajolet und Martin, 1985

Philippe Flajolet und G. Nigel Martin formalisierten das in „Probabilistic Counting Algorithms for Data Base Applications" (Journal of Computer and System Sciences 31(2), 1985, 182–209). Ihr Verfahren erreichte einen relativen Standardfehler von 0,78/√m bei m verwendeten Beobachtungspositionen.

Die zentrale Technik, die sie einführten, heißt stochastisches Mitteln: Ein einzelnes Extremum schwankt wild – es ist ein Einzelversuch mit exponentieller Varianz. Also teilt man den Hashraum anhand der ersten Bits in m Teilmengen („Register", „Buckets"), beobachtet in jeder Teilmenge ihr eigenes Extremum und mittelt über alle m. Die Varianz sinkt mit √m. Mehr Register, mehr Genauigkeit – zum Preis von m mal wenigen Bits.

LogLog, 2003

Marianne Durand und Philippe Flajolet verbesserten das Verfahren in „Loglog Counting of Large Cardinalities" (ESA 2003, LNCS 2832, 605–617). Die namensgebende Beobachtung: Jedes Register muss nur die Position der ersten Eins speichern, also eine Zahl in der Größenordnung log log N. Fünf Bit pro Register genügen für Kardinalitäten bis in den Milliardenbereich. Der Standardfehler lag bei 1,30/√m – schlechter pro Register als Flajolet-Martin, aber dramatisch billiger pro Register, also besser pro Byte.

HyperLogLog, 2007: Das harmonische Mittel

Der Durchbruch kam mit „HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" von Philippe Flajolet, Éric Fusy, Olivier Gandouët und Frédéric Meunier (2007 Conference on Analysis of Algorithms, AofA'07; DMTCS proc. AH, 2007, 137–156).

Die entscheidende Änderung ist eine einzige Zeile Mathematik: Statt des arithmetischen oder geometrischen Mittels der Registerwerte verwendet HyperLogLog das harmonische Mittel. Der Grund ist statistisch elegant – das harmonische Mittel dämpft große Ausreißer stark. Und große Ausreißer sind hier genau das Problem: Ein einzelnes Register, das zufällig einen sehr langen Nullenlauf gesehen hat, würde die Schätzung sonst nach oben reißen.

Das Ergebnis, aus dem Abstract der Arbeit zitiert: die relative Genauigkeit (der Standardfehler) ist typischerweise etwa 1,04/√m. Präziser gibt Theorem 1 der Arbeit die Konstanten β_m an: β₁₆ ≈ 1,106, β₃₂ ≈ 1,070, β₆₄ ≈ 1,054, β₁₂₈ ≈ 1,046, und im Grenzwert β_∞ = √(3 ln 2 − 1) ≈ 1,03896.

Und dann steht da der Satz, der die Datenwelt verändert hat: „For instance, the new algorithm makes it possible to estimate cardinalities well beyond 10⁹ with a typical accuracy of 2% while using a memory of only 1.5 kilobytes." Kardinalitäten jenseits einer Milliarde, 2 % Genauigkeit, 1,5 Kilobyte.

Die Autoren stellen in ihrer Übersichtstabelle auch den direkten Vergleich auf: Probabilistic Counting 0,78/√m, MINCOUNT 1,00/√m, LOGLOG 1,30/√m, HYPERLOGLOG 1,04/√m. HyperLogLog erreicht die Genauigkeit von LogLog mit nur 64 % des Speichers.

Der praktische Bezugspunkt, den du vermutlich schon benutzt hast: Redis implementiert HyperLogLog mit m = 16384 Registern. 1,04/√16384 = 1,04/128 ≈ 0,81 % Standardfehler – bei rund 12 Kilobyte pro Sketch. Das ist die Zahl aus dem Aufhänger.

HyperLogLog++ , 2013: Was Google in der Praxis änderte

Stefan Heule, Marc Nunkesser und Alex Hall beschrieben in „HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm" (Proceedings of the EDBT 2013 Conference, ACM, Genua) eine Reihe von Verbesserungen, die bis heute die Grundlage produktiver Implementierungen (BigQuery, Presto, Druid u. a.) sind:

• 64-Bit-Hashes statt 32 Bit. Mit 32 Bit treten bei Kardinalitäten um 10⁹ Hash-Kollisionen in relevantem Umfang auf; die Schätzung sättigt. 64 Bit verschieben diese Grenze außer Reichweite praktischer Datenmengen.
• Empirische Bias-Korrektur im Bereich kleiner Kardinalitäten, wo die asymptotische Formel systematisch danebenliegt. Statt des von Flajolet et al. vorgeschlagenen Umschaltens auf „Linear Counting" verwenden sie gemessene Bias-Tabellen.
• Sparse-Repräsentation. Bei kleinen Kardinalitäten sind fast alle Register leer. Statt m Register voller Nullen speichert man eine kompakte Liste der tatsächlich belegten – und wechselt erst bei Bedarf auf die dichte Darstellung. Das senkt den Speicherbedarf für den (in der Praxis extrem häufigen) Fall kleiner Mengen drastisch.

Im Abstract halten die Autoren den Zweck knapp fest: eine Reihe von Verbesserungen, die den Speicherbedarf senken und die Genauigkeit für einen wichtigen Kardinalitätsbereich signifikant erhöhen.

Die Eigenschaft, die alles verändert: Vereinigungen sind gratis

Hier kommt der architektonisch wichtigste Punkt des ganzen Artikels, und er wird in Tutorials oft unterschlagen.

Zwei HyperLogLog-Sketches über zwei disjunkte oder überlappende Datenmengen lassen sich exakt und verlustfrei vereinigen: Man nimmt registerweise das Maximum. Das Ergebnis ist bitgenau derselbe Sketch, den man erhalten hätte, wenn man beide Datenströme von Anfang an gemeinsam verarbeitet hätte.

Mathematisch gesprochen: HyperLogLog-Sketches bilden mit dem registerweisen Maximum einen kommutativen, assoziativen, idempotenten Monoid – ein Join-Semilattice. Wer den Artikel über Einigkeit ohne Abstimmung: CRDTs und die Kunst der konfliktfreien Replikation gelesen hat, erkennt die Struktur sofort wieder: Das ist genau die algebraische Eigenschaft, die konfliktfreie Replikation möglich macht. Ein HLL-Sketch ist ein CRDT.

Die praktischen Folgen sind enorm:

• Vorberechnung pro Dimension. Du speicherst einen Sketch pro Stunde, pro Land, pro Kampagne. Jede beliebige Aggregation – „eindeutige Nutzer im dritten Quartal in der DACH-Region" – ist dann eine Vereinigung vorberechneter Sketches, keine Neuberechnung über Rohdaten.
• Beliebige Parallelisierung. Map-Reduce, Spark, Flink: Jeder Worker baut lokal einen Sketch, der Reducer vereinigt sie. Kein Shuffle über Nutzer-IDs. Das ist der Unterschied zwischen einer Query, die skaliert, und einer, die es nicht tut.
• Rohdaten werden entbehrlich. Nach der Aggregation kannst du die IDs löschen. Dazu mehr in Teil 7.

Die Warnung dazu – und sie ist wichtig: Für Schnittmengen gilt das nicht. Es gibt keine entsprechende Operation. Man kann über Inklusion-Exklusion rechnen (|A ∩ B| = |A| + |B| − |A ∪ B|), aber dabei addieren sich die absoluten Fehler der drei Schätzungen. Wenn A und B groß und ihre Schnittmenge klein ist, ist das Ergebnis Rauschen – der Fehler kann die geschätzte Größe deutlich übersteigen. Wer Überlappungen messen will, braucht ein anderes Werkzeug (etwa MinHash oder Theta-Sketches). Diese eine Asymmetrie ist die häufigste schwere Fehlanwendung von HyperLogLog, die ich kenne.

Teil 4: Count-Min Sketch – nicht ob, sondern wie oft

Bloom-Filter antworten auf „ist x drin?". HyperLogLog antwortet auf „wie viele verschiedene?". Die dritte große Frage lautet: „Wie oft kam x vor?"

Graham Cormode und S. Muthukrishnan beschrieben dafür den Count-Min Sketch in „An improved data stream summary: The count-min sketch and its applications" (Journal of Algorithms 55(1), 2005, 58–75, DOI 10.1016/j.jalgor.2003.12.001).

Die Mechanik

Der Sketch ist eine Matrix von d Zeilen und w Spalten, initial null, mit einer Hash-Funktion pro Zeile.

Einfügen von Element x mit Gewicht 1: Erhöhe in jeder Zeile i die Zelle [i, h_i(x)] um 1.

Abfragen der Häufigkeit von x: Lies in jeder Zeile die Zelle [i, h_i(x)] und nimm das Minimum über alle d Zeilen.

Die Logik des Minimums ist dieselbe Asymmetrie wie beim Bloom-Filter, nur in Zahlen statt Bits: Jede Zelle enthält die Summe aus der echten Häufigkeit von x plus den Beiträgen aller kollidierenden Elemente. Jede Zelle ist also eine Überschätzung. Das Minimum ist die am wenigsten kontaminierte Schätzung.

Also wieder ein einseitiger Fehler:

• Unterschätzung: ausgeschlossen.
• Überschätzung: möglich, beschränkt durch die Dimensionierung.

Die Dimensionierung

Will man einen absoluten Fehler von höchstens ε·N (N = Summe aller Gewichte) mit Wahrscheinlichkeit 1 − δ, wählt man

w = ⌈e/ε⌉ und d = ⌈ln(1/δ)⌉

Das ist die Zeile, auf die es ankommt: Die Breite steuert die Genauigkeit, die Tiefe steuert die Zuverlässigkeit. Und der Speicher wächst mit 1/ε, nicht mit 1/ε². Im Abstract halten die Autoren fest, dass ihre Schranken die vorher bekannten signifikant verbessern – „typischerweise von 1/ε² auf 1/ε im Faktor". Das klingt technisch, ist aber der Unterschied zwischen praktikabel und unpraktikabel: Für ε = 0,1 % bedeutet 1/ε rund 2 700 Spalten, 1/ε² rund 2,7 Millionen.

Wofür man das braucht

Der klassische Anwendungsfall sind Heavy Hitters – die Frage „welche Elemente machen mehr als x % des Datenstroms aus?". Das ist in der Praxis erstaunlich oft die eigentliche Frage:

• Welche IP-Adressen dominieren gerade den Traffic? (DDoS-Erkennung, Rate Limiting)
• Welche Suchanfragen trenden in den letzten fünf Minuten?
• Welche API-Keys verursachen die Last?
• Welche Produkt-IDs sind Hot Keys und gehören in den Cache?

Für all diese Fragen ist der Long Tail irrelevant – und genau dort ist der Count-Min Sketch ungenau. Der Fehler ist absolut (proportional zu N), nicht relativ. Für häufige Elemente ist er damit vernachlässigbar, für seltene Elemente kann er die gesamte Schätzung ausmachen. Der Sketch ist präzise genau dort, wo du ihn brauchst, und unbrauchbar genau dort, wo es dir egal ist. Das ist kein Zufall, das ist Design.

Teil 5: Eine Landkarte der Fehler

Hier ist das Framework, das ich mir an die Wand hängen würde:

Zwei Dinge fallen beim Betrachten der Tabelle auf.

Erstens: Drei der fünf Strukturen haben einen einseitigen Fehler. Das ist der Grund, warum sie architektonisch so nützlich sind. Ein einseitiger Fehler lässt sich durch eine nachgeschaltete exakte Prüfung vollständig eliminieren – und genau das ist das dominante Einsatzmuster.

Zweitens: Die Vereinigbarkeit ist eine Eigenschaft der Struktur, nicht der Implementierung. Wo sie fehlt (Cuckoo-Filter), fehlt sie grundsätzlich. Wer verteilte Aggregation plant, muss diese Spalte zuerst lesen.

(Historische Fußnote zur letzten Zeile: Robert Morris beschrieb 1978 in „Counting large numbers of events in small registers", CACM 21(10), 840–842, den approximativen Zähler – wahrscheinlich die erste probabilistische Datenstruktur mit dieser Logik. Die Idee: statt N speichert man ungefähr log N und inkrementiert nur mit Wahrscheinlichkeit 2^(−Zählerwert).)

Teil 6: Wo das in deinen Systemen schon läuft

Das Faszinierende an diesen Strukturen ist, wie unsichtbar allgegenwärtig sie sind.

Speicher-Engines: der teure Festplattenzugriff

Dies ist der wichtigste und sauberste Anwendungsfall. In einem Log-Structured Merge-Tree liegen die Daten in vielen unsortierten Generationen von SSTables verteilt (siehe Schreiben statt Suchen – Log-Structured Merge-Trees und die Umkehrung der Datenbank). Eine Leseanfrage nach einem Schlüssel, der nicht existiert, müsste im Worst Case jede SSTable auf der Platte prüfen – teuer, und bei Nicht-Existenz komplett umsonst.

Lösung: Jede SSTable trägt einen Bloom-Filter über ihre Schlüssel im RAM. Vor jedem Plattenzugriff wird gefragt: „könnte der Schlüssel hier sein?" Bei „definitiv nein" entfällt der Zugriff. Bei „wahrscheinlich ja" liest man – und findet im Falsch-Positiv-Fall nichts.

Jetzt beachte, was hier passiert: Das Gesamtsystem antwortet trotzdem immer korrekt. Ein Falsch-Positiv verursacht ausschließlich einen unnötigen Plattenzugriff, also Latenz, niemals ein falsches Ergebnis. Der approximative Teil ist vollständig in einem Performance-Pfad eingekapselt, während die Korrektheit beim exakten Speicher bleibt. Das ist das Muster, das du in jedes Design übernehmen solltest: Sketch als Vorfilter, exakte Quelle als Autorität.

Produktiv findet man das in RocksDB und LevelDB, in Apache Cassandra und HBase, in Googles Bigtable – also unter einem erheblichen Teil der Daten dieser Welt.

Analytik: die Kardinalitätsfrage

• APPROX_COUNT_DISTINCT in BigQuery, Presto/Trino, Snowflake, Spark SQL – HyperLogLog oder Varianten davon.
• PFADD / PFCOUNT / PFMERGE in Redis – HyperLogLog mit 12 kB und 0,81 % Standardfehler.
• Apache Druid, ClickHouse, Elasticsearch cardinality-Aggregation – dasselbe Prinzip.

Entscheidend ist hier nicht die Rechenzeitersparnis einer einzelnen Query, sondern die Vorberechenbarkeit: Weil Sketches vereinigbar sind, kann man sie als Spaltenwerte in Aggregattabellen materialisieren und nachträglich beliebig neu gruppieren.

Netzwerke, Caches und Routing

Der Counting-Bloom-Filter entstand, wie erwähnt, im Kontext kooperierender Web-Caches: Proxies tauschen kompakte Zusammenfassungen ihres Inhalts aus, statt einander zu befragen. Dieselbe Idee – „sag mir ungefähr, was du hast" – findet man heute in Service-Discovery, in Set-Reconciliation-Protokollen und in verteilten Deduplizierungssystemen. Die Verwandtschaft zu den effizienten Abgleichsverfahren der Der Baum, der die Wahrheit verdichtet: Merkle-Bäume und die Kunst der effizienten Integritätsprüfung ist hier offensichtlich: beide Male geht es darum, Mengen zu vergleichen, ohne sie zu übertragen.

Count-Min-Sketches sitzen in Netzwerktelemetrie und DDoS-Abwehr, weil sie Heavy Hitters bei Leitungsgeschwindigkeit und in konstantem Speicher finden.

Eine lehrreiche Warnung: Bitcoins BIP37

2012 führte Bitcoin mit BIP37 Bloom-Filter ein, damit Leichtgewicht-Clients („SPV-Wallets") von vollen Knoten nur die für sie relevanten Transaktionen anfordern konnten, ohne ihre exakten Adressen zu verraten. Die Falsch-Positiv-Rate sollte als Datenschutz-Puffer dienen: Der Knoten sieht ein verrauschtes Interessensprofil, nicht die echten Adressen.

In der Praxis funktionierte das nicht. Analysen zeigten, dass ein Knoten durch mehrere Filter desselben Clients, durch Korrelation über Verbindungen hinweg und durch die Struktur des Filters selbst die Adressen mit hoher Zuverlässigkeit rekonstruieren konnte. BIP37 gilt heute als Datenschutz-Fehlschlag und wurde durch BIP157/158 (Compact Block Filters, clientseitiges Filtern) ersetzt.

Die Lektion ist allgemein und wichtig: Eine probabilistische Fehlerrate ist kein kryptographischer Schutz. Rauschen, das gegen Zufall schützt, schützt nicht gegen einen Angreifer, der viele Beobachtungen korrelieren darf. Wer Sketches als Privacy-Mechanismus einsetzen will, braucht ein formales Modell – differenzielle Privatheit etwa –, nicht ein Bauchgefühl über Unschärfe.

Teil 7: Die Fallgruben, die in Produktion weh tun

1. Sättigung: der Filter, der still verfällt

Ein Bloom-Filter wird für ein erwartetes n dimensioniert. Wird er mit 5n oder 10n Elementen befüllt, steigt die Falsch-Positiv-Rate nicht linear, sondern bricht ein: Bei m/n ≈ 9,6 und k = 7 liegt man bei 1 %; mit der fünffachen Elementzahl sind praktisch alle Bits gesetzt, und der Filter antwortet auf alles mit „wahrscheinlich ja". Er ist dann nicht kaputt – er ist nur völlig nutzlos, und zwar ohne Fehlermeldung.

Das ist die gefährlichste Eigenschaft der ganzen Familie: stille Degradation. Konsequenz für den Betrieb: Die Füllrate (Anteil gesetzter Bits) muss eine überwachte Metrik sein, mit Alarm. Für unbekannt wachsende Mengen gehören skalierbare Varianten (Scalable Bloom Filter, Schichtung mehrerer Filter) oder periodische Neudimensionierung ins Design.

2. Der Fehler ist deterministisch, nicht zufällig

Dies ist der subtilste Denkfehler, und ich habe ihn oft gesehen. „1 % Falsch-Positiv-Rate" klingt wie ein Würfel, der pro Anfrage neu geworfen wird. Das ist falsch. Bei fixem Filterinhalt ist ein Falsch-Positiv eine Eigenschaft des Elements: Ist Element y ein Falsch-Positiv, dann ist es das bei jeder Abfrage, immer, bis sich der Filterinhalt ändert.

Daraus folgt praktisch:

• Wiederholen hilft nicht. Es gibt keinen „zweiten Versuch".
• Die 1 % beziehen sich auf eine Zufallsauswahl von Nicht-Elementen. Wenn dein Zugriffsmuster ausgerechnet ein Falsch-Positiv-Element heiß abfragt, trägst du dessen Kosten in jeder einzelnen Anfrage.
• Bei nicht-kryptographischen Hashes kann ein Angreifer, der die Hash-Funktion und ihren Seed kennt, Falsch-Positive gezielt konstruieren und so den Vorfilter wertlos machen – ein Algorithmic-Complexity-Angriff. Gegenmaßnahme: geheime, pro Instanz zufällige Seeds; bei exponierten Schnittstellen schlüsselbasierte Hashes (etwa SipHash).

3. Kardinalität ist nicht Schnittmenge

Wiederholt sei es, weil es der häufigste Fehler ist: HyperLogLog vereinigt exakt und schneidet miserabel. Dashboards, die „Nutzer, die A und B getan haben" aus HLL-Sketches via Inklusion-Exklusion berechnen, produzieren bei kleinen Überlappungen und großen Mengen Zahlen, die statistisch nicht von Rauschen zu unterscheiden sind.

4. Compliance: wo „ungefähr" verboten ist

Hier wird es für Beratungskontexte interessant, denn die Entscheidung ist keine technische, sondern eine regulatorische.

Wo approximativ unzulässig ist: alles, was einer Nachweispflicht unterliegt oder als Grundlage einer Rechtsfolge dient. Abrechnung und Umsatzermittlung. Finanzberichtswesen. Audit-Trails und Protokollierung sicherheitsrelevanter Ereignisse. Zugriffskontrolle – ein Bloom-Filter darf niemals allein über eine Berechtigung entscheiden, denn ein Falsch-Positiv ist dort eine unberechtigte Freigabe. Auch die regulatorisch geforderte Vollständigkeit von Meldeketten (etwa bei Vorfallsmeldungen) verträgt keine Schätzung.

Wo approximativ nicht nur zulässig, sondern vorzuziehen ist: Monitoring, Kapazitätsplanung, Produktanalytik, Trenderkennung, A/B-Test-Vorsichtung, Anomalieerkennung. Hier ist eine Zahl mit 1 % Fehler, die in Sekunden vorliegt, einer exakten Zahl überlegen, die in zwanzig Minuten vorliegt – weil die Entscheidung, die sie stützt, von einem Prozent nicht abhängt.

Und ein Punkt, der in Datenschutzgesprächen oft übersehen wird: Sketches können die Datenminimierung aktiv unterstützen. Ein HyperLogLog-Register enthält Maxima von Nullenläufen – keine IDs, keine Hashes vollständiger Identifikatoren, keine wiedergewinnbaren Elemente. Wenn du nur die Frage „wie viele verschiedene Besucher" beantworten musst, kannst du den Sketch führen und die Rohdaten nach kurzer Frist löschen. Das ist Zweckbindung und Speicherbegrenzung nach Art. 5 Abs. 1 lit. b und e DSGVO, technisch umgesetzt statt nur in einer Richtlinie behauptet.

Mit zwei Vorbehalten, die man ehrlich benennen muss: Erstens gilt das nur für die Kardinalitätsfrage – ein Bloom-Filter über Nutzer-IDs erlaubt sehr wohl Mitgliedschaftstests („war diese Person hier?"), ist also keineswegs anonym. Zweitens zeigt BIP37, dass Unschärfe allein keine Anonymisierung ist. Ich bin der Meinung, dass Sketches ein starkes Werkzeug der Datenminimierung sind, aber nur dort, wo die gestellte Frage selbst aggregiert ist – nicht als nachträgliche Verschleierung einer individuellen Abfrage.

Teil 8: Die tiefere Lektion – Fehler als Entwurfsmaterial

Ich halte diese Strukturen für mehr als eine Sammlung von Tricks. Sie machen eine Denkfigur sichtbar, die über Datenstrukturen weit hinausreicht.

In der klassischen Informatik ist Korrektheit binär: Ein Algorithmus ist korrekt oder fehlerhaft. Ein Fehler ist ein Defekt, etwas, das man beseitigt. Die probabilistischen Datenstrukturen führen eine dritte Kategorie ein: den spezifizierten, beschränkten, gewollten Fehler. Er ist nicht ein Mangel an Qualität, sondern eine Dimension des Entwurfsraums, an der man dreht – wie an Latenz oder Speicher.

Und sobald man das einmal gesehen hat, sieht man es überall: in der Lossy-Kompression, in Monte-Carlo-Verfahren, in Caching mit TTL (jede veraltete Antwort ist ein kalkulierter Fehler gegen Latenzgewinn), in Eventual Consistency, in Sampling-basiertem Tracing, in randomisierten Algorithmen, in der differenziellen Privatheit, wo das Rauschen die Schutzwirkung ist. Es ist dieselbe Denkfigur wie bei der Das Versprechen, das keiner halten kann: Zwei-Phasen-Commit, Sagas und das Ende der verteilten Transaktion: Man gibt eine starke Garantie auf, die man sich nicht leisten kann, und bekommt dafür eine schwächere, aber präzise beschriebene – mit der man dann bewusst arbeitet.

Der Unterschied zwischen einem guten und einem schlechten System ist deshalb selten, ob es Fehler hat. Er ist, ob die Fehler benannt, beschränkt und an der richtigen Stelle platziert sind. Ein Bloom-Filter vor einer Datenbank ist ein eingebauter Fehler, der niemandem schadet, weil er nur Arbeit verursacht, nie falsche Antworten. Eine Berechtigungsprüfung auf einem Bloom-Filter wäre derselbe Fehler, an der falschen Stelle – und ein Sicherheitsvorfall.

Die Frage lautet nie: „Fehlerfrei oder fehlerhaft?" Sie lautet: „Welchen Fehler kann ich mir hier leisten, in welcher Richtung, und wo liegt die Autorität, die ihn auffängt?"

Die zentrale Erkenntnis zum Mitnehmen

1. Exaktheit ist eine Anforderung, nicht ein Naturgesetz. Ob du sie brauchst, ist eine Entscheidung mit Preisschild – und bei Kardinalität, Mitgliedschaft und Häufigkeit liegt der Preis bei Faktoren von Tausenden bis Millionen an Speicher.
2. Die Richtung des Fehlers ist wichtiger als seine Größe. Einseitige Fehler (Bloom: nur Falsch-Positive; Count-Min: nur Überschätzung) lassen sich in Architekturen einkapseln, ohne die Korrektheit des Ganzen anzutasten. Das Muster heißt: Sketch als Vorfilter, exakte Quelle als Autorität.
3. Vereinigbarkeit entscheidet über Skalierbarkeit. HyperLogLogs verlustfreie Vereinigung (registerweises Maximum) macht sie zu einem CRDT und damit zum idealen Baustein verteilter, vorberechneter Aggregation. Schnittmengen sind dagegen eine Falle.
4. Stille Degradation ist das Betriebsrisiko. Ein übersättigter Bloom-Filter funktioniert weiter und ist nutzlos. Füllraten gehören ins Monitoring.
5. Unschärfe ist kein Datenschutz (BIP37), aber Sketches sind ein starkes Werkzeug der Datenminimierung, wenn die Frage selbst aggregiert ist.

Konkreter Handlungsanstoß für diese Woche: Nimm dir die langsamste Query oder den teuersten Job in einem System, das du betreust, und stelle genau eine Frage: „Hängt irgendeine Entscheidung, die auf dieser Zahl beruht, von den letzten 1 % Genauigkeit ab?"

Bei Abrechnung, Audit oder Berechtigung lautet die Antwort Nein – dann hast du eine Grenze dokumentiert, und das ist Gewinn genug. Bei einem Monitoring-Dashboard, einer Kapazitätsplanung oder einer Produktmetrik lautet sie fast immer Ja, man darf schätzen – und dann ist ein einzeiliges APPROX_COUNT_DISTINCT statt COUNT(DISTINCT …) womöglich die billigste Performance-Verbesserung, die du dieses Quartal ausliefern wirst. Prüfe es an einer echten Abfrage und vergleiche beide Ergebnisse: Der gemessene Abstand zwischen Schätzung und Wahrheit ist das überzeugendste Argument, das du in der nächsten Architekturdiskussion haben kannst.

Reflexionsfrage: Wenn ein bewusst eingebauter, beschränkter Fehler ein System um Größenordnungen besser machen kann – an welcher Stelle deiner eigenen Architektur zahlst du gerade einen hohen Preis für eine Exaktheit, die niemand jemals angefordert hat, die aber auch niemand je in Frage gestellt hat?

Querverweise im Vault

• Schreiben statt Suchen – Log-Structured Merge-Trees und die Umkehrung der Datenbank – der prominenteste Produktionseinsatz von Bloom-Filtern: Vermeidung unnötiger SSTable-Zugriffe.
• Einigkeit ohne Abstimmung: CRDTs und die Kunst der konfliktfreien Replikation – HyperLogLog-Sketches bilden mit dem registerweisen Maximum ein Join-Semilattice und sind damit ein CRDT.
• Der Baum, der die Wahrheit verdichtet: Merkle-Bäume und die Kunst der effizienten Integritätsprüfung – die exakte Antwort auf dieselbe Grundfrage: Mengen vergleichen, ohne sie zu übertragen.
• Die Nadel im Milliarden-Heuhaufen: Approximate Nearest Neighbor Search, HNSW und die Architektur der Vektordatenbanken – derselbe Tauschhandel in der Ähnlichkeitssuche: Recall gegen Geschwindigkeit statt Exaktheit gegen Speicher.
• Das Versprechen, das keiner halten kann: Zwei-Phasen-Commit, Sagas und das Ende der verteilten Transaktion – die gleiche Denkfigur auf Transaktionsebene: starke Garantie gegen schwächere, aber bezahlbare tauschen.
• Der Ring, der die Last verteilt: Consistent Hashing und die Kunst des sanften Umzugs – Hashing als Strukturgeber verteilter Systeme; hier als Randomisierungsquelle, dort als Zuordnungsfunktion.

Quellen und zum Weiterlesen

• Burton H. Bloom – Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM 13(7), 1970, 422–426, DOI 10.1145/362686.362692: https://cacm.acm.org/research/space-time-trade-offs-in-hash-coding-with-allowable-errors
• Philippe Flajolet, Éric Fusy, Olivier Gandouët, Frédéric Meunier – HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, AofA'07, DMTCS proc. AH, 2007, 137–156: https://dmtcs.episciences.org/3545/pdf
• Philippe Flajolet, G. Nigel Martin – Probabilistic Counting Algorithms for Data Base Applications, Journal of Computer and System Sciences 31(2), 1985, 182–209: https://www.gwern.net/doc/cs/algorithm/1985-flajolet.pdf
• Stefan Heule, Marc Nunkesser, Alex Hall – HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm, Proceedings of the EDBT 2013 Conference, ACM, Genua, 2013: https://research.google/pubs/hyperloglog-in-practice-algorithmic-engineering-of-a-state-of-the-art-cardinality-estimation-algorithm/
• Graham Cormode, S. Muthukrishnan – An improved data stream summary: The count-min sketch and its applications, Journal of Algorithms 55(1), 2005, 58–75, DOI 10.1016/j.jalgor.2003.12.001: https://www.cs.ox.ac.uk/people/graham.cormode/pubs/html/CormodeMuthukrishnan04CMJalg.html
• Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher – Cuckoo Filter: Practically Better Than Bloom, Proceedings of CoNEXT'14, Dezember 2014: https://pdl.cmu.edu/PDL-FTP/FS/cuckoo-conext2014_abs.shtml
• Marianne Durand, Philippe Flajolet – Loglog Counting of Large Cardinalities, ESA 2003, LNCS 2832, 605–617, DOI 10.1007/978-3-540-39658-1_55: https://doi.org/10.1007/978-3-540-39658-1_55

Erstellt im Rahmen des täglichen Lern-Workflows. Interessensgebiet: Software-Architekturen. Geschätzte Lesedauer: ~30 Minuten.

← All articles