欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

redis系列之------数据库

程序员文章站 2022-08-19 19:06:40
前言 当我们在Redis数据库中set一个KV的时候,这个KV保存在哪里?如果我们get的时候,又从哪里get出来。时间复杂度,空间复杂的等等,怎么优化等等一系列问题。 服务器中的数据库 Redis服务器将所有数据库信息都保存在redis.h##redisService结构体中。代码如下: 列了几个 ......

前言

当我们在redis数据库中set一个kv的时候,这个kv保存在哪里?如果我们get的时候,又从哪里get出来。时间复杂度,空间复杂的等等,怎么优化等等一系列问题。

服务器中的数据库

redis服务器将所有数据库信息都保存在redis.h##redisservice结构体中。代码如下:

 1 struct redisserver {
 2 
 3     // ...
 4 
 5     /* general */
 6 
 7     // 配置文件的绝对路径
 8     char *configfile;           /* absolute config file path, or null */
 9 
10     // 数据库
11     redisdb *db;
12 
13      // 是否设置了密码
14     char *requirepass;          /* pass for auth command, or null */
15 
16     // pid 文件
17     char *pidfile;              /* pid file path */
18 
19     // tcp 监听端口
20     int port;                   /* tcp listening port */
21 
22    // ...
23 
24 }

列了几个,我认为比较重要的。其中最重要的,肯定是redisdb *db; 这个数据结构保存了我们所有的数据。

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

/* redis database representation. there are multiple databases identified
 * by integers from 0 (the default database) up to the max configured
 * database. the database number is the 'id' field in the structure. */
typedef struct redisdb {

    // 数据库键空间,保存着数据库中的所有键值对
    dict *dict;                 /* the keyspace for this db */

    // 键的过期时间,字典的键为键,字典的值为过期事件 unix 时间戳
    dict *expires;              /* timeout of keys with a timeout set */

    // 正处于阻塞状态的键
    dict *blocking_keys;        /* keys with clients waiting for data (blpop) */

    // 可以解除阻塞的键
    dict *ready_keys;           /* blocked keys that received a push */

    // 正在被 watch 命令监视的键
    dict *watched_keys;         /* watched keys for multi/exec cas */

    struct evictionpoolentry *eviction_pool;    /* eviction pool of keys */

    // 数据库号码
    int id;                     /* database id */

    // 数据库的键的平均 ttl ,统计信息
    long long avg_ttl;          /* average ttl, just for stats */

} redisdb;

其中最重要的就是 dict *dict; 他是一个字典,不太了解的小伙伴,可以看我前一篇的文章(https://www.cnblogs.com/wenbochang/p/11673590.html),对redis的字典有详细的介绍。

这个dict存储了我们真正的数据。

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

  • 键空间的键也就是数据库的键, 每个键都是一个字符串对象。
  • 键空间的值也就是数据库的值, 每个值可以是字符串对象、列表对象、哈希表对象、集合对象和有序集合对象在内的任意一种 redis 对象。

因为数据库的键空间是一个字典, 所以所有针对数据库的操作 —— 比如添加一个键值对到数据库, 或者从数据库中删除一个键值对, 又或者在数据库中获取某个键值对, 等等, 实际上都是通过对键空间字典进行操作来实现的。那么复杂度显而易见基本就是o(1)级别了,这也是redis为什么能这么快的一个重要原因。

 

对键取值

对一个数据库键进行取值, 实际上就是在键空间中取出键所对应的值对象。代码如下:

 1 /*
 2  * 返回字典中包含键 key 的节点
 3  *
 4  * 找到返回节点,找不到返回 null
 5  *
 6  * t = o(1)
 7  */
 8 dictentry *dictfind(dict *d, const void *key)
 9 {
10     dictentry *he;
11     unsigned int h, idx, table;
12 
13     // 字典(的哈希表)为空
14     if (d->ht[0].size == 0) return null; /* we don't have a table at all */
15 
16     // 如果条件允许的话,进行单步 rehash
17     if (dictisrehashing(d)) _dictrehashstep(d);
18 
19     // 计算键的哈希值
20     h = dicthashkey(d, key);
21     // 在字典的哈希表中查找这个键
22     // t = o(1)
23     for (table = 0; table <= 1; table++) {
24 
25         // 计算索引值
26         idx = h & d->ht[table].sizemask;
27 
28         // 遍历给定索引上的链表的所有节点,查找 key
29         he = d->ht[table].table[idx];
30         // t = o(1)
31         while(he) {
32 
33             if (dictcomparekeys(d, key, he->key))
34                 return he;
35 
36             he = he->next;
37         }
38 
39         // 如果程序遍历完 0 号哈希表,仍然没找到指定的键的节点
40         // 那么程序会检查字典是否在进行 rehash ,
41         // 然后才决定是直接返回 null ,还是继续查找 1 号哈希表
42         if (!dictisrehashing(d)) return null;
43     }
44 
45     // 进行到这里时,说明两个哈希表都没找到
46     return null;
47 }

 

看代码其实是很简单的。

  • 首先判断字典是否为空,如果为空,没有继续下去的必要了,直接return null
  • 第二步,如果在进行rehash,则先进行渐进式rehash。(不懂的,翻我上一篇博文)
  • 第三步,计算key的hash值。
  • 第四步,查找ht[0],ht[1]两张table表。其中如果是链表,则while循环查找即可。
  • 找到返回,没找到返回null。非常的简单清晰的逻辑。
  • 大致如下图:

 

           redis系列之------数据库

 

对键增加,删除,更新类似于查找。我就不一一列出源码了。

后言

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

  • 在读取一个键之后(读操作和写操作都要对键进行读取), 服务器会根据键是否存在, 以此来更新服务器的键空间命中(hit)次数或键空间不命中(miss)次数, 这两个值可以在 info stats 命令的 keyspace_hits 属性和 keyspace_misses 属性中查看。
  • 在读取一个键之后, 服务器会更新键的 lru (最后一次使用)时间, 这个值可以用于计算键的闲置时间, 使用命令 object idletime <key> 命令可以查看键 key 的闲置时间。
  • 如果服务器在读取一个键时, 发现该键已经过期, 那么服务器会先删除这个过期键, 然后才执行余下的其他操作。
  • 如果有客户端使用 watch 命令监视了某个键, 那么服务器在对被监视的键进行修改之后, 会将这个键标记为脏(dirty), 从而让事务程序注意到这个键已经被修改过。
  • 服务器每次修改一个键之后, 都会对脏(dirty)键计数器的值增一, 这个计数器会触发服务器的持久化以及复制操作执行。