What is the algorithm for expiring items in key-value storage?

Question

I was thinking on how current key-value storages implement "expire date" for items. Currently I have 2 variants for that in my mind:

1. they don't do anything (keep expired data), and only do check when you do, for example, GET by some key. The problem here is that if you are limited in memory, expired items won't be deleted.

2. they keep additional data structures to be able to get "earliest to expire". I see it can be done with something like this:

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

Answer 1

The problem of deleting expired entries in cache is very much an equivalent of garbage collection, minus whole complexity of reference counting.

People at Nasza-Klasa have proposed O(1) algorithm for Memcache as follows:

It seems that many people believed for some reason that freeing expired entries can not be performed in O(1), or even that it requires Omega(N) operations. Using a heap, or other priority queue data structures can obviously give you O(log N), but the patch below aims at O(1). This is achieved by having one bucket for each second, and by putting each entry in a proper bucket by looking at the expiration time. Then at each second we just free elements from the next bucket. This is obviously O(1) amortized time, but it can happen that you have a lot of elements that expire at the very same moment, so the patch offers a fixed limit for number of operations that you are willing to perform per one request, to make the garbage collection run smoother.

See whole proposal with attached code.

Answer 2

I assume the key-value storage is too large to just iterate over all k-v-pairs to find out which can be expired. I also assume that each read access refreshes the expiry timestamp, so only items which haven't been accessed for some time are expired.

The challenge is to efficiently find all records which can be expired (whenever cleanup is due), but also efficiently refresh the expiry timestamp on every read access (so we must find the key in the structure used for expiration).

My proposal: group expiry_timestamps into buckets; for example, if items live for 8 hours, make one bucket per hour. Those buckets are kept in a linked list; when expiration happens, the first bucket is emptied and the list reduced. The number of buckets is lifespan/cleanup interval. Each bucket contains a hashSet of all keys that should be expired. Iteration over all keys in a hashset is efficient enough.

During read access, the program checks which bucket the key currently is in and which bucket it now belongs to. In most cases, it's the same bucket, so no further action is necessary. Otherwise, remove the key from the old bucket (removing from a hash set is efficient) and insert it into the new bucket.

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