Redis实现-从键空间到过期策略

一、引言

Redis 是一个高性能的键值对数据库，其核心功能之一就是数据库的管理。每个 Redis 服务器可以包含多个数据库，每个数据库本质上是一个字典（键空间），存储着所有的键值对。除此之外，数据库还需要处理键的过期时间、持久化、通知等功能。

本文深入剖析 Redis 数据库的底层原理，包括服务器中数据库的表示、客户端切换数据库的机制、键空间的操作、过期键的处理策略、以及数据库通知的实现。

二、服务器中的数据库

Redis 服务器将所有数据库都保存在服务器状态 redisServer 结构的 db 数组中，db 数组的每个元素都是一个 redisDb 结构，代表一个数据库。

struct redisServer {
    // ...
    redisDb *db;          // 一个数组，保存着服务器中的所有数据库
    int dbnum;            // 服务器的数据库数量
    // ...
};

在服务器初始化时，程序会根据 dbnum 属性来决定创建多少个数据库。dbnum 的值由服务器配置的 database 选项决定，默认情况下该选项的值为 16，因此 Redis 服务器默认会创建 16 个数据库，编号从 0 到 15。如下图所示：

数据库

三、切换数据库

每个 Redis 客户端都有自己的目标数据库，默认情况下是 0 号数据库。客户端可以通过 SELECT 命令来切换目标数据库。例如：

redis> SET msg "hello world"
OK
redis> SELECT 2
OK
redis[2]> GET msg
(nil)

在服务器内部，客户端状态 redisClient 结构的 db 属性记录了客户端当前的目标数据库，它是一个指向 redisDb 结构的指针。

typedef struct redisClient {
    // ...
    redisDb *db;          // 指向当前正在使用的数据库
    // ...
} redisClient;

redisClient.db 指针指向 redisServer.db 数组中的某个元素，即被选中的数据库。如下图所示，客户端当前的目标数据库为 1 号数据库。

客户端指向数据库

当客户端执行 SELECT 2 时，服务器会修改 redisClient.db 指针，使其指向 redisServer.db 数组中的第 2 个元素（即 2 号数据库）。这就是 SELECT 命令的实现原理。

注意：

在多数据库程序中，需要谨慎处理。因为有些客户端（如 redis-cli）会显示当前数据库编号，但很多语言的客户端库并不显示。在执行危险命令（如 FLUSHDB）之前，最好先显式执行 SELECT 切换到正确的数据库，避免误操作。

四、数据库键空间

Redis 是一个键值对数据库，服务器中的每个数据库都由 redisDb 结构表示，其中最重要的属性是 dict 字典，它保存了数据库中所有的键值对。我们把这个字典称为键空间（key space）。

typedef struct redisDb {
    // ...
    dict *dict;          // 数据库键空间，保存着所有键值对
    // ...
} redisDb;

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

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

例如，执行以下命令后：

SET message "hello world"
RPUSH alphabet "a" "b" "c"
HSET book name "Redis in Action"
HSET book author "Josiah L. Carlson"
HSET book publisher "Manning"

数据库的键空间如下图所示：

键空间

4.1 添加新键

添加一个新键值对到数据库，就是在键空间字典中添加一个新键值对，其中键为字符串对象，值为任意类型的 Redis 对象。

例如，执行 SET date "2023-12-01" 后，键空间会添加一个新的键值对，如下图所示。

添加新键后的键空间

4.2 删除键

删除一个数据库键，就是在键空间中删除键所对应的键值对。

例如，执行 DEL book 后，键 book 及其值将从键空间中被删除，如下图所示：

删除键之后的空间

4.3 更新键

更新一个数据库键，实际上是对键空间中键对应的值对象进行更新。根据值对象的类型不同，更新的方法也不同。

例如，执行 SET message "blah blah" 后，message 键的值对象被更新，如下图所示：

更新键之后的键空间

4.4 对键取值

对一个数据库键进行取值，就是在键空间中取出键对应的值对象。

例如，执行 GET message，服务器会在键空间中查找键 message，找到后返回其值对象中的字符串，如下图所示：

对键取值

4.5 其他键空间操作

许多 Redis 命令都是通过对键空间进行处理来完成的，例如：

FLUSHDB：删除键空间中的所有键值对。
RANDOMKEY：从键空间中随机返回一个键。
DBSIZE：返回键空间中键值对的数量。
EXISTS、RENAME、KEYS 等命令也都是通过对键空间进行操作来实现的。

五、读写键空间时的维护操作

当使用 Redis 命令对数据库进行读写时，服务器不仅会执行指定的操作，还会执行一些额外的维护操作，这些操作对于服务器的正常运行非常重要：

更新键空间命中/不命中次数：在读取一个键之后，服务器会根据键是否存在来更新服务器的 keyspace_hits 或 keyspace_misses 统计信息，可以通过 INFO stats 命令查看。
更新键的 LRU 时间：在读取一个键之后，服务器会更新键的 LRU（最后一次使用）时间，这个值可以用于计算键的空转时长（通过 OBJECT idletime 命令查看），也用于内存淘汰策略。
删除过期键：如果服务器在读取一个键时发现该键已经过期，那么会先删除这个过期键，然后再执行后续操作（详见后文）。
标记脏键：如果客户端使用了 WATCH 命令监视了某个键，那么服务器在对被监视的键进行修改后，会将该键标记为脏（dirty），从而让事务程序注意到这个键已经被修改。
增加脏计数器：服务器每次修改一个键之后，都会将脏（dirty）计数器的值增加 1，这个计数器用于触发持久化操作（如 BGSAVE 的条件检查）。
发送数据库通知：如果服务器开启了数据库通知功能，那么在对键进行修改之后，会按配置发送相应的数据库通知（详见后文）。

这些维护操作确保了 Redis 服务器的各项功能能够正确运行。

六、设置键的生存时间或过期时间

Redis 提供了四个命令来设置键的生存时间（TTL）或过期时间：

EXPIRE <key> <ttl>：将键的生存时间设置为 ttl 秒。
PEXPIRE <key> <ttl>：将键的生存时间设置为 ttl 毫秒。
EXPIREAT <key> <timestamp>：将键的过期时间设置为 timestamp 指定的秒数时间戳。
PEXPIREAT <key> <timestamp>：将键的过期时间设置为 timestamp 指定的毫秒数时间戳。

6.1 设置过期时间

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

typedef struct redisDb {
    // ...
    dict *expires;       // 过期字典，保存着键的过期时间
    // ...
} redisDb;

过期字典的键是一个指针，指向键空间中的某个键对象；过期字典的值是一个 long long 类型的整数，保存了该键的过期时间（毫秒精度的 UNIX 时间戳）。下图展示了一个带有过期字典的数据库示例。

过期键

图中过期字典保存了两个键值对：

alphabet 键的过期时间为 1385877600000（2013年12月1日零时）。
book 键的过期时间为 1388556000000（2014年1月1日零时）。

当客户端执行 PEXPIREAT 命令（或其他转换命令）为一个数据库键设置过期时间时，服务器会在过期字典中关联给定的数据库键和过期时间。

6.2 移除过期时间

PERSIST 命令可以移除一个键的过期时间，它是 PEXPIREAT 的反操作：在过期字典中查找给定的键，并解除键和值的关联。如下图所示，执行 PERSIST book 后，过期字典中的 book 键值对被移除。

移除过期时间

6.3 计算并返回剩余生存时间

TTL 命令以秒为单位返回键的剩余生存时间，PTTL 命令以毫秒为单位返回。它们的实现都是通过计算键的过期时间和当前时间之间的差来完成的。伪代码如下：

def PTTL(key):
    if key not in redisDb.dict:
        return -2          // 键不存在
    expire_time = redisDb.expires.get(key)
    if expire_time is None:
        return -1          // 键没有设置过期时间
    now = get_current_unix_timestamp_in_ms()
    return expire_time - now

def TTL(key):
    ttl_ms = PTTL(key)
    if ttl_ms < 0:
        return ttl_ms
    else:
        return ms_to_sec(ttl_ms)

6.4 过期键的判定

通过过期字典，程序可以用以下步骤检查一个给定键是否过期：

检查给定键是否存在于过期字典：如果存在，取得键的过期时间。
检查当前 UNIX 时间戳是否大于键的过期时间：如果是，则键已过期；否则未过期。

伪代码如下：

def is_expired(key):
    expire_time = redisDb.expires.get(key)
    if expire_time is None:
        return False
    now = get_current_unix_timestamp_in_ms()
    return now > expire_time

七、过期键删除策略

如果一个键过期了，它什么时候会被删除呢？通常有三种可能的删除策略：

定时删除：在设置键的过期时间的同时，创建一个定时器，让定时器在键过期时立即执行删除操作。
惰性删除：放任键过期不管，但每次从键空间获取键时，检查取得的键是否过期，如果过期则删除。
定期删除：每隔一段时间，程序对数据库进行一次检查，删除里面的过期键。

Redis 服务器实际使用的是惰性删除和定期删除两种策略的结合。

7.1 惰性删除的实现

惰性删除策略由 expireIfNeeded 函数实现（位于 db.c）。所有读写数据库的 Redis 命令在执行之前都会调用 expireIfNeeded 对输入键进行检查：

如果输入键已经过期，则将其从数据库中删除。
如果输入键未过期，则不做动作。

命令调用 expireIfNeeded 的过程如下图所示。

expireIfNeeded流程

expireIfNeeded 就像一个过滤器，确保命令不会接触到过期键。同时，因为每个被访问的键都可能被删除，所以命令的实现函数必须能同时处理键存在和不存在两种情况。例如，GET 命令的执行过程如下图所示。

get命令流程

7.2 定期删除的实现

定期删除策略由 activeExpireCycle 函数实现（位于 redis.c）。每当 Redis 的服务器周期性操作 serverCron 函数执行时，activeExpireCycle 就会被调用。它在规定的时间内，分多次遍历服务器中的各个数据库，从过期字典中随机检查一部分键的过期时间，并删除其中的过期键。

其工作模式可以用伪代码描述如下：

// 每次检查的默认数据库数量
#define DEFAULT_DB_NUMBERS 16
// 每个数据库默认检查的键数量
#define DEFAULT_KEY_NUMBERS 20

// 全局变量，记录检查进度
int current_db = 0;

def activeExpireCycle():
    // 初始化要检查的数据库数量
    db_numbers = min(server.dbnum, DEFAULT_DB_NUMBERS)
    
    for i in range(db_numbers):
        if current_db >= server.dbnum:
            current_db = 0   // 重置，开始新一轮遍历
        
        redisDb = server.db[current_db]
        current_db += 1
        
        // 如果数据库没有过期键，跳过
        if redisDb.expires.size() == 0:
            continue
        
        for j in range(DEFAULT_KEY_NUMBERS):
            // 随机获取一个带有过期时间的键
            key_with_ttl = redisDb.expires.get_random_key()
            if is_expired(key_with_ttl):
                delete_key(key_with_ttl)
            
            // 如果已经达到时间上限，停止处理
            if reach_time_limit():
                return

函数每次运行时，会从一定数量的数据库中取出一定数量的随机键进行检查并删除。current_db 记录当前检查的进度，下一次调用时从该进度继续。随着函数的不断执行，所有数据库都会被检查一遍，然后重置。

这种策略将删除操作分散到多次执行中，避免了集中删除对服务器性能的影响，同时又保证了过期键不会长期占用内存。

7.3 两种策略的对比

策略	优点	缺点
惰性删除	对 CPU 时间最友好，只在访问时检查，不会额外占用 CPU	对内存不友好，过期键可能长期占用内存（类似内存泄漏）
定期删除	内存和 CPU 的折中，定期清理过期键，避免内存浪费	难以确定执行频率和时长，配置不当可能影响性能

Redis 通过结合两者，既保证了内存不被大量过期键浪费，又避免了频繁删除对 CPU 的影响。

#Redis

Redis实现-从键空间到过期策略

https://johnjoyjzw.github.io/2023/04/08/Redis实现-从键空间到过期策略/

Author

JiangZW

Posted on

April 8, 2023

Licensed under

微服务组件 -- 服务治理 Previous

Redis实现-持久化 Next