Redis原理解析

发表于 分类于 阅读次数：

Redis原理解析

数据结构

动态字符串SDS

SDS简介

Redis中保存的Key是字符串, value往往是字符串或者字符串的集合. 可见字符串是Redis中最常用的一种数据结构

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

  • 获取字符串长度的需要通过运算, 循环加计数器直到找到结尾标识符

  • 非二进制安全, 不可以存在结尾特殊字符 \0

  • 不可修改, 保存在常量中

    image-20220702023422666

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

例如，我们执行命令：

1
2
127.0.0.1:6379> set name ni9ne
OK

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

底层实现

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

image-20220702024023424

Redis提供了不同位的数据结构实现, 可存储 2^5 / 2^8 / 2^16 / 2^32 / 2^64 大小的字符串

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

1
2
3
4
5
 ------------------------------------------------
| len:4 | alloc:4 | flags:1 | n | a | m | e | \0 |
 ------------------------------------------------
\         header            /\      数据         /
 - - - - - - - - - - - - - -  - - - - - - - - -

SDS扩容

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如给上面的SDS数据添加字符串 : ofyou

首先会申请新内存空间：

  • 如果新字符串小于1M，则新空间为 扩展后字符串长度的两倍+1；

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

    避免用户态与内核态频繁切换, 预先分配内存空间

扩容后结构如下: 

1
2
3
4
5
 ------------------------------------------------------------------------------------
| len:9 | alloc:18| flags:1 | n | a | m | e | o | f | y | o | u | \0 | | | | | | | | |
 ------------------------------------------------------------------------------------
\         header            /\                     数据                              /
 - - - - - - - - - - - - - -  - - - - - - - - - - - - - - - - - - - - - - - - - - -

优点:

  • 获取字符串长度的时间复杂度为O(1)

  • 支持动态扩容

  • 减少内存分配次数

  • 二进制安全

IntSet

IntSet简介

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

结构如下：

image-20220702033837718

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

image-20220702033940663

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

image-20220702034513176

1
2
3
4
现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为:
- encoding：4字节
- length：4字节
- contents：2字节 * 3  = 6字节

IntSet升级

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

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

流程如下：

image-193507020329160000030

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

②倒序依次将数组中的元素拷贝到扩容后的正确位置 (避免顺序覆盖原有数据)

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

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

image-20220702035044685

IntSet新增流程

新增动作:

image-20220702142044022

升级动作:

image-20220702142248229

查找当前值角标:

image-20220702142513749

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/* Search for the position of "value". Return 1 when the value was found and
 * sets "pos" to the position of the value within the intset. Return 0 when
 * the value is not present in the intset and sets "pos" to the position
 * where "value" can be inserted. */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    // 初始化二分查找的 min , max , mid
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;	// mid对应的值

    /* 若数组为空则不需要找了, 返回0 */
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* 数组不为空, 判断value是否大于最大值, 小于最小值 */
        if (value > _intsetGet(is,max)) {	// 大于最大值, 插入队尾
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {	// 小于最小值, 插入队首
            if (pos) *pos = 0;
            return 0;
        }
    }
	// 二分查找
    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }
    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}

IntSet特点

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

  • Redis会确保Intset中的元素唯一、有序

  • 具备类型升级机制，可以节省内存空间

  • 底层采用二分查找方式来查询

存储少量数据, 在数据量不多的情况下使用

Dict

Dict简介

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

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

  • 哈希表（DictHashTable）

    image-20220702104442031

  • 哈希节点（DictEntry）

    image-20220702104607302

  • 字典（Dict）

    image-20220702104743512

Dict添加键值对

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

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

image-20220702104943218

再次添加k2=v2 , 使用头插法插入数据

image-20220702105133894

Dict完整结构

image-20220702105304986

type 和 privdata为私有数据, rehashidx 和 pauserehash 供Rehash使用, 实际数据存储于ht[2]

ht[1] 用于存储数据, ht[2] 用于rehash

Dict的扩容

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

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

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

  • 哈希表的 LoadFactor > 5 ；

image-20220702142914108

Dict的收缩

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

image-20220702143228068

image-20220702143331778

image-20220702143501558

Dict的rehash

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

158955482123522445622131

①计算新hash表的size，值取决于当前要做的是扩容还是收缩：

  • 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n

  • 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）

②按照新的size申请内存空间，创建dictht，并赋值给dict.ht[1]

③设置dict.rehashidx = 0，标示开始rehash

④将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1] 

1
2
3
Dict的rehash并不是一次性完成的。
如果Dict中包含数百万的entry，要在一次rehash完成，极有可能导致主线程阻塞。
因此Dict的rehash是分多次、渐进式的完成，因此称为渐进式rehash。

④每次执行新增、查询、修改、删除操作时，都检查一下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]的内存

⑥将rehashidx赋值为-1，代表rehash结束

⑦在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空

总结

Dict的结构：

  • 类似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简介

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

image-20220703085252637

属性 类型 长度 用途
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个字节，浪费内存。而是采用了下面的结构：

image-20220703085748538

  • 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”, 储存结构为:

    image-20220703090501059

  • 整数：如果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位置保存数值, 范围从00011101, 减1后结果为实际值, 即012

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

    image-20220703090900521

ZipList的连锁更新问题

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

  • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值

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

假设存在有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节即可表示，如果在队首添加一个大于等于254字节的元素, 如图所示：

12332455703091933089823211

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

总结

ZipList特性：

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

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

③如果列表数据过多，导致链表过长，可能影响查询性能, 所以长度有限制

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

QuickList

QuickList引入

ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。为了缓解这个问题，我们必须限制ZipList的长度和entry大小。

但是要存储大量数据，超出了ZipList最佳的上限, 可以创建多个ZipList来分片存储数据。

数据拆分后比较分散，不方便管理和查找，这多个ZipList如何建立联系？Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个ZipList。

image-20220703093654762

ZipList节点控制

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

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

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

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

    image-20220703093837954

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

1
2
3
4
5
0：特殊值，代表不压缩
1：标示QuickList的首尾各有1个节点不压缩，中间节点压缩
2：标示QuickList的首尾各有2个节点不压缩，中间节点压缩
其默认值为 0
以此类推

image-20220703093958090

底层实现

image-20220703094248775

image-20220703094428304

QuickList数据结构

image-20220703094456586

SkipList

SkipList简介

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

  • 元素按照升序排列存储

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

对比ZipList和QuickList, 查询中间节点数据性能较好, 不用逐个遍历元素

image-20220703100231514

数据结构

image-20220703100618827

image-20220703100729681

总结

SkipList的特点：

  • 跳跃表是一个双向链表，每个节点都包含score和ele值

  • 节点按照score值排序，score值一样则按照ele字典排序

  • 每个节点都可以包含多层指针，层数是1到32之间的随机数

  • 不同层指针到下一个节点的跨度不同，层级越高，跨度越大

  • 增删改查效率与红黑树基本一致，实现却更简单

RedisObject

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

image-20220703102753661

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。

    image-20220703110216960

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

    image-20220703110236364

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

    image-20220703110258535

image-20220703110548121

使用字符串格式数据时, 按照节省内存的逻辑, 尽量使用优先数字(int编码格式), 其次优先使用小于45个字符的字符串(embstr编码格式), 不推荐使用大字符串保存数据, 可能造成BigKey

List

Redis的List类型可以从首、尾操作列表中的元素, 满足该特征的数据结构有三种:

  • LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多

  • ZipList ：压缩列表，可以从双端访问，连续内存空间, 内存占用低，存储上限低

  • QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高

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

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

image-20220703112919765

image-20220703112936331

内存图:

image-20220703113020320

Set

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

  • 不保证有序性

  • 保证元素唯一 (可以判断元素是否存在)

  • 求交集、并集、差集

可以看出，Set对查询元素的效率要求非常高, 使用HashTable可以满足以上需求, 也就是Redis中的Dict，不过Dict是双列集合（可以存键、值对）

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

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

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

代码实现

创建:

image-20220703133521825

添加元素

image-20220703133825524

image-20220703134722184

内存图

image-20220703140602215

添加新数据变动:

1232344220703134230324430

Zset

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

  • 可以根据score值排序后

  • member必须唯一

  • 可以根据member查询分数

因此，zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。其中编码结构可以满足需求的有:

  • SkipList：可以排序，并且可以同时存储score和ele值（member）

  • HT（Dict）：可以键值存储，并且可以根据key找value

代码实现

创建:

image-20220703141350789

少量元素优化:

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

①元素数量小于zset_max_ziplist_entries，默认值128

②每个元素都小于zset_max_ziplist_value字节，默认值64

image-20220703142327034

添加元素:

image-20220703143032001

排序实现

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

  • ZipList是连续内存，因此score和element是紧挨在一起的两个entry， element在前，score在后

  • score越小越接近队首，score越大越接近队尾，按照score值升序排列

image-20220703143222838

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字节）

image-20220703150630161

代码实现:

image-20220703152600746

网络模型

用户空间和内核空间

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

image-20220704124243506

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

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

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

  • 内核空间可以执行特权命令（Ring0），调用一切系统资源

image-20220704124448883

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

  • 写数据时，要把用户缓冲数据拷贝到内核缓冲区，然后写入设备

  • 读数据时，要从设备读取数据到内核缓冲区，然后拷贝到用户缓冲区

image-20220704124828298

五种IO模型

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

  • 阻塞IO（Blocking IO）

  • 非阻塞IO（Nonblocking IO）

  • IO多路复用（IO Multiplexing）

  • 信号驱动IO（Signal Driven IO）

  • 异步IO（Asynchronous IO）

image-20220704124731196

阻塞IO

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

image-20220704125002627

阶段一：

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

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

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

阶段二：

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

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

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

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

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

非阻塞IO

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

image-20220704125144758

阶段一：

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

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

  • ③返回异常给用户进程

  • ④用户进程拿到error后，再次尝试读取

  • ⑤循环往复，直到数据就绪

阶段二：

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

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

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

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

IO多路复用

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

  • 如果调用recvfrom时，恰好没有数据，阻塞IO会使CPU阻塞，非阻塞IO使CPU空转，都不能充分发挥CPU的作用。

  • 如果调用recvfrom时，恰好有数据，则用户进程可以直接进入第二阶段，读取并处理数据

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

1
2
3
4
5
6
7
8
9
就比如服务员给顾客点餐，分两步：
 ①顾客思考要吃什么（等待数据就绪）
 ②顾客想好了，开始点餐（读取数据）

要提高效率有几种办法？
- 方案一：增加更多服务员（多线程）
- 方案二：不排队，谁想好了吃什么（数据就绪了），服务员就给谁点餐（用户应用就去读取数据）

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

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

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

image-20220704125458059

阶段一：

  • ①用户进程调用select，指定要监听的FD集合

  • ②内核监听FD对应的多个socket

  • ③任意一个或多个socket数据就绪则返回readable

  • ④此过程中用户进程阻塞

阶段二：

  • ①用户进程找到就绪的socket

  • ②依次调用recvfrom读取数据

  • ③内核将数据拷贝到用户空间

  • ④用户进程处理数据

1
2
3
4
5
6
7
8
IO多路复用是利用单个线程来同时监听多个FD，不过监听FD的方式、通知的方式又有多种实现，常见的有：
- select
- poll
- epoll

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

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

image-20220704131319638

53432341123210704130219 00_

select模式存在的问题：

  • 需要将整个fd_set从用户空间拷贝到内核空间，select结束还要再次拷贝回用户空间

  • select无法得知具体是哪个fd就绪，需要遍历整个fd_set

  • fd_set监听的fd数量不能超过1024

IO多路复用-poll

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

image-20220704131935087

IO流程：

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

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

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

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

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

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

与select对比：

  • select模式中的fd_set大小固定为1024，而pollfd在内核中采用链表，理论上无上限

  • 监听FD越多，每次遍历消耗时间也越久，性能反而会下降

IO多路复用-epoll

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

image-20220704132641292

867645456704132748 00_0

1
2
3
4
5
6
7
8
9
10
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数量增多而下降
IO多路复用-事件通知机制

当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不会返回，数据无法读取，客户端响应超时。

结论:

  • LT：事件通知频率较高，会有重复通知，影响性能

  • ET：仅通知一次，效率高。可以基于非阻塞IO循环读取解决数据读取不完整问题

select和poll仅支持LT模式，epoll可以自由选择LT和ET两种模式

IO多路复用-web服务流程

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

image-20220704133537920

信号驱动IO

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

image-20220704133804934

阶段一：

  • ①用户进程调用sigaction，注册信号处理函数

  • ②内核返回成功，开始监听FD

  • ③用户进程不阻塞等待，可以执行其它业务

  • ④当内核数据就绪后，回调用户进程的SIGIO处理函数

阶段二：

  • ①收到SIGIO回调信号

  • ②调用recvfrom，读取

  • ③内核将数据拷贝到用户空间

  • ④用户进程处理数据

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

异步IO

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

image-20220704134003847

阶段一：

  • ①用户进程调用aio_read，创建信号回调函数

  • ②内核等待数据就绪

  • ③用户进程无需阻塞，可以做任何事情

阶段二：

  • ①内核数据就绪

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

  • ③拷贝完成，内核递交信号触发aio_read中的回调函数

  • ④用户进程处理数据

可以看到，异步IO模型中，用户进程在两个阶段都是非阻塞状态。
但在大并发情况下, 内核积存的IO处理可能崩溃, 所以需要应用并发限流, 造成代码复杂度升高

同步和异步判断

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

image-20220704134151079

Redis网络模型

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

  • 如果仅仅是Redis的核心业务部分（命令处理），是单线程

  • 如果是整个Redis，那么就是多线程

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

  • Redis v4.0：引入多线程异步处理一些耗时较旧的任务，例如异步删除命令unlink

  • Redis v6.0：在核心网络模型中引入 多线程，进一步提高对于多核CPU的利用率

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

为什么Redis要选择单线程

  • 抛开持久化不谈，Redis是纯内存操作，执行速度非常快，它的性能瓶颈是网络延迟而不是执行速度，因此多线程并不会带来巨大的性能提升。

  • 多线程会导致过多的上下文切换，带来不必要的开销

  • 引入多线程会面临线程安全问题，必然要引入线程锁这样的安全手段，实现复杂度增高，而且性能也会大打折扣

事件API库 AE

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

image-20220704134802204

Redis单线程网络模型的流程

image-20220704140419658

image-20220704140551856

beforSleep代码

image-20220704140907427

readQueryFromClient代码

image-20220704141124651

Redis多线程应用

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

image-20220704140655294

通信协议

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协议-数据类型

在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“

    image-20220704154034088

  • 数组：首字节是 ‘*’，后面跟上数组元素个数，再跟上元素，元素数据类型不限:

    image-20220704154114414

使用socket模拟Redis-cli

1

内存策略

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

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

1
2
3
4
# 格式：
# maxmemory <bytes>
# 例如：
maxmemory 1gb

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

  • 内存过期策略

  • 内存淘汰策略

过期策略

可以通过expire命令给Redis的key设置TTL（存活时间）：

image-20220704154451906

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

过期策略-DB结构

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

image-20220704154725181

redisDb内存图如下:

image-20220704154902329

即Redis是通过key所在redisDb中expires包含TTL数据确定过期与否

过期策略-过期删除

Redis的过期删除是通过结合使用惰性删除和周期删除完成的

  • 惰性删除

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

    image-20220704155509355

  • 周期删除.

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

    • Redis服务初始化函数initServer()中设置定时任务serverCron，按照server.hz的频率来执行过期key清理，模式为SLOW

      SLOW模式规则：

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

    • Redis的每个事件循环前会调用beforeSleep()函数，执行过期key清理，模式为FAST

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

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

    image-20220704155829670

淘汰策略

内存淘汰

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

image-20220704160141189

八种淘汰策略

image-20220704160346602

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算法进行淘汰

比较容易混淆的有两个：

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

LRU/LFU淘汰原理

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

image-20220704160630664

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

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

image-20220704160955402

淘汰策略流程

image-20220704161044411