网站支付链接怎么做,厚昌营销网站建设,北京突发重大消息,单页销售网站源码Redis作为目前最主流的高性能缓存#xff0c;里面有很多精妙的设计#xff0c;其中有一种数据类型#xff0c;当在存储的时候会同时采用两种数据结构来进行分别存储#xff0c;那么
Redis 为什么要这么做呢#xff1f;这么做会造成同一份数据占用两倍空间吗#xff1f; …Redis作为目前最主流的高性能缓存里面有很多精妙的设计其中有一种数据类型当在存储的时候会同时采用两种数据结构来进行分别存储那么
Redis 为什么要这么做呢这么做会造成同一份数据占用两倍空间吗
接下来我们带着上面的两个疑问一起去探讨一下
1.五种基本类型之集合对象—Set
Set 是 String 类型的无序集合。集合是通过 hashtable 实现的。Set 中的元素是没有顺序的而且是没有重复的。常用命令sdd、spop、smembers、sunion 等。
底层数据结构 set的底层是 intset整数数组 或者 hashtable哈希表。 当set同时满足以下两个条件时使用 intset整数数组
集合对象保存的所有对象都是整数值集合对象保存的元素数量小于512个这个阈值可以通过配置文件 set-max-intset-entries 来控制
不能满足这两个条件的就使用 hashtable哈希表
那么redis为什么做这种设计呢
1.1 intset 编码
intset整数集合可以保存类型为 int16_tint32_tint64_t 的整数值并且保证集合中没有重复元素。
intset 数据结构定义如下源码 inset.h 内
typedef struct intset {uint32_t encoding;//编码方式uint32_t length;//当前集合中的元素数量int8_t contents[];//集合中具体的元素
} intset;encoding
在 intset 内部的 encoding 记录了当前整数集合的数据存储类型主要有三种
INTSET_ENC_INT16 此时 contents[] 内的每个元素都是一个 int16_t 类型的整数值范围是-32768 ~ 32767-2 的 15 次方 ~ 2 的 15 次方 - 1。
INTSET_ENC_INT32 此时contents[]内的每个元素都是一个 int32_t 类型的整数值范围是-2147483648 ~ 2147483647-2 的 31 次方 ~ 2 的 31 次方 - 1。
INTSET_ENC_INT64 此时 contents[]内的每个元素都是一个 int64_t 类型的整数值范围是-9223372036854775808 ~ 9223372036854775807-2 的 63 次方 ~ 2 的 63 次方 - 1。
contents[]
contents[] 虽然结构的定义上写的是 int8_t 类型但是实际存储类型是由上面的 encoding 来决定的。
整数集合的升级
假如一开始整数集合中的元素都是 16 位的采用 int16_t 类型来存储此时需要再存储一个 32 位的整数那么就需要对原先的整数集合进行升级升级之后才能将 32 位的整数存储到整数集合内。这就涉及到了整数集合的类型升级升级过程主要有 4 个步骤
根据新添加元素的类型来扩展底层数组空间的大小按照升级后现有元素的位数来分配新的空间。将现有的元素进行类型转换并将转换类型后的元素从后到前逐个重新放回到数组内。将新元素放到数组的头部或者尾部因为触发升级的条件就是当前数组的整数类型无法存储新元素所以新元素要么比现有元素都大要么就比现有元素都小。将 encoding 属性修改为最新的编码并且同步修改 length 属性。
值得我们注意的是和字符串对象的编码一样整数集合的类型一旦发生升级将会保持编码无法降级。
下面举一个简单的例子来还原一下上面的四个步骤
1.假如我们有一个集合存储的 encoding 是 int16_t内部存储了 3 个元素
位数0-15位16-31位32-47位元素123
2.这时候需要插入一个整数 50000发现存储不下去因为50000 是一个 int32_t 类型整数所以需要申请新空间申请空间大小为 4 * 32 - 4880。
位数0-15位16-31位32-47位48-127位元素123新申请空间
3.现在新的数组内要放置 4 个元素原来的数组排在第 3所以需要将升级后的 3 移动到 64-95 位。
位数0-15位16-31位32-63位64-95位96-127位元素123
4.继续将升级后的 2 移动到 32-63 位。
位数0-15位16-31位32-63位64-95位96-127位元素123
5.继续将升级后的 1 移动到 0-31 位。
位数0-31位32-63位64-95位96-127位元素123
6.然后会将 50000 放到 96-127 位。
位数0-31位32-63位64-95位96-127位元素12350000
7.最后会修改 encoding 和 length 属性修改之后就完成了本次的升级。
1.2 集合对象常用命令
sadd key member1 member2将一个或多个元素 member 加入到集合 key 当中并返回添加成功的数目如果元素已存在则被忽略。sismember key member判断元素 member 是否存在集合 key 中。srem key member1 member2移除集合 key 中的元素不存在的元素会被忽略。smove source dest member将元素 member 从集合 source 中移动到 dest 中如果 member 不存在则不执行任何操作。smembers key返回集合 key 中所有元素。
下面我们实操一下看看intset和hashTable之间是怎么转换的
依次执行以下命令
sadd num 1 2 3 //设置 3 个整数的集合会使用 intset 编码
type num //查看类型
object encoding num //查看编码sadd name 1 2 3 test //设置 3 个整数和 1 个字符串的集合会使用 hashtable 编码
type name //查看类型
object encoding name //查看编码 可以看到当设置的元素里面只有整数时集合使用的就是 intset 编码当设置的元素中含有非整数时使用的就是 hashtable 编码。
2.五种基本类型之有序集合对象—ZSet
Redis 中的有序集合和集合的区别是有序集合中的每个元素都会关联一个 double 类型的分数然后按照分数从小到大的顺序进行排列。
换句话说有序集合的顺序是由我们自己设值的时候通过分数来确定的。
使用场景Sorted Set 可以通过用户额外提供一个优先级score的参数来为成员排序并且是插入有序的即自动排序。
当你需要一个有序的并且不重复的集合列表那么可以选择 Sorted Set 结构。
和 Set 相比Sorted Set关联了一个 Double 类型权重的参数 Score使得集合中的元素能够按照 Score 进行有序排列Redis 正是通过分数来为集合中的成员进行从小到大的排序。
实现方式Redis Sorted Set 的内部使用 HashMap 和跳跃表skipList来保证数据的存储和有序HashMap 里放的是成员到 Score 的映射。
而跳跃表里存放的是所有的成员排序依据是 HashMap 里存的 Score使用跳跃表的结构可以获得比较高的查找效率并且在实现上比较简单。
有序集合对象的底层数据结构有两种skiplist 和 ziplist。内部同样是通过编码来进行区分
编码属性描述Object encoding 命令返回值OBJ_ENCODING_SKIPLIST使用跳跃表实现的有序集合对象skiplistOBJ_ENCODING_ZIPLIST使用压缩表实现的有序集合对象ziplist
2.1 skiplist 编码
skiplist 即跳跃表有时候也简称为跳表。使用 skiplist 编码的有序集合对象使用了 zset 结构来作为底层实现而zset 中同时包含了一个字典和一个跳跃表。
跳跃表
跳跃表是一种有序的数据结构其主要特点是通过在每个节点中维持多个指向其他节点的指针从而达到快速访问节点的目的。
大部分情况下跳跃表的效率可以等同于平衡树但是跳跃表的实现却远远比平衡树的实现简单所以 Redis 选择了使用跳跃表来实现有序集合。
下图是一个普通的有序链表我们如果想要找到 35 这个元素只能从头开始遍历到尾链表中元素不支持随机访问所以不能用二分查找而数组中可以通过下标随机访问所以二分查找一般适用于有序数组时间复杂度是 O(n)。
那么假如我们可以直接跳到链表的中间那就可以节省很多资源了这就是跳表的原理如下图所示就是一个跳表的数据结构示例
上图中 level1level2level3 就是跳表的层级每一个 level 层级都有一个指向下一个相同 level 层级元素的指针比如上图我们遍历寻找元素 35 的时候就有三种方案
第 1 种就是执行 level1 层级的指针需要遍历 7 次1-8-9-12-15-20-35才能找到元素 35。第 2 种就是执行 level2 层级的指针只需要遍历 5 次1-9-12-15-35就能找到元素 35。第 3 种就是执行 level3 层级的元素这时候只需要遍历 3 次1-12-35就能找到元素 35 了大大提升了效率。
skiplist 的存储结构
跳跃表中的每个节点是一个 zskiplistNode 节点源码 server.h 内
typedef struct zskiplistNode {sds ele;//元素double score;//分值struct zskiplistNode *backward;//后退指针struct zskiplistLevel {//层struct zskiplistNode *forward;//前进指针unsigned long span;//当前节点到下一个节点的跨度跨越的节点数} level[];
} zskiplistNode;level层
level 即跳跃表中的层其是一个数组也就是说一个节点的元素可以拥有多个层即多个指向其他节点的指针程序可以通过不同层级的指针来选择最快捷的路径提升访问速度。
level 是在每次创建新节点的时候根据幂次定律power law随机生成的一个介于 1~32 之间的数字。
forward前进指针
每个层都会有一个指向链表尾部方向元素的指针遍历元素的时候需要使用到前进指针。
span跨度
跨度记录了两个节点之间的距离,需要注意的是如果指向了 NULL 的话则跨度为 0。
backward后退指针
和前进指针不一样的是后退指针只有一个所以每次只能后退至前一个节点上图中没有画出后退指针。
ele元素
跳跃表中元素是一个 sds 对象早期版本使用的是 redisObject 对象元素必须唯一不能重复。
score分值
节点的分值是一个 double 类型的浮点数跳跃表中会将节点按照分值按照从小到大的顺序排列不同节点的分值可以重复。
上面介绍的只是跳跃表中的一个节点多个 zskiplistNode 节点组成了一个 zskiplist 对象
typedef struct zskiplist {struct zskiplistNode *header, *tail;//跳跃表的头节点和尾结点指针unsigned long length;//跳跃表的节点数int level;//所有节点中最大的层数
} zskiplist;到这里你可能以为有序集合就是用这个 zskiplist 来实现的然而实际上 Redis 并没有直接使用 zskiplist 来实现而是用 zset 对象再次进行了一层包装。
typedef struct zset {dict *dict;//字典对象zskiplist *zsl;//跳跃表对象
} zset;所以最终一个有序集合如果使用了 skiplist 编码其数据结构如下图所示
上图中上面一部分中的字典中的 key 就是对应了有序集合中的元素membervalue 就对应了分值score。上图中下面一部分中跳跃表整数 1,8,9,12 也是对应了元素member最后一排的 double 型数字就是分值score。
也就是说字典和跳跃表中的数据都指向了我们存储的元素两种数据结构最终指向的是同一个地址所以数据并不会出现冗余存储Redis 为什么要这么做呢
为什么同时选择使用字典和跳跃表 有序集合直接使用跳跃表或者单独使用字典完全可以独自实现但是我们想一下如果单独使用跳跃表来实现那么虽然可以使用跨度大的指针去遍历元素来找到我们需要的数据但是其复杂度仍然达到了 O(logN)而字典中获取一个元素的复杂度是 O(1)而如果单独使用字典虽然获取元素很快但是字典是无序的所以如果要范围查找就需要对其进行排序这又是一个耗时的操作所以 Redis 综合了两种数据结构来最大程度的提升性能这也是 Redis 设计的精妙之处。 2.2 ziplist 编码
ziplist压缩列表在Redis的hash以及list对象中均有使用ziplist是一个典型的以时间换空间的设计。
ziplist 是为了节省内存而设计出来的一种数据结构。ziplist 是由一系列特殊编码组成的连续内存块的顺序型数据结构一个 ziplist 可以包含任意多个 entry而每一个 entry 又可以保存一个字节数组或者一个整数值。
ziplist 作为一种列表其和普通的双端列表如 linkedlist 的最大区别就是 ziplist 并不存储前后节点的指针而 linkedlist 一般每个节点都会维护一个指向前置节点和一个指向后置节点的指针。那么 ziplist 不维护前后节点的指针它又是如何寻找前后节点的呢
ziplist 虽然不维护前后节点的指针但是它却维护了上一个节点的长度和当前节点的长度然后每次通过长度来计算出前后节点的位置。既然涉及到了计算那么相对于直接存储指针的方式肯定有性能上的损耗这就是一种典型的用时间来换取空间的做法。因为每次读取前后节点都需要经过计算才能得到前后节点的位置所以会消耗更多的时间而在 Redis 中一个指针是占了 8 个字节但是大部分情况下如果直接存储长度是达不到 8 个字节的所以采用存储长度的设计方式在大部分场景下是可以节省内存空间的。
当然没有完美的技术只能折中选择虽然压缩列表ziplist可以节省内存空间但是却会引发ziplist 连锁更新问题
我们来设想这么一种场景 假设一个 ziplist 中连续多个 entry 的长度都是一个接近但是又不到 254 的值介于 250~253 之间那么这时候 ziplist 中每个节点都只用了 1 个字节来存储上一个节点的长度假如这时候添加了一个新节点如 entry1 其长度大于 254 个字节此时 entry1 的下一个节点 entry2 的 prelen 属性就必须要由 1 个字节变为 5 个字节也就是需要执行空间重分配而此时 entry2 因为增加了 4 个字节导致长度又大于 254 个字节了那么它的下一个节点 entry3 的 prelen 属性也会被改变为 5 个字节。 依此类推这种产生连续多次空间重分配的现象就称之为连锁更新。同样的不仅仅是新增节点执行删除节点操作同样可能会发生连锁更新现象。 虽然 ziplist 可能会出现这种连锁更新的场景但是一般如果只是发生在少数几个节点之间那么并不会严重影响性能而且这种场景发生的概率也比较低所以实际使用时不用过于担心。
2.3 ziplist 和 skiplist 编码转换
当有序集合对象同时满足以下两个条件时会使用 ziplist 编码进行存储
有序集合对象中保存的元素个数小于 128 个可以通过配置 zset-max-ziplist-entries 修改。有序集合对象中保存的所有元素的总长度小于 64 字节可以通过配置 zset-max-ziplist-value 修改。
2.4 有序集合对象常用命令
zadd key score1 member1 score2 member2将一个或多个元素member及其 score 添加到有序集合 key 中。zscore key member返回有序集合 key 中 member 成员的 score。zincrby key num member将有序集合 key 中的 member 加上 numnum 可以为负数。zcount key min max返回有序集合 key 中 score 值在 [min,max] 区间的 member 数量。zrange key start stop返回有序集合 key 中 score 从小到大排列后在 [start,stop] 区间的所有 member。zrevrange key start stop返回有序集合 key 中 score 从大到小排列后在 [start,stop] 区间的所有 member。zrangebyscore key min max返回有序集合中按 score 从小到大排列后在 [min,max] 区间的所有元素。注意这里默认是闭区间但是可以在 max 和 min 的数值前面加上 ( 或者 [ 来控制开闭区间。zrevrangebyscore key max min返回有序集合中按 score 从大到小排列后在 [min,max] 区间的所有元素。注意这里默认是闭区间但是可以在 max 和 min 的数值前面加上 ( 或者 [ 来控制开闭区间。zrank key member返回有序集合中 member 中元素排名从小到大返回的结果从 0 开始计算。zrevrank key member返回有序集合中 member 中元素排名从大到小返回的结果从 0 开始计算。zlexcount key min max返回有序集合中 min 和 max 之间的 member 数量。注意这个命令中的 min 和 max 前面必须加 ( 或者 [ 来控制开闭区间特殊值 - 和 分别表示负无穷和正无穷。
依次执行如下命令
zadd name 1 zs 2 lisi //设置 2 个元素会使用 ziplist
type name //查看类型
object encoding name //查看编码 zadd address 1 beijing 2 shanghai 3 guangzhou 4 shenzhen //设置4个元素则会使用 skiplist编码
type address //查看类型
object encoding address //查看编码 3.总结
本文主要分析了set对象和zset对象的底层存储结构 intset 和 skiplist 的实现原理并且重点分析了有序集合如何实现排序以及为何同时使用两种数据结构字典和跳表同时进行进行存储数据的原因。
