原理

Redis数据结构

动态字符串

Redis 中保存的 Key 是字符串，value 往往是字符串或者字符串的集合。可见字符串是 Redis 中最常用的一种数据结构不过 Redis 没有直接使用 C 语言中的字符串，因为 C 语言字符串存在很多问题：

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

Redis 构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称 SDS。例如，执行命令：

20240829215556

那么 Redis 将在底层创建两个 SDS，其中一个是包含“name”的 SDS，另一个是包含“虎哥”的 SDS

Redis 是 C 语言实现的，其中 SDS 是一个结构体，源码如下：

20240829215630

例如，一个包含字符串“name”的sds结构如下：

20240829215717

SDS 之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的 SDS：

20240829215729

假如要给 SDS 追加一段字符串“,Amy”，这里首先会申请新内存空间：

如果新字符串小于 1M，则新空间为扩展后字符串长度的两倍+1
如果新字符串大于 1M，则新空间为扩展后字符串长度+1M+1 称为内存预分配

20240829215848

inset

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

20240829220014

其中的 encoding 包含三种模式，表示存储的整数大小不同：

20240829220102

为了方便查找，Redis 会将 intset 中所有的整数按照升序依次保存在 contents 数组中，结构如图：

20240829220256

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

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

20240829220330

当向该其中添加一个数字：50000，这个数字超出了 int16_t 的范围，intset 会自动升级编码方式到合适的大小。以当前案例来说流程如下：

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

20240829220628

源码如下：

20240829220639

20240829220647

总结：

Intset 可以看做是特殊的整数数组，具备一些特点：

Redis 会确保 Intset 中的元素唯一、有序
具备类型升级机制，可以节省内存空间
底层采用二分查找方式来查询

Dict

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

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

20240829220731

当向 Dict 添加键值对时，Redis 首先根据 key 计算出 Hash 值（h），然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置。我们存储 k1=v1，假设 k1 的哈希值 h =1，则 1&3 =1，因此 k1=v1 要存储到数组角标1位置

20240829221418

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

20240829221447

20240829221552

Dict的扩容

Dict 中的 HashTable 就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。Dict 在每次新增键值对时都会检查负载因子（LoadFactor = used/size），满足以下两种情况时会触发哈希表扩容：

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

20240829221618

20240829221644

Dict的rehash

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

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

整个过程可以描述成：

20240829222115

总结：

Dict的结构：

类似 Java 的 HashTable，底层是数组加链表来解决哈希冲突
Dict 包含两个哈希表，ht[0] 平常用，ht[1] 用来 rehash

Dict的伸缩：

当 LoadFactor 大于5或者 LoadFactor 大于1并且没有子进程任务时，Dict 扩容
当 LoadFactor 小于0.1时，Dict 收缩
扩容大小为第一个大于等于used + 1的$2^n$
收缩大小为第一个大于等于 used 的$2^n$
Dict 采用渐进式 rehash，每次访问 Dict 时执行一次 rehash
rehash 时 ht[0] 只减不增，新增操作只在 ht[1] 执行，其它操作在两个哈希表

ZipList

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

20240829225910

20240829225922

属性	类型	长度	用途
zlbytes	uint32_t	4 字节	记录整个压缩列表占用的内存字节数
zltail	uint32_t	4 字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址。
zllen	uint16_t	2 字节	记录了压缩列表包含的节点数量。最大值为UINT16_MAX （65534），如果超过这个值，此处会记录为65535，但节点的真实数量需要遍历整个压缩列表才能计算得出。
entry	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend	uint8_t	1 字节	特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

ZipListEntry

ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：

20240829225939

previous_entry_length：前一节点的长度，占1个或5个字节。
- 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
- 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为 0xfe，后四个字节才是真实长度数据
encoding：编码属性，记录 content 的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
contents：负责保存节点的数据，可以是字符串或整数

ZipList 中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值0x1234，采用小端字节序后实际存储值为：0x3412

Encoding编码

ZipListEntry 中的 encoding 编码分为字符串和整数两种：字符串：如果 encoding 是以“00”、“01”或者“10”开头，则证明 content 是字符串

编码	编码长度	字符串大小
\|00pppppp\|	1 bytes	<= 63 bytes
\|01pppppp\|qqqqqqqq\|	2 bytes	<= 16383 bytes
\|10000000\|qqqqqqqq\|rrrrrrrr\|ssssssss\|tttttttt\|	5 bytes	<= 4294967295 bytes

例如，要保存字符串：“ab”和 “bc”

20240829230051

ZipListEntry 中的 encoding 编码分为字符串和整数两种：整数：如果 encoding 是以“11”开始，则证明 content 是整数，且 encoding 固定只占用1个字节

编码	编码长度	整数类型
11000000	1	int16_t（2 bytes）
11010000	1	int32_t（4 bytes）
11100000	1	int64_t（8 bytes）
11110000	1	24位有符整数(3 bytes)
11111110	1	8位有符整数(1 bytes)
1111xxxx	1	直接在xxxx位置保存数值，范围从0001~1101，减1后结果为实际值

20240829230429

20240829230438

连续更新问题

ZipList 的每个 Entry 都包含 previous_entry_length 来记录上一个节点的大小，长度是1个或5个字节：如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

现在，假设有 N个连续的、长度为250~253字节之间的 entry，因此 entry 的 previous_entry_length 属性用1个字节即可表示，如图所示：

20240829230451

ZipList 这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生

总结

ZipList特性：

压缩列表的可以看做一种连续内存空间的"双向链表"
列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
如果列表数据过多，导致链表过长，可能影响查询性能
增或删较大数据时有可能发生连续更新问题

QuickList

问题1：ZipList 虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。怎么办？

答：为了缓解这个问题，我们必须限制 ZipList 的长度和entry大小。

问题2：但是我们要存储大量数据，超出了 ZipList 最佳的上限该怎么办？

答：我们可以创建多个 ZipList 来分片存储数据。

问题3：数据拆分后比较分散，不方便管理和查找，这多个ZipList如何建立联系？

答：Redis 在3.2版本引入了新的数据结构 QuickList，它是一个双端链表，只不过链表中的每个节点都是一个 ZipList

20240829230519

为了避免 QuickList 中的每个 ZipList 中 entry 过多，Redis 提供了一个配置项：list-max-ziplist-size 来限制

如果值为正，则代表 ZipList 的允许的 entry 个数的最大值

如果值为负，则代表 ZipList 的最大内存大小，分5种情况：

-1：每个 ZipList 的内存占用不能超过4kb
-2：每个 ZipList 的内存占用不能超过8kb
-3：每个 ZipList 的内存占用不能超过16kb
-4：每个 ZipList 的内存占用不能超过32kb
-5：每个 ZipList 的内存占用不能超过64kb

其默认值为 -2：

20240829230534

以下是QuickList的和QuickListNode的结构源码：

20240829230543

用一段流程图来描述当前的这个结构

20240829230550

总结

QuickList 的特点：

是一个节点为 ZipList 的双端链表
节点采用 ZipList，解决了传统链表的内存占用问题
控制了 ZipList 大小，解决连续内存空间申请效率问题
中间节点可以压缩，进一步节省了内存

SkipList

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：

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

20240829230602

源码：

20240829230613

20240829230622

总结

SkipList 的特点：

跳跃表是一个双向链表，每个节点都包含 score 和 ele 值
节点按照 score 值排序，score 值一样则按照 ele 字典排序
每个节点都可以包含多层指针，层数是1到32之间的随机数
不同层指针到下一个节点的跨度不同，层级越高，跨度越大
增删改查效率与红黑树基本一致，实现却更简单

RedisObject

Redis中的任意数据类型的键和值都会被封装为一个 RedisObject，也叫做 Redis 对象，源码如下：

1、什么是 RedisObject：从 Redis 的使用者的角度来看，⼀个 Redis 节点包含多个 database（非 cluster 模式下默认是16个，cluster 模式下只能是1个），而一个 database 维护了从 key space 到 object space 的映射关系。这个映射关系的 key 是 string 类型，⽽ value 可以是多种数据类型，比如：

string, list, hash、set、sorted set 等。我们可以看到，key 的类型固定是 string，而 value 可能的类型是多个。⽽从 Redis 内部实现的⾓度来看，database 内的这个映射关系是用⼀个 dict 来维护的。dict 的 key 固定用⼀种数据结构来表达就够了，这就是动态字符串 sds。而 value 则比较复杂，为了在同⼀个 dict 内能够存储不同类型的 value，这就需要⼀个通⽤的数据结构，这个通用的数据结构就是 robj，全名是 redisObject

20240829230640

Redis 的编码方式

Redis 中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型：

编号	编码方式	说明
0	OBJ_ENCODING_RAW	raw编码动态字符串
1	OBJ_ENCODING_INT	long类型的整数的字符串
2	OBJ_ENCODING_HT	hash表（字典dict）
3	OBJ_ENCODING_ZIPMAP	已废弃
4	OBJ_ENCODING_LINKEDLIST	双端链表
5	OBJ_ENCODING_ZIPLIST	压缩列表
6	OBJ_ENCODING_INTSET	整数集合
7	OBJ_ENCODING_SKIPLIST	跳表
8	OBJ_ENCODING_EMBSTR	embstr的动态字符串
9	OBJ_ENCODING_QUICKLIST	快速列表
10	OBJ_ENCODING_STREAM	Stream流

五种数据结构

Redis 中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：

数据类型	编码方式
OBJ_STRING	int、embstr、raw
OBJ_LIST	LinkedList和ZipList(3.2以前)、QuickList（3.2以后）
OBJ_SET	intset、HT
OBJ_ZSET	ZipList、HT、SkipList
OBJ_HASH	ZipList、HT

String

String 是 Redis 中最常见的数据存储类型：

其基本编码方式是 RAW，基于简单动态字符串（SDS）实现，存储上限为512mb

如果存储的 SDS 长度小于44字节，则会采用 EMBSTR 编码，此时 object head 与 SDS 是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高

底层实现⽅式：动态字符串 sds 或者 long

String 的内部存储结构⼀般是 sds（Simple Dynamic String，可以动态扩展内存），但是如果⼀个 String 类型的 value 的值是数字，那么 Redis 内部会把它转成 long 类型来存储，从⽽减少内存的使用

20240829230702

如果存储的字符串是整数值，并且大小在 LONG_MAX 范围内，则会采用 INT 编码：直接将数据保存在 RedisObject 的 ptr 指针位置（刚好8字节），不再需要 SDS 了

20240829230715

20240829230725

20240829230733

确切地说，String 在 Redis 中是⽤⼀个 robj 来表示的

用来表示String的robj可能编码成3种内部表⽰：OBJ_ENCODING_RAW，OBJ_ENCODING_EMBSTR，OBJ_ENCODING_INT

其中前两种编码使⽤的是 sds 来存储，最后⼀种OBJ_ENCODING_INT编码直接把 string 存成了 long 型

在对 string 进行 incr, decr 等操作的时候:

如果它内部是OBJ_ENCODING_INT编码，那么可以直接行加减操作
如果它内部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR编码，那么 Redis 会先试图把 sds 存储的字符串转成 long 型，如果能转成功，再进行加减操作

对⼀个内部表示成 long 型的 string 执行 append, setbit, getrange 这些命令，针对的仍然是 string 的值（即⼗进制表示的字符串），而不是针对内部表⽰的long型进⾏操作

比如字符串”32”，如果按照字符数组来解释，它包含两个字符，它们的 ASCII 码分别是0x33和0x32

当执行命令setbit key 7 0的时候，相当于把字符0x33变成了0x32，这样字符串的值就变成了”22”

⽽如果将字符串”32”按照内部的64位 long 型来解释，那么它是0x0000000000000020，在这个基础上执⾏setbit位操作，结果就完全不对了因此，在这些命令的实现中，会把 long 型先转成字符串再进行相应的操作

List

Redis 的 List 类型可以从首、尾操作列表中的元素：

20240829230809

哪一个数据结构能满足上述特征？

LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多
ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低
QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高

Redis 的 List 结构类似一个双端链表，可以从首、尾操作列表中的元素：

在3.2版本之前，Redis 采用 ZipList 和 LinkedList 来实现 List，当元素数量小于512并且元素大小小于64字节时采用 ZipList 编码，超过则采用 LinkedList 编码

在3.2版本之后，Redis 统一采用 QuickList 来实现 List：

20240829230826

Set结构

Set 是 Redis 中的单列集合，满足下列特点：

不保证有序性
保证元素唯一
求交集、并集、差集

20240829230836

可以看出，Set 对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？HashTable，也就是 Redis 中的 Dict，不过 Dict 是双列集合（可以存键、值对）

Set 是 Redis 中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高

为了查询效率和唯一性，set 采用 HT 编码（Dict）。Dict 中的 key 用来存储元素，value 统一为 null

当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用IntSet编码，以节省内存

20240829230854

结构如下：

20240829230909

ZSet

ZSet 也就是 SortedSet，其中每一个元素都需要指定一个 score 值和 member 值：

可以根据 score 值排序后
member 必须唯一
可以根据 member 查询分数

20240829230920

因此，zset 底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。之前学习的哪种编码结构可以满足？

SkipList：可以排序，并且可以同时存储 score 和 ele 值（member）
HT（Dict）：可以键值存储，并且可以根据 key 找 value

20240829230930

20240829230937

当元素数量不多时，HT 和 SkipList 的优势不明显，而且更耗内存。因此 zset 还会采用 ZipList 结构来节省内存，不过需要同时满足两个条件：

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

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

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

20240829230951

20240829230957

Hash

Hash 结构与 Redis 中的 Zset 非常类似：

都是键值存储
都需求根据键获取值
键必须唯一

区别如下：

zset 的键是 member，值是 score；hash 的键和值都是任意值
zset 要根据 score 排序；hash 则无需排序

底层实现方式：压缩列表 ziplist 或者字典 dict

当 Hash 中数据项比较少的情况下，Hash 底层才⽤压缩列表 ziplist 进⾏存储数据，随着数据的增加，底层的 ziplist 就可能会转成 dict，具体配置如下：

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

当满足上面两个条件其中之⼀的时候，Redis 就使⽤ dict 字典来实现 hash

Redis 的 hash 之所以这样设计，是因为当 ziplist 变得很⼤的时候，它有如下几个缺点：

每次插⼊或修改引发的 realloc 操作会有更⼤的概率造成内存拷贝，从而降低性能
⼀旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更⼤的⼀块数据
当 ziplist 数据项过多的时候，在它上⾯查找指定的数据项就会性能变得很低，因为 ziplist 上的查找需要进行遍历

总之，ziplist 本来就设计为各个数据项挨在⼀起组成连续的内存空间，这种结构并不擅长做修改操作。⼀旦数据发⽣改动，就会引发内存 realloc，可能导致内存拷贝

hash 结构如下：

20240829231044

zset集合如下：

20240829231055

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

Hash 结构默认采用 ZipList 编码，用以节省内存。 ZipList 中相邻的两个 entry 分别保存 field 和 value

当数据量较大时，Hash 结构会转为 HT 编码，也就是 Dict，触发条件有两个：

ZipList 中的元素数量超过了hash-max-ziplist-entries（默认512）
ZipList 中的任意 entry 大小超过了hash-max-ziplist-value（默认64字节）

20240829231108

Redis网络模型

用户空间和内核态空间

服务器大多都采用Linux系统，这里以Linux为例来讲解:

Ubuntu和Centos 都是Linux的发行版，发行版可以看成对linux包了一层壳，任何Linux发行版，其系统内核都是Linux。我们的应用都需要通过Linux内核与硬件交互

20240829231123

用户的应用，比如redis，mysql等其实是没有办法去执行访问我们操作系统的硬件的，所以我们可以通过发行版的这个壳子去访问内核，再通过内核去访问计算机硬件

20240829231144

计算机硬件包括，如cpu，内存，网卡等等，内核（通过寻址空间）可以操作硬件的，但是内核需要不同设备的驱动，有了这些驱动之后，内核就可以去对计算机硬件去进行内存管理，文件系统的管理，进程的管理等等

20240829231154

想要用户的应用来访问，计算机就必须要通过对外暴露的一些接口，才能访问到，从而简介的实现对内核的操控，但是内核本身上来说也是一个应用，所以他本身也需要一些内存，cpu等设备资源，用户应用本身也在消耗这些资源，如果不加任何限制，用户去操作随意的去操作我们的资源，就有可能导致一些冲突，甚至有可能导致我们的系统出现无法运行的问题，因此我们需要把用户和内核隔离开

进程的寻址空间划分成两部分：内核空间、用户空间

什么是寻址空间呢？我们的应用程序也好，还是内核空间也好，都是没有办法直接去物理内存的，而是通过分配一些虚拟内存映射到物理内存中，我们的内核和应用程序去访问虚拟内存的时候，就需要一个虚拟地址，这个地址是一个无符号的整数，比如一个32位的操作系统，他的带宽就是32，他的虚拟地址就是2的32次方，也就是说他寻址的范围就是0~2的32次方，这片寻址空间对应的就是2的32个字节，就是4GB，这个4GB，会有3个GB分给用户空间，会有1GB给内核系统

20240829231214

在linux中，他们权限分成两个等级，0和3，用户空间只能执行受限的命令（Ring3），而且不能直接调用系统资源，必须通过内核提供的接口来访问内核空间可以执行特权命令（Ring0），调用一切系统资源，所以一般情况下，用户的操作是运行在用户空间，而内核运行的数据是在内核空间的，而有的情况下，一个应用程序需要去调用一些特权资源，去调用一些内核空间的操作，所以此时他俩需要在用户态和内核态之间进行切换

比如：

Linux系统为了提高IO效率，会在用户空间和内核空间都加入缓冲区：

写数据时，要把用户缓冲数据拷贝到内核缓冲区，然后写入设备
读数据时，要从设备读取数据到内核缓冲区，然后拷贝到用户缓冲区针对这个操作：我们的用户在写读数据时，会去向内核态申请，想要读取内核的数据，而内核数据要去等待驱动程序从硬件上读取数据，当从磁盘上加载到数据之后，内核会将数据写入到内核的缓冲区中，然后再将数据拷贝到用户态的buffer中，然后再返回给应用程序，整体而言，速度慢，就是这个原因，为了加速，我们希望read也好，还是wait for data也最好都不要等待，或者时间尽量的短

20240829231251

网络模型

在《UNIX网络编程》一书中，总结归纳了5种IO模型：

阻塞IO（Blocking IO）
非阻塞IO（Nonblocking IO）
IO多路复用（IO Multiplexing）
信号驱动IO（Signal Driven IO）
异步IO（Asynchronous IO）

阻塞IO

应用程序想要去读取数据，他是无法直接去读取磁盘数据的，他需要先到内核里边去等待内核操作硬件拿到数据，这个过程就是1，是需要等待的，等到内核从磁盘上把数据加载出来之后，再把这个数据写给用户的缓存区，这个过程是2，如果是阻塞IO，那么整个过程中，用户从发起读请求开始，一直到读取到数据，都是一个阻塞状态

具体流程如下图：

20240829231307

用户去读取数据时，会去先发起recvform一个命令，去尝试从内核上加载数据，如果内核没有数据，那么用户就会等待，此时内核会去从硬件上读取数据，内核读取数据之后，会把数据拷贝到用户态，并且返回ok，整个过程，都是阻塞等待的，这就是阻塞IO

阶段一：

用户进程尝试读取数据（比如网卡数据）
此时数据尚未到达，内核需要等待数据
此时用户进程也处于阻塞状态

阶段二：

数据到达并拷贝到内核缓冲区，代表已就绪
将内核数据拷贝到用户缓冲区
拷贝过程中，用户进程依然阻塞等待
拷贝完成，用户进程解除阻塞，处理数据

可以看到，阻塞IO模型中，用户进程在两个阶段都是阻塞状态

20240829231320

非阻塞IO

顾名思义，非阻塞IO的recvfrom操作会立即返回结果而不是阻塞用户进程

阶段一：

用户进程尝试读取数据（比如网卡数据）
此时数据尚未到达，内核需要等待数据
返回异常给用户进程
用户进程拿到error后，再次尝试读取
循环往复，直到数据就绪

阶段二：

将内核数据拷贝到用户缓冲区
拷贝过程中，用户进程依然阻塞等待
拷贝完成，用户进程解除阻塞，处理数据
可以看到，非阻塞IO模型中，用户进程在第一个阶段是非阻塞，第二个阶段是阻塞状态。虽然是非阻塞，但性能并没有得到提高。而且忙等机制会导致CPU空转，CPU使用率暴增

20240829231332

IO多路复用

无论是阻塞IO还是非阻塞IO，用户应用在一阶段都需要调用recvfrom来获取数据，差别在于无数据时的处理方案：

如果调用recvfrom时，恰好没有数据，阻塞IO会使CPU阻塞，非阻塞IO使CPU空转，都不能充分发挥CPU的作用
如果调用recvfrom时，恰好有数据，则用户进程可以直接进入第二阶段，读取并处理数据

所以怎么看起来以上两种方式性能都不好

而在单线程情况下，只能依次处理IO事件，如果正在处理的IO事件恰好未就绪（数据不可读或不可写），线程就会被阻塞，所有IO事件都必须等待，性能自然会很差

就比如服务员给顾客点餐，分两步：

顾客思考要吃什么（等待数据就绪）
顾客想好了，开始点餐（读取数据）

要提高效率有几种办法？

方案一：增加更多服务员（多线程）

方案二：不排队，谁想好了吃什么（数据就绪了），服务员就给谁点餐（用户应用就去读取数据）

那么问题来了：用户进程如何知道内核中数据是否就绪呢？

所以接下来就需要详细的来解决多路复用模型是如何知道到底怎么知道内核数据是否就绪的问题了

这个问题的解决依赖于提出的文件描述符（File Descriptor）：简称FD，是一个从0 开始的无符号整数，用来关联Linux中的一个文件。在Linux中，一切皆文件，例如常规文件、视频、硬件设备等，当然也包括网络套接字（Socket）

通过FD，网络模型可以利用一个线程监听多个FD，并在某个FD可读、可写时得到通知，从而避免无效的等待，充分利用CPU资源

阶段一：

用户进程调用select，指定要监听的FD集合
核监听FD对应的多个socket
任意一个或多个socket数据就绪则返回readable
此过程中用户进程阻塞

阶段二：

用户进程找到就绪的socket
依次调用recvfrom读取数据
内核将数据拷贝到用户空间
用户进程处理数据

当用户去读取数据的时候，不再去直接调用recvfrom了，而是调用select的函数，select函数会将需要监听的数据交给内核，由内核去检查这些数据是否就绪了，如果说这个数据就绪了，就会通知应用程序数据就绪，然后来读取数据，再从内核中把数据拷贝给用户态，完成数据处理，如果N多个FD一个都没处理完，此时就进行等待

用IO复用模式，可以确保去读数据的时候，数据是一定存在的，他的效率比原来的阻塞IO和非阻塞IO性能都要高

20240829231429

IO多路复用是利用单个线程来同时监听多个FD，并在某个FD可读、可写时得到通知，从而避免无效的等待，充分利用CPU资源。不过监听FD的方式、通知的方式又有多种实现，常见的有：

select
poll
epoll

其中select和pool相当于是当被监听的数据准备好之后，他会把你监听的FD整个数据都发给你，你需要到整个FD中去找，哪些是处理好了的，需要通过遍历的方式，所以性能也并不是那么好

而epoll，则相当于内核准备好了之后，他会把准备好的数据，直接发给你，咱们就省去了遍历的动作

select模式

select是Linux最早是由的I/O多路复用技术：

简单说，就是把需要处理的数据封装成FD，然后在用户态时创建一个fd的集合（这个集合的大小是要监听的那个FD的最大值+1，但是大小整体是有限制的），这个集合的长度大小是有限制的，同时在这个集合中，标明出来我们要控制哪些数据

比如要监听的数据，是1,2,5三个数据，此时会执行select函数，然后将整个fd发给内核态，内核态会去遍历用户态传递过来的数据，如果发现这里边都数据都没有就绪，就休眠，直到有数据准备好时，就会被唤醒，唤醒之后，再次遍历一遍，看看谁准备好了，然后再将处理掉没有准备好的数据，最后再将这个FD集合写回到用户态中去，此时用户态就知道了，奥，有人准备好了，但是对于用户态而言，并不知道谁处理好了，所以用户态也需要去进行遍历，然后找到对应准备好数据的节点，再去发起读请求，我们会发现，这种模式下他虽然比阻塞IO和非阻塞IO好，但是依然有些麻烦的事情，比如说频繁的传递fd集合，频繁的去遍历FD等问题

20240829231450

poll模式

poll模式对select模式做了简单改进，但性能提升不明显，部分关键代码如下：

IO流程：

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

与select对比：

select模式中的fd_set大小固定为1024，而pollfd在内核中采用链表，理论上无上限
监听FD越多，每次遍历消耗时间也越久，性能反而会下降

20240829231505

epoll函数

epoll模式是对select和poll的改进，它提供了三个函数：

eventpoll的函数，他内部包含两个东西
- 红黑树-> 记录的事要监听的FD
- 链表->一个链表，记录的是就绪的FD
epoll_ctl函数，将要监听的数据添加到红黑树上去，并且给每个fd设置一个监听函数，这个函数会在fd数据就绪时触发，就是准备好了，现在就把fd把数据添加到list_head中去
epoll_wait函数，调用epoll_wait函数就去等待，在用户态创建一个空的events数组，当就绪之后，我们的回调函数会把数据添加到list_head中去，当调用这个函数的时候，会去检查list_head，当然这个过程需要参考配置的等待时间，可以等一定时间，也可以一直等，如果在此过程中，检查到了list_head中有数据会将数据添加到链表中，此时将数据放入到events数组中，并且返回对应的操作的数量，用户态的此时收到响应后，从events中拿到对应准备好的数据的节点，再去调用方法去拿数据

总结

select模式存在的三个问题：

能监听的FD最大不超过1024
每次select都需要把所有要监听的FD都拷贝到内核空间
每次都要遍历所有FD来判断就绪状态

poll模式的问题：

poll利用链表解决了select中监听FD上限的问题，但依然要遍历所有FD，如果监听较多，性能会下降

epoll模式中如何解决这些问题的？

基于epoll实例中的红黑树保存要监听的FD，理论上无上限，而且增删改查效率都非常高
每个FD只需要执行一次epoll_ctl添加到红黑树，以后每次epol_wait无需传递任何参数，无需重复拷贝FD到内核空间
利用ep_poll_callback机制来监听FD状态，无需遍历所有FD，因此性能不会随监听的FD数量增多而下降

epoll中的ET和LT

当FD有数据可读时，我们调用epoll_wait（或者select、poll）可以得到通知。但是事件通知的模式有两种：

LevelTriggered：简称LT，也叫做水平触发。只要某个FD中有数据可读，每次调用epoll_wait都会得到通知。
EdgeTriggered：简称ET，也叫做边沿触发。只有在某个FD有状态变化时，调用epoll_wait才会被通知。

举个栗子：

假设一个客户端socket对应的FD已经注册到了epoll实例中
客户端socket发送了2kb的数据
服务端调用epoll_wait，得到通知说FD就绪
服务端从FD读取了1kb数据回到步骤3（再次调用epoll_wait，形成循环）

总结

如果采用LT模式，因为FD中仍有1kb数据，则第⑤步依然会返回结果，并且得到通知如果我们采用ET模式，因为第③步已经消费了FD可读事件，第⑤步FD状态没有变化，因此epoll_wait不会返回，数据无法读取，客户端响应超时

基于epoll的服务器端流程

服务器启动以后，服务端会去调用epoll_create，创建一个epoll实例，epoll实例中包含两个数据

红黑树（为空）：rb_root 用来去记录需要被监听的FD
链表（为空）：list_head，用来存放已经就绪的FD
创建好了之后，会去调用epoll_ctl函数，此函数会会将需要监听的数据添加到rb_root中去，并且对当前这些存在于红黑树的节点设置回调函数,当这些被监听的数据一旦准备完成，就会被调用，而调用的结果就是将红黑树的fd添加到list_head中去(但是此时并没有完成)
当第二步完成后，就会调用epoll_wait函数，这个函数会去校验是否有数据准备完毕（因为数据一旦准备就绪，就会被回调函数添加到list_head中），在等待了一段时间后(可以进行配置)，如果等够了超时时间，则返回没有数据，如果有，则进一步判断当前是什么事件，如果是建立连接时间，则调用accept() 接受客户端socket，拿到建立连接的socket，然后建立起来连接，如果是其他事件，则把数据进行写出

20240829231626

信号驱动

信号驱动IO是与内核建立SIGIO的信号关联并设置回调，当内核有FD就绪时，会发出SIGIO信号通知用户，期间用户应用可以执行其它业务，无需阻塞等待

阶段一：

用户进程调用sigaction，注册信号处理函数
内核返回成功，开始监听FD
用户进程不阻塞等待，可以执行其它业务
当内核数据就绪后，回调用户进程的SIGIO处理函数

阶段二：

收到SIGIO回调信号
调用recvfrom，读取
内核将数据拷贝到用户空间
用户进程处理数据

20240829231642

当有大量IO操作时，信号较多，SIGIO处理函数不能及时处理可能导致信号队列溢出，而且内核空间与用户空间的频繁信号交互性能也较低

异步IO

这种方式，不仅仅是用户态在试图读取数据后，不阻塞，而且当内核的数据准备完成后，也不会阻塞

他会由内核将所有数据处理完成后，由内核将数据写入到用户态中，然后才算完成，所以性能极高，不会有任何阻塞，全部都由内核完成，可以看到，异步IO模型中，用户进程在两个阶段都是非阻塞状态

20240829231655

对比

20240829231704

Redis是单线程的吗？为什么使用单线程

Redis到底是单线程还是多线程？

如果仅仅聊Redis的核心业务部分（命令处理），答案是单线程
如果是聊整个Redis，那么答案就是多线程

在Redis版本迭代过程中，在两个重要的时间节点上引入了多线程的支持：

Redis v4.0：引入多线程异步处理一些耗时较旧的任务，例如异步删除命令unlink
Redis v6.0：在核心网络模型中引入多线程，进一步提高对于多核CPU的利用率

因此，对于Redis的核心网络模型，在Redis 6.0之前确实都是单线程。是利用epoll（Linux系统）这样的IO多路复用技术在事件循环中不断处理客户端情况

为什么Redis要选择单线程？

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

Redis的单线程模型

Redis单线程和多线程网络模型变更

20240829231721

当我们的客户端想要去连接我们服务器，会去先到IO多路复用模型去进行排队，会有一个连接应答处理器，他会去接受读请求，然后又把读请求注册到具体模型中去，此时这些建立起来的连接，如果是客户端请求处理器去进行执行命令时，他会去把数据读取出来，然后把数据放入到client中， clinet去解析当前的命令转化为redis认识的命令，接下来就开始处理这些命令，从redis中的command中找到这些命令，然后就真正的去操作对应的数据了，当数据操作完成后，会去找到命令回复处理器，再由他将数据写出

Redis通信协议-RESP协议

Redis是一个CS架构的软件，通信一般分两步（不包括pipeline和PubSub）：

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

因此客户端发送命令的格式、服务端响应结果的格式必须有一个规范，这个规范就是通信协议

而在Redis中采用的是RESP（Redis Serialization Protocol）协议：

Redis 1.2版本引入了RESP协议
Redis 2.0版本中成为与Redis服务端通信的标准，称为RESP2
Redis 6.0版本中，从RESP2升级到了RESP3协议，增加了更多数据类型并且支持6.0的新特性--客户端缓存

但目前，默认使用的依然是RESP2协议，也是我们要学习的协议版本（以下简称RESP）

在RESP中，通过首字节的字符来区分不同数据类型，常用的数据类型包括5种：

单行字符串：首字节是 ‘+’ ，后面跟上单行字符串，以CRLF（ "\r\n" ）结尾。例如返回"OK"： "+OK\r\n"
错误（Errors）：首字节是 ‘-’ ，与单行字符串格式一样，只是字符串是异常信息，例如："-Error message\r\n"
数值：首字节是 ‘:’ ，后面跟上数字格式的字符串，以CRLF结尾。例如：":10\r\n"
多行字符串：首字节是 ‘$’ ，表示二进制安全的字符串，最大支持512MB：
1. 如果大小为0，则代表空字符串："$0\r\n\r\n"
2. 如果大小为-1，则代表不存在："$-1\r\n"
数组：首字节是 ‘*’，后面跟上数组元素个数，再跟上元素，元素数据类型不限:

基于Socket自定义Redis的客户端

Redis支持TCP通信，因此我们可以使用Socket来模拟客户端，与Redis服务端建立连接：

public class Main {

    static Socket s;
    static PrintWriter writer;
    static BufferedReader reader;

    public static void main(String[] args) {
        try {
            // 1.建立连接
            String host = "192.168.150.101";
            int port = 6379;
            s = new Socket(host, port);
            // 2.获取输出流、输入流
            writer = new PrintWriter(new OutputStreamWriter(s.getOutputStream(), StandardCharsets.UTF_8));
            reader = new BufferedReader(new InputStreamReader(s.getInputStream(), StandardCharsets.UTF_8));

            // 3.发出请求
            // 3.1.获取授权 auth 123321
            sendRequest("auth", "123321");
            Object obj = handleResponse();
            System.out.println("obj = " + obj);

            // 3.2.set name 虎哥
            sendRequest("set", "name", "虎哥");
            // 4.解析响应
            obj = handleResponse();
            System.out.println("obj = " + obj);

            // 3.2.set name 虎哥
            sendRequest("get", "name");
            // 4.解析响应
            obj = handleResponse();
            System.out.println("obj = " + obj);

            // 3.2.set name 虎哥
            sendRequest("mget", "name", "num", "msg");
            // 4.解析响应
            obj = handleResponse();
            System.out.println("obj = " + obj);
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            // 5.释放连接
            try {
                if (reader != null) reader.close();
                if (writer != null) writer.close();
                if (s != null) s.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    private static Object handleResponse() throws IOException {
        // 读取首字节
        int prefix = reader.read();
        // 判断数据类型标示
        switch (prefix) {
            case '+': // 单行字符串，直接读一行
                return reader.readLine();
            case '-': // 异常，也读一行
                throw new RuntimeException(reader.readLine());
            case ':': // 数字
                return Long.parseLong(reader.readLine());
            case '$': // 多行字符串
                // 先读长度
                int len = Integer.parseInt(reader.readLine());
                if (len == -1) {
                    return null;
                }
                if (len == 0) {
                    return "";
                }
                // 再读数据,读len个字节。我们假设没有特殊字符，所以读一行（简化）
                return reader.readLine();
            case '*':
                return readBulkString();
            default:
                throw new RuntimeException("错误的数据格式！");
        }
    }

    private static Object readBulkString() throws IOException {
        // 获取数组大小
        int len = Integer.parseInt(reader.readLine());
        if (len <= 0) {
            return null;
        }
        // 定义集合，接收多个元素
        List<Object> list = new ArrayList<>(len);
        // 遍历，依次读取每个元素
        for (int i = 0; i < len; i++) {
            list.add(handleResponse());
        }
        return list;
    }

    // set name 虎哥
    private static void sendRequest(String ... args) {
        writer.println("*" + args.length);
        for (String arg : args) {
            writer.println("$" + arg.getBytes(StandardCharsets.UTF_8).length);
            writer.println(arg);
        }
        writer.flush();
    }
}

Redis内存回收

过期Key处理

Redis之所以性能强，最主要的原因就是基于内存存储。然而单节点的Redis其内存大小不宜过大，会影响持久化或主从同步性能可以通过修改配置文件来设置Redis的最大内存：

20240829231919

当内存使用达到上限时，就无法存储更多数据了。为了解决这个问题，Redis提供了一些策略实现内存回收：

内存过期策略

在学习Redis缓存的时候我们说过，可以通过expire命令给Redis的key设置TTL（存活时间）：

20240829231930

可以发现，当key的TTL到期以后，再次访问name返回的是nil，说明这个key已经不存在了，对应的内存也得到释放。从而起到内存回收的目的

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

20240829231946

20240829231956

这里有两个问题需要我们思考：Redis是如何知道一个key是否过期呢？

利用两个Dict分别记录key-value对及key-ttl对

是不是TTL到期就立即删除了呢？

惰性删除

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

20240829232010

周期删除

周期删除：顾明思议是通过一个定时任务，周期性的抽样部分过期的key，然后执行删除。执行周期有两种：Redis服务初始化函数initServer()中设置定时任务，按照server.hz的频率来执行过期key清理，模式为SLOWRedis的每个事件循环前会调用beforeSleep()函数，执行过期key清理，模式为FAST

SLOW模式规则：

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

FAST模式规则（过期key比例小于10%不执行）：

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

总结

RedisKey的TTL记录方式：

在RedisDB中通过一个Dict记录每个Key的TTL时间

过期key的删除策略：

惰性清理：每次查找key时判断是否过期，如果过期则删除
定期清理：定期抽样部分key，判断是否过期，如果过期则删除。定期清理的两种模式：
- SLOW模式执行频率默认为10，每次不超过25ms
- FAST模式执行频率不固定，但两次间隔不低于2ms，每次耗时不超过1ms

内存淘汰策略

内存淘汰：就是当Redis内存使用达到设置的上限时，主动挑选部分key删除以释放更多内存的流程。Redis会在处理客户端命令的方法processCommand()中尝试做内存淘汰：

20240829232136

淘汰策略

Redis支持8种不同策略来选择要删除的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算法进行淘汰比较容易混淆的有两个：
- LRU（Least Recently Used），最少最近使用。用当前时间减去最后一次访问时间，这个值越大则淘汰优先级越高
- LFU（Least Frequently Used），最少频率使用。会统计每个key的访问频率，值越小淘汰优先级越高

Redis 的数据都会被封装为 RedisObject 结构：

20240829232157

LFU的访问次数之所以叫做逻辑访问次数，是因为并不是每次key被访问都计数，而是通过运算：

生成0~1之间的随机数R
计算 (旧次数 * lfu_log_factor + 1)，记录为P
如果 R < P ，则计数器 + 1，且最大不超过255
访问次数会随时间衰减，距离上一次访问时间每隔 lfu_decay_time 分钟，计数器 -1

用一副图来描述当前的这个流程

20240829232204

Redis数据结构​

动态字符串​

inset​

Dict​

ZipList​

连续更新问题​

QuickList​

SkipList​

RedisObject​

String​

List​

Set结构​

ZSet​

Hash​

Redis网络模型​

用户空间和内核态空间​

网络模型​

阻塞IO​

非阻塞IO​

IO多路复用​

select模式​

poll模式​

epoll函数​

epoll中的ET和LT​

基于epoll的服务器端流程​

信号驱动​

异步IO​

对比​

Redis是单线程的吗？为什么使用单线程​

Redis的单线程模型​

Redis通信协议-RESP协议​

基于Socket自定义Redis的客户端​

Redis内存回收​

过期Key处理​

内存淘汰策略​

Redis数据结构

动态字符串

inset

Dict

ZipList

连续更新问题

QuickList

SkipList

RedisObject

String

List

Set结构

ZSet

Hash

Redis网络模型

用户空间和内核态空间

网络模型

阻塞IO

非阻塞IO

IO多路复用

select模式

poll模式

epoll函数

epoll中的ET和LT

基于epoll的服务器端流程

信号驱动

异步IO

对比

Redis是单线程的吗？为什么使用单线程

Redis的单线程模型

Redis通信协议-RESP协议

基于Socket自定义Redis的客户端

Redis内存回收

过期Key处理

内存淘汰策略