Redis ziplist內部結構分析
來源：nosqlfan
pesiwang
摘要： 本文來自對Redis內部ziplist結構的內部實現進行了詳細深入的分析，ziplist是用一個字符串來實現的雙向鏈表結構。
Abstract：
Key words :
ziplist是用一個字符串來實現的雙向鏈表結構，顧名思義，使用ziplist可以減少雙向鏈表的存儲空間，主要是節省了鏈表指針的存儲，如果存儲指向上一個鏈表結點和指向下一個鏈表結點的指針需要8個字節，而轉化成存儲上一個結點長度和當前結點長度在大多數情況下可以節省很多空間(最好的情況下只需2個字節)。但是每次向鏈表增加元素都需要重新分配內存。
ziplist中的結構體
typedef struct zlentry {
unsigned int prevrawlensize, prevrawlen;
unsigned int lensize, len;
unsigned int headersize;
unsigned char encoding;
unsigned char *p;
} zlentry;
Prevrawlen：上個鏈表結點占用的長度
Prevrawlensize：上個鏈表結點長度的存儲占用的字節數
Len：當前鏈表結點占用的長度
Lensize：當前鏈表結點長度的存儲占用的字節數
Headersize：當前鏈表結點的頭部大小， headersize = prevrawlensize + lensize
Encoding：當前鏈表結點長度(即字段len)使用的編碼類型
P：指向當前結點起始位置的指針
Ziplist的存儲結構
鏈表存儲結構
Zlbytes：一個4字節的無符號整型，存儲的是整個ziplist占用的字節數，用于重分配內存時使用。
Zltail：一個4字節的無符號整型，存儲的是鏈表最后一個結點的偏移值，即鏈表開頭地址+zltail即為最后一個結點的起始地址
Zllen：一個2字節的無符號整型，存儲的是鏈表中存儲的結點數，當這個值存儲的是2字節無符號整型的最大值時，需要遍歷鏈表獲取鏈表的結點數
Entry：鏈表結點，鏈表結點的存儲格式見結點存儲結構
Zlend：占用1字節的鏈表的結尾符，值為255
相關的宏定義
Ziplist.c: 89
/* Utility macros */
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+ZIPLIST_TAIL_OFFSET(zl))
#define ZIPLIST_ENTRY_END(zl) ((zl)+ZIPLIST_BYTES(zl)-1)
結點存儲結構
<上一個鏈表結點占用的長度><當前鏈表結點占用的長度><當前結點數據>
上一個鏈表結點占用的長度
上一個鏈表結點占用的長度占用的字節數根據編碼類型而定
當長度數據小于254使用一個字節存儲，該字節存儲的數值就是該長度，
當長度數據大于等于254時，使用5個字節存儲，第一個字節的數值為254，表示接下來的4個字節才真正表示長度
當前鏈表結點用的長度存儲和數據存儲
第一個字節的前兩位用于區分長度存儲編碼類型和數據編碼類型，具體如下
字符串類型編碼
|00pppppp|
長度小于等于63(2^6-1)字節的字符串，后6位用于存儲字符串長度，長度與類型總共占用了1個字節
|01pppppp|qqqqqqqq|
長度小于等于16383(2^14-1)字節的字符串，后14位用于存儲字符串長度，長度與類型總共占用了2個字節
|10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|
長度大于等于16384字節的字符串，后4個字節用于存儲字符串長度，長度與類型總共占用了5個字節
整型編碼
|1100____|
整型類型，后2個字節存儲的值就是該整數
|1101____|
整型類型，后4個字節存儲的值就是該整數
|1110____|
整型類型，后8個字節存儲的值就是該整數
相關的宏定義
Ziplist.c：77
/* Different encoding/length possibilities */
#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)
/* Macro's to determine type */
#define ZIP_IS_STR(enc) (((enc) & 0xc0) < 0xc0)
#define ZIP_IS_INT(enc) (!ZIP_IS_STR(enc) && ((enc) & 0x30) < 0x30)
ziplist提供的接口
unsigned char *ziplistNew(void);
創建一個ziplist
返回創建的ziplist的指針
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where);
在ziplist的尾端或頭部添加一個結點
zl是ziplist的指針
s是待添加結點的值
slen是待添加結點的值長度
返回最新的ziplist的指針
unsigned char *ziplistIndex(unsigned char *zl, int index);
根據索引獲取ziplist的結點，封裝類似數組接口
zl是ziplist的指針
index是索引，從0開始，0即取鏈表的第一個結點，index可以是負數，負數表從后往前算，-1就是取鏈表的最后一個元素
如果index處有結點，則返回指向改結點的指針，否則返回NULL
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);
獲取ziplist的下一個結點
zl是無用參數
p是當前結點指針
如果還有下一個結點，則返回下一個結點的指針，否則返回NULL
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);
獲取ziplist的上一個結點
zl是ziplist的指針
p是當前結點指針
如果還有上一個結點，則返回上一個結點的指針，否則返回NULL
unsigned int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, long long *lval);
獲取p指向的當前結點的值
p是指向當前結點的指針
sval保存獲取到的當前結點的值的指針
slen是獲取到的當前結點的值的長度
lval是當值是整型時保存返回的數值
如果p指向的結點是合法結點返回1，否則返回0
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);
在指針p指向的位置插入一個結點
zl是ziplist的指針
p是待插入結點的位置
s是待插入結點的值
slen是待插入結點的值的長度
返回最新的ziplist的指針
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);
刪掉*p指向的結點
zl是ziplist的指針
p是一個value-result參數，傳入需刪除的結點，返回被刪除結點下一個結點的指針
返回最新的ziplist的指針
unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num);
刪除連續的一批結點
zl是ziplist的指針
index是開始刪除的索引
num是刪除的個數
返回最新的ziplist的指針
unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen);
p指向的結點的值和s對應的值做比較
p是ziplist結點的指針
s是呆比較的值
slen是s的長度
相等返回1，否則返回0
unsigned int ziplistLen(unsigned char *zl);
取ziplist鏈表中元素的個數
zl是ziplist的指針
返回ziplist鏈表中元素的個數
size_t ziplistBlobLen(unsigned char *zl);
取ziplist鏈表占用的字節數
zl是ziplist的指針
返回ziplist鏈表占用的字節數
此內容為AET網站原創，未經授權禁止轉載。