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

前言

当我们在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 命令对数据库进行读写时, 服务器不仅会对键空间执行指定的读写操作, 还会执行一些额外的维护操作, 其中包括:

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

已发表评论数()

相关站点

+订阅
热门文章