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

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

Redis的渐进式rehash扩容机制是其核心特性之一，对于理解Redis的内部工作原理和优化性能具有重要意义。本文将从底层数据结构出发，详细解析rehash的触发机制和渐进式rehash的过程。

底层数据结构

Redis使用C语言实现，其字典数据结构dict用于存储哈希表。一个Redis实例对应一个dict，其具体结构如下：

typedef struct dict{
    dictType *type; //指向dictType结构，包含自定义函数，支持存储任意类型的数据
    void *privdata; //私有数据，保存dictType结构中函数的参数
    dictht ht[2]; //两张哈希表
    long rehashidx; //rehash标记，-1表示未进行rehash，每迁移一个桶加一
    int iterators;  //正在迭代的迭代器数量
};

typedef struct dictht{
    dictEntry *table;        //存放哈希节点dictEntry的地址
    unsigned long size;      //哈希表大小，初始为4
    unsigned long sizemask;  //用于映射hash值到table位置的索引，值为(size-1)
    unsigned long used;      //记录已有节点数量
};

typedef struct dictEntry{
    void *key; //键
    union {
        void *val; //自定义类型
        uint64_t u64; //无符号整形
        int64_t s64; //符号整形
        double d; //浮点型
    } v;
    struct dictEntry *next; //链表指针，用于处理哈希冲突
};

rehash触发机制

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

static int _dictExpandIfNeeded(dict *d) {
    if (dictIsRehashing(d)) return DICT_OK; //如果正在进行渐进式扩容，则返回OK
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); //如果哈希表大小为0，则初始化

    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（在RDB生成和AOF重写时禁止）
• 装载因子 ≥ 5

渐进式rehash

渐进式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的删除、查找、更新操作会在两个哈希表上进行，而新增操作只会在新的哈希表ht[1]上进行。Redis还会定时执行rehash操作，每次执行时间不超过1ms，以避免影响其他任务。