Quelles sont les structures de données sous-jacentes utilisées pour Redis?

la plupart du temps, vous n'avez pas besoin de comprendre les structures de données sous-jacentes utilisées par Redis. Mais un peu de connaissance vous aide à faire des échanges de mémoire CPU v/s. Il vous permet également de modéliser vos données de manière efficace.

à L'interne, Redis utilise les structures de données suivantes:

1. Chaîne
2. Dictionnaire
3. Liste Doublement Liée
4. Sauter Liste
5. Zip "Liste Des 1519210920"
6. Int Sets
7. Zip Cartes (déconseillée en faveur de zip liste depuis Redis 2.6)

pour trouver le codage utilisé par une clé particulière, utilisez la commande object encoding <key> .

1. Cordes

dans Redis, les cordes sont appelées simple Dynamic Strings, ou SDS . C'est un petit emballage sur un char * qui permet vous pouvez stocker la longueur de la chaîne et le nombre d'octets libres comme préfixe.

parce que la longueur de la chaîne est stockée, strlen est une opération O(1). Aussi, parce que la longueur est connue, les chaînes Redis sont binaires sûres. Il est parfaitement légal pour une chaîne de caractères de contenir le caractère nul .

Les chaînes

sont la structure de données la plus polyvalente disponible dans Redis. Une chaîne est tous de ce qui suit:

1. une chaîne de caractères qui peut stocker du texte. Voir les commandes SET et GET .
2. Un tableau d'octets qui peut stocker des données binaires.
3. Un long qui permet de stocker des nombres. Voir INCRR , DECR , INCRBY et DECRBY commandes.
4. un réseau (de chars , ints , longs ou tout autre type de données) qui permettent un accès aléatoire efficace. Voir les commandes SETRANGE et GETRANGE .
5. A tableau de bits qui vous permet de définir ou d'obtenir des bits individuels. Voir les commandes SETBIT et GETBIT .
6. Un bloc de mémoire que vous pouvez utiliser pour construire d'autres structures de données. Ceci est utilisé en interne pour construire des ziplists et des intsets, qui sont des structures de données compactes et économes en mémoire pour un petit nombre d'éléments. En savoir plus sur ce ci-dessous.

2. Dictionnaire

Redis utilise un Dictionnaire par le texte suivant:

1. pour mapper une clé à sa valeur associée, où la valeur peut être une chaîne, un hachage, un ensemble, un ensemble trié ou une liste.
2. pour cartographier une clé de son horodatage.
3. pour implémenter les types de données Hash, Set et triés.
4. pour associer les commandes Redis aux fonctions qui gèrent ces commandes.
5. pour cartographier une clé Redis à une liste de clients qui sont bloqués sur cette clé. Voir BLPOP .

les dictionnaires Redis sont mis en œuvre à l'aide des Tables de hachage . Au lieu d'expliquer la mise en œuvre, je vais simplement expliquer les choses spécifiques de Redis:

Les dictionnaires

1. utilisent une structure appelée dictType pour étendre le comportement d'une table de hachage. Cette structure a des indicateurs de fonction, et les opérations suivantes sont donc extensibles: a) fonction de hachage, b) comparaison de clés, c) destructeur de clés, et d) destructeur de valeurs.
Les dictionnaires
2. utilisent le murmurhash2 . (Auparavant, ils utilisaient la fonction de hachage djb2 , avec seed=5381, mais ensuite la fonction de hachage a été commuté en murmur2 . Voir cette question pour une explication de l'algorithme de hachage djb2 .)
3. Redis utilise des Différentiels de Hachage, aussi connu comme Incrémentielle Redimensionnement . Le dictionnaire a deux tables de hachage. Chaque fois que le dictionnaire est touché , un le seau est migré de la première (plus petite) table de hash à la seconde. De cette façon, Redis empêche une opération de redimensionnement coûteuse.

la structure de données Set utilise un dictionnaire pour garantir qu'il n'y a pas de doublons. Le Sorted Set utilise un dictionnaire pour mapper un élément à sa partition, c'est pourquoi ZSCORE est une opération O(1).

3. Listes Doublement Liées

le list le type de données est mis en œuvre en utilisant listes doublement liées . L'implémentation de Redis est tout droit sortie du manuel de l'algorithme. Le seul changement est que Redis stocke la longueur dans la structure des données de la liste. Cela garantit que LLEN A O (1) complexité.

4. Skip Lists

Redis utilise Skip Lists comme structure de données sous-jacente pour les ensembles triés. Wikipedia a un bon introduction. L'article de William Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees contient plus de détails.

ensembles triés utilisent à la fois une liste de saut et un dictionnaire. Le dictionnaire stocke la partition de chaque élément.

L'implémentation de la liste de sauts de Redis diffère de l'implémentation standard de la manière suivante:

1. Redis permet de dupliquer les scores. Si deux nœuds ont le même partition, ils sont triés par le ordre lexicographique .
2. chaque noeud a un pointeur arrière au niveau 0. Cela vous permet de parcourir les éléments dans l'ordre inverse de la partition.

5.

une liste Zip est comme une liste doublement liée, sauf qu'elle n'utilise pas de pointeurs et stocke les données en ligne.

chaque noeud dans une liste doublement liée A à 3 pointeurs-un pointeur vers l'avant, un pointeur vers l'arrière et un pointeur pour référencer les données stockées à ce noeud. Les pointeurs nécessitent de la mémoire (8 octets sur un système 64 bits), et donc pour les petites listes, une liste doublement liée est très inefficace.

une liste Zip stocke les éléments séquentiellement dans une chaîne de caractères Redis. Chaque élément a une petite tête qui stocke la longueur et le type de données de l'élément, le décalage de l'élément suivant et le décalage de l'élément précédent. Ces offsets remplacent l'avant et en arrière des pointeurs. Puisque les données sont stockées en ligne, nous n'avons pas besoin d'un pointeur de données.

la liste Zip est utilisée pour stocker des petites listes, des ensembles triés et des hachures. Les ensembles triés sont aplatis dans une liste comme [element1, score1, element2, score2, element3, score3] et stockés dans la liste Zip. Les traits sont aplatis dans une liste comme [key1, value1, key2, value2] etc.

avec des listes Zip vous avez le pouvoir de faire un compromis entre CPU et mémoire. Les listes Zip sont économes en mémoire, mais elles utilisent plus de CPU qu'un lien liste (ou Liste de hachage/liste de sauts). Trouver un élément dans la liste zip est O(n). L'insertion d'un nouvel élément nécessite une réallocation de la mémoire. Pour cette raison, Redis utilise ce codage uniquement pour les petites listes, les hachures et les ensembles triés. Vous pouvez modifier ce comportement en modifiant les valeurs de <datatype>-max-ziplist-entries et <datatype>-max-ziplist-value> dans redis.conf. Voir Redis Optimisation de la Mémoire, la section "encodage de petit agrégat" types de données pour plus d'informations.

le commentaires sur la ziplist.c sont excellents, et vous pouvez comprendre cette structure de données complètement sans avoir à lire le code.

6. Sets Int

les ensembles Int sont un nom fantaisiste pour "tableaux entiers triés".

dans Redis, les ensembles sont généralement implémentés en utilisant des tables de hachage. Pour les petits ensembles, une table de hachage est inefficace mémoire Sage. Lorsque l'ensemble est composé de nombres entiers, un tableau est souvent plus efficace.

un ensemble Int est un tableau trié d'entiers. Pour trouver un élément un algorithme de recherche binaire est utilisé. Cela a une complexité de O (log n). L'ajout de nouveaux entiers à ce tableau peut nécessiter une réallocation de la mémoire, qui peut devenir coûteuse pour de grands tableaux entiers.

comme autre optimisation de la mémoire, les ensembles Int sont disponibles en 3 variantes avec différentes tailles d'entiers: 16 bits, 32 bits et 64 bits. Redis est assez intelligent pour utiliser le variante en fonction de la taille des éléments. Lorsqu'un nouvel élément est ajouté et il dépasse la taille actuelle, Redis migre automatiquement à la taille. Si une chaîne est ajoutée, Redis convertit automatiquement le jeu Int en un jeu régulier basé sur une Table de hachage.

Les ensembles

Int sont un compromis entre CPU et mémoire. Les sets Int sont extrêmement économes en mémoire, et pour les petits sets ils sont plus rapides qu'une table de hachage. Mais après un certain nombre d'éléments, la récupération O (log N) le temps et le coût de la réallocation de mémoire deviennent trop importants. D'après les expériences, le seuil optimal pour passer à une table de hachage régulière était de 512. Cependant, vous pouvez augmenter ce seuil (diminuer n'a pas de sens) en fonction des besoins de votre application. Voir set-max-intset-entries dans redis.conf.

7. Zip Maps

les cartes Zip sont des dictionnaires aplatis et stockés dans une liste. Ils sont très similaires aux listes Zip.

les cartes Zip ont été dépréciées depuis Redis 2.6, et les petits hachages sont stockés dans des listes Zip. Pour en savoir plus sur cet encodage, reportez-vous aux commentaires dans zipmap.c .

Redis stocke les clés pointant vers des valeurs. Les clés peuvent être n'importe quelle valeur binaire jusqu'à une taille raisonnable (l'utilisation de chaînes ASCII courtes est recommandée pour la lisibilité et le débogage). Les valeurs sont l'un des cinq types de données natives Redis.

1.strings-une séquence d'octets binaires sûrs jusqu'à 512 MB

2.hashes-une collection de valeurs clés paires

3.listes-une collection de chaînes de caractères en ordre d'insertion

4.sets-une collection de cordes uniques sans commande

5.ensembles triés-une collection de chaînes uniques ordonnées par notation définie par l'utilisateur

cordes

une chaîne Redis est une séquence d'octets.

les chaînes de caractères dans Redis sont binaires (ce qui signifie qu'elles ont une longueur connue non déterminée par des caractères terminants spéciaux), donc vous peut stocker n'importe quoi jusqu'à 512 mégaoctets en une seule chaîne.

Strings sont le concept cannonique de "key value store". Vous avez une clé pointant vers une valeur, où la clé et la valeur sont des chaînes de texte ou binaires.

pour toutes les opérations possibles sur cordes, voir la http://redis.io/commands/#string

Hashs

un hash Redis est une collection de paires de valeurs clés.

un hash Redis contient de nombreuses paires de valeurs clés, où chaque clé et chaque valeur est une chaîne. Les hachages Redis ne supportent pas les valeurs complexes directement (ce qui signifie que vous ne pouvez pas avoir un champ de hachage ayant une valeur d'une liste ou d'un jeu ou d'un autre hachage), mais vous pouvez utiliser les champs de hachage pour pointer vers d'autres valeurs complexes de haut niveau. La seule opération spéciale que vous pouvez effectuer sur les valeurs de champ de hachage est l'incrément atomique/décrément de contenu numérique.

vous pouvez penser à un Redis hashes en deux ways: comme une représentation directe d'objet et comme un moyen de stocker de nombreuses petites valeurs de façon compacte.

les représentations directes d'objets sont simples à comprendre. Les objets ont un nom (la clé du hachage) et une collection de clés internes avec des valeurs. Voir l'exemple ci-dessous pour un exemple.

stocker de nombreuses petites valeurs à l'aide d'un hachage est une technique intelligente de stockage de données massive Redis. Lorsqu'un hash a un petit nombre de champs (~100), Redis optimise le efficacité de stockage et d'accès de tout le hash. L'optimisation de la petite mémoire de hachage de Redis suscite un comportement intéressant: il est plus efficace d'avoir 100 hachages chacun avec 100 clés et valeurs internes plutôt que d'avoir 10 000 clés de haut niveau pointant vers des valeurs de chaîne. L'utilisation de Redis hashes pour optimiser votre stockage de données de cette façon ne nécessite pas la programmation aérienne supplémentaire pour le suivi où les données se termine, mais si votre stockage de données est principalement basé string, vous pouvez économiser beaucoup de mémoire aérienne en utilisant ce un truc bizarre.

pour toutes les opérations possibles sur les hachures, voir le hash docs

listes

les listes Redis agissent comme des listes liées.

vous pouvez insérer, supprimer ou parcourir des listes à partir de la tête ou de la queue d'une liste.

utilise des listes quand tu as besoin de maintenir les valeurs dans l'ordre où elles ont été insérées. (Redis ne vous donner la possibilité de l'insérer dans n'importe quelle position si vous en avez besoin, mais votre insertion performances se dégradent si vous insérez loin de votre position de départ.)

les listes Redis sont souvent utilisées comme Files d'attente producteur/consommateur. Insérez des articles dans une liste puis pop articles de la liste. Que se passe-t-il si vos consommateurs essaient de sortir d'une liste sans éléments? Vous pouvez demander Redis attendre à un élément d'apparaître et de vous le renvoyer immédiatement lorsqu'il est ajouté. Ceci fait de Redis un file d'attente de messages en temps réel/événement/emploi/tâche/Système de notification.

vous pouvez atomiquement supprimer des éléments à la fin d'une liste, permettant à n'importe quelle liste d'être traitée comme une pile ou une file d'attente.

vous pouvez également maintenir des listes à longueur fixe (collections plafonnées) en ajustant votre liste à une taille spécifique après chaque insertion.

pour toutes les opérations possibles sur Listes, voir les listes docs

Jeux

les sets Redis sont des sets.

un ensemble Redis contient des chaînes Redis uniques non ordonnées où chaque chaîne n'existe qu'une fois par ensemble. Si vous ajoutez le même élément dix fois à un ensemble, il n'apparaîtra qu'une fois. Les ensembles sont grands pour s'assurer que quelque chose existe au moins une fois sans se soucier des éléments dupliqués accumulant et gaspillant de l'espace. Vous pouvez ajouter la même chaîne autant de fois que vous le souhaitez sans avoir à vérifier s'il existe déjà.

Les ensembles

sont rapides pour la vérification de l'adhésion, l'insertion et la suppression des membres dans l'ensemble.

Les ensembles

ont des opérations de jeu efficaces, comme vous pouvez vous y attendre. Vous pouvez prendre l'union, intersection, et la différence de plusieurs ensembles à la fois. Les résultats peuvent être retournés à l'appelant ou stockés dans un nouvel ensemble pour un usage ultérieur.

ensembles ont un accès temps constant pour les vérifications d'adhésion (contrairement liste), et Redis a même le retrait aléatoire de membre et le retour commode ("pop un élément aléatoire de l'ensemble") ou le retour aléatoire de membre sans remplacement ("donnez-moi 30 utilisateurs au hasard-ish unique") ou avec remplacement ("donnez-moi 7 cartes, mais après chaque sélection, mettez la carte en arrière de sorte qu'elle puisse potentiellement être échantillonnée à nouveau").

pour toutes les opérations possibles sur sets, voir le sets docs .

Ensembles Triés

les ensembles triés Redis sont des ensembles avec un ordre défini par l'utilisateur.

pour la simplicité, vous pouvez penser à un ensemble trié comme un arbre binaire avec des éléments uniques. (Redis ensembles classés sont en fait des skip lists .) L'ordre de tri des éléments est définie par chaque élément de la partition.

les ensembles triés sont toujours des ensembles. Les éléments ne peuvent apparaître qu'une fois dans un jeu. Un élément, par unicité, est défini par son contenu de chaîne. L'insertion de l'élément " apple "avec le score de tri 3, puis l'insertion de l'élément" apple "avec le score de tri 500 donne un résultat" apple " avec le score de tri 500 dans votre ensemble trié. Les ensembles ne sont uniques que sur la base de données, et non sur la base de paires (Score, données).

assurez-vous que votre modèle de données repose sur le contenu de la chaîne de caractères et non sur le score de l'élément pour l'unicité. Les Scores peuvent être répétés (ou même zéro), mais, une dernière fois, les éléments de jeu ne peuvent exister qu'une fois par ensemble trié. Par exemple, si vous essayez de stocker l'histoire de chaque connexion utilisateur comme un ensemble trié en faisant le score l'époque de la connexion et la valeur de l'ID utilisateur, vous finirez par stocker seulement la dernière époque de connexion pour tous vos utilisateurs. Votre ensemble atteindrait la taille de votre base de données userbase et non la taille désirée de vos logins userbase*.

Des éléments

sont ajoutés à votre set avec des partitions. Vous pouvez mettre à jour le score de n'importe quel élément à tout moment, il suffit d'ajouter l'élément à nouveau avec une nouvelle partition. Les Scores sont représentés par des doubles à virgule flottante, de sorte que vous pouvez spécifier la granularité des horodateurs de haute précision si nécessaire. Plusieurs éléments peuvent avoir le même score.

vous pouvez récupérer des éléments de différentes façons. Puisque tout est trié, vous pouvez demander des éléments à partir des scores les plus bas. Vous pouvez demander des éléments commençant par les scores les plus élevés ("à l'envers"). Vous pouvez demander des éléments par leur tri score nature ou en ordre inverse.

pour toutes les opérations possibles sur les ensembles triés, voir le ensembles triés docs.