侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

Redis 常见数据结构的底层实现系列(三):列表篇

kaixindeken
2021-04-28 / 0 评论 / 0 点赞 / 70 阅读 / 3,312 字

Redis 列表的底层实现经历了从双向链表到压缩列表,再到快速列表的多次优化演进,在 Redis 3.2 之前,当元素不多时,Redis 是通过压缩列表来实现列表结构的,而当元素很多时,则会切换为通过双向链表来实现列表结构。

双向链表

正常情况下,要实现一个基本的、符合列表要求的数据结构,使用标准的双向链表就可以了:

// 双向链表的节点
struct listNode<T> {
    listNode* prev;
    listNode* next;
    T value;
}

// 双向链表的结构
struct linkedList {
    listNode *head;
    listNode *tail;
    long length;
}

对于双向链表而言,除了元素值本身,每个节点都要包含 prev 和 next 两个指针,它们要占据额外的 16 个字节内存空间(64 位系统的指针是 8 个字节),另外,每个节点的内存都是单独分配,会加剧内存的碎片化,在回收被删除的元素时,又以页为单位,同一个键对应的列表元素会离散分布到多个页中,这些都会影响内存管理效率。

如果列表元素很少,这些额外分配的空间和离散操作成本可能都会超过元素本身的管理成本,在追求极致性能的 Redis 中,这是不能忍受的,所以当元素很少时,Redis 会通过一个叫做压缩列表的数据结构来管理列表元素的存取操作。

压缩列表

Redis 的压缩列表 ziplist 是一个紧凑的字节数组结构,每个元素之间都是紧挨着的,没有任何冗余空隙。这就降低了内存管理成本和额外分配的指针空间,那压缩列表又是如何实现列表功能的呢?

与数组结构不同的是,压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示压缩列表总字节数、表尾的偏移量和列表中的元素个数,具体的元素通过 entry 表示,在压缩列表表尾还有一个 zlend,表示列表结束。图示如下:

1.jpeg

对应的数据结构如下:

// 压缩列表的结构
struct ziplist<T> {
    int32 zlbytes; 
    int32 zltail_offset;
    int16 zllength;
    T[] entries;
    int8 zlend;
}
// 压缩列表中的节点元素
struct entry {
    int<var> prevlen; // 前一个 entry 的字节长度
    int<var> encoding; // 元素编码类型
    optional byte[] content; // 具体元素内容
}

这里之所有定义一个 ztail 偏移量用来快速定位到列表尾部,是因为 Redis 的列表结构是一个双向列表,支持从左到右读取元素,也支持从右到左读取元素,这两个操作的时间复杂度都是 O(1),但是不支持随机读取元素,因为其时间复杂度依然是 O(n)。

另外,Redis 列表支持范围查询,这个时候,从左往右读取时,基于元素编码类型和元素字节数组可以确定后一个相邻元素的偏移位置,而如果从右往左读取时,可以基于 prevlen 值确定前一个相邻元素的偏移位置,显然,范围查询时间复杂度最差是 O(N),对于存放元素很多的列表,不推荐进行范围查询。

由于压缩列表是紧凑存储,没有冗余空间,意味着每次添加元素都要分配新的内存空间,然后将老的元素拷贝到新地址,当列表元素不断增加,或者单个元素值过大,这种新分配内存的成本会越来越高,当达到一定阈值,Redis 会升级为通过标准的双向链表来实现列表结构,这个阈值可以在 Redis 配置文件中配置:

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

上面两个配置值的含义分别是当列表元素个数超过 512 或者单个元素值的长度超过 64 时(默认值),则会切换为使用标准的双向链表来实现 Redis 列表。

快速列表

压缩列表在处理小规模列表时,性能显然是要优于双向链表的,但是随着元素增多或者元素值很大,还是要切换成双向链表,再度面临内存分配和管理的低效问题,为此,从 Redis 3.2 开始,Redis 引入了一种新的数据结构 —— 快速列表(quicklist),并且从 Redis 4.0 起,只支持通过这一种数据结构实现 Redis 列表:

127.0.0.1:6379> rpush queue xueyuanjun.com
(integer) 1
127.0.0.1:6379> debug object queue
Value at:0x7f86796c4d20 refcount:1 encoding:quicklist serializedlength:29 lru:341827 lru_seconds_idle:15 ql_nodes:1 ql_avg_node:1.00 ql_ziplist_max:-2 ql_compressed:0 ql_uncompressed_size:27

快速列表并不是什么全新的数据结构,而是建立在压缩列表和双向链表之上的,它将双向链表按段切分成多个快速列表节点,每一个快速列表节点中的列表元素使用压缩列表紧凑存储,最后快速列表内部的多个压缩列表之间再使用双向指针串联起来:

1.jpeg

这样一来,就可以充分利用压缩列表的高性能,又能避免双向链表存在的问题。对应的 C 语言底层数据结构实现代码如下:

// 快速列表的节点
struct quicklistNode {
    quicklistNode* prev;
    quicklistNode* next;
    ziplist* zl; // 指向压缩列表
    int32 size; // 压缩列表的字节总数
    int16 count; // 压缩列表中的元素数量
    int2 encoding; // 存储编码类型,原生字节数组还是 LZF 压缩存储
    ...
}
// 快速列表的结构
struct quicklist {
    quicklistNode* head;
    quicklistNode* tail;
    long count; // 快速列表节点总数
    int nodes; // 压缩列表节点个数
    int compressDepth; // LZF 算法压缩深度
    ...
}

这里面有一个 LZF 压缩的概念,为了进一步节约内存空间,Redis 还会对压缩列表进行压缩存储,这里使用的 LZF 算法压缩,可以选择压缩深度,默认是 0,表示不压缩,则对应的 encoding 值是 raw,否则 encoding 值是 compressed。

压缩深度可以通过 Redis 配置文件中的如下配置项进行配置:

list-compress-depth 0

另外,每个快速列表节点内部单个压缩列表长度上限为 8KB,超出了这个字节数,就会新建一个压缩列表,你可以通过 Redis 配置文件的如下配置项来配置这个默认值:

list-max-ziplist-size -2

以上两个配置项的配置示例在 Redis 配置文件注释中都已经给出了,这里就不具体演示了。

0

评论区