[email protected] wrote:
Hi,
here at nasza-klasa.pl, we were always a bit worried about the way
that memcached handles expired elements, which causes evictions of
unexpired entries even though there is a lot of garbage that could be
freed.
After introducing the patch below we managed to eliminate evictions
entirely without sacrificing speed, memory or cache hit/miss ratio.
Another benefit of this patch is that if you know that there is no
garbage in memory, then you can put more trust in stats such as number
of cached items, and then decide how much RAM do you really need, or
how long should the TTLs be.
It was already known, that a lot of memory can be wasted by expired
entries. In our case it was at least 50%, but actually it could be
arbitrary large number, as memcached always consumes all memory that
you assign to it.
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.
Great idea.
Here at nasza-klasa.pl we run memcached in a single threaded mode, so
we have not tested the patch for the multithread set-ups.
There should be no problem with multithread. clean_up() is only called
inside do_item_alloc(), which always has the global 'cache_lock' mutex held.
I'm a little concerned about the latency that such operation could add
at alloc time. I think a background thread that does the cleaning every
second and doesn't bother the event loop should be better.
Regards,
Jaime.
