深入理解Redis
深入理解Redis
Redis的数据类型和数据结构
常见的数据类型
Stirng类型
- 底层数据结构:SDS
List类型
- 底层数据结构:双向链表或者压缩列表
- 当列表元素小于512个,列表的每个元素的值都小于64字节,Redis会使用压缩列表
- 否则Redis会使用双向链表
- 在Redis3.2之后,List的底层数据结构由quickList实现
Hash类型
- 底层数据结构:压缩列表或者哈希表实现
- 如果哈希类型元素小于512个且所有值小于64字节,Redis会使用压缩列表作为Hash类型的底层数据结构
- 否则使用哈希表
- 在Redis7.0之后,由listpack数据结构实现
Set类型
- 底层数据结构:哈希表或者整数集合
- 如果集合中的元素都是整数且个数小于512,Redis会使用整数集合作为Set类型的底层数据结构
- 否则,使用哈希表作为Set类型的底层数据结构
ZSet类型
- 底层数据结构:压缩列表或者跳表
- 如果有序集合的元素个数小于128个,并且每个元素的值小于64字节,Redis会使用压缩列表作为ZSet类型的底层数据结构
- 否则使用跳表
- 在Redis7.0,压缩列表的数据结构已经废弃,使用listpack数据结构实现
Redis数据结构(8种)
SDS
- 结构设计:
- Len:记录字符串长度
- Alloc:记录分配的空间长度
- Flags:记录sds的类型
- Buf[]:存放数据的字节数组
- 相比于原本C的字符串的好处
- 可以以O(1)的时间复杂度获取字符串的长度,直接返回len
- 二进制安全,可以存储\0
- 不会发送缓冲区溢出,会自动扩容
- 扩容机制:
- 如果所需的sds长度小于1mb,扩容策略是翻倍
- 如果所需的sds长度超过1mb,扩容策略是所需sds长度+1mb
- 好处:
- 可以有效减少内存的分配次数
- 扩容机制:
- 节省内存空间
- 使用不同的sds类型:数据结构中的len和alloc变量的数据类型不同,可以灵活的保存不同大小的字符串,从而节省内存空间
- 使用编译优化:要求编译器在编译过程中取消优化对齐,按照实际占用的字节数进行对齐
双向链表
- 结构设计:
- head 头节点
- 节点设计:
- prev 前置节点
- next 后置节点
- value 节点值
- 节点设计:
- tail 尾节点
- dup 节点负责函数
- free 节点释放函数
- match 节点比较函数
- len 节点数量
- head 头节点
- 优点:
- 获取前置节点和后置节点的时间复杂度为O(1),前后置节点都可以指向NULL,所以无环
- 获取头节点和尾节点的时间复杂度是O(1)
- 获取节点数量的时间复杂度是O(1)
- 可以保持不同类型的值
- 缺点:
- 每个节点的内存并不连续,所以无法很好的利用cpu缓存
- 每个节点要存储额外的信息,内存开销大
压缩列表
设计思想,一种内存紧凑型的数据结构,占用一块连续的内存空间,便于利用cpu缓存,根据不同长度的数据,进行相应的编码
缺陷:
- 不能保存过多的元素,否则查询效率会降低
- 新增或者修改某个元素的时候,压缩列表占用的内存空间需要重新分配,可能引发连锁更新的问题
结构设计:
- 表头:
- zlbytes:记录整个压缩列表占用内存字节数
- Zltail : 记录尾部节点距离起始地址多少节点,也就是列表尾的偏移量
- Zllen: 记录压缩列表包含的节点数量
- 表尾
- Zlend: 记录压缩列表的结束点,固定值oxFF
- 表头:
节点:
- Prevlen: 记录前一个节点的长度,便于实现从后向前遍历
- 如果前一个节点的长度小于254字节,需要1字节的空间
- 如果前一个节点的长度大于等于254字节,需要5字节的空间
- encoding:记录当前节点实际数据的类型(字符串和整数)和长度
- 如果节点数据为整数,那么encoding需要1字节的空间
- 如果是字符串,根据字符串的大小,使用,1字节/2字节/5字节空间进行编码
- 前两个bit表示数据的类型,后续表示数据的实际长度
- data:记录当前节点的实际数据
- Prevlen: 记录前一个节点的长度,便于实现从后向前遍历
优点:
- 查询第一个节点,最后一个节点,节点数的实际复杂度是O(1),查找其他元素的时间复杂度是O(N),因此压缩列表不适合保存过多的元素
缺陷:
- 连锁更新
- 更新一个节点导致prevlen发送变化,进而导致后续所有节点的prevlen发送变化
- 连锁更新
哈希表
- 结构设计:
- dictEntry tabile : 哈希表数组
- Key 键值对中的键
- V 键值对中的值
- next:指向下一个节点,形成链表
- Size : 哈希表大小
- Sizemask: 哈希表大小的掩码,用于计算索引值
- Used : 哈希表已有的节点数量
- dictEntry tabile : 哈希表数组
- 哈希冲突的解决:
- 使用链式哈希,被分配到同一个哈希桶的多个节点,使用单项链表连接起来
- Rehash: 如果一个桶的数据过多,就需要Rehash
- 步骤:
- 给哈希表2分配空间,一般比哈希表1大一倍
- 将哈希表1的数据迁移到哈希表2中
- 迁移完成后,将哈希表2设置为哈希表1,新创建一个哈希表2,为下次rehash做准备
- 渐进式rehash
- 在rehash期间,每次对哈希表进行新增、删除、查找、更新操作时,除了执行对应的操作之外,还会按照顺序将哈希表1上索引位置所有的key-value,迁移到哈希表2上
- rehash的触发条件
- 负载因子:
- 计算:哈希表已保存节点数量 / 哈希表的大小
- 当负载因子大于等于1,并且Redis没有执行bgsave或者bgrewriteaof,也就是没有执行RDB快照或者进行AOF重写的时候,就会进行rehash操作
- 当负载因子大于5的时候,无论有没有执行RDB快照或者AOF重写,都会强制进行rehash操作
- 负载因子:
- 步骤:
整数集合
- 结构设计:
- Encoding 编码方式
- Length: 元素数量
- Contents: 保存元素的数组,元素的类型取决于encoding的值
- 整数集合的升级操作
- 当新元素的类型比现在所有元素的类型都要长时,整数集合要先按照新元素的类型扩展contents数组的大小,在将新元素加入到整数集合
- 好处:节省内存资源
跳表
- 结构设计:
- Header, tail跳表的头尾节点
- Ele 对象的元素值
- Score 元素的权重值
- Backward 后向指针
- Level[]
- 保存每一层的前向指针和跨度
- length 跳表的长度
- Level 跳表的最大层数
- Header, tail跳表的头尾节点
- 查询过程:
- 从头节点的最高点开始,逐一遍历每一层
- 如果当前节点的权重小于要查找的权重,跳表就会访问该层的下一个节点
- 如果当前节点的权重等于要查找的权重,并且当前节点的sds类型数据小于要查找的数据,跳表就会访问该层的下一个节点
- 如果以上条件不满足,或者下一个节点为空,跳表会使用当前遍历节点level数组里的下一层指针,沿着下一层指针继续查找,相当于跳到了下一层继续查找
- 从头节点的最高点开始,逐一遍历每一层
- 跳表相邻两层的节点数量最理想的比例是2:1,查找复杂度可以降低到O(logN)
- 跳表在创建节点的时候,会生成范围(0 - 1)的一个随机数,如果这个随机数小于0.25,层数就增加一层,然后继续生成下一个随机数,直到结果大于0.25
- 层高的限制是64,在创建头节点的时候,就会直接创建64层高的头节点
- 为什么要使用跳表而不使用平衡树
- 从内存占用来说,跳表每个节点只有1.33个指针,调整参数后,跳表比平衡树更灵活一些
- 在做范围查找的时候,跳表比平衡树操作要简单
- 从算法实现难度上来说,跳表比平衡树要简单
Quicklist
- quicklist取代了list的双向链表或者压缩列表的底层数据结构
- 本质上是 双向链表 + 压缩列表
- 结构设计
- Head, tail, quicklist链表头
- Prev. next, 前置,后置节点
- zl,节点对应的压缩列表
- 压缩列表的字节大小
- 压缩列表的元素个数
- Count 压缩列表元素总数
- Len quicklist节点总数
- Head, tail, quicklist链表头
Listpack
目的:用于替换压缩列表,解决连锁更新的问题
结构设计:
- 头部
- listpack总字节数
- listpack元素数量
- 节点:
- Encoding 元素的编码类型,会对不同长度的整数和字符串进行编码
- data,数据存放
- Len encoding + data的总长度
- 尾部
- 结尾标识
- 头部
listpack没有压缩列表中记录前一个节点长度的字段了,listpack只记录了当前节点的长度,当我们向listpack加入一个新元素的时候,不会影响其他节点的长度字段的变化,从而避免了压缩列表的连锁更新问题
如何向前遍历:
- 从当前列表项起始位置的指针开始,向左逐个字节解析,得到前一项的 entry-len 值
Redis 线程模型
Redis并非单线程
- 接收客户端请求->解析请求->进行数据的读写操作->发送数据给客户端这个过程是由一个线程,主线程来完成的
- 在2.6版本,会启动2个后台线程,分别用来处理关闭文件、AOF刷盘
- 在4.0 之后,新增了一个后台线程,用来异步释放Redis内存,也就是lazyfree线程
Redis单线程模式是怎么样的
- 使用了epoll,IO多路复用来监听连接事件,读事件,写事件,在监听到事件后,调用对应的事件处理函数
为什么Redis是单线程,但还是这么快
- Redis大部分操作都在内存中完成,并且采用了高效的数据结构
- Redis采用单线程模型避免了多线程之间的竞争
- Redis采用了I/O多路复用机制来处理大量的客户端的Socket请求
为什么Redis要使用单线程
- CPU并不是制约Redis性能表现的瓶颈所在
- 引入多线程,会增加系统复杂度,同时可能存在线程切换、加锁解锁、死锁造成的性能损耗
为什么Redis6.0之后引入了多线程
- 在Redis6.0之后,采用了多个I/O线程来处理网络请求,因为随着网络硬件的性能提升,Redis的性能瓶颈有时会出现在网络I/O的处理上
Redis 持久化
Redis如何实现数据不丢失
- AOF日志:每执行一条写操作命令,就把该命令以追加的方式写入到一个文件里
- RDB快照:将某一时刻的内存数据,以二进制的方式写入磁盘
- 混合持久化方式:Redis4.0新增的方式,集合了AOF和RDB的优点
AOF日志实现方式
Redis在执行完一条命令后,会把命令以追加的方式,写入到一个文件里,然后Redis重启时,会读取该文件记录的命令,然后逐一执行命令的方式来进行数据恢复
为什么先执行命令,再把数据写入日志呢?
- 好处
- 避免额外的检查开销
- 不会阻塞当前写操作命令的执行
- 弊端
- 数据可能会丢失
- 可能会阻塞其他操作
- 好处
写入日志的实现过程:
- 命令追加到server.aof_buf缓冲区(用户态)
- I/O系统调用(write())切换到内核态
- 写入到内核缓冲区
- 由内核发起写操作,写入磁盘
- 什么
- 时候写入磁盘,由操作系统内核决定
- Redis.conf提供了3种写入磁盘的参数
- Always:每次写操作完毕后,同步将AOF日志数据写回磁盘
- EverySec:每次写操作命令执行完后,先将命令写入到AOF文件的内核缓冲区,然后每隔1s将缓冲区的内容写回磁盘
- No:不由Redis控制写回磁盘的时机,由操作系统控制
AOF日志过大,触发重写机制
- 重写机制会读取所有key最新的value,然后用一条命令记录到新的AOF文件,之前的一个命令就没有必要记录了,重写完成后,会将新的AOF文件覆盖现在的AOF文件,这相当于压缩了AOF文件,使得AOF文件的体积变小了
- 重写的过程:
- 启动一个重写子进程,共享物理内存
- 子进程对内存只读,重写子进程读取内存所有键值对,逐一转换成命令,在将命令写到新的日志
- 重写过程中,主进程依然可以正常处理命令,但主进程修改已经存在的kv会导致写时复制,此时这个 key-value 数据在子进程的内存数据就跟主进程的内存数据不一致了
- 为了解决这种数据不一致问题,Redis 设置了一个 AOF 重写缓冲区
- 重写 AOF 期间,当 Redis 执行完一个写命令之后,它会同时将这个写命令写入到 「AOF 缓冲区」和 「AOF 重写缓冲区」
- 当子进程完成 AOF 重写工作会向主进程发送一条信号,信号是进程间通讯的一种方式,且是异步的。
- 调用一个信号处理函数,该函数主要做以下工作
- 将 AOF 重写缓冲区中的所有内容追加到新的 AOF 的文件中,使得新旧两个 AOF 文件所保存的数据库状态一致
- 新的 AOF 的文件进行改名,覆盖现有的 AOF 文件。
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.