[TOC] ## 概述 Redis中的List是一個有序（按加入的時序排序）的數據結構，一般有序我們會采用數組或者是雙向鏈表，其中雙向鏈表由于有前后指針實際上會很浪費內存, 3.2版本之前采用兩種數據結構作為底層實現： * 壓縮列表ziplist： `ziplist`存儲在一段連續的內存上，所以存儲效率很高。但是，它不利于修改操作，插入和刪除操作需要頻繁的申請和釋放內存。特別是當`ziplist`長度很長的時候，一次`realloc`可能會導致大批量的數據拷貝。 * 雙向鏈表linkedlist：雙向鏈表`linkedlist`便于在表的兩端進行`push`和`pop`操作，在插入節點上復雜度很低，但是它的內存開銷比較大。首先，它在每個節點上除了要保存數據之外，還要額外保存兩個指針；其次，雙向鏈表的各個節點是單獨的內存塊，地址不連續，節點多了容易產生內存碎片。 3.2版本之后升級為quicklist。`ziplist`會引入頻繁的內存申請和釋放，而linkedlist由于指針也會造成內存的浪費，而且每個節點是單獨存在的，會造成很多內存碎片，所以結合兩個結構的特點，設計了quickList。 `quickList` 是一個 `ziplist` 組成的雙向鏈表。每個節點使用 `ziplist` 來保存數據。本質上來說，`quicklist` 里面保存著一個一個小的 `ziplist`。  ## quicklist數據結構 ``` 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 quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* total count of all entries in all ziplists */ unsigned long len; /* number of quicklistNodes */ int fill : QL_FILL_BITS; /* fill factor for individual nodes */ unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */ unsigned int bookmark_count: QL_BM_BITS; quicklistBookmark bookmarks[]; } quicklist; ``` `quicklistNode`結構為節點類型： * prev：指向前驅節點 * next：指向后繼節點 * zl：指向對應的壓縮列表 * sz：壓縮列表的大小 * encoding：采用的編碼方式，1為原生，2代表使用LZF進行壓縮 * container：為節點指向的容器類型，1代表none，2代表ziplist存儲數據 * recompress：代表這個節點是否是壓縮節點，如果是，則使用壓縮節點前先進行解壓縮，使用后重新壓縮 * attempted_compress：測試時使用 `quicklist`結構為雙向鏈表類型： * head：指向頭節點 * tail：指向尾節點 * count：quicklist中壓縮列表的entry總數 * len：節點個數 * fill：每個節點的ziplist長度，可以通過參數`list-max-ziplist-size`配置節點所占內存大小 * compress：該值表示兩端各有compress個節點不壓縮 ## 參數配置 ### 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-compress-depth ``` list-compress-depth?0 ``` **這個參數表示一個quicklist兩端不被壓縮的節點個數**。注：這里的節點個數是指quicklist雙向鏈表的節點個數，而不是指ziplist里面的數據項個數。實際上，一個quicklist節點上的ziplist，如果被壓縮，就是整體被壓縮的。 * 0: 是個特殊值，表示都不壓縮。這是Redis的默認值。 * 1: 表示quicklist兩端各有1個節點不壓縮，中間的節點壓縮。 * 2: 表示quicklist兩端各有2個節點不壓縮，中間的節點壓縮。 * 3: 表示quicklist兩端各有3個節點不壓縮，中間的節點壓縮。 * 依此類推… 由于0是個特殊值，很容易看出quicklist的頭節點和尾節點總是不被壓縮的，以便于在表的兩端進行快速存取。Redis對于quicklist內部節點的壓縮算法，采用的[LZF](http://oldhome.schmorp.de/marc/liblzf.html)——一種無損壓縮算法。 ## 優點 結合了list和ziplist的優點。quicklist表示的是一個鏈表節點里存放的是一個ziplist。 ## 應用場景 redis3.2版本后的list數據結構底層用的是quicklist