Redis之dict数据结构的渐进式rehash原理

小鱼儿 2022-12-01 15:44 188阅读 0赞

前面这篇文章 《[图解Redis底层数据结构实现原理][Redis]》简单的讲解了redis的底层数据结构，本篇文章继续深入了解dict(字典)数据结构的扩容过程（即渐进式rehash过程）。

# 1.dict数据结构 #

dict是一个用于维护key和value映射关系的数据结构，与很多语言中的Map或dictionary类似。Redis的一个database中所有key到value的映射，就是使用一个dict来维护的。dict本质上是为了解决算法中的查找问题(Searching)。

#1.一般查找问题的解法分为两个大类：一个是基于各种平衡树，一个是基于哈希表，平常使用的各种Map或dictionary，大都是基于哈希表实现的。
    
    #2.dict也是一个基于哈希表的算法，跟java中的hashMap类似，用key计算出哈希值，并得到key在哈希表中的位置，再采用拉链法解决冲突，并在装载因子（load factor）超过预定值时自动扩展内存，引发重哈希（rehashing）。

为了能更清楚地展示dict的数据结构定义，用一张结构图来表示dict(字典)的构成。如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70][]

#dict字典的数据结构
    typedef struct dict{
        dictType *type; //直线dictType结构，dictType结构中包含自定义的函数，这些函数使得key和value能够存储任何类型的数据
        void *privdata; //私有数据，保存着dictType结构中函数的 参数
        dictht ht[2]; //两张哈希表
        long rehashidx; //rehash的标记，rehashidx=-1表示没有进行rehash，rehash时每迁移一个桶就对rehashidx加一
        int itreators;  //正在迭代的迭代器数量
    }
    
    #dict结构中ht[0]、ht[1]哈希表的数据结构
    typedef struct dictht{
        dictEntry[] table;        //存放一个数组的地址，数组中存放哈希节点dictEntry的地址
        unsingned long size;      //哈希表table的大小，出始大小为4
        unsingned long  sizemask; //用于将hash值映射到table位置的索引，大小为（size-1）
        unsingned long  used;     //记录哈希表已有节点（键值对）的数量
    }

上图就是Redis的dict(字典)数据结构，一个dict需要注意几点：

*  （1）dict采用哈希函数对key取哈希值得到在哈希表中的位置(桶的位置)，采用拉链法解决hash冲突。
 *  （2）两张哈希表（ht\[2\]）：只有在重哈希的过程中，ht\[0\]和ht\[1\]才都有效。而在平常情况下，只有ht\[0\]有效，ht\[1\]里面没有任何数据。上图表示的就是重哈希进行到中间某一步时的情况。
 *  （3）重哈希：跟HashMap一样当装载因子（load factor）超过预定值时就会进行rehash。dict进行rehash扩容，将ht\[0\]上某一个bucket（即一个桶上dictEntry链表）上的每一个链表移动到扩容后的ht\[1\]上**(每次只移动一个链表，即渐进式rehash。原因是为了防止redis长时间的堵塞导致不可用)**，触发rehash的操作有查询、插入和删除元素。rehashidx会记录每次需要移动链表bucket桶的位置(后面会详细讲解)。
 *  （4）当 ht\[0\] 包含的所有键值对都迁移到了 ht\[1\] 之后 （ht\[0\] 变为空表），释放 ht\[0\] ， 将 ht\[1\] 设置为 ht\[0\] ， 并在 ht\[1\] 新创建一个空白哈希表， 为下一次 rehash 做准备。

# 2.触发rehash的条件 #

## (1)负载因子计算 ##

#哈希表的负载因子计算：负载因子 = 哈希表已保存节点数量 / 哈希表大小
    load_factor = ht[0].used / ht[0].size

## (2)rehash的条件 ##

触发dict的rehash主要有两种：一种是触发扩容操作，另一种是触发收缩操作。两种rehash触发的条件是不一样的，需要各自满足一下条件才能导致rehash操作。

**1）触发扩容操作条件：**当以下条件中的任意一个被满足时， 程序会自动开始对哈希表执行扩展操作。

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

根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行，服务器执行扩展操作所需的负载因子并不相同，这是因为在执行 BGSAVE 命令或 BGREWRITEAOF命令的过程中， Redis会fork一个子进程，而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作， 最大限度地节约内存。

**2）触发收缩操作条件：**当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。

(ht[0].used / ht[0].siz) < 0.1，也就是填充率必须<10%。

# 3.dict添加、查询和删除操作 #

*  （1）dict添加操作：如果正在重哈希中，会把数据插入到ht\[1\]；否则插入到ht\[0\]。
 *  （2）dict查询操作：先在第一个哈希表ht\[0\]上进行查找，再判断当前是否在重哈希，如果没有，那么在ht\[0\]上的查找结果就是最终结果。否则，在ht\[1\]上进行查找。查询时会先根据key计算出桶的位置，在到桶里的链表上寻找key。
 *  （3）dict删除操作：判断当前是不是在重哈希过程中，如果是只在ht\[0\]中查找要删除的key；否则ht\[0\]和ht\[1\]它都要查找删除。

# 4.渐进式 rehash #

扩展或收缩哈希表需要将 ht\[0\]里面的所有键值对 rehash 到 ht\[1\]里面， 但是， 这个 rehash 动作并不是一次性、集中式地完成的， 而是分多次、渐进式地完成的。

这样做的原因在于，如果哈希表里保存的键值对数量很大时， 如：四百万、四千万甚至四亿个键值对， 那么一次性将这些键值对全部 rehash 到 ht\[1\] 的话，**庞大的计算量(需要重新计算链表在桶中的位置)可能会导致服务器在一段时间内停止服务(redis是单线程的，如果全部移动会引起客户端长时间阻塞不可用)。**

因此， 为了避免 rehash 对服务器性能造成影响， 服务器不是一次性将 ht\[0\]里面的所有键值对全部 rehash 到 ht\[1\]， 而是分多次、渐进式地将 ht\[0\]里面的键值对慢慢地 rehash 到 ht\[1\]。

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

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

渐进式 rehash 的好处在于它采取分而治之的方式， 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上， 从而避免了集中式 rehash 而带来的庞大计算量。

如下：图4-12 至 图4-17 展示了一次完整的渐进式 rehash 过程， **注意:观察在整个 rehash 过程中， 字典的 rehashidx 属性是如何变化的。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 6][]

**总结：渐进式 rehash 执行期间的哈希表操作**  
**（1）删除和查找：**在进行渐进式rehash的过程中，字典会同时使用ht\[0\]和ht\[1\]两个哈希表，所以在渐进式rehash进行期间，字典的删除、查找、更新等操作会在两个哈希表上进行。比如说，要在字典里面查找一个键的话，程序会先在ht\[0\]里面进行查找，如果没找到的话，就会继续到ht\[1\]里面进行查找，诸如此类。

**（2）新增数据：**在渐进式 rehash 执行期间，新添加到字典的键值对一律会被保存到ht\[1\]里面，而ht\[0\]则不再进行任何添加操作。这一措施保证了ht\[0\]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。

文章主要参考《Redis设计与实现》、《Redis实战》。

附两本书在线学习地址：[《Redis设计与实现》][Redis 1]、[《Redis实战》][Redis 2]

2020年09月02号 晚 于北京记

[Redis]: https://blog.csdn.net/Seky_fei/article/details/106968173
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70]: /images/20221123/bf6bfdfea969496cb5cfe54cf0390339.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 1]: /images/20221123/1fe5e0678952486f8466cc2074f605f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 2]: /images/20221123/a1144b66ca874a9095d0fc8d4c5d8726.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 3]: /images/20221123/b237fe993224458da6b3a95f905729bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 4]: /images/20221123/30cf790fa7aa407c88e3702a42e5dad8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 5]: /images/20221123/fa3a9ffec29f4c2dbfd4806bce4e06de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Nla3lfZmVp_size_16_color_FFFFFF_t_70 6]: /images/20221123/1765eb30f38c49d783960c9a633f3595.png
[Redis 1]: http://redisbook.com/index.html
[Redis 2]: http://redisinaction.com/index.html