Redis算法（三）LFU 算法_redis lfu 概率因子

Redis算法（三）LFU 算法

Least Frequently Used，最不经常使用
redis中每个对象都有24 bits空间来记录LRU/LFU信息，LRU：24位的时钟，LFU：访问时间+访问频率（counter）、及16+8
counter并不是简单的线性计数器，而是用基于概率的对数计数器实现
概率分布计算公式为：

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

低8位最大值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;
  }
1
2
3
4
5
6
7
8
9

counter的衰减

衰减因子 server.lfu_decay_time 单位为分钟
如果一个key长时间没有访问，counter就会按衰减因子的值来减少

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;
}
1
2
3
4
5
6
7
8

衰减因子为1的情况下，N分钟没有访问，就要减N
配置中，概率因子和衰减因子的配置：
fu-log-factor 10
lfu-decay-time 1

参考 https://yq.aliyun.com/articles/278922