redis 压缩列表ziplist、quicklist

高手们,打扰一下,redis 压缩列表ziplist、quicklist
最新回答
一枕庭前雪

2024-09-22 05:58:11

压缩列表(ziplist)是Redis中一种用于节约内存的线性数据结构,适用于存储少量元素,特别是短字符串,作为有序集合、哈希和列表的底层存储方式。列表则使用快速链表(quicklist)结构,快速链表是双向链表和压缩列表的组合。使用命令创建哈希键并查看其编码可揭示其底层实现。

压缩列表以字节数组形式存储,逻辑划分为多个字段,每个字段对应不同的信息。包含三个节点的示例显示总空间为80字节,尾部偏移量为60字节,节点数量为3。每个节点可以是整数或字节数组,由三个属性组成:previous_entry_length、encoding和content。

previous_entry_length用于记录前一个节点的长度,根据前一个节点大小不同,其长度可以是1字节或5字节。小于254字节时使用1字节表示,大于等于254字节时使用5字节表示,首字节为254。这种设计允许通过当前地址减去上一个节点的长度来方便地获取上一个节点的位置,实现从表尾到表头的遍历。

encoding字段通过规则记录content的类型,一字节、两字节或五字节长,最高位为00、01或10表示字节数组编码,表示节点content属性保存字节数组,长度由编码除去最高两位后的其他位记录;一字节长、最高位以11开头表示整数编码,表示节点content保存整数值,类型和长度由编码除去最高两位后的其他位决定。

在添加或删除节点时,可能会因previous_entry_length的变化导致连锁更新操作,可能从插入位置一直更新到末尾,即执行了N次空间重分配,每次空间重分配的复杂度为O(N),因此连锁更新的最坏复杂度为O(N^2)。尽管存在这种情况,但通常不会对性能产生重大影响,除非更新的节点数量较多。快速列表(quicklist)结合了链表和压缩列表的优点,成为Redis 3.2版本后列表的底层实现。

String类型的编码类型可能包括embstr编码,以减少短字符串的内存分配次数。List类型的默认编码为OBJ_ENCODING_QUICKLIST,而Hash类型的编码类型则有OBJ_ENCODING_ZIPLIST和OBJ_ENCODING_HT两种,具体使用哪种编码取决于Redis配置选项。在特定情况下,如key或value长度超过64字节,可能会影响编码类型的选择。