皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析

admin 3个月前 (08-01) 科技 31 1

一、前言

随着操作的不停执行, 哈希表保留的键值对会逐渐地增多或者削减, 为了让哈希表的负载因子(load factor)维持在一个合理的局限之内, 当哈希表保留的键值对数目太多或者太少时, 程序需要对哈希表的巨细举行响应的扩展或者缩短。

原文剖析

二、实现剖析

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 所示。

皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析 第1张

3. 释放 ht[0] ,并将 ht[1] 设置为 ht[0] ,然后为 ht[1] 分配一个空缺哈希表,如图 4-11 所示。
至此, 对哈希表的扩展操作执行完毕, 程序乐成将哈希表的巨细从原来的 4 改为了现在的 8

皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析 第2张

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 属性是若何转变的。皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析 第3张
皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析 第4张
皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析 第5张
皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析 第6张
皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析 第7张
皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析 第8张

形貌

由于在举行渐进式 rehash 的历程中, 字典会同时使用 ht[0] 和 ht1 两个哈希表, 以是在渐进式 rehash 举行时代, 字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上举行: 比如说, 要在字典内里查找一个键的话, 程序会先在 ht[0] 内里举行查找, 若是没找到的话, 就会继续到 ht1 内里举行查找, 诸如此类。

另外, 在渐进式 rehash 执行时代, 新添加到字典的键值对一律会被保留到 ht1 内里, 而 ht[0] 则不再举行任何添加操作: 这一措施保证了 ht[0] 包罗的键值对数目会只减不增, 并随着 rehash 操作的执行而最终酿成空表。

三、要点总结

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

2.当哈希表保留的键值对数目太多或者太少时, 程序需要对哈希表的巨细举行响应的扩展或者缩短(rehash)

3.rehash 动作并不是一次性、集中式地完成的, 而是分多次、渐进式地完成的

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

皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析 第9张

,

Allbet Gmaing

欢迎进入欧博Allbet官网(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

AllBetGaming声明:该文看法仅代表作者自己,与本平台无关。转载请注明:皇冠app下载:《闲扯Redis八》Redis字典的哈希表执行Rehash历程剖析

网友评论

  • (*)

最新评论

  • UG环球手机版下载 2020-08-01 00:02:54 回复

    欧博亚洲欢迎进入欧博亚洲(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。别结局,我还想一直看

    1

文章归档

站点信息

  • 文章总数:669
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1075
  • 评论总数:254
  • 浏览总数:7763