过期删除策略

设置过期时间

  1. 只对key设置
1
2
3
4
expire key n // key在n秒后过期
pexpire key n // key在n毫秒后过期
expireat key n // key在时间戳n秒的时刻过期
pexpireat key n // key在时间戳n毫秒的时刻过期
  1. 创建key的时候设置
1
2
3
set key value ex n // 创建key，并且key在n秒后过期
set key value px n // 创建key，并且key在n毫秒后过期
set key n value // 创建key，并且key在时间戳n秒的时刻过期
  1. 查看某个key的存活时间
1
ttl key

判定key是否过期

1
2
3
4
typedef struct redisDb { 
    dict *dict; /* 数据库键空间，存放着所有的键值对 */ 
    dict *expires; /* 键的过期时间 */ .... 
} redisDb;

过期字典数据结构：

  • key 是一个指针，指向某个键对象
  • value 是一个 long long 类型的整数，这个整数保存了 key 的过期时间

alt text

判断策略：

  • 字典实际上是哈希表，哈希表的最大好处就是让我们可以用 O(1) 的时间复杂度来快速查找
  • 当我们查询一个 key 时，Redis 首先检查该 key 是否存在于过期字典中：
    1. 如果不在，则正常读取键值；
    2. 如果存在，则会获取该 key 的过期时间，然后与当前系统时间进行比对，如果比系统时间大，那就没有过期，否则判定该 key 已过期。

过期键删除策略

  • 定时删除：给key创建过期时间的同时创建一个定时器，在过期时间来临的时候进行主动删除。好处是删除及时使得内存空间释放，坏处是定时器占用CPU时间
  • 惰性删除：不主动删除过期键，每次从数据库访问 key 时，都检测 key 是否过期，如果过期则删除该key。好处是占用CPU时间少，坏处是容易造成内存泄漏
  • 定期删除：每隔一段时间随机从数据库中取出一定数量的 key 进行检查，并删除其中的过期key。平衡了CPU和内存占用
  • Redis采用的是最后两种，惰性删除和定期删除组合使用

Redis定期删除的流程

  1. 从过期字典中随机抽取 20 个 key
  2. 检查这 20 个 key 是否过期，并删除已过期的 key
  3. 如果本轮检查的已过期 key 的数量，超过 5 个（20/4），也就是「已过期 key 的数量」占比「随机抽取 key 的数量」大于 25%，则继续重复步骤 1；如果已过期的 key 比例小于 25%，则停止继续删除过期 key，然后等待下一轮再检查

内存淘汰策略

有哪些内存淘汰策略

alt text

  • noevction：不淘汰任何数据，如果运行内存超过了最大设置内存，会不允许写入
  • volatile：针对过期键
    • lru：淘汰最久未访问到的数据
    • lfu：淘汰使用频率最少的数据
    • random：随机淘汰
    • ttl：淘汰最久的过期键
  • allkeys：针对所有键
    • lru：淘汰最久未访问到的数据
    • lfu：淘汰使用频率最少的数据
    • random：随机淘汰

Redis的LRU算法

LRU，最近最久未使用算法：记录了每个key的最近访问时间，每次淘汰最久这个时间的key，但是redis的lru不是标准的，做了优化

优化：

  • 标准lru需要维护双链表，开销很大，所以redis采用的是近似LRU算法
  • 具体的是每次随机采样n个key，默认值是5，然后按照时间戳淘汰最久的那个。如果淘汰后内存还是不足继续随机采样淘汰。在3.0之后，redis LRU还维护了淘汰池，池中的数据按照访问时间进行排序。第一次随机选取的key都会放入池中，每次淘汰池中最久访问的key。
  • 随后每次选取的key只有空闲时间（指的是没有访问到的时候）大于池中空间时间最小的key，才能放入其中。当池子装满了，需要新的key放入的时候，就将池子中最大的key淘汰

Redis的LFU算法

LRU 算法有一个问题，无法解决缓存污染问题，比如应用一次读取了大量的数据，而这些数据只会被读取这一次，那么这些数据会留存在 Redis 缓存中很长一段时间，造成缓存污染

所以， LFU 算法会记录每个数据的访问次数。当一个数据被再次访问时，就会增加该数据的访问次数。这样就解决了偶尔被访问一次之后，数据留存在缓存中很长一段时间的问题，相比于 LRU 算法也更合理一些

LFU 算法相比于 LRU 算法的实现，多记录了「数据的访问频次」的信息。Redis 对象的结构如下：

1
2
3
4
5
6
typedef struct redisObject { 
    ... // 24 bits，
    用于记录对象的访问信息 unsigned lru:24; 
    ... 
} 
robj;

Redis对象头中的lru字段，在LRU算法下和LFU算法下使用方式并不相同:

  • 在 LRU 算法中，Redis对象头的24bits的lru字段是用来记录key的访问时间戳，因此在 LRU 模式下，Redis可以根据对象头中的lru字段记录的值，来比较最后一次key的访问时间长，从而淘汰最久未被使用的key
  • 在 LFU 算法中，Redis对象头的24bits的lru字段被分成两段来存储，高16bit存储ldt(Last Decrement Time)，低8bit存储logc(Logistic Counter)

alt text

lfu字段：

  • ldt:用来记录key的访问时间戳；
  • logc:用来记录key的访问频次，它的值越小表示使用频率越低，越容易淘汰，每个新加入的key的logc初始值为5
  • logc 并不是单纯的访问次数，而是访问频次（访问频率），因为 logc 会随时间推移而衰减的。
    在每次 key 被访问时，会先对 logc 做一个衰减操作，衰减的值跟前后访问时间的差距有关系，如果上一次访问的时间与这一次访问的时间差距很大 （ldt的作用），那么衰减的值就越大，这样实现的 LFU 算法是根据访问频率来淘汰数据的，而不只是访问次数。访问频率需要考虑 key 的访问是多长时间段内发生的。key 的先前访问距离当前时间越长，那么这个 key 的访问频率相应地也就会降低，这样被淘汰的概率也会更大。
    对 logc 做完衰减操作后，就开始对 logc 进行增加操作，增加操作并不是单纯的 + 1，而是根据概率增加，如果 logc 越大的 key，它的 logc 就越难再增加