【Redis面试】基础题总结(中)

导读:本篇文章讲解 【Redis面试】基础题总结(中),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

相关文章:
【Redis面试】基础题总结(上)
【Redis面试】基础题总结(下)
有关redis基础知识见专栏:Redis

1.介绍redis集群的实现方案

redis集群的分区方案:
redis集群采用虚拟分槽来实现数据分片,它把所有键根据哈希函数映射到0-16383整数数据槽内,每一个节点负责维护一部分槽及所映射的键值数据,虚拟槽特点:
1.解耦数据和节点之间的关系,简化了节点扩容和收缩的难度;
2.节点自身维护槽的映射关系,不需要客户端或者代理服务维护槽分区元数据
3.支持节点,槽,键之间的映射查询,用于数据路由,在线伸缩等场景
Redis集群中数据的分片逻辑:
在这里插入图片描述
redis集群的功能限制
redis集群方案在扩展redis的处理能力的同时,也带来了一些使用上的限制
1.key批量支持有限:如mset,mget,目前只支持具有相同slot值的key执行批量操作,对于映射为不同slot值的key由于执行mset,mget等操作可能存在与多个节点上所以不被支持;
2.key事务操作支持有限:支持在同一节点上的事务操作;
3.key作为数据分区的最小粒度,所以不能将一个大的键值对(hash,list等)映射到不同节点;
4.不支持多数据库空间:单机下的redis支持16个数据库,集群下只能使用1个即DBO;
5.复制结构只支持一层,从节点只能复制主节点,不支持嵌套树状复制结构;
Redis集群的通信方案:
redis集群采用P2P的Gossip(流言)协议,Gossip协议的工作原理是节点彼此不断通信交换信息,一段时间后所有节点都会知道集群完整的信息,这种方式类似与留言传播,过程如下:
1.集群中每一个节点都会单独开辟一个tcp通道,用于节点之间的彼此通信,通信端口在基础端口上加10000;
2.每个节点在固定周期内通过特定规则选择几个节点ping消息;
3.接收ping消息的节点用pong消息作为响应
其中,Gossip协议的主要职责是交换信息,而信息交换的载体是节点彼此间发送gossip消息,Gossip消息分为:meet消息,ping消息,pong消息,fail消息等;
meet消息:用于通知新节点加入,消息发送者通知接收者加入到当前集群,meet‘消息通信正常完成后,接收点会加入到集群并进行周期性的ping消息,pong消息
ping消息:集群内交换最为频繁的消息,集群中每个节点每秒向多个其他节点发送ping消息,用于检测节点是否在线和交换彼此的状态信息,ping消息分装了自身节点和一部分其他节点的状态信息;
pong消息:当接收到meet,ping消息后作为响应回复给发送方确认消息正常通信,pong消息封装了自身的状态数据,节点也可以向集群内广播自身的pong消息来通知整个集群对自身状态信息更新。
fail消息:当节点判断集群中的某一个节点下线时会向集群中发送一个fail消息,其他节点收到fail消息之后把对应节点更新为下线状态;

2.说一说hash类型底层的数据结构

hash对象有两种编码方案,当同时满足以下条件时,哈希对象采用ziplist,否则采用hashtable编码;
哈希对象保存的键值对数量小于512个
哈希对象保存的所有键值对中的键和值,其字符串长度都小于64字节
其中压缩列表编码采用压缩链表作为底层实现,而hashtable采用字典作为底层实现
压缩列表:
是redis为了节约内存而设计的一种线性数据结构,它是由一系列具有特殊编码的连续内存块构成,一个压缩链表可以包含任意多个节点,每个节点可以保存一个字节数组或一个整数
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
previous_entry_length(pel)属性以字节为单位,记录当前节点的前一节点的长度,其自身占据1字节或5字节:

如果前一节点的长度小于254字节,则“pel”属性的长度为1字节,前一节点的长度就保存在这一个字节内;

如果前一节点的长度达到254字节,则“pel”属性的长度为5字节,其中第一个字节被设置为0xFE,之后的四个字节用来保存前一节点的长度;

基于“pel”属性,程序便可以通过指针运算,根据当前节点的起始地址计算出前一节点的起始地址,从而实现从表尾向表头的遍历操作。
content属性负责保存节点的值(字节数组或整数),其类型和长度则由encoding属性决定,它们的关系如下:
在这里插入图片描述
字典:
又称为散列表,是一种用来存储键值对的数据结构
redis字典的实现主要涉及三个结构体:字典,哈希表哈希表节点。其中每个哈希表节点存储一个键值对,每个哈希表由多个哈希表节点构成,而字典是对哈希表的进一步封装。这三个结构的关系如下:
在这里插入图片描述
其中dict代表字典,dictht代表哈希表,dictEntry代表哈希表节点。可以看出dictEntry是一个数组,因为每一个哈希表要存放多个哈希表节点。而dict里包含2个dictht多出的哈希表用于rehash。当哈希表保存的键值对过多或过少时,需要对哈希表的大小进行扩展或收缩操作,在redis中扩展和收缩哈希表是通过rehash’实现的。执行rehash的步骤如下:
1.为字典的ht[1]哈希表分配存储空间

如果执行的是扩展操作,则ht[1]的大小等于h[0].used*2的2n。如果执行的是收缩操作则ht[1]的大小为第1个大于等于ht[0].used的2n。

2.将存储在ht[0]中的数据迁移到ht[1]上

重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的指定位置上。

3.将字典的ht[1]哈希表晋升为默认哈希表

迁移完成后,清空ht[0],再交换ht[0]和ht[1]的值,为下一次REHASH做准备。

当满足以下任何一个条件时,程序会自动开始对哈希表执行扩展操作:

1.服务器目前没有执行bgsave或bgrewriteof命令,并且哈希表的负载因子大于等于1;

2.服务器目前正在执行bgsave或bgrewriteof命令,并且哈希表的负载因子大于等于5。

为了避免REHASH对服务器性能造成影响,REHASH操作不是一次性地完成的,而是分多次、渐进式地完成的。渐进式REHASH的详细过程如下:

1.为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表;

2.在字典中的索引计数器rehashidx设置为0,表示REHASH操作正式开始;

3.在REHASH期间,每次对字典执行添加、删除、修改、查找操作时,程序除了执行指定的操作外,还会顺带将ht[0]中位于rehashidx上的所有键值对迁移到ht[1]中,再将rehashidx的值加1;

4.随着字典不断被访问,最终在某个时刻,ht[0]上的所有键值对都被迁移到ht[1]上,此时程序将rehashidx属性值设置为-1,标识REHASH操作完成。

REHSH期间,字典同时持有两个哈希表,此时的访问将按照如下原则处理:

1.新添加的键值对,一律被保存到ht[1]中;

2.删除、修改、查找等其他操作,会在两个哈希表上进行,即程序先尝试去ht[0]中访问要操作的数据,若不存在则到ht[1]中访问,再对访问到的数据做相应的处理

3.介绍一下zset类型底层的数据结构

有序集合对象有两种编码方案,当同时满足以下条件时,集合对象采用ziplist,否则采用skiplist编码
1.有序集合保存的元素数量不超过128个
2.有序集合保存的所有元素的成员长度都小于64字节
其中ziplist编码的有序集合采用压缩列表作为底层实现,skiplist编码的有序集合采用zset结构作为底层实现。
其中zset是一个复合结构,它的内部采用字典和调表来实现,其源码如下
其中dict保存了从成员到分支的映射关系,zsl则按分值由小到大保存了所有集合元素,这样,当按照成员来访问有序集合时可以直接从dict中取值,当按照分值的范围访问有序集合列表时可以直接从zsl中取值,采用了空间换时间的策略。
综上所述,zset对象的底层数据结构包括:压缩列表,字典,跳跃表
跳跃表:

跳跃表的查找复杂度为平均O(logN),最坏O(N),效率堪比红黑树,却远比红黑树实现简单。跳跃表是在链表的基础上,通过增加索引来提高查找效率的。

有序链表插入、删除的复杂度为O(1),而查找的复杂度为O(N)。例:若要查找值为60的元素,需要从第1个元素依次向后比较,共需比较6次才行,如下图:
在这里插入图片描述
跳跃表是从有序链表中选取部分节点,组成一个新链表,并以此作为原始链表的一级索引。再从一级索引中选取部分节点,组成一个新链表,并以此作为原始链表的二级索引。以此类推,可以有多级索引,如下图:
在这里插入图片描述
跳跃表在查找时,优先从高层开始查找,若next节点值大于目标值,或next指针指向NULL,则从当前节点下降一层继续向后查找,这样便可以提高查找的效率了。

跳跃表的实现主要涉及2个结构体:zskiplist、zskiplistNode,它们的关系如下图所示:
在这里插入图片描述
其中,蓝色的表格代表zskiplist,红色的表格代表zskiplistNode。zskiplist有指向头尾节点的指针,以及列表的长度,列表中最高的层级。zskiplistNode的头节点是空的,它不存储任何真实的数据,它拥有最高的层级,但这个层级不记录在zskiplist之内。

4.如何利用redis实现分布式session

在web开发中,我们会把用户的登录信息存储在session中,而session是依赖与cookie的,即服务器创建session时会给他分配一个唯一的id,并在响应时创建一个cookie用于存储这个session,当客户端收到这个cookie后会自动保存这个sessionid,并在下次访问时自动携带这个sessionid,届时服务器就可以通过这个sessionid得到与之对应的session,从而识别用户身份
在这里插入图片描述
现在的互联网应用,基本都是采用分布式部署方式,即将应用程序部署在多台服务器上,并通过nginx做统一的请求分发。而服务器与服务器之间是隔离的,它们的session是不共享的,这就存在session同步的问题了,如下图:

在这里插入图片描述
如果客户端第一次访问服务器,请求被分发到了服务器A上,则服务器A会为该客户端创建session。如果客户端再次访问服务器,请求被分发到服务器B上,则由于服务器B中没有这个session,所以用户的身份无法得到验证,从而产生了不一致的问题。

解决这个问题的办法有很多,比如可以协调多个服务器,让他们的session保持同步。也可以在分发请求时做绑定处理,即将某一个IP固定分配给同一个服务器。但这些方式都比较麻烦,而且性能上也有一定的消耗。更合理的方式就是采用类似于Redis这样的高性能缓存服务器,来实现分布式session。

从上面的叙述可知,我们使用session保存用户的身份信息,本质上是要做两件事情。第一是保存用户的身份信息,第二是验证用户的身份信息。如果利用其它手段实现这两个目标,那么就可以不用session,或者说我们使用的是广义上的session了。

具体实现的思路如下图,我们在服务端增加两段程序:

第一是创建令牌的程序,就是在用户初次访问服务器时,给它创建一个唯一的身份标识,并且使用cookie封装这个标识再发送给客户端。那么当客户端下次再访问服务器时,就会自动携带这个身份标识了,这和SESSIONID的道理是一样的,只是改由我们自己来实现了。另外,在返回令牌之前,我们需要将它存储起来,以便于后续的验证。而这个令牌是不能保存在服务器本地的,因为其他服务器无法访问它。因此,我们可以将其存储在服务器之外的一个地方,那么Redis便是一个理想的场所。

第二是验证令牌的程序,就是在用户再次访问服务器时,我们获取到了它之前的身份标识,那么我们就要验证一下这个标识是否存在了。验证的过程很简单,我们从Redis中尝试获取一下就可以知道结果。
在这里插入图片描述

5.如何利用Redis实现一个分布式锁?

何时需要分布式锁?

在分布式的环境下,当多个server并发修改同一个资源时,为了避免竞争就需要使用分布式锁。那为什么不能使用Java自带的锁呢?因为Java中的锁是面向多线程设计的,它只局限于当前的JRE环境。而多个server实际上是多进程,是不同的JRE环境,所以Java自带的锁机制在这个场景下是无效的。

如何实现分布式锁?

采用Redis实现分布式锁,就是在Redis里存一份代表锁的数据,通常用字符串即可。实现分布式锁的思路,以及优化的过程如下:

在这里插入图片描述
在这里插入图片描述
想要解决这个问题,我们需要解决两件事情:

1.在加锁时就要给锁设置一个标识,进程要记住这个标识。当进程解锁的时候,要进行判断,是自己持有的锁才能释放,否则不能释放。可以为key赋一个随机值,来充当进程的标识。

2.解锁时要先判断、再释放,这两步需要保证原子性,否则第二步失败的话,就会出现死锁。而获取和删除命令不是原子的,这就需要采用Lua脚本,通过Lua脚本将两个命令编排在一起,而整个Lua脚本的执行是原子的。

按照以上思路,优化后的命令如下:

# 加锁 set key random-value nx ex seconds   # 解锁 if redis.call("get",KEYS[1]) == ARGV[1] then     return redis.call("del",KEYS[1]) else     return 0 end

基于RedLock算法的分布式锁:

上述分布式锁的实现方案,是建立在单个主节点之上的。它的潜在问题如下图所示,如果进程A在主节点上加锁成功,然后这个主节点宕机了,则从节点将会晋升为主节点。若此时进程B在新的主节点上加锁成果,之后原主节点重启,成为了从节点,系统中将同时出现两把锁,这是违背锁的唯一性原则的。

在这里插入图片描述

总之,就是在单个主节点的架构上实现分布式锁,是无法保证高可用的。若要保证分布式锁的高可用,则可以采用多个节点的实现方案。这种方案有很多,而Redis的官方给出的建议是采用RedLock算法的实现方案。该算法基于多个Redis节点,它的基本逻辑如下:

这些节点相互独立,不存在主从复制或者集群协调机制;

加锁:以相同的KEY向N个实例加锁,只要超过一半节点成功,则认定加锁成功;

解锁:向所有的实例发送DEL命令,进行解锁;

RedLock算法的示意图如下,我们可以自己实现该算法,也可以直接使用Redisson框架。

在这里插入图片描述

6.说一说对布隆过滤器的理解

布隆过滤器可以用很低的代价,估算出数据是否真实存在。例如:给用户推介新闻时,要去掉重复的新闻,可以利用布隆过滤器,判断是否已经推介过。
布隆过滤器的核心包括两部分:
1.一个大型的位数组
2.若干个不一样的哈希函数,每个哈希函数都能将哈希值算的比较均匀
工作原理:
1.添加key时,每个哈希函数都利用这个key算出一个哈希值,再根据哈希值算出一个位置,并将位数组中的这个位置设置为1
2.询问key时:每个哈希函数都利用这个key算出一个哈希值,再算出一个位置,然后对比这些哈希函数在位数组中对应位置的值
**如果这几个位置有一个位置是0,则不存在这个值

** 如果所有位置都是1,就说明极有可能存在,之所以不是100%,是因为也可能是运算导致的

7.多台redis抗高并发访问该则么设计?

redis cluster是redis的分布式解决方案,在3.0版本中正式推出,有效的解决了redis分布式方面的需求,遇到单机内存,并发,流量等瓶颈时,可以采用cluster架构方案达到负载均衡的目的。
redis集群采用虚拟机分槽,来实现数据分片,它把所有建根据哈希函数映射到0-16383的整数槽内,计算公式slot=crc16(key)&16383,每个节点负责维护一部分槽,以及槽所映射的键值数据,虚拟槽分区具有如下特点:
1.解耦数据和节点之间的关系,简化了节点扩容和收缩的难度
2.节点自身维护槽的映射关系,不需要客户端或者代理服务维护槽分区元数据
3.支持节点,槽,键之间的映射查询,用于数据路由,在线伸缩等场景。

8.redis的应运场景?

Redis 在互联网产品中使用的场景实在是太多太多,这里分别对 Redis 几种数据类型做了整理:

1)String:缓存、限流、分布式锁、计数器、分布式 Session 等。

2)Hash:用户信息、用户主页访问量、组合查询等。

3)List:简单队列、关注列表时间轴。

4)Set:赞、踩、标签等。

5)ZSet:排行榜、好友关系链表。

9.Zset 为何不使用红黑树等平衡树?

1)跳跃表范围查询比平衡树操作简单。 因为平衡树在查询到最小值的时还需要采用中序遍历去查询最大值。 而跳表只需要在找到最小值后,对第一层的链表遍历即可。

2)平衡树的删除和插入需要对子树进行相应的调整,而跳表只需要修改相邻的节点即可。

3)跳表和平衡树的查询操作都是O(logN)的时间复杂度。

4)从整体上来看,跳表算法实现的难度要低于平衡树。

10.什么是 RedisObject?

我们知道,Redis 底层实现了很多高级数据结构,如简单动态字符串、双端链表、字典、压缩列表、跳跃表、整数集合等。然而 Redis 并没有直接使用这些数据结构来实现键值对的数据库,而是在这些数据结构之上又包装了一层 RedisObject(对象),也就是我们常说的五种数据结构:字符串对象、列表对象、哈希对象、集合对象和有序集合对象。

typedef struct redisObject {
// 类型
unsigned type:4;
// 编码,即对象的底层实现数据结构
unsigned encoding:4;
// 对象最后一次被访问的时间
unsigned lru:REDIS_LRU_BITS;
// 引用计数
int refcount;
// 指向实际值的指针
void *ptr;
} robj;

这样做有两个好处:

1)通过不同类型的对象,Redis 可以在执行命令之前,根据对象的类型来判断一个对象是否可以执行该的命令。

2)可以针对不同的使用场景,为对象设置不同的实现,从而优化内存或查询速度。

11.缓存更新策略

缓存更新策略的最佳实践:

低一致性需求:使用Redis自带的内存淘汰机制

高一致性需求:主动更新,并以超时剔除作为兜底方案

读操作:

缓存命中则直接返回

缓存未命中则查询数据库,并写入缓存,设定超时时间

写操作:

先写数据库,然后再删除缓存

要确保数据库与缓存操作的原子性

12.Redis网络模型

用户空间和内核空间
为了避免用户应用导致冲突甚至内核崩溃,用户应用与内核是分离的:

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

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

内核空间可以执行特权命令(Ring0),调用一切系统资源。

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

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

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

13.客户端如何路由?

既然 Redis 集群中的数据是分片存储的,那我们该如何知道某个 key 存在哪个节点上呢?即我们需要一个查询路由,该路由根据给定的 key,返回存储该键值的机器地址。

常规的实现方式便是采用如下图所示的代理方案,即采用一个中央节点(比如HDFS中的NameNode)来管理所有的元数据,但是这样的方案带来的最大问题就是代理节点很容易成为访问的瓶颈,当读写并发量高的时候,代理节点会严重的拖慢整个系统的性能。
在这里插入图片描述

Redis 并没有选择使用代理,而是客户端直接连接每个节点。Redis 的每个节点中都存储着整个集群的状态,集群状态中一个重要的信息就是每个桶的负责节点。在具体的实现中,Redis 用一个大小固定为 CLUSTER_SLOTS 的 clusterNode 数组 slots 来保存每个桶的负责节点。

typedef struct clusterNode {
...
unsigned char slots[CLUSTER_SLOTS/8];
...
} clusterNode;

typedef struct clusterState {
// slots记录每个桶被哪个节点存储
clusterNode *slots[CLUSTER_SLOTS];
...
} clusterState;

在集群模式下,Redis 接收任何键相关命令时首先计算键对应的桶编号,再根据桶找出所对应的节点,如果节点是自身,则处理键命令;否则回复 MOVED 重定向错误,通知客户端请求正确的节点,这个过程称为 MOVED 重定向。重定向信息包含了键所对应的桶以及负责该桶的节点地址,根据这些信息客户端就可以向正确的节点发起请求。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/82261.html

(0)

相关推荐

半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!