建设美食网站的目的和功能定位,宁波定制网站建设解决方案,大连网站关键字优化,奎文营销型网站建设目录一、Redis源代码的核心部分1.redis源码在哪里2.src源码包下面该如何看#xff1f;二、我们平时说redis是字典数据库KV键值对到底是什么1.6大类型说明(粗分)2.6大类型说明3.上帝视角4.Redis定义了redisObject结构体4.1 C语言struct结构体语法简介4.2 字典、KV是什么4.3 red…
目录一、Redis源代码的核心部分1.redis源码在哪里2.src源码包下面该如何看二、我们平时说redis是字典数据库KV键值对到底是什么1.6大类型说明(粗分)2.6大类型说明3.上帝视角4.Redis定义了redisObject结构体4.1 C语言struct结构体语法简介4.2 字典、KV是什么4.3 redisObject Redis数据类型Redis 所有编码方式底层实现三者之间的关系三、5大结构底层C语言源码分析1.从set hello world说起2.redisObjec结构的作用2.1 RedisObject各字段的含义2.2 案例3.数据类型以及数据结构的关系3.1 String数据结构介绍3.1.1 3大编码格式3.1.2 3大编码案例3.2.2.1 案例测试3.2.2.2 C语言中字符串的展现3.2.2.3 SDS简单动态字符串3.2.2.4 Redis为什么重新设计一个 SDS 数据结构3.1.3 源码分析3.1.4 总结3.2 Hash数据结构介绍3.2.1 案例3.2.2 hash的两种编码格式3.2.3 源码分析3.3 List数据结构介绍3.3.1 案例3.3.2 List的一种编码格式3.3.3 源码分析3.4 Set数据结构介绍3.4.1 案例3.4.2 Set的两种编码格式3.4.3 源码分析3.5 ZSet数据结构介绍3.5.1 案例3.5.2 ZSet的两种编码格式3.5.3 源码分析4.小总结四、skiplist跳表面试题1.是什么2.说说链表和数组的优缺点为什么引出跳表3.优缺点一、Redis源代码的核心部分
1.redis源码在哪里
redis-6.0.8\redis-6.0.8\src
2.src源码包下面该如何看 二、我们平时说redis是字典数据库KV键值对到底是什么
1.6大类型说明(粗分)
redis 是 key-value 存储系统其中key类型一般为字符串 value 类型则为redis对象(redisObject)
2.6大类型说明
传统的5大类型 新介绍的3大类型
bitmap实质StringhyperLogLog实质StringGEO实质Zset
3.上帝视角
https://redissrc.readthedocs.io/en/latest/datastruct/dict.html https://redissrc.readthedocs.io/en/latest/index.html
4.Redis定义了redisObject结构体
Redis定义了redisObject结构体来表示string、hash、list、set、zset等数据类型 Redis中每个对象都是一个 redisObject 结构
4.1 C语言struct结构体语法简介 4.2 字典、KV是什么
每个键值对都会有一个dictEntry
4.3 redisObject Redis数据类型Redis 所有编码方式底层实现三者之间的关系 三、5大结构底层C语言源码分析
1.从set hello world说起
set hello word为例因为Redis是KV键值对的数据库每个键值对都会有一个dictEntry(源码位置dict.h)
里面指向了key和value的指针next 指向下一个 dictEntry。 key 是字符串但是 Redis 没有直接使用 C 的字符数组而是存储在redis自定义的 SDS中。 value 既不是直接作为字符串存储也不是直接存储在 SDS 中而是存储在redisObject 中。 实际上五种常用的数据类型的任何一种都是通过 redisObject 来存储的。 2.redisObjec结构的作用 为了便于操作Redis采用redisObject结构来统一五种不同的数据类型这样所有的数据类型就都可以以相同的形式在函数间传递而不用使用特定的类型结构。同时为了识别不同的数据类型redisObject中定义了type和encoding字段对不同的数据类型加以区别。简单地说redisObject就是string、hash、list、set、zset的父类可以在函数间传递时隐藏具体的类型信息所以作者抽象了redisObject结构来到达同样的目的。
2.1 RedisObject各字段的含义 1.4位的type表示具体的数据类型 2.4位的encoding表示该类型的物理编码方式见下表同一种数据类型可能有不同的编码方式。(比如String就提供了3种:int embstr raw) 3.lru字段表示当内存超限时采用LRU算法清除内存中的对象。 4.refcount表示对象的引用计数。 5.ptr指针指向真正的底层数据结构的指针。
2.2 案例
set age 17
type类型encoding编码此处是数字类型lru最近被访问的时间refcount等于1表示当前对象被引用的次数ptrvalue值是多少当前就是17
3.数据类型以及数据结构的关系 程序员写代码时脑子底层思维
3.1 String数据结构介绍
3.1.1 3大编码格式
int 保存long 型(长整型)的64位(8个字节)有符号整数 9223372036854775807数字最多19位 补充 只有整数才会使用 int如果是浮点数 Redis 内部其实先将浮点数转化为字符串值然后再保存。 embstr 代表 embstr 格式的 SDS(Simple Dynamic String 简单动态字符串),保存长度小于44字节的字符串 EMBSTR 顾名思义即embedded string表示嵌入式的String raw 保存长度大于44字节的字符串
3.1.2 3大编码案例
3.2.2.1 案例测试 3.2.2.2 C语言中字符串的展现 Redis没有直接复用C语言的字符串而是新建了属于自己的结构-----SDS 在Redis数据库里包含字符串值的键值对都是由SDS实现的(Redis中所有的键都是由字符串对象实现的即底层是由SDS实现Redis中所有的值对象中包含的字符串对象底层也是由SDS实现)。 3.2.2.3 SDS简单动态字符串 Redis中字符串的实现,SDS有多种结构sds.h
sdshdr5、(2^532byte)
sdshdr8、(2 ^ 8256byte)
sdshdr16、(2 ^ 1665536byte64KB)
sdshdr32、 (2 ^ 32byte4GB)
sdshdr642的64次方byte17179869184G用于存储不同的长度的字符串。len 表示 SDS 的长度使我们在获取字符串长度的时候可以在 O(1)情况下拿到而不是像 C 那样需要遍历一遍字符串。alloc 可以用来计算 free 就是字符串已经分配的未使用的空间有了这个值就可以引入预分配空间的算法了而不用去考虑内存分配的问题。buf 表示字符串数组真存数据的。3.2.2.4 Redis为什么重新设计一个 SDS 数据结构 C语言没有Java里面的String类型只能是靠自己的char[]来实现字符串在 C 语言中的存储方式想要获取 「Redis」的长度需要从头开始遍历直到遇到 ‘\0’ 为止。所以Redis 没有直接使用 C 语言传统的字符串标识而是自己构建了一种名为简单动态字符串 SDSsimple dynamic string的抽象类型并将 SDS 作为 Redis 的默认字符串。
3.1.3 源码分析
用户API set k1 v1底层发生了什么调用关系 三大编码 INT 编码格式 命令示例 set k1 123 当字符串键值的内容可以用一个64位有符号整形来表示时Redis会将键值转化为long型来进行存储此时即对应 OBJ_ENCODING_INT 编码类型。内部的内存结构表示如下: Redis 启动时会预先建立 10000 个分别存储 0~9999 的 redisObject 变量作为共享对象这就意味着如果 set字符串的键值在 0~10000 之间的话则可以 直接指向共享对象 而不需要再建立新对象此时键值不占空间 set k1 123 set k2 123 redis源代码object.c EMBSTR编码格式
redis源代码object.c 对于长度小于 44的字符串Redis 对键值采用OBJ_ENCODING_EMBSTR 方式EMBSTR 顾名思义即embedded string表示嵌入式的String。从内存结构上来讲 即字符串 sds结构体与其对应的 redisObject 对象分配在同一块连续的内存空间字符串sds嵌入在redisObject对象之中一样。 RAW 编码格式 set k1 大于44长度的一个字符串,随便写 当字符串的键值为长度大于44的超长字符串时Redis 则会将键值的内部编码方式改为OBJ_ENCODING_RAW格式这与OBJ_ENCODING_EMBSTR编码方式的不同之处在于此时动态字符串sds的内存与其依赖的redisObject的内存不再连续了 明明没有超过阈值为什么变成 raw 了 转变逻辑图
3.1.4 总结
Redis内部会根据用户给的不同键值而使用不同的编码格式自适应地选择较优化的内部编码格式而这一切对用户完全透明! 流程图
3.2 Hash数据结构介绍
3.2.1 案例
结构 hash-max-ziplist-entries使用压缩列表保存时哈希集合中的最大元素个数。 hash-max-ziplist-value使用压缩列表保存时哈希集合中单个元素的最大长度。 结论 1.哈希对象保存的键值对数量小于 512 个 2.所有的键值对的健和值的字符串长度都小于等于 64byte一个英文字母一个字节 时用ziplist反之用hashtable ziplist升级到hashtable可以反过来降级不可以
一旦从压缩列表转为了哈希表Hash类型就会一直用哈希表进行保存而不会再转回压缩列表了。
在节省内存空间方面哈希表就没有压缩列表高效了。3.2.2 hash的两种编码格式
ziplist hashtable
3.2.3 源码分析
ziplist.c Ziplist 压缩列表是一种紧凑编码格式总体思想是多花时间来换取节约空间即以部分读写性能为代价来换取极高的内存空间利用率 因此只会用于 字段个数少且字段值也较小 的场景。压缩列表内存利用率极高的原因与其连续内存的特性是分不开的。 想想我们的学过的一种GC垃圾回收机制标记–压缩算法 当一个 hash对象 只包含少量键值对且每个键值对的键和值要么就是小整数要么就是长度比较短的字符串那么它用 ziplist 作为底层实现 ziplist什么样 ziplist是一个经过特殊编码的双向链表它不存储指向上一个链表节点和指向下一个链表节点的指针而是存储上一个节点长度和当前节点长度通过牺牲部分读写性能来换取高效的内存空间利用率节约内存是一种时间换空间的思想。只用在字段个数少字段值小的场景里面 ziplist各个组成单元什么意思 明明有链表了为什么出来一个压缩链表? 1 普通的双向链表会有两个指针在存储数据很小的情况下我们存储的实际数据的大小可能还没有指针占用的内存大得不偿失。ziplist 是一个特殊的双向链表没有维护双向指针:prev next而是存储上一个 entry的长度和 当前entry的长度通过长度推算下一个元素在什么地方。牺牲读取的性能获得高效的存储空间因为(简短字符串的情况)存储指针比存储entry长度更费内存。这是典型的“时间换空间”。 2 链表在内存中一般是不连续的遍历相对比较慢而ziplist可以很好的解决这个问题普通数组的遍历是根据数组里存储的数据类型找到下一个元素的(例如int类型的数组访问下一个元素时每次只需要移动一个sizeof(int)就行)但是ziplist的每个节点的长度是可以不一样的而我们面对不同长度的节点又不可能直接sizeof(entry)所以ziplist只好将一些必要的偏移量信息记录在了每一个节点里使之能跳到上一个节点或下一个节点。 3 头节点里有头节点里同时还有一个参数 len和string类型提到的 SDS 类似这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表直接拿到len值就可以了这个时间复杂度是 O(1) 压缩列表节点的构成 压缩列表是 Redis 为节约空间而实现的一系列特殊编码的连续内存块组成的顺序型数据结构本质上是字节数组 在模型上将这些连续的数组分为3大部分分别是headerentry集合end 其中header由zlbyteszltailzllen组成 entry是节点 zlend是一个单字节255(1111 1111)用做ZipList的结尾标识符。见下 压缩列表结构由zlbytes、zltail、zllen、entry、zlend这五部分组成 zlbytes 4字节记录整个压缩列表占用的内存字节数。 zltail 4字节记录压缩列表表尾节点的位置。 zllen 2字节记录压缩列表节点个数。 zlentry 列表节点长度不定由内容决定。 zlend 1字节0xFF 标记压缩的结束。 zlentry实体结构解析 官网源码 解析 压缩列表zlentry节点结构每个zlentry由前一个节点的长度、encoding和entry-data三部分组成 前节点(前节点占用的内存字节数)表示前1个zlentry的长度prev_len有两种取值情况1字节或5字节。取值1字节时表示上一个entry的长度小于254字节。虽然1字节的值能表示的数值范围是0到255但是压缩列表中zlend的取值默认是255因此就默认用255表示整个压缩列表的结束其他表示长度的地方就不能再用255这个值了。所以当上一个entry长度小于254字节时prev_len取值为1字节否则就取值为5字节。 enncoding记录节点的content保存数据的类型和长度。 content保存实际数据内容
typedef struct zlentry { // 压缩列表节点// prevrawlen是前一个节点的长度unsigned int prevrawlensize, prevrawlen; //prevrawlensize是指prevrawlen的大小有1字节和5字节两种unsigned int prevrawlensize, prevrawlen; // len为当前节点长度 lensize为编码len所需的字节大小unsigned int lensize, len; // 当前节点的header大小unsigned int headersize; // 节点的编码方式unsigned char encoding; // 指向节点的指针unsigned char *p;
} zlentry;压缩列表的遍历 通过指向表尾节点的位置指针p1, 减去节点的previous_entry_length得到前一个节点起始地址的指针。如此循环从表尾遍历到表头节点。从表尾向表头遍历操作就是使用这一原理实现的只要我们拥有了一个指向某个节点起始地址的指针那么通过这个指针以及这个节点的previous_entry_length属性程序就可以一直向前一个节点回溯最终到达压缩列表的表头节点。
ziplist存取情况 t_hash.c 在 Redis 中hashtable 被称为字典dictionary它是一个数组链表的结构 OBJ_ENCODING_HT 编码分析 OBJ_ENCODING_HT 这种编码方式内部才是真正的哈希表结构或称为字典结构其可以实现O(1)复杂度的读写操作因此效率很高。 在 Redis内部从 OBJ_ENCODING_HT类型到底层真正的散列表数据结构是一层层嵌套下去的组织关系见面图
3.3 List数据结构介绍
3.3.1 案例 (1) ziplist压缩配置list-compress-depth 0 表示一个quicklist两端不被压缩的节点个数。这里的节点是指quicklist双向链表的节点而不是指ziplist里面的数据项个数 参数list-compress-depth的取值含义如下 0: 是个特殊值表示都不压缩。这是Redis的默认值。 1: 表示quicklist两端各有1个节点不压缩中间的节点压缩。 2: 表示quicklist两端各有2个节点不压缩中间的节点压缩。 3: 表示quicklist两端各有3个节点不压缩中间的节点压缩。 依此类推…
(2) ziplist中entry配置list-max-ziplist-size -2 当取正值的时候表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如当这个参数配置成5的时候表示每个quicklist节点的ziplist最多包含5个数据项。当取负值的时候表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时它只能取-1到-5这五个值 每个值含义如下 -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。注1kb 1024 bytes -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。 -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。 -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。-2是Redis给出的默认值 -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。
3.3.2 List的一种编码格式
list用quicklist来存储quicklist存储了一个双向链表每个节点都是一个ziplist 在低版本的Redis中list采用的底层数据结构是ziplistlinkedList
高版本的Redis中底层数据结构是quicklist(它替换了ziplistlinkedList)而quicklist也用到了ziplist quicklist 在低版本的Redis中list采用的底层数据结构是ziplistlinkedList 高版本的Redis中底层数据结构是quicklist(它替换了ziplistlinkedList)而quicklist也用到了ziplist。
quicklist 实际上是 zipList 和 linkedList 的混合体它将 linkedList按段切分每一段使用 zipList 来紧凑存储多个 zipList 之间使用双向指针串接起来。 是ziplist和linkedlist的结合体
3.3.3 源码分析
quicklist.hhead和tail指向双向列表的表头和表尾 quicklistNode中的*zl指向一个ziplist一个ziplist可以存放多个元素
3.4 Set数据结构介绍
3.4.1 案例
Redis用intset或hashtable存储set。如果元素都是整数类型就用intset存储。 如果不是整数类型就用hashtable数组链表的存来储结构。key就是元素的值value为null。
3.4.2 Set的两种编码格式
intset hashtable
3.4.3 源码分析
t_set.c
3.5 ZSet数据结构介绍
3.5.1 案例
当有序集合中包含的元素数量超过服务器属性 server.zset_max_ziplist_entries 的值默认值为 128 或者有序集合中新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值默认值为 64 时 redis会使用跳跃表作为有序集合的底层实现。 否则会使用ziplist作为有序集合的底层实现
3.5.2 ZSet的两种编码格式
ziplist skiplist
3.5.3 源码分析
t_zset.c
4.小总结 redis数据类型以及数据结构的关系
不同数据类型对应的底层数据结构 字符串 int:8个字节的长整型。 embstr:小于等于44个字节的字符串。 raw:大于44个字节的字符串。 Redis会根据当前值的类型和长度决定使用哪种内部编码实现。 哈希 ziplist(压缩列表):当哈希类型元素个数小于hash-max-ziplist-entries 配置(默认512个)、同时所有值都小于hash-max-ziplist-value配置(默认64 字节)时 Redis会使用ziplist作为哈希的内部实现ziplist使用更加紧凑的 结构实现多个元素的连续存储所以在节省内存方面比hashtable更加优秀。 hashtable(哈希表):当哈希类型无法满足ziplist的条件时Redis会使 用hashtable作为哈希的内部实现因为此时ziplist的读写效率会下降而hashtable的读写时间复杂度为O(1)。 列表 ziplist(压缩列表):当列表的元素个数小于list-max-ziplist-entries配置 (默认512个)同时列表中每个元素的值都小于list-max-ziplist-value配置时 (默认64字节) Redis会选用ziplist来作为列表的内部实现来减少内存的使 用。 linkedlist(链表):当列表类型无法满足ziplist的条件时Redis会使用 linkedlist作为列表的内部实现。quicklist ziplist和linkedlist的结合以ziplist为节点的链表(linkedlist) 集合 intset(整数集合):当集合中的元素都是整数且元素个数小于set-max- intset-entries配置(默认512个)时Redis会选用intset来作为集合的内部实现从而减少内存的使用。 hashtable(哈希表):当集合类型无法满足intset的条件时Redis会使用hashtable作为集合的内部实现。 有序集合 ziplist(压缩列表):当有序集合的元素个数小于zset-max-ziplist- entries配置(默认128个)同时每个元素的值都小于zset-max-ziplist-value配 置(默认64字节)时 Redis会用ziplist来作为有序集合的内部实现ziplist 可以有效减少内存的使用。 skiplist(跳跃表):当ziplist条件不满足时有序集合会使用skiplist作 为内部实现因为此时ziplist的读写效率会下降。
redis数据类型以及数据结构的时间复杂度
四、skiplist跳表面试题
1.是什么
跳表是可以实现二分查找的有序链表
skiplist是一种以空间换取时间的结构。由于链表无法进行二分查找因此借鉴数据库索引的思想提取出链表中关键节点索引先在关键节点上查找再进入下层链表查找。提取多层关键节点就形成了跳跃表
总结来讲 跳表 链表 多级索引
2.说说链表和数组的优缺点为什么引出跳表
痛点 解决方法升维也叫空间换时间。
优化 跳表的时间复杂度 时间复杂度是O(logN) 跳表查询的时间复杂度分析 首先每一级索引我们提升了2倍的跨度那就是减少了2倍的步数所以是n/2、n/4、n/8以此类推 第 k 级索引结点的个数就是 n/(2^k) 假设索引有 h 级 最高的索引有2个结点n/(2^h) 2, 从这个公式我们可以求得 h log2(N)-1 所以最后得出跳表的时间复杂度是O(logN) 跳表的空间复杂度 所以空间复杂度是O(N) 跳表查询的空间复杂度分析 首先原始链表长度为n 如果索引是每2个结点有一个索引结点每层索引的结点数n/2, n/4, n/8 … , 8, 4, 2 以此类推 或者所以是每3个结点有一个索引结点每层索引的结点数n/3, n/9, n/27 … , 9, 3, 1 以此类推 所以空间复杂度是O(n)
3.优缺点
跳表是一个最典型的空间换时间解决方案而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多写少的情况下才能使用所以它的适用范围应该还是比较有限的
维护成本相对要高 - 新增或者删除时需要把所有索引都更新一遍 最后在新增和删除的过程中的更新时间复杂度也是O(log n)
