Redis--过期删除策略和数据淘汰策略

过期删除策略

Redis 的键过期后不会立即删除，而是通过定时删除、定期删除和惰性删除三种策略来管理过期键。这些策略旨在平衡性能和内存使用，避免系统资源的过度消耗。下面详细介绍这三种策略：

1. 定时删除（Timely Deletion）

解释：Redis 会为每个设置了过期时间的键创建一个定时器，当键过期时，定时器触发，Redis 会立即删除这个键。

优点：及时删除过期键，释放内存。

缺点：为每个键都设置定时器可能会消耗大量 CPU 和内存资源，特别是在有大量设置了过期时间的键时。

2. 定期删除（Periodic Deletion）

解释：Redis 默认每 100 毫秒会随机抽取一部分设置了过期时间的键进行检查，并删除已过期的键。这个检查过程是非阻塞的。

优点：控制了检查过期键的频率，避免了 CPU 过载。

缺点：可能会有一些过期键在检查前依然存在，未能及时删除，导致内存占用。

3. 惰性删除（Lazy Deletion）

解释：当客户端尝试访问一个键时，Redis 会检查这个键是否过期，如果过期则立即删除，并返回空结果。

优点：只在需要时才检查和删除过期键，开销较低。

缺点：如果某些过期键一直不被访问，它们会一直占用内存。

例子

假设你在 Redis 中设置了一个带有过期时间的键：

SET mykey "value"
EXPIRE mykey 10

在这之后，过期键的删除过程可能如下：

1. 定时删除：Redis 会为 mykey 设置一个定时器，10 秒后触发删除操作，但实际中 Redis 并没有采用这种策略。

2. 定期删除：假如当前系统的 100 毫秒周期检查到 mykey 已经过期，mykey 会被删除。

3. 惰性删除：如果在过期后的某个时间点，有客户端尝试访问 mykey，Redis 会检查发现 mykey 已经过期并立即删除它，然后返回空结果。

总结

Redis 使用定期删除和惰性删除相结合的策略来管理过期键。定期删除通过定期扫描的方式来减少过期键的数量，而惰性删除则确保了访问过期键时能够及时删除。这样设计的目的是在性能和内存之间找到一个平衡点，既能及时释放内存，又不会给系统带来过多的负担。

数据淘汰策略

Redis 实现数据淘汰策略主要通过配置文件 redis.conf 中的 maxmemory-policy 参数来控制。这个参数决定了当内存达到上限时，Redis 会如何淘汰数据。以下是几种常见的数据淘汰策略及其实现方式：

1. volatile-lru

策略解释：

• 从设置了过期时间的键中，选择最近最少使用（Least Recently Used, LRU）的键进行淘汰。

实现方式：

• 在 redis.conf 中设置：

maxmemory-policy volatile-lru

 例子： 假设 Redis 中有以下键：

SET key1 value1
EXPIRE key1 3600  # 设置 key1 的过期时间为 1 小时

SET key2 value2
EXPIRE key2 7200  # 设置 key2 的过期时间为 2 小时

当 Redis 的内存使用接近 maxmemory 设置的上限时，会优先淘汰那些设置了过期时间的键中最近最少被使用的键。例如，如果 key1 比 key2 更久没有被访问，那么 key1 可能会被淘汰。

2. allkeys-lru

策略解释：

• 从所有键中选择最近最少使用（LRU）的键进行淘汰，不考虑是否设置了过期时间。

实现方式：

• 在 redis.conf 中设置：

maxmemory-policy allkeys-lru

例子： 假设 Redis 中有以下键：

SET key1 value1
SET key2 value2

当 Redis 的内存使用接近 maxmemory 设置的上限时，不论是否设置了过期时间，都会优先淘汰最近最少被使用的键。例如，如果 key1 比 key2 更久没有被访问，那么 key1 可能会被淘汰。

3. volatile-ttl

策略解释：

• 从设置了过期时间的键中，选择即将过期（Time To Live, TTL）最短的键进行淘汰。

实现方式：

• 在 redis.conf 中设置：

maxmemory-policy volatile-ttl

例子： 假设 Redis 中有以下键：

SET key1 value1
EXPIRE key1 3600  # 设置 key1 的过期时间为 1 小时

SET key2 value2
EXPIRE key2 1800  # 设置 key2 的过期时间为 30 分钟

当 Redis 的内存使用接近 maxmemory 设置的上限时，会优先淘汰那些设置了过期时间的键中 TTL 最短的键。例如，key2 的 TTL 比 key1 的 TTL 更短，那么 key2 可能会被淘汰。

4. allkeys-random

策略解释：

• 从所有键中随机选择一个键进行淘汰。

实现方式：

• 在 redis.conf 中设置：

maxmemory-policy allkeys-random

例子： 当 Redis 的内存使用接近 maxmemory 设置的上限时，会随机选择一个键进行淘汰，没有特定顺序。

LRU（最近最少使用）

算法描述： LRU 算法基于这样的思想：如果数据最近被访问过，那么将来被访问的可能性也更大。因此，LRU 算法会优先淘汰最长时间未被访问的数据。

实现方式：

• 使用双向链表（Doubly Linked List）和哈希表（Hash Map）实现。哈希表用于快速查找，双向链表用于记录访问顺序。

应用场景：

• 缓存系统：在内存缓存中，LRU 可以有效地保留那些经常访问的数据，减少缓存命中率下降的可能性。
• 页面置换算法：操作系统中的页面置换算法（如虚拟内存管理）也可以使用 LRU 策略。

优点：

• 简单易实现。
• 适用于经常访问相同数据的场景。

缺点：

• 当访问模式突然变化时，LRU 可能会导致缓存命中率下降。

LFU（最不经常使用）

算法描述： LFU 算法基于这样的思想：如果数据在一段时间内被访问次数多，那么在未来一段时间内被访问的概率也较大。LFU 算法会优先淘汰访问频率最低的数据。

实现方式：

• 使用哈希表和优先队列（或最小堆）实现。哈希表用于快速查找，优先队列用于记录访问频率。

应用场景：

• 缓存系统：LFU 可以保留那些经常被访问的但是访问间隔较长的数据，适合访问模式稳定的场景。
• 数据库系统：在数据库查询优化中，LFU 可以帮助选择哪些查询语句应该被缓存。

优点：

• 能够保留那些长时间内访问频率稳定的数据。
• 可以在数据访问模式变化较大时，有更好的表现。

缺点：

• 实现复杂度较高，特别是在维护频率计数时需要额外的数据结构支持。
• 对于访问模式不稳定的数据，LFU 可能会导致缓存性能下降。

LRU 实现的数据结构

1. 双向链表（Doubly Linked List）：

   • 作用：用于记录数据的访问顺序，最近访问过的数据会移动到链表头部，最久未访问的数据位于链表尾部。
   • 操作：
     • 插入新数据到链表头部（表示最近访问过）。
     • 访问已存在的数据时，将数据移动到链表头部。
     • 当链表满时，移除链表尾部的数据（表示最久未访问）。

2. 哈希表（Hash Map）：

   • 作用：用于快速查找缓存中的数据，键为缓存的键，值为对应的链表节点。
   • 操作：
     • 插入新数据时，在哈希表中保存数据键和对应的链表节点。
     • 访问数据时，通过哈希表快速定位到链表中的节点，然后移动节点至链表头部。

LFU 实现的数据结构

1. 哈希表（Hash Map）：

   • 作用：用于存储缓存的键和对应的缓存数据。
   • 操作：
     • 插入新数据时，在哈希表中保存数据键和对应的缓存数据。
     • 访问数据时，更新数据的访问频率计数。

2. 优先队列（Priority Queue）或最小堆（Min-Heap）：

   • 作用：用于按照数据的访问频率来排序数据。
   • 操作：
     • 每次访问数据时，增加对应数据的访问频率计数。
     • 根据访问频率调整优先队列或最小堆中的数据顺序。
     • 当缓存空间不足时，移除访问频率最低（即最少访问）的数据。

总结

LRU 和 LFU 是两种常见的缓存淘汰策略，各自适合不同的应用场景和访问模式。在实际应用中，根据业务需求和系统特性选择合适的淘汰策略，可以有效提升缓存的命中率和系统性能。