Redis中內部數據結構quicklist的作用是什么

Redis中內部數據結構quicklist的作用是什么，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。

quicklist概述

Redis對外暴露的上層list數據類型，經常被用作隊列使用。比如它支持的如下一些操作：

• lpush: 在左側（即列表頭部）插入數據。

• rpop: 在右側（即列表尾部）刪除數據。

• rpush: 在右側（即列表尾部）插入數據。

• lpop: 在左側（即列表頭部）刪除數據。

這些操作都是O(1)時間復雜度的。

當然，list也支持在任意中間位置的存取操作，比如lindex和linsert，但它們都需要對list進行遍歷，所以時間復雜度較高，為O(N)。

概況起來，list具有這樣的一些特點：它是一個能維持數據項先后順序的列表（各個數據項的先后順序由插入位置決定），便于在表的兩端追加和刪除數據，而對于中間位置的存取具有O(N)的時間復雜度。這不正是一個雙向鏈表所具有的特點嗎？

list的內部實現quicklist正是一個雙向鏈表。在quicklist.c的文件頭部注釋中，是這樣描述quicklist的：

A doubly linked list of ziplists

它確實是一個雙向鏈表，而且是一個ziplist的雙向鏈表。

這是什么意思呢？

我們知道，雙向鏈表是由多個節點（Node）組成的。這個描述的意思是：quicklist的每個節點都是一個ziplist。ziplist我們已經在 上一篇介紹過。

ziplist本身也是一個能維持數據項先后順序的列表（按插入位置），而且是一個內存緊縮的列表（各個數據項在內存上前后相鄰）。比如，一個包含3個節點的quicklist，如果每個節點的ziplist又包含4個數據項，那么對外表現上，這個list就總共包含12個數據項。

quicklist的結構為什么這樣設計呢？總結起來，大概又是一個空間和時間的折中：

• 雙向鏈表便于在表的兩端進行push和pop操作，但是它的內存開銷比較大。首先，它在每個節點上除了要保存數據之外，還要額外保存兩個指針；其次，雙向鏈表的各個節點是單獨的內存塊，地址不連續，節點多了容易產生內存碎片。

• ziplist由于是一整塊連續內存，所以存儲效率很高。但是，它不利于修改操作，每次數據變動都會引發一次內存的realloc。特別是當ziplist長度很長的時候，一次realloc可能會導致大批量的數據拷貝，進一步降低性能。

于是，結合了雙向鏈表和ziplist的優點，quicklist就應運而生了。

不過，這也帶來了一個新問題：到底一個quicklist節點包含多長的ziplist合適呢？比如，同樣是存儲12個數據項，既可以是一個quicklist包含3個節點，而每個節點的ziplist又包含4個數據項，也可以是一個quicklist包含6個節點，而每個節點的ziplist又包含2個數據項。

這又是一個需要找平衡點的難題。我們只從存儲效率上分析一下：

• 每個quicklist節點上的ziplist越短，則內存碎片越多。內存碎片多了，有可能在內存中產生很多無法被利用的小碎片，從而降低存儲效率。這種情況的極端是每個quicklist節點上的ziplist只包含一個數據項，這就蛻化成一個普通的雙向鏈表了。

• 每個quicklist節點上的ziplist越長，則為ziplist分配大塊連續內存空間的難度就越大。有可能出現內存里有很多小塊的空閑空間（它們加起來很多），但卻找不到一塊足夠大的空閑空間分配給ziplist的情況。這同樣會降低存儲效率。這種情況的極端是整個quicklist只有一個節點，所有的數據項都分配在這僅有的一個節點的ziplist里面。這其實蛻化成一個ziplist了。

可見，一個quicklist節點上的ziplist要保持一個合理的長度。那到底多長合理呢？這可能取決于具體應用場景。實際上，Redis提供了一個配置參數list-max-ziplist-size，就是為了讓使用者可以來根據自己的情況進行調整。

list-max-ziplist-size -2

我們來詳細解釋一下這個參數的含義。它可以取正值，也可以取負值。

當取正值的時候，表示按照數據項個數來限定每個quicklist節點上的ziplist長度。比如，當這個參數配置成5的時候，表示每個quicklist節點的ziplist最多包含5個數據項。

當取負值的時候，表示按照占用字節數來限定每個quicklist節點上的ziplist長度。這時，它只能取-1到-5這五個值，每個值含義如下：

• -5: 每個quicklist節點上的ziplist大小不能超過64 Kb。（注：1kb => 1024 bytes）

• -4: 每個quicklist節點上的ziplist大小不能超過32 Kb。

• -3: 每個quicklist節點上的ziplist大小不能超過16 Kb。

• -2: 每個quicklist節點上的ziplist大小不能超過8 Kb。（-2是Redis給出的默認值）

• -1: 每個quicklist節點上的ziplist大小不能超過4 Kb。

另外，list的設計目標是能夠用來存儲很長的數據列表的。比如，Redis官網給出的這個教程： Writing a simple Twitter clone with PHP and Redis，就是使用list來存儲類似Twitter的timeline數據。

當列表很長的時候，最容易被訪問的很可能是兩端的數據，中間的數據被訪問的頻率比較低（訪問起來性能也很低）。如果應用場景符合這個特點，那么list還提供了一個選項，能夠把中間的數據節點進行壓縮，從而進一步節省內存空間。Redis的配置參數list-compress-depth就是用來完成這個設置的。

list-compress-depth 0

這個參數表示一個quicklist兩端不被壓縮的節點個數。注：這里的節點個數是指quicklist雙向鏈表的節點個數，而不是指ziplist里面的數據項個數。實際上，一個quicklist節點上的ziplist，如果被壓縮，就是整體被壓縮的。

參數list-compress-depth的取值含義如下：

• 0: 是個特殊值，表示都不壓縮。這是Redis的默認值。

• 1: 表示quicklist兩端各有1個節點不壓縮，中間的節點壓縮。

• 2: 表示quicklist兩端各有2個節點不壓縮，中間的節點壓縮。

• 3: 表示quicklist兩端各有3個節點不壓縮，中間的節點壓縮。

• 依此類推…

由于0是個特殊值，很容易看出quicklist的頭節點和尾節點總是不被壓縮的，以便于在表的兩端進行快速存取。

Redis對于quicklist內部節點的壓縮算法，采用的 LZF——一種無損壓縮算法。

quicklist的數據結構定義

quicklist相關的數據結構定義可以在quicklist.h中找到：

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned int len;           /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

quicklistNode結構代表quicklist的一個節點，其中各個字段的含義如下：

• prev: 指向鏈表前一個節點的指針。

• next: 指向鏈表后一個節點的指針。

• zl: 數據指針。如果當前節點的數據沒有壓縮，那么它指向一個ziplist結構；否則，它指向一個quicklistLZF結構。

• sz: 表示zl指向的ziplist的總大小（包括zlbytes, zltail, zllen, zlend和各個數據項）。需要注意的是：如果ziplist被壓縮了，那么這個sz的值仍然是壓縮前的ziplist大小。

• count: 表示ziplist里面包含的數據項個數。這個字段只有16bit。稍后我們會一起計算一下這16bit是否夠用。

• encoding: 表示ziplist是否壓縮了（以及用了哪個壓縮算法）。目前只有兩種取值：2表示被壓縮了（而且用的是 LZF壓縮算法），1表示沒有壓縮。

• container: 是一個預留字段。本來設計是用來表明一個quicklist節點下面是直接存數據，還是使用ziplist存數據，或者用其它的結構來存數據（用作一個數據容器，所以叫container）。但是，在目前的實現中，這個值是一個固定的值2，表示使用ziplist作為數據容器。

• recompress: 當我們使用類似lindex這樣的命令查看了某一項本來壓縮的數據時，需要把數據暫時解壓，這時就設置recompress=1做一個標記，等有機會再把數據重新壓縮。

• attempted_compress: 這個值只對Redis的自動化測試程序有用。我們不用管它。

• extra: 其它擴展字段。目前Redis的實現里也沒用上。

quicklistLZF結構表示一個被壓縮過的ziplist。其中：

• sz: 表示壓縮后的ziplist大小。

• compressed: 是個柔性數組（ flexible array member），存放壓縮后的ziplist字節數組。

真正表示quicklist的數據結構是同名的quicklist這個struct：

• head: 指向頭節點（左側第一個節點）的指針。

• tail: 指向尾節點（右側第一個節點）的指針。

• count: 所有ziplist數據項的個數總和。

• len: quicklist節點的個數。

• fill: 16bit，ziplist大小設置，存放list-max-ziplist-size參數的值。

• compress: 16bit，節點壓縮深度設置，存放list-compress-depth參數的值。

上圖是一個quicklist的結構圖舉例。圖中例子對應的ziplist大小配置和節點壓縮深度配置，如下：

list-max-ziplist-size 3
list-compress-depth 2

這個例子中我們需要注意的幾點是：

• 兩端各有2個橙黃色的節點，是沒有被壓縮的。它們的數據指針zl指向真正的ziplist。中間的其它節點是被壓縮過的，它們的數據指針zl指向被壓縮后的ziplist結構，即一個quicklistLZF結構。

• 左側頭節點上的ziplist里有2項數據，右側尾節點上的ziplist里有1項數據，中間其它節點上的ziplist里都有3項數據（包括壓縮的節點內部）。這表示在表的兩端執行過多次push和pop操作后的一個狀態。

現在我們來大概計算一下quicklistNode結構中的count字段這16bit是否夠用。

我們已經知道，ziplist大小受到list-max-ziplist-size參數的限制。按照正值和負值有兩種情況：

• 當這個參數取正值的時候，就是恰好表示一個quicklistNode結構中zl所指向的ziplist所包含的數據項的最大值。list-max-ziplist-size參數是由quicklist結構的fill字段來存儲的，而fill字段是16bit，所以它所能表達的值能夠用16bit來表示。

• 當這個參數取負值的時候，能夠表示的ziplist最大長度是64 Kb。而ziplist中每一個數據項，最少需要2個字節來表示：1個字節的prevrawlen，1個字節的data（len字段和data合二為一；詳見 上一篇）。所以，ziplist中數據項的個數不會超過32 K，用16bit來表達足夠了。

實際上，在目前的quicklist的實現中，ziplist的大小還會受到另外的限制，根本不會達到這里所分析的最大值。

下面進入代碼分析階段。

quicklist的創建

當我們使用lpush或rpush命令第一次向一個不存在的list里面插入數據的時候，Redis會首先調用quicklistCreate接口創建一個空的quicklist。

quicklist *quicklistCreate(void) {
    struct quicklist *quicklist;
    quicklist = zmalloc(sizeof(*quicklist));
    quicklist->head = quicklist->tail = NULL;
    quicklist->len = 0;
    quicklist->count = 0;
    quicklist->compress = 0;
    quicklist->fill = -2;
    return quicklist;
}

在很多介紹數據結構的書上，實現雙向鏈表的時候經常會多增加一個空余的頭節點，主要是為了插入和刪除操作的方便。從上面quicklistCreate的代碼可以看出，quicklist是一個不包含空余頭節點的雙向鏈表（head和tail都初始化為NULL）。

quicklist的push操作

quicklist的push操作是調用quicklistPush來實現的。

void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
                   int where) {
    if (where == QUICKLIST_HEAD) {
        quicklistPushHead(quicklist, value, sz);
    } else if (where == QUICKLIST_TAIL) {
        quicklistPushTail(quicklist, value, sz);
    }
}
/* Add new entry to head node of quicklist.
 *
 * Returns 0 if used existing head.
 * Returns 1 if new head created. */
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        quicklistNodeUpdateSz(quicklist->head);
    } else {
        quicklistNode *node = quicklistCreateNode();
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}
/* Add new entry to tail node of quicklist.
 *
 * Returns 0 if used existing tail.
 * Returns 1 if new tail created. */
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_tail = quicklist->tail;
    if (likely(
            _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {
        quicklist->tail->zl =
            ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);
        quicklistNodeUpdateSz(quicklist->tail);
    } else {
        quicklistNode *node = quicklistCreateNode();
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);
        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
    }
    quicklist->count++;
    quicklist->tail->count++;
    return (orig_tail != quicklist->tail);
}

不管是在頭部還是尾部插入數據，都包含兩種情況：

• 如果頭節點（或尾節點）上ziplist大小沒有超過限制（即_quicklistNodeAllowInsert返回1），那么新數據被直接插入到ziplist中（調用ziplistPush）。

• 如果頭節點（或尾節點）上ziplist太大了，那么新創建一個quicklistNode節點（對應地也會新創建一個ziplist），然后把這個新創建的節點插入到quicklist雙向鏈表中（調用_quicklistInsertNodeAfter）。

在_quicklistInsertNodeAfter的實現中，還會根據list-compress-depth的配置將里面的節點進行壓縮。它的實現比較繁瑣，我們這里就不展開討論了。

quicklist的其它操作

quicklist的操作較多，且實現細節都比較繁雜，這里就不一一分析源碼了，我們簡單介紹一些比較重要的操作。

quicklist的pop操作是調用quicklistPopCustom來實現的。quicklistPopCustom的實現過程基本上跟quicklistPush相反，先從頭部或尾部節點的ziplist中把對應的數據項刪除，如果在刪除后ziplist為空了，那么對應的頭部或尾部節點也要刪除。刪除后還可能涉及到里面節點的解壓縮問題。

quicklist不僅實現了從頭部或尾部插入，也實現了從任意指定的位置插入。quicklistInsertAfter和quicklistInsertBefore就是分別在指定位置后面和前面插入數據項。這種在任意指定位置插入數據的操作，情況比較復雜，有眾多的邏輯分支。

• 當插入位置所在的ziplist大小沒有超過限制時，直接插入到ziplist中就好了；

• 當插入位置所在的ziplist大小超過了限制，但插入的位置位于ziplist兩端，并且相鄰的quicklist鏈表節點的ziplist大小沒有超過限制，那么就轉而插入到相鄰的那個quicklist鏈表節點的ziplist中；

• 當插入位置所在的ziplist大小超過了限制，但插入的位置位于ziplist兩端，并且相鄰的quicklist鏈表節點的ziplist大小也超過限制，這時需要新創建一個quicklist鏈表節點插入。

• 對于插入位置所在的ziplist大小超過了限制的其它情況（主要對應于在ziplist中間插入數據的情況），則需要把當前ziplist分裂為兩個節點，然后再其中一個節點上插入數據。

quicklistSetOptions用于設置ziplist大小配置參數（list-max-ziplist-size）和節點壓縮深度配置參數（list-compress-depth）。代碼比較簡單，就是將相應的值分別設置給quicklist結構的fill字段和compress字段。

看完上述內容，你們掌握Redis中內部數據結構quicklist的作用是什么的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！