redis学习记录：字典(dict)源码分析

• 最近在看《redis设计与实现》这本书，对于其中一些部分内容我还是很感兴趣的，由此抽空会切进去学习一下实现源码，并且在CSDN上记录一下吧。
• 个人的《redis设计与实现》读书笔记记录：https://github.com/zgg2001/redis_learning

一、前言

  字典是目前使用率蛮高的一种KV存储数据结构，简单说就是一个key对应一个value，并且可以确保通过key可以快速的获取value。
  字典的具体实现还是有很大的差异的。在C++中一般字典结构被称为map，目前stl常用的字典结构有std::map和std::unordered_map，前者的底层实现是红黑树，后者的底层实现为哈希表，两者都可以实现高效率的查询/插入操作。
  回归到redis上，redis中字典的出场率很高，毕竟redis本来就是一个KV内存数据库。可以说其底层就是使用字典来实现的，而常规的增删查改也是基于字典来进行的。但是C语言中是没有内置字典数据结构的，所以redis自己构建了字典实现。

 

二、redis字典的实现思路

  redis的字典底层实现采用哈希表，总体思路和C++里的std::unordered_map思路差不多，简单来说都是哈希表+开链法。但是由于C语言里也没有自己的std::vector，所以redis的字典存储空间也是需要自己通过malloc/free管理。
  从具体实现上来看，redis字典主要由三部分组成：字典部分、哈希表部分、哈希表节点部分。从关系上来看，字典部分含有两张哈希表，而哈希表中含有若干哈希表节点。
  redis的字典思路其实还算是简单，但是其中很多策略和细节的实现我都蛮感兴趣的，所以还是会细看一下。其中个人比较感兴趣的部分有开链法的代码部分以及渐进式rehash的实现部分。

 

三、实现源码分析

1. 哈希表节点数据结构

typedef struct dictEntry {
    
    
    // 键
    void *key;

    // 值
    union {
    
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

  如上为哈希表节点的数据结构，可以说是字典结构里的最底层数据结构。简而言之一个哈希表节点由常规的key、value以及一个next指针组成，还是比较清晰的。
  key的类型为void指针，来实现存各式各样的内容。redis字典的键部分一般都是字符串对象，所以就没有像值部分那样使用联合体来特化内容。
  value部分使用一个联合体，其中有void*类型和有/无符号64位int类型，另外新版本的redis中好像也添加了高精度浮点数double类型。这里使用联合体主要还是为了节省内存，避免存数值内容时的内存浪费。
  next指针部分算是开链法的具体实现，即通过这个指针来把哈希冲突的节点给连接起来，来解决哈希冲突问题。

2. 哈希表数据结构

typedef struct dictht {
    
    
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

  如上为哈希表的数据结构，dictht通过一个dictEntry指针数组来建表。除了基础的表结构，此数据结构中也存放了已使用大小、总大小和大小掩码。
  首先是二级指针table，用于指向一个哈希表节点数组，来保存哈希表节点。所以这部分内存实际上是由字典直接进行管理的，不像是STL里使用std::vector当底层。
  然后说一下sizemask这个属性，其值总是等于size - 1，其实也就是指针数组的下标范围(0 ~ size - 1)，相关公式为index = hash & sizemask，来避免索引值超出数组范围。redis字典的扩容策略要求哈希表大小全部为2的n次方，所以这里进行减一操作就可以获取范围掩码了，还是挺巧妙的。
  剩下的两个属性size和used就比较常规了，没什么好说的。

3. 字典数据结构

typedef struct dict {
    

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;

  如上为字典的数据结构。首先看最重要的，属性ht用于存放哈希表，而且可以看到是用大小为2的数组存的，主要就是为了方便进行渐进式rehash操作，而下面的rehashidx属性用来配合记录rehash进度，rehash部分下面会进行具体分析。
  其次privdata属性是一个void*指针，指向一些特定参数，这些参数用于配合dictType里的回调函数。
  接下来来看type属性，其类型为dictType指针。具体来看内容，dictType结构体里存了一组回调函数，其结构体内容如下：

typedef struct dictType {
    

    // 计算哈希值的函数
    unsigned int (*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;

  可以看到是一组用于操作指定类型键值对的函数，不同的字典配备函数也可能不同，算是为了方便进行泛型编程吧。

4. 渐进式rehash部分

  首先讲一下redis字典的rehash策略，redis中为了防止在进行扩展/收缩的rehash时，由于数据过多造成服务器停止服务，采用了渐进式rehash思路。即rehash不一次性进行完毕，而是分多次、渐进式的对键值对进行rehash操作。
  首先实现渐进式rehash的基础就是得有可记录的、独立的两张新表，对此redis数据结构dict以dictht数组的形式存放哈希表，数组大小为2。日常使用时使用[0]表，在扩展/收缩时，为[1]分配新表，并渐进式将[0]表上的键值对rehash分配到[1]表上。当rehash完成时，[1]表拥有所有键值对而[0]表为空，此时释放[0]表，并将[1]表设置[0]表，再将[1]表置空，此时渐进式rehash流程完全完成。
  还有一个值得一提的重点就是渐进式rehash的具体过程：redis字典数据结构dict中有一个rehash索引rehashidx，每当对rehash过程中的字典进行增删查改操作时，程序除了进行指定操作外，还会将[0]表在rehashidx索引上的所有键值对rehash到[1]表上，随后索引rehashidx值自增一。当渐进式rehash过程结束后，索引rehashidx置为-1，意为未在rehash过程中。
  此外，还需要注意的一个细节是渐进式rehash过程中增删查改的操作。在这个过程中，字典是同时使用[0]和[1]两张表的，所以删、查、改操作会同时在两张表上进行，来保证不会漏数据。例如查找一个键时，会先在[0]表上找，如果没有则会去[1]表上找，找不到再返回。而增操作则会直接将新键值对放在[1]表上，[0]表不进行任何添加操作，这主要是为了保证[0]表数据只减不增，并随着rehash操作最终变成空表。
  然后来看一下具体的实现源码：

int dictRehash(dict *d, int n) {
    

    // 只可以在 rehash 进行中时执行
    if (!dictIsRehashing(d)) return 0;

    // 进行 N 步迁移
    // T = O(N)
    while(n--) {
    
        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */
        // 如果 0 号哈希表为空，那么表示 rehash 执行完毕
        // T = O(1)
        if (d->ht[0].used == 0) {
    
            // 释放 0 号哈希表
            zfree(d->ht[0].table);
            // 将原来的 1 号哈希表设置为新的 0 号哈希表
            d->ht[0] = d->ht[1];
            // 重置旧的 1 号哈希表
            _dictReset(&d->ht[1]);
            // 关闭 rehash 标识
            d->rehashidx = -1;
            // 返回 0 ，向调用者表示 rehash 已经完成
            return 0;
        }

        /* Note that rehashidx can't overflow as we are sure there are more * elements because ht[0].used != 0 */
        // 确保 rehashidx 没有越界
        assert(d->ht[0].size > (unsigned)d->rehashidx);

        // 略过数组中为空的索引，找到下一个非空索引
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;

        // 指向该索引的链表表头节点
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        // 将链表中的所有节点迁移到新哈希表
        // T = O(1)
        while(de) {
    
            unsigned int h;

            // 保存下个节点的指针
            nextde = de->next;

            /* Get the index in the new hash table */
            // 计算新哈希表的哈希值，以及节点插入的索引位置
            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;
        // 更新 rehash 索引
        d->rehashidx++;
    }

    return 1;
}

  可以看到在渐进式rehash的过程里，碰到空索引会跳过并且会自动找下一个非空索引，直至完成指定步数或者[0]表为空。当[0]表为空时，进行释放、交换、重置三连，并标记渐进式rehash结束。
  渐进式rehash的每一步都会把一个索引处内的一条链表rehash至[1]表上，其中涉及到索引更新、计数器更新和置空等操作。

最后看一下各种情况下进行rehash的源码部分：

static void _dictRehashStep(dict *d) {
    
    if (d->iterators == 0) dictRehash(d,1);
}

  首先是封装好的进行单次rehash操作的函数。

dictEntry *dictAddRaw(dict *d, void *key)
{
    
    ...
    // 如果条件允许的话，进行单步 rehash
    // T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);
    ...

  尝试插入键会触发单步rehash。

static int dictGenericDelete(dict *d, const void *key, int nofree)
{
    
   	...
    // 进行单步 rehash ，T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);
    ...

  查找删除节点会触发单步rehash。

dictEntry *dictFind(dict *d, const void *key)
{
    
	...
    // 如果条件允许的话，进行单步 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    ...	

  只进行节点查找也会触发单步rehash。

dictEntry *dictGetRandomKey(dict *d)
{
    
	...
    // 进行单步 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    ...

  随机返回任一节点也会触发单步rehash。

5. 扩容部分

  首先来讲一下redis字典的空间分配策略，总结哈希表空间变化规律如下：

• 当执行扩展操作时：新的大小为第一个大于等于当前已使用大小二倍的2的n次方。例如当前已使用大小为4，执行扩容操作，扩容后哈希表总大小为8(8 >= 4 * 2)。
• 当执行收缩操作时：新的大小为第一个大于等于当前已使用大小的2的n次方。例如当前已使用大小为3，执行收缩操作，收缩后哈希表总大小为4(4 >= 3)。

  哈希表扩展和收缩的情况如下：(负载因子：已使用/总量)

• 当负载因子小于0.1时，进行收缩操作。
• 当未执行BGSAVE/BGREWRITEAOF命令时，负载因子大于等于1时，进行扩展操作。
• 当在执行BGSAVE/BGREWRITEAOF命令时，负载因子大于等于5时，进行扩展操作。

  当执行BGSAVE/BGREWRITEAOF时提高扩展所需负载因子，主要是因为执行这两个命令时都需要redis创建子进程，而此时进行rehash操作可能会触发子进程的"写时复制"机制。所以此时减少rehash操作即可避免不必要的内存写入操作，最大限度的节约内存。
  然后来看一下具体的实现源码：

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

    // 新哈希表
    dictht n;
    
    // 根据 size 参数，计算哈希表的大小
    unsigned long realsize = _dictNextPower(size);

    /* the size is invalid if it is smaller than the number of * elements already inside the hash table */
    // 不能在字典正在 rehash 时进行
    // size 的值也不能小于 0 号哈希表的当前已使用节点
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    // 为哈希表分配空间，并将所有指针指向 NULL
    n.size = realsize;
    n.sizemask = realsize-1;
    // T = O(N)
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

  可以看到这部分在获取下一个大小后进行了内存申请，申请了realsize个dictEntry指针大小的内存。

    // 如果 0 号哈希表为空，那么这是一次初始化：
    // 程序将新哈希表赋给 0 号哈希表的指针，然后字典就可以开始处理键值对了。
    if (d->ht[0].table == NULL) {
    
        d->ht[0] = n;
        return DICT_OK;
    }

    // 如果 0 号哈希表非空，那么这是一次 rehash ：
    // 程序将新哈希表设置为 1 号哈希表，
    // 并将字典的 rehash 标识打开，让程序可以开始对字典进行 rehash
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;

  这部分主要是为了进入rehash状态，当然如果是初始化就不用进rehash状态。

6. 开链法解决哈希冲突部分

  最后我决定看一下开链法的具体实现，毕竟这么有名的思路，看一下redis源码里是怎么写的。首先看一下新增节点的源码部分：

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

    // 如果条件允许的话，进行单步 rehash
    // T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if * the element already exists. */
    // 计算键在哈希表中的索引值
    // 如果值为 -1 ，那么表示键已经存在
    // T = O(N)
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

    // T = O(1)
    /* Allocate the memory and store the new entry */
    // 如果字典正在 rehash ，那么将新键添加到 1 号哈希表
    // 否则，将新键添加到 0 号哈希表
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 为新节点分配空间
    entry = zmalloc(sizeof(*entry));
    // 将新节点插入到链表表头
    entry->next = ht->table[index];
    ht->table[index] = entry;
    // 更新哈希表已使用节点数量
    ht->used++;

    /* Set the hash entry fields. */
    // 设置新节点的键
    // T = O(1)
    dictSetKey(d, entry, key);

    return entry;
}

  太长不看，截取出关键部分：

//hash取下标
index = _dictKeyIndex(d, key);
// 将新节点插入到链表表头
entry = zmalloc(sizeof(*entry));//申请新结点内存
entry->next = ht->table[index];//执行头插操作
ht->table[index] = entry;

  所以实际上redis的开链法实现就是配合着数据结构里的next指针，简单的把每个新节点头插在对应下标的链表上，非常的简单，也就几行代码，完全没有进行任何哈希冲突方面的判定。

 

四、总结

  redis的字典设计的还是非常巧妙的，尤其是其中的渐进式rehash实现。通过这次看具体代码我也是学到了很多新思路，尤其是看源码前完全没想到开链法实现竟然这么简单。
  就个人的感觉来看，redis的代码写的还是蛮清晰简便的，不像C++标准库套来套去非常的恶心。我感觉可能主要是因为C语言比较灵活，没有搞C++强类型那一套，所以通过void*就可以非常简便的实现泛型编程。其次可能就是redis的代码风格比较精简，确实读起来蛮舒服的（当然也是huangz大佬的书写的好）。