Redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)quicklist的作用是什么
redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)quicklist的作用是什么，相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。
創(chuàng)新互聯(lián)建站專注于網(wǎng)站建設(shè)|網(wǎng)頁維護|優(yōu)化|托管以及網(wǎng)絡(luò)推廣，積累了大量的網(wǎng)站設(shè)計與制作經(jīng)驗，為許多企業(yè)提供了網(wǎng)站定制設(shè)計服務(wù)，案例作品覆蓋廣告制作等行業(yè)。能根據(jù)企業(yè)所處的行業(yè)與銷售的產(chǎn)品，結(jié)合品牌形象的塑造，量身制作品質(zhì)網(wǎng)站。
quicklist概述
Redis對外暴露的上層list數(shù)據(jù)類型，經(jīng)常被用作隊列使用。比如它支持的如下一些操作：
lpush: 在左側(cè)（即列表頭部）插入數(shù)據(jù)。rpop: 在右側(cè)（即列表尾部）刪除數(shù)據(jù)。rpush: 在右側(cè)（即列表尾部）插入數(shù)據(jù)。lpop: 在左側(cè)（即列表頭部）刪除數(shù)據(jù)。
這些操作都是O(1)時間復(fù)雜度的。
當(dāng)然，list也支持在任意中間位置的存取操作，比如lindex和linsert，但它們都需要對list進行遍歷，所以時間復(fù)雜度較高，為O(N)。
概況起來，list具有這樣的一些特點：它是一個能維持數(shù)據(jù)項先后順序的列表（各個數(shù)據(jù)項的先后順序由插入位置決定），便于在表的兩端追加和刪除數(shù)據(jù)，而對于中間位置的存取具有O(N)的時間復(fù)雜度。這不正是一個雙向鏈表所具有的特點嗎？
list的內(nèi)部實現(xiàn)quicklist正是一個雙向鏈表。在quicklist.c的文件頭部注釋中，是這樣描述quicklist的：
A doubly linked list of ziplists
它確實是一個雙向鏈表，而且是一個ziplist的雙向鏈表。
這是什么意思呢？
我們知道，雙向鏈表是由多個節(jié)點（Node）組成的。這個描述的意思是：quicklist的每個節(jié)點都是一個ziplist。ziplist我們已經(jīng)在 上一篇介紹過。
ziplist本身也是一個能維持數(shù)據(jù)項先后順序的列表（按插入位置），而且是一個內(nèi)存緊縮的列表（各個數(shù)據(jù)項在內(nèi)存上前后相鄰）。比如，一個包含3個節(jié)點的quicklist，如果每個節(jié)點的ziplist又包含4個數(shù)據(jù)項，那么對外表現(xiàn)上，這個list就總共包含12個數(shù)據(jù)項。
quicklist的結(jié)構(gòu)為什么這樣設(shè)計呢？總結(jié)起來，大概又是一個空間和時間的折中：
雙向鏈表便于在表的兩端進行push和pop操作，但是它的內(nèi)存開銷比較大。首先，它在每個節(jié)點上除了要保存數(shù)據(jù)之外，還要額外保存兩個指針；其次，雙向鏈表的各個節(jié)點是單獨的內(nèi)存塊，地址不連續(xù)，節(jié)點多了容易產(chǎn)生內(nèi)存碎片。
ziplist由于是一整塊連續(xù)內(nèi)存，所以存儲效率很高。但是，它不利于修改操作，每次數(shù)據(jù)變動都會引發(fā)一次內(nèi)存的realloc。特別是當(dāng)ziplist長度很長的時候，一次realloc可能會導(dǎo)致大批量的數(shù)據(jù)拷貝，進一步降低性能。
于是，結(jié)合了雙向鏈表和ziplist的優(yōu)點，quicklist就應(yīng)運而生了。
不過，這也帶來了一個新問題：到底一個quicklist節(jié)點包含多長的ziplist合適呢？比如，同樣是存儲12個數(shù)據(jù)項，既可以是一個quicklist包含3個節(jié)點，而每個節(jié)點的ziplist又包含4個數(shù)據(jù)項，也可以是一個quicklist包含6個節(jié)點，而每個節(jié)點的ziplist又包含2個數(shù)據(jù)項。
這又是一個需要找平衡點的難題。我們只從存儲效率上分析一下：
每個quicklist節(jié)點上的ziplist越短，則內(nèi)存碎片越多。內(nèi)存碎片多了，有可能在內(nèi)存中產(chǎn)生很多無法被利用的小碎片，從而降低存儲效率。這種情況的極端是每個quicklist節(jié)點上的ziplist只包含一個數(shù)據(jù)項，這就蛻化成一個普通的雙向鏈表了。
每個quicklist節(jié)點上的ziplist越長，則為ziplist分配大塊連續(xù)內(nèi)存空間的難度就越大。有可能出現(xiàn)內(nèi)存里有很多小塊的空閑空間（它們加起來很多），但卻找不到一塊足夠大的空閑空間分配給ziplist的情況。這同樣會降低存儲效率。這種情況的極端是整個quicklist只有一個節(jié)點，所有的數(shù)據(jù)項都分配在這僅有的一個節(jié)點的ziplist里面。這其實蛻化成一個ziplist了。
可見，一個quicklist節(jié)點上的ziplist要保持一個合理的長度。那到底多長合理呢？這可能取決于具體應(yīng)用場景。實際上，Redis提供了一個配置參數(shù)list-max-ziplist-size，就是為了讓使用者可以來根據(jù)自己的情況進行調(diào)整。
list-max-ziplist-size -2
我們來詳細解釋一下這個參數(shù)的含義。它可以取正值，也可以取負值。
當(dāng)取正值的時候，表示按照數(shù)據(jù)項個數(shù)來限定每個quicklist節(jié)點上的ziplist長度。比如，當(dāng)這個參數(shù)配置成5的時候，表示每個quicklist節(jié)點的ziplist最多包含5個數(shù)據(jù)項。
當(dāng)取負值的時候，表示按照占用字節(jié)數(shù)來限定每個quicklist節(jié)點上的ziplist長度。這時，它只能取-1到-5這五個值，每個值含義如下：
-5: 每個quicklist節(jié)點上的ziplist大小不能超過64 Kb。（注：1kb => 1024 bytes）
-4: 每個quicklist節(jié)點上的ziplist大小不能超過32 Kb。
-3: 每個quicklist節(jié)點上的ziplist大小不能超過16 Kb。
-2: 每個quicklist節(jié)點上的ziplist大小不能超過8 Kb。（-2是Redis給出的默認值）
-1: 每個quicklist節(jié)點上的ziplist大小不能超過4 Kb。
另外，list的設(shè)計目標(biāo)是能夠用來存儲很長的數(shù)據(jù)列表的。比如，Redis官網(wǎng)給出的這個教程： Writing a simple Twitter clone with PHP and Redis，就是使用list來存儲類似Twitter的timeline數(shù)據(jù)。
當(dāng)列表很長的時候，最容易被訪問的很可能是兩端的數(shù)據(jù)，中間的數(shù)據(jù)被訪問的頻率比較低（訪問起來性能也很低）。如果應(yīng)用場景符合這個特點，那么list還提供了一個選項，能夠把中間的數(shù)據(jù)節(jié)點進行壓縮，從而進一步節(jié)省內(nèi)存空間。Redis的配置參數(shù)list-compress-depth就是用來完成這個設(shè)置的。
list-compress-depth 0
這個參數(shù)表示一個quicklist兩端不被壓縮的節(jié)點個數(shù)。注：這里的節(jié)點個數(shù)是指quicklist雙向鏈表的節(jié)點個數(shù)，而不是指ziplist里面的數(shù)據(jù)項個數(shù)。實際上，一個quicklist節(jié)點上的ziplist，如果被壓縮，就是整體被壓縮的。
參數(shù)list-compress-depth的取值含義如下：
0: 是個特殊值，表示都不壓縮。這是Redis的默認值。
1: 表示quicklist兩端各有1個節(jié)點不壓縮，中間的節(jié)點壓縮。
2: 表示quicklist兩端各有2個節(jié)點不壓縮，中間的節(jié)點壓縮。
3: 表示quicklist兩端各有3個節(jié)點不壓縮，中間的節(jié)點壓縮。
依此類推…
由于0是個特殊值，很容易看出quicklist的頭節(jié)點和尾節(jié)點總是不被壓縮的，以便于在表的兩端進行快速存取。
Redis對于quicklist內(nèi)部節(jié)點的壓縮算法，采用的 LZF——一種無損壓縮算法。
quicklist的數(shù)據(jù)結(jié)構(gòu)定義
quicklist相關(guān)的數(shù)據(jù)結(jié)構(gòu)定義可以在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結(jié)構(gòu)代表quicklist的一個節(jié)點，其中各個字段的含義如下：
prev: 指向鏈表前一個節(jié)點的指針。
next: 指向鏈表后一個節(jié)點的指針。
zl: 數(shù)據(jù)指針。如果當(dāng)前節(jié)點的數(shù)據(jù)沒有壓縮，那么它指向一個ziplist結(jié)構(gòu)；否則，它指向一個quicklistLZF結(jié)構(gòu)。
sz: 表示zl指向的ziplist的總大小（包括
zlbytes,zltail,zllen,zlend和各個數(shù)據(jù)項）。需要注意的是：如果ziplist被壓縮了，那么這個sz的值仍然是壓縮前的ziplist大小。count: 表示ziplist里面包含的數(shù)據(jù)項個數(shù)。這個字段只有16bit。稍后我們會一起計算一下這16bit是否夠用。
encoding: 表示ziplist是否壓縮了（以及用了哪個壓縮算法）。目前只有兩種取值：2表示被壓縮了（而且用的是 LZF壓縮算法），1表示沒有壓縮。
container: 是一個預(yù)留字段。本來設(shè)計是用來表明一個quicklist節(jié)點下面是直接存數(shù)據(jù)，還是使用ziplist存數(shù)據(jù)，或者用其它的結(jié)構(gòu)來存數(shù)據(jù)（用作一個數(shù)據(jù)容器，所以叫container）。但是，在目前的實現(xiàn)中，這個值是一個固定的值2，表示使用ziplist作為數(shù)據(jù)容器。
recompress: 當(dāng)我們使用類似lindex這樣的命令查看了某一項本來壓縮的數(shù)據(jù)時，需要把數(shù)據(jù)暫時解壓，這時就設(shè)置recompress=1做一個標(biāo)記，等有機會再把數(shù)據(jù)重新壓縮。
attempted_compress: 這個值只對Redis的自動化測試程序有用。我們不用管它。
extra: 其它擴展字段。目前Redis的實現(xiàn)里也沒用上。
quicklistLZF結(jié)構(gòu)表示一個被壓縮過的ziplist。其中：
sz: 表示壓縮后的ziplist大小。
compressed: 是個柔性數(shù)組（ flexible array member），存放壓縮后的ziplist字節(jié)數(shù)組。
真正表示quicklist的數(shù)據(jù)結(jié)構(gòu)是同名的quicklist這個struct：
head: 指向頭節(jié)點（左側(cè)第一個節(jié)點）的指針。
tail: 指向尾節(jié)點（右側(cè)第一個節(jié)點）的指針。
count: 所有ziplist數(shù)據(jù)項的個數(shù)總和。
len: quicklist節(jié)點的個數(shù)。
fill: 16bit，ziplist大小設(shè)置，存放
list-max-ziplist-size參數(shù)的值。compress: 16bit，節(jié)點壓縮深度設(shè)置，存放
list-compress-depth參數(shù)的值。
上圖是一個quicklist的結(jié)構(gòu)圖舉例。圖中例子對應(yīng)的ziplist大小配置和節(jié)點壓縮深度配置，如下：
list-max-ziplist-size 3 list-compress-depth 2
這個例子中我們需要注意的幾點是：
兩端各有2個橙黃色的節(jié)點，是沒有被壓縮的。它們的數(shù)據(jù)指針zl指向真正的ziplist。中間的其它節(jié)點是被壓縮過的，它們的數(shù)據(jù)指針zl指向被壓縮后的ziplist結(jié)構(gòu)，即一個quicklistLZF結(jié)構(gòu)。
左側(cè)頭節(jié)點上的ziplist里有2項數(shù)據(jù)，右側(cè)尾節(jié)點上的ziplist里有1項數(shù)據(jù)，中間其它節(jié)點上的ziplist里都有3項數(shù)據(jù)（包括壓縮的節(jié)點內(nèi)部）。這表示在表的兩端執(zhí)行過多次
push和pop操作后的一個狀態(tài)。
現(xiàn)在我們來大概計算一下quicklistNode結(jié)構(gòu)中的count字段這16bit是否夠用。
我們已經(jīng)知道，ziplist大小受到list-max-ziplist-size參數(shù)的限制。按照正值和負值有兩種情況：
當(dāng)這個參數(shù)取正值的時候，就是恰好表示一個quicklistNode結(jié)構(gòu)中zl所指向的ziplist所包含的數(shù)據(jù)項的最大值。
list-max-ziplist-size參數(shù)是由quicklist結(jié)構(gòu)的fill字段來存儲的，而fill字段是16bit，所以它所能表達的值能夠用16bit來表示。當(dāng)這個參數(shù)取負值的時候，能夠表示的ziplist最大長度是64 Kb。而ziplist中每一個數(shù)據(jù)項，最少需要2個字節(jié)來表示：1個字節(jié)的
prevrawlen，1個字節(jié)的data（len字段和data合二為一；詳見 上一篇）。所以，ziplist中數(shù)據(jù)項的個數(shù)不會超過32 K，用16bit來表達足夠了。
實際上，在目前的quicklist的實現(xiàn)中，ziplist的大小還會受到另外的限制，根本不會達到這里所分析的最大值。
下面進入代碼分析階段。
quicklist的創(chuàng)建
當(dāng)我們使用lpush或rpush命令第一次向一個不存在的list里面插入數(shù)據(jù)的時候，Redis會首先調(diào)用quicklistCreate接口創(chuàng)建一個空的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;
}在很多介紹數(shù)據(jù)結(jié)構(gòu)的書上，實現(xiàn)雙向鏈表的時候經(jīng)常會多增加一個空余的頭節(jié)點，主要是為了插入和刪除操作的方便。從上面quicklistCreate的代碼可以看出，quicklist是一個不包含空余頭節(jié)點的雙向鏈表（head和tail都初始化為NULL）。
quicklist的push操作
quicklist的push操作是調(diào)用quicklistPush來實現(xiàn)的。
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);
}不管是在頭部還是尾部插入數(shù)據(jù)，都包含兩種情況：
如果頭節(jié)點（或尾節(jié)點）上ziplist大小沒有超過限制（即
_quicklistNodeAllowInsert返回1），那么新數(shù)據(jù)被直接插入到ziplist中（調(diào)用ziplistPush）。如果頭節(jié)點（或尾節(jié)點）上ziplist太大了，那么新創(chuàng)建一個quicklistNode節(jié)點（對應(yīng)地也會新創(chuàng)建一個ziplist），然后把這個新創(chuàng)建的節(jié)點插入到quicklist雙向鏈表中（調(diào)用
_quicklistInsertNodeAfter）。
在_quicklistInsertNodeAfter的實現(xiàn)中，還會根據(jù)list-compress-depth的配置將里面的節(jié)點進行壓縮。它的實現(xiàn)比較繁瑣，我們這里就不展開討論了。
quicklist的其它操作
quicklist的操作較多，且實現(xiàn)細節(jié)都比較繁雜，這里就不一一分析源碼了，我們簡單介紹一些比較重要的操作。
quicklist的pop操作是調(diào)用quicklistPopCustom來實現(xiàn)的。quicklistPopCustom的實現(xiàn)過程基本上跟quicklistPush相反，先從頭部或尾部節(jié)點的ziplist中把對應(yīng)的數(shù)據(jù)項刪除，如果在刪除后ziplist為空了，那么對應(yīng)的頭部或尾部節(jié)點也要刪除。刪除后還可能涉及到里面節(jié)點的解壓縮問題。
quicklist不僅實現(xiàn)了從頭部或尾部插入，也實現(xiàn)了從任意指定的位置插入。quicklistInsertAfter和quicklistInsertBefore就是分別在指定位置后面和前面插入數(shù)據(jù)項。這種在任意指定位置插入數(shù)據(jù)的操作，情況比較復(fù)雜，有眾多的邏輯分支。
當(dāng)插入位置所在的ziplist大小沒有超過限制時，直接插入到ziplist中就好了；
當(dāng)插入位置所在的ziplist大小超過了限制，但插入的位置位于ziplist兩端，并且相鄰的quicklist鏈表節(jié)點的ziplist大小沒有超過限制，那么就轉(zhuǎn)而插入到相鄰的那個quicklist鏈表節(jié)點的ziplist中；
當(dāng)插入位置所在的ziplist大小超過了限制，但插入的位置位于ziplist兩端，并且相鄰的quicklist鏈表節(jié)點的ziplist大小也超過限制，這時需要新創(chuàng)建一個quicklist鏈表節(jié)點插入。
對于插入位置所在的ziplist大小超過了限制的其它情況（主要對應(yīng)于在ziplist中間插入數(shù)據(jù)的情況），則需要把當(dāng)前ziplist分裂為兩個節(jié)點，然后再其中一個節(jié)點上插入數(shù)據(jù)。
quicklistSetOptions用于設(shè)置ziplist大小配置參數(shù)（list-max-ziplist-size）和節(jié)點壓縮深度配置參數(shù)（list-compress-depth）。代碼比較簡單，就是將相應(yīng)的值分別設(shè)置給quicklist結(jié)構(gòu)的fill字段和compress字段。
看完上述內(nèi)容，你們掌握Redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)quicklist的作用是什么的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！
分享標(biāo)題：Redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)quicklist的作用是什么
網(wǎng)頁網(wǎng)址：http://bm7419.com/article32/pcghsc.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護、品牌網(wǎng)站設(shè)計、企業(yè)網(wǎng)站制作、域名注冊、用戶體驗、云服務(wù)器
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
- 交互設(shè)計與網(wǎng)站設(shè)計。 2018-12-23
- 移動網(wǎng)站建設(shè)時要注意視覺的設(shè)計及優(yōu)化 2016-10-05
- 這7個網(wǎng)站設(shè)計元素或許有助于或影響您的轉(zhuǎn)換率 2022-09-30
- 手機APP設(shè)計制作定律（二） 2016-11-04
- 極簡主義的網(wǎng)站設(shè)計需要哪些元素來搭配? 2015-01-25
- 簡潔的網(wǎng)站設(shè)計會是未來的趨勢 2023-01-28
- 在網(wǎng)站設(shè)計中使用好邊框的作用 2021-05-28
- 微型網(wǎng)站設(shè)計時需要掌握什么重點？ 2015-01-11
- 如何做好商城網(wǎng)站設(shè)計 2013-08-30
- 成都網(wǎng)站設(shè)計：怎樣有效降低更新網(wǎng)站帶來的損失？ 2022-06-22
- 網(wǎng)站設(shè)計應(yīng)該注意什么？ 2018-12-12
- 東營網(wǎng)站設(shè)計制作：教你如何才能設(shè)計出一個更美的網(wǎng)站？ 2021-11-26