Explication détaillée de la structure des données dans Redis

Dans le développement réel, Redis sera utilisé fréquemment, alors comment choisir correctement le type de données lors de l'utilisation ? Quels types de données conviennent à quels scénarios. Et lors des entretiens, les enquêteurs posent souvent des questions sur la structure des données Redis :

• Pourquoi Redis est-il rapide ?
• Pourquoi l'opération de requête ralentit-elle ?
• Processus de rehachage Redis Hash
• Pourquoi utiliser la table de hachage comme index Redis

Quand nous avons analysé et compris la structure des données Redis, ce qui peut nous aider à choisir correctement le type de données à utiliser et à améliorer les performances du système lors de l'utilisation de Redis. [Recommandations associées : Tutoriel vidéo Redis]

RedisLa structure de données sous-jacente

Redis est une mémoire La base de données clé-valeur key-value et les données de paire clé-valeur sont stockées dans la mémoire , donc Redis les opérations de données basées sur la mémoire sont très efficaces et rapides

parmi elles, Key est le type String. Les types Redis pris en charge par value incluent String, List, Hash, Set, Sorted Set, BitMap, etc. Redis La raison pour laquelle il peut être largement appliqué à de nombreux scénarios commerciaux repose sur ses divers types value.

Et le type de données de Redis Value est basé sur le système d'objets personnalisés Redis implémenté pour redisObject,

typedef struct redisObject{
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针
    void *ptr;
    ….. 
}

redisObject De plus l'enregistrement des données réelles nécessite également de l'espace mémoire supplémentaire pour enregistrer les informations de métadonnées telles que la longueur des données et l'utilisation de l'espace, qui contiennent 8 octets de métadonnées et un pointeur de 8 octets qui pointe vers l'emplacement des données réelles du type de données spécifique :

Parmi eux, le pointeur pointe vers l'emplacement où les données sont stockées en fonction de la structure de données sous-jacente de Redis. La structure de Redis est : SDS , implémentée par des listes doublement chaînées, des listes ignorées, des tables de hachage, des listes compressées et des ensembles d'entiers.

Alors, comment la structure de données sous-jacente de Redis est-elle implémentée ?

Implémentation de la structure de données sous-jacente de Redis

Examinons d'abord le Redis relativement simple SDS, la liste doublement chaînée et la collection d'entiers .

SDS, liste doublement chaînée et ensemble d'entiers

SDS, utilisez le champ len pour enregistrer le nombre d'octets utilisés, ce qui le rendra compliqué d'obtenir la longueur de la chaîne. La vitesse est réduite à O(1), et SDS est libère paresseusement de l'espace Si vous free libérez de l'espace, le système enregistrera les données et l'utilisera. directement la prochaine fois que vous voudrez l'utiliser. Pas besoin de postuler pour un nouvel espace.

Collection d'entiers, allouez un espace avec des adresses continues dans la mémoire, et les éléments de données seront stockés les uns à côté des autres, sans surcharge d'espace causé par des pointeurs supplémentaires. Ses caractéristiques sont une mémoire compacte pour économiser de l'espace mémoire, la complexité des requêtes de O(1) et une efficacité élevée, ainsi que d'autres complexités opérationnelles de O(N) ; >Double liste chaînée , il peut s'agir d'un espace non contigu et non séquentiel dans la mémoire, et la séquence entre les éléments est connectée en série via la surcharge de pointeur supplémentaire du pointeur front-end/back-end.

Il se caractérise par une grande efficacité de la complexité des données d'insertion/mise à jour de section de O(1) et de la complexité des requêtes de O(N)

Table de hachage

 ;

Une table de hachage est en fait similaire à un tableau. Chaque élément du tableau est appelé un compartiment de hachage. Chaque compartiment de hachage stocke les données de la paire clé-valeur, et les éléments du compartiment de hachage utilisent la structure Hash.

dictEntry
Par conséquent, l'élément du compartiment de hachage n'enregistre pas la paire clé-valeur elle-même, mais un pointeur vers la valeur spécifique, Par conséquent, il y aura surcharge d'espace supplémentaire lors de l'enregistrement de chaque paire clé-valeur, qui augmentera d'au moins 24 octets , en particulier la paire clé-valeur où

est

, chaque paire clé-valeur nécessitera 24 octets supplémentaires. .espace d'octets. Lorsque les données enregistrées sont petites et que la surcharge supplémentaire est supérieure aux données, envisagez de modifier la structure des données afin d'économiser de l'espace.

Jetons un coup d'œil à l'image complète de la table de hachage globale :

Bien que le fonctionnement de la table de hachage soit très rapide, Redislorsque les données deviennent plus volumineuses, a Risques potentiels : Problèmes de collision avec les tables de hachage et rehashproblèmes de surcharge, Cela peut-il expliquer pourquoi les opérations des tables de hachage sont plus lentes ?

Lors de l'écriture de plus de données dans la table de hachage, les conflits de hachage sont un problème inévitable. La façon dont Redis résout les conflits de hachage est le hachage en chaîne, plusieurs éléments dans le même compartiment de hachage sont stockés. dans une liste chaînée, et ils sont connectés tour à tour par des pointeurs, comme le montre la figure :

Quand il y a de plus en plus de conflits de hachage, cela rendra certaines chaînes de conflits de hachage trop longues, ce qui entraînera une recherche longue et fastidieuse des éléments de cette chaîne et une efficacité réduite.

Afin de résoudre le problème des chaînes trop longues causées par des conflits de hachage, effectuez l'rehashopération pour augmenter le nombre de compartiments de hachage existants et disperser le nombre de compartiments de hachage uniques. éléments de seau. Alors, comment se déroule le processus rehash ?

Rehash

Afin de rendre l'opération rehash plus efficace, deux tables de hachage globales sont utilisées : la table de hachage 1 et la table de hachage 2, comme suit :

• Allouer un espace plus grand à la table de hachage 2,
• Remapper et copier les données de la table de hachage 1 vers la table de hachage 2
• Libérer l'espace de la table de hachage ; 1

Cependant, en raison de la grande taille des données des tables 1 et 2 lors du remappage et de la copie, si toutes les données de la table de hachage 1 sont migrées en même temps, cela entraînera Redis Le fil est bloqué et ne peut pas répondre à d'autres demandes.

Afin d'éviter ce problème et de garantir que les Redi puissent traiter normalement les demandes des clients, Redis a adopté le progressif rehash.

Chaque fois qu'une demande est traitée, toutes les entrées à la position d'index sont copiées de la table de hachage 1 vers la table de hachage 2, et le coût d'un grand nombre de copies à la fois est réparti sur le processus de traitement de plusieurs requêtes, évitant les opérations fastidieuses et garantissant un accès rapide aux données.

Après avoir compris les points de connaissance pertinents de la table de hachage Hash, jetez un œil à la liste de compression inhabituelle et sautez la table.

Liste compressée et liste à sauter

Liste compressée, basée sur le tableau, la liste compressée a trois champs dans l'en-tête : zlbytes, zltail et zllen, représente respectivement la longueur de la liste, le décalage de la fin de la liste et le nombre d'entrées dans la liste ; la liste compressée a également un zlend en fin de tableau, indiquant la fin de la liste.

Avantages : La mémoire est compacte et économise de l'espace mémoire Un espace avec des adresses consécutives est alloué dans la mémoire, et les éléments de données seront stockés. l'un à côté de l'autre sans avoir besoin de pointeurs supplémentaires. Pour réduire la surcharge d'espace ; la recherche et la localisation du premier élément et du dernier élément peuvent être localisées directement sur la longueur des trois champs d'en-tête, et la complexité est O(1).

Liste de raccourcis, basée sur la liste chaînée, un index multi-niveaux est ajouté pour obtenir un positionnement rapide des données grâce à plusieurs sauts dans la position de l'index, comme indiqué dans ce qui suit figure :

Par exemple, requête 33

Caractéristiques : Lorsque la quantité de données est importante, la complexité de recherche de la table de saut est O(logN) .

Pour résumer, nous pouvons connaître la complexité temporelle de la structure de données sous-jacente :

数据结构类型	时间复杂度
哈希表	O(1)
整数数组	O(N)
双向链表	O(N)
压缩列表	O(N)
跳表	O(logN)

Le type de système d'objets personnalisé de

Redis est le type de données de Redis de Value. Le type de données de Redis est implémenté en fonction de la structure de données sous-jacente.

Type de données Redis

String, List, Hash, Sorted Set, Set sont des types relativement courants, qui sont liés au structure de données sous-jacente La relation correspondante est la suivante :

数据类型	数据结构
String	SDS(简单动态字符串)
List	双向链表 压缩列表
Hash	压缩列表 哈希表
Sorted Set	压缩列表 跳表
Set	哈希表 整数数组

Les caractéristiques correspondantes du type de données sont similaires à la structure de données sous-jacente de son implémentation, et les propriétés sont les mêmes, et

String est implémenté sur la base de SDS, adapté aux simples key-value stockage et setnx key value mise en œuvre de verrous distribués, de compteurs (atomicité), d'identifiants distribués globalement uniques.

List est trié selon l'ordre dans lequel les éléments entrent List , en suivant la règle FIFO (premier entré, premier sorti), et est généralement utilisé dans le tri des statistiques et des files d'attente de messages simples.

Hash est le mappage entre la chaîne key et la chaîne value Il est très approprié pour représenter les informations d'un objet. La complexité de l'ajout et de la suppression de fonctionnalités est O(1).

Set est une collection non ordonnée d'éléments de type String. Les membres de la collection sont uniques, ce qui signifie que les données en double ne peuvent pas apparaître dans la collection. Il est implémenté sur la base d'une table de hachage, donc la complexité de l'ajout, de la suppression et de la recherche est O(1).

Sorted Set est une mise à niveau du type Set La différence est que chaque élément est associé à un score de type double. En triant le score, une requête par plage est possible.

Alors jetons un coup d'œil à ces types de données, Redis Geo, HyperLogLog, BitMap ?

Redis Geo, considère la Terre comme une sphère approximative et convertit la longitude et la latitude bidimensionnelles en chaînes basées sur GeoHash pour implémenter la division de localisation et la requête de distance spécifiée. Les fonctionnalités sont généralement utilisées dans les applications liées à la localisation.

HyperLogLog est une structure de données probabiliste qui utilise des algorithmes probabilistes pour compter la cardinalité approximative d'un ensemble, avec un taux d'erreur d'environ 0,81 %. Lorsque le nombre d’éléments définis est très grand, l’espace requis pour calculer la cardinalité est toujours fixe et très petit, ce qui le rend adapté aux statistiques UV.

BitMap utilise un bit pour mapper l'état d'un élément. Il n'y a que deux états : 0 et 1, qui sont des états binaires très typiques et sont implémentés en utilisant le type String comme structure de données sous-jacente. type de données pour compter les états binaires, qui présente l'avantage d'économiser beaucoup d'espace mémoire, mais peut être utilisé dans des scénarios de statistiques binaires.

Après avoir compris les connaissances ci-dessus, discutons des stratégies utilisées pour sélectionner le type de données Redis dans le scénario d'application correspondant ?

Choisissez la Redisstratégie de type de données appropriée

Dans les applications de développement réelles, Redis peut être appliqué à de nombreux scénarios commerciaux, mais comment choisir le stockage de type de données ? Étoffe de laine?

La base principale est la complexité temps/espace. Dans le développement réel, les points suivants peuvent être pris en compte :

• La quantité de données, la taille des données elles-mêmes
Type de collection Mode statistique
• Prend en charge les requêtes/requêtes de plage à point unique
• Scénarios d'utilisation spéciaux

Quantité de données, taille des données elles-mêmes

Lorsque la quantité de données est relativement importante et les données elles-mêmes sont relativement petites, l'utilisation de

String augmentera considérablement l'utilisation d'espace supplémentaire, car l'utilisation d'une table de hachage pour enregistrer paires clé-valeur et l'utilisation d'une structure pour enregistrer entraîneront la surcharge liée à l'enregistrement de trois pointeurs supplémentaires de dictEntry lors de l'enregistrement de chaque paire clé-valeur, les données elles-mêmes seront plus petites que la surcharge d'espace supplémentaire, et finalement conduire à ce que la taille des données de l'espace de stockage soit beaucoup plus grande que la taille de stockage des données d'origine. dictEntry

peut être implémenté en utilisant un

tableau entier et une liste compressée, car tableau entierList et HashListe compresséeSorted Set alloue un espace avec adresses contiguës dans la mémoire, puis place les éléments de la collection les uns après les autres dans cet espace. Il est très compact et ne nécessite pas de pointeurs supplémentaires pour concaténer les éléments, ce qui évite la surcharge d'espace causée par des pointeurs supplémentaires. De plus, lors de l'utilisation du type collection, une clé correspond aux données d'une collection, et beaucoup plus de données peuvent être enregistrées, mais un seul est utilisé, ce qui économise de la mémoire. Mode statistique de type ensembledictEntry

Les modes statistiques de type ensemble courants incluent :

• Statistiques d'agrégation (statistiques d'intersection, de différence et d'union) : lorsque vous effectuez des calculs d'agrégation sur plusieurs ensembles, vous pouvez choisir Set ;
• statistiques de tri (exige que le type d'ensemble puisse conserver les Ordre des éléments) : Redis et List dans Sorted Set sont des ensembles ordonnés List est trié selon l'ordre dans lequel les éléments entrent List peuvent être triés en fonction du poids des éléments. ; Sorted Set
Statistiques d'état binaire (il n'y a que deux valeurs​​d'éléments d'ensemble : 0 et 1) :
• lui-même est un type de données d'état binaire statistique implémenté en utilisant le type Bitmap comme sous-jacent. structure de données. Bitmap utilise BITOP Utilisez BITCOUNT pour compter le nombre de 1 après les opérations ET, OU et XOR au niveau du bit. String
Statistiques de cardinalité (comptage du nombre d'éléments uniques dans un ensemble) :
• est un type d'ensemble de données utilisé pour compter la cardinalité. Les résultats statistiques ont une certaine erreur et le taux d'erreur standard est de 0,81 %. Si vous avez besoin de résultats statistiques précis, utilisez le type Set ou Hash. Type HyperLogLog

, adapté aux opérations d'agrégation de collecte de statistiques d'utilisateurs/amis/suivi/fans/personnes intéressées, telles que Set

Comptez le nombre de nouveaux utilisateurs de l'application mobile chaque jour
• Amis communs de deux utilisateurs

où Redis et List sont des ensembles ordonnés, utilisez la réponse définit les exigences de tri des éléments, telles que Sorted Set

Liste des derniers commentaires
• Liste de classement

Statistiques d'état binaire, adaptées à de grandes quantités de données, et peut être utilisé Statistiques représentées par un statut binaire, telles que : Bitmap

Connexion et pointage, nombre d'enregistrements d'utilisateurs ce jour-là
• Utilisateur actif hebdomadaire
• Statut en ligne de l'utilisateur

est un type de collecte de données utilisé pour les statistiques de cardinalité. Il compte le nombre d'éléments uniques dans une collection. Par exemple, HyperLogLog

<.> compte l'UV d'une page Web. Un utilisateur compte plusieurs fois par jour. L'accès ne peut être compté qu'une seule fois

prend en charge la requête à point unique/la requête par plage

.

dans

et Redis sont ordonnés pour prendre en charge la requête de plage, mais List ne prend pas en charge la requête de plageSorted SetHash

Scénarios d'utilisation spéciaux

File d'attente des messages

, utilisez comme file d'attente des messages. La mise en œuvre nécessite les exigences de base des messages : préservation de l'ordre des messages Redis, traitement des messages en double et assurer la fiabilité des messages Les solutions sont les suivantes :

Solution de file d'attente de messages basée sur des listes

• Solution de file d'attente de messages basée sur des flux
• .

	基于List	基于Strems
消息保序	使用LPUSH/RPOP	使用XADD/XREAD
阻塞读取	使用BRPOP	使用XREAD block
重复消息处理	生产者自行实现全局唯一ID	Streams自动生成全局唯一ID
消息可靠性	使用BRPOPLPUSH	使用PENDING List自动留存消息
适用场景	消息总量小	消息总量大，需要消费组形式读取数据

Service LBS basé sur la localisation

, utilisant l'implémentation de types de données spécifiques, Redis peut enregistrer des informations de localisation géographique sous forme de longitude et de latitude, et est largement utilisé dans les services LBS . Par exemple : comment un logiciel d'appel de taxi fournit des services en fonction de l'emplacement. GEOGEO

Résumé

est si rapide en raison de ses opérations de données basées sur la mémoire et de l'utilisation de

tables de hachage comme index, ce qui est très efficace. Il est rapide et grâce à la diversification de ses données sous-jacentes, il peut être appliqué à de nombreux scénarios. Choisir le type de données approprié dans différents scénarios peut améliorer les performances de ses requêtes. RedisHashPour plus de connaissances sur la programmation, veuillez visiter :

Vidéo de programmation

 ! !

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!