Redis原理

Redis底层数据结构

String   Hash  List  Set   Zset  

BitMap   HyperLogLog  GEO  Stream

Set和 Zset的区别

点击图片可查看完整电子表格

Set是无序，唯一元素的集合，适合存储不重复且无需排序的数据              

Zset是有序的，唯一元素的集合，每个元素关联一个“分数score”，按分数从小到大排序

Zset底层怎么实现的

数据结构由压缩列表或跳表实习

有序集合的元素个数<128个，并且每个元素的值小于64字节时，Redis会使用压缩列表作为Zset类型的底层数据结构

有序集合的元素不满足上面条件，用跳表作为Zset类型底层数据结构

 Redis7.0之后，ziplist被弃用，由listpack 数据结构实现

跳表如何实现？

跳表是一个多层的有序链表，每一层可包含多个节点，每一个节点通过指针连接，由zskiplist结构体类型的level数组，level每个元素表示一层，level[0]第一层，level[1]第二层，里面的*forward是下一个跳表的指针，跨度（span）用来记录两个节点之间的距离，遍历只需要struct zsliplistNode *forward 实现。

C++                  

typedef struct zskiplistNode {                  

    sds ele;                  // 成员对象（如字符串）

    double score;               // 权重值（用于排序）

    struct zskiplistNode *backward; // 后退指针（双向链表）

    struct zskiplistLevel {                  

        struct zskiplistNode *forward; // 前进指针

        unsigned int span;      // 跨度（记录距离）

    } level[];                  // 柔性数组，动态分配层数

} zskiplistNode;

Zset保存元素和元素权重对应到跳表节点结构就是sds类型的ele和变量double类型的score变量。每个跳表节点都有个后向的指针（struct zsliplistNode *backwad）形成双向链表,指向前一个节点，目的是为了方便从跳表的尾节点开始访问，倒序查找时方便  

Redis跳表创建节点的适合，随机生成每个节点的层数，生成随机数【0-1】，<0.25则层数增加，继续随机，直到全都>0.25，最终确定该节点的层数，层高最大限制为64（设置层高）默认32

创建头节点的时候，如果层高的最大限制是64，就会直接创建64层高的头节点

跳表vsB+树

点击图片可查看完整电子表格

Redis是内存数据库，跳表在实现简单下，写入性能，内存访问模式等方面的综合优势，使其成为更合适的选择。

压缩列表ziplist

ziplist 的优缺点

点击图片可查看完整电子表格

zlibytes:记录整个ziplist占用内存的总字节数

zltail:最后一个entry的偏移量（支持反向遍历 ）

zllen: entry数量(2^32-1，超过就需遍历计算）

zlend:结束标记0XFF

prevlen:前一个entry的长度

encoding：当前entry长度

content：实际数据

查询时间复杂度：第一个元素O(1）， O（n)

ziplist根据数据类型（sting int )以及大小，会使用不同的prevlen和encoding保存信息，来节省内存

缺点：更新会发生连锁更新，ziplist占用的内存空间要多次重新分配，影响ziplist的使用性能

适用于保存节点数量不多的场景。

listpack:

encoding:定义该元素的编码类型

data:数据

len:encoding +data长度

listpack:只记录当前节点的长度，加入一个新元素的时候，不会影响其他长度字段的变化，从而避免了压缩列表的连锁更新

哈希表的扩容

在rehash进行期间，每次哈希表元素进行新增，删除，查找或者更新操作时，Redis除了会执行对应的操作之外，还会顺序将哈希表1中的索引位置上的所有key-value迁移到哈希表2上

随着处理客户端发起的哈希表请求数量变多，最终会把哈希表1中索引位置上的所有key-value迁移到哈希表2上，从而完成rehash操作。

哈希表扩容，有读请求怎么查

查找key值的话，先在哈希表1查找，没找到在哈希表2继续查找

String 使用什么存储，不用c语言中的字符串

Redis的String是用SDS(简单动态字符串，支持多种编码格式)存储的

len:记录了字符串长度

alloc:分配给字符数组的空间长度

flags:不同类型的SDS

buf[]:字符数组，用来保存实际数据

O（1）获取字符串长度

可存储"�"的数据，二进制安全

缓冲区大小不够用时，Redis会自动扩展SDS大小

线程

Redis快，why?

Redis的QPS(10w/s)

Redis的大部分操作在内存中完成，且采用了高效的数据结构

采用单线程可以避免多线程之间的竞争，省去了多线程切换带来的时间和性能上的开销，而且不会死锁

Redis采用I/O多路复用机制处理大量的客户端Socket请求，即一个线程处理多个IO流。

Redis多线程

Redis命令仍然是单线程的，多线程的引进用来异步处理关闭文件任务，AOF刷盘任务，释放内存任务，以及处理I/O请求——I/O多路复用

日志持久化

AOF（追加日志）：

Redis每执行一条写操作命令后，就会把该命令以追加的方式写到一个文件里，当AOF文件过大，Redis会进行AOF重写（通过执行bgrewriteaof命令)，剔除多余的命令，Redis重启时，读取此文件记录的命令，然后逐一执行命令的方式进行数据恢复

刷盘策略

always:   同步刷盘    可靠性高，几乎不丢失数据     性能影响大

everysec: 每秒刷盘           性能始适中                   最多丢失1s数据

no:          OS控制              性能最好    下              可靠性差，可能丢失大量数据

RDB（快照）

save ：在主线程生成RDB文件，由于和执行操作命令在同一个线程，如果写入RDB文件的时间过长，会阻塞主线程

bigsave：创建子线程生成RDB文件，避免主线程阻塞

AOFvsRDB

点击图片可查看完整电子表格

高可用

主从复制

一个主节点连接多个从节点，主节点写，从节点读，实现读写分离

提升系统的并发能力以及保证其高可用性

原理：

建立连接：从节点连接主节点，并发送psync命令，请求数据同步，这时候主节点会为从节点创建客户端连接，分配复制缓冲区，记录复制积压缓冲区

全量同步：当从节点首次连接主节点时，会触发全量同步（复制ID不匹配时也是全量）

增量同步：主节点把同步的写命令暂存一份到复制积压缓冲区，用于存储最近的命令，主从发生网络断链，从节点重新连接，可以复制积压缓冲区中复制尚未同步的写命令

命令传播：主从完成全量同步后，依靠传播命令阶段来保证数据的增量同步，主节点会将每次执行的命令异步发送给所有从节点。

问题：

主节点处理完命令后写命令后会立即响应客户端，而不会等待从节点确认，可能出现数据一致性，

全量同步会占用大量的CPU和IO资源，大数据的情况下，会导致主节点的性能下降

哨兵机制

核心功能：

监控 通知和自动故障转移，

哨兵会定期检查主从节点是否按预期工作，当检测到主节点故障时，在从节点选举一个新的主节点，并通知客户端连接到新的主节点

原理：

主观下线：单个哨兵发现主节点没有响应，临时标记为主观下线

客观下线：达到法定人数的哨兵认为主观下线，则判定为客观下线

故障转移：哨兵选举出一个领导者，领导者再从从节点基于Raft算法投票选举出一个最合适的节点作为新的主节点，选举标准包括连接状态复制偏移量 运行ID等

确定主节点后，哨兵 向其发送slaveof no one 命令使其升级为主节点，然后在向其他从节点发送slaveof命令指向新主节点 ，最后通过发布/订阅机制通知客户端主节点已经发生变化

 

描述：

Redis 哨兵机制通过多节点监控实现高可用。当单个哨兵判定主节点主观下线时，若法定人数（quorum）的哨兵达成共识，则标记为客观下线。哨兵集群通过 Raft 算法选举领导者，由领导者依据数据偏移量和优先级选择新主节点，执行 SLAVEOF no one升级新主，并命令其他从节点复制新主。故障转移后，哨兵通过发布/订阅通知客户端，并将旧主节点降级为从节点。

Raft算法

1.当一个哨兵确认主观下线后，会像其他哨兵发送节点请求，希望自己来执行主从切换，并让所有哨兵进行投票，候选者先给自己投一票，等待其他哨兵投票

2.收到请求的哨兵节点进行判断，候选者日志和自己一样新，任期号也<自己，没投票过，就Y,or N。

3.投票超过一半，竞选为领导者

4.选举失败则进入下一轮选举，为了防止无限制选举失败，每个哨兵都有个选举超时时间，随机的

选取主节点优先级：

1从节点优先级： slave_priority值越小优先级越高，优先级为0不会被选中

2.复制偏移量：偏移量越大意味着从节点数据越新，复制的越完整，

3.运行ID：如果优先级和偏移量相同，ID小优先

Redis集群

Redis Cluster:

官方提供的分布式集群解决方案，核心理念是去中心化，每个节点都保存着数据和整个集群的状态。

通过分片的方式将整个 数据集划分为16384个hash slot,每个键通过CRC16校验后，对16834取模决定属于哪个槽

缓存

缓存击穿

某个热点数据缓存过期时，大量请求会穿透缓存直接访问数据库，导致数据库瞬间压力大

解决方式：

1 加互斥锁：缓存失效时，第一个访问的线程先获取锁并重建缓存，其他线程等待或重试

2 永不过期策略：热点数据不设置过期时间，由后台异步更新缓存，或者在缓存过期前，提前通知后台线程更新缓存以及重新设置

过期时间。

缓存穿透

用户访问数据，不在缓存和数据库中，请求在访问缓存时，发现缓存缺失，缓存找不到，全都打到数据库上。大量请求，数据库压力剧增

解决方式：

布隆过滤器：一种效率极高的数据结构，用于快速判断一个元素是否可能存在于一个集合中（可能会误判，但不会漏判）

缓存空值：空值写入缓存，设置一个合理的过期时间，下次相同查询直接从缓存返回，不访问数据库

缓存雪崩：

某一时间段，大量缓存同时失效或者服务器突然宕机，导致大量请求涌向数据库，导致数据库压力剧增，甚至引发系统崩溃的现象

大量缓存同时过期：添加随机过期时间

缓存服务崩溃：使用高可用的缓存集群  可配置本地缓存作为二级缓存

缓存服务正常但并发超过了缓存服务的承载能力：限流或者降级措施

如何处理热key:

 将热key缓存到本地内存，这样请求不需要访问Redis

特热key，拆分为多个子key，随机分布在redis节点上

如何处理大key

常见大key:大量元素的list，set，hash，大文件String，复杂嵌套的json

拆分成小key，json类型的，Gzip压缩后在存储

缓存预热

提前将热数据加载到缓存中，避免冷启动时大量请求直接打到数据库

在夜间用户量少的时候更新最新数据，使更多的用户第一次访问时就能获取缓存数据，减轻数据库的压力

过期策略：

惰性删除：客户端访问key,Redis检查key是否过期，如果过期会立即删除并返回null

定期删除:

内存淘汰：

noeviction:不删除key,返回错误信息，生产上几乎不用

对key:

  allkeys-lru:删除最少使用的key 

  allkeys-lfu:删除访问频率最低的key 

  allkeys-random:随机删除key

过期时间：

volatile-lru: volatile-lfu: volatile-ttl:  volatile-random

lru在缓存场景使用，能自动保留热点数据

lfu适合长期运行的系统

Reids和Mysql一致

旁路缓存+延迟双删

写操作：

先删除Redis中的缓存数据，在更新Mysql的数据，延迟一会，在删除Redis缓存

读操作：

先读Redis，如果命中则直接返回，如果未命中，则读Mysql,将Mysql中读到的数据写入Redis

缓存更新与业务逻辑解耦：

业务：只更新数据库，不更新缓存。

缓存：客户端接收变更信息后，调用接口删除或更新Reids中对应的缓存

分布式锁 ：           

1.set key value NX PX 3000 

锁名为key,持有者value。 NX保证只有key不存在时才能创建成功，EX设置时间防止死锁

解锁：

Lua脚本：get和del是两个独立操作，非原子性不用Lua,可能在get之后，del之前锁就过期了，且被其他客户段获取，从而导致误删别人的锁，Lua脚本可以保证这俩个操作的原子性。

2.Redisson

看门狗机制： 

调用lock()方法加锁时，如果没有显式设置过期时间，Redission会默认给锁加一个30s的过期时间，同时启动”看门狗“的定时任务，每隔10s会检查一次锁是否还被当前线程持有吗，如果是，自动续期，将过期时间延长到30s

续期操作通过Lua保证原子性

Redlock:

部署N个独立的Redis节点,容忍部分节点故障

客户端向所有N个节点发送加锁命令，只有当从大多数节点（>1/2）上成功获取锁，且加锁总耗时小于所得过期时间，才认为加锁成功

场景假设

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

使用SCAN命令配合MATCH参数解决

2，秒杀场景处理高并发以及超卖现象

解决方式：

1.数据库上：

在查询商品库存上设置排他锁，更新库存时，进行库存限制条件 

性能不好，无法应对高并发

2分布式锁+分布缓存

把数据分成多段，每个段都是一个单独的锁，多线程并发修改数据的时候，可以并发的修改不同段的数据。

当某段锁的库存不足时，一定要自动是否锁然后换下一个分段库存再次尝试加速处理

3.redis的incr,decr的原子性+异步队列

初始化时，将商品库存加载到Reids缓存中

接收到秒杀请求时，在Reids预减缓存（利用Redis decr的原子性），当Redis缓存不足时，直接返回秒杀失败，否则继续下步

将请求放入异步队列，返回正在排队中

服务端异步队列将请求出队（哪些请求可以出队，可以根据业务来判定，比如：判断对应用户是否已经秒杀过对应商品，防止重复秒杀），出队成功的请求可以生成秒杀订单，减少数据库库存（在扣减库存的sql如下，返回秒杀订单详情）

用户在客户端申请秒杀请求后，进行轮询，查看是否秒杀成功，成功进入秒杀订单详情，否则秒杀失败。

上一条：redis十种数据类型及底层原理

下一条：Redis缓存一致性问题