Une brève discussion sur le dictionnaire, l'algorithme de hachage et le principe ReHash dans Redis

Cet article vous fera comprendre le dictionnaire, l'algorithme de hachage et le principe ReHash dans Redis. J'espère qu'il vous sera utile !

Les dictionnaires de Redis sont largement utilisés pour implémenter diverses fonctions de Redis, notamment des bases de données et des clés de hachage.

L'implémentation sous-jacente du dictionnaire est une table de hachage. Chaque dictionnaire a deux tables de hachage, l'une est utilisée normalement et l'autre est utilisée lorsque le rehash est utilisé pour étendre l'espace. [Recommandations associées : Tutoriel vidéo Redis]

Définition de la structure du dictionnaire

typedef struct dict {
	
	// 类型特定函数
	dictType *type;
	
	// 私有数据
	void *privdata;
	
	// 哈希表，两个元素
	dictht ht[2]
	
	// rehash时记录的索引下标，当没有rehash时，值为-1
	int rehashidx;

} dict;

==Lors d'un rehash, les données d'entrée de chaque index migré par rehashidx seront + 1 ;==

Parmi eux, la table de hachage La structure de dicttht est définie comme :

typedef struct dictht {
	
	// 哈希表数组
	dictEntry **table;
	
	// 哈希表大小
	unsigned long size;
	
	// 哈希表大小掩码，用于计算索引值
	unsigned long sizenask;
	
	// 该哈希表已有节点的数量
	unsigned long uesd;

} dictht;

Parmi eux, table est un tableau, chaque élément du tableau pointe vers un pointeur de type dictEntry et le type dictEntry stocke une paire clé-valeur.

On peut également voir ici que les nœuds de la table de hachage sont connectés par des listes chaînées pour résoudre le problème de conflit de hachage, qui est la méthode d'adresse en chaîne.

Hash collision et algorithme de hachage

Afin d'obtenir un accès rapide de la clé à la valeur, Redis utilise une table de hachage pour enregistrer toutes les paires clé-valeur. La key correspond à la Key définie par Redis, et la valuene correspond pas à la valeur elle-même, mais au pointeur pointant vers la valeur spécifique. Le plus grand avantage de l’utilisation d’une table de hachage est que vous pouvez trouver rapidement des paires clé-valeur avec une complexité temporelle O(1). Mais comme il s'agit d'une table de hachage, il y aura forcément un problème de conflit de hachage.

Le conflit de hachage signifie que lorsque la valeur de hachage de deux clés et du compartiment de hachage sont calculées, elles tombent sur le même compartiment de hachage.

La façon dont Redis résout les conflits de hachage consiste à utiliser le hachage en chaîne, qui est la méthode zippé. Lorsque plusieurs éléments pointent vers le même compartiment de hachage, une liste chaînée est utilisée pour enregistrer les données correspondantes dans le même compartiment de hachage, et ils sont connectés à leur tour à l'aide de pointeurs.

Algorithme de hachage

Lorsqu'une nouvelle paire clé-valeur est ajoutée au dictionnaire, le programme doit d'abord calculer la valeur de hachage et la valeur d'index en fonction de la paire clé-valeur, puis en fonction de la valeur d'index, la la nouvelle clé sera incluse. Le nœud de table de hachage de la paire de valeurs est placé à l'index spécifié dans le tableau de table de hachage.

processus reHash

Il existe un facteur de charge dans la table de hachage pour contrôler le nombre de paires clé-valeur enregistrées dans la table de hachage. Cela nécessite une opération de répétition pour terminer. Parmi eux, la formule de calcul du facteur de charge est :

// 负载因子 = 哈希表已保存的节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

Les conditions d'expansion et de contraction de la table de hachage sont les suivantes :

• Le serveur n'exécute pas actuellement la commande BGSAVE ou la commande BGREWRITEAOF, et le facteur de charge du hachage la table est supérieure ou égale à 1 ;
• Serveur La commande BGSAVE ou la commande BGREWRITEAOF est en cours d'exécution et le facteur de charge de la table de hachage est supérieur ou égal à 5 ; atteint, le processus de répétition sera exécuté.

Si le serveur exécute BGSAVE ou BGREWRITEAOF, Redis créera un processus enfant du processus serveur actuel

Le processus de rehachage est grossièrement divisé en trois étapes :

Allouer un espace plus grand à la table de hachage 2, par exemple, le hachage actuel Deux fois la taille de la table de hachage 1 ;

• 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 ; La taille de l'espace d'allocation d'étape est déterminée par le type d'opération de rehachage actuel et le nombre de paires clé-valeur dans la table de hachage actuelle.

• Lorsqu'une opération d'expansion est effectuée, la taille de l'espace alloué est la première valeur 2^n supérieure ou égale à (le nombre de paires clé-valeur dans la table de hachage * 2) 

Supposons que le ; le nombre actuel de paires clé-valeur est 4 , alors 4 * 2 = 8, car 8 est exactement égal à 2^3, ce qui est exactement égal à la première valeur égale à 2^n, donc l'espace d'expansion est 8 ;

• Si une opération de réduction est effectuée, l'espace alloué La taille est la première valeur 2^n supérieure ou égale à (le nombre de paires clé-valeur dans la table de hachage) ;
  Lorsque le nombre de tables de hachage est important, si toutes les données sont copiées en même temps, cela risque très probablement d'affecter le serveur. Par conséquent, Redis effectue une répétition plusieurs fois, ce qui est une répétition progressive.在 En termes simples, dans la deuxième étape, Redis gère toujours la demande du client normalement Chaque fois qu'une demande est traitée, à partir de la première position d'index dans la table de hachage 1 L'élément d'entrées est copié dans la table de hachage 2 ; effectuée, les entrées à la position d'index suivante sont copiées. De cette façon, il copie intelligemment la surcharge d'un grand nombre de copies à la fois, qui est appliquée au processus de demandes de traitement multiples, évitant ainsi les opérations fastidieuses et garantissant un accès rapide aux données.

  Opérations sur les tables de hachage pendant la période de rehachage

  Pendant l'opération de rehachage progressif, la suppression du dictionnaire, la recherche, la mise à jour et d'autres opérations seront effectuées dans deux tables de hachage. Par exemple, si vous souhaitez rechercher une clé dans le dictionnaire, vous l'interrogerez d'abord dans la table d'origine. S'il ne la trouve pas, vous l'interrogerez dans la nouvelle table. L'ajout du dictionnaire ne sera conservé que dans le nouveau tableau.

  Pour plus de connaissances sur la programmation, veuillez visiter :

  Introduction à la 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!