过期删除策略: redis可以对key设置过期时间,因此要有相应的机制将已过期的键值对删除。
expire key time
这是最常用的方式setex key, seconds, value
字符串独有的方式如果未设置时间,那就是永不过期。 如果设置了过期时间,使用 persist key
让key永不过期。
每当我们对一个 key 设置了过期时间,Redis 会把该 key 带上过期时间存储到一个过期字典(expires dict)中,也就是说过期字典保存了数据库中所有 key 的过期时间。
过期字典存储在 redisDb 结构中,如下:
typedef struct redisDb { dict *dict; /* 存放着所有的键值对 */ dict *expires; /* 过期字典: 键和键的过期时间 */ .... } redisDb; /* 过期字典数据结构结构如下: 过期字典的 key 是一个指针,指向某个键对象; 过期字典的 value 是一个 long long 类型的整数,这个整数保存了 key 的过期时间; */
字典实际上是哈希表,哈希表的最大好处就是让我们可以用 O(1) 的时间复杂度来快速查找。
当我们查询一个 key 时,Redis首先检查该 key是否存在于过期字典中:
Redis 采用了 惰性删除 + 定期删除 的方式处理过期数据,以求在合理使用 CPU 时间和避免内存浪费之间取得平衡 。
Redis 为了保证定期删除不会出现循环过度,导致线程卡死现象,为此增加了定期删除循环流程的时间上限,默认不会超过 25ms(超过就停止检查)。
内存淘汰策略:redis 的运行内存已经超过redis设置的最大内存后,会使用内存淘汰策略删除符合条件的 key,以此来保障 Redis 高效的运行。
在配置文件 redis.conf 中,可以通过参数 maxmemory
来设定最大运行内存,只有在 Redis 的运行内存达到了我们设置的最大运行内存,才会触发内存淘汰策略。
不同位数的操作系统,maxmemory 的默认值是不同的:
Redis 内存淘汰策略共有八种,这八种策略大体分为「不进行数据淘汰」和「进行数据淘汰」两类策略
不进行数据淘汰的策略:
在设置了过期时间的数据中进行淘汰:
在所有数据范围内进行淘汰:
可以使用 config get maxmemory-policy 命令,来查看当前 Redis 的内存淘汰策略,命令如下:
127.0.0.1:6379> config get maxmemory-policy 1) "maxmemory-policy" 2) "noeviction"
Redis 使用的是 noeviction
类型的内存淘汰策略,它是 Redis 3.0 之后默认使用的内存淘汰策略,表示当运行内存超过最大设置内存时,不淘汰任何数据,但新增操作会报错。
设置内存淘汰策略有两种方法:
LRU全称是 Least Recently Used 翻译为 最近最少使用,会选择淘汰最近最少使用的数据
Redis 并没有使用这样的方式实现 LRU 算法,因为传统的 LRU 算法存在两个问题:
Redis 实现的是一种近似 LRU 算法,目的是为了更好的节约内存,它的实现方式是在 Redis 的对象结构体中添加一个额外的字段,用于记录此数据的最后一次访问时间。
当 Redis 进行内存淘汰时,会使用随机采样的方式来淘汰数据,它是随机取 5 个值(此值可配置),然后淘汰最久没有使用的那个。
Redis 实现的 LRU 算法的优点:
但是 LRU 算法有一个问题,无法解决缓存污染问题,比如应用一次读取了大量的数据,而这些数据只会被读取这一次,那么这些数据会留存在 Redis 缓存中很长一段时间,造成缓存污染。因此,在 Redis 4.0 之后引入了 LFU 算法来解决这个问题
LFU 全称是 Least Frequently Used 翻译为最近最不常用的,LFU 算法是根据数据访问次数来淘汰数据的,它的核心思想是"如果数据过去被访问多次,那么将来被访问的频率也更高"。所以, LFU 算法会记录每个数据的访问次数。当一个数据被再次访问时,就会增加该数据的访问次数。这样就解决了偶尔被访问一次之后,数据留存在缓存中很长一段时间的问题,相比于 LRU 算法也更合理一些.
LFU 算法相比于 LRU 算法的实现,多记录了「数据的访问频次」的信息。
Redis 对象的结构如下:
typedef struct redisObject { ... unsigned lru:24; // 24 bits,用于记录对象的访问信息 ... } robj;
Redis 对象头中的 lru 字段,在 LRU 算法下和 LFU 算法下使用方式并不相同。
在 LRU 算法中,Redis 对象头的 24 bits 的 lru 字段是用来记录 key 的访问时间戳,因此在 LRU 模式下,Redis可以根据对象头中的 lru 字段记录的值,来比较最后一次 key 的访问时间长,从而淘汰最久未被使用的 key。
在 LFU 算法中,Redis对象头的 24 bits 的 lru 字段被分成两段来存储,高 16bit 存储 ldt(Last Decrement Time),低 8bit 存储 logc(Logistic Counter)。
注意:logc并不是单纯的访问次数,而是访问频次(访问频率),因为logc会随时间推移而衰减的。
在每次 key 被访问时,会先对 logc 做一个衰减操作,衰减的值跟前后访问时间的差距有关系,如果上一次访问的时间与这一次访问的时间差距很大,那么衰减的值就越大,这样实现的 LFU 算法是根据访问频率来淘汰数据的,而不只是访问次数。访问频率需要考虑 key 的访问是多长时间段内发生的。key 的先前访问距离当前时间越长,那么这个 key 的访问频率相应地也就会降低,这样被淘汰的概率也会更大。
对 logc 做完衰减操作后,就开始对 logc 进行增加操作,增加操作并不是单纯的 + 1,而是根据概率增加,如果 logc 越大的 key,它的 logc 就越难再增加。
所以,Redis 在访问 key 时,对于 logc 是这样变化的: 先按照上次访问距离当前的时长,来对 logc 进行衰减; 然后,再按照一定概率增加 logc 的值
redis.conf 提供了两个配置项,用于调整 LFU 算法从而控制 logc 的增长和衰减: