在LFU演算法中，可以為每個key維護一個計數器。每次key被訪問的時候，計數器增大。計數器越大，可以約等於訪問越頻繁。

上述簡單演算法存在兩個問題：

在LRU演算法中可以維護一個雙向連結串列，然後簡單的把被訪問的節點移至連結串列開頭，但在LFU中是不可行的，節點要嚴格按照計數器進行排序，新增節點或者更新節點位置時，時間複雜度可能達到O(N)。

只是簡單的增加計數器的方法並不完美。訪問模式是會頻繁變化的，一段時間內頻繁訪問的key一段時間之後可能會很少被訪問到，只增加計數器並不能體現這種趨勢。

第一個問題很好解決，可以借鑑LRU實現的經驗，維護一個待淘汰key的pool。第二個問題的解決辦法是，記錄key最後一個被訪問的時間，然後隨著時間推移，降低計數器。

Redis物件的結構如下：

typedef struct redisObject {

unsigned type:4;

unsigned encoding:4;

unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or

* LFU data (least significant 8 bits frequency

* and most significant 16 bits access time). */

int refcount;

void *ptr;

} robj;