【redis前传】redis整数集为什么不能降级

╰半橙微兮° 2022-08-30 14:53 118阅读 0赞

# 前言 #

整数集合相信有的同学没有听说过，因为redis对外提供的只有封装的五大对象！而我们本系列主旨是学习redis内部结构。内部结构是redis五大结构重要支撑！

前面我们分别从redis内部结构分析了redis的List、Hash、Zset三种数据结构了。今天我们再来分析set数据结构内部是如何存储的

# 基本结构 #

*  在src/t\_set.c中我们发现这样一段代码

![image-20210706105819274][]

*  由此我们可知在set中是由两种数据结构构成的： hashtable+intset 。关于redis内部其他的结构我专门在[【redis专栏中有介绍】][redis]。hashtable不是我们今天的主角，我们今天先分析intset俗称整数集合。

![image-20210706110151754][]

*  从上图中我们可以看出，我构造了两个set集合分别为【commonset】、【cs】。两个集合前者存储字符串、后者专门存储数字。
 *  我们在通过`object encoding key` 来查看下两个集合的底层数据结构，发现一个是hashtable 一个是intset 。这也验证了我们上面对set基本结构的描述。
 *  在redis中对外提供五大类型实际上都是redis的一个抽象对象叫做redisobject。在内部映射了我们redis内部的数据结构

![image-20210706111432308][]

*  针对commonset和cs两个集合在内部数据结构大概可以这么理解

![image-20210706112349968][]

# 何时使用intset #

*  你可以单纯的认为只要是数字就会使用intset结构来存储，我恐怕要给你当头一棒了。实际上并不是这样
 *  需要同时满足以下两个条件：

![image-20210706113636870][]

![image-20210706113647350][]

# intset #

![image-20210706133736601][]

*  图中表示的很清楚了，在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位。他的取值范围是

− 2 7 ∼ 2 7 − 1 即 − 128 ∼ 127 -2^\{7\} \\sim 2^\{7\}-1 \\\\ 即 \\\\ -128 \\sim 127 −27∼27−1即−128∼127

![image-20210706135925132][]

# 添加元素 #

sadd juejin -123
    sadd juejin -6
    sadd juejin 12
    sadd juejin 56
    sadd juejin 321

*  juejin这个key内部就是intset 。

![image-20210706162521929][]

*  上面我们添加了5个元素且这五个元素的长度都在16之内！所以当前的intset的encoding=INTSET\_ENC\_INT16。-123在contents中占前16位。
 *  所以当前五个元素占contents的长度是16\*5=80 ；
 *  注意set在存储int类型数据时，内部是按照从小到大的顺序存储的。

# 类型变动 #

![image-20210706164922957][]

*  上面的问题不知道你有没有考虑过，或者说有没有遇到过！intset默认是int16位，正如我们上面添加的五个元素。加入此时我们添加第6个元素是65535(32位)。那么此时16位的长度就不够存储了这个时候intset会怎么做！
 *  另外当我们添加第6个元素后又将65535删除了之后，结构和添加之前是否一样！下面我们带着这两个问题来一探究竟！！！

## 升级 ##

*  首先我们针对第一问题来看看。原来五个元素都是16位就可以满足了，这个时候添加的65535是32位长度的。那么是不是可以直接追加32位分配给65535呢？
 *  答案是肯定不行，首先直接追加无法保证数组元素的大小顺序！其次如果前五个分别是16位，第6个是32位那么在intset结构中没有多余的字段来进行标记。也就是说在解析的时候就无法判断应该解析16位还是32位了.
 *  redis为了方便解析所以在有高长度加入时会将整个contents进行升级。意思就是将整个contents先进行扩容，然后在重新填充数据

![image-20210706171505334][]

### 加入65535 ###

*  首先根据length可以确定扩容后元素个数为6 ， 每个占位32，所以contents长度为32\*6=192 。 此时前80位内容保持不变

![image-20210706171605386][]

### 旧数据移位 ###

*  开辟了足够的空间后，我们就可以对旧数据进行移位了这里我们从原数组的末尾开始移动，在移动之前需要明确在新数组中的排序位置。
 *  此时我们首先将321进行比对确定在新数组中他的排名是第五名，那么他将占用新contents中128~159区间。

![image-20210706172455270][]

*  最终前5 个元素就会被移动好 。

![image-20210706172652958][]

*  最后将新加入的元素填充进去。当发生升级时肯定是因为新元素的长度大于原有长度了。那么他的值一定会是在新数组的两端。负数在最左侧，正数在最右侧

![image-20210706172836896][]

## 降级 ##

*  接下来就是第二个问题当新加入的65535又被删除了redis该怎么办，这个时候元素长度实际16位就可以满足了，但是此时encoding却是32位的。按照我的看法应该在实现降级！
 *  但是遗憾的是redis并没有，那么请思考为什么没有？如果让你实现你将如何实现

### 为什么不实现降级 ###

*  当加入元素超过当前长度我们很容易就知道此时需要进行升级操作，但是当我们删除一个数据时我们如何判断是否需要降级却很困难，我们需要重新遍历一遍剩下的元素是否小于当前长度，实现复杂度O(N) 。这就是为什么不进行降级原因之一
 *  你可能会说重新遍历一遍很快的反正在内存中，那么你有没有想过如果降级之后又遇到升级情况，这样来回的升级降级就降低了我们程序的性能了。我们知道升级是必须的所以这里降级redis采取的是忽略的策略

## 小结 ##

![image-20210707135328472][]

[参考资料：内存升级优化内存降级][Link 1]

[image-20210706105819274]: /images/20220829/f43817ffce2348d29d7b352064418a36.png
[redis]: https://juejin.cn/column/6978749088464371725
[image-20210706110151754]: /images/20220829/ca82dfc651fb4070b98e679ef270a6c9.png
[image-20210706111432308]: /images/20220829/0253d6cf682f4c2fb787ab029d7c7e8d.png
[image-20210706112349968]: /images/20220829/2f9a93bed3fd44e3947ee34c881f1844.png
[image-20210706113636870]: /images/20220829/5f881bc1a5ee4238bff8afbf016406b3.png
[image-20210706113647350]: /images/20220829/41c3dadd11bc41c880418442462ce482.png
[image-20210706133736601]: /images/20220829/0167025ab6304e7dbb4012bd743f7a2a.png
[image-20210706135925132]: /images/20220829/4882e7d3a45d45f48a14b63fdee45bdb.png
[image-20210706162521929]: /images/20220829/3c01d26412f941e4b350465fa5ce7efb.png
[image-20210706164922957]: /images/20220829/24e6e02e71914343b6bb25e26fd71f6d.png
[image-20210706171505334]: /images/20220829/a5097adbdf154fddbb62731d2f29d8ee.png
[image-20210706171605386]: /images/20220829/8d52523820c34fe998bd06d184101d13.png
[image-20210706172455270]: /images/20220829/1608069d0888421b88490d7714ac1a4c.png
[image-20210706172652958]: /images/20220829/87ce2bc2a57f48a48d474c96c92b8bbc.png
[image-20210706172836896]: /images/20220829/ced8aed2b46a485b835f7efa1fd59ee1.png
[image-20210707135328472]: /images/20220829/eed19c6920d84a2aa79b05e97342c473.png
[Link 1]: https://www.cnblogs.com/lonelytree/archive/2013/05/30/3109207.html