Comment utiliser l'algorithme HyperLogLog de Redis

Vous vous relâchez joyeusement, mais le chef de produit vous envoie un document d'exigences par e-mail. L'entreprise doit conserver des statistiques à long terme sur les adresses IP quotidiennes des visiteurs du site Web, et la période statistique peut durer des mois, voire des années.

Après avoir lu les exigences, vous penserez que c'est si simple. Vous pouvez facilement implémenter cette fonction en utilisant le type de collection de Redis : générez une clé de type de collection chaque jour, utilisez SADD pour stocker l'adresse IP quotidienne du visiteur et utilisez la commande SCARD. pour obtenir facilement la quantité d’adresse IP quotidienne des visiteurs.

Vous avez rapidement fini de taper le code et réussi le test, et cette fonction a été lancée. Après être resté en ligne et avoir fonctionné pendant un certain temps, vous constaterez que le serveur sur lequel se trouve Redis commence à émettre une alarme. La raison en est que l'utilisation de la mémoire de certaines clés est trop importante. Vous avez jeté un coup d'œil et avez constaté que ces clés sont toutes des clés définies. qui stockent les adresses IP des visiteurs. Ce n’est qu’à ce moment-là que vous vous êtes tapoté la tête, sachant que vous vous étiez creusé un grand trou.

Supposons que le stockage d'une adresse IP au format IPv4 nécessite jusqu'à 15 octets et que le site Web compte jusqu'à 1 million de visiteurs par jour. Ces clés définies utiliseront 0,45 Go de mémoire par mois et 5,4 Go de mémoire par an. Ceci n'est qu'une estimation du format IPv4 si le format IPv6 occupera plus de mémoire. Bien que la complexité temporelle de SADD et SCARD soit O(1), leur consommation de mémoire est intolérable.

Vous avez parcouru le site officiel de Redis et avez constaté que Redis fournit également un type de données HyperLogLog, qui peut non seulement répondre aux besoins du produit mais également occuper moins de mémoire.

Algorithme HyperLogLog

HyperLogLog est un algorithme probabiliste créé spécifiquement pour calculer la cardinalité d'un ensemble. Il peut calculer la cardinalité approximative d'un ensemble donné.

La cardinalité approximative n'est pas la cardinalité réelle de l'ensemble. Elle peut être un peu plus petite ou plus grande que la cardinalité réelle, mais l'erreur entre la cardinalité estimée et la cardinalité réelle sera dans une plage raisonnable. exiger très précis Vous pouvez utiliser l'algorithme HyperLogLog.

L'avantage d'HyperLogLog est que la mémoire requise pour calculer la cardinalité approximative ne change pas en raison de la taille de l'ensemble. Quel que soit le nombre d'éléments que contient l'ensemble, la mémoire requise pour le calcul d'HyperLogLog est toujours fixe et très petite. .

Redis ne nécessite que 12 Ko de mémoire par type HyperLogLog pour compter près de : 2⁶⁴ éléments, alors que l'erreur type de l'algorithme n'est que de 0,81 %.

Si vous utilisez le type HyperLogLog pour implémenter les fonctions ci-dessus, s'il y a 1 million de visiteurs par jour, il n'occupera que 360 ​​Ko de mémoire en un mois.

PFADD

La commande PFADD peut compter un ou plusieurs éléments d'un ensemble donné.

Élément clé PFADD [élément...]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...]

Selon que l'élément donné a été compté, la commande PFADD peut renvoyer 0 ou 1 :

Si l'élément donné Tous les éléments ont été compté, la commande PFADD renverra 0, indiquant que la cardinalité approximative calculée par HyperLogLog n'a pas changé.

• Si la cardinalité approximative calculée par HyperLogLog change en raison de la présence d'au moins un élément dans l'élément donné qui n'a pas été compté précédemment, la commande PFADD renverra 1.

Par exemple :

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

Il est également possible de spécifier uniquement la clé sans préciser l'élément lors de l'appel de cette commande. Si la clé existe, aucune opération ne sera effectuée. Si elle n'existe pas, une donnée. La structure sera créée (renvoie 1).

PFCOUNT

Utilisez la commande PFCOUNT pour obtenir la cardinalité définie basée sur le calcul approximatif d'HyperLogLog. Si la clé donnée n'existe pas, 0 sera renvoyé.

Touche PFCOUNT [key...]🎜🎜Par exemple : 🎜rrreee🎜Lorsque plusieurs HyperLogLogs sont transmis à PFCOUNT, la commande PFCOUNT trouvera d'abord l'union de tous les HyperLogLogs, puis renverra le nombre approximatif base . La commande 🎜rrreee

🎜PFMERGE🎜🎜🎜PFMERGE peut effectuer un calcul d'union sur plusieurs HyperLogLogs, puis enregistrer l'union HyperLogLog calculée dans la clé spécifiée. 🎜🎜PFMERGE destKey sourceKey [sourceKey...]🎜🎜Si la clé spécifiée existe déjà, la commande PFMERGE écrasera la clé existante. 🎜rrreee🎜Vous pouvez voir que les commandes PFMERGE et PFCOUNT sont très similaires. En fait, la commande PFCOUNT effectue les opérations suivantes lors du calcul de la cardinalité approximative de plusieurs HyperLogLogs : 🎜🎜🎜🎜La commande PFMERGE est appelée en interne pour calculer l'union de tous étant donnés HyperLogLogs, et stockez cette union dans un HyperLogLog temporaire. 🎜🎜🎜🎜Exécutez la commande PFCOUNT sur l'HyperLogLog temporaire pour obtenir sa cardinalité approximative. 🎜🎜🎜🎜Supprimer l'HyperLogLog temporaire. 🎜🎜🎜🎜Renvoie la base approximative résultante. 🎜

Lorsque le programme a besoin d'appeler la commande PFCOUNT sur plusieurs HyperLogLogs, et que cet appel peut être répété plusieurs fois, vous pouvez envisager de remplacer cet appel par l'appel de commande PFMERGE correspondant : par Le calcul les résultats de l'union sont stockés dans l'HyperLogLog spécifié au lieu de recalculer l'union à chaque fois. Le programme peut minimiser les calculs d'union inutiles.

Scénario métier

Les fonctionnalités d'HyperLogLog sont très adaptées pour : le comptage (statistiques mensuelles, annuelles), la déduplication (détection de spams) et d'autres scénarios .

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!