本文首发于公众号：Hunter 后端
原文链接：Redis 数据结构三之压缩列表
本篇笔记介绍压缩列表。
在 Redis 3.2 版本之前，压缩列表是列表对象、哈希对象、有序汇合对象的的底层实现之一。
因为压缩列表自身构造上的一些缺点，压缩列表这个构造被替换了，然而压缩列表构造自身有一些可取之处，并且替换它的新构造 listpack 与之很类似，所以咱们这里还是介绍一下压缩列表的构造和存储
1、压缩列表的构造
压缩列表是 Redis 为了节约内存而开发的，由一个间断内存块组成的程序型数据结构。
它的组成构造如下：
`
| zlbytes | zltail | zllen | entry1 | entry2 | … | entryN | zlend |
`
压缩列表的英文名是 ziplist，所以它的属性都是 zl 结尾。
1. 列表属性介绍
zlbytes
zlbytes 长度为 4 字节，记录整个压缩列表占用的内存字节数
zltail
zltail 长度为 4 字节，记录压缩列表最初一个节点，也就是咱们构造示例中的 entryN 到 zlbytes 的地址之间的偏移量。
zllen
zllen 长度为 2 字节，记录的是压缩列表蕴含的节点数量，也就是构造中的 N。
zlend
zlend 长度为 1 字节，它的值为 0xFF（十进制 255），用于标记压缩列表的末端。
2. 压缩列表节点属性介绍
对于每一个 entry 节点，也就是压缩列表中的元素节点，它的构造示意如下：
`
| previous_entry_length | encoding | content |
`
previous_entry_length
previous_entry_length 属性记录的是压缩列表中前一个节点的长度
previous_entry_length 属性自身的长度能够是 1 字节或者 5 字节
如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性的长度为 1 字节，前一个节点的长度保留在这个字节里
如果前一节点的长度大于等于 254 字节，那么 previous_entry_length 属性的长度为 5 字节，第一个字节被设置成 0xFE（也就是 254），之后的四个字节用于前一节点的长度。
通过 previous_entry_length 属性，咱们能够通过以后节点的地址和 previous_entry_length 属性，计算出前一个节点的起始地址，压缩列表的从表尾到表头的遍历操作就是应用这个原理一个节点一个节点往前回溯实现的。
encoding
encoding 属性记录了节点的 content 属性所保留数据的类型以及长度。
encoding 的值如果是一字节长，且值的最高位以 11 结尾，那么示意是整数编码，示意 content 属性保留着整数值。
encoding 的值为 一字节、两字节、五字节长，且值的最高位为 00、01、10 则示意是字节数组编码
content
content 属性保留的是节点的值，能够是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。
2、连锁更新
在压缩列表的节点属性中，previous_entry_length 属性的长度是依据前一节点的长度来进行赋值的，如果前一节点的长度小于 254 字节，那么下一节点的 previous_entry_length 属性长度为 1 字节，如果前一节点的长度大于等于 254 字节，那么下一节点的 previous_entry_length 属性为 5 字节。
那么在这种状况下，就存在一种较为极其的状况，那就是压缩列表中每个节点的长度都在 250 – 253 字节之间，这时候，如果在表头插入一个长度大于等于 254 字节的节点，那么绝对应的第二个节点的 previous_entry_length 的长度就要从 1 字节变为 4 字节，那么该节点的整体长度就大于等于 254 字节。
依此类推，压缩列表的每一个节点的长度都会产生连锁反应，长度都会一一变成大于等于 254 字节长度，程序就须要一直地对压缩列表执行空间重调配的操作。
Redis 将这种在非凡状况下产生的间断屡次空间扩大操作称为 连锁更新。
除了新增节点这种状况，还有一种删除节点也可能造成连锁更新的状况，比方有这么几个节点，big 节点的长度大于等于 254 字节，small 节点长度小于 254 字节，e1 到 eN 的节点长度都在 250-253 字节之间。
`
| zlbytes | zltail | zllen | big | small | entry1 | entry2 | … | entryN | zlend |
`
这时候，删除 small 节点，entry1 节点的前节点的长度就会从 250-253 变成大于等于 254，因而 entry1 节点的 previous_entry_length 长度就会变成 5 字节，entry1 整体长度就会大于等于 254 字节，顺次之后每个节点都会这样产生连锁更新。
只管连锁更新的复杂度较高，但它真正造成性能问题的几率是很低的：
首先，压缩列表里要恰好有多个间断的、长度介于 250-253 字节之间的节点，连锁反应才有可能被引发
其次，即便呈现连锁更新，但只有被更新的节点数量不多，就不会对性能造成任何影响，比方对只领有三五个节点的压缩列表进行连锁更新。
3、压缩列表毛病
压缩列表尽管能节约内存，但依然存在一些毛病：
- 须要通过遍历操作来查找节点，元素过多时会造成查问效率低下
- 对压缩列表节点进行新增或者批改时，可能会造成连锁更新的问题
如果想获取更多相干文章，可扫码关注浏览：