• 周五. 10月 7th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

压缩列表

admin

11月 28, 2021

使用场景

  1. 当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,使用压缩列表实现列表键
  2. 当一个哈希键只包含少量键值对,并且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,使用压缩哈希实现哈希键

定义

// 压缩列表是为了节约内存而开发出由 一系列特殊编码的 连续内存块组成的 顺序型数据结构,一个压缩列表可以包含任意多个节点
// 压缩列表组成部分: zlbytes   zltail  zllen   entry1  entry2 ···· entryN  zlend
// zlbytes : 类型为uint32_t,长度为4个字节,记录整个压缩列表占用的内存字节数
// zltail : 类型为uint32_t,长度为4个字节,记录压缩列表表尾节点距离压缩列表的起始地址有多少字节
// zllen : 类型为uint16_t,长度为2个字节,记录压缩列表包含的节点数量
// entryX : 列表节点,记录压缩列表包含的各个节点,节点的长度由节点保存的内容决定
// zlend : 类型为uint8_t,长度为1个字节,特殊值0xFF(即255),用于标记压缩列表的末端

// 压缩列表节点:每个节点可以保存一个字符串或者一个整数值
typedef struct {
    // 当保存的是字节数组,sval保存字符串值,slen保存字符串的长度
    unsigned char *sval;
    unsigned int slen;

    // 当保存的是整数值,lval保存整数值,sval为NULL
    long long lval;

    // sval、lval这两个属性都由previous_entry_length、encoding、content三个部分组成
    // previous_entry_length : 以字节为单位,记录前一个节点的长度,可以凭此进行指针运算,从而实现遍历操作
    // encoding : 记录content所保存数据的类型以及长度
    // content : 保存节点的值

} ziplistEntry;

连续更新

每个节点的previous_entry_length都记录了前一个节点的长度:
如果前一节点的长度 < 254字节,那么previous_entry_length需要用1字节长的空间保存长度值
如果前一节点的长度 >= 254字节,那么previous_entry_length需要用5字节长的空间保存长度值

当添加新节点、删除节点的时候,前一个节点的长度值从 小于254字节 => 大于等于254字节
从而引发下一个节点的previous_entry_length需要从1字节扩展为5字节,
进而引发后续节点的previous_entry_length也需要从1字节扩展为5字节,
这种特殊情况下产生的连续多次空间扩展操作称之为 连锁更新 ,最坏复杂度为O(N^2)

要引发连锁更新的几率极低

  1. 压缩列表里要恰好有多个连续的、长度介于250字节至253字节之间的节点,连锁更新才有可能被引发,在实际中,这种情况并不多见
  2. 即使出现连锁更新,但只要被更新的节点数量不多,就不会对性能造成影响,

源码阅读

  1. 文件:src/ziplist.h 和 src/ziplist.c
只言片语任我说,提笔句句无需忖。落笔不知寄何人,唯有邀友共斟酌。

发表回复

您的电子邮箱地址不会被公开。