首页 Redis

# 数据结构

# 动态字符串 SDS

# 介绍

Redis 中保存的 Key 是字符串，value 往往是字符串或者字符串的集合，Redis 构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称 SDS

不过 Redis 没有直接使用 c 语言中的字符串，因为 c 语言存在以下问题

  1. 获取字符串长度需要通过运算
  2. 非二进制安全
  3. 不可修改

# 扩容机制

  1. 新字符串小于 1M，则新空间为扩展后字符串长度的两倍 + 1
  2. 新字符串大于 1M，则新空间为扩展后字符串长度 + 1M+1，称为内存预分配
  3. 优点
    1. 获取字符串长的的时间复杂度为 O (1)
    2. 支持动态扩容
    3. 减少内存分配次数
    4. 二进制安全

# IntSet

# 介绍

IntSet 是 Redis 中 set 集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征

# 结构

Redis 会将 intset 中所有整数按照升序依次保存在 contents 数组中，如图

image-20230410162051333

数组中每个数字都在 int16_t 范围内，因此采用编码方式是 INTEST_ENC_INT16，每部分占用字节大小为

  1. encoding：4 字节
  2. length：4 字节
  3. contents：2 字节 * 3=6 字节

# 升级功能

假设有一个 intset，元素为 {5，10，20}，采用的编码是 INTSET_ENC_INT16，则每个整数占 2 字节

image-20230410162730198

image-20230410163302257

我们向该其中添加一个数字：50000，这个数字超出了 int_16 的范围，intset 会自动升级编码方式到合适的大小

  1. 升级编码为 INTEST_ENC_INT32，每个整数占用 4 字节，并按照新的编码方式及元素个数扩容数组
  2. 倒序依次将数组中的元素拷贝到扩容后的正确位置
  3. 将待添加的元素放入数组末尾
  4. 最后，将 inset 的 encoding 属性改为 INTEST_ENC_INT32，将 length 属性改为 4

image-20230410163312416

# Dict

# 介绍

Redis 是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速增删改查，而键值的映射关系正是通过 Dict 来实现的

Dict 由三部分组成：分别是：哈希表（DictTable）、哈希节点（DictEntry）、字典（Dict）

# Dict 的扩容

Dict 中的 HashTable 就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率大大降低

Dict 在每次新增键值对时都会检查负载因子（LoadFactor = used/size），满足以下两种情况时会发生哈希表扩容

  1. 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程
  2. 哈希表的 LoadFactory > 5

# Dict 的收缩

Dict 在 1 每次删除元素时，也会对负载因子做检查，当 LoadFactor < 0.1 时，会做哈希表的收缩

# Dict 的 rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的 size 和 sizemask 变化 1，而 key 的查询于 sizemask 有关，因此必须对哈希表中的每一个 key 重新计算索引，插入新的哈希表，这个过程称为 rehash

  1. 计算新的 hash 表的 realeSize，值取决于当前做的是扩容还是收缩
    1. 如果是扩容，则新 size 为第一个大于等于 dict.ht [0].used + 1 的2n2^n
    2. 如果是收缩，则新 size 为第一个大于等于 dict.ht [0].used 的2n2^n（不得小于 4）
  2. 按照新的 realeSize 申请内存空间，创建 dictht，并赋值给 dict.ht[1]
  3. 设置 dict.rehashidx = 0，标示开始 rehash
  4. 每次执行新增、查询、修改、删除操作时，都检查一下 dict.rehashidx 是否大于 - 1，如果是则将 dict.ht[0].table[rehashidx] 的 entry 链表 rehash 到 dict.ht [1]，并且将 rehashidx++，直至 dict.ht[0] 的所有数据都 rehash 到 dict.ht[1]
  5. 将 dict.ht[1] 赋值给 dict.ht[0]，给 dict.ht [1] 初始化为空哈希表，释放原来的 dict.ht [0] 的内存
  6. 将 rehashidx 赋值为 - 1，代表 rehash 结束
  7. 在 rehash 过程中，新增操作，则直接写入 ht [1]，查询、修改和删除会在 dict.ht[0] 和 dict.ht [1] 依次查找并执行，这样可以确保 ht [0] 的数据只增不减，随着 rehash 最终为空

# ZipList

# 介绍

ZipList 是一种特殊的双端链表，由于一些特殊性编码的连续内存块组成，可以 1 任意一端进行压入 / 弹出操作，并且该操作的时间复杂度为 O (1)

# ZipListEntry

ZipList 中 Entry 并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用 16 个字节，浪费内存

image-20230410204826925

  1. previous_entry_length：前一个字节的长度，占一个或五个字节
  2. encoding：编码属性，记录 content 的数据类型（字符串还是整数）以及长度，占用 1 个、2 个或 5 个字节
  3. contents：负责保存节点的数据，可以是字符串或整数

# ZipList 的连锁更新问题

ZipList 在特殊情况下产生的连续多次空间扩展操纵称之为连锁更新（Cascade Update），新增、删除都可能导致连锁更新问题

# QuickList

# 介绍

QuickList，本质是一个双端链表，只不过链表中的每个节点都是一个 ZipList

image-20230410211025153

# 内存结构图

image-20230410211633910

# ShipList

# 介绍

SkipList（跳表）首先是链表，与传统链表有如下差异

  1. 元素按照升序排列存储
  2. 节点可能包含多个指针，指针跨度不同

image-20230410212515000

# RedisObject

# 介绍

Redis 中任意数据类型的键和值都会被封装成一个 RedisObject，也叫做 Redis 对象

image-20230410212954549

# 五种数据类型

# String

  1. String 基本编码方式是 RAW，基于简单动态字符串（SDS）实现，存储上限为 512Mb
  2. 如果存储的 SDS 长度小于 44 字节，则会采用 EMBSTR 编码，此时 object head 与 SDS 是一段连续空间，申请内存时只需要调用一次内存分配函数，效率更高
  3. 如果存储的字符串是整数值，，并且大小在 LONG_MAX 范围内，则会采用 INT 编码：直接将数据保存在 RedisObject 的 ptr 指针位置，不再需要 SDS 了

image-20230411154344621

# List

  1. Redis 的 List 结构类似于一个双端链表，可以从首、尾操作列表中的元素
  2. 在 3.2 版本之前，Redis 采用 ZipList 和 LinkedList 来实现 List，当元素数量小于 512 并且元素大小小于 64 字节时采用 ZipList 编码，超过则采用 LinkedList
  3. 在 3.2 版本之后，Redis 统一采用 QuickList 来实现 List

image-20230411154733861

# Set

  1. 为了查询效率和唯一性，set 采用哈希编码（Dict），Dict 中 key 用来存储元素，value 统一为 null
  2. 当存储的所有数据都是整数，并且元素数量不超过 set-max-intset-ertries 时，Set 会采用 IntSet 编码，以节省内存

image-20230411160053905

# ZSet

  1. zset 底层数据结构必须满足键值存储、键必须唯一、可排序
  2. SkipList：可以排序，并且可以同时存储 score 和 ele 值
  3. 哈希表（Dict）：可以键值存储，并且可以根据 key 找 value

image-20230411160944332

当元素数量不多时，哈希和 SkipList 的优势不明显，而且更耗内存，因此 zset 还会采用 ZipList 结构来节省内存，不过要满足以下条件

  1. 元素数量小于 zset_max_ziplist_entries，默认值 128
  2. 每个元素都小于 zset_max_ziplist_value 字节，默认值 64

ZipList 本身没有排序功能，而且没有键值对的概念，因此需要有 zset 通过编码实现

  1. ZipList 是连续内存，因此 score 和 element 是紧挨在一起的两个 entry，element 在前，score 在后
  2. score 越小越接近队首，score 越大越接近队尾，按照 score 值升序排列

image-20230411162014790

# Hash

Hash 底层采用的编码与 Zset 也基本一致，只要把排序相关的 SkipList 去掉即可

  1. Hash 结构默认采用 ZipList 编码，用来节省内存，ZipList 中相邻的两个 entry 分别保存 fidld 和 value
  2. 当数据量较大时，Hash 的结构会转为哈希编码，也就是 Dict，触发条件有两个
    1. ZipList 中元素数量超过了 hash-max-ziplist-entries
    2. ZipList 中的任意 entry 大小超过了 hash-max-ziplist-value

image-20230411163202401

# Redis 网络模型

# 用户空间和内核空间

# 用户空间

只能执行受限的命令，而且不能直接调用系统资源，必须通过内核提供的接口来访问

# 内核空间

可以执行特权命令，调用一切系统资源

image-20230411195129817

# 阻塞 IO

image-20230411195437820

# 非阻塞 IO

image-20230411195728494

# IO 多路复用

# 文件描述符（File Description）

是一个从 0 开始递增的无符号整数，用来关联 Linux 中的一个文件，在 Linux 中，一切皆文件

# IO 多路复用

是利用单个线程来同时监听多个 FD，并在某个 FD 可读、可写时得到通知，从而避免无效的等待，充分利用 CPU 资源

image-20230411201048058

# 三种模式

  1. select 和 poll 只会通知用户进程有 FD 就绪，但不确定具体是哪个 FD，需要用户进程逐个遍历 FD 来确认
  2. epoll 则会在通知用户进程 FD 就绪的同时，把已就绪的 FD 写入用户空间

# IO 多路复用 - select

  1. 需要将整个 fd_set 从用户空间拷贝到内核空间，select 结束还要再次拷贝回用户空间
  2. select 无法得知具体是哪个 fd 就绪，需要遍历整个 fd_set
  3. fd_set 监听的 fd 数量不能超过 1024

# IO 多路复用 - poll

  1. 创建 pollfd 数组，向其中添加关注的 fd 信息，数组大小自定义
  2. 调用 poll 函数，将 pollfd 数组拷贝到内核空间，转链表存储，无上限
  3. 内核遍历 fd，判断是否就绪
  4. 数组就绪或超时后，拷贝 pollfd 数组到用户空间，返回就绪 fd 数量 n
  5. 用户进程判断 n 是否大于 0
  6. 大于 0 则遍历 pollfd 数组，找到就绪的 fd

# IO 多路复用 - epoll

  1. 基于红黑树保存要监听的 FD，理论上无上限，而且增删改查效率都非常高，性能不会随监听的 FD 数量增多而下降
  2. 每个 FD 只需要执行一次 epoll_ctl 添加到红黑树，以后每次 epol_wait 无需传递任何参数，无需重复拷贝 FD 到内核空间

image-20230411205003035

# IO 多路复用 - 事件通知机制

  1. LevelTriggered：简称 LT，当 FD 有数据可读时，会重复通知多次，直至数据处理完成，是 Epoll 的默认模式
  2. EdgeTriggered：简称 ET，当 FD 有数据可读时，只会被通知一次，不管数据是否处理完成

# IO 多路复用 - web 服务流程

image-20230414201455723

# Redis 网络模型

# Redis 单线程

  1. 抛开持久化不谈，Redis 是纯内存操作 1，执行速度非常快，它的性能瓶颈是网络延迟而不是执行速度，因此多线程并不会带来巨大的性能提升
  2. 多线程会导致过多的上下文切换，带来不必要的开销
  3. 引入多线程会面临线程安全问题，必然要引入线程锁这样的安全手段，实现复杂度增高，而且性能也会大打折扣

# Redis 单线程模型

image-20230414205809657

# Redis 通信协议

# RESP 协议

# 介绍

Redis 是一个 CS 结构的软件，通信分为两步

  1. 客户端（client）向服务端（server）发送一条指令
  2. 服务端解析并执行命令，返回响应结果给客户端

# RESP 协议 - 数据类型

  1. 单行字符串：首字节是 ==+，后面戈恩上单行字符串，以 CRLF ("\r\n==") 结尾
  2. 错误（Errors）：首字节是 ==-==，与单行字符串一样，只是字符串是异常信息
  3. 数值：首字节是 ==:==，后面跟上数字格式字符串，以 CRLF 结尾
  4. 多行字符串：首字节是 ==$==，表示二进制安全的字符串
  5. 数组：首字节是 ==*==，后面跟上数组元素个数，再跟上元素，数据元素类型不限

# Redis 内存回收

# 过期策略

# DB 结构

Redis 本身是一个典型的 key-value 内存存储数据库，因此所有的 key，value 都保存在之前学习的 DIct 结构中，不过在其 database 结构体中，有两个 Dict：一个用来记录 key-value，另一个用来记录 key-TTL

image-20230414211346094

# 惰性删除

并不是在 TTL 到期后就立即删除，而是在访问一个 key 的时候，检查该 key 的存活时间，如果已经过期才执行删除

# 周期删除

通过一个定时任务，周期性的抽样部分过期的 key，然后执行删除

  1. Redis 会设置一个定时闹钟 serverCron ()，按照 server.hz 的频率来执行过期 key 清理，模式为 SLOW
  2. Redis 的每个事件循环前会调用 beforeSleep () 函数，执行过期 key 清理，模式为 FAST

# SLOW 模式规则

  1. 执行频率受 server.hz 影响，默认为 10，即每秒执行 10 次，每个执行周期 100ms
  2. 执行清理耗时不超过一次执行周期的 25%
  3. 逐个遍历 db，逐个遍历 db 中的 bucket，抽取 20 个 key 判断是否过期
  4. 如果没达到时间上限（25ms）并且过期 key 比例大于 10%，再进行一次抽样，否则结束

# FAST 模式规则

  1. 执行频率受 beforeSleep () 调用频率影响，但两次 FAST 模式间隔不低于 2ms
  2. 执行清理耗时不超过 1ms
  3. 逐个遍历 db，逐个遍历 db 中的 bucket，抽取 20 个 key 判断是否过期
  4. 如果还没达到时间上限，并且过期 key 比例大于 10%，再进行一次抽样，否则结束

# 淘汰策略

# 介绍

就是当 Redis 内存使用达到设置的阈值时，Redis 主动挑选部分 key 删除以释放更多内存的流程

# 八种淘汰策略

名称 说明
noeviction 不淘汰任何 key，但是内存满时不允许写入新数据，默认就是这种策略
volatile-ttl 对设置了 TTL 的 key，比较 key 的剩余 TTL 值，TTL 越小越先淘汰
allkeys-random 对全体 key，随机进行淘汰，也就是直接从 db->dict 中随机挑选
volatile-random 并设置了 TTL 的 key，随机进行淘汰，也就是从 db->expires 中随机挑选
allkeys-lru 对全体 key，基于 LRU 算法进行淘汰
volatile-lru 对设置了 TTL 的 key，基于 LRU 算法进行淘汰
allkeys-lfu 对全体 key，基于 LFU 算法进行淘汰
volatile-lfu 对设置了 TTL 的 key，基于 LFI 算法进行淘汰
  1. LRU：最少最近使用，用当前时间减去最后一次访问时间，这个值越大则淘汰优先级越高
  2. LFU：最少频率使用，会统计每个 key 的访问频率，值越小淘汰优先级越高

image-20230414214942936

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

Baozi 微信支付

微信支付

Baozi 支付宝

支付宝

Baozi 微信

微信