昆山网站建设秦皇岛,网页模板下载哪个网站好,综合购物网站排名,大连哪个区最好一、Redis的数据结构
1.动态字符串
我们知道Redis中保存的Key是字符串#xff0c;value往往hi字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。不过#xff0c;Redis
没有直接使用c语言的字符串#xff0c;因为c语言字符串存在许多问题#xff1a;
…一、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则新空间为扩展后字符串1m1.称为内存预分配 优点1.获取字符串长度的时间复杂度为O1
2.支持动态扩容
3.减少内存分配次数
4.二进制安全
2.Redis数据结构—inset
Inset是Redis中set集合的一种实现方式基于整数数组来实现并且具备长度可变、有序等特征
为了方便查找Redis会将inset中所有的整数按照升序依次保存在contents数组中结构如图 现在数组中每个数字都在int16_t的范围内因此采用的编码方式是INTSET_ENC_INT16,每部分占用的字节大小为
encoding4字节
length4字节 contents2字节 * 3 6字节
小总结
Intset可以看做是特殊的整数数组具备一些特点
Redis会确保Intset中的元素唯一、有序具备类型升级机制可以节省内存空间底层采用二分查找方式来查询
3.Redis数据结构—Dict
我们知道Redis是一个键值型Key-Value Pair的数据库我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。 Dict由三部分组成分别是哈希表DictHashTable、哈希节点DictEntry、字典Dict
当我们向Dict添加键值对时Redis首先根据key计算出hash值h然后利用 h sizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1v1假设k1的哈希值h 1则13 1因此k1v1要存储到数组角标1位置。 Dict由三部分组成分别是哈希表DictHashTable、哈希节点DictEntry、字典Dict
Dict的扩容
Dict中的HashTable就是数组结合单向链表的实现当集合中元素较多时必然导致哈希冲突增多链表过长则查询效率会大大降低。 Dict在每次新增键值对时都会检查负载因子LoadFactor used/size 满足以下两种情况时会触发哈希表扩容 哈希表的 LoadFactor 1并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程 哈希表的 LoadFactor 5
4.Redis数据结构-ZipList ZipList是一种特殊的“双端链表”由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作并且改操作的时间复杂度为O1。
属性类型长度用途zlbytesuint32_t4 字节记录整个压缩列表占用的内存字节数zltailuint32_t4 字节记录压缩列表表尾节点距离压缩列表的起始地址有多少字节通过这个偏移量可以确定表尾节点的地址。zllenuint16_t2 字节记录了压缩列表包含的节点数量。 最大值为UINT16_MAX 65534如果超过这个值此处会记录为65535但节点的真实数量需要遍历整个压缩列表才能计算得出。entry列表节点不定压缩列表包含的各个节点节点的长度由节点保存的内容决定。zlenduint8_t1 字节特殊值 0xFF 十进制 255 用于标记压缩列表的末端。
ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小长度是1个或5个字节 如果前一节点的长度小于254字节则采用1个字节来保存这个长度值 如果前一节点的长度大于等于254字节则采用5个字节来保存这个长度值第一个字节为0xfe后四个字节才是真实长度数据
ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新Cascade Update。新增、删除都可能导致连锁更新的发生。
小总结**
ZipList特性
压缩列表的可以看做一种连续内存空间的双向链表列表的节点之间不是通过指针连接而是记录上一节点和本节点长度来寻址内存占用较低如果列表数据过多导致链表过长可能影响查询性能增或删较大数据时有可能发生连续更新问题
5.Redis数据结构-QuickList
问题1ZipList虽然节省内存但申请内存必须是连续空间如果内存占用较多申请内存效率很低。怎么办
答为了缓解这个问题我们必须限制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的内部存储结构⼀般是sdsSimple Dynamic String可以动态扩展内存但是如果⼀个String类型的value的值是数字那么Redis内部会把它转成long类型来存储从⽽减少内存的使用。
9 Redis数据结构-List
Redis的List类型可以从首、尾操作列表中的元素 哪一个数据结构能满足上述特征
LinkedList 普通链表可以从双端访问内存占用较高内存碎片较多ZipList 压缩列表可以从双端访问内存占用低存储上限低QuickListLinkedList 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值是scorehash的键和值都是任意值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被数据穿透了直接打到数据库上
1.3缓存的击穿
雪崩是大量key同时失效穿透式热点key失效结果都是数据库压力过大而产生错误
[外链图片转存中…(img-sOtUt4xx-1729479919885)]
解决方式可以使用分布式锁在击穿redis到数据库时给上锁就只有一个线程能操作它的锁对数据的压力就变小等查到这个数据时再把缓存重新写到这个redis里面其他没有抢到线程的先暂停几毫秒当第一个线程在数据库中访问到信息就会返回到redis里面去当接下来的用户进行数据请求时就能够直接俄从redis里面把数据给查询出来。
