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

3次阅读

共计 2888 个字符，预计需要花费 8 分钟才能阅读完成。

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

扩大和膨胀哈希表的工作能够通过执行 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

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

服务器目前没有在执行 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）是一种能够推延甚至防止复制数据的技术。内核此时并不是复制整个过程空间，而是让父过程和子过程共享同一个正本。只有在须要写入的时候，数据才会被复制，从而使父过程、子过程领有各自的正本。也就是说，资源的复制只有在须要写入的时候才进行，在此之前以只读形式共享。

扩大或膨胀哈希表须要将 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] 两个哈希表

正文完