Do you know how memcached does it? Do they pay the performance overhead, or do they cheat in some way? I don't think perfect LRU is needed, but the general idea behind LRU works /very/ well for a memcached style cache.

Trying to achieve something similar using Redis by for example updating the expire on every read would be a bit of a pain and I think put extra load on the client and server. This isn't a complaint about Redis though, it has its own use cases which are wonderful and I have no objection to using both for their strengths.