Eine kurze Analyse des Lernens von HyperLogLog für Redis-Datentypen

Dieser Artikel wird Ihnen helfen, den HyperLogLog im Redis-Datentyp zu verstehen, der normalerweise zum Zählen der Anzahl eindeutiger Elemente in einer Sammlung verwendet wird. Ich hoffe, er wird Ihnen hilfreich sein!

Heute ist Freitag, Sie fischen fröhlich und der Produktmanager sendet Ihnen ein Anforderungsdokument per E-Mail. Die Nachfrage ist wahrscheinlich: Das Unternehmen muss die täglichen Besucher-IPs der Website zählen, und diese Statistik ist ein langfristiges Verhalten, das von einigen Monaten bis zu einigen Jahren reicht.

Nachdem Sie die Anforderungen gelesen haben, werden Sie denken, dass dies so einfach ist. Sie können diese Funktion einfach mit dem Sammlungstyp von Redis implementieren: Generieren Sie jeden Tag einen Sammlungstypschlüssel, verwenden Sie SADD, um die tägliche Besucher-IP zu speichern, und verwenden Sie den SCARD-Befehl um ganz einfach die tägliche Besucher-IP zu erhalten.

Sie haben den Code schnell eingegeben, den Test bestanden und diese Funktion wurde gestartet. Nachdem Sie eine Weile online gegangen sind, werden Sie feststellen, dass der Server, auf dem sich Redis befindet, einen Alarm auslöst. Der Grund dafür ist, dass die Speichernutzung einiger Schlüssel zu groß ist. Sie haben einen Blick darauf geworfen und festgestellt, dass es sich bei diesen Schlüsseln um festgelegte Schlüssel handelt die Besucher-IPs speichern. Erst dann tätschelten Sie Ihren Kopf und wussten, dass Sie sich ein großes Loch gegraben hatten.

Gehen Sie davon aus, dass das Speichern einer IP-Adresse im IPv4-Format bis zu 15 Bytes erfordert und die Website bis zu 1 Million Besucher pro Tag hat. Diese festgelegten Schlüssel verbrauchen 0,45 GB Speicher pro Monat und 5,4 GB Speicher pro Jahr. Dies ist nur eine Schätzung des IPv4-Formats, wenn das IPv6-Format mehr Speicher belegt. Obwohl die Zeitkomplexität von SADD und SCARD O(1) ist, ist ihr Speicherverbrauch inakzeptabel.

Sie haben die offizielle Website von Redis durchsucht und festgestellt, dass Redis auch einen Datentyp HyperLogLog bereitstellt, der nicht nur die Anforderungen des Produkts erfüllen kann, sondern auch weniger Speicher belegt. [Verwandte Empfehlungen: Redis-Video-Tutorial]

HyperLogLog-Algorithmus

HyperLogLog ist ein probabilistischer Algorithmus, der speziell für die Berechnung der Kardinalität einer Menge entwickelt wurde. Er kann die ungefähre Kardinalität einer bestimmten Menge berechnen.

Die ungefähre Kardinalität ist nicht die tatsächliche Kardinalität der Menge. Sie kann etwas kleiner oder größer sein als die tatsächliche Kardinalität, aber der Fehler zwischen der geschätzten Kardinalität und der tatsächlichen Kardinalität liegt in einem angemessenen Bereich erfordern sehr genaue Sie können den HyperLogLog-Algorithmus verwenden.

Der Vorteil von HyperLogLog besteht darin, dass sich der Speicherbedarf für die Berechnung der ungefähren Kardinalität aufgrund der Größe des Satzes nicht ändert. Unabhängig davon, wie viele Elemente der Satz enthält, ist der für die Berechnung von HyperLogLog erforderliche Speicher immer fest und sehr gering. .

Redis benötigt nur 12 KB Speicher pro HyperLogLog-Typ, um nahezu 2⁶⁴ Elemente zu zählen, während der Standardfehler des Algorithmus nur 0,81 % beträgt.

Wenn Sie den HyperLogLog-Typ verwenden, um die oben genannten Funktionen zu implementieren, werden bei 1 Million Besuchern pro Tag in einem Monat nur 360 KB Speicher belegt.

PFADD

Der PFADD-Befehl kann ein oder mehrere gegebene Mengenelemente zählen.

PFADD-Schlüsselelement [Element...]PFADD key element [element...]

根据给定的元素是否已经进行过计数，PFADD 命令可能返回 0，也可能返回 1：

• 如果给定的所有元素都已经进行过计数，那么 PFADD 命令将返回 0，表示 HyperLogLog 计算出的近似基数没有发生变化。
• 如果给定的元素中出现了至少一个之前没有进行过计数的元素，导致 HyperLogLog 计算出的近似基数发生了变化，那么 PFADD 命令将返回 1。

例如：

redis> PFADD letters a b c -- 第一次添加
(integer) 1
redis> PFADD letters a     -- 第二次添加
(integer) 0

如果在调用该命令时仅指定 key 而不指定元素也是可以的，如果 key 存在，则不会有任何操作，如果不存在，则会创建一个数据结构（返回 1）。

PFCOUNT

通过 PFCOUNT 命令可以获取 HyperLogLog 为集合计算出的近似基数。若给定的 key 不存在将返回 0。

PFCOUNT key [key...]

例如：

redis> PFCOUNT letters
(integer) 3

当向 PFCOUNT 传入多个 HyperLogLog 时，PFCOUNT 命令将先对所有的 HyperLogLog 求并集，然后返回近似基数。

redis> PFADD letters1 a b c
(integer) 1
redis> PFADD letters2 c d e
(integer) 1
redis> PFCOUNT letters1 letters2
(integer) 5

PFMERGE

PFMERGE 命令可以对多个 HyperLogLog 执行并集计算，然后把计算得出的并集 HyperLogLog 保存到指定的键中。

PFMERGE destKey sourceKey [sourceKey...]

Je nachdem, ob das angegebene Element gezählt wurde, kann der PFADD-Befehl 0 oder 1 zurückgeben:

Wenn angegeben, haben alle Elemente von have gezählt wurde, gibt der PFADD-Befehl 0 zurück, was darauf hinweist, dass sich die von HyperLogLog berechnete ungefähre Kardinalität nicht geändert hat.
Wenn sich die von HyperLogLog berechnete ungefähre Kardinalität aufgrund des Vorhandenseins von mindestens einem Element im angegebenen Element ändert, das zuvor nicht gezählt wurde, gibt der PFADD-Befehl 1 zurück.
• Zum Beispiel:

  redis> PFADD letters1 a b c
  (integer) 1
  redis> PFADD letters2 c d e
  (integer) 1
  redis> PFMERGE res letters1 letters2
  OK
  redis> PFCOUNT res
  (integer) 5

  Es ist auch möglich, beim Aufrufen dieses Befehls nur den Schlüssel anzugeben, ohne das Element anzugeben. Wenn der Schlüssel vorhanden ist, wird keine Operation ausgeführt wird erstellt (Return 1).

• PFCOUNT

Verwenden Sie den Befehl PFCOUNT, um die von HyperLogLog berechnete ungefähre Kardinalität für den Satz zu erhalten. Wenn der angegebene Schlüssel nicht existiert, wird 0 zurückgegeben.

• PFCOUNT key [key...]

Zum Beispiel:
• rrreee

  Wenn mehrere HyperLogLogs an PFCOUNT übergeben werden, findet der PFCOUNT-Befehl zuerst die Vereinigung aller HyperLogLogs und gibt dann den ungefähren Wert zurück Basis. Der Befehl

  rrreee

  🎜PFMERGE🎜🎜🎜PFMERGE kann die Vereinigungsberechnung für mehrere HyperLogLogs durchführen und dann das berechnete Union-HyperLogLog im angegebenen Schlüssel speichern. 🎜🎜PFMERGE destKey sourceKey [sourceKey...]🎜🎜Wenn der angegebene Schlüssel bereits vorhanden ist, überschreibt der Befehl PFMERGE den vorhandenen Schlüssel. 🎜rrreee🎜Sie können sehen, dass die Befehle PFMERGE und PFCOUNT sehr ähnlich sind. Tatsächlich führt der Befehl PFCOUNT die folgenden Operationen aus, wenn er die ungefähre Kardinalität mehrerer HyperLogLogs berechnet: 🎜🎜🎜🎜Der Befehl PFMERGE wird intern aufgerufen, um die Vereinigung von zu berechnen alle angegebenen HyperLogLogs und speichern Sie diese Vereinigung in einem temporären HyperLogLog. 🎜🎜🎜🎜Führen Sie den Befehl PFCOUNT für das temporäre HyperLogLog aus, um dessen ungefähre Kardinalität zu erhalten. 🎜🎜🎜🎜Temporäres HyperLogLog löschen. 🎜🎜🎜🎜Gibt die resultierende ungefähre Basis zurück. 🎜

Wenn das Programm den Befehl PFCOUNT für mehrere HyperLogLogs aufrufen muss und dieser Aufruf möglicherweise mehrmals wiederholt wird, können Sie diesen Aufruf durch den entsprechenden Aufruf des Befehls PFMERGE ersetzen: indem Sie das Ergebnis der Vereinigungsberechnung im angegebenen Speicherort speichern, anstatt es neu zu berechnen Wenn Sie in HyperLogLog jedes Mal die Vereinigung durchführen, kann das Programm unnötige Vereinigungsberechnungen minimieren.

Geschäftsszenarien

Die Funktionen von HyperLogLog eignen sich sehr gut für: Zählung (monatliche, jährliche Statistiken), Deduplizierung (Spam-SMS-Erkennung) und andere Szenarien.

Weitere Kenntnisse zum Thema Programmierung finden Sie unter: Einführung in die Programmierung! !

Das obige ist der detaillierte Inhalt vonEine kurze Analyse des Lernens von HyperLogLog für Redis-Datentypen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!