凌云的博客

Redis 5 数据结构（四）字典

分类：Redis| 发布时间：2019-04-22 23:49:00

---

概述

本文是 Redis 5 数据结构系列的第四篇，主要讲解字典（dict）的结构和实现细节。

字典的实现

Redis 的字典以哈希表作为底层实现,一个哈希表有多个哈希节点,而每个哈希节点保存了一个字典的键值对。

哈希表

哈希表的定义如下：

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

• table 保存哈希表节点的指针
• size：table 的长度
• sizemask：掩码，等于 size - 1
• used：键值对的个数

哈希表节点的定义如下：

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

dictEntry 主要保存了字典的键指对，由于不同的 key 的哈希值有可能相同，next 指针用于将多个哈希值相同的键值对连接起来成为一个链表。

下图是一个 dictht 的例子：

字典

Redis 字典的定义如下：

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

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;

• type 包含了特定的字典的一组回调方法，根据要创建的字典类型，可以在创建字典时指定不同的 type。
• privdata type 可能会用到的私有数据
• ht 哈希表，平时只用到 ht[0]，在 rehash 期间会用到 ht[1]，下面会详细讲解 rehash 操作
• rehashidx：-1 表示没有进行 rehash，否则表示当前 rehash 的索引
• iterators 目前有多少个迭代器

下图是一个普通状态下的字典（rehashidx=-1）：

哈希函数和键冲突

在对字典进行插入，查找，删除等操作的时候，首先要做的是根据 key 和字典的哈希函数算出哈希值。 以插入为例，首先根据 key 和字典的哈希函得到 hash。 然后根据得到的哈希值 hash 和哈希表的 sizemask 进行与操作得到 idx。

伪代码如下：

hash = hashFunction(key);
idx = hash & sizemask;

举个例子，假设有如下字典。

现在要插入 (k2,v2)，假设：

hash = hashFunction(k2) = 6;
idx = 6 & ht[0].sizemask = 6 & 3 = 2;

因此将 (k2, v2) 插入 ht[0].dictEntry[2]，结果如下：

键冲突

通过上一节的内容我们知道，键插入的位置是通过：

hash = hashFunction(key);
idx = hash & sizemask;

计算出来的。如果此 idx 上已经有数据存在则会发生键冲突。

还是以这个字典为例：

假设要插入 (k3, v3)，假设：

hash = hashFunction(k2) = 7;
idx = 7 & ht[0].sizemask = 7 & 3 = 3;

由于 ht[0].dictEntry[3] 已经有数据，因此 Redis 会将这个链表中的每个节点的 key 和 k3 进行比较（调用 dictType 的 keyCompare），若相等表示已存在 key 相同的节点，否则将 (k3, v3) 插入 ht[0].dictEntry[3] 的表头。 假设 k3 和 ht[0].dictEntry[3] 上的各个节点的 key 均不相等，因此会将 (k3, v3) 插入字典，结果如下：

rehashing

从字典的定义我们知道，每个字典都有两个哈希表，正常情况下我们只会使用一个哈希表（ht[0]）。 当我们需要对哈希表进行扩展或者收缩时会用到 ht[1]，此时字典的 rehashidx 表示处理到 ht[0] 的哪个节点。

当出现如下情况时，Redis 会对哈希表进行扩展：

• 服务没有进行 BGSAVE 或者 BGREWRITEAOF，并且哈希表的负载因子大于 1
• 服务正在进行 BGSAVE 或者 BGREWRITEAOF，并且哈希表的负载因子大于 5

负载因子的计算方式如下：

load_factor = ht[0].used / ht[0].size

当出现如下情况时，Redis 会对哈希表进行收缩（通过 dictResize 函数）

• 哈希表的负载因子小于 0.1

需要注意的是哈希表的 rehash 过程是渐进式的，对于数据库的键空间和 expires 的哈希表，Redis 服务端会在每个服务周期调用：

dictRehashMilliseconds(d, 1);

同时在字典的内部实现中，每次进行插入，查找和删除等操作时都会调用

dictRehash(d, 1);

Redis 只会对数据库的键空间和 expires 的哈希表调用 dictRehashMilliseconds(d, 1); 其他的哈希表只能依靠内部调用 dictRehash(d, 1) 进行缓慢的 rehash 操作。

由于在进行 rehashing 过程中字典同时用到了两个哈希表，因此在 rehashing 过程中，字典的行为会有所变化，具体表现为：

• 查找/删除 等操作时，首先会查找 ht[0]，若未找到则继续查找 ht[1] 若仍未找到，则表示键不存在
• 所有插入数据都会写入 ht[1]

以下网址有字典 rehashing 的示例，可以参考下：

http://1e-gallery.redisbook.com/4-dict.html

dict API

dict *dictCreate(dictType *type, void *privDataPtr);

创建一个字典

#define DICT_OK 0
#define DICT_ERR 1

int dictExpand(dict *d, unsigned long size);

扩展字典，成功返回 DICT_OK，失败返回 DICT_ERR（正在进行 rahashing，或者 size 比哈希表当前大小还小）

int dictAdd(dict *d, void *key, void *val);

添加一个元素

返回值：

• DICT_OK 成功
• DICT_ERR 节点已存在，添加失败

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing);

添加或者查找节点。

返回值：

• NULL 表示已存在此键，*existing 指向已有的节点
• 否则返回添加的节点

dictEntry *dictAddOrFind(dict *d, void *key) {
    dictEntry *entry, *existing;
    entry = dictAddRaw(d,key,&existing);
    return entry ? entry : existing;
}

dictAddRaw 的简单封装，返回新增或者已有的节点。

int dictReplace(dict *d, void *key, void *val);

添加节点或者更新已有的节点的值。 返回值：

• 0 节点已存在，进行值更新
• 1 节点不存在，添加新节点

int dictDelete(dict *d, const void *key);

删除节点，成功返回 DICT_OK，若节点不存在返回 DICT_ERR。

dictEntry *dictUnlink(dict *ht, const void *key);
void dictFreeUnlinkedEntry(dict *d, dictEntry *he);

dictUnlink 用于从字典中移除指定的节点，与 dictDelete 不同的是这个函数会返回移除出字典的节点。 这个函数主要用于当你想将节点删掉前还想根据节点的内容进行某些操作，操作完成后你需要调用 dictFreeUnlinkedEntry 真正释放节点占用的内存。

原先你可能需要进行如下操作：

 entry = dictFind(...);
 // Do something with entry
 dictDelete(dictionary,entry);

这需要查找两次字典，有了这个函数后你可以改为：

entry = dictUnlink(dictionary,entry);
// Do something with entry
dictFreeUnlinkedEntry(entry); // <- This does not need to lookup again.

只需要查找一次字典。

void dictRelease(dict *d);

释放整个字典。

dictEntry * dictFind(dict *d, const void *key);

返回指定的节点，若此节点不存在则返回 NULL。

void *dictFetchValue(dict *d, const void *key);

若节点存在返回节点中的 val，否则返回 NULL。

#define DICT_HT_INITIAL_SIZE     4

int dictResize(dict *d);

收缩字典，若此时可以进行 resize 操作，则将哈希表的大小收缩到当前节点数， 若当前节点数小于 DICT_HT_INITIAL_SIZE 则收缩到 DICT_HT_INITIAL_SIZE。

typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;
} dictIterator;

dictIterator *dictGetIterator(dict *d);
dictIterator *dictGetSafeIterator(dict *d);
dictEntry *dictNext(dictIterator *iter);
void dictReleaseIterator(dictIterator *iter);

以上几个函数主要用于对字典进行遍历。 dictGetSafeIterator 和 dictGetIterator 区别在于会将 safe 设置为 1。 这意味着在遍历过程中可以对字典进行 dictAdd，dictFind 等操作。 如果使用的不是安全的迭代器，在迭代过程中，你只能使用 dictNext()。

dictEntry *dictGetRandomKey(dict *d);

随机返回字典中的一个节点。

unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count);

对字典进行随机采样。

这个函数不保证能返回 count 个节点（字典中节点没那么多的情况下），也不保证返回的节点都是不重复的，

当你需要足够随机分布地返回字典中的节点时这个函数是不适合的，这个函数只适合于根据采样信息进行数据统计的情况。 通过这个函数获取 N 个节点会比使用 dictGetRandomKey() 要快很多。

void dictGetStats(char *buf, size_t bufsize, dict *d);

获取字典的统计信息

uint64_t dictGenHashFunction(const void *key, int len);
uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len);

返回 Redis 字典内部实现的默认哈希函数，目前使用的默认哈希算法为 SipHash（Redis 3.2 以及之前版本默认使用 MurmurHash2）。

void dictEmpty(dict *d, void(callback)(void*));

对字典进行清空，清空过程中每处理 dictht 的 table 中的元素 65536 次（注意不是 dictEntry 的个数）会调用一次传进来的回调函数，传入字典的 privdata 作为参数。

void dictEnableResize(void);
void dictDisableResize(void);

设置 dict.c 里面的全局静态变量 dict_can_resize 来控制是否允许 resizeing 字典中的哈希表。 对于 Redis 来说，当我们 fork 了一个子进程进行一些操作时（比如持久化到 RDB）， 通过 dictDisableResize() 禁止哈希表的 resizeing，是很有必要的，这时我们可以尽量减少由于 COW （由于 fork）导致的内存数据移动。

注意：当 dict_can_resize 设置为 0 后并不是所有的 resize 操作都是被禁止的； 当一个哈希表拥有的节点和 bucket 的数量（就是 table 的元素个数）的比例大于 dict_force_resize_ratio。 哈希表依然会进行 resize 操作。

int dictRehash(dict *d, int n);

进行 N 次增量式 rehashing 操作。 返回 1 表示还有 keys 需要从旧的哈希表移动到新的哈希表。 返回 0 表示 rehash 操作已经完成。

注意：一次 rehash 操作表示将旧的哈希表的一个 bucket（一条链表）移动到新的哈希表中。 由于哈希表中可能有很多空的 bucket，为了避免此函数耗时过长，此函数最多检查哈希表中 N * 10 个 bucket。

int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = 0;

    while(dictRehash(d,100)) {
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}

使用 dictRehash 进行哈希表的 rehash，每次处理哈希表中的 100 个 bucket，然后检查是否已经超过限定时间。

void dictSetHashFunctionSeed(uint8_t *seed);
uint8_t *dictGetHashFunctionSeed(void);

设置/获取 默认的哈希函数的 seed。

typedef void (dictScanFunction)(void *privdata, const dictEntry *de);
typedef void (dictScanBucketFunction)(void *privdata, dictEntry **bucketref);

unsigned long dictScan(dict *d, unsigned long v,
                       dictScanFunction *fn, dictScanBucketFunction *bucketfn,
                       void *privdata);

dictScan() 用于遍历字典的所有节点。

通过如下方式进行迭代：

1. 首先使用 cursor（v） 为 0 来调用这个函数。
2. 当调用这个函数时，函数内部会处理一个 bucket。然后返回新的 cursor。
3. 当返回值为 0 时表示迭代完成。

这个函数保证在遍历过程中都存在的节点会被访问到，但是某些元素可能会被访问多次。

函数会对每个访问到的节点调用 'fn' 回调函数，第一个参数为传入的 privdata 参数，第二个参数为要处理的节点。

uint64_t dictGetHash(dict *d, const void *key);

获取 key 的哈希值。

dictEntry **dictFindEntryRefByPtrAndHash(dict *d, const void *oldptr, uint64_t hash);

根据 hash 和 oldkey 的指针获取节点。 需要注意的是 oldkey 的内存已经被释放，而 hash 是在释放前使用 dictGetHash() 函数预先计算出来的。 这个函数不会进行任何 字符串/key 的对比（只比较指针地址是否相同）。 若未找到对应的节点则返回 NULL。

dictScan

dictScan 的行为有点不是很直观，这里专门讲解下。 dictScan() 用于遍历字典的所有节点。

迭代方式

通过如下方式进行迭代：

1. 首先使用 cursor（v） 为 0 来调用这个函数。
2. 当调用这个函数时，函数内部会处理一个 bucket。然后返回新的 cursor。
3. 当返回值为 0 时表示迭代完成。

这个函数保证在遍历过程中都存在的节点会被访问到，但是某些元素可能会被访问多次。

函数会对每个访问到的节点调用 'fn' 回调函数，第一个参数为传入的 privdata 参数，第二个参数为要处理的节点。

如何工作

这个迭代算法是由 Pieter Noordhuis 设计的。 主要想法是由高比特位对 cursor 进行增加。主要做法就是先将 cursor 进行比特翻转，然后增加 cursor，最后在将 cursor 进行比特翻转。

Redis 使用 http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel 这个网站介绍的算法进行高效的比特翻转，有兴趣的可以看看。

由于哈希表有可能会在多次调用 dictScan 过程中 resize，因此这种策略是很有必要的。

Redis 的哈希表的大小总是 2 的某个次方，一个键的位置的计算方法如下：

idx = HASH(kye) & (SIZE - 1);

比如当前的哈希表的大小为 16，掩码为 15（二进制的 1111）。一个 key 总是位于哈希表的最后 4 个比特。

当哈希表发生 resize 时

当哈希表变大后，一个 key 可能会位于原先位置的 N 倍，比如当前的 cursor 为 01100（掩码为 1111，哈希表大小为 16）。

如果哈希表的大小后来变为 64，新的掩码变为 111111。此时原先 cursor 的数据只会位于 ??1100，问号可能是 0 或者 1。

先遍历高位的比特会让我们在遇到哈希表 resize 的时候不需要重置 cursor。所有位于以 110 结尾的数据都已经被访问过了， 同理其他所有和 cursor 已经遍历的后四位相同的数据也都已经遍历过了。

类似的当哈希表进行收缩的时候也一样。

当我们正在进行 rehash 时

此时我们有两个哈希表，我们总是先访问小的哈希表，然后根据测试当前 cursor 在大的哈希表的扩展。 比如，当前的 cursor 为 101 大的哈希表为 16，小的哈希表为 8，我们在进行 scan 时会同时对大的哈希表的 (0)101 和 (1)101 进行访问。通过这种方式，我们回到了只有一个哈希表类似的逻辑。

限制

这种遍历方式的一个巨大优点是完全无状态的，也不需要任何额外的内存占用。

同时这种设计方式有如下缺点：

1. 同一个节点可能遍历多次，当然在应用层面这很容易解决
2. 每次调用 dictScan 都必须返回多个节点，这是由于必须返回都一个 bucket 的所有数据
3. 逆向的 cursor 有点难以理解

总结

• Redis 的字典通过哈希表实现
• 每个字典都有两个哈希表，正常情况下只会使用第一个，在进行 rehashing 的情况下，会两个都使用
• 当数据库键空间和 expires 的哈希表正在进行 rehash 时，Redis 服务端会在每个服务周期分出 1 毫秒对其进行 rehash
• 每次对字典进行操作时也会对正在 rehash 的哈希表进行一次 rehash 操作
• dictScan 通过巧妙的设计实现了无状态的遍历方法

参考

• dict.c
• 《Redis 设计与实现》图片集