【redis前传】集思广益之quicklist，取其精华去其糟粕

怼烎@ 2022-09-12 05:52 140阅读 0赞

# 前言 #

*  在之前我们已经学习了redis五大数据结构中的list结构。其内部是linkedList和zipList两种结构。这是我们已经学习的内容。之前我没有结合操作具体查看。事实上在两者中还存在一种结合体quickList

![image-20210715191310177][]

# 结构演变 #

*  在上面我们添加了一个key为zlist的数据。通过object encoding zlist查看底层就是通过quicklist来构建的。之前在ziplist章节汇总我们了解到在redis中hash和list基本数据结构都使用了ziplist存储数据的。在list中我们确实quicklist。这里我们提前说明下quicklist内部就是基于ziplist来实现的。

## linkedList ##

*  在开场quicklist之前我们简单梳理下之前学过的linkedList ，他是一种常见的双线链表。通过两个指针完成我们链表的构建。

![image-20210723133046693][]

## C++指针 ##

*  redis是基于内存运行的，而内存有十分的宝贵所以redis在设计了双线链表后觉得有点耗内存。因为指针本身也是需要开辟空间的。根据系统的不同指针占位不同。这里我总结了一下一个指针占位就是一个系统操作的基本位
 *  这里基本位是什么意思呢？加入你是64位系统那么一个指针就是64位即8个字节。如果你是32位系统那么一个指针就是32位即4个字节
 *  也就是说如果我在redis中向双向链表中存储N个英文字母，我们又知道一个应为字母占1个字节。那么这N个元素就是N的listNode . 那么维持着N个listNode中间就需要2\*(N-1)个指针。在64位系统中也就是我们需要开辟将近129倍的空间来存储内容。上述情况我们只有N个字节的内容，却需要`2*(N-1)*8+N`个字节来构建listNode。
 *  随着节点的递增我们浪费程度越离谱。所以redis在双向链表的基础上结合了ziplist进行改良。

## 过渡原因 ##

![image-20210723133853290][]

## ziplist ##

*  在ziplist章节中我们知道ziplist是一块连续内存，是redis对内存的一种改良结构。ziplist实现了内存的高使用率！

![image-20210723134013816][]

## linkedlist+ziplist好处 ##

![image-20210723134105776][]

# quicklist引入 #

*  quicklist是在redis3.2之后引入的，笔者这里使用的是redis6.4方便源码好像并没有quicklist源码。
 *  后来翻阅了之后redis6.4好像取消了quicklist . 结构。所以我又特别下了一个3.2的版本。这里具体的是redis3.2.4版本！！！

# 庐山真面目 #

## quicklist ##

![image-20210723134438938][]

*  通过他的源码我们很清晰的看出他的内部数据结构！这个大家应该很熟悉了。quicklist可以说就是我们之前的linkedList 结构。内部就是双向链表只不过里面的属性稍微多了点

![image-20210723134617683][]

*  通过图示是不是感觉和linkedList一样。

![image-20210723134817146][]

*  接下来我们看看quicklist中各个属性的含义吧

![image-20210723134859582][]

## quicklistNode ##

*  quicklist只是一个抽象的概念，真正负责数据的存储的是组成quicklist的成员quicklistNode 。

![image-20210723135204092][]

*  各个属性的作用

![image-20210723135327554][]

*  通过上面的属性介绍，我们也可以了解了解到node节点中的数据结构就是ziplist 。在ziplist基础上会在进行压缩达到内存更高的使用效率！
 *  关于压缩这里我们不用太去了解！主要目的就是一种编码，这种编码是无法真正使用的在使用期间redis会进行解码操作。在解码操作期间就是通过recompress属性来标记的。

![image-20210723135734482][]

# insert #

*  在了解quicklist基本结构之后我们在看看insert时结构会发生哪些变化！上面我们也提到了在redis.conf配置文件中`list-max-ziplist-size`属性是用来设置quicklist中每个节点中的ziplist存储的大小设置的。

<table> 
 <thead> 
  <tr> 
   <th>属性值</th> 
   <th>作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>-1</td> 
   <td>每个quicklistNode节点的ziplist所占字节数不能超过4kb</td> 
  </tr> 
  <tr> 
   <td>-2</td> 
   <td>每个quicklistNode节点的ziplist所占字节数不能超过8kb</td> 
  </tr> 
  <tr> 
   <td>-3</td> 
   <td>每个quicklistNode节点的ziplist所占字节数不能超过16kb</td> 
  </tr> 
  <tr> 
   <td>-4</td> 
   <td>每个quicklistNode节点的ziplist所占字节数不能超过32kb</td> 
  </tr> 
  <tr> 
   <td>-5</td> 
   <td>每个quicklistNode节点的ziplist所占字节数不能超过64kb</td> 
  </tr> 
  <tr> 
   <td>int</td> 
   <td>ziplist包含的entry上限</td> 
  </tr> 
 </tbody> 
</table>

### 两端插入 ###

![image-20210723140744723][]

*  第一种情况就是我们需要插入的数据是在两端的。如上图所示我们在redis.conf配置文件中设置的`list-max-ziplist-size: 2` 。表示内部节点ziplist中entry个数最大为2 。此时我们head头部节点中已经存储了两个内容，tail尾部节点存储的是1个节点！
 *  这个时候如果我们想头部添加一个元素是obj1 。 可想而知我们是无法加入的，这个时候redis会重新创建一个ziplist结构并包含obj1 ，将新创建的ziplist加入到链表的头部之后

![image-20210723141323765][]

*  而obj2加入尾结点时，因为尾结点的节点数是1还未达到峰值2，所以直接就加入了。最终的效果图如下

![image-20210723141540152][]

### 中间插入 ###

Created with Raphaël 2.3.0Insertziplist是否可以容纳向ziplist中插入插入位置在ziplist两端相邻ziplist是否可以容纳插入相邻的ziplist中新建ziplist插入将该ziplist拆分两个ziplist， 在对应位置加入yesnoyesnoyesno

# 总结 #

![image-20210723144626592][]

### 参考文献 ###

[lzf压缩算法][lzf]

[image-20210715191310177]: /images/20220828/c00a05eb83c04834993bbae503df0fa9.png
[image-20210723133046693]: /images/20220828/298a1babddd54fea95d5b2510cd3e57e.png
[image-20210723133853290]: /images/20220828/af44ba38a2e54ae0b45977f480cbf259.png
[image-20210723134013816]: /images/20220828/29bd74ef46814e99852c456e61254b96.png
[image-20210723134105776]: /images/20220828/969a184fdbc54329b0b8038aede3ea86.png
[image-20210723134438938]: /images/20220828/af81a0bc930b483c97a675dbf5c88337.png
[image-20210723134617683]: /images/20220828/32c2c1ad138c4588989069dfd28fb73e.png
[image-20210723134817146]: /images/20220828/cdc2fc17bd7143a7bd52ec688a6c1ef1.png
[image-20210723134859582]: /images/20220828/dc1c3da540694f7b8993897b3a291480.png
[image-20210723135204092]: /images/20220828/11d74a76ac194fcfa20048aab92b3041.png
[image-20210723135327554]: /images/20220828/3e7ef80ef4de426080f7ecbcf67787d1.png
[image-20210723135734482]: /images/20220828/da1a1a1eb6db4e60840ae634f83f00c9.png
[image-20210723140744723]: /images/20220828/9d6182bd19a04280b3921d196dfc99c8.png
[image-20210723141323765]: /images/20220828/4550ab1f914e4d2293723ee6c11699e0.png
[image-20210723141540152]: /images/20220828/c48a5c9c3ba8409cac7b3cf20d0a3bbc.png
[image-20210723144626592]: /images/20220828/e1cd5926c27d4478a2c955551e643f74.png
[lzf]: https://blog.csdn.net/yitouhan/article/details/108035859