【复习】Redis

数据结构

Redis常见的数据结构

String：缓存对象
Hash：缓存对象、购物车
List：消息队列
Set：点赞、共同关注
ZSet：排序

Zset底层？

Zset底层的数据结构是由压缩链表或跳表实现的

如果有序集合的元素 < 128，并且每个元素 < 64字节时，会用压缩列表作为Zset类型的底层数据结构
如果有序集合的元素不满足上面的条件，会用跳表作为Zset类型的底层数据结构

跳表是怎么实现的？

请添加图片描述

跳表在创建节点时，随机生成每个节点的层数。

跳表在创建节点时，先生成[0, 1]的随机数，如果随机数 < 0.25，层数就会增加一层；然后继续生成下一个随机数，直到随机数 > 0.25结束，最终确定该节点的层数

为什么Zset使用跳表而不是B+树？

B+树的设计目标是优化磁盘，通过减少树的高度来降低磁盘寻道次数；跳表是基于链表，通过多级索引加速查询，内存访问模式更符合CPU缓存局部性。Redis是内存数据库，数据完全存储在内存中，不需要优化磁盘IO，B+树的磁盘特性对Redis意义不大，跳表的设计更优
跳表相比B+树实现起来更简单，B+树插入和删除可能需要触发节点的分裂和合并，跳表插入时只需要随机生成层高，删除时直接移除节点并调整指针即可。
B+树每个节点需要存储多个键值和叶子节点，存在内存碎片；跳表每个节点只需要存储键值、层高、多个前向指针，内存占用更紧凑。

压缩列表是怎么实现的?

压缩列表是由连续内存块组成的顺序型数据结构，类似数组。

查找第一个元素和最后一个元素时间复杂度：O(1)
查找其他元素：只能逐个查找，复杂度O(n)

压缩列表的缺点：会发生连锁更新，导致压缩列表占用的内存空间要多次重新分配，这回直接影响到压缩列表的访问性能。

压缩列表只适合保存数据量不多的场景。

quicklist和listpack这两种数据结构就是为了尽可能地保持压缩列表节省内存的优势

哈希表怎么扩容的？

在正常服务请求阶段，插入的数据都会写到哈希表1中，此时哈希表2没有被分配空间，随着数据量的增多，触发了rehash操作：

给哈希表2分配空间，一般比哈希表1大2倍
将哈希表1的数据移动到哈希表2中
迁移完成后，把哈希表1的空间释放，并把哈希表2设置为哈希表1，在哈希表1新创建一个空白的哈希表，为下次rehash做准备。

存在问题：如果哈希表1非常大，那么每次迁移到哈希表2的时候，可能会对redis造成阻塞，无法响应其他请求。

解决：在rehash进行期间，每次进行新增、删除、查找操作，redis除了操作哈希表1，还会操作redis2，这样就把一次大量数据的迁移工作分摊到了多个请求中。

注：哈希表扩容时，如果来了一个读请求，会现在哈希表1里查找；如果没找到，才会到哈希表2里查找。

String是用什么存储的？为什么不用c语言的字符串？

redis中的string字符串使用SDS数据结构存储的，SDS结构如下：

len：记录了字符串的长度
alloc：分配给字节数组的空间长度
flags：用来表示不同类型的SDS（sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64）
buf[]：字符数组，用来保存实际数据

SDS数据结构可以O(1)获取字符串长度，c语言的字符串需要O(n)

SDS不需要"\0"来表示字符串结尾，有个len来记录字符串的长度（但是她为了兼容部分c的库函数，还是加了"\0"）

C语言的字符串在追加的时候是不安全的，程序内部不会判断缓冲区大小是否够用，当缓冲区发生溢出后会导致程序异常；SDS结构里加入alloc和len，这样可以通过alloc - len来判断剩余缓冲区的大小，当缓冲区大小不够用时，redis会自动扩大SDS的空间大小。

线程模型

Redis为什么快？

单线程的redis吞吐量可以达到10w/s

Redis大部分的操作都在内存中完成的，redis的瓶颈可能是机器的内存或网络带宽而非CPU
Redis采用单线程模型可以避免多线程之间的竞争，省去了多线程切换带来的开销
Redis采用IO多路复用机制处理大量客户端的Socket请求，在只运行单线程的情况下，该机制允许内核同时存在多个监听Socket和已连接Socket。

Redis的单线程指的是”接收客户端请求 -> 解析请求 -> 进行读写数据操作 -> 发送数据给客户端“这个过程是一个线程完成的，但是Redis程序不是单线程的，Redis在启动时，会启动后台线程

关闭文件、AOF刷盘、释放内存这些任务会创建单独的线程来处理，如果放在主线程来处理，Redis主线程就会发生阻塞。

Redis6也采用多个IO线程来处理网络请求，因为随着硬件的升级，Redis的性能瓶颈出现在网络IO的处理上

Redis怎么实现IO多路复用

因为Redis是单线程的，所有的操作都是按顺序进行，由于读写操作等待用户的输入和输出都是阻塞的，IO多路复用就是为了单线程的服务同时处理多个客户端的请求。

多路：指多个网络连接客户端

复用：指复用同一个进程

IO多路复用是使用一个线程来检查多个Socket的就绪状态，在单个线程中通过记录跟踪每个Socket的状态来管理处理多个IO流

日志

Redis的持久化方式？

Redis的读写操作都是发生在内存的，但是redis重启后，内存中的数据就会丢失，为了保证内存中的数据不丢失，就需要持久化机制，把数据存储到磁盘，这样Redis重启后就能从磁盘中恢复数据，Redis主要有两种持久化方式，分别是：

AOF日志：每执行一条写操作，就会把该命令以追加的方式写入文件中，redis重启时，会逐一执行这个文件里的命令将数据恢复。redis由三种写回磁盘的策略：
- Always：每次写操作命令执行完后，同步将AOF日志数据写回磁盘
- Everysec：每次写操作命令执行完后，先将命令写到缓冲区中，再每隔一秒将数据写回磁盘
- No：Redis不控制写回磁盘的时机，交给操作系统控制，每次写操作后先将命令写到缓冲区，由操作系统决定何时将命令写回磁盘。
RDB快照：RDB快照只记录一瞬间的内存数据，记录的是实际的数据。Redis有两个命令来生成RDB快照：
- save命令：在主线程中生成RDB文件（会阻塞主线程）
- bgsave命令：创建一个子线程来生成RDB文件（避免阻塞主线程）

AOF日志记录的是操作命令，用AOF做故障恢复时，需要全量把日志全部执行一遍，一旦AOF日志非常多，会造成Redis恢复操作慢。所以引入了RDB快照（记录一瞬间的内存数据，记录的是实际数据，AOF文件记录的是命令操作的日志，而不是实际数据）

内存淘汰和过期删除

内存淘汰和过期删除的区别？

内存淘汰是在内存满时会触发内存淘汰策略来淘汰一些不必要的资源

过期删除是将已过期的键值对进行删除

内存淘汰策略有哪些？

内存淘汰：当Redis内存达到设置的阈值时，Redis就会主动挑选部分key删除以释放更多的内存。

Redis在每次处理客户端命令时，都会对内存使用情况判断，如果必要，则执行内存淘汰。内存淘汰的策略有：

前缀：
- allkeys：对所有的key进行淘汰，从dict的哈希表中挑选
- volatile：只对设置了TTL的key进行淘汰，从expires的哈希表中挑选
后缀：
- ttl：淘汰ttl小的
- random：随机挑选
- lru：基于LRU算法
- lfu：基于LFU算法

过期删除策略？

redis的失效缓存不会立即删除，而是使用惰性删除 + 定期删除这两种策略配合

惰性删除：在访问或修改key时，判断key是否过期，如果过期就删除key；如果没有过期，就不做处理，返回正常的键值对
定期删除：每隔一段时间随机从数据库中取出一部分key进行检查，删除过期的key，如果过期的key≥选举的key的四分之一，则再次选取，直到＜四分之一，这个过程可能会很长时间，所以需要设置循环的上限。

集群

Redis主从同步

全量同步：以下情况会发生全量同步
- 主从集群首次建立连接
- 从服务器断开连接时间过长
步骤：
1. 从服务器发送SYNC命令，开始请求同步
2. 主服务器收到SYNC命令后，生成RDB快照，并将生成的RDB文件发送到从服务器中
3. 从服务器收到RDB文件后，先清空当前的数据集，并载入RDB文件中的数据
4. 在RDB文件传输的过程中，如果又有新的指令，主服务器会将新的指令先放在缓冲区中，一旦RDB文件传输完成，主服务器又会将缓冲区里的命令发给从服务器，保证数据的一致性。
增量同步：允许从服务器从断点处继续同步
步骤：
1. 从服务器在网络恢复后，发送psync命令
2. 主服务器收到psync命令后，告诉从服务器接下来要用增量同步的方式同步数据
3. 主服务器将从服务器断开这段时间内执行的命令，发送给从服务器。
（断开这段时间内执行的命令会存在主服务器的环形缓冲区中，主要存放的是最近传播的写命令，如果缓冲区里的一部分数据还没同步给从服务器，就已经被覆盖了，主服务器就会再次采取全量同步）

哨兵机制的原理？

redis的主从集群中，主从模式是读写分离的，如果主节点挂了，需要选择一个主节点变成从节点，如果没有哨兵机制，那么只能人工选择一个主节点变成从节点，还要通知其他从节点现在主节点的变更。

哨兵机制主要是实现了主从节点的故障转移，他会检测主节点是否存活，如果主节点挂了，就会选取一个从节点当成主节点，并且把新的主节点信息通知给其他的从节点。

哨兵机制选择主节点的算法？

故障节点主观下线：哨兵节点会定时对redis集群里的所有节点发送心跳包检测节点是否正常，如果一个节点没有恢复哨兵节点的心跳包，则认为该节点主观下线
故障节点客观下线：当一个节点被标记成故障，不代表这个节点下线了，但是如果哨兵集群中有超过quorum数量的哨兵节点认为该redis节点主观下线，则该redis客观下线

如果下线的redis节点是从节点或哨兵节点，则没有后续操作了；如果是主节点，则开始故障转移，从剩下的从节点中选出一个节点升级为主节点
哨兵集群中选择Leader：要从redis集群中选择一个节点变成主节点，必须先从哨兵节点中选取leader，一个哨兵节点至少要拿到quorunm个赞成票，才能成为Leader
哨兵Leader选择新主节点：哨兵Leader从redis从节点中选择一个redis节点作为主节点
- 首先判断slave节点与master节点断开时间长短，如果超过指定值（down-after-milliseconds * 10）则会排除该slave节点。
- 然后判断slave节点的slave-priority值，值越小优先级越高。（如果是0则用不参与选举，默认是0）
- 如果slave-priority一样，则判断slave节点的offset值，越大说明数据越新，优先级越高。
- 最后是判断slave节点的运行id大小，越小优先级越高。

Redis集群的模式？

Redis缓存数据量大到一台服务器无法缓存时，就需要使用Redis切片集群，将数据分布在不同的服务器上，降低对单主节点的依赖。

一个切片有16384个哈希插槽，这些哈希插槽类似数据分区，根据他的key被映射到一个哈希槽中。

场景

为什么使用Redis

Redis具备高性能：如果用户第一次访问Mysql中的某些数据，这个过程比较慢，因为是从磁盘上读取的；如果将该用户的数据缓存在Redis中，下次在访问这些数据的时候就可以直接从Redis中读取了，操作Redis缓存就是直接操作内存，速度快。【需要考虑Mysql和Redis中的数据一致性】
Redis具备高并发：单台Redis的QPS是Mysql的10倍，所以访问Redis能承受的请求远远大于Mysql，因此可以考虑将数据库中一部分数据缓存到Redis中，这样就不需要每次请求都到数据库中查了。