发表于 | 0 | 阅读次数 558

压缩列表

Redis为了节约内存空间使用，zset和hash容器对象在元素个数较少的时候，采用压缩列表进行存储。压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。

$ zadd programmings 1.0 go
$ debug object programmings
Value at:0x7fc0a3108050 refcount:1 encoding:ziplist serializedlength:18 lru:12441250 lru_seconds_idle:7

debug object 输出的encoding字段都是ziplist，这就表示内部采用压缩列表结构进行存储。

image.png

struct ziplist<T> {
    int32 zlbytes;     // 整个压缩列表占用字节数
    int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength;     // 元素个数
    T[] entries;        // 元素内容列表，依次紧凑存储
    int8 zlend;         // 标志压缩列表的结束，值恒为 0xFF
}

压缩列表为了支持双向遍历，所以才会有ztail_offset这个字段，用来快速定位到最后一个元素，然后倒着遍历。

entry块随着容纳的元素类型不同，也会有不一样的结构。

struct entry {
    int<var> prevlen;        // 前一个entry的字节长度
    int<var> encoding;       // 元素类型编码
    optional byte[] content; // 元素内容
}

prevlen字段表示前一个entry的字节长度，当压缩列表倒着遍历时，需要通过这个字段来快速定位到下一个元素的位置。它时一个变长的整数，当字符串长度小于254时，使用一个字节表示；如果达到或超出254时，就使用5个字节来表示。第一个字节是0xFE，剩余四个字节表示字符串长度。5个字节占用不到2%的空间

len_size = 5 # 存储字符串长度占用字节数
str_size >=254 # 存储字符串内容占用字节数
# 字符串长度存储占用的空间百分比
len_size_ratio = len_size/(len_size + str_size) <= 5/(5 + 254) = 1.93%

image.png

encoding 字段存储了元素内容的编码类型信息，ziplist通过这个字段来决定后面的content形式。

Redis为了节约存储空间，对encoding字段进行了相当复杂的设计。Redis通过这个字段的前缀来识别具体存储的数据形式。

注意content字段在结构体中定义为optional类型，表示这个字段是可选的，对于很小的整数而言，它的内容已经内联到encoding字段的尾部了。

增加元素

因为ziplist都是紧凑存储，没有冗余空间，意味着插入一个新的元素就需要调用realloc扩展内存。取决于内存分配器算法和当前的ziplist内存大小，realloc可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也有可能在原有的地址进行扩展，这时就不需要进行旧内容的内存拷贝。

级联更新

每个entry都会有一个prevlen字段存储前一个entry的长度。如果内容小于254字节，prevlen就用1字节存储，否则就用5字节存储。这意味着某个entry经过修改操作从253字节变成254字节，那么后面的entry就需要更新

删除entry也会产生级联。

intset小整数集合

当set集合容纳的元素都是整数并且元素个数较小时，Redis会使用intset来存储集合元素。intset时紧凑的数组结构，同时支持16位、32位和64位整数。

struct intset<T> {
	int32 encoding; // 决定整数位宽时16位，32位还是64位
	int32 length;   // 元素个数
	int<T> contents; // 整数数组，可以是16位，32位和64位
}

image.png