
- 本文对Redis源码的学习是基于5.0.2版本.
前言
Redis实现的字典是一种key-value键值对的数据结构,如果你看过Java的HashMap这种key-value键值对数据结构的源码,那么本文对你来说难度并不大.
本人对Redis实现的字典比较有感兴趣的是作者实现的渐进式扩容(rehash),但本文也会全面分析字典的增删改查.
Dict --- (源文件dict.h/dict.c)
Dict的结构体如下 :
# dictEntry
# key-value 结构
typedef struct dictEntry {
// key
void *key;
// value
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
// next指针,指向下一个dictEntry,用来解决哈希冲突
struct dictEntry *next;
} dictEntry;
# dictht
# 哈希表,正真来存数据的(dictEntry),默认初始化为长度4的哈希表数组
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 当前哈希表数组是多少个桶,即size个桶
unsigned long size;
// size-1,方便用于计算数组索引值
unsigned long sizemask;
// 当前哈希表数组中存放了多少个dictEntry,即存储的元素个数
unsigned long used;
} dictht;
# dict
# 通过dict来操作dictht
typedef struct dict {
// 该属性用于多态字典 : 类型特定函数
dictType *type;
// 该属性用于多态字典 : 私有数据
void *privdata;
// 2个dictht哈希表数组
dictht ht[2];
// rehash时该值起到作用,表示从哪个索引值开始rehash
// rehashidx == -1 时表示当前不是处于rehash状态
long rehashidx;
// 当前运行的迭代器数,等于0时表示支持rehash
unsigned long iterators;
} dict;
# dictType
# dict的多态调用函数
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;
- dictType : 每个dictType保存了用于操作特定类型键值对的函数,Redis会为用途不同的字典设置不同的类型特定函数.
- privdata : 保存了需要传给那些类型特定函数的可选参数
- ht[2] : 包含两个数组,即数组中2个dictht哈希表数组,一般情况下,只使用ht[0]哈希表,ht[1]在rehash的情况下才会使用.
- 【PS : 什么是rehash : 哈希表保存的键值对逐渐地增多或者减少,为了让哈希表的负载因子维持在一个合理的范围之内,当哈希表保存的键值对数量太多或者太少时,需要对哈希表进行扩展或者收缩,即迁移数据】
dict 结构体如下图 :

创建 --- dictCreate()
dictCreate()
dictCreate() : 初始化dict
# dictCreate()
dict *dictCreate(dictType *type,
void *privDataPtr)
{
1. // 申请内存
dict *d = zmalloc(sizeof(*d));
2. // 最终调用 _dictInit()
_dictInit(d,type,privDataPtr);
return d;
}
_dictInit()
# _dictInit
int _dictInit(dict *d, dictType *type,
void *privDataPtr)
{
// 初始化两个 dictht
_dictReset(&d->ht[0]);
_dictReset(&d->ht[1]);
d->type = type;
d->privdata = privDataPtr;
// 默认为 -1
d->rehashidx = -1;
// 默认为 0
d->iterators = 0;
return DICT_OK;
}
# _dictReset
static void _dictReset(dictht *ht)
{
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}
添加操作 --- dictAdd()
# dictAdd()
int dictAdd(dict *d, void *key, void *val)
{
// 调用dictAddRaw(),该函数下面具体分析
// 该函数包揽了很多工作 :
// 检查 初始化、扩容、是否相同的key值dictEntry
// 创建dictEntry、保存key等
// 最终会返回一个dictEntry
dictEntry *entry = dictAddRaw(d,key,NULL);
if (!entry) return DICT_ERR;
// 保存value
dictSetVal(d, entry, val);
return DICT_OK;
}
实则很多工作被dictAddRaw()包揽了,重点看看这个函数.
是否需要迁移数据、扩容、保存key --- dictAddRaw()
这个函数我分为三大部分 :
- ①检查当前字典是否需要迁移数据 : dictRehashStep()
- ②迁移完成后则执行获取index,并且检查当前字典是否需要初始化或者扩容、是否有相同的key值dictEntry : dictKeyIndex()
- ③如果能走到这一步,说明没有相同的key值dictEntry,需要创建dictEntry并且保存key值后插入到对应的index位置中(头部插入法)
# dictAddRaw()
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
# 检查当前字典是否需要迁移数据
1.// 如果目前处于rehash状态, 执行 _dictRehashStep(),该函数下面具体分析
// _dictRehashStep() : 判断是否需要迁移数据
if (dictIsRehashing(d)) _dictRehashStep(d);
# 迁移完成后则执行获取index,并且检查当前字典是否需要初始化或者扩容
2. // 否则目前并非处于rehash状态 或者 已完成迁移动作
// 获取index索引,_dictKeyIndex(),该函数下面具体分析
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
# 如果能走到这一步,说明没有相同的key值dictEntry,需要创建dictEntry并且保存key值后插入到对应的index位置中(头部插入法)
3. // 如果当前处于rehash状态,则使用ht[1]
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
4. 申请内存
entry = zmalloc(sizeof(*entry));
5. 头部插入法
entry->next = ht->table[index];
ht->table[index] = entry;
6. 存储的个数+1
ht->used++;
7. // 保存key指
dictSetKey(d, entry, key);
return entry;
}
三大步骤:
- ①判断是否执行迁移数据 : 如果当前处于rehash状态,则最终调用dictRehash()来迁移数据,每次最大迁移10个桶的数据,无论桶中有没有数据;
- ②获取index索引 : 根据_dictKeyIndex()来获取;
- ③将dictEntry插入到字典中 :
- 如果当前处于rehash状态,则使用ht[1];
- 头部插入法
- 保存dictEntry的key值.
dictRehashStep() --- 是否执行迁移数据
- 该函数会判断是否需要迁移数据,只有在哈希表没有绑定安全迭代器的情况下才执行,当我们的迭代器处于重新哈希的状态时,我们不进行迁移数据的操作,否则某些元素可能会丢失或重复.
- 此函数由字典中的常用查找或更新操作调用,以便哈希表在活动使用时自动从h1迁移到h2.
# dictRehashStep()
static void _dictRehashStep(dict *d) {
// 迭代器为0,可以迁移数据
if (d->iterators == 0) dictRehash(d,1);
}
dictRehash() --- 迁移数据
# dictRehash()
int dictRehash(dict *d, int n) {
// 最大迁移10个桶的数据,无论桶中有没有数据
int empty_visits = n*10;
1. // 再次判断一下当前是否处于rehash状态
if (!dictIsRehashing(d)) return 0;
# 迁移数据
2. // 迁移数据
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
assert(d->ht[0].size > (unsigned long)d->rehashidx);
2.1 // 根据rehashidx获取需要迁移的桶
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
2.2 // 已完成10个桶数据的迁移
if (--empty_visits == 0) return 1;
}
2.3 // 开始迁移索引值为rehashidx的桶数据
de = d->ht[0].table[d->rehashidx];
while(de) {
uint64_t h;
nextde = de->next;
2.3.1 // 重新计算索引值
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
2.3.2 // 头指针插入
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
2.3.3 // 保存used
d->ht[0].used--;
d->ht[1].used++;
2.3.4 // 继续操作下一dictEntry结点
de = nextde;
}
2.4 // 索引值为rehashidx的桶数据迁移完成
d->ht[0].table[d->rehashidx] = NULL;
2.5 // 继续推进迁移
d->rehashidx++;
}
3. // 检查是否全部迁移完成
if (d->ht[0].used == 0) {
3.1 // 回收ht[0]
zfree(d->ht[0].table);
3.2 // ht[0] 指向 ht[1]
d->ht[0] = d->ht[1];
3.3 // 重新初始化h[1]
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
return 1;
}
_dictKeyIndex() --- 获取index索引值
dictKeyIndex() : 该函数的最终目的是计算索引值,即根据key、sizemask计算索引值.
首先检查当前字典是否需要初始化或者扩容,最后根据key判断当前字典是否存在相同的key值dictEntry,如果出现,则保留原先的,新插入的value并没有进行替换旧的value.否则没有出现,返回idx.
- ①检查是否需要初始化或者扩容 : dictExpandIfNeeded(),具体下面分析.
- ②获取index :
- 可能此时处于非rehash状态,那么最终返回的是第一张table的idx;并且需要检查是否存在相同的key值dictEntry,如果不存在,那么直接计算获取第一张table的idx;
- 可能此时处于rehash状态,那么如果第一张table对应的idx桶存在数据,需要检查是否存在相同的key值dictEntry;如果不存在,那么直接计算获取第二张table的idx;
- 以上两种情况如果存在相同的key值dictEntry,则保留旧的value,新的value并没有覆盖旧的value.
# _dictKeyIndex()
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
unsigned long idx, table;
dictEntry *he;
if (existing) *existing = NULL;
1. // 判断是否需要初始化或者扩容,该函数下面具体分析
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
2. // 检查是否有相同的key值dictEntry,如果有则无需再申请dictEntry的内存来保存key,操作同一个dictEntry即可
// 为什么2个哈希表都要遍历 :
① // 可能此时处于非rehash状态 :
// 那么直接 操作第一张table,对应的第3步骤直接bread;
② // 可能此时处于rehash状态 :
// 那么如果此时第一张table对应的idx桶存在数据,需要检查是否存在相同的key值dictEntry
// 如果不存在,那么计算获取第二张table的idx
for (table = 0; table <= 1; table++) {
2.1 // 计算索引值
idx = hash & d->ht[table].sizemask;
2.2 // 开始判断是否存在相同的key值dictEntry
he = d->ht[table].table[idx];
while(he) {
2.2.1 // 判断是否相同key
if (key==he->key || dictCompareKeys(d, key, he->key)) {
// 保存相同key的dictEntry的指针
if (existing) *existing = he;
return -1;
}
2.2.2 // 继续向下一指针查找
he = he->next;
}
3. // 如果当前不处于rehash状态,则第二张table无需查找了,直接操作第一张table
if (!dictIsRehashing(d)) break;
}
4. // 返回idx
return idx;
}
_dictExpandIfNeeded() --- 是否执行需要初始化或者扩容
dictExpandIfNeeded() : 是否执行初始化或扩容
- ①第一次初始化 : dictExpand(d, ,DICT_HT_INITIAL_SIZE),第一次初始化长度为4;
- ②否则不是第一次初始化,那么需要检查是否需要扩容 :
- 如果存储的元素个数大于等于table数组的size,即负载因子大于等于1时,就需要继续判断是否需要扩容了;
- 如果此时并不是处于正在执行持久化命令(BGSAVE、BGREWRITEAOF),即dict_can_resize == 0,那么继续判断下面的条件,否则不允许扩容;
- 如果存储的元素个数 除以 table数组的size 大于 dict_force_resize_ratio(负载因子为5) , 那么执行dictExpand()扩容;
- 当大于 dict_force_resize_ratio触发执行扩容时,并不是扩容为 当前存储的元素个数的2倍,而是会根据这个值继续计算,具体看看下面的_dictNextPower()
static int _dictExpandIfNeeded(dict *d)
{
// 当前处于rehash状态
if (dictIsRehashing(d)) return DICT_OK;
1. // 第一次初始化,需要执行dictExpand()来初始化,DICT_HT_INITIAL_SIZE(该值为4)
if (d->ht[0].size == 0) return dictExpand(d, ,DICT_HT_INITIAL_SIZE);
2. // 如果存储的元素个数大于等于table数组的size,那么就需要判断是否需要扩容
// dict_can_resize : 是否扩容,默认为1,处于正在执行持久化命令(BGSAVE、BGREWRITEAOF),该值为0.
// d->ht[0].used/d->ht[0].size : 如果 存储的元素个数 除以 table数组的size 大于 dict_force_resize_ratio(该值为5) , 那么执行dictExpand()扩容
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
2.1 // 并不是扩容为 当前存储的元素个数的2倍,而是会根据这个值继续计算,具体看看下面的_dictNextPower()
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
dictExpand() --- 执行扩容操作
# dictExpand()
# 参数size : 新的table长度扩容为 最少size
int dictExpand(dict *d, unsigned long size)
{
// 如果当前是处于rehash状态 或者 字典中存储元素个数 大于 扩容长度
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
// 扩容后新的哈希表
dictht n;
// 重新计算扩容长度,_dictNextPower()保证扩容的长度总是2的次幂且大于等于size
unsigned long realsize = _dictNextPower(size);
// 重新扩容到相同的表大小是没有用的
if (realsize == d->ht[0].size) return DICT_ERR;
// 以下都是设置ht[0]、ht[1]属性
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}
_dictNextPower() --- 保证了扩容长度总是2的次幂
dictNextPower() : 该函数保证了扩容长度总是2的次幂,并且是大于等于size.
# _dictNextPower()
static unsigned long _dictNextPower(unsigned long size)
{
unsigned long i = DICT_HT_INITIAL_SIZE;
if (size >= LONG_MAX) return LONG_MAX + 1LU;
while(1) {
// 保证大于等于size
if (i >= size)
return i;
// 保证了总是2的次幂
i *= 2;
}
}
小结
- dictAdd() 的添加操作核心是dictAddRaw(),dictAddRaw()包揽了 渐进式迁移数据、初始化或者扩容、最终是否保存key的操作.
- 渐进式迁移数据 : 如果当前处于rehash状态,并且非迭代状态,那么当前需要先迁移h[0]中10个桶数据到h[1] ;
- 初始化或者扩容 : 如果当前字典并非处于rehash状态,并且 负载因子大于等于1,那么如果满足 负载因子大于5 这个条件,则执行扩容,扩容的长度为最少 字典存储的元素个数 * 2 , 举个例子 : 如果当前字典存储的个数为 17 触发扩容 , 那么 17 * 2 = 34 , 最终扩容的哈希表数组长度则为 64 , 具体可以结合_dictNextPower() ;
- 是否保存key : 保存key的前提是当前字典中并没有相同的key值dictEntry,那么则需要创建新的dictEntry来保存key,否则保留原先的dictEntry,即新插入的value并没有进行替换旧的value.
创建或者查找 --- dictAddOrFind()
还是调用dictAddRaw(),那么跟dictAdd()有什么区别 :
- dictAdd() : 传送的&existing是一个NULL,即出现相同key的时候是不做任何操作的.
- dictAddOrFind() : 传送的&existing是一个dictEntry指针,即如果出现相同的key值dictEntry,会把existing指向该dictEntry,我们根据拿到的这个指针来做相对应的操作.
dictEntry *dictAddOrFind(dict *d, void *key) {
dictEntry *entry, *existing;
entry = dictAddRaw(d,key,&existing);
return entry ? entry : existing;
}
创建 --- dictReplace()
还是调用dictAddRaw(),那么跟dictAdd()有什么区别 :
- dictAdd() : 传送的&existing是一个NULL,即出现相同key的时候是不做任何操作的.
- dictReplace() : 传送的&existing是一个dictEntry指针,即如果出现相同的key值dictEntry,会把existing指向该dictEntry,我们根据拿到的这个指针来覆盖掉旧的value值.
int dictReplace(dict *d, void *key, void *val)
{
dictEntry *entry, *existing, auxentry;
// 返回entry则表示没有相同key值dictEntry,创建成功
entry = dictAddRaw(d,key,&existing);
if (entry) {
// 创建成功,设置value值
dictSetVal(d, entry, val);
// 返回1表示插入
return 1;
}
// 出现相同key值dictEntry,覆盖掉旧的value
auxentry = *existing;
// 覆盖掉旧的value
dictSetVal(d, existing, val);
// 回收旧的value
dictFreeVal(d, &auxentry);
// 返回0表示覆盖
return 0;
}
删除操作 --- dictDelete()、dictUnlink()
# dictDelete() : 回收被删除的dictEntry
int dictDelete(dict *ht, const void *key) {
// 最终调用 dictGenericDelete()
return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
# dictUnlink() : 不回收被删除的dictEntry,并返回该dictEnty
dictEntry *dictUnlink(dict *ht, const void *key) {
return dictGenericDelete(ht,key,1);
}
# dictGenericDelete()
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
uint64_t h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
// 如果处于rehash状态,先迁移10个桶数据
if (dictIsRehashing(d)) _dictRehashStep(d);
1. // 计算hash值
h = dictHashKey(d, key);
2. // 开始查找是否存在删除的key值dictEntry
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
2.1 // 记录上一个dictEntry结点
prevHe = NULL;
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key)) {
2.2 // 出现相同的key值dictEntry
if (prevHe)
2.2.1 // 上一节点.next 与 下一节点接上
prevHe->next = he->next;
else
2.2.2 // 删除的是头结点
d->ht[table].table[idx] = he->next;
2.3 // 是否执行回收内存
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
}
d->ht[table].used--;
return he;
}
2.5 // 继续向下一结点查找
prevHe = he;
he = he->next;
}
// 如果当前非rehash状态,操作第一张table就好
// 否则第二张table也需要查找删除
if (!dictIsRehashing(d)) break;
}
// 没有查找到对应的key值dictEntry
return NULL;
}
回收操作 --- dictFreeUnlinkedEntry
# dictFreeUnlinkedEntry()
void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {
if (he == NULL) return;
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
}
清空字典并回收内存 --- dictRelease()
# dictRelease()
void dictRelease(dict *d)
{
_dictClear(d,&d->ht[0],NULL);
_dictClear(d,&d->ht[1],NULL);
zfree(d);
}
根据key查找操作dictEntry --- dictFind()
# dictFind()
# 根据key查找dictEntry
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
uint64_t h, idx, table;
if (d->ht[0].used + d->ht[1].used == 0) return NULL;
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
// 存在需要查找的dictEntry
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
根据key查找操作value --- dictFetchValue()
# dictFetchValue()
void *dictFetchValue(dict *d, const void *key) {
dictEntry *he;
// 根据key值查找dictEntry
he = dictFind(d,key);
// 返回value值
return he ? dictGetVal(he) : NULL;
}
迭代器相关 --- dictIterator
如果safe设置为1,这是一个安全的迭代器,也就是说,即使在迭代时,也可以对字典调用dictAdd()、dictFind和其他函数.否则它是一个不安全的迭代器,迭代时只能调用dictNext().
typedef struct dictIterator {
// 字典
dict *d;
// 哈希表数组索引值
long index;
// 哪张表,是否为安全迭代器
int table, safe;
// 迭代的数据
dictEntry *entry, *nextEntry;
// 非安全迭代器
long long fingerprint;
} dictIterator;
初始化字典迭代器 --- dictGetIterator()
# dictGetIterator()
dictIterator *dictGetIterator(dict *d)
{
dictIterator *iter = zmalloc(sizeof(*iter));
iter->d = d;
iter->table = 0;
iter->index = -1;
// 不是安全的迭代器
iter->safe = 0;
iter->entry = NULL;
iter->nextEntry = NULL;
return iter;
}
初始化字典为安全迭代器 --- dictGetSafeIterator()
# dictGetSafeIterator()
dictIterator *dictGetSafeIterator(dict *d) {
dictIterator *i = dictGetIterator(d);
// 安全迭代器
i->safe = 1;
return i;
}
迭代 --- dictNext()
# dictNext()
# 安全下可调用
# 不安全下必须调用
dictEntry *dictNext(dictIterator *iter)
{
while (1) {
// 使用iter->entry来存储迭代到的数据
if (iter->entry == NULL) {
// 根据iter->table迭代哪张table
dictht *ht = &iter->d->ht[iter->table];
if (iter->index == -1 && iter->table == 0) {
// 安全迭代器
if (iter->safe)
iter->d->iterators++;
else
// 非安全迭代器
iter->fingerprint = dictFingerprint(iter->d);
}
iter->index++;
// 迭代第二张table
if (iter->index >= (long) ht->size) {
if (dictIsRehashing(iter->d) && iter->table == 0) {
iter->table++;
iter->index = 0;
ht = &iter->d->ht[1];
} else {
break;
}
}
// 把迭代的数据接上iter->entry
iter->entry = ht->table[iter->index];
} else {
// 完成迭代数据
iter->entry = iter->nextEntry;
}
// 最终把迭代的数据iter->entry接上iter->nextEntry
if (iter->entry) {
iter->nextEntry = iter->entry->next;
return iter->entry;
}
}
return NULL;
}
释放迭代 --- dictReleaseIterator()
# dictReleaseIterator()
void dictReleaseIterator(dictIterator *iter)
{
if (!(iter->index == -1 && iter->table == 0)) {
if (iter->safe)
iter->d->iterators--;
else
assert(iter->fingerprint == dictFingerprint(iter->d));
}
zfree(iter);
}
结束语
- 渐进式rehash : 当需要扩容的时候,Redis并不是直接扩容,而是采用渐进式扩容,即每个字典的删除、查找、更新和添加等操作会进行迁移10个桶数据,这样就不会导致数据较大的时候,阻塞更多的请求,将rehash操作对所需的工作均摊到对字典的每个删除、查找、更新和添加操作上.
- 应用场景 : 字典被广泛用于实现Redis的各自功能,其中包括数据库和哈希键.
- Redis中的字典使用哈希表作为底层实现,每个字典带有两个哈希表,一个平时使用,另一个仅在进行rehash的使用.
- Java的HashMap、ConcurrentHashp都是键值对数据结构的实现,都有很大的相似之处,有兴趣的可以结合这些文章一起看看.
- 原创不易
- 希望看完这篇文章的你有所收获!
相关参考资料
- Redis设计与实现【书籍】