【Redis】压缩列表

Bertha 。 2022-03-09 13:48 188阅读 0赞

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3czNzI0MjYwOTY_size_16_color_FFFFFF_t_70][]

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

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

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

它的 `prevlen` 字段表示前一个 entry 的字节长度，当压缩列表倒着遍历时，需要通过这个字段来快速定位到下一个元素的位置。它是一个变长的整数，当字符串长度小于 254(0xFE) 时，使用一个字节表示；如果达到或超出 254(0xFE) 那就使用 5 个字节来表示。第一个字节是 0xFE(254)，剩余四个字节表示字符串长度。你可能会觉得用 5 个字节来表示字符串长度，是不是太浪费了。我们可以算一下，当字符串长度比较长的时候，其实 5 个字节也只占用了不到`(5/(254+5))<2%`的空间。

![1][]

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

## 增加元素 ##

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

如果 ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist 不适合存储大型字符串，存储的元素也不宜过多。

## IntSet 小整数集合 ##

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

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

![1 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3czNzI0MjYwOTY_size_16_color_FFFFFF_t_70]: /images/20220309/dee963c9c05342778c0c39d39f1c9458.png
[1]: https://user-gold-cdn.xitu.io/2018/7/30/164ea7e76014e30c?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[1 1]: https://user-gold-cdn.xitu.io/2018/7/29/164e1a049ea6ea41?imageView2/0/w/1280/h/960/format/webp/ignore-error/1