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

Redis 字典实现的内存管理策略

2021-07-142.9k 阅读

Redis 字典概述

Redis 作为一款高性能的键值对存储数据库，字典（dict）是其核心数据结构之一，用于实现数据库的核心功能，如键值对的存储与查询。Redis 字典采用哈希表作为底层实现，能够在平均情况下以 O(1) 的时间复杂度完成查找、插入和删除操作。

在 Redis 中，字典由 dict 结构体表示，其定义如下：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

其中，type 字段指向一个 dictType 结构体，该结构体定义了针对不同数据类型的操作函数，例如哈希函数、比较函数等。privdata 字段则用于传递一些与特定数据类型相关的私有数据。

ht 数组包含两个 dictht 哈希表，主要用于 rehash 操作。rehashidx 字段用于记录当前 rehash 操作的进度，当 rehashidx 为 -1 时，表示当前没有进行 rehash 操作。iterators 字段记录当前正在运行的迭代器数量。

哈希表（dictht）结构

dictht 结构体定义了哈希表的具体结构，如下所示：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
  • table 是一个指向 dictEntry 指针数组的指针，每个 dictEntry 指针指向一个哈希表节点，即实际存储键值对的地方。
  • size 表示哈希表的大小，即 table 数组的长度。
  • sizemask 用于计算哈希值在 table 数组中的索引位置，其值为 size - 1。
  • used 表示哈希表中已使用的节点数量。

哈希表节点（dictEntry）结构

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 字典的内存管理策略

  1. 初始内存分配 当创建一个新的 Redis 字典时，会分配一个 dict 结构体和一个初始的 dictht 哈希表。哈希表的初始大小通常为 4，这意味着会分配一个包含 4 个 dictEntry 指针的数组。此时，used 字段为 0，表示哈希表中没有存储任何键值对。

以下是简化的创建字典的代码示例：

dict *dictCreate(dictType *type, void *privDataPtr) {
    dict *d = zmalloc(sizeof(*d));
    _dictInit(d, type, privDataPtr);
    return d;
}

int _dictInit(dict *d, dictType *type, void *privDataPtr) {
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}

void _dictReset(dictht *ht) {
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

在上述代码中，dictCreate 函数首先为 dict 结构体分配内存，然后调用 _dictInit 函数初始化 dict 结构体的各个字段，包括两个 dictht 哈希表。_dictReset 函数将 dictht 哈希表的各个字段初始化为默认值。

  1. 动态扩容与缩容 随着键值对的不断插入和删除，哈希表的负载因子（used / size）会发生变化。为了保证字典的性能，Redis 会根据负载因子动态调整哈希表的大小，即进行扩容或缩容操作。

扩容条件： 当哈希表的负载因子达到一定阈值时，会触发扩容操作。Redis 默认的负载因子阈值为 1，即当 used 等于 size 时，会进行扩容。扩容时，新的哈希表大小为原大小的两倍（如果原大小小于 1024），否则为原大小的 1.5 倍。

以下是扩容的核心代码逻辑：

int dictExpand(dict *d, unsigned long size) {
    dictht n;
    unsigned long realsize = _dictNextPower(size);
    if (dictIsRehashing(d)) return DICT_ERR;
    if (d->ht[0].used > realsize) return DICT_ERR;

    _dictReset(&n);
    n.size = realsize;
    n.sizemask = realsize - 1;
    n.table = zcalloc(realsize * sizeof(dictEntry*));

    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

unsigned long _dictNextPower(unsigned long size) {
    unsigned long i = DICT_HT_INITIAL_SIZE;
    if (size >= LONG_MAX) return LONG_MAX;
    while(1) {
        if (i >= size) return i;
        i *= 2;
    }
}

在 dictExpand 函数中，首先计算新的哈希表大小 realsize，然后初始化一个新的 dictht 哈希表 n，并为其分配内存。接着将新的哈希表赋值给 d->ht[1]，并将 rehashidx 设置为 0，开始进行 rehash 操作。

缩容条件： 当哈希表的负载因子小于 0.1 时，会触发缩容操作。缩容时，新的哈希表大小为原大小的 1.5 倍（如果原大小大于 4），否则保持原大小不变。

以下是缩容的核心代码逻辑：

int dictResize(dict *d) {
    int minimal;
    unsigned long used = dictSlots(d);
    minimal = d->ht[0].used;
    if (used > minimal) used = minimal;
    if (used < d->ht[0].size/4 && d->ht[0].size > DICT_HT_INITIAL_SIZE) {
        return dictExpand(d, d->ht[0].used*2);
    } else if (used > d->ht[0].size &&
               (d->ht[0].size < DICT_HT_INITIAL_SIZE ||
                used > d->ht[0].size*2)) {
        return dictExpand(d, d->ht[0].used);
    }
    return DICT_OK;
}

在 dictResize 函数中，首先计算当前哈希表中实际使用的槽位数 used，然后根据负载因子判断是否需要进行缩容或扩容操作。如果负载因子小于 0.1 且原大小大于初始大小 4，则进行缩容操作；如果负载因子大于 1 且满足一定条件，则进行扩容操作。

  1. Rehash 操作 Rehash 操作是将旧哈希表中的键值对重新计算哈希值并迁移到新哈希表中的过程。由于 Redis 是单线程的，为了避免在 rehash 过程中阻塞其他操作，Redis 采用渐进式 rehash 策略。

渐进式 rehash 过程如下：

  • 初始化时，rehashidx 为 -1，表示没有进行 rehash 操作。当需要进行 rehash 时，rehashidx 被设置为 0。
  • 在每次对字典进行插入、删除、查找或迭代操作时，会顺带将一定数量的键值对从旧哈希表迁移到新哈希表。每次迁移的数量通常为 1 个，但在某些情况下可能会更多。
  • 当旧哈希表中的所有键值对都迁移到新哈希表后，rehashidx 被重新设置为 -1，rehash 操作完成。

以下是渐进式 rehash 的关键代码片段：

static int _dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        while(de) {
            uint64_t 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;
        }
        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 0;
    }
    return 1;
}

在 _dictRehash 函数中，通过循环将旧哈希表 d->ht[0] 中索引为 rehashidx 的链表上的所有键值对迁移到新哈希表 d->ht[1] 中。迁移完成后，将旧哈希表中对应的槽位设置为 NULL，并将 rehashidx 加 1。当旧哈希表中的所有键值对都迁移完毕后，释放旧哈希表的内存，并将 rehashidx 设置为 -1。

  1. 内存释放 当删除字典中的键值对时，不仅要从哈希表中移除对应的 dictEntry 节点，还要释放该节点及其键值所占用的内存。如果删除操作导致哈希表的负载因子过低，可能会触发缩容操作，进一步释放多余的内存。

以下是删除键值对的核心代码：

int dictDelete(dict *d, const void *key) {
    dictEntry *de;
    int space_freed;

    if (dictIsRehashing(d)) _dictRehashStep(d);
    de = _dictFind(d, key);
    if (!de) return DICT_ERR;

    space_freed = dictFreeUnlinkedEntry(d, de);
    if (space_freed && dict_can_resize &&
        d->ht[0].used < d->ht[0].size/10 &&
        d->ht[0].size > DICT_HT_INITIAL_SIZE)
    {
        dictResize(d);
    }
    return DICT_OK;
}

int dictFreeUnlinkedEntry(dict *d, dictEntry *de) {
    if (de->v.val) d->type->valfree(d->privdata, de->v.val);
    d->type->keyfree(d->privdata, de->key);
    zfree(de);
    return 1;
}

在 dictDelete 函数中，首先检查是否正在进行 rehash 操作，如果是则执行一步 rehash 操作。然后通过 _dictFind 函数查找要删除的键值对对应的 dictEntry 节点。找到节点后，调用 dictFreeUnlinkedEntry 函数释放节点及其键值所占用的内存。最后，如果删除操作导致负载因子过低且满足缩容条件，则调用 dictResize 函数进行缩容操作。

内存管理策略的优化与思考

  1. 负载因子的权衡 负载因子是决定 Redis 字典性能和内存使用的关键因素。较高的负载因子可以减少内存使用，但会增加哈希冲突的概率，从而降低查询性能；较低的负载因子可以提高查询性能，但会浪费更多的内存。Redis 默认的负载因子阈值为 1，在大多数情况下能够在性能和内存使用之间取得较好的平衡。然而，对于一些对性能要求极高或内存非常紧张的场景，可以根据实际情况调整负载因子阈值。

  2. 渐进式 rehash 的开销 渐进式 rehash 虽然避免了一次性 rehash 带来的阻塞问题，但也增加了每次操作的额外开销。在高并发场景下，频繁的插入、删除等操作可能会导致 rehash 操作过于频繁，从而影响系统性能。为了减少这种影响，可以适当调整每次 rehash 迁移的键值对数量，或者在系统负载较低时手动触发 rehash 操作。

  3. 内存碎片问题 由于 Redis 频繁地进行内存分配和释放操作，可能会导致内存碎片的产生。内存碎片会降低内存的利用率，甚至可能导致系统因内存不足而无法分配足够的连续内存块。为了减少内存碎片，可以选择合适的内存分配器，如 jemalloc，它在处理小内存块的分配和释放方面具有较好的性能，能够有效减少内存碎片的产生。

  4. 多线程与内存管理 随着多核处理器的广泛应用，多线程技术在提高系统性能方面具有巨大潜力。然而，在 Redis 中引入多线程需要谨慎考虑内存管理问题。多线程环境下，对共享内存的访问需要进行同步控制，否则可能会导致数据竞争和内存不一致等问题。同时，多线程的内存分配和释放也需要更加精细的管理，以避免内存泄漏和内存碎片等问题。

总结

Redis 字典的内存管理策略是其高性能和高效内存使用的关键所在。通过动态扩容与缩容、渐进式 rehash 等机制，Redis 能够在保证查询性能的同时，合理地利用内存资源。在实际应用中，深入理解这些内存管理策略，根据具体场景进行优化和调整，对于提高 Redis 系统的性能和稳定性具有重要意义。同时，随着硬件技术的不断发展和应用场景的日益复杂，内存管理技术也需要不断演进和创新，以满足日益增长的性能和资源需求。