memcached purging and LRU

[Anatoly Vorobey]

On Fri, Feb 11, 2005 at 02:42:36PM -0800, Sergio Salvatore wrote:
> understand with memcached's slab allocator that I may
> run out of appropriately sized slabs before my overall
> memory is exhausted, but other posts that I've
> encountered seem to indicate that there's an LRU
> purging method in cases like this.  Is this correct? 
> If so, why would you ever get an "out of memory"
> problem?

Basically you get an "out of memory error" if you already filled all
available memory with items of various sizes, and now you're trying
to store a new item with a very different size - such that you haven't
stored items in the same size class before.

In more detail: as you're storing items, each item is put into the 
appropriate size class, which currently go by powers of 2: 128 bytes,
256 bytes, 512bytes, 1k, 2k, 4k, 8k... The size of the item is roughly 
the size of its key + size of its data + a fixed header, and all this
taken together will determing into which LRU queue it will go. There's 
a separate LRU queue for each class. 

As the cache is filled in initially, memcached allocates chunks of 1Mb 
of memory to a class whenever it needs to store a new item into it and 
there's no free slots available. It chops up that 1Mb into slots of the 
appropriate size for that class and makes them available. 

When all the memory you've given to memcached has been exhausted by 
this, it starts to remove items from LRU queues in order to put in new 
ones. But it only does so on an individual class basis. So that, for 
instance, if you're trying to store an item of total size 10k, memcached 
will look at the free slots it has for the 16k class, and if it has 
none, it'll throw away an existing item from that class (the one that 
hasn't been requested for the longest time) and let your new item take 
its slot. However, if there are no existing items in the LRU for that
class, and no free slots either, because when the cache had been filling
an item of that size had never been stored and a chunk of 1Mb had never 
been given to this class, memcached gives up and returns the error.


> If memcached doesn't have LRU purging, is there a way
> to implement this on top of the daemon?  

Memcached does have LRU purging, but it doesn't have one global LRU for 
all items, only a bunch of separate LRUs for different classes based on 
item sizes.

If the problem you described must be avoided, a crude and quick way to 
do that would be to send to memcached, right after the server is 
started, dummy items of all classes that you could possibly store in 
the future, to make the server allocate at least one 1Mb chunk to each 
class. 

-- 
avva
"There's nothing simply good, nor ill alone" -- John Donne