0. 题外话
接着昨天的[决战西二旗] |Redis 面试热点之底层实现篇 https://mp.weixin.qq.com/s/3IptChwLLMN6aTeQhapSNw 继续来了解一下 ziplist 压缩列表这个数据结构.
你可能会抱有疑问: 我只是使用 Redis 的功能并且公司的运维同事都已经搭建好了平台, 只需要在线申请一下配置和获取连接的地址就可以愉快地使用了, 为啥还要这么深入的理解底层的数据结构呢? 有啥用呢?
其实这个问题可以分几个方面去回答吧, 笔者试着去解释一下原因:
好奇心 作为技术人员, 没有好奇心会让我们错过很多精彩, 难道你对如此强悍的 NoSQL 是如何跑起来的不感兴趣吗? 好奇心让我们知道的更多, 也让我们不知道的更多;
辩证的职业素养 无论是 996 还是快速迭代, 让很多人陷入了网上找找, GitHub 找找, 改改, 跑起来万事大吉的循环, 但是这种确实是温水煮青蛙, 长此以往我们将渐渐失去判断力, 再者国内的文章或者技术点说明基本上都是抄来抄去, 没有好的鉴别能力往往就走很多弯路, 在这个过程中职业素养就显得意义重大, 算是比较核心的竞争力了;
善于思考的习惯 个人认为了解源码的一个好处是能对其中的原理有一定认识, 不至于完全黑盒子一样使用, 调包 Boy 或者 API 工程师往往在遇到一些问题是束手无策, 因为不知道是什么原因造成的. 更重要的一个好处在于对源码的学习本质上是相同问题的迁移, 换句话说, 我们有时候抱怨自己接触不到高难度的项目, 无法快速提高自己的能力, 但是个人觉得如果能力不够给你高难度项目只能让你失眠, 因为当没有可借鉴可参考的过往项目时会让你束手无策, 因为从 0-1 做一个好项目的能力不是一天养成的. 深入研究开源工程的实现细节能让我们置身相同的境况来思考问题, 假如自己被指定去完成该任务, 那么要如何实现呢?
胸有成竹的能力 我们有个成语叫庖丁解牛, 就是说我们掌握了事物的客观规律, 就能运用自如. 经验丰富的人在拿到一个任务之后, 脑海里便可以浮现出这个任务需要被拆解成几部分, 设计的重难点是什么, 其中可能出现的坑是什么, 需要使用哪些方法来解决特殊的问题, 个人感觉阅读源码可以让你慢慢获得这种能力, 试想你和大师面对一样的问题, 你先深入思考如何去做, 然后再仔细研究大师的方案, 久而久之自己的功力也必然会提升, 我觉得这也是研究开源工程源码最重要的原因.
说了这么多, 无非是想表达, 带着思考去学习, 受益的必然是你自己, 大的方针政策是正确的, 剩下的就是一步步去执行了, 源码工程千千万, 那也不必着急, 核心的思想并没有那么多, 怕什么真理无穷, 进一寸有一寸的欢喜!
Q6:Redis 的 ziplist 是如何实现的? 压缩列表的连锁更新的原因了解吗?
前面的文章介绍了 zset 和 hash 在数据量少且长度满足一定条件的基础上就会选择使用 ziplist 来进行存储.
当然后面 antirez 又推出了 quicklist 的结构, 后续可以聊聊 quicklist, 不过快速链表也是基于压缩列表实现的, ziplist 是一种使用特殊编码的内存连续型的数据结构, 让我们来一起揭开 ziplist 的神秘面纱吧.
1. 如何设计 ziplist
先不看 Redis 的对 ziplist 的具体实现, 我们先来想一下如果我们来设计这个数据结构需要做哪些方面的考虑呢? 思考式地学习收获更大呦!
考虑点 1: 连续内存的双面性
连续型内存减少了内存碎片, 但是连续大内存又不容易满足.
这个非常好理解, 你和好基友三人去做地铁, 你们三个挨着坐肯定不浪费空间, 但是地铁里很多人都是单独出行的, 大家都不愿意紧挨着, 就这样有 2 个的位置有 1 个的位置, 可是 3 个连续的确实不好找呀, 来张图:
考虑点 2: 压缩列表承载元素的多样性
待设计结构和数组不一样, 数组是已经强制约定了类型, 所以我们可以根据元素类型和个数来确定索引的偏移量, 但是压缩列表对元素的类型没有约束, 也就是说不知道是什么数据类型和长度, 这个有点像 TCP 粘包拆包的做法了, 需要我们指定结尾符或者指定单个存储的元素的长度, 要不然数据都粘在一起了.
考虑点 3: 属性的常数级耗时获取
就是说我们解决了前面两点考虑, 但是作为一个整体, 压缩列表需要常数级消耗提供一些总体信息, 比如总长度, 已存储元素数量, 尾节点位置 (实现尾部的快速插入和删除) 等, 这样对于操作压缩列表意义很大.
考虑点 4: 数据结构对增删的支持
理论上我们设计的数据结构要很好地支持增删操作, 当然凡事必有权衡, 没有什么数据结构是完美的, 我们边设计边调整吧.
考虑点 5: 如何节约内存
我们要节约内存就需要特殊情况特殊处理, 所谓变长设计, 也就是不像双向链表一样固定使用两个 pre 和 next 指针来实现, 这样空间消耗更大, 因此可能需要使用变长编码.
2.ziplist 总体结构
大概想了这么多, 我们来看看 Redis 是如何考虑的, 笔者又画了一张总览简图:
从图中我们基本上可以看到几个主要部分: zlbytes,zltail,zllen,zlentry,zlend.
来解释一下各个属性的含义, 借鉴网上一张非常好的图, 其中红线验证了我们的考虑点 2, 绿线验证了我们的考虑点 3:
来看下 ziplist.c 中对 ziplist 的申请和扩容操作, 加深对上面几个属性的理解:
- /* Create a new empty ziplist. */
- unsigned char *ziplistNew(void) {
- unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
- unsigned char *zl = zmalloc(bytes);
- ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
- ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
- ZIPLIST_LENGTH(zl) = 0;
- zl[bytes-1] = ZIP_END;
- return zl;
- }
- /* Resize the ziplist. */
- unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
- zl = zrealloc(zl,len);
- ZIPLIST_BYTES(zl) = intrev32ifbe(len);
- zl[len-1] = ZIP_END;
- return zl;
- }
3.zlentry 的实现
encoding 编码和 content 存储
我们再来看看 zlentry 的实现, encoding 的具体内容取决于 content 的类型和长度, 其中当 content 是字符串时 encoding 的首字节的高 2bit 表示字符串类型, 当 content 是整数时, encoding 的首字节高 2bit 固定为 11, 从 Redis 源码的注释中可以看的比较清楚, 笔者再做一层汉语版的注释 ^_^:
/*
########### 字符串存储详解 ###############
#### encoding 部分分为三种类型: 1 字节, 2 字节, 5 字节 ####
#### 最高 2bit 表示是哪种长度的字符串 分别是 00 01 10 各自对应 1 字节 2 字节 5 字节 ####
#### 当最高 2bit=00 时 表示 encoding=1 字节 剩余 6bit 2^6=64 可表示范围 0~63####
#### 当最高 2bit=01 时 表示 encoding=2 字节 剩余 14bit 2^14=16384 可表示范围 0~16383####
#### 当最高 2bit=11 时 表示 encoding=5 字节 比较特殊 用后 4 字节 剩余 32bit 2^32=42 亿多 ####
* |00pppppp| - 1 byte
* String value with length Less than or equal to 63 bytes (6 bits).
* "pppppp" represents the unsigned 6 bit length.
* |01pppppp|qqqqqqqq| - 2 bytes
* String value with length Less than or equal to 16383 bytes (14 bits).
* IMPORTANT: The 14 bit number is stored in big endian.
* |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
* String value with length greater than or equal to 16384 bytes.
* Only the 4 bytes following the first byte represents the length
* up to 32^2-1. The 6 lower bits of the first byte are not used and
* are set to zero.
* IMPORTANT: The 32 bit number is stored in big endian.
*######################## 字符串存储和整数存储的分界线 ####################*
*#### 高 2bit 固定为 11 其后 2bit 分别为 00 01 10 11 表示存储的整数类型
* |11000000| - 3 bytes
* Integer encoded as int16_t (2 bytes).
* |11010000| - 5 bytes
* Integer encoded as int32_t (4 bytes).
* |11100000| - 9 bytes
* Integer encoded as int64_t (8 bytes).
* |11110000| - 4 bytes
* Integer encoded as 24 bit signed (3 bytes).
* |11111110| - 2 bytes
* Integer encoded as 8 bit signed (1 byte).
* |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer.
* Unsigned integer from 0 to 12. The encoded value is actually from
* 1 to 13 because 0000 and 1111 can not be used, so 1 should be
* subtracted from the encoded 4 bit value to obtain the right value.
* |11111111| - End of ziplist special entry.
*/
content 保存节点内容, 其内容可以是字节数组和各种类型的整数, 它的类型和长度决定了 encoding 的编码, 对照上面的注释来看两个例子吧:
保存字节数组: 编码的最高两位 00 表示节点保存的是一个字节数组, 编码的后六位 001011 记录了字节数组的长度 11,content 属性保存着节点的值 "hello world".
保存整数: 编码为 11000000 表示节点保存的是一个 int16_t 类型的整数值, content 属性保存着节点的值 10086.
prevlen 属性
最后来说一下 prevlen 这个属性, 该属性也比较关键, 前面一直在说压缩列表是为了节约内存设计的, 然而 prevlen 属性就恰好起到了这个作用, 回想一下链表要想获取前面的节点需要使用指针实现, 压缩列表由于元素的多样性也无法像数组一样来实现, 所以使用 prevlen 属性记录前一个节点的大小来进行指向.
prevlen 属性以字节为单位, 记录了压缩列表中前一个节点的长度, 其长度可以是 1 字节或者 5 字节:
如果前一节点的长度小于 254 字节, 那么 prevlen 属性的长度为 1 字节, 前一节点的长度就保存在这一个字节里面.
如果前一节点的长度大于等于 254 字节, 那么 prevlen 属性的长度为 5 字节, 第一字节会被设置为 0xFE, 之后的四个字节则用于保存前一节点的长度.
思考: 注意一下这里的第一字节设置的是 0xFE 而不是 0xFF, 想下这是为什么呢?
没错! 前面提到了 zlend 是个特殊值设置为 0xFF 表示压缩列表的结束, 因此这里不可以设置为 0xFF, 关于这个问题在 Redis 有个 issue, 有人提出来 antirez 的 ziplist 中的注释写的不对, 最终 antirez 发现注释写错了, 然后愉快地修改了, 哈哈!
再思考一个问题, 为什么 prevlen 的长度要么是 1 字节要么是 5 字节呢? 为啥没有 2 字节, 3 字节, 4 字节这些中间态的长度呢? 要解答这个问题就引出了今天的一个关键问题: 连锁更新问题.
4. 连锁更新问题
试想这样一种增加节点的场景:
如果在压缩列表的头部增加一个新节点, 并且长度大于 254 字节, 所以其后面节点的 prevlen 必须是 5 字节, 然而在增加新节点之前其 prevlen 是 1 字节, 必须进行扩展, 极端情况下如果一直都需要扩展那么将产生连锁反应:
试想另外一种删除节点的场景:
如果需要删除的节点时小节点, 该节点前面的节点是大节点, 这样当把小节点删除时, 其后面的节点就要保持其前面大节点的长度, 面临着扩展的问题:
理解了连锁更新问题, 再来看看为什么要么 1 字节要么 5 字节的问题吧, 如果是 2-4 字节那么可能产生连锁反应的概率就更大了, 相反直接给到最大 5 字节会大大降低连锁更新的概率, 所以笔者也认为这种内存的小小浪费也是值得的.
5. 辩证看待 ziplist
从 ziplist 的设计来看, 压缩列表并不擅长修改操作, 这样会导致内存拷贝问题, 并且当压缩列表存储的数据量超过某个阈值之后查找指定元素带来的遍历损耗也会增加.
6. 巨人的肩膀
Redis - 压缩列表 - 掘金 https://juejin.im/post/5d1dd120e51d45778f076d9d
来源: https://www.cnblogs.com/backnullptr/p/12033923.html