Redis底层和缓存雪崩，击穿，穿透

一、Redis的数据结构

1.动态字符串

我们知道Redis中保存的Key是字符串，value往往hi字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。不过，Redis

没有直接使用c语言的字符串，因为c语言字符串存在许多问题：

获取字符串长度的需要通过运算

非二进制安全

不可修改

Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dyname String），简称SDS

在这里插入图片描述

那么Redis将在底层创建两个SDS，其中一个是包含“name”的SDS，另一个包含“虎哥”的SDS

SDS之所以叫做动态字符串，因为它具备动态扩容的能力，列如

一个内容为“hi”的SDS

在这里插入图片描述

假如我们给SDS追加一段字符串“AMY”，这里首先会申请新内存空间：

如果新字符串小于1m，则新空间为扩展后字符串长度的两倍+1

如果新字符串大于1M，则新空间为扩展后字符串+1m+1.称为内存预分配

在这里插入图片描述

优点：1.获取字符串长度的时间复杂度为O（1）

2.支持动态扩容

3.减少内存分配次数

4.二进制安全

2.Redis数据结构—inset

Inset是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征

为了方便查找，Redis会将inset中所有的整数按照升序依次保存在contents数组中，结构如图：

在这里插入图片描述

现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16,每部分占用的字节大小为：

encoding：4字节

length：4字节
contents：2字节 * 3 = 6字节

小总结：

Intset可以看做是特殊的整数数组，具备一些特点：

Redis会确保Intset中的元素唯一、有序
具备类型升级机制，可以节省内存空间
底层采用二分查找方式来查询

3.Redis数据结构—Dict

我们知道Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。
Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1=v1，假设k1的哈希值h =1，则1&3 =1，因此k1=v1要存储到数组角标1位置。

在这里插入图片描述

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

Dict的扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。
Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size），满足以下两种情况时会触发哈希表扩容：
哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
哈希表的 LoadFactor > 5 ；

4.Redis数据结构-ZipList

ZipList是一种特殊的“双端链表”，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作，并且改操作的时间复杂度为O（1）。

属性	类型	长度	用途
zlbytes	uint32_t	4 字节	记录整个压缩列表占用的内存字节数
zltail	uint32_t	4 字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址。
zllen	uint16_t	2 字节	记录了压缩列表包含的节点数量。最大值为UINT16_MAX （65534），如果超过这个值，此处会记录为65535，但节点的真实数量需要遍历整个压缩列表才能计算得出。
entry	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend	uint8_t	1 字节	特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节：
如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。

小总结：**

ZipList特性：

压缩列表的可以看做一种连续内存空间的"双向链表"
列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
如果列表数据过多，导致链表过长，可能影响查询性能
增或删较大数据时有可能发生连续更新问题

5.Redis数据结构-QuickList

问题1：ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。怎么办？

答：为了缓解这个问题，我们必须限制ZipList的长度和entry大小。

问题2：但是我们要存储大量数据，超出了ZipList最佳的上限该怎么办？

答：我们可以创建多个ZipList来分片存储数据。

问题3：数据拆分后比较分散，不方便管理和查找，这多个ZipList如何建立联系？

答：Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个ZipList。

为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。
如果值为正，则代表ZipList的允许的entry个数的最大值
如果值为负，则代表ZipList的最大内存大小，分5种情况：

-1：每个ZipList的内存占用不能超过4kb
-2：每个ZipList的内存占用不能超过8kb
-3：每个ZipList的内存占用不能超过16kb
-4：每个ZipList的内存占用不能超过32kb
-5：每个ZipList的内存占用不能超过64kb

总结：

QuickList的特点：

是一个节点为ZipList的双端链表
节点采用ZipList，解决了传统链表的内存占用问题
控制了ZipList大小，解决连续内存空间申请效率问题
中间节点可以压缩，进一步节省了内存

6.Redis数据结构-SkipList

SkipList（跳表）首先是；链表，但与传统表相比有几点差异：

元素按照升序排序存储

节点可能包含多个指针，指针跨度不同

SkipList的特点：

跳跃表是一个双向链表，每个节点都包含score和ele值
节点按照score值排序，score值一样则按照ele字典排序
每个节点都可以包含多层指针，层数是1到32之间的随机数
不同层指针到下一个节点的跨度不同，层级越高，跨度越大
增删改查效率与红黑树基本一致，实现却更简单

7.Redis数据结构-RedisObject

Redis的任意数据类型的键和值都会被封装为一个RedisObject，也叫Redis对象

1、什么是redisObject：
从Redis的使用者的角度来看，⼀个Redis节点包含多个database（非cluster模式下默认是16个，cluster模式下只能是1个），而一个database维护了从key space到object space的映射关系。这个映射关系的key是string类型，⽽value可以是多种数据类型，比如：
string, list, hash、set、sorted set等。我们可以看到，key的类型固定是string，而value可能的类型是多个。
⽽从Redis内部实现的⾓度来看，database内的这个映射关系是用⼀个dict来维护的。dict的key固定用⼀种数据结构来表达就够了，这就是动态字符串sds。而value则比较复杂，为了在同⼀个dict内能够存储不同类型的value，这就需要⼀个通⽤的数据结构，这个通用的数据结构就是robj，全名是redisObject。

8 Redis数据结构-String

String是Redis中最常见的数据存储类型：

其基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb。

如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时

只需要调用一次内存分配函数，效率更高。

（1）底层实现⽅式：动态字符串sds 或者 long
String的内部存储结构⼀般是sds（Simple Dynamic String，可以动态扩展内存），但是如果⼀个String类型的value的值是数字，那么Redis内部会把它转成long类型来存储，从⽽减少内存的使用。

9 Redis数据结构-List

Redis的List类型可以从首、尾操作列表中的元素：

在这里插入图片描述

哪一个数据结构能满足上述特征？

LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多
ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低
QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高

Redis的List结构类似一个双端链表，可以从首、尾操作列表中的元素：

在3.2版本之前，Redis采用ZipList和LinkedList来实现List，当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则采用LinkedList编码。

在3.2版本之后，Redis统一采用QuickList来实现List：

10.Redis数据结构-Set结构

Set是Redis中的单列集合，满足下列特点：

不保证有序性
保证元素唯一
求交集、并集、差集

在这里插入图片描述

可以看出，Set对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？
HashTable，也就是Redis中的Dict，不过Dict是双列集合（可以存键、值对）

Set是Redis中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高。
为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null。
当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用IntSet编码，以节省内存

11 .Redis数据结构-Hash

Hash结构与Redis中的Zset非常类似：

都是键值存储
都需求根据键获取值
键必须唯一

区别如下：

zset的键是member，值是score；hash的键和值都是任意值
zset要根据score排序；hash则无需排序

（1）底层实现方式：压缩列表ziplist 或者字典dict
当Hash中数据项比较少的情况下，Hash底层才⽤压缩列表ziplist进⾏存储数据，随着数据的增加，底层的ziplist就可能会转成dict，具体配置如下：

hash-max-ziplist-entries 512

hash-max-ziplist-value 64

当满足上面两个条件其中之⼀的时候，Redis就使⽤dict字典来实现hash。
Redis的hash之所以这样设计，是因为当ziplist变得很⼤的时候，它有如下几个缺点：

每次插⼊或修改引发的realloc操作会有更⼤的概率造成内存拷贝，从而降低性能。
⼀旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更⼤的⼀块数据。
当ziplist数据项过多的时候，在它上⾯查找指定的数据项就会性能变得很低，因为ziplist上的查找需要进行遍历。

总之，ziplist本来就设计为各个数据项挨在⼀起组成连续的内存空间，这种结构并不擅长做修改操作。⼀旦数据发⽣改动，就会引发内存realloc，可能导致内存拷贝。

在这里插入图片描述

因此，Hash底层采用的编码与Zset也基本一致，只需要把排序有关的SkipList去掉即可：

Hash结构默认采用ZipList编码，用以节省内存。 ZipList中相邻的两个entry 分别保存field和value

二、Redis面试题

1.缓存雪崩、穿透、击穿

缓存流程

1.1缓存雪崩

在这里插入图片描述

用户访问某宝，redis里面的key大面积的失效，

导致某宝和数据库进行沟通，把请求都打到数据库

这种现象就是缓存雪崩，就是大量的redis缓存在同一时间全部失效

解决方案：

第一个：设置缓存的失效时间，让它不在同一时间失效，在我们设计这个缓存的时候，随机初始化它的这个失效时间，这样的话所有的缓存就不会同一时间失效，把所有的请求都打到数据库上

第二个: redis一般都是集群部署，我们把这些热点的key放到不同的节点上去，让这些热点的缓存，平均的分布在这个我不同的redis节点上，

第三个：就是不设置这个缓存失效的时间，让他永远不失效

或者跑定时任务，让他定时的刷这个缓存，比如说我这个缓存设置了三小时失效，当失效之前，继续进行定时刷新

1.2缓存穿透

是指缓存和数据中都没有的数据，一般常见与黑客攻击。比如用请求id=“-1”的数据，这种数据直接穿透缓存，打在数据库上导致数据库挂掉

数据库的主键从零开始的，递增的，没有负数那么黑客就利用id小于零的数来请求，redis里面并没有这个id小于零的数据，这样的话redis就查不到这个结果，一旦这个redis查不到这个结果，就会去数据库中，查找，就不断的访问数据库，redis被数据穿透了，直接打到数据库上

1.3缓存的击穿

雪崩是大量key同时失效，穿透式热点key失效，结果都是数据库压力过大而产生错误

在这里插入图片描述

解决方式：可以使用分布式锁，在击穿redis到数据库时，给上锁就只有一个线程能操作它的锁，对数据的压力就变小，等查到这个数据时，再把缓存重新写到这个redis里面，其他没有抢到线程的，先暂停几毫秒，当第一个线程在数据库中访问到信息，就会返回到redis里面去，当接下来的用户进行数据请求时，就能够直接俄从redis里面把数据给查询出来。

edis被数据穿透了，直接打到数据库上