Stratégies de suppression des clés expirées

Redis offre la possibilité d'attribuer une durée de vie aux clés stockées. Un mécanisme dédié gère leur suppression une fois cette durée écoulée. Plusieurs approches coexistent pour effectuer ce nettoyage.

Configuration de la durée de vie

Plusieurs commandes permettent de paramétrer l'expiration :

• expire <clé> <secondes> : définit l'expiration après un nombre de secondes spécifié.
• pexpire <clé> <millisecondes> : définit l'expiration en millisecondes.
• expireat <clé> <timestamp_sec> : fixe l'expiration à un horodatage précis en secondes.
• pexpireat <clé> <timestamp_ms> : fixe l'expiration à un horodatage précis en millisecondes.

Pour les types chaînes, l'expiration peut être définie lors de la création :

• set <clé> <valeur> ex <secondes>
• set <clé> <valeur> px <millisecondes>
• setex <clé> <secondes> <valeur>

La commande TTL <clé> indique le temps restant avant expiration. L'annulation de l'expiration est possible avec PERSIST <clé>.

Détection des clés périmées

Redis maintient un dictionnaire interne (expires) qui associe chaque clé à son timestamp d'expiration. La structure de base de données inclut :

typedef struct {
    dict *keys;    /* Toutes les paires clé-valeur */
    dict *expires; /* Horodatages d'expiration */
    // ...
} Database;

Lors d'un accès à une clé, Redis vérifie sa présence dans ce dictionnaire. Si elle y figure, il compare l'horodatage enregistré avec le temps système courant pour déterminer si la clé est périmée.

Approches de nettoyage

Les principales méthodes de suppression sont :

Nettoyage immédiat (suppression programmée) : Chaque clé se voit attacher un minuteru lors de la définition de son expiration. À échéance, le processus de suppression est déclenché automatiquement. Cette méthode libère la mémoire rapidement mais peut solliciter le processeur en cas de nombreux événements.

Nettoyage à la demande (suppression paresseuse) : La vérification d'expiration n'a lieu qu'au moment de l'accès à une clé. Cela économise les ressources processeur mais peut laisser des données périmées occuper la mémoire si elles ne sont plus consultées.

Nettoyage périodique (suppression régulière) : Un processus d'arrière-plan examine aléatoirement un sous-ensemble de clés à intervalles réguliers. Il supprime celles qui sont périmées. Cette approche équilibre charge processeur et occupation mémoire, mais nécessite un calibrage précis de la fréquence et de la durée des cycles.

Implémentation dans Redis

Redis combine les stratégies paresseuse et périodique pour un compromis optimal.

Suppression paresseuse : La fonction checkExpiry est appelée avant chaque opération sur une clé. Elle vérifie l'expiration et, si nécessaire, déclenche la suppression.

int checkExpiry(Database *db, StringObject *key) {
    if (!isExpired(db, key)) return 0;
    // ...
    return useAsyncDeletion ? asyncDelete(db, key) : syncDelete(db, key);
}

Suppression périodique : Le processus s'exécute selon la fréquence définie par le paramètre hz (par défaut 10 par seconde). À chaque cycle, il échantillonne 20 clés aléatoires, supprime les périmées, et répète l'opération si plus de 25% des clés échantillonnées étaient périmées, sans dépasser une limite de temps de 25ms.

procedure periodicExpiry():
    maxTime = currentTime() + 25ms
    repeat
        expiredCount = 0
        sampledKeys = 20
        while sampledKeys > 0 and currentTime() < maxTime:
            key = randomKeyFromExpiryDict()
            if isExpired(key):
                delete(key)
                expiredCount += 1
            sampledKeys -= 1
    until expiredCount <= 5  // 20/4 = 5

Stratégies d'éviction mémoire

Lorsque la mémoire utilisée par Redis dépasse la limite configurée, des mécanismes d'éviction entrent en jeu pour libérer de l'espace. Ces mécanismes sont distincts des stratégies d'expiration et agissent sur des critères différents.

Configuration de la limite mémoire

Le paramètre maxmemory dans la configuration (redis.conf) définit la mémoire maximale autorisée. Son comportement par défaut varie selon l'architecture du système (aucune limite sur 64 bits, 3Go sur 32 bits).

Politiques d'éviction

Huit politiques d'éviction sont disponibles, classées en deux catégories :

Sans éviction : noeviction (par défaut depuis Redis 3.0). Lorsque la limite est atteinte, les nouvelles écritures échouent avec une erreur.

Avec éviction parmi les clés expirables :

• volatile-random : élimine aléatoirement une clé ayant une durée de vie définie.
• volatile-ttl : privilégie l'élimination des clés dont le TTL est le plus faible.
• volatile-lru : élimine la clé expirable la moins récemment utilisée.
• volatile-lfu (depuis Redis 4.0) : élimine la clé expirable la moins fréquemment utilisée.

Avec éviction parmi toutes les clés :

• allkeys-random : élimine aléatoirement n'importe quelle clé.
• allkeys-lru : élimine la clé globale la moins récemment utilisée.
• allkeys-lfu (depuis Redis 4.0) : élimine la clé globale la moins fréquemment utilisée.

La commande CONFIG GET maxmemory-policy permet de consulter la politique active. La modification peut se faire dynamiquement avec CONFIG SET ou de façon permanente via le fichier de configuration.

Algorithmes LRU et LFU

LRU (Least Recently Used) : Privilégie la suppression des éléments inutilisés depuis longtemps. Redis implémente une approximation probabiliste : lors d'une éviction, il échantillonne aléatoirement un nombre limité de clés et supprime celle dont le dernier accès est le plus ancien. Cela évite le surcoût d'une liste chaînée complète.

LFU (Least Frequently Used) : Privilégie la suppression des éléments les moins sollicités. L'objet Redis utilise 24 bits pour stocker des métadonnées. En mode LFU, ces bits sont répartis entre un horodatage de dernière décroissance et un compteur logique de fréquence. Ce competur diminue progressivement avec le temps et augmente probabiliste lors des accès, reflétant ainsi la fréquence d'utilisation réelle plutôt qu'un simple comptage. Les paramètres lfu-decay-time et lfu-log-factor permettent d'ajuster le comportement.