数据结构

Redis常见的数据结构

• String：缓存对象
• Hash：缓存对象、购物车
• List：消息队列
• Set：点赞、共同关注
• ZSet：排序

Zset底层？

Zset底层的数据结构是由压缩链表或跳表实现的

• 如果有序集合的元素 < 128，并且每个元素 < 64字节时，会用压缩列表作为Zset类型的底层数据结构
• 如果有序集合的元素不满足上面的条件，会用跳表作为Zset类型的底层数据结构

跳表是怎么实现的？

跳表在创建节点时，随机生成每个节点的层数。

跳表在创建节点时，先生成[0, 1]的随机数，如果随机数 < 0.25，层数就会增加一层；然后继续生成下一个随机数，直到随机数 > 0.25结束，最终确定该节点的层数

为什么Zset使用跳表而不是B+树？

1. B+树的设计目标是优化磁盘，通过减少树的高度来降低磁盘寻道次数；跳表是基于链表，通过多级索引加速查询，内存访问模式更符合CPU缓存局部性。Redis是内存数据库，数据完全存储在内存中，不需要优化磁盘IO，B+树的磁盘特性对Redis意义不大，跳表的设计更优
2. 跳表相比B+树实现起来更简单，B+树插入和删除可能需要触发节点的分裂和合并，跳表插入时只需要随机生成层高，删除时直接移除节点并调整指针即可。
3. B+树每个节点需要存储多个键值和叶子节点，存在内存碎片；跳表每个节点只需要存储键值、层高、多个前向指针，内存占用更紧凑。

压缩列表是怎么实现的?

压缩列表是由连续内存块组成的顺序型数据结构，类似数组。

• 查找第一个元素和最后一个元素时间复杂度：O(1)
• 查找其他元素：只能逐个查找，复杂度O(n)

压缩列表的缺点：会发生连锁更新，导致压缩列表占用的内存空间要多次重新分配，这回直接影响到压缩列表的访问性能。

压缩列表只适合保存数据量不多的场景。

quicklist和listpack这两种数据结构就是为了尽可能地保持压缩列表节省内存的优势

哈希表怎么扩容的？

在正常服务请求阶段，插入的数据都会写到哈希表1中，此时哈希表2没有被分配空间，随着数据量的增多，触发了rehash操作：

1. 给哈希表2分配空间，一般比哈希表1大2倍
2. 将哈希表1的数据移动到哈希表2中
3. 迁移完成后，把哈希表1的空间释放，并把哈希表2设置为哈希表1，在哈希表1新创建一个空白的哈希表，为下次rehash做准备。

存在问题：如果哈希表1非常大，那么每次迁移到哈希表2的时候，可能会对redis造成阻塞，无法响应其他请求。

解决：在rehash进行期间，每次进行新增、删除、查找操作，redis除了操作哈希表1，还会操作redis2，这样就把一次大量数据的迁移工作分摊到了多个请求中。

注：哈希表扩容时，如果来了一个读请求，会现在哈希表1里查找；如果没找到，才会到哈希表2里查找。

String是用什么存储的？为什么不用c语言的字符串？

redis中的string字符串使用SDS数据结构存储的，SDS结构如下：

• len：记录了字符串的长度
• alloc：分配给字节数组的空间长度
• flags：用来表示不同类型的SDS（sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64）
• buf[]：字符数组，用来保存实际数据

SDS数据结构可以O(1)获取字符串长度，c语言的字符串需要O(n)

SDS不需要"\0"来表示字符串结尾，有个len来记录字符串的长度（但是她为了兼容部分c的库函数，还是加了"\0"）

C语言的字符串在追加的时候是不安全的，程序内部不会判断缓冲区大小是否够用，当缓冲区发生溢出后会导致程序异常；SDS结构里加入alloc和len，这样可以通过alloc - len来判断剩余缓冲区的大小，当缓冲区大小不够用时，redis会自动扩大SDS的空间大小。

线程模型

Redis为什么快？

单线程的redis吞吐量可以达到10w/s

1. Redis大部分的操作都在内存中完成的，redis的瓶颈可能是机器的内存或网络带宽而非CPU
2. Redis采用单线程模型可以避免多线程之间的竞争，省去了多线程切换带来的开销
3. Redis采用IO多路复用机制处理大量客户端的Socket请求，在只运行单线程的情况下，该机制允许内核同时存在多个监听Socket和已连接Socket。

Redis的单线程指的是”接收客户端请求 -> 解析请求 -> 进行读写数据操作 -> 发送数据给客户端“这个过程是一个线程完成的，但是Redis程序不是单线程的，Redis在启动时，会启动后台线程

关闭文件、AOF刷盘、释放内存这些任务会创建单独的线程来处理，如果放在主线程来处理，Redis主线程就会发生阻塞。

Redis6也采用多个IO线程来处理网络请求，因为随着硬件的升级，Redis的性能瓶颈出现在网络IO的处理上

Redis怎么实现IO多路复用

因为Redis是单线程的，所有的操作都是按顺序进行，由于读写操作等待用户的输入和输出都是阻塞的，IO多路复用就是为了单线程的服务同时处理多个客户端的请求。

多路：指多个网络连接客户端

复用：指复用同一个进程

IO多路复用是使用一个线程来检查多个Socket的就绪状态，在单个线程中通过记录跟踪每个Socket的状态来管理处理多个IO流

日志

Redis的持久化方式？

Redis的读写操作都是发生在内存的，但是redis重启后，内存中的数据就会丢失，为了保证内存中的数据不丢失，就需要持久化机制，把数据存储到磁盘，这样Redis重启后就能从磁盘中恢复数据，Redis主要有两种持久化方式，分别是：

1. AOF日志：每执行一条写操作，就会把该命令以追加的方式写入文件中，redis重启时，会逐一执行这个文件里的命令将数据恢复。redis由三种写回磁盘的策略：

   • Always：每次写操作命令执行完后，同步将AOF日志数据写回磁盘
   • Everysec：每次写操作命令执行完后，先将命令写到缓冲区中，再每隔一秒将数据写回磁盘
   • No：Redis不控制写回磁盘的时机，交给操作系统控制，每次写操作后先将命令写到缓冲区，由操作系统决定何时将命令写回磁盘。

2. RDB快照：RDB快照只记录一瞬间的内存数据，记录的是实际的数据。Redis有两个命令来生成RDB快照：

   • save命令：在主线程中生成RDB文件（会阻塞主线程）
   • bgsave命令：创建一个子线程来生成RDB文件（避免阻塞主线程）

AOF日志记录的是操作命令，用AOF做故障恢复时，需要全量把日志全部执行一遍，一旦AOF日志非常多，会造成Redis恢复操作慢。所以引入了RDB快照（记录一瞬间的内存数据，记录的是实际数据，AOF文件记录的是命令操作的日志，而不是实际数据）

内存淘汰和过期删除

内存淘汰和过期删除的区别？

内存淘汰是在内存满时会触发内存淘汰策略来淘汰一些不必要的资源

过期删除是将已过期的键值对进行删除

内存淘汰策略有哪些？

内存淘汰：当Redis内存达到设置的阈值时，Redis就会主动挑选部分key删除以释放更多的内存。

Redis在每次处理客户端命令时，都会对内存使用情况判断，如果必要，则执行内存淘汰。内存淘汰的策略有：

1. 前缀：
   • allkeys：对所有的key进行淘汰，从dict的哈希表中挑选
   • volatile：只对设置了TTL的key进行淘汰，从expires的哈希表中挑选
2. 后缀：
   • ttl：淘汰ttl小的
   • random：随机挑选
   • lru：基于LRU算法
   • lfu：基于LFU算法

过期删除策略？

redis的失效缓存不会立即删除，而是使用惰性删除 + 定期删除这两种策略配合

1. 惰性删除：在访问或修改key时，判断key是否过期，如果过期就删除key；如果没有过期，就不做处理，返回正常的键值对
2. 定期删除：每隔一段时间随机从数据库中取出一部分key进行检查，删除过期的key，如果过期的key≥选举的key的四分之一，则再次选取，直到＜四分之一，这个过程可能会很长时间，所以需要设置循环的上限。

集群

Redis主从同步

1. 全量同步：以下情况会发生全量同步

   • 主从集群首次建立连接
   • 从服务器断开连接时间过长

   步骤：

   1. 从服务器发送SYNC命令，开始请求同步
   2. 主服务器收到SYNC命令后，生成RDB快照，并将生成的RDB文件发送到从服务器中
   3. 从服务器收到RDB文件后，先清空当前的数据集，并载入RDB文件中的数据
   4. 在RDB文件传输的过程中，如果又有新的指令，主服务器会将新的指令先放在缓冲区中，一旦RDB文件传输完成，主服务器又会将缓冲区里的命令发给从服务器，保证数据的一致性。

2. 增量同步：允许从服务器从断点处继续同步

   步骤：

   1. 从服务器在网络恢复后，发送psync命令
   2. 主服务器收到psync命令后，告诉从服务器接下来要用增量同步的方式同步数据
   3. 主服务器将从服务器断开这段时间内执行的命令，发送给从服务器。

   （断开这段时间内执行的命令会存在主服务器的环形缓冲区中，主要存放的是最近传播的写命令，如果缓冲区里的一部分数据还没同步给从服务器，就已经被覆盖了，主服务器就会再次采取全量同步）

哨兵机制的原理？

redis的主从集群中，主从模式是读写分离的，如果主节点挂了，需要选择一个主节点变成从节点，如果没有哨兵机制，那么只能人工选择一个主节点变成从节点，还要通知其他从节点现在主节点的变更。

哨兵机制主要是实现了主从节点的故障转移，他会检测主节点是否存活，如果主节点挂了，就会选取一个从节点当成主节点，并且把新的主节点信息通知给其他的从节点。

哨兵机制选择主节点的算法？

1. 故障节点主观下线：哨兵节点会定时对redis集群里的所有节点发送心跳包检测节点是否正常，如果一个节点没有恢复哨兵节点的心跳包，则认为该节点主观下线

2. 故障节点客观下线：当一个节点被标记成故障，不代表这个节点下线了，但是如果哨兵集群中有超过quorum数量的哨兵节点认为该redis节点主观下线，则该redis客观下线

   如果下线的redis节点是从节点或哨兵节点，则没有后续操作了；如果是主节点，则开始故障转移，从剩下的从节点中选出一个节点升级为主节点

3. 哨兵集群中选择Leader：要从redis集群中选择一个节点变成主节点，必须先从哨兵节点中选取leader，一个哨兵节点至少要拿到quorunm个赞成票，才能成为Leader

4. 哨兵Leader选择新主节点：哨兵Leader从redis从节点中选择一个redis节点作为主节点

   • 首先判断slave节点与master节点断开时间长短，如果超过指定值（down-after-milliseconds * 10）则会排除该slave节点。
   • 然后判断slave节点的slave-priority值，值越小优先级越高。（如果是0则用不参与选举，默认是0）
   • 如果slave-priority一样，则判断slave节点的offset值，越大说明数据越新，优先级越高。
   • 最后是判断slave节点的运行id大小，越小优先级越高。

Redis集群的模式？

Redis缓存数据量大到一台服务器无法缓存时，就需要使用Redis切片集群，将数据分布在不同的服务器上，降低对单主节点的依赖。

一个切片有16384个哈希插槽，这些哈希插槽类似数据分区，根据他的key被映射到一个哈希槽中。

场景

为什么使用Redis

1. Redis具备高性能：如果用户第一次访问Mysql中的某些数据，这个过程比较慢，因为是从磁盘上读取的；如果将该用户的数据缓存在Redis中，下次在访问这些数据的时候就可以直接从Redis中读取了，操作Redis缓存就是直接操作内存，速度快。【需要考虑Mysql和Redis中的数据一致性】
2. Redis具备高并发：单台Redis的QPS是Mysql的10倍，所以访问Redis能承受的请求远远大于Mysql，因此可以考虑将数据库中一部分数据缓存到Redis中，这样就不需要每次请求都到数据库中查了。

为什么Redis比Mysql快？

1. Redis是基于内存存储、Mysql是基于磁盘存储
2. Redis是基于键值对结构，支持简单的数据结构；Mysql需要定义表结构、索引等复杂的数据结构
3. Redis采用单线程可以避免多线程之间的竞争，省去了多线程切换带来的开销。

本地缓存和分布式缓存的区别

本地缓存：将数据存储在本地应用程序或服务器上，用于加速数据访问，本地缓存通常是使用内存作为存储介质，利用内存的高速读写来提高访问速度。

本地缓存：由于本地缓存是存储在本地内存中，访问速度快，而且能够降低对远程服务器的访问次数；但是本地缓存的可扩展性收到硬件资源的限制，无法支持大规模的数据存储。

分布式缓存：将数据存储在多个分布式节点上，通过协同工作来提供高性能的数据访问服务，利用多台服务器来分担数据存储和访问的压力。

分布式缓存：节点可以动态扩展，能够支持大规模数据存储和访问的需求；但是相对本地缓存，分布式存储的访问速度相对慢，因为数据需要从多个节点进行访问，且需要通过网络进行数据传输。

Redis分布式锁的实现原理？

分布式锁是分布式环境下并发控制的一种机制，用来控制某个资源在同一时刻只能被一个应用使用。

Redis本身可以被多个客户端共享，可以用来保存分布式锁，而且Redis的读写性能高，可以应对高并发锁的场景。

redis的set命令有个nx参数可以实现”key不存在时插入“，所以可以使用它实现分布式锁：

• 如果key不存在，则表示插入成功（加锁成功）
• 如果key存在，则表示插入失败（加锁失败）

加锁的操作要注意：

1. 加锁包括了：读取锁变量、检查锁变量值、设置锁变量三个操作，需要以原子操作的方式完成，所以使用set命令要带上nx选项来实现加锁。
2. 锁变量需要设置过期时间，以免客户端拿到锁后发生异常，导致锁一直无法释放
3. 锁变量的值需要能够区分来自不同客户端的加锁操作。

大Key问题？

字符串类型的Key对应的Value值占用空间很大就是大Key问题

大Key问题会导致：内存占用过高，从而触发内存淘汰策略；大Key会占用大量内存，导致性能下降；会造成网络拥堵；会导致主从同步延迟

解决：

1. 对大Key进行拆分，将一个含有数万成员的hashkey拆分成多个hashkey；
2. 将不适用Redis的数据移到别的地方存储，并在Redis中异步删除这个数据

什么是热key？

一般是以key的请求频率来判断的，例如：

1. QPS集中在特定的key
2. 带宽使用率集中在特定的Key
3. CPU使用时间占比集中在特定的Key

解决：

1. 将对应的热ky进行复制并迁移到其他的数据分片，来解决单个数据分片的热key压力
2. 如果热key的产生来自读请求，可以使用读写分离架构来降低每个数据分片的读请求，也可以不断增加从节点。

怎么保证redis和mysql数据缓存的一致性？

1. 对于读数据，如果redis不命中，会先去数据库中查询后加载到redis中
2. 对于写数据，会更新数据库后去删除缓存

缓存系统就是CAP中的AP，通过牺牲强一致性来提高性能，如果需要数据库和缓存保持强一致性，就不适合用缓存。

缓存的过期时间设置是太短、太长都不好：

• 太短的话，请求可能会比较多的落在数据库上，就失去了缓存的意义
• 太长的话，缓存中的脏数据会让系统长时间处于一个延迟的状态，会浪费内存。

通过一些方案是可以达到最终一致性的（针对删除缓存异常的情况）：

1. 删除缓存重试策略（消息队列）：如果删除缓存失败，可以从消息队列中重新读取数据，然后再删除缓存；如果删除缓存成功，就要把数据从消息队列中移除，避免重复操作。
2. 订阅MySQL binlog，再操作缓存：正常操作是先更新数据库，再删除缓存，一旦数据库更新成功，就会产生一条变更日志记录再binlog里，我们通过订阅binlog日志，拿到要操作的数据，然后执行缓存删除。

缓存雪崩、缓存击穿、缓存穿透是什么？

• 缓存雪崩：大量缓存数据同时失效，或redis宕机，如果有大量的用户请求，都无法在redis中处理，于是请求直接访问数据库，造成数据库的压力，严重的会导致数据库宕机

  • 如果要给缓存设置过期时间，应该避免大量的数据设置同一个过期时间，可以在设置过期时间的时候给这些数据加上随机数，这样数据就不会在同一时间过期
  • 当业务线程在处理用户请求时，如果访问的数据不在redis里，就加个互斥锁，保证同一时间只能由一个请求来构建缓存（未能获取互斥锁的请求要么锁释放后重新读取缓存，要么返回空值或默认值），互斥锁一定要设置过期时间，不然一个请求拿到锁可能因为一些意外而阻塞，这时其他请求也一直拿不到锁。
  • 让缓存“永久有效”，将更新缓存的工作交给后台线程定时更新

• 缓存击穿：缓存中某个热点数据过期，大量的请求访问该热点数据，就无法从缓存中读取，直接访问数据库，数据库很容易被高并发的请求冲垮。

  • 当业务线程在处理用户请求时，如果访问的数据不在redis里，就加个互斥锁，保证同一时间只能由一个请求来构建缓存（未能获取互斥锁的请求要么锁释放后重新读取缓存，要么返回空值或默认值），互斥锁一定要设置过期时间，不然一个请求拿到锁可能因为一些意外而阻塞，这时其他请求也一直拿不到锁。
  • 不给热点数据设置过期时间，由后台异步更新缓存，或者在热点数据过期前，提前通知后台线程更新缓存

  缓存击穿可以理解成时缓存雪崩的一个子集，缓存雪崩指的是大量的key过期，而缓存击穿特指的是热点key过期。

• 缓存穿透：用户访问的数据即不在缓存中，也不在数据库中，导致请求在访问缓存时，发现缓存缺失，再去访问数据库，数据库也没有对应的数据，当有大量的这种请求到来，数据库的压力就会很大。

  • 在Api入口处判断要请求的参数是否合法，如果不合法直接返回错误，防止进一步去访问数据库和缓存
  • 可以争对查询的数据，在缓存中也设置一个空值或默认值，这样后续的请求就可以从缓存中获取空值或默认值返回给应用，而不会继续查询数据库
  • 布隆过滤器：在写入数据库数据时，先用布隆过滤器做个标记，在用户请求到来时，业务线程确认缓存失效后，可以通过查询布隆过滤器快速判断数据是否存在，不存在就不通过查询数据库来判断数据库来判断数据是否存在。即使发生了缓存穿透，大量的请求只会查询Redis和布隆过滤器，而不会查询数据库。

介绍一下布隆过滤器的原理

在写入数据库数据时，先用布隆过滤器做个标记。

请求过来会先经过布隆过滤器，布隆过滤器先判断数据库中是否存在这条数据，如果不存在，就会拒绝这个请求。

注意，布隆过滤器判断一个元素不存在时，它绝对不存在；但是如果它判断一个元素存在，这个元素可能会不存在。

如何实现秒杀场景处理高并发以及超卖现象？

1. 在数据库层面：

   • 在查询商品库存时加排他锁，比如“select * from goods where id = #{id} for update”，此时相当于对id为#{id}的数据行加锁，其他线程可以使用select读取数据，但是如果是select for update、update、delete都会阻塞，直到线程A提交事务，其他线程才能获得锁。
   • 在更新数据库的时候，可以通过加一个库存限制的条件“select * from goods where id = #{id} and stock > 0”

2. 利用分布式锁：同一个key，同一个时间只有一个客户端拿到锁，其他客户端会陷入无限等待来尝试获取锁，只有获得锁的客户端才能执行接下来的业务逻辑

   缺点：同一个商品在多个用户同时下单时，会基于分布式锁串行化处理，导致没法同时处理用同一个商品的大量下单请求。

3. 利用Redis的incr、decr的原子性 + 异步性：

   • 系统初始化时，将商品库存加到Redis中
   • 收到秒杀请求时，再redis中进行预减库存（利用incr、decr的原子性），当redis中库存不足时，直接返回秒杀失败
   • 把秒杀请求放入异步队列，返回正在排队中
   • 服务端异步请求出队（有些商品规定用户只能购买一次，防止重复秒杀），出队成功的商品可以生成秒杀订单，扣减库存
   • 用户在客户端申请秒杀请求后，会有个定时任务进行查询，查看秒杀是否成功，如果秒杀成功就进入秒杀订单详情，否则就会提示秒杀失败。