相关链接

redis LRU策略分析：https://www.cnblogs.com/linxiyue/p/10945216.html

redis LFU策略分析：https://www.cnblogs.com/linxiyue/p/10955533.html

redis LRU伪代码演示：https://github.com/mailjobblog/dev_redis/blob/master/LRU/LRU_Cache.php

内存淘汰策略

  1. noeviction：当内存使用超过配置的时候会返回错误，不会驱逐任何键
  2. allkeys-lru：加入键的时候，如果过限，首先通过LRU算法驱逐最久没有使用的键
  3. volatile-lru：加入键的时候如果过限，首先从设置了过期时间的键集合中驱逐最久没有使用的键
  4. allkeys-random：加入键的时候如果过限，从所有key随机删除
  5. volatile-random：加入键的时候如果过限，从过期键的集合中随机驱逐
  6. volatile-ttl：从配置了过期时间的键中驱逐马上就要过期的键
  7. volatile-lfu：从所有配置了过期时间的键中驱逐使用频率最少的键
  8. allkeys-lfu：从所有键中驱逐使用频率最少的键

LRU和LFU的区别

LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面!

LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页!

LRU

举例如下的访问模式，A每5s访问一次，B每2s访问一次，C与D每10s访问一次，|代表计算空闲时间的截止点：

~~~~~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对于A、B、C工作的很好，完美预测了将来被访问到的概率B>A>C，但对于D却预测了最少的空闲时间。

但是，总体来说，LRU算法已经是一个性能足够好的算法了

图解说明

  • 新数据插入到链表头部
  • 每当缓存命中（即缓存数据被访问），则将数据移到链表头部
  • 当链表满的时候，将链表尾部的数据丢弃

LRU Cache具备的操作：

  • set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除，并移动到链表的头部；若果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除即可。
  • get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。

LRU配置参数

Redis配置中和LRU有关的有三个：

  • maxmemory: 配置Redis存储数据时指定限制的内存大小，比如100m。当缓存消耗的内存超过这个数值时, 将触发数据淘汰。该数据配置为0时，表示缓存的数据量没有限制, 即LRU功能不生效。64位的系统默认值为0，32位的系统默认内存限制为3GB
  • maxmemory_policy: 触发数据淘汰后的淘汰策略
  • maxmemory_samples: 随机采样的精度，也就是随即取出key的数目。该数值配置越大, 越接近于真实的LRU算法，但是数值越大，相应消耗也变高，对性能有一定影响，样本值默认为5。

LFU

示例图展示

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

在上面的情况中，在一定时期内，根据访问频繁情况，可以确定保留优先级：B>A>C=D。

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的减少速度

内存淘汰策略的选择

个人观点

我们在选择使用淘汰策略的时候可以根据访问key的方式来选择不同的淘汰策略

1、当我们redis中的key基本上都有用到，也就是说每个key都有周期性访问到，那就可以选择使用random策略

2、当我们redis中的key部分是我们经常访问的，部分是非经常访问的就可以考虑使用LRU和LFU策略

3、当我们想根据时间长久淘汰超时数据时，就选用ttl

4、我们根据我们的需要是否有要长久保存的key来选择volatile或者是all，如果有需要长久保存的key，则使用volatile，否则可以使用all全表扫描