Comment implémenter Redis à l'aide d'HyperLogLog

1. Présentation

Redis a ajouté la structure de données HyperLogLog dans la version 2.8.9, qui est utilisée pour les statistiques de cardinalité. Son avantage est que lorsque le nombre d'éléments d'entrée est très grand, c'est le cas. nécessaire pour calculer la cardinalité. L'espace est plus petit et généralement plus constant.

Dans Redis, chaque clé HyperLogLog ne coûte que 12 Ko de mémoire pour calculer la cardinalité de près de 2^64 éléments différents. Cela contraste fortement avec le calcul de cardinalité, où une collection contenant plus d’éléments consomme plus de mémoire. Cependant, comme HyperLogLog calcule uniquement la cardinalité en fonction des éléments d'entrée et ne stocke pas les éléments d'entrée eux-mêmes, HyperLogLog ne peut pas renvoyer des éléments individuels de l'entrée comme une collection.

2. Quelle est la cardinalité ?

Par exemple, l'ensemble de données {1, 3, 5, 7, 5, 7, 8}, puis l'ensemble de cardinalité de cet ensemble de données est { 1, 3, 5, 7, 8}, la cardinalité (éléments non répétitifs) est 5. L'estimation de la cardinalité consiste à calculer rapidement la cardinalité dans la plage d'erreur acceptable.

3. Commandes

Actuellement, seules trois commandes, PFADD, PFCOUNT et PFMERGE, sont prises en charge par HyperLogLog. Présentons-les d’abord un par un.

3.1 PFADD

Première version disponible : 2.8.9. Complexité temporelle : O(1).

La commande PFADD peut ajouter des éléments (plusieurs éléments peuvent être spécifiés) à la structure de données HyperLogLog et les stocker dans la clé spécifiée par la première clé de paramètre. Renvoie 1 si l'estimation de cardinalité (nombre d'éléments évalués) a changé, sinon renvoie 0, c'est-à-dire pour confirmer si l'estimation de cardinalité a changé après l'exécution de la commande. Si la clé spécifiée n'existe pas, une structure de données HyperLogLog vide est créée (c'est-à-dire une chaîne Redis avec la longueur de chaîne et l'encodage spécifiés). Il est également possible d'appeler la commande sans spécifier de paramètre d'élément et en spécifiant uniquement la clé. Si la clé existe, ne faites rien et renvoyez 0 ; si la clé n'existe pas, un nouveau nœud de données HyperLogLog est créé et 1 est renvoyé. Essentiellement, il génère simplement une nouvelle structure de données HyperLogLog sans stocker aucun élément.

(1) Format de syntaxe :

PFADD key element [element ...]

(2) Valeur de retour :

Entier, si au moins un élément est ajouté, 1 est renvoyé . Sinon, renvoie 0.

(3) Exemple :

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

Première version disponible : 2.8.9. Complexité temporelle : O(1) Pour plusieurs clés relativement volumineuses, la complexité temporelle est O(N).

Utilisez la commande PFCOUNT pour obtenir une valeur de cardinalité estimée HyperLogLog (c'est-à-dire le nombre d'éléments). Cette commande renvoie 0 si la clé n'existe pas, sinon elle renvoie une estimation de la cardinalité de la clé. Pour plusieurs clés, le résultat est une estimation de cardinalité pour l’union de plusieurs HyperLogLogs, calculée en fusionnant plusieurs HyperLogLogs dans un HyperLogLog temporaire. En utilisant une quantité minimale et cohérente de mémoire, HyperLogLog peut compter le nombre d'éléments uniques d'une collection. Chaque HyperLogLog utilise seulement 12 Ko plus quelques octets de la clé elle-même.

(1) Format de syntaxe :

PFCOUNT key [key ...]

(2) Valeur de retour :

Integer, renvoie l'estimation de cardinalité de l'HyperLogLog spécifié, s'il y a sont multiples HyperLogLog renvoie l'estimation de cardinalité de l'union.

(3) Exemple :

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) Limitation :

HyperLogLog Les résultats renvoyés ne sont pas précis et le taux d'erreur est d'environ 0,81 %.

L'utilisation de cette commande modifiera HyperLogLog et utilisera 8 octets pour stocker la dernière base calculée. Donc, techniquement parlant, PFCOUNT est une commande d'écriture.

(5) Problèmes de performances

Même si le traitement d'un HyperLogLog intensif prend théoriquement beaucoup de temps, la commande PFCOUNT a toujours de hautes performances lorsqu'une seule clé est spécifiée. performance. En effet, PFCOUNT met en cache la base du dernier calcul, et cette base ne change pas tout le temps, car la commande PFADD ne met pas à jour le registre dans la plupart des cas. Par conséquent, l’effet de centaines de requêtes par seconde peut être obtenu.

Lors de l'utilisation de la commande PFCOUNT pour traiter plusieurs clés, HyperLogLog sera fusionné. Plus important encore, la cardinalité calculée de l'union ne peut pas être mise en cache. Lors de l'utilisation de plusieurs clés, l'exécution de PFCOUNT peut prendre un certain temps (généralement de l'ordre de quelques millisecondes), une utilisation excessive n'est donc pas recommandée.

Il est à noter que la sémantique d'exécution mono-clé et multi-clé de cette commande est différente et a des performances différentes. L’utilisation excessive de la sémantique d’exécution multi-clés n’est pas recommandée.

3.3 PFMERGE

Première version disponible : 2.8.9. Complexité temporelle : O(N), N est le nombre d'HyperLogLogs à fusionner.

Plusieurs HyperLogLogs peuvent être fusionnés en un seul HyperLogLog via la commande PFMERGE. L'estimation de cardinalité de l'HyperLogLog fusionné est calculée en prenant l'union de tous les HyperLogLogs donnés. Le résultat calculé est enregistré sur la clé spécifiée.

Format de grammaire :

PFMERGE destkey sourcekey [sourcekey ...]

Valeur de retour :

Retour OK.

Exemple :

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

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!