August's Box

Redis设计与实现笔记-章4.字典

字典在Redis里应用十分广泛,比如最重要的作为kv的数据库就是用字典来实现的。字典也是hash键的底层实现之一(当hash键包含的键值对较多,或者键值对中元素都是比较长时),另外很多其他的功能也用到了字典。

字典的实现

Redis的字典使用哈希表作为底层实现,每个哈希表可以有多个哈希表节点,每个节点保存了字典中的一个键值对。整个关联结构见图:

定义

字典,字典值类型,迭代器的定义
dict.h/dictlink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
typedef struct dictType {
// 计算哈希值的函数
unsigned int (*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;
typedef struct dictIterator {
dict *d;// 被迭代的字典
// table :正在被迭代的哈希表号码,值可以是 0 或 1 。
// index :迭代器当前所指向的哈希表索引位置。
// safe :标识这个迭代器是否安全
int table, index, safe;
// entry :当前迭代到的节点的指针
// nextEntry :当前迭代节点的下一个节点
// 因为在安全迭代器运作时, entry 所指向的节点可能会被修改,
// 所以需要一个额外的指针来保存下一节点的位置,
// 从而防止指针丢失
dictEntry *entry, *nextEntry;
long long fingerprint; /* unsafe iterator fingerprint for misuse detection */
} dictIterator;
typedef struct dict {
dictType *type;// 类型特定函数
void *privdata;// 私有数据,保存需要传递给特定类型特定函数的可选参数
dictht ht[2];// 两个哈希表,实现渐进式rehash
int rehashidx;// 不在rehashing时为-1,否则为rehashing进度
int iterators;// 目前正在运行的安全迭代器的数量
} dict;
哈希表的定义
dict.h/dicthtlink
1
2
3
4
5
6
7
8
9
10
11
typedef struct dictht {
// 哈希表数组,保存哈希表节点
dictEntry **table;
// 哈希表大小,即table大小
unsigned long size;
// 哈希表大小掩码,和哈希值决定键放置到table哪个index
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
哈希表节点的定义
dict.h/dicthtlink
1
2
3
4
5
6
7
8
9
typedef struct dictEntry {
void *key;//键
union {
void *val;
uint64_t u64;
int64_t s64;
} v;//值
struct dictEntry *next;//指向下个哈希表节点,形成链表,解决冲突
} dictEntry;

创建

用给定的字典类型和数据创建字典,并初始化字典各项属性。

dict.c/dictCreatelink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//创建
dict *dictCreate(dictType *type, void *privDataPtr)
{
dict *d = zmalloc(sizeof(*d));
_dictInit(d,type,privDataPtr);
return d;
}
//初始化
int _dictInit(dict *d, dictType *type, void *privDataPtr)
{
// 初始化两个哈希表的各项属性值
// 但暂时还不分配内存给哈希表数组
_dictReset(&d->ht[0]);
_dictReset(&d->ht[1]);
// 设置类型特定函数
d->type = type;
// 设置私有数据
d->privdata = privDataPtr;
// 设置哈希表 rehash 状态
d->rehashidx = -1;
// 设置字典的安全迭代器数量
d->iterators = 0;
return DICT_OK;
}
//重置或初始化哈希表的各项属性
static void _dictReset(dictht *ht)
{
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}

哈希算法

新加一个键值对到字典的时候,需要根据key来计算出哈希值,然后通过哈希值计算出索引值,再讲键值对的哈希表节点放到哈希表数组的指定索引上。
hash = dict->type->hashFunction(key);
index = hash & dict->ht[x].sizemask;//x为0 or 1
Redis使用的hash算法是Murmurhash的Murmurhash2版本,对于输入的键有规律的仍可以给出很好的随机分布,计算速度也很快。Redis实现见函数dictGenHashFunction
解决键冲突的方法根据dictEntry的定义可以看出,Redis使用了链地址法来解决,即相同index的key节点用单向链表链接起来。基于新增加的键值对被访问的概率越高,redis将新添加的节点插入到链表head位置。

使用

_dictReset函数可以知道,字典被创建的时候并未分配内存,只有当首次向字典里加入元素的时候,内存才真正被分配(dictAdd)。

dict.c/dictAddlink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key);//尝试添加键
if (!entry) return DICT_ERR;//键已经存在,返回失败
dictSetVal(d, entry, val);//不存在,设置val
return DICT_OK;
}
dictEntry *dictAddRaw(dict *d, void *key)
{
//pre code ......
// 计算键在哈希表中的索引值
// 如果值为 -1 ,那么表示键已经存在
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
//after code, 分配空间给key,插入节点到哈希表数组,返回entry ......
}
static int _dictKeyIndex(dict *d, const void *key)
{
//pre code ......
if (_dictExpandIfNeeded(d) == DICT_ERR)//是否需要扩展
return -1;
//after code,计算key的哈希值->索引值,遍历索引所在的链表看是否存在,
//存在返回-1,否则返回索引值 ......
}
static int _dictExpandIfNeeded(dict *d)
{
//pre code ...
//第一次添加元素时
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
// 一下两个条件之一为真时,对字典进行扩展
// 1)字典已使用节点数和字典大小之间的比率接近 1:1
// 并且 dict_can_resize 为真
// 2)已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
// 新哈希表的大小至少是目前已使用节点数的两倍,
// 在dictExpand里实际扩展的大小是第一个大于传入参数的pow(2, X)
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}

所有pre code基本上是变量申明,rehashing状态check和操作等,dictExpand主要是给哈希表数组扩展容量,包括rehashing状态的检查。

rehash

rehash操作主要是为了保证哈希表的负载均衡,当哈希表保存的键值对数量在过多和过少时进行相应的扩容和减容。rehash的操作work on哈希表ht[1],rehash操作的状态由字典的属性rehashidx表示。

  1. 为ht[1]分配空间,分配的空间大小由扩容或减容的操作和ht[0].used属性来决定:
    • 扩容的话,大小为第一个大于ht[0].used*2的pow(2, X)
    • 减容的话,大小为第一个大于ht[1].used的pow(2, X)
  2. 将ht[0]上面的所有键值对rehash到ht[1]上面
  3. 等rehash操作完毕后,释放ht[0],将字典的ht[0]指向ht[1],ht[1]新建一个空白的哈希表。

rehash自动触发的几个条件(负载因子为节点数量/哈希表大小):

  1. 服务器没有执行BGSAVEBGREWRITEAOF命令时,哈希表的负载因子大于等于1,执行扩展操作
  2. 服务器执行BGSAVEBGREWRITEAOF命令时,哈希表的负载因子大于等于5,执行扩展操作
  3. 哈希表的负载因子小于0.1时,执行减容操作

渐进式rehash

哈希表的rehash操作不是一次性、集中式的操作,除了服务器长时间没有命令执行,主动调用rehash(dictRehashMilliseconds)以外,还有另一种方式:渐进式rehash,操作的详细步骤如下:

  1. 为ht[1]分配空间
  2. rehashidx设置为0,表示rehash正式开始
  3. rehash期间,所有增删改查的操作请求除了正常服务外,执行单步rehash(_dictRehashStep),单步rehash操作会rehash一条index的链表,同时rehashidx+1,下次rehash的时候就从rehashidx开始
  4. 当ht[0]所有键值对被rehash到ht[1]的时候,rehashidx重置为-1,完成

渐进式rehash采用分治的思想把rehash的操作平摊到服务器请求上,避免集中式操作带来的庞大计算量。另外,在渐进式rehash执行国过程中,增删改查的操作会work在两张表上,新增的话会进到ht[1]等,保证ht[0]只减不增。

主要API

字典的主要API包括了基本的字典操作:
dictCreatedictAdddictReplacedictFetchValuedictGetRandomKeydictDeletedictRelease