MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Redis的rehash机制与触发条件

2021-10-175.9k 阅读

Redis哈希表结构概述

在深入探讨Redis的rehash机制之前，我们首先要了解Redis中哈希表的基本结构。Redis使用一种称为字典（dict）的数据结构来实现哈希表。在Redis的源码中，dict结构体定义如下：

typedef 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 */
} dict;

其中，ht是一个包含两个哈希表的数组，ht[0]用于正常情况下存储数据，ht[1]则主要在rehash过程中发挥作用。rehashidx字段用于记录当前rehash的进度，如果其值为 -1，表示当前没有进行rehash操作。

dictht结构体定义了哈希表的具体结构：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

table是一个指针数组，每个元素都是一个指向dictEntry结构体的指针。size表示哈希表的大小，sizemask用于计算哈希值对应的数组索引（通常为size - 1），used表示哈希表中已使用的槽位数量。

dictEntry结构体则存储了实际的键值对数据：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

key是键，v是值的联合体，可以存储不同类型的数据，next用于解决哈希冲突，形成链表结构。

常规哈希表操作

在正常情况下，Redis对哈希表的操作主要包括插入、查找和删除。

插入操作

当执行插入操作时，Redis首先计算键的哈希值，然后通过h = dictHashFunction(key) & d->ht[x].sizemask计算出对应的数组索引，其中d是dict结构体指针，x通常为0（表示ht[0]）。如果该索引位置已经有数据，就通过链表的方式将新的dictEntry插入到链表头部。例如，下面是简化的插入代码逻辑：

int dictAdd(dict *d, void *key, void *val) {
    long index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    index = _dictKeyIndex(d, key);
    if (index == -1) return DICT_ERR;

    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    dictSetKey(d, entry, key);
    dictSetVal(d, entry, val);
    ht->used++;
    return DICT_OK;
}

查找操作

查找操作同样先计算键的哈希值，找到对应的数组索引，然后遍历链表查找目标键值对。如果找到了，就返回对应的值。示例代码逻辑如下：

dictEntry *dictFind(dict *d, const void *key) {
    dictEntry *he;
    unsigned int h, idx, table;

    if (d->ht[0].used == 0) return NULL;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    h = dictHashFunction(key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while (he) {
            if (dictCompareKeys(d, key, he->key)) return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return NULL;
}

删除操作

删除操作也是类似的流程，先找到要删除的键值对所在的链表节点，然后将其从链表中移除，并释放相关内存。例如：

int dictDelete(dict *d, const void *key) {
    dictEntry *he, *prevHe;
    unsigned int h, idx;
    int table;

    if (d->ht[0].used == 0) return DICT_ERR;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    for (table = 0; table <= 1; table++) {
        idx = dictHashFunction(key) & 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;
                dictFreeKey(d, he);
                dictFreeVal(d, he);
                zfree(he);
                d->ht[table].used--;
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return DICT_ERR;
}

Redis的rehash机制

随着数据的不断插入和删除，哈希表的负载因子（used / size）会发生变化。当负载因子过高或过低时，为了保持哈希表的性能，Redis需要对哈希表进行重新哈希（rehash）操作。

渐进式rehash

Redis采用渐进式rehash的方式，而不是一次性完成整个哈希表的重新构建。这是因为如果哈希表中数据量非常大，一次性重新哈希可能会导致Redis在一段时间内无法处理其他请求，影响性能。

在渐进式rehash过程中，Redis会逐步将ht[0]中的数据迁移到ht[1]。具体步骤如下：

  1. 初始化阶段：当决定进行rehash时，Redis会分配一个大小合适的ht[1]。如果是扩展操作，ht[1]的大小通常是ht[0]的两倍；如果是收缩操作，ht[1]的大小通常是ht[0]的一半。同时，将rehashidx设置为0。
  2. 迁移阶段：在每次哈希表操作（插入、查找、删除等）时，Redis会检查rehashidx是否大于 -1，如果是，则执行一次迁移步骤。每次迁移步骤会将ht[0]中rehashidx索引位置的所有键值对迁移到ht[1]。迁移完成后，rehashidx加1。
  3. 完成阶段：当rehashidx等于ht[0].size时，表示ht[0]中的所有数据都已迁移到ht[1]，此时将ht[0]指向ht[1]，释放ht[0]的内存，并将rehashidx设置为 -1，表示rehash操作完成。

下面是_dictRehashStep函数的简化代码，它执行一次迁移步骤：

int _dictRehashStep(dict *d) {
    if (!dictIsRehashing(d)) return 0;

    while (d->ht[0].used && d->rehashidx < d->ht[0].size) {
        dictEntry *he, *nextHe;

        he = d->ht[0].table[d->rehashidx];
        if (he == NULL) {
            d->rehashidx++;
            continue;
        }

        while (he) {
            nextHe = he->next;
            unsigned int h = dictHashFunction(he->key) & d->ht[1].sizemask;
            he->next = d->ht[1].table[h];
            d->ht[1].table[h] = he;
            d->ht[0].used--;
            d->ht[1].used++;
            he = nextHe;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }

    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 1;
    }
    return 0;
}

rehash触发条件

Redis的rehash操作主要由以下两种情况触发：

扩展触发条件

  1. 负载因子大于等于1且ht[0].used大于dict_force_resize_ratio：当哈希表的负载因子（used / size）大于等于1，并且ht[0].used大于dict_force_resize_ratio（默认为512）时，会触发扩展rehash。这意味着哈希表中的元素数量已经达到或超过了哈希表的大小，且元素数量超过了一定阈值，为了避免哈希冲突加剧，需要扩展哈希表的大小。
  2. dict_can_resize为1且负载因子大于等于dict_force_resize_ratio：如果dict_can_resize标志位为1（表示允许重新调整大小），并且负载因子大于等于dict_force_resize_ratio，也会触发扩展rehash。这是一种更宽松的触发条件，只要负载因子达到一定程度且允许调整大小，就会进行扩展。

在dictExpandIfNeeded函数中可以看到相关的触发逻辑：

int dictExpandIfNeeded(dict *d) {
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used >= dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used * 2);
    }
    return DICT_OK;
}

收缩触发条件

当负载因子小于0.1时，会触发收缩rehash。这表示哈希表中的元素数量相对哈希表大小过少，占用了过多的内存空间，通过收缩哈希表可以减少内存占用。在dictRehashIfNeeded函数中可以看到收缩触发的逻辑：

void dictRehashIfNeeded(dict *d) {
    if (!dictIsRehashing(d) && (d->ht[0].used == 0 ||
        (double)d->ht[0].used / d->ht[0].size < dict_force_resize_ratio))
    {
        int ht_size = d->ht[0].used ? d->ht[0].used : 1;
        if (ht_size < dict_force_resize_ratio) ht_size = dict_force_resize_ratio;
        dictExpand(d, ht_size);
    }
}

代码示例

为了更好地理解Redis的rehash机制，我们可以通过一个简单的Python代码示例来模拟类似的渐进式rehash过程。假设我们有一个简单的哈希表，使用列表来模拟哈希表的数组部分，使用字典来模拟链表结构存储键值对。

class HashTable:
    def __init__(self, initial_size=4):
        self.size = initial_size
        self.sizemask = initial_size - 1
        self.used = 0
        self.table = [None] * self.size

    def hash_function(self, key):
        return hash(key) & self.sizemask

    def add(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = {key: value}
        else:
            self.table[index][key] = value
        self.used += 1
        if self.used / self.size >= 1:
            self.rehash()

    def get(self, key):
        index = self.hash_function(key)
        if self.table[index] is not None:
            return self.table[index].get(key)
        return None

    def rehash(self):
        new_size = self.size * 2
        new_sizemask = new_size - 1
        new_table = [None] * new_size

        for bucket in self.table:
            if bucket is not None:
                for key, value in bucket.items():
                    new_index = hash(key) & new_sizemask
                    if new_table[new_index] is None:
                        new_table[new_index] = {key: value}
                    else:
                        new_table[new_index][key] = value

        self.size = new_size
        self.sizemask = new_sizemask
        self.table = new_table

# 测试代码
ht = HashTable()
ht.add('key1', 'value1')
ht.add('key2', 'value2')
ht.add('key3', 'value3')
ht.add('key4', 'value4')
print(ht.get('key1'))  # 输出: value1

在这个示例中，HashTable类模拟了一个简单的哈希表。add方法在插入元素时会检查负载因子，如果负载因子大于等于1，则调用rehash方法进行扩展。rehash方法会创建一个新的更大的哈希表，并将旧表中的所有元素重新插入到新表中。

rehash机制对性能的影响

优点

  1. 避免性能骤降：渐进式rehash避免了一次性重新哈希带来的性能问题。在数据量较大时，一次性重新哈希可能会导致Redis在较长时间内无法处理其他请求，而渐进式rehash将重新哈希的工作分散到多次操作中，减少了对系统性能的影响。
  2. 优化内存使用：通过扩展和收缩哈希表，Redis可以根据实际数据量调整哈希表的大小，从而优化内存使用。在数据量增长时，及时扩展哈希表可以减少哈希冲突，提高查找效率；在数据量减少时，收缩哈希表可以释放多余的内存空间。

缺点

  1. 增加操作复杂度：由于渐进式rehash的存在，每次哈希表操作都需要额外检查rehashidx并可能执行一次迁移步骤，这增加了操作的复杂度。虽然每次迁移步骤的开销较小，但在高并发场景下，这些额外的检查和迁移操作可能会对性能产生一定的影响。
  2. 内存占用增加：在rehash过程中，需要同时维护ht[0]和ht[1]两个哈希表，这会导致在一段时间内内存占用增加。虽然最终会释放ht[0]的内存，但在rehash期间，系统的内存压力会有所上升。

实际应用中的考虑

  1. 数据量预估：在设计使用Redis哈希表的应用时，尽量对数据量有一个合理的预估。如果预计数据量会有较大的增长，提前设置合适的初始哈希表大小可以减少rehash的频率。
  2. 性能监控：通过监控Redis的哈希表负载因子等指标，可以及时了解哈希表的状态。例如，可以使用Redis的INFO命令获取哈希表相关的统计信息，如used_memory、hash_table_size、hash_table_used等，根据这些指标来调整应用的策略。
  3. 高并发场景：在高并发场景下，渐进式rehash可能会对性能产生一定影响。可以考虑在业务低峰期手动触发rehash操作，以减少对正常业务的影响。同时，合理调整dict_can_resize和dict_force_resize_ratio等参数，以平衡性能和内存使用。

总结rehash机制要点

  1. 哈希表结构基础：Redis的哈希表基于dict结构体，包含两个dictht哈希表用于rehash过程。dictEntry结构体存储键值对，通过链表解决哈希冲突。
  2. 渐进式rehash过程：分为初始化、迁移和完成阶段，每次操作逐步迁移部分数据，避免一次性操作带来的性能问题。
  3. 触发条件：扩展触发条件包括负载因子大于等于1且ht[0].used大于阈值，或dict_can_resize为1且负载因子大于等于dict_force_resize_ratio；收缩触发条件是负载因子小于0.1。
  4. 性能影响：优点是避免性能骤降和优化内存使用，缺点是增加操作复杂度和在rehash期间增加内存占用。
  5. 实际应用考虑：合理预估数据量、监控性能指标、在高并发场景下合理安排rehash操作。

通过深入理解Redis的rehash机制及其触发条件，开发者可以更好地优化使用Redis哈希表的应用，提高系统的性能和稳定性。无论是在小型应用还是大规模分布式系统中，对rehash机制的掌握都有助于充分发挥Redis的优势。在实际开发中，结合具体的业务场景和性能需求，灵活运用rehash相关的知识，可以为应用的高效运行提供有力保障。同时，通过代码示例的实践和性能分析，能够更直观地感受到rehash机制在不同情况下的表现，从而做出更合理的决策。无论是从内存管理的角度，还是从高并发处理的角度，深入理解rehash机制都是Redis开发者必不可少的技能之一。