Redis字典设计详解
Redis 是一个高性能的 key-value 内存数据库，与 Memcached 只能存储字符串数据类型不一样，它支持存储的数据结构类型包括：字符串（string）、链表（lists）、哈希表（hash）、集合（set）、有序集合（zset）等。
Redis 的高性能得益于其 I/O事件驱动 模型，当然本文并不是讨论 Redis 的所有知识点，下面主要介绍 Redis 的核心数据结构：字典 的设计和实现。
哈希表介绍
Redis 本质上就是在字典上挂载着各种数据结构，我们先来看看 字典 这种数据结构。Redis中的 字典 其实是就是 哈希表（HashTable），我们来看看 哈希表 的定义：
哈希表（HashTable）是根据键值(Key)而直接进行访问的数据结构。也就是说，它通过把键值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
先来看看 哈希表 数据结构的原理图：
上图比较清晰的描述了 哈希表 的原理，主要的步骤如下：
-
通过Hash函数把key映射到哈希表的某个位置
-
如果有不同的key被映射到同一个位置（冲突），采用拉链法（使用链表存储）来处理。
Redis字典介绍
Redis的字典基本遵从了哈希表的设计，当然在通用性和性能上改进了一些地方，下面我们来解释一下Redis字典的设计。
首先我们来看看在Redis中字典数据结构的定义：
dictEntry {
*key;
{
*val;
u64;
s64;
d;
} v;
dictEntry *next;
} dictEntry;
dictht {
dictEntry **table;
size;
sizemask;
used;
} dictht;
dict {
dictType *type;
*privdata;
dictht ht[];
rehashidx;
iterators;
} dict;
我们通过下图来整理一下这几个结构体的关系：
在Redis中，字典是通过结构体 dict 来表示的，而 dict 结构又会引用 dictht 和 dictEntry 这些结构，下面介绍一下这些结构体的各个字段作用。
dict结构
-
type：是用户自定义的函数列表，主要用于插入数据到字典时进行的一些操作，比如计算key哈希值的hashFunction函数句柄。 -
privdata：创建字典时指定的私有数据，一般提供给type字段中的函数句柄使用。 -
ht[2]：类型为dictht结构的数组，这个数组有两个元素，而dictht结构主要用于保存数据，至于为什么需要两个dictht结构是因为rehash的需要。 -
rehashidx：rehash操作过程中最后一次处理的桶索引。 -
iterators：用于迭代字典中的数据。
dictht结构
-
table：类型为dictEntry结构指针的数组，用于保存数据，每个key-value的数据对通过类型为dictEntry的结构来存储。 -
size：table数组的大小。 -
sizemark：用于取模，得到一个0 ～ size的索引值。 -
used：表示字典中有多少个元素。
dictEntry结构
-
key：数据的键，主要用于查找数据。 -
v：数据的值，数据主要通过这个字段来存储。 -
next：用于解决Hash冲突，把冲突的key连接起来（拉链法）。
字典的创建
接下来分析啊一下在Redis中怎么创建一个字典，创建一个字典是通过 dictCreate() 函数来实现的：
dict *(dictType *type,
*privDataPtr)
{
dict \*d = ((\*d));
(d,type,privDataPtr);
d;
}
(dict \*d, dictType \*type,
*privDataPtr)
{
(&d->[]);
(&d->[]);
d-> = type;
d-> = privDataPtr;
d-> = -;
d-> = ;
DICT_OK;
}
(dictht *ht)
{
ht-> = ;
ht-> = ;
ht-> = ;
ht-> = ;
}
dictCreate() 函数申请了一个类型为 dict 的结构，然后通过调用 _dictInit() 函数对其进行初始化操作，总体过程比较简单。下面来看看在Redis中怎么创建一个字典的：
dictType commandTableDictType = {
dictSdsCaseHash,
,
,
dictSdsKeyCaseCompare,
dictSdsDestructor,
};
() {
...
server. = (&commandTableDictType,);
...
}
创建字典时，需要提供类型为 dictType 的参数，这个参数主要定义了插入数据到字典时进行的一些操作，比如插入数据时key是否要进行复制的keyDup函数，我们来看看 dictType 的定义：
dictType {
(\*hashFunction)( \*key);
*(\*keyDup)( \*privdata, *key);
*(\*valDup)( \*privdata, *obj);
(\*keyCompare)( \*privdata, \*key1, \*key2);
(\*keyDestructor)( \*privdata, *key);
(\*valDestructor)( \*privdata, *obj);
} dictType;
dictType 结构的每个字段都是一个函数指针，下面说明一下各个字段的作用：
-
hashFunction：用于计算键的哈希值 -
keyDup：用于复制数据的键 -
valDup：用于复制数据的值 -
keyCompare：用于比较键是否相等 -
keyDestructor：用于释放复制出来的键的内存 -
valDestructor：用于释放复制出来的值的内存
插入数据到字典
插入数据到字典是通过 dictAdd() 函数实现的，代码如下：
(dict \*d, \*key, *val)
{
dictEntry *entry = (d,key,);
(!entry) DICT_ERR;
(d, entry, val);
DICT_OK;
}
dictAdd() 函数主要还是通过调用 dictAddRaw() 函数来完成插入操作，dictAddRaw() 函数的代码如下：
dictEntry *(dict \*d, \*key, dictEntry **existing)
{
;
dictEntry *entry;
dictht *ht;
((d)) (d);
(( = (d, key, (d,key), existing)) == -)
;
ht = (d) ? &d->[] : &d->[];
entry = ((*entry));
entry-> = ht->[];
ht->[] = entry;
ht->++;
(d, entry, key);
entry;
}
dictAddRaw() 函数主要完成以下几个工作：
-
判断是否正在进行rehash操作（
dictIsRehashing()判断为真），如果是就调用_dictRehashStep()函数进行rehash。 -
通过调用
_dictKeyIndex()函数计算key对应所在哈希表的位置（索引）index。 -
如果正在rehash，那么就使用ht数组的第二个哈希表，否则就用第一个（原因下面会说明）。
-
创建一个
dictEntry结构用于保存数据的键和值。
dictAddRaw() 函数会返回一个类型为 dictEntry 结构的值，然后 dictAdd() 函数通过调用 dictSetVal() 函数设置其值。
Rehash操作
当哈希表中的数据个数超过一定数量时，哈希冲突的链表过长，从而导致查询效率降低，这个时候就需要Rehash操作。Rehash操作是将哈希表的数组扩大，从而减少哈希冲突的比率。当然扩大哈希表的数组会导致之前的映射关系无效，所以需要把旧数据重新迁移到新的哈希表数组中。下面描述了Rehash的过程：
Redis在插入数据到字典时，会通过 _dictExpandIfNeeded() 函数来判断是否需要进行Rehash操作，_dictExpandIfNeeded() 函数代码如下：
(dict *d)
{
((d)) DICT_OK;
(d->[]. == ) (d, DICT_HT_INITIAL_SIZE);
(d->[]. >= d->[]. &&
(dict_can_resize ||
d->[]./d->[]. > dict_force_resize_ratio))
{
(d, d->[].*);
}
DICT_OK;
}
_dictExpandIfNeeded() 函数主要完成3个工作：
-
通过
dictIsRehashing()来判断字典是否正在Rehash操作，如果是就直接返回OK，不需要再进行Rehash。 -
如果字典的第一个哈希表的大小为0，表示需要对第一个哈希表进行初始化。
-
如果第一个哈希表的元素个数大于等于哈希表的大小，那么就对第一个哈希表进行Rehash操作（把哈希表的大小扩大为原来的2倍）。
进行Rehash操作通过调用 dictExpand() 函数来完成，dictExpand() 函数代码如下：
(dict *d, size)
{
((d) || d->[]. > size)
DICT_ERR;
dictht n;
realsize = (size);
(realsize == d->[].) DICT_ERR;
n. = realsize;
n. = realsize-;
n. = (realsize*(dictEntry*));
n. = ;
(d->[]. == ) {
d->[] = n;
DICT_OK;
}
d->[] = n;
d-> = ;
DICT_OK;
}
dictExpand() 函数比较简单，就是申请一个更大的哈希数组，如果第一个哈希表的哈希数组为空，那么就把第一个哈希表的哈希数组设置为新的哈希数组。否则将第二个哈希表的哈希数组设置为新的哈希数组。
这里有个问题，为什么需要两个哈希表呢？这是因为如果哈希表的元素个数比较多的时候Rehash一次的时间会比较长，这样就有可能导致阻塞Redis的服务。所以Redis通过对数据分批Rehash的方式来解决这个问题，也就是说把一次长耗时的操作分为多次短耗时的操作，这样就不会对Redis的服务造成太大的影响。而分批Rehash的关键就在于第二个哈希表。
从 dictExpand() 函数的实现来看，并没有在这里对数据进行Rehash操作，只是把哈希数组扩大2倍而已，那么Rehash操作在什么时候进行呢？对数据进行Rehash操作的触发点有很多个，如插入、删除和查找，当然最后都会调用 dictRehash() 函数来完成，我们来看看 dictRehash() 函数的实现：
(dict *d, n) {
empty_visits = n*;
(!(d)) ;
(n-- && d->[]. != ) {
dictEntry \*de, \*nextde;
(d->[]. > ( )d->);
(d->[].[d->] == ) {
d->++;
(--empty_visits == ) ;
}
de = d->[].[d->];
(de) {
h;
nextde = de->;
h = (d, de->) & d->[].;
de-> = d->[].[h];
d->[].[h] = de;
d->[].--;
d->[].++;
de = nextde;
}
d->[].[d->] = ;
d->++;
}
(d->[]. == ) {
(d->[].);
d->[] = d->[];
(&d->[]);
d-> = -;
;
}
;
}
dictRehash() 函数的第二个参数是指定了每次要对多少个槽进行Rehash（也就是冲突链表），Rehash操作就是遍历第一个哈希表的所有数据，然后重新计算key的哈希值，保存到第二个哈希表中，并且从第一个哈希表中删除。当第一个哈希表的元素个数为0时，就将第一个哈希表替换成第二个哈希表，并且完成Rehash操作。
查找数据
要在字典中查找某个key的值通过 dictFind() 函数完成，dictFind() 函数代码如下：
dictEntry *(dict \*d, \*key)
{
dictEntry *he;
h, idx, table;
(d->[]. + d->[]. == ) ;
((d)) (d);
h = (d, key);
(table = ; table <= ; table++) {
idx = h & d->[table].;
he = d->[table].[idx];
(he) {
(key==he-> || (d, key, he->))
he;
he = he->;
}
(!(d)) ;
}
;
}
通过上面的介绍，dictFind() 函数的实现也比较容易理解，主要进行了如下操作：
-
如果字典为空（第一个和第二个哈希表都为空），那么就返回NULL。
-
如果正在进行Rehash操作，那么就调用
_dictRehashStep()对数据进行分批Rehash。 -
计算key的哈希值，并且先在第一个哈希表中查找是否存在，如果存在就返回key对应的值。
-
如果key不在第一个哈希表中，那么就要判断当前是否正在Rehash操作，如果是就在第二哈希表中查找key是否存在。因为在Rehash的过程中，key有可能被移动到第二个哈希表中。
总结
本文主要介绍了哈希表和Redis字典的设计与实现，Redis字典是对传统哈希表的一种扩展实现，能够减少Rehash操作对服务造成的阻塞。
本文转载自:https://mp.weixin.qq.com/s/0-xxZ1v4WFxMviH9ILb0aw
热门推荐
近期评论
-
来自： 留言板
-
来自： 留言板
-
来自： 留言板
-
来自： 程序设计原则之SOLID原则
-
来自： 程序设计原则之SOLID原则
