又到了金三银四跳槽季,好多同学已经开始行动了。今天我来助力一把,送出这套redis
面试题,助力大家通关。
1 redis为什么响应快
1.1数据保存在内存中
redis
数据保存在内存中,读写操作只要访问内存,不需要磁盘IO
。
1.2.底层数据结构
redis
的数据以key:value
的格式存储在散列表中,时间复杂度o(1)
。redis
为value
定义了丰富的数据结构,包括动态字符串、双向链表、压缩列表、hash
、跳表和整数数组,可以根据value的特性选择选择最高效的数据结构。
1.3.单线程模型
redis
的网络IO
和数据读写使用单线程模型,可以绑定CPU
,这避免了线程上下文切换带来的开销。
「注意:redis6.0对网络请求引入了多线程模型,读写操作还是用单线程。」
redis
多线程网络模型见下图:
1.4.IO多路复用
redis
采用epoll
网络模型,如下图:
内核会一直监听新的socket
连接事件的和已建立socket
连接的读写事件,把监听到的事件放到事件队列,redis使用单线程不停的处理这个事件队列。这避免了阻塞等待连接和读写事件到来。
这些事件绑定了回调函数,会调用redis的处理函数进行处理。
2 redis底层数据结构
redis
有5种数据类型,包括「字符串、列表、集合、有序集合和字典」。
redis
底层的数据结构有6种,包括「动态字符串、双向链表、压缩列表(ziplist)、hash表、跳表(skip list)和整数数组」。
redis
数据类型和底层数据结构有如下对应关系:
2.1.字符串类型
底层数据结构是动态字符串。
2.2.列表
如果同时满足下面条件,就使用压缩列表,否则使用双向链表。
- 列表中单个元素小于
64
字节 - 列表中元素个数少于
512
「压缩列表」在内存中是一块儿连续的内存空间,结构如下:
「压缩列表查找时间复杂度是o(n)
」
2.3.集合
如果同时满足下面条件,就使用有序整数数组,否则使用hash表。
- 集合中元素都是整数类型
- 集合中元素个数不超过
512
个
2.4.有序集合
如果同时满足下面2个条件,就使用压缩列表,否则使用跳表。
- 集合中元素都小于
64
字节 - 集合中元素个数小于
128
个
「注意:有序集合还有一个HASH
表用于保存集合中元素的分数,做ZSCORE
操作时,查询的就是这个HASH
表,所以效率很高。」
「跳表」的结构如下:
如果不加索引,查找10
这个数字需要查询10
次,使用了二级索引,查找10
这个数字需要5
次,而使用一级索引,需要查询3
次。
❝跳表的每一层都是一个有序链表,最下面一层保存了全部数据。跳表插入、删除、查询的时间复杂度是
❞o(logN)
。跳表需要存储额外的索引节点,会增加额外的空间开销。
2.5.字典
如果同时满足下面2个条件,就使用压缩列表,否则使用hash表。
- 字典中每个
entry
的key/value
都小于64字节 - 字典中元素个数小于
512
个
3 redis缓存淘汰策略
redis
总共有8
种淘汰策略,如下图:
volatile-lfu
和allkeys-lfu
策略是4.0
版本新增的。
- 「lru」是按照数据的最近最少访问原则来淘汰数据,可能存在的问题是如果大批量冷数据最近被访问了一次,就会占用大量内存空间,如果缓存满了,部分热数据就会被淘汰掉。
- 「lfu」是按照数据的最小访问频率访问次数原则来淘汰数据,如果两个数据的访问次数相同,则把访问时间较早的数据淘汰。
4 redis数据持久化
redis
持久化的方式有2
种,一种是写后日志(AOF)
,一种是内存快照(RDB)
。
4.1.AOF日志
AOF
日志记录了每一条收到的命令,redis
故障宕机恢复时,可以加载AOF
日志中的命令进行重放来进行故障恢复。AOF
有3
种同步策略,如下图:
❝如果不是对丢失数据特别敏感的业务,推荐使用
❞everysec
,对主线程的阻塞少,故障后丢失数据只有1s
。
4.2.RDB快照
RDB
快照是一个内存快照,记录了redis
某一时刻的全部数据。
4.3.混合日志
从redis4.0
开始,AOF
文件也可以保存RDB
快照,AOF
重写的时候redis
会把AOF
文件内容清空,先记录一份RDB
快照,这份数据以"REDIS"
开头。记录RDB
内容后,AOF
文件会接着记录AOF
命令。故障恢复时,先加载AOF
文件中RDB
快照,然后回放AOF
文件中后面的命令。
4.4.主从同步
redis
主从同步时,主节点会先生成一份RDB
快照发送给从节点,把快照之后的命令写入主从同步缓存区(replication buffer)
,从节点把RDB
文件加载完成后,主节点把缓存区命令发送给从节点。
4.5.AOF重写
AOF
日志是用记录命令的方式追加的,这样可能存在对同一个key
的多条命令,这些命令是可以合并成1
条的。比如对同一个key
的多个set
操作日志,可以合成一条。
4.6.阻塞点
AOF
重写和RDB
快照执行的过程中,redis
都会fork
一个子进程来执行操作,子进程执行过程中是不是阻塞主线程的。
「但是要注意2
点:」
fork
子进程的过程中,redis
主线程会拷贝一份内存页表(记录了虚拟内存和物理内存的映射关系)给子进程,这个过程是阻塞的,redis
主线程内存越大,阻塞时间越长;- 子进程和
redis
主线程共用一块儿物理内存,如果新的请求到来,必须使用copy on write
的方式,拷贝要修改的数据页到新的内存空间进行修改。如下图:
注意:如果开启了内存大页,每次拷贝都需要分配2MB的内存。
❞
5 redis高可用
下图是一个「一主二从三哨兵」的架构图:
从图我们可以看到哨兵之间、哨兵和主从节点之间、哨兵和客户端之间都建立了连接。
如果主节点挂了,哨兵集群需要完成主从切换,如下图:
下面我们依次来聊一下这4个步骤「5.1~5.4」。
5.1.判断主节点下线
当一个哨兵监控到主节点下线时,就会给其他哨兵发送确认命令,其他命令会根据自己的判断回复"Y"
或"N"
。
如果有n/2 + 1
以上数量的哨兵都认为主节点下线了,才会判定主节点下线。这里的n
是哨兵集群的数量。
❝❞
n/2 + 1
这个参数由quorum
参数配置,比如有5
个哨兵,这里一般配置成3
。也可以配置成其他值。
5.2.选举新主节点
主节点被判定下线后,哨兵集群会重新选择新的主节点。
5.2.1 淘汰不稳定从节点
根据配置参数down-after-milliseconds * 10
来淘汰。
「down-after-milliseconds」表示主从节点断开时间,10
表示次数,如果从节点跟主节点断开时间超过down-after-milliseconds
的次数达到了10
次以上,从节点就被淘汰了。
5.2.2 slave-priority参数
「slave-priority」参数配置了从节点的优先级,选择从节点时哨兵会优先选择优先级高的从节点。
5.2.3 复制进度
redis
有一个记录主从增量复制的缓存区叫repl_backlog_buffer
,这是一个环形结构的缓冲区,如下图:
主节点有一个写偏移量master_repl_offset
,从节点也有一个偏移量slave_repl_offset
。优先选择slave_repl_offset
最接近master_repl_offset
的从节点作为新的主节点。
所以,上图中偏移量为114
的从节点优先被选为新的主节点。
5.2.4 ID编号
优先级和参数都一样的情况下,ID
编号小的从节点优先被选为新主节点。
5.3.选举哨兵leader
第一个判断主节点下线的哨兵节点收到其他节点的回复并确定主节点下线后,就会给其他哨兵发送命令申请成为哨兵leader
。
「成为leader的条件如下:」
- 收到赞成票必须大于等
quorum
值 - 必须拿到半数以上的赞成票
❝如果集群配置了5个哨兵,
❞quorum
的值设置为3,其中一个哨兵节点挂了,很有可能会判断到主节点下线,但是因为选举不出哨兵leader
而不能切换。如果集群有2
个哨兵,其中一个挂了,那必定选不出哨兵leader
。
下面的图展示了哨兵一成功当选leader
的过程:
5.4.主节点切换
选出新主节点和哨兵leader
后,哨兵leader
会执行主从切换的操作。完成后会做一些「事件通知」:
- 通知其他哨兵新主节点地址
- 通知所有从节点新的主节点地址,从节点收到后向新主节点请求主从同步
- 通知客户端连接新主节点
5.5.主从切换过程中请求处理
如果客户端的读请求会发送到从节点,可以正常处理。
在客户端收到新主节点地址通知前写请求会失败。
客户端可以采取一些应急措施应对主节点下线,比如缓存写请求。
为了能够及时获取到新主节点信息,客户端可以订阅哨兵的主节点下线事件和新主节点变更事件。
6 redis为什么变慢了
redis
变慢了的原因有很多,总结一下有11
个,见下图:
从图中看出,redis
变慢原因主要有两类:「阻塞主线程和操作系统限制」。
6.1主线程阻塞
6.1.1.AOF重写和RDB快照
前面已经讲过了,redis
在AOF
重写时,主线程会fork
出一个bgrewriteaof
子进程。
redis
进行RDB
快照时主线程会fork
出一个bgsave
子进程。
这两个操作表面上看不阻塞主线程,但fork
子进程的这个过程是在主线程完成的。fork
子进程时redis
需要拷贝内存页表,如果redis
实例很大,这个拷贝会耗费大量的CPU
资源,阻塞主线程的时间也会变长。
6.1.2.内存大页
redis
默认支持内存大页是2MB
,使用内存大页,一定程度上可以减少redis
的内存分配次数,但是对数据持久化会有一定影响。
redis
在AOF
重写和RDB
快照过程中,如果主线程收到新的写请求,就需要CopyOnWrite
。使用了内存大页,即使redis
只修改其中一个大小是1kb
的key
,也需要拷贝一整页的数据,即2MB
。在写入量较多时,大量拷贝就会导致redis
性能下降。
6.1.3.命令复杂度高
执行复杂度高的命令是造成redis
阻塞的常见原因。比如对一个set
或者list
数据类型执行SORT
操作,复杂度是O(N+M*log(M))
。
6.1.4.bigkey操作
如果一个key
的value
非常大,创建的时候分配内存会很耗时,删除的时候释放内存也很耗时。
redis4.0
以后引入了layfree
机制,可以使用子进程异步删除,从而不影响主线程执行。用UNLINK
命令替代DEL
命令,就可以使用子进程异步删除。
redis6.0
增加了配置项lazyfree-lazy-user-del
,配置成yes
后,del
命令也可以用子进程异步删除。
❝如果
❞lazyfree-lazy-user-del
不设置为yes
,那redis
是否采用异步删除,是要看删除的时机的。对于String
类型和底层采用整数数组和压缩列表的数据类型,redis
是不会采用异步删除的。
6.1.5.从节点全量同步
从节点全量同步过程中,需要先清除内存中的数据,然后再加载RDB文件,这个过程中是阻塞的,如果有读请求到来,只能等到加载RDB文件完成后才能处理请求,所以响应会很慢。
另外,如果redis
实例很大,也会造成RDB
文件太大,从库加载时间长。所以尽量保持redis
实例不要太大,比如单个实例限制4G
,如果超出就采用切片集群。
6.1.6.AOF同步写盘
appendfsync
策略有3种:always、everysec、no
,如果采用always,每个命令都会同步写盘,这个过程是阻塞的,等写盘成功后才能处理下一条命令。
除非是严格不能丢数据的场景,否则尽量不要选择always
策略,推荐尽量选择everysec
策略,如果对丢失数据不敏感,可以采用no
。
6.1.7.内存达到maxmemory
内存达到maxmemory
,需要使用淘汰策略来淘汰部分key
。即使采用lazyfree
异步删除,选择key
的过程也是阻塞的。
❝可以选择较快的淘汰策略,比如用随机淘汰来替换
❞LRU
和LFU
算法淘汰。也可以扩大切片数量来减轻淘汰key
的时间消耗。
6.2操作系统限制
6.2.1.使用了swap
使用swap
的原因是操作系统不能给redis
分配足够大的内存,如果操作其他开启了swap
,内存数据就需要不停地跟swap
换入和换出,对性能影响非常大。
操作系统没有能力分配内存的原因也可能是其他进程使用了大量的内存。
6.2.2.网络问题
如果网卡负载很大,对redis
性能影响会很大。这一方面有可能redis
的访问量确实很高,另一方面也可能是有其他流量大的程序占用了带宽。
这个最好从运维层面进行监控。
6.2.3.线程上下文切换
redis
虽然是单线程的,但是在多核cpu
的情况下,也可能会发生上下文切换。如果主线程从一个物理核切换到了另一个物理核,那就不能使用CPU
高效的一级缓存和二级缓存了。如下图所示:
为防止这种情况,可以把redis
绑定到一个CPU
物理核。
6.2.4.磁盘性能低
对于AOF
同步写盘的使用场景,如果磁盘性能低,也会影响redis
的响应。可以优先采用性能更好的SSD
硬盘。
7 设计排行榜功能
redis
的zset
类型保存了分数值,可以方便的实现排行榜的功能。
比如要统计10
篇文章的排行榜,可以先建立一个存放10
篇文章的zset
,每当有读者阅读一篇文章时,就用ZINCRBY
命令给这篇文章的分数加1
,最后可以用range
命令统计排行榜前几位的文章。
8 redis实现分布式锁
8.1.redis单节点的分布式锁
如下图,一个服务部署了2
个客户端,获取分布式锁时一个成功,另一个就失败了。
redis
一般使用setnx
实现分布式锁,命令如下:
SETNX KEY_NAME VALUE
设置成功返回 1
,设置失败返回 0
。
使用单节点分布式锁存在一些问题。
8.1.1.客户端1获取锁后发生了故障
结果锁就不能释放了,其他客户端永远获取不到锁。解决方法是用下面命令对key
设置过期时间:
SET key value [EX seconds] [PX milliseconds] NX
8.1.2 客户端2误删除了锁
解决方法是对key
设置value
时加入一个客户端表示,比如在客户端1
设置key
时在value
前拼接一个字符串application1
,删除的时候做一下判断。
8.2.redis红锁
redis
单节点会有可靠性问题,节点故障后锁操作就会失败。redis
为了应对单点故障的问题,设计了多节点的分布式锁,也叫红锁。主要思想是客户端跟多个redis
实例请求加锁,只有超过半数的实例加锁成功,才认为成功获取了分布式锁。
如下图,客户端分别跟3个实例请求加锁,有2个实例加锁成功,所以获取分布式锁成功:
9 缓存雪崩、击穿、穿透
9.1.缓存雪崩
redis
做缓存时,如果同一时间大量缓存数据失效,客户端请求会大量发送到数据库,导致数据库压力激增。如下图:
「应对方法主要有3个:」
- 给key设置过期时间时加一个小的随机数
- 限流
- 服务降级
9.2.缓存击穿
某个热点key
,突然过期了,大量请求发送到了数据库。解决方案是给热点key
不设置过期时间。
9.3.缓存穿透
某个热点key
,查询缓存和查询数据库都没有,就发生了缓存穿透。如下图:
「应对方法主要有2个:」
- 缓存热点的空值和缺省值
- 查询数据库之前先查询布隆过滤器
10 数据倾斜
什么是数据倾斜?看下面这个面试题:
❝如果
❞redis
有一个热点key
,qps
能达到100w
,该如何存储?
如果这个热点key
被放到一个redis
实例上,这个实例面临的访问压力会非常大。如下图,redis3
这个实例保存了foo
这个热点key
,访问压力会很大:
「解决方法主要有两个:」
1.使用客户端本地缓存来缓存key
,这样改造会有两个问题:
- 客户端缓存的热点
key
可能消耗大量内存 - 客户端需要保证本地缓存和
redis
缓存的一致性
2.给热点key
加一个随机前缀,让它保存到不同的redis
实例上,这样也会存在两个问题:
- 客户端在访问的时候需要给这个
key
加前缀 - 客户端在删除的时候需要根据所有前缀来删除不同实例上保存的这个
key
11 bitmap使用
❝有一道经典的面试题,
❞10
亿整数怎么在内存中去重排序?
我们先算一下10
亿整数占的内存,java
一个整数类型占四字节,占用内存大小约
10亿 * 4 / 1024 / 1024 = 3.7G
占得内存太大了,如果内存不够,怎么办呢?
11.1.bitmap介绍
bitmap
类型使用的数据结构是String
,底层存储格式是二进制的bit
数组。假如我们有1、4、6、9
四个数,保存在bit
数组中如下图:
在这个bit
数组中用10
个bit
的空间保存了四个整数,占用空间非常小。
再回到面试题,我们使用bit
数组长度是10
亿整数中 「(最大值 - 最小值 + 1)」。
❝如果有负数,需要进行一个转化,所有数字加最小负数的绝对值。比如
❞{-2, 0, 1, 3}
,我们转换成{0, 2, 3, 5}
,因为数组下标必须从0开始
11.2.使用场景
11.2.1.员工打卡记录
在一个有100
个员工的公司,要统计一个月内员工全勤的人数,可以每天创建一个bitmap
,签到的员工bit
位置为1
。
要统计当天签到的员工只要用BITCOUNT
命令就可以。
要统计当月全勤的员工,只要对当月每天的bitmap
做交集运算就可以,命令如下:
BITOP AND srckey1 srckey2 srckey3 ... srckey30
❝❞
srckeyN
表示第N
天的打卡记录bitmap
11.2.2.统计网站日活跃用户
比如网站有10
万个用户,这样我们创建一个长度为10
万的bitmap
,每个用户id
占一个位,如果用户登录,就把bit
位置为1
,日终的时候用BITCOUNT
命令统计出当天登录过的用户总数。