Redis字典的渐进式rehash

采用渐进式 rehash 的原因

扩展或收缩哈希表需要将ht[0]中的所有键值对rehash到ht[1]中。不过，这个rehash的动作不一定是一次性、集中式完成的，而是分多次、渐进式完成的。

这样做的原因在于，避免当ht[0]中保存了太多的键值对时，一次性集中式rehash让服务器在较长的时间内停止服务。rehash动作的过程中肯定是不能对外提供增删改查的操作的，如果ht[0]中只有四个键值对的话，那么一次性完成rehash也不会对服务器的运行造成太多延迟，但如果是四百万、四千万的话一次性完成rehash将会严重阻塞服务器运行。

渐进式 rehash 的过程

以下是哈希表渐进式rehash的详细步骤：

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
2. 在字典中维护一个rehashidx变量，来标记当前rehash到了ht[0] 的 dictEntry table哪个位置。
3. 在渐进式rehash进行期间，每次对字典执行增删改查操作时，除了执行指定操作外还要讲ht[0]中的rehashidx索引位置上的键值对 rehash 到ht[1]上，当本次rehash完成时，rehashidx加一。
4. 随着字典操作的不断进行，最终在某个时间点上，ht[0]上的键值对都 rehash 到了ht[1]上，这时程序将 rehashidx 设置为-1，表示 rehash 操作已经完成。
5. rehash 完所有键值对后，ht[1]和ht[0]将交换位置，即ht[1]将成为新的ht[0]。

渐进式 rehash 采用了分治的思想，将 rehash 键值对所需的工作分摊到了每次对字典的增删改查操作上，虽然降低了 redis 服务器的整体吞吐量，但提升了响应速度，不会出现在某次操作时特别慢的情况。

渐进式 rehash 期间的哈希表操作

因为在渐进式 rehash 的过程中，字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以在这个过程中对字典的增删改查操作会在两个哈希表上进行。例如在字典上查找一个键时，程序会先查询ht[0]，如果没有查到就再查 ht[1]。
新添加到字典上的键值对只会保存在ht[1]上，而ht[0]上不再进行任何添加操作，这样就保证了ht[0]中包含的键值对的数量只减不增，并随着rehash的进行而逐渐变成空表。

总结

• 原因：数据太多的话一次rehash可能让服务器长时间停止服务，渐进式就是将停止服务的时间分散给一段时间内的每次增删改查上。
• 渐进：rehashidx 从0开始到ht[0].length-1，每次增删改查时 将对ht[rehashidx]进行rehash。
• 操作：查询操作同时查询ht[0]和ht[1]，新增操作只新增ht[1]