方圆

redis-dict

2019-08-03

Redis是一个开放源代码(BSD许可)的内存中数据结构存储,用作数据库,缓存和消息代理。 它支持字符串,哈希,列表,集合,带范围查询的排序集合,位图,超日志,带有半径查询和流的地理空间索引
strings, hashes, lists, sets, 带范围查询的有序sets, bitmaps, hyperloglogs, 带有 radius queries 和 streams 的 geospatial indexes 等数据结构。 Redis具有内置的备份,Lua脚本,LRU逐出,事务和不同级别的磁盘持久性,并通过Redis Sentinel和Redis Cluster自动分区提供高可用性。

Important DataStructure

在Redis中,字典是一个dict类型的结构体,定义在src/dict.h:

1
2
3
4
5
6
7
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;

这里的 dictht 是用于存储数据的结构体。这里定义了一个长度为 2 的数组,它是为了解决扩容时速度较慢而引入的,,rehashidx 扩容时会用到。

1
2
3
4
5
6
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;

结构体中有一个二维数组 table,元素类型是 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可以看出,redis的hash使用的是拉链法解决冲突。

Main Methods

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
// 如果正在rehash,迁移 `rehashidx` 位置上的链表
if (dictIsRehashing(d)) _dictRehashStep(d);
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
// 正在扩容时,使用第二个hash表
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// 在链表头部插入
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;

dictSetKey(d, entry, key);
return entry;
}
  • 头部插入好处:

    1. 找到链表尾部的时间复杂度是 O(n),或者需要使用额外的内存地址来保存链表尾部的位置。头插法可以节省插入耗时。
    2. 对于一个数据库系统来说,最新插入的数据往往更有可能频繁的被获取。头插法可以节省查找耗时。
  • 增量式扩容:
    所谓的增量式扩容是指,当需要重哈希时,每次只迁移一个箱子里的链表,这样扩容时不会出现性能的大幅度下降。

    为了标记哈希表正处于扩容阶段,我们在 dict 结构体中使用 rehashidx 来表示当前正在迁移哪个箱子里的数据。由于在结构体中实际上有两个哈希表,如果添加新的键值对时哈希表正在扩容,我们首先从第一个哈希表中迁移一个箱子的数据到第二个哈希表中,然后键值对会被插入到第二个哈希表中。

迁移链表(bin)时,最终调用如下函数:

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
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;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long)d->rehashidx);
/*跳过第一个表中null的元组,但是不超过10个*/
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
while(de) {
uint64_t h;
nextde = de->next;
/*获取在新hash表中的位置 */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
/*把de转移到新hash表*/
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++;
}
/**将0释放,并将1移交给0,重置1*/
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
return 1;
}
  • 默认hash函数
    与 Java 不同的是,Redis 提供了 void * 类型 key 的哈希函数,也就是通过任何类型的 key 的指针都可以求出哈希值。具体算法定义在 dictGenHashFunction 函数中。它的实现原理是根据指针地址和这一块内存的长度,获取内存中的值,并且放入到一个数组当中,可见这个数组仅由 0 和 1 构成。然后再对这些数字做哈希运算。因此即使两个指针指向的地址不同,但只要其中内容相同,就可以得到相同的哈希值。

    Compare with jdk1.8 HashMap

    参考:JCF-HashMap&HashSet
    Java 的长处在于当哈希函数不合理导致链表过长时,会使用红黑树来保证插入和查找的效率。缺点是当哈希表比较大时,如果扩容会导致瞬时效率降低。

Redis 通过增量式扩容解决了这个缺点,同时拉链法的实现(放在链表头部)值得我们学习。Redis 还提供了一个经过严格测试,表现良好的默认哈希函数,避免了链表过长的问题。

Redis作为存储系统,不支持重写hash方法。Redis 支持的数据结构包括哈希表和集合(Set),但是其中的数据类型只能是字符串。因此 Redis 并不存在对象等同性的考虑,也就可以提供默认的哈希函数了。

Reference

Tags: redis
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章