Redis数据结构底层、Redis网络模型_redis底层模型

课程链接：Redis 6 入门到精通
Redis入门到实战教程

手写的redis分布式锁

测试
切换xshell用于将命令推送给所有会话

此时我们
set lock haha NX
可以发现三台主机只有一台成功设置，即可认为他成功拿到了锁

转为Java代码

public void testRedisLock() throws InterruptedException {
        Boolean lock = redisTemplate.opsForValue().setIfAbsent("lock", "111");
        if (lock) {
            System.out.println("加锁成功 执行业务");
            redisTemplate.delete("lock");//删除锁
        } else {
            //加锁失败，重试 用自旋的方式
            Thread.sleep(1000);
            testRedisLock();
        }
    }
1
2
3
4
5
6
7
8
9
10
11

问题:
setnx占好了位，业务代码异常或者程序在页面过程中宕机。没有执行删除锁逻辑，这就造成了死锁
解决:设置锁自动过期，即使没有删除，会自动删除

nx-> not exist
改进

 public void testRedisLock() throws InterruptedException {
        Boolean lock = redisTemplate.opsForValue().setIfAbsent("lock", "111",300,TimeUnit.SECONDS);
        if (lock) {
            System.out.println("加锁成功 执行业务");
            redisTemplate.delete("lock");//删除锁
        } else {
            //加锁失败，重试 用自旋的方式
            Thread.sleep(1000);
            testRedisLock();
        }
    }
1
2
3
4
5
6
7
8
9
10
11

问题:
删除锁直接删除???
如果由于业务时间很长，锁自己过期了，我们直接删除，有可能把别人正在持有的锁删除了。
解决：占锁的时候，值指定为uuid，每个人匹配是自己的锁才删除。

public void testRedisLock() throws InterruptedException {
        String uuid = UUID.randomUUID().toString();
        Boolean lock = redisTemplate.opsForValue().setIfAbsent("lock", uuid, 300, TimeUnit.SECONDS);
        if (lock) {
            System.out.println("加锁成功 执行业务");
            String lockVal = redisTemplate.opsForValue().get("lock");
            if (uuid.equals(lockVal)) {
                redisTemplate.delete("lock");//只能删自己的锁
            }
        } else {
            //加锁失败，重试 用自旋的方式
            Thread.sleep(1000);
            testRedisLock();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

但这样获取值对比+对比成功删除仍然不是原子操作
继续看

使用lua脚本

    public void testRedisLock() throws InterruptedException {
        String uuid = UUID.randomUUID().toString();
        Boolean lock = redisTemplate.opsForValue().setIfAbsent("lock", uuid, 300, TimeUnit.SECONDS);
        if (lock) {
            System.out.println("加锁成功 执行业务");
//            String lockVal = redisTemplate.opsForValue().get("lock");
//            if (uuid.equals(lockVal)) {
//                redisTemplate.delete("lock");//只能删自己的锁
//            }
            String script = "if redis.call('get',KEYS[1]) == ARGV[1] then return redis.call('del',KEYS[1]) else return 0 end";
Long redisResult = redisTemplate.execute(new DefaultRedisScript<Long>(script, Long.class),
                        Arrays.asList("lock"), uuid);
        } else {
            //加锁失败，重试 用自旋的方式
            Thread.sleep(1000);
            testRedisLock();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

总而言之就是加锁解锁都保证原子性

public void testRedisLock() throws InterruptedException {
        String uuid = UUID.randomUUID().toString();
        Boolean lock = redisTemplate.opsForValue().setIfAbsent("lock", uuid, 300, TimeUnit.SECONDS);
        if (lock) {
            try {
                System.out.println("加锁成功 执行业务");
            } finally {
                String script = "if redis.call('get',KEYS[1]) == ARGV[1] then return redis.call('del',KEYS[1]) else return 0 end";
Long redisResult = redisTemplate.execute(new DefaultRedisScript<Long>(script, Long.class),
                        Arrays.asList("lock"), uuid);
            }
        } else {
            //加锁失败，重试 用自旋的方式
            Thread.sleep(1000);
            testRedisLock();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

redis分布式锁框架

缓存穿透

当用户访问的数据，既不在缓存中，也不在数据库中，导致请求在访问缓存时，发现缓存缺失，再去访问数据库时，发现数据库中也没有要访问的数据，没办法构建缓存数据，来服务后续的请求。那么当有大量这样的请求到来时，数据库的压力骤增，这就是缓存穿透的问题。

解决方案一：
缓存无效的key，即使他查出来是null，我也给放到缓存里面，下次查给他返回，但这样治标不治本

解决方案二：
布隆过滤器是一个非常神奇的数据结构，通过它我们可以非常方便地判断一个给定数据是否存在于海量数据中。我们需要的就是判断 key 是否合法。

把所有可能存在的请求的值都存放在布隆过滤器中，当用户请求过来，先判断用户发来的请求的值是否存在于布隆过滤器中。不存在的话，直接返回请求参数错误信息给客户端，存在的话才会走下面的流程。

不同的字符串可能哈希出来的位置相同，这种情况我们可以适当增加位数组大小或者调整我们的哈希函数。
综上，我们可以得出：布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。
解决方案三：
当发现Redis命中率急剧下降，需要排查访问对象，设置访问黑名单

缓存击穿

redis某个热点key过期，导致请求直接落在MySQL上
解决方案：

• 预先设置热门数据，加大热门数据key的时长
• 现场监控哪些数据热门，实时调整key的过期时长
• 使用锁：缓存失效时，先判断拿出来的值，而不要直接去load db【互斥锁方案（Redis 中使用 setNX 方法设置一个状态位，表示这是一种锁定状态），保证同一时间只有一个业务线程请求缓存，未能获取互斥锁的请求，要么等待锁释放后重新读取缓存，要么就返回空值或者默认值。】但这样效率很低

缓存雪崩

大面积key失效
解决方案：

• 将缓存失效时间随机打散： 我们可以在原有的失效时间基础上增加一个随机值（比如 1 到 10 分钟）这样每个缓存的过期时间都不重复了，也就降低了缓存集体失效的概率。
• 设置缓存不过期： 我们可以通过后台服务来更新缓存数据，从而避免因为缓存失效造成的缓存雪崩，也可以在一定程度上避免缓存并发问题。
• 构建多级缓存
• 使用锁

redis数据结构底层

String

String 类型的底层的数据结构实现主要是 SDS（简单动态字符串）

SDS 相比于 C 的原生字符串：

• SDS 不仅可以保存文本数据，还可以保存二进制数据。
• SDS 获取字符串长度的时间复杂度是 O(1)。
• Redis 的 SDS API 是安全的，拼接字符串不会造成缓冲区溢出。因为 SDS 在拼接字符串之前会检查 SDS 空间是否满足要求，如果空间不够会自动扩容，所以不会导致缓冲区溢出的问题。【动态扩容】
  

IntSet（整数集合）

整数集合本质上是一块连续内存空间

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中
整数集合依然有一个升级过程，升级的好处是节省内存资源。

如果集合中的元素都是整数且元素个数小于 512 （默认值，set-maxintset-entries配置）个，Redis 会使用整数集合作为
Set 类型的底层数据结构； 如果集合中的元素不满足上面条件，则 Redis 使用哈希表作为 Set 类型的底层数据结构。

List

List可以从首尾操作元素
能满足以上要求的

• LinkedList:普通链表，可以从双端访问，内存占用较高，内存碎片较多
• ZipList:压缩列表，可以从双端访问，内存占用低，存储上限低

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

quicklistNode 结构体里包含了前一个节点和下一个节点指针，这样每个 quicklistNode 形成了一个双向链表。但是链表节点的元素不再是单纯保存元素值，而是保存了一个压缩列表，所以 quicklistNode 结构体里有个指向压缩列表的指针 *zl。

set

set是Redis中的单列集合，满足下列特点:
不保证有序性
保证元素唯一（可以判断元素是否存在)
求交集、并集、差集

那我们会经常去判断元素是否在该set里面存在
对查询效率要求高
那肯定是数组优于列表

这里选用的是HashTable哈希表，也就是Redis里面的Dict字典

Key存放元素，value统一为null
这其实和HashSet HashMap关系挺像的，可能设计理念都是互相借鉴

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

可以看看源码，全是整数走一个逻辑，不全是走另一个逻辑

如果插入元素多了非整数，那就要转类型

ZSET

可以根据score值排序
member必须唯一
可以根据member查询分数
因此需要满足键值存储，键必须唯一，可排序

考虑以下几种备选项
intset可以按序存，但是不能存值
skipList可以排序，也可以同时存score和member
HT可以键值对存放，也可以根据key获得value

• 如果有序集合的元素个数小于 128 个，并且每个元素的值小于 64 字节时，Redis 会使用压缩列表ziplist【自定义出score和member】作为 Zset 类型的底层数据结构；
• 如果有序集合的元素不满足上面的条件，Redis 会使用跳表skiplist作为 Zset 类型的底层数据结构；

ziplist本身没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现:
zipList是连续内存，因此score和element是紧挨在一起的两个entry,element在前，score在后score越小越接近队首，score越大越接近队尾，按照score值升序排列

Hash

Hash结构与Redis中的Zset非常类似:
都是键值存储
都需求根据键获取值键必须唯一

Hash 类型的底层数据结构是由压缩列表或哈希表实现的：

• 如果哈希类型元素个数小于 512 个（默认值，可由 hash-max-ziplist-entries 配置），所有值小于 64 字节（默认值，可由 hash-max-ziplist-value 配置）的话，Redis 会使用压缩列表作为 Hash 类型的底层数据结构；相邻两个entry分别保存field和value【此时情况和ZSET差不多，把排序相关的跳表去掉】
• 如果哈希类型元素不满足上面条件，Redis 会使用哈希表作为 Hash【HashTable，也就是dict】 类型的 底层数据结构。

Redis网络模型

用户空间和内核空间

为了避免用户应用导致冲突甚至内核崩溃，用户应用与内核是分离的:
进程的寻址空间会划分为两部分:内核空间、用户空间

Linux系统为了提高IO效率，会在用户空间和内核空间都加入缓冲区:
写数据时，要把用户缓冲数据拷贝到内核缓冲区，然后写入设备
读数据时，要从设备读取数据到内核缓冲区，然后拷贝到用户缓冲区

数据的等待和拷贝都会影响性能

阻塞IO

两个阶段【等待数据和拷贝数据】都阻塞等待

非阻塞IO

立即返回而不阻塞用户进程

会有一个轮询的过程
【拷贝的过程阻塞，等待数据的过程是非阻塞的】

老师点评：花里胡哨的，其实没啥用，询问的过程也没提升进程性能，但有时候用他，可以判断数据有没有读完，返回空，那我们就知道读完了。

多路复用IO

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

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

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

第一步：等待用户就绪；
第二步：读取数据

提高办法一：开多线程【开销大】
提高办法二：数据就绪了，用户应用就去读取数据【监听】，而不是完全单队列的排队等待。

select模式

select监听多个FD【File Descriptor】
等监听到可以了，再去receive
能够避免无效等待

我们首先来看看select方案

select 实现多路复用的方式是，将已连接的 Socket 都放到一个文件描述符集合，然后调用 select 函数将文件描述符集合拷贝到内核里，让内核来检查是否有网络事件产生，检查的方式很粗暴，就是通过遍历文件描述符集合的方式。
当检查到有事件产生后，将此 Socket 标记为可读或可写， 接着再把整个文件描述符集合拷贝回用户态里，然后用户态还需要再通过遍历的方法找到可读或可写的 Socket，然后再对其处理。
所以，对于 select 这种方式，需要进行 2 次「遍历」文件描述符集合，一次是在内核态里，一个次是在用户态里 ，而且还会发生 2 次「拷贝」文件描述符集合，先从用户空间传入内核空间，由内核修改后，再传出到用户空间中。
select 使用固定长度的 BitsMap，表示文件描述符集合，而且所支持的文件描述符的个数是有限制的，在 Linux 系统中，由内核中的 FD_SETSIZE 限制， 默认最大值为 1024，只能监听 0~1023 的文件描述符。

监听谁就标记谁，然后从用户空间到内核空间，在内核空间进行标记
标记完后他还要拷贝回用户态，并且用户态也不知道标记了哪些，用户态还要遍历找到可用的socket进行处理

不足之处：两次拷贝；内核态遍历取值，用户态遍历检查值；监听数量有限 1024个

poll方案

IO流程:

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

和select比主要就是多了 链表存储，存储无上限

但监听的FD多了，每次遍历时间也越长，性能反而会下降

epoll模式

效率比之poll和select进步明显

通过红黑树来跟踪进程所有待检测的文件描述字

内核里维护了一个链表list_head来记录就绪事件

当用户调用 epoll_wait() 函数时，只会返回有事件发生的文件描述符的个数，不需要整个一起复制回去

总结：

• select模式存在的三个问题:
  能监听的FD最大不超过1024
  每次select都需要把所有要监听的FD都拷贝到内核空间每次都要遍历所有FD来判断就绪状态
• poll模式的问题:
  poll利用链表解决了select中监听FD上限的问题，但依然要遍历所有FD，如果监听较多，性能会下降
• epoll模式中如何解决这些问题的?
  基于epoll实例中的红黑树保存要监听的FD，理论上无上限，而且增删改查效率都非常高，性能不会随监听的FD数量增多而下降，每个FD只需要执行一次epoll_ctl添加到红黑树，以后每次epol_wait无需传递任何参数，无需重复拷贝FD到内核空间 内核会将就绪的FD直接拷贝到用户空间的指定位置，用户进程无需遍历所有FD就能知道就绪的FD是谁

epoll事件通知机制

边缘触发edge trigger：当FD有数据可读时，会重复通知多次，直至数据处理完成。是Epoll的默认模式。
水平触发 level trigger：当FD有数据可读时，只会被通知一次，不管数据是否处理完成。

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

那么如果是水平触发，你只读了1kb数据，还有1kb没读，我也不通知你了。会从就绪列表中移除这两个数据【可以通过epoll_ctl来手动把他添加回就绪列表】
边缘触发，你读了1kb，还有1kb没读，我会接着通知你

循环从文件描述符读写数据，那么如果文件描述符是阻塞的，没有数据可读写时，进程会阻塞在读写函数那里，程序就没办法继续往下执行。所以，边缘触发模式一般和非阻塞 I/O 搭配使用，程序会一直执行 I/O 操作，直到系统调用（如 read 和 write）返回错误，错误类型为 EAGAIN 或 EWOULDBLOCK。

一般来说，边缘触发的效率比水平触发的效率要高，因为边缘触发可以减少 epoll_wait 的系统调用次数，系统调用也是有一定的开销的的，毕竟也存在上下文的切换。

Redis网络模型

如果仅仅聊Redis的核心业务部分（命令处理)，答案是单线程

如果是聊整个Redis，那么答案就是多线程

Redis 单线程指的是「接收客户端请求->解析请求 ->进行数据读写等操作->发送数据给客户端」这个过程是由一个线程（主线程）来完成的，这也是我们常说 Redis 是单线程的原因。

为什么redis核心业务是单线程？

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

Redis6.0以后引入多线程

采用了多个 I/O 线程来处理网络请求，这是因为随着网络硬件的性能提升，Redis 的性能瓶颈有时会出现在网络 I/O 的处理上。> 所以为了提高网络 I/O 的并行度，Redis 6.0 对于网络 I/O 采用多线程来处理。但是对于命令的执行，Redis> 仍然使用单线程来处理，所以大家不要误解 Redis 有多线程同时执行命令。

结束时间：2022-10-10