Introduction aux structures de données Redis :hachages

Les hachages Redis sont (assez intuitivement !) Des hachages qui mappent les noms de chaîne aux valeurs de chaîne. Ce sont essentiellement des conteneurs nommés de champs uniques et de leurs valeurs. Ils sont le moyen idéal pour représenter un objet en tant que structure de données Redis. Comme prévu, ils fournissent des opérations de base en temps constant comme obtenir, définir, exister, etc. Un tas d'opérations avancées sont également fournies. La liste complète des commandes de hachage est ici.

Prenons un tour à partir du redis-cli .

# hmset key field value [field value ...] :  Insert elements in a hash. O(N), N is # of field being set
127.0.0.1:6379> hmset std:101 name "John Smith" dob "01-01-2000" gender M active 0 cgpa 2.9
OK

# hgetall key : key all keys and values in the hash. O(N), N is size of hash
127.0.0.1:6379> hgetall std:101
 1) "name"
 2) "John Smith"
 3) "dob"
 4) "01-01-2000"
 5) "gender"
 6) "M"
 7) "active"
 8) "0"
 9) "cgpa"
10) "2.9"
127.0.0.1:6379> hmset std:102 name "Jane" name "Ann"
OK
# If duplicates are found, only the last set is valid
127.0.0.1:6379> hgetall std:102
1) "name"
2) "Ann"

# hexists key field: does field exist in the hash with key. O(1)
127.0.0.1:6379> hexists std:102 cgpa
(integer) 0

# hincrby key field increment: Increment the integer field by increment. O(1)
127.0.0.1:6379> hincrby std:101 active 1
(integer) 1

# hget key field : the value for field in the hash stored at key. O(1)
127.0.0.1:6379> hget std:101 active
1) "1"
# If field doesn't exist, hincrby sets it to 0 and then applies increment
127.0.0.1:6379> hincrby std:102 active 2
(integer) 2

# hmget key field [field ...]: the values of the fields requested for the hash with key. O(N), N is # of keys requested
127.0.0.1:6379> hmget std:102 active
1) "2"

# hincrbyfloat key field increment: Increment the float value in field by increment. O(1) 
127.0.0.1:6379> HINCRBYFLOAT std:101 cgpa 1.0
"3.9"

# HSETNX key field value: set field to value if not alread set. O(1)
127.0.0.1:6379> hsetnx std:102 cgpa 4.0
(integer) 1
127.0.0.1:6379> hget std:102 cgpa
"4.0"

# hlen key: number of fields in the hash. O(1)
127.0.0.1:6379> hlen std:101
(integer) 5

# hkeys key : all fields in the hash. O(N), N is size of hash
127.0.0.1:6379> hkeys std:101
1) "name"
2) "dob"
3) "gender"
4) "active"
5) "cgpa"

Comme nous l'attendons de notre hébergement pour Redis™* en tant que serveur de structure de données, nous constatons que Redis fournit des opérations assez utiles et avancées sur les hachages.

Internes

Comme les ensembles Redis, les hachages Redis sont également implémentés sous forme de dictionnaires. Les dictionnaires dans Redis sont implémentés sous forme de tables de hachage qui utilisent la fonction de hachage MurmurHash2 et se développent via un redimensionnement incrémentiel. Les collisions de hachage sont gérées par chaînage. Plus de détails peuvent être trouvés dans l'implémentation Redis du dictionnaire sur dict.c.
Comme avec les ensembles, une optimisation du stockage est faite pour les hachages plus petits. Cette structure de données est appelée ziplist (les hachages étaient optimisés à l'aide d'une structure de données différente appelée zipmap avant Redis 2.6) dans l'implémentation Redis. Il s'agit essentiellement d'une liste à double liaison spécialement codée qui est optimisée pour économiser de la mémoire. Les données, ainsi que les pointeurs sont stockés en ligne. Ziplist est également utilisé pour optimiser le stockage de petits ensembles et listes triés. Un hachage, lorsqu'il est aplati dans une telle liste, ressemble à [clé1, valeur1, clé2, valeur2, ...]. En quoi est-ce plus efficace que les clés ordinaires ? Les hachages avec peu de clés peuvent être compressés intelligemment dans cette structure de type tableau linéaire (c'est-à-dire la liste zip) tout en garantissant des performances O(1) amorties pour get et set. Évidemment, cela ne peut pas suivre à mesure que les champs de hachage augmentent. Au fur et à mesure que le hachage grandit, il est converti dans la structure de dictionnaire standard pour maintenir les performances O(1) et les économies d'espace sont perdues. Les paramètres de configuration Redis contrôlant cette transformation sont :

• list-max-ziplist-entries par défaut (512) :passe à la représentation standard si le hachage dépasse cette limite.

• list-max-ziplist-value par défaut (64) :passe à la représentation standard si le plus grand élément du hachage dépasse cette limite.

Plus de détails peuvent être compris à partir du code et des commentaires dans l'implémentation trouvée ici. Les économies de mémoire résultant de l'utilisation de cette optimisation spéciale sont importantes. Nous en parlerons plus en détail dans la section suivante.

Optimisation de la mémoire

L'une des recommandations bien connues pour économiser de la mémoire lors de l'utilisation de Redis consiste à utiliser des hachages au lieu de chaînes simples. Il s'agit d'un cas d'utilisation important pour utiliser la puissance des hachages Redis dans des applications du monde réel. De la documentation officielle de Redis sur l'optimisation de la mémoire :

Utilisez des hachages si possible

Les petits hachages sont encodés dans un très petit espace, vous devriez donc essayer de représenter vos données à l'aide de hachages chaque fois que cela est possible. Par exemple, si vous avez des objets représentant des utilisateurs dans une application Web, au lieu d'utiliser différentes clés pour le nom, le prénom, l'e-mail, le mot de passe, utilisez un seul hachage avec tous les champs obligatoires.

Cet article propose ensuite une façon de mapper une gamme d'objets dans un ensemble de hachages pour tirer parti des économies de mémoire. Instagram, dans un article de blog très populaire, décrit l'utilisation d'une technique similaire qui les a aidés à réaliser des ordres de grandeur d'économies potentielles. Voici un autre blog qui tente de mesurer les avantages de l'optimisation.

Applications

• Les hachages Redis sont naturellement adaptés pour stocker des objets :sessions, utilisateurs, visiteurs, etc. Cela en fait l'une des structures de données clés fournies par Redis.
• Dans sa forme optimisée pour la mémoire, c'est un excellent choix pour mettre en cache de grandes quantités de données.

Un magasin d'adresses d'objets

Étant donné que l'optimisation de la mémoire est un cas d'utilisation important pour les hachages, examinons un exemple similaire au déploiement d'Instagram pour montrer comment utiliser les fonctionnalités d'économie de mémoire des hachages Redis. Disons que nous avons un énorme déploiement de stockage adressable par le contenu (CAS) avec des centaines de millions d'objets stockés. L'emplacement de chaque objet est une chaîne de hachage. Nous avons l'intention de développer un système de recherche pour connaître l'emplacement de l'objet en fonction de son ID. La façon typique de le faire dans Redis sera d'utiliser une chaîne.

set object:14590860 "007f80f0a62408..."
set object:11678 "009f80abcd0a60..."
...


Cette approche fonctionne très bien. Cependant, comme le nombre d'objets que nous avons est énorme, nous aurons besoin de beaucoup de mémoire pour Redis. Nous voulons faire mieux. Prenons l'approche de hachage optimisée en mémoire pour ce problème. Nous devrons choisir les bonnes valeurs pour list-max-ziplist-entries et list-max-ziplist-value . La valeur correcte pour list-max-ziplist-value est quelle que soit la longueur maximale de la chaîne de hachage de l'adresse de stockage. La valeur de list-max-ziplist-entries doit être maintenu suffisamment bas et dépendra du nombre total de seaux de hachage que nous souhaitons créer. Il sera mieux compris empiriquement. Par ex. pour 100 millions d'objets, nous pourrions choisir d'utiliser des hachages de 100 000. Les entrées maximales dans ce cas seront 100m / 100k =1000. La logique de l'application pour décider dans quel hachage l'adresse de stockage d'un objet va être :diviser l'ID de l'objet par 100 k et supprimer le reste. Ainsi, l'ID d'objet 14590860 ira dans le hachage (14590860/100k) =145 c'est-à-dire


hset object:145 14590860 "007f80f0a62408..."
hget object:145 14590860
> "007f80f0a62408..."


Cette implémentation sera non seulement beaucoup plus légère en mémoire, mais devrait également fournir une bonne localité de cache.

Voici nos autres articles de la série sur la structure de données Redis.

• Ensembles Redis
• Bitmaps Redis
• Ensembles triés Redis