Redis 字典的底层实现

「爱情、让人受尽委屈。」 2021-09-21 05:28 295阅读 0赞

字典又称符号表，关联数组或者映射，是一种用于**保存键值对的抽象数据结构**。

### 一、Redis的字典底层结构 ###

Redis 的字典使用哈希表作为底层实现，**一个哈希表里面有多个哈希节点**，而每个哈希表节点就保存了字典中的一个键值对，Redis的字典可以参照Java中的HashMap。

**哈希表代码**

typedef struct dictht{ 
         //哈希表数组
         dictEntry **table;
         //哈希表大小
         unsigned long size;
         //哈希表大小掩码，用于计算索引值
         //总是等于 size-1
         unsigned long sizemask;
         //该哈希表已有节点的数量
         unsigned long used;
         }dictht；

**哈希表节点**

typedef struct dictEntry{ 
         //键
         void *key;
         //值
         union{ 
              void *val;
              uint64_tu64;
              int64_ts64;
         }v;
    
         //指向下一个哈希表节点，形成链表
         struct dictEntry *next;
    }dictEntry；

Redis的字典结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]

### 二、解决哈希冲突 ###

**1.哈希冲突**

提到的哈希冲突，解决他的办法有两种，**开放寻址法和拉链法**，Redis 很明显采用的是后者，后者很明显更加清晰，存取更加方便，第一种数据不多还好，如果数据量特别大的时候，插入，查找，删除，修改都是一件很困难的事情，时间复杂度太高。

**2.rehash**

随着操作的不断执行，**哈希表保存的键值会逐渐地增多或者减少**，为了让哈希表的负载因子维持在一个范围之内，**当哈希表存储的键值对太多或者太少，程序要对哈希表的大小进行相应的扩展或者收缩。这就是我们要说的 rehash**。

**3.那么什么时候才会 rehash 呢？**

*  服务器目前**没有执行的 BGSAVE 命令**或者 BGREWRUTEAOF 命令，并且**哈希表的负载因子大于等于 1；**
 *  服务器目前**正在执行 BGSAVE** 命令或者 BGREWRUTEAOF 命令，并且哈希表的**负载因子大于等于 5；**

负载因子 = 哈希表以保存的节点数量 / 哈希表的大小

BGSAVE，这个命令是 redis 进行 RDB 持久化时所用到的命令；BGREWRUTEAOF 就是另一种 AOF 持久化方式的工作方式，也就是**在 Redis 进行持久化的时候，可能会触发 rehash。**

**4.rehash 的实现原理**

既然要进行重新散列，那么原来的表肯定是不适合了，所以要重新开辟一张表，这就是上面我们所说的 ht \[1\], **之所以维持两张表就是这个原因，如果需要扩容**，那么扩容后的长度也就是 ht \[1\].size=ht \[0\].used\*2 的 2^n， 缩小的话就是 ht \[1\].size=ht \[0\].used 的 2^n, 准备条件好了就要开始移动了，直到 0 号哈希表中没有保存的节点，这时候释放空表的空间，将 ht \[1\] 更名为 ht \[0\]，然后将 ht \[1\] 置为空，就完成了 rehash。

**5.渐进式 rehash**

如果像这样 rehash 的话，如果你的字典中存储这几万条，几十万条，几百万条的数据时，如果我们一次性的，集中式的把这些数据 rehash，那估计服务器就不能再进行其它服务了，高性能的 Redis 是绝对不允许这种事情发生的。所以Redis是通过渐进式rehash来保证性能的。

**hash表有一个字段 rehashidx**，索引计数器，记录了 rehash 的进度。

以下是哈希表渐进式 rehash 的详细步骤：

1）为 ht \[1\] 分配空间， 让字典同时持有 ht \[0\] 和 ht \[1\] 两个哈希表。  
2）在字典中维持一个索引计数器变量 rehashidx ， 并**将它的值设置为 0 ， 表示 rehash 工作正式开始**。  
3）**在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht \[0\] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht \[1\]** ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。  
4）随着字典操作的不断执行， 最终在某个时间点上， ht \[0\] 的所有键值对都会被 rehash 至 ht \[1\] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

**6.注意：**

因为在进行 rehash 的时候，两个表中都有值，所以不能确定具体在哪个表中，所以要在两个表中进行 字典的删除（delete）、查找（find）、更新（update）等操作，**如果是查找的话，就会现在 ht \[0\] 中查找，没有就去 ht \[1\] 中找，但是如果是增加的话，就会一律保存到 ht \[1\] 中**，不会再像 ht \[0\] 中进行任何添加操作，不会多此一举，**保证 ht \[0\] 中的数据只减不增**，直到他变成一个空表。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/dd9fdd30e47545a7bf1e318002042497.png