聊聊 Redis中 的字典设计与实现
Redis作为非关系数据库，其底层采用了字典(也称为映射)保存键值对。本文会基于源码分析的方式带你了解redis中这一常见数据结构的精巧设计，希望对你有帮助。
哈希表的数据结构
我们简单说明一下redis字典数据结构特征：
- 用table管理当前存储键值对而table本质上就是一个数组
- 数组的大小可采用一个size字段维护
- 添加一个键值时，会通过sizemask进行按位与运算得到table数组的某个索引位置并将其存储，然后自增一下哈希表的used字段，标识当前数组元素+1。
可能上文说的比较抽象，我们不妨举个例子，假设我们现在键入如下指令:
HSET student xiaoming 18redis完成命令解析后，定位到student这个key对应的字段空间的字典，找到当前正在使用的哈希表，按照如下步骤完成键值对存储：
- 计算xiaoming的哈希值。
- 将计算出的哈希值和sizemask即3，也就是数组的索引范围进行按位与运算，得到对应的数组索引位置。
- 查看该位置是否有元素，如果没有则直接添加，反之追加到该dictEntry的后面，这也就是我们常说的链地址法。
- used字段自增一下，表示当前哈希表有一个元素。
我们可以在dict.h看到上文所提及的哈希表和字典中每一个元素的数据结构：
typedef struct dictht {
//存储键值对的哈希表
dictEntry **table;
//当前哈希表的大小
unsignedlong size;
//计算哈希值的掩码值
unsignedlong sizemask;
//当前哈希表的节点数
unsignedlong used;
} dictht;
//记录键值对的数据结构dictEntry
typedefstruct dictEntry {
//指向键的指针
void *key;
//通过共用体存储值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
//next指针指向下一个dictEntry
struct dictEntry *next;
} dictEntry;字典的数据结构
上文我们讲解了哈希结构，而哈希表在极端算法情况下会造成大量键值对冲突碰撞的情况，导致查询效率由原来的O(1)变为O(n)，所以为了保证针对冲突的数组进行优化，redis的字典采用的双数组的方式管理键值对，所以这一小节我们着重说明redis如何基于字典管理两个哈希表空间。
对应的我们也可以在dict.h看到dict 的定义，可以看到字典维护哈希表字段ht是一个空间为2的数组：
typedef struct dict {
//.......
//定义2个哈希表
dictht ht[2];
//-1时表示当前哈希表处于渐进式哈希
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
//.......
} dict;如下图所示，可以看到dict的数据结构定义了大小为2的哈希表数组，当某个哈希表碰撞激烈需要进行调整时，就会采用渐进式哈希算法将键值对存到dictht[1]，并通过rehashidx标志为-1表示当前处于渐进式哈希阶段：
字典的初始化创建
进行键值对创建时，dictCreate会进行必要的内存分配，然后进入初始化工作：
- 初始化两个哈希表空间。
- 设置类型特定函数type ，这个type 包含了各种类型哈希值计算、值复制以及键比对等各种方法的指针。
- 设置私有数据privdata 。
- 初始化rehashidx 为-1表示未进行渐进式再哈希。
对应的我们可以在dict.c中看到dictCreate函数的源代码：
/* 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)
returnNULL;
//定位要存储元素的哈希表位置
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的字典默认会初始化两张哈希表的原因所在。
符合以下两个条件时，字典就会触发扩容机制:
- 未进行BGSAVE命令或者BGREWRITEAOF持久化操作，且当前哈希表元素数和哈希表空间大小一样。
- 正进行BGSAVE命令或者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, constvoid *key)
{
unsignedint 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即可看到扩容判断的逻辑，也就是我们上文所说的符合两个扩容条件：
- 数组0使用空间大于等于数组长度且dict_can_resize为1(持久化结束或者未进行持久化这个值都不会被设置为1)，若为1则是允许resize操作。
- 数组0使用空间大于等于数组长度，且数组0使用空间已经打到数组长度的5倍。
只要符合上述的条件，该函数就会调用dictExpand触发扩容，并将rehashidx设置为0即代表从数组0的索引0位置尝试渐进式驱逐：
static int _dictExpandIfNeeded(dict *d)
{
//......
/**
* 如果数组0使用空间大于等于数组长度则判断：
* 1. dict_can_resize是否为1(持久化结束或者未进行持久化这个值都不会被设置为1)，若为1则是允许resize操作
* 2. 数组0使用空间是否是数组长度的5倍
* 若符合上述要求，则调用dictExpand将数组1设置为数组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;
//dictIsRehashing会判断当前是否处于再哈希阶段，若符合要求则进行一次ht[0]哈希表元素驱逐操作
if (dictIsRehashing(d)) _dictRehashStep(d);
//保存键值对操作
//......
return entry;
}我们直接查看_dictRehashStep内部的实现就可以看到一个dictRehash的函数，它就是渐进式哈希的核心实现，该方法会从0开始每次驱逐10个元素到ht[1]中：
int dictRehash(dict *d, int n) {
//基于传入的n得出访问空bucket的最大次数，默认为1*10=10
int empty_visits = n*10;
if (!dictIsRehashing(d)) return0;
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
assert(d->ht[0].size > (unsignedlong)d->rehashidx);
//基于empty_visits 循环找到第一个非空的bucket
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return1;
}
//定位到需要驱逐元素的bucket
de = d->ht[0].table[d->rehashidx];
//计算当前元素在ht[1]中的位置并驱逐过去
while(de) {
unsignedint 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;
//旧有哈希表元素数减去1
d->ht[0].used--;
//新的哈希元素空间加上1
d->ht[1].used++;
//de指向下一个元素，进行下一轮迭代
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;
return0;
}
return1;
}查询操作
有了上述的基础后，我们查看查询操作就比较简单了，其步骤比较固定:
- 计算key的哈希值。
- 计算对应索引位置到ht[0]定位，如果找到了直接返回。
- 如果没找到，查看当前是否处于扩容阶段，若是则到ht[1]进行哈希定位，若找到直接返回。
- 上述操作都未找到该元素，直接返回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)) returnNULL;
}
returnNULL;
}删除操作
同理我们最后给出删除操作的源码，也查询操作一样，定位到元素后，将其从索引位置中解除该元素和前驱节点关系即可:
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 */
}
