Adaptive Replacement Cache

[Sean Chittenden]

> Might be nice to make memcached support configurable cache policies.
> Currently it's just LRU, but this would be a good option:

I've thought about this.  PostgreSQL just moved to using this over LRU 
and so far the tests have shown it to perform exceedingly well.  That 
said, ARC and 2Q were designed to prevent full table scans from purging 
a database's cache.  With that in mind, I think ARC would be less 
effective for memcached because there isn't the equiv of a full table 
scan (ie, the ability to do "get foo*").  Now, if one could move from a 
hash to a tree (or have both exist in the backend with a flag 
determining which lookup method, or with keys ending up in both the 
hash and tree), which would let people perform "get foo*", then ARC 
would become an invaluable replacement for LRU.

I'm finding that being able to do purges of data similar to:

delete uid_1234_*
delete news_pages_*

are becoming rather hard to keep track of.

Think about:

delete search_page_offset:0_limit:30
delete search_page_offset:30_limit:60
delete search_page_offset:60_limit:90
etc...

Being able to do:

delete search_page_*

would be infinitely nicer and probably faster, actually, because it'd 
save the client from making multiple requests.  Given that memcached is 
nearly always RAM bound and not CPU bound, I'm wondering what people 
(ie, Brad, Ava) would think in terms of moving/adding a tree storage 
method.  Storage would still be managed by the slab/pool allocator, but 
instead of using a hash to lookup keys, a tree could be used instead, 
or in addition too (pending some kind of config).  Granted a tree is 
going to take a few more cycles when doing a lookup, but in terms of 
price/performance for being able to do wild card matching, I don't know 
that it'd be a hard tradeoff to justify adding, esp if it's a CLI 
option that'd allow existing functionality to be used.

-sc

-- 
Sean Chittenden