【Redis 源碼】ziplist 壓縮表
前言：
壓縮表是一個連續內存空間的線性結構，元素之間緊挨着存儲，沒有任何空隙。redis 爲了節省空間，當使用 zset 和 hash 容器對象時再元素個數較少時採取了壓縮表（ziplist）進行存儲。
- 壓縮表結構介紹
壓縮表構成如下：
zlbytes :
壓縮表字節長度，類型 uint32_t 佔用 4 個字節，需要存儲此值才能調整整個結構的大小。壓縮表的大小爲 2^32 - 1。
zltail:
是列表中最後一個條目的偏移量, 類型 uint32_t 佔用 4 個字節。
zllen：
壓縮表個數，類型 uint16_t 佔用 2 個字節，個數最大數量爲 2^16-1，也就是 65535。必須遍歷整個壓縮表才能知道它的個數。
entry:
壓縮表存儲元素，可以是字節數組或者是整數。
zlend:
結束標識，類型 uint8_t 佔用 1 個字節。該值爲 255，對應 ZIP_END 宏, 16 進製爲 0xFF。
壓縮表各字段間的獲取宏如下，ziplist.c 中：
//ziplist的zlbytes字段
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
//ziplist的zltail字段
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
//ziplist的zllen字段
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
//最後一個字節，對應zlend字段
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
//ziplist頭大小10字節
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//尾大小1字節
#define ZIPLIST_END_SIZE (sizeof(uint8_t))
//ziplist數據頭入口也就是第一個entry結構位置
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
//ziplist數據最後一個entry入口,最後一個entry結構位置
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))- 壓縮表 entry 介紹
prevlen：
壓縮表中前一個 entry 的長度，佔用 1 個或者 5 個字節。
1）若前一個 entry 佔用的字節數小於 254，則 prevlen 字段佔 1 個字節。
2）若前一個 entry 佔用字節數大於或等於 254，則 prevlen 字段佔用 5 個字節。注意此時第一個字節固定爲 254，即 0xFE，另外 4 個字節以 uint32_t 存儲值。
encoding：
entry 的編碼，表示當前 entry 存儲數據的類型和數據的長度。
字符串編碼規則如下：
整型編碼規則如下：
entry-data：
數據存儲的值。大小由 encode
對應的編碼宏如下, ziplist.c 中：
#define ZIP_STR_MASK 0xc0
#define ZIP_INT_MASK 0x30
#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根據以上內容，咱們可以看一下如下 hash 命令的 ziplist 存儲結構
127.0.0.1:6379> hmset name5 a zhaoyu b hello
看上面兩張圖，解析 name5 點 hash 數據存儲結構。zl 爲 ziplist 的字節數組。
- 0 ～ 9 的 10 個字節對應 zlbytes、zltail、zllen 三個字段。
- 然後從 zl[10] 開始，zl[10] 等於 prevlen 字段當前是 0。因爲 zl[10] 是第一個 entry 沒有之前所以爲 0。然後 zl[11] 等於十六進制 0x1，在二進制下是 0000 0001，開頭兩位是 00 說明對應 1 字節的字符數組。其次就是佔用一個字節，所以我們 zl[12] 得到 a 鍵。也就是我們命令行中的 hmset name5 a 中的 a。
- 從 zl[13] 對應 prevlen 字段，當前是 0x3。說明前一個 entry 是 3 個字節。確實是 zl[10] ~zl[12] 三個字節。然後 zl[14] 等於十六進制 0x6，說明是 6 個字節的的字符數組。剛好得到 zhaoyu 6 個字符。
4）zl[31] 當前等於 10 進制 255 對應 0xFF。也就是結尾。
zlentry 結構體，ziplist.c 中：
typedef struct zlentry {
unsigned int prevrawlensize; /* 前一個元素的內存大小的編碼空間 */
unsigned int prevrawlen; /* 前一個元素的內存大小. */
unsigned int lensize; /* 當前元素value部分佔用內存大小的編碼空間 */
unsigned int len; /* 當前元素value部分佔用內存大小 */
unsigned int headersize; /* 當前元素value部分佔用內存大小 */
unsigned char encoding; /* 編碼類型，標誌value的類型和佔用的字節數. */
unsigned char *p; /* 內容 */
} zlentry;zlentry 並不是實際的 zl 中存儲的，只是用作解析 entry 計算使用的結構體。
解碼 entry 函數，ziplist.c 中：
void zipEntry(unsigned char *p, zlentry *e) {
ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen); //解碼prevlen字段
ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len); //解碼encoding長度
e->headersize = e->prevrawlensize + e->lensize;
e->p = p;
}解碼 prevlen 字段宏，ziplist.c 中：
#define ZIP_BIG_PREVLEN 254
#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \
ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \
if ((prevlensize) == 1) { \
(prevlen) = (ptr)[0]; \
} else if ((prevlensize) == 5) { \
assert(sizeof((prevlensize)) == 4); \
memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \
memrev32ifbe(&prevlen); \
} \
} while(0);
#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \
if ((ptr)[0] < ZIP_BIG_PREVLEN) { \
(prevlensize) = 1; \
} else { \
(prevlensize) = 5; \
} \
} while(0);該宏其實是解碼 prevrawlensize 字段，是 1 個字節還是 5 個字節空間。
解碼的長度宏如下 ziplist.c 中：
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \
ZIP_ENTRY_ENCODING((ptr), (encoding)); \
if ((encoding) < ZIP_STR_MASK) { //判斷是否爲字節數組 \
if ((encoding) == ZIP_STR_06B) { //63字節的字節數組 \
(lensize) = 1; \
(len) = (ptr)[0] & 0x3f; \
} else if ((encoding) == ZIP_STR_14B) { //16383字節內的字節數組 \
(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);獲得 zip 的整型大小，可以看一下整型編碼規則表，代碼 ziplist.c 中：
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 bit immediate */
panic("Invalid integer encoding 0x%02X", encoding);
return 0;
}- 壓縮表 ziplist 的 API 說明
總結
1）ziplist 在 zset 和 hash 中使用到，元素個數較少時用到。
2）壓縮表是一個字節數組，比較緊湊的結構。
3）壓縮表可以存儲存儲多個節點，也就是 entry。每個節點可以存儲字節數組和整型兩種數據。
4）壓縮表支持最大個數 65535 個。
5）壓縮表插入和刪除可能會引起連鎖更新。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ENj32humItpiVVS7kVWh0Q