八股文之Redis篇_八股文redis 数据结构

前言

Redis的应用场景有很多，比如缓存、分布式锁、消息队列、延迟队列、排行榜，每一个场景都会有对应的问题和成熟的解决方案，都需要进行了解，特别要结合自身的项目进行侧重。下面会列出多种面试会问到的点，以及一些解决方案。

Redis底层中的数据结构

• SDS（Simple Dynamic String）：简单动态字符串，代替了C语言的中的char *定义的字符串，因为其有很多问题，比如：内存分配带来的开销、安全性问题（C 语言的字符串没有保存字符串的长度信息，容易导致缓冲区溢出和越界访问等安全问题）、复杂的字符串操作问题，所以SDS的优点有如下：O(1) 时间获取字符串的长度、支持动态扩容、使用预分配来减少内存分配次数、拥有二进制安全（涉及到二进制字符、字符串长度信息、越界访问等等）。
• IntSet：IntSet是Redis中Set集合的一种实现方式，基于整数数组来实现，具备长度可变、有序等特性，Redis会确保intSet中的元素唯一、有序，具备类型升级机制、可以节省内存空间、底层采用二分查找的方式来查询，数据量不多的情况下使用最佳。
• Dict（dictionary）：实现键与值的映射关系的数据结构，包括Dict + dictHashTable + dictEntry，渐进式rehash
• ZipList：是一种特殊的双端链表，由一系列特殊编码的连续内存块组成，可以在任意一段进行插入和弹出操作，并且读取操作的时间复杂度是O(1)，节省内存，但是必须是连续空间，一旦内存占用多，则申请内存得效率很低
• QuickList：Redis3.2引入的，是一个双端链表，只不过链表中得每一个节点都是ZipList
• SkipList：是一个双向链表，元素按照升序排列存储，节点包含多个指针，指针的跨度不同，最多32层，实现相比红黑树更加简单，层数越大，跨度越大，crud效率和红黑树基本一致
• RedisObject：Redis中的任意数据类型的键和值都会被封装成一个RedisObject

Redis中的编码方式

Redis数据类型对应的编码方式

String：编码方式RAW编码，基于SDS实现，存储上限为512mb，如果SDS长度小于44字节，则会采用EMBSTR编码，如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节）
List：3.2版本之前，Redis采用ZipList和LinkedList来实现List，当元素数量小于512并且元素大小小于64字节时采用ZipList，超过则采用LinkedList编码实现。在3.2版本之后，Redis统一采用QuickList实现List
Set：采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null（和Java中的HashMap与HashSet类型），当存储的所有数据都是整数，并且数量不超过set-max-intset-entries时，set会采用IntSet编码，以节省内存
ZSet：也就是sorted set，其中每一个元素都需要指定一个score和member值，需要根据score值排序，member必须唯一，可以根据member查询分数，能够总结出三个点：键值存储、键必须唯一、可排序，自然用到的编码方式就有：SkipList（可以排序，并且可以同时存储score和member值）、HT（Dict）：可以键值存储、并且可以根据 key 找 value，优化点：当元素数量不多时，HT和SkipList的优势不明显，而且更消耗内存，因此zset还会采用ZipList接口来节省内存，不过需要同时满足两个条件：1.元素数量小于zset_max_ziplist_entries（默认128），2.每个元素都小于zset_max_ziplist_value字节（默认64）。ZipList本身没有排序功能，没有键值对的概念，因此需要由zset通过编码实现：ziplist是连续内存，而且score和element是紧挨在一起的entry，element在前，score在后，score越小越接近队首，越大越接近队尾，按照score值升序排列，这种方式只是为了节省内存，查询效率并不提升，这是兼顾内存节省和查询性能的表现。
Hash：Hash底层采用的编码和Zse基本一致，只需要把排序有关的SkipList去掉即可，Hash结构默认采用ZipList编码，以节省内存，ZipList中相邻的两个entry分别保存field和value，当数据量较大的时候，Hash结构会转为HT编码，也就是Dict，必须满足：ZipList中的元素数量超过了hash-max-ziplist-entries（默认512），ZipList中任意entry大小超过了hash-max-ziplist-value字节（默认64）

缓存穿透

• 缓存穿透：客户端发送请求是查询类的话，如果数据库查不到，那一般就会直接返回空，如果有大量的这类查询结果为空的请求，导致每次请求都查数据库，那么数据库会扛不住，直接挂掉，这是很严重的。
• 解决方案一：缓存空数据，查询返回的数据为空，仍然把这个空数据进行缓存
• 优点：实现起来很简单
  缺点：消耗内存，可能会发生数据不一致的问题
• 解决方案二：布隆过滤器（bitmap，每一位都是bit的数组，多hash映射），用于快速的检索一个元素是否在一个集合中，在缓存预热的时候，预热布隆过滤器
• 优点：内存占用少，没有多余的key（初始化热数据，不会存在多余的key）
• 缺点：实现复杂，存在误判

缓存击穿

• 缓存击穿：给某一个key设置了过期时间，当key过期的时候，恰好这个时间点对这个key有大量的并发请求过来，这些并发的请求可能瞬间把DB压垮
• 解决方案一：加互斥锁，会带来强一致性，不过性能较差
• 解决方案二：设置逻辑过期，缓存失效返回过期数据，另外开辟一个线程来重建缓存，这个期间会使用互斥锁 ，热点数据不设置过期时间，会带来高可用，性能优，但不能保证数据绝对一致

缓存雪崩

• 缓存雪崩：指的是同一时段大量的缓存key同时失效或者Redis服务宕机，导致大量请求直达数据库
• 解决方案一：给不同的key的过期时间添加一个随机值，避免大量key同时过期
• 解决方案二：利用Redis集群提高服务的可用性，哨兵模式或集群模式，部署多个Redis实例
• 解决方案三：启用降级和熔断措施（保底策略），不是核心数据，返回预定义信息、空值、错误信息，访问缓存接口，不会发给Redis
• 解决方案四：添加多级缓存，Caffine

双写一致性

• 双写一致性：当修改了数据库的数据也要同时更新缓存的数据，缓存和数据库的数据要保持一致
• 读操作：缓存命中，直接返回。缓存未命中，查询数据库，写入缓存。
• 写操作：
  • 延迟双删：删除缓存 $\to$ 修改数据库 $\stackrel{延时}{⟶}$ 删除缓存，无论先删除缓存还是先修改数据库，都有脏数据的产生，删两次就是为了减少脏数据，第二次删除延时是因为数据库主从模式下的同步需要时间，所以需要延时删除，性能高，不能保证强一致性
  • 强一致性：使用共享锁、排他锁（setnx），redisson提供了这两种锁，能够保证强一致性，但是性能不高
  • 延时一致性：使用MQ中间件，更新数据后，通知缓存删除，使用Canal中间件，不需要修改业务代码，伪装成MySQL的从节点，读取binlog数据更新缓存

持久化

• Redis中提供了两种数据的持久化方式：RDB 和 AOF
• RDB：RDB全称Redis DataBase Backup File（Redis数据备份文件，以二进制格式存储），也叫做Redis数据快照，把内存中的数据都记录到磁盘中，当Redis重新启动时，从磁盘中读取快照文件，恢复数据。客户端使用 save 和 bgsave 命令来执行RDB，前者是主线程来执行RDB，会阻塞其他命令，后者是开启子进程执行RDB，避免主进程受影响。还可以在redis.conf中通过配置来自动开启子进程来执行RDB，save 900 1 的意思是900秒内，如果至少有一个 key 被修改，则执行 basave。RDB数据安全性不高，因为是周期性生成的，可能会丢失最近一次持久化的之后的数据。
• RDB执行原理：fork主进程得到子进程（主要是复制页表，因为进程无法直接操作内存），子进程会共享主进程的内存数据，完成fork后读取内存数据并写入RDB文件，fork采用的是copy - on - write技术，具体来说是这样的，共享内存只可以读，如果主线程要进行写操作，则会拷贝出一份数据，再执行写操作
• AOF：AOF全称Append Only File（追加文件），Redis处理的每一个写命令都会记录在AOF文件，可以看做是命令日志文件，AOF默认是关闭的，需要修改redis.conf中配置开启AOF，开启AOF：appendonly yes，指定文件：appendfilename "filename"，同时AOF的命令记录的频率也可以通过redis.conf文件来配置，有三种刷盘策略，1.同步刷盘，2.每秒刷盘，3.操作系统控制。AOF还可以通过设置重写命令的触发阈值，来自动的对所记录的命令做简化，用最少的命令达到相同的效果，具体的可以在redis.conf中配置，触发阈值：一个是超过上次文件大小的百分比，一个是和上次文件体积相差多大。AOF持久化方式相对于RDB具有更高的数据安全性，尤其是在数据丢失方面具有更好的保障，因为AOF文件记录了每个操作。AOF数据恢复比较慢，是因为AOF文件记录了每个写操作的详细信息，而在数据恢复过程中需要逐条回放这些操作，导致了恢复的耗时

数据过期策略 / Key删除策略

1. 惰性删除：设置该key过期时间后，我们不去管它，当需要该 key 时，我们在检查其是否过期，如果过期，我们就删掉它，反之返回该key

   优点：性能影响较少，对CPU友好，只会在使用该key时才会进行过期检查，对于很多用不到的key不用浪费时间进行过期检查
   缺点：对内存不友好，如果一个key已经过期，但是一直没有使用，那么该key就会一直存在内存当中，内存永远不会自主释放，造成内存泄漏

2. 定期删除：每隔一段时间，Redis就会对一些key进行检查，删除里面过期的key（从一定量的数据库中取出一定量的随机key进行检查，并删除其中的过期key），SLOW模式是定时任务，执行策略默认为10hz，每次不超过25ms，以通过修改配置文件redis.conf的hz选项来调整这个次数，FAST模式执行频率不固定，但两次间隔不低于2ms，每次耗时不超过1ms

   优点：可以通过限制删除操作的执行时长和频率来减少删除操作对CPU的影响，能有效释放过期key占用的内存
   缺点：删除不够实时

3. 定时删除：设置一个key的过期时间时，增加一个定时任务，检测key将要过期时，直接将其删除

   优点：删除key比较及时，对内存比较友好
   缺点：如果本身业务操作频繁时，刚好有一大批key同时过期时会导致cpu过高

Redis的过期删除策略：惰性删除 + 定期删除，配合使用能够有效的删除过期key

数据淘汰策略

• 数据淘汰策略：当Redis中内存不够用时，此时在向Redis中添加新的key时，那么Redis就会按照某一种规则将内存中的数据删除掉，这种数据的删除规则被称之为内存的淘汰策略
• Redis支持8中不同的策略来选择要删除的key，要清楚LRU、LFU算法的概念，以及默认的策略（不淘汰任何key，满内存时不写入新数据），RANDOM策略就是随机选择一个key进行淘汰，TTL策略就是淘汰距离过期时间最短的那些key

分布式锁

服务器集群部署模式下，如果不对某些业务加分布式锁，就会出问题！好在Redis帮我们实现了分布式锁，来看看具体的分布式锁吧。

Redis实现分布式锁主要利用Redis的setnx命令。setnx时 set if not exists 的简写，在之前setnx实现的分布式锁其实是两条命令，不是原子的，后来Redis官方给 set 命令添加了 nx 选项，所以Redis分布式锁是set命令来执行的：set lock value NX EX 10（EX表示设置超时时间，单位是秒），业务结束使用del key释放锁，但是要考虑到死锁的情况，就是我执行完了业务，但是服务器宕机了，释放锁的动作无法执行，导致其他线程一直在死等，就造成了死锁。我们可以发现这个分布式锁需要设置过期时间，万一我们设置的时间段比较小，业务还在执行中，锁过期了，其他线程抢到了锁，这不就完蛋了吗，这个时候有两种解决方案：

• 第一种是根据业务的执行时间预估一下，把预估结果设置成过期时间，听起来不怎么靠谱，万一网络延迟了呢，但这也是一种解决方案，会有它的用处
• 第二种是给锁续期，实现起来的话就是在执行业务方法的时候，开一个线程来做监控业务执行时长，发现时间比锁过期时间还长，就给锁续期，听起来很靠谱啊，并且市面上有技术已经实现了，就是redisson实现的分布式锁（看门狗机制，过期时间 / 3 就是续期操作的周期），释放锁的时候注意要通知“看门狗”不需要再进行监听了，还需要说明的是，如果其他线程来获取锁，发现锁已经被持有了，该线程会进行重试（re-try），并且存在阈值，在阈值内获取其他线程释放的锁是很高效的，因为我并没有消耗恢复中断的线程所需的时间，但如果阈值到了我还是没有获得锁，该线程就会中断，和前一种保持一致，如果获取到了锁，则会根据方法的调用规则来设定该锁是否存在看门狗机制，redisson官网分布式锁介绍
  

集群模式1：主从复制（高并发读）

单节点模式的Redis的并发能力是有上限的，要进一步提高Redis的并发能力，就需要搭建主从集群，来实现读写分离，主节点称为 master ，从节点称为 slave 或者 replica，一般会有多个从节点，因为缓存主要是读多写少的，从节点就会负责读操作，主节点会负责写操作，在主节点写操作的时候，就需要考虑到一个问题，就是主从结点的数据一致性问题。

主从数据同步原理

两种方式：主从全量同步、主从增量同步
比较重要的是从节点和主节点都会有replid和offset的概念，一个是数据集的标识，另外一个偏移量标识的是当前结点的数据集在哪一个”位置处“，下面的图是具体的流程步骤：

哨兵机制（Sentinel）

Redis的哨兵机制是考虑了主从集群的故障问题，实现集群的高可用，该机制能够提供以下作用：
监控：Sentinel会不断检查master和slave是否按照预期工作，也就是检查是不是出故障了
自动恢复故障：如果主节点挂掉了，Sentinel会将一个slave提升为master。当故障实例恢复后也是以新的master为主
通知：Sentinel充当Redis客户端的服务发现来源，当集群发生故障转移时，会将最新信息推送给Redis客户端，主要就是目前新的主节点是哪个服务器会通知给Redis客户端，Sentinel是根据心跳机制来检测服务状态，每隔一段时间向集群主节点实例发送ping命令，这个时候会有两个现象，一个是某个主节点实例在某一个Sentinel检测下未响应，则是主观下线，如果超过半数（这个阈值可以自行设定）Sentinel都未接到响应，则该实例会客观下线，就要选取一个从节点当作新的主节点，这个选举的规则，具体的可以查文档，要记住的是哪个从节点的offset越大，优先级就越高，因为它的数据越完整嘛

集群模式2：Redis集群 + 哨兵模式下的脑裂问题

因为网络原因，导致主节点、从节点和Sentinel在不同的网络分区，哨兵无法感知主节点的存在，这就是脑裂问题，脑裂问题会导致原来的（真正的）主节点数据丢失，因为从节点会进行选主操作，在网络恢复后的话，选出来的主节点会将数据同步到真正的主节点中，导致数据丢失，因为这期间，真正的主节点在正常工作，接收客户端发送的写操作。
解决方案：我们在配置参数中可以设置一些选项，比如当主结点至少有一个从节点的时候，才会接收客户端发送的数据，另外一个是缩小主从数据同步的延迟，因为在短延迟中，同步操作会识别你有没有从节点，如果没有的话，就不会接收客户端发送的数据

集群模式3： Redis Cluster 分片集群结构

分片集群可以解决海量数据存储、高并发写问题，分片集群结构就是有多个master节点，每个master节点的数据不同，并且可以持有属于自己的从节点slave，这样就可以解决上面的两个问题了。master之间通过ping检测彼此的健康状态，会进行主客观下线的操作，并且客户端的请求可以访问到集群中的任何节点，最终会通过路由转发到正确的节点。
数据读写：Redis分片集群架构引入了哈希槽的概念，Redis集群中共有16384个哈希槽，客户端发过来的每一个key的有效部分通过CRC16校验后对哈希槽的数量16384取模来决定放置哪个槽，集群的每个节点负责一部分的哈希槽

Redis是单线程架构，为什么还能这么快

• Redis是纯内存操作的，执行速度非常快（由CPU直接操作的），不像硬盘，需要通过机械运动来寻找数据。
• 采用单线程，并且占用时间短，因为它基于key / value 的数据操作，大多数命令都是hash计算key，再操作，hash计算key本身就很快，同时结构简单，并且避免了线程切换的和竞争所产生的消耗（这里涉及到线程切换和竞争锁）
• IO模型采用多路复用模型，尽可能充分使用单线程去完成连接处理以及读写IO，非阻塞IO

Redis存在什么问题

• 基于内存操作，数据不稳定，容易丢失
• key / value 的结构导致数据检索能力较差，比如范围查询、模糊查询
• 事务支持不友好

IO多路复用模型

Redis是纯内存操作，执行速度非常快，它的性能瓶颈是网络延迟而不是执行速度，IO多路复用模型就是实现了高效的网络请求。

用户空间和内核空间

• Linux中一个进程使用的内存情况划分为两部分：内核空间、用户空间
• 用户空间只能执行受限的命令（Ring3），而且不能直接调用系统资源，必须通过内核提供的接口来访问
• 内核空间可以执行特权命令（Ring0），调用一切系统资源
• Linux为了提高IO效率，在这两个空间内设置了缓冲区，写数据，先拷贝到内核缓冲区，再写入设备，读数据，先读取数据到内核缓冲区，再拷贝到用户缓冲区
• 阻塞IO、非阻塞IO、IO多路复用（三种模式select、poll、epoll，前两种中只会去遍历判断，而epoll会直接通知是哪个具体的Socket就绪了，再把它写入用户空间）
• IO多路复用是利用单个线程同时监听多个Socket，并在某个Socket可读，可写时得到通知，从而避免无效的等待，充分利用CPU资源，会采用epoll模式实现，他会在通知用户进程就绪的同时，把已就绪的Socket写入用户空间。

Redis网络模型

Redis通过IO多路复用模型来提高网络性能，并且支持各种不同的多路复用实现（select、poll、epoll），并且将这些实现进行了封装，提供了统一的高性能事件处理器库（连接应答、命令回复、命令请求处理器等等）