Redis 渐进式 rehash 的并发控制策略
Redis 的 rehash 基本概念
在深入探讨 Redis 渐进式 rehash 的并发控制策略之前，我们先来了解一下什么是 rehash。
Redis 中的字典（dict）是一种非常重要的数据结构，它被广泛用于实现 Redis 的各种功能，比如数据库中的键值对存储。字典使用哈希表来实现，哈希表能够提供高效的查找、插入和删除操作。然而，哈希表有一个问题，当哈希表中的元素数量过多或者过少时，哈希表的性能会受到影响。
为了解决这个问题，Redis 采用了 rehash 机制。简单来说，rehash 就是对哈希表进行重新调整大小的过程。当哈希表中的元素数量过多，超过了负载因子（load factor）的阈值时，Redis 会扩大哈希表的大小；当哈希表中的元素数量过少，低于负载因子的另一个阈值时，Redis 会缩小哈希表的大小。
普通 rehash 的问题
如果采用传统的一次性 rehash 方式，会存在一些问题。想象一下，在一个大型的 Redis 实例中，存储了大量的键值对。当需要进行 rehash 时，如果一次性将所有键值对重新计算哈希值并迁移到新的哈希表中，这将是一个非常耗时的操作。在这个过程中，Redis 可能无法处理其他客户端的请求，导致服务暂停，严重影响系统的可用性。
Redis 渐进式 rehash
为了解决一次性 rehash 的问题，Redis 采用了渐进式 rehash。渐进式 rehash 的核心思想是将 rehash 操作分成多个步骤，逐步完成。
在 Redis 的字典结构中，有两个哈希表，分别为 ht[0] 和 ht[1]。正常情况下，所有的数据都存储在 ht[0] 中。当需要进行 rehash 时，Redis 会先分配一个大小合适的 ht[1]，然后在后续的操作中，逐步将 ht[0] 中的元素迁移到 ht[1] 中。每次进行字典的插入、删除、查找或者更新操作时，Redis 都会顺带将一小部分 ht[0] 中的元素迁移到 ht[1] 中。这样，随着时间的推移，ht[0] 中的元素会逐渐全部迁移到 ht[1] 中，完成 rehash 操作。
渐进式 rehash 的数据结构基础
在 Redis 的 dict 结构中，我们可以看到与渐进式 rehash 相关的部分代码：
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehash 索引，当 rehashidx == -1 时，表示没有进行 rehash */
int iterators; /* 当前正在运行的迭代器数量 */
} dict;
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
在上述代码中，dict 结构体中的 ht 数组包含两个 dictht 哈希表。rehashidx 字段用于记录当前 rehash 操作进行到的位置，当 rehashidx 为 -1 时，表示没有进行 rehash 操作。
渐进式 rehash 的并发读控制策略
读操作与 rehash 的关系
在渐进式 rehash 过程中，读操作可能会涉及到两个哈希表，因为在 rehash 完成之前，数据可能分布在 ht[0] 和 ht[1] 两个哈希表中。
读操作的实现
以查找键值对为例，Redis 的查找函数会先在 ht[0] 中查找，如果没有找到，再在 ht[1] 中查找。以下是简化后的查找代码逻辑：
dictEntry *dictFind(dict *d, const void *key) {
unsigned long h, idx;
dictEntry *he;
if (d->ht[0].used == 0) return NULL; /* 空字典 */
h = dictHashKey(d, key);
/* 先在 ht[0] 中查找 */
idx = h & d->ht[0].sizemask;
he = d->ht[0].table[idx];
while (he) {
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
/* 如果 ht[0] 中没找到，且正在进行 rehash，则在 ht[1] 中查找 */
if (d->rehashidx != -1) {
idx = h & d->ht[1].sizemask;
he = d->ht[1].table[idx];
while (he) {
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
}
return NULL;
}
通过这种方式，在渐进式 rehash 过程中，读操作能够正确地获取到数据，不会因为部分数据迁移到新的哈希表而丢失。
渐进式 rehash 的并发写控制策略
写操作与 rehash 的复杂交互
写操作（插入、删除、更新）在渐进式 rehash 过程中会更加复杂，因为这些操作不仅要处理数据的变更，还要考虑如何继续推进 rehash 操作。
插入操作的并发控制
当进行插入操作时，如果发现正在进行 rehash，Redis 会优先将新元素插入到 ht[1] 中。这样可以保证新插入的数据直接进入新的哈希表，加速 rehash 的完成。以下是简化后的插入代码逻辑：
int dictAdd(dict *d, const void *key, void *val) {
dictEntry *entry;
unsigned long hash;
if (dictIsRehashing(d)) _dictRehashStep(d);
hash = dictHashKey(d, key);
if (dictExpandIfNeeded(d) == DICT_ERR)
return DICT_ERR;
entry = dictAddRaw(d, key, hash);
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);
return DICT_OK;
}
在上述代码中，dictIsRehashing(d) 用于判断是否正在进行 rehash，如果是，则调用 _dictRehashStep(d) 推进 rehash 操作。dictExpandIfNeeded(d) 用于在必要时进行哈希表的扩展。
删除操作的并发控制
删除操作同样需要考虑 rehash 的状态。在删除元素时，Redis 会在两个哈希表中查找要删除的元素。如果找到了，就将其删除，并在适当的时候推进 rehash 操作。以下是简化后的删除代码逻辑：
int dictDelete(dict *d, const void *key) {
unsigned long h;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].used == 0) return DICT_ERR;
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
prevHe = NULL;
while (he) {
if (dictCompareKeys(d, key, he->key)) {
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
dictFreeEntry(d, he);
d->ht[table].used--;
if (dictIsRehashing(d)) _dictRehashStep(d);
return DICT_OK;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return DICT_ERR;
}
在这个代码中，通过循环在 ht[0] 和 ht[1] 中查找要删除的元素，找到后删除并推进 rehash 操作。
更新操作的并发控制
更新操作类似于查找操作，先在 ht[0] 中查找，如果找到则更新；如果没找到且正在进行 rehash，则在 ht[1] 中查找并更新。同时，在更新操作中也会推进 rehash 操作。以下是简化后的更新代码逻辑：
int dictReplace(dict *d, const void *key, void *val) {
dictEntry *entry;
if (dictIsRehashing(d)) _dictRehashStep(d);
entry = dictFind(d, key);
if (entry) {
dictSetVal(d, entry, val);
return DICT_OK;
}
return dictAdd(d, key, val);
}
在这个代码中，先调用 dictFind 查找键，如果找到则更新值；如果没找到则调用 dictAdd 进行插入。
迭代器与渐进式 rehash 的并发控制
迭代器的工作原理
Redis 的迭代器用于遍历字典中的所有元素。在渐进式 rehash 过程中，迭代器需要正确地处理数据在两个哈希表之间的分布。
迭代器与 rehash 的并发控制
当创建一个迭代器时，迭代器会记录当前哈希表的状态。在迭代过程中，如果遇到 rehash 操作，迭代器会根据当前的状态继续正确地遍历所有元素。以下是迭代器相关的部分代码逻辑：
dictIterator *dictGetIterator(dict *d) {
dictIterator *iter = zmalloc(sizeof(*iter));
iter->d = d;
iter->table = 0;
iter->index = -1;
iter->safe = 0;
iter->entry = NULL;
iter->nextEntry = NULL;
return iter;
}
dictEntry *dictNext(dictIterator *iter) {
while (1) {
if (iter->entry == NULL) {
/* 移动到下一个桶 */
if (iter->table == 0 && iter->d->rehashidx != -1) {
/* 如果正在 rehash 且在 ht[0] 中遍历，先完成 ht[0] 的遍历 */
while (1) {
iter->index++;
if (iter->index >= (signed long)iter->d->ht[0].size) {
iter->table = 1;
iter->index = 0;
break;
}
if (iter->d->ht[0].table[iter->index] != NULL) {
iter->entry = iter->d->ht[0].table[iter->index];
break;
}
}
} else {
while (1) {
iter->index++;
if (iter->index >= (signed long)iter->d->ht[iter->table].size) {
if (iter->table == 0 && iter->d->rehashidx != -1) {
iter->table = 1;
iter->index = 0;
} else {
break;
}
}
if (iter->d->ht[iter->table].table[iter->index] != NULL) {
iter->entry = iter->d->ht[iter->table].table[iter->index];
break;
}
}
}
} else {
iter->entry = iter->nextEntry;
}
if (iter->entry) {
iter->nextEntry = iter->entry->next;
return iter->entry;
} else {
return NULL;
}
}
}
在这个代码中，dictGetIterator 用于创建一个迭代器，dictNext 用于获取下一个元素。在 dictNext 中，通过复杂的逻辑处理在 rehash 过程中如何正确遍历两个哈希表中的元素。
总结并发控制策略的要点
- 读操作：读操作在渐进式 rehash 过程中通过先在
ht[0]查找，若未找到再在ht[1]查找的方式，确保能够正确获取数据。 - 写操作：插入操作优先将新元素插入到
ht[1]，删除和更新操作在查找元素时会遍历ht[0]和ht[1]，并且在操作完成后会推进 rehash 操作。 - 迭代器：迭代器在创建时记录哈希表状态，在迭代过程中根据 rehash 的进行情况，正确地遍历两个哈希表中的所有元素。
通过这些并发控制策略，Redis 的渐进式 rehash 能够在保证系统可用性的同时，高效地完成哈希表的调整，为 Redis 的高性能和稳定性提供了有力保障。