【Redis源码分析】Redis的压缩列表ZipList

53次阅读

共计 12162 个字符,预计需要花费 31 分钟才能阅读完成。

  本文将介绍 Redis 中一种重要的数据结构,这种数据结构是为了节省内存而设计的,这就是压缩列表(ZipList)。
1、简介
  压缩列表(ziplist)本质上就是一个字节数组,是 Redis 为了节约内存而设计的一种线性数据结构,可以包含任意多个元素,每个元素可以是一个字节数组或一个整数。Redis 的有序集合、哈希以及列表都直接或者间接使用了压缩列表。当有序集合或哈希的元素数目比较少,且元素都是短字符串时,Redis 便使用压缩列表作为其底层数据存储方式。列表使用快速链表(quicklist)数据结构存储,而快速链表就是双向链表与压缩列表的组合。例如,使用下面命令创建一个哈希键并查看其编码:
127.0.0.1:6379> hmset person name zhangsan gender 1 age 22
OK
127.0.0.1:6379> object encoding person
“ziplist”
2、数据存储
2.1 编码
  Redis 使用字节数组表示一个压缩列表,字节数组逻辑划分为多个字段,如图所示:

各字段含义如下:

1、zlbytes:压缩列表的字节长度,占 4 个字节,因此压缩列表最长(2^32)- 1 字节;
2、zltail:压缩列表尾元素相对于压缩列表起始地址的偏移量,占 4 个字节;
3、zllen:压缩列表的元素数目,占两个字节;那么当压缩列表的元素数目超过(2^16)- 1 怎么处理呢?此时通过 zllen 字段无法获得压缩列表的元素数目,必须遍历整个压缩列表才能获取到元素数目;
4、entryX:压缩列表存储的若干个元素,可以为字节数组或者整数;entry 的编码结构后面详述;
5、zlend:压缩列表的结尾,占一个字节,恒为 0xFF。

假设 char * zl 指向压缩列表首地址,Redis 通过以下宏定义实现了压缩列表各个字段的操作存取:
//zl 指向 zlbytes 字段
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))

//zl+ 4 指向 zltail 字段
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

//zl+zltail 指向尾元素首地址;intrev32ifbe 使得数据存取统一按照小端法
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))

//zl+ 8 指向 zllen 字段
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

// 压缩列表最后一个字节即为 zlend 字段
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
  了解了压缩列表的基本结构,我们可以很容易获得压缩列表的字节长度,元素数目等,那么如何遍历压缩列表的所有元素呢?我们已经知道对于每一个 entry 元素,存储的可能是字节数组或整数值;那么对任一个元素,我们如何判断存储的是什么类型?对于字节数组,我们又如何获取字节数组的长度?回答这些问题之前,需要先看看压缩列表元素的编码结构,如图所示:

  previous_entry_length 字段表示前一个元素的字节长度,占 1 个或者 5 个字节;当前一个元素的长度小于 254 字节时,previous_entry_length 字段用一个字节表示;当前一个元素的长度大于等于 254 字节时,previous_entry_length 字段用 5 个字节来表示;而这时候 previous_entry_length 的第一个字节是固定的标志 0xFE,后面 4 个字节才真正表示前一个元素的长度;假设已知当前元素的首地址为 p,那么(p-previous_entry_length)就是前一个元素的首地址,从而实现压缩列表从尾到头的遍历;encoding 字段表示当前元素的编码,即 content 字段存储的数据类型(整数或者字节数组),数据内容存储在 content 字段;为了节约内存,encoding 字段同样是可变长度,编码如表 - 1 所示:<center> 表 -1 压缩列表元素编码表格 </center>

encoding 编码
encoding 长度
content 类型

00 bbbbbb(6 比特表示 content 长度)
1 字节
最大长度 63 的字节数组

01 bbbbbb xxxxxxxx(14 比特表示 content 长度)
2 字节
最大长度(2^14)- 1 字节最大长度的字节数组

10 __  aaaaaaaa bbbbbbbb cccccccc dddddddd(32 比特表示 content 长度)
5 字节
最大长度(2^32)- 1 的字节数组

11 00 0000
1 字节
int16 整数

11 01 0000
1 字节
int32 整数

11 10 0000
1 字节
int64 整数

11 11 0000
1 字节
24 比特整数

11 11 1110
1 字节
8 比特整数

11 11 xxxx
1 字节
没有 content 字段;xxxx 表示 0~12 之间的整数

  可以看出,根据 encoding 字段第一个字节的前 2 个比特,可以判断 content 字段存储的是整数,或者字节数组(以及字节数组最大长度);当 content 存储的是字节数组时,后续字节标识字节数组的实际长度;当 content 存储的是整数时,根据第 3、4 比特才能判断整数的具体类型;而当 encoding 字段标识当前元素存储的是 0~12 的立即数时,数据直接存储在 encoding 字段的最后 4 个比特,此时没有 content 字段。参照 encoding 字段的编码表格,Redis 预定义了以下常量:
#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
#define ZIP_INT_16B (0xc0 | 0<<4)
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
#define ZIP_INT_24B (0xc0 | 3<<4)
#define ZIP_INT_8B 0xfe
2.2 结构体 entry
  2.1 节分析了压缩列表的底层存储结构。但是我们发现对于任意的压缩列表元素,获取前一个元素的长度,判断存储的数据类型,获取数据内容,都需要经过复杂的解码运算才行,那么解码后的结果应该被缓存起来,为此定义了结构体 zlentry,用于表示解码后的压缩列表元素:
typedef struct zlentry {
unsigned int prevrawlensize;
unsigned int prevrawlen;

unsigned int lensize;
unsigned int len;

unsigned int headersize;

unsigned char encoding;

unsigned char *p;
} zlentry;
  我们看到结构体定义了 7 个字段,而 2.1 节显示每个元素只包含 3 个字段。回顾压缩列表元素的编码结构,可变因素实际上不止三个;previous_entry_length 字段的长度(字段 prevrawlensize 表示)、previous_entry_length 字段存储的内容(字段 prevrawlen 表示)、encoding 字段的长度(字段 lensize 表示)、encoding 字段的内容(字段 len 表示数据内容长度,字段 encoding 表示数据类型)、和当前元素首地址(字段 p 表示)。而 headersize 字段则表示当前元素的首部长度,即 previous_entry_length 字段长度与 encoding 字段长度之和。函数 zipEntry 用来解码压缩列表的元素,存储于 zlentry 结构体:
void zipEntry(unsigned char *p, zlentry *e) {
ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
e->headersize = e->prevrawlensize + e->lensize;
e->p = p;
}
解码过程主要可以分为以下两个步骤:
1) 解码 previous_entry_length 字段,此时入参 ptr 指向元素首地址;
#define ZIP_BIG_PREVLEN 254

#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do {\
if ((ptr)[0] < ZIP_BIG_PREVLEN) {\
(prevlensize) = 1; \
(prevlen) = (ptr)[0]; \
} else {\
(prevlensize) = 5; \
memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \
memrev32ifbe(&prevlen); \
} \
} while(0);
2) 解码 encoding 字段逻辑,此时 ptr 指向元素首地址偏移 previous_entry_length 字段长度的位置:
#define ZIP_STR_MASK 0xc0

#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {\
(encoding) = (ptr[0]); \
// ptr[0]小于 11000000 说明是字节数组,前两个比特为编码
if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
if ((encoding) < ZIP_STR_MASK) {\
if ((encoding) == ZIP_STR_06B) {\
(lensize) = 1; \
(len) = (ptr)[0] & 0x3f; \
} else if ((encoding) == ZIP_STR_14B) {\
(lensize) = 2; \
(len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \
} else if ((encoding) == ZIP_STR_32B) {\
(lensize) = 5; \
(len) = ((ptr)[1] << 24) | \
((ptr)[2] << 16) | \
((ptr)[3] << 8) | \
((ptr)[4]); \
} else {\
panic(“Invalid string encoding 0x%02X”, (encoding));\
} \
} else {\
(lensize) = 1; \
(len) = zipIntSize(encoding); \
} \
} while(0);
字节数组只根据 ptr[0]的前 2 个比特即可判类型,而判断整数类型需要 ptr[0]的前 4 个比特,代码如下:
unsigned int zipIntSize(unsigned char encoding) {
switch(encoding) {
case ZIP_INT_8B: return 1;
case ZIP_INT_16B: return 2;
case ZIP_INT_24B: return 3;
case ZIP_INT_32B: return 4;
case ZIP_INT_64B: return 8;
}

// 4 比特立即数
if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
return 0;
panic(“Invalid integer encoding 0x%02X”, encoding);
return 0;
}
3、基本操作
3.1 创建压缩列表
创建压缩列表的 API 定义如下,函数无输入参数,返回参数为压缩列表首地址:
unsigned char *ziplistNew(void);
创建空的压缩列表,只需要分配初始存储空间(11=4+4+2+ 1 个字节),并对 zlbytes、zltail、zllen 和 zlend 字段初始化即可。
unsigned char *ziplistNew(void) {
//ZIPLIST_HEADER_SIZE = zlbytes + zltail + zllen;
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;

// 结尾标识 0XFF
zl[bytes-1] = ZIP_END;
return zl;
}
3.2 插入元素
压缩列表插入元素的 API 定义如下,函数输入参数 zl 表示压缩列表首地址,p 指向新元素的插入位置,s 表示数据内容,slen 表示数据长度,返回参数为压缩列表首地址。
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p,
unsigned char *s, unsigned int slen);
插入元素时,可以简要分为三个步骤:第一步需要将元素内容编码为压缩列表的元素,第二步重新分配空间,第三步拷贝数据。下面分别讨论每个步骤的实现逻辑。
1) 编码
编码即计算 previous_entry_length 字段、encoding 字段和 content 字段的内容。如何获取前一个元素的长度呢?这时候就需要根据插入元素的位置分情况讨论了,如图所示:

  当压缩列表为空插入位置为 P0 时,此时不存在前一个元素,即前一个元素的长度为 0;当插入位置为 P1 时,此时需要获取 entryX 元素的长度,而 entryX+ 1 元素的 previous_entry_length 字段存储的就是 entryX 元素的长度,比较容易获取;当插入位置为 P2 时,此时需要获取 entryN 元素的长度,entryN 是压缩列表的尾元素,计算其元素长度需要将其三个字段长度相加,函数实现如下:
unsigned int zipRawEntryLength(unsigned char *p) {
    unsigned int prevlensize, encoding, lensize, len;
    ZIP_DECODE_PREVLENSIZE(p, prevlensize);
    ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
    return prevlensize + lensize + len;
}
  其中 ZIP_DECODE_PREVLENSIZE 和 ZIP_DECODE_LENGTH 在 2.2 节已经讲过,这里不再赘述。encoding 字段标识的是当前元素存储的数据类型以及数据长度,编码时首先会尝试将数据内容解析为整数,如果解析成功则按照压缩列表整数类型编码存储,解析失败的话按照压缩列表字节数组类型编码存储。
if (zipTryEncoding(s,slen,&value,&encoding)) {
    reqlen = zipIntSize(encoding);
} else {
    reqlen = slen;
}
 
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
  程序首先尝试按照整数解析新添加元素的数据内容,数值存储在变量 value,编码存储在变量 encoding。如果解析成功,还需要计算整数所占字节数。变量 reqlen 最终存储的是当前元素所需空间大小,初始赋值为元素 content 字段所需空间大小,再累加 previous_entry_length 所需空间大小与 encoding 字段所需空间大小。
2) 重新分配空间

  由于新插入元素,压缩列表所需空间增大,因此需要重新分配存储空间。那么空间大小是否是添加元素前的压缩列表长度与新添加元素元素长度之和呢?并不完全是,如图中所示的例子。插入元素前,entryX 元素长度为 128 字节,entryX+ 1 元素的 previous_entry_length 字段占 1 个字节;添加元素 entryNEW 元素,元素长度为 1024 字节,此时 entryX+ 1 元素的 previous_entry_length 字段需要占 5 个字节;即压缩列表的长度不仅仅是增加了 1024 字节,还有 entryX+ 1 元素扩展的 4 字节。我们很容易知道,entryX+ 1 元素长度可能增加 4 字节,也可能减小 4 字节,也可能不变。而由于重新分配空间,新元素插入的位置指针 P 会失效,因此需要预先计算好指针 P 相对于压缩列表首地址的偏移量,待分配空间之后再偏移即可。
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl));
 
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {
    nextdiff = 0;
    forcelarge = 1;
}
 
// 存储偏移量
offset = p-zl;
// 调用 realloc 重新分配空间
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
// 重新偏移到插入位置 P
p = zl+offset;
  那么 nextdiff 与 forcelarge 在这里有什么用呢?分析 ziplistResize 函数的 3 个输入参数,curlen 表示插入元素前压缩列表的长度,reqlen 表示插入元素元素的长度,而 nextdiff 表示的是 entryX+ 1 元素长度的变化,取值可能为 0(长度不变)、4(长度增加 4)和 -4(长度减小 4)。我们再思考下,当 nextdiff 等于 -4,而 reqlen 小于 4 时会发生什么呢?没错,插入元素导致压缩列表所需空间减少了,即函数 ziplistResize 底层调用 realloc 重新分配的空间小于指针 zl 指向的空间。这可能会存在问题,我们都知道 realloc 重新分配空间时,返回的地址可能不变,当重新分配的空间大小反而减少时,realloc 底层实现可能会将多余的空间回收,此时可能会导致数据的丢失。因此需要避免这种情况的发生,即重新赋值 nextdiff 等于 0,同时使用 forcelarge 标记这种情况。可以再思考下,nextdiff 等于 - 4 时,reqlen 会小于 4 吗?答案是可能的,连锁更新可能会导致这种情况的发生。连锁更新将在第 4 节介绍。
3) 数据拷贝
  重新分配空间之后,需要将位置 P 后的元素移动到指定位置,将新元素插入到位置 P。我们假设 entryX+ 1 元素的长度增加 4(即 nextdiff 等于 4),此时数据拷贝示意图如图所示:

  从图中可以看到,位置 P 后的所有元素都需要移动,移动的偏移量是插入元素 entryNew 的长度,移动的数据块长度是位置 P 后所有元素长度之和再加上 nextdiff 的值,数据移动之后还需要更新 entryX+ 1 元素的 previous_entry_length 字段。
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); 
// 更新 entryX+ 1 元素的 previous_entry_length 字段字段
if (forcelarge)
    //entryX+ 1 元素的 previous_entry_length 字段依然占 5 个字节;
// 但是 entryNEW 元素长度小于 4 字节
    zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
    zipStorePrevEntryLength(p+reqlen,reqlen);
 
// 更新 zltail 字段
ZIPLIST_TAIL_OFFSET(zl) =
    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
 
zipEntry(p+reqlen, &tail);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
    ZIPLIST_TAIL_OFFSET(zl) =
        intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
 
// 更新 zllen 字段
ZIPLIST_INCR_LENGTH(zl,1);
  思考一下,第一次更新尾元素偏移量之后,为什么指向的元素可能不是尾元素呢?很显然,当 entryX+ 1 元素就是尾元素时,只需要更新一次尾元素的偏移量;但是当 entryX+ 1 元素不知尾元素,且 entryX+ 1 元素长度发生了改变,此时尾元素偏移量还需要加上 nextdiff 的值。
3.3 删除元素
  压缩列表删除元素的 API 定义如下,函数输入参数 zl 指向压缩列表首地址,* p 指向待删除元素的首地址(参数 p 同时可以作为输出参数),返回参数为压缩列表首地址。
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);
ziplistDelete 函数只是简单调用底层__ziplistDelete 函数实现删除功能;__ziplistDelete 函数可以同时删除多个元素,输入参数 p 指向的是首个删除元素的首地址,num 表示待删除元素数目。
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
    size_t offset = *p-zl;
    zl = __ziplistDelete(zl,*p,1);
    *p = zl+offset;
    return zl;
}
删除元素同样可以简要分为三个步骤:第一步计算待删除元素总长度,第二步数据拷贝,第三步重新分配空间。下面分别讨论每个步骤的实现逻辑。
1) 计算待删除元素总长度,其中 zipRawEntryLength 函数在 3.2 节已经讲过,这里不再详述;
// 解码第一个待删除元素
zipEntry(p, &first);
 
// 遍历所有待删除元素,同时指针 p 向后偏移
for (i = 0; p[0] != ZIP_END && i < num; i++) {
    p += zipRawEntryLength(p);
    deleted++;
}
//totlen 即为待删除元素总长度
totlen = p-first.p;
2) 数据拷贝;
第一步骤计算完成之后,指针 first 与指针 p 之间的元素都是待删除的。很显然,当指针 p 恰好指向 zlend 字段,不再需要数据的拷贝了,只需要更新尾节点的偏移量即可。下面分析另外一种情况,即指针 p 指向的是某一个元素而不是 zlend 字段。分析类似于 3.2 节插入元素。删除元素时,压缩列表所需空间减少,减少的量是否仅仅是待删除元素总长度呢?答案同样是否定的,举个简单的例子,下图是经过第一步骤计算之后的示意图:

  删除元素 entryX+ 1 到元素 entryN- 1 之间的 N -X- 1 个元素,元素 entryN- 1 的长度为 12 字节,因此元素 entryN 的 previous_entry_length 字段占 1 个字节;删除这些元素之后,entryX 称为了 entryN 的前一个元素,元素 entryX 的长度为 512 字节,因此元素 entryN 的 previous_entry_length 字段需要占 5 个字节。即删除元素之后的压缩列表的总长度,还与 entryN 元素长度的变化量有关。
// 计算元素 entryN 长度的变化量
nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
 
// 更新元素 entryN 的 previous_entry_length 字段
p -= nextdiff;
zipStorePrevEntryLength(p,first.prevrawlen);
 
// 更新 zltail
ZIPLIST_TAIL_OFFSET(zl) =
    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
 
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
    ZIPLIST_TAIL_OFFSET(zl) =
       intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
 
// 数据拷贝
memmove(first.p,p,
    intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
与 3.2 节插入元素更新 zltail 字段相同,当 entryX+ 1 元素就是尾元素时,只需要更新一次尾元素的偏移量;但是当 entryX+ 1 元素不是尾元素时,且 entryX+ 1 元素长度发生了改变,此时尾元素偏移量还需要加上 nextdiff 的值。
3) 重新分配空间
逻辑与 3.2 节插入元素逻辑基本类似,这里就不再详述。代码如下:
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
p = zl+offset;
ZIPLIST_INCR_LENGTH(zl,-deleted);
  思考一下:在 3.2 节我们提到,调用 ziplistResize 函数重新分配空间时,如果重新分配的空间小于指针 zl 指向的空间大小时,可能会出现问题。而这里由于是删除元素,压缩列表的长度肯定是减少的。为什么又能这样使用呢?根本原因在于删除元素时,我们是先拷贝数据,再重新分配空间,即调用 ziplistResize 函数时,多余的那部分空间存储的数据已经被拷贝了,此时回收这部分空间并不会造成数据的丢失。
3.5 遍历压缩列表
  遍历就是从头到尾(前向遍历)或者从尾到头(后向遍历)访问压缩列表中的每一个元素。压缩列表的遍历 API 定义如下,函数输入参数 zl 指向压缩列表首地址,p 指向当前访问元素的首地址;ziplistNext 函数返回后一个元素的首地址,ziplistPrev 返回前一个元素的首地址。
// 后向遍历
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);
// 前向遍历
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);
  我们已经知道压缩列表每个元素的 previous_entry_length 字段存储的是前一个元素的长度,因此压缩列表的前向遍历相对简单,表达式 (p-previous_entry_length) 即可获取前一个元素的首地址,这里不做详述。后向遍历时,需要解码当前元素,计算当前元素长度,才能获取后一个元素首地址;ziplistNext 函数实现如下:
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
    //zl 参数无用;这里只是为了避免警告
    ((void) zl);
 
    if (p[0] == ZIP_END) {
        return NULL;
    }
 
    p += zipRawEntryLength(p);
    if (p[0] == ZIP_END) {
        return NULL;
    }
 
    return p;
}
4、连锁更新
  如下图所示,删除压缩列表 zl1 位置 P1 的元素 entryX,或者在压缩列表 zl2 位置 P2 插入元素 entryY,此时会出现什么情况呢?

  压缩列表 zl1,元素 entryX 之后的所有元素 entryX+1、entryX+ 2 等长度都是 253 字节,显然这些元素的 previous_entry_length 字段的长度都是 1 字节。当删除元素 entryX 时,元素 entryX+ 1 的前驱节点改为元素 entryX-1,长度为 512 字节,此时元素 entryX+ 1 的 previous_entry_length 字段需要 5 字节才能存储元素 entryX- 1 的长度,则元素 entryX+ 1 的长度需要扩展至 257 字节;而由于元素 entryX+ 1 长度的增加,元素 entryX+ 2 的 previous_entry_length 字段同样需要改变。以此类推,由于删除了元素 entryX,之后的所有元素 entryX+1、entryX+ 2 等长度都必须扩展,而每次元素的扩展都将导致重新分配内存,效率是很低下的。压缩列表 zl2,插入元素 entryY 同样会产生上面的问题。上面的情况称之为连锁更新。从上面分析可以看出,连锁更新会导致多次重新分配内存以及数据拷贝,效率是很低下的。但是出现这种情况的概率是很低的,因此对于删除元素与插入元素的操作,redis 并没有为了避免连锁更新而采取措施。redis 只是在删除元素与插入元素操作的末尾,检查是否需要更新后续元素的 previous_entry_length 字段,其实现函数_ziplistCascadeUpdate,主要逻辑如下图所示:

5、总结
  本文首先介绍了压缩列表的编码与数据结构,随后介绍了压缩列表的基本操作:创建压缩列表、插入元素、删除元素与遍历,最后分析了压缩列表连锁更新的出现以及解决方案。

正文完
 0