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條數據好一點。