通俗易懂redis数据结构之链表+字典
数据结构之链表
上次写了SDS的内容,很荣幸上了CSDN热榜,距离今天已经过了好久了,因为最近在看一些其他的东西,加上工作有点忙,所以就停止了,这次主要写下链表和字典。
链表定义
链表在redis中使用也是比较多的,比如key对应的元素比较多或者元素包含字符串比较长、发布与订阅、监视器等都会用到链表。
每个链表节点使用一个adlist.h/listNode结构表示,如下:
typedef struct listNode {// 前置节点
typedef listNode *prev;// 后置节点
typedef listNode *next;// 节点的值void*value;} listNode
// 这里其实不用多解释的,双端链表嘛,有前驱节点和有后继节点,next指向下一个节点指针,pre指向前一个节点指针
最经典的比如使用list类型时,l/rpush元素,使用llen获取元素个数等这些操作,在一开始接触时,就想获取元素个数应该不是通过遍历O(n)复杂度来获取长度吧?其实还有使用adlist.h/list来持有的链表,如下:
typedef struct list {// 表头节点
listNode *head;// 表尾节点
listNode *tail;// 链表长度
unsigned long len;// 节点值复制函数void*(*dup)(void*ptr);// 节点值释放函数void*(*free)(void*ptr);// 节点值对比函数int(*match)(void*ptr,void*key);} list;
以上的dup、free、match是实现多态链表所需的类型特定函数,所以可以保存不同类型的值:
- dup函数用于复制链表节点所保存的值
- free函数用于释放链表节点所保存的值
- match函数用于对比链表节点所保存的值和另一个输入值是否相等 一个list结构和三个listNode结构如下: 通过上面方式实现redis链表就有了如下特性:
- 双端:节点都有pre和next,获取前驱和后继节点复杂度O(1)
- 链表无环:表头的前驱结点以及表尾的后继节点都指向null
- 获取表头和表尾节点复杂度O(1)
- 获取链表长度复杂度O(1)
- void *指针保存节点值,通过list结构的dup、free、match三属性为节点值设置类型特定函数,所以链表可以用于保存不同类型的值。
数据结构之字典
字典嘛,我首先会想到的就是map这种东西,其实就是一个key和value的映射,在字典里,每个键都是唯一的,可以根据键来进行查找、删除、更新操作等。这种字典在java中很多数据结构使用,但是redis构建了自己的字典。
字典使用
比如如下代码块set一个值,就会将键值对<name,dtxld>保存在字典里,除了数据库,字典还是哈希键的实现之一,当哈希键键值对比较多或者键值对中元素都是比较长的字符串时,就会使用字典作为其实现。
set name dtxld // 简单的string类型
下面主要是由字典来进行的一些延伸:字典的数据结构如下:
typedef struct dict {// 类型特定函数
dictType *type;// 私有数据void*privdata;// hash表(这里可以对比下hashMap)
dicht ht[2];// rehash索引,rehash不进行时,值为-1int rehashidx;} dict
上面的参数其实都好理解,对于我这个新手来说主要陌生的就是type、privdata、ht,下面分析下:
type属性指向了dictType结构的指针,每个dictType保存了一簇用于操作特定类型键值对的函数,redis为用途不同的字典设置不同的类型特定函数(可以参考下双端链表),privdata属性保存了需要传给类型特定函数的可选参数,dictType结构如下:
typedef struct dictType {// 计算哈希值函数
unsigned int(*hashFunction)(constvoid*key);// 复制键的函数void*(*keyDup)(void*privdata,constvoid*key);// 复制值的函数void*(*valDup)(void*privdata,constvoid*obj);// 对比键的函数int(*keyCompare)(void*privdata,constvoid*key1,constvoid*ke2);// 销毁键的函数void(*keyDestructor)(void*privdata,void*key);// 销毁值的函数void(*valDestructor)(void*privdata,void*obj);} dictType
接着看下ht,塔是包含了两个项的数组,数组中的每一项都是dictht哈希表,一般情况,只使用ht[0],ht[1]只是对ht[0]进行rehash时使用,dictht结构如下dict.h/dictht:
typedef struct dictht {// 哈希表数组
dictEntry **table;// 哈希表大小
unsigned long size;// 总是等于size - 1,用于计算哈希索引值
unsigned long sizeMask;// 该哈希表已有节点数量
unsigned long used;} dictht
table属性是数组,数组里每个元素指向dictEntry,dictEntry结构如下dict.h/dictEntry:
typedef struct dictEntry {// 兼void*key;// 值--可以指针/uint64_t整数/int64_t整数
union {void*val;
uint64_tu64;
int64_ts64;} v;// next指针指向另一个哈希表节点的指针,形成链表--hash冲突,形成链表的时候// 使用的头插法,因为链表没有指向表尾的指针,redis毕竟性能优先嘛// 也是为了性能
struct dictEntry *next;} dictEntry
rehash之前整个字典结构合起来如下:
知道上面的这些东西之后,我首先会去想怎么把一个键值对放进去这个哈希表中,所以redis会有hash算法来计算索引值:
// 计算hash值,字典被用作数据库底层实现或者hash键底层实现,redis使用的Murmurhash算法来计算键的hash值
hash = dict->type->hashFunction(key);// 计算索引值,为什么是ht[x]因为ht[0]和ht[1]会换的,后面会说
index = hash & dict->ht[x].sizeMask;
rehash
随着业务的变化,键值对太多或者太少,这时肯定会有相应的扩展和收缩的操作,这个操作通过执行rehash(重新散列函数)来完成,主要步骤如下:
- 为字典的ht[1]分配空间(这个在上面画到过,一开始是0),这个空间的大小会取决于要执行的操作以及ht[0]当前包含的键值对数量,也就是ht[0].used的值 如果执行的是扩展操作:ht[1]大小是第一个大于等于ht[0].used * 2的2 ^ n(2的n次幂)。 如果执行的是收缩操作:ht[1]大小是第一个大于等于ht[0].used 的2n。
- 将保存的ht[0]里的元素rehash到ht[1],rehash就是重新计算hash值和index索引
- 当ht[0]都迁移到ht[1]以后(ht[0变成了空表]),这时释放掉ht[0],将ht[1]设置成ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备
在这里我一开始就联想到了hashMap,就会去想那什么时候去扩展呢?
redis是根据服务器有没有在执行bgsave或者bgrewriteaof来进行扩展,当正在进行时,并且hash表的load_factor(负载因子)大于等于5会去扩展;
当没有进行时,hash表的load_factor(负载因子)大于等于1会去扩展。
// 负载因子 = 哈希表已保存节点数量 / 哈希表的大小
load_factor = ht[0].used / ht[0].size
这里会想到为什么和是否执行bgsave或者bgrewriteaof,他的负载因子不同呢?当然了,redis也是出于避免rehash和他们一同执行,毕竟他们执行时候会去创建子进程,这样可以避免不必要的内存写入,减少内存。
这里当load_factor小于0.1时,会自动进行收缩操作。
这里还有一个问题,既然是rehash,那到底是怎么执行的呢?键值对如果就4、5个,那一会的事情就搞定,如果数量很大,500多万,5亿个呢?一次性rehash完,肯定会导致服务器一段时间停止服务,这估计就完了吧…
所以redis采用的渐进式rehash,什么是渐进式rehash,其实就是分多次进行。具体步骤如下:
- 为ht[1] 分配空间,让字典同时持有ht[0]和ht[1]两个哈希表
- 在字典里维护一个索引计数器变量rehashidx,将它的值设为0,表示rehash工作正式开始
- 在rehash期间,每次对字典进行curd操作时,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],rehash完成之后,程序将其rehashidx值+1
- 随着程序的执行,最终ht[0]上的键值对全部rehash到ht[1],将rehashidx设置为-1,rehash结束。
当然在字典同时持有ht[0]和ht[1]的时候,并且在rehash期间,ht[0]不在进行任何添加操作,都会添加到ht[1],这时候你在添加到ht[0]那真是没意义,因为这样可以保证ht[0]只会减少不会增加,随着rehash最后变为空表。当查找一个键的时候,程序会先在ht[0]查找,若没有才会去ht[1]查找。
上面是我对这两个的理解,若有不对欢迎指出评论,顺便给个赞,年后马上金三银四,祝福大家跳槽愉快,薪资翻倍,下一篇跳表、整数集合、压缩列表一起整了,加油吧年轻人!
版权归原作者 短腿小鲁蛋 所有, 如有侵权,请联系我们删除。