网站建站东莞,湛江手机网站建设公司,做网站拍摄照片用什么佳能相机好,没有网站百度推广#x1f44f;作者简介#xff1a;大家好#xff0c;我是爱吃芝士的土豆倪#xff0c;24届校招生Java选手#xff0c;很高兴认识大家#x1f4d5;系列专栏#xff1a;Spring源码、JUC源码、Kafka原理、分布式技术原理、数据库技术#x1f525;如果感觉博主的文章还不错的… 作者简介大家好我是爱吃芝士的土豆倪24届校招生Java选手很高兴认识大家系列专栏Spring源码、JUC源码、Kafka原理、分布式技术原理、数据库技术如果感觉博主的文章还不错的话请三连支持一下博主哦博主正在努力完成2023计划中源码溯源一探究竟联系方式nhs19990716加我进群大家一起学习一起进步一起对抗互联网寒冬 文章目录 Redis经典五大类型源码及底层实现经典面试题redis源码核心部分数据结构Redis数据库的实现Redis服务端和客户端实现Redis字典数据库KV键值对是什么10大类型上帝视角RedisObject结构体struct结构体字典、KV是什么redisObject Redis数据类型 Redis所有编码方式底层实现三者之间的关系 五大数据结构C语言源码分析redis6.0.5Redis7源码分析总体数据结构大纲从set hello world说起redisObject结构的作用RedisObject各个字段的含义 五大经典结构解析String数据类型介绍3大物理编码方式intembstrraw 3大物理编码案例SDS简单动态字符串Redis为什么要重新设计一个SDS数据结构呢源码分析结论 Hash数据结构介绍Redis6案例源码分析t_hash.cOBJ_ENCODING_HT编码解析ziplist明明已经有链表了出来一个压缩链表ziplist总结 Redis经典五大类型源码及底层实现
经典面试题
Redis的跳跃列表了解吗这个数据结构有什么特点
redis项目里面怎么用redis的数据结构都了解那些
redis的zset底层实现说了压缩列表和跳表问这样设计的优缺点只说了优点缺点没说出来
redis的跳表说一下解决了哪些问题时间复杂度和空间复杂度如何
其实阅读源码90%是没有太大意义的完全是为了面试但是10%是因为大厂自己的内部中间件比如贵公司自己内部redis重构阿里云redis美团tair滴滴kedrs等等
redis源码 https://github.com/redis/redis
而对应的源码分析的书籍有 核心部分
数据结构
简单动态字符串sds.c整数集合intset.c压缩列表ziplist.c快速链表quicklist.clistpack字典dict.c
Redis数据库的实现
数据库底层实现db.c 和 持久化rdb.c 、aof.c
Redis服务端和客户端实现
事件驱动ae.c 和 ae_epoll.c网络连接anet.c 和 networking.c服务端程序 server.c客户端程序redis-cli.c
Redis字典数据库KV键值对是什么
redis是key-value存储系统key一般是String类型的字符串对象value类型则为redis对象redisObjectvalue可以是字符串对象也可以是集合数据类型的对象比如List对象Hash对象set对象和zset对象。 10大类型
String
List
Hash
Set
Zset
bitmap 实质是String
hyperloglog 实质是String
GEO 实质是Zset
Stream 实质是Stream
BITFIELD 看具体key 上帝视角 RedisObject结构体
redis定义了redisobject结构体来表示string、hash、list、set、zset等数据结构
struct结构体 Redis中每个对象都是一个redisobject
字典、KV是什么
每个键值对都会有一个dictEntry 这些键值对是如何保存进Redis并进行读取操作O1复杂度的 redisObject Redis数据类型 Redis所有编码方式底层实现三者之间的关系 五大数据结构C语言源码分析
redis6.0.5
redis6之前老版本 Redis7 源码分析总体数据结构大纲
程序员写代码时脑子底层思维 从set hello world说起
set hello word为例因为Redis是KV键值对的数据库每个键值对都会有一个dictEntry(源码位置dict.h)
里面指向了key和value的指针next 指向下一个 dictEntry。
key 是字符串但是 Redis 没有直接使用 C 的字符数组而是存储在redis自定义的 SDS中。
value 既不是直接作为字符串存储也不是直接存储在 SDS 中而是存储在redisObject 中。
实际上五种常用的数据类型的任何一种都是通过 redisObject 来存储的。 看看类型
type hello
String看看编码
Object encoding hello
embstrredisObject结构的作用
为了便于操作Redis采用redisObjec结构来统一五种不同的数据类型这样所有的数据类型就都可以以相同的形式在函数间传递而不用使用特定的类型结构。同时为了识别不同的数据类型redisObjec中定义了type和encoding字段对不同的数据类型加以区别。简单地说redisObjec就是string、hash、list、set、zset的父类可以在函数间传递时隐藏具体的类型信息所以作者抽象了redisObjec结构来到达同样的目的。 RedisObject各个字段的含义 1 4位的type表示具体的数据类型
2 4位的encoding表示该类型的物理编码方式见下表同一种数据类型可能有不同的编码方式。
(比如String就提供了3种:int embstr raw)
3 lru字段表示当内存超限时采用LRU算法清除内存中的对象。
4 refcount表示对象的引用计数。
5 ptr指针指向真正的底层数据结构的指针。 例如
set age 17 type类型encoding编码此处是数字类型lru最近被访问的时间refcount等于1表示当前对象被引用的次数ptrvalue值是多少当前就是17
五大经典结构解析
各个类型的数据结构的编码映射和定义 Debug Object key 开启后 Value at: 内存地址
refcount: 引用次数
encoding: 物理编码类型
serializedlength: 序列化后的长度注意这里的长度是序列化后的长度保存为rdb文件时使用了该算法不是真正存贮在内存的大小),会对字串做一些可能的压缩以便底层优化
lru记录最近使用时间戳
lru_seconds_idle空闲时间 String数据类型介绍
3大物理编码方式
RedisObjectt内部对应的3大物理编码 int
保存long型长整型的64位8个字节的有符号整数 补充只有整数才会使用int如果是浮点数Redis内部其实先将浮点数转化为字符串值然后再保存。
embstr
代表embstr格式的SDS 简单动态字符串保存长度小于44字节的字符串顾名思义表示嵌入式的String
raw
保存长度大于44字节的字符串
3大物理编码案例 假如现在展现一个字符串:Redis Redis没有直接复用C语言的字符串而是新建了属于自己的结构-----SDS
在Redis数据库里包含字符串值的键值对都是由SDS实现的(Redis中所有的键都是由字符串对象实现的即底层是由SDS实现Redis中所有的值对象中包含的字符串对象底层也是由SDS实现)。 SDS简单动态字符串
sds.h源码分析 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 表示字符串数组真存数据的。 Redis为什么要重新设计一个SDS数据结构呢
C语言没有Java里面的String类型只能是靠自己的char[]来实现字符串在 C 语言中的存储方式想要获取 「Redis」的长度需要从头开始遍历直到遇到 ‘\0’ 为止。所以Redis 没有直接使用 C 语言传统的字符串标识而是自己构建了一种名为简单动态字符串 SDSsimple dynamic string的抽象类型并将 SDS 作为 Redis 的默认字符串。
C语言SDS字符串长度处理需要从头开始遍历直到遇到 ‘\0’ 为止时间复杂度O(N)记录当前字符串的长度直接读取即可时间复杂度 O(1)内存重新分配分配内存空间超过后会导致数组下标越级或者内存分配溢出空间预分配 SDS 修改后len 长度小于 1M那么将会额外分配与 len 相同长度的未使用空间。如果修改后长度大于 1M那么将分配1M的使用空间。惰性空间释放 有空间分配对应的就有空间释放。SDS 缩短时并不会回收多余的内存空间而是使用 free 字段将多出来的空间记录下来。如果后续有变更操作直接使用 free 中记录的空间减少了内存的分配。二进制安全二进制数据并不是规则的字符串格式可能会包含一些特殊的字符比如 ‘\0’ 等。前面提到过C中字符串遇到 ‘\0’ 会结束那 ‘\0’ 之后的数据就读取不上了根据 len 长度来判断字符串结束的二进制安全的问题就解决了
源码分析
set k1 v1 底层发生了什么调用关系 三大物理编码方式 int编码 set k1 123
命令示例 set k1 123
当字符串键值的内容可以用一个64位有符号整形来表示时Redis会将键值转化为long型来进行存储此时即对应 OBJ_ENCODING_INT 编码类型。内部的内存结构表示如下: Redis 启动时会预先建立 10000 个分别存储 0~9999 的 redisObject 变量作为共享对象这就意味着如果 set字符串的键值在 0~10000 之间的话则可以
直接指向共享对象 而不需要再建立新对象此时键值不占空间
set k1 123
set k2 123
接下来就很类似Integer如果是128以内的话那么常量池中就存在 redis源代码server.h,笔记下面还有 redis6源代码object.c笔记下面还有 redis7源代码object.c笔记下面还有 EMBSTR编码格式 set k1 abc
redis源代码object.c 对于长度小于 44的字符串Redis 对键值采用OBJ_ENCODING_EMBSTR 方式EMBSTR 顾名思义即embedded string表示嵌入式的String。从内存结构上来讲 即字符串 sds结构体与其对应的 redisObject 对象分配在同一块连续的内存空间字符串sds嵌入在redisObject对象之中一样。 进一步createEmbeddedStringObject方法
redis源代码object.c
从图中也可以看出内存相当紧凑没有重新分配空间 RAW编码格式 set k1 大于44长度的一个字符串随便写 当字符串的键值为长度大于44的超长字符串时Redis 则会将键值的内部编码方式改为OBJ_ENCODING_RAW格式这与OBJ_ENCODING_EMBSTR编码方式的不同之处在于此时动态字符串sds的内存与其依赖的redisObject的内存不再连续了 明明没有超过阈值为什么变成raw了 判断不出来就取最大Raw
转变逻辑图 结论
只有整数才会使用 int如果是浮点数 Redis 内部其实先将浮点数转化为字符串值然后再保存。
embstr 与 raw 类型底层的数据结构其实都是 SDS (简单动态字符串Redis 内部定义 sdshdr 一种结构)。
那这两者的区别见下图
1 intLong类型整数时RedisObject中的ptr指针直接赋值为整数数据不再额外的指针再指向整数了节省了指针的空间开销。2 embstr当保存的是字符串数据且字符串小于等于44字节时embstr类型将会调用内存分配函数只分配一块连续的内存空间空间中依次包含 redisObject 与 sdshdr 两个数据结构让元数据、指针和SDS是一块连续的内存区域这样就可以避免内存碎片3 raw当字符串大于44字节时SDS的数据量变多变大了SDS和RedisObject布局分家各自过会给SDS分配多的空间并用指针指向SDS结构raw 类型将会调用两次内存分配函数分配两块内存空间一块用于包含 redisObject结构而另一块用于包含 sdshdr 结构 总结Redis内部会根据用户的不同键值而使用不同的编码格式自适应地选择较优化的内部编码格式而这一切对用户来说完全透明
Hash数据结构介绍
Redis6
ziplist hashtable
案例
hash-max-ziplist-entries使用压缩列表保存时哈希集合中的最大元素个数。
hash-max-ziplist-value使用压缩列表保存时哈希集合中单个元素的最大长度。
Hash类型键的字段个数 小于 hash-max-ziplist-entries 并且每个字段名和字段值的长度 小于 hash-max-ziplist-value 时
Redis才会使用 OBJ_ENCODING_ZIPLIST来存储该键前述条件任意一个不满足则会转换为 OBJ_ENCODING_HT的编码方式 hash-max-ziplist-entries使用压缩列表来保存是哈希集合中最大元素个数
hash-max-ziplist-value使用压缩列表保存时哈希集合中单个元素的最大长度
结论
1.哈希对象保存的键值对数量小于512个
2.所有的键值对的键和值字符串长度豆小于等于64byte一个英文字母一个字节时用ziplist反之用hashtable
其中ziplist升级到hashtable可以反过来降级不可以
一旦从压缩列表转为了哈希表Hash类型就会一直用哈希表进行保存而不会再转回压缩列表了。
在节省内存空间方面哈希表就没有压缩列表高效了。 流程 源码分析
t_hash.c
在Redis中hashtable被称为字典dictionary它是有一个数组 链表的结构
OBJ_ENCODING_HT编码解析
OBJ_ENCODING_HT 这种编码方式内部才是真正的哈希表结构或称为字典结构其可以实现O(1)复杂度的读写操作因此效率很高。
在 Redis内部从 OBJ_ENCODING_HT类型到底层真正的散列表数据结构是一层层嵌套下去的组织关系见面图 源代码dict.h hset命令解读 ziplist
Ziplist 压缩列表是一种紧凑编码格式总体思想是多花时间来换取节约空间即以部分读写性能为代价来换取极高的内存空间利用率
因此只会用于 字段个数少且字段值也较小 的场景。压缩列表内存利用率极高的原因与其连续内存的特性是分不开的。
为了节约内存而开发的它是由连续内存块组成的顺序型数据结构有点类似于数组
ziplist是一个经过特殊编码的双向链表它不存储指向前一个链表节点prev和指向下一个链表节点的指针next而是存储上一个节点长度和当前节点长度通过牺牲部分读写性能来换取高效的内存空间利用率节约内存是一种时间换空间的思想。只用在字段个数少字段值小的场景里面 zlentry实体结构解析 prevlen记录了前一个节点的长度encoding记录了当前节点实际数据的类型以及长度data记录了当前节点的实际数据
压缩列表zlentry节点结构每个zlentry由前一个节点的长度、encoding和entry-data三部分组成 前节点(前节点占用的内存字节数)表示前1个zlentry的长度privious_entry_length有两种取值情况1字节或5字节。取值1字节时表示上一个entry的长度小于254字节。虽然1字节的值能表示的数值范围是0到255但是压缩列表中zlend的取值默认是255因此就默认用255表示整个压缩列表的结束其他表示长度的地方就不能再用255这个值了。所以当上一个entry长度小于254字节时prev_len取值为1字节否则就取值为5字节。记录长度的好处占用内存小1或者5个字节
enncoding记录节点的content保存数据的类型和长度。
content保存实际数据内容 privious_entry_lengthencoding长度都可以根据编码方式推算真正变化的是content而content长度记录在encoding里 因此entry的长度就知道了。entry总长度 privious_entry_length字节数encoding字节数content字节数 为什么entry这么设计记录前一个节点的长度
链表在内存中一般是不连续的遍历相对比较慢而ziplist可以很好的解决这个问题。如果知道了当前的起始地址因为entry是连续的entry后一定是另一个entry想知道下一个entry的地址只要将当前的起始地址加上当前entry总长度。如果还想遍历下一个entry只要继续同样的操作。
明明已经有链表了出来一个压缩链表
1 普通的双向链表会有两个指针在存储数据很小的情况下我们存储的实际数据的大小可能还没有指针占用的内存大得不偿失。ziplist 是一个特殊的双向链表没有维护双向指针:previous next而是存储上一个 entry的长度和当前entry的长度通过长度推算下一个元素在什么地方。牺牲读取的性能获得高效的存储空间因为(简短字符串的情况)存储指针比存储entry长度更费内存。这是典型的“时间换空间”。
2 链表在内存中一般是不连续的遍历相对比较慢而ziplist可以很好的解决这个问题普通数组的遍历是根据数组里存储的数据类型找到下一个元素的(例如int类型的数组访问下一个元素时每次只需要移动一个sizeof(int)就行)但是ziplist的每个节点的长度是可以不一样的而我们面对不同长度的节点又不可能直接sizeof(entry)所以ziplist只好将一些必要的偏移量信息记录在了每一个节点里使之能跳到上一个节点或下一个节点。
备注:sizeof实际上是获取了数据在内存中所占用的存储空间以字节为单位来计数。
3 头节点里有头节点里同时还有一个参数 len和string类型提到的 SDS 类似这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表直接拿到len值就可以了这个时间复杂度是 O(1)
ziplist总结
ziplist为了节省内存采用了紧凑的连续存储。
ziplist是一个双向链表可以在时间复杂度为 O(1) 下从头部、尾部进行 pop 或 push。
新增或更新元素可能会出现连锁更新现象(致命缺点导致被listpack替换)。
不能保存过多的元素否则查询效率就会降低数量小和内容小的情况下可以使用。
