Redis中LFU算法的深入分析

2020-10-28 21:30:19

字體：大中小

來源：轉載

供稿：網友

前言

在Redis中的LRU算法文中說到，LRU有一個缺陷，在如下情況下：

~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|

會將數據D誤認為將來最有可能被訪問到的數據。

Redis作者曾想改進LRU算法，但發現Redis的LRU算法受制于隨機采樣數maxmemory_samples，在maxmemory_samples等于10的情況下已經很接近于理想的LRU算法性能，也就是說，LRU算法本身已經很難再進一步了。

于是，將思路回到原點，淘汰算法的本意是保留那些將來最有可能被再次訪問的數據，而LRU算法只是預測最近被訪問的數據將來最有可能被訪問到。我們可以轉變思路，采用一種LFU(Least Frequently Used)算法，也就是最頻繁被訪問的數據將來最有可能被訪問到。在上面的情況中，根據訪問頻繁情況，可以確定保留優先級：B>A>C=D。

Redis中的LFU思路

在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;

在LRU算法中，24 bits的lru是用來記錄LRU time的，在LFU中也可以使用這個字段，不過是分成16 bits與8 bits使用：

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

高16 bits用來記錄最近一次計數器降低的時間ldt，單位是分鐘，低8 bits記錄計數器數值counter。

LFU配置

Redis4.0之后為maxmemory_policy淘汰策略添加了兩個LFU模式：

volatile-lfu：對有過期時間的key采用LFU淘汰算法
allkeys-lfu：對全部key采用LFU淘汰算法

還有2個配置可以調整LFU算法：

lfu-log-factor 10lfu-decay-time 1

lfu-log-factor可以調整計數器counter的增長速度，lfu-log-factor越大，counter增長的越慢。

lfu-decay-time是一個以分鐘為單位的數值，可以調整counter的減少速度

源碼實現

在lookupKey中:

robj *lookupKey(redisDb *db, robj *key, int flags) {  dictEntry *de = dictFind(db->dict,key->ptr);  if (de) {    robj *val = dictGetVal(de);    /* Update the access time for the ageing algorithm.     * Don't do it if we have a saving child, as this will trigger     * a copy on write madness. */    if (server.rdb_child_pid == -1 &&      server.aof_child_pid == -1 &&      !(flags & LOOKUP_NOTOUCH))    {      if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {        updateLFU(val);      } else {        val->lru = LRU_CLOCK();      }    }    return val;  } else {    return NULL;  }}

當采用LFU策略時，updateLFU更新lru：

/* Update LFU when an object is accessed. * Firstly, decrement the counter if the decrement time is reached. * Then logarithmically increment the counter, and update the access time. */void updateLFU(robj *val) {  unsigned long counter = LFUDecrAndReturn(val);  counter = LFULogIncr(counter);  val->lru = (LFUGetTimeInMinutes()<<8) | counter;}

降低LFUDecrAndReturn

首先，LFUDecrAndReturn對counter進行減少操作：

/* If the object decrement time is reached decrement the LFU counter but * do not update LFU fields of the object, we update the access time * and counter in an explicit way when the object is really accessed. * And we will times halve the counter according to the times of * elapsed time than server.lfu_decay_time. * Return the object frequency counter. * * This function is used in order to scan the dataset for the best object * to fit: as we check for the candidate, we incrementally decrement the * counter of the scanned objects if needed. */unsigned long LFUDecrAndReturn(robj *o) {  unsigned long ldt = o->lru >> 8;  unsigned long counter = o->lru & 255;  unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;  if (num_periods)    counter = (num_periods > counter) ? 0 : counter - num_periods;  return counter;}

函數首先取得高16 bits的最近降低時間ldt與低8 bits的計數器counter，然后根據配置的lfu_decay_time計算應該降低多少。

LFUTimeElapsed用來計算當前時間與ldt的差值：

/* 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. */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) {  unsigned long now = LFUGetTimeInMinutes();  if (now >= ldt) return now-ldt;  return 65535-ldt+now;}

具體是當前時間轉化成分鐘數后取低16 bits，然后計算與ldt的差值now-ldt。當ldt > now時，默認為過了一個周期(16 bits，最大65535)，取值65535-ldt+now。

然后用差值與配置lfu_decay_time相除，LFUTimeElapsed(ldt) / server.lfu_decay_time，已過去n個lfu_decay_time，則將counter減少n，counter - num_periods。

增長LFULogIncr

增長函數LFULogIncr如下：

/* 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) {  if (counter == 255) return 255;  double r = (double)rand()/RAND_MAX;  double baseval = counter - LFU_INIT_VAL;  if (baseval < 0) baseval = 0;  double p = 1.0/(baseval*server.lfu_log_factor+1);  if (r < p) counter++;  return counter;}

counter并不是簡單的訪問一次就+1，而是采用了一個0-1之間的p因子控制增長。counter最大值為255。取一個0-1之間的隨機數r與p比較，當r<p時，才增加counter，這和比特幣中控制產出的策略類似。p取決于當前counter值與lfu_log_factor因子，counter值與lfu_log_factor因子越大，p越小，r<p的概率也越小，counter增長的概率也就越小。增長情況如下：

+--------+------------+------------+------------+------------+------------+
| factor | 100 hits   | 1000 hits | 100K hits | 1M hits    | 10M hits   |
+--------+------------+------------+------------+------------+------------+
| 0      | 104        | 255        | 255        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 1      | 18         | 49         | 255        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 10     | 10         | 18         | 142        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 100    | 8          | 11         | 49         | 143        | 255        |
+--------+------------+------------+------------+------------+------------+

可見counter增長與訪問次數呈現對數增長的趨勢，隨著訪問次數越來越大，counter增長的越來越慢。

新生key策略

另外一個問題是，當創建新對象的時候，對象的counter如果為0，很容易就會被淘汰掉，還需要為新生key設置一個初始counter，createObject:

robj *createObject(int type, void *ptr) {  robj *o = zmalloc(sizeof(*o));  o->type = type;  o->encoding = OBJ_ENCODING_RAW;  o->ptr = ptr;  o->refcount = 1;  /* Set the LRU to the current lruclock (minutes resolution), or   * alternatively the LFU counter. */  if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {    o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;  } else {    o->lru = LRU_CLOCK();  }  return o;}

counter會被初始化為LFU_INIT_VAL，默認5。

pool

pool算法就與LRU算法一致了：

    if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) ||      server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL)

計算idle時有所不同：

    } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {      /* When we use an LRU policy, we sort the keys by idle time       * so that we expire keys starting from greater idle time.       * However when the policy is an LFU one, we have a frequency       * estimation, and we want to evict keys with lower frequency       * first. So inside the pool we put objects using the inverted       * frequency subtracting the actual frequency to the maximum       * frequency of 255. */      idle = 255-LFUDecrAndReturn(o);

使用了255-LFUDecrAndReturn(o)當做排序的依據。

參考鏈接