做饮品的网站,修改网站空间服务器密码,营销型网站建设菲凡网,百度推广注册文章目录 1. 引言2. redis 源码下载3. zipList 数据结构3.1 整体3.2 entry 数据结构分析3.3 连锁更新 4. 参考 1. 引言
前情提要#xff1a; 《redis 从0到1完整学习 #xff08;一#xff09;#xff1a;安装初识 redis》 《redis 从0到1完整学习 #xff08;二 《redis 从0到1完整学习 一安装初识 redis》 《redis 从0到1完整学习 二redis 常用命令》 《redis 从0到1完整学习 三redis 数据结构》 《redis 从0到1完整学习 四字符串 SDS 数据结构》 《redis 从0到1完整学习 五集合 IntSet 数据结构》 《redis 从0到1完整学习 六Hash 表数据结构》 本文主要结合源码来介绍 ZipList 的数据结构
2. redis 源码下载
Redis 源码可以点击这里下载方便查看其中定义的一些数据结构。
3. zipList 数据结构
3.1 整体
zipList 是为了提高存储效率而设计的一种特殊编码的双向链表由一系列特殊编码的连续内存块组成。可以在任意一端进行 push 和 pop 操作并且该操作的时间复杂度为 O(1)。它可以存储字符串或者整数存储整数时是采用整数的二进制而不是字符串形式存储。
zipList 数据结构示意图
名称类型size用途zlbytesuint32_t4 字节记录整个 zipList 占用的字节总数即图中 zlbytes 的起始 到 zlend 的末尾zltailuint32_t4 字节记录 zipList 尾节点距离起始地址有多少字节即图中 zlbytes 起始 到 tail 起始的偏移量通过这个偏移量可以确定尾节点的地址zllenuint16_t2 字节记录了压缩列表包含的节点数量。 最大值为 UINT16_MAX 65534。如果超过这个值会记录为65535。entry不定压缩列表包含的各个节点节点的长度由节点保存的内容决定。zlenduint8_t1 字节特殊值 0xFF 十进制 255 用于标记压缩列表的末端。
3.2 entry 数据结构分析
ziplist 中的每个 entry 都以包含两条信息的元数据作为前缀。首先存储上一个 entry 的长度以便能够从后向前遍历列表。其次提供 entry encoding表示 entry 类型整数或字符串如果是字符串它还表示字符串有效负载的长度。因此完整的 entry 存储如下
prevlen前一个 entry 的长度占1个或5个字节。 如果前一个 entry 的长度 254字节则采用1个字节来保存这个长度值如果前一个 entry 的长度 254字节则采用5个字节来保存这个长度值第一个字节为 0xfe后四个字节才是真实长度数据 encoding编码属性记录数据类型字符串还是整数以及长度占用1个、2个或5个字节entry-data负责保存 entry 数据可以是字符串或整数
根据 redis 源码的注解来看encoding 的编码如下 1字符串编码
encoding 格式编码长度字符串大小|00pppppp|1 bytes 63 bytes|01pppppp|qqqqqqqq|2 bytes 16383 bytes|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|5 bytes 4294967295 bytes
例如下面保存 ab、bc 字符串示例 * [13 00 00 00] [0e 00 00 00] [02 00] [00 02 61 62] [04 02 62 63] [ff]* | | | | | |* zlbytes zltail zllen ab bc end* a 的 ASCII 码是97对应的16进制是61 b 的 ASCII 码是98对应的16进制是62 c 的 ASCII 码是99对应的16进制是63 ab 的编码是 6162长度是2字节所以 encoding 是 00000010 即 16进制02而前一个 entry 不存在因而 prevlen 为 0所以 ab 编码为 00026162同样的 bc 前一个 entry 为 ab字节一共为4所以 bc 编码为 04026263。
2数字编码
encoding 格式编码长度整数类型110000001int16_t2 bytes110100001int32_t4 bytes111000001int64_t8 bytes11110000124位有符整数(3 bytes)1111111018位有符整数(1 bytes)1111xxxx1在xxxx位置保存数值范围从0001~1101减1后结果为实际值
例如下面是 redis 源码给出的保存 2、5 整数示例 * [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]* | | | | | |* zlbytes zltail zllen 2 5 end* 2 的长度在 0001~1101对应上面表格的最后一种所以 encoding 为 11110011即16进制的 f3 这里的3实际为21同样 5 encoding 为 11110110即 f6
3.3 连锁更新
zipList 的每个 entry 都包含 prevlen 来记录上一个节点的大小长度是1个或5个字节
如果前一节点的长度 254字节则采用1个字节来保存这个长度值如果前一节点的长度 254字节则采用5个字节来保存这个长度值第一个字节为0xfe后四个字节才是真实长度数据
当一种边界场景下插入了一个 entryentry 的大小超过了 254 字节导致后续大范围的 entry 的 prevlen 由1字节转为用5个字节来保存触发了连锁更新同时删除也可能触发连锁更新。
4. 参考
《redis 从0到1完整学习 一安装初识 redis》 《redis 从0到1完整学习 二redis 常用命令》 《redis 从0到1完整学习 三redis 数据结构》 《redis 从0到1完整学习 四字符串 SDS 数据结构》 《redis 从0到1完整学习 五集合 IntSet 数据结构》 《redis 从0到1完整学习 六Hash 表数据结构》
