Quel est l'algorithme d'expiration des éléments dans le stockage de valeurs-clés?

Je réfléchissais à la façon dont les stockages de valeurs-clés actuels implémentent la «date d'expiration» pour les articles. Actuellement, j'ai 2 variantes pour cela dans mon esprit:

1. ils ne font rien (gardent les données expirées), et ne vérifient que lorsque vous faites, par exemple, GET par une clé. Le problème ici est que si vous êtes limité en mémoire, les éléments expirés ne seront pas supprimés.

2. ils conservent des structures de données supplémentaires pour pouvoir «expirer au plus tôt». Je vois que cela peut être fait avec quelque chose comme ça:

   storage_data = dict(key -> [value, expire_timestamp])
   expire_tree = SomeBinaryLikeTree(expire_timestamp -> [keys])
   

Le problème de la suppression des entrées expirées dans le cache est très similaire à la récupération de place , moins toute la complexité du comptage des références.

Les gens de Nasza-Klasa ont proposé l'algorithme O (1) pour Memcache comme suit:

Il semble que de nombreuses personnes pensent pour une raison quelconque que la libération des entrées expirées ne peut pas être effectuée dans O (1), ou même qu'elle nécessite des opérations Omega (N). L'utilisation d'un tas ou d'autres structures de données de file d'attente prioritaire peut évidemment vous donner O (log N), mais le patch ci-dessous vise O (1). Ceci est réalisé en ayant un seau pour chaque seconde, et en mettant chaque entrée dans un seau approprié en regardant l'heure d'expiration. Ensuite, à chaque seconde, nous libérons simplement les éléments du prochain seau. Il s'agit bien sûr de temps amorti O (1), mais il peut arriver que vous ayez beaucoup d'éléments qui expirent au même moment, donc le patch offre une limite fixe pour le nombre d'opérations que vous êtes prêt à effectuer pour une demande, pour rendre la collecte des ordures plus fluide.

Voir toute la proposition avec le code ci-joint .

Je suppose que le stockage de valeur-clé est trop grand pour simplement itérer sur toutes les paires kv pour savoir lequel peut expirer. Je suppose également que chaque accès en lecture actualise l'horodatage d'expiration, de sorte que seuls les éléments qui n'ont pas été consultés depuis un certain temps sont expirés.

Le défi est de trouver efficacement tous les enregistrements qui peuvent expirer (chaque fois que le nettoyage est dû), mais aussi d'actualiser efficacement l'horodatage d'expiration à chaque accès en lecture (nous devons donc trouver la clé dans la structure utilisée pour l'expiration).

Ma proposition: grouper expiry_timestamps dans des compartiments; par exemple, si les objets vivent pendant 8 heures, faites un seau par heure. Ces compartiments sont conservés dans une liste chaînée; à l'expiration, le premier compartiment est vidé et la liste réduite. Le nombre de compartiments est la durée de vie / intervalle de nettoyage. Chaque compartiment contient un hashSet de toutes les clés qui doivent être expirées. L'itération sur toutes les clés d'un hachage est suffisamment efficace.

Pendant l'accès en lecture, le programme vérifie dans quel compartiment la clé se trouve actuellement et à quel compartiment elle appartient maintenant. Dans la plupart des cas, il s'agit du même compartiment, donc aucune autre action n'est nécessaire. Sinon, retirez la clé de l'ancien compartiment (la suppression d'un ensemble de hachage est efficace) et insérez-la dans le nouveau compartiment.

   +--------------+   +--------------+   +--------------+
-->+ Expiry 08:00 +-->+ Expiry 09:00 +-->+ Expiry 10:00 +
   | KeySet       |   | KeySet       |   | KeySet       |
   +--------------+   +--------------+   +--------------+