Redis基础

Redis

面经整理，主要是理论知识

Redis基本数据类型

key是字符串，value是5种：String、List、Hash、Set、Zset

String：是SDS(Simple Dynamic String)，动态字符串，可修改，最长512M。

扩展：为什么不用c语言的字符串？Redis如何解决

多增加了字符串长度属性len：c语音中的字符串末尾有’\0’，并且获取长度是O(N)级别的。SDS只需O(1)

自动扩展空间：由于字符串经常会进行拼接操作，所以没有提取获取长度，可能会造成缓存区溢出。当 SDS 需要对字符串进行修改时，首先借助于 len 和 alloc 检查空间是否满足修改所需的要求，如果空间不够的话，SDS 会自动扩展空间，避免了像 C 字符串操作中的覆盖情况；

有效降低内存分配次数：SDS优化了修改字符串带来的内存重分配的次数，采用空间预分配(会分配多余的free空间)和惰性空间释放(缩减字符串后不会马上释放空间)

二进制安全：因为存了长度，不用去判断空字符\0

List：相当于Java的LinkedList，插入删除O(1)，索引定位O(n)

lrange：输出list指定范围的元素lrange mylist 0 -1

Hash：数组+链表解决哈希冲突，实际上字典结构内部包含两个HashTable，用于扩容时的渐进式搬迁。当hash表中的元素个数等于第一位数组的长度时，扩容为原数组的两倍。如果Redis正在做 bgsave(持久化命令)，为了减少内存也得过多分离，Redis 尽量不去扩容，但是如果 hash 表非常满了，达到了第一维数组长度的 5 倍了，这个时候就会 强制扩容。

当 hash 表因为元素逐渐被删除变得越来越稀疏时，Redis 会对 hash 表进行缩容来减少 hash 表的第一维数组空间占用。所用的条件是 元素个数低于数组长度的 10%，缩容不会考虑 Redis 是否在做 bgsave。

渐进式rehash：大字典扩容需要申请新数组，并将原数组所有元素重新挂接到新数组中，由于单线程，所以采用渐进式rehash，这会在rehash的过程中，保留新旧两个hash结构，查询时同时查两个，当全部迁移完成后，使用新的hash结构取而代之

Set：无序、唯一。

Redis的zset的底层数据结构？

zset：唯一性，并为每个value赋予一个score值，代表排序权重

跳跃表：有序列表zset的数据结构，链表按照score排序，链表分层，上层的链表树约为下层的1/2，查询的时候从上层开始查，查询效率O(logN)

为什么不用红黑树/平衡树？性能和实现考虑

插入节点，根据随机算法来分配合理的层数，从期望上来看，50%的概率被分到第一层，25%的概率被分到第二层，1/4第三层…

跳表默认最大的层数为32层

插入的大致流程：声明存储变量、搜索当前节点插入的位置、生成插入节点、重排前向指针、重排后向指针并返回

元素排名：跳跃表在前向指针上增加了一个span属性，用来表示从前一个节点沿着当前层的forward指针跳到当前节点中间跳过了多少节点。因此可以沿着搜索路径，将所有经过的节点的跨度span值加起来就能得到最终的rank值

扩展：

Bitmap：布隆过滤器

HyperLogLog：不精确的去重计数功能，适合大规模去重统计

Geospatial：保存地理位置

pub/sub：订阅功能，简单的消息队列

Pipeline：批量执行一组指令，一次性返回结果，可以减少频繁的请求应答

Lua：支持Lua脚本执行一系列的功能。具有原子性

事务：只保证串行执行命令，并保证全部执行，但执行命令失败不会回滚，而是继续执行

Redis 和 Memcached 的区别和共同点

MC：多线程异步IO，只支持K-V，最大失效时间30天，key和value大小有限制

Redis：单线程，采用非阻塞的异步事件处理机制，避免线程上下文切换的代价；支持持久化；支持多种数据结构；主从同步机制、集群

Redis如何支持高并发

主从架构 + 读写分离

一主多从，主负责写，并负责将数据同步到其他slave节点上，从负责读

为什么Redis用单线程而不是多线程

https://draveness.me/whys-the-design-redis-single-thread

CPU不是Redis的瓶颈，Redis的瓶颈是内存大小和网络带宽，数据都在内存中

单线程带来更高的可维护性，方便开发

单线程也可以并发处理客户端请求，IO多路复用

4.0后引入多线程？只是在部分命令上引入(多个非阻塞的删除操作)，在整体架构上还是单线程模型

Redis的事务是怎么实现的

redis事务是通过multi,exec,discard,watch/unwatch指令用来操作事务。

mutil：开启事务，此后所有的操作将会添加到当前链接的事务“操作队列”中。
exec：提交事务
discard：取消事务，记住，此指令不是严格意义上的“事务回滚”，只是表达了“事务操作被取消”的语义，将会导致事务的操作队列中的操作不会被执行，且事务关闭。
watch/unwatch：“观察”，被watch的key如果被其他客户端修改，会discard；事务执行成功或discard会导致被watch的key变为unwatch

这里的watch其实实现了一个CAS乐观锁，只有被watch的key没有改变时，才会exec执行事务

原理：EXEC指令将会触发事务中所有的操作被写入AOF文件（如果开启了AOF），然后开始在内存中实施这些数据变更操作
如果在EXEC指令被提交之前，Redis-server即检测到提交的某个指令存在语法错误，那么此事务将会被提前标记DISCARD，此后事务提交也将直接被驳回；但是如果在EXEC提交后，在实施数据变更时（Redis将不会预检测数据类型，比如你对一个“非数字”类型的key执行INCR操作），某个操作导致了ERROR，那么redis仍然不会回滚此前已经执行成功的操作，而且也不会中断ERROR之后的其他操作继续执行。

对于开发者而言，你务必关注事务执行后返回的结果（结果将是一个集合，按照操作提交的顺序排列，对于执行失败的操作，结果将是一个ERROR）。

缓存的更新方式

可以在更新完DB后直接更新缓存；设置失效时间，可以看做数据不一致的最大容忍时间，可以在key失效时请求数据源获取新数据，重置失效时间；失效时，异步更新，防止数据源更新时出错

缓存一致性问题

先删除缓存，后更新数据库

如果删除缓存后，更新数据库的过程中，有线程进行读，缓存被删了，读数据库，读到旧数据，写入缓存，不一致

解决：延时双删：更新数据库的线程在更新完后，sleep一段时间，然后再删除一次缓存
先更新数据库，再删除缓存

如果更新成功，缓存删除失败，不一致

解决：通过消息队列，利用消息队列的重试机制，保证消息的最终一致性
其他：设置缓存过期时间。

如果在更新Redis时服务器宕机，怎么办？

持久化、主从、

Redis的部署架构是什么样的？

单机、主从、集群

Redis内存淘汰机制、几种淘汰策略

设置有效期

删除过期键的策略：定时删除、惰性删除、定时扫描

定时删除 ：为每个键设置一个定时器，一旦过期时间到了，则将键删除。这种策略对内存很友好，但是对 CPU 不友好，因为每个定时器都会占用一定的 CPU 资源。
惰性删除 ：不管键有没有过期都不主动删除，等到每次去获取键时再判断是否过期，如果过期就删除该键，否则返回键对应的值。这种策略对内存不够友好，可能会浪费很多内存。
定期扫描 ：系统每隔一段时间就定期扫描一次，发现过期的键就进行删除。这种策略相对来说是上面两种策略的折中方案，需要注意的是这个定期的频率要结合实际情况掌控好，使用这种方案有一个缺陷就是可能会出现已经过期的键也被返回。

淘汰没过期键的策略

淘汰策略	说明
volatile-lru	根据 LRU 算法删除设置了过期时间的键，直到腾出可用空间。如果没有可删除的键对象，且内存还是不够用时，则报错
allkeys-lru	根据 LRU 算法删除所有的键，直到腾出可用空间。如果没有可删除的键对象，且内存还是不够用时，则报错
volatile-lfu	根据 LFU 算法删除设置了过期时间的键，直到腾出可用空间。如果没有可删除的键对象，且内存还是不够用时，则报错
allkeys-lfu	根据 LFU 算法删除所有的键，直到腾出可用空间。如果没有可删除的键对象，且内存还是不够用时，则报错
volatile-random	随机删除设置了过期时间的键，直到腾出可用空间。如果没有可删除的键对象，且内存还是不够用时，则报错
allkeys-random	随机删除所有键，直到腾出可用空间。如果没有可删除的键对象，且内存还是不够用时，则报错
volatile-ttl	根据键值对象的 ttl 属性，删除最近将要过期数据。如果没有，则直接报错
noeviction	默认策略，不作任何处理，直接报错

衍生：Redis对LRU算法的改进，解决传统LRU的什么缺点？怎么改进的？抽样删除

Redis热度数据管理：LRU：lru属性24位、全局属性lru_clock；LFU：lru属性高16位时钟低8位频数、频次递增(随机数、概率p公式、对数因子)、频次递减(lfu-decay-time、计算差值、除以lfu-decay-time)

Redis缓存穿透和缓存雪崩？

缓存雪崩：Redis中的缓存大面积失效，所有的流量直接打在数据库上，数据库亚历山大啊

解决方案：在往Redis中存数据的时候，设置随机的失效时间；或者考虑热点数据永不失效，有更新操作的时候更新一下缓存

缓存穿透：缓存和数据库都没有的数据，而某个不良用户不断地发起请求，比如数据库中的id都大于0，我一直用小于0的id去请求，每次都能避开Redis，直接打在数据库上，造成数据库压力过大

解决方案1：在接口层增加校验，如用户权限校验、参数校验、不合法的直接返回Null给前端。比如id校验id<=0直接拦截。

解决方案2：缓存和数据库都取不到的key，可以将对应key的value设置为null、错误提示等，具体看场景，设置个失效时间30秒。

解决方案3：布隆过滤器

缓存击穿：是指某个热点key，不停地扛着大并发，当这个key失效的瞬间，持续的大并发就会击穿缓存，直接请求数据库。

解决方案：设置热点数据永不过期，数据有更新时，同时更新缓存即可

总结：上述三个问题，之前：Redis高可用，主从+哨兵，Redis集群，避免全盘崩溃

若还是发生了上述问题，采用本地缓存、限流、降级等方法，避免MySQL挂掉

发生问题之后，Redis持久化RDB+AOF，一旦重启，自动从磁盘加载数据，快速恢复缓存数据

哪怕限流，也不能让数据库挂掉，对用户来说多刷几次而已~

布隆过滤器

概念：用于检索一个元素是否在一个集合中。

原理：当元素被加入集合时，通过k个散列函数将这个元素映射成一个位(bit)数组中的k个点，把他们置成1。检索时，只要看对应的这些点是否为1，就大概率知道该集合中是否有该元素。

缺点：有可能误判，可能元素不在集合中，但k个bit位都为1；删除困难

Redis持久化的方式

两种持久化方式：RDB和AOF

RDB

快照是一次全量备份，快照作为包含整个数据集的单个.rdb文件生成，快照是内存数据的二进制序列化形式，在存储上非常紧凑。

使用系统多进程COW(Copy On Write)机制的fork函数，产生一个子进程，子进程会拷贝父进程的部分代码段和数据段，快照持久化可以完全由子进程完成，父进程继续处理客户端请求。数据段由操作系统的页面组合而成，主进程在对某个页面进行修改时，会得到该页面的一份复制，然后在复制页上进行修改，而子进程相应的页面是没有变化的，子进程只需要遍历数据进行序列化写磁盘就行了。

触发机制：手动、自动

自动触发：

在配置文件中设置触发条件

# 当在规定的时间内，Redis发生了写操作的个数满足条件，会触发发生BGSAVE命令。
# save <seconds> <changes>
# 当用户设置了多个save的选项配置，只要其中任一条满足，Redis都会触发一次BGSAVE操作
save 900 1 
save 300 10 
save 60 10000
# 以上配置的含义：900秒之内至少一次写操作、300秒之内至少发生10次写操作、
# 60秒之内发生至少10000次写操作，只要满足任一条件，均会触发bgsave

执行shutdown命令关闭服务器时，如果没有开启AOF，则会自动执行一次bgsave
主从同步：master执行bgsave，并缓存该时间段的写操作，将rdb发送给slave，slave同步数据，最后master向所有slave发送缓存中的写操作，完成同步

执行流程：使用操作系统多进程的COW机制

执行bgsave时，先看有不有子进程正在执行RDB/AOF持久化任务，有则返回
主进程fork一个子进程来执行RDF，fork操作会对主进程造成阻塞，只是fork期间阻塞，之后就不阻塞了
子进程根据主进程的内存生成临时快照文件，持久化完成后用临时快照文件替换原来的RDF文件。此过程主进程仍然可以响应写操作，但是是在内存页面的副本进行，不会影响子进程持久化工作
子进程完成后发消息给主进程

RDB的优缺点

优点

RDB文件小，适合定时备份，用于容灾
Redis加载RDB文件速度比AOF日志快很多，因为RDB存的是内存中的数据，而AOF日志记录的是指令，需要顺序执行所有指令来恢复

缺点

无法实时持久化，两次bgsave过程中的数据可能丢失
fork子进程会阻塞Redis主进程
老版本的Redis可能不兼容新版本RDB格式文件

AOF

Append Only File，仅追加文件，AOF 日志是连续的增量备份。每次执行修改内存中数据集的写操作时，都会记录该操作。假设AOF记录了自Redis实例创建以来所有的修改性指令，那么就可以通过对一个空的Redis实例顺序执行所有指令，即重放，来恢复Redis当前实例的内存数据结构的状态

AOF会在持续运行中持续增大，因此需要定期进行AOF重写，对AOF日志进行瘦身

开启方式

## 此选项为aof功能的开关，默认为“no”，可以通过“yes”来开启aof功能  
## 只有在“yes”下，aof重写/文件同步等特性才会生效  
appendonly yes  

## 指定aof文件名称  
appendfilename appendonly.aof  

## 指定aof操作中文件同步策略，有三个合法值：always everysec no,默认为everysec  
appendfsync everysec  
## 在aof-rewrite期间，appendfsync是否暂缓文件同步，"no"表示“不暂缓”，“yes”表示“暂缓”，默认为“no”  
no-appendfsync-on-rewrite no  

## aof文件rewrite触发的最小文件尺寸(mb,gb),只有大于此aof文件大于此尺寸是才会触发rewrite，默认“64mb”，建议“512mb”  
auto-aof-rewrite-min-size 64mb  

## 相对于“上一次”rewrite，本次rewrite触发时aof文件应该增长的百分比  
## 每一次rewrite之后，redis都会记录下此时“新aof”文件的大小(例如A)
## aof文件增长到A*(1 + p)之后，触发下一次rewrite，每一次aof记录的添加，都会检测当前aof文件的尺寸。  
auto-aof-rewrite-percentage 100

Linux对文件采用延迟写入，即每次写入先进缓存，到了已定时机再写入磁盘。

Linux提供了fsync(int fd)函数，可以将指定文件的内容强制从内核缓存刷到磁盘，但是是一个磁盘IO操作，非常耗时。因此Redis提供了3种AOF同步策略：

always：每条AOF都立即同步，性能低，安全
everysec：每秒同步，默认的方式，性能安全较平衡
no：永不直接同步，全由操作系统决定。性能好但非常不安全

重写(Rewrite)机制

不是基于源AOF文件，而是基于当前内存数据，类似于RDB快照的方式，使用更少的指令来记录内存中数据的状态。先存当前内存状态，再将重写期间的写操作从缓存写入AOF。

触发机制：手动和自动

手动：bgrewriteaof命令：redis-cli -h ip -p port bgrewriteaof

自动

1
2
3

auto-aof-rewrite-min-size:表示运行AOF重写时文件最小体积，默认为64MB（我们线上是512MB）。

auto-aof-rewrite-percentage:代表当前AOF文件空间（aof_current_size）和上一次重写后AOF文件空间（aof_base_size）

AOF的优缺点

优点：只是追加写日志，写增量信息，对服务器性能影响小，速度比RDB快，内存消耗少

缺点

日志文件太大，需要不断重写瘦身，但和RDB文件比还是很大
使用AOF恢复数据时，比RDB慢

Redis4.0混合持久化

RDB文件和AOF日志结合，AOF日志记录自RDB持久化开始到当前这段时间发生的增量数据。

大量数据使用RDB，性能高，恢复快；增量数据使用AOF，尽量保证数据不丢失

Redis主从复制怎么实现的

作用

数据冗余：主从复制实现数据的热备份
故障恢复：主节点挂了，从节点可以提供服务，实现快速故障恢复
负载均衡：主从复制、读写分离，主提供写，从提供读

实现原理

准备阶段 - > 数据同步阶段 - > 命令传播阶段

slave第一次连接到master时，master会启动子进程生成RDB快照，并把过程中的写请求存到缓存，RDB文件生成后，将RDB文件发给slave，并把缓存中的写操作也发给slave

之后的数据通过AOF日志同步

Redis中的哨兵是干啥的

架构

哨兵节点：哨兵系统由一个或多个哨兵节点组成，不存储数据

数据节点：主、从都是数据节点

功能

监控（Monitoring）： 哨兵会不断地检查主节点和从节点是否运作正常。
自动故障转移（Automatic failover）： 当 主节点 不能正常工作时，哨兵会开始 自动故障转移操作，它会将失效主节点的其中一个 从节点升级为新的主节点，并让其他从节点改为复制新的主节点。
1. 在失效主服务器属下的从服务器当中，那些被标记为主观下线、已断线、或者最后一次回复 PING 命令的时间大于五秒钟的从服务器都会被淘汰。
2. 在失效主服务器属下的从服务器当中，那些与失效主服务器连接断开的时长超过 down-after 选项指定的时长十倍的从服务器都会被淘汰。
3. 在 经历了以上两轮淘汰之后 剩下来的从服务器中，我们选出 复制偏移量（replication offset）最大 的那个 从服务器 作为新的主服务器；如果复制偏移量不可用，或者从服务器的复制偏移量相同，那么 带有最小运行 ID 的那个从服务器成为新的主服务器。
配置提供者（Configuration provider）： 客户端在初始化时，通过连接哨兵来获得当前 Redis 服务的主节点地址。
通知（Notification）： 哨兵可以将故障转移的结果发送给客户端。

为什么Redis的负载因子设置比HashMap的负载因子大

Redis的负载因子是键值对的数量/长度，HashMap是已使用的数量/长度

Redis的分布式锁？

最低保证分布式锁的有效性及安全性的要求如下：

1.互斥；任何时刻只能有一个client获取锁

2.释放死锁；即使锁定资源的服务崩溃或者分区，仍然能释放锁

3.容错性；只要多数redis节点（一半以上）在使用，client就可以获取和释放锁

问题

因为redis在进行主从复制时是异步完成的，比如在clientA获取锁后，主redis复制数据到从redis过程中崩溃了，导致没有复制到从redis中，然后从redis选举出一个升级为主redis,造成新的主redis没有clientA 设置的锁，这是clientB尝试获取锁，并且能够成功获取锁，导致互斥失效；

Redis分布式锁的实现

单实例中的实现：SET key_name value_name NX PX 30000保证原子性

NX 表示if not exist 就设置并返回True，否则不设置并返回False PX 表示过期时间用毫秒级， 30000 表示这些毫秒时间后此key过期

获取失败则等待一段时间重试(大于ttl)或退出

获取锁，完成相关操作后，必须删除自己的锁。这里获取和删除都是用lua脚本，保证操作的原子性

多节点Redis实现(RedLock)：有效防止单点故障

1.获取当前时间戳

2.client尝试按照顺序使用相同的key,value获取所有redis服务的锁，在获取锁的过程中的获取时间比锁过期时间短很多，这是为了不要过长时间等待已经关闭的redis服务。并且试着获取下一个redis实例。

比如：TTL为5s,设置获取锁最多用1s，所以如果一秒内无法获取锁，就放弃获取这个锁，从而尝试获取下个锁

3.client通过获取所有能获取的锁后的时间减去第一步的时间，这个时间差要小于TTL时间并且至少有3个redis实例成功获取锁，才算真正的获取锁成功

4.如果成功获取锁，则锁的真正有效时间是 TTL减去第三步的时间差的时间；比如：TTL 是5s,获取所有锁用了2s,则真正锁有效时间为3s(其实应该再减去时钟漂移);

5.如果客户端由于某些原因获取锁失败，便会开始解锁所有redis实例；因为可能已经获取了小于3个锁，必须释放，否则影响其他client获取锁

Redis包含的模块

Redis为什么快？

纯内存操作
单线程，没有各自乱七八糟的锁
多路IO复用模型，底层有很多优化
高效的数据结构：如不同长度的字符串用了不同的结构体、HyperLogLog的密集型存储结构等

Redis的HyperLogLog

HyperLogLog是一种估计基数的近似最优算法。基数统计：用来统计一个集合中不重复的元素个数，比如统计网站每个页面的UV(独立访客)

大致的原理：一个随机数，尾部有1个0的概率为1/2，两个0的概率为1/4，…，尾部k个0的概率为 $2^{-k}$ 。因此我们可以通过尾部连续0的最大数量k，估算出我们用了多少个随机数。HyperLogLog通过分配若干桶( $2^{14}$ =26384)，对每个桶得到的最大数量k进行调和平均，得到一个k#，k#为一个浮点数。具体还有很多修正因子，比较复杂

占用内存仅12KB， $2^{14}$ 个桶，每个6bit， $2^{14}*\frac68$

Redis的实现：计数量小的时候，转换成稀疏存储方式；否则采用密集存储。最大限度节约内存

密集存储：16384个6bit连续成串，8bit 1字节，需要一些移位拼接的处理

稀疏存储：当某个计数值需要调整到大于32时，会转换为密集存储

00开头表示后6位整数值加1就是零值计数器的数量
01后14bit最多可以表示连续16384个零值计数器
1vvvvvxx：中间5bit计数，后2bit表示连续几个桶

指令：pfadd和pfcount

https://mp.weixin.qq.com/s/9dtGe3d_mbbxW5FpVPDNow

https://cloud.tencent.com/developer/article/1349691

假如Redis里面有1亿个key，其中有10w个key是以某个固定的已知的前缀开头的，如何将它们全部找出来？

使用 keys 指令可以扫出指定模式的 key 列表。但是要注意 keys 指令会导致线程阻塞一段时间，线上服务会停顿，直到指令执行完毕，服务才能恢复。这个时候可以使用 scan 指令，scan 指令可以无阻塞的提取出指定模式的 key 列表，但是会有一定的重复概率，在客户端做一次去重就可以了，但是整体所花费的时间会比直接用 keys 指令长。