深入理解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 节点数量
• 优点：
  • 获取前置节点和后置节点的时间复杂度为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：记录当前节点的实际数据

• 优点：

  • 查询第一个节点，最后一个节点，节点数的实际复杂度是O(1)，查找其他元素的时间复杂度是O(N)，因此压缩列表不适合保存过多的元素

• 缺陷：

  • 连锁更新
    • 更新一个节点导致prevlen发送变化，进而导致后续所有节点的prevlen发送变化

哈希表

• 结构设计：
  • dictEntry tabile : 哈希表数组
    • Key 键值对中的键
    • V 键值对中的值
    • next：指向下一个节点，形成链表
  • Size : 哈希表大小
  • Sizemask: 哈希表大小的掩码，用于计算索引值
  • Used : 哈希表已有的节点数量
• 哈希冲突的解决：
  • 使用链式哈希，被分配到同一个哈希桶的多个节点，使用单项链表连接起来
  • 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 跳表的最大层数
• 查询过程：
  • 从头节点的最高点开始，逐一遍历每一层
    • 如果当前节点的权重小于要查找的权重，跳表就会访问该层的下一个节点
    • 如果当前节点的权重等于要查找的权重，并且当前节点的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节点总数

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 文件。