Specifics on Memcached's strategy for allocation after max memory has been reached

Question

Hi,

According to the Memcached wiki, the following occurs when an attempt to allocate a value to the cache is executed and the memory limit is reached:

When do expired cached items get deleted from the cache?

memcached uses a lazy expiration, which means it uses no extra cpu expiring items. When an item is requested (a get request) it checks the expiration time to see if the item is still valid before returning it to the client.

Similarly when adding a new item to the cache, if the cache is full, it will look at for expired items to replace before replacing the least used items in the cache.used items in the cache.

The question is, what exactly occurs when it replaces the 'least used items'. Does it simply maintain a rank by access for each key, or does it track access over a period?

For example. I add 2 items to the cache (A and B). The access patterns for A and B are slightly different. I access A 5000 times every hour while I access B once every second. According to the documentation, it seems that if I attempt to add another item (C) after two hours and the max memory allocation is reached, B will be removed. This is because B has only been accessed 7200 times while A has been accessed 10000 times.

Is this correct? If not, is there a sliding time window where access is tracked? For example, A would be removed if the window is 30 minutes because it would have been accessed 0 times in the last 30 minutes while B would have been accessed 1800 times.

Any thoughts?

Answer 1

It's not an exact LRU. In general, you shouldn't make any assumptions about availability of things in the cache.

An exact LRU would be a lot more expensive as things would be moving around too frequently. Instead, memcached won't place an item at the head of an LRU if it's done so recently.