Redis(四):字典-渐进式hash

╰半橙微兮° 2022-05-24 04:41 206阅读 0赞

本篇接着上面Redis的字典进行继续分析，主要讲解Redis字典里面是如何实现渐进式Hash的策略的。

###### 渐进式Hash ######

听名字就很容易参透出来是什么意思，渐进的意思就是不一步到位，而是慢慢的操作。慢慢的计算出Hash值。这个Redis的动作并不是一次性，集中性的完成，而是分多次，渐进式的完成的。

这样做的原因在于，如果ht\[0\]里保存的键非常少，那么服务器可以在瞬间就将这些键值对全部rehash到ht\[1\]。但是，如果哈希表里面保存的键值对数量非常多，几百万，几千万甚至上亿个。那么要一次性将这些键值对全部Rehash到ht\[1\]的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

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

详细步骤：

1）为ht\[1\]分配空间，让字典同时持有ht\[1\]和ht\[0\]两个哈希表。

2）在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始

3）在Rehash期间，每次对字典的执行添加，删除，查找或者更新操作时，程序除了执行指定的操作外，还会顺带将ht\[0\]哈希表在rehashidex索引上的所有键值对rehash到\[1\]，当rehash完成，程序将rehashidx属性的值增一。

4）随着字典操作的不断执行，最终在某个时间点上，ht\[0\]的所有键值对都会被rehash至ht\[1\]，这时程序将rehashidex属性的值设置为-1，表示rehash操作已完成。

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

###### 渐进式Rehash执行期间的哈希表操作 ######

因为在渐进式rehash的过程中，字典会同时使用ht\[0\]，ht\[1\]两个哈希表，所以在渐进式rehash期间，字典的删除，查找，更新等操作会在两个哈希表上进行，例如，要在字典里面查找一个键的话，程序会先在ht\[0\]里面进行查找，如果没找到，则会继续到ht\[1\]里面进行查找，诸如此类。

另外，在渐进式rehash执行期间，新添加到字典的键值对一律保存到ht\[1\]当中，而ht\[0\]则不再进行任何添加操作，这一措施保证了ht\[0\]包含的键值对数量会只减不增。并随着rehash的操作，最后变为空表。