redis(7)LRU缓存

一、LRU简介

LRU是Least Recently Used的缩写,即:最近最少使用。

它是内存管理中的一种页面置换算法,对于在内存中但是又不用的数据块,操作系统会根据哪些数据属于LRU而将其移除内存而腾出空间来加载另外的数据。

二、redis LRU

官方文章:https://redis.io/topics/lru-cache#using-redis-as-an-lru-cache

redis常常被用作缓存,当有新的数据进来的时候会自动驱逐旧的数据。LRU是memcached 默认的驱逐策略,在开发者当中也是常常被提及的。

1)最大内存配置

在redis LRU缓存使用中,你需要配置最大内存。最大内存的作用是限制redis的内存使用,当内存使用接近最大值的时候就会根据驱逐策略进行旧数据驱逐。

你可以通过redis.conf配置:

macmemory 100mb

当然新版的redis可以通过命令来配置你可以使用命令

config set maxmemory '100mb'

来配置

2)驱逐策略

最大内存限制了内存的使用以及临界值,那么驱逐策略则定义旧数据的驱逐方式,可用的策略有以下几种:

1、noeviction: 当接近最大值的时候报错

2、allkeys-lru: 移除所有keys中最近最少使用的key

3、volatile-lru: 移除所有携带过期时间(expire set)的keys中最少使用的key

4、allkeys-random: 随机移除所有key

5、volatile-random: 随机移除所有携带过期时间(expire set)的key

6、volatile-ttl: 移除携带过期时间(expire set),且剩余过期时间更短的key

3) 执行流程

1、当客户端发送一个命令,需要新增数据

2、服务端会检查内存使用情况,如将要大于限制,它就会根据驱逐策略驱逐key以释放空间;

3、新命令被执行,以此类推。

4)近似LRU算法

事实上,Redis LRU 算法并不完全是LRU算法的实现,只能说是接近于LRU算法。尤其是在3.0版本以后已经非常接近LRU算法了。

Redis LRU 算法不会计算出所有keys当中最接近的(因为会比较耗内存),而是从所有key当中挑选出样本,然后再挑选样本的算法基础上驱逐最接近的。

你可以配置样本的数量:

maxmemory-samples 5

我们看官方网站提供的一张对比图,LRU算法和Redis LRU算法的对比:

redis(7)LRU缓存

说明:1、绿色区域是新增数据;2、灰色区域是未驱逐数据;3、浅灰色区域是驱逐数据。

左上角是LRU算法,右上角是样本为10的Redis3.0 LRU算法,左下角是样本为5的Redis 2.8 LRU算法,右下角是样本为5的Redis3.0 LRU。

很明显,相同样本的情况下,3.0版本较2.8版本有了很大程度的进步,更接近LRU算法。

在3.0版本中样本为10较样本为5的情况来说已经非常接近LRU算法。

三、Redis LFU

从redis4.0开始,提供了一种新的策略LFU (Least Frequently Used eviction mode),意思就是根据历史的最少访问频率来决定驱逐的数据。这种策略的中心思想是认为,如果该数据历史访问频率很高,那么在未来的访问频率也会很高。

LFU有两种选择:

1)volatile-lfu: 从携带过期时间的keys中选择历史访问最少的key

2) allkeys-lfu: 从所欲keys中选择历史访问最少的key

四、LFU算法介绍:

在redis中每个对象都有24bits空间来记录LRU/LFU信息:

当这24bits用作LFU时,其被分为两部分:

1、高16位用来记录访问时间(单位:分钟)

2、低8位用来记录访问频率,简称(counter)

我们来看counter:基于概率的对数计数器

我们通常计数器就是直接递增,但redis的计数器只有8bits最大值也就是2^8 - 1 = 255 ,如果采用直接递增的方式那么最多只能记录255频率。

因此,redis在这里采用了概率对数的方法,在默认概率因子配置:lfu_log_factor = 10 的情况下,8bits可以表示100万的访问频率。

概率对数的算法让8bits可以记录很高的访问频率,但是如果计数器只做增长,就无法区分热点key。可能出现的情况就是即使长时间没有访问,它的访问频率依然很高。

针对这种情况,redis提供了一个衰减因子lfu_decay_time(单位:分钟),目的就是如果一个key长时间没有被访问那么计数器就要减少,减少的值由衰减因子来控制。

redis的衰减因子默认值为1,意思是如果N分钟没有被访问,那么计数器就减 1 * N。

上面的概率因子和衰减因子,redis都有默认值,当然也可以进行配置:

lfu-log-factor 10
lfu-decay-time 1

Redis LFU算法可以参考文章:https://yq.aliyun.com/articles/278922

上一篇:JAVA自学笔记17


下一篇:Redis做LRU缓存