02 关于 ziplist

2024-02-17 11:16:04

前言

关于 redis 的数据结构 ziplist

相关介绍主要围绕着如下测试用例, 来看看 ziplist 的存储, 以及相关的 api

本文的 ziplist 相关代码拷贝自 redis-6.2.0

测试用例

//
// Created by Jerry.X.He on 2021-02-21.
//


#include <iostream>
#include "../libs/sds.h"
#include "../libs/ziplist.h"

using namespace std;

// Test25ZipListUsage
int main(int argc, char **argv) {

    unsigned char *zl = ziplistNew();

    // ziplistPush
    sds firstEle = sdsnew("first");
    zl = ziplistPush(zl, (unsigned char *) firstEle, (unsigned int) sdslen(firstEle), ZIPLIST_TAIL);
    sds secondEle = sdsnew("second");
    zl = ziplistPush(zl, (unsigned char *) secondEle, (unsigned int) sdslen(secondEle), ZIPLIST_TAIL);
    sds replacedFirstEle = sdsnew("replaceFirst");
    zl = ziplistPush(zl, (unsigned char *) replacedFirstEle, (unsigned int) sdslen(replacedFirstEle), ZIPLIST_HEAD);

    // ziplistInsert
    sds betweenFirstAndSecond = sdsnew("betweenFirstAndSecond");
    zl = ziplistInsert(zl, ziplistIndex(zl, 2),
                       (unsigned char *) betweenFirstAndSecond,
                       (unsigned int) sdslen(betweenFirstAndSecond));

    int len = ziplistLen(zl);

    // ziplistIndex
    unsigned char *secondEntry = ziplistIndex(zl, 1);
    unsigned char *secondEntryValue = NULL;
    unsigned int secondEntryLen = 0;
    ziplistGet(secondEntry, &secondEntryValue, &secondEntryLen, NULL);

    // ziplistNext
    unsigned char *thirdEntry = ziplistNext(zl, secondEntry);
    unsigned char *thirdEntryValue = NULL;
    unsigned int thirdEntryLen = 0;
    ziplistGet(secondEntry, &thirdEntryValue, &thirdEntryLen, NULL);

    // ziplistPrev
    secondEntry = ziplistPrev(zl, thirdEntry);
    ziplistGet(secondEntry, &secondEntryValue, &secondEntryLen, NULL);

    // ziplistFind
    unsigned char *findEntry = ziplistFind(zl, secondEntry, (unsigned char *) secondEle,
                                           (unsigned int) sdslen(secondEle), 0);
    unsigned char *findEntryValue = NULL;
    unsigned int findEntryLen = 0;
    ziplistGet(findEntry, &findEntryValue, &findEntryLen, NULL);

    // ziplistCompare
    unsigned int compResult = ziplistCompare(secondEntry, (unsigned char *) secondEle,
                                             (unsigned int) sdslen(secondEle));

    // ziplistDelete
    zl = ziplistDelete(zl, &secondEntry);
    int newLen = ziplistLen(zl);

    // ziplistBlobLen
    int zlBytes = ziplistBlobLen(zl);

    // ziplistRepr
    ziplistRepr(zl);

    int x = 0;

}

数据结构

ziplist 的内存结构大致如下 <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

zlbytes 是一个四字节的长度, 记录了当前 ziplist 多少字节

zltail 四字节, 是指向最后一个元素的偏移

zllen 两字节, 表示的是当前 ziplist 的元素数量

中间为当前 ziplist 的各个元素

zlend 一字节, 0xff 标记 ziplist 结尾标记[类似于 string 约束 '\0' 为结束符]

每一个 entry 的结构为

prevLen + len + data

zipEntry 的编码约定, 字符串或者是整形
   如果是 String, 以 0x00, 0x01, 0x10 开头, 分别用当前字节, 后面的1字节, 后面的4字节来表示当前 entry 的长度
   如果是 Int, 以 0x11 开头
       如果是以 0x11000000 开头, 后续 2 字节为内容
       如果是以 0x11010000 开头, 后续 4 字节为内容
       如果是以 0x11100000 开头, 后续 8 字节为内容
       如果是以 0x11110000 开头, 后续 3 字节为内容
       如果是以 0x11111110 开头, 后续 1 字节为内容
       其他场景当前字节即代表了值, ((val & 0x00001111) - 1), 值域为 0 - 12

对于 prevLen 的编码和上面的约束 Int 编码是不一样的

如果长度小于 254 则使用 1字节编码

否则第一个字节为 254 用于标记, 后续四个字节表示长度

ziplistNew

分配了 11 字节, 4字节的 zlBytes, 4字节的 zltail, 2字节的 zllen, 1字节的结束标记

我们来 inspect 一下 zl

可以发现 zlBytes 为 11, zltail 为 10, zllen 为 0

0x7fcaa950006a 位置上的 0xff 为 zlend ziplist 的结束标记

(lldb) x 0x7fcaa9500060
0x7fcaa9500060: 0b 00 00 00 0a 00 00 00 00 00 ff 00 00 00 00 70  ..........�....p
0x7fcaa9500070: 00 00 00 00 00 00 00 70 00 00 00 00 00 00 00 70  .......p.......p

ziplistPush

根据 where 选择带插入的位置, 表头还是表尾, 标记为节点 p, 插入数据在节点 p 之前
根据表头表尾的节点查询这个节点的占用字节数, 用于当前节点的 prevLen
尝试使用 int 来编码 entry, 获取当前 entry 内容会占用的字节数
获取编码 prevLen 需要的字节数 + 编码 len 需要的字节数 + 编码当前 entry 需要的字节数
计算节点 p 的 prevLen 和当前 entry 的 len 的长度之差 [p.prevLen 需要更新为 len] 标记为 nextDiff
根据当前长度 + 当前entry的长度 + 节点p变化的长度, realloc, 这里会更新 zlBytes
如果 p 是末尾节点, 则更新 zlTail
如果 p 是中间节点, 移动节点p以及后续节点, 写入更新之后的节点 p 的 prevLen 为 len, 如果 p 是最后一个节点, zlTail 累增 len, 否则 zlTail 累增 len + nextDiff
如果 p 节点长度会发生变化, 级联更新 p 后面的节点的 entry 的 prevLen, len 的相关信息
向当前节点编码 prevLen, len, 以及当前节点的数据信息
增加 zl 的 zlLen

我们来 inspect 一下 zl

可以发现 zlBytes 为 18, zltail 为 10, zllen 为 1

0x7fcaa950006a 位置上的 0x00 指的是 firstEntry 的 prevLen 为 0

0x7fcaa950006b 位置上的 0x05 指的是 firstEntry 的 len 为 5

紧接着的五个字节为 firstEntry 的数据 "first "

0x7fcaa9500071 位置上的 0xff 为 zlend ziplist 的结束标记

(lldb) x 0x7fcaa9500060
0x7fcaa9500060: 12 00 00 00 0a 00 00 00 01 00 00 05 66 69 72 73  ............firs
0x7fcaa9500070: 74 ff 00 00 00 00 00 70 00 00 00 00 00 00 00 70  t�.....p.......p

当执行过 "ziplistPush(zl, (unsigned char *) secondEle, (unsigned int) sdslen(secondEle), ZIPLIST_TAIL);" 之后

我们来 inspect 一下 zl

可以发现 zlBytes 为 26, zltail 为 17, zllen 为 2

0x7fcaa950006a 位置上的 0x00 指的是 firstEntry 的 prevLen 为 0

0x7fcaa950006b 位置上的 0x05 指的是 firstEntry 的 len 为 5

紧接着的五个字节为 firstEntry 的数据 "first"

0x7fcaa9500071 位置上的 0x07 指的是 secondEntry 的 prevLen 为 7

0x7fcaa9500072 上面的 0x06 值的是 secondEntry 的 len 为 6

紧接着的六个字节为 secondEntry 的数据 "second"

0x7fcaa9500079 位置上的 0xff 为 zlend ziplist 的结束标记

(lldb) x 0x7fcaa9500060
0x7fcaa9500060: 1a 00 00 00 11 00 00 00 02 00 00 05 66 69 72 73  ............firs
0x7fcaa9500070: 74 07 06 73 65 63 6f 6e 64 ff 00 00 00 00 00 70  t..second�.....p

当执行过 "ziplistPush(zl, (unsigned char *) replacedFirstEle, (unsigned int) sdslen(replacedFirstEle), ZIPLIST_HEAD);" 之后

我们来 inspect 一下 zl

可以发现 zlBytes 为 40, zltail 为 31, zllen 为 3

0x7fcaa950006a 位置上的 0x00 指的是 replacedFirstEntry 的 prevLen 为 0

0x7fcaa950006b 位置上的 0x0c 指的是 replacedFirstEntry 的 len 为 12

紧接着的十二个字节为 replacedFirstEntry 的数据 "replaceFirst"

0x7fcaa9500078 位置上的 0x0e 指的是 firstEntry 的 prevLen 为 14

0x7fcaa9500079 上面的 0x05 值的是 firstEntry 的 len 为 5

紧接着的五个字节为 firstEntry 的数据 "first"

0x7fcaa950007f 位置上的 0x07 指的是 secondEntry 的 prevLen 为 7

0x7fcaa9500080 上面的 0x06 值的是 secondEntry 的 len 为 6

紧接着的六个字节为 secondEntry 的数据 "second"

0x7fcaa9500087 位置上的 0xff 为 zlend ziplist 的结束标记

(lldb) x 0x7fcaa9500060 -c 0x30
0x7fcaa9500060: 28 00 00 00 1f 00 00 00 03 00 00 0c 72 65 70 6c  (...........repl
0x7fcaa9500070: 61 63 65 46 69 72 73 74 0e 05 66 69 72 73 74 07  aceFirst..first.
0x7fcaa9500080: 06 73 65 63 6f 6e 64 ff 00 00 00 00 00 00 00 70  .second�.......p

ziplistInsert

和上面的 __ziplistInsert 使用的同一套代码, 这里不多赘述, 流程也是一致

我们来 inspect 一下 zl, 这里具体的细节你可以自行分析

我们稍微看一下大致是四个元素, "replaceFirst", "first", "betweenFirstAndSecond", "second"

(lldb) x 0x7fcaa9500060 -c 0x50
0x7fcaa9500060: 3f 00 00 00 36 00 00 00 04 00 00 0c 72 65 70 6c  ?...6.......repl
0x7fcaa9500070: 61 63 65 46 69 72 73 74 0e 05 66 69 72 73 74 07  aceFirst..first.
0x7fcaa9500080: 15 62 65 74 77 65 65 6e 46 69 72 73 74 41 6e 64  .betweenFirstAnd
0x7fcaa9500090: 53 65 63 6f 6e 64 17 06 73 65 63 6f 6e 64 ff 70  Second..second�p
0x7fcaa95000a0: 00 00 00 00 00 00 00 70 00 00 00 00 00 00 00 70  .......p.......p

ziplistLen

对于 ziplist 的元素未溢出的情况, 直接读取 ziplist 头里面的 zllen

否则需要遍历一次 ziplist, 获取对象的长度

ziplistIndex

根据 index > 0, 来决定是 ziplist 头到尾的遍历, 还是尾到头的遍历

获取第 n 个元素, 如果走到最后一个元素之后, 或者第一个元素之前, 返回 NULL

返回的是该节点的指针

inspect 一下第二个 entry, 可以看到当前 entry 的 prevLen 为 14, len 为 5

接下来五个字节表示数据, "first"

entry 里面已经包含了向前, 向后迭代元素的完整的信息, 以及当前 entry 的所有的信息

(lldb) x 0x7fcaa9500078
0x7fcaa9500078: 0e 05 66 69 72 73 74 07 15 62 65 74 77 65 65 6e  ..first..between
0x7fcaa9500088: 46 69 72 73 74 41 6e 64 53 65 63 6f 6e 64 17 06  FirstAndSecond..

ziplistGet

根据 entry 的指针构造 zipEntry

如果是字符串, 更新字符串的长度, 以及指针信息

如果是 Int, 将 zipEntry 保存的 Int 数据信息放置到整形结果指针中

根据 zipEntry 指针构造 zipEntry

获取 prevLen, len, 数据指针, 其他的为推导的辅助字段, 比如 prevlenSize, lenSize, headerSize

ziplistNext/ziplistPrev

根据当前 entry 的元素据信息, 返回下一个 entry 的地址, 如果迭代到末尾, 返回 NULL

根据当前 entry 的元素据信息, 返回上一个 entry 的地址, 如果迭代到列表头, 返回 NULL

ziplistFind

从给定的 entry 开始每次跳过 skip 个元素

然后进行元素比较, 字符串使用 memcmp 比较, Int 使用 == 比较, 找到和目标元素相同的元素, 返回该 entry

如果已经迭代到末尾, 返回 NULL

ziplistCompare

比较给定的 entry 的数据, 和传入的待比较的数据是否相同

ziplistDelete

记录 p 的偏移, __ziplistDelete 可能对 ziplist realloc
执行业务 __ziplistDelete
   从 p 开始删除 num 个元素, 计算迭代 num 个元素之后的位置, pNext, 计算移除的entry的长度 len
   如果 pNext 之后没有元素了, 更新 zlTail, nextDiff 为 0
   如果 pNext 之后还有元素, 更新 pNext 的 prevLen 为 p.prevrawlen, 如果 pNext 是最后一个节点, zlTail 减去 len, 否则 zlTail 减去 (len + nextDiff), 将 pNext 以及之后的元素向前移动, 移动到 p
   根据当前长度 - 移除entry的长度 + 节点pNext变化的长度, realloc, 这里会更新 zlBytes
   如果节点pNext长度发生变化, 级联更新 pNext 后面的节点的 entry 的 prevLen, len 的相关信息
更新 p, 更新为基于新的 zl 的地址

我们来 inspect 一下 zl

可以发现 zlBytes 为 56, zltail 为 47, zllen 为 3

0x7fcaa950006a 位置上的 0x00 指的是 replacedFirstEntry 的 prevLen 为 0

0x7fcaa950006b 位置上的 0x0c 指的是 replacedFirstEntry 的 len 为 12

紧接着的十二个字节为 betweenFirstAndSecondEntry 的数据 "replaceFirst"

0x7fcaa9500078 位置上的 0x0e 指的是 betweenFirstAndSecondEntry 的 prevLen 为 14

0x7fcaa9500079 上面的 0x15 值的是 betweenFirstAndSecondEntry 的 len 为 21

紧接着的二十一个字节为 betweenFirstAndSecondEntry 的数据 "betweenFirstAndSecond"

0x7fcaa950007f 位置上的 0x17 指的是 secondEntry 的 prevLen 为 23

0x7fcaa9500090 上面的 0x06 值的是 secondEntry 的 len 为 6

紧接着的六个字节为 secondEntry 的数据 "second"

0x7fcaa9500097 位置上的 0xff 为 zlend ziplist 的结束标记

(lldb) x 0x7fcaa9500060 -c 0x50
0x7fcaa9500060: 38 00 00 00 2f 00 00 00 03 00 00 0c 72 65 70 6c  8.../.......repl
0x7fcaa9500070: 61 63 65 46 69 72 73 74 0e 15 62 65 74 77 65 65  aceFirst..betwee
0x7fcaa9500080: 6e 46 69 72 73 74 41 6e 64 53 65 63 6f 6e 64 17  nFirstAndSecond.
0x7fcaa9500090: 06 73 65 63 6f 6e 64 ff 73 65 63 6f 6e 64 ff 70  .second�second�p
0x7fcaa95000a0: 00 00 00 00 00 00 00 70 00 00 00 00 00 00 00 70  .......p.......p

ziplistBlobLen

直接使用 ziplist 表头的元数据 zlBytes 进行支持

相对来说还是比较简单, 维护 ziplist 的各个 entry 记录的编码约束比较麻烦

至于各个函数语义, 可以稍微看下 doc 就明确了

ziplistRepr

输出 ziplist 的头数据信息, 输出每一个 entry 的相关数据信息

如上面 zl 输出结果如下

为了更深入的理解各个 ziplist 这个数据结构, 初学还是建议直接查看内存信息来剖析

{total bytes 56} {num entries 3}
{tail offset 47}
{
	addr 0x7f86ce402bba,
	index  0,
	offset    10,
	hdr+entry len:    14,
	hdr len 2,
	prevrawlen:     0,
	prevrawlensize:  1,
	payload    12
	bytes: 00|0c|72|65|70|6c|61|63|65|46|69|72|73|74|
	[str]replaceFirst
}
{
	addr 0x7f86ce402bc8,
	index  1,
	offset    24,
	hdr+entry len:    23,
	hdr len 2,
	prevrawlen:    14,
	prevrawlensize:  1,
	payload    21
	bytes: 0e|15|62|65|74|77|65|65|6e|46|69|72|73|74|41|6e|64|53|65|63|6f|6e|64|
	[str]betweenFirstAndSecond
}
{
	addr 0x7f86ce402bdf,
	index  2,
	offset    47,
	hdr+entry len:     8,
	hdr len 2,
	prevrawlen:    23,
	prevrawlensize:  1,
	payload     6
	bytes: 17|06|73|65|63|6f|6e|64|
	[str]second
}
{end}

完

码农公寓

前言

测试用例

数据结构

ziplistNew

ziplistPush

ziplistInsert

ziplistLen

ziplistIndex

ziplistGet

ziplistNext/ziplistPrev

ziplistFind

ziplistCompare

ziplistDelete

ziplistBlobLen

ziplistRepr

相关文章