压缩列表
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,这就表示内部采用压缩列表结构进行存储。
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%
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位
}