发表于 | 分类于 | 0 | 阅读次数 32

压缩链表简介

压缩列表(ziplist)是List类型和Hash类型的底层编码实现之一。比如List底层的编码有两种：ziplist和linkedlist，hash类型也有两种：ziplist和hashtable。这两种Redis的基本类型都用到了ziplist编码。

为什么List和Hash都用到了ziplist去做底层实现呢？因为ziplist对空间的利用节省到了极致，先来看下ziplist的数据结构，在源码ziplist.c文件中注释中可以看到，但是我并没有找到相关结构体的定义，只找到了entry节点的结构体定义。ziplist是个连续的entry节点组成的列表。

压缩列表数据结构

ziplist结构：
ziplist_2.png

<zlbytes><zltail><zllen><entry><entry><zlend>
  • zlbytes：记录着ziplist总大小(byte)
  • zltail：ziplist表尾的entry节点距ziplist起始位置有多少个字节，用zltail通过计算可以很快得出ziplist表尾的位置
  • zllen：压缩列表中entry节点的个数
  • entry：节点，在ziplist中连续排列
  • zlend：用于标记ziplist的结束位置，相当于字符串用'\0'来标记结束位置

entry结构：

typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;	// prevrawlen前一个entry的长度
    unsigned int lensize, len;
    unsigned int headersize;
    unsigned char encoding;	// p的实际类型
    unsigned char *p;	// 节点的值
} zlentry;
  • p：节点内容，节点可以是个字节数组或者整数，它的类型和长度由encoding属性决定
  • prevrawlen：前一个entry的长度，如果前一节点的长度小于 254 字节， 那么 prevrawlen 属性的长度为 1 字节，如果前一节点的长度大于等于 254 字节， 那么prevrawlen属性的长度为 5 字节
  • encoding：p属性的实际类型，这个是ziplist节省空间的关键，如果可以动态调整p的类型大小
    ziplist_1.png

连锁更新

前面说过， 每个节点的 prevrawlen 属性都记录了前一个节点的长度：

  • 如果前一节点的长度小于 254 字节， 那么 prevrawlen 属性需要用 1 字节长的空间来保存这个长度值。
  • 如果前一节点的长度大于等于 254 字节， 那么 prevrawlen 属性需要用 5 字节长的空间来保存这个长度值。

ziplist_1.jpg

因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作， 而每次空间重分配的最坏复杂度为 O(N)