Redis中内存数据淘汰机制

计算机硬件中，内存是一种十分昂贵的资源，而Redis又是一个相当消耗内存的数据库。Redis中有下列两种方式，使得写入内存的数据能够被清理：

• Redis数据过期机制
• Redis内存淘汰机制

简单介绍第一种方式，重点介绍第二种方式；

• Redis数据过期机制：

expire key time

该命令为key设置过期时间time，当经过time时间后。该key会存在下面三种过期机制：定时删除，惰性删除，定期删除；

需要注意 ：当我们把一批key-value数据存入到Redis中，底层会使用一张hash表对这些数据进行存储。此时如果我们对其中一些数据设置过期时间，那么底层还会单独将这些设置了过期时间的key-value数据用另一张的hash表进行保存；

• Redis内存淘汰机制

1.背景：

由于Redis数据过期机制存在着隐患：如果key没有及时过期，会造成内存使用值>maxmemory值。为了解决这个问题，内存淘汰机制就应运而生了。

2.配置信息：

#Redis设置的最大内存，当缓存内存大于这个值时，就会触发内存淘汰策略；
#设置为0表示不限制大小，64位的系统默认值为0，32位的系统默认内存限制为3GB;
maxmemory: 

#Redis内存的淘汰策略
maxmemory_policy: 

3.Redis内存淘汰策略：

• 内存淘汰策略即maxmemory_policy的赋值有以下几种：
  • noeviction : 当缓存内存值大于maxmemory值，如果此时客户端继续执行的写入内存命令，则向客户端返回错误响应；
  • volatile-lru : 对设置了过期时间的key进行lru淘汰 ;
  • allkeys-lru : 对所有的key都进行lru淘汰;
  • volatile-random : 对设置了过期时间的key进行随机淘汰;
  • allkeys-random : 对所有的key进行随机淘汰;
  • volatile-ttl ：在设置了过期时间的key中对具有更早过期时间的key优先移除；
• 适用场景：
  • noeviction ：Redis数据做持久化使用;
  • volatile-lru ：Redis数据一部分做缓存，一部分做持久化并且做缓存数据的key被访问的概率不一致；
  • allkeys-lru ：Redis数据做缓存使用，并且缓存数据的key被访问的概率不一致；
  • volatile-random : Redis数据一部分做缓存，一部分做持久化并且做缓存数据的key被访问的概率一致；
  • allkeys-random : Redis数据做缓存使用，并且缓存数据的key被访问的概率一致；

小结：由于Redis对设置过期时间的key会单独维护一张hash表，这会浪费服务器内存。所以在数据做缓存时，建议直接设置allkeys-lru策略。

4.RedisLRU算法：

• LRU算法：一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰；
• Redis内存淘汰策略中应用最多的是LRU算法，下面重点讲一下这个算法使用：

1.配置信息：

#Redis设置的最大内存，当缓存内存大于这个值时，就会触发数据淘汰策略；
#设置为0表示不限制大小，4位的系统默认值为0，32位的系统默认内存限制为3GB;
maxmemory: 

#Redis内存的淘汰策略
maxmemory_policy: allkeys-lru 

#LRU算法随机采样的精度，也就是随机取出key的数目。
#该数值配置越大, 越接近于真实的LRU算法，数值越大，相应消耗也变高，对性能有一定影响，样本值默认为5。
maxmemory_samples: 5

2.Redis LRU算法底层：

• 原生LRU算法和Redis LRU算法的比较？：

我们都知道，原生的LRU算法，需要一个双向链表来记录数据的最近被访问顺序。原生LRU算法在数据量多时，会造成大量的内存浪费。所以Redis使用的是一种近似的LRU算法，通过随机采样N个key(N个数由maxmemory_samples

控制)，回收其中最久未被访问的key值。所以当maxmemory_samples参数越大，LRU算法会越准确，伴随的开销也会越大。

• Redis LRU算法如何计算每个key的空闲时间？：

Redis为了实现近似LRU算法的key空闲时间计算，为每个key新增了一个24bit的字段，用来存储该key最后一次被访问的时间，这个时间称为key的LRU时钟；

typedef struct redisObject {
    ........
    #key的LRU时钟
    unsigned lru:24;
    ........
} robj;

Redis中还有一个全局的LRU时钟，同样也是一个24bit的字段

struct redisServer {
       //全局LRU时钟
       unsigned lruclock:24; 
       ...
};

由于24bit大小最多只能存储194天的数据，显然用lru字段和lruclock字段是无法存储操作系统完整的时间戳。所以Redis内部这两字段的计算公式 = Unix 时间戳 & (2^24-1) （取模操作）

#define LRU_BITS 24
#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1)
#define LRU_CLOCK_RESOLUTION 1000
 
unsigned int getLRUClock(void) {
    # mstime()结果是ms
    return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

1. key的空闲时间 = 全局LRU时钟 - key的LRU时钟 ( 全局LRU时钟 > key的LRU时钟 )
2. key的空闲时间 = 全局LRU时钟 + LRU_CLOCK_MAX - key的LRU时钟 ( 全局LRU时钟 <= key的LRU时钟 )

图1

• Redis LRU算法的优化？

Redis3.0对LRU算法进行了优化：新算法提供了一个键池（pool of keys），键池默认大小为16，键池中的key是按空闲时间排序的。当执行 N 个key（N由maxmemory_samples控制）随机采样时，只有采样key的idle time大于池中的idle time或者池中有空闲空间时，新key才会进入池，入池后key依然是按照空闲时间大小排序。

其实新算法提供键池本质就是提供一个缓冲池，使得空闲时间更大的key能够保留下，降低数据离散度；

通过一个实验对比各LRU算法的准确率，先往Redis里面添加一定数量的数据n，使Redis可用内存用完，再往Redis里面添加n/2的新数据，这个时候就需要淘汰一部分的数据，如果按照严格的LRU算法，应该淘汰掉的是最先加入的n/2的数据。

生成如下各LRU算法的对比图：

图1

浅灰色是被淘汰的数据
灰色是没有被淘汰掉的老数据
绿色是新加入的数据

参考资料：

• Redis中的LRU淘汰策略分析 - 再见紫罗兰 - 博客园 (cnblogs.com)
• Using Redis as an LRU cache – Redis