列表類型可以存儲一組按插入順序排序的字符串，它非常靈活，支持在兩端插入、彈出數(shù)據(jù)，可以充當棧和隊列的角色。

> LPUSH fruit Apple
(integer) 1
> RPUSH fruit banana
(integer) 2
> RPOP fruit
"banana"
> LPOP fruit
"apple"

本文探討redis中列表類型的實現(xiàn)。

ziplist

使用數(shù)組和鏈表結構都可以實現(xiàn)列表類型。Redis中使用的是鏈表結構。下面是一種常見的鏈表實現(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)部使用該鏈表保存運行數(shù)據(jù)，如主服務下所有的從服務器信息。
但Redis并不使用該鏈表保存用戶列表數(shù)據(jù)，因為它對內(nèi)存管理不夠友好：
（1）鏈表中每一個節(jié)點都占用獨立的一塊內(nèi)存，導致內(nèi)存碎片過多。
（2）鏈表節(jié)點中前后節(jié)點指針占用過多的額外內(nèi)存。
讀者可以思考一下，用什么結構可以比較好地解決上面的兩個問題？沒錯，數(shù)組。ziplist是一種類似數(shù)組的緊湊型鏈表格式。它會申請一整塊內(nèi)存，在這個內(nèi)存上存放該鏈表所有數(shù)據(jù)，這就是ziplist的設計思想。

定義

ziplist總體布局如下：

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

zlbytes：uint32_t，記錄整個ziplist占用的字節(jié)數(shù)，包括zlbytes占用的4字節(jié)。
zltail：uint32_t，記錄從ziplist起始位置到最后一個節(jié)點的偏移量，用于支持鏈表從尾部彈出或反向（從尾到頭）遍歷鏈表。
zllen：uint16_t，記錄節(jié)點數(shù)量，如果存在超過216-2個節(jié)點，則這個值設置為216-1，這時需要遍歷整個ziplist獲取真正的節(jié)點數(shù)量。
zlend：uint8_t，一個特殊的標志節(jié)點，等于255，標志ziplist結尾。其他節(jié)點數(shù)據(jù)不會以255開頭。

entry就是ziplist中保存的節(jié)點。entry的格式如下：

<prevlen> <encoding> <entry-data>

entry-data：該節(jié)點元素，即節(jié)點存儲的數(shù)據(jù)。
prevlen：記錄前驅節(jié)點長度，單位為字節(jié)，該屬性長度為1字節(jié)或5字節(jié)。
① 如果前驅節(jié)點長度小于254，則使用1字節(jié)存儲前驅節(jié)點長度。② 否則，使用5字節(jié)，并且第一個字節(jié)固定為254，剩下4個字節(jié)存儲前驅節(jié)點長度。
encoding：代表當前節(jié)點元素的編碼格式，包含編碼類型和節(jié)點長度。一個ziplist中，不同節(jié)點元素的編碼格式可以不同。編碼格式規(guī)范如下：
① 00pppppp（pppppp代表encoding的低6位，下同）：字符串編碼，長度小于或等于63（26-1），長度存放在encoding的低6位中。② 01pppppp：字符串編碼，長度小于或等于16383（214-1），長度存放在encoding的后6位和encoding后1字節(jié)中。③ 10000000：字符串編碼，長度大于16383（214-1），長度存放在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é)保存一個整數(shù)。⑧ 11111110：數(shù)值編碼，使用1字節(jié)保存一個整數(shù)。⑨ 1111xxxx：使用encoding低4位存儲一個整數(shù)，存儲數(shù)值范圍為0～12。該編碼下encoding低4位的可用范圍為0001～1101，encoding低4位減1為實際存儲的值。⑩ 11111111：255，ziplist結束節(jié)點。注意第②、③種編碼格式，除了encoding屬性，還需要額外的空間存儲節(jié)點元素長度。第⑨種格式也比較特殊，節(jié)點元素直接存放在encoding屬性上。該編碼是針對小數(shù)字的優(yōu)化。這時entry-data為空。

字節(jié)序

encoding屬性使用多個字節(jié)存儲節(jié)點元素長度，這種多字節(jié)數(shù)據(jù)存儲在計算機內(nèi)存中或者進行網(wǎng)絡傳輸時的字節(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é)序存儲方式如圖2-1所示。

CPU處理指令通常是按照內(nèi)存地址增長方向執(zhí)行的。使用小端字節(jié)序，CPU可以先讀取并處理低位字節(jié)，執(zhí)行計算的借位、進位操作時效率更高。大端字節(jié)序則更符合人們的讀寫習慣。
ziplist采取的是小端字節(jié)序。
下面是Redis提供的一個簡單例子：

[0f 00 00 00]：zlbytes為15，代表整個ziplist占用15字節(jié)，注意該數(shù)值以小端字節(jié)序存儲。
[0c 00 00 00]：zltail為12，代表從ziplist起始位置到最后一個節(jié)點（[02 f6]）的偏移量。
[02 00]：zllen為2，代表ziplist中有2個節(jié)點。
[00 f3]：00代表前一個節(jié)點長度，f3使用了encoding第⑨種編碼格式，存儲數(shù)據(jù)為encoding低4位減1，即2。
[02 f6]：02代表前一個節(jié)點長度為2字節(jié)，f5編碼格式同上，存儲數(shù)據(jù)為5。
[ff]：結束標志節(jié)點。
ziplist是Redis中比較復雜的數(shù)據(jù)結構，希望讀者結合上述屬性說明和例子，理解ziplist中數(shù)據(jù)的存放格式。

操作分析

提示：本節(jié)以下代碼如無特殊說明，均在ziplist.h、ziplist.c中。

ziplistFind函數(shù)負責在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ù)說明：

p：指定從ziplist哪個節(jié)點開始查找。
vstr、vlen：待查找元素的內(nèi)容和長度。
skip：間隔多少個節(jié)點才執(zhí)行一次元素對比操作。

【1】計算當前節(jié)點prevlen屬性長度是1字節(jié)還是5字節(jié)，結果存放在prevlensize變量中。
【2】計算當前節(jié)點相關屬性，結果存放在如下變量中：
encoding：節(jié)點編碼格式。
lensize：額外存放節(jié)點元素長度的字節(jié)數(shù)，第②、③種格式的encoding編碼需要額外的空間存放節(jié)點元素長度。
len：節(jié)點元素的長度。
【3】如果當前節(jié)點元素是字符串編碼，則對比String的內(nèi)容，若相等則返回。
【4】當前節(jié)點元素是數(shù)值編碼，并且還沒有對待查找內(nèi)容vstr進行編碼，則對它進行編碼操作（編碼操作只執(zhí)行一次），編碼后的數(shù)值存儲在vll變量中。
【5】如果上一步編碼成功（待查找內(nèi)容也是數(shù)值），則對比編碼后的結果，否則不需要對比編碼結果。zipLoadInteger函數(shù)從節(jié)點元素中提取節(jié)點存儲的數(shù)值，與上一步得到的vll變量進行對比。
【6】skipcnt不為0，直接跳過節(jié)點并將skipcnt減1，直到skipcnt為0才對比數(shù)據(jù)。
【7】p指向p + prevlensize + lensize + len（數(shù)據(jù)長度），得到下一個節(jié)點的起始位置。

提示：由于源碼中部分函數(shù)太長，為了版面整潔，本書將其劃分為多個代碼段，并使用“// more”標志該函數(shù)后續(xù)還有其他代碼段，請讀者留意該標志。

下面看一下如何在ziplist中插入節(jié)點：

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ù)說明：

zl：待插入ziplist。
p：指向插入位置的后驅節(jié)點。
s、slen：待插入元素的內(nèi)容和長度。

【1】計算前驅節(jié)點長度并存放到prevlen變量中。
如果p沒有指向ZIP_END，則可以直接取p節(jié)點的prevlen屬性，否則需要通過ziplist.zltail找到前驅節(jié)點，再獲取前驅節(jié)點的長度。
【2】對待插入元素的內(nèi)容進行編碼，并將內(nèi)容的長度存放在reqlen變量中。
zipTryEncoding函數(shù)嘗試將元素內(nèi)容編碼為數(shù)值，如果元素內(nèi)容能編碼為數(shù)值，則該函數(shù)返回1，這時value指向編碼后的值，encoding存儲對應編碼格式，否則返回0。
【3】zipStorePrevEntryLength函數(shù)計算prevlen屬性的長度（1字節(jié)或5字節(jié)）。
zipStoreEntryEncoding函數(shù)計算額外存放節(jié)點元素長度所需字節(jié)數(shù)（encoding編碼中第②、③種格式）。reqlen變量值添加這兩個函數(shù)的返回值后成為插入節(jié)點長度。
【4】zipPrevLenByteDiff函數(shù)計算后驅節(jié)點prevlen屬性長度需調(diào)整多少個字節(jié)，結果存放在nextdiff變量中。

假如p指向節(jié)點為e2，而插入前e2的前驅節(jié)點為e1，e2的prevlen存儲e1的長度。
插入后e2的前驅節(jié)點為插入節(jié)點，這時e2的prevlen應該存儲插入節(jié)點長度，所以e2的prevlen需要修改。圖2-2展示了一個簡單示例。

從圖2-2可以看到，后驅節(jié)點e2的prevlen屬性長度從1變成了5，則nextdiff變量為4。
如果插入節(jié)點長度小于4，并且原后驅節(jié)點e2的prevlen屬性長度為5，則這時設置forcelarge為1，代表強制保持后驅節(jié)點e2的prevlen屬性長度不變。讀者可以思考一下，為什么要這樣設計？
繼續(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é)點申請空間。新ziplist的內(nèi)存大小為curlen+reqlen+nextdiff（curlen變量為插入前ziplist長度）。將p重新賦值為zl+offset（offset變量為插入節(jié)點的偏移量），是因為ziplistResize函數(shù)可能會為ziplist申請新的內(nèi)存地址。
下面針對存在后驅節(jié)點的場景進行處理。
【6】將插入位置后面所有的節(jié)點后移，為插入節(jié)點騰出空間。移動空間的起始地址為p-nextdiff，減去nextdiff是因為后驅節(jié)點的prevlen屬性需要調(diào)整nextdiff長度。移動空間的長度為curlen-offset-1+nextdiff，減1是因為最后的結束標志節(jié)點已經(jīng)在ziplistResize函數(shù)中設置了。
memmove是C語言提供的內(nèi)存移動函數(shù)。
【7】修改后驅節(jié)點的prevlen屬性。
【8】更新ziplist.zltail，將其加上reqlen的值。
【9】如果存在多個后驅節(jié)點，則ziplist.zltail還要加上nextdiff的值。
如果只有一個后驅節(jié)點，則不需要加上nextdiff，因為這時后驅節(jié)點大小變化了nextdiff，但后驅節(jié)點只移動了reqlen。

提示：zipEntry函數(shù)會將給定節(jié)點的所有信息賦值到zlentry結構體中。zlentry結構體用于在計算過程中存放節(jié)點信息，實際存儲數(shù)據(jù)格式并不使用該結構體。讀者不要被tail這個變量名誤導，它只是指向插入節(jié)點的后驅節(jié)點，并不一定指向尾節(jié)點。

【10】這里針對不存在后驅節(jié)點的場景進行處理，只需更新最后一個節(jié)點偏移量ziplist.zltail。
【11】級聯(lián)更新。
【12】寫入插入數(shù)據(jù)。
【13】更新ziplist節(jié)點數(shù)量ziplist.zllen。

解釋一下以下代碼：

ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);

intrev32ifbe函數(shù)完成以下工作：如果主機使用的小端字節(jié)序，則不做處理。如果主機使用的大端字節(jié)序，則反轉數(shù)據(jù)字節(jié)序（數(shù)據(jù)第1位與第4位、第2位與第3位交換），這樣會將大端字節(jié)序數(shù)據(jù)轉化為小端字節(jié)序，或者將小端字節(jié)序數(shù)據(jù)轉化為大端字節(jié)序。
在上面的代碼中，如果主機CPU使用的是小端字節(jié)序，則intrev32ifbe函數(shù)不做任何處理。
如果主機CPU使用的是大端字節(jié)序，則從內(nèi)存取出數(shù)據(jù)后，先調(diào)用intrev32ifbe函數(shù)將數(shù)據(jù)轉化為大端字節(jié)序后再計算。計算完成后，調(diào)用intrev32ifbe函數(shù)將數(shù)據(jù)轉化為小端字節(jié)序后再存入內(nèi)存。

級聯(lián)更新

例2-1：
考慮一種極端場景，在ziplist的e2節(jié)點前插入一個新的節(jié)點ne，元素數(shù)據(jù)長度為254，如圖2-3所示。

插入節(jié)點如圖2-4所示。

插入節(jié)點后e2的prevlen屬性長度需要更新為5字節(jié)。
注意e3的prevlen，插入前e2的長度為253，所以e3的prevlen屬性長度為1字節(jié)，插入新節(jié)點后，e2的長度為257，那么e3的prevlen屬性長度也要更新了，這就是級聯(lián)更新。在極端情況下，e3后續(xù)的節(jié)點也要繼續(xù)更新prevlen屬性。
我們看一下級聯(lián)更新的實現(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ù)說明：

p：p指向插入節(jié)點的后驅節(jié)點，為了描述方便，下面將p指向的節(jié)點稱為當前節(jié)點。

【1】如果遇到ZIP_END，則退出循環(huán)。
【2】如果下一個節(jié)點是ZIP_END，則退出。
rawlen變量為當前節(jié)點長度，rawlensize變量為當前節(jié)點長度占用的字節(jié)數(shù)。
p[rawlen]即p的后驅節(jié)點的第一個字節(jié)。
【3】計算后驅節(jié)點信息。如果后驅節(jié)點的prevlen等于當前節(jié)點的長度，則退出。
【4】假設存儲當前節(jié)點長度需要使用actprevlen（1或者5）個字節(jié)，這里需要處理3種情況。情況1：后驅節(jié)點的prevlen屬性長度小于actprevlen，這時需要擴容，如例2-1中的場景。
【5】重新為ziplist分配內(nèi)存。
【6】如果后驅節(jié)點非ZIP_END，則需要修改ziplist.zltail屬性。
【7】將當前節(jié)點后面所有的節(jié)點后移，騰出空間用來修改后驅節(jié)點的prevlen。
【8】將p指針指向后驅節(jié)點，繼續(xù)處理后面節(jié)點的prevlen。
【9】情況2：后驅節(jié)點的prevlen屬性長度大于actprevlen，這時需要縮容。為了不讓級聯(lián)更新繼續(xù)下去，這時強制后驅節(jié)點的prevlen保持不變。
【10】情況3：后驅節(jié)點的prevlen屬性長度等于actprevlen，只要修改后驅節(jié)點prevlen值，不需要調(diào)整ziplist的大小。
【11】情況2和情況3中級聯(lián)更新不需要繼續(xù)，退出。
回到上面__ziplistInsert函數(shù)中為什么要設置forcelarge為1的問題，這樣是為了避免插入小節(jié)點時，導致級聯(lián)更新現(xiàn)象的出現(xiàn)，所以強制保持后驅節(jié)點的prevlen屬性長度不變。

從上面的分析我們可以看到，級聯(lián)更新下的性能是非常糟糕的，而且代碼復雜度也高，那么怎么解決這個問題呢？我們先看一下為什么需要使用prevlen這個屬性？這是因為反向遍歷時，每向前跨過一個節(jié)點，都必須知道前面這個節(jié)點的長度。
既然這樣，我們把每個節(jié)點長度都保存一份到節(jié)點的最后位置，反向遍歷時，直接從前一個節(jié)點的最后位置獲取前一個節(jié)點的長度不就可以了嗎？而且這樣每個節(jié)點都是獨立的，插入或刪除節(jié)點都不會有級聯(lián)更新的現(xiàn)象。基于這種設計，Redis作者設計另一種結構listpack。設計listpack的目的是取代ziplist，但是ziplist使用范圍比較廣，替換起來比較復雜，所以目前只應用在新增加的Stream結構中。等到我們分析Stream時再討論listpack的設計。由此可見，優(yōu)秀的設計并不是一蹴而就的。
ziplist提供常用函數(shù)如表2-1所示。

函數(shù)	作用
ziplistNew	創(chuàng)建一個空的ziplist
ziplistPush	在ziplist頭部或尾部添加元素
ziplistInsert	插入元素到ziplist指定位置
ziplistFind	查找給定的元素
ziplistDelete	刪除給定節(jié)點

即使使用新的listpack格式，每插入一個新節(jié)點，也還可能需要進行兩次內(nèi)存拷貝。
（1）為整個鏈表分配新內(nèi)存空間，主要是為新節(jié)點創(chuàng)建空間。
（2）將插入節(jié)點所有后驅節(jié)點后移，為插入節(jié)點騰出空間。
如果鏈表很長，則每次插入或刪除節(jié)點時都需要進行大量的內(nèi)存拷貝，這個性能是無法接受的，那么如何解決這個問題呢？這時就要用到quicklist了。