Redis里dict源码剖析

Redis全名叫做Remote Dictionary Server,从全称就可以看出dict是Redis里重要的数据结构,看了下dict.c里的源码,简单分析下。

dict.c主要是实现了哈希功能,实际上实现哈希(字典)常见的方法有几种:

<1>比如我们数据结构课上学的数组和链表法,但是这种方法适用于元素个数不多的情况下

<2>使用复杂的平衡树(B-等等),性能比较不错,比如MySQL里的索引就使用了这种方法

<3>哈希表,兼顾了高效和简单性,Redis选择了这种方法。

我们就解读下dict.c里源码里的数据结构吧,我们知道hash表的性能由hash表的大小和解决冲突的方法决定。Redis里使用了两个哈希表(ht[0])和哈希表(ht[1]),hash[0]是字典主要使用的hash表,而hash[1]主要对0号哈希表进行rehash时才使用。读者可能不明白这个地方啥意思?其实就是,程序每次申请几个字节(默认为4字节),当key/value数量达到规定时,程序申请的4字节就翻一倍(这里使用了慢迁移),那什么时候rehash呢?我们知道size == used(根据下面的dictht结构体)时,达到最理想状态,所以当used/size > 1时,就进行rehash。我们先看看dict.h里定义的几个结构体吧:

dict:

1
2
3
4
5
6
7
typedef struct dict {
dictType *type; //哈希表节点指针数组(俗称桶,bucket)hash表的类型,可以是string,list等
void *privdata; //该hash表的一些private数据
dictht ht[2];
int rehashidx; /* rehashidx记录的实际上是rehash进行到的索引,比如如果rehash进行到第10个元素,那么rehashidx的值就为9。如果没有在进行rehash,rehashidex的值就为-1.*/
int iterators; /* number of iterators currently running */
} dict;

dictType:

1
2
3
4
5
6
7
8
9
//每种hash table的类型,里面既有成员函数,又有成员变量,模拟的C++类,每个函数带有的privdata均为预留参数
typedef struct dictType {
unsigned int (*hashFunction)(const void *key); //要采用的hash函数
void *(*keyDup)(void *privdata, const void *key); //对key进行拷贝
void *(*valDup)(void *privdata, const void *obj); //对value进行拷贝
int (*keyCompare)(void *privdata, const void *key1, const void *key2); //key比较器
void (*keyDestructor)(void *privdata, void *key); //销毁key,一般为释放空间
void (*valDestructor)(void *privdata, void *obj); //销毁value,一般为释放空间
} dictType;

dictht:

1
2
3
4
5
6
7
8
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
dictEntry **table; //hash表中的数据,以key/value形式,通过单链表保存
unsigned long size; //桶个数
unsigned long sizemask; //size - 1,方便定位
unsigned long used; //实际保存的元素数
} dictht;

dictEntry:

1
2
3
4
5
6
7
8
9
10
//hash表中每一项key/value,若key的映射值,以单链表的形式保存
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
struct dictEntry *next;
} dictEntry;

dict.h一共有这四种结构,每个结构体里的每个变量的用途,我都已经注释出来。

根据程序分析出整个字典结构如图所示(此时的状态为dictadd,且未出现rehash和rehash也未在进行中):

我们之后再说下程序的执行流程吧:

首先是dict初始化,init_hash_dict –> dictCreate –> _dictInit –> _dictRest

上面流程代码都很简单,就是把dict结构体和dictht里面的数据都初始化。

然后是添加键值到字典,这个地方比较难懂,也是重点,因为它包括的操作比较多,分为三种情况:

<1>如果字典为未初始化(也即字典的0号哈希表的table属性为空),那么程序需要对0号哈希表进行初始化。

<2>如果在插入时发生了键碰撞,处理碰撞,链表法

<3>如果插入新元素使得字典满足了rehash条件,那么启动相应的rehash程序(used / size > 1)。

这里有个需要注意的地方,如果rehash正在进行中(ht[0]数据–>ht[1]),那么选择ht[1]作为新键值对的添加目标,否则ht[0]作为新键值对的添加目标。

本来想长篇大论呢,但是学校网速真的是太卡了,不写了,看看其他的吧。

参考资料:

《Redis设计与实现》