当前位置： 移动技术网 > IT编程>数据库>Redis > Redis中LFU算法的深入分析

Redis中LFU算法的深入分析

2019年07月18日  | 移动技术网IT编程  | 我要评论

前言

在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 10
lfu-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)当做排序的依据。

参考链接

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对移动技术网的支持。

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网