Redis-HyperLogLog

Redis fügte die HyperLogLog-Struktur in Version 2.8.9 hinzu.

Redis HyperLogLog ist ein Algorithmus für Kardinalitätsstatistiken. Der Vorteil von HyperLogLog besteht darin, dass bei sehr, sehr großer Anzahl oder Menge an Eingabeelementen der zur Berechnung der Kardinalität benötigte Speicherplatz immer konstant und sehr klein ist.

In Redis benötigt jeder HyperLogLog-Schlüssel nur 12 KB Speicher, um die Kardinalität von nahezu 2^64 unterschiedlichen Elementen zu berechnen. Das steht in scharfem Kontrast zu Mengen, bei denen mit steigender Elementanzahl auch mehr Speicher bei der Berechnung der Kardinalität verbraucht wird.

Da HyperLogLog die Kardinalität jedoch nur anhand der Eingabeelemente berechnet und die Eingabeelemente selbst nicht speichert, kann HyperLogLog – anders als Mengen – die einzelnen Eingabeelemente nicht zurückgeben.

Was ist Kardinalität?

Zum Beispiel ist bei der Datenmenge {1, 3, 5, 7, 5, 7, 8} die Kardinalitätsmenge dieser Datenmenge {1, 3, 5, 7, 8}, und die Kardinalität (distinkte Elemente) ist 5. Die Kardinalitätsschätzung besteht darin, die Kardinalität innerhalb eines akzeptablen Fehlerbereichs schnell zu berechnen.

Beispiel

Das folgende Beispiel zeigt, wie HyperLogLog funktioniert:

redis 127.0.0.1:6379> PFADD examplekey "redis"

1) (integer) 1

redis 127.0.0.1:6379> PFADD examplekey "mongodb"

1) (integer) 1

redis 127.0.0.1:6379> PFADD examplekey "mysql"

1) (integer) 1

redis 127.0.0.1:6379> PFCOUNT examplekey

(integer) 3