Redis学习【5】之集合的底层实现原理

短命女 2024-03-27 16:50 49阅读 0赞

#### 文章目录 ####

*  一 集合的底层实现原理
 *   *  1.1 两种实现的选择
     *  1.2 zipList【存在于Redis7.0之前的版本】
     *  1.3 listPack【Redis7.0中zipList的改进版】
     *  1.4 skipList
     *   *  1.4.1 skipList 原理
         *  1.4.2 skipList存在的问题与优化
     *  1.5 quickList
     *   *  1.5.1 quitList检索操作
         *  1.5.2 quitList插入操作
         *  1.5.3 quitList删除操作
     *  1.6 key 与 value 中元素的数量

## 一 集合的底层实现原理 ##

*  Redis 中对于 Set 类型的底层实现，直接采用了 hashTable。但对于 Hash、ZSet、List 合的底层实现进行了特殊的设计，使其保证了 Redis 的高性能。

### 1.1 两种实现的选择 ###

*  对于Hash与ZSet集合，其底层的实现实际有两种：压缩列表zipList，与跳跃列表skipList。（对于用户来说是透明的，但用户写入不同的数据，系统会自动使用不同的实现。）
 *  只有同时满足以配置文件 `redis.conf` 中相关集合元素数量阈值与元素大小阈值两个条件，使用的就是**压缩列表 zipList**，**只要有一个条件不满足使用的就是跳跃列表 skipList。**
    
     *  例如，对于ZSet 集合中这两个条件如下：
        
         *  集合元素个数小于 `redis.conf 中 zset-max-ziplist-entries` 属性的值，其默认值为 `128`
         *  每个集合元素大小都小于 `redis.conf 中 zset-max-ziplist-value` 属性的值，其默认值为 `64`字节

### 1.2 zipList【存在于Redis7.0之前的版本】 ###

*  zipList通常称为压缩列表，是一个经过特殊编码的用于存储字符串或整数的双向链表。其底层数据结构由三部分构成：**head、entries 与 end 这三部分在内存上是连续存放的。**  
    ![在这里插入图片描述][1ad671daccde48f9bb23aa61a4263118.png]
 *  ***head的结构***：
    
     *  zlbytes：**占 4 个字节，用于存放 zipList 列表整体数据结构所占的字节数，包括 zlbytes本身的长度。**
     *  zltail：**占 4 个字节，用于存放 zipList 中最后一个 entry 在整个数据结构中的偏移量（字节）。** 该数据的存在可以快速定位列表的尾 entry 位置，以方便操作。
     *  zllen：**占 2 字节，用于存放列表包含的 entry 个数**。由于其只有 16 位，所以 zipList 最多可以含有的 entry 个数为 ： 2 1 6 − 1 = 65535 个 2^16-1 = 65535 个 216−1=65535个。

--------------------

*  ***entries的结构***：
    
     *  **entries 由很多的列表元素 entry 构成**。**由于不同的元素类型、数值的不同，从而导致每个 entry 的长度不同。**

--------------------

*  每个 **entry** 仍由三部分构成：
    
     *  **prevlength**：**该部分用于记录上一个 entry 的长度，以实现逆序遍历。** 默认长度为 1 字节，只要上一个 entry 的长度<254 字节，prevlength 就占 1 字节，否则，其会自动扩展为 3 字节长度。
     *  **encoding**：**用于标志后面的 data 的具体类型**。如果 data 为整数类型，encoding长度可能会是 1、2、3、4、5 或 9 字节。不同的字节长度，其标识位不同；如果 data为字符串类型，则 **encoding** 长度可能会是 1、2 或 5 字节。data 字符串不同的长度，对应着不同的 **encoding** 长度。
     *  **data**：**真正存储的数据**。数据类型只能是整数类型或字符串类型。不同的数据占用的字节长度不同。

--------------------

*  end
    
     *  end 只包含一部分——zlend：**占 1 个字节，值固定为 255，即二进制位为全 1，表示一个 zipList 列表的结束。**

### 1.3 listPack【Redis7.0中zipList的改进版】 ###

>  *  对于 ziplist，实现复杂，为了逆序遍历，每个 entry 中包含前一个 entry 的长度，这样会导致在 ziplist 中间修改或者插入 entry 时需要进行级联更新。
>  *  在高并发的写操作场景下会极度降低 Redis 的性能。为了实现更紧凑、更快的解析，更简单的实现，重写实现了 ziplist，并命名为 listPack。

*  **在 Redis 7.0 中，已经将 zipList 全部替换为了 listPack，但为了兼容性，在配置中也保留了 zipList 的相关属性。**  
    ![在这里插入图片描述][ecdc0f3086694765ada318dafd215c5f.png]
 *  **listPack 也是一个经过特殊编码的用于存储字符串或整数的双向链表。**
 *  **其底层数据结构由三部分构成：head、entries 与 end，且这三部分在内存上也是连续存放的。**

>  *  listPack与zipList的重大区别在head与每个entry的结构上：与 zipList 的 head 相比，没有了记录最后一个 entry 偏移量的 zltail；

--------------------

*  head  
    head 由两部分构成：
    
     *  **totalBytes：占 4 个字节，用于存放 listPack 列表整体数据结构所占的字节数，包括totalBytes 本身的长度。**
     *  **elemNum：占 2 字节，用于存放列表包含的 entry 个数。** 其意义与 zipList 中 zllen 的相同。

--------------------

*  **entries**
    
     *  **entries 是 listPack 中真正的列表，由很多的列表元素 entry 构成。** 由于不同的元素类型、数值的不同，从而导致每个 entry 的长度不同。
    
    >  *  但与 zipList 的 entry 结构相比，listPack的 entry 结构发生了较大变化。其中最大的变化就是没有了记录前一个 entry 长度的prevlength，而增加了记录当前entry 长度的 element-total-len。而这个改变仍然可以实现逆序遍历，但却避免了由于在列表中间修改或插入 entry 时引发的级联更新。

--------------------

*  每个 **entry** 仍由三部分构成：
    
     *  **encoding：该部分用于标志后面的 data 的具体类型。** 如果 data 为整数类型，encoding长度可能会是 1、2、3、4、5 或 9 字节。不同的字节长度，其标识位不同;如果 data为字符串类型，则 encoding 长度可能会是 1、2 或 5 字节。data 字符串不同的长度，对应着不同的 encoding 长度。
     *  **data：真正存储的数据。数据类型只能是整数类型或字符串类型。不同的数据占用的字节长度不同。**
     *  **element-total-len：该部分用于记录当前 entry 的长度，用于实现逆序遍历。** 由于其特殊的记录方式，使其本身占有的字节数据可能会是 1、2、3、4 或 5 字节。

--------------------

*  end
    
     *  end与zipList的 zlend 是相同的，占一个字节，且 8 位全为 1。

### 1.4 skipList ###

*  skipList——跳跃列表，简称**跳表，是一种随机化的数据结构，基于并联的链表，实现简单，查找效率较高。**
 *  **跳表也是链表的一种，只不过它在链表的基础上增加了跳跃功能。正是这个跳跃功能，使得在查找元素时，能够提供较高的率。**

#### 1.4.1 skipList 原理 ####

*  假设有一个带头尾结点的有序链表  
    ![在这里插入图片描述][cd4cce4252dd4306bccef123f7050644.png]
 *  在该链表中，如果要查找某个数据，需要从头开始逐个进行比较，直到找到包含数据的节点。如果找到第一个比给定数据大的节点，或者找到最后尾结点，后两种都属于没有找到的情况。同样地，当要插入新数据的时候，也要经历同样的查找过程，从而确定插入位置。
 *  为了提升查找效率，在偶数结点上增加一个指针，让其指向下一个偶数结点。  
    ![在这里插入图片描述][c287023e2c714c9cbd51c7ecffe4d29c.png]
 *  所有偶数结点就连成了一个新的链表（简称高层链表）。高层链表包含的节点个数只是原来链表的一半。此时再想查找某个数据时，先沿着高层链表进行查找。当遇到第一个比待查数据大的节点时，立即从该大节点的前一个节点回到原链表中进行查找。
    
     *  如：若想插入一个数据  20 20 20，则先在 （ 8 ， 19 ， 31 ， 42 ） （8，19，31，42） （8，19，31，42）的链表中查找，找到第一个比  20 20 20大的节 31 31 31，然后再在高层链表中找到  31 31 31 节点的前一个节点  19 19 19，然后再在原链表中获取到其下一个节点值为  23 23 23。比  20 20 20 大，则将  20 20 20 插入到  19 19 19 节点与  23 23 23 节点之间。若插入的是  25 25 25，比节点 23 23 23 大，则插入到  23 23 23 节点与  31 31 31 节点之间。

--------------------

*  该方式明显可以减少比较次数，提高查找效率。如果链表元素较多，为了进一步提升查找效率，可以将原链表构建为再高层级链表。  
    ![在这里插入图片描述][e5647f58e40b4c989d2082a1a240f1bd.png]

#### 1.4.2 skipList存在的问题与优化 ####

*  这种对链表分层级的方式从原理上看确实提升了查找效率，但在实际操作时就出现了问题：由于固定序号的元素拥有固定层级，所以列表元素出现增加或删除的情况下，会导致列表整体元素层级大调整，但这样会大大降低系统性能。
    
     *  例如，对于划分两级的链表，可以规定奇数结点为高层级链表，偶数结点为低层级链表。对于划分三级的链表，可以按照节点序号与 3 取模结果进行划分。但如果插入了新的节点，或删除的原来的某些节点，那么定会按照原来的层级划分规则进行重新层级划分，那么势必  
        会大大降低系统性能。

--------------------

*  解决方法：**随机层级方式**
 *  为了避免前面的问题，skipList 采用了**随机分配层级方式**。**即在确定了总层级后，每添加一个新的元素时会自动为其随机分配一个层级。** 这种随机性就解决了节点序号与层级间的固定关系问题。  
    ![随机层次方式][b39cb81921f3458bb031341e1d4d8d62.png]
 *  上图演示了列表在生成过程中为每个元素随机分配层级的过程。从这个 skiplist 的创建和插入过程可以看出，**每一个节点的层级数都是随机分配的，而且新插入一个节点不会影响到其它节点的层级数。** \*\*只需要修改插入节点前后的指针，而不需对很多节点都进行调整。\*\*这  
    降低了插入操作的复杂度。

--------------------

*  总结：
    
     *  skipList 指除了最下面第 1 层链表之外，它会产生若干层稀疏的链表，这些链表里面的指针跳过一些节点，并且越高层级的链表跳过的节点越多。在查找数据的时先在高层级链表中进行查找，然后逐层降低，最终可能会降到第  1 1 1 层链表来精确地确定数据位置。由于跳过一些节点，从而加快了查找速度。

### 1.5 quickList ###

![在这里插入图片描述][1b68daaa33b94bb0afae7e5d67b19018.png]

*  quickList(快速列表)——一个双向无循环链表，它的每一个节点都是一个zipList。

>  *  从Redis3.2版本开始，对于List的底层实现，使用quickList替代了zipList 和 linkedList。zipList 与 linkedList 都存在有明显不足，而 quickList 则对它们进行了改进：吸取了 zipList 和 linkedList 的优点，避开了它们的不足。

*  **quickList 本质上是 zipList 和 linkedList 的混合体**。*其将 linkedList 按段切分，每一段使用 zipList 来紧凑存储若干真正的数据元素，多个 zipList 之间使用双向指针串接起来。* 对于每个 zipList 中最多可存放多大容量的数据元素，在配置文件中通过 list-max-ziplist-size属性可以指定。

--------------------

#### 1.5.1 quitList检索操作 ####

*  对于  L i s t List List 元素的检索，都是以其索引  i n d e x index index 为依据的。 q u i c k L i s t quickList quickList由一个个的  z i p L i s t zipList zipList 构成，每个  z i p L i s t zipList zipList 的  z l l e n zllen zllen 中记录的是当前  z i p L i s t zipList zipList 中包含的  e n t r y entry entry 的个数（即包含的真正数据元素的个数）。根据要检索元素的  i n d e x index index，从  q u i c k L i s t quickList quickList 的头节点开始，逐个对  z i p L i s t zipList zipList 的  z l l e n zllen zllen 做  s u m sum sum求和，直到找到第一个求和后  s u m sum sum 大于  i n d e x index index 的  z i p L i s t zipList zipList，那么要检索的元素就在这个 z i p L i s t zipList zipList 中。

#### 1.5.2 quitList插入操作 ####

*  由于 `zipList` 是有大小限制的，所以在 `quickList` 中插入一个元素在逻辑上相对就比较复杂一些。
 *  假设要插入的元素的大小为 `insertBytes`，而查找到的插入位置所在的 `zipList` 当前的大小为 `zlBytes`，那么具体可分为下面几种情况：
    
     *  情况一：当 `insertBytes + zlBytes <= list-max-ziplist-size` 时，直接插入到 `zipList` 中相应位置即可
     *  情况二：当 `insertBytes + zlBytes > list-max-ziplist-size`，且插入的位置位于该 `zipList` 的首部位置，此时需要查看该 `zipList` 的前一个 `zipList` 的大小 `prev_zlBytes`。
        
         *  若 `insertBytes + prev_zlBytes<= list-max-ziplist-size` 时，直接将元素插入到前一个`zipList` 的尾部位置即可
         *  若 `insertBytes + prev_zlBytes> list-max-ziplist-size` 时，直接将元素自己构建为一个新的 `zipList`，并连入 `quickList` 中
     *  情况三：当 `insertBytes + zlBytes > list-max-ziplist-size`，且插入的位置位于该 `zipList` 的尾部位置，此时需要查看该 `zipList` 的后一个 `zipList` 的大小 `next_zlBytes`。
        
         *  若 `insertBytes + next_zlBytes<= list-max-ziplist-size` 时，直接将元素插入到后一个`zipList` 的头部位置即可
         *  若 `insertBytes + next_zlBytes> list-max-ziplist-size` 时，直接将元素自己构建为一个新的 `zipList`，并连入 `quickList` 中
     *  情况四：当 `insertBytes + zlBytes > list-max-ziplist-size`，且插入的位置位于该 `zipList` 的中间位置，则将当前 `zipList` 分割为两个 `zipList` 连接入 `quickList` 中，然后将元素插入到分割后的前面 `zipList` 的尾部位置

#### 1.5.3 quitList删除操作 ####

*  对于删除操作，在相应的 zipList 中删除元素后，该 zipList 中是否还有元素。如果没有其它元素了，则将该 `zipList` 删除，将其前后两个 `zipList` 相连接。

### 1.6 key 与 value 中元素的数量 ###

*  Redis 的各种特殊数据结构的设计，不仅极大提升了 Redis 的性能，并且还使得 Redis 可以支持的 key 的数量、集合 value 中可以支持的元素数量可以非常庞大。
    
     *  Redis 最多可以处理  2 3 2 2^32 232个 key（约 42 亿），并且在实践中经过测试，每个 Redis 实例至少可以处理 2.5 亿个 key。
     *  每个 `Hash、List、Set、ZSet` 集合都可以包含  2 3 2 2^32 232 个元素。

[1ad671daccde48f9bb23aa61a4263118.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/69a81d22e59d485ca46d51d3b4a21029.png
[ecdc0f3086694765ada318dafd215c5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/093a5d862df44b44aed09da1d5a0fc2b.png
[cd4cce4252dd4306bccef123f7050644.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/2bd3623a08754a24a0d0c2578dff2ee3.png
[c287023e2c714c9cbd51c7ecffe4d29c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bbe124eee7524c09974b12259a82f50b.png
[e5647f58e40b4c989d2082a1a240f1bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/7e034e54bccc49949efd4ba9da58ce82.png
[b39cb81921f3458bb031341e1d4d8d62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8b7d207c38254be38f01c5f313314c32.png
[1b68daaa33b94bb0afae7e5d67b19018.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/93b7bc890c734c46804bc139df227abe.png