【redis前传】｜ 将内存节省到极致的一种数据结构ziplist ?在我们讲解 list 结构的时候提到了一种特殊的结构 ziplist ，俗称压缩列表。同时他也是 hash 结构和 list 结构采用的底层结构之一。他的出现是为了节省内存的一种结构。?当一个 list 结构的数据中只包含少量列表项且里面元素是小整数或者是短的字符串时 redis 底层就会使用 ziplist 来存储数据redis 的 ziplist 是一块连续内存块。我们可以简单理解成数组，相比较数组而言她却多了很多对节点关联的描述，比如说数组总长、最后一个地址偏移量、上一个节点的长度等等信息。上述是 redis 源码中对 ziplist 结构的一段描述！根据图中圈出部分我们可以简单的理解 ziplist 的总体结构那么这些分别代表着什么作用呢？他们又是如何将内容存储在连续内存块中的呢？每一块都有固定的内存空间表示这他的作用。只有 entry 因为是存储节点的所用他的长度是动态的。字段类型长度作用zlbytesunit32_t四字节，32 位整个 ziplist 占用字节数。zltailunit32_t四字节，32 位尾结点距离起始位置偏移量。这里需要尾结点句柄距离头部偏移量zllenunit16_t二字节，16 位节点个数 。16 位表示最大值 65535 。当元素超过 65535 时我们只能遍历获取节点个数entry ...entry动态 zlendunit8_t一字节，8 位固定值 0XFF 。用于表示标记位下面我们来看看一个列子针对 redis 源码中我做了解释。他的内存结构如图上述头部是有一定关联的。我们可以将头部进行简单规划为一个 head关于 previous_entry 就表示这前一个节点的长度。我们根据他就可以逆推值前一节点。这也解释了我们如何定位 ziplist 中的元素。我们可以根据 zlbytes 和 zltail 获取到尾结点。在根据尾结点的 previous_entry 获取前一节点。previous_entry这部分我们简单理解他会占用 5 字节 (最大情况) 。redis 考虑到内存的紧凑型这地方会优先使用 1 字节来记录当 1 字节不满足情况下类似于 intset 一样这时候会用 5 字节来表示。5 字节去除第一字节固定值正好能表示 32 数字是我们 int 类型的数字范文。这里也正好呼应我开头说的 ziplist 的使用场景。ziplist 主要是用来存储小整数或者是短字符。他们很小或者很短的情况下 entry 的节点长度也不会太大，极大的情况下 8 位就可以表示了他们的长度！这里也可以看出 redis 真的对内存把握的死死的。当超出了 254redis 的 previous_entry 相当于升级了扩展成了 5 字节，其中第一字节设置为 0XFE 固定值。而后面四字节表示前一节点的实际长度疑问？为什么固定值是 0XFE首先只有第一字节被设置成固定值，1 个字节在 16 进制中常见的是 FF 用来表示。但是这里为什么不是 FF 。因为在 ziplist 中 0XFF 用于表示 zlend 标记。所以这里前移用 0XFE 作为 entry 的标记。encodingencoding 属性记录了节点的数据的类型以及长度！简单描述就是记录了内容的特征上述是 redis 源码对 entry 的一个解释。我针对他做了一份表格统计。编码长度 (字节)值00aaaaaa1长度 =63 字符串01pppppp|qqqqqqqq2长度 =16383 字符串10xxxxxx|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt5长度 =4294967295 字符串110000001int16110100001int32111000001int6411110000124 位有符号整数1111111018 位有符号整数1111xxxx (xxxx 的取值范围【0000 ， 1101）)10~1211111111ziplist 结束位 所有的 encoding 除了 11111111 固定结束位，其他所有的前两位用于表示数据类型 前两位 11 表示整数；00 表示字节长的字符串；01 表示字节字符串；10 表示 5 字节字符串 计算长度就是 encoding 去除前两位后表示的数字就是属性的长度。 00001000首先开头是 00，我们根据手册可以知道 entry 中存储的是 1 字节的字符串，那么他的长度是多少的呢？是二进制的 1000 即长度为 8.8 位也就是 1 个字节，也就是说他表示的节点内部存储的内容是 1 字节内容，可能是 a01000001,00000000首先开头是 01 表示长度为 2 字节的字符。去除开头两位翻译成十进制是 256。表示 32 字节的内容。我们可以理解成该 entry 存储了 32 个英文字母后续的就不在进行举例。根据 encoding 我们就可以确定 entry 的内容及长度。内容节点的 p 是用于保存实际内容的。根据上面 encoding 的介绍我们了解到内容可以是字符串也可以是整数。 所以在计算 entry 的长度时我们是不需要看实际内容的长度的，因为他的长度已经在 encoding 里了。 还记得上面我们展示的 ziplist 草图吗，在哪里我们标注了 zlbytes、zltail、zllen 、 entryx 、 zlend 等占位说明。现在我们将完善这幅草图 在上面这张图我们加入了三个节点的内存图示。在这里我们将清楚的了解 entry 的结构。但是最终的内部还是将头部的展示进行了细分在上面我们知道 previous_entry 是用于标记前一节点的长度，而且当时我们也说了 redis 为了节省内存会先尝试用 1 字节来表示当长度超出 254 时才会扩容为 4 字节长度。这就意味着我们每个 entry 节点长度都是动态的，换言之我们每个 entry 都会受到前一节点的影响 比如说现在我们的 entry 的长度都在 250~254 之间。如下图 这个时候我们需要在头部添加一个长度为 254 的节点。因为该节点 254 所以我们上面第一个节点的 previous_entry 将会由 1 变成了 5 字节。从而影响到整个 entry 由原来的 250 字节变成了 254 字节。因为第一个节点变成了 254 字节从而又递归影响了原来第二节点！redis 将这种添加节点到头部引发的连锁反应称之为连锁更新。同样的道理我们在删除的时候也会遇到类似情况，应该这两种情况统称为连锁更新！首先我们从结构上解析了 ziplist 的属性，然后从 ziplist 中主要角色 entry 出发继续解析内部结构说明。在 entry 中我们大体分成三部分。其中 previous_entry 因为取决于前一节点，从而牵扯出 redis 重要问题【连锁更新】 。连锁更新发生的概览很是罕见。每个节点长度在 25-~253 范围内才会发生连锁更新，这本身概览就很低。其次在添加的节点是 254 本身也很低了。因为 ziplist 主要是小整数或者短字符使用的。而且当节点很少的情况下即使发生连锁更新我们也是可以接受的。毕竟在内存中。综上！ziplist 主要使用在小整数、短字符等数据量少的情况最佳！！！ 阅读原文