Redis-KardinalitätsstatistikHyperLogLog verfügt über einen kleinen Speicher und eine große Verwendung

Wir wussten immer, dass Redis über mehrere häufig verwendete Datenstrukturen verfügt, z. B. Zeichenfolgen, Hashes, Listen, Mengen und geordnete Mengen. Tatsächlich hat Redis später viele Ergänzungen vorgenommen, darunter HyperLogLog und GEO (geografischer Standort), das in Version 3.2 hinzugefügt wurde.

Hier stellen wir kurz die HyperLogLog-Struktur vor.

Lassen Sie uns zunächst über die Verwendung sprechen: Diese Struktur kann viel Speicher sparen, um verschiedene Zählungen zu zählen, wie z. B. die Anzahl der registrierten IPs, die Anzahl der täglich besuchten IPs, die Echtzeit-UV der Seite ( (die PV muss eine Zeichenfolge sein) und die Anzahl der Online-Benutzer, die warten.

Hier handelt es sich bei allen Verwendungen um xxx-Zahlen. Das Merkmal dieser Datenstruktur besteht also darin, dass sie die Menge, die Sie zählen möchten, genauer schätzen kann, es jedoch unmöglich ist, den detaillierten Inhalt der Statistiken zu kennen. Wenn Sie beispielsweise die Anzahl der täglich besuchten IPs zählen, können Sie die Gesamtzahl der zu diesem Zeitpunkt besuchten IPs ermitteln. Es gibt jedoch keine Möglichkeit herauszufinden, um welche IPs es sich handelt.

Es gibt natürlich Gewinne und Verluste, die Sie mit den oben genannten Inhalten verarbeiten können, damit Sie die Menge kennen und alle detaillierten Listen erhalten. Aber für eine große Website gibt es beispielsweise 1 Million IPs pro Tag. Wir berechnen, dass eine IP 15 Bytes verbraucht, also sind 1 Million IPs 150 MB.

Schauen wir uns noch einmal unser HyperLogLog an. Jeder Schlüssel in Redis belegt 12 KB Inhalt, und der theoretische Speicher liegt unabhängig vom gespeicherten Inhalt bei etwa 2^64 Werten. 12K, Sie kennen die Rolle dieser Datenstruktur. Aus diesem Grund kann er die Details im Inneren nicht kennen. Hierbei handelt es sich um einen auf Kardinalitätsschätzung basierenden Algorithmus, der die Kardinalität nur relativ genau schätzen kann und eine kleine Menge festen Speichers zum Speichern und Identifizieren eindeutiger Elemente in der Menge verwenden kann. Und die Grundlage dieser Schätzung ist nicht unbedingt genau. Es handelt sich um eine Näherung mit einem Standardfehler von 0,81 %.

Je mehr Inhalte Sie hier aufzeichnen, desto einfacher ist es, einen scharfen Kontrast zu den in der Sammlung verwendeten Inhalten herzustellen, da die HyperLogLog-Struktur, unabhängig davon, wie viele Werte der Bereich zulässt, ist ausgegraut und belegt 12 KB Speicher.

Wenn wir beispielsweise die tägliche IP aufzeichnen und davon ausgehen, dass jeden Tag 100 Millionen IP-Zugriffe erfolgen, beträgt die Speichernutzung pro Tag 1,5 G. Angenommen, wir speichern die Aufzeichnungen eines Monats 45G Kapazität. Bei Verwendung von HyperLogLog sind es jedoch 12.000 pro Tag und 360.000 pro Monat. Wenn wir die spezifischen Informationen der IP nicht kennen müssen, können wir diese Aufzeichnungen ein Jahr lang im Speicher behalten oder sie nicht löschen. Bei Bedarf speichern wir sämtliche IP-Zugriffsdatensätze auch auf andere Weise. Durch die Speicherung täglicher Informationen können wir die Gesamtzahl der IPs pro Monat (MERGE), die Gesamtzahl der IPs in einem Jahr usw. berechnen (Duplikate entfernen).

Das Folgende ist eine Einführung in den HyperLogLog-Befehl. Tatsächlich ähnelt er dem Sammlungsbefehl, außer dass es weniger Befehle gibt und die Liste nicht abgerufen werden kann. Darüber hinaus erfordert die Verwendung dieser Datenstruktur Version 2.8.9 und höher.

PFADD

Nach der Ausführung dieses Befehls wird die interne Struktur von HyperLogLog aktualisiert und bei Ausführung wird eine Rückmeldung gegeben Wenn sich nach Abschluss die interne Kardinalitätsschätzung von HyperLogLog ändert, wird 1 zurückgegeben, andernfalls (es wird davon ausgegangen, dass es bereits existiert) wird 0 zurückgegeben.
Eine weitere magische Eigenschaft dieses Befehls ist, dass er nur Schlüssel und keine Werte haben kann. Das bedeutet, dass nur leere Schlüssel ohne Werte erstellt werden.
Wenn der Schlüssel vorhanden ist, tun Sie nichts und geben Sie 0 zurück. Wenn er nicht vorhanden ist, erstellen Sie ihn und geben Sie 1 zurück.

Die zeitliche Komplexität dieses Befehls beträgt O(1), Sie können ihn also gerne verwenden~

Befehlsbeispiel:

redis> PFADD  ip:20160929  "1.1.1.1"  "2.2.2.2"  "3.3.3.3"
(integer) 1
redis> PFADD  ip:20160929 "2.2.2.2"  "4.4.4.4"  "5.5.5.5"  # 存在就只加新的
(integer) 1
redis> PFCOUNT  ip:20160929  # 元素估计数量没有变化
(integer) 5
redis> PFADD  ip:20160929 "2.2.2.2"  # 存在就不会增加
(integer) 0

Tatsächlich haben wir das gefunden, als Es gibt weniger. Ziemlich genau, haha.

PFCOUNT

Tatsächlich haben wir dies bereits in der obigen Studie verwendet und werden es hier vorstellen.

Wenn der Befehl auf einen einzelnen Schlüssel angewendet wird, wird die Kardinalitätsschätzung des Schlüssels zurückgegeben. Wenn der Schlüssel nicht existiert, wird 0 zurückgegeben.
Bei Anwendung auf mehrere Schlüssel wird die Vereinigungsschätzung dieser Schlüssel zurückgegeben. Rufen Sie diesen Befehl zur Ausgabe auf, ähnlich wie beim Zusammenführen dieser Schlüssel.

Wenn dieser Befehl mit einem einzelnen Wert arbeitet, ist die Zeitkomplexität O(1) und hat eine sehr niedrige durchschnittliche konstante Zeit, wenn er mit N Werten arbeitet, ist die Zeitkomplexität O(N), die Konstante Die Komplexität dieses Befehls wird geringer sein.

Befehlsbeispiel:

redis> PFADD  ip:20160929  "1.1.1.1"  "2.2.2.2"  "3.3.3.3"
(integer) 1
redis> PFCOUNT  ip:20160929
(integer) 3
redis> PFADD  ip:20160928  "1.1.1.1"  "4.4.4.4"  "5.5.5.5"
(integer) 1
redis> PFCOUNT  ip:20160928  ip:20160929
(integer) 5

PFMERGE

Mehrere HyperLogLogs zu einem HyperLogLog zusammenführen. Tatsächlich ist dies leicht zu verstehen, und die kombinierte geschätzte Kardinalität entspricht auch ungefähr der Vereinigung aller geschätzten Kardinalitäten von HyperLogLog.

Der erste Parameter dieses Befehls ist der Zielschlüssel, und die restlichen Parameter sind das zusammenzuführende HyperLogLog. Wenn der Befehl ausgeführt wird und der Zielschlüssel nicht vorhanden ist, wird er erstellt und dann zusammengeführt.

Die zeitliche Komplexität dieses Befehls beträgt O(N), wobei N die Anzahl der zusammenzuführenden HyperLogLogs ist. Allerdings ist die konstante Zeitkomplexität dieses Befehls relativ hoch.

Befehlsbeispiel:

edis> PFADD  ip:20160929  "1.1.1.1"  "2.2.2.2"  "3.3.3.3"
(integer) 1
redis> PFADD  ip:20160928  "1.1.1.1"  "4.4.4.4"  "5.5.5.5"
(integer) 1
redis> PFMERGE ip:201609   ip:20160928   ip:20160929
OK
redis> PFCOUNT  ip:201609
(integer) 5

到此HyperLogLog所有的命令就都介绍完了，没错，目前就只有这三个。其实也很简单的，知道了这个结构的用法，也就知道什么时候适合用了，对我们非常珍贵的内存还是很有帮助。