前言
整数汇合置信有的同学没有据说过,因为 redis 对外提供的只有封装的五大对象!而咱们本系列宗旨是学习 redis 内部结构。内部结构是 redis 五大构造重要撑持!
后面咱们别离从 redis 内部结构剖析了 redis 的 List、Hash、Zset 三种数据结构了。明天咱们再来剖析 set 数据结构外部是如何存储的
根本构造
在 src/t_set.c 中咱们发现这样一段代码
由此咱们可知在 set 中是由两种数据结构形成的:hashtable+intset。对于 redis 外部其余的构造我专门在【redis 专栏中有介绍】。hashtable 不是咱们明天的配角,咱们明天先剖析 intset 俗称整数汇合。
从上图中咱们能够看出,我结构了两个 set 汇合别离为【commonset】、【cs】。两个汇合前者存储字符串、后者专门存储数字。
咱们在通过 object encoding key 来查看下两个汇合的底层数据结构,发现一个是 hashtable 一个是 intset。这也验证了咱们上面对 set 根本构造的形容。
在 redis 中对外提供五大类型实际上都是 redis 的一个形象对象叫做 redisobject。在外部映射了咱们 redis 外部的数据结构
针对 commonset 和 cs 两个汇合在外部数据结构大略能够这么了解
何时应用 intset
你能够单纯的认为只有是数字就会应用 intset 构造来存储,我恐怕要给你当头一棒了。实际上并不是这样
须要同时满足以下两个条件:
intset
图中示意的很分明了,在 intset 中的 encoding 有三种取值别离代表 contents 保留数据类型。这里有人可能会有疑难了 contents 的类型不就是 int8_t 吗?为什么还须要 encoding 呢?这里通过源码跟踪外部确实跟 int8_t 没啥关系。而且数据的默认类型就是 int16_t。对于 length 这里无需太多解释,记住一点示意 contents 元素的个数并非示意 contents 数组的长度!
理解 intset 的同学都晓得在 encoding 三种取值范畴中波及了降级的操作!在讲降级之前咱们先来理解下 C、C++ 中 int 的取值范畴是如何定义的
int8_t 的取值范畴是【-128,127】。相似于 java 中 byte 占 1 个字节也就是 8 位。他的取值范畴是
−27∼27−1 即−128∼127−27∼27−1 即−128∼127
增加元素
sadd juejin -123
sadd juejin -6
sadd juejin 12
sadd juejin 56
sadd juejin 321
juejin 这个 key 外部就是 intset。
下面咱们增加了 5 个元素且这五个元素的长度都在 16 之内!所以以后的 intset 的 encoding=INTSET_ENC_INT16。-123 在 contents 中占前 16 位。
所以以后五个元素占 contents 的长度是 16*5=80;
留神 set 在存储 int 类型数据时,外部是依照从小到大的顺序存储的。
类型变动
下面的问题不晓得你有没有思考过,或者说有没有遇到过!intset 默认是 int16 位,正如咱们下面增加的五个元素。退出此时咱们增加第 6 个元素是 65535(32 位)。那么此时 16 位的长度就不够存储了这个时候 intset 会怎么做!
另外当咱们增加第 6 个元素后又将 65535 删除了之后,构造和增加之前是否一样!上面咱们带着这两个问题来一探到底!!!
降级
首先咱们针对第一问题来看看。原来五个元素都是 16 位就能够满足了,这个时候增加的 65535 是 32 位长度的。那么是不是能够间接追加 32 位调配给 65535 呢?
答案是必定不行,首先间接追加无奈保障数组元素的大小程序!其次如果前五个别离是 16 位,第 6 个是 32 位那么在 intset 构造中没有多余的字段来进行标记。也就是说在解析的时候就无奈判断应该解析 16 位还是 32 位了.
redis 为了不便解析所以在有高长度退出时会将整个 contents 进行降级。意思就是将整个 contents 先进行扩容,而后在从新填充数据
退出 65535
首先依据 length 能够确定扩容后元素个数为 6,每个占位 32,所以 contents 长度为 32*6=192。此时前 80 位内容放弃不变
旧数据移位
开拓了足够的空间后,咱们就能够对旧数据进行移位了这里咱们从原数组的开端开始挪动,在挪动之前须要明确在新数组中的排序地位。
此时咱们首先将 321 进行比对确定在新数组中他的排名是第五名,那么他将占用新 contents 中 128~159 区间。
最终前 5 个元素就会被挪动好。
最初将新退出的元素填充进去。当产生降级时必定是因为新元素的长度大于原有长度了。那么他的值肯定会是在新数组的两端。正数在最左侧,负数在最右侧
降级
接下来就是第二个问题当新退出的 65535 又被删除了 redis 该怎么办,这个时候元素长度理论 16 位就能够满足了,然而此时 encoding 却是 32 位的。依照我的认识应该在实现降级!
然而遗憾的是 redis 并没有,那么请思考为什么没有?如果让你实现你将如何实现
为什么不实现降级
当退出元素超过以后长度咱们很容易就晓得此时须要进行降级操作,然而当咱们删除一个数据时咱们如何判断是否须要降级却很艰难,咱们须要从新遍历一遍剩下的元素是否小于以后长度,实现复杂度 O(N)。这就是为什么不进行降级起因之一
你可能会说从新遍历一遍很快的反正在内存中,那么你有没有想过如果降级之后又遇到降级状况,这样来回的降级降级就升高了咱们程序的性能了。咱们晓得降级是必须的所以这里降级 redis 采取的是疏忽的策略
小结