前言:

数据库键空间

Redis是一个键值对(key-value pair)数据库服务器，服务器中的每个数据库都由一个redis.h/redisDb结构表示，其中，redisDb结构的dict字典保存了数据库中所有键值对，我们将这个字典称为键空间(key space)。

typedef struct redisDb{

// ....

// 数据库键空间，保存着数据库中的所有键值对

dict *dicy;

// ...

} redisDb;

键空间和用户所见的数据库是直接对应的：

·键空间的键就是数据库的键，每个键都是一个字符串对象

·键空间的值就是数据库的值，每个值可以是字符串对象、列表对象、哈希对象、集合对象和有序集合对象中任意一种Redis对象。

数据库键空间例子

如上图，dict里保存着三种对象，List、String、Hash。

键空间操作

在Redis中对于键的增删改查都是基于键空间操作的，添加新键就是再增加一组键值，删除就是去除一组键值，更新就是替换键的值，对键取值就是通过key寻找value，复杂的对象操作会先取出value再进行进一步操作（比如取list前几位）。

除了上述的增删改查操作，用于清空整个数据库的FLUSHDB命令、用于随机返回数据库中某个键的RANDOMKEY命令等，都是通过对键空间进行操作来实现的。

过期键的实现&删除策略

Redis对于键过期的实现是通过expires过期字典实现的。

typedef struct redisDb{

// ....

// 数据库键空间，保存着数据库中的所有键值对

dict *expires;

// ...

} redisDb;

redisDb结构的expires字典保存了数据库中所有键的过期时间，我们称这个字典为过期字典。

·过期字典的键是一个指针，这个指针指向键空间中的某个键对象（也可以是某个数据库键）。

·过期字典的值是一个long long类型的整数，这个整数保存了键所指向的数据库键的过期时间（一个毫秒精度的UNIX时间戳）

带有过期字典的数据库例子

如图，在expires字典中保存了键的过期时间，过期时间的计算是用户设置的expireTime + 设置键值对的当前系统时间。

当取值的时候，就会取出这个ttl时间，跟当前系统时间对比，如果大于当前时间，说明还没有过期。如果小于当前时间，说明这个key已经失效了。

这个思路基本上和阿里巴巴开源缓存产品JetCache实现是一样的，JetCache是通过包装Holder对象将值和ttl存进Holder对象，然后取值的时候，取出Holder中的ttl进行与当前时间的对比。

笔者自己研发的内存缓存框架也是基于这个实现做的键过期。

那么对于失效的key，需要考虑失效key的删除策略。

Redis对于过期键的删除策略有三种：

1.定时删除

在设置键的过期时间的同时，创建一个定时器，让定时器在键的过期时间来临时，立即执行对键的删除操作。

通过使用定时器，定时删除策略可以保证过期键会尽可能快地被删除，并释放过期键所占用的内存。

定时删除策略对内存是最友好的，它能够保证键很及时的被删除，节省了内存空间。但是它对CPU不友好，因为当过期键大量存在时，删除过期键这一行为可能会占用相当一部分CPU事件，在内存不紧张但是CPU非常紧张的情况下，将CPU事件用在删除和当前任务无关的过期键上，无疑会对服务器的响应时间和吞吐量造成影响。

除此之外，创建一个定时器需要用到Redis服务器中的时间事件

时间事件：

一个时间事件由以下三个属性组成，

id，服务器为时间事件生成的全局唯一的ID（标志号）。该ID是自增的，即新的事件ID总是比旧事件ID要大。

when，毫秒精度的时间戳，记录了事件的到达（arrive）时间

timeProc，时间事件处理器，一个函数

时间事件无序链表

Redis 服务器将所有的时间事件都放在了一个无序列表中，每当时间事件执行器运行时，它就会遍历链表，查找所有已到达的时间事件，并调用相应的事件处理器。这是一个O(n)操作，并不能高效处理大量时间事件。

因此，要让服务器创建大量的定时器，从而实现定是删除策略，在现阶段来说并不现实。

（有个题外话是现在定时处理方面“时间轮”比较高性能，不知道redis作者基于什么考虑没有选择时间轮实现Timer事件。）

2.惰性删除

放任键过期不管，但是每次从键空间中获取键时，都检查所取得的键时候过期，如果过期的话，就删除该键；如果没有过期，就返回该键。

这是一个对CPU最友好的策略，这个策略不会在删除其他无关的过期键上花费任何CPU时间。

但是这个策略对内存最不友好，如果没有访问到这个键，将会一直存在在内存中，相当于一种内存泄漏了。

3.定期删除

每隔一段时间程序就对数据库进行一次检查，删除里面的过期键，至于要删多少检查多少，由算法决定。

折中方案，难点在于执行时长和频率

总结：

Redis采用键空间实现键值的增删改查

Redis中同时使用了惰性过期和定期过期两种过期策略。

参考书籍以及开源技术实现方案：

<Redis设计与实现>

<JetCache>

<Guava Cache>

<Caffeine Cache>