Redis淘汰机制

说到Redis的内存淘汰机制,突然我联想到之前上大学时候的手机内存不够用的问题。记得那时候买的是16G的5s,🍎手机都知道,非常耐用,用了四年都不卡,所以手机里存了大量的东西,导致手机经常提示内存不够用。我就经常删除手机里的图片,当时我的策略就是将手机里最不重要的照片以及很少会用到的照片删除掉,现在想想当初买手机的时候真应该买内存大一些的了。其实这里我删除手机照片的思考方式就有点类似Redis的内存淘汰机制了。

删除策略

  • 定时删除:在设置键的过期时间的同时,创建一个定时器 timer). 让定时器在键的过期 时间来临时,立即执行对键的删除操作。
  • 惰性删除:放任键过期不管,但是每次从键空间中获取键时,都检查取得的键是否过 期,如果过期的话,就删除该键;如果没有过期,就返回该键。
  • 定期删除:每隔一段时间程序就对数据库进行一次检查,删除里面的过期键。至于要 删除多少过期键,以及要检查多少个数据库,则由算法决定。

淘汰策略

Redis的内存淘汰机制就是为了淘汰掉一些数据,保证Redis的正常服务。可以通过在配置文件中添加maxmemery-policy选择不同的淘汰策略,具体的策略有以下几种:

  • noeviction 不进行任何淘汰操作,当内存不够时写命令会报错
  • allkeys-lru 在所有的key中查找最近最少使用的key进行淘汰
  • volatile-lru 在设置过期时间的key中查找最近最少使用的key进行淘汰
  • allkeys-random 在所有的key中随机移除某个key
  • volatile-random 在设置了过期时间的key中随机移除某个key
  • volatile-ttl 在设置了过期时间的key中,删除过期时间最早的key
  • allkeys-lfu 在所有的key中查找最近访问频率最低的key进行淘汰(4.0版本)
  • volatile-lfu 在设置过期时间的key中查找最近访问频率最低的key进行淘汰(4.0版本)

备注
这里删除的key其实只删除一个,这是因为Redis在执行具有申请内存的命令时,会先判断内存是否超过maxmemery,如果超过了就会基于设置的maxmemery-policy策略删除key。

LRU算法

LRU(Least Recently Used)算法,即最近最少使用使用策略,淘汰掉最近最少使用的key。想要实现LRU算法很简单,只需要为每个key添加一个最近使用时间,在内存达到上限后,添加新的key时遍历所有key剔除空闲时间(idle time)最大的,访问频率最低的可以。或者可以使用另外一种方式,将所有的key放进一个队列中,如果达到内存上线,只需要将队尾的key剔除就行了。

不论是上述的哪种实现方式,如果直接运用在Redis中,都会影响性能,这显然与Redis的高性能相悖。所以Redis中采用是一种近似LRU算法。

lru算法由来

如下图所示,分别有四个key,~代表1秒的时间间隔,第一条线A为五秒钟访问一次,第二条线B为2秒钟访问一次,第三条线C为10秒钟访问一次,第四条线D同样为10秒钟访问一次,只不过和C起始时间点不一样。|表示同一时间点,lru算法在置换key的时候会剔除空闲时间最大的key。根据lru算法的原理得知,在|时刻,D的空闲时间(idle time)是最小的,代表下一次最有可能访问的key是D,但是从整体上来看B是即将访问的key,虽然这种情况下lru算法会出现miss情况,但是在绝大多数的情况下还是可以按照期望运行的。

这里为什么会用到置换一次呢,主要就是只有在新的key写入并且内存达到上线的时候才会出现剔除旧的key,所以置换一次就是用新的key替换旧的key。

~~~~~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|

为什么采用近似的LRU算法

redis中使用的LRU算法并不是真正的LRU算法,采用的是一种近似的LRU算法,如果每次添加key的时候查找所有key的最大空闲时间,显然在性能上会有所降低,本来这种剔除的策略就是一种概率的猜测,所以在选择最大的空闲时间key的时候,只要在概率上逼近真正lru算法就行了。过期算法是在redis2.8版本中加入的,并且在3.0中对其进行了优化。

下图对lru算法进行了一些比较,左上角是理想的lru算法效果。上层是改进版即3.0后的版本与理想的lru算法的一个比较,下面两张图是2.8版本与3.0版本进行的一个比较。那么需要怎么理解这个图呢?

在这个图里面分为三个区域

  • 最上层的浅灰色区域代表需要淘汰的key
  • 中间层深灰色区域代表是旧的key
  • 最下层绿色的区域代表的是新增的key

在了解这三个区域之后,那么怎样理解这个算法呢,在最上层区域中残留的深灰色点表示的是未被剔除的淘汰key,深灰色区域白色的点是被剔除掉的key,但是本来不应该被剔除掉,同理,浅绿色区域白色的点也是代表被剔除的key。lru算法的好坏程度就是是不是剔除了需要淘汰的key,在上图中可以看存储redis3.0算法是最接近理想的lru算法效果。

redis3.0中对lru算法的改进

在每次随机选取的key,都会放进一个poll(默认为16)缓存池中,这里面的key是根据每个key的空闲时间大小排序的,每次随机选择的key都需要和poll中最小的key进行比较,只有大于最小的空闲值才会被放入poll中,在每次剔除key的时候都会选择一个最大的空闲值来剔除。

一个redis实例中会有多个DB,对于每个DB都会创建一个poll淘汰缓存。为什么在这里单独提一下这个问题呢?在后面的LFU算法由来中会说道。

LFU算法

全称Least Frequently Used,与LRU不同的是,LFU是按照每个key访问频率进行淘汰的,随着时间的变化,每个key的访问频率会发生递减。

由来

Everything started from an open issue: when you have multiple databases
with Redis 3.2, the algorithm evicts making local choices. So
if for example you have all keys with a small idle time in DB number 0,
and all keys with large idle time in DB number 1, Redis will evict
one key from each DB. A more rational choice is of course to start
evicting keys from DB number 1, and only later to evict the other keys.

上面是来自作者antire写lru算法blog中的一段话,这段话的意思是当有两个DB时,一个DB全是空闲时间小的key,另一个DB全是空闲时间大的key,然而这个时候比较的是各自DB中的key数据,其实应该剔除的是空闲时间大的DB。后面作者提到,不管在lru的基础上怎么优化,在性能上都提高不了,所以作者后面就开始研究新的算法即LFU算法。具体作者怎么说的可以去看原文,原文链接

设计方案

为了实现LFU方案,将LRU算法中一个24bit字段(用来保存访问时间的)拆分成16bit和8bit,分别用来保存Last decr time(最近递减时间)以及LOC_C(访问次数)。

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

LFU设计源码

// LFU更新
void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);//首先计算是否需要将counter衰减
    counter = LFULogIncr(counter);//根据上述返回的counter计算新的counter
    val->lru = (LFUGetTimeInMinutes()<<8) | counter; //robj中的lru字段只有24bits,lfu复用该字段。高16位存储一个分钟数级别的时间戳,低8位存储访问计数
}
// counter增加
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;//counter最大只能存储到255,到达后不再增加
    double r = (double)rand()/RAND_MAX;//算一个随机的小数值,counter++是个概率事件🤣
    double baseval = counter - LFU_INIT_VAL;//新加入的key初始counter设置为LFU_INIT_VAL,为5.不设置为0的原因是防止直接被逐出
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);//server.lfu_log_facotr默认为10
    if (r < p) counter++;//可以看到,counter越大,则p越小,随机值r小于p的概率就越小。换言之,counter增加起来会越来越缓慢
    return counter;
}
// counter衰减
unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;//原来保存的时间戳
    unsigned long counter = o->lru & 255; //原来保存的counter
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    //server.lfu_decay_time默认为1,每经过一分钟counter衰减1
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;//如果需要衰减,则计算衰减后的值
    return counter;
}
// 获取分级别的时间
unsigned long LFUGetTimeInMinutes(void) {
    return (server.unixtime/60) & 65535;//获取分钟级别的时间戳
}

想要了解LFU算法,一定要先看这段源码,这段摘自思否的一篇文章(尊重原创)。

网上很多这段代码的注释,至于谁是原著不太了解,在这里我把学习时看到的原文放上去。

  1. counter更新
    更新的方法中主要有三行代码,第一行代码判断counter是否需要递减,第二行对counter进行增加,第三行,更新counter以及最新的时间。
  2. counter衰减
  3. counter增加
    在看源码的时候对于随机值p不是太理解,看到注释的时候才明白,原来counter值的增加也是一个概率事件,当counter越来越大的时候发生++的概率就越小。

lru、lfu算法测试

redis官方提供了一个测试工具来测试lru算法以及lfu算法的效果,我们可以根据测试的结果了解lfu算法带来的效果优化。

  1. config set maxmemory 50m
  2. config set maxmemory-policy allkeys-lru
  3. ./redis-cli -p 6380 --lru-test 1000000
  4. info 查看淘汰策略具体过程

建议自己操作下lru算法和lfu算法,比对测试结果。这里的测试命令好像只有lru-test,不存在lfu-test😧。

参考链接

  1. reids作者关于LRU算法的讲解
  2. redis源码分析