大家好,我是阿秀。
大家五一过的怎么样啊?有没有出去玩,哦不,有没有被堵在路上...
机智的我选择呆在实验室里看B站技术视频和《计算机程序的构造和解释》
五一结束之后再出去溜达溜达,嘿嘿,完美避开游客高峰期。
阿秀五一期间除了疯狂卷肝视频之外也没闲着,还把以前自己做的 Redis 笔记好好整理了一遍,大概整理出 25 道高频面试题。由于篇幅原因,一次性更新 25 道题导致整体太过冗长,很多人可能根本看不过来,所以 Redis 篇打算分为两期更新。
另外,C++、操作系统、计算机网络、MySQL 的硬核面试资料均已更新完毕,如果有还没看过的可以先去看看啦。
《逆袭进大厂系列》(包含C++、操作系统、计算机网络、MySQL、Redis、情景题)
下面就把本期的 Redis 分享给大家吧。
Redis是一个数据库,不过与传统数据库不同的是Redis的数据库是存在内存中,所以读写速度非常快,因此 Redis被广泛应用于缓存方向。
除此之外,Redis也经常用来做分布式锁,Redis提供了多种数据类型来支持不同的业务场景。除此之外,Redis 支持事务持久化、LUA脚本、LRU驱动事件、多种集群方案。
Redis没有直接使用C语言传统的字符串,而是自己构建了一种名为简单动态字符串(Simple dynamic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示。
其实SDS等同于C语言中的char * ,但它可以存储任意二进制数据,不能像C语言字符串那样以字符’\0’来标识字符串的结 束,因此它必然有个长度字段。
struct sdshdr {
// 记录buf数组中已使用字节的数量
// 等于sds所保存字符串的长度
int len;
// 记录buf数组中未使用字节的数量
int free;
// 字节数组,用于保存字符串
char buf[];
}
它具有很常规的 set/get 操作,value 可以是String也可以是数字,一般做一些复杂的计数功能的缓存。
当有一个列表键包含了数量比较多的元素,又或者列表中包含的元素都是比较长的额字符串时,Redis就会使用链表作为列表建的底层实现。
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 链表所包含的节点数量
unsigned long len;
// 节点值复制函数
void *(*dup)(void *ptr);
// 节点值是放过函数
void (*free)(void *ptr);
// 节点值对比函数
int(*match)(void *ptr, void *key);
} list;
字典的底层是哈希表,类似 C++中的 map ,也就是键值对。
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于size-1
unsigned long sizemark;
// 该哈希表已有节点的数量
unsigned long used;
} dichht;
当字典被用作数据库的底层实现,或者哈希键的底层实现时,Redis使用MurmurHash算法。这种算法的优点在于即使输入的键是规律的,算法仍能给出一个个很好的随机分布性,并且算法的计算速度非常快。
Redis的哈希表使用链地址法来解决键冲突,每个哈希表节点都有一个next指针,多个哈希表节点可以用这个单向链表连接起来,这就解决了键冲突的问题。
先看这样一张图:
如上图,我们要查找一个元素,就需要从头节点开始遍历,直到找到对应的节点或者是第一个大于要查找的元素的节点(没找到)。时间复杂度为O(N)。
这个查找效率是比较低的,但如果我们把列表的某些节点拔高一层,如下图,例如把每两个节点中有一个节点变成两层。那么第二层的节点只有第一层的一半,查找效率也就会提高。
查找的步骤是从头节点的顶层开始,查到第一个大于指定元素的节点时,退回上一节点,在下一层继续查找。
比如我们要查找16:
这个例子中遍历的节点不比一维列表少,但是当节点更多,查找的数字更大时,这种做法的优势就体现出来了。还是上面的例子,如果我们要查找的是39,那么只需要访问两个节点(7、39)就可以找到了。这比一维列表要减少一半的数量。
为了避免插入操作的时间复杂度是O(N),skiplist每层的数量不会严格按照2:1的比例,而是对每个要插入的元素随机一个层数。
随机层数的计算过程如下:
typedef struct zskiplistNode {
// 后退指针
struct zskiplistNode *backward;
// 分值 权重
double score;
// 成员对象
robj *obj;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} leval[];
} zskiplistNode;
一般来说,层的数量越多,访问其他节点的速度越快。
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int leval;
} zskiplist;
“压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现。
看他的名字就能看出来,是为了节省内存造的列表结构。
String数据结构是简单的key-value类型,value其实不仅可以是String,也可以是数字。常规key-value缓存应用;常规计数:微博数,粉丝数等。
Hash 是一个 string 类型的 field 和 value 的映射表,hash 特别适合用于存储对象,后续操作的时候,你可以直接仅 仅修改这个对象中的某个字段的值。比如我们可以Hash数据结构来存储用户信息,商品信息等。
list 就是链表,Redis list 的应用场景非常多,也是Redis最重要的数据结构之一,比如微博的关注列表,粉丝列表, 消息列表等功能都可以用Redis的 list 结构来实现。
Redis list 的实现为一个双向链表,即可以支持反向查找和遍历,更方便操作,不过带来了部分额外的内存开销。
另外可以通过 lrange 命令,就是从某个元素开始读取多少个元素,可以基于 list 实现分页查询,这个很棒的一个功 能,基于 Redis 实现简单的高性能分页,可以做类似微博那种下拉不断分页的东西(一页一页的往下走),性能高。
set 对外提供的功能与list类似是一个列表的功能,特殊之处在于 set 是可以自动排重的。
当你需要存储一个列表数据,又不希望出现重复数据时,set是一个很好的选择,并且set提供了判断某个成员是否在 一个set集合内的重要接口,这个也是list所不能提供的。可以基于 set 轻易实现交集、并集、差集的操作。
比如:在微博应用中,可以将一个用户所有的关注人存在一个集合中,将其所有粉丝存在一个集合。Redis可以非常 方便的实现如共同关注、共同粉丝、共同喜好等功能。这个过程也就是求交集的过程,具体命令如下:sinterstore key1 key2 key3
将交集存在key1内。
和set相比,sorted set增加了一个权重参数score,使得集合中的元素能够按score进行有序排列。
举例:在直播系统中,实时排行信息包含直播间在线用户列表,各种礼物排行榜,弹幕消息(可以理解为按消息维 度的消息排行榜)等信息,适合使用 Redis 中的 SortedSet 结构进行存储。
主要是因为 Redis 具备高性能和高并发两种特性。
严格意义上来说缓存分为本地缓存和分布式缓存。
那以 C++ 语言为例,我们可以使用 STL 下自带的容器 map 来实现缓存,但只能实现本地缓存,它最主要的特点是轻量以及快速,但是其生命周期随着程序的销毁而结束,并且在多实例的情况下,每个实例都需要各自保存一份缓存,缓存不具有一致性。
使用 Redis 或 Memcached 之类的称为分布式缓存,在多实例的情况下,各实例共享一份缓存数据,缓存具有一致性。这是Redis或者Memcached的优点所在,但它也有缺点,那就是需要保持 Redis 或 Memcached服务的高可用,整个程序架构上较为复杂。
1、访问速度快,因为数据存在内存中,类似于Java中的HashMap或者C++中的Map,这两者的优势就是查找和操作的时间复杂度都是O(1)
2、数据类型丰富,支持String,list,set,sorted set,hash这五种数据结构
3、支持事务,Redis中的操作都是原子性,换句话说就是对数据的更改要么全部执行,要么全部不执行,这就是原子性的定义
4、特性丰富:Redis可用于缓存,消息,按key设置过期时间,过期后将会自动删除。
1、存储方式
2、数据支持类型
3、使用底层模型不同
4、集群模式:Memcached没有原生的集群模式,需要依靠客户端来实现往集群中分片写入数据;但是 Redis 目前 是原生支持 cluster 模式的.
5、Memcached是多线程,非阻塞IO复用的网络模型;Redis使用单线程的多路 IO 复用模型。
6、Value 值大小不同:Redis 最大可以达到 512MB;Memcached 只有 1MB。
1、Memcached所有的值均是简单字符串,Redis作为其替代者,支持更为丰富的数据类型
2、Redis 的速度比 Memcached 快很多
3、Redis可以做到持久化数据
其实就是名字上的意思,热数据就是访问次数较多的数据,冷数据就是访问很少或者从不访问的数据。
需要注意的是只有热点数据,缓存才有价值 对于冷数据而言,大部分数据可能还没有再次访问到就已经被挤出内存,不仅占用内存,而且价值不大。
数据更新前至少读取两次,缓存才有意义。这个是最基本的策略,如果缓存还没有起作用就失效了,那就没有太大价值了。
这主要是基于一种客观原因来考虑的。因为Redis是基于内存的操作,CPU不是Redis的瓶颈,Redis的瓶颈最有可能是机器内存的大小或者网络带宽。既然单线程容易实现,而且CPU不会成为瓶颈,那就顺理成章地采用单线程的方案了(毕竟采用多线程会有很多麻烦!)
主要是有三个原因:1、Redis的全部操作都是纯内存的操作;2、Redis采用单线程,有效避免了频繁的上下文切换;3,采用了非阻塞I/O多路复用机制。
如果你打开看过 Redis 的源码就会发现Redis 内部使用文件事件处理器 file event handler,这个文件事件处理器是单线程的,所以 Redis 才叫做单线程的模型。它采用 IO 多路复用机制同时监听多个 socket,根据 socket 上的事件来选择对应的事件处理器进行处理。
文件事件处理器的结构包含 4 个部分:
使用 I/O 多路复用程序来同时监听多个套接字, 并根据套接字目前执行的任务来为套接字关联不同的事件处理器。当被监听的套接字准备好执行连接应答(accept)、读取(read)、写入(write)、关闭(close)等操作时, 与操作相对应的文件事件就会产生, 这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。
多个 socket 可能会并发产生不同的操作,每个操作对应不同的文件事件,但是 IO 多路复用程序会监听多个 socket,会将 socket 产生的事件放入队列中排队,事件分派器每次从队列中取出一个事件,把该事件交给对应的事件处理器进行处理。
一句话总结就是:“I/O 多路复用程序负责监听多个套接字, 并向文件事件分派器传送那些产生了事件的套接字。”
Redis中有个设置时间过期的功能,即对存储在 Redis 数据库中的值可以设置一个过期时间。
作为一个缓存数据库, 这是非常实用的,比如一些 token 或者登录信息,尤其是短信验证码都是有时间限制的,按照传统的数据库处理方式,一般都是自己判断过期,这样无疑会严重影响项目性能。
我们 set key 的时候,都可以给一个 expire time,就是过期时间,通过过期时间我们可以指定这个 key 可以存活的时间,主要可采用定期删除和惰性删除两种方案。
并不能保证一定删除,Redsi有一个Redis 内存淘汰机制来确保数据一定会被删除。
首先介一下定期删除和惰性删除的工作流程:
1、定期删除,Redis默认每个100ms检查,是否有过期的key,有过期key则删除。需要说明的是,Redis不是每个100ms将所有的key检查一次,而是随机抽取进行检查(如果每隔100ms,全部key进行检查,Redis岂不是卡死)。因此,如果只采用定期删除策略,会导致很多key到时间没有删除。
2、于是,惰性删除派上用场。也就是说在你获取某个key的时候,Redis会检查一下,这个key如果设置了过期时间那么是否过期了?如果过期了此时就会删除。
3、采用定期删除+惰性删除就没其他问题了么? 不是的,如果定期删除没删除key。然后你也没即时去请求key,也就是说惰性删除也没生效。这样,Redis
4、内存会越来越高。那么就应该采用内存淘汰机制。
在Redis.conf中有一行配置:maxmemory-policy volatile-lru
该配置就是配内存淘汰策略的,主要有以下六种方案:
volatile-lru:从已设置过期时间的数据集(server.db[i].expires)中挑选最近最少使用的数据淘汰
volatile-ttl:从已设置过期时间的数据集(server.db[i].expires)中挑选将要过期的数据淘汰
volatile-random:从已设置过期时间的数据集(server.db[i].expires)中任意选择数据淘汰
allkeys-lru:从数据集(server.db[i].dict)中挑选最近最少使用的数据淘汰allkeys-random:从数据集(server.db[i].dict)中任意选择数据淘汰
no-enviction(驱逐):禁止驱逐数据,新写入操作会报错
需要注意的是,如果没有设置 expire 的key, 不满足先决条件(prerequisites); 那么 volatile-lru, volatile-random 和 volatile-ttl 策略的行为, 和 noeviction(不删除) 基本上一致。
1、Redis是一个单线程程序,也就说同一时刻它只能处理一个客户端请求;2、Redis是通过IO多路复用(select,epoll,kqueue,依据不同的平台,采取不同的实现)来处理多个客户端请求。
缓存雪崩指的是缓存同一时间大面积的失效,所以,后面的请求都会落到数据库上,造成数据库短时间内承受大量请求而崩掉。
看不懂?那我说人话。
我们可以简单的理解为:由于原有缓存失效,新缓存未到期间(例如:我们设置缓存时采用了相同的过期时间,在同一时刻出现大面积的缓存过期),所有原本应该访问缓存的请求都去查询数据库了,而对数据库CPU和内存造成巨大压力,严重的会造成数据库宕机,从而形成一系列连锁反应,造成整个系统崩溃。
解决办法
一般是黑客故意去请求缓存中不存在的数据,导致所有的请求都落到数据库上,造成数据库短时间内承受大量 请求而崩掉。
这也看不懂?那我再换个说法好了。
缓存穿透是指查询一个一定不存在的数据,由于缓存不命中,接着查询数据库也无法查询出结果,因此也不会写入到缓存中,这将会导致每个查询都会去请求数据库,造成缓存穿透。
解决办法
1、布隆过滤器
这是最常见的一种解决方法了,它是将所有可能存在的数据哈希到一个足够大的bitmap中,一个一定不存在的数据会被 这个bitmap拦截掉,从而避免了对底层存储系统的查询压 力。
对所有可能查询的参数以hash形式存储,在控制层先进行校验,不符合则丢弃,从而避免了对底层存储系统的查询压力;
这里稍微科普一下布隆过滤器。
“布隆过滤器是引入了k(k>1)k(k>1)个相互独立的哈希函数,保证在给定的空间、误判率下,完成元素判重的过程。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。 该算法的核心思想就是利用多个不同的Hash函数来解决“冲突”。Hash存在一个冲突(碰撞)的问题,用同一个Hash得到的两个URL的值有可能相同。为了减少冲突,我们可以多引入几个Hash,如果通过其中的一个Hash值我们得出某元素不在集合中,那么该元素肯定不在集合中。只有在所有的Hash函数告诉我们该元素在集合中时,才能确定该元素存在于集合中。这便是布隆过滤器的基本思想,一般用于在大数据量的集合中判定某元素是否存在。
2、缓存空对象
当存储层不命中后,即使返回的空对象也将其缓存起来,同时会设置一个过期时间,之后再访问这个数据将会从缓存中获取,保护了后端数据源;如果一个查询返回的数据为空(不管是数据不存 在,还是系统故障),我们仍然把这个空结果进行缓存,但它的过期时间会很短,最长不超过五分钟。
但是这种方法会存在两个问题:
1、如果空值能够被缓存起来,这就意味着缓存需要更多的空间存储更多的键,因为这当中可能会有很多的空值的键;
2、即使对空值设置了过期时间,还是会存在缓存层和存储层的数据会有一段时间窗口的不一致,这对于需要保持一致性的业务会有影响。
我们可以从适用场景和维护成本两方面对这两汇总方法进行一个简单比较:
适用场景:缓存空对象适用于1、数据命中不高 2、数据频繁变化且实时性较高 ;而布隆过滤器适用1、数据命中不高 2、数据相对固定即实时性较低
维护成本:缓存空对象的方法适合1、代码维护简单 2、需要较多的缓存空间 3、数据会出现不一致的现象;布隆过滤器适合 1、代码维护较复杂 2、缓存空间要少一些
缓存预热是指系统上线后,将相关的缓存数据直接加载到缓存系统。这样就可以避免在用户请求的时候,先查询数据库,然后再将数据缓存的问题。用户会直接查询事先被预热的缓存数据!
解决思路1、直接写个缓存刷新页面,上线时手工操作下;2、数据量不大,可以在项目启动的时候自动进行加载;3、定时刷新缓存;
除了缓存服务器自带的缓存失效策略之外(Redis默认的有6中策略可供选择),我们还可以根据具体的业务需求进行自定义的缓存淘汰,常见的策略有两种:
(1)定时去清理过期的缓存;定时删除和惰性删除
(2)当有用户请求过来时,再判断这个请求所用到的缓存是否过期,过期的话就去底层系统得到新数据并更新缓存。两者各有优劣,第一种的缺点是维护大量缓存的key是比较麻烦的,第二种的缺点就是每次用户请求过来都要判断缓存失效,逻辑相对比较复杂!具体用哪种方案,大家可以根据自己的应用场景来权衡。
缓存击穿,是指一个key非常热点,在不停的扛着大并发,大并发集中对这一个点进行访问,当这个key在失效的瞬间,持续的大并发就穿破缓存,直接请求数据库,就像在一个屏障上凿开了一个洞。
比如常见的电商项目中,某些货物成为“爆款”了,可以对一些主打商品的缓存直接设置为永不过期。即便某些商品自己发酵成了爆款,也是直接设为永不过期就好了。mutex key互斥锁基本上是用不上的,有个词叫做大道至简。
当访问量剧增、服务出现问题(如响应时间慢或不响应)或非核心服务影响到核心流程的性能时,仍然需要保证服务还是可用的,即使是有损服务。系统可以根据一些关键数据进行自动降级,也可以配置开关实现人工降级。降级的最终目的是保证核心服务可用,即使是有损的。而且有些服务是无法降级的(如加入购物车、结算)。以参考日志级别设置预案:
(1)一般:比如有些服务偶尔因为网络抖动或者服务正在上线而超时,可以自动降级;
(2)警告:有些服务在一段时间内成功率有波动(如在95~100%之间),可以自动降级或人工降级,并发送告警;
(3)错误:比如可用率低于90%,或者数据库连接池被打爆了,或者访问量突然猛增到系统能承受的最大阀值,此时可以根据情况自动降级或者人工降级;
(4)严重错误:比如因为特殊原因数据错误了,此时需要紧急人工降级。服务降级的目的,是为了防止Redis服务故障,导致数据库跟着一起发生雪崩问题。因此,对于不重要的缓存数据,可以采取服务降级策略,例如一个比较常见的做法就是,Redis出现问题,不去数据库查询,而是直接返回默认值给用户。
最近有粉丝跑来告诉我说,自己整理的《InterviewGuide》,面试资料被某个培训机构拿去做面试突击,emm,就很无语。
我分享这些东西是无偿的,如今却被你们拿去盈利。。。
惹不起,我还躲不起吗,一气之下阿秀以后都不再提供 md 格式的文件了,以后只在公众号提供自己的文章,并且提供一些 PDF 资料的下载了。
还有,对于上述问题,你,学废了吗?