Probabilistische Datenstrukturen: HyperLogLog

Angenommen wir möchten in einer Web-Applikation messen, wie viele Unique-Users [1] jeden Tag, jede Woche und jeden Monat mit dem Dienst interagieren.
Die wohl einfachste Lösung sähe wohl so aus: In einer Logging-Tabelle mit den Spalten „Uhrzeit“ und „User-ID“ werden bei jedem Seitenaufruf ein Eintrag mit der Uhrzeit und einem eindeutigen Identifizierungsmerkmal abgelegt. (In der Regel wird so ein Marker mithilfe eines Langzeit-Cookies realisiert.) Möchte man nun wissen, wie viele eindeutige Besucher pro Tag zu Besuch waren, fragt man diese über eine gruppierte Abfrage aus dieser Tabelle ab. Diese Abfrage könnte zum Beispiel so aussehen:

SELECT COUNT(*) AS number, DATE(time)
FROM log_table
GROUP BY DATE(time), user_ident

Dieses Vorgehen bringt einen entscheidenden Nachteil mit sich:
Der benötigte Speicherplatz ist nicht konstant, sondern direkt abhängig von der tatsächlichen Anzahl der Besucher und der Anzahl der Besuche. Dies ist bei kleineren Services möglicherweise noch kein Problem. Wenn die täglichen Seitenabrufe aber mal in die Millionen gehen, benötigt so eine simple Funktionalität wie die statistische Besucher-Auswertung auf einmal doch eine nicht triviale Menge an Festplattenplatz. Zusätzlich leidet die Performance der Auswertung, wenn man nicht mit komplizierten Caching-Mechanismen versucht, Daten-Aggregate im Voraus zu berechnen.

HyperLogLog to the rescue! (Hyper-what???)

HyperLogLog ist ein Algorithmus, der sich die Regeln der Wahrscheinlichkeit zu Nutze macht, um bei konstantem Speicherplatz Auskunft über die Anzahl von distinkten Werten geben zu können.
Entscheidend dabei ist die Kardinalität des zu speichernden Wertes. Betrachten wir zum Beispiel den Inhalt von folgendem Fruchtkorb:

Banane
Apfel
Apfel
Birne
Orange

Die Kardinalität des Wertes „Obst“ ist 4, das heißt es gibt vier verschiedene Obstsorten. Nachdem alle Früchte der Datenstruktur hinzugefügt und entsprechend kodiert wurden, kann der Algorithmus diese Kardinalität über eine einfache Berechnung abschätzen. Im Gegenteil zu dem obigen Beispiel wird jedoch nicht jede Frucht einzeln sondern in kodierter Form abgelegt, deswegen ist der dafür benötigte Speicherplatz konstant und damit unabhängig von der zu zählenden Ereignis-Anzahl.

Weil hier die Regeln der Wahrscheinlichkeit gelten, ist diese ermittelte Kardinalität natürlich kein exakter Wert. Des Weiteren hat die maximale Kardinalität eine Obergrenze.
Der Fehler liegt aber im Bereich von etwa 2% bei nur 1,5Kb benötigtem Speicherplatz bei einer Maximal-Kardinalität von über 10^9.

Einsatz

Möchte man HyperLogLog einsetzen bietet sich dafür zum Beispiel ein Key-Value-Storage wie das Datenbank-System „Redis“ an. Redis bietet über die Operatoren „pfadd“ und „pfcount“ die Möglichkeit den Algorithmus einzusetzen.

Wenden wir ihn auf unser Beispiel vom Anfang an!
Folgende Seitenaufrufe werden im Laufe des 01.10.2019 registriert:

10:00 Ada
10:01 Anni
10:01 Margret
10:08 Ada
10:08 Barbara
10:09 Ada
10:10 Anni
10:10 Ada
10:11 Grace
10:12 Barbara
10:14 Anni
10:14 Ada
10:15 Ada

Insgesamt haben wir also zwölf Aufrufe von fünf verschiedenen Personen registriert.
Wir möchten in unserem Beispiel die Seitenaufrufe pro Tag identifizieren können und müssen dazu einen Schlüssel definieren, unter der die Datenstruktur zugreifbar ist, zum Beispiel „views:2019-10-01“.
Wir benutzen den „pfadd“-Aufruf von Redis, um diesem Schlüssel alle entstehenden Aufrufe zuzuordnen:

pfadd views:2019-10-01 Anni
:1
pfadd views:2019-10-01 Margret
:1
pfadd views:2019-10-01 Ada
:1
pfadd views:2019-10-01 Barbara
:1
pfadd views:2019-10-01 Ada
:0
…

Der Rückgabewert (:1 oder :0) zeigt hier schon, ob der Wert schon einmal hinzugefügt worden ist. In Zeile 5 wurde „ada“ zum zweiten Mal eingetragen, entsprechend die Rückgabe (:0).
Im Anschluss benötigen wie lediglich den Aufruf „pfcount“, um die Anzahl der unterschiedlichen Besucher abzufragen:

pfcount views:2019-10-01
:5

In der Anforderung war jedoch nicht nur die Anzahl der Unique-Users pro Tag gefragt, sondern auch die Anzahl der User pro Woche und pro Monat. Natürlich können wir nicht einfach die Zahlen der verschiedenen Tage nehmen und addieren. Wenn ein User innerhalb eine Woche jeden Tag als Besucher auftritt soll die Person für diese Woche trotzdem nur einmal gezählt werden!

Hier bietet Redis zwei Möglichkeiten.
Zum Einen können wir an „pfcount“ mehrere Schlüssel übergeben. Diese werden dann intern zusammengefasst, wobei die Gesamtkardinalität berücksichtigt wird:

pfcount views:2019-09-30 views:2019-10-01 views:2019-10-02 views:2019-10-03 views:2019-10-04 views:2019-10-05 views:2019-10-06
:42

Alternativ steht die Operation „pfmerge“ zur Verfügung. Diese fasst unter Berücksichtigung der gesamten Kardinalität mehrere Einträge zu einem neuen Eintrag (views:week:2019-09-30) zusammen:

pfmerge views:week:2019-09-30 views:2019-09-30 views:2019-10-01 views:2019-10-02 views:2019-10-03 views:2019-10-04 views:2019-10-05 views:2019-10-06
+OK
pfcount views:week:2019-09-30
:1337

Resourcenbetrachtung

Ich habe auf meinem Laptop eine Redis-Instance in einem Docker-Container gestartet und mit einem Test-Skript 10.000 Werte abgespeichert. Bei jedem Aufruf habe ich die benötigte Zeit gemessen. Zusätzlich habe ich die erstellte Datenstruktur 10.000 mal aus der Datenbank abgefragt. Im Median benötigt ein „pfadd“-Aufruf ca. 0.15ms, ein „pfcount“-Aufruf liegt mit ca. 0.16ms in einer ähnlichen Größenordnung. Dabei spielt es weder beim Hinzufügen noch beim Auslesen eine Rolle, wie viele Einträge bereits abgelegt worden sind.
Wer möchte kann sich mein Testskript bei Github ansehen.

Andere probabilistische Datenstrukturen

In Teil 2 werden wir uns mit einer weiteren probabilistischen Datenstruktur, dem Bloom-Filter beschäftigen. Im Gegensatz zum HyperLogLog geht es hierbei nicht darum die Anzahl von eindeutigen Werten zu messen, stattdessen ist es möglich, mit dem Bloom-Filter das Vorhandensein (oder die Abwesenheit) eines bestimmten Wertes zu ermitteln.

Quellen:
https://en.wikipedia.org/wiki/HyperLogLog
https://redis.io/commands/pfadd
https://redis.io/commands/pfcount
https://redis.io/commands/pfmerge

[1] Ein Unique-User zählt innerhalb eines definierten Zeitraumes nur einmal, unabhängig davon wie viele Seitenaufrufe die Person macht.