Redis、Memcached、Guava、Ehcache中的算法

緩存那些事，一是內存爆了要用LRU(最近最少使用)、LFU(最少訪問次數)、FIFO的算法清理一些；二是設置了超時時間的鍵過期便要刪除，用主動或惰性的方法。

1. LRU

簡單粗暴的Redis

今天看Redis3.0的發行通告里說，LRU算法大幅提升了，就翻開源碼來八卦一下，結果哭笑不得，這舊版的"近似LRU"算法，實在太簡單，太偷懶，太Redis了。

在Github的Redis項目里搜索lru，找到代碼在redis.c的freeMemoryIfNeeded()函數里。

先看2.6版的代碼： 竟然就是隨機找三條記錄出來，比較哪條空閑時間最長就刪哪條，然后再隨機三條出來，一直刪到內存足夠放下新記錄為止.......可憐我看配置文檔后的想象，一直以為它會幫我在整個Redis里找空閑時間最長的，哪想到我有一百萬條記錄的時候，它隨便找三條就開始刪了。

好，收拾心情再看3.0版的改進：現在每次隨機五條記錄出來，插入到一個長度為十六的按空閑時間排序的隊列里，然后把排頭的那條刪掉，然后再找五條出來，繼續嘗試插入隊列.........嗯，好了一點點吧，起碼每次隨機多了兩條，起碼不只在一次隨機的五條里面找最久那條，會連同之前的一起做比較......

中規中矩的Memcached

相比之下，Memcached實現的是再標準不過的LRU算法，專門使用了一個教科書式的雙向鏈表來存儲slab內的LRU關系，代碼在item.c里，詳見memcached源碼分析-----LRU隊列與item結構體，元素插入時把自己放到列頭，刪除時把自己的前后兩個元素對接起來，更新時先做刪除再做插入。

分配內存超限時，很自然就會從LRU的隊尾開始清理。

同樣中規中矩的Guava Cache

Guava Cache同樣做了一個雙向的Queue，見LocalCache中的AccessQueue類，也會在超限時從Queue的隊尾清理，見evictEntries()函數。

和Redis一樣懶的Ehcache

看文檔，居然和Redis2.6一樣，直接隨機8條記錄，找出最舊那條，刷到磁盤里，再看代碼，Eviction類 和 OnHeapStore的evict()函數，的確如此。

小結

不過后來再想想，也許Redis本來就不是主打做Cache的，這種內存爆了需要通過LRU刪掉一些元素不是它的主要功能，默認設置都是 noeviction——內存不夠直接報錯的，所以就懶得建個雙向鏈表，而且每次訪問時都要更新它了，看Google Group里長長的討論，新版算法也是社區智慧的結晶。但Ehache是專門做Cache的呀，也這么懶。

2. 過期鍵刪除

如果能為每一個設置了過期的元素啟動一個Timer，一到時間就觸發把它刪掉，那無疑是能最快刪除過期鍵最省空間的，在Java里用一條DeplayQueue存著，開條線程不斷的讀取就能做到。但因為該線程消耗CPU較多，在內存不緊張時有點浪費，似乎大家都不用這個方法。

所以有了惰性檢查，就是每次元素被訪問時，才去檢查它是否已經超時了，這個各家都一樣。但如果那個元素后來都沒再被訪問呢，會永遠占著位子嗎？所以各家都再提供了一個定期主動刪除的方式。

Redis

代碼在redis.c的activeExpireCycle()里，看過文檔的人都知道，它會在主線程里，每100毫秒執行一次，每次隨機抽20條Key檢查，如果有1/4的鍵過期了，證明此時過期的鍵可能比較多，就不等100毫秒，立刻開始下一輪的檢查。不過為免把CPU時間都占了，又限定每輪的總執行時間不超過1毫秒。

Memcached

Memcached里有個文不對題的LRU爬蟲線程，利用了之前那條LRU的隊列，可以設置多久跑一次(默認也是100毫秒)，沿著列尾一直檢查過去，每次檢查LRU隊列中的N條數據。雖然每條Key設置的過期時間可能不一樣，但怎么說命中率也比Redis的隨機選擇N條數據好一點，但它沒有Redis那種過期的多了立馬展開下一輪檢查的功能，所以每秒最多只能檢查10N條數據，需要自己自己權衡N的設置。

Guava Cache

在Guava Cache里，同一個Cache里所有元素的過期時間是一樣的，所以它比Memached更方便，順著之前那條LRU的Queue檢查超時，不限定個數，直到不超時為止。而且它這個檢查的調用時機并不是100毫秒什么的，而是每次各種寫入數據時的preWriteCleanup()方法中都會調用。

吐槽一句，Guava的Localcache類里面已經4872行了，一點都不輕量了。

Ehcache

Ehcache更亂，首先它的內存存儲中只有惰性檢查，沒有主動檢查過期的，只會在內存超限時不斷用近似LRU算法(見上)把內存中的元素刷到磁盤中，在文件存儲中才有超時檢查的線程，FAQ里專門解釋了原因。

然后磁盤存儲那有一條8小時左右跑一次的線程，每次遍歷所有元素.....見DiskStorageFactory里的DiskExpiryTask。 一圈看下來，Ehcache的實現最弱。