壓縮清單是清單鍵和哈西鍵的底層實作之一，當一個清單鍵隻包含少量清單項，并且每個清單項要麼就是小整數值，要麼就是長度比較短的字元串，那麼Redis就會使用壓縮清單來做清單鍵的底層實作。
壓縮清單是Redis為了節約記憶體而開發的，是一系列特殊編碼的連續記憶體塊組成的順序型資料結構，一個壓縮清單可以包含任意多個節點，每個節點可以儲存一個位元組數組或者一個整數值。
ziplist的構成
ziplist的記憶體布局如下所示：
- zlbytes：4位元組，記錄整個壓縮清單占用記憶體的位元組數
- zltail：4位元組，記錄壓縮清單尾部節點距離起始位址的偏移量
- zllen：2位元組，記錄壓縮清單包含的節點數量
- entry：不定，清單中的每個節點
- zlend：1位元組，特殊值0xFF，标記壓縮清單的結束
是以通過下面的宏定義可以非常友善的求出各個字段的值
#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)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
一個簡單的ziplist示意圖如下：
zlbytes為0x50，表示壓縮清單一共占用了0x50=80位元組，其中zltail訓示最後一個節點距離起始位址的偏移量為0x3C=60位元組，是以p+60就為最後一個節點的起始位址，zllen=3表示清單中一共有3個節點。
ziplist節點定義如下：
typedef struct zlentry {
unsigned int prevrawlensize, prevrawlen;
unsigned int lensize, len;
unsigned int headersize;
unsigned char encoding;
unsigned char *p;
} zlentry;
- prevrawlen：前置節點的長度
- prevrawlensize：編碼 prevrawlen 所需的位元組大小
- len：目前節點的長度
- lensize：編碼 len 所需的位元組大小
- headersize：目前節點 header 的大小，等于 prevrawlensize + lensize
- encoding：目前節點值所使用的編碼類型
- p：指向目前節點的指針
- prevrawlen：前置節點的長度
- prevrawlensize：編碼 prevrawlen 所需的位元組大小
- len：目前節點的長度
- lensize：編碼 len 所需的位元組大小
- headersize：目前節點 header 的大小，等于 prevrawlensize + lensize
- encoding：目前節點值所使用的編碼類型
- p：指向目前節點的指針
ziplist的建立
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//即ZIPLIST_HEADER_SIZE=zlbytes(4)+zltail(4)+zllen(2)
unsigned char *ziplistNew(void) {
unsigned int bytes = ZIPLIST_HEADER_SIZE+;//1位元組的zlend
unsigned char *zl = zmalloc(bytes); //配置設定記憶體
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);//初始化各字段
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
ZIPLIST_LENGTH(zl) = ;
zl[bytes-] = ZIP_END; //ZIP_END=0xFF
return zl;//傳回ziplist的起始位址
}
這樣就完成了一個壓縮清單的建立了 加入一個元素
向ziplist中加入一個元素可以調用ziplistPush或ziplistInsert，二者的差別在于push隻能在清單頭部或尾部插入，而insert則可以在任意位置插入。這兩個函數最終都是通過調用__ziplistInsert來完成插入操作的.
//在zl的位置p處插入一個元素，元素的内容為s，s的長度為slen
static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned int prevlensize, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789; /*任意一個非0值*/
zlentry tail;
/* 首先找到待插入位置的前一個節點的長度prevlen*/
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 = zipRawEntryLength(ptail);
}
}
/* 首先判斷節點是否可以被編碼，并選擇合适的編碼方式 */
if (zipTryEncoding(s,slen,&value,&encoding)) {
reqlen = zipIntSize(encoding);
} else {
reqlen = slen;//若不能被編碼，直接以字元串形式存儲
}
/* 還需要存儲前一個節點的長度和目前節點的長度 */
reqlen += zipPrevEncodeLength(NULL,prevlen);
reqlen += zipEncodeLength(NULL,encoding,slen);
/* 當插入位置不為tail時，需要保證後一個節點的prevlen字段足夠存儲目前節點的長度 */
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
/* 儲存偏移量 */
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
p = zl+offset;
/* Apply memory move when necessary and update tail offset. */
if (p[0] != ZIP_END) { //當插入位置不為tail時
/* 将p之後的所有内容向後移動到p+reqlen */
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/*将目前節點的長度經編碼後存儲到下一個節點的prevlen中*/
zipPrevEncodeLength(p+reqlen,reqlen);
/* 更新zltail的值 */
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
tail = zipEntry(p+reqlen);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else { //插入到清單尾部
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
/* 将新元素寫到位置p */
p += zipPrevEncodeLength(p,prevlen);
p += zipEncodeLength(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
ZIPLIST_INCR_LENGTH(zl,1);
return zl;
}
當加入新節點後，後一個節點需要儲存新節點的長度資訊，當後一個節點的長度字段在記憶體中占有的長度不足以表示該長度資訊時，就需要對後一個節點進行更新，并擴充其記憶體。是以這個步驟可能會導緻連鎖更新。而删除操作也類似
Redis-資料結構-壓縮清單-ziplist
- 1string2ll（）函數的傳回值：
//判斷能否編碼，傳回1時可以編碼。
static int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
long long value;
if (entrylen >= 32 || entrylen == 0) return 0; //字元串長度隻能為0~32
if (string2ll((char*)entry,entrylen,&value)) {
if (value >= 0 && value <= 12) {
*encoding = ZIP_INT_IMM_MIN+value;
} else if (value >= INT8_MIN && value <= INT8_MAX) {
*encoding = ZIP_INT_8B;
} else if (value >= INT16_MIN && value <= INT16_MAX) {
*encoding = ZIP_INT_16B;
} else if (value >= INT24_MIN && value <= INT24_MAX) {
*encoding = ZIP_INT_24B;
} else if (value >= INT32_MIN && value <= INT32_MAX) {
*encoding = ZIP_INT_32B;
} else {
*encoding = ZIP_INT_64B;
}
*v = value;
return 1;
}
return 0;
}
a）當傳入的字元串隻包含數字，如”1234”、”-456”這種情況時，才會傳回1，并将字元串轉化為數字存儲在value中.當數字過大溢出時，也會傳回0
b）否則都傳回0
可以發現 zipTryEncoding（）對字元串的長度和整數的大小進行了限制，隻有在一定範圍内才會進行編碼
查找元素
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
int skipcnt = 0;
unsigned char vencoding = 0;
long long vll = 0;
while (p[0] != ZIP_END) { //從頭周遊到最後一個節點
unsigned int prevlensize, encoding, lensize, len;
unsigned char *q;
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
q = p + prevlensize + lensize;
if (skipcnt == 0) {
if (ZIP_IS_STR(encoding)) { //如果沒有編碼，直接以字元串形式比較
if (len == vlen && memcmp(q, vstr, vlen) == 0) {
return p;
}
} else {
if (vencoding == 0) { //否則對vstr進行編碼
if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
vencoding = UCHAR_MAX;
}
assert(vencoding);
}
if (vencoding != UCHAR_MAX) {
long long ll = zipLoadInteger(q, encoding);
if (ll == vll) { //然後再與節點資料比較
return p;
}
}
}
skipcnt = skip;
} else {
skipcnt--;
}
p = q + len;
}
return NULL;
}
API
Redis-資料結構-壓縮清單-ziplist