我命由我,不由天!


  • 搜索
prometheus docker golang linux kubernetes

redis-压缩列表(二十五)

发表于 2021-06-07 | 0 | 阅读次数 469

压缩列表

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

  • 本文作者: Dante
  • 本文链接: https://gaodongfei.com/archives/redis-压缩列表
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
redis-hash结构(二十四)
redis-quicklist
  • 文章目录
  • 站点概览
Dante

Dante

119 日志
5 分类
5 标签
RSS
Creative Commons
0%
© 2023 Dante
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
沪ICP备2020033702号