Bits and Bats – Opérations au niveau du bit sur les clés Redis

Bits and Bats – Opérations au niveau du bit sur les clés Redis

Dans cet article, vous allez apprendre à effectuer des opérations au niveau du bit sur les clés Redis, ainsi qu’à définir, obtenir et comparer des valeurs binaires. Pour commencer, réfléchissons à la manière dont le “retournement de bits” peut être un moyen utile de stocker des informations en général, puis à la manière dont nous pouvons exécuter une opération binaire avec Redis.

Prenons l’exemple suivant : il y a 30 équipes de la Ligue majeure de baseball et chaque équipe joue 162 matchs par an. Il y a 2430 matchs au total joués chaque année. Ces jeux se jouent sur environ six mois. Nous savons qu’un mois ne compte jamais plus de 31 jours, nous pouvons donc stocker le calendrier de jeu d’une seule équipe sur un mois en utilisant 31 bits d’un nombre 32 bits.

Comme vous le savez déjà, un (1) octet correspond à 8 bits et les bits sont suivis «de droite à gauche» en nombres binaires (base 2). Le bit zéro (0) est le plus à droite et le plus petit. Le plus grand nombre que vous pouvez représenter avec 8 bits est 256 :

Dans les exemples ci-dessous, nous travaillerons avec des nombres de 32 bits (4 octets), avec la 31e position de bit (la plus grande possible dans un mois donné) adressée à 2 ^ 30.

Disons que les Yankees de New York jouent du 1er, du 3 au 10, du 13 au 28 et au 31. En bits, en commençant le plus à droite, où le bit zéro représente le premier jour, cela ressemble à :

Cela montre que nous aurons besoin de 10 octets pour stocker le calendrier mensuel d’une équipe MLB. Ce qui signifie que nous pouvons stocker les horaires de chaque équipe dans 10 * 30 octets (octets * nombre d’équipes), ce qui n’est pas beaucoup d’octets, et en plus de cela, nous pouvons prouver que c’est l’espace maximum que nous allons déjà besoin, à moins que les règles régissant le baseball ne changent.

Si vous vouliez savoir si l’équipe jouait le 13, vous auriez besoin d’obtenir un masque de bits pour le 13e bit (en utilisant l’opérateur de décalage à gauche <<):

1 << 12 // 4096

En utilisant un langage comme JavaScript, nous pouvons démontrer plus clairement le décalage à gauche et le remplissage implicite de 0 sur un nombre de 31 bits :

Ou visualisé comme la comparaison de deux chaînes de zéros et de uns :

De même, nous pouvons définir le 13ème bit à l’aide de l’opérateur OR(|) :

1342174205 | 4096

Ou plus explicitement :

Soigné! Utilisons maintenant Redis pour stocker des quantités beaucoup plus importantes de données binaires.

Comment Redis active-t-il les opérations au niveau du bit ?

Redis est un magasin de structure de données construit sur le paradigme clé/valeur, et l’opération la plus basique consiste à stocker une chaîne dans une clé :

La famille de commandes Redis BITOP vous permet d’effectuer des opérations de bit sur des clés de chaîne. En utilisant les commandes bien nommées SETBIT et GETBIT, vous pouvez… définir et obtenir des bits sur une clé. Vous pouvez définir des clés de comparaison à l’aide des opérateurs binaires AND, OR et XOR, comme nous l’avons fait avec le programme MLB ci-dessus. Par exemple, activons le test de la clé du 3ème bit :

C’était facile. Il devrait être clair comment accomplir le test ci-dessus en définissant des bits sur certains jours d’un horaire d’équipe ou en créant des masques.

Utilisons des bitmaps pour résoudre le problème de stockage du record de victoires/défaites des Yankees. Nous savons qu’ils joueront 162 matchs en un an. Si 1 est un gain et 0 est une perte, nous pouvons créer une clé Redis ‘yankees_record’ et définir tous les gains comme ceci :

En appliquant des masques de bits mappant une plage de bits à d’autres valeurs binaires, vous pouvez effectuer des comparaisons analytiques très rapides et économes en mémoire. Dans la section suivante, nous apprendrons quelques exemples typiques d’utilisation de cette technique.

Toute clé d’une base de données Redis peut stocker (2^32 – 1) bits, soit un peu moins de 512 Mio (pour l’instant). Cela signifie qu’il existe environ 4,29 milliards de colonnes, ou décalages, qui peuvent être définis par clé. Il s’agit d’un grand nombre de bits référencés dans une seule clé. Nous pouvons définir des bits le long de ces plages pour décrire les caractéristiques d’un élément que nous aimerions suivre, comme le nombre d’utilisateurs qui ont consulté un article donné.

Supposons que nous servons de nombreux articles différents et que chaque article se voit attribuer un identifiant unique. Supposons également que nous ayons 100 000 membres actifs sur notre site Web et que chaque utilisateur possède également un identifiant unique, un nombre compris entre 1 et 100 000. Nous pouvons utiliser des opérations sur les bits pour suivre l’activité de visualisation en créant une clé unique pour cet article et en définissant des bits correspondant à l’ID de l’utilisateur qui consulte l’article donné. L’exemple suivant montre que l’article 808 a été consulté par les utilisateurs 4, 6, 9-11, etc. :

article:808:01-03-2018 : 00010100111010001001111...

Cette clé représente l’article 808 à une date spécifique, stockant efficacement les ID utilisateur uniques des téléspectateurs ce jour-là en inversant un peu le décalage correspondant à l’ID attribué à l’utilisateur. Chaque fois qu’un utilisateur consulte un article, nous utilisons le SETBIT commande pour définir un bit au décalage fourni par l’ID de cet utilisateur :

Créons des données pour trois articles :

Ici, nous avons simplement créé trois clés Redis, article (1-3) : aujourd’hui, et avons défini au hasard 100 000 bits sur chaque clé, soit 0 ou 1. En utilisant la technique de stockage de l’activité de l’utilisateur en fonction des décalages d’ID utilisateur, nous avons maintenant des exemples de données. pour une hypothétique journée de trafic contre trois articles.

Pour compter le nombre d’utilisateurs ayant consulté un article, nous pouvons utiliser BITCOUNT :

Cette méthode est simple : le nombre d’utilisateurs qui ont vu l’article est égal au nombre de bits définis sur la clé. Maintenant, comptons le nombre total de vues d’articles :

Une fois que MULTI renvoie un tableau de résultats correspondant aux résultats SETBIT renvoyé de Redis pour chaque opération (un nombre de bits), nous réduisons le nombre à une somme représentant le nombre total de vues de tous nos articles.

Si nous sommes plutôt intéressés par le nombre d’articles que l’utilisateur 123 a consultés aujourd’hui, nous pouvons utiliser GETBIT, qui renvoie simplement la valeur (0 ou 1) à un décalage donné. Le résultat sera compris entre 0 et 3 :

Ce sont des moyens très utiles et directs de glaner des informations à partir de représentations binaires. Allons un peu plus loin et apprenons à filtrer les bits à l’aide de masques de bits et des opérateurs AND, OR et XOR.

Et si nous voulons vérifier si l’utilisateur 123 a lu les deux articles ? En utilisant le BITOP ET, c’est facile à réaliser :

Tout d’abord, nous créons un masque qui isole un utilisateur spécifique stocké à la clé utilisateur123, contenant un seul bit positif au décalage 123 (représentant à nouveau l’ID de l’utilisateur). Les résultats d’une opération AND sur deux représentations binaires ou plus ne sont pas renvoyés sous forme de valeur par Redis, mais plutôt écrits sur une clé spécifiée, qui est donnée dans l’exemple précédent sous la forme “123:sawboth”. Cette clé contient la représentation de bit qui répond à la question de savoir si les deux clés d’article contiennent ou non des représentations de bit qui ont également un bit positif au même décalage que la clé user123.

L’opérateur OU fonctionne bien lorsque vous essayez de trouver le nombre total d’utilisateurs qui ont vu au moins un article :

Ici le au moins un article de pierre bits d’indicateurs de clé à tous les décalages qui ont été définis dans l’un des trois articles. Nous pouvons utiliser ces techniques pour créer un moteur de recommandation simple.

Par exemple, si nous sommes en mesure de déterminer par d’autres moyens que deux articles sont similaires (basés sur des balises, des mots-clés, etc.), nous pouvons trouver des utilisateurs qui ont lu l’un et recommandé l’autre. Pour ce faire, nous utilisons XOR pour trouver tous les utilisateurs qui ont lu le premier article ou le deuxième article, mais pas les deux. Nous divisons ensuite cet ensemble en deux listes : ceux qui ont lu le premier article et ceux qui ont lu le deuxième article et comparons ces listes pour proposer des recommandations :

Bien que ce ne soit pas nécessaire, nous récupérons également un décompte de chaque liste et supprimons les clés de résultat lorsque nous avons terminé.

Pour calculer le nombre total d’octets occupés par une valeur binaire dans Redis, divisez le plus grand décalage par 8. Le stockage des données d’accès pour 1 000 000 d’utilisateurs sur un article nécessite un maximum d’environ 125 Ko, ce qui n’est pas une très grande quantité de mémoire ou de stockage à dépenser. en échange d’un ensemble aussi riche de données d’analyse. Parce que nous pouvons mesurer avec précision l’espace nécessaire, cela nous donne également une certaine confiance lors de la planification des coûts de stockage, de la mise à l’échelle, etc.

A propos de l’auteur

Sandro Pasquali a formé une société technologique nommée Simple en 1997, qui a vendu le premier cadre de développement d’applications basé sur JavaScript au monde et a obtenu plusieurs brevets pour des technologies de déploiement et de publicité qui ont anticipé l’avenir des logiciels basés sur Internet. Il a écrit trois livres sur NodeJS. Il crée des logiciels de classe entreprise pour des clients privés, déployant souvent l’incroyable polyvalence de Redis pour aider à répondre aux exigences complexes de gestion de l’information pour les grands clients.

Development Source

Related Posts

RLEC 4.2.1 apporte des contrôles granulaires à la haute disponibilité et aux performances

RLEC 4.2.1 apporte des contrôles granulaires à la haute disponibilité et aux performances

Comment HolidayMe utilise Redis Enterprise comme base de données principale

Comment HolidayMe utilise Redis Enterprise comme base de données principale

Annonce de RedisGears 1.0 : un moteur sans serveur pour Redis

Annonce de RedisGears 1.0 : un moteur sans serveur pour Redis

Clés Redis dans la RAM |  Redis

Clés Redis dans la RAM | Redis

No Comment

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *