Redis 中的字典是如何实现的？

写在文章开头

redis作为非关系数据库，其底层采用了字典(也称为映射)保存键值对。本文会基于源码分析的方式带你了解redis中这一常见数据结构的精巧设计，希望对你有帮助。

详解redis中的字典的设计与实现

哈希表的基本数据结构

字典用table管理当前存储键值对的数组，这个数组的大小可有size这个字段知晓，每当我们有一个键值对要存储到字典时就会通过sizemask进行按位与运算得到table数组的某个索引位置将当前键值对存储，然后自增一个used标识当前有一个节点加入。

可能上文说的比较抽象，我们不妨举个例子，假设我们现在键入如下指令:

HSET student  xiaoming 18

redis完成命令解析后，定位到student这个key对应的字段空间的字典，找到当前正在使用的哈希表，按照如下步骤完成键值对存储：

1. 计算xiaoming的哈希值。

2. 将计算出的哈希值和sizemask即3，也就是数组的索引范围进行按位与运算，得到对应的数组索引位置。

3. 查看该位置是否有元素，如果没有则直接添加，反之追加到该dictEntry的后面，这也就是我们常说的链地址法。

4. used字段自增一下，表示当前哈希表有一个元素。

我们可以在dict.h看到上文所提及的哈希表和字典中每一个元素的数据结构：

typedef struct dictht {
 //存储键值对的哈希表
    dictEntry **table;
    //当前哈希表的大小
    unsigned long size;
    //计算哈希值的掩码值
    unsigned long sizemask;
    //当前哈希表的节点数
    unsigned long used;
} dictht;

//记录键值对的数据结构dictEntry 
typedef struct dictEntry {
 //指向键的指针
    void *key;
    
    //通过共用体存储值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //next指针指向下一个dictEntry 
    struct dictEntry *next;
} dictEntry;

字典的数据结构

哈希表在极端算法情况下会造成大量键值对冲突碰撞的情况，导致查询效率由原来的O(n)变为O(1)，所以为了保证针对冲突的数组进行优化，redis的字典采用的双数组的方式管理键值对，如下图所示，可以看到dict的数据结构定义了大小为2的哈希表数组，当某个哈希表碰撞激烈需要进行调整时就调整算法将对应的键值对存到dictht[1]，并通过rehashidx标志为-1表示当前处于渐进式哈希阶段：

对应的我们也可以在dict.h看到dict 的定义：

typedef struct dictht {
 //存储键值对的哈希表
    dictEntry **table;
    //当前哈希表的大小
    unsigned long size;
    //计算哈希值的掩码值
    unsigned long sizemask;
    //当前哈希表的节点数
    unsigned long used;
} dictht;

//记录键值对的数据结构dictEntry 
typedef struct dictEntry {
 //指向键的指针
    void *key;
    
    //通过共用体存储值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //next指针指向下一个dictEntry 
    struct dictEntry *next;
} dictEntry;

字典的创建

进行键值对创建时，dictCreate会进行必要的内存分配，然后进入初始化工作：

1. 初始化两个哈希表空间。

2. 设置类型特定函数type ，这个type 包含了各种类型哈希值计算、值复制以及键比对等各种方法的指针。

3. 设置私有数据privdata 。

4. 初始化rehashidx 为-1表示未进行渐进式再哈希。

对应的我们可以在dict.c中看到这段源代码：

/* Create a new hash table */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
 //内存分配
    dict *d = zmalloc(sizeof(*d));
 //字典初始化
    _dictInit(d,type,privDataPtr);
    return d;
}

/* Initialize the hash table */
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;
}

元素的插入

字典的插入操作大体流程也很市面上常见的哈希表实现差不多，通过哈希算法(MurmurHash2)定位元素插入的位置再进行插入操作，唯一有所区别的是，redis版本字典的链地址法解决冲突的上的优化，为了保证哈希定位的位置存在元素时能够快速插入，redis字典的插入采用的是头插法，即将最新的元素作为链表头元素插入:

与之对应的我们给出代码的入口，也就是dict.c下的dictAdd方法，可以看到其内部是通过完成键的添加，只有key插入成功后才会通过setVal方法维护插入的entry的值：

int dictAdd(dict *d, void *key, void *val)
{
 //通过dictAddRaw完成key的插入
    dictEntry *entry = dictAddRaw(d,key);
 //如果插入成功再维护value
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictAddRaw逻辑也比较简单，先检查当前的字典表是否因为大量冲突而处理渐进式哈希(关于渐进式哈希后文会详细讲解，这里也补充一些简单的概念)，通过_dictKeyIndex定位到当前元素插入的索引位置，采用头插法将其插入到对应索引位置的链表首部:

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;
 //是否处于渐进式哈希阶段
    if (dictIsRehashing(d)) _dictRehashStep(d);

   //定位索引位置
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

   //定位要存储元素的哈希表位置
    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. */
    dictSetKey(d, entry, key);
    return entry;
}

哈希冲突及其对应解决方案

随着我们不断的新增键值对，当前的哈希算法得到的索引位置很大概率会出现哈希冲突，即每次定位到的索引位置都很大概率存在元素，这也就是我们的常说的哈希冲突，这就是redis的字典默认会初始化两张哈希表的原因所在。 符合以下两个条件时，字典就会触发扩容机制:

1. 未进行BGSAPE命令或者BGREWRITEAOF持久化操作，且当前哈希表元素数何哈希表空间大小一样。

2. 正进行BGSAPE命令或者BGREWRITEAOF持久化操作，当且哈希表元素数是哈希表空间的5倍。

触发扩容时，字典会将rehashidx设置为0意为当前因为大量冲突碰撞而从0索引开始渐进式再哈希，ht[1]就会开辟一个ht[0]即当前正在使用的哈希表空间大小*2的空间，后续的新插入的元素也都会根据哈希算法将元素插入到ht[1]中。 对于旧有存在的元素，考虑到整个哈希表可能存在不可预估数量的键值对，redis的字典会通过渐进式哈希的方式在元素每次进行增删改查操作时将旧有元素迁移到ht[1]中，一旦所有元素全部迁移到ht[1]后，哈希表就会将ht[1]指向的哈希表指针赋值给ht[0]，并将ht[0]原有哈希表释放。

了解整体的设计之后，我们就可以从源码角度印证这个问题了，可以看到字典在每次进行哈希索引定位时都会调用_dictKeyIndex方法，而该方法内部则有一个_dictExpandIfNeeded操作，其内部就会根据我们上文所说的阈值判断当前哈希表是否需要进行扩容:

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

    //判断当前哈希表是否需要进行扩容操作
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
   //获取当前key的哈希值
    h = dictHashKey(d, 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 -1;
            he = he->next;
        }
        //如果不处于渐进式哈希阶段，则直接将该索引值返回，后续元素直接存入ht[0]表中，反之进入下一个循环计算当前元素在ht[1]表的索引
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

我们继续步入_dictExpandIfNeeded即可看到扩容判断的逻辑，也就是我们上文所说的符合两个扩容条件之一时就会触发扩容：

static int _dictExpandIfNeeded(dict *d)
{
 //如果正处于渐进式哈希则直接返回
    if (dictIsRehashing(d)) return DICT_OK;

   //......
   //如果当前有子进程进行持久化操作则dict_can_resize为false，所以当字典元素数大于等于哈希表大小且未进行持久化，或进行持久化操作且元素数是哈希表的5倍时才会进行扩容操作，dictExpand会将rehashidx设置为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;
}

此时我们再回看之前的键值对插入操作，它会根据dictIsRehashing判断rehashidx是否为0，从而调用_dictRehashStep进入渐进式哈希操作在键值对维护：

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;
 //如果处于再哈希阶段，若符合要求则进行一次ht[0]哈希表元素驱逐操作
    if (dictIsRehashing(d)) _dictRehashStep(d);

   //保存键值对操作
   //......
    return entry;
}

我们直接查看_dictRehashStep内部的实现就可以看到一个dictRehash的方法，它就是渐进式哈希的核心实现，可以看到该方法会从0开始每次驱逐10个元素到ht[1]中：

int dictRehash(dict *d, int n) {
 //驱逐10个元素
    int empty_visits = n*10; 
    if (!dictIsRehashing(d)) return 0;
    
 //将当前rehashidx中的元素驱逐到ht[1]中
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        //当前索引位置为空，说明驱逐完成返回1，下次继续
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        //计算当前元素在ht[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;
        d->rehashidx++;
    }

  //used 为0说明所有元素驱逐完成，将ht[1]指向的哈希表赋值给ht[0]，重置rehashidx ，并返回0
    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;
    }

    /* More to rehash... */
    return 1;
}

查询操作

有了上述的基础后，我们查看查询操作就比较简单了，其步骤比较固定:

1. 计算key的哈希值。

2. 计算对应索引位置到ht[0]定位，如果找到了直接返回。

3. 如果没找到，查看当前是否处于扩容阶段，若是则到ht[1]进行哈希定位，若找到直接返回。

4. 上述操作都未找到该元素，直接返回null。

dictEntry *dictFind(dict *d, const void *key)
{
    //......
    //计算哈希值
    h = dictHashKey(d, 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;
        }
        //上一步没找到则判断是否处于扩容，若处于扩容则进入下一个循环到ht[1]表找，反之直接返回null
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

删除操作

同理我们最后给出删除操作的源码，也查询操作一样，定位到元素后，将其从索引位置中解除该元素和前驱节点关系即可:

static int dictGenericDelete(dict *d, const void *key, int nofree)
{
 //......
 
    //定位元素
    h = dictHashKey(d, key);
 
    for (table = 0; table <= 1; table++) {
        idx = h & 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;
                //释放当前节点
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                zfree(he);
                //元素数减去1
                d->ht[table].used--;
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return DICT_ERR; /* not found */
}

小结

本文笔者从字典的数据结构和常见操作的角度对redis中字典的设计思想和优化思路进行深入的剖析，希望对你有帮助。

参考

《Redis设计与实现》