Cet article vous apporte des connaissances pertinentes sur Redis Il présente principalement la mise en œuvre de l'algorithme d'élimination du cache LRU, y compris la mise en œuvre de l'algorithme LRU approximatif de Redis, l'exécution réelle de l'algorithme LRU approximatif, etc. être utile à tout le monde.
Apprentissage recommandé : Tutoriel d'apprentissage Redis
LRU, Least Récemment utilisé (Least Récemment utilisé, LRU), algorithme de cache classique.
LRU utilisera une liste chaînée pour maintenir l'état d'accès de chaque donnée dans le cache, et ajustera la position des données dans la liste chaînée en fonction de l'accès en temps réel aux données, puis utilisera la position des données dans la liste chaînée pour indiquer si les données ont été récemment consultées ou non.
LRU placera respectivement la tête et la queue de la chaîne à l'extrémité MRU et à l'extrémité LRU :
LRU peut être divisé dans les cas suivants :
Illustration du cas 2 : La longueur de la liste chaînée est de 5, et les données enregistrées de la tête à la queue de la liste chaînée sont 5, 33, 9, 10 et 8 respectivement. Supposons que les données 9 soient consultées une fois, puis 9 seront déplacées vers la tête de la liste chaînée, et en même temps, les données 5 et 33 seront toutes deux déplacées d'une position vers la fin de la liste chaînée.
Donc, s'il est implémenté strictement selon LRU, en supposant que Redis enregistre beaucoup de données, il doit être implémenté dans le code :
Lorsque Redis utilise le maximum de mémoire, maintenez une liste chaînée pour tous les données qui peuvent être hébergées
Espace mémoire supplémentaire pour enregistrer la liste chaînée
Chaque fois que de nouvelles données sont insérées ou que des données existantes sont à nouveau accessibles, plusieurs opérations de liste chaînée doivent être effectuées
Dans le processus d'accès aux données, Redis est affecté par la surcharge liée au mouvement des données et aux opérations de liste chaînée
Conduisant en fin de compte à une réduction des performances d'accès Redis.
Ainsi, qu'il s'agisse d'économiser de la mémoire ou de maintenir les hautes performances de Redis, Redis n'est pas implémenté strictement selon les principes de base de LRU, mais fournit une implémentation approximative de l'algorithme LRU.
Comment le mécanisme d'élimination de mémoire de Redis active-t-il l'algorithme LRU approximatif ? Les paramètres de configuration suivants dans redis.conf :
maxmemory, définissez la capacité de mémoire maximale que le serveur Redis peut utiliser. Une fois que la mémoire réelle utilisée par le serveur dépasse le seuil, le serveur effectuera une élimination de mémoire en fonction du. Politique de configuration maxmemory-policy. Utilisez
maxmemory-policy pour définir la stratégie d'élimination de la mémoire du serveur Redis, y compris LRU, LFU approximatifs, l'élimination par valeur TTL et l'élimination aléatoire, etc. une fois l'option maxmemory définie et lorsque maxmemory-policy est configuré comme allkeys-lru ou volatile-lru, une LRU approximative est activée. allkeys-lru et volatile-lru utilisent tous deux un LRU approximatif pour éliminer les données. La différence est la suivante :
volatile-lru filtre dans les paires KV avec TTL défini Les données qui sera éliminé
Initialisation de la valeur clé et mise à jour de la valeur de l'horloge LRU
Quoi Dans la fonction, la valeur d'horloge LRU correspondant à chaque paire clé-valeur est initialisée et mise à jourL'exécution réelle de l'algorithme LRU approximatif
Comment exécuter l'algorithme LRU approximatif, c'est-à-dire lorsque l'élimination des données est déclenchée, et le mécanisme d'élimination réel Pour mettre en œuvre2.1 Calcul de la valeur globale de l'horloge LRU
L'algorithme LRU approximatif doit encore distinguer la rapidité d'accès des différentes données, c'est-à-dire que Redis a besoin de connaître la dernière heure d'accès aux données. D’où l’horloge LRU : enregistrer l’horodatage de chaque accès aux données. Redis utilisera une structure redisObject pour enregistrer le pointeur vers V pour V dans chaque paire KV. En plus du pointeur qui enregistre la valeur, redisObject utilise également 24 bits pour enregistrer les informations d'horloge LRU, qui correspondent à la variable membre lru. De cette manière, chaque paire KV enregistrera l'horodatage de son dernier accès dans la variable lru.Comment la valeur d'horloge LRU de chaque paire KV est-elle calculée ? Redis Server utilise une horloge LRU globale au niveau de l'instance, et l'heure LRU de chaque paire KV est définie en fonction de l'horloge LRU globale.
Cette horloge LRU globale est stockée dans la variable membre du serveur de variables globales Redislruclock
Lorsque le serveur Redis est démarré et que initServerConfig est appelé pour initialiser divers paramètres, getLRUClock sera appelé pour définir la valeur de lruclock :
Il faut donc noter que si l'intervalle de temps entre deux accès à une donnée est
La fonction getLRUClock divise l'horodatage UNIX obtenu par LRU_CLOCK_RESOLUTION pour obtenir l'horodatage UNIX calculé avec la précision de l'horloge LRU, qui est la valeur actuelle de l'horloge LRU.
getLRUClock effectuera une opération AND entre la valeur de l'horloge LRU et la définition de la macro LRU_CLOCK_MAX (la valeur maximale que l'horloge LRU peut représenter).
Ainsi, par défaut, la valeur globale de l'horloge LRU est un horodatage UNIX calculé avec une précision de 1s, et est initialisé dans initServerConfig.
Comment la valeur de l'horloge LRU globale est-elle mise à jour lorsque Redis Server est en cours d'exécution ? Il est lié au serverCron correspondant à l'événement s'exécutant régulièrement de Redis Server dans le cadre piloté par les événements.
serverCron, en tant que fonction de rappel pour les événements temporels, sera exécutée périodiquement. Sa valeur de fréquence est déterminée par l'élément de configuration hz dans redis.conf. La valeur par défaut est 10, c'est-à-dire que la fonction serverCron s'exécutera toutes les 100 ms. (1s/10 = 100ms). Dans serverCron, la valeur de l'horloge globale LRU sera mise à jour régulièrement en fonction de la fréquence d'exécution de cette fonction en appelant getLRUClock :
De cette façon, chaque paire KV peut obtenir le dernier horodatage d'accès de l'horloge globale LRU.
Pour chaque paire KV, dans quelles fonctions son redisObject.lru correspondant est-il initialisé et mis à jour ?
Pour une paire KV, la valeur d'horloge LRU est initialement définie lors de la création de la paire KV. Cette opération d'initialisation est appelée dans la fonction createObject, cette fonction. est appelé lorsque Redis souhaite créer une paire KV.
En plus d'allouer de l'espace mémoire à redisObject, createObject initialisera également redisObject.lru selon la configuration maxmemory_policy.
LRU_CLOCK renvoie la valeur actuelle de l'horloge LRU globale. Parce qu'une fois qu'une paire KV est créée, elle équivaut à un accès, et sa valeur d'horloge LRU correspondante représente son horodatage d'accès :
Quand la valeur d'horloge LRU de cette paire KV sera-t-elle à nouveau mise à jour ?
Tant qu'une paire KV est accédée, sa valeur d'horloge LRU sera mise à jour ! Lorsqu'une paire KV est accédée, l'opération d'accès finira par appeler lookupKey.
lookupKey recherchera la paire KV accessible à partir de la table de hachage globale. Si la paire KV existe, lookupKey mettra à jour la valeur d'horloge LRU de la paire clé-valeur, qui est son horodatage d'accès, en fonction de la valeur de configuration de maxmemory_policy.
Lorsque maxmemory_policy n'est pas configuré en tant que politique LFU, la fonction lookupKey appellera la fonction LRU_CLOCK pour obtenir la valeur d'horloge globale LRU actuelle et l'attribuera à la variable lru dans la structure redisObject de la paire clé-valeur
De cette façon, une fois l'accès à chaque paire KV effectué, elle peut obtenir le dernier horodatage d'accès. Mais vous pourriez être curieux : comment ces horodatages d'accès sont-ils finalement utilisés pour se rapprocher de l'algorithme LRU pour l'élimination des données ?
La raison pour laquelle Redis implémente le LRU approximatif est de réduire la surcharge des ressources mémoire et du temps de fonctionnement.
La logique principale du LRU approximatif réside dans la réalisation d'expulsions.
performEvictions est appelée par evictionTimeProc et la fonction evictionTimeProc est appelée par processCommand.
processCommand, Redis appellera lors du traitement de chaque commande :
Ensuite, isSafeToPerformEvictions jugera à nouveau s'il faut continuer à exécuter performEvictions en fonction des conditions suivantes :
Une fois performEvictions appelé et maxmemory-policy défini sur allkeys-lru ou volatile-lru, l'exécution approximative de LRU est déclenchée.
L'exécution peut être divisée en les étapes suivantes :
Appelez getMaxmemoryState pour évaluer l'utilisation actuelle de la mémoire et déterminer si le Le serveur Redis actuel utilise la capacité de mémoire. La valeur de configuration maxmemory est dépassée.
S'il ne dépasse pas maxmemory, C_OK sera renvoyé et performEvictions reviendra également directement.
Lorsque getMaxmemoryState évalue l'utilisation actuelle de la mémoire, s'il constate que la mémoire utilisée dépasse la mémoire maximale, il calculera la quantité de mémoire qui doit être libérée. La taille de cette mémoire libérée = la quantité de mémoire utilisée - maxmemory.
Mais la quantité de mémoire utilisée n'inclut pas la taille du tampon de copie utilisée pour la réplication maître-esclave, qui est calculée par getMaxmemoryState en appelant freeMemoryGetNotCountedMemory.
Si la quantité de mémoire actuellement utilisée par le serveur dépasse la limite supérieure de maxmemory, performEvictions exécutera une boucle while pour éliminer les données et libérer de la mémoire.
Pour les données d'élimination, Redis définit le tableau EvictionPoolLRU pour enregistrer les paires KV candidates à éliminer :
De cette façon, lorsque Redis Server exécute initSever pour l'initialisation, il appellera evictionPoolAlloc pour allouer de l'espace mémoire au tableau EvictionPoolLRU. La taille du tableau est déterminée par EVPOOL_SIZE. Par défaut, il peut enregistrer 16 candidats. Paires KV à éliminer.
PerformEvictions mettra à jour l'ensemble des paires KV candidates à éliminer, qui est le tableau EvictionPoolLRU, pendant le processus cyclique d'élimination des données.
performEvictions appelle evictionPoolPopulate, qui appellera d'abord dictGetSomeKeys pour obtenir aléatoirement un certain nombre K de la table de hachage à échantillonner :
Donc, dictGetSomeKeys renvoie l'ensemble de paires KV échantillonnées. evictionPoolPopulate exécute une boucle basée sur le nombre réel de paires KV échantillonnées : appelezestimateObjectIdleTime pour calculer le temps d'inactivité de chaque paire KV dans l'ensemble d'échantillonnage :
Ensuite, evictionPoolPopulate parcourt l'ensemble des paires KV candidates à éliminer, c'est-à-dire le tableau EvictionPoolLRU, essayez d'insérer chaque paire KV échantillonnée dans le tableau EvictionPoolLRU, en fonction de l'une des conditions suivantes :
2.3.2.3 Sélectionnez la paire KV éliminée et supprimez
Une fois le K éliminé sélectionné, performEvictions effectuera une suppression synchrone ou une suppression asynchrone selon la configuration de suppression paresseuse du serveur Redis : 
À ce stade, performEvictions a éliminé un K. Si l'espace mémoire libéré à ce moment n'est pas suffisant, c'est-à-dire que l'espace à libérer n'est pas atteint, performEvictions répétera également le processus de mise à jour de l'ensemble des paires KV candidates à éliminer et de sélection de la paire KV finale jusqu'à ce que le L'espace à libérer est satisfait aux exigences de taille. 
L'algorithme LRU approximatif n'utilise pas de liste chaînée qui prend du temps et de l'espace, mais utilise un ensemble de données de taille fixe à éliminer et sélectionne au hasard quelques K à ajouter à l'ensemble de données à éliminer. éliminé à chaque fois.
Enfin, en fonction de la durée d'inactivité des K dans l'ensemble à éliminer, supprimez les K avec le temps d'inactivité le plus long.
Selon les principes de base de l'algorithme LRU, il s'avère que si l'algorithme LRU est implémenté strictement selon les principes de base, le système développé aura besoin d'espace mémoire supplémentaire pour enregistrer la liste chaînée LRU, et le système Le fonctionnement sera également affecté par la surcharge des opérations de liste chaînée LRU.
Les ressources mémoire et les performances de Redis sont toutes deux importantes, c'est pourquoi Redis implémente l'algorithme LRU approximatif :
Le principe de base d'un algorithme et l'exécution réelle de l'algorithme sont dans le système Il y aura certains compromis pendant le développement, et les exigences en matière de ressources et de performances du système développé doivent être prises en compte de manière globale pour éviter la surcharge de ressources et de performances causée par une mise en œuvre stricte de l'algorithme.
Apprentissage recommandé : Tutoriel Redis
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!
Logiciel de base de données couramment utilisé
Que sont les bases de données en mémoire ?
Lequel a une vitesse de lecture plus rapide, mongodb ou redis ?
Comment utiliser Redis comme serveur de cache
Comment Redis résout la cohérence des données
Comment MySQL et Redis assurent-ils la cohérence des doubles écritures ?
Quelles données le cache Redis stocke-t-il généralement ?
Quels sont les 8 types de données de Redis
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
