redis中ziplist
ziplist 是一個壓縮的雙向列表。傳統(tǒng)的雙向鏈表，在每個節(jié)點(diǎn)，都需要指向下一個和前一個節(jié)點(diǎn)的指針，占據(jù)了一定的空間；同時雙向鏈表中使用字符串保存了節(jié)點(diǎn)的值，對于整形的數(shù)值而言，比較費(fèi)空間。ziplist 在這些方面進(jìn)行了一些優(yōu)化。
下面跟著源碼來學(xué)習(xí)下：
結(jié)構(gòu) <zlbytes><zltail><zllen><entry><entry><zlend>
其中 zlbytes 整個列表所占據(jù)的空間。
zltail 最后一個節(jié)點(diǎn)的下標(biāo)，這個是便于從后往前遍歷。
zllen 列表中的節(jié)點(diǎn)個數(shù)
entry 節(jié)點(diǎn)
zlend 結(jié)束標(biāo)識符號
每個節(jié)點(diǎn)的結(jié)構(gòu)如下 <pre_node_len> <node_encode><node>
其中pre_node_len表示前面一個節(jié)點(diǎn)占據(jù)的空間，這樣可以從后面往前面遍歷節(jié)點(diǎn)
node_encode編碼以及數(shù)據(jù)信心， 具體編碼如下：
1, 00pppppp 前面兩個bit 是00,那么表示長度小于64的字符串，后面剩下的6個bit表示字符串的長度[0-63]
2, 01pppppp|qqqqqqqq 前面兩個bit是01,那么整個信息占兩個字節(jié)，剩下的14個字節(jié)來表示字符串的長度[64 – 2^14-1]
3, 10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| 前面兩個bit是10,那么整個信息占5個字節(jié)，剩下的4個字節(jié)來表示字符串長度
4， 1100____ 表示節(jié)點(diǎn)是一個整數(shù)，并且能用兩個字節(jié)表示的
5， 1101____ 表示節(jié)點(diǎn)是一個整數(shù)，并且能用四個字節(jié)表示的
6， 1110____ 表示節(jié)點(diǎn)是一個整數(shù)，并且能用八個字節(jié)表示的
通過上面的介紹，我們舉個簡單的例子，比如一個小于64位字符串（前面節(jié)點(diǎn)長度小于254），那么需要 1 ＋ 1 ＝ 2 個字節(jié)存儲額外信息(非內(nèi)容)
下圖各種編碼需要占據(jù)的空間(byte)
| 編碼方式 | 前面節(jié)點(diǎn)長度小于254 | 大于254 |
| 1 | 1+ 1 = 2 | 1 + 5 = 6 |
| 2 | 2+ 1 = 3 | 2 + 5 = 7 |
| 3 | 5+ 1 =6 | 5+ 5 = 10 |
| 4 | 1 + 1 = 2 | 1 + 5 = 6 |
| 5 | 1 + 1 = 2 | 1 + 5=6 |
| 6 | 1 + 1 = 2 | 1 + 5 = 6 |
從上圖可以看出，大部分情況，比使用鏈表消耗的8個byte(4個pre指針，4個next指針) 省。
但是也是需要代價的，實(shí)現(xiàn)復(fù)雜，特別插入和刪除過程，需要內(nèi)存的移動。
看下插入過程：
/* Insert item at "p". */
static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
size_t curlen = ZIPLIST_BYTES(zl), reqlen, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value;
zlentry entry, tail;
//計(jì)算插入節(jié)點(diǎn)前面一個節(jié)點(diǎn)的長度： 1 如果不是插入最后面，那么直接從原來的節(jié)點(diǎn)可以獲取，2 如果是最后插入，那么就要計(jì)算末個節(jié)點(diǎn)的長度
/* Find out prevlen for the entry that is inserted. */
if (p[0] != ZIP_END) {
entry = zipEntry(p);
prevlen = entry.prevrawlen;
} else {
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
prevlen = zipRawEntryLength(ptail);
}
}
//計(jì)算需要占據(jù)的空間
/* 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 zipEncodeLength will use the
* string length to figure out how to encode it. */
reqlen = slen;
}
//計(jì)算整個節(jié)點(diǎn)需要占據(jù)的空間(pre_len, slen, content)
/* We need space for both the length of the previous entry and
* the length of the payload. */
reqlen += zipPrevEncodeLength(NULL,prevlen);
reqlen += zipEncodeLength(NULL,encoding,slen);
//不過不是末尾插入，需要考慮下個節(jié)點(diǎn)紀(jì)錄當(dāng)前節(jié)點(diǎn)的長度的空間是否夠
/* 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. */
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
/* Store offset because a realloc may change the address of zl. */
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) {
/* Subtract one because of the ZIP_END bytes */
// (p-nexdiff ) --> (p+reqlen)
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/* Encode this entry's raw length in the next entry. */
zipPrevEncodeLength(p+reqlen,reqlen);
//如果下個節(jié)點(diǎn)就是最后節(jié)點(diǎn)，那么結(jié)尾節(jié)點(diǎn)下標(biāo)移動reqlen,否者把next diff 考慮進(jìn)去
/* Update offset for tail */
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. */
tail = zipEntry(p+reqlen);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END)
ZIPLIST_TAIL_OFFSET(zl) += nextdiff;
} else {
/* This element will be the new tail. */
ZIPLIST_TAIL_OFFSET(zl) = p-zl;
}
//如果下個節(jié)點(diǎn)長度變化，那么需要修改下下個節(jié)點(diǎn)對應(yīng)的字段,而這個操作有可能導(dǎo)致下下個節(jié)點(diǎn)的長度發(fā)生變化,所以需要往##修改，知道某個節(jié)點(diǎn)長度不發(fā)生改變
/* 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 */
//寫入節(jié)點(diǎn)信息
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;
}需要注意幾點(diǎn) ： 1 因?yàn)槭褂眠B續(xù)內(nèi)存，所以當(dāng)在中間插入的時候，需要把后面的節(jié)點(diǎn)往后移動。
2 插入節(jié)點(diǎn)，因?yàn)橄聜€節(jié)點(diǎn)需要保存當(dāng)前節(jié)點(diǎn)的長度，因?yàn)榧o(jì)錄這個長度使用壓縮算法，所以可能導(dǎo)致下個節(jié)點(diǎn)占據(jù)的空間發(fā)生變化，如果發(fā)生變化，那么就需要調(diào)整下個節(jié)點(diǎn)，這樣又會導(dǎo)致下下個節(jié)點(diǎn)，所以這里需要做調(diào)整。
刪除和插入過程相反，所要考慮的也就是上面兩點(diǎn)。 其中第二點(diǎn)單獨(dú)有個函數(shù)來實(shí)現(xiàn)：
static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
size_t curlen = ZIPLIST_BYTES(zl), rawlen, rawlensize;
size_t offset, noffset, extra;
unsigned char *np;
zlentry cur, next;
//如果一直有變化，那么一直到結(jié)尾
while (p[0] != ZIP_END) {
cur = zipEntry(p);
rawlen = cur.headersize + cur.len;
rawlensize = zipPrevEncodeLength(NULL,rawlen);
/* Abort if there is no next entry. */
if (p[rawlen] == ZIP_END) break;
next = zipEntry(p+rawlen);
/* Abort when "prevlen" has not changed. */
if (next.prevrawlen == rawlen) break;
//實(shí)際比原來的大
if (next.prevrawlensize < rawlensize) {
/* The "prevlen" field of "next" needs more bytes to hold
* the raw length of "cur". */
offset = p-zl;
extra = rawlensize-next.prevrawlensize;
zl = ziplistResize(zl,curlen+extra);
p = zl+offset;
/* Current pointer and offset for next element. */
np = p+rawlen;
noffset = np-zl;
/* Update tail offset when next element is not the tail element. */
if ((zl+ZIPLIST_TAIL_OFFSET(zl)) != np)
ZIPLIST_TAIL_OFFSET(zl) += extra;
/* Move the tail to the back. */
memmove(np+rawlensize,
np+next.prevrawlensize,
curlen-noffset-next.prevrawlensize-1);
zipPrevEncodeLength(np,rawlen);
/* Advance the cursor */
p += rawlen;
curlen += extra;
} else {
if (next.prevrawlensize > rawlensize) {
/* This would result in shrinking, which we want to avoid.
* So, set "rawlen" in the available bytes. */
//通過浪費(fèi)4個byte,來避免內(nèi)存移動
zipPrevEncodeLengthForceLarge(p+rawlen,rawlen);
} else {
zipPrevEncodeLength(p+rawlen,rawlen);
}
/* Stop here, as the raw length of "next" has not changed. */
break;
}
}
return zl;
}整個過程就是： 從當(dāng)前位置往后循環(huán)，如果節(jié)點(diǎn)需要增長，那么就根據(jù)增加的大小，移動數(shù)據(jù)，修改下標(biāo)等。如果縮小了，這里為避免移動，采用了一個技巧，就是大空間存小數(shù)據(jù)，浪費(fèi)4個bye
總結(jié)
以上是生活随笔為你收集整理的redis中ziplist的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： SAP CRM Distribution
- 下一篇： 3dmax中怎么种植树代理 3dmax代