4 ms·

Good to hear, but that algorithm isn't LRU, and LRU makes more sense when backing a cache.

patio11 16y ago
Interestingly, I think if you tweaked it to be "Randomly sample three keys and blow away the LRU among them" it would be pretty close to a fully LRU implementation for a lot of typical workloads. Consider a website where 10% of the cache is hot: you'd discard a single hot entry only once every thousand cache evictions. I think for a lot of sites that is likely to be Good Enough, depending on the impact of a cache miss. Bonus: you can trivially tweak how sensitive that is by increasing the number of items to randomly sample.
- moe 16y ago
  To add my 2 cents here: I've been using both memcached and redis in various projects and for me they serve slightly different purposes. For plain old caching I haven't (yet) had a need to use redis, which is younger and by nature more complex. RAM is so cheap nowadays, we just tend to stuff two memcached machines with 64G, which goes a ridiculously long way. On the other hand, as antirez pointed out, redis shines when you need "a little more than caching". We have rolled a few custom queueing solutions on top of redis (similar to resque) and working with lists and the SUBSTR operation is an extremely pleasant experience. Redis seems to be the optimal "roll-your-own-queue" toolkit at this point. We had some strong delivery- and persistence-guarantee requirements in our project but those were not a problem to meet with a simple WAL on the clients and a redis-pair. So far our solution wins over the previous rabbitmq setup big time in all areas (performance, reliability, complexity, transparency). It could have been done with memcached, but less efficiently due to the lack of the aforementioned list-operations.
jasonwatkinspdx 16y ago
LRU isn't a panacea. Maintaining a real LRU can involve non-trivial overhead. It also can have trouble predicting some access patterns. Random replacement can definitely out perform LRU, particularly for tree structures.
- antirez 16y ago
  LRU has also memory overhead. So storing more data and using a less precise algorithm may be indeed better in some circumstances. Also there is no way to mount a precise LRU schema that is O(1). O(log(N)) complexity is needed.
  - wanderr 16y ago
    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.

Interestingly, I think if you tweaked it to be "Randomly sample three keys and blow away the LRU among them" it would be pretty close to a fully LRU implementation for a lot of typical workloads. Consider a website where 10% of the cache is hot: you'd discard a single hot entry only once every thousand cache evictions. I think for a lot of sites that is likely to be Good Enough, depending on the impact of a cache miss. Bonus: you can trivially tweak how sensitive that is by increasing the number of items to randomly sample.

moe 16y ago
To add my 2 cents here: I've been using both memcached and redis in various projects and for me they serve slightly different purposes. For plain old caching I haven't (yet) had a need to use redis, which is younger and by nature more complex. RAM is so cheap nowadays, we just tend to stuff two memcached machines with 64G, which goes a ridiculously long way. On the other hand, as antirez pointed out, redis shines when you need "a little more than caching". We have rolled a few custom queueing solutions on top of redis (similar to resque) and working with lists and the SUBSTR operation is an extremely pleasant experience. Redis seems to be the optimal "roll-your-own-queue" toolkit at this point. We had some strong delivery- and persistence-guarantee requirements in our project but those were not a problem to meet with a simple WAL on the clients and a redis-pair. So far our solution wins over the previous rabbitmq setup big time in all areas (performance, reliability, complexity, transparency). It could have been done with memcached, but less efficiently due to the lack of the aforementioned list-operations.

jasonwatkinspdx 16y ago

LRU isn't a panacea. Maintaining a real LRU can involve non-trivial overhead. It also can have trouble predicting some access patterns. Random replacement can definitely out perform LRU, particularly for tree structures.

antirez 16y ago
LRU has also memory overhead. So storing more data and using a less precise algorithm may be indeed better in some circumstances. Also there is no way to mount a precise LRU schema that is O(1). O(log(N)) complexity is needed.
- wanderr 16y ago
  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.