一, 前言
Redis 提供了 5 种数据类型: String(字符串),Hash(哈希),List(列表),Set(集合),Zset(有序集合), 理解每种数据类型的特点对于 Redis 的开发和运维非常重要.
原文解析
Redis 中的 list 是我们经常使用到的一种数据类型, 根据使用方式的不同, 可以应用到很多场景中.
二, 底层解析
1, 上节回顾
上节《闲扯 Redis 四》List 数据类型底层编码转换 说道, 在 3.0 版本的 Redis 中, List 类型有两种实现方式:
1, 使用压缩列表 (ziplist) 实现的列表对象.
2, 使用双端链表 (linkedlist) 实现的列表对象.
在 3.2 版本后新增了 quicklist 数据结构实现了 list, 现在就来分析下 quicklist 的结构
2, 官方描述
先来看看 Redis 官方对 quicklist 的描述:
- A doubly linked list of ziplists
- A generic doubly linked quicklist implementation
可见 quicklist 是一个双向链表, 并且是一个 ziplist 的双向链表, 也就是说 quicklist 的每个节点都是一个 ziplist. 而通过前面的文章咱们可以知道, ziplist 本身也是一个能维持数据项先后顺序的列表, 而且数据项保存在一个连续的内存块中. 那是不是意味着 quicklist 结合了压缩列表和双端链表的特点呢!
3, 结构分析
quicklist 结构定义
- /*
- * quicklist
- */
- typedef struct quicklist {
- // 头结点
- quicklistNode *head;
- // 尾节点
- quicklistNode *tail;
- // 所有 ziplist 中 entry 数量
- unsigned long count;
- //quicklistNodes 节点数量
- unsigned int len;
- //ziplist 中 entry 能保存的数量, 由 list-max-ziplist-size 配置项控制
- int fill : 16;
- // 压缩深度, 由 list-compress-depth 配置项控制
- unsigned int compress : 16;
- } quicklist;
quicklist 结构属性注释
注释:
fill :ziplist 中 entry 能保存的数量, 由 list-max-ziplist-size 配置项控制
表示了单个节点 (quicklistNode) 的负载比例(fill factor), 负数限制 quicklistNode 中的 ziplist 的字节长度,
正数限制 quicklistNode 中的 ziplist 的最大长度.
-5: 最大存储空间: 64 Kb <-- 通常情况下不要设置这个值
-4: 最大存储空间: 32 Kb <-- 非常不推荐
-3: 最大存储空间: 16 Kb <-- 不推荐
-2: 最大存储空间: 8 Kb <-- 推荐
-1: 最大存储空间: 4 Kb <-- 推荐
对于正整数则表示最多能存储到你设置的那个值, 当前的节点就装满了
通常在 -2 (8 Kb size) 或 -1 (4 Kb size) 时, 性能表现最好
compress : 压缩深度, 由 list-compress-depth 配置项控制
表示 quicklist 中的节点 quicklistNode, 除开最两端的 compress 个节点之后, 中间的节点都会被压缩(LZF 压缩算法).
quicklistNode 结构定义
- typedef struct quicklistNode {
- // 前节点指针
- struct quicklistNode *prev;
- // 后节点指针
- struct quicklistNode *next;
- // 数据指针. 当前节点的数据没有压缩, 那么它指向一个 ziplist 结构; 否则, 它指向一个 quicklistLZF 结构.
- unsigned char *zl;
- //zl 指向的 ziplist 实际占用内存大小. 需要注意的是: 如果 ziplist 被压缩了, 那么这个 sz 的值仍然是压缩前的 ziplist 大小
- unsigned int sz;
- //ziplist 里面包含的数据项个数
- unsigned int count : 16;
- //ziplist 是否压缩. 取值: 1--ziplist,2--quicklistLZF
- unsigned int encoding : 2;
- // 存储类型, 目前使用固定值 2 表示使用 ziplist 存储
- unsigned int container : 2;
- // 当我们使用类似 lindex 这样的命令查看了某一项本来压缩的数据时, 需要把数据暂时解压, 这时就设置 recompress=1 做一个标记, 等有机会再把数据重新压缩
- unsigned int recompress : 1;
- unsigned int attempted_compress : 1; /* node can't compress; too small */
- unsigned int extra : 10; /* more bits to steal for future usage */
- } quicklistNode;
quicklistLZF 结构定义
- typedef struct quicklistLZF {
- unsigned int sz; // 压缩后的 ziplist 大小
- char compressed[];// 柔性数组, 存放压缩后的 ziplist 字节数组
- } quicklistLZF;
4,quicklist 结构图
根据上述结构体定义, 咱们可以绘制一下 quicklist 的结构:
三, 要点总结
1, 双端链表
1. 双端链表便于在表的两端进行 push 和 pop 操作, 但是它的内存开销比较大;
2. 双端链表每个节点上除了要保存数据之外, 还要额外保存两个指针;
3. 双端链表的各个节点是单独的内存块, 地址不连续, 节点多了容易产生内存碎片;
2, 压缩列表
1.ziplist 由于是一整块连续内存, 所以存储效率很高;
2.ziplist 不利于修改操作, 每次数据变动都会引发一次内存的 realloc;
3. 当 ziplist 长度很长的时候, 一次 realloc 可能会导致大批量的数据拷贝, 进一步降低性能;
3,quicklist
1. 空间效率和时间效率的折中;
2. 结合了双端链表和压缩列表的优点;
来源: https://www.cnblogs.com/jstarseven/p/12765251.html