Redis设计与实现第二部分：第9章：单机数据库的实现

9.1：服务器中的数据库

　　Redis服务器将所有的数据库都保存在服务器状态 redis.h/redisServer 结构的db数组中，db数组的每个项都是一个 redis.h/redisDb 结构，每个redisDb结构都是一个数据库：

 1 struct redisServer{
 2    
 3     //...
 4 
 5     //一个数组，保存着服务器中所有的数据库
 6     redisDb *db;
 7     
 8     //服务器数据库数量
 9     int dbnum;
10     //...
11 };

　　在初始化数据库时，程序会根据服务器状态的dbnum属性来决定应该创建多少个数据库，dbnum属性的值是由服务器配置的database选项决定，默认情况下，该选项值为16，所以Redis服务器会默认创建16个数据库，如下图所示：　　

9.2 切换数据库

　　每个Redis客户端都有自己的数据库目标，每当客户端执行数据库写命令或者数据库读命令的时候，目标数据库就会成为这些命令的操作对象。

　　默认情况下，Redis客户端的目标数据库为0号数据库，但客户端也可以通过执行 SELECT 命令切换目标数据库。

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

1 typedef struct redisClient{
2    
3     //...
4 
5     //记录当前客户端正在使用的数据库
6     redisDb *db;
7     
8     //...
9 }redisClient;

　　redisClient.db 指针指向 redisServer.db 数组的其中一个元素，而被指向的元素就是客户端的目标数据库。

　　通过修改redisClient.db 指针，让它指向服务器不同的数据库，从而实现切换目标数据库的功能，这就是SELECT命令的原理。

　　备注：Redis没有返回客户端目标数据库的功能。

9.3 数据库键空间

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

1 typedef struct redisDb{
2    
3     //...
4 
5     //数据库键空间，保存着数据库中所有的键值对。
6     dict *dict;
7     
8     //...
9 }redisDb;

9.3 读写键空间时的维护操作

　　当使用Redis命令对数据库进行读写操作时，服务器不仅会对键空间执行指定的读写操作，还会执行一些额外的操作，其中包括：

　　1. 在读取一个键之后（读操作和写操作都要对键进行读取），服务器都会根据键是否存在来更新服务器键的空间命中（hit）次数或键空间不命中（miss）次数，这两个值可以在INFO stats命令的 keyspace_hits 属性和 keyspace_misses 属性中查看。

　　2. 在读取一个键之后，服务器会更新键的LRU（最后一次使用）时间，这个值可以用于计算键的闲置时间，使用OBJECT idletime<key>命令可以查看键key的闲置时间。

　　3. 如果服务器在读取一个键时，发现这个键已经过期，那么服务器会先删除这个过期键，然后才执行其它操作。

　　4. 如果有客户端使用WATCH 命令监视了某个键，那么服务器在对被监视的键进行修改之后，会将这个过期键标记为 脏（dirty），从而让事务程序注意到这个键已经被修改。

　　5. 服务器每次修改一个键后，都会对 脏（dirty）键计数器的值增1，这个计数器会触发服务器的持久化已经复制操作。

　　6. 如果服务器开启了数据库通知功能，那么在对键进行修改之后，服务器将按配置发送响应的数据库通知。

9.4 设置键的生存时间或过期时间

　　通过 EXPIRE 命令或者 PEXPIRE 命令，客户端可以以秒或者毫秒精度为数据库中的某个键设置生存时间（Time To Live，TTL），在经过指定的秒数或者毫秒数之后买服务器就会自动删除生存时间为0 的键。

 1 redis> SET key value
 2 OK
 3 
 4 redis> EXPIRE key 5
 5 (integer) 1
 6 
 7 redis> GET key     //5秒之内
 8 "value"
 9 
10 redis> GET key     //5秒之后
11 (nil)

　　备注：SETEX 命令可以在设置一个字符串键的同时设置该键的过期时间，因为这个命令是一个类型限定命令（只能用于字符串键）。但是 SETEX 命令设置过期时间的原理和 EXPIRE 命令的原理是完全一样的。

　　与 EXPIRE 命令和 PEXPIRE 命令类似，客户端可以通过 EXPIREAT 命令和 PEXPIREAT 命令以秒或者毫秒精度为数据库中的某个键设置过期时间（expire time）。过期时间是一个 UNIX 时间戳，当键过期时间来临时，服务器就会字典从数据库删除这个键。

　　设置过期时间：

　　Redis有四个不同耳钉命令可以用于设置键的生存时间（键可以存在多久）或者过期时间（键什么时候可以删除）：

　　　　1. EXPIRE<key><ttl>命令用于将键key的生存时间设置为 ttl 秒。

　　　　2. PEXPIRE<key><ttl>命令用于将键key的生存时间设置为 ttl 毫秒。

　　　　3. EXPIREAT<key><timestamp>命令用于将键key的过期时间设置为 timestamp 所指定的秒数时间戳。

　　　　4. PEXPIREAT <key><timestamp>命令用于将键key的过期时间设置为 timestamp 所指定的毫秒数时间戳。

　　虽然有不同单位和不同形式的设置命令，但实际上 EXPIRE、PEXPIRE、EXPIREAT 三个命令都是使用PEEXPIREAT命令来实现的：无论客户端执行的是以上四个命令的哪一个，经过转换时候，最终的执行都和执行 PEXPIREAT 命令。

9.4 保存过期时间

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

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

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

 1 typedef struct redisDb{
 2    
 3     //...
 4 
 5     //数据库键空间，保存着数据库中所有的键值对。
 6     dict *dict;
 7     
 8     //过期字典，保存着键的过期时间
 9     dict *expires;
10     
11     //...
12 }redisDb;

　　备注：键空间保存了数据库中的所有键值对，而过期字典则保存了数据库键的过期时间。

　　示例：

　　备注：在实际中，键空间的键 和 过期字典中的键都是指向同一个键对象，所以不会造成内存浪费。

　　移除过期时间：

　　PERSIST 命令可以移除一个键的过期时间。PERSIST 命令就是 PEXPIREAT  命令的反操作：PERSIST 命令命令在过期字典中查找给定的键，并解除键和值（过期时间）在过期字典中的关联。

　　计算并返回剩余时间：

　　TTL 命令以秒为单位返回剪的剩余生存时间，而 PTTL 命令则以毫秒为单位返回键的剩余生存时间。TTL 命令和 PTTL 命令都是通过计算键的过期时间和当前时间之间的差来实现的。

　　过期键的判定：

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

　　1. 检查给定键是否存在与过期字典，如果存在，那么取得键的过期时间；

　　2. 检查当前 UNIX 时间戳是否大于键的过期时间，如果是的话，那么键已经过期，否则的话，键未过期。

9.5 过期键删除策略

　　数据键的过期时间都保存在过期字典中。如果一个键过期了，那么它什么时候会被删除呢？

　　三种不同的删除策略：

　　1. 定时删除（主动删除策略）：在设置键的过期时间的同时，创建一个定时器（timer），让定时器在键过期时间来临时，立即执行对键的删除操作。

　　2. 惰性删除（被动删除策略）：放任键过期不管，但是每次从键空间获取键时，都检查取得的键是否过期，如果过期的话，则删除该键；如果没有，则返回该键。

　　3. 定期删除（主动删除策略）：每隔一段时间，程序就对数据库进行一次检查，删除里面的过期键。置于要删除多少过期键，以及要检查多少数据库，则由算法决定。

　　下面介绍各自删除策略的特点：

　　1. 定时删除：优点：对内存是最友好的，通过使用定时器，定时删除策略可以保证过期键可以尽可能快的被删除，并释放过期键所占用的内存；缺点：对CPU时间是不友好的，在过期键比较多的情况下，删除过期键的行为可能占用相当一部分CPU的时间，在内存不紧张但是CPU时间非常紧张额情况下，将CPU时间用在删除和当前任务无关的过期键上，无疑会对服务器的响应时间和吞吐量造成影响。

　　例如，如果正有大量的命令请求正等待服务器处理，并且服务器当前不缺少内存，那么服务器应该优先将CPU时间用在处理客户端请求上面，而不是用在删除过期键上面。

　　除此之外，创建一个定时器需要用到Redis服务器中的时间事件，而当前时间事件的实现方式——无序链表，查找一个事件的时间复杂度为O(N)，——并不能高效的处理大量时间事件。

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

　　2. 惰性删除：优点：对CPU时间是最友好的，程序只会在取出键时才对键过期检查，这可以保证删除过期的键的操作是在非做不可的情况下进行，并且删除的目标仅限于当前的键，这个策略不会再删除其它的过期键上花费任何CPU时间。缺点：对内存是不友好的，如果一个键已经过期，而这个键仍然保存在数据库中，那么只要这个过期键不删除，它所占用的内存就不会被释放（除非用户手动执行 ELFUSHDB 命令）这可以视为 “内存泄漏” 的一种。

　　3. 定期删除：从上面对定时删除和惰性删除来看，这两种删除方式在单一使用时都有明显的缺陷：a. 定时删除占用太多CPU时间，影响服务器的响应时间和吞吐量。b. 惰性删除浪费太多内存，有内存泄漏的风险。

　　　定期删除策略是前两种策略的一种整合和折中：

　　　a. 定期删除策略每隔一段时间执行一次删除过期键操作，并通过限制删除操作的时长和频率来减少删除操作对CPU的影响。除此之外，通过定期删除过期键，定期删除策略有效的减少了因为过期键而带来的内存浪费。

　　　b. 定期删除策略的难点在于合理的设置删除操作的频率和时长。

9.6 Redis 的过期键删除策略

　　Redis 服务器实际采用的是惰性删除和定期删除两种策略：搭配使用，合理的使用CPU时间和避免浪费内存空间之间取得平衡。

　　惰性策略的实现：

　　过期键的惰性策略由 db.c/expireIfNeeded 函数实现，所有读写数据库的redis命令在执行之前都会调用  expireIfNeeded  函数对输入键进行检查：

　　1. 如果输入键已经过期，那么  expireIfNeeded  函数将输入键从数据库删除；

　　2. 如果输入键没有过期，那么  expireIfNeeded  不做动作；

　　 expireIfNeeded  函数就像一个过滤器，它可以在命令真正执行之前，过滤掉过期输入键，从而避免命令接触到过期键。

　　另外，因为每个被访问的键都有肯因为过期而被  expireIfNeeded  函数删除，所以每个命令的实现函数都必须能同时处理键存在和键不存在这两种情况：

　　1.当键存在时，命令按照键存在的情况执行。

　　2.当键不存在或者键因为过期而被  expireIfNeeded  函数删除时，命令按照键不存在的情况执行。

　　举例：GET 命令的执行过程。

　　定期策略的实现：

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

　　 activeExpireCycle  函数的工作模式可以总结如下：

　　1. 函数每次运行时，都从一定数量的数据库中取出一定数量的随机键进行检查，并删除其中的过期键。

　　2. 全局变量  current_db  会记录当前  activeExpireCycle  函数检查的进度，并在下一次   activeExpireCycle    调用时，接着上一次的进度进行处理。比如说，如果当前  activeExpireCycle   函数在遍历10号数据库返回了，那么下次   activeExpireCycle   函数执行时，将从11号数据库开始查找并删除过期键。

　　3. 随着   activeExpireCycle 函数的不断执行，服务器中的所有数据库都会被检查一遍，这时函数将current_db 变量重置为0，然后再次开始新一轮的检查工作。

9.7 AOF、RDB 和复制功能对过期键的处理

　　生成RDB文件

　　在执行  SAVE 命令或者 BGSAVE  命令创建一个新的 RDB  文件是，程序会对数据库中的键进行检查，已过期的键不会被保存到新创建的  RDB  文件中。