共计 1406 个字符,预计需要花费 4 分钟才能阅读完成。
之前相关联文章:
redis 学习之一 SDS
redis 学习之二链表
一 字典相干的数据结构
哈希表定义:
typedef struct dictht{
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值,总是等于 size -1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
}dictht;
哈希表节点定义:
typedef struct dictEntry{
// 键
void *key;
// 值
union{
void *val;
uint64_t u64;
int64_t s64;
}v;
// 指向下个哈希表节点,造成链表
struct dictEntry *next;
}dictEntry;
字典定义:
typedef struct dict{
// 类型函数
dictType *type;
// 公有数据
void *private;
// 哈希表
dictht ht[2];
//rehash 索引,当 rehash 不再进行时值为 -1,// 每次进行 rehash 时,rehashidx 的值就是对应 ht[0]里 dictht 中 dictEntry 数组的索引
int rehashidx;
}dict;
上面是没有进行 rehash 的字典意识图:
redis 应用 MurmurHash2 算法来计算键的哈希值,应用链地址法解决键抵触。
rehash 与渐进式 rehash
二 扩容与缩容过程
当哈希表保留的键值对数量太多或太少的时候,哈希表会进行扩大或膨胀。rehash 的步骤如下:
- 为字典 ht[1]调配空间。
扩容:ht[1]的大小为第一个大于等于 ht[0].used* 2 的 2 的 n 次幂;
缩容:ht[1]的大小为第一个大于等于 ht[0].used 的 2 的 n 次幂。 - 将保留在 ht[0]中的所有键值对 rehash 到 ht[1]下面,在这个过程中会从新计算键的哈希值与索引值。
- 当 ht[0]所有键值都迁徙到了 ht[1]之后,开释 ht[0],将 ht[1]设置为 ht[0],并在 ht[1]新创建一个空白哈希表,为下次 rehash 做筹备。
三 扩容与缩容的机会
- 服务器没有执行 BGSAVE 或 BGREWRITEAOF 命令,且哈希表的负载因子大于等于 1。
- 服务器正在执行 BGSAVE 或 BGREWRITEAOF 命令,且哈希表的负载因子大于等于 5。
- 哈希表的负载因子小于 0.1。
四 渐进式 rehash
思考到 redis 服务性能,rehash 并不是一次性集中进行而是分屡次渐进式进行的,步骤如下:
- 为 ht[1]调配空间,让字典同时持有 ht[0] ht[1]两个哈希表。
- 将下面定义的 dict 构造里的 rehashidx 值设置为 0,示意 rehash 开始进行。
- 每次对字典进行增加、删除、查找或更新时,除了进行这些操作外,还会将 ht[0]在 rehashidx 索引上的所有键值对 rehash 到 ht[1],rehash 的过程上中 rehashidx 值为增 1。
- ht[0]里所有键值对 rehash 到 ht[1]后,将 rehashidx 值置为 -1,rehash 完结。
上面是两 rehash 的过程图:
这个还没进行 rehash,所以这里的 rehashidx 值为 -1,留神 ht[0]里 dictEntry 里的值。
这里 rehashidx 值为 3,这是在对 ht[0]里 dictEntry 里第 3 个键值对(k1,v1)进行 rehash。
此文大部分内容都来自于黄健宏《Redis 设计与实现》一书
正文完