过期删除
Redis 可以设置 key 的过期时间,对于过期的 key,Redis 需要进行清理。
过期时间
当对一个 key 设置了过期时间,Redis 会把该 key 带上过期时间存储到一个过期字典(哈希表)中,过期字典保存了所有 key 的过期时间。所以在访问一个 key 时,可以在常数级时间复杂度查找 key 是否过期:
- 不在过期字典中,说明没有设置过期时间。
- 在过期字典中,获取过期时间,与系统当前时间进行比对是否过期。
删除策略
Redis 采用惰性删除+定期删除两种删除策略配合使用,以求在合理使用 CPU 时间和避免内存浪费之间取得平衡。
惰性删除
惰性删除中,不主动删除过期 key,只有当查询到过期 key 时才进行删除操作,删除可以选择异步删除或者同步删除。
惰性删除节省 CPU 时间,但是浪费内存。
定期删除
定期删除策略的做法是,每隔一段时间随机从数据库中取出一定数量的 key 进行检查,并删除其中的过期key。
定期删除相对于惰性删除更需要 CPU 资源,但是更加节约内存。
Redis 实现的定期删除需要解决两个问题:
- 定期检查间隔时间:默认每 10 秒钟检查一次,这是可以配置的。
- 随机抽查的数量:数量是写死在代码中的,数值是 20。
Redis 的定期删除的流程:
- 从过期字典中随机抽取 20 个 key;
- 检查这 20 个 key 是否过期,并删除已过期的 key;
- 如果本轮检查的已过期 key 的数量,比例大于 25%(5 个),则继续重复步骤 1;否则停止继续删除过期 key,然后等待下一轮再检查。
Redis 为了保证定期删除不会出现循环过度,导致线程卡死现象,为此增加了定期删除循环流程的时间上限,默认不会超过 25ms。
内存淘汰
Redis 可以通过设置 maxmemory
配置,来设定最大运行内存。不同位数的操作系统,maxmemory 的默认值是不同的:
- 在 64 位操作系统中,maxmemory 的默认值是 0,表示没有内存大小限制,直到 Redis 实例因内存不足而崩溃也无作为。
- 在 32 位操作系统中,maxmemory 的默认值是 3G,因为 32 位的机器最大只支持 4GB 的内存,而系统本身就需要一定的内存资源来支持运行,这样可以避免因为内存不足而导致 Redis 实例崩溃。
内存淘汰策略
Redis 内存淘汰策略共有八种,这八种策略大体分为「不进行数据淘汰」和「进行数据淘汰」两类策略。
不进行数据淘汰的策略
noeviction(Redis3.0之后,默认的内存淘汰策略) :它表示当运行内存超过最大设置内存时,不淘汰任何数据,这时如果有新的数据写入,会报错禁止写入(查询正常工作)。
进行数据淘汰的策略
针对「进行数据淘汰」这一类策略,又可以细分为「在设置了过期时间的数据中进行淘汰」和「在所有数据范围内进行淘汰」这两类策略。
在设置了过期时间的数据中进行淘汰:
- volatile-random:随机淘汰设置了过期时间的任意键值;
- volatile-ttl:优先淘汰更早过期的键值。
- volatile-lru(Redis3.0 之前,默认的内存淘汰策略):淘汰所有设置了过期时间的键值中,最久未使用的键值;
- volatile-lfu(Redis 4.0 后新增的内存淘汰策略):淘汰所有设置了过期时间的键值中,最少使用的键值;
在所有数据范围内进行淘汰:
- allkeys-random:随机淘汰任意键值;
- allkeys-lru:淘汰整个键值中最久未使用的键值;
- allkeys-lfu(Redis 4.0 后新增的内存淘汰策略):淘汰整个键值中最少使用的键值。
LRU 和 LFU
Redis 中的 LRU
Redis 并没有使用这样的方式实现 LRU 算法,因为传统的 LRU 算法存在两个问题:
- 需要用链表管理所有的缓存数据,这会带来额外的空间开销;
- 当有数据被访问时,需要在链表上把该数据移动到头端,如果有大量数据被访问,就会带来很多链表移动操作,会很耗时,进而会降低 Redis 缓存性能。
Redis 实现的是一种近似 LRU 算法,目的是为了更好的节约内存,它的实现方式是在 Redis 的对象结构体中添加一个额外的字段,用于记录此数据的最后一次访问时间。当 Redis 进行内存淘汰时,会使用随机采样的方式来淘汰数据,它是随机取 5 个值(此值可配置),然后淘汰最久没有使用的那个。Redis 实现的 LRU 算法的优点:
- 不用为所有的数据维护一个大链表,节省了空间占用;
- 不用在每次数据访问时都移动链表项,提升了缓存的性能;
但是 LRU 算法有一个问题,无法解决缓存污染问题,比如应用一次读取了大量的数据,而这些数据只会被读取这一次,那么这些数据会留存在 Redis 缓存中很长一段时间,造成缓存污染。
因此,在 Redis 4.0 之后引入了 LFU 算法来解决这个问题。
Redis 中的 LFU
LFU 算法会记录每个数据的访问次数,每次淘汰最少访问次数的数据。当一个数据被再次访问时,就会增加该数据的访问次数。LFU 算法解决了缓存污染问题。
Redis 实现
Redis 对象头中的 lru 字段为 24 bit,在 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)。
- ldt 用于记录 key 的上一次访问时间戳。
- logc 用于揭露 key 的访问频次,它的值越小表示使用频率越低,越容易淘汰,每个新加入的 key 的logc 初始值为 5。
logc 并不是单纯的访问次数,而是访问频次,会随着时间推移减小。
LRU 中,Redis 在访问 key 时,logc 是这样变化的:
先对 logc 做一个衰减操作,衰减的值跟前后访问时间的差距有关系,如果上一次访问的时间与这一次访问的时间差距很大,那么衰减的值就越大。
对 logc 进行增加操作,增加操作并不是单纯的 + 1,而是根据概率增加,如果 logc 越大的 key,它的 logc 就越难再增加。
Redis 提供了配置选项,可以控制 logc 的增长和衰减速度。