LFU算法在Redis中的实现机制和应用

算法 Redis

缓存

发布日期: 2020-04-30

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

LFU算法在Redis中的实现机制和应用

Redis 4.0提供了两种新的内存淘汰策略：

volatile-lfu：基于LFU算法对设置了过期时间的key进行删除
allkeys-lfu：基于LFU算法对所有的key进行删除

Redis 4.0.3正式支持基于LFU算法的热点key发现机制。

LFU数据结构

redisObject对象中的unsigned lru:LRU_BITS字段为24bit大小，用来记录LRU/LFU的信息。

记录LFU信息时：

0-15bit：last access time，即上次访问时间，单位分钟

16-24bit：LOG_C，即访问频率，简称counter，显然其最大为255

显然，LFU算法是通过对key的访问频率来筛选key，那么其内部实现就必然要能区分出不同key的访问频率。

counter

counter是一个基于概率的计数器，它的作用并非精准地记录某个key的访问次数。

实际上，在Redis源码中通过一个公式来对counter进行计算来体现key的访问次数。

公式 : 1 / (( counter - LFU_INIT_VAL ) * server.lfu_log_factor + 1)

其中LFU_INIT_VAL = 5 ，下文解释为什么该值为5。

server.lfu_log_factor是Redis配置项中的概率因子，默认为10，通过该公式的计算，可以记录较多的key访问次数。

//计算key的访问频率的源码
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;
  }

factor	100hits	1000hits	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

该表格来自于阿里云团队根据公式计算出的key访问次数与counter的关系，可以看到server.lfu_log_factor越大，就越能记录更高的key访问次数，当server.lfu_log_factor = 10时，counter可体现1百万次的key访问记录。

counter的衰减因子

实际上Redis运行中，所有存活已久的key的访问次数都在增加，counter最终都会收敛到255。

极端情况下，可能存在一些key从Redis第一次启动就存在，一直未消失，但被访问次数并不高，只是因为存活时间久，导致累计访问次数很高，其counter很容易收敛到255，这种情况下，给热点key的筛选带来了干扰。

即，counter只增长不衰减就无法区分热点key。

因此Redis提供了衰减因子server.lfu_decay_time，单位是分钟。

原理：如果一个key很长时间没有被访问，counter就应该减小，具体减小的程度由该衰减因子控制。

默认server.lfu_decay_time = 1，这种情况下，N分钟没有访问key，key的counter就减N。

业务中，使用默认值就可以。

为什么LFU_INIT_VAL = 5

由衰减因子可得，访问次数很大的key，但由于长时间不被访问，导致其counter变成很小，当counter衰减到0时，Redis淘汰该key。
理论上，新创建的key，其counter=0，因为从未被访问过，但这样会导致key被Redis误淘汰。

基于以上2点，对于新生成的key，LFU_INIT_VAL = 5，使得其在创建时counter!=0，其不在被创建时就立即被淘汰。

There is yet another problem, new keys need a chance to survive after
all. In vanilla LFU a just added key has an access score of 0, so it
is a very good candidate for eviction. In Redis new keys start with
an LFU value of 5. This initial value is accounted in the increment
and halving algorithms. Simulations show that with this change keys have
some time in order to accumulate accesses: keys with a score less than
5 will be preferred （non active keys for a long time）.