压缩列表时列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项都是小整数或者长度较短的字符串时，Redis 就会使用压缩列表来做列表键的底层实现
另外，当一个哈希键只包含少量键值对，并且每个键值对的键和值都是小整数或者长度较短的字符串时，Redis 就会使用压缩列表来做哈希键的底层实现
压缩列表的实现
压缩列表时 Redis 为了节约内存而开发的，是由一些列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保持一个字节数组或者整数值
压缩列表的各个组成部分
压缩列表各个组成部分详细说明
压缩列表示例
压缩列表节点构成
previous_entry_length
previous_entry_length 记录了前一个节点的长度，程序可以通过指针运算，根据当前节点的起始地址拉算出前一个节点的其实地址
压缩列表从表尾向表头的遍历就是使用这一原理实现的
encoding
encoding 记录了节点的 content 属性所保存的数据类型及长度
content
content 负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由 encoding 属性决定
连锁更新
每个节点的 previous_entry_length 属性都记录了前一个节点的长度：
- 如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值
- 如果前一节点的长度大于等于 254 字节，那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值
假设在一个压缩列表中，有多个连续的、长度介于 250 到 253 字节之间的节点 e1 至 eN：
因为 e1 至 eN 所有节点长度都小于 254 字节，所以这些节点长度的 previous_entry_length 都是 1 字节的
这时，如果在压缩列表头添加一个长度大于等于 254 字节的新节点：
因为 e1 的 previous_entry_length 属性仅长 1 字节，无法保存新节点的程度，所以程序将对压缩列表进行空间重分配，并将 e1 的 previous_entry_length 从原来的 1 字节长扩展为 5 字节长
这时 e1 的 previous_entry_length 属性新增了四个字节，e1 的长度大于等于 254 字节了，这样用 1 字节长的 previous_entry_length 就无法保存
因此，e2 的 previous_entry_length 属性也会被扩展。依次类推，后面所有节点都会被扩展，造成连锁更新
类似地，删除节点操作也可能会引发连锁更新：
因为连锁更新最坏情况下需要对压缩列表执行 N 次空间重分配，而每次空间重分配复杂度最坏为 O(N)，所以连锁更新最坏复杂度为 O(N^2)
尽管连锁更新复杂度较高，但真正造成性能问题的几率很低：
- 压缩列表里恰好有多个连续的、长度介于 250 到 253 字节之间的节点
- 即便出现连锁更新，只要被更新节点数目不多，影响就不大
所以添加删除节点的操作平均复杂度仅为 O(N)
网友评论