紧缩列表牺牲速度来节省内存，Redis是膨胀了吗

正常情况下我们选择使用 Redis 就是为了提升查询速度，但是让人意外的是，Redis 当中却有一种比较成心思的数据结构，这类数据结构通过牺牲部份读写速度来到达节省内存的目的，这就是 ziplist（紧缩列表），Redis 为何要这么做呢？难道真的是觉得自己的速度太快了，牺牲一点速度也不影响吗？

甚么是紧缩列表

ziplist 是为了节省内存而设计出来的一种数据结构。ziplist 是由一系列特殊编码组成的连续内存块的顺序型数据结构，一个 ziplist 可以包括任意多个 entry，而每个 entry 又可以保存一个字节数组或一个整数值。

ziplist 作为一种列表，其和普通的双端列表，如 linkedlist 的最大区分就是 ziplist 其实不存储前后节点的指针，而 linkedlist 一般每一个节点都会保护一个指向前置节点和一个指向后置节点的指针。那末 ziplist 不保护前后节点的指针，它又是如何寻觅前后节点的呢？

ziplist 虽然不保护前后节点的指针，但是它却保护了上一个节点的长度和当前节点的长度，然后每次通太长度来计算出前后节点的位置。既然触及到了计算，那末相对直接存储指针的方式肯定有性能上的消耗，这就是一种典型的用时间来换取空间的做法。由于每次读取前后节点都需要经过计算才能得到前后节点的位置，所以会消耗更多的时间，而在 Redis 中，一个指针是占了 8 个字节，但是大部份情况下，如果直接存储长度是达不到 8 个字节的，所以采取存储长度的设计方式在大部份场景下是可以节省内存空间的。

ziplist 的存储结构

ziplist 的组成结构为：

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

其中 zlbytes，zltail，zllen 为 ziplist 的 head 部份，entry 为 ziplist 的 entries 部份，每个 entry 代表一个数据，最后 zlend 表示 ziplist 的 end 部份，以下图所示：

ziplist 中每一个属性代表的含义以下表格所示：

entry 存储结构

ziplist 的 head 和 end 存的都是长度和标记，而 entry 存储的是具体元素，这又是经过特殊的设计的一种存储格式，每一个 entry 都以包括两段信息的元数据作为前缀，每个 entry 的组成结构为：

<prevlen> <encoding> <entry-data>

prevlen

prevlen 属性存储了前一个 entry 的长度，通过此属性能够从后到前遍历列表。 prevlen 属性的长度多是 1 字节也多是 5 字节：

当链表的前一个 entry 占用字节数小于 254，此时 prevlen 只用 1 个字节进行表示。

<prevlen from 0 to 253> <encoding> <entry>

当链表的前一个 entry 占用字节数大于等于 254，此时 prevlen 用 5 个字节来表示，其中第 1 个字节的值固定是 254（相当因而一个标记，代表后面跟了一个更大的值），后面 4 个字节才是真正存储前一个 entry 的占用字节数。

0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>

注意：1 个字节完全你能存储 255 的大小，之所以只取到 254 是由于 zlend 就是固定的 255，所以 255 这个数要用来判断会不会是 ziplist 的结尾。

encoding

encoding 属性存储了当前 entry 所保存数据的类型和长度。encoding 长度为 1 字节，2 字节或 5 字节长。前面我们提到，每个 entry 中可以保存字节数组和整数，而 encoding 属性的第 1 个字节就是用来肯定当前 entry 存储的是整数或者字节数组。当存储整数时，第 1 个字节的前两位总是 11，而存储字节数组时，则多是 00、01 和 10 三种中的一种。

当存储整数时，第 1 个字节的前 2 位固定为 11，其他位则用来记录整数值的类型或整数值（下表所示的编码中前两位均为 11）：

注意：xxxx 四位编码范围是 0000⑴111，但是 0000，1111 和 1110 已被表格中前面表示的数据类型占用了，所以实际上的范围是 0001⑴101，此时能保存数据 1⑴3，再减去 1 以后范围就是 0⑴2。至于为何要减去 1 是从使用习惯来讲 0 是一个非常经常使用的数据，所以才会选择统一减去 1 来存储一个 0⑴2 的区间而不是直接存储 1⑴3 的区间。

当存储字节数组时，第 1 个字节的前 2 位为 00、01 或 10，其他位则用来记录字节数组的长度：

entry-data

entry-data 存储的是具体数据。当存储小整数（0⑴2）时，由于 encoding 就是数据本身，此时 entry-data 部份会被省略，省略了 entry-data 部份以后的 ziplist 中的 entry 结构以下：

<prevlen> <encoding>

紧缩列表中 entry 的数据结构定义以下（源码 ziplist.c 文件内），固然实际存储并没有直接使用到这个结构定义，这个结构只是用来接收数据，所以大家了解一下就能够了：

typedef struct zlentry {
 unsigned int prevrawlensize;//存储prevrawlen所占用的字节数
 unsigned int prevrawlen;//存储上一个链表节点需要的字节数
 unsigned int lensize;//存储len所占用的字节数
 unsigned int len;//存储链表当前节点的字节数
 unsigned int headersize;//当前链表节点的头部大小(prevrawlensize + lensize)即非数据域的大小
 unsigned char encoding;//编码方式
 unsigned char *p;//指向当前节点的起始位置(由于列表内的数据也是一个字符串对象)
} zlentry;

ziplist 数据示例

上面讲授了大半天，可能大家都觉得枯燥无味了，也可能会觉得云里雾里，这个没有关系，这些只要心里有个概念，用到的时候再查询对应资料就能够了，其实不需要全部记住，接下来让我们一起通过两个例子来体会一下 ziplist 究竟是如何来组织存储数据的。

下面就是一个紧缩列表的存储示例，这个紧缩列表里面存储了 2 个节点，节点中存储的是整数 2 和 5：

[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
  |    |   |  |  |  |
 zlbytes  zltail  zllen "2"  "5" end

第一组 4 个字节为 zlbytes 部份，0f 转成二进制就是 1111 也就是 15，代表全部 ziplist 长度是 15 个字节。第二组 4 个字节 zltail 部份，0c 转成二进制就是 1100 也就是 12，这里记录的是紧缩列表尾节点距离起始地址有多少个字节，也就是就是说 [02 f6] 这个尾节点距离起始位置有 12 个字节。第三组 2 个字节就是记录了当前 ziplist 中 entry 的数量，02 转成二进制就是 10，也就是说当前 ziplist 有 2 个节点。第四组 2 个字节 [00 f3] 就是第一个 entry，00 表示 0，由于这是第 1 个节点，所之前一个节点长度为 0，f3 转成二进制就是 11110011，恰好对应了表格中的编码 1111xxxx，所以后面四位就是存储了一个 0⑴2位的整数。0011 转成十进制就是 3，减去 1 得到 2，所以第一个 entry 存储的数据就是 2。第五组 2 个字节 [02 f6] 就是第二个 entry，02 即为 2，表示前一个节点的长度为 2，注意，由于这里算出来的结果是小于 254，所以就代表了这里只用到了 1 个字节来存储上一个节点的长度（如果等于 254，这说明接下来 4 个字节才存储的是长度），所以后面的 f6 就是当前节点的数据，转换成二进制为 11110110，对应了表格中的编码 1111xxxx，一样的后四位 0110 存储的是真实数据，计算以后得出是5。最后一组1个字节[ff]转成二进制就是 11111111，代表这是全部 ziplist 的结尾。

假设这时候候又添加了一个 Hello World 字符串到列表中，那末就会新增一个 entry，以下所示：

[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]

第一组的 1 个字节 02 转成十进制就是 2 ，表示前一个节点（即上面示例中的 [02 f6]）长度是 2。第 二组的2 个字节 0b 转成二进制为 00001011，以 00 开头，符合编码 00pppppp，而除掉最开始的两位 00，计算以后得到十进制 11，这就说明后面字节数组的长度是 11。第三组恰好是 11 个字节，对应了上面的长度，所以这里就是真正存储了 Hello World 的字节数组。

ziplist 连锁更新问题

上面提到 entry 中的 prevlen 属性多是 1 个字节也多是 5 个字节，那末我们来假想这么一种场景：假定一个 ziplist 中，连续多个 entry 的长度都是一个接近但是又不到 254 的值（介于 250~253 之间），那末这时候候 ziplist 中每一个节点都只用了 1 个字节来存储上一个节点的长度，假设这时候候添加了一个新节点，如 entry1 ，其长度大于 254 个字节，此时 entry1 的下一个节点 entry2 的 prelen 属性就一定要要由 1 个字节变成 5 个字节，也就是需要履行空间重分配，而此时 entry2 由于增加了 4 个字节，致使长度又大于 254 个字节了，那末它的下一个节点 entry3 的 prelen 属性也会被改变成 5 个字节。依此类推，这类产生连续屡次空间重分配的现象就称之为连锁更新。一样的，不单单是新增节点，履行删除节点操作一样可能会产生连锁更新现象。

虽然 ziplist 可能会出现这类连锁更新的场景，但是一般如果只是产生在少数几个节点之间，那末其实不会严重影响性能，而且这类场景产生的几率也比较低，所以实际使用时不用过于担心。

总结

本文主要讲授了 Redis 当中的 ziplist（紧缩列表），一种用时间换取空间的数据结构，在介绍紧缩列表存储结构的同时通过一个存储示例来分析了 ziplist 是如何存储数据的，最后介绍了 ziplist 中可能产生的连锁更新问题。

到此这篇关于紧缩列表牺牲速度来节省内存，Redis是膨胀了吗的文章就介绍到这了,更多相关Redis紧缩列表内容请搜索之前的文章或继续浏览下面的相关文章希望大家以后多多支持！