Redis从入门到实战 - 原理篇

一、数据结构

1. 动态字符串SDS

我们都知道Redis中保存的key是字符串，value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。

不过Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：

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

// C语言，声明字符串
char* s = "hello"
// 本质是字符数组：{'h', 'e', 'l', 'l', 'o', '\0'}

Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamin String），简称SDS。

例如，我们执行命令：

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

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

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

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

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

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

优点：

• 获取字符串长度的时间复杂度为O(1)
• 支持动态扩容
• 减少内存分配次数
• 二进制安全

2. IntSet

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

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

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

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

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

寻址公式：startPtr + (sizeof(int16) * index)

IntSet升级

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

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

以当前案例来说，流程如下：

①升级编码为INTSET_ENC_INT32，每个整数占4字节，并按照新的编码方式及元素个数扩容数组

②倒序依次将数组中的元素拷贝到扩容后的正确位置

③将待添加的元素放入数组末尾

④最后，将intset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

总结

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

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

3. Dict

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

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

当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置。

假如，我们存储k1 = v1，假设k1的哈希值h = 1，则1 & 3 = 1，因此k1 = v1要存储到数组角标1位置：

现在又来了一个键值对k2 = v2，刚好计算得到的角标也是1，则把新来的键值对放到链表的头部（头插法）

结构：

Dict的扩容

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

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

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

Dict的收缩

Dict除了扩容之外，每次删除元素时，也会对负载因子做检查，当LoadFactor < 0.1时，会做哈希表收缩：

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.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]

⑤将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存

总结

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]执行，其它操作在两个哈希表

4. ZipList

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

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

ZipListEntry

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

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

注意：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”

链表结构：

• 整数：如果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后结果为实际值

例如，一个ZipList中包含两个整数值：“2”和“5”

ZipList结构：

ZipList的连锁更新问题

ZipList的每个Entry都包含previos_entry_length来记录上一个节点的大小，长度是1个或5个字节：

• 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
• 如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

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

插入一个254bytes的节点：

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

总结

ZipList特性：

①压缩列表可以看做一种连续内存空间的“双向链表”

②列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低

③如果列表数据过多，导致链表过长，可能影响查询性能

④增或删较大数据时有可能发生连锁更新问题

5. QuickList

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

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

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

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

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

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

为了避免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：

除了控制ZipList的大小，QuickList还可以对节点的ZipList做压缩。通过配置项 list-compress-depth来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。这个参数是控制首尾不压缩的节点个数：

• 0：特殊值，代表不压缩
• 1：标示QuickList的首尾各有1个节点不压缩，中间节点压缩
• 2：标示QuickList的首尾各有2个节点不压缩，中间节点压缩
• 以此类推

默认值：

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

总结

QuickList的特点：

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

6. SkipList

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

• 元素按照升序排列存储

• 节点可能包含多个指针，指针跨度不同

总结

SkipList的特点：

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

7. RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做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流

8. 五种数据结构

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

8.1 String

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

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

• 如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高；
• 如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8个字节），不再需要SDS了。

示例：

8.2 List

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

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

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

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

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

8.3 Set

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

• 不保证有序性
• 保证元素唯一（可以判断元素是否存在）
• 求交集、并集、差集

可以看出，Set对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足要求？

答：HashTable，也就是Redis中的Dict，不过Dict是双列集合（可以存键、值对）

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

• 为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null；
• 当存储的所有数据都是整数，并且元素数量不超过 set-max-intset-entries（默认是512）时，Set会采用IntSet编码，以节省内存；

8.4 ZSet

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

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

因此，ZSet底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。

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

当元素数量不多时，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值升序排列

ZipList转HT + SkipList：

8.5 Hash

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

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

区别如下：

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

因此，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字节）

二、网络模型

1. 用户空间和内核空间

服务器大多采用Linux系统，这里我们以Linux为例来讲解：

任何Linux发行版，其系统内核都是Linux，我们的应用都需要通过Linux内核与硬件交互。

为了避免用户应用导致冲突甚至内核崩溃，用户应用于内核是分离的：

• 进程的寻址空间会划分为两部分：内核空间、用户空间
• 用户空间只能执行受限的命令（Ring3），而且不能直接调用系统资源，必须通过内核提供的接口来访问
• 内核空间可以执行特权命令（Ring0），调用一切系统资源

2. 阻塞IO

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

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

顾名思义，阻塞IO就是两个阶段都必须阻塞等待：

阶段一：

• 用户进程尝试读取数据（比如网卡数据）

• 此时数据尚未到达，内核需要等待数据

• 此时用户进程也处于阻塞状态

阶段二：

• 数据到达并拷贝到内核缓冲区，代表已就绪

• 将内核数据拷贝到用户缓冲区

• 拷贝过程中，用户进程依然阻塞等待

• 拷贝完成，用户进程解除阻塞，处理数据

3. 非阻塞IO

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

阶段一：

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

阶段二：

• 将内核数据拷贝到用户缓冲区
• 拷贝过程中，用户进程依然阻塞等待
• 拷贝完成，用户进程解除阻塞，处理数据

可以看到，非阻塞IO模型中，用户进程在第一个阶段是非阻塞，第二个阶段是阻塞状态。虽然是非阻塞，但性能并没有得到提高。而且忙等机制会导致CPU空转，CPU使用率暴增。

4. IO多路复用

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

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

比如服务端处理客户端Socket请求时，在单线程情况下，只能依次处理每一个socket，如果正在处理的socket恰好未就绪（数据不可读或不可写），线程就会被阻塞，所有其它客户端socket都必须等待，性能自然会很差。

这就像服务员给顾客点餐，分两步：

①顾客思考要吃什么（等待数据就绪）

②顾客想好了，开始点餐（读取数据）

要提高效率有几种方法？

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

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

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

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

不过监听FD的方式、通知的方式又有多种实现，常见的有：

• select
• poll
• epoll

差异：

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

4.1 IO多路复用 - select

select是Linux中最早的I/O多路复用实现方案：

IO流程：

①初始化fd_set集合

• 使用FD_ZERO清空集合；
• 使用FD_SET将需要监控的FD加入readfds（可读）、writefds（可写）或exceptfds（异常）集合；

②调用select阻塞等待：

• select会阻塞，直到至少一个FD就绪，或者超时（如果设置了timeout）
• 内核会轮询所有被监控的FD，检查它们是否就绪（如socket可读、可写或发生异常）；

③select返回：

• 返回值 > 0：表示就绪的FD数量；
• 返回值 = 0：表示超时，没有FD就绪；
• 返回值 = -1：表示出错（如被信号中断）；

④遍历fd_set检查就绪的FD：

• 使用FD_ISSET检查哪些FD已经就绪；
• 处理就绪的FD（如读取数据、发送数据等）；

⑤循环调用select：

• 由于select会修改fd_set，每次调用前需要重新设置FD集合。

select模式存在的问题：

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

4.2 IO多路复用 - poll

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

IO流程：

①创建pollfd数组，向其中添加关注的fd信息，数组大小自定义

②调用poll函数，将pollfd数组拷贝到内核空间，转链表存储，无上限

③内核遍历fd，判断是否就绪

④数据就绪或超时后，拷贝pollfd数组到用户空间，返回就绪fd数量n

⑤用户进程判断n是否大于0

⑥大于0则遍历pollfd数组，找到就绪的fd

与select对比：

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

4.3 IO多路复用 - epoll

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

IO流程：

①创建epoll实例：

• 内核会创建一个epoll实例，返回对应的句柄epoll_fd；
• 底层数据结构：红黑树（存储待监听的FD）+ 就绪链表（存储就绪的FD）。

②注册/修改/删除 FD事件

• epoll_ctl操作类型：EPOLL_CTL_ADD、EPOLL_CTL_MOD、EPOLL_CTL_DEL
• 事件类型：EPOLLIN（FD可读）、EPOLLOUT（FD可写）、EPOLLET（边缘触发模式，默认是水平触发LT）、EPOLLRDHUP（对端关闭连接 - TCP半关闭）

③等待事件就绪：

• epoll_wait返回就绪的FD数量，并将就绪事件填充到events数组；
• 两种触发模式：
  • 水平触发（LT，默认）：只有FD 可读/可写，就会一直通知。
  • 边缘触发（ET）：仅在FD状态变化时通知一次（必须一次性处理完数据）

④处理就绪事件：

• 遍历events数组，处理所有就绪的FD（如读取数据、发送数据等）。

总结：

1. select模式存在的三个问题：

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

2. poll模式的问题：

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

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

• 基于epoll实例中的红黑树保存要监听的FD，理论上无上限，而且增删改查效率都非常高，性能不会随监听的FD数量增多而下降
• 每个FD只需要执行一次epoll_ctl添加到红黑树，以后每次epoll_wait无需传递任何参数，无需重复拷贝FD到内核空间；
• 内核会将就绪的FD直接拷贝到用户空间的指定位置，用户进程无需遍历所有FD就能知道就绪的FD是谁。

特性	select	poll	epoll (Linux)
FD 数量限制	1024（固定）	无限制（基于链表）	无限制（基于红黑树）
效率	O(n) 遍历所有 FD	O(n) 遍历所有 FD	O(1) 仅返回就绪 FD
事件通知	仅返回就绪 FD	仅返回就绪 FD	可返回具体事件类型
内存拷贝	每次调用都要拷贝 FD 集合	每次调用都要拷贝 FD 数组	使用 mmap 减少拷贝
适用场景	跨平台、少量连接	比 select 稍好	高并发（如 10万+ 连接）

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

当FD有数据可读时，我们调用epoll_wait就可以得到通知。但是事件通知的模式有两种：

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

举个例子：

①假设一个客户端socket对应的FD已经注册到了epoll实例中

②客户端socket发送了2kb的数据

③服务端调用epoll_wait，得到通知说FD就绪

④服务端从FD读取了1kb数据

⑤回到步骤3（再次调用epoll_wait，形成循环）

结论

• 如果我们采用LT模式，因为FD中仍有1kb数据，则第⑤步依然会返回结果，并且得到通知；
• 如果我们采用ET模式，因为第③步已经消费了FD可读事件，第⑤步FD状态没有变化，因此epoll_wait不会返回，数据无法读取客户端响应超时。
• ET模式避免了LT模式可能出现的惊群现象
• ET模式最好结合非阻塞IO读取FD数据，相比LT会复杂一些

4.3.2 IO多路复用 - 基于epoll的服务器端流程

基于epoll模式的web服务器的基本流程如图：

我们来梳理一下这张图：

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

• 红黑树（为空）：rb_root用来记录需要被监听的FD
• 链表（为空）：list_head，用来存放已经就绪的FD

②创建好了之后，会去调用epoll_ctl函数，此函数会将需要监听的数据添加到rb_root中去，并且对当前这些存在于红黑树的节点设置回调函数，当这些被监听的数据一旦准备完成，就会被调用，而调用的结果就是将红黑树的fd添加到list_head中去（但是此时并没有完成）；

③当第二步完成以后，就会调用epoll_wait函数，这个函数会去校验是否有数据准备完毕（因为数据一旦准备就绪，就会被回调函数添加到list_head中），在等待了一段时间后（可以进行配置），如果等够了超时时间，则返回没有数据；如果有，则进一步判断当前是什么事件，如果是建立连接事件，则调用accept()接受客户端socket，拿到建立连接的socket，然后建立起来连接，如果是其它事件，则把数据进行写出。

5. 信号驱动IO

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

阶段一：

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

阶段二：

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

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

6. 异步IO

异步IO的整个过程都是非阻塞的，用户进程调用完异步API后就可以去做其它事情，内核等待数据就绪并拷贝到用户空间后才会递交信号，通知用户进程。

同步和异步

IO操作是同步还是异步，关键看数据在内核空间与用户空间的拷贝过程（数据读写的IO操作），也就是阶段二是同步还是异步：

7. Redis网络模型

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

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

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

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

2. 为什么Redis要选择单线程？

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

Redis通过IO多路复用来提高网络性能，并且支持各种不同的多路复用实现，并且将这些实现进行封装，提供了统一的高性能事件库API库 AE：

来看下Redis单线程网络模型的整个流程：

Redis 6.0版本中引入了多线程，目的是为了提高IO读写效率。因此在解析客户端命令、写响应结果时采用了多线程。核心的命令执行、IO多路复用模块依然是由主线程执行。

三、通信协议

1. RESP协议

Redis是一个C/S架构的软件，通信一般分两步（不包括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：
  • 如果大小为0，则代表空字符串："$0\r\n\r\n"
  • 如果大小为-1，则代表不存在："$-1\r\n"
  • 
• 数组：首字节是'*'，后面跟上数组元素个数，再跟上元素，元素数据类型不限：
  • 

2. 模拟Redis客户端

package com.company;

import java.io.*;
import java.net.Socket;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;

public class Main {

    static Socket s;
    static PrintWriter writer;  // 按行输出
    static BufferedReader reader;

    public static void main(String[] args) {
        try {
            // 1.建立连接
            String host = "192.168.200.130";
            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 leadnews
            sendRequest("auth", "leadnews");
            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.get 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();
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (writer != null) writer.close();
            try {
                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内存回收

Redis之所以性能强，最主要的原因就是基于内存存储。然而单结点的Redis其内存大小不宜过大，会影响持久化或主从同步性能。

我们可以通过修改配置文件来设置Redis的最大内存：

当内存使用达到上限时，就无法存储更多数据了。

1. 过期策略

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

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

过期策略 - DB结构

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

过期策略 - 惰性删除

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

过期策略 - 周期删除

周期删除：顾名思义是通过一个定时任务，周期性的抽样部分过期的key，然后执行删除。执行周期有两种：

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

SLOW模式规则：

①执行频率受server.hz影响，默认为10，即每秒执行10次，每个执行周期100ms；

②执行清理耗时不超过一次执行周期的25%；

③逐个遍历db，逐个遍历db中的bucket，抽取20个key判断是否过期；

④如果没达到时间上限（25ms）并且过期key比例大于10%，再进行一次抽样，否则结束。

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

①执行频率受beforeSleep()调用频率影响，但两次FAST模式间隔不低于2ms；

②执行清理耗时不超过1ms；

③逐个遍历db，逐个遍历db中的bucket，抽取20个key判断是否过期

④如果没达到时间上限（1ms），并且过期key比例大于10%，再进行一次抽样，否则结束

总结：

1. Redis是如何知道一个key是否过期呢？

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

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

• 惰性删除：每次查找key时判断是否过期，如果过期则删除
• 周期删除：定期抽样部分key，判断是否过期，如果过期则删除

3. 定期清理的两种模式：

• SLOW模式执行频道默认为10，每次不超过25ms；
• FAST模式执行频率不固定，但两次间隔不低于2ms，每次耗时不超过1ms

2. 淘汰策略

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

Redis支持8种不同策略来选择要删除的key：

• noeviction：不淘汰任何key，但是内存满时不允许写入新数据，默认就是这种策略。
• volatitle-ttl：对设置了TTL的key，比较key的剩余TTL值，TTL越小越先淘汰
• allkeys-random：对全体key，随机进行淘汰。也就是直接从db->dict中随机挑选
• volatitle-random：对设置了TTL的key，随机进行淘汰。也就是从db-expires中随机挑选
• allkeys-lru：对全体key，基于LRU算法进行淘汰
• volatile-lru：对设置了TTL的key，基于LRU算法进行淘汰
• allkeys-lfu：对全体key，基于LFU算法进行淘汰
• volatile-lfu：对设置了TTL的key，基于LFU算法进行淘汰

比较容易混淆的有两个：

• LRU（Least Recently Used）：最少最近使用（最近最久未使用），用当前时间减去最后一次访问时间，这个值越大则淘汰优先级越高；
• LFU：最少频率使用，会统计每个key的访问频率，值越小淘汰优先级越高

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

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

• ①生成0~1之间的随机数R；
• ②计算 1 / (旧次数 * lfu_log_factor + 1)，记录为P，lfu_log_factor默认为10；
• ③如果R < P，则计数器 + 1，且最大不超过255
• ④访问次数会随时间衰减，距离上一次访问时间间隔 lfu_decay_time分钟（默认1），计数器 - 1。

旧访问次数越大，分母越大，P的值越小，R < P的概率越小，计数器累计的概率越低。