redis源码分析与思考（七）——压缩列表

ziplist，即压缩列表。在Redis中，它是为了尽量节约内存而开发出来的，可谓是将节约内存做到了极致。它是哈希键与列表键的底层实现之一，当哈希键与列表键只含有整数或者两者的键长度较小时，两者就采用压缩列表来实现其功能。

之所以被称作压缩列表，是因为不同于之前所说的adlist表，压缩列表将普通顺序表的pre与next指针取消掉，采用计算长度的方法来实现各种操作，而且其长度也做了动态内存分配。打个比方，在存贮内容时你只用了一两个字节，而pre与next指针却要占到几个字节，显然是不合理的。压缩列表就是把这个用计算长度的方法来代替，在一定的程度上减少了大量的内存，也就起到了压缩的作用。
当你在阅读其源码时，你会发现压缩列表本质上是一个字符串，只不过这个字符串由一系列的连续内存地址块组成。一个压缩列表包含多个节点(entry)，而一个节点包含着一个字节数组或者一个整数。

结构与创建

压缩列表的创建是直接基于指针操作的，它申请一块内存，并将这块内存分成几块分别用于记录该压缩列表的所占空间、多少节点等等，从而使得压缩列表看起来像是由一系列连续地址块组成的顺序表结构：

// 定位到 ziplist 的 bytes 属性，该属性记录了整个 ziplist 所占用的内存字节数
// 用于取出 bytes 属性的现有值，或者为 bytes 属性赋予新值
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
// 定位到 ziplist 的 offset 属性，该属性记录了到达表尾节点的偏移量
// 用于取出 offset 属性的现有值，或者为 offset 属性赋予新值
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
// 定位到 ziplist 的 length 属性，该属性记录了 ziplist 包含的节点数量
// 用于取出 length 属性的现有值，或者为 length 属性赋予新值
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
// 返回 ziplist 表头的大小
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
// 返回指向 ziplist 第一个节点（的起始位置）的指针
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
// 返回指向 ziplist 最后一个节点（的起始位置）的指针
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
// 返回指向 ziplist 末端 ZIP_END （的起始位置）的指针
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

//创建压缩列表
unsigned char *ziplistNew(void) {
    // ZIPLIST_HEADER_SIZE 是 ziplist 表头的大小
    // 1 字节是表末端 ZIP_END 的大小
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
    // 为表头和表末端分配空间
    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;
}

而节点的结构如下：

typedef struct zlentry {
    // prevrawlen ：前置节点的长度
    // prevrawlensize ：编码 prevrawlen 所需的字节大小
    unsigned int prevrawlensize, prevrawlen;
    // len ：当前节点值的长度
    // lensize ：编码 len 所需的字节大小
    unsigned int lensize, len;
    // 当前节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;
    // 当前节点值所使用的编码类型
    unsigned char encoding;
    // 指向当前节点的指针
    unsigned char *p;
} zlentry;

大量的使用宏定义来完成指针的移位操作，并且在指针移位的时候通过强制转换将指定的地址转换为存贮目标信息的位置。通过对宏定义的分析，不难得到压缩列表第一部分是ZIPLIST_BYTES，也就是首地址所在，它是用来存贮整个压缩列表所占字节的多少，即表示着压缩列表的大小，而其后是ZIPLIST_TAIL_OFFSET，这一部分的地址是通过第一部分移位sizeof(uint32_t)个字节大小得到的，从而得出第一部分占有sizeof(uint32_t)个字节，即4个字节，同理，可以通过该方法得到其余的几大部分：

1. ZIPLIST_BYTES：这部分是用来存贮压缩列表所占空间的大小，占4个字节。
2. ZIPLIST_TAIL_OFFSET：这部分是用来存贮偏移量的，这个偏移量用来计算左后一个节点的位置，所以压缩列表得到最后一个节点的位置复杂度为O(1)，占4个字节。
3. ZIPLIST_LENGTH：这一部分用来记录包含节点的数量，占两个字节。而第一、二、三部分构成了压缩列表的头。
4. ZIPLIST_ENTRY_HEAD：该指针指向第一个节点。
5. ZIPLIST_ENTRY_TAIL：该指针指向最后一个节点。第四以及第五指向的节点加上中间的节点共同组成压缩列表的body部分，即内容。
6. ZIPLIST_ENTRY_END：这一指针指向压缩列表的尾。
7. ZIP_END：这一部分表示压缩列表的尾部，用来标示已到尽头，占1字节。

如图所示：
redis源码分析与思考（七）——压缩列表

待续。。。。。。

redis源码分析与思考（七）——压缩列表

结构与创建

相关推荐