网站的数据库做备份,想开工作室没有项目,企业邮箱 888 密码 888,开发一个h5网站多少钱压缩列表ziplist本质上就是一个字节数组#xff0c;是Redis为了节约内存而设计的一种线性数据结构#xff0c;可以包含多个元素#xff0c;每个元素可以是一个字节数组或一个整数。Redis的有序集合、散列和列表都直接或者间接使用了压缩列表。当有序集合或散列表的元素个数比…压缩列表ziplist本质上就是一个字节数组是Redis为了节约内存而设计的一种线性数据结构可以包含多个元素每个元素可以是一个字节数组或一个整数。Redis的有序集合、散列和列表都直接或者间接使用了压缩列表。当有序集合或散列表的元素个数比较少且元素都是短字符串时Redis便使用压缩列表作为其底层数据存储结构。列表使用快速链表quicklist数据结构存储而快速链表就是双向链表与压缩列表的组合。
例如使用如下命令创建一个散列键并查看其编码。 127.0.0.1:6379 hmset person name zhangsan gender 1 age 22OK127.0.0.1:6379 object encoding personziplist
本章将从源码层次详细介绍压缩列表的存储结构及基本操作。
压缩列表的存储结构
Redis使用字节数组表示一个压缩列表压缩列表结构示意如下图所示 各字段的含义如下 zlbytes压缩列表的字节长度占4个字节因此压缩列表最多有-1个字节。zltail压缩列表尾元素相对于压缩列表起始地址的偏移量占4个字节。zllen压缩列表的元素个数占2个字节。zllen无法存储元素个数超过65535-1的压缩列表必须遍历整个压缩列表才能获取到元素个数。entryX压缩列表存储的元素可以是字节数组或者整数长度不限。entry的编码结构将在后面详细介绍。zlend压缩列表的结尾占1个字节恒为0xFF。 假设char * zl指向压缩列表首地址Redis可通过以下宏定义实现压缩列表各个字段的存取操作。
/* zl返回zlbytes的总字节数。 */
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))/* zl4返回zltail的偏移量。 */
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)sizeof(uint32_t))))/* 返回ziplist的长度如果无法确定长度则返回UINT16_MAX。 */
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)sizeof(uint32_t)*2)))/* ziplist头部的大小两个32位整数用于总字节数和最后一个项的偏移量。一个16位整数用于项数字段。 */
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2sizeof(uint16_t))/* 返回zlend的大小只有一个字节。 */
#define ZIPLIST_END_SIZE (sizeof(uint8_t))/* 返回ziplist的第一个条目的指针。 */
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)ZIPLIST_HEADER_SIZE)/* 使用ziplist头部中的最后一个条目偏移量返回ziplist的最后一个条目的指针。 */
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))/* 返回ziplist的最后一个字节的指针即end of ziplist FF条目的末尾。 */
#define ZIPLIST_ENTRY_END(zl) ((zl)intrev32ifbe(ZIPLIST_BYTES(zl))-ZIPLIST_END_SIZE)
其中头部是zlbyteszltailzllen一共占用了442即ZIPLIST_HEADER_SIZE。压缩列表中第一个元素的指针偏移量是zlZIPLIST_HEADER_SIZE。
了解了压缩列表的基本结构我们可以很容易地获得压缩列表的字节长度、元素个数等那么如何遍历压缩列表呢对于任意一个元素我们如何判断其存储的是什么类型呢我们又如何获取字节数组的长度呢
回答这些问题之前需要先了解压缩列表元素的编码结构如下所示 previous_entry_length字段表示前一个元素的字节长度占1个或者5个字节当前一个元素的长度小于254字节时用1个字节表示当前一个元素的长度大于或等于254字节时用5个字节来表示。而此时previous_entry_length字段的第1个字节是固定的0xFE后面4个字节才真正表示前一个元素的长度。假设已知当前元素的首地址为p那么p-previous_entry_length就是前一个元素的首地址从而实现压缩列表从尾到头的遍历。
encoding字段表示当前元素的编码即content字段存储的数据类型整数或者字节数组数据内容存储在content字段。为了节约内存encoding字段同样长度可变。压缩列表元素的编码如下表所示 可以看出根据encoding字段第1个字节的前2位可以判断content字段存储的是整数或者字节数组及其最大长度。当content存储的是字节数组时后续字节标识字节数组的实际长度当content存储的是整数时可根据第3、第4位判断整数的具体类型。而当encoding字段标识当前元素存储的是012的立即数时数据直接存储在encoding字段的最后4位此时没有content字段。参照encoding字段的编码表格Redis预定义了以下常量对应encoding字段的各编码类型
#define ZIP_STR_06B (0 6)
#define ZIP_STR_14B (1 6)
#define ZIP_STR_32B (2 6)
#define ZIP_INT_16B (0xc0 | 04)
#define ZIP_INT_32B (0xc0 | 14)
#define ZIP_INT_64B (0xc0 | 24)
#define ZIP_INT_24B (0xc0 | 34)
#define ZIP_INT_8B 0xfe
结构体
我们发现对于压缩列表的任意元素获取前一个元素的长度、判断存储的数据类型、获取数据内容都需要经过复杂的解码运算。解码后的结果应该被缓存起来为此定义了结构体zlentry用于表示解码后的压缩列表元素。
/* 我们使用这个函数来接收关于ziplist条目的信息。* 注意这些数据并不是这样编码的这只是我们通过一个函数填充的以便更轻松地操作的数据。 */
typedef struct zlentry {unsigned int prevrawlensize; /* 编码前一个条目长度所使用的字节数 */unsigned int prevrawlen; /* 前一个条目长度 */unsigned int lensize; /* 编码条目类型/长度所使用的字节数。例如字符串有1、2或5个字节的头部。整数始终使用一个字节。*/unsigned int len; /* 表示实际条目的字节数。对于字符串这只是字符串的长度而对于整数取决于数值范围可以是1、2、3、4、8或0对于4位立即整数。 */unsigned int headersize; /* prevrawlensize lensize */unsigned char encoding; /* 根据条目的编码设置为ZIP_STR_*或ZIP_INT_*。然而对于4位立即整数它可以假设一组值并需要进行范围检查。 */unsigned char *p; /* 指向条目开头的指针即指向前条目长度字段。 */
} zlentry;
回顾压缩列表元素的编码结构可变因素实际上不止3个previous_entry_length字段的长度prevrawlensize、previous_entry_length字段存储的内容prevrawlen、encoding字段的长度lensize、encoding字段的内容len表示元素数据内容的长度encoding表示数据类型和当前元素首地址p而headersize则表示当前元素的首部长度即previous_entry_length字段长度与encoding字段长度之和。
函数zipEntry用来解码压缩列表的元素存储于zlentry结构体。
/* 填充一个关于条目的信息的结构体。* 此函数是下面那个函数的不安全替代方案。* 一般情况下返回ziplist中元素指针的所有函数都会断言这个元素是有效的因此可以自由使用。* 一般情况下ziplistGet等函数假设输入指针已经经过验证因为它是另一个函数的返回值。*/
static inline void zipEntry(unsigned char *p, zlentry *e) {ZIP_DECODE_PREVLEN(p, e-prevrawlensize, e-prevrawlen);ZIP_ENTRY_ENCODING(p e-prevrawlensize, e-encoding);ZIP_DECODE_LENGTH(p e-prevrawlensize, e-encoding, e-lensize, e-len);assert(e-lensize ! 0); /* 检查编码是否有效。*/e-headersize e-prevrawlensize e-lensize;e-p p;
}
解码主要可以分为以下两个步骤。
1解码previous_entry_length字段此时入参ptr指向元素首地址。
#define ZIP_END 255 /* 特殊的 ziplist结尾 标记值。 */
#define ZIP_BIG_PREVLEN 254 /* ZIP_BIG_PREVLEN - 1 是前一个条目的最大长度用于表示每个条目的prevlen字段前缀如果长度大于等于254字节则使用FE AA BB CC DD表示其中AA BB CC DD是一个无符号整数使用4个字节表示前一个条目的长度。 *//* * 返回用于编码上一个条目的长度的字节数。 * 长度通过将变量 prevlensize 设置为特定值来返回。*/
#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \if ((ptr)[0] ZIP_BIG_PREVLEN) { \(prevlensize) 1; \} else { \(prevlensize) 5; \} \
} while(0)/* 返回前一个元素的长度以及用于编码前一个元素长度的字节数。* ptr 必须指向一个元素的前一个元素长度的 prevlen 前缀用于遍历元素向后导航。* 前一个元素的长度存储在 prevlen 中编码前一个元素长度所需的字节数存储在 prevlensize 中。 */
#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \if ((prevlensize) 1) { \(prevlen) (ptr)[0]; \} else { /* prevlensize 5 */ \(prevlen) ((ptr)[4] 24) | \((ptr)[3] 16) | \((ptr)[2] 8) | \((ptr)[1]); \} \
} while(0)
2解码encoding字段逻辑此时入参ptr指向元素首地址偏移previous_entry_length字段长度的位置。
#define ZIP_STR_MASK 0xc0/* 从指向 ptr 的字节中提取编码并将其设置为 zlentry 结构体中的 encoding 字段 */
#define ZIP_ENTRY_ENCODING(ptr, encoding) do { \(encoding) ((ptr)[0]); \if ((encoding) ZIP_STR_MASK) (encoding) ZIP_STR_MASK; \
} while(0)/*
* 解码ptr中的条目编码类型和数据长度字符串长度为字符串整数条目使用的字节数。
* encoding变量为输入参数调用者提取lensize变量将保存用于编码条目长度的字节数
* len变量将保存条目长度。在无效编码错误的情况下lensize被设置为0。
*/
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \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) ((uint32_t)(ptr)[1] 24) | \((uint32_t)(ptr)[2] 16) | \((uint32_t)(ptr)[3] 8) | \((uint32_t)(ptr)[4]); \} else { \(lensize) 0; /* 编码错误应该在之前的代码中被覆盖 */ \(len) 0; /* ZIP_ASSERT_ENCODING / zipEncodingLenSize或者 */ \/* 在此宏之后将lensize与0匹配 */ \} \} else { \(lensize) 1; \if ((encoding) ZIP_INT_8B) (len) 1; \else if ((encoding) ZIP_INT_16B) (len) 2; \else if ((encoding) ZIP_INT_24B) (len) 3; \else if ((encoding) ZIP_INT_32B) (len) 4; \else if ((encoding) ZIP_INT_64B) (len) 8; \else if (encoding ZIP_INT_IMM_MIN encoding ZIP_INT_IMM_MAX) \(len) 0; /* 4位立即值 */ \else \(lensize) (len) 0; /* 编码错误 */ \} \
} while(0)
字节数组只根据ptr[0]的前2个比特即可判断类型而判断整数类型需要ptr[0]的前4个比特代码如下。
/*
* 返回由encoding编码的整数所需的字节数
*/
static inline 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;}if (encoding ZIP_INT_IMM_MIN encoding ZIP_INT_IMM_MAX)return 0; /* 4位立即值 *//* 编码错误通过之前的ZIP_ASSERT_ENCODING调用已覆盖 */redis_unreachable();return 0;
}
基本操作
本节主要介绍压缩列表的基本操作包括创建压缩列表、插入元素、删除元素及遍历压缩列表让读者从源码层次进一步理解压缩列表。
创建压缩列表
创建压缩列表的API定义如下函数无输入参数返回参数为压缩列表首地址。
unsigned char *ziplistNew(void);
创建空的压缩列表只需要分配初始存储空间11(4421)个字节并对zlbytes、zltail、zllen和zlend字段初始化即可。
/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {//ZIPLIST_HEADER_SIZE zlbytes zltail zllen;unsigned int bytes ZIPLIST_HEADER_SIZEZIPLIST_END_SIZE;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; //结尾标识0XFFreturn zl;
}
插入元素
压缩列表插入元素的API定义如下函数输入参数zl表示压缩列表首地址p指向元素插入位置s表示数据内容slen表示数据长度返回参数为压缩列表首地址。
/*
* 在指定位置 p 插入一个键值对。
*
* 参数:
* - zl: 待操作的 ziplist。
* - p: 待插入的位置。
* - s: 键值对的键。
* - slen: 键值对的键的长度。
*
* 返回值:
* - 插入后的 ziplist。
*/
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {return __ziplistInsert(zl,p,s,slen);
}/* * 在指定位置插入项目。* * param zl 待插入的ziplist* param p 插入位置的指针* param s 待插入的字符串* param slen 待插入字符串的长度* return 更新后的ziplist*/
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {size_t curlen intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen, newlen;unsigned int prevlensize, prevlen 0;size_t offset;int nextdiff 0;unsigned char encoding 0;long long value 123456789; /* 初始化为避免警告。使用一个易于看到的值如果由于某种原因未初始化则使用。 */zlentry tail;/* 确定要插入的条目的前一条记录的长度。 */if (p[0] ! ZIP_END) {ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);} else {unsigned char *ptail ZIPLIST_ENTRY_TAIL(zl);if (ptail[0] ! ZIP_END) {prevlen zipRawEntryLengthSafe(zl, curlen, ptail);}}/* 查看是否可以对条目进行编码 */if (zipTryEncoding(s,slen,value,encoding)) {/* 将encoding设置为相应的整数编码 */reqlen zipIntSize(encoding);} else {/* encoding不变但是zipStoreEntryEncoding将使用字符串长度来确定如何编码。 */reqlen slen;}/* 我们需要为之前的记录长度和有效负载长度腾出空间。 */reqlen zipStorePrevEntryLength(NULL,prevlen);reqlen zipStoreEntryEncoding(NULL,encoding,slen);/* 如果插入位置不等于尾部则需要确保下一个条目的prevlen字段可以容纳此条目的长度。 */int forcelarge 0;nextdiff (p[0] ! ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;if (nextdiff -4 reqlen 4) {nextdiff 0;forcelarge 1;}/* 存储realloc可能改变ziplist地址的情况下的地址。 */offset p-zl;newlen curlenreqlennextdiff;zl ziplistResize(zl,newlen);p zloffset;/* 应用必要的内存移动并更新尾部偏移量。 */if (p[0] ! ZIP_END) {/* 减少一个是由于ZIP_END字节 */memmove(preqlen,p-nextdiff,curlen-offset-1nextdiff);/* 在下一个条目中编码此条目的raw长度。 */if (forcelarge)zipStorePrevEntryLengthLarge(preqlen,reqlen);elsezipStorePrevEntryLength(preqlen,reqlen);/* 更新尾部偏移量。 */ZIPLIST_TAIL_OFFSET(zl) intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))reqlen);/* 当尾部包含多于一个条目时我们还需要考虑nextdiff。否则prevlen大小的变化对尾部偏移量没有影响。 */assert(zipEntrySafe(zl, newlen, preqlen, tail, 1));if (p[reqlentail.headersizetail.len] ! ZIP_END) {ZIPLIST_TAIL_OFFSET(zl) intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))nextdiff);}} else {/* 这个元素将是新的尾部。 */ZIPLIST_TAIL_OFFSET(zl) intrev32ifbe(p-zl);}/* 当nextdiff不为0时下一个条目的原始长度发生变化因此需要在ziplist中进行更新。 */if (nextdiff ! 0) {offset p-zl;zl __ziplistCascadeUpdate(zl,preqlen);p zloffset;}/* 写入条目 */p zipStorePrevEntryLength(p,prevlen);p zipStoreEntryEncoding(p,encoding,slen);if (ZIP_IS_STR(encoding)) {memcpy(p,s,slen);} else {zipSaveInteger(p,value,encoding);}ZIPLIST_INCR_LENGTH(zl,1);return zl;
}
插入元素可以简要分为3个步骤① 将元素内容编码② 重新分配空间③ 复制数据。下面分别讲解每个步骤的实现逻辑。
1编码
编码即计算previous_entry_length字段、encoding字段和content字段的内容。那么如何获取前一个元素的长度呢此时就需要根据元素的插入位置分情况讨论。插入元素位置示意如下所示 1当压缩列表为空、插入位置为P0时不存在前一个元素即前一个元素的长度为0。
2当插入位置为P1时需要获取entryX元素的长度而entryX1元素的previous_entry_length字段存储的就是entryX元素的长度比较容易获取。
3当插入位置为P2时需要获取entryN元素的长度entryN是压缩列表的尾元素计算元素长度时需要将其3个字段长度相加函数实现如下。
/*
* 返回由指针 p 指向的条目使用的总字节数。 */
static inline unsigned int zipRawEntryLengthSafe(unsigned char* zl, size_t zlbytes, unsigned char *p) {zlentry e;assert(zipEntrySafe(zl, zlbytes, p, e, 0));return e.headersize e.len;
}/*** 将结构体填充为关于条目的所有信息。** 这个函数是安全使用的即使是指向不受信任的指针也能确保不会尝试访问ziplist负载外部的内存。* 返回1表示条目是有效的返回0表示否则。*/
static inline int zipEntrySafe(unsigned char* zl, size_t zlbytes, unsigned char *p, zlentry *e, int validate_prevlen) {unsigned char *zlfirst zl ZIPLIST_HEADER_SIZE;unsigned char *zllast zl zlbytes - ZIPLIST_END_SIZE;
#define OUT_OF_RANGE(p) (unlikely((p) zlfirst || (p) zllast))/* 如果头部不可能超出ziplist范围那么走快速路径。最大lensize和prevrawlensize均为5字节 */if (p zlfirst p 10 zllast) {ZIP_DECODE_PREVLEN(p, e-prevrawlensize, e-prevrawlen);ZIP_ENTRY_ENCODING(p e-prevrawlensize, e-encoding);ZIP_DECODE_LENGTH(p e-prevrawlensize, e-encoding, e-lensize, e-len);e-headersize e-prevrawlensize e-lensize;e-p p;/* 我们没有调用ZIP_ASSERT_ENCODING所以检查lensize是否被设置为0。 */if (unlikely(e-lensize 0))return 0;/* 确保条目不会超出ziplist边缘 */if (OUT_OF_RANGE(p e-headersize e-len))return 0;/* 如果需要验证prevlen则确保prevlen不会超出ziplist边缘 */if (validate_prevlen OUT_OF_RANGE(p - e-prevrawlen))return 0;return 1;}/* 确保指针不会超出ziplist的边缘 */if (OUT_OF_RANGE(p))return 0;/* 确保编码的prevlen头部不会超出分配范围 */ZIP_DECODE_PREVLENSIZE(p, e-prevrawlensize);if (OUT_OF_RANGE(p e-prevrawlensize))return 0;/* 确保编码的条目头是有效的。 */ZIP_ENTRY_ENCODING(p e-prevrawlensize, e-encoding);e-lensize zipEncodingLenSize(e-encoding);if (unlikely(e-lensize ZIP_ENCODING_SIZE_INVALID))return 0;/* 确保编码的条目头不会超出分配范围 */if (OUT_OF_RANGE(p e-prevrawlensize e-lensize))return 0;/* 解码prevlen和条目长度头。 */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;/* 确保条目不会超出ziplist边缘 */if (OUT_OF_RANGE(p e-headersize e-len))return 0;/* 如果需要验证prevlen则确保prevlen不会超出ziplist边缘 */if (validate_prevlen OUT_OF_RANGE(p - e-prevrawlen))return 0;e-p p;return 1;
#undef OUT_OF_RANGE
}
encoding字段标识的是当前元素存储的数据类型和数据长度。编码时首先尝试将数据内容解析为整数如果解析成功则按照压缩列表整数类型编码存储如果解析失败则按照压缩列表字节数组类型编码存储。 /* 查看是否可以对条目进行编码 */if (zipTryEncoding(s,slen,value,encoding)) {/* 将encoding设置为相应的整数编码 */reqlen zipIntSize(encoding);} else {/* encoding不变但是zipStoreEntryEncoding将使用字符串长度来确定如何编码。 */reqlen slen;}/* 我们需要为之前的记录长度和有效负载长度腾出空间。 */reqlen zipStorePrevEntryLength(NULL,prevlen);reqlen zipStoreEntryEncoding(NULL,encoding,slen);
上述程序尝试按照整数解析新添加元素的数据内容数值存储在变量value中编码存储在变量encoding中。如果解析成功还需要计算整数所占字节数。变量reqlen最终存储的是当前元素所需空间大小初始赋值为元素content字段所需空间大小再累加previous_entry_length和encoding字段所需空间大小。
重新分配空间
由于新插入了元素压缩列表所需空间增大因此需要重新分配存储空间。那么空间大小是不是添加元素前的压缩列表长度与新添加元素长度之和呢并不完全是。压缩列表长度变化示意如下图所示。 插入元素前entryX元素的长度为128字节entryX1元素的previous_entry_length字段占1个字节添加元素entryNEW元素长度为1024字节此时entryX1元素的previous_entry_length字段需要占5个字节即压缩列表的长度不仅增加了1024个字节还要加上entryX1元素扩展的4个字节。而entryX1元素的长度可能增加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, curlenreqlennextdiff);//重新偏移到插入位置Pp zloffset;
nextdiff与forcelarge在这里有什么用呢分析ziplistResize函数的第二个参数curlen表示插入元素前压缩列表的长度reqlen表示新插入元素的长度而nextdiff表示entryX1元素长度的变化取值可能为0长度不变、4长度增加4或-4长度减少4。我们再思考下当nextdiff4而reqlen4时会发生什么呢没错插入元素导致压缩列表所需空间减小了即函数ziplistResize内部调用realloc重新分配的空间小于指针zl指向的空间。我们知道realloc重新分配空间时返回的地址可能不变当前位置有足够的内存空间可供分配当重新分配的空间减小时realloc可能会将多余的空间回收导致数据丢失。因此需要避免这种情况的发生即重新赋值nextdiff0同时使用forcelarge标记这种情况。
那么nextdiff-4时reqlen会小于4吗nextdiff-4说明插入元素之前entryX1元素的previous_entry_length字段的长度是5字节即entryX元素的总长度大于或等于254字节所以entryNEW元素的previous_entry_length字段同样需要5个字节即entryNEW元素的总长度肯定是大于5个字节的reqlen又怎么会小于4呢正常情况下是不会出现这种情况的但是由于存在连锁更新将在4.4节介绍可能会出现nextdiff-4但entryX元素的总长度小于254字节的情况此时reqlen可能会小于4。
数据复制
重新分配空间之后需要将位置P后的元素移动到指定位置将新元素插入到位置P。我们假设entryX1元素的长度增加4即nextdiff4此时压缩列表数据复制示意如下图所示。 从上图中可以看到位置P后的所有元素都需要移动移动的偏移量是待插入元素entryNEW的长度移动的数据块长度是位置P后所有元素的长度之和加上nextdiff的值数据移动之后还需要更新entryX1元素的previous_entry_length字段。
/* 应用必要的内存移动并更新尾部偏移量。 */if (p[0] ! ZIP_END) {//为什么减1呢zlend结束表示恒为0xFF不需要移动memmove(preqlen,p-nextdiff,curlen-offset-1nextdiff);//更新entryX1元素的previous_entry_length字段if (forcelarge)//entryX1元素的previous_entry_length字段依然占5个字节//但是entryNEW元素的长度小于4字节zipStorePrevEntryLengthLarge(preqlen,reqlen);elsezipStorePrevEntryLength(preqlen,reqlen);//更新zltail字段ZIPLIST_TAIL_OFFSET(zl) intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))reqlen);/* 当尾部包含多于一个条目时我们还需要考虑nextdiff。否则prevlen大小的变化对尾部偏移量没有影响。 */assert(zipEntrySafe(zl, newlen, preqlen, tail, 1));if (p[reqlentail.headersizetail.len] ! ZIP_END) {ZIPLIST_TAIL_OFFSET(zl) intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))nextdiff);}} else {/* 这个元素将是新的尾部。 */ZIPLIST_TAIL_OFFSET(zl) intrev32ifbe(p-zl);}
第一次更新尾元素偏移量之后为什么指向的元素可能不是尾元素呢因为当entryX1元素就是尾元素时只需要更新一次尾元素的偏移量但是当entryX1元素不是尾元素且entryX1元素的长度发生了改变时尾元素偏移量还需要加上nextdiff的值。
删除元素
压缩列表删除元素的API定义如下函数输入参数zl指向压缩列表首地址*p指向待删除元素的首地址参数p同时可以作为输出参数返回参数为压缩列表首地址。
/* 删除指针 *p指向的ziplist中的单个条目。* 同时在place中更新*p以便能够迭代ziplist同时删除条目。 */
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {size_t offset *p-zl;zl __ziplistDelete(zl,*p,1);/* 将当前元素的指针存储在p中因为ziplistDelete会进行realloc可能会导致不同的zl指针。* 当删除方向为从后往前时可能会删除最后一个条目并导致p指向ZIP_END因此需要检查这一点。 */*p zloffset;return zl;
}
ziplistDelete函数只是简单调用底层_ziplistDelete函数实现删除功能。_ziplistDelete函数可以同时删除多个元素输入参数p指向的是首个待删除元素的地址num表示待删除元素数目。
/* Delete num entries, starting at p. Returns pointer to the ziplist. */
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {unsigned int i, totlen, deleted 0; // 定义变量i, totlen, deleted并初始化size_t offset; // 定义变量offsetint nextdiff 0; // 定义变量nextdiff并初始化zlentry first, tail; // 定义变量first和tailsize_t zlbytes intrev32ifbe(ZIPLIST_BYTES(zl)); // 获取ziplist的大小并赋值给zlbyteszipEntry(p, first); // 获取p所在entry的信息并赋值给firstfor (i 0; p[0] ! ZIP_END i num; i) { // 循环删除entryp zipRawEntryLengthSafe(zl, zlbytes, p); // 移动到下一个待删除的entrydeleted; // 删除的entry数量加1}assert(p first.p); // 断言p大于等于first的起始位置totlen p-first.p; // 计算待删除的entry总长度if (totlen 0) { // 如果删除的entry总长度大于0uint32_t set_tail; // 定义变量set_tailif (p[0] ! ZIP_END) { // 如果下一个entry不是ZIP_ENDnextdiff zipPrevLenByteDiff(p,first.prevrawlen); // 计算prevlen字节大小的变化量p - nextdiff; // 移动到上一个entry的位置assert(p first.p pzlzlbytes-1); // 断言p在正确的位置上zipStorePrevEntryLength(p,first.prevrawlen); // 在上一个entry中存储prevlen的长度set_tail intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen; // 计算更新后的tail偏移量if (p[tail.headersizetail.len] ! ZIP_END) {set_tail nextdiff; // 如果下一个entry的长度发生了变化更新tail偏移量}size_t bytes_to_move zlbytes-(p-zl)-1; // 计算需要移动的字节数memmove(first.p,p,bytes_to_move); // 将内存中的数据向前移动} else {set_tail (first.p-zl)-first.prevrawlen; // 尾部已经被删除不需要移动内存}zlbytes - totlen - nextdiff; // 更新ziplist的剩余大小zl ziplistResize(zl, zlbytes); // 调整ziplist的大小p zloffset; // 更新p的位置ZIPLIST_INCR_LENGTH(zl,-deleted); // 更新ziplist中的记录数assert(set_tail zlbytes - ZIPLIST_END_SIZE); // 断言tail偏移量在有效范围内ZIPLIST_TAIL_OFFSET(zl) intrev32ifbe(set_tail); // 更新tail偏移量if (nextdiff ! 0) {zl __ziplistCascadeUpdate(zl,p); // 如果nextdiff不等于0递归更新下一个entry的长度}}return zl; // 返回ziplist的指针
}
删除元素同样可以简要分为三个步骤① 计算待删除元素的总长度② 数据复制③ 重新分配空间。下面分别讨论每个步骤的实现逻辑。
1计算待删除元素的总长度。 //解码第一个待删除元素zipEntry(p, first);//遍历所有待删除元素同时指针p向后偏移for (i 0; p[0] ! ZIP_END i num; i) {p zipRawEntryLength(p);deleted;}//totlen即为待删除元素总长度totlen p-first.p;
2数据复制。第1步完成之后指针first与指针p之间的元素都是待删除的。当指针p恰好指向zlend字段时不再需要复制数据只需要更新尾节点的偏移量即可。下面分析另一种情况即指针p指向的是某一个元素而不是zlend字段。
删除元素时压缩列表所需空间减小减小的量是否仅为待删除元素的总长度呢答案同样是否定的。举个简单的例子下图是经过第1步之后的压缩列表示意。 删除元素entryX1到元素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);//更新zltailZIPLIST_TAIL_OFFSET(zl) intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);zipEntry(p, tail);if (p[tail.headersizetail.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);
与之前更新zltail字段的操作相同当entryN元素就是尾元素时只需要更新一次尾元素的偏移量但是当entryN元素不是尾元素且entryN元素的长度发生了改变时尾元素偏移量还需要加上nextdiff的值。
3重新分配空间。 offset first.p-zl;zl ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlennextdiff);p zloffset;ZIPLIST_INCR_LENGTH(zl, -deleted);
调用ziplistResize函数重新分配空间时如果重新分配的空间小于指针zl指向的空间时可能会出现问题。而删除元素时压缩列表的长度肯定是减小的。因为删除元素时先复制数据再重新分配空间即调用ziplistResize函数时多余的那部分空间存储的数据已经被复制了此时回收这部分空间并不会造成数据丢失。
遍历压缩列表
遍历就是从头到尾后向遍历或者从尾到头前向遍历访问压缩列表中的每个元素。压缩列表的遍历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函数实现如下。
/* 返回ziplist中的下一个元素的指针。** zl是ziplist的指针* p是当前元素的指针** 返回下一个元素的指针如果没有下一个元素则返回NULL。 */
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {((void) zl);size_t zlbytes intrev32ifbe(ZIPLIST_BYTES(zl));/* p可能等于ZIP_END这是由ziplistDelete引起的此时应该返回NULL。* 否则当下一个元素是ZIP_END时即没有下一个元素应该返回NULL。 */if (p[0] ZIP_END) {return NULL;}p zipRawEntryLength(p);if (p[0] ZIP_END) {return NULL;}zipAssertValidEntry(zl, zlbytes, p);return p;
}
