Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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])
    
share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
Thanks. I also thought on "bucket" solution as one way. Also there's no problem with "too much items in bucket" since you can go with algorithm "take buckets you didn't take last time, and get back when you're finished". –  Konstantine Rybnikov May 30 '12 at 11:08
    
@k_bx: that's why they propose double linked list, so you can go back to previous buckets. –  vartec May 30 '12 at 11:10
    
If buckets are something like seconds, then you don't need linked lists at all. To go previous, you just decrease key :) –  Konstantine Rybnikov May 30 '12 at 11:35
    
@k_bx: decrease key by how much? one second? what if previous not completely emptied bucket was 5 minutes ago? decrease by step of 1s 300 times? –  vartec May 30 '12 at 11:42
    
On first server start, you init variable called current_expire_bucket to some value. Then, you run cleanup starting from current_expire_bucket, ending current second. After cleanup ends, you sleep for some small period. If server stops, you'll go through same "expire bucket" again, yes, but it should happen only on server stops. –  Konstantine Rybnikov May 30 '12 at 13:52
show 1 more comment

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       |
   +--------------+   +--------------+   +--------------+
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.