【Redis源码系列】Redis6.0数据结构详解--ziplist篇
2024-09-23 11:58:39
上篇文章我们研究了Redis SDS数据结构的实现原理, 并深入分析了其针对性的优化手段。本篇我们研究一下另一个数据结构ziplist。
前期回顾: 【Redis源码系列】Redis6.0数据结构详解--SDS篇
数据结构整体布局ziplist没有结构体定义, 官方文档描述其为: 一种特殊结构的双向链表。其特殊之处在, 没有使用双向指针(prev, next)去连接前后的元素, 而是通过计算元素中特定编码的字长偏移量来访问不同的元素, 借助源码src/ziplist.c 中的注释描述:
我们可以了解到典型的压缩列表布局为:
由如下部分组成:
zlbytes: uint32_t类型, 表示整个ziplist所占用内存的字节数, 在执行内存分配时会被使用。
zltail: uint32_t类型, 即上图到达zlend节点的偏移量, 通过此偏移量可以快速定位到zlend节点。
zllen: uint16_t类型, ziplist 中节点的数量。 当这个值小于?UINT16_MAX?（65535）时，这个值就是 ziplist 中节点的数量； 当这个值等于?UINT16_MAX?时，节点的数量需要遍历整个 ziplist 才能计算得出。
entry: ziplist 所保存的节点，各个节点的长度根据内容而定。
zlend: uint8_t类型, 255?的二进制值?1111?1111?（UINT8_MAX） ，用于标记 ziplist 的末端。
entry组成entry的逻辑定义如下:
其并非实际存储结构, 只是辅助结构, 可以通过一些宏定义更方便的展开, 简化为更容易理解的内存布局如下：
pre_entry_lengthpre_entry_length记录了前一个节点的长度, 可占用 1 或者 5个字节, 语句 #define ZIP_BIG_PREVLEN 254 定义当前一个节点的字长小于254时, 使用一个字节保存其值, 超过254, 则第一个字节被设置为254, 剩下字节保存其实际长度。可以通过次记录作指针偏移量计算跳转到上一个节点，如上图, 当前指针位置为 curptr，则 preptr = curptr-pre_entry_length，这样可以快速定位到上一个节点。参见源码如下:
lenlen字长有 encoding & len 两部分组成, 长度可能为 1,2,5个字节。其中encoding占用两个字节, 其值有如下两种情况:
00,01,10: 表示存储的是字符数组
11: 表示存储的是整数 其值在不同情况子长下的存储示例为:
字节长编码content值1 byte00bbbbbb长度小于等于 63 字节的字符数组2 byte01bbbbbb xxxxxxxx长度小于等于 16383 字节的字符数组5 byte10____ aaaaaaaa bbbbbbbb cccccccc dddddddd长度小于等于 16383 字节的字符数组1 byte11000000int16_t?类型的整数1 byte11010000int32_t?类型的整数1 byte11100000int64_t?类型的整数1 byte1111000024 bit 有符号整数1 byte111111108 bit 有符号整数1 byte1111xxxx4 bit 无符号整数，介于?0?至?12?之间content通过以上的结构分析我们已经能够了解entry布局的基本组成, 关于content的内容我们从一个实例入手来进行了解, 老规矩, 有请万能的 hello world 登场:
一个存储hello world的ziplist节点如图所示, 其中encoding占用两位, 00 标识内容类型为字符数组, length 占用6位, 为二进制的11, 表示 content 字节长度, encoding & length整体占用一个字节。
数据操作创建ziplist创建的方法比较简单, 可以看到ziplist本质上是一个字节数组, 初始化内存为: ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE=11个字节, 宏定义如下:
ZIPLIST_HEADER_SIZE: (sizeof(uint32_t)*2+sizeof(uint16_t)) 共10个字节。
ZIPLIST_END_SIZE: (sizeof(uint8_t)) 一个字节, 表示尾部节点。 创建完成后结构如下:
插入元素__ziplistInsert 方法上游有ziplistInsert和ziplistPush方法调用核心都是执行__ziplistInsert方法，源码分析如下:
查找元素基于我们如上的分析, 可以比较清除的理解ziplist的查找操作, 源码解析如下:
连锁更新前面我们分析过entry的previous_entry_length属性保存了前一个节点的长度, 为 1 或 5 个字节长度，当前一个节点长度在 254 以下时，使用一个字节保存其长度, 长度在 254 以上时, 使用5个字节保存其长度, 事项如下实例: 在ziplist中连续保存着长度为 250 - 253 长度的节点 e1,e2...eN, 此时每个节点的previous_entry_length属性长度都为 1, 当我们在头结点插入一个长度超过254的entry后, 第二个节点e1需要修改自己的属性previous_entry_length, 增加4个字节, 依此类推, 直到后面的每一个节点执行类似的操作, 我们将这种情况命名为: 连锁更新, 在源码src/ziplist.c的__ziplistCascadeUpdate方法实现了这样的操作逻辑。源码解析如下:
基于源码有如下思考, 在连锁更新的最坏的情况下需要执行N次空间重新分配操作, 而每次空间分配最坏复杂度为O(N), 所以连锁更新最坏的复杂度为O(N^2)，看起来是一个非常危险的存在, 尽管如此, 实际使用起来要达到最坏情况条件相对比较苛刻, 要满足所有节点长度介于250-253之间。同时在实际情况中, 更新的节点仍在小范围内, 不会对性能造成明显可见的影响。
此类操作可类比到PHP7的zend_hash源码实现, PHP7使用链表来处理hash冲突, 同时使用开源的time33算法做hash值计算, 当我们使用恶意数据构造zend_hash的数据结构, 就是得原本连续存储的bucket数组转化为基于bucket的链表, 我们很容易实现这样的入侵:
<?phpecho?"开始添加元素"?.?PHP_EOL;$a?=?["cooper"?=>?"cooper_key"];$size?=?pow(2,?16);$startTime?=?microtime(true);$array?=?array();for?($key?=?0,?$maxKey?=?($size?-?1)?*?$size;?$key?<=?$maxKey;?$key?+=?$size)?{????$array[$key]?=?0;}$endTime?=?microtime(true);echo?'插入?',?$size,?'?个恶意的元素需要?',?$endTime?-?$startTime,?'?秒',?"\n";$startTime?=?microtime(true);$array?=?array();for?($key?=?0,?$maxKey?=?$size?-?1;?$key?<=?$maxKey;?++$key)?{????$array[$key]?=?0;}$endTime?=?microtime(true);echo?'插入?',?$size,?'?个普通元素需要?',?$endTime?-?$startTime,?'?秒',?"\n";执行结果如下:
开始添加元素插入?65536?个恶意的元素需要?8.8367640972137?秒插入?65536?个普通元素需要?0.0045688152313232?秒尽管如此, 我们仍然大规模的使用PHP做web服务的实现, 不过我们需要注意防范此类的攻击。
总结本篇我们分析了Redis ziplist的源码实现, 可以看到ziplist本质内存结构是一个字节数组, 作者通过相对复杂的指针偏移规则做结构的逻辑模拟, 这样带来的好处是极大的提高的了内存的使用率, 整体实现几乎是不浪费任何一个可存储的字节, 也体现了作者对于设计一个内存型数据库的极致追求。 关于ziplist个人认为需要重点理解其编码的实现规则, 以及这些规则背后存在的意义。同时对于基于此规则引起的可能存在的复杂度较高的操作我们也做了详细的解析, 并且举一反三类比PHP源码的实现做了分解。复杂事物背后很难有100%完美的解法, 使用空间换取时间也是很多优秀作品的共同选择, 同时能够将复杂逻辑做严谨的设计与实现, 也使得我们可以站在巨人的肩膀上更好的充实自己。
原文：https://juejin.cn/post/7097856013776191518
热门标签
