阅读 377

LRU算法及其优化策略——Redis篇

LRU算法及其优化策略——Redis篇 .jpg

上一篇文章中,分享了一些LRU基本算法及优化策略,本篇继续该主题,分享在Redis中LRU算法的使用和优化。

Redis 内存回收策略

在介绍Redis的LRU使用之前,我们需要先要了解一下Redis的内存回收策略。

Redis作为一个高性能的内存型的KV数据库,势必需要一个机制来控制Redis的内存占用,避免内存溢出。而和内存占用限制有关的配置即为maxmemory这个参数,通过动态调整该参数即可动态地限制Redis的内存占用。

Redis内存回收策略分为两个方面:

  • 删除过期键
  • 回收策略

删除过期键

Redis通过两种手段删除过期键:

  1. 惰性删除

    对于有过期时间的键,会在键上附加一个过期时间的时间戳,当客户端访问到该键时,会先检查过期时间戳,如果该键值已过期,则返回空,并删除该键。使用惰性删除可以避免维护过期时间的链表,但是如果一个过期键一直没有被访问,则有内存泄漏的问题。

  2. 定时任务删除

    为了避免惰性删除造成的内存泄漏,Redis会启动一个定时任务,默认为10s运行一次,该定时任务会随机从数据库中选取一些键并删除其中过期的键,如果发现其中超过25%的键都已过期,则重复执行一次该定时任务,直至随机扫描到的一批键中,过期键值的占比小于25%。

回收策略

当Redis的内存占用超过配置值时,就会执行驱逐政策,按照一定的规则驱逐旧数据,Redis可以配置六种回收策略:

  1. noeviction:拒绝所有的写入操作并返回Error,对读取操作没有影响。
  2. allkeys-lru:对所有的键执行LRU算法。
  3. volatile-lru:对所有有过期时间的键执行LRU算法。
  4. allkeys-random:对所有的键随机驱逐。
  5. volatile-random:对有过期时间的键随机驱逐。
  6. volatile-ttl:驱逐最快要过期的数据。

可以根据具体应用的数据访问方式及配合info命令计算出的缓存命中率来选择合适的驱逐策略。

我们可以看到有两条驱逐策略是和LRU相关的,而且Redis对LRU算法进行了一些优化。

近似LRU算法

原理

Redis 使用了一种基于采样的近似LRU算法来替代普通的LRU算法,从而避免普通的LRU算法带来的过高的资源消耗,而像Redis这样的程序,并不需要驱逐精确的那个最久没有访问的键。

简述:Redis随机采样一小部分键值,并选中其中最久没有访问的键,然后淘汰。

可以通过maxmemory-samples参数来配置每次采样的键数量,一般来说该值配置为5,当该值为10时就和普通的LRU算法的回收结果很接近,但是也会带来相应的资源消耗。Redis官网中有下面这么一个测试结果:

LRU测试.png

  • 浅灰色:被回收的数据
  • 深灰色:还没有被回收的数据
  • 绿色:最新插入的数据

左上角是普通的LRU的回收结果,因为只会插入和访问一次,所以就是按照先来后到的顺序,将旧数据依次的淘汰了。因为Redis3.0增加了一个驱逐池,所以可以看到3.0的回收效果要好与2.8的版本。而且可以看到,提高采样数量也能提高回收效果。

实现

1. LRU时钟

Redis中有一个全局的LRU时钟lruclock,该时钟记录了自服务启动后的LRU时间,并且该时钟每100ms更新一次。当客户端创建或访问键值时,都会根据这个全局的时钟更新键值自身的LRU时钟。

如此相当于每个键值都有一个访问时间的记录。

2. 执行回收策略的判断

在插入数据时,会先判断是否有足够的容量,如果没有,则执行回收策略,驱逐旧数据。此处我们指定为LRU相关的回收策略。

3. 驱逐池

一个驱逐池中的Entry的结构如下图所示:

#define REDIS_EVICTION_POOL_SIZE 16
struct evictionPoolEntry {
    unsigned long long idle;    /* Object idle time. */
    sds key;                    /* Key name. */
};
复制代码

其中idle即为空闲时间,key即为键值,空闲时间就是按照上面的LRU时钟计算的。驱逐池就是以Entry的idle为顺序组成组成的数组,一共有16个Entry。

当需要在驱逐池中插入一个键时,首先需要填充驱逐池,按照配置的采样参数从数据库中随机挑选几个键值,然后依次执行下面的操作。

该键值会依次比较驱逐池中寻找该键空闲时间大的键值:

  • 如果没有找到这样的键值,且驱逐池没有空位,则代表该插入的键值是空闲时间最小的键,所以该键并没有接入驱逐池的必要,所以直接跳过。
  • 如果找到了这样的键值,且驱逐池有空位,则直接插入到已有键值之前,以前的Entry移位。
  • 如果找到了这样的键值,而驱逐池没有空位,则在驱逐池中剔除掉空闲时间最小的键值后插入。

然后就到了真正删除键的逻辑了:

在驱逐池中,依次从空闲时间最长的键值开始删除,直到有足够的数据空间。

对这部分感兴趣的道友,可以去看下Redis的源码,主要是freeMemoryIfNeeded()方法evictionPoolPopulate()方法

源码地址

总结

本文介绍了Redis的内存回收策略及Redis近似LRU算法的原理和实现。从Redis对LRU算法的优化中,我们可以发现一个好的设计,并不是说要有多么准确,有时候可以在准确性和性能之间做权衡,以满足自己真正想要实现的功能。