Redis 数据结构(dict)实现
文章目录
一、什么是字典?
字典又称为hash、或者映射(map)、是一种保存键值对的数据结构。
字典中的每一个key都是独一无二的,可以通过key进行、查询、添加、删除、修改操作。
二、哈希表
哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理。哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后和数组容量取模,得到在数组中的位置后再插入。取值时,先对指定的键求Hash值,再和容量取模得到底层数组中对应的位置,如果指定的键值与存贮的键相匹配,则返回该键值对,如果不匹配,则表示哈希表中没有对应的键值对。这样做的好处是在查找、插入等操作可以做到𝑂(1),最坏的情况是𝑂(𝑛),当然这种是最极端的情况,极少遇到。1、hash函数
通过hash函数把不同的键转化为唯一的整数m,redis使用siphash算法、
问题:
我们很难保证把每一个 ”键“ 通过哈希函数转化为不同的”索引“, ”键“通过hash函数得到的”索引”分布越均匀越好。
不管是整数、浮点型、字符串等都可以转化为整型,
原则:
1、一致性。
2、高效性:计算高效简洁。
3、均匀性:哈希值均匀分布。
hash冲突
- 两个不同的 ”键“ 通过 hash 函数转化为了同样的索引,这就叫 hash冲突。
- redis的哈希表的每个hash节点都有一个 next指针,把冲突的节点通过next连接起来,形成一个单向链表,这样就解决了hash冲突。
- redis考虑性能,如果有hash冲突,并且已经有新的节点,采用头插法,插入链表的第一个元素,时间复杂度为 o(1)。
例如插入下标为0的的元素

如果下次通过hash函数计算出下标为还是为0,那么如下,采用头插法,把k2插入到k1之前,并形成单向链表。

三、字典的结构体定义
redis字典结构体代码在dict.h中定义
1、hash表
typedef struct dictht {
dictEntry **table; // hash表数组,指向 dictEntry结构体
unsigned long size; // table 数组的大小。
unsigned long sizemask; //掩码 = size - 1
unsigned long used; // table数组已存在元素个数~~~~
} dictht;
2、hash表的节点
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; //单链表~~~~
} dictEntry;
key保存的是键值对中的键,而v保存键值对中的值,next表示hash冲突时指向的另一对键值对,通过头插法,形成单向链表。

3、redis字典
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;
1、ht 是一个包含了 ht[0] 和 ht[1]两个hash桶,默认情况下是不会使用 ht[1]的,只有在 rehash的时候才会使用。
2、rehashidx字段,默认为 -1,表示没有进行rehash,否在会标记正在进行rehash的index。
二、基本操作
2、添加
流程图

代码
1、从 setKey开始:检查 key是否存在,不存在走dbAdd。
void setKey(redisDb *db, robj *key, robj *val) {
if (lookupKeyWrite(db,key) == NULL) { //检查key是否存在
dbAdd(db,key,val); //不存在插入
} else {
dbOverwrite(db,key,val);
}
incrRefCount(val);
removeExpire(db,key);
signalModifiedKey(db,key);
}
2、创建sds字符串,执行 dictAdd函数
void dbAdd(redisDb *db, robj *key, robj *val) {
sds copy = sdsdup(key->ptr); //创建字符串
int retval = dictAdd(db->dict, copy, val);//插入
serverAssertWithInfo(NULL,key,retval == DICT_OK);
if (val->type == OBJ_LIST ||
val->type == OBJ_ZSET)
signalKeyAsReady(db, key);
if (server.cluster_enabled) slotToKeyAdd(key);
}3、dictAdd调用 dictAddRaw 函数插入 key值。
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key,NULL);
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);
return DICT_OK;
}
4、dictAddRaw 进行如下操作
- 判断是否在 rehash,如果是,执行一次 rehash。
- 获取新元素的索引,如果元素已经存在,否则返回-1。
- 是否在进行 rehash,如果是插入 ht[1],否则插入 ht[0]
- 申请新的内存给新的节点,并插入。
- 给新创建的 dictEntry,赋值 key,并返回新的节点
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d); //判断是否在 rehash。
//获取新元素的索引,如果元素已经存在,则返回-1
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
//是否在进行 rehash,如果是插入 ht[1],否则插入 ht[0]
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; //返回新的节点
}
设置 key
#define dictSetKey(d, entry, _key_) do { \
if ((d)->type->keyDup) \
(entry)->key = (d)->type->keyDup((d)->privdata, _key_); \
else \
(entry)->key = (_key_); \
} while(0)5、如果返回的节点不为null,给新的 entry设置 val
#define dictSetVal(d, entry, _val_) do { \
if ((d)->type->valDup) \
(entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \
else \
(entry)->v.val = (_val_); \
} while(0)gdb
1、setkey,判断key是否存在,不存在走dbAdd。

2、dbAdd 插入键值对。调用 dictAddRaw 函数

3、dictAddRaw,添加键,如果不存在插入新的节点,存在,返回null

4、dictSetVal,根据返回的节点,设置 value。

3、修改。
流程图

代码
1、从 setKey开始:检查 key是否存在,存在走 dbOverwrite。
void setKey(redisDb *db, robj *key, robj *val) {
if (lookupKeyWrite(db,key) == NULL) { //检查key是否存在
dbAdd(db,key,val); //不存在插入
} else {
dbOverwrite(db,key,val);
}
incrRefCount(val);
removeExpire(db,key);
signalModifiedKey(db,key);
}
2、执行dbOverwrite,
- 先调用 dictFind查找key是否存在
- 不存在执行中断
- 存在先获取老节点的值
- 给节点设置新的值
- 释放老节点的val
void dbOverwrite(redisDb *db, robj *key, robj *val) {
dictEntry *de = dictFind(db->dict,key->ptr);//查找key的节点
serverAssertWithInfo(NULL,key,de != NULL); //不存在执行中断
dictEntry auxentry = *de;
robj *old = dictGetVal(de);//获取老节点的值
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
val->lru = old->lru;
}
dictSetVal(db->dict, de, val);//给节点设置新的值
if (server.lazyfree_lazy_server_del) {
freeObjAsync(old);
dictSetVal(db->dict, &auxentry, NULL);
}
dictFreeVal(db->dict, &auxentry); //释放老节点的val
}dictFind 查找 key是否存在
- 如果 ht[0]和ht[1]没有节点,返回 null。
- 是否在进行 rehash,如果是执行一次rehash。
- 循环遍历获取 key的节点,找到返回,否则返回null。
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
uint64_t h, idx, table;
if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}gdb


4、删除
调用的是dictDelete中。实则调用的是 dictGenericDelete函数。
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
uint64_t h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
//遍历 ht[0] 和 ht[1],循环遍历,找到节点,删除
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
prevHe = NULL;
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key)) {
/* Unlink the element from the list */
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
}
d->ht[table].used--;
return he;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return NULL; /* not found */
}缩容:
htNeedsResize 判断当前的 dict是否需要缩容。
如:HASHTABLE_MIN_FILL = 10size = 16used = 1
判断是否可以缩容,最小容量为4。
例如:
容量为16(size),当used为1,时,才能缩容。
如:(used*100/size < HASHTABLE_MIN_FILL)) = 100/16 < 10;
int htNeedsResize(dict *dict) {
long long size, used;
size = dictSlots(dict);
used = dictSize(dict);
return (size > DICT_HT_INITIAL_SIZE &&
(used*100/size < HASHTABLE_MIN_FILL));
}void tryResizeHashTables(int dbid) {
if (htNeedsResize(server.db[dbid].dict))
dictResize(server.db[dbid].dict);
if (htNeedsResize(server.db[dbid].expires))
dictResize(server.db[dbid].expires);
}gdb
缩容前 size = 16

缩容后 size = 4

5、扩容 和 渐进式 rehash。
扩容
默认为4个dictEntry,当插入的元素主键增多,容量上限时,会触发扩容。

- 通过调用栈可以看到,通过dictAdd,dictAddRaw,会执行 _dictExpandIfNeeded,判断是否需要扩容,走到dictExpand。
- 通过 gdb可以看到需要当前库容 为 p d->ht[0].used*2 = 18
- 执行_dictNextPower,检查库容后的值,必须为 2 的 N 次方。最小为4。
- 申请一个新的 dictEntry,并赋值给 ht[1]。
- 把前的 rehashidx 复制为 0,表示正在进行rehash。
- 前面的添加操作可以看到添加时,会判断是否在rehahash,如果是,会添加到ht[1]上,而修改、删除、查询、则会在两个ht中查找。
static int _dictExpandIfNeeded(dict *ht) {
/* If the hash table is empty expand it to the initial size,
* if the table is "full" dobule its size. */
if (ht->size == 0)
return dictExpand(ht, DICT_HT_INITIAL_SIZE);
if (ht->used == ht->size)
return dictExpand(ht, ht->size*2);
return DICT_OK;
}int dictExpand(dict *d, unsigned long size)
{
/* the size is invalid if it is smaller than the number of
* elements already inside the hash table */
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
dictht n; /* the new hash table */
unsigned long realsize = _dictNextPower(size);
/* Rehashing to the same table size is not useful. */
if (realsize == d->ht[0].size) return DICT_ERR;
/* 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) {
d->ht[0] = n;
return DICT_OK;
}
/* Prepare a second hash table for incremental rehashing */
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}
满 8 后,后续插入到 ht[1]中,如下:
(gdb) p d
$10 = (dict *) 0x7ff810c0b360
(gdb) p *d
$11 = {type = 0x786a40 <dbDictType>, privdata = 0x0, ht = {{table = 0x7ff810c15100, size = 8, sizemask = 7, used = 8}, {table = 0x7ff8088c4000, size = 16,
sizemask = 15, used = 1}}, rehashidx = 0, iterators = 0}渐进式rehash
- 创建足够的空间,给ht[1],如果上述 8扩容至16,每次*2。
- 把 rehashidx 从 -1 改为 1,表示正在进行rehash。
- 重新计算 ht[0] 中 键对应的hash值,依次添加到 ht[1]。
- rehash操作完成后,清空ht[0],对调一下ht[1]和ht[0]
- 把rehashidex 修改为-1
rehash完成的结果
(gdb)
$18 = {type = 0x786a40 <dbDictType>, privdata = 0x0, ht = {{table = 0x7ff8088c4000, size = 16, sizemask = 15, used = 9}, {table = 0x0, size = 0, sizemask = 0,
used = 0}}, rehashidx = -1, iterators = 0}

6、迭代器(待补充)
思考:
1、php和redis实现的区别及rehash的区别?为什么要这么做?
区别:
php的数组结构,分为索引数组和bucket两个,索引数组用来记录存数据真正放在 bucket的那一个索引。如果通过hash函数计算的值有冲突通过, 通过 zval 的 next 链接起来,解决了hash冲突,这一点和redis一样的原理,php这种方式保证了是有序存放的,而redis的字典存储是无序的。

php 的rehash是一次性扩容,只有一个ht,把旧的ht直接放到新的ht。
测试在php脚本中(使用一个比较大的数组测试扩容)耗时
<?php
ini_set('memory_limit','256M');
//$start = microtime(true);
$startMemory = memory_get_usage();
$t1 = microtime(true);
$arr = [];
for ($i = 0 ; $i < 2097152; $i ++) {
$arr[$i] = $i;
}
$arr[] = '触发扩容';
//结束
$t2 = microtime(true);
$endMemory = memory_get_usage();
//输出
echo sprintf("内存使用: %f kb<br>", ($endMemory - $startMemory) / 1024);
echo sprintf("耗时: %f秒<br>", round($t2-$t1,3));
扩容前:
内存使用: 65540.187500 kb 耗时: 0.303000秒
扩容后:
内存使用: 131076.187500 kb 耗时: 0.396000秒可以看到 大概扩容耗时在 50- 100 毫秒。
为什么这么做?
因为php是多进程模型的(master、worker),而在php业务中,数组的大小普遍会比较小,就算是在一个rehash一个比较大的数组,因为是多进程模型是可以接受的,不会堵塞所有的进程。 而redis是单进程、单线程,dict是存储数据库的,会存储海量的数据,几百万,几千万、甚至几个亿,这个时候如果不采用渐进式的rehash,而是使用php的rehash的操作,有很大的可能会造成服务器的短暂瘫痪,这对于高性能的redis是不可接受的。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论