一文搞懂Redis的渐进式rehash扩容机制

一文搞懂Redis的渐进式rehash扩容机制

Redis的渐进式rehash扩容机制是其高性能和稳定性的关键之一。本文将深入探讨Redis的底层数据结构、rehash触发机制以及渐进式rehash的具体步骤，帮助读者全面理解这一重要的技术细节。

底层数据结构

Redis使用C语言实现，其核心数据结构之一是字典（dict）。一个Redis实例对应一个dict，dict中包含两张哈希表（ht[0]和ht[1]），以及一些控制变量。

dict结构

typedef struct dict{
    dictType *type; //指向dictType结构，包含自定义函数
    void *privdata; //私有数据
    dictht ht[2]; //两张哈希表
    long rehashidx; //rehash标记
    int iterators;  //迭代器数量
} dict;

dictht结构

typedef struct dictht{
    dictEntry *table;        //哈希表数组
    unsigned long size;      //哈希表大小
    unsigned long sizemask;  //索引掩码
    unsigned long used;      //已使用的节点数
} dictht;

dictEntry结构

typedef struct dictEntry{
    void *key; //键
    union {
        void *val; //值
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; //链表指针
} dictEntry;

rehash触发机制

在向Redis中添加键时，会调用_dictExpandIfNeeded函数来判断是否需要扩容。

static int _dictExpandIfNeeded(dict *d) {
    if (dictIsRehashing(d)) return DICT_OK;
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

简单来说，Redis会使用装载因子（load factor）来判断是否需要做rehash。装载因子的计算方式是，哈希表中所有entry的个数除以哈希表的哈希桶个数（数组长度）。当满足以下条件中的其中一个时就会进行扩容：

• 装载因子 ≥ 1，同时，哈希表被允许进行rehash。
• 装载因子 ≥ 5。

渐进式rehash

渐进式rehash是Redis处理大规模数据扩容的关键机制，它通过分多次、渐进式地完成哈希表的迁移，避免了因一次性迁移大量数据而导致的服务中断。

渐进式rehash步骤

1. 为ht[1]分配内存空间，此时字典同时存在两个哈希表。
2. 将dict::rehashidx置为0，rehash工作正式开始。
3. 在rehash进行期间，每次对字典执行增删改查操作时，程序在执行客户端指定操作之外，还会将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]，然后将rehashidx的值加一。
4. 随着字典操作的不断执行，ht[0]的所有键值对最终会全部移动到ht[1]，此时程序会将rehashidx设为-1，释放ht[0]的空间，表示rehash操作已完成。

需要注意的是，在渐进式rehash操作过程中，因为同时存在两个哈希表，所以对key的删除、查找、更新操作会在两个哈希表上进行。Redis会先尝试在ht[0]中寻找目标键值对，如果没有找到则会在ht[1]再次寻找。但是新增操作就不一样了，新增key只会在新的哈希表ht[1]上进行，为的是确保ht[0]中的已经被清空的单向链表不会新增元素。在rehash被触发后，即使没有收到新请求，Redis也会定时执行一次rehash操作，而且，每次执行时长不会超过1ms，以免对其他任务造成影响。