转载

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的队尾开始清理。