Redis五大数据结构的底层实现

news/2024/12/22 9:19:42/

一)String类型:可以使用object encoding name就可以查看字符串的编码

SDS,flags的值不同,那么len和alloc所表示的值的数据范围也不同,所以flags的只是为了标识SDS头的总大小;

alloc和len刚开始进行申请内存空间的时候都是相同的

String是redis中最常见的数据结构类型:

1)最基本的编码方式是RAW,是基于简单动态字符串来实现的,存储上线是512mb,每一次存储一个String类型的数据的时候,需要先申请内存创建一个RedisObject的内存空间,再申请SDS的内存空间,申请的时候有两次内存的申请,释放的时候也是有两次内存的释放;

 2)如果存储的SDS的长度是小于44个字节的,那么会直接采用EMBSTR编码,此时的ObjectHead和SDS是一段连续的内存空间,申请内存的时候只是需要调用一次内存分配函数即可(因为每一次分配内存都要涉及到用户态和内核态的切换) 

SDS一共占用48个字节,RedisObject占用16个字节,一共是64个字节(不会超过64字节),Redis在底层采用的内存分配算法是以2^N来做内存分配的,64恰好是一个分片大小,就不会产生内存碎片,所以实际使用String类型的时候,尽量字符串长度小于44字节

3)如果进行存储的字符串是整数值,况且在Long_Max范围内,底层就会使用INT编码,直接将数据存储在RedisObject的指针位置(指针刚好8个字节),就不需要SDS了

Redis中的List数据结构

Redis的List类型可以从首和尾进行操作元素

哪一个数据结构可以满足以上特征呢 

1)使用普通双向链表,可以从双端进行访问内存占用比较高,内存碎片比较多

2)使用ZipList,可以从双端进行访问,内存的占用比较低,存储的上限比较低,双端访问不是基于指针实现的,而是记录每一个结点的大小,推算出内存地址的,因为他是申请连续内存空间的,如果数据量不多还可以,但是如果数据量过大,申请较大的连续内存空间效率可能非常低,所以是不建议使用ZipList来存储过多的数据的,只能存储少量数据

3)QuickList:底层是使用双端链表+压缩列表,可以从双端进行访问,内存占用是比较低的,包含多个Ziplist,存储上限较高,双端列表的每一个节点不是数据而是一个ZipList

3.1)在3.2版本之前,Redis使用ZipList(只能存储少量数据)和LinkedList来实现List,当元素数量小于512况且元素大小小于64字节的时候采用ZipList编码,超过使用LinkedList编码;

3.2)在3.2版本以后,Redis统一使用QuickList来实现List;

1)上面这个方法是通用的插入方法,where是队首或者是队尾,lpush和rpush底层都是调用的pushGenericCommand方法,最后的这个xx参数,如果你进行传递了,也就是true,只有当前的key存在,才会执行push命令,如果不存在,一般是不会传递的,也就是当你第一次进行插入的时候,key不存在,就会自动创建这个key,并分配内存空间;

2)第一个参数client代表客户端,当redis的客户端和服务端建立连接的时候,都会被封装成一个client对象,里面包含着客户端的各种信息,包括客户端要执行的命令,每一个命令都会被分成N段(lpush key value l1 l2 l3),命令本质上就是一个一个的字符串,每一个字符串会使用空格隔开,分成多个命令段放到一个数组中,也就是argv数组,其实最后执行命令的时候,就是从c里面的argv数组中取出一个一个的参数命令段,拼接成完整命令执行;

3)j=2开始遍历是在寻找未来可以存放在list中的元素,里面的if语句是针对用户传递过来的针对于元素大小的校验,argc就是整个argv数组元素的个数;

4)lookupkeywrite方法是在寻找你要向list集合中的哪一个key进行push,第一个参数是c->db,是客户端要进行访问哪一个数据库,取出当前客户端要访问的数据库,第二个参数在数据库中去选择对应key去寻找对应的value(list);

最终方法的返回值是一个RedisObject对象(list)

5)然后去进行检查当前类型是否是一个List类型,根据RedisObject中的type属性来检查当前对象的类型,如果不是list类型直接返回;

6)如果RedisObject不存在并且xx为true,说明没有list就直接返回了;

7)否则就会在createQuickList中创建一个全新的List:

8)createObject方法底层创建了一个全新的RedisObject对象,并将RedisObject中数据的指针指向创建的新的list,并在方法底层针对RedisObject设置全新的编码和类型;

 

9)最后的quicklistsetoptions中限制QuickList中每一个ZipList的大小,是否压缩,server.list_compress_depth是压缩深度,如果是0表示不进行压缩,如果是1表示QuickList的首尾各有一个不压缩,中间节点压缩,如果是2表示QuickList的首尾各有两个节点不压缩,中间节点压缩

10)dbAdd方法是真正的添加元素

Redis中的Set数据结构:对元素的查询效率非常高

Set是Redis中的单列集合,包括以下特点:

1)不保证有序性

2)保证元素唯一

3)求并集,差集,补集

1)首先就是跳表, 查询性能比较不错,但是不太合适,首先跳表要去根据score值进行排序,但是Set集合不需要有序,但是Set集合中还没有score值;

2)Set是Redis中的集合,不一定保证元素有序性,但是需要保证元素唯一,对查询性能要求极高,为了保证查询效率和唯一性,set使用dict编码,dict中的key用来存储元素,value统一使用null;

3)当存储的Set集合里面全部都是整数的时候,并且元素数量不超过set-max-intset-entries的时候,底层默认使用的是IntSet编码,是连续存储空间,元素数量也不能太多,从而来节省内存;

1)subject就是一个RedisObject对象,里面的编码可能是Inset或者是dict,第二个参数是要插入的值

2)进行新增元素的时候如果RedisObject中的编码是HT编码,那么直接插入元素value即可

3)如果RedisObject中的编码类型是IntSet那么直接判断当前value是否是整数,如果是整数,直接添加元素到IntSet里面,如果此时添加元素成功了,直接判断当前元素个数是否大于了set-max-intset-entries的值,如果大于,那么直接将编码转换成HT

4)如果value值不是整数直接转换成HT编码;

 

Zset集合:

Zset也是SortedSet,其中每一个元素都需要指定score值和member值

1)可以根据score值进行排序

2)member值必须唯一

3)可以根据member值查询分数

在Zset里面底层的数据结构必须满足键值存储,键必须唯一,可以进行排序

1)跳表这种数据结构,SkipList可以进行排序,并且可以同时存储score值和ele字符串,但是要根据键查询对应的分数值就比较困难了,只能通过遍历的方式进行查询,效率比较低,况且member只能是唯一的,实现起来就比较困难;

2)HT:可以进行键值存储,并且可以根据Key(member)来查询对应的value值但是不能做排序

基于跳表进行排序(根据value也就是score得分来做排序,来做范围查找,基于哈希表来根据key(member)查询指定的val(score),但是很占用内存;

当元素数量不多的时候,那么HT和SkipList的优势是不明显的,而且还会更耗费内存,因此Zet底层还会采用ZipList结构来节省内存,但是要满足以下两个条件:

1)元素数量小于zset_max_ziplist_entries,默认值是128

2)每一个元素都小于zset_max_ziplist_value,默认值是64字节,这两个条件都是可以通过配置文件进行修改

1)这个代码首先会根据key去寻找对应的zset结构,如果不存在就创建新的Zset,最终返回的是RedisObject对象,里面的内容执行zset;

2)进行检查编码是否是Zset,如果不是则进行退出

3)如果zset不存在那么直接进行初始化操作,首先会在if条件中进行判断zset_max_ziplist_entries是否等于0,如果等于0说明这是人为手动进行设置的,说明如果这个条件成立,那么永远也不会再使用ZipList编码了,永远使用Dict+SkipList编码

或者是value中的元素大小小于zset_max_ziplist_value

 

1)上面的代码首先进行判断当前的编码格式,如果已经是跳表了,那么无需进行转换

2)如果是ZipList编码,首先进行判断当前元素中是否已经存在了这个新增的值(通过RedisObject中的ptr指针来进行查询),如果当前元素已经存在了,那么直接更新score值即可

3)如果元素不存在,就直接判断当前元素总个数(假设已经把这个元素给添加进来了,所以要+1)和当前元素的大小是否已经超过了指定的值,或者是整个ZipList的大小超过了上限,也是更换编码

但数据量比较小的时候,Zset底层使用ZipList,ZipList本身并没有排序功能,而且没有键值对的概念,因此只能通过Zset底层编码来实现:

1)ZipList是连续内存空间,因此score值和element是连续紧挨在一起的两个entry,element在前,score值在后面

2)score值越小越靠近队首,score值越大越靠近队尾,最终是按照score值升序排列的

 Hash结构的底层实现:

Hash结构和Zset结构十分相似,都是键值存储,都是要求根据键来获取对应的值,况且键都是唯一的,但是它们的区别也是很明显的:

1)Zset的值要求是member,值是score,但是哈希类型的键和值都是任意值

2)zset要根据score值进行排序,hash则无需进行排序

因此Hash结构底层采用的编码和Zset也是基本一致的只需要把排序有关的ZipList去掉即可 

1)Hash结构底层默认使用的是ZipList编码,用来节省内存,ZipList中的两个相邻Entry分别保存field和value

2)但数据量比较大的时候,Hash结构默认会转化为HT编码也就是Dict,但是触发条件有两个

2.1)ZipList中的元素数量超过了hash-max-ziplist-entries默认是512字节

2.2)ZipList中的任意entry大小超过了hash-max-ziplist-value默认是64字节

argv数组中全是用户输入的分段命令,argc是argv数组的长度

 

1)首先redis会进行判断如果当前编码不是ZipList编码,那么啥也不用做了,直接返回

2)start=2,表示要想hash结构中添加的元素的第一个value值得索引,argc是最后一个数组的长度,argc-1就是最后一个要向key中添加得value得索引下标

3)开始进行for循环遍历,判断这个value值是否是字符串,如果是字符串,就继续向下进行判断,然后根据sdslen来求出字符串的字节数,如果字节数大于hash_max_ziplist_value那么直接更换编码为hash

4)如果ZipList的长度大小超过了1G,也转化成哈希表

5)但是在上面的这个代码里面没有做ZipList元素大小的判断,因为用户输入的field值可能原来已经在redis中存在了,如果发现redis中的field值和用户所进行指定的field值相同,那么会直接覆盖对应的value值,但是redis中哈希结构的值的个数也是没有发生变化的,所以在这里面是不能够判断ZipList中的元素数量超过了hash-max-ziplist-entries转化成Dict编码

最终向Zset集合中添加元素的代码:

1)先进行查看是否是ZipList编码,如果不是ZipList编码,直接将之插入到哈希表中或者覆盖

2)如果是ZipList编码,先进行查询head指针,如果head不为空,再根据ziplistFind查询field值是否已经在redis中存在了,如果已经存在了,直接调用zipListReplace更新value值update代表是否执行了更新操作,将其置为1;

3)如果不存在,也就是update不等一,直接添加到ZipList的尾部

4)最后再来判断list长度是否超出


http://www.ppmy.cn/news/168092.html

相关文章

VS Code的launch.json配置文件如何编写?

文章目录 launch.jsonconfigurationsnametypelaunch.json {"version": "0.2.0","configurations": [{"name": "g++ - Build and debug active file"

NSS周常刷密码(2)

[GWCTF 2019]babyRSA 解答过程在脚本内 from Crypto.Util.number import * import gmpy2 import sympy import z3e 0x10001 N63658514959457474690903016018269086622290925646484729178300065183722792133723789965128794359777327094438403485892529574488072710160684141…

CAR-T药物|疗法适应症|市场销售-上市药品前景分析

对患有癌症的人来说,能够幸运地度过5年大关是一种成功,而能够成功地度过10年大关则是一种奇迹。Emily作为全球第一个接受CAR-T治疗成功的白血病儿童患者,至今已成功摆脱癌症11年之久。 ①CAR-T细胞治疗(Emily Whitehead治疗案例时…

核心交换机、汇聚交换机、接入交换机

核心交换机 核心交换机是三层交换机支持路由功能,高速转发,有大容量接口宽带(万兆),较大的背板出来能力,性能高于汇聚、接入交换机。 (背板能力:背板能力是路由器的内部实现。背板能…

工业交换机与普通商用交换机区别

工业交换机,也称为工业以太网交换机,是一种专门设计用于工业环境的网络技术。它为工业网络提供可靠、高速的数据传输,包括速度更快的万兆(10G)工业交换机。通常,工业以太网是管理各种类型工业设备之间通信的一种经济有效的方法。 …

工业级交换机应该怎么选,您知道吗?

工业级交换机现在是愈来愈广了,许多相对性较严苛、繁杂的环境基本上都靠工业交换机来完成数据信息通信网络。可是,销售市场上各式各样的工业级交换机十分多,假如公司分配你来购置一批交换机,你知道如何选择吗?就这个难…

工业交换机和工控交换机有什么区别?

众所周知,以太网交换机一般分为:商用(以太网)交换机、工业(以太网)交换机、家用(以太网)交换机,因为我们是专业的工业交换机厂家,在这里着重介绍下工业交换机。 工业交换机一般用在工业生产场合,通常外观和安装形式多…

工业交换机,工控交换机和程控交换机的区别和联系

数据通信行业的人都应该听说过工业交换机、工控交换机、程控交换机等交换机的说法,但很多的朋友估计还不太清楚他们三者之间的区别和关系,它们一般各自都应用在哪些方面,今天我们就来简单介绍一下。 工控交换机其实不是标准名称,只…