HyperLogLog

In Redis (PFADD, PFCOUNT). "Pf" steht für Philippe Flajolet (Erfinder). Du kannst Millionen von User-IDs reinwerfen. Redis speichert nur 12 KB. Auch in Elasticsearch (cardinality aggregation) und BigQuery.

1. Leading Zeros

Die Idee: Wenn ich zufällige Zahlen (Hash) werfe. Wie wahrscheinlich ist es, dass eine Zahl mit 0... beginnt? 50% ($1/2$). Mit 00...? 25% ($1/4$). Mit 000...? 12.5% ($1/8$). Wenn ich eine Zahl sehe, die mit 10 Nullen beginnt ($1/2^{10}$), dann habe ich wahrscheinlich ca. $2^{10} = 1024$ verschiedene Zahlen gesehen. Max Leading Zeros $\approx \log_2(N)$.

2. Bucketing (LogLog)

Ein einzelner Hashwert ist zu zufällig (Varianz). HLL teilt die Hashes in $m$ Eimer (Buckets) auf (z. B. 16384). Es nimmt das harmonische Mittel der Eimer, um Ausreißer zu glätten ("Hyper"). Das reduziert den Standardfehler auf $1.04 / \sqrt{m}$.

1. Register-Kollisionen und Dense/Sparse Representation

Wenn Redis ein HLL-Objekt erstellt, verbraucht es nicht sofort 12 KB Speicher. Redis nutzt intern Sparse Representation. Solange nur wenige Tausend Unique-Elemente im HLL liegen, speichert Redis die Keys komprimiert im Binär-Encoding (run-length encoding) und verbraucht nur wenige Bytes. Erst wenn das HLL eine festgelegte Speichergrenze (hll-sparse-max-bytes, Default 3000) reißt, konvertiert Redis drastisch in die Dense Representation (ein festes 12 KB C-Array). In C nutzt jeder Bucket genau 6 Bits (da $\max(\text{LeadingZeros}) < 64$ und $2^6 = 64$ Bits). $16384 \times 6 \text{ Bits} = 12288 \text{ Bytes}$ (= 12 KB). Perfekte Ausnutzung der Prozessor-Register.

2. Bias-Korrektur und Linear Counting

Die Mathematik von Flajolet schätzte zwar asymptotisch super, lag aber bei kleinen Zahlen (z. B. nur 50 Elementen) katastrophal daneben. Das Original-Google-Paper ("HyperLogLog++") patchte dies. Bei einer niedrigen Cardinality (nahe an 0 bis $5 \times \text{RegisterZahl}$) wechselt der Algorithmus heimlich unter der Haube auf eine pure lineare Wahrscheinlichkeitsrechnung (Linear Counting), abgeleitet durch die pure Anzahl der Eimer, die noch auf exakt Null (also komplett leer) stehen. Sobald Elemente wachsen, slided er fließend in die klassische Log-Schätzung, durch eine interpolierte Bias-Error-Curve.

3. HyperLogLog State Merging in Streaming (Kafka)

Die magische Eigenschaft von HLL ist, dass es eine kommutative Halbgruppe (Idempotenz) ist. Wenn man im Big Data (Flink/Kafka-Streams) ein 1-Minuten-Window analysiert ("Wie viele Uniques um 14:01 Uhr?"), speichert man pro Minute das kleine 12 KB Blob. Wenn der Chef sagt: "Gib mir die Uniques vom ganzen Monat Januar!", muss das System nicht die Rohevents scannen. Es nimmt einfach alle $31 \times 24 \times 60$ HLL-Blobs, wirft sie in den CPU-Akkumulator und macht ein simples bitweises MAX() über jedes einzelne der 16k Register. Heraus kommt exakt dasselbe Ergebnis, als hätte man die Original-IPs nochmal kumuliert gescanned.