Redis
 sql >> Base de données >  >> NoSQL >> Redis

Introduction aux structures de données Redis :Bitmaps

Les bitmaps (également appelés tableaux de bits, vecteurs de bits, etc.) sont la structure de données qui apparaît immédiatement dans votre tête lorsque vous avez besoin de mapper des informations booléennes pour un domaine énorme dans un compact représentation. C'est une structure de données très populaire chaque fois que l'espace mémoire est limité :noyaux de système d'exploitation (pages mémoire, inodes, etc.), imagerie numérique, etc.

Redis, étant un serveur de structure de données en mémoire, prend en charge les opérations de manipulation de bits. Cependant, il n'y a pas de structure de données spéciale pour les Bitmaps dans Redis. Au lieu de cela, les opérations au niveau du bit sont prises en charge sur la structure Redis de base :les chaînes. Désormais, la longueur maximale des chaînes Redis est de 512 Mo. Ainsi, le plus grand domaine que Redis peut mapper en tant que Bitmap est 2 (512 Mo =2 octets =2 bits).

Les opérations liées aux bits dans Redis sont de deux types :temps constant (O(1)) par ex. les opérations pour obtenir/définir un bit particulier et les opérations O(N) qui opèrent essentiellement sur un groupe de bits. N dans ces cas est la longueur de bits sur laquelle l'opération devra travailler. Regardons quelques exemples.

Commandes

# SETBIT key offset value: Store bit value 'value' at offset 'offset' for 'key'. O(1)
# Returns the original bit value stored at that offset.
127.0.0.1:6379> setbit k 10 1
(integer) 0
# GETBIT key offset: Fetch value of 'offset' in 'key'. O(1)
127.0.0.1:6379> getbit k 10
(integer) 1
127.0.0.1:6379> getbit k 11
(integer) 0
127.0.0.1:6379> getbit k 0
(integer) 0
127.0.0.1:6379> setbit k 9 1
(integer) 0
127.0.0.1:6379> setbit k 8 1
(integer) 0
# And since it is still a generic String, here's a get.
127.0.0.1:6379> get k
"\x00\xe0"
# "\x00\xe0" -> "0000 0000 111"
# BITCOUNT key [start end]: Number of set bits in the range. O(N)
# IMPORTANT: start & end are bytes not bits
127.0.0.1:6379> bitcount k
(integer) 3
127.0.0.1:6379> set m "meow"
OK
# meow -> 01101101 01100101 01101111 01110111 
127.0.0.1:6379> bitcount m
(integer) 21
# BITPOS key bit [start] [end]: 1st position of 1 or 0 in the key in range. O(N)
127.0.0.1:6379> SET mykey "\xff\xf0\x00"
OK
127.0.0.1:6379> BITPOS mykey 0
(integer) 12

Outre les opérateurs qui travaillent sur la clé elle-même, le BITOP L'opérateur est utilisé pour les opérations logiques au niveau du bit entre plusieurs clés.

# BITOP operation destkey key [key ...]. O(N)
# operation can be  AND, OR, XOR and NOT
127.0.0.1:6379> set a "\xff\xff"
OK
127.0.0.1:6379> bitop not nota a
(integer) 2
127.0.0.1:6379> get nota
"\x00\x00"
127.0.0.1:6379> set b "\x0f\x0f"
OK
127.0.0.1:6379> set c "\xf0\xf0"
OK
127.0.0.1:6379> BITOP OR orbc b c
(integer) 2
127.0.0.1:6379> get orbc
"\xff\xff"
127.0.0.1:6379> BITOP AND andbc b c
(integer) 2
127.0.0.1:6379> get andbc
"\x00\x00"
127.0.0.1:6379> BITOP XOR xorbc b c
(integer) 2
127.0.0.1:6379> get xorbc
"\xff\xff"

Internes

Étant donné que les opérations bitmap n'ont pas de structure de données propre, il n'y a pas de structure de données spéciale à décrire. Les chaînes Redis elles-mêmes sont implémentées en tant que chaîne binaire sécurisée. La structure de données de la chaîne Redis est appelée en interne Simple Dynamic String (SDS). Il s'agit essentiellement d'un char [] natif avec quelques informations supplémentaires sur la comptabilité. Les détails de mise en œuvre peuvent être trouvés ici.

L'implémentation des fonctions bitmap se trouve dans le fichier bitops.c .

P.S. :étant donné l'importance des algorithmes de manipulation de bits pour les fonctionnalités critiques du système d'exploitation et des graphiques, la plupart des architectures fournissent des instructions spéciales pour de telles opérations. Un bon endroit pour lire sur divers algorithmes arithmétiques informatiques intéressants est le classique intemporel Hacker's Delight.

Applications

Ce blog GetSpool populaire est un excellent exemple d'utilisation du bitmap pour l'analyse en temps réel sur un grand ensemble de données. C'est également un exemple du cas d'utilisation classique d'un bitmap :pour stocker des informations booléennes d'un domaine extrêmement volumineux dans un espace (relativement) réduit tout en conservant des performances décentes.

La taille est généralement un problème pour les bitmaps très volumineux, car les opérations les plus utiles sur celui-ci sont O(N). Afin d'éviter de travailler avec des clés énormes, la documentation Redis recommande de diviser les clés énormes en plusieurs clés plus petites. Les performances de BITCOUNT restent acceptables jusqu'à ce que la clé devienne importante. À ce stade, la recommandation consiste à diviser les clés ou à utiliser les arguments de plage pour interroger de manière incrémentielle. La recommandation pour gérer les opérations BITOP lentes est de l'exécuter sur des esclaves. Ainsi, en général, il est logique de gérer des clés de taille modérée et de planifier une croissance potentielle future en divisant les clés en plusieurs clés.

 Ensembles Redis et Bitmap Redis

La nature des fonctionnalités fournies par les ensembles Redis et les opérations bitmap est similaire. Il est donc souvent difficile de savoir laquelle des deux approches est la meilleure. Eh bien, cela dépend vraiment de la nature exacte du cas d'utilisation. De toute évidence, cette discussion n'est valable que pour le type d'opérations que les ensembles et le bitmap peuvent réaliser.

Les ensembles Redis sont en général efficaces et bien évolutifs et devraient être la structure de données de choix jusqu'à ce que sa taille devienne intenable. Les ensembles Redis sont également plus faciles à gérer, programmer et déboguer fonctionneraient bien pour la plupart des applications. La facilité d'utilisation des Sets ne doit pas être sous-estimée :le code qui manipule les bitmaps est généralement difficile à lire, à comprendre, à déboguer et à maintenir. Même lorsque le domaine est très grand, les ensembles peuvent toujours être appropriés. Par ex. Si une application est destinée à suivre les visites quotidiennes sur un site de commerce électronique populaire, les résultats peuvent toujours s'intégrer parfaitement dans un ensemble, car généralement seulement 5 à 10 % de l'ensemble de la base d'utilisateurs visiteront le site quotidiennement. Cela change évidemment pour un site où 60% de l'ensemble de la base d'utilisateurs devrait se connecter quotidiennement. Ensuite, les bitmaps deviennent plus pertinents compte tenu de la taille et des performances des opérations logiques au niveau des bits sur un grand nombre de clés. Les ensembles Redis ont également l'avantage de ne pas avoir à mapper les identifiants sur les décalages de bits. De même, si vos valeurs proviennent d'un domaine supérieur à 2, les ensembles Redis sont plus faciles à utiliser que de trouver des mécanismes pour diviser le domaine pour le bitmap.

Analytique pour un MOOC

Voici un exemple concocté (mais assez réel !) pour un endroit où l'on pourrait appliquer des opérations bitmap Redis. Supposons que vous gérez un MOOC en ligne très populaire auquel des centaines de milliers d'étudiants se sont inscrits. L'équipe académique qui anime le cours veut un tableau de bord où ils peuvent voir l'état en temps réel des progrès des étudiants ainsi que le contexte général des étudiants inscrits. Vous décidez de l'implémenter via des opérations bitmap Redis. Voici une approche étape par étape.

  1. Créez un plan pour mapper entre l'ID de l'étudiant et le décalage bitmap. Cela pourrait être aussi simple que l'ID étant le décalage dans le bitmap.
  2. Créez et remplissez divers bitmaps liés à la démographie une fois le cours commencé. Par ex. étudiants inscrits dans d'autres MOOC de la même université, niveau d'études, sexe, etc.
  3. Au fur et à mesure que le cours progresse, vous pouvez créer de nouveaux bitmaps pour enregistrer la progression du cours. Par ex. les étudiants qui ont terminé de regarder tous les cours de la semaine 1, les étudiants qui ont terminé tous les devoirs de la semaine 1. etc.
  4. Désormais, créer des analyses en temps réel basées sur ces clés serait un exercice très simple et peut être effectué sur une interface utilisateur par glisser-déposer. Par exemple
  • Un professeur qui souhaite voir combien d'étudiants ont regardé les cours de la semaine 1 (A) mais n'ont pas terminé le devoir de la semaine 1 (B) :Opérateur :BITOP. Opération :A ET (PAS B).
  • Étudiant ayant terminé tous les devoirs de la semaine 1 (A), de la semaine 2 (B), de la semaine 3 (C) et de la semaine 4 (D) :Opérateur :BITOP. Opération A ET B ET C ET D. Dites, ce sont les gens qui ont réussi le cours.
  • Tous les étudiants de sexe masculin (M) qui ont réussi le cours (tel que calculé ci-dessus, disons, P) :Opérateur :BITOP. Opération :M ET P.
  • Nombre d'étudiants ayant réussi le cours :BITCOUNT P.

De même, n'importe quel nombre de cohortes intéressantes peut être configuré en tant que bitmaps et de telles permutations s'exécutent dessus.

Note de bas de page

Autres articles de notre série sur les structures de données Redis :

  • Ensembles
  • Hachages
  • Ensembles triés