压缩列表

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

构成

压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                         ZIPLIST_ENTRY_TAIL
zlbytesuint32_t整个 ziplist 占用的内存字节数,对 ziplist 进行内存重分配,或者计算末端时使用。
zltailuint32_t到达 ziplist 表尾节点的偏移量。 通过这个偏移量,可以在不遍历整个 ziplist 的前提下,弹出表尾节点。
zllenuint16_tziplist 中节点的数量。 当这个值小于 UINT16_MAX (65535)时,这个值就是 ziplist 中节点的数量; 当这个值等于 UINT16_MAX 时,节点的数量需要遍历整个 ziplist 才能计算得出。
entryX? ziplist所保存的节点,各个节点的长度根据内容而定。
zlenduint8_t255 的二进制值 1111 1111 (UINT8_MAX) ,用于标记 ziplist 的末端。

节点构成

area        |<------------------- entry -------------------->|

            +------------------+----------+--------+---------+
component   | pre_entry_length | encoding | length | content |
            +------------------+----------+--------+---------+

pre_entry_length

pre_entry_length 记录了前一个节点的长度,通过这个值,可以进行指针计算,从而跳转到上一个节点。

根据编码方式的不同, pre_entry_length 域可能占用 1 字节或者 5 字节:

  • 1 字节:如果前一节点的长度小于 254 字节,便使用一个字节保存它的值。
  • 5 字节:如果前一节点的长度大于等于 254 字节,那么将第 1 个字节的值设为 254 ,然后用接下来的 4 个字节保存实际长度。

encoding 和 length

ncoding 和 length 两部分一起决定了 content 部分所保存的数据的类型(以及长度)。

其中, encoding 域的长度为两个 bit , 它的值可以是 00 、 01 、 10 和 11 :

00 、 01 和 10 表示 content 部分保存着字符数组。 11 表示 content 部分保存着整数。

字符数组的编码:

编码编码长度content 部分保存的值
00bbbbbb1 byte长度小于等于 63 字节的字符数组。
01bbbbbb xxxxxxxx2 byte长度小于等于 16383 字节的字符数组。
10__ aaaaaaaa bbbbbbbb cccccccc dddddddd5 byte长度小于等于 4294967295 的字符数组。

整数编码:

编码编码长度content 部分保存的值
110000001 byteint16_t 类型的整数
110100001 byteint32_t 类型的整数
111000001 byteint64_t 类型的整数
111100001 byte24 bit 有符号整数
111111101 byte8 bit 有符号整数
1111xxxx1 byte4 bit 无符号整数,介于 0 至 12 之间

content

content 部分保存着节点的内容,类型和长度由 encoding 和 length 决定。

字符数组 hello world 的节点的例子

area      |<---------------------- entry ----------------------->|

size        ?                  2 bit      6 bit    11 byte
          +------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content       |
          |                  |          |        |               |
value     | ?                |    00    | 001011 | hello world   |
          +------------------+----------+--------+---------------+

整数 10086 :

area      |<---------------------- entry ----------------------->|

size        ?                  2 bit      6 bit    2 bytes
          +------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content       |
          |                  |          |        |               |
value     | ?                |    11    | 000000 | 10086         |
          +------------------+----------+--------+---------------+

连锁更新

每个节点的previous_entry_length属性都记录了前一个节点的长度:

  • 如果前一节点的长度小于254字节,那么previous_entry_length属性需要用1字节长的空间来保存这个长度值。
  • 如果前一节点的长度大于等于254字节,那么previous_entry_length属性需要用5字节长的空间来保存这个长度值。

删除/修改/添加都可能会导致连锁更新

因为连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作,而每次空间重分配的最坏复杂度为O(N),所以连锁更新的最坏复杂度为O(N2)

Updated: