关于redis:redis-存储结构原理-2

咱们接着上一部分来进行分享，咱们能够在如下地址下载 redis 的源码：

https://redis.io/download

此处我下载的是 redis-6.2.5 版本的，xdm 能够间接下载上图中的 redis-6.2.6 版本，

redis 中 hash 表的数据结构

redis hash 表的数据结构定义在：

redis-6.2.5\src\dict.h

哈希表的构造，每一个字典都有两个实现从旧表到新表的增量重哈希

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

table：

table 是一个二级指针，对应这一个数组，数组中的每个元素都是指向了一个 dictEntry 构造体指针的，dictEntry 具体的数据结构是保留一个键值对

具体的 dictEntry 数据结构是这样的：

size：

size 属性是记录了整个 hash 表的大小，也能够了解为上述 table 数组的大小

sizemask：

sizemask 属性，和具体的 hash 值来一起决定键要放在 table 数组的哪个地位

sizemask 的值，总是会比 size 小 1，咱们能够来演示一下

应用取余的形式，实际上是很低效的，咱们的计算机是不会做乘除法的，同样都是用加减法来进行解决的，为了高效解决，咱们能够应用二进制的形式

应用二进制的形式，就会用到该字段 sizemask，次要是用来 和 具体的 hash 值做按位与操作

如图就很明确了，size = 4，sizemask = 3，hash 值为 7，最初 hash 值 & sizemask = 0011，也就是 3，因而就会插入到上图的具体位置

used：

used 属性示意 hash 表外面曾经有 键值对的数量

对于上述的案例，能够用一个简图来示意一下 hash 表构造 dictht

dictEntry 构造每个属性的含意

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

下面咱们看到数组中的节点信息，是 dictEntry 构造，属性别离是这些意思：

• key

  具体的 redis 键

• union v

  • val

    指向不同类型的数据，此处是 void *，应用该类型，是为了节俭内存

  • u64

    用于 redis 集群中的哨兵模式和选举模式

  • s64

    记录过期工夫的

• next

  指向下一个节点的指针

dict 构造

在 src\dict.h 文件 中，咱们接着往下看，可能看到一个十分要害的构造，就是 dict，redis 中都是应用这个构造来进行组织的

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

• type

字段对应的操作函数，具体有哪些操作函数，咱们能够看到typedef struct dictType 给出的信息

• privdata

字典依赖的数据，例如 redis 具体的操作等等

• ht[2]

hash 表的键值对，放在此处，一个旧的，一个新的

ht[0]：是扩容前的数组

ht[1]：是扩容后的数组

这个是当数据量大的时候，用于渐进式 rehash 的

• rehashidx

来指定具体 rehash 的地位，对应到 ht[0] 的索引上，rehashidx == -1，就是没有进行再 hash，rehashidx != -1 时，阐明正在进行再 hash

还记得咱们之前说到 redis 有 16 个 db 吗？

咱们在 redis 源码中 src\server.h 也可能看到 redisdb 的数据结构

咱们能够看到 dict 这个字典，是 redis 中应用是相当频繁和要害的

下面有说到 ht[2] 会用在渐进式 rehash 上，那么为什么要用渐进式 rehash 以及他是如何做的？

扩容的时候，会触发 rehash

当数据量很大的时候，会波及到扩容，若一次性从 ht[0] 拷贝到 ht[1] 是比较慢的，会阻塞其余操作，那么就没有方法解决其余申请了，因为 redis 是单线程解决工作的

ht[0] 数据拷贝到 ht[1] 的形式一

是这样进行 rehash 的：

扩容的时候，rehash 是这样做的：

• 先会对上述说到的 ht[1] 开拓内存空间，会将 ht[0].size * 2 给到 ht[1]
• 而后再将 ht[0] 的数据，从 ht[0][0] ... ht[0][size-1] 将数据拷贝到 ht[1] 外面

如何做到渐进式呢？

应用分而治之的思维，无论 redis 目前是否在做长久化的时候 ，当咱们每次操作 redis 增删改查，就会进行边枚举边筛查的形式，逐渐的将 ht[0][0] ... ht[0][size-1] rehash 到 ht[1] 中

能够追一下代码流程，咱们从 src\server.c 注册 setCommand 命令开始追起，代码设计要害流程如下

当追到 dictAddRaw 函数的时候，咱们能够清晰的看进去，当 redis 退出数据 的时候，应用的是头插法

• 先对新的节点开拓相应的内存
• 将新建节点的 next 对象指向链表的头
• 而后将链表的头指向新建的节点地址，即实现了一次 头插

此处咱们能够看到，实际上是做了一次 rehash

追到 dictRehash 函数的时候，能够看到此处的再 hash 函数 dictRehash，咱们能够看到 rehash 的做法是：

• 在 ht[0] 数组中，获得 rehashidx 对应的桶，或者脚数组对应的索引地位
• 通过上述找到的索引地位，取 ht[0].table[d->rehashidx] 对应的链表
• 而后将链表中的数据顺次进行 rehash

此处 dictRehash 的 n 的参数，示意再 hash 的次数，再 hash 1 次，示意对于数组的这个桶对应的链表上的所有数据，进行一轮 hash

能够看到代码中

 /* Get the index in the new hash table */
  h = dictHashKey(d, de->key) & d->ht[1].sizemask;

此处正是 dictHashKey 计算出一个整数，而后和咱们 dictht 中的 sizemask 进行一次按位与操作，旨在失去一个新的 hash 表索引地位

redis 调用 _dictRehashStep 的地位

通过查看代码中调用 _dictRehashStep 函数的地位并不多，咱们一次查看调用关系，咱们会晓得的确是当咱们每次操作 redis 增删改查 的时候，会产生 渐进式的 rehash，这些是在咱们进行扩容之后，如何将 ht[0] 的数据拷贝到 ht[1] 的实现形式

理论 redis 中波及到如上几个函数 都会调用 _dictRehashStep：

• dictAddRaw
• dictGenericDelete
• dictFind
• dictGetRandomKey
• dictGetSomeKeys

ht[0] 数据拷贝到 ht[1] 的形式二

定时器调用 dictRehash 的逻辑

当 redis 中没有长久化操作的时候，redis 中的定时操作就会就会走定时的逻辑，逻辑是这样的

咱们能够在 redis 源码中搜寻应用 dictRehash 函数的地位

应用的地位也并不多，咱们很容易就能找到依照毫秒级别来定时操作的地位

dictRehashMilliseconds

此处的逻辑是，while 循环是以 100 次 rehash 为一轮，工夫限度是 1ms，只有工夫不超过 1ms，能做的 rehash 次数至多是 100 次（每一轮 100 次），若超过 1 ms，则会立即完结本次定时操作

此处咱们能够看到，dictRehash(d,100) 传递的参数是 100，示意 rehash 100 次，还记得之前的渐进式 rehash 是 传入的 1 次 吗，能够往上看看文章内容

明天就到这里，学习所得，若有偏差，还请斧正

欢送点赞，关注，珍藏

敌人们，你的反对和激励，是我保持分享，提高质量的能源

好了，本次就到这里

技术是凋谢的，咱们的心态，更应是凋谢的。拥抱变动，背阴而生，致力向前行。

我是 阿兵云原生，欢送点赞关注珍藏，下次见~