[Redis]Redis-渐进式rehash

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对，我也把它称为全局哈希表。
一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。所以，我们常说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。

需要注意的是，哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。

• Redis的全局哈希表

• Redis使用链式哈希解决hash冲突(指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接)

为了使rehash操作更高效，Redis默认使用了两个全局哈希表ht[0]和ht[1]。一开始，当你刚插入数据时，默认使用ht[0]，此时的ht[1]并没有被分配空间。随着数据逐步增多，使用链式哈希解决hash冲突导致链表过长，Redis越来越慢，此时Redis开始执行rehash，整个过程分为三步：

1. 给ht[1]分配更大的空间，例如是当前ht[0]大小的两倍；

2. 把ht[0]中的数据重新映射并拷贝到ht[1]中；

3. 释放ht[0]的空间

渐进式rehash

在Redis中，rehash需要将ht[0]里面的所有键值对rehash到ht[1]里面，但是，这个rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。为了避免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属性的值增1，这就是操作辅助rehash;

4. 在rehash进行期间，如果服务器比较空闲，在Redis周期函数中，如果发现有字典正在进行渐进式rehash操作，则会花费1毫秒的时间，帮助一起进行渐进式rehash操作，这就是定时辅助rehash；

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

6. 释放ht[0]的空间

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

• Redis的渐进式rehash

因为在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行：比如说，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找，诸如此类。
另外，在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作：这一措施保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。

问题:

• 同时有两个hash表在使用，会使得redis内存使用量瞬间突增
• 在Redis满容状态下,Rehash会导致大量Key驱逐