信丰网站制作,网页电子书在线阅读器wordpress,企业集团网站建设,wordpress 发件邮箱Redis 字典
基本语法
字典是Redis中的一种数据结构#xff0c;底层使用哈希表实现#xff0c;一个哈希表中可以存储多个键值对#xff0c;它的语法如下#xff0c;其中KEY为键#xff0c;field和value为值#xff08;也是一个键值对#xff09;#xff1a;
HSET key…Redis 字典
基本语法
字典是Redis中的一种数据结构底层使用哈希表实现一个哈希表中可以存储多个键值对它的语法如下其中KEY为键field和value为值也是一个键值对
HSET key field value根据Key和field获取value
HGET key field哈希表
数据结构
dictht
dictht是哈希表的数据结构定义
table哈希表数组数组中的元素是dictEntry类型的size哈希表数组的大小sizemask哈希表大小掩码一般等于size-1used已有节点的数量存储键值对的数量
typedef struct dictht {dictEntry **table;unsigned long size;unsigned long sizemask;unsigned long used;
} dictht;dictEntry
dictEntry是哈希表节点的结构定义
key键值对中的键v键值对中的值next由于会出现哈希冲突所以next是指向下一个节点的指针
typedef struct dictEntry {void *key; // 键union {void *val;uint64_t u64;int64_t s64;double d;} v; // 值struct dictEntry *next; // 指向下一个节点的指针
} dictEntry;dict
dict是Redis中字典的结构定义
type指向dictType的指针privdataht[2]一个dictht类型的数组数组大小为2保存了两个哈希表rehash时使用rehashidx记录了当前rehash的进度pauserehashrehash暂停标记大于0表示没有进行rehash
typedef struct dict {dictType *type; // void *privdata; // 私有数据dictht ht[2]; // 保存了两个哈希表long rehashidx; // rehash的进度标记int16_t pauserehash;
} dict;typedef struct dictType {uint64_t (*hashFunction)(const void *key);void *(*keyDup)(void *privdata, const void *key);void *(*valDup)(void *privdata, const void *obj);int (*keyCompare)(void *privdata, const void *key1, const void *key2);void (*keyDestructor)(void *privdata, void *key);void (*valDestructor)(void *privdata, void *obj);int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;哈希冲突
一个键值对放入哈希表的时候会根据key的值计算一个hash值然后根据hash值与哈希表大小掩码做与运算得到一个索引值索引值决定元素放入哪个哈希桶中落入哈希表数组哪个索引位置处。 // 计算hash值hash dictHashKey(d,key)// 计算索引idx hash d-ht[table].sizemask;在进行哈希计算的时候不可避免会出现哈希冲突出现哈希冲突的时候Redis采用链式哈希解决冲突也就是落入同一个桶中的元素使用链表将这些冲突的元素链起来dictEntry中的next指针。 rehash
由于Redis采用链式哈希解决冲突那么在冲突频繁的场景下链表会变得越来越长这种情况下查找效率是比较低下的需要遍历链表对比KEY的值来获取数据为了处理效率低下的问题需要对哈希表进行扩容扩容的过程称为rehash。
在dict结构替中ht保存了两个哈希表ht[0]用于数据正常的增删改查ht[1]用于rehash
1正常情况下所有的增删改查操作都在ht[0]中进行
2需要进行rehash时会使用ht[1]建立新的哈希表并将ht[0]中的数据迁移到ht[1]中
3迁移完成后ht[0]的空间被释放然后将ht[1]地址赋给ht[0]ht[1]的大小被设为0ht[0]重新接收正常的请求回到了第1步的状态
rehash的触发条件
/* 判断是否需要扩容 */
static int _dictExpandIfNeeded(dict *d)
{/* 如果已经处于rehash状态中直接返回 */if (dictIsRehashing(d)) return DICT_OK;/* 如果ht[0]的大小为0意味着哈希表为空此时做初始化操作 */if (d-ht[0].size 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);/*如果已经存储的节点数量大于或等于哈希表数组的大小并且跨域扩容或者节点数量/哈希表数组大小大于一个比例同时根据字典的类型判断是否允许分配内存*/if (d-ht[0].used d-ht[0].size (dict_can_resize ||d-ht[0].used/d-ht[0].size dict_force_resize_ratio) dictTypeExpandAllowed(d)){ // 进行扩容return dictExpand(d, d-ht[0].used 1);}return DICT_OK;
}/* 由于扩容需要分配内存这里检查字典类型分配是否被允许*/
static int dictTypeExpandAllowed(dict *d) {if (d-type-expandAllowed NULL) return 1;return d-type-expandAllowed(_dictNextPower(d-ht[0].used 1) * sizeof(dictEntry*),(double)d-ht[0].used / d-ht[0].size);
}d-ht[0].used/d-ht[0].size : 节点数量与哈希表数组大小的比例称作负载因子。 dict_force_resize_ratio 的默认值是 5。 ht[0]的大小为0此时哈希表是空的相当于对哈希表做一个初始化的操作。如果哈希表中存储的节点数量大于或者等于哈希表数组的大小并且哈希表可以扩容或者负载因子大于dict_force_resize_ratio默认值为5根据字典的类型判断允许分配内存满足这三个条件开始扩容。
dict_can_resize
dict_can_resize用来判断哈希表是否可以扩容有两种状态值分别为1和01代表可以扩容0代表禁用扩容
void dictEnableResize(void) {dict_can_resize 1;
}void dictDisableResize(void) {dict_can_resize 0;
}updateDictResizePolicy中对dict_can_resize的状态进行了控制当前没有RDB子进程并且也没有AOF子进程时设置dict_can_resize状态为可扩容 void updateDictResizePolicy(void) {// 没有RDB子进程并且也没有AOF子进程if (server.rdb_child_pid -1 server.aof_child_pid -1)dictEnableResize(); // 启用扩容elsedictDisableResize(); // 禁用扩容
}扩容大小
从代码中可以看到扩容后哈希表数组的大小为已经存储的节点数量1
// 进行扩容
return dictExpand(d, d-ht[0].used 1);一些旧版本中扩容后的大小为已存储节点数量的2倍
dictExpand(d, d-ht[0].used*2);渐进式hash
当哈希表存储节点内容比较多时需要将原来的节点一个一个拷贝到新的哈希表中此时Redis主线程无法执行其他请求造成阻塞影响性能为了解决这个问题引入了渐进式hash。
渐进式hash并不会一次把旧节点全部拷贝到新的哈希表中而是分多次渐进式的完成拷贝其中rehashidx记录了迁移进度每一次迁移的过程中会更新rehashidx的值下一次进行数据迁移的时候从rehashidx的位置开始迁移在dictRehash中可以看到迁移的处理
方法传入了一个参数n代表本次需要迁移几个哈希桶根据需要迁移哈希桶的数量循环处理每一个哈希桶 如果当前哈希桶中为空继续下一个桶的处理rehashidx如果当前哈希桶不为空将当前桶中的所有节点迁移到新的哈希表中然后更新rehashidx的值继续处理下一个桶 如果已经处理够了n个桶或者哈希表的所有数据已经迁移完毕则结束迁移。
int dictRehash(dict *d, int n) {int empty_visits n*10; /* Max number of empty buckets to visit. */if (!dictIsRehashing(d)) return 0;// 循环处理每一个哈希桶n为需要迁移哈希桶的数量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) {// rehashidx的值是哈希表数组的某个索引值指向了某个哈希桶意味着当前迁移到数组的哪个索引位置处d-rehashidx; // 继续下一个桶if (--empty_visits 0) return 1;}de d-ht[0].table[d-rehashidx];// 如果当前的哈希桶中存储着数据将哈希桶存储的所有数据迁移到新的哈希表中while(de) {uint64_t h;nextde de-next;/* Get the index in the new hash table */h dictHashKey(d, de-key) d-ht[1].sizemask;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;// rehashidx继续迁移下一个哈希桶d-rehashidx;}/* 判断ht[0]的节点是否迁移完成 */if (d-ht[0].used 0) {// 释放ht[0]的空间zfree(d-ht[0].table);// 将ht[0]指向ht[1]d-ht[0] d-ht[1];// 重置ht[1]的大小为0_dictReset(d-ht[1]);// 设置rehashidx-1代表rehash结束d-rehashidx -1;return 0;}/* More to rehash... */return 1;
}_dictRehashStep
_dictRehashStep中可以看到调用dictRehash时每次迁移哈希桶的数量为1
static void _dictRehashStep(dict *d) {if (d-pauserehash 0) dictRehash(d,1);
}总结 Redis字典底层使用哈希表实现。 键值对放入哈希表的时候会根据key的值计算hash值出现哈希冲突的时候Redis采用链式哈希解决冲突使用链表将这些冲突的元素链起来。 由于Redis采用链式哈希解决冲突那么在冲突频繁的场景下链表会变得越来越长这种情况下查找效率是比较低下的需要遍历链表对比KEY的值来获取数据为了处理效率低下的问题需要对哈希表进行扩容扩容的过程称为rehash。 当哈希表存储节点内容比较多时进行rehas的时候主线程无法执行其他请求造成阻塞影响性能所以采用了渐进式hash渐进式hash并不会一次把旧节点全部拷贝到新的哈希表中而是分多次渐进式的完成拷贝。
参考
黄健宏《Redis设计与实现》
极客时间 - Redis源码剖析与实战(蒋德钧)
美团针对Redis Rehash机制的探索和实践
Redis版本redis-6.2.5
