Un article expliquant en détail l'algorithme LRU dans Redis

Cet article vous présentera LRU (Least Récemment Utilisé) dans Redis J'espère qu'il vous sera utile !

Redis est une base de données clé-valeur basée sur le stockage en mémoire. Nous savons que même si la mémoire est rapide, elle dispose de peu d'espace lorsque la mémoire physique atteint la limite supérieure, car le système fonctionne très lentement. le mécanisme de swap stockera une partie de la mémoire. Les données sont transférées vers la partition de swap et l'échange avec swap garantit que le système continue de fonctionner. Toutefois, le swap est un stockage sur disque dur et sa vitesse est bien plus lente que celle de swap. mémoire Surtout pour un service avec un QPS très élevé comme Redis, il est impossible de le faire lorsqu'il est reçu. (Notez que si la mémoire de la partition de swap est également pleine, une erreur se produira dans le système !) [Recommandation associée : Tutoriel vidéo Redis]

Le système d'exploitation Linux peut vérifier la taille du swap via free -m:

Alors comment ? Il est très important d'éviter que cette situation ne se produise dans Redis (l'intervieweur ne pose presque jamais de questions sur ce point de connaissance lorsqu'il est interrogé sur Redis).

2. configuration maxmemory

Redis fournit une configuration maxmemory pour résoudre les problèmes ci-dessus. Cette configuration peut spécifier l'ensemble de données maximum de stockage Redis, ou elle peut être configurée à l'aide du CONFIG SET. commande au moment de l’exécution.
Schéma schématique des éléments de configuration dans le fichier redis.conf :

Par défaut, l'élément de configuration maxmemory n'est pas activé Redis introduit officiellement que les systèmes d'exploitation 64 bits n'ont pas de limite de mémoire par défaut, et 32. Les systèmes d'exploitation -bit ont une configuration de mémoire implicite par défaut de 3 Go. Si maxmemory est 0, cela signifie que la mémoire est illimitée.

Ainsi, lorsque nous construisons une architecture de cache, nous devons effectuer des configurations de mémoire maximale appropriées en fonction des ressources matérielles et des besoins de l'entreprise.

3. Que dois-je faire si la mémoire atteint maxmemory ? Évidemment, lorsque maxmemory atteint la limite maximale, il est impossible pour Redis de cesser de fonctionner. C'est l'objet de cet article. Redis propose une stratégie d'élimination de la politique de mémoire maximale (

Cet article ne parle que de LRU et n'implique pas LFU

, LFU sera décrit dans le prochain article), qui supprime les clés qui remplissent les conditions pour dire. au revoir aux anciens et bienvenue aux nouveaux. stratégie d'élimination de la politique de mémoire maximale :

noeviction :
• Lorsque la limite de mémoire est atteinte et que le client tente d'exécuter une commande susceptible d'entraîner l'utilisation de plus de mémoire, une erreur est renvoyée. En termes simples, les opérations de lecture sont. toujours autorisé, mais les écritures ne sont pas autorisées. Pour les nouvelles données, les requêtes del (suppression) sont OK .
allkeys-lru :
• Élimine de toutes les clés via l'algorithme lru (Least Récemment utilisé - Le moins récemment utilisé)
allkeys-random :
• Élimine aléatoirement de toutes les clés
volatile-lru :
• De toutes les clés avec un délai d'expiration défini, ils sont éliminés via l'algorithme lru (Least Récemment utilisé - Le moins récemment utilisé). Cela garantit que les données qui n'ont pas de délai d'expiration défini et qui doivent être conservées ne seront pas sélectionnées pour l'élimination. - random : Élimine aléatoirement de toutes les clés avec un délai d'expiration défini
• volatile-ttl : De toutes les clés avec un délai d'expiration défini, en comparant la valeur du temps d'expiration restant TTL de la clé, plus le TTL est petit, plus tôt Eliminate
• et volatile-lfu/allkeys-lfu seront discutés ci-dessous. Les deux algorithmes sont différents !
L'élimination aléatoire nécessite uniquement de sélectionner au hasard certaines clés pour supprimer et libérer de l'espace mémoire ; le délai d'expiration du ttl est court et celles avec le délai d'expiration le plus court peuvent être éliminées en premier. Vous pouvez également comparer la taille du ttl et supprimer le. clé avec la petite valeur ttl pour libérer de l'espace mémoire.

Alors, comment LRU est-il mis en œuvre ? Comment Redis sait-il quelle clé a été utilisée récemment et quelle clé n'a pas été utilisée récemment ?

4. Implémentation de l'algorithme LRU

Nous utilisons d'abord des conteneurs Java pour implémenter un algorithme LRU simple. Nous utilisons ConcurrentHashMap pour effectuer la relation de mappage des éléments de stockage des résultats clé-valeur et utilisons ConcurrentLinkedDeque pour maintenir la séquence d'accès aux clés.

Code d'implémentation LRU :

package com.lizba.redis.lru;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedDeque;

/**
 * <p>
 *      LRU简单实现
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/9/17 23:47
 */
public class SimpleLru {

    /** 数据缓存 */
    private ConcurrentHashMap<string> cacheData;
    /** 访问顺序记录 */
    private ConcurrentLinkedDeque<string> sequence;
    /** 缓存容量 */
    private int capacity;

    public SimpleLru(int capacity) {
        this.capacity = capacity;
        cacheData = new ConcurrentHashMap(capacity);
        sequence = new ConcurrentLinkedDeque();
    }


    /**
     * 设置值
     *
     * @param key
     * @param value
     * @return
     */
    public Object setValue(String key, Object value) {
        // 判断是否需要进行LRU淘汰
        this.maxMemoryHandle();
        // 包含则移除元素，新访问的元素一直保存在队列最前面
        if (sequence.contains(key)) {
            sequence.remove();
        }
        sequence.addFirst(key);
        cacheData.put(key, value);
        return value;
    }


    /**
     * 达到最大内存，淘汰最近最少使用的key
     */
    private void maxMemoryHandle() {
        while (sequence.size() >= capacity) {
            String lruKey = sequence.removeLast();
            cacheData.remove(lruKey);
            System.out.println("key: " + lruKey + "被淘汰！");
        }
    }


    /**
     * 获取访问LRU顺序
     *
     * @return
     */
    public List<string> getAll() {
        return Arrays.asList(sequence.toArray(new String[] {}));
    }
}复制代码</string></string></string>

Code de test :

package com.lizba.redis.lru;

/**
 * <p>
 *      测试最近最少使用
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/9/18 0:00
 */
public class TestSimpleLru {

    public static void main(String[] args) {
        SimpleLru lru = new SimpleLru(8);
        for (int i = 0; i <p>Résultats des tests : <strong></strong></p><p><strong></strong>Comme le montrent les résultats des tests ci-dessus, key0 et key1 qui ont été ajoutées en premier ont été éliminées et ont été ajouté en dernier La clé est également la dernière clé stockée en tête de la séquence. </p>Avec cette solution, l'algorithme LRU peut être facilement implémenté ; mais les inconvénients sont également très évidents. La solution nécessite l'utilisation de structures de données supplémentaires pour enregistrer la séquence d'accès aux clés, ce qui augmentera la consommation de mémoire Redis. optimiser la mémoire Mais cela consomme beaucoup de mémoire, ce qui n'est évidemment pas possible. <p><img src="https://img.php.cn/upload/image/775/594/750/163409191823487Un%20article%20expliquant%20en%20d%C3%A9tail%20lalgorithme%20LRU%20dans%20Redis" title="163409191823487Un article expliquant en détail lalgorithme LRU dans Redis" alt="Un article expliquant en détail lalgorithme LRU dans Redis"></p><h2 data-id="heading-4">5. LRU approximatif de Redis</h2><p>En réponse à cette situation, Redis utilise l'algorithme LRU approximatif, qui n'est pas complètement précis pour éliminer les clés les moins fréquemment utilisées récemment, mais la précision globale peut être garantie. <br>L'algorithme LRU approximatif est très simple. Dans l'objet clé Redis, 24 bits sont ajoutés pour stocker l'horodatage système du dernier accès Lorsque le client envoie une requête liée à l'écriture de clé au serveur Redis, il s'avère que la mémoire. atteint la mémoire maximale À ce moment-là, déclenchez la suppression paresseuse ; le service Redis sélectionne 5 clés qui remplissent les conditions par échantillonnage aléatoire (notez que cet échantillonnage aléatoire <strong>allkeys-lru</strong> est échantillonné de manière aléatoire à partir de toutes les clés, <strong>volatile-lru</strong> est à partir de toutes les clés. avec le délai d'expiration défini Échantillonnage aléatoire), comparez le dernier horodatage d'accès enregistré dans l'objet clé et éliminez la clé la plus ancienne parmi les cinq clés si la mémoire n'est toujours pas suffisante, continuez à répéter cette étape ; <br></p><p><strong>Notez que 5 est la taille de valeur d'échantillonnage aléatoire par défaut de Redis, qui peut être configurée via maxmemory_samples dans redis.conf : </strong></p><p><img src="https://img.php.cn/upload/image/866/655/134/163409192913128Un%20article%20expliquant%20en%20d%C3%A9tail%20lalgorithme%20LRU%20dans%20Redis" title="163409192913128Un article expliquant en détail lalgorithme LRU dans Redis" alt="Un article expliquant en détail lalgorithme LRU dans Redis"></p><p><strong>Pour l'algorithme LRU aléatoire ci-dessus, le responsable de Redis a donné un tableau de données de précision de test : </strong></p>

• La couche supérieure gris clair représente les anciennes clés éliminées. La figure 1 est un diagramme schématique de l'élimination de l'algorithme LRU standard.
• La couche moyenne gris foncé représente les anciennes clés qui n'ont pas été éliminées. la couche de vert clair représente la clé la plus récemment consultée

Dans Redis 3.0, lorsque maxmemory_samples est défini sur 10, l'algorithme LRU approximatif de Redis est très proche du véritable algorithme LRU, mais définir évidemment maxmemory_samples sur 10 consomme plus de CPU que le paramètre maxmemory_samples à 5 Temps de calcul, étant donné que les données d'échantillonnage échantillonnées à chaque fois augmentent, le temps de calcul augmentera également.

L'algorithme LRU de Redis3.0 est plus précis que l'algorithme LRU de Redis2.8
, car Redis3.0 ajoute un pool d'élimination de la même taille que maxmemory_samples. Chaque fois qu'une clé est éliminée, elle est d'abord comparée à la clé. pool d'élimination en attente d'élimination. Les clés sont comparées, et la clé la plus ancienne est finalement éliminée. En fait, les clés sélectionnées pour l'élimination sont rassemblées et comparées à nouveau, et la clé la plus ancienne est éliminée. 6. Il y a des problèmes

L'algorithme LRU semble plus facile à utiliser, mais il y a aussi des endroits déraisonnables. Par exemple, deux clés A et B ont été ajoutées à Redis en même temps une heure avant l'élimination, avec A. d'abord, il a été consulté 1 000 fois en 49 minutes, mais n'a pas été consulté dans les 11 minutes suivantes ; B n'a été consulté qu'une fois au cours de la 59e minute de cette heure si l'algorithme LRU est utilisé à ce moment-là, si A et B sont tous deux ; sélectionné par échantillonnage Redis, A Sera éliminé, ce n'est évidemment pas raisonnable.

En réponse à cette situation, Redis 4.0 a ajouté l'algorithme LFU (Le moins fréquemment utilisé), qui est le moins fréquemment utilisé. Cet algorithme est plus raisonnable que LRU. Nous découvrirons l'algorithme d'élimination ci-dessous. Si nécessaire, veuillez faire attention à mon. colonne.

Pour plus de connaissances liées à la programmation, veuillez visiter :

Enseignement de 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!