Redis ziplist內(nèi)部結(jié)構(gòu)分析
來(lái)源：nosqlfan
pesiwang
摘要： 本文來(lái)自對(duì)Redis內(nèi)部ziplist結(jié)構(gòu)的內(nèi)部實(shí)現(xiàn)進(jìn)行了詳細(xì)深入的分析，ziplist是用一個(gè)字符串來(lái)實(shí)現(xiàn)的雙向鏈表結(jié)構(gòu)。
Abstract：
Key words :
ziplist是用一個(gè)字符串來(lái)實(shí)現(xiàn)的雙向鏈表結(jié)構(gòu),，顧名思義,，使用ziplist可以減少雙向鏈表的存儲(chǔ)空間，主要是節(jié)省了鏈表指針的存儲(chǔ),，如果存儲(chǔ)指向上一個(gè)鏈表結(jié)點(diǎn)和指向下一個(gè)鏈表結(jié)點(diǎn)的指針需要8個(gè)字節(jié),，而轉(zhuǎn)化成存儲(chǔ)上一個(gè)結(jié)點(diǎn)長(zhǎng)度和當(dāng)前結(jié)點(diǎn)長(zhǎng)度在大多數(shù)情況下可以節(jié)省很多空間(最好的情況下只需2個(gè)字節(jié))。但是每次向鏈表增加元素都需要重新分配內(nèi)存,。
ziplist中的結(jié)構(gòu)體
typedef struct zlentry {
unsigned int prevrawlensize, prevrawlen;
unsigned int lensize, len;
unsigned int headersize;
unsigned char encoding;
unsigned char *p;
} zlentry;
Prevrawlen：上個(gè)鏈表結(jié)點(diǎn)占用的長(zhǎng)度
Prevrawlensize：上個(gè)鏈表結(jié)點(diǎn)長(zhǎng)度的存儲(chǔ)占用的字節(jié)數(shù)
Len：當(dāng)前鏈表結(jié)點(diǎn)占用的長(zhǎng)度
Lensize：當(dāng)前鏈表結(jié)點(diǎn)長(zhǎng)度的存儲(chǔ)占用的字節(jié)數(shù)
Headersize：當(dāng)前鏈表結(jié)點(diǎn)的頭部大小,， headersize = prevrawlensize + lensize
Encoding：當(dāng)前鏈表結(jié)點(diǎn)長(zhǎng)度(即字段len)使用的編碼類(lèi)型
P：指向當(dāng)前結(jié)點(diǎn)起始位置的指針
Ziplist的存儲(chǔ)結(jié)構(gòu)
鏈表存儲(chǔ)結(jié)構(gòu)
Zlbytes：一個(gè)4字節(jié)的無(wú)符號(hào)整型，存儲(chǔ)的是整個(gè)ziplist占用的字節(jié)數(shù),，用于重分配內(nèi)存時(shí)使用,。
Zltail：一個(gè)4字節(jié)的無(wú)符號(hào)整型，存儲(chǔ)的是鏈表最后一個(gè)結(jié)點(diǎn)的偏移值,，即鏈表開(kāi)頭地址+zltail即為最后一個(gè)結(jié)點(diǎn)的起始地址
Zllen：一個(gè)2字節(jié)的無(wú)符號(hào)整型,，存儲(chǔ)的是鏈表中存儲(chǔ)的結(jié)點(diǎn)數(shù)，當(dāng)這個(gè)值存儲(chǔ)的是2字節(jié)無(wú)符號(hào)整型的最大值時(shí),，需要遍歷鏈表獲取鏈表的結(jié)點(diǎn)數(shù)
Entry：鏈表結(jié)點(diǎn),，鏈表結(jié)點(diǎn)的存儲(chǔ)格式見(jiàn)結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)
Zlend：占用1字節(jié)的鏈表的結(jié)尾符，值為255
相關(guān)的宏定義
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)
結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)
<上一個(gè)鏈表結(jié)點(diǎn)占用的長(zhǎng)度><當(dāng)前鏈表結(jié)點(diǎn)占用的長(zhǎng)度><當(dāng)前結(jié)點(diǎn)數(shù)據(jù)>
上一個(gè)鏈表結(jié)點(diǎn)占用的長(zhǎng)度
上一個(gè)鏈表結(jié)點(diǎn)占用的長(zhǎng)度占用的字節(jié)數(shù)根據(jù)編碼類(lèi)型而定
當(dāng)長(zhǎng)度數(shù)據(jù)小于254使用一個(gè)字節(jié)存儲(chǔ),，該字節(jié)存儲(chǔ)的數(shù)值就是該長(zhǎng)度,，
當(dāng)長(zhǎng)度數(shù)據(jù)大于等于254時(shí)，使用5個(gè)字節(jié)存儲(chǔ),，第一個(gè)字節(jié)的數(shù)值為254,，表示接下來(lái)的4個(gè)字節(jié)才真正表示長(zhǎng)度
當(dāng)前鏈表結(jié)點(diǎn)用的長(zhǎng)度存儲(chǔ)和數(shù)據(jù)存儲(chǔ)
第一個(gè)字節(jié)的前兩位用于區(qū)分長(zhǎng)度存儲(chǔ)編碼類(lèi)型和數(shù)據(jù)編碼類(lèi)型，具體如下
字符串類(lèi)型編碼
|00pppppp|
長(zhǎng)度小于等于63(2^6-1)字節(jié)的字符串,，后6位用于存儲(chǔ)字符串長(zhǎng)度,，長(zhǎng)度與類(lèi)型總共占用了1個(gè)字節(jié)
|01pppppp|qqqqqqqq|
長(zhǎng)度小于等于16383(2^14-1)字節(jié)的字符串，后14位用于存儲(chǔ)字符串長(zhǎng)度,，長(zhǎng)度與類(lèi)型總共占用了2個(gè)字節(jié)
|10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|
長(zhǎng)度大于等于16384字節(jié)的字符串,，后4個(gè)字節(jié)用于存儲(chǔ)字符串長(zhǎng)度，長(zhǎng)度與類(lèi)型總共占用了5個(gè)字節(jié)
整型編碼
|1100____|
整型類(lèi)型,，后2個(gè)字節(jié)存儲(chǔ)的值就是該整數(shù)
|1101____|
整型類(lèi)型,，后4個(gè)字節(jié)存儲(chǔ)的值就是該整數(shù)
|1110____|
整型類(lèi)型，后8個(gè)字節(jié)存儲(chǔ)的值就是該整數(shù)
相關(guān)的宏定義
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);
創(chuàng)建一個(gè)ziplist
返回創(chuàng)建的ziplist的指針
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where);
在ziplist的尾端或頭部添加一個(gè)結(jié)點(diǎn)
zl是ziplist的指針
s是待添加結(jié)點(diǎn)的值
slen是待添加結(jié)點(diǎn)的值長(zhǎng)度
返回最新的ziplist的指針
unsigned char *ziplistIndex(unsigned char *zl, int index);
根據(jù)索引獲取ziplist的結(jié)點(diǎn),，封裝類(lèi)似數(shù)組接口
zl是ziplist的指針
index是索引,，從0開(kāi)始,，0即取鏈表的第一個(gè)結(jié)點(diǎn)，index可以是負(fù)數(shù),，負(fù)數(shù)表從后往前算,，-1就是取鏈表的最后一個(gè)元素
如果index處有結(jié)點(diǎn)，則返回指向改結(jié)點(diǎn)的指針,，否則返回NULL
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);
獲取ziplist的下一個(gè)結(jié)點(diǎn)
zl是無(wú)用參數(shù)
p是當(dāng)前結(jié)點(diǎn)指針
如果還有下一個(gè)結(jié)點(diǎn),，則返回下一個(gè)結(jié)點(diǎn)的指針，否則返回NULL
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);
獲取ziplist的上一個(gè)結(jié)點(diǎn)
zl是ziplist的指針
p是當(dāng)前結(jié)點(diǎn)指針
如果還有上一個(gè)結(jié)點(diǎn),，則返回上一個(gè)結(jié)點(diǎn)的指針,，否則返回NULL
unsigned int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, long long *lval);
獲取p指向的當(dāng)前結(jié)點(diǎn)的值
p是指向當(dāng)前結(jié)點(diǎn)的指針
sval保存獲取到的當(dāng)前結(jié)點(diǎn)的值的指針
slen是獲取到的當(dāng)前結(jié)點(diǎn)的值的長(zhǎng)度
lval是當(dāng)值是整型時(shí)保存返回的數(shù)值
如果p指向的結(jié)點(diǎn)是合法結(jié)點(diǎn)返回1，否則返回0
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);
在指針p指向的位置插入一個(gè)結(jié)點(diǎn)
zl是ziplist的指針
p是待插入結(jié)點(diǎn)的位置
s是待插入結(jié)點(diǎn)的值
slen是待插入結(jié)點(diǎn)的值的長(zhǎng)度
返回最新的ziplist的指針
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);
刪掉*p指向的結(jié)點(diǎn)
zl是ziplist的指針
p是一個(gè)value-result參數(shù),，傳入需刪除的結(jié)點(diǎn),，返回被刪除結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)的指針
返回最新的ziplist的指針
unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num);
刪除連續(xù)的一批結(jié)點(diǎn)
zl是ziplist的指針
index是開(kāi)始刪除的索引
num是刪除的個(gè)數(shù)
返回最新的ziplist的指針
unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen);
p指向的結(jié)點(diǎn)的值和s對(duì)應(yīng)的值做比較
p是ziplist結(jié)點(diǎn)的指針
s是呆比較的值
slen是s的長(zhǎng)度
相等返回1，否則返回0
unsigned int ziplistLen(unsigned char *zl);
取ziplist鏈表中元素的個(gè)數(shù)
zl是ziplist的指針
返回ziplist鏈表中元素的個(gè)數(shù)
size_t ziplistBlobLen(unsigned char *zl);
取ziplist鏈表占用的字節(jié)數(shù)
zl是ziplist的指針
返回ziplist鏈表占用的字節(jié)數(shù)
此內(nèi)容為AET網(wǎng)站原創(chuàng),，未經(jīng)授權(quán)禁止轉(zhuǎn)載,。