LRU算法的实现，简单粗暴的Redis与中规中矩的Memcached

Redis

今天看 Redis3.0的发行通告 里说，LRU算法大幅提升了，就翻开源码来八卦一下，结果哭笑不得，这所谓"近似LRU"算法，实在太简单，太粗暴，太偷懒，太Redis了。

在 Github的Redis项目 里搜索lru，代码在redis.c的freeMemoryIfNeeded()函数里，如果内存超出了maxmemory的设置，就会用此方法释放出足够的内存来存放新增记录。

先看 2.6版的代码 ： 竟然就是随机找三条记录出来，比较哪条空闲时间最长就删哪条，然后再随机三条出来，一直删到内存足够放下新记录为止.......可怜我看 配置文档 后的想象，一直以为它会帮我在整个Redis里找空闲时间最长的。

好，收拾心情再看 3.0版的改进 ：现在每次随机五条记录出来，插入到一个长度为十六的按空闲时间排序的队列里，然后把排头的那条删掉，然后再找五条出来，继续尝试插入队 列.........嗯，也就好了一点点吧，起码每次随机多了两条，起码不只在一次随机的五条里面找最久那条，会连同之前的一起做比较......

Memcached

相比之下，Memcached实现的是再标准不过的LRU算法，专门使用了一个教科书式的双向链表来存储slab内的LRU关系，代码在 item.c 里，详见 memcached源码分析-----LRU队列与item结构体 ，元素插入时把自己放到列头，删除时把自己的前后两个元素对接起来，更新时先做删除再做插入。分配内存不够时，很自然就会从LRU的队尾开始清理。

后来

不过后来再想想，也许Redis本来就不是主打做Cache的，这种内存爆了需要通过LRU删掉一些元素不是它的主要功能，默认设置都是noeviction——内存不够直接报错的，所以就懒得建个双向链表，而且每次访问时都要更新它了。

再瞄了一眼 Ehcache的Eviction算法 ，看文档居然和Redis2.6一样，直接随机15条记录，找出最旧那条......你是专门做Cache的呀，也这么懒。

另外，还看了下Memcached如何主动删除过期的数据，也就是那个文不对题的 LRU爬虫 ，和Redis的有点像，也是可以控制多久跑一次(默认100毫秒)，每次检查LRU队列中的N条数据，沿着列尾一直检查过去，比Redis的随机选择N条数据好一点。