dict
dict 源码分析(哈希表 + 渐进式 rehash)
dict 是 Redis 的地基:整个数据库的键空间就是一个 dict,Hash/Set 类型、过期字典也全靠它。本体就是拉链法哈希表,招牌是渐进式 rehash:扩缩容不一次性搬完,把搬迁摊到之后的每次增删改查里,换来单线程主循环永远不被一次 O(n) 大搬家卡死。
注意版本:网上教程大多讲 6.x 的 dict -> dictht[2] -> table 两级结构,7.0 起 dictht 已合并进 dict;本地仓是 unstable (8.4-int),dictEntry 完全 opaque、查找改成 link 体系、强制扩容阈值从 5 改成 4、还加了自动缩容。下面全是新版真码。
// 基于本地 Redis 仓 (unstable, 8.4-int), src/dict.c
static dictResizeEnable dict_can_resize = DICT_RESIZE_ENABLE; // 全局三态开关：bgsave/AOF 重写期间服务器会调成 AVOID
static unsigned int dict_force_resize_ratio = 4; // AVOID 也扛不住的红线：负载因子到 4 必须扩（老版本是 5）
struct dictEntry { // 定义藏在 dict.c 里，对外 opaque：字段布局随时可改而不破坏调用方
struct dictEntry *next; /* Must be first */ // 拉链法：冲突节点串成单链表；next 放第一位是为了和 NoValue 版布局对齐
void *key; /* Must be second */
union { // value 用联合体：整数/double 直接内联在 entry 里，省一次指针跳转和一次堆分配
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
};
typedef struct dictEntryNoValue { // dict 当 Set 用(no_value=1)时的瘦身版：没有 value 就别为它付 8 字节
dictEntry *next; /* Must be first */
void *key; /* Must be second */
} dictEntryNoValue;// 基于本地 Redis 仓 (unstable, 8.4-int), src/dict.h
struct dict {
dictType *type; // 一组函数指针(hashFunction/keyCompare/keyDestructor...)：C 手工多态，键空间/Hash/过期字典各配一套
dictEntry **ht_table[2]; // 核心：两张表。平时只用 [0]；rehash 期间 [1] 是新表，数据从 0 往 1 搬
unsigned long ht_used[2]; // 两张表各自的节点数，dictSize = 两者之和
long rehashidx; /* rehashing not in progress if rehashidx == -1 */ // 搬迁进度：下次搬 ht_table[0] 的哪个桶
unsigned pauserehash; /* If >0 rehashing is paused */ // 安全迭代器在遍历时暂停 rehash，否则搬桶会让遍历漏掉/重复元素
/* Keep small vars at end for optimal (minimal) struct padding */
signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */ // 容量恒为 2 的幂，只存指数：1 字节顶 8 字节
int16_t pauseAutoResize; /* If >0 automatic resizing is disallowed (<0 indicates coding error) */
void *metadata[];
};
#define DICTHT_SIZE(exp) ((exp) == -1 ? 0 : (unsigned long)1<<(exp))
#define DICTHT_SIZE_MASK(exp) ((exp) == -1 ? 0 : (DICTHT_SIZE(exp))-1) // 容量是 2 的幂，取模退化成按位与，这是 exp 方案的真正收益
#define dictIsRehashing(d) ((d)->rehashidx != -1) // 判断"是否在 rehash"就看这一个字段扩容触发与搬迁本体。扩容判断埋在每次插入的路径里;真正搬桶的只有 rehashEntriesInBucketAtIndex 一个函数,主动搬和顺手搬最后都汇到它。
代码块收起展开
// 基于本地 Redis 仓 (unstable, 8.4-int), src/dict.c
int dictExpandIfNeeded(dict *d) {
/* Incremental rehashing already in progress. Return. */
if (dictIsRehashing(d)) return DICT_OK; // 已在 rehash 就不重复触发：任何时刻最多两张表
/* If the hash table is empty expand it to the initial size. */
if (DICTHT_SIZE(d->ht_size_exp[0]) == 0) {
dictExpand(d, DICT_HT_INITIAL_SIZE); // 空表首次分配只给 4 个桶：Redis 里海量小 dict，起步必须抠
return DICT_OK;
}
if ((dict_can_resize == DICT_RESIZE_ENABLE &&
d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0])) || // 常态：负载因子到 1 就扩
(dict_can_resize != DICT_RESIZE_FORBID &&
d->ht_used[0] >= dict_force_resize_ratio * DICTHT_SIZE(d->ht_size_exp[0]))) // AVOID(有子进程)：拖到 4 才被迫扩
{
if (dictTypeResizeAllowed(d, d->ht_used[0] + 1))
dictExpand(d, d->ht_used[0] + 1); // 传 used+1，_dictNextExp 向上取整到 2 的幂，效果即翻倍
return DICT_OK;
}
return DICT_ERR;
}
/* Performs N steps of incremental rehashing. Returns 1 if there are still
* keys to move from the old to the new hash table, otherwise 0 is returned. */
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */ // 关键护栏：没有它，"搬 n 个桶"可能扫几百万个空桶，耗时无上界
unsigned long s0 = DICTHT_SIZE(d->ht_size_exp[0]);
unsigned long s1 = DICTHT_SIZE(d->ht_size_exp[1]);
if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0;
if (dict_can_resize == DICT_RESIZE_AVOID &&
((s1 > s0 && s1 < dict_force_resize_ratio * s0) || // AVOID 连已经开始的 rehash 都冻结，等子进程退出再继续
(s1 < s0 && s0 < HASHTABLE_MIN_FILL * dict_force_resize_ratio * s1)))
{
return 0;
}
while(n-- && d->ht_used[0] != 0) {
assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);
while(d->ht_table[0][d->rehashidx] == NULL) { // 跳过空桶
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
/* Move all the keys in this bucket from the old to the new hash HT */
rehashEntriesInBucketAtIndex(d, d->rehashidx);
d->rehashidx++;
}
return !dictCheckRehashingCompleted(d); // 返回 1 = 还没搬完，调用方可以接着喂预算
}
static void rehashEntriesInBucketAtIndex(dict *d, uint64_t idx) {
dictEntry *de = d->ht_table[0][idx];
uint64_t h;
dictEntry *nextde;
while (de) {
nextde = dictGetNext(de);
void *storedKey = dictGetKey(de);
/* Get the index in the new hash table */
if (d->ht_size_exp[1] > d->ht_size_exp[0]) { // 扩容：重算哈希定位新桶
const void *key = dictStoredKey2Key(d, storedKey);
h = dictGetHash(d, key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
} else {
h = idx & DICTHT_SIZE_MASK(d->ht_size_exp[1]); // 缩容：都是 2 的幂，小表掩码直接截断旧下标，连哈希都不用算
}
if (d->type->no_value) {
// ... Set 模式的指针标记(pointer tagging)优化，单 key 桶不分配 entry
} else {
dictSetNext(de, d->ht_table[1][h]); // 头插进新表对应桶：节点原地复用，搬迁零拷贝零分配
}
d->ht_table[1][h] = de;
d->ht_used[0]--;
d->ht_used[1]++;
de = nextde;
}
d->ht_table[0][idx] = NULL;
}
static int dictCheckRehashingCompleted(dict *d) {
if (d->ht_used[0] != 0) return 0;
// ... rehashingCompleted/bucketChanged 回调
zfree(d->ht_table[0]); // 旧表搬空：释放旧表，新表转正
/* Copy the new ht onto the old one */
d->ht_table[0] = d->ht_table[1];
d->ht_used[0] = d->ht_used[1];
d->ht_size_exp[0] = d->ht_size_exp[1];
_dictReset(d, 1);
d->rehashidx = -1;
return 1;
}
static void _dictRehashStep(dict *d) {
if (d->pauserehash == 0) dictRehash(d,1);
}
static void _dictRehashStepIfNeeded(dict *d, uint64_t visitedIdx) { // 增删查改每次顺手搬一个桶，搬迁成本摊进日常操作
if ((!dictIsRehashing(d)) || (d->pauserehash != 0))
return;
/* rehashing not in progress if rehashidx == -1 */
if ((long)visitedIdx >= d->rehashidx && d->ht_table[0][visitedIdx]) {
_dictBucketRehash(d, visitedIdx); // 优先搬"本次操作正要访问的那个桶"：数据马上要进 CPU 缓存，搬它近乎白嫖
} else {
dictRehash(d,1); // 访问的桶不在旧表里，退回按 rehashidx 顺序搬
}
}查找与插入。新版统一走 link 体系:dictEntryLink 是”指向 entry 指针的指针”,一次遍历同时拿到 entry 和它的前驱位置,查/删/改共用。
代码块收起展开
// 基于本地 Redis 仓 (unstable, 8.4-int), src/dict.c
dictEntry *dictFind(dict *d, const void *key)
{
dictEntryLink link = dictFindLink(d, key, NULL); // 空 dict 短路后转发给 dictFindLinkInternal
return (link) ? *link : NULL;
}
static dictEntryLink dictFindLinkInternal(dict *d, const void *key, dictEntryLink *bucket) {
dictCmpCache cmpCache = {0};
dictEntryLink link;
uint64_t idx;
int table;
// ...
const uint64_t hash = dictGetHash(d, key);
idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[0]);
keyCmpFunc cmpFunc = dictGetCmpFunc(d);
/* Rehash the hash table if needed */
_dictRehashStepIfNeeded(d,idx); // 纯读操作也推进 rehash：读写共同分摊搬迁
int tables = (dictIsRehashing(d)) ? 2 : 1; // rehash 期间 key 可能在任意一张表，两张都要查
for (table = 0; table < tables; table++) {
if (table == 0 && (long)idx < d->rehashidx) continue; // rehashidx 之前的旧桶必然已搬空，整张直接跳过
idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
link = &(d->ht_table[table][idx]);
if (bucket) *bucket = link;
while(link && *link) {
const void *visitedKey = dictStoredKey2Key(d, dictGetKey(*link));
if (key == visitedKey || cmpFunc( &cmpCache, key, visitedKey)) // 先比指针再比内容，同一对象免去 sds 逐字节比较
return link;
link = dictGetNextLink(*link);
}
}
return NULL;
}
/* Finds and returns the link within the dict where the provided key should
* be inserted using dictInsertKeyAtLink() if the key does not already exist in
* the dict. If the key exists in the dict, NULL is returned and the optional
* 'existing' entry pointer is populated, if provided. */
dictEntryLink dictFindLinkForInsert(dict *d, const void *key, dictEntry **existing) {
unsigned long idx, table;
dictCmpCache cmpCache = {0};
dictEntry *he;
uint64_t hash = dictGetHash(d, key);
if (existing) *existing = NULL;
idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[0]);
/* Rehash the hash table if needed */
_dictRehashStepIfNeeded(d,idx);
/* Expand the hash table if needed */
_dictExpandIfNeeded(d); // 扩容检查埋在插入路径上：每次写入前看一眼负载因子
keyCmpFunc cmpFunc = dictGetCmpFunc(d);
for (table = 0; table <= 1; table++) {
if (table == 0 && (long)idx < d->rehashidx) continue;
idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
/* Search if this slot does not already contain the given key */
he = d->ht_table[table][idx];
while(he) {
const void *he_key = dictStoredKey2Key(d, dictGetKey(he));
if (key == he_key || cmpFunc(&cmpCache, key, he_key)) {
if (existing) *existing = he;
return NULL; // key 已存在：没有插入位置可言，带出旧 entry 让上层决定改还是报错
}
he = dictGetNext(he);
}
if (!dictIsRehashing(d)) break;
}
/* If we are in the process of rehashing the hash table, the bucket is
* always returned in the context of the second (new) hash table. */
dictEntry **bucket = &d->ht_table[dictIsRehashing(d) ? 1 : 0][idx]; // 铁律：rehash 期间新 key 只进新表
return bucket;
}
dictEntry *dictInsertKeyAtLink(dict *d, void *key __stored_key, dictEntryLink link) {
dictEntryLink bucket = link; /* It's a bucket, but the API hides that. */
dictEntry *entry;
int htidx = dictIsRehashing(d) ? 1 : 0;
// ...
if (d->type->no_value) {
// ... Set 模式：桶里只有一个 key 时给 key 指针打低位标记直接塞进桶，dictEntry 都省了
} else {
entry = zmalloc(sizeof(*entry));
assert(entryIsNormal(entry)); /* Check alignment of allocation */
entry->key = key;
entry->next = *bucket; // 头插 O(1)：刚写入的 key 更可能马上被访问，放链头符合时间局部性
}
*bucket = entry;
d->ht_used[htidx]++;
return entry;
}原理串讲
拿一条 SET k v 在键空间 dict 里落地走一遍。上层 dbAdd 最终调 dictAdd(d, key, val),它转手给 dictAddRaw,核心在 dictFindLinkForInsert:先用 siphash 算出 64 位哈希,hash & DICTHT_SIZE_MASK 按位与出桶下标,然后连做两件”顺手”的事——_dictRehashStepIfNeeded(d, idx) 搬一个桶、_dictExpandIfNeeded(d) 检查要不要扩容。
假设此刻 used == size、负载因子到 1,dictExpand 一路走到 _dictResize:分配一张 2 倍大的新表挂到 ht_table[1],把 rehashidx 从 -1 置 0——注意这一步只分配、一个节点都不搬,“扩容”瞬间完成,欠下的搬迁账后面慢慢还。
回到 dictFindLinkForInsert,两张表扫一遍确认 key 不存在,返回插入位置;因为正在 rehash,这个位置强制取自 ht_table[1]。
最后 dictInsertKeyAtLink 分配 entry 头插进桶,ht_used[1]++。
为什么新 key 必须进新表?这是渐进式 rehash 能收敛的根基:旧表从此只减不增,每搬一个桶 ht_used[0] 就单调递减,搬迁一定会结束。
反过来若允许写旧表,写入速度快过搬迁速度时 rehash 永远做不完,两表并存的过渡态就成了常态。
代价也在这:过渡期查找、删除都要两张表各查一次(dictFindLinkInternal 里 tables = 2 的循环),好在 (long)idx < d->rehashidx 这个判断能把旧表已搬空的前缀整段跳过。
欠下的搬迁账由两个渠道偿还。被动渠道:所有增删查改入口都会路过 _dictRehashStepIfNeeded,每次搬一个桶,量大但零专门开销,而且它优先搬”本次正要访问的那个桶”(_dictBucketRehash(d, visitedIdx))——反正这个桶的数据马上要被拉进 CPU 缓存,搬迁近乎免费,这是 8.x 相对老版本纯按 rehashidx 顺序搬的一个新优化。
主动渠道:serverCron 里 kvstoreIncrementallyRehash 按微秒预算调 dictRehashMicroseconds,每次 dictRehash(d, 100) 搬 100 桶、超预算即停,专治冷 dict——没人访问就没有被动搬迁,没有这条腿,一个不再被读写的大 dict 会永远卡在两表状态多吃一倍桶内存。
dictRehash 里 empty_visits = n*10 同理:大表刚开始搬时空桶连片,不设上限的话”搬 1 个桶”可能变成扫几万个空槽,延迟又不可控了。
等 ht_used[0] 归零,dictCheckRehashingCompleted 释放旧表、新表转正、rehashidx = -1,世界恢复单表。
为什么负载因子到 1 就扩,偏偏 bgsave/AOF 重写时又拖到 4?因为 fork 出的子进程和父进程共享物理内存页(写时复制),rehash 是对全表指针的密集改写,会把共享页大面积写脏,等于变相把内存翻倍。
所以有子进程时 dict_can_resize 被调成 AVOID:新的扩容不触发、已开始的 rehash 也在 dictRehash 开头被冻结,只有链表长到平均 4 的红线才不得不扩。
这是”内存峰值”和”查询退化”之间的一次明码标价。
设计取舍
- 渐进式 rehash 用”总工作量变多”换”单次停顿有上界”:搬迁期间两表并存、每次查找多一次探测,但主线程永远没有 O(n) 尖刺。与 Java 对比,HashMap 是一次性 resize,ConcurrentHashMap 的 transfer 靠多线程帮搬,dict 靠时间摊薄,三种思路对应三种约束。
- 头插法在这里是安全的:Redis 主线程单线程访问 dict,没有 JDK 7 HashMap 多线程头插成环的问题,所以可以放心拿头插换 O(1) 和局部性。
- 容量恒为 2 的幂:取模变按位与、缩容时新下标 = 旧下标截断掩码、
ht_size_exp一个字节存容量。代价是哈希质量全押在 siphash 的均匀性上,没有素数表长兜底。 - 8.x 的 dict 自带自动缩容(
dictShrinkIfNeeded,填充率低于 1/8 触发),大量删除后桶数组能还回内存;缩容同样走渐进式、同样受子进程 AVOID 约束。 dictEntry对外 opaque +no_value/pointer tagging:Set 场景单 key 桶连 entry 都不分配,把 key 指针打标记直接塞桶里。聊内存优化,这个比”intset/listpack 编码”更底层。