So implementieren Sie Redis mit HyperLogLog

1. Übersicht

Redis hat in Version 2.8.9 die HyperLogLog-Datenstruktur hinzugefügt, die für Kardinalitätsstatistiken verwendet wird. Der Vorteil besteht darin, dass der zur Berechnung der Kardinalität erforderliche Platz relativ klein ist im Allgemeinen relativ konstant.

In Redis kostet jeder HyperLogLog-Schlüssel nur 12 KB Speicher, um die Kardinalität von fast 2^64 verschiedenen Elementen zu berechnen. Dies steht in scharfem Gegensatz zur Berechnung der Kardinalität, bei der eine Sammlung mit mehr Elementen mehr Speicher verbraucht. Da HyperLogLog die Kardinalität jedoch nur anhand der Eingabeelemente berechnet und die Eingabeelemente selbst nicht speichert, kann HyperLogLog nicht wie eine Sammlung einzelne Elemente der Eingabe zurückgeben.

2. Was ist die Kardinalität?

Zum Beispiel ist der Datensatz {1, 3, 5, 7, 5, 7, 8}, dann ist der Kardinalitätssatz dieses Datensatzes {1, 3, 5,7 , 8}, die Kardinalität (sich nicht wiederholende Elemente) beträgt 5. Bei der Kardinalitätsschätzung geht es darum, die Kardinalität schnell innerhalb des akzeptablen Fehlerbereichs zu berechnen.

3. Befehle

Derzeit werden nur drei Befehle, PFADD, PFCOUNT und PFMERGE, von HyperLogLog unterstützt. Lassen Sie uns sie zunächst einzeln vorstellen.

3.1 PFADD

Früheste verfügbare Version: 2.8.9. Zeitkomplexität: O(1). Der Befehl

PFADD kann Elemente (mehrere Elemente können angegeben werden) zur HyperLogLog-Datenstruktur hinzufügen und sie in dem durch den ersten Parameterschlüssel angegebenen Schlüssel speichern. Gibt 1 zurück, wenn sich die Kardinalitätsschätzung (Anzahl der ausgewerteten Elemente) geändert hat, andernfalls wird 0 zurückgegeben, d. h. um zu bestätigen, ob sich die Kardinalitätsschätzung nach der Ausführung des Befehls geändert hat. Wenn der angegebene Schlüssel nicht vorhanden ist, wird eine leere HyperLogLog-Datenstruktur erstellt (d. h. ein Redis-String mit der angegebenen String-Länge und -Codierung). Es ist auch möglich, den Befehl ohne Angabe eines Elementparameters und nur mit Angabe des Schlüssels aufzurufen. Wenn der Schlüssel vorhanden ist, tun Sie nichts und geben Sie 0 zurück. Wenn der Schlüssel nicht vorhanden ist, wird ein neuer HyperLogLog-Datenknoten erstellt und 1 zurückgegeben. Im Wesentlichen wird lediglich eine neue HyperLogLog-Datenstruktur generiert, ohne dass Elemente gespeichert werden.

(1) Syntaxformat:

PFADD key element [element ...]

(2) Rückgabewert:

Ganzzahl, wenn mindestens ein Element hinzugefügt wird, wird 1 zurückgegeben, andernfalls wird 0 zurückgegeben.

(3) Beispiel:

127.0.0.1:6379> PFADD hll a b c d e f g
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 7

3.2 PFCOUNT

Früheste verfügbare Version: 2.8.9. Zeitkomplexität: O(1). Für mehrere relativ große Schlüssel beträgt die Zeitkomplexität O(N).

Verwenden Sie den Befehl PFCOUNT, um einen geschätzten HyperLogLog-Kardinalitätswert (d. h. die Anzahl der Elemente) zu erhalten. Dieser Befehl gibt 0 zurück, wenn der Schlüssel nicht existiert, andernfalls gibt er eine Schätzung der Kardinalität des Schlüssels zurück. Bei mehreren Schlüsseln wird eine Kardinalitätsschätzung für die Vereinigung mehrerer HyperLogLogs zurückgegeben, die durch Zusammenführen mehrerer HyperLogLogs zu einem temporären HyperLogLog berechnet wird. Mit einer minimalen und konsistenten Speichermenge kann HyperLogLog die Anzahl der eindeutigen Elemente einer Sammlung zählen. Jedes HyperLogLog verwendet nur 12 KB plus ein paar Bytes des Schlüssels selbst.

(1) Syntaxformat:

PFCOUNT key [key ...]

(2) Rückgabewert:

integer, gibt die Kardinalitätsschätzung des angegebenen HyperLogLogs zurück. Wenn mehrere HyperLogLogs vorhanden sind, wird die Kardinalitätsschätzung der Union zurückgegeben.

(3) Beispiel:

127.0.0.1:6379> PFADD hll foo bar zap
(integer) 1
127.0.0.1:6379> PFADD hll zap zap zap
(integer) 0
127.0.0.1:6379> PFADD hll foo bar
(integer) 0
127.0.0.1:6379> PFCOUNT hll
(integer) 3
127.0.0.1:6379> PFADD some-other-hll 1 2 3
(integer) 1
127.0.0.1:6379> PFCOUNT some-other-hll
(integer) 3
127.0.0.1:6379> PFCOUNT hll some-other-hll
(integer) 6

(4) Einschränkung: Die von

HyperLogLog zurückgegebenen Ergebnisse sind nicht genau und die Fehlerquote beträgt etwa 0,81 %.

Mit diesem Befehl wird HyperLogLog geändert und 8 Bytes zum Speichern der zuletzt berechneten Basis verwendet. Technisch gesehen ist PFCOUNT also ein Schreibbefehl.

(5) Leistungsprobleme

Auch wenn die Verarbeitung eines intensiven HyperLogLog theoretisch länger dauert, weist der Befehl PFCOUNT immer noch eine hohe Leistung auf, wenn nur ein Schlüssel angegeben wird. Dies liegt daran, dass PFCOUNT die Basis der letzten Berechnung zwischenspeichert und sich diese Basis nicht ständig ändert, da der Befehl PFADD das Register in den meisten Fällen nicht aktualisiert. Daher kann der Effekt von Hunderten von Anfragen pro Sekunde erzielt werden.

Wenn Sie den Befehl PFCOUNT verwenden, um mehrere Schlüssel zu verarbeiten, wird HyperLogLog zusammengeführt. Noch wichtiger ist, dass die berechnete Kardinalität der Vereinigung nicht zwischengespeichert werden kann. Bei Verwendung mehrerer Schlüssel kann die Ausführung von PFCOUNT einige Zeit dauern (normalerweise in der Größenordnung von Millisekunden), daher wird eine übermäßige Verwendung nicht empfohlen.

Es ist zu beachten, dass die Einzelschlüssel- und Mehrschlüssel-Ausführungssemantik dieses Befehls unterschiedlich ist und eine unterschiedliche Leistung aufweist. Eine übermäßige Verwendung der Mehrschlüssel-Ausführungssemantik wird nicht empfohlen.

3.3 PFMERGE

Früheste verfügbare Version: 2.8.9. Zeitkomplexität: O(N), N ist die Anzahl der zusammenzuführenden HyperLogLogs.

Mehrere HyperLogLogs können über den Befehl PFMERGE zu einem HyperLogLog zusammengeführt werden. Die Kardinalitätsschätzung des zusammengeführten HyperLogLog wird berechnet, indem die Vereinigung aller gegebenen HyperLogLogs gebildet wird. Das berechnete Ergebnis wird auf dem angegebenen Schlüssel gespeichert.

Syntaxformat:

PFMERGE destkey sourcekey [sourcekey ...]

Rückgabewert:

Rückgabe OK.

Beispiel:

127.0.0.1:6379> PFADD hll1 foo bar zap a
(integer) 1
127.0.0.1:6379> PFADD hll2 a b c foo
(integer) 1
127.0.0.1:6379> PFMERGE hll3 hll1 hll2
OK
127.0.0.1:6379> PFCOUNT hll3
(integer) 6

Das obige ist der detaillierte Inhalt vonSo implementieren Sie Redis mit HyperLogLog. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!