[Redis] 哈希表的Rehash机制

Redis 2021-02-05

哈希表的完整结构,因为他是多个哈希一层层嵌套的,所以会是这样的结构

触发rehash的时机

字典类型容量变化过程叫做rehash,需要满足一定的条件才能触发扩容机制
服务器当前没有进行BGWRITEAOF或者BGSAVE命令，且当前键值对个数超过一维数组的大小，才会触发扩容。

如果当前键值对个数超过一维数组大小的五倍，无论是否在进行BGWRITEAOF或者BGSAVE命令，都会强制扩容。
Hash类型扩容后数组的长度为原来的二倍

缩容机制：如果当前键值对个数少于一维数组大小的十分之一，则触发缩容过程。缩容不会考虑当前服务器是否在进行BGWRITEAOF或者BGSAVE命令

渐进式rehash的过程

利用了两个哈希表进行的,有点类似数据库的迁移,读的时候先读旧库,读不到读新库,写的时候只写新库 ; 其他旧数据一点点的往新库上搬

当触发扩容的时候，Redis会首先为ht[1] 分配一块内存空间。如果当前字典是一个比较大的字典，那么整个扩容过程的时间复杂度为O(n)，直接完整进行扩容机制可能会导致Redis一段时间内停止服务。为了避免停止服务的情况，Redis的设计团队采用了渐进式rehash的策略，每次只对原哈希表中的一小部分进行搬迁，这样渐进式的进行，直到全部键值对都迁移到新的哈希表中。

首先，对于key的查询，我们需要到原来的哈希表中进行查找，如果找到对应的value，直接返回就可以了。如果没有找到，那么只有两种可能，一个是这个键值对已经搬迁到新的哈希表了，另外一种可能是根本就不存在这个键值对，无论是哪种可能，我们都需要再去新哈希表中对他进行查找，如果找到了就返回，如果找不到说明这个键值对不存在。

步骤如下：
1.为字典的备用哈希表分配空间：
如果执行的是扩展操作，那么备用哈希表的大小为第一个大于等于(已用节点个数)*2的2n（2的n次方幂）
如果执行的是收缩操作，那么备用哈希表的大小为第一个大于等于(已用节点个数)的2n
2.在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始（为-1时表示没有进行rehash）。
3.rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当一次rehash工作完成之后，程序将rehashidx属性的值+1。同时在serverCron中调用rehash相关函数，在1ms的时间内，进行rehash处理，每次仅处理少量的转移任务(100个元素)。
随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。