列表類型可以存儲(chǔ)一組按插入順序排序的字符串，它非常靈活，支持在兩端插入、彈出數(shù)據(jù)，可以充當(dāng)棧和隊(duì)列的角色。
> LPUSH fruit Apple
(integer) 1
> RPUSH fruit banana
(integer) 2
> RPOP fruit
"banana"
> LPOP fruit
"apple"
本文探討redis中列表類型的實(shí)現(xiàn)。
ziplist
使用數(shù)組和鏈表結(jié)構(gòu)都可以實(shí)現(xiàn)列表類型。Redis中使用的是鏈表結(jié)構(gòu)。下面是一種常見的鏈表實(shí)現(xiàn)方式adlist.h：
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;
Redis內(nèi)部使用該鏈表保存運(yùn)行數(shù)據(jù)，如主服務(wù)下所有的從服務(wù)器信息。
但Redis并不使用該鏈表保存用戶列表數(shù)據(jù)，因?yàn)樗鼘?duì)內(nèi)存管理不夠友好：
（1）鏈表中每一個(gè)節(jié)點(diǎn)都占用獨(dú)立的一塊內(nèi)存，導(dǎo)致內(nèi)存碎片過多。
（2）鏈表節(jié)點(diǎn)中前后節(jié)點(diǎn)指針占用過多的額外內(nèi)存。
讀者可以思考一下，用什么結(jié)構(gòu)可以比較好地解決上面的兩個(gè)問題？沒錯(cuò)，數(shù)組。ziplist是一種類似數(shù)組的緊湊型鏈表格式。它會(huì)申請(qǐng)一整塊內(nèi)存，在這個(gè)內(nèi)存上存放該鏈表所有數(shù)據(jù)，這就是ziplist的設(shè)計(jì)思想。
定義
ziplist總體布局如下：
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
- zlbytes：uint32_t，記錄整個(gè)ziplist占用的字節(jié)數(shù)，包括zlbytes占用的4字節(jié)。
- zltail：uint32_t，記錄從ziplist起始位置到最后一個(gè)節(jié)點(diǎn)的偏移量，用于支持鏈表從尾部彈出或反向（從尾到頭）遍歷鏈表。
- zllen：uint16_t，記錄節(jié)點(diǎn)數(shù)量，如果存在超過216-2個(gè)節(jié)點(diǎn)，則這個(gè)值設(shè)置為216-1，這時(shí)需要遍歷整個(gè)ziplist獲取真正的節(jié)點(diǎn)數(shù)量。
- zlend：uint8_t，一個(gè)特殊的標(biāo)志節(jié)點(diǎn)，等于255，標(biāo)志ziplist結(jié)尾。其他節(jié)點(diǎn)數(shù)據(jù)不會(huì)以255開頭。
entry就是ziplist中保存的節(jié)點(diǎn)。entry的格式如下：
<prevlen> <encoding> <entry-data>
- entry-data：該節(jié)點(diǎn)元素，即節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)。
- prevlen：記錄前驅(qū)節(jié)點(diǎn)長(zhǎng)度，單位為字節(jié)，該屬性長(zhǎng)度為1字節(jié)或5字節(jié)。
① 如果前驅(qū)節(jié)點(diǎn)長(zhǎng)度小于254，則使用1字節(jié)存儲(chǔ)前驅(qū)節(jié)點(diǎn)長(zhǎng)度。② 否則，使用5字節(jié)，并且第一個(gè)字節(jié)固定為254，剩下4個(gè)字節(jié)存儲(chǔ)前驅(qū)節(jié)點(diǎn)長(zhǎng)度。 - encoding：代表當(dāng)前節(jié)點(diǎn)元素的編碼格式，包含編碼類型和節(jié)點(diǎn)長(zhǎng)度。一個(gè)ziplist中，不同節(jié)點(diǎn)元素的編碼格式可以不同。編碼格式規(guī)范如下：
① 00pppppp（pppppp代表encoding的低6位，下同）：字符串編碼，長(zhǎng)度小于或等于63（26-1），長(zhǎng)度存放在encoding的低6位中。② 01pppppp：字符串編碼， 長(zhǎng)度小于或等于16383（214-1），長(zhǎng)度存放在encoding的后6位和encoding后1字節(jié)中。③ 10000000：字符串編碼，長(zhǎng)度大于16383（214-1），長(zhǎng)度存放在encoding后4字節(jié)中。④ 11000000：數(shù)值編碼， 類型為int16_t，占用2字節(jié)。⑤ 11010000：數(shù)值編碼，類型為int32_t，占用4字節(jié)。⑥ 11100000：數(shù)值編碼，類型為int64_t，占用8字節(jié)。⑦ 11110000：數(shù)值編碼，使用3字節(jié)保存一個(gè)整數(shù)。⑧ 11111110：數(shù)值編碼，使用1字節(jié)保存一個(gè)整數(shù)。⑨ 1111xxxx：使用encoding低4位存儲(chǔ)一個(gè)整數(shù)，存儲(chǔ)數(shù)值范圍為0～12。該編碼下encoding低4位的可用范圍為0001～1101，encoding低4位減1為實(shí)際存儲(chǔ)的值。⑩ 11111111：255，ziplist結(jié)束節(jié)點(diǎn)。注意第②、③種編碼格式，除了encoding屬性，還需要額外的空間存儲(chǔ)節(jié)點(diǎn)元素長(zhǎng)度。第⑨種格式也比較特殊，節(jié)點(diǎn)元素直接存放在encoding屬性上。該編碼是針對(duì)小數(shù)字的優(yōu)化。這時(shí)entry-data為空。
字節(jié)序
encoding屬性使用多個(gè)字節(jié)存儲(chǔ)節(jié)點(diǎn)元素長(zhǎng)度，這種多字節(jié)數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)內(nèi)存中或者進(jìn)行網(wǎng)絡(luò)傳輸時(shí)的字節(jié)順序稱為字節(jié)序，字節(jié)序有兩種類型：大端字節(jié)序和小端字節(jié)序。
- 大端字節(jié)序：低字節(jié)數(shù)據(jù)保存在內(nèi)存高地址位置，高字節(jié)數(shù)據(jù)保存在內(nèi)存低地址位置。
- 小端字節(jié)序：低字節(jié)數(shù)據(jù)保存在內(nèi)存低地址位置，高字節(jié)數(shù)據(jù)保存在內(nèi)存高地址位置。
數(shù)值0X44332211的大端字節(jié)序和小端字節(jié)序存儲(chǔ)方式如圖2-1所示。
CPU處理指令通常是按照內(nèi)存地址增長(zhǎng)方向執(zhí)行的。使用小端字節(jié)序，CPU可以先讀取并處理低位字節(jié)，執(zhí)行計(jì)算的借位、進(jìn)位操作時(shí)效率更高。大端字節(jié)序則更符合人們的讀寫習(xí)慣。
ziplist采取的是小端字節(jié)序。
下面是Redis提供的一個(gè)簡(jiǎn)單例子：
- [0f 00 00 00]：zlbytes為15，代表整個(gè)ziplist占用15字節(jié)，注意該數(shù)值以小端字節(jié)序存儲(chǔ)。
- [0c 00 00 00]：zltail為12，代表從ziplist起始位置到最后一個(gè)節(jié)點(diǎn)（[02 f6]）的偏移量。
- [02 00]：zllen為2，代表ziplist中有2個(gè)節(jié)點(diǎn)。
- [00 f3]：00代表前一個(gè)節(jié)點(diǎn)長(zhǎng)度，f3使用了encoding第⑨種編碼格式，存儲(chǔ)數(shù)據(jù)為encoding低4位減1，即2。
- [02 f6]：02代表前一個(gè)節(jié)點(diǎn)長(zhǎng)度為2字節(jié)，f5編碼格式同上，存儲(chǔ)數(shù)據(jù)為5。
- [ff]：結(jié)束標(biāo)志節(jié)點(diǎn)。
ziplist是Redis中比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，希望讀者結(jié)合上述屬性說(shuō)明和例子，理解ziplist中數(shù)據(jù)的存放格式。
操作分析
提示：本節(jié)以下代碼如無(wú)特殊說(shuō)明，均在ziplist.h、ziplist.c中。
ziplistFind函數(shù)負(fù)責(zé)在ziplist中查找元素：
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;
// [1]
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
// [2]
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
q = p + prevlensize + lensize;
if (skipcnt == 0) {
// [3]
if (ZIP_IS_STR(encoding)) {
if (len == vlen && memcmp(q, vstr, vlen) == 0) {
return p;
}
} else {
// [4]
if (vencoding == 0) {
if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
vencoding = UCHAR_MAX;
}
assert(vencoding);
}
// [5]
if (vencoding != UCHAR_MAX) {
long long ll = zipLoadInteger(q, encoding);
if (ll == vll) {
return p;
}
}
}
// [6]
skipcnt = skip;
} else {
skipcnt--;
}
// [7]
p = q + len;
}
return NULL;
}
參數(shù)說(shuō)明：
- p：指定從ziplist哪個(gè)節(jié)點(diǎn)開始查找。
- vstr、vlen：待查找元素的內(nèi)容和長(zhǎng)度。
- skip：間隔多少個(gè)節(jié)點(diǎn)才執(zhí)行一次元素對(duì)比操作。
【1】計(jì)算當(dāng)前節(jié)點(diǎn)prevlen屬性長(zhǎng)度是1字節(jié)還是5字節(jié)，結(jié)果存放在prevlensize變量中。
【2】計(jì)算當(dāng)前節(jié)點(diǎn)相關(guān)屬性，結(jié)果存放在如下變量中：
encoding：節(jié)點(diǎn)編碼格式。
lensize：額外存放節(jié)點(diǎn)元素長(zhǎng)度的字節(jié)數(shù)，第②、③種格式的encoding編碼需要額外的空間存放節(jié)點(diǎn)元素長(zhǎng)度。
len：節(jié)點(diǎn)元素的長(zhǎng)度。
【3】如果當(dāng)前節(jié)點(diǎn)元素是字符串編碼，則對(duì)比String的內(nèi)容，若相等則返回。
【4】當(dāng)前節(jié)點(diǎn)元素是數(shù)值編碼，并且還沒有對(duì)待查找內(nèi)容vstr進(jìn)行編碼，則對(duì)它進(jìn)行編碼操作（編碼操作只執(zhí)行一次），編碼后的數(shù)值存儲(chǔ)在vll變量中。
【5】如果上一步編碼成功（待查找內(nèi)容也是數(shù)值），則對(duì)比編碼后的結(jié)果，否則不需要對(duì)比編碼結(jié)果。zipLoadInteger函數(shù)從節(jié)點(diǎn)元素中提取節(jié)點(diǎn)存儲(chǔ)的數(shù)值，與上一步得到的vll變量進(jìn)行對(duì)比。
【6】skipcnt不為0，直接跳過節(jié)點(diǎn)并將skipcnt減1，直到skipcnt為0才對(duì)比數(shù)據(jù)。
【7】p指向p + prevlensize + lensize + len（數(shù)據(jù)長(zhǎng)度），得到下一個(gè)節(jié)點(diǎn)的起始位置。
提示：由于源碼中部分函數(shù)太長(zhǎng)，為了版面整潔，本書將其劃分為多個(gè)代碼段，并使用“// more”標(biāo)志該函數(shù)后續(xù)還有其他代碼段，請(qǐng)讀者留意該標(biāo)志。
下面看一下如何在ziplist中插入節(jié)點(diǎn)：
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
...
// [1]
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);
}
}
// [2]
if (zipTryEncoding(s,slen,&value,&encoding)) {
reqlen = zipIntSize(encoding);
} else {
reqlen = slen;
}
// [3]
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
// [4]
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {
nextdiff = 0;
forcelarge = 1;
}
// more
}
參數(shù)說(shuō)明：
- zl：待插入ziplist。
- p：指向插入位置的后驅(qū)節(jié)點(diǎn)。
- s、slen：待插入元素的內(nèi)容和長(zhǎng)度。
【1】計(jì)算前驅(qū)節(jié)點(diǎn)長(zhǎng)度并存放到prevlen變量中。
如果p沒有指向ZIP_END，則可以直接取p節(jié)點(diǎn)的prevlen屬性，否則需要通過ziplist.zltail找到前驅(qū)節(jié)點(diǎn)，再獲取前驅(qū)節(jié)點(diǎn)的長(zhǎng)度。
【2】對(duì)待插入元素的內(nèi)容進(jìn)行編碼，并將內(nèi)容的長(zhǎng)度存放在reqlen變量中。
zipTryEncoding函數(shù)嘗試將元素內(nèi)容編碼為數(shù)值，如果元素內(nèi)容能編碼為數(shù)值，則該函數(shù)返回1，這時(shí)value指向編碼后的值，encoding存儲(chǔ)對(duì)應(yīng)編碼格式，否則返回0。
【3】zipStorePrevEntryLength函數(shù)計(jì)算prevlen屬性的長(zhǎng)度（1字節(jié)或5字節(jié)）。
zipStoreEntryEncoding函數(shù)計(jì)算額外存放節(jié)點(diǎn)元素長(zhǎng)度所需字節(jié)數(shù)（encoding編碼中第②、③種格式）。reqlen變量值添加這兩個(gè)函數(shù)的返回值后成為插入節(jié)點(diǎn)長(zhǎng)度。
【4】zipPrevLenByteDiff函數(shù)計(jì)算后驅(qū)節(jié)點(diǎn)prevlen屬性長(zhǎng)度需調(diào)整多少個(gè)字節(jié)，結(jié)果存放在nextdiff變量中。
假如p指向節(jié)點(diǎn)為e2，而插入前e2的前驅(qū)節(jié)點(diǎn)為e1，e2的prevlen存儲(chǔ)e1的長(zhǎng)度。
插入后e2的前驅(qū)節(jié)點(diǎn)為插入節(jié)點(diǎn)，這時(shí)e2的prevlen應(yīng)該存儲(chǔ)插入節(jié)點(diǎn)長(zhǎng)度，所以e2的prevlen需要修改。圖2-2展示了一個(gè)簡(jiǎn)單示例。
從圖2-2可以看到，后驅(qū)節(jié)點(diǎn)e2的prevlen屬性長(zhǎng)度從1變成了5，則nextdiff變量為4。
如果插入節(jié)點(diǎn)長(zhǎng)度小于4，并且原后驅(qū)節(jié)點(diǎn)e2的prevlen屬性長(zhǎng)度為5，則這時(shí)設(shè)置forcelarge為1，代表強(qiáng)制保持后驅(qū)節(jié)點(diǎn)e2的prevlen屬性長(zhǎng)度不變。讀者可以思考一下，為什么要這樣設(shè)計(jì)？
繼續(xù)分析__ziplistInsert函數(shù)：
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
...
// [5]
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
p = zl+offset;
if (p[0] != ZIP_END) {
// [6]
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
// [7]
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
// [8]
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
// [9]
zipEntry(p+reqlen, &tail);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
// [10]
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
// [11]
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
// [12]
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
// [13]
ZIPLIST_INCR_LENGTH(zl,1);
return zl;
}
【5】重新為ziplist分配內(nèi)存，主要是為插入節(jié)點(diǎn)申請(qǐng)空間。新ziplist的內(nèi)存大小為curlen+reqlen+nextdiff（curlen變量為插入前ziplist長(zhǎng)度）。將p重新賦值為zl+offset（offset變量為插入節(jié)點(diǎn)的偏移量），是因?yàn)閦iplistResize函數(shù)可能會(huì)為ziplist申請(qǐng)新的內(nèi)存地址。
下面針對(duì)存在后驅(qū)節(jié)點(diǎn)的場(chǎng)景進(jìn)行處理。
【6】將插入位置后面所有的節(jié)點(diǎn)后移，為插入節(jié)點(diǎn)騰出空間。移動(dòng)空間的起始地址為p-nextdiff，減去nextdiff是因?yàn)楹篁?qū)節(jié)點(diǎn)的prevlen屬性需要調(diào)整nextdiff長(zhǎng)度。移動(dòng)空間的長(zhǎng)度為curlen-offset-1+nextdiff，減1是因?yàn)樽詈蟮慕Y(jié)束標(biāo)志節(jié)點(diǎn)已經(jīng)在ziplistResize函數(shù)中設(shè)置了。
memmove是C語(yǔ)言提供的內(nèi)存移動(dòng)函數(shù)。
【7】修改后驅(qū)節(jié)點(diǎn)的prevlen屬性。
【8】更新ziplist.zltail，將其加上reqlen的值。
【9】如果存在多個(gè)后驅(qū)節(jié)點(diǎn)，則ziplist.zltail還要加上nextdiff的值。
如果只有一個(gè)后驅(qū)節(jié)點(diǎn)，則不需要加上nextdiff，因?yàn)檫@時(shí)后驅(qū)節(jié)點(diǎn)大小變化了nextdiff，但后驅(qū)節(jié)點(diǎn)只移動(dòng)了reqlen。
提示：zipEntry函數(shù)會(huì)將給定節(jié)點(diǎn)的所有信息賦值到zlentry結(jié)構(gòu)體中。zlentry結(jié)構(gòu)體用于在計(jì)算過程中存放節(jié)點(diǎn)信息，實(shí)際存儲(chǔ)數(shù)據(jù)格式并不使用該結(jié)構(gòu)體。讀者不要被tail這個(gè)變量名誤導(dǎo)，它只是指向插入節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn)，并不一定指向尾節(jié)點(diǎn)。
【10】這里針對(duì)不存在后驅(qū)節(jié)點(diǎn)的場(chǎng)景進(jìn)行處理，只需更新最后一個(gè)節(jié)點(diǎn)偏移量ziplist.zltail。
【11】級(jí)聯(lián)更新。
【12】寫入插入數(shù)據(jù)。
【13】更新ziplist節(jié)點(diǎn)數(shù)量ziplist.zllen。
解釋一下以下代碼：
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
intrev32ifbe函數(shù)完成以下工作：如果主機(jī)使用的小端字節(jié)序，則不做處理。如果主機(jī)使用的大端字節(jié)序，則反轉(zhuǎn)數(shù)據(jù)字節(jié)序（數(shù)據(jù)第1位與第4位、第2位與第3位交換），這樣會(huì)將大端字節(jié)序數(shù)據(jù)轉(zhuǎn)化為小端字節(jié)序，或者將小端字節(jié)序數(shù)據(jù)轉(zhuǎn)化為大端字節(jié)序。
在上面的代碼中，如果主機(jī)CPU使用的是小端字節(jié)序，則intrev32ifbe函數(shù)不做任何處理。
如果主機(jī)CPU使用的是大端字節(jié)序，則從內(nèi)存取出數(shù)據(jù)后，先調(diào)用intrev32ifbe函數(shù)將數(shù)據(jù)轉(zhuǎn)化為大端字節(jié)序后再計(jì)算。計(jì)算完成后，調(diào)用intrev32ifbe函數(shù)將數(shù)據(jù)轉(zhuǎn)化為小端字節(jié)序后再存入內(nèi)存。
級(jí)聯(lián)更新
例2-1：
考慮一種極端場(chǎng)景，在ziplist的e2節(jié)點(diǎn)前插入一個(gè)新的節(jié)點(diǎn)ne，元素?cái)?shù)據(jù)長(zhǎng)度為254，如圖2-3所示。
插入節(jié)點(diǎn)如圖2-4所示。
插入節(jié)點(diǎn)后e2的prevlen屬性長(zhǎng)度需要更新為5字節(jié)。
注意e3的prevlen，插入前e2的長(zhǎng)度為253，所以e3的prevlen屬性長(zhǎng)度為1字節(jié)，插入新節(jié)點(diǎn)后，e2的長(zhǎng)度為257，那么e3的prevlen屬性長(zhǎng)度也要更新了，這就是級(jí)聯(lián)更新。在極端情況下，e3后續(xù)的節(jié)點(diǎn)也要繼續(xù)更新prevlen屬性。
我們看一下級(jí)聯(lián)更新的實(shí)現(xiàn)：
unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
size_t offset, noffset, extra;
unsigned char *np;
zlentry cur, next;
// [1]
while (p[0] != ZIP_END) {
// [2]
zipEntry(p, &cur);
rawlen = cur.headersize + cur.len;
rawlensize = zipStorePrevEntryLength(NULL,rawlen);
if (p[rawlen] == ZIP_END) break;
// [3]
zipEntry(p+rawlen, &next);
if (next.prevrawlen == rawlen) break;
// [4]
if (next.prevrawlensize < rawlensize) {
// [5]
offset = p-zl;
extra = rawlensize-next.prevrawlensize;
zl = ziplistResize(zl,curlen+extra);
p = zl+offset;
// [6]
np = p+rawlen;
noffset = np-zl;
if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
}
// [7]
memmove(np+rawlensize,
np+next.prevrawlensize,
curlen-noffset-next.prevrawlensize-1);
zipStorePrevEntryLength(np,rawlen);
// [8]
p += rawlen;
curlen += extra;
} else {
// [9]
if (next.prevrawlensize > rawlensize) {
zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
} else {
// [10]
zipStorePrevEntryLength(p+rawlen,rawlen);
}
// [11]
break;
}
}
return zl;
}
參數(shù)說(shuō)明：
- p：p指向插入節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn)，為了描述方便，下面將p指向的節(jié)點(diǎn)稱為當(dāng)前節(jié)點(diǎn)。
【1】如果遇到ZIP_END，則退出循環(huán)。
【2】如果下一個(gè)節(jié)點(diǎn)是ZIP_END，則退出。
rawlen變量為當(dāng)前節(jié)點(diǎn)長(zhǎng)度，rawlensize變量為當(dāng)前節(jié)點(diǎn)長(zhǎng)度占用的字節(jié)數(shù)。
p[rawlen]即p的后驅(qū)節(jié)點(diǎn)的第一個(gè)字節(jié)。
【3】計(jì)算后驅(qū)節(jié)點(diǎn)信息。如果后驅(qū)節(jié)點(diǎn)的prevlen等于當(dāng)前節(jié)點(diǎn)的長(zhǎng)度，則退出。
【4】假設(shè)存儲(chǔ)當(dāng)前節(jié)點(diǎn)長(zhǎng)度需要使用actprevlen（1或者5）個(gè)字節(jié)，這里需要處理3種情況。情況1：后驅(qū)節(jié)點(diǎn)的prevlen屬性長(zhǎng)度小于actprevlen，這時(shí)需要擴(kuò)容，如例2-1中的場(chǎng)景。
【5】重新為ziplist分配內(nèi)存。
【6】如果后驅(qū)節(jié)點(diǎn)非ZIP_END，則需要修改ziplist.zltail屬性。
【7】將當(dāng)前節(jié)點(diǎn)后面所有的節(jié)點(diǎn)后移，騰出空間用來(lái)修改后驅(qū)節(jié)點(diǎn)的prevlen。
【8】將p指針指向后驅(qū)節(jié)點(diǎn)，繼續(xù)處理后面節(jié)點(diǎn)的prevlen。
【9】情況2：后驅(qū)節(jié)點(diǎn)的prevlen屬性長(zhǎng)度大于actprevlen，這時(shí)需要縮容。為了不讓級(jí)聯(lián)更新繼續(xù)下去，這時(shí)強(qiáng)制后驅(qū)節(jié)點(diǎn)的prevlen保持不變。
【10】情況3：后驅(qū)節(jié)點(diǎn)的prevlen屬性長(zhǎng)度等于actprevlen，只要修改后驅(qū)節(jié)點(diǎn)prevlen值，不需要調(diào)整ziplist的大小。
【11】情況2和情況3中級(jí)聯(lián)更新不需要繼續(xù)，退出。
回到上面__ziplistInsert函數(shù)中為什么要設(shè)置forcelarge為1的問題，這樣是為了避免插入小節(jié)點(diǎn)時(shí)，導(dǎo)致級(jí)聯(lián)更新現(xiàn)象的出現(xiàn)，所以強(qiáng)制保持后驅(qū)節(jié)點(diǎn)的prevlen屬性長(zhǎng)度不變。
從上面的分析我們可以看到，級(jí)聯(lián)更新下的性能是非常糟糕的，而且代碼復(fù)雜度也高，那么怎么解決這個(gè)問題呢？我們先看一下為什么需要使用prevlen這個(gè)屬性？這是因?yàn)榉聪虮闅v時(shí)，每向前跨過一個(gè)節(jié)點(diǎn)，都必須知道前面這個(gè)節(jié)點(diǎn)的長(zhǎng)度。
既然這樣，我們把每個(gè)節(jié)點(diǎn)長(zhǎng)度都保存一份到節(jié)點(diǎn)的最后位置，反向遍歷時(shí)，直接從前一個(gè)節(jié)點(diǎn)的最后位置獲取前一個(gè)節(jié)點(diǎn)的長(zhǎng)度不就可以了嗎？而且這樣每個(gè)節(jié)點(diǎn)都是獨(dú)立的，插入或刪除節(jié)點(diǎn)都不會(huì)有級(jí)聯(lián)更新的現(xiàn)象。基于這種設(shè)計(jì)，Redis作者設(shè)計(jì)另一種結(jié)構(gòu)listpack。設(shè)計(jì)listpack的目的是取代ziplist，但是ziplist使用范圍比較廣，替換起來(lái)比較復(fù)雜，所以目前只應(yīng)用在新增加的Stream結(jié)構(gòu)中。等到我們分析Stream時(shí)再討論listpack的設(shè)計(jì)。由此可見，優(yōu)秀的設(shè)計(jì)并不是一蹴而就的。
ziplist提供常用函數(shù)如表2-1所示。
|
函數(shù) |
作用 |
|
ziplistNew |
創(chuàng)建一個(gè)空的ziplist |
|
ziplistPush |
在ziplist頭部或尾部添加元素 |
|
ziplistInsert |
插入元素到ziplist指定位置 |
|
ziplistFind |
查找給定的元素 |
|
ziplistDelete |
刪除給定節(jié)點(diǎn) |
即使使用新的listpack格式，每插入一個(gè)新節(jié)點(diǎn)，也還可能需要進(jìn)行兩次內(nèi)存拷貝。
（1）為整個(gè)鏈表分配新內(nèi)存空間，主要是為新節(jié)點(diǎn)創(chuàng)建空間。
（2）將插入節(jié)點(diǎn)所有后驅(qū)節(jié)點(diǎn)后移，為插入節(jié)點(diǎn)騰出空間。
如果鏈表很長(zhǎng)，則每次插入或刪除節(jié)點(diǎn)時(shí)都需要進(jìn)行大量的內(nèi)存拷貝，這個(gè)性能是無(wú)法接受的，那么如何解決這個(gè)問題呢？這時(shí)就要用到quicklist了。
