Redis 字典

本文将介绍Redis字典的具体实现。

基本结构

Redis字典Python的字典Java中的Map)的性质是一样的,也被称为关联数组或映射,是一种保存键值对的数据结构。

Redis字典使用哈希表作为底层实现,字典中的键不允许相同。

1
2
3
4
5
6
typedef struct dictht {
dictEntry **table; // 哈希表
unsigned long size; // 哈希表大小
unsigned long sizemask; // 哈希表大小掩码
unsigned long used; // 已使用大小
} dictht;

哈希表中每一个键值对用dictEntry来表示,

1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry {
void *key; // 键
union { // 值
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // 链表指针
} dictEntry;

其中,next指针是用来解决哈希表的键冲突的,所有key的哈希值相同的节点都会添加在链表上。v`值支持4种格式:指针、unit64_t、int64_t、double类型。

哈希算法

添加新的键值对时,需要先计算键的哈希值和索引值,然后按照索引值把键值对插入到对应的位置。

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
50
51
// 查找key在索引中的位置
static int _dictKeyIndex(dict *d, const void *key, unsigned int hash, dictEntry **existing)
{
unsigned int idx, table;
dictEntry *he;
if (existing) *existing = NULL;

/* Expand the hash table if needed */
if (_dictExpandIfNeeded(d) == DICT_ERR) // 哈希表扩展
return -1;
for (table = 0; table <= 1; table++) { // 遍历两个哈希table
idx = hash & d->ht[table].sizemask; // 获取table上索引位置
/* Search if this slot does not already contain the given key */
he = d->ht[table].table[idx];
while(he) { // 遍历桶内数据(冲突链)
if (key==he->key || dictCompareKeys(d, key, he->key)) {
if (existing) *existing = he;
return -1;
}
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return idx;
}

// 添加键值对
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
int index;
dictEntry *entry;
dictht *ht;

if (dictIsRehashing(d)) _dictRehashStep(d); // 如果在rehash,则采用渐进方式

/* Get the index of the new element, or -1 if
* the element already exists. */
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) // -1代表已存在
return NULL;

...
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index]; // 链表头插法
ht->table[index] = entry;
ht->used++;

/* Set the hash entry fields. */
dictSetKey(d, entry, key);
return entry;
}

功能实现

rehash

当桶后面的链表不断增长时,访问目标键值变慢,就需要rehash来加快访问速度(减少链表长度)。

此外,随着键值对的添加和删除,需要动态调整哈希表的大小。

在redis中,字典的存储结构如下,

1
2
3
4
5
6
7
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2]; // 默认使用ht[0],ht[1]用于rehash
long rehashidx; /* 是否执行rehash的标识rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;

其中,ht[2]用来存储字典内容,只有在进行rehash操作时,ht[1]才会被用到(默认hash数据都存储在ht[0]上)。

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
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;

while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;

...
assert(d->ht[0].size > (unsigned long)d->rehashidx);
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++; // 如果当前table桶中数据为空,则增加索引值
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx]; // 获取当前哈希桶中的第一个键值对
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) { // 遍历哈希桶中的所有数据
unsigned int h;

nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask; // rehash原有数据到新的哈希表的桶中
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}

/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) { //如果原有hash表中所有数据已转移完成,则释放旧哈希表
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}

/* More to rehash... */
return 1;
}

在进行rehash的过程中,字典会同时在ht的两个table上进行查找、删除、更新操作,而新增只会在ht[1]上操作。

哈希表扩展

redis提供了dictExpand函数来扩展哈希表的大小。

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
// 哈希表扩展
int dictExpand(dict *d, unsigned long size)
{
dictht n; /* the new hash table */
unsigned long realsize = _dictNextPower(size); // 计算哈希表的大小

...

/* Allocate the new hash table and initialize all pointers to NULL */
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;

/* Is this the first initialization? If so it's not really a rehashing
* we just set the first hash table so that it can accept keys. */
if (d->ht[0].table == NULL) { // 如果哈希表ht[0]没有被初始化,则使用ht[0]
d->ht[0] = n;
return DICT_OK;
}

/* Prepare a second hash table for incremental rehashing */
// 否则,使用ht[1]用于rehash方式扩展
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}

static unsigned long _dictNextPower(unsigned long size)
{
unsigned long i = DICT_HT_INITIAL_SIZE;

if (size >= LONG_MAX) return LONG_MAX;
while(1) {
if (i >= size)
return i;
i *= 2; // 2的指数被增大
}
}