关于redis:闲扯Redis八Redis字典的哈希表执行Rehash过程分析

一、前言

随着操作的一直执行， 哈希表保留的键值对会逐步地增多或者缩小， 为了让哈希表的负载因子（load factor）维持在一个正当的范畴之内， 当哈希表保留的键值对数量太多或者太少时， 程序须要对哈希表的大小进行相应的扩大或者膨胀。

<p align=”right”>原文解析</p>

二、实现剖析

1.rehash过程剖析

扩大和膨胀哈希表的工作能够通过执行 rehash （从新散列）操作来实现。

Redis 对字典的哈希表执行 rehash 的步骤：

1.为字典的 ht[1] 哈希表调配空间， 这个哈希表的空间大小取决于要执行的操作， 以及 ht[0] 以后蕴含的键值对数量 （也即是ht[0].used 属性的值）：

如果执行的是扩大操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n （2 的 n 次方幂）；

如果执行的是膨胀操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n 。

2.将保留在 ht[0] 中的所有键值对 rehash 到 ht[1] 下面： rehash 指的是从新计算键的哈希值和索引值， 而后将键值对搁置到 ht[1] 哈希表的指定地位上。

3.当 ht[0] 蕴含的所有键值对都迁徙到了 ht[1] 之后 （ht[0] 变为空表）， 开释 ht[0] ， 将 ht[1] 设置为 ht[0] ， 并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做筹备。

构造图解，程序对字典的 ht[0] 进行扩大操作， 步骤如下：

1. ht[0].used 以后的值为 4 ， 4 * 2 = 8 ， 而 8 （2^3）恰好是第一个大于等于 4 的 2 的 n 次方， 所以程序会将 ht[1] 哈希表
的大小设置为 8 。图 4-9 展现了 ht[1] 在调配空间之后， 字典的样子。

2. 将 ht[0] 蕴含的四个键值对都 rehash 到 ht[1] ， 如图 4-10 所示。

3. 开释 ht[0] ，并将 ht[1] 设置为 ht[0] ，而后为 ht[1] 调配一个空白哈希表，如图 4-11 所示。
至此， 对哈希表的扩大操作执行结束， 程序胜利将哈希表的大小从原来的 4 改为了当初的 8

2.哈希表的扩大与膨胀

当以下条件中的任意一个被满足时， 程序会主动开始对哈希表执行扩大操作：

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

其中哈希表的负载因子能够通过公式计算：

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

比如说， 对于一个大小为 4 ， 蕴含 4 个键值对的哈希表来说， 这个哈希表的负载因子为：

load_factor = 4 / 4 = 1

又比如说， 对于一个大小为 512 ， 蕴含 256 个键值对的哈希表来说， 这个哈希表的负载因子为：

load_factor = 256 / 512 = 0.5

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

另一方面， 当哈希表的负载因子小于 0.1 时， 程序主动开始对哈希表执行膨胀操作。

正文：写时复制（copy-on-write）是一种能够推延甚至防止复制数据的技术。内核此时并不是复制整个过程空间，而是让父过程和子过程共享同一个正本。只有在须要写入的时候，数据才会被复制，从而使父过程、子过程领有各自的正本。也就是说，资源的复制只有在须要写入的时候才进行，在此之前以只读形式共享。

3.渐进式 rehash

扩大或膨胀哈希表须要将 ht[0] 外面的所有键值对 rehash 到 ht[1] 外面， 然而， 这个 rehash 动作并不是一次性、集中式地实现的， 而是分屡次、渐进式地实现的。

这样做的起因在于， 如果 ht[0] 里只保留着四个键值对， 那么服务器能够在霎时就将这些键值对全副 rehash 到 ht[1] ； 然而， 如果哈希表里保留的键值对数量不是四个， 而是四百万、四千万甚至四亿个键值对， 那么要一次性将这些键值对全副 rehash 到 ht[1] 的话， 宏大的计算量可能会导致服务器在一段时间内进行服务。

因而， 为了防止 rehash 对服务器性能造成影响， 服务器不是一次性将 ht[0] 外面的所有键值对全副 rehash 到 ht[1] ， 而是分屡次、渐进式地将 ht[0] 外面的键值对缓缓地 rehash 到 ht[1] 。

以下是哈希表渐进式 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 操作已实现。

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

图 4-12 至图 4-17 展现了一次残缺的渐进式 rehash 过程， 留神察看在整个 rehash 过程中， 字典的 rehashidx 属性是如何变动的。

形容：

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

另外， 在渐进式 rehash 执行期间， 新增加到字典的键值对一律会被保留到 ht[1] 外面， 而 ht[0] 则不再进行任何增加操作： 这一措施保障了 ht[0] 蕴含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。

三、要点总结

1.字典应用哈希表作为底层实现， 每个字典带有两个哈希表， 一个用于平时应用， 另一个仅在进行 rehash 时应用

2.当哈希表保留的键值对数量太多或者太少时， 程序须要对哈希表的大小进行相应的扩大或者膨胀（rehash）

3.rehash 动作并不是一次性、集中式地实现的， 而是分屡次、渐进式地实现的

4.渐进式 rehash 的过程中， 字典会同时应用 ht[0] 和 ht[1] 两个哈希表