压缩列表是由一系列特殊编码的连续内存块组成的顺序整数结构,一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数。适合存储小对象和长度有限的数据。
压缩列表是列表键和哈希键的底层实现之一,当列表键只包含少量列表项,并且每个列表项要么是小整数值,要么是长度比较短的字符串,那么 Redis 就会使用压缩列表来做列表键的底层实现。
举个例子,当哈希表只包含少量键值对,并且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么 Redis 就会使用压缩列表来做哈希键 的底层实现。
数据结构
下面是 ziplistEntry 的定义:
/* Each entry in the ziplist is either a string or an integer. */ typedef struct { /* When string is used, it is provided with the length (slen). */ unsigned char *sval; unsigned int slen; /* When integer is used, 'sval' is NULL, and lval holds the value. */ long long lval; } ziplistEntry;
下面是压缩列表的每个部分组成(逻辑结构)
- zlbytes 记录了整个压缩列表的字节数,在压缩列表进行内存重新分配或者计算 zlend 的时候使用
- ztail 记录了压缩列表表尾节点距离压缩列表的起始地址有多少个字节,通过该偏移量无需遍历真个压缩列表就可以确定表尾节点,在返乡遍历时使用
- zllen 记录压缩列表包含的节点数量,当该值小于 65535 时,记录的列表节点数量;否则该值恒等于 65535时, 要获取节点数量需要进行遍历。
- zlend 特殊值 0xFF (十进制 255),用来标记压缩列表的末端。
举个例子(如下图):
每个部分说明:
1)列表 zlbytes 属性的值为 0x50 (十进制 80),表示压缩列表的总长度为 80 个字节
2)列表 zltail 属性的值为 0x3c (十进制 60),这个表示如果我们有一个指向压缩列表
的启始指针 p, 那么我们就用指针加上偏移量 60, 就可以计算出尾节点的 entry3. 的地址。
3)列表 zllen 属性值为 0x3(十进制 3 )表示有 3个节点。
节点构成
/* We use this function to receive information about a ziplist entry. * Note that this is not how the data is actually encoded, is just what we * get filled by a function in order to operate more easily. */ typedef struct zlentry { unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/ unsigned int prevrawlen; /* Previous entry len. */ unsigned int lensize; /* Bytes used to encode this entry type/len. For example strings have a 1, 2 or 5 bytes header. Integers always use a single byte.*/ unsigned int len; /* Bytes used to represent the actual entry. For strings this is just the string length while for integers it is 1, 2, 3, 4, 8 or 0 (for 4 bit immediate) depending on the number range. */ unsigned int headersize; /* prevrawlensize + lensize. */ unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on the entry encoding. However for 4 bits immediate integers this can assume a range of values and must be range-checked. */ unsigned char *p; /* Pointer to the very start of the entry, that is, this points to prev-entry-len field. */ } zlentry;
对应关系如下:
转换函数如下:
static inline void zipEntry(unsigned char *p, zlentry *e) { ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen); ZIP_ENTRY_ENCODING(p + e->prevrawlensize, e->encoding); ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len); assert(e->lensize != 0); /* check that encoding was valid. */ e->headersize = e->prevrawlensize + e->lensize; e->p = p; }
prevlen: 记录的是当前节点的长度,以字节为单位。当一个节点长度小于 254时, prevlen 是需要一个字节即可;否则 prevlen 需要使用 5 个字节来进行存储,其中第一个字节固定位 0xfe (254), 而后面 4个字节蒂娜存储前一个节点的长度。作用是:更具该属性可以快速定位前一个节点的起始位置,支持 ziplist 反向遍历。
1、 数据为字符串
编码 | 字符串长度 | content 属性保存值 |
00bbbbbb | 1 字节 | 长度小于 63 字节数组 |
01bbbbbb xxxxxxxx | 2 字节 | 长度小于等于 16 383 字节数组 |
10_ _ _ _ _ _ aaaaaaaa bbbbbbbb cccccccc dddddddd | 5 字节 | 长度小于等于 4 294 967 295字节数组 |
2、数据为整数时
编码 | 字符串长度 | content 属性保存值 |
11000000 | 1 字节 | Int16_t 类型的整数 |
11010000 | 1 字节 | Int32_t 类型的整数 |
11100000 | 1 字节 | Int64_t 类型的整数 |
11110000 | 1 字节 | 24 位有符号整数 |
11111110 | 1 字节 | 8 位有符号整数 |
1111xxxx | 1 字节 | 使用这个编码的节点没有对应的 content 属性,因为编码本身 xxxx 四个位已经保存了一个介于 0 和 12 之间的值, 1 = 11110001> 13 = 11111111> 避免和 8 位冲突所以是 [0, 12] 所以它无需 content 属性 |
代码如下:
连锁更新
在 entry 中 prevlen 会保留前一个字节的长度:
- 如果前一个字典长度小于 256 字节,那么 prevlen 属性需要一个字
- 如果前一个字节的长度大于等于 256 字节,那么 prevlen 属性就需要用 5 个字节来保存这个长度
因此当插入或者删除操作,会打破 ziplist 具有特性,此时需要进行节点的更新。Redis 中只处理集诶单的扩张即 1 个字节变成 5 个重点,不进行收缩操作(为了防止反复出现缩小 -扩大)
最差的情况下:连续更新对 ziplist 执行 N 次空间分配操作,而每次重新分配最坏的复杂度为 O(N), 所以连锁更新最坏的情况是 O(N ^2)。
注意点
1、查找时间复杂度为 O(N)
2、列表的长度超过了 UINT16_MAX, 此时 zllen 不再表示节点的个数
3、连锁更新相关内容