Redis系列1：深刻理解高效能Redis的本質
 Redis系列2：資料持久化提高可用性
 Redis系列3：高可用之主從架構
 Redis系列4：高可用之Sentinel(哨兵模式）
Redis系列5：深入分析Cluster 叢集模式
 追求效能極致：Redis6.0的多執行緒模型
 追求效能極致：使用者端快取帶來的革命
 Redis系列8：Bitmap實現億萬級資料計算
 Redis系列9：Geo 型別賦能億級地圖位置計算
 Redis系列10：HyperLogLog實現海量資料基數統計
 Redis系列11：記憶體淘汰策略
 Redis系列12：Redis 的事務機制
 Redis系列13：分散式鎖實現
 Redis系列14：使用List實現訊息佇列
 Redis系列15：使用Stream實現訊息佇列
 Redis系列16：聊聊布隆過濾器（原理篇）
Redis系列17：聊聊布隆過濾器（實踐篇）
Redis系列18：過期資料的刪除策略
 Redis系列19：LRU記憶體淘汰演演算法分析

1 介紹

上一期我們介紹了 Redis系列19：LRU淘汰記憶體淘汰演演算法分析，大致瞭解了LRU(Least Rencently Used) 的演演算法原理，即將最近最久未使用的演演算法進行資料淘汰。
但是這樣的演演算法也有一些比較明顯缺陷：

穩定性和效能問題：LRU演演算法認為最近最少使用的資料是最該被淘汰的，但是這可能導致某些資料被頻繁地淘汰和載入，因為它們可能只在某個時間段內被使用一次，而在其他時間段內則不會被使用。這會使得快取的效率降低，增加了CPU和記憶體之間的通訊開銷。
空間問題：LRU演演算法需要維護一個連結串列來記錄資料的存取順序，這需要額外的空間。連結串列可能會佔用較大的空間，導致快取的效率降低。
存取順序問題：我們的存取順序並不一定是按照時間來的，而是有一定的規律。例如，我們在處理資料時可能會按照某個頻率存取資料，而不是按照時間順序。這種情況下，LRU演演算法可能會將某些我們還需要被存取資料淘汰掉。
資料侷限性問題：淘汰演演算法的本意是保留那些將來最有可能被再次存取的資料，而LRU演演算法只是預測最近被存取的資料將來最有可能被存取到。這樣太侷限，誤傷很多高頻被存取但某段時間空窗的資料。

如上圖，Key 1會被優先淘汰掉，但實際上，Key 1的存取頻率和可能行高很多，我們並不希望Key 1被淘汰，而是希望淘汰率是 Key 2 > Key 1
為了解決這些問題，一些改進的演演算法被提出來，例如LFU（Least Frequently Used）演演算法和FIFO（First In First Out）演演算法。這些演演算法在某些情況下比LRU演演算法更合理更有效。

2 實現原理

LFU(Least Frequently Used)是Redis 4.0 引入的淘汰演演算法，它通過key的存取頻率、存取時間比較來淘汰key，重點突出的是Frequently Used，用於在快取容量有限時決定哪些快取塊應該被清除。

LFU演演算法根據快取塊的使用頻率來決定哪些塊應該被清除。具體來說，它會記錄每個快取塊的使用次數，並按照使用次數從低到高排序。當快取達到容量上限時，LFU演演算法會選擇使用次數最少的快取塊進行清除，也就是最不經常使用的快取塊。

LFU演演算法的優點是能夠有效地防止快取溢位，並且能夠最大限度地減少清除重要資料的概率。但是，由於需要記錄每個快取塊的使用次數，因此LFU演演算法需要較大的記憶體空間，並且由於需要經常更新使用次數，因此其時間複雜度相對較高。

LFU演演算法常用於Web快取、資料庫快取、檔案系統快取等場景，用於提高系統的效能和穩定性。

實現原理如下：

LFU近似於LRU，使用概率計數器Morris計數器來估計每個物件的存取頻率，並結合衰變週期使計數器隨時間減少。這樣，即使在過去，我們也不再考慮頻繁存取的金鑰。因此，該演演算法可以適應存取模式的變化。
Redis4.0之後 maxmemory_policy 淘汰策略新增了兩個LFU模式：

allkeys-lfu：對全部key採用LFU淘汰演演算法進行計算
volatile-lfu：對設定了過期時間的key採用LFU淘汰演演算法

3 演演算法實現

3.1 從原始碼理解演演算法實現過程

在LFU模式下，Redis物件頭的24bit lru欄位被分成兩段來儲存。其中，高16bit用於儲存最後一次計數器降低的時間（ldt），低8bit用於儲存存取次數的對數值（logc）。

高16bit的ldt欄位用於記錄最近一次計數器降低的時間。由於只有16bit，它可以表示的最大值為65535（2^16-1）。由於時間以1秒為單位進行計數，因此大約每45.5天（65535/24/60）時間戳會折返重新從0開始。
低8bit的logc欄位用於記錄存取次數的對數值。由於只有8bit，它可以表示的最大值為255。實際上，logc無法記錄真實的Redis key的存取次數，因為每個新加入的key的logc初始值為5（LFU_INITI_VAL），這樣可以保證新加入的值不會被首先選中淘汰。每次存取key時，logc都會更新。

     16 bits      8 bits
+----------------+--------+
+ Last decr time | LOG_C  |
+----------------+--------+

Last Decrement Time計算的演演算法原始碼：

/* Return the current time in minutes, just taking the least significant
 * 16 bits. The returned time is suitable to be stored as LDT (last decrement
 * time) for the LFU implementation. */
// server.unixtime為Redis快取的Unix時間戳
// 使用的Unix的分鐘時間戳，取模2^16
unsigned long LFUGetTimeInMinutes(void) {
  return (server.unixtime/60) & 65535;
}
 
/* Given an object last access time, compute the minimum number of minutes
 * that elapsed since the last access. Handle overflow (ldt greater than
 * the current 16 bits minutes time) considering the time as wrapping
 * exactly once. */
unsigned long LFUTimeElapsed(unsigned long ldt) {
  // 獲取系統當前的LFU time
  unsigned long now = LFUGetTimeInMinutes();
  // 如果now >= ldt 直接取差值  
  if (now >= ldt) return now-ldt;
  // 如果now < ldt 增加上65535
  return 65535-ldt+now;
}

Redis Logistic Counter增長計算的原始碼：

/* Logarithmically increment a counter. The greater is the current counter value
 * the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
  // Logistic Counter最大值為255 （8位元的最大值）,  如果已經是最大值了，直接返回
  if (counter == 255) return 255;
  // 取一個0~1之間的亂數數
  double r = (double)rand()/RAND_MAX;
  // counter減去LFU_INIT_VAL （LFU_INIT_VAL為每個key的Logistic Counter基數值，預設為5）
  double baseval = counter - LFU_INIT_VAL;
  // 如果衰減之後counter已經小於基數（如5），那麼得出的結果 < 0，也取0
  if (baseval < 0) baseval = 0;
  // 可以看出如果lfu_log_factor的值越大，分母越大，得到的p越小
  double p = 1.0/(baseval*server.lfu_log_factor+1);
    // p 越小，r < p的可能性就越小，Logistic Counter增加的概率就越小
	// 綜上，lfu_log_factor越大增長越緩慢，緩解255空間緊張的問題
  if (r < p) counter++;
  return counter;
}

3.2 在redis.conf中開啟設定

可以修改redis.conf組態檔，設定maxmemory-policy volatile-lfu / allkeys-lfu 來進行開啟

# MAXMEMORY POLICY: how Redis will select what to remove when maxmemory
# is reached. You can select one from the following behaviors:
#
# volatile-lru -> Evict using approximated LRU, only keys with an expire set.
# allkeys-lru -> Evict any key using approximated LRU.
# volatile-lfu -> Evict using approximated LFU, only keys with an expire set.
# allkeys-lfu -> Evict any key using approximated LFU.
# volatile-random -> Remove a random key having an expire set.
# allkeys-random -> Remove a random key, any key.
# volatile-ttl -> Remove the key with the nearest expire time (minor TTL)
# noeviction -> Don't evict anything, just return an error on write operations.
#
# LRU means Least Recently Used
# LFU means Least Frequently Used
#
# Both LRU, LFU and volatile-ttl are implemented using approximated
# randomized algorithms.
#
# Note: with any of the above policies, when there are no suitable keys for
# eviction, Redis will return an error on write operations that require
# more memory. These are usually commands that create new keys, add data or
# modify existing keys. A few examples are: SET, INCR, HSET, LPUSH, SUNIONSTORE,
# SORT (due to the STORE argument), and EXEC (if the transaction includes any
# command that requires memory).
#
# The default is:
#
# maxmemory-policy noeviction
#
#
# 備註1：對設定了過期時間的key啟用LFU淘汰演演算法
# maxmemory-policy volatile-lfu
# 備註2：對全部key啟用LFU淘汰演演算法進行計算
# maxmemory-policy allkeys-lfu

4 總結

LFU(Least Frequently Used)是Redis 4.0 引入的淘汰演演算法，它通過key的存取頻率、存取時間比較來淘汰key，重點突出的是Frequently Used，用於在快取容量有限時決定哪些快取塊應該被清除。它避免了LRU淘汰演演算法明顯缺陷。

Redis系列20：LFU記憶體淘汰演演算法分析