redis学习笔记-策略LRU和LFU策略思想(之后会书写代码)

小鱼儿 2021-11-02 12:26 170阅读 0赞

最近在看<<redis实现与分析>>这本书,在学习redis之前，学长就建议我可以学习一下redis的淘汰策略 LRU　和　LFU　策略

LRU策略:使用和操作系统中的LRU近似的一种说法，在所有的key中找到一部分，找出其中距离现在访问最迟的key，并且淘汰

LRU行为配置参数:  
maxmemory , 缓存数据占用的内存限制，如果缓存的数据消耗的内存超过这个数值的限制的话，会触发数据淘汰  
maxmemory\_policy 淘汰策略，定义参与淘汰的数据的类型和属性  
maxmemory\_samples 随机采样的精度，配置越大，越接近LRU

Redis维护了24位时钟，每隔一段时间会更新这个时钟,每个key对象内部维护了一个２４位的时钟,新增的话会把系统的时钟赋值给这个内部对象时钟.我现在进行LRU,首先拿到当前的全局时钟，之后找出距离全局时钟距离时间最久的进行淘汰，全局时钟只有24位，key可能会超过24位，这个时候就把系统时钟和内部对象时钟相加，值最大的被淘汰

struct redisServer
    {
    ....
    unsigned lruclock:LRU_BITS;
    ...
    };
    typedef  struct object
    {
    ...
    lru:LRU_BITS;
    ....
    };

该计数器调用getLRUClock获取当前系统的毫秒数，作为LRU时间数，该计数器占用了24位,但是在这里如果超出24位就是超出194天之后，会重新赋值，  
Redis 中还有一个缓冲池的概念，当每一轮移除Ｋｅｙ的idle time , 如果它的idle time 比pool 里面idle time 最大的，并且 : pool 里面的key经过多轮筛选的，它的idle time 在概率上比随机获取的key的idle time 要大，pool里面的key　保留了　“历史经验消息”

LRU淘汰的场景:  
1.主动淘汰。  
1.1 通过定时任务serverCron定期的清理过期的key。  
2.被动淘汰  
2.1 每次写入key时，发现内存不够，调用activeExpireCycle释放一部分内存。  
2.2 每次访问相关的key，如果发现key过期，直接释放掉该key相关的内存。

LFU思想  
LFU起源于redis4.0后开始出现,LFU一般是用来淘汰之前的最久没有被访问过的key  
LFU的实现不难，就只是给每一个key挂一个计数器，我们就知道给定的key是不是比另外的key访问更多  
在LRU中，使用的是24bit控件，其中分为８位为计数器,16位记录递减时间  
一般来说８位很快会进行溢出，在这里redis采用了对数计数器

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越小，r < p的概率就越小  
在redis.conf 中有两个配置可以调整LFU算法

*  lfu-log-factor 　调整计数器的增长速度
 *  lfu-decay-time是一个以分钟为单位的数值，可以调整counter的减少速度

if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) 
    {
    updateLFU(val);
     } else {
        val->lru = LRU_CLOCK();
      }

每次采用LFU策略会同时更新lru

void updateLFU(robj *val) {
    
      unsigned long counter = LFUDecrAndReturn(val);
    
      counter = LFULogIncr(counter);
    
      val->lru = (LFUGetTimeInMinutes()<<8) | 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;
    
    }

首先取得高16bit的最近降低时间与低8bit的计数器counter ,之后计算应该降低多少  
LFUTimeElapsed用来计算当前时间与ldt的差值：

unsigned long LFUTimeElapsed(unsigned long ldt) {
    
      unsigned long now = LFUGetTimeInMinutes();
    
      if (now >= ldt) return now-ldt;
    
      return 65535-ldt+now;
    
    }

把当前时间转化为分钟后，取较低16位的bit ,然后计算出来与ldt之间的插值 ,如果ldt > now 的时候，默认过去一个周期，取值65535-ldt+now

然后用差值与配置lfu\_decay\_time相除，LFUTimeElapsed(ldt) / server.lfu\_decay\_time，已过去n个lfu\_decay\_time，则将counter减少n，counter - num\_periods