Redisbook学习笔记（1）字典（3

渐进式rehash

在上一节，我们了解了字典的rehash 过程，需要特别指出的是，rehash 程序并不是在激活之

后就马上执行直到完成的，而是分多次、渐进式地完成的。

假设这样一个场景：在一个有很多键值对的字典里，某个用户在添加新键值对时触发了rehash

过程，如果这个rehash 过程必须将所有键值对迁移完毕之后才将结果返回给用户，这样的处理

方式将是非常不友好的。

另一方面，要求服务器必须阻塞直到rehash 完成，这对于Redis 服务器本身也是不能接受的。

为了解决这个问题，Redis 使用了渐进式（incremental）的rehash 方式：通过将rehash 分散

到多个步骤中进行，从而避免了集中式的计算。

渐进式rehash 主要由_dictRehashStep 和dictRehashMilliseconds 两个函数进行：
. _dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动rehash ；
. dictRehashMilliseconds 则由Redis 服务器常规任务程序（server cron job）执行，用
于对数据库字典进行主动rehash ；
_dictRehashStep
每次执行_dictRehashStep ，ht[0]->table 哈希表第一个不为空的索引上的所有节点就会全
部迁移到ht[1]->table 。

在rehash 开始进行之后（d->rehashidx 不为-1），每次执行一次添加、查找、删除操作，
_dictRehashStep 都会被执行一次：

因为字典会保持哈希表大小和节点数的比率在一个很小的范围内，所以每个索引上的节点数量
不会很多（从目前版本的rehash 条件来看，平均只有一个，最多通常也不会超过五个），所以
在执行操作的同时，对单个索引上的节点进行迁移，几乎不会对响应时间造成影响。
dictRehashMilliseconds
dictRehashMilliseconds 可以在指定的毫秒数内，对字典进行rehash 。
当Redis 的服务器常规任务执行时，dictRehashMilliseconds 会被执行，在规定的时间内，
尽可能地对数据库字典中那些需要rehash 的字典进行rehash ，从而加速数据库字典的rehash
进程（progress）。
其他措施
在哈希表进行rehash 时，字典还会采取一些特别的措施，确保rehash 顺利、正确地进行：
 因为在rehash 时，字典会同时使用两个哈希表，所以在这期间的所有查找、删除等操作，
除了在ht[0] 上进行，还需要在ht[1] 上进行。
 在执行添加操作时，新的节点会直接添加到ht[1] 而不是ht[0] ，这样保证ht[0] 的节
点数量在整个rehash 过程中都只减不增。

字典的收缩
上面关于rehash 的章节描述了通过rehash 对字典进行扩展（expand）的情况，如果哈希表的
可用节点数比已用节点数大很多的话，那么也可以通过对哈希表进行rehash 来收缩（shrink）
字典。
收缩rehash 和上面展示的扩展rehash 的操作几乎一样，它执行以下步骤：
1. 创建一个比ht[0]->table 小的ht[1]->table ；
2. 将ht[0]->table 中的所有键值对迁移到ht[1]->table ；
3. 将原有ht[0] 的数据清空，并将ht[1] 替换为新的ht[0] ；
扩展rehash 和收缩rehash 执行完全相同的过程，一个rehash 是扩展还是收缩字典，关键在于
新分配的ht[1]->table 的大小：
. 如果rehash 是扩展操作，那么ht[1]->table 比ht[0]->table 要大；
. 如果rehash 是收缩操作，那么ht[1]->table 比ht[0]->table 要小；
字典的收缩规则由redis.c/htNeedsResize 函数定义：

int htNeedsResize(dict *dict) {
long long size, used;
// 哈希表已用节点数量
size = dictSlots(dict);
// 哈希表大小
used = dictSize(dict);
// 当哈希表的大小大于DICT_HT_INITIAL_SIZE
// 并且字典的填充率低于REDIS_HT_MINFILL 时
// 返回1
return (size && used && size > DICT_HT_INITIAL_SIZE &&
(used*100/size < REDIS_HT_MINFILL));
}

在默认情况下，REDIS_HT_MINFILL 的值为10 ，也即是说，当字典的填充率低于10% 时，程
序就可以对这个字典进行收缩操作了。
字典收缩和字典扩展的一个区别是：
. 字典的扩展操作是自动触发的（不管是自动扩展还是强制扩展）；
. 而字典的收缩操作则是由程序手动执行。
因此，使用字典的程序可以决定何时对字典进行收缩：
. 当字典用于实现哈希键的时候，每次从字典中删除一个键值对，程序就会执行一次
htNeedsResize 函数，如果字典达到了收缩的标准，程序将立即对字典进行收缩；
. 当字典用于实现数据库键空间（key space） 的时候， 收缩的时机由
redis.c/tryResizeHashTables 函数决定.

字典其他操作
除了添加操作和伸展/收缩操作之外，字典还定义了其他一些操作，比如常见的查找、删除和更
新。
因为链地址法哈希表实现的相关信息可以从任何一本数据结构或算法书上找到，这里不再对字
典的其他操作进行介绍，不过前面对创建字典、添加键值对、收缩和扩展rehash 的讨论已经涵
盖了字典模块的核心内容。

字典的迭代
字典带有自己的迭代器实现——对字典进行迭代实际上就是对字典所使用的哈希表进行迭代：
. 迭代器首先迭代字典的第一个哈希表，然后，如果rehash 正在进行的话，就继续对第二
个哈希表进行迭代。
. 当迭代哈希表时，找到第一个不为空的索引，然后迭代这个索引上的所有节点。
. 当这个索引迭代完了，继续查找下一个不为空的索引，如此循环，一直到整个哈希表都迭
代完为止。
整个迭代过程可以用伪代码表示如下：

def iter_dict(dict):
// 迭代0 号哈希表
iter_table(ht[0]->table)
// 如果正在执行rehash ，那么也迭代1 号哈希表
if dict.is_rehashing(): iter_table(ht[1]->table)
def iter_table(table):
// 遍历哈希表上的所有索引
for index in table:
// 跳过空索引
if table[index].empty():
continue
// 遍历索引上的所有节点
for node in table[index]:
// 处理节点
do_something_with(node)

字典的迭代器有两种：
 安全迭代器：在迭代进行过程中，可以对字典进行修改。
 不安全迭代器：在迭代进行过程中，不对字典进行修改。
以下是迭代器的数据结构定义：

typedef struct dictIterator {
dict *d; // 正在迭代的字典
int table, // 正在迭代的哈希表的号码（0 或者1）
index, // 正在迭代的哈希表数组的索引
safe; // 是否安全？
dictEntry *entry, // 当前哈希节点
*nextEntry; // 当前哈希节点的后继节点
} dictIterator;

小结
 字典由键值对构成的抽象数据结构。
 Redis 中的数据库和哈希键都基于字典来实现。
 Redis 字典的底层实现为哈希表，每个字典使用两个哈希表，一般情况下只使用0 号哈希
表，只有在rehash 进行时，才会同时使用0 号和1 号哈希表。
 哈希表使用链地址法来解决键冲突的问题。
 Rehash 可以用于扩展或收缩哈希表。
 对哈希表的rehash 是分多次、渐进式地进行的。