字典
Redis 中的字典 由 dict.h/dict 结构表示:
typedef struct dict {
dictType *type; //类型特定函数
void *privdata; //私有数据
dictht ht[2]; //哈希表
int rehashdx; //rehash 索引,当 rehash 不在进行时,值为-1
} dict;
type 和 privdata 是针对不同类型的键值对,为创建多态字典而设置的
type指向一个 dictType 结构的指针, 每个dictType 结构保存了一簇用于操作特作特定类型键值对的函数, Redis 会为用途不同的字典设置不同的类型特定函数.
而pridata 则保存了需要传给那些特定类型函数看可选参数.
ht 属性,包含两个数组,数组的每一项都是一个 dictht 哈希表,一般情况下字典只使用ht[0] 哈希表,ht[1]哈希表只会在对哈希表进行 rehash 时使用.
rehashidex 记录了 rehash 当前的进度,如果没有进行 rehash, 值就为-1.
哈希表
Redis 字典所使用的哈希表由 dict.h/dictht 结构定义:
typedef struct dictht {
dictEntry **table; //哈希表数组
unsigned long size; //哈希表大小
unsigned long sizemask; //用于计算索引值,
//总是等于 size - 1
unsigned long used; //哈希表已有节点数量
} dictht;
table 属性是一个数组, 数组中每个元素都是一个指向 dictEntry 结构的指针, 每个 dictEntry 结构保存着一个键值对.
size 属性记录了哈希表的大小,也就是 table 数组的大小
sizemask 属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面
哈希表节点
哈希表节点使用 dictEntry 表示,每个 dictEntry 结构保存着一个键值对
typedef struct dictEntry {
void *key; //键
union { //值
void *val;
uint_64 u64;
int64_t s64;
} v;
sturct dictEntry *next; //指向下个哈希表节点,形成链表
} dictEntry;
注意这里 v 属性保存着键值对中的值,其中的键值可以是指针,或是 uint_64 整数,又或者是 int64_t 整数.
next 属性是指向另一个哈希表节点的指针,这个指针将多个哈希值相同的键值对连接在一起,以此来解决键值冲突(collision)问题.
下图展示了一个普通状态下的字典(没有 rehash 进行)
哈希算法
Redis 使用 MurmurHash2 算法 来计算键的哈希值.
Redis 计算哈希值和索引的方法如下:
hash = dict->type->hashFunction(k);
index = hash & dict->ht[0].sizemask
解决键冲突
当有两个或两个以上的键被分配到了哈希表数组的同一索引上时,称这些键发生了冲突( collision)
Redis 的哈希表使用链地址法来解决冲突,每个哈希表节点都有一个 next 指针,多个哈希表节点可以用 next 指针构成一个单项链表,被分配到同一个索引上的多个节点可以用这个对单向链表连接起来,这就解决了键冲突的问题.
如前面的字典示意图所示, 键 k0 和 k1 的索引值均为1,这里只需用 next 指针将两个节点连接起来.
,因为dictEntry 节点组成的链表没有表尾指针,为了 速度考虑,程序总是将新节点调价到链表的表头位置,排在其他已有节点的前面,这样插入的复杂度为$ O(1)$.
Rehash
随着操作的不断进行, 哈希表保存的键值对会逐渐地增多或减少,为了让哈希表的负载因子维持在一个合理的范围之内,当哈希表保存的键值对数量太多或者太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩.这个过程叫做rehash.
Redis 对字典的哈希表执行 rehash 的步骤如下:
- 为字典的 ht[1] 哈希表分配空间,空间的大小取决于要执行的操作,以及 ht0]当前包含的键值对数量( used 属性值):
- 如果执行的是扩展操作,那么 ht[1] 的大小为第一个大于等于 ht0].used*2的 $2^n$ .
- 如果执行的是收缩操作,那么ht[1]的大小为打一个大于等于 ht[0].used 的$2^n$.
- 将保存在 ht[0] 中所有键值对 rehash 到 ht[1] 上面: 任何事指的是重新计算键的哈希值和索引值,然后键键值对放到 ht[1] 哈希表的指定位置.
- 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后, 释放 ht[0], 再将 ht[1] 设置为 ht[0],并在 ht[1] 后面创建一个空白的哈希表.
举个例子,假设程序要对下图的 `ht[0] 进行扩展操作
ht[0].used 当前值为4 , $2^3$ 恰好是第一个大于等于 4*2 的值,所以 ht[1] 哈希表的大小设置为8,下图展示了 ht[1] 分配了空间之后字典的样子.
将 ht[0] 包含的四个键值对 rehash 到 ht[1], 图下图所示:
释放 ht[0], 将 ht[1] 设置为 ht[0]. 再分配一个空哈希表. 哈希表的大小由原来的4 扩展至8.
渐进式 rehash
上一节说过, 扩展或收缩哈希表需要将 ht[0] 里的所有键值对 rehash 到 ht[1] 中,但是这个 rehash
动作并不是一次性,集中式完成的,而是分多次,渐进式完成的.
这么做的原因是,当哈希表里保存的键值对多至百万甚至亿级别时,一次性地全部 rehash 的话,庞大的计算量会对服务器性能造成严重影响.
以下是渐进式 rehash 的步骤:
- 为 ht[1] 分配空间
- 在字典中维持一个索引计数器变量 rehashidx, 将它的值设置为0,表示 rehash 正式开始
- 在 rehash 进行期间,每次对字典进行增删改查时,顺带将 ht[0] 在 rehashidx 索引上的所有键值对 rehash 到 ht[1] 中,同时将 rehashidx 加 1.
- 随着操作不断进行,最终在某个时间点上, ht[0] 所有的键值对全部 rehash 到 ht[1] 上,这是讲 rehashidx 属性置为 -1,,表示 rehash操作完成.
- 在渐进式 rehash 执行期间,新添加到字典的键值对一律保存到 ht[1] 里,不会对 ht[0] 做添加操作,这一措施保证了 ht[0]只减不增,并随着 rehash 进行, 最终编程空表.
