过期删除

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 的增长和衰减速度。

Dawn's Blogs

Redis学习 (10) 过期删除与内存淘汰