Comment Redis et Memcache font expirer leurs données


Redis et Memcache ont des opérations d’insertion de complexité O(1) (très rapide). Malgré ça ils proposent tout deux l’expiration de clé.

Et je me suis demandé : comment ils font ? Comment je pourrais fais ça si je devais le coder en Python ?

En effet, rechercher une clé expirée prend du temps. J’ai pensé à utiliser heapq, mais l’insertion serait en 0(log(n)) (temps dépendant du nombre d’items), donc rapide, mais loin des perfs de Redis et Memcache.

Même si on garde à l’esprit qu’ils sont codés en C, et donc plus rapide, ça m’a turlupiné. Comment ils font ces cons ?

La réponse est surprenant : ils font la même chose que 0bin !

Memcache :

Memcache doesn’t evict keys when their expiration time expires, as doing so isn’t possible while still guaranteeing O(1) operation times. Instead expiration is more of a way to say how long until a key should be considered stale. When a GET is performed, Memcache checks if the key’s expiration time is still valid before returning it.

Redis :

Redis keys are expired in two ways: a passive way, and an active way. A key is actively expired simply when some client tries to access it, and the key is found to be timed out. Of course this is not enough as there are expired keys that will never be accessed again. This keys should be expired anyway, so periodically Redis test a few keys at random among keys with an expire set. All the keys that are already expired are deleted from the keyspace.

Memcache et Redis ne cherchent donc pas les clés, ils vérifient l’expiration à l’accès de la clé et suppriment le contenu si c’est dépassé.

Redis va plus loin en régulièrement prenant des clés au hasard et en checkant leur date d’expiration.

Gif de Tealc' buvant un café très chaud

Comment il fait ? Ah bah il fait pas.

12 thoughts on “Comment Redis et Memcache font expirer leurs données

  • kontre

    Je trouve ça toujours étonnant ces trucs qui marchent au hasard. Tout est déterministe et on fait quand même des trucs “au pif”.
    Si je ne dis pas de bêtise, c’est le cas de certains systèmes de fichiers sous Linux : on écrit à un endroit aléatoire du disque. Il y a l’algo classique du voyageur de commerce, aussi.
    Dans ce cas précis, on note aussi que le stockage coûte que dalle, puisque potentiellement ils gardent un paquet de données qui ont déjà expirées…

  • roro

    Question du fouilleur de catacombes: Où import sys va t-il chercher “sys.py” que je ne trouve nulle part ?

  • Sam Post author

    Dans la lib standard Python. Sys est un module codé en C, donc tu ne le trouveras que sous le forme d’un binaire compilé.

  • roro

    D’accord, d’accord. Hum! c’est les entrailles de la bête.
    Mais alors, il est inclus dans autre chose (invisible)?

  • roro

    Si on veut faire un “compilé” pour une machine qui n’a pas python; où on le pêche ce “sys” ?

  • Sam Post author

    Sous windows, sys sera un .dll, sous linux ce sera un .so.

    Python n’est pas un langage compilé. Il faut forcément une machine virtuel Python pour le faire tourner.

    Par contre on peut faire un executable pour windows qui intégrera Python avec Py2exe.

  • roro

    Hé bé c’est pour ça que j’y arrivais pas!
    L’installeur aussi, il voulait python.
    Faut pas vous inquiéter, j’aime bien tenter l’impossible.
    Juste une question de “cuisine”:
    Quand tu est sur un projet; tu as combien de pc sur “on” et combien d’écrans à portée de vue…en moyenne (à 10 près)?????

  • Sam Post author

    Juste mon portable, parfois un deuxième écran pour le confort. Dans certaines boites j’ai parfois des PC de tests pour accélérer les tests sur différentes config. Rajouter à ça les devices tels que : téléphones et tablettes…

    Mais la plupart du temps, juste mon portable. Et des tas de serveurs en SSH.

  • Greg

    Aha, je fais pareil sur mes applis JS. Et de temps en temps une routine parcoure le cache (tout) et nettoie ca… (tiens, je devrais faire ca dans un webworker)
    Maintenant je peux me la peter et dire que memcache utilise le meme principe! ;)

  • Sam Post author

    Par contre ils parcours pas tout justement, mais juste quelques entrées aléatoirement. L’impact sur les perfs est très différent. A court terme c’est plus léger, mais ça bouffe plus de mémoire.

  • Steeve

    Bonjour,
    Redis supporte-il les données massives ?
    Dans le cas où je choisis de stocker mes données de façon définitives (possibilité de retrouver mes données après redemarrage du poste), elles sont concervées dans la RAM ou dans le ROM ?

    bien cordialement,
    Steeve

  • Sam Post author

    Défini massive.

    Bien qu’on puisse le régler autrement, Redis est à la base fait pour que toutes les données de ta base doivent tenir en RAM.

    La plupart des base de données font moins d’un Go. Dans ce cas, acheter un serveur qui le permet n’est pas prohibitif.

    Memcache garde tout en RAM et perd tout au reboot. Redis garde tout en RAM mais écrit toutes les x secondes sur le disque. Aussi en cas de reboot, on retrouve ses données, – X secondes. Généralement on perds moins de 10 secodes de données.

Comments are closed.

Des questions Python sans rapport avec l'article ? Posez-les sur IndexError.