Redis中的压缩列表（连锁更新） redis

压缩列表的应用压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做列表键的底层实现。

redis> RPUSH lst 1 3 5 10086 "hello" "world" (integer)6redis> OBJECT ENCODING lst "ziplist"

另外，当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。

redis> HMSET profile "name" "Jack" "age" 28 "job" "Programmer" OK redis> OBJECT ENCODING profile "ziplist"

压缩列表的构成压缩列表（ziplist）是列表和哈希的底层实现之一。当列表只包含少量的列表项，并且每个列表项要么是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做列表的底层实现。哈希同样。
压缩列表由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

文章图片

【Redis中的压缩列表（连锁更新）】

文章图片

压缩列表结点的构成每个压缩列表可以保存一个字节数组或者一个整数值。每个节点由previous_entry_length，encoding以及content组成。

文章图片

previous_entry__length记录前一个节点的长度，所以程序可以通过指针运算（当前节点的起始位置-previous_entry__length得到上一个节点的起始位置。），压缩列表从表尾遍历操作就是通过这个原理实现的。encoding属性记录节点的content属性所保存数据的类型以及长度。content保存节点的内容，可以是整数或者是字节数组。
previous_entry_length（重点）
● 如果前一节点的长度小于254字节，那么previous_entry__length属性的长度为1字节：前一节点的长度就保存在这一字节里面。
● 如果前一节点的长度大于等于254字节，那么previous_entry__length属性的长度为5字节：其属性的第一字节会被设置为0xFE（十进制254），而之后的四个字节长度则用于保存前一节点的长度。
连锁更新连锁更新是由于previous_entry_length造成的。
现在考虑这样一种情况：在一个压缩列表中，有多个连续的，长度介于250字节到253字节之间的节点e1-eN，如下图：

文章图片

因为e1到eN的长度都介于250字节到253字节之间，所以它们的previous_entry__length均为1字节。
现在将一个长度大于254字节的节点插入到e1前面，如下图：

文章图片

因为newE的长度大于254字节，所以他后面的e1的previous_entry__length长度需要从1字节变为5字节。但是由于e1原本的长度为250字节到253字节之间，这样子扩展后，长度必然超过254字节，就会导致后面的e2的previous_entry__length也需要改变…以此类推，后面的节点的previous_entry__length都需要扩展。Redis将这种特殊情况下产生的连续多次空间扩展操作称之为"连锁更新"。
除了插入节点会发生"连锁更新"。删除节点也会，如下图：

文章图片

假设small及后面的节点的长度都介于250-253字节，big长度大于254字节，现在把samll删除了，导致e1的previous_entry__length需要扩展，后面依此类推，这样就会发生"连锁更新"。
因为连锁更新在最坏的情况下需要对压缩列表执行N次空间重分配，而每次空间重分配的最坏复杂度为O(N)，所以连锁更新的最坏复杂度为O(N^2).