知识点
- 压缩列表是一种为节约内存而开发的顺序型数据结构
- 压缩列表被用作列表键和哈希键的底层实现之一，当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做键表列的底层实现。
- 另外，当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做哈希键的底层实现。
- 压缩列表可以包含多个节点，每个节点可以保存一个字节数或者整数值
- 添加新节点到压缩列表，或者从压缩列表中删除节点，可能引起连锁更新操作，但这种操作出现的概率不高。
压缩列表概述
压缩列表是一种编码过的“链表”旨在实现高效的内存管理。它可以存储整数和字符串，整数以小端序存储，字符串则以字节数组存储
其中zlbytes、zltail、zllen 是 压缩列表头（ ziplist header ），entry1 到 entryN 是列表的结点部分，zlen 是结尾标记。
- zlbytes：记录整个压缩列表占用的内存字节数，在对压缩列表进行内存重分配时或者计算zlend的位置时使用
- zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，redis无需遍历整个压缩列表就可以确定表尾节点的地址
- zllen：记录了压缩列表包含的节点数量
- entry：压缩列表的各个节点
- end：用于标记压缩列表末端
结构体
/*
* 节点结构
*/
typedef struct zlentry {
unsigned int prevrawlensize, // 保存前一节点的长度所需的长度
prevrawlen; // 前一节点的长度
unsigned int lensize, // 保存节点的长度所需的长度
len; // 节点的长度
unsigned int headersize; // header 长度
unsigned char encoding; // 编码方式
unsigned char *p; // 内容
} zlentry;
连锁更新
-
考虑这样一种情况， 有多个连续的、长度介于 250 字节到 253 字节之间的结点 e1 到 eN 。由于长度范围在 [250, 253]，所以每个结点的 prevlen 字段只需要一个字节。其中 e1 的 prevlen 字段等于 0。如图所示：
-
这时，我们在列表头插入一个新结点 new ，这个新结点的长度大于等于 254 。如图所示：
- e1 的 prevlen 字段就表示 new 结点的长度（大于等于254），需要从 1字节 变为 5字节。换言之，e1 结点的长度增加了4。 e1 结点原本的长度范围在 [250，253]，现在变成了 [254, 257]，那么 e2 结点的 prevlen 字段也从原来的 1 字节变成了 5 字节。就这样以此类推， 一直到 eN，所有结点的 prevlen 字段都从 1 字节 增长为 5 字节。这就是连锁更新。
- 连锁更新最坏情况下会触发 n 次空间重分配 (realloc) 和内存移动 (memmove)，每次空间重分配的复杂度是O(n)，所以连锁更新的最坏时间复杂度是O(n^2)。但是由于要有恰好多个长度 [250, 253] 的结点才会触发连锁更新，连续三五个在这个范围内的结点是不会影响性能的。
API源码
/*
* 新创建一个空 ziplist
* 返回值：新创建的 ziplist
*/
unsigned char *ziplistNew(void) {
// 分配 2 个 32 bit，一个 16 bit，以及一个 8 bit
// 分别用于 <zlbytes><zltail><zllen> 和 <zlend>
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;
}
/* Resize the ziplist. */
/*
* 对 zl 进行空间重非配，并更新相关属性
* 返回值：更新后的 ziplist
*/
static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
// 重分配
zl = zrealloc(zl,len);
// 更新长度
ZIPLIST_BYTES(zl) = intrev32ifbe(len);
// 设置表尾
zl[len-1] = ZIP_END;
return zl;
}
/* Insert item at "p". */
/*
* 添加保存给定元素 s 的新节点到地址 p
* 返回值：删除元素后的 ziplist
*/
static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)),
reqlen,
prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789; /* initialized to avoid warning. Using a value
that is easy to see if for some reason
we use it uninitialized. */
zlentry entry, tail;
/* Find out prevlen for the entry that is inserted. */
// 如果 p 之后不是没有节点（不是插入到末端）
// 那么取出节点相关资料，以及 prevlen
if (p[0] != ZIP_END) {
entry = zipEntry(p);
prevlen = entry.prevrawlen;
} else {
// 获取列表最后一个节点（表尾）的地址
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
// 如果地址之后不是末端（也即是，列表至少有一个节点）
if (ptail[0] != ZIP_END) {
// 保存 ptail 指向的节点的空间长度
prevlen = zipRawEntryLength(ptail);
}
}
/* See if the entry can be encoded */
// 查看能否将新值保存为整数
// 如果可以的话返回 1 ，
// 并将新值保存到 value ，编码形式保存到 encoding
if (zipTryEncoding(s,slen,&value,&encoding)) {
/* 'encoding' is set to the appropriate integer encoding */
// s 可以保存为整数，那么继续计算保存它所需的空间
reqlen = zipIntSize(encoding);
} else {
/* 'encoding' is untouched, however zipEncodeLength will use the
* string length to figure out how to encode it. */
// 不能保存为整数，直接使用字符串长度
reqlen = slen;
}
/* We need space for both the length of the previous entry and
* the length of the payload. */
// 计算编码 prevlen 所需的长度
reqlen += zipPrevEncodeLength(NULL,prevlen);
// 计算编码 slen 所需的长度
reqlen += zipEncodeLength(NULL,encoding,slen);
/* When the insert position is not equal to the tail, we need to
* make sure that the next entry can hold this entry's length in
* its prevlen field. */
// 如果添加的位置不是表尾，那么必须确定后继节点的 prevlen 空间
// 足以保存新节点的编码长度
// zipPrevLenByteDiff 的返回值有三种可能：
// 1）新旧两个节点的编码长度相等，返回 0
// 2）新节点编码长度 > 旧节点编码长度，返回 5 - 1 = 4
// 3）旧节点编码长度 > 新编码节点长度，返回 1 - 5 = -4
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
/* Store offset because a realloc may change the address of zl. */
// 保存偏移量，因为重分配空间有可能改变 zl 的内存地址
offset = p-zl;
// 重分配空间，并更新长度属性和表尾
// 新空间长度 = 现有长度 + 新节点所需长度 + 编码新节点长度所需的长度差
// O(N)
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
// 更新 p 的指针
p = zl+offset;
/* Apply memory move when necessary and update tail offset. */
// 如果新节点不是添加到列表末端，那么它后面就有其他节点
// 因此，我们需要移动这部分节点
if (p[0] != ZIP_END) {
/* Subtract one because of the ZIP_END bytes */
// 向右移动移原有数据，为新节点让出空间
// O(N)
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/* Encode this entry's raw length in the next entry. */
// 将本节点的长度编码至下一节点
zipPrevEncodeLength(p+reqlen,reqlen);
/* Update offset for tail */
// 更新 ziplist 的表尾偏移量
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
/* When the tail contains more than one entry, we need to take
* "nextdiff" in account as well. Otherwise, a change in the
* size of prevlen doesn't have an effect on the *tail* offset. */
// 有需要的话，将 nextdiff 也加上到 zltail 上
tail = zipEntry(p+reqlen);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
/* This element will be the new tail. */
// 更新 ziplist 的 zltail 属性，现在新添加节点为表尾节点
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
/* When nextdiff != 0, the raw length of the next entry has changed, so
* we need to cascade the update throughout the ziplist */
if (nextdiff != 0) {
offset = p-zl;
// O(N^2)
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
/* Write the entry */
// 写入数据到节点
// 编码上一节点的长度，并向后移动指针
p += zipPrevEncodeLength(p,prevlen);
// 编码本节点的长度和类型，并向后移动指针
p += zipEncodeLength(p,encoding,slen);
// 写入内容到节点
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
// 更新节点数量
ZIPLIST_INCR_LENGTH(zl,1);
return zl;
}
/*
* 将新元素插入为列表的表头节点或者表尾节点
* 返回值：添加操作完成后的 ziplist
*/
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
unsigned char *p;
p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
return __ziplistInsert(zl,p,s,slen);
}
/*
* 返回指向 p 的下一个节点的指针，
* 如果 p 已经到达表尾，那么返回 NULL 。
*/
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
((void) zl);
/* "p" could be equal to ZIP_END, caused by ziplistDelete,
* and we should return NULL. Otherwise, we should return NULL
* when the *next* element is ZIP_END (there is no next entry). */
if (p[0] == ZIP_END) {
return NULL;
}
// 指向下一节点，O(1)
p += zipRawEntryLength(p);
if (p[0] == ZIP_END) {
return NULL;
}
return p;
}
/*
* 返回 p 的前一个节点
*/
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
zlentry entry;
/* Iterating backwards from ZIP_END should return the tail. When "p" is
* equal to the first element of the list, we're already at the head,
* and should return NULL. */
// 这是表尾
if (p[0] == ZIP_END) {
p = ZIPLIST_ENTRY_TAIL(zl);
return (p[0] == ZIP_END) ? NULL : p;
// 到达表头，停止
} else if (p == ZIPLIST_ENTRY_HEAD(zl)) {
return NULL;
} else {
entry = zipEntry(p);
assert(entry.prevrawlen > 0);
return p-entry.prevrawlen;
}
}
/*
* 删除 p 所指向的节点，
* 并原地更新 p 指针，让它指向被删除节点的后一个节点，
* 使得可以迭代地进行删除
* 返回值：删除完成后的 ziplist
*/
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
size_t offset = *p-zl;
zl = __ziplistDelete(zl,*p,1);
/* Store pointer to current element in p, because ziplistDelete will
* do a realloc which might result in a different "zl"-pointer.
* When the delete direction is back to front, we might delete the last
* entry and end up with "p" pointing to ZIP_END, so check this. */
*p = zl+offset;
return zl;
}
/*
* 将 p 所指向的节点的属性和 sstr 以及 slen 进行对比，
* 如果相等则返回 1 。
*/
unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) {
zlentry entry;
unsigned char sencoding;
long long zval, sval;
// p 是表尾？
if (p[0] == ZIP_END) return 0;
// 获取节点属性
entry = zipEntry(p);
// 对比字符串
if (ZIP_IS_STR(entry.encoding)) {
/* Raw compare */
if (entry.len == slen) {
// O(N)
return memcmp(p+entry.headersize,sstr,slen) == 0;
} else {
return 0;
}
// 对比整数
} else {
/* Try to compare encoded values. Don't compare encoding because
* different implementations may encoded integers differently. */
if (zipTryEncoding(sstr,slen,&sval,&sencoding)) {
zval = zipLoadInteger(p+entry.headersize,entry.encoding);
return zval == sval;
}
}
return 0;
}
/* Return length of ziplist. */
/*
* 返回 ziplist 的长度
*/
unsigned int ziplistLen(unsigned char *zl) {
unsigned int len = 0;
// 节点的数量 < UINT16_MAX
if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) {
// 长度保存在一个 uint16 整数中
len = intrev16ifbe(ZIPLIST_LENGTH(zl));
// 节点的数量 >= UINT16_MAX
} else {
// 遍历整个 ziplist ，计算长度
unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
while (*p != ZIP_END) {
p += zipRawEntryLength(p);
len++;
}
/* Re-store length if small enough */
if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len);
}
return len;
}
/* Return ziplist blob size in bytes. */
/*
* 返回整个 ziplist 的空间大小
*/
size_t ziplistBlobLen(unsigned char *zl) {
return intrev32ifbe(ZIPLIST_BYTES(zl));
}
网友评论