中间件 | Redis - [全局 hash & 渐进 rehash]

Redis中的全局哈希表是一种用于存储键值对的数据结构，它在服务器中被广泛用于多种目的，包括数据库的键空间和各种缓存数据。

Redis中的全局哈希表采用了渐进式rehash策略，目的是为了数据的平滑迁移，减少rehash期间对服务器性能的影响。

以下是一个简化的Redis全局哈希表结构和渐进式rehash的伪代码示例：

// 哈希表结构
struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
};
 
// 哈希表节点结构
struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
};
 
// Redis字典结构
struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
};
 
// 渐进式rehash的伪代码
void rehash(dict *d, int n) {
    int empty_visits = n * 10; /* Max number of empty buckets to visit. */
    if (d->ht[0].used + d->ht[0].deleted < (unsigned long)ht_table_size(d->ht[0].size) * 5)
        return;
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        /* 对第一个哈希表的所有节点进行rehash */
        if (d->ht[0].used == 0) break;
        if (iterations++ > empty_visits && (unsigned long)iterations < d->ht[0].size) {
            /* 如果访问空桶次数过多，且rehashIdx没有到达第一个哈希表的末尾，则退出 */
            break;
        }
        if ((de = d->ht[0].table[index]) == NULL) {
            index++;
            continue;
        }
        while(de) {
            unsigned int h;
            nextde = de->next;
            /* 计算键的新哈希值 */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
    }
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        if (it == 0) d->iterators = 0;
    } else {
        d->rehashidx = index;
        if (n == -1) d->rehashidx = 0;
    }
}

在这个示例中，我们定义了一个Redis字典和两个哈希表，其中一个用于当前数据存储，另一个用于rehash期间的数据迁移。rehash函数负责执行渐进式rehash，它会逐步将第一个哈希表的节点迁移到第二个哈希表，直至所有节点都迁移完成或达到某些限制条件。这个过程可以分步进行，不需要一次性对所有数据进行重新计算哈希值和重新分配内存，因此对服务器性能的影响较小。