写在前面
以下内容是基于Redis 6.2.6 版本整理总结
一、压缩列表（ziplist）
当一个哈希键只包含少量键值对，并且每个键值对的键和值要么是小整数，要么是短字符串，Redis就会采用压缩列表作为哈希键的底层实现。
1.1 压缩列表的构成
压缩列表是Redis为节约内存而开发的，是由一系列特殊编码的连续内存组成。一个压缩列表可以包含任意多个节点，每个节点可以保存一个小整数或者一个短的字符串。
ziplist 的结构如下：
各字段说明：
- zlbytes（4 字节）： ziplist占用总的字节数
- zltail（4 字节）: ziplist 最后一个 entry 距离起始位置偏移的字节数
- zllen（2 字节）: ziplist 中 entry 的个数
- zlend（1 字节）：结束符（ziplist 以0xFF作为结束）
举个栗子：
说明：ziplist 的总长度为96字节（0x60的十进制），最后一个entry距离ziplist起始位置偏移了75字节（0x4B的十进制），ziplist中此时有3（0x03的十进制）个entry。
entry的结构如下:
各字段说明：
pre_entry_len：上一个entry的长度。占用的字节数取决于上一个节点的长度，如果上一个节点的长度小于254字节，pre_entry_len就占1个字节；如果大于等于254，pre_entry_len就占5个字节，而且，第一个字节会被设置为0xFE（十进制的254）。
encoding：记录该节点content属性保存数据的类型及长度。开头说了 ziplist 用来存储小整数或者短的字符串。encoding规则如下：
存储字符串：
encoding的长度有1字节、2字节、和5字节：主要根据高位的00/01/10来区分不同的编码。
存储小整数：
1.2 ziplist源码分析
1.2.1 创建ziplist
redis用ziplistNew() 函数来创建ziplist。采用zmalloc分配空间，初始化ziplist的 header 和 end，共 11 个字节。
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t)) #define ZIPLIST_END_SIZE (sizeof(uint8_t)) /* Create a new empty ziplist. */ unsigned char *ziplistNew(void) { // bytes = 4 + 4 + 2 + 1 = 11 字节 unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE; unsigned char *zl = zmalloc(bytes); // 初始化 zlbytes = 11 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); // 初始化 zltail = 10，此时还没有entry ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); // 初始化 zllen = 10 ZIPLIST_LENGTH(zl) = 0; // 初始化 zlend = 255 zl[bytes-1] = ZIP_END; return zl; }
1.2.2 ziplist的插入
__ziplistInsert() 函数，将新节点查到给定节点之后。
/* Insert item at "p". */ 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; /* initialized to avoid warning. Using a value that is easy to see if for some reason we use it uninitialized. */ zlentry tail; /* Find out prevlen for the entry that is inserted. */ 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); } } /* See if the entry can be encoded */ if (zipTryEncoding(s,slen,&value,&encoding)) { /* 'encoding' is set to the appropriate integer encoding */ reqlen = zipIntSize(encoding); } else { /* 'encoding' is untouched, however zipStoreEntryEncoding 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. */ reqlen += zipStorePrevEntryLength(NULL,prevlen); reqlen += zipStoreEntryEncoding(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. */ int forcelarge = 0; nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0; if (nextdiff == -4 && reqlen < 4) { nextdiff = 0; forcelarge = 1; } /* Store offset because a realloc may change the address of zl. */ offset = p-zl; newlen = curlen+reqlen+nextdiff; zl = ziplistResize(zl,newlen); 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 */ memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); /* Encode this entry's raw length in the next entry. */ if (forcelarge) zipStorePrevEntryLengthLarge(p+reqlen,reqlen); else zipStorePrevEntryLength(p+reqlen,reqlen); /* Update offset for tail */ 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. */ assert(zipEntrySafe(zl, newlen, p+reqlen, &tail, 1)); 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_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; zl = __ziplistCascadeUpdate(zl,p+reqlen); p = zl+offset; } /* Write the entry */ 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; }
二、总结
- ziplist是Redis为了节约内存而实现的一种顺序型数据结构
- 压缩列表中的节点用来存储较短的字符串或小整数
- 添加和删除节点可能会引发连锁更新，但这种概率很低
