Redis HyperLogLog fuer naeherungsweise Zaehlungen

1. Das Problem: eindeutige Werte in riesigen Mengen zaehlen

Die Frage "Wie viele eindeutige Besucher hatte diese Seite heute?" klingt trivial, ist aber bei hohem Traffic ein handfestes Speicherproblem. Die naive Loesung, jede Besucher-ID in einem Redis-Set zu speichern und SCARD aufzurufen, funktioniert korrekt, aber der Speicherverbrauch waechst linear mit der Anzahl eindeutiger Besucher. Bei zehn Millionen eindeutigen IDs pro Tag, jede vielleicht 16 Byte gross, kommen schnell hunderte Megabyte pro Tag zusammen, multipliziert mit der Anzahl der Tage, die man aufbewahren will.

Genau hier setzt HyperLogLog an: eine probabilistische Datenstruktur, die die Kardinalitaet, also die Anzahl eindeutiger Elemente, einer Menge schaetzt, ohne die Elemente selbst zu speichern. Statt linear wachsendem Speicher braucht ein HyperLogLog in Redis konstant nur rund 12 Kilobyte, unabhaengig davon, ob die geschaetzte Menge tausend oder eine Milliarde eindeutige Elemente enthaelt. Der Preis fuer diese Speicherersparnis ist eine kontrollierte, mathematisch bekannte Fehlermarge von typischerweise unter einem Prozent.

Fuer Anwendungsfaelle, bei denen die exakte Zahl nicht entscheidend ist, sondern eine verlaessliche Groessenordnung genuegt, etwa Dashboards, Analytics oder A/B-Test-Auswertungen, ist HyperLogLog eine der elegantesten Loesungen im Redis-Werkzeugkasten. Dieser Beitrag erklaert die Commands, die Mathematik dahinter auf konzeptioneller Ebene und die konkrete Anwendung fuer Unique-Visitor-Zaehlung.

Wichtig ist die Abgrenzung von Anfang an: HyperLogLog ersetzt kein Set fuer Anwendungsfaelle, in denen Mitgliedschaft, Entfernung einzelner Elemente oder absolute Exaktheit erforderlich sind. Es loest ausschliesslich das Zaehlproblem, und zwar so effizient, dass Systeme mit Millionen paralleler Zaehlungen erst durch HyperLogLog realistisch mit einer einzigen Redis-Instanz betrieben werden koennen.

Der Name HyperLogLog stammt aus der theoretischen Informatik und beschreibt, dass der Speicherbedarf mit dem doppelten Logarithmus der zu zaehlenden Menge waechst, praktisch also nicht messbar zunimmt, selbst wenn die tatsaechliche Menge um Groessenordnungen waechst. Diese asymptotische Eigenschaft ist der theoretische Kern, der die konstante Speichergroesse in der Praxis erst erklaert.

2. PFADD und PFCOUNT: die Basis-Commands

Die Redis-Commands fuer HyperLogLog tragen alle das Praefix PF, eine Reminiszenz an Philippe Flajolet, den Mathematiker, dessen Forschung den Algorithmus begruendet hat. PFADD key element fuegt ein Element zur geschaetzten Menge hinzu. Intern wird das Element gehasht, und der Hash beeinflusst einen von 16384 Registern, die zusammen den internen Zustand des HyperLogLog bilden. Mehrere Elemente koennen in einem einzigen PFADD-Aufruf uebergeben werden.

Ruft man PFADD key ohne jedes Element auf, wird lediglich sichergestellt, dass der Schluessel als HyperLogLog existiert, ohne dass sich die Schaetzung veraendert. Das ist praktisch, um einen taeglichen Zaehler bereits beim Tageswechsel anzulegen, noch bevor der erste tatsaechliche Besucher eintrifft, sodass nachgelagerte Prozesse den Schluessel garantiert vorfinden.

Ein leerer HyperLogLog-Schluessel liefert bei PFCOUNT zuverlaessig 0 zurueck, genau wie ein leeres Set bei SCARD. Dieses konsistente Verhalten an den Raendern des Wertebereichs erleichtert die Integration in bestehende Zaehl-Pipelines, weil keine Sonderfaelle fuer "Schluessel existiert nicht" gegenueber "Schluessel ist leer" behandelt werden muessen.

PFCOUNT key liefert die geschaetzte Anzahl eindeutiger Elemente, die jemals per PFADD hinzugefuegt wurden. Wichtig zu verstehen: Es gibt keinen Command, um ein einzelnes Element wieder zu entfernen, HyperLogLog ist eine reine Add-Only-Struktur. Das ist ein bewusster Trade-off des Algorithmus: Die Kompaktheit wird dadurch erkauft, dass einzelne Elemente nach dem Hinzufuegen nicht mehr identifizierbar oder entfernbar sind, nur die Gesamtschaetzung bleibt erhalten.

PFADD liefert als Rueckgabewert 1, wenn sich die interne Register-Repraesentation durch das neue Element tatsaechlich veraendert hat, und 0, wenn nicht. Dieser Rueckgabewert ist eine praktische Nebenwirkung: Ein Client kann daran erkennen, ob ein Element mit hoher Wahrscheinlichkeit neu war, ohne dafuer einen separaten Command aufzurufen, auch wenn dieses Verhalten kein zuverlaessiger Ersatz fuer eine echte Mitgliedschaftspruefung ist.

# HyperLogLog: approximate cardinality with constant memory
redis-cli PFADD visitors:2026-07-23 "user:1001" "user:1002" "user:1003"
redis-cli PFADD visitors:2026-07-23 "user:1001"
redis-cli PFCOUNT visitors:2026-07-23
redis-cli STRLEN visitors:2026-07-23
redis-cli PFADD visitors:2026-07-24 "user:2001" "user:2002"
redis-cli PFCOUNT visitors:2026-07-23 visitors:2026-07-24
redis-cli PFADD visitors:2026-07-24
redis-cli TYPE visitors:2026-07-24
redis-cli OBJECT ENCODING visitors:2026-07-24

3. Der Algorithmus hinter HyperLogLog verstaendlich erklaert

Die Grundidee von HyperLogLog laesst sich ohne tiefe Mathematik verstehen: Jedes hinzugefuegte Element wird durch eine Hash-Funktion in eine scheinbar zufaellige Bitfolge verwandelt. Ein zentrales Beobachtungsprinzip probabilistischer Zaehlalgorithmen lautet, dass die Wahrscheinlichkeit, eine lange Folge fuehrender Nullen in einer zufaelligen Bitfolge zu beobachten, exponentiell mit der Laenge dieser Folge sinkt. Beobachtet man in einer Menge von Hash-Werten eine besonders lange Folge fuehrender Nullen, deutet das statistisch auf eine grosse Anzahl unterschiedlicher Elemente hin, denn je mehr verschiedene Zufallswerte generiert wurden, desto wahrscheinlicher taucht irgendwann eine lange Nullfolge auf.

HyperLogLog verbessert dieses Grundprinzip, indem es nicht nur einen einzigen Zaehler fuehrt, sondern die eingehenden Hash-Werte auf 16384 unabhaengige Register verteilt, basierend auf einem Teil des Hashs. Jedes Register merkt sich die laengste beobachtete Folge fuehrender Nullen innerhalb seines Anteils der Elemente. Am Ende wird ueber alle Register ein harmonisches Mittel gebildet, was die Varianz einzelner Ausreisser-Register stark daempft und eine deutlich stabilere Gesamtschaetzung liefert als ein einzelner Zaehler es koennte.

Diese Register-basierte Mittelung ist der Grund, warum HyperLogLog mit nur 16384 Registern zu je 6 Bit, insgesamt rund 12 Kilobyte, eine Schaetzung mit einem Standardfehler von etwa 0,81 Prozent liefert, vollkommen unabhaengig von der tatsaechlichen Menge der Elemente. Ob eine Million oder eine Milliarde Elemente hinzugefuegt wurden, der Speicherbedarf des HyperLogLog bleibt exakt gleich, nur die statistische Schaetzung passt sich an.

Der urspruengliche Flajolet-Martin-Algorithmus aus den 1980er-Jahren nutzte bereits die Idee der fuehrenden Nullen, litt aber unter hoher Varianz bei einem einzelnen Zaehler. Die HyperLogLog-Verfeinerung von Flajolet und Kollegen im Jahr 2007 fuegte die Aufteilung auf viele Register und die harmonische Mittelung hinzu, wodurch die Fehlermarge auf ein praktikables, vorhersagbares Niveau sank und die Struktur produktionsreif wurde.

Redis implementiert diesen Algorithmus in reinem C direkt im Server-Prozess, sodass jede PFADD-Operation ohne zusaetzliche Netzwerk-Roundtrips oder externe Bibliotheken auskommt. Diese native Integration ist ein wesentlicher Grund, warum HyperLogLog in Redis so verbreitet ist, verglichen mit vergleichbaren Implementierungen, die als separate Anwendungslogik auf Client-Seite realisiert werden muessten.

Redis nutzt zusaetzlich eine sogenannte sparse Encoding-Variante fuer kleine Mengen, bei der nur die tatsaechlich befuellten Register kompakt gespeichert werden, statt aller 16384 Register in voller Groesse. Erst wenn eine Menge so gross wird, dass die sparse Repraesentation ineffizienter waere als die feste dense Repraesentation, konvertiert Redis automatisch und transparent, aehnlich wie beim listpack-Encoding anderer Datentypen.

4. Fehlermarge und Genauigkeit in der Praxis

Der Standardfehler von etwa 0,81 Prozent bei der Redis-Implementierung von HyperLogLog bedeutet konkret: Bei einer tatsaechlichen Kardinalitaet von einer Million eindeutiger Elemente liegt die Schaetzung typischerweise zwischen 991.900 und 1.008.100. Fuer Dashboards, Trend-Analysen oder Kapazitaetsplanung ist diese Abweichung in aller Regel irrelevant, weil Entscheidungen selten von der letzten Stelle einer Zahl abhaengen.

Wichtig ist, die Fehlermarge im Kontext der Anwendung zu bewerten: Fuer Abrechnungssysteme, bei denen jede zusaetzliche eindeutige Nutzung tatsaechlich abgerechnet wird, ist eine Schaetzung mit 0,81 Prozent Fehler ungeeignet, dort muss ein exaktes Set verwendet werden. Fuer Analytics-Dashboards, die ohnehin gerundete oder aggregierte Zahlen anzeigen, etwa "ca. 1,2 Millionen Besucher diese Woche", ist die Fehlermarge dagegen komplett unproblematisch und faellt visuell nicht auf.

Ein praktischer Faustwert aus der Betriebserfahrung: Bei Kennzahlen, die ohnehin auf volle Tausend oder Zehntausend gerundet praesentiert werden, liegt eine Abweichung von 0,81 Prozent deutlich unterhalb der Rundungsschwelle und ist fuer Endanwender niemals sichtbar. Erst bei Kennzahlen, die auf die letzte Stelle genau kommuniziert werden, etwa in einem Vertragsdokument, wird die Naeherung zum echten Problem.

Ein interessanter Aspekt: Die Fehlermarge ist relativ konstant, unabhaengig von der absoluten Groesse der Menge. Das unterscheidet HyperLogLog von naiven Sampling-Methoden, bei denen der relative Fehler mit wachsender Grundgesamtheit tendenziell zunimmt. HyperLogLog liefert bei einer Million wie bei einer Milliarde Elementen eine aehnlich zuverlaessige prozentuale Genauigkeit, solange genuegend unterschiedliche Hash-Werte in die Register eingeflossen sind.

Bei sehr kleinen Mengen, im niedrigen zwei- oder dreistelligen Bereich, nutzt Redis eine Korrektur, die auf lineares Zaehlen zurueckfaellt, um die sonst bei kleinen Mengen ungenauere Standardschaetzung zu verbessern. Diese eingebaute Korrektur sorgt dafuer, dass HyperLogLog auch am unteren Ende des Wertebereichs verlaessliche Ergebnisse liefert, ohne dass Anwendungsentwickler sich um diesen Sonderfall kuemmern muessen.

5. Praxisbeispiel: Unique-Visitor-Tracking pro Tag

Ein klassischer Anwendungsfall ist das taegliche Tracking eindeutiger Besucher einer Website oder API. Bei jedem eingehenden Request wird die Besucher-ID, etwa eine Cookie-ID oder IP-Hash, per PFADD visitors: hinzugefuegt. Am Ende des Tages oder in Echtzeit liefert PFCOUNT visitors: die geschaetzte Anzahl eindeutiger Besucher fuer diesen Tag, ohne dass jemals eine einzelne Besucher-ID dauerhaft gespeichert werden musste.

Fuer Wochen- oder Monatsansichten muss die Anwendung nicht neu zaehlen: PFCOUNT akzeptiert mehrere Schluessel gleichzeitig und liefert die kombinierte Kardinalitaet ueber alle uebergebenen HyperLogLogs, ohne dass die einzelnen taeglichen Strukturen dafuer veraendert werden. Ein Aufruf wie PFCOUNT visitors:2026-07-21 visitors:2026-07-22 visitors:2026-07-23 liefert sofort die eindeutigen Besucher ueber alle drei Tage kombiniert, inklusive korrekter Deduplizierung von Besuchern, die an mehreren Tagen aktiv waren.

Diese Kombinierbarkeit macht HyperLogLog besonders attraktiv fuer mehrdimensionale Analytics: Ein separates HyperLogLog pro Tag, pro Land oder pro Marketingkanal ermoeglicht flexible Auswertungen im Nachhinein, ohne dass vorab entschieden werden muss, welche Aggregationsebenen spaeter gebraucht werden. Diese Flexibilitaet waere mit exakten Sets bei vergleichbarer Datenmenge kaum praktikabel.

Fuer die Aufbewahrung empfiehlt sich, jeden taeglichen Schluessel mit EXPIRE auf ein sinnvolles Retentionsfenster zu setzen, etwa 90 Tage, damit alte HyperLogLogs automatisch verschwinden, ohne dass ein separater Cleanup-Job noetig ist. Da jeder Schluessel konstant nur 12 Kilobyte belegt, ist selbst eine Aufbewahrung von mehreren Jahren taeglicher Zaehlungen unproblematisch fuer den Speicherbedarf einer Redis-Instanz.

Fuer produktive Systeme mit hohem Traffic empfiehlt sich zudem, PFADD asynchron ueber eine kleine Queue oder ein Batching im Anwendungscode zu buendeln, statt bei jedem einzelnen Request synchron zu blockieren. Da HyperLogLog-Operationen ohnehin sehr guenstig sind, reicht in den meisten Faellen aber ein direkter, synchroner Aufruf vollkommen aus, ohne dass zusaetzliche Infrastruktur noetig waere.

# Daily unique visitor tracking, combined across days
redis-cli PFADD visitors:2026-07-21 "cookie:a1" "cookie:a2" "cookie:a3"
redis-cli PFADD visitors:2026-07-22 "cookie:a2" "cookie:a4"
redis-cli PFADD visitors:2026-07-23 "cookie:a1" "cookie:a5"
redis-cli PFCOUNT visitors:2026-07-21
redis-cli PFCOUNT visitors:2026-07-21 visitors:2026-07-22 visitors:2026-07-23
redis-cli EXPIRE visitors:2026-07-21 2592000

6. PFMERGE: Mengen kombinieren ohne Praezisionsverlust

Waehrend PFCOUNT mit mehreren Schluesseln nur eine kombinierte Schaetzung zurueckgibt, ohne die zugrunde liegenden HyperLogLogs zu veraendern, erzeugt PFMERGE destkey sourcekey1 sourcekey2 ein neues, dauerhaftes HyperLogLog, das die Vereinigung mehrerer Quell-Strukturen repraesentiert. Das ist nuetzlich, wenn eine kombinierte Sicht dauerhaft gespeichert und wiederverwendet werden soll, etwa ein rollierendes 30-Tage-Fenster eindeutiger Nutzer, das taeglich um einen neuen Tag erweitert und um den aeltesten Tag reduziert wird.

Ein wichtiger mathematischer Vorteil von PFMERGE gegenueber einer naiven Summierung einzelner Zaehlungen: Wenn ein Nutzer sowohl am Montag als auch am Dienstag aktiv war, wuerde eine einfache Addition der Tages-PFCOUNT-Werte diesen Nutzer doppelt zaehlen. PFMERGE gefolgt von PFCOUNT auf dem Ergebnis dedupliziert korrekt, weil die Register-basierte Struktur beim Merge pro Register jeweils das Maximum der beiden Quell-Register uebernimmt, was der korrekten mathematischen Vereinigungsoperation entspricht.

Ein rollierendes Fenster laesst sich effizient pflegen, indem taeglich ein neues PFMERGE aus den letzten sieben taeglichen Schluesseln erzeugt und der alte rollierende Schluessel ueberschrieben wird. Dieser Ansatz ist deutlich guenstiger als das Neuaufbauen eines Sets aus sieben Tagen Rohdaten und liefert dieselbe korrekte Deduplizierung ueber den gesamten Zeitraum.

Da PFMERGE das Zielobjekt ueberschreibt, sollte in produktiven Systemen ein temporaerer Zwischenschluessel verwendet und erst nach erfolgreichem Merge per RENAME aktiviert werden. So bleibt der vorherige rollierende Wert bis zum letzten Moment abrufbar, falls der Merge-Vorgang aus irgendeinem Grund fehlschlaegt oder unterbrochen wird.

# PFMERGE: build a persistent rolling 7-day unique count
redis-cli PFMERGE visitors:rolling7d:tmp visitors:2026-07-17 visitors:2026-07-18 visitors:2026-07-19 visitors:2026-07-20 visitors:2026-07-21 visitors:2026-07-22 visitors:2026-07-23
redis-cli RENAME visitors:rolling7d:tmp visitors:rolling7d
redis-cli PFCOUNT visitors:rolling7d
redis-cli EXPIRE visitors:rolling7d 604800

7. Speichereffizienz im direkten Vergleich mit Sets

Der quantitative Speichervorteil von HyperLogLog wird beim direkten Vergleich mit einem Set deutlich. Ein Redis-Set mit einer Million eindeutiger String-IDs von je 20 Byte Laenge braucht, inklusive interner Verwaltungsstruktur der Hashtabelle, typischerweise mehrere zehn Megabyte Speicher. Ein HyperLogLog fuer dieselbe Datenmenge belegt konstant rund 12 Kilobyte, unabhaengig von der Laenge oder Anzahl der urspruenglichen Elemente. Das entspricht einer Speicherersparnis um den Faktor tausend oder mehr.

Dieser Unterschied wird besonders relevant, wenn viele parallele Zaehlungen gefuehrt werden, etwa ein HyperLogLog pro Kombination aus Tag, Land und Geraetetyp. Wo tausende Sets mit Millionen Eintraegen den verfuegbaren Speicher einer Redis-Instanz sprengen wuerden, bleiben tausende HyperLogLogs mit ihren konstanten 12 Kilobyte problemlos in einem Bruchteil des Speichers eines einzigen grossen Sets.

Auch bei der Replikation und beim Persistenz-Snapshot zahlt sich die Kompaktheit aus: Ein RDB-Snapshot mit tausenden HyperLogLog-Schluesseln bleibt handhabbar klein, waehrend dieselbe Anzahl an vollstaendigen Sets den Snapshot spuerbar aufblaehen und die Zeit fuer BGSAVE sowie die initiale Replikations-Synchronisation deutlich verlaengern wuerde.

Auch bei der Netzwerkbandbreite zahlt sich der Unterschied aus: Waehrend SMEMBERS auf einem grossen Set potenziell Megabyte an Daten ueber das Netzwerk uebertraegt, liefert PFCOUNT stets nur eine einzelne Zahl zurueck, unabhaengig von der geschaetzten Kardinalitaet. Das macht HyperLogLog auch bei sehr haeufigen Live-Abfragen, etwa fuer ein Echtzeit-Dashboard, ressourcenschonend.

8. Grenzen: wann HyperLogLog die falsche Wahl ist

HyperLogLog ist keine universelle Loesung fuer jedes Zaehlproblem. Wird eine exakte Zahl benoetigt, etwa fuer Rechnungsstellung, rechtliche Nachweise oder Kapazitaetslimits mit harten Grenzen, ist ein Set oder ein anderer exakter Zaehlmechanismus zwingend erforderlich. Ebenso ungeeignet ist HyperLogLog, wenn einzelne Elemente spaeter wieder identifiziert oder entfernt werden muessen, denn die Struktur speichert keine Elemente, sondern nur eine statistische Zusammenfassung.

Fuer sehr kleine Mengen, etwa unter hundert Elementen, lohnt sich HyperLogLog kaum, weil der feste Speicherbedarf von 12 Kilobyte in diesem Fall groesser ist als ein einfaches Set mit denselben wenigen Elementen. HyperLogLog spielt seine Staerke erst bei grossen bis sehr grossen Mengen aus, bei denen der konstante Speicherbedarf den linear wachsenden Speicherbedarf eines Sets deutlich unterbietet.

Auch fuer sicherheitskritische Zaehlungen, etwa das Erkennen von Brute-Force-Login-Versuchen mit einer harten Sperrgrenze, ist eine Naeherung riskant, weil ein Fehler von einem Prozent in die falsche Richtung im Zweifel den Unterschied zwischen einer korrekt blockierten Attacke und einer durchgelassenen Anfrage ausmachen kann. In solchen Faellen ist ein exakter Zaehler, etwa via INCR auf einem String, die richtige Wahl.

Ein weiterer Grenzfall betrifft sehr kleine, aber sehr viele parallele Zaehlungen: Tausende HyperLogLogs mit je wenigen Elementen summieren sich trotz kompakter sparse-Kodierung auf einen relevanten Gesamtspeicherbedarf. In solchen Faellen kann es guenstiger sein, mehrere kleine Zaehlkontexte in einem gemeinsamen Hash mit einer Bitmap-Loesung zu buendeln, statt fuer jeden Kontext ein eigenes HyperLogLog anzulegen.

9. HyperLogLog im Vergleich zu Set und Bitmap

Die folgende Tabelle stellt HyperLogLog den beiden verwandten Ansaetzen Set und Bitmap fuer Zaehl- und Mitgliedschaftsprobleme gegenueber.

Die Wahl zwischen den drei Strukturen haengt vom Genauigkeitsbedarf und der erwarteten Groessenordnung ab. HyperLogLog gewinnt immer dann, wenn eine Naeherung ausreicht und die Menge gross genug ist, damit sich der konstante Speicherbedarf gegenueber linear wachsenden Alternativen auszahlt. In der Praxis werden alle drei Strukturen haeufig nebeneinander eingesetzt, je nachdem, welche Anforderung fuer den jeweiligen Zaehler im Vordergrund steht.

10. Zusammenfassung

Redis HyperLogLog loest ein sehr konkretes Problem: die Kardinalitaet riesiger Mengen mit konstantem, minimalem Speicherbedarf schaetzen. Mit PFADD werden Elemente hinzugefuegt, mit PFCOUNT die Schaetzung abgefragt, mit PFMERGE mehrere HyperLogLogs dauerhaft und korrekt dedupliziert kombiniert. Der Speicherbedarf bleibt bei rund 12 Kilobyte pro Struktur, vollkommen unabhaengig davon, ob tausend oder eine Milliarde Elemente hinzugefuegt wurden, bei einem typischen Standardfehler von etwa 0,81 Prozent.

Fuer exakte Anforderungen wie Abrechnung oder rechtliche Nachweise bleibt ein Set die richtige Wahl. Fuer Analytics, Dashboards und Kapazitaetsplanung, wo eine verlaessliche Groessenordnung genuegt, ist HyperLogLog eine der effizientesten Datenstrukturen, die Redis bietet, und spart bei grossen Mengen typischerweise mehrere Groessenordnungen an Speicher gegenueber einer exakten Set-basierten Zaehlung.

Wer HyperLogLog in ein bestehendes Analytics-System einfuehrt, sollte mit unkritischen Metriken beginnen, etwa Seitenaufrufen oder Kampagnen-Reichweiten, und die Fehlermarge dort gegen die reale Praezisionsanforderung pruefen. Zeigt sich, dass 0,81 Prozent Abweichung in der Praxis nicht auffaellt, laesst sich die Migration schrittweise auf weitere Zaehler ausweiten, ohne das Risiko, an einer kritischen Stelle versehentlich Exaktheit zu verlieren.

11. FAQ: Redis HyperLogLog