压缩列表(ziplist)是列表和哈希的底层实现之一。当一个列表只包含少量的列表项时,并且每个列表项要么是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表的底层实现。
压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一字节数组或者一个整数值。
压缩列表节点的构成:
[previous_entry_length,encoding,content] // 连续的内存块,不是数组
previous_entry_length:以字节为单位,记录了压缩列表中前一个节点的长度。(细节就不关注了)
encoding:记录了content属性所保存的类型以及长度。(细节就不关注了)
content:保存节点的值,可以是一个字节数组或者整数。
连锁更新
当 ziplist 中的元素(entry)长度接近或超过 254 字节时,记录前一个元素长度的 previous_entry_length 属性需要使用 5 个字节来存储。如果一个元素的长度小于 254 字节,这个属性只需要 1 个字节。因此,当新增或删除操作导致元素长度变化,从而需要更多空间来存储 previous_entry_length 时,就可能触发连锁更新。这种更新可能需要对后续所有元素的 previous_entry_length 属性进行空间调整,导致性能下降,尤其是在元素较多的情况下。
连锁更新最坏的情况下需要对空间进行N次重分配操作,每次空间重分配的最坏复杂度为O(N),所以连锁更新最坏复杂度是O(N²)。
实际上,对ziplist操作的API的平均复杂度为O(N),所以不必担心连锁更新带来的性能问题。
2024.10.21
writeBy kaiven