redis底层原理基础面试题

前言：由于正在准备之后的实习面试，故总结了一部分redis底层原理的问题，回答全为自己组织的语言，若有错各位大佬可及时指出，大家共同进步，谢谢。

1.Redis的各个数据结构及使用场景

redis中自主实现的数据结构主要有字符串、链表、字典、跳表、整数集合、压缩列表。
字符串作为最基本的数据结构类型，对于简单字符数组在安全性、效率及功能方面有所提升。底层结构中包含free\len\buf字段，分别表示是否还能分配使用空间、字符长度、底层数组指针。由于包含len字段，首先可以以O(1)时间复杂度获取字符串长度，其次可以防止缓冲区溢出，当调用修改API时会检测当前空间是否满足需求，如果不满足则会先扩容底层数组，这些操作对于上层来说都是封装隐藏的。而包含free字段，通过预分配和释放惰性空间等机制则可以减少修改字符串时带来的内存重分配次数。最后，简单字符数组不能保存二进制文件，因为不能出现空字符否则会被认定为结束字符，但redis中的字符串类型由于存在len属性来判断是否结束，所以可以保证二进制安全，可以保存任意二进制数据。字符串结构常用在缓存、计数、限速等场景。
链表则是提供节点重排、顺序访问，并且可以提供增删节点来灵活调整链表长度。链表结点的底层结构就是一个带前后结点指针的双向链表，链表底层结构中有复制、释放、对比的相应函数指针。主要是为了实现双端、无环且带表头表尾指针、长度计数器的特性。列表键的底层实现之一就是链表，发布、订阅、慢查询、监视器等等都用到了链表。
字典就是redis中所实现的map类型，字典底层也是采用hashtable的结构实现，由哈希表结点作为桶，结点结构中有下个结点的指针从而形成链表，解决冲突的方法也是挂载到冲突结点，负载因子过大或过小时系统也会自动扩容和收缩然后渐进式进行rehash。redis中的数据库就是字典作为底层实现的，对数据库的增删查改等等操作都是用字典API操作，字典本身也可以作为键类型：哈希键。
跳表是一种有序数据结构，通过在每个结点中维持多个指向不同结点的指针以实现快速访问不同结点的目的。跳表结点底层结构中包括一个元素数组、前进后退双向指针、层数，层数就是表示跳表查询过程中跨度的参数。插入跳表结点是会随机生成一个层数值以保证查询效率。跳表支持平均O(logn)，最坏O(N)时间复杂度的查找，由于底层数据结点可以顺序访问，功能类似于B+Tree叶节点上的双向指针，所以可以顺序批量处理结点，查询效率也跟平衡树类似。
整数集合则是用于保存整数值的集合抽象数据结构，可以保存不同类型的整数值且保证不出现重复，底层结构比较简单只包括编码格式、长度、底层数组三个字段。比较值得一提的是升级操作，由于集合中可以插入不同整数类型的值，当需要插入更长类型的值时就会触发升级，首先将底层数组扩容到相应的大小再依次将元素转换成新类型，最后插入新元素。整数集合是集合键的底层实现之一。
压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构，列表中可以包含多个节点，每个节点可以保存字节数组或者整数值，每个节点都有一个属性记录前一个节点的长度。

2.Redis持久化方式怎样实现

redis持久化机制一共有两种：RDB、AOF
RDB持久化的原理是把内存中的数据库状态以快照形式压缩保存到一个dump二进制文件，redis提供了两个命令来手动执行生成RDB，一种是阻塞服务器进程直到RDB创建完成，一种是开一个子进程来单独生成RDB，值得一提的是，AOF比RDB优先级高，要使用RDB还原数据库状态得先关闭AOF。一般情况下，redis是通过设置服务器配置来自动完成间隔性开子进程保存RDB，通过save x y来实现设置x秒内至少有y次修改则触发RDB保存。
AOF持久化的原理是通过保存redis服务器中所执行的写命令，被写入的命令都是以命令请求协议保存，每次服务器执行完一个写命令之后，就以协议格式追加到AOF缓冲区，结束一个事件循环之前都会判断是否需要将缓冲区内容同步到具体的AOF文件中，具体规则由服务器设置而定。
在单机架构中，由于AOF文件中都是可读性的协议命令，而RDB是压缩快照，所以AOF文件普遍大于RDB文件而且由于AOF需要持续同步，效率也略低于RDB。而对于主从同步来说，同步策略是先传输RDB作全量同步，再使用AOF作增量同步。

3.Redis的LRU具体实现

redis每次按key获取一个值的时候，都会更新value中的lru字段为当前秒级别的时间戳。Redis初始的实现算法很简单，随机从dict中取出五个key,淘汰一个lru字段值最小的。 在3.0的时候，又改进了一版算法，首先第一次随机选取的key都会放入一个pool中(pool的大小为16),pool中的key是按lru大小顺序排列的。 接下来每次随机选取的keylru值必须小于pool中最小的lru才会继续放入，直到将pool放满。放满之后，每次如果有新的key需要放入，需要将pool中lru最大的一个key取出。淘汰的时候，直接从pool中选取一个lru最小的值然后将其淘汰。

4.Redis为什么IO速度这么快

redis数据都保存内存当中，API基本都是内存操作；服务器进程大部分时间是单线程操作，避免了上下文切换的开销；redis底层为每个键类型对象都实现了合理高效的数据结构；redisIO采用的是非阻塞IO多路复用机制。

5.Redis的数据过期策略

redis数据过期策略包括：定期删除、惰性删除
定期删除通过启动一个定时监视函数监视所有Key,若存在过期就删除，但是这种策略每次都需要遍历所有键值，非常消耗cpu资源，若当key已过期但未到定时器启动状态，则不能保证key的不可用。
惰性删除则是获取key时先判断是否过期，若过期则删除。这种策略则是会一直占用内存资源，若已经过期key未被使用，则会一直保存在内存中。
目前redis采用不再每次扫描全部的键，而是随机抽取一部分键进行检查，这样就降低了对cpu的资源损耗。

6.如何解决Redis缓存雪崩问题

主要有几个方面的解决思路：
redis缓存雪崩的原因呢是因为一大部分的key在同一时间段内全都失效从而使得请求全都进到数据库从而导致服务失效，要解决缓存雪崩，首先很简单的思路就是让并发分散，既然大部分key同时过期承受不住，就给key随机的过期时间保证同一时刻的缓存穿透量不多，再有是从另外的系统业务层面设置随机延时保证请求的分散，最后就是使用高可用集群架构，保证redis服务不挂。

7.如何解决Redis缓存穿透问题

主要有几个方面的解决思路：
redis缓存穿透和击穿是两个比较容易混淆的概念，穿透是强调数据库和缓存内都没有数据导致缓存永远不能命中所以请求都会传到数据库加大数据库压力。最简单的方法是直接填入一个nil值表示数据不存在，再次查询同一个key时返回nil，但是带来的影响就是内存吃紧，如果同时出现大量请求查询不存在的数据就会造成内存内大部分都是nil值对。所以怎样在有效且尽可能小的内存空间内表示大部分不存在的数据才是解决缓存穿透的方案，那就是bloom filter,具体简单的原理是通过bitmap位图来实现，初始化一个位数组，对于每一个key值都通过不同hash到不同的多个位上将位点置1，查询时检查key的hash值所对应的位点是否被置1，若已经都被置1，则代表数据存在，若存在其中任意一个位点未被置1，则代表数据必然不存在。

8.Redis并发竞争key如何解决

主要有两个方面的解决思路：
首先是可以利用分布式锁来保证客户端请求进程的独占，在redis中的实现是通过setnx先设置锁键值对，如果已经存在此键值对，则获取锁失败，如果不存在则获取锁成功。接着对锁键值对设置过期时间来保证就算请求中断或是客户端宕机也能保证锁最终可以被释放，但是这带来的问题是如果客户端是因为执行时间长导致锁过期，会导致锁被释放该客户端需要重新获取锁导致延迟增高。所以redis在客户端加锁成功后会启动一个后台线程监视该锁，如果客户端需要持续持有该锁，则延长锁过期时间。
其次是通过MQ对流量进行削峰，但是由于消息队列造成了串行化，这也会造成性能的降低。

9.Redis的主从模式和哨兵模式和集群模式具体实现原理区别

redis中模式主要就分为三种：主从、哨兵、集群
主从模式：
主要作用是保证数据的备份，通常会设置一个主节点若干个从节点，主节点提供全部IO操作，并且同步数据到从节点上，从节点只提供读操作。由于主从模式保证了读写分离，所以一定程度上缓解了主节点的读压力，但是主从模式并未提供了高可用机制，主结点宕机后服务会瘫痪。
哨兵模式：
是对主从模式的优化，可以为redis提供高可用性。开启哨兵模式后，redis会在主从模式的基础上再在后台启动一个新结点-sentinel也就是哨兵，哨兵会持续监控当前所有的主从结点的可用性，也可以和多个哨兵通信保持对一个主从集群的监视，若主节点出现问题下线了，哨兵会从所有从节点中选出一个成为新主结点从而实现故障转移。
哨兵模式的底层原理和主要的详细步骤可以大致总结为：首先初始化哨兵服务器，为哨兵服务器提供专有的代码和命令表，并且初始化哨兵的监视表，也就是每个正在被监视的结点的状态信息结构，然后创建对主节点的网络连接包括命令和订阅。之后定时通过命令连接获取主节点当前信息，发现从节点后再通过命令和订阅连接到从节点。若从主节点订阅频道获取到其他哨兵的信息，则也会创建相应的命令连接。创建完所有连接后当前哨兵会以每秒一次的频率对所有创建了命令连接的结点服务器发起PING命令来检查服务器是否在线，若指定时间内未收到回复命令，则判断该结点为主观下线。若出现主观下线的结点，当前哨兵会向监视该结点的其他哨兵发送命令以检查其他哨兵是否也认为当前结点是主观下线的，若得到的回复超过配置中指定的数量则认为该结点已经客观下线。若有客观下线的结点出现，当前哨兵会发起一次选举以成为可以执行故障转移的leader，之所以要发起选举而不是直接由当前结点进行故障转移，是因为有可能同一时间有多个哨兵都判断该节点为客观下线，若同时启动故障转移，会造成操作冲突。
哨兵选举的机制等同于raft的选举机制，具体流程大致为：当前哨兵发起选举时初始化配置纪元(任期)，依次向其他哨兵发送命令请求他们同意自己成为leader,其他哨兵同意的规则是先到先得，在一个配置纪元中哨兵只能投一票，投票后会发送回复命令给发起投票的哨兵，回复命令中记录了当前哨兵的ID和配置纪元数，若相对应，则当前哨兵认为已经获得了该选票，这也保证了一个配置纪元中只能有一个leader产生，一旦获得有超过半数哨兵的投票，则当前哨兵成为leader，继而执行故障转移。
故障转移的具体流程大致为：先从故障主节点属下的从节点中挑选出一个状态良好、数据完备的从节点成为新的主节点，判断机制为依次筛选出下线断线、五秒内未回复、与主节点断开连接过、复制偏移量小，从而按照优先级选出最合适的从节点。选出后修改其他所有从节点的同步复制目标为当前新的主节点，将旧主节点设置为新主节点的从节点，从而保证旧主节点上线后依旧可以加入到此集群。
集群模式：
redis集群是通过分布式数据分片来将数据分割到不同节点上实现高可用，一个集群也包括主节点和从节点，其中主节点用于处理槽，从节点用于复制一个主节点，并在该主节点下线后可以代替主节点继续处理命令请求。
启动集群时，先将各个主结点通过命令握手依次进入集群，redis整个数据库被分为16384个槽，按命令要求可以指派0-16384个槽给任意结点，之后初始化一个结构来保存各个结点当前处理槽的信息，处理槽可以通过命令进行转移或重新分片给新结点。当结点接收到IO命令后，该结点会计算当前命令属于哪个槽、是否落入当前处理槽，若有就处理，若没有就把命令发送给目标槽结点。
当集群加入从节点后，从节点会持续同步对应主节点的数据，若检测到连接断开，则判断该主节点为疑似下线，会将下线信息同步给集群中的其他主结点，若超过半数主节点都将某个主节点报告为疑似下线，则该结点会被标记为已下线，具体机制类似于哨兵的监视机制。若出现已下线结点，则该结点的从节点也会发起选举，选举机制也和哨兵的选举机制相同，都是参考raft中的选举而来。

10.Redis中的各个对象底层是怎么实现的

redis中自主实现的所有数据结构都是为了实现定义的键值对象，保证键值对象的性能。创建键值对时，则至少创建键、值两个对象。redis中对象类型有：字符串对象、列表对象、哈希对象、集合对象、有序集合对象。redis为每个对象初始化时都实例化了一个结构体，里面有类型、编码、指向底层结构的指针等。对象的编码可以根据不同使用场景随意切换，决定了此对象由什么数据结构封装而成。
字符串对象可以由int、raw、embstr编码实现，int编码只能保存整数值的字符串对象，raw编码会创建SDS动态字符串结构，embstr编码则是raw的优化，专门用于保存短字符串，将对象结构与底层SDS结构分配在一块连续的内存空间，一定条件下编码也可以互相转换。
列表对象可以由ziplist、linkedlist编码实现，ziplist编码使用压缩列表作为底层实现，linkedlist编码使用双端链表作为底层实现，链表结点嵌套了字符串对象。
哈希对象可以由ziplist、hashtable编码实现，ziplist编码使用压缩列表作为底层实现，当存入键值对时，先将键结点压到列表尾，再将值结点压到列表尾以此保证键值对紧邻。hashtable编码使用字典作为底层实现，键值对直接使用字典键值对保存。
集合对象可以由inset、hashtable编码实现，intset编码使用整数集作为底层实现，而hashtable编码则是将集合元素作为键，值设置为nil保存到字典。
有序集合可以由ziplist、skiplist编码实现，ziplist编码使用压缩列表作为底层实现，每个集合元素使用紧邻的节点依次保存元素成员和权重。skiplist编码使用一个字典+一个跳表作为底层实现，字典可以实现O(1)复杂度查找，跳表可以实现范围型操作。

11.跳表的底层实现原理，查询过程是怎么样的，查询和插入的时间复杂度

跳表是一种有序数据结构，通过在每个结点中维持多个指向不同结点的指针以实现快速访问不同结点的目的。跳表结点底层结构中包括一个元素数组、前进后退双向指针、层数，层数就是表示跳表查询过程中跨度的参数。插入跳表结点是会随机生成一个层数值以保证查询效率。跳表支持平均O(logn)，最坏O(N)时间复杂度的查找和插入，由于底层数据结点可以顺序访问，功能类似于B+Tree叶节点上的双向指针，所以可以顺序批量处理结点，查询效率也跟平衡树类似。