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.

No related posts.

flattr this!

10 comments

  1. 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…

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

  3. 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é.

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

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

  6. 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.

  7. 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)?????

  8. 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.

  9. 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! ;)

  10. 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.

Flux RSS des commentaires

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">

Jouer à mario en attendant que les autres répondent