前言

最近在看《Redis的設(shè)計(jì)與實(shí)現(xiàn)》這本書(shū)，寫(xiě)的真的是太好了，一下子就看入迷了，謝謝作者。不過(guò)在學(xué)習(xí)的時(shí)候發(fā)現(xiàn)一個(gè)問(wèn)題，我服務(wù)器上安裝的是Redis5.0.9版本的，而作者介紹的是Redis3.0版本的，在第一部分將數(shù)據(jù)結(jié)構(gòu)與對(duì)象章節(jié)的時(shí)候，出現(xiàn)了一些差別，就是在redis對(duì)外暴露的list結(jié)構(gòu)底層使用的數(shù)據(jù)結(jié)構(gòu)問(wèn)題。由于書(shū)上沒(méi)有記錄，所以就在網(wǎng)上查閱了些資料學(xué)習(xí)了一下， 自己再做個(gè)總結(jié)，當(dāng)做自己的筆記。

差別

出現(xiàn)的差別就是，在redis3.2版本之前，它使用的是ziplist和linkedlist編碼作為列表鍵的底層實(shí)現(xiàn)，在它之后，就采用了一個(gè)叫做quicklist的數(shù)據(jù)結(jié)構(gòu)來(lái)作其底層實(shí)現(xiàn)。
先來(lái)介紹下redis3.2之前的版本的知識(shí)點(diǎn)：
在使用ziplist和linkedlist作為列表鍵底層實(shí)現(xiàn)的時(shí)候，他們之間會(huì)有一個(gè)選擇標(biāo)準(zhǔn)：
選擇ziplist的時(shí)候：

• 列表對(duì)象保存的所有字符串元素的長(zhǎng)度都小于64字節(jié)；
• 列表對(duì)象保存的元素量小于512個(gè)

上面的是選擇ziplist作為底層實(shí)現(xiàn)所必須滿足的條件，如果沒(méi)滿足的話就選用linkedlist作為其底層實(shí)現(xiàn)。

127.0.0.1:6379> rpush blah "hello" "world" "again"
3
127.0.0.1:6379> object encoding blah
ziplist
127.0.0.1:6379> rpush blah "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww"
4
127.0.0.1:6379> object encoding blah
linkedlist

再來(lái)介紹下redis3.2之后的版本：

這個(gè)涉及到quicklist這個(gè)數(shù)據(jù)結(jié)構(gòu)了，書(shū)上沒(méi)有記錄，所以我查了下資料，也總結(jié)到自己的博客當(dāng)中。

我安裝的時(shí)候redis5.0.9版本的，所以上面的幾個(gè)指令執(zhí)行的結(jié)果會(huì)有所不同

127.0.0.1:6379> rpush blah "hello" "world" "again"
3
127.0.0.1:6379> object encoding blah
quicklist
127.0.0.1:6379> rpush blah "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww"
4
127.0.0.1:6379> object encoding blah
quicklist

quicklist數(shù)據(jù)結(jié)構(gòu)的介紹

ziplist和linkedlist就不介紹了，書(shū)本上有，我們來(lái)看看quicklist。
quicklist其實(shí)現(xiàn)也是依賴于ziplist和linkedlist來(lái)實(shí)現(xiàn)的，它是兩個(gè)結(jié)構(gòu)的結(jié)合。它將ziplist來(lái)進(jìn)行分段存儲(chǔ)，也就是分成一個(gè)個(gè)的quicklistNode節(jié)點(diǎn)來(lái)進(jìn)行存儲(chǔ)。每個(gè)quicklistNode指向一個(gè)ziplist，然后quicklistNode之間是通過(guò)雙向指針來(lái)進(jìn)行連接的。我們來(lái)看下大致的結(jié)構(gòu)：

看到這個(gè)結(jié)構(gòu)可能會(huì)有些疑問(wèn)：

• 這個(gè)結(jié)構(gòu)啥意思啊，為什么有的節(jié)點(diǎn)是ziplist，有的是quicklistZF？
• 為什么quicklist頭部和尾部各有兩個(gè)節(jié)點(diǎn)是ziplist，剩下中間的是quicklistZF？
• 為什么每個(gè)quicklistNode節(jié)點(diǎn)的ziplist內(nèi)部的數(shù)據(jù)個(gè)數(shù)不一致呢？

為什么要把底層數(shù)據(jù)結(jié)構(gòu)優(yōu)化成quicklist？

在解決上面的問(wèn)題之前我們先來(lái)解決一個(gè)首要的問(wèn)題，也就是redis為什么要把列表鍵的底層數(shù)據(jù)結(jié)構(gòu)優(yōu)化成quicklist？
其實(shí)可以從兩個(gè)方面來(lái)考慮這個(gè)原因：

• ziplist這個(gè)結(jié)構(gòu)，它內(nèi)部的數(shù)據(jù)存儲(chǔ)是一段連續(xù)的空間，這樣的話，就要求很大一塊內(nèi)存空間。就比如說(shuō)，我們想存儲(chǔ)很多的數(shù)據(jù)，但是內(nèi)存中并沒(méi)有符合要求的連續(xù)的存儲(chǔ)空間，而是存在很多不連續(xù)的小空間（加起來(lái)可以符合要求）。
• 再來(lái)說(shuō)說(shuō)linkedlist這個(gè)結(jié)構(gòu)，它數(shù)據(jù)存儲(chǔ)不要求連續(xù)，就可以避免上面的弊端，不過(guò)這樣以來(lái)，每個(gè)節(jié)點(diǎn)都分配一個(gè)一塊內(nèi)存，那就有可能造成大量的內(nèi)存碎片。

綜上兩個(gè)考慮，redis在3.2版本以后就對(duì)此情況進(jìn)行了優(yōu)化，就出來(lái)了quicklist這個(gè)數(shù)據(jù)結(jié)構(gòu)，quicklist其實(shí)就是一個(gè)分段的ziplist，為什么這么說(shuō)呢？其實(shí)quicklist存儲(chǔ)數(shù)據(jù)基本單位是quicklistNode，每個(gè)quicklistNode的內(nèi)容區(qū)就是以ziplist數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的。也就是上面圖示展示的。

為什么每個(gè)quicklistNode節(jié)點(diǎn)的ziplist內(nèi)部的數(shù)據(jù)個(gè)數(shù)不一致呢？

現(xiàn)在轉(zhuǎn)化到quicklist了，但是還需要考慮，quicklistNode里的ziplist里的內(nèi)容處理呢？一個(gè)ziplist我需要存儲(chǔ)多少個(gè)數(shù)據(jù)呀？也跟上面兩個(gè)點(diǎn)考慮的一樣

• 如果ziplist里的內(nèi)容分配的越少的話，也就是往linkedlist方向發(fā)展了，就可能會(huì)產(chǎn)生很多的內(nèi)存碎片
• 但要如果ziplist里的內(nèi)容分配的越多的話，也會(huì)出現(xiàn)問(wèn)題，就是需要很大一塊連續(xù)的內(nèi)存空間。

redis設(shè)計(jì)者已經(jīng)給我們想好了，它的配置文件里有這樣一個(gè)參數(shù)：list-max-ziplist-size

看到這個(gè)配置，我們來(lái)解釋下這個(gè)參數(shù)，它既可以設(shè)置正數(shù)，也可以設(shè)置負(fù)數(shù)

當(dāng)它取正數(shù)的時(shí)候，表示按照數(shù)據(jù)項(xiàng)個(gè)數(shù)來(lái)限定quicklist節(jié)點(diǎn)上的ziplist長(zhǎng)度，比如我們?cè)O(shè)置為4，就說(shuō)明每個(gè)ziplist的數(shù)據(jù)項(xiàng)最多不能超過(guò)5個(gè)

當(dāng)它取負(fù)數(shù)的時(shí)候，表示按照占用字節(jié)來(lái)限定quicklsit節(jié)點(diǎn)上的ziplist長(zhǎng)度，這時(shí)，它只能取-1到-5這五個(gè)值，每個(gè)值的含義如下：
1)、-5：每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過(guò)64kb。（1kb == 1024 byte）
2)、-4：每個(gè)quicklsit節(jié)點(diǎn)上的ziplist大小不能超過(guò)32kb。
3)、-3：每個(gè)quicklsit節(jié)點(diǎn)上的ziplist大小不能超過(guò)16kb。
4)、-2：每個(gè)quicklsit節(jié)點(diǎn)上的ziplist大小不能超過(guò)8kb。
5)、-1：每個(gè)quicklsit節(jié)點(diǎn)上的ziplist大小不能超過(guò)4kb。

所以就會(huì)出現(xiàn)問(wèn)題所說(shuō)的，ziplist內(nèi)存存儲(chǔ)數(shù)據(jù)個(gè)數(shù)不一致的問(wèn)題，我們也可以自己手動(dòng)設(shè)置參數(shù)值。

這個(gè)結(jié)構(gòu)啥意思啊，為什么有的節(jié)點(diǎn)是ziplist，有的是quicklistZF？

這里又出現(xiàn)了一個(gè)配置參數(shù)：list-compress-depth
其實(shí)，當(dāng)鏈表很長(zhǎng)的時(shí)候，最頻繁訪問(wèn)的就是兩端的數(shù)據(jù)，中間被訪問(wèn)的頻率比較低，所以我們可以將中間部分節(jié)點(diǎn)進(jìn)行壓縮，從而能夠進(jìn)一步節(jié)省空間。上面說(shuō)的list-compress-depth就是來(lái)設(shè)置這個(gè)的。
這個(gè)參數(shù)的取值含義如下：

0：是個(gè)特殊值，表示都不壓縮。這是redis的默認(rèn)值

1：表示quicklist兩端各有一個(gè)節(jié)點(diǎn)不被壓縮，中間節(jié)點(diǎn)進(jìn)行壓縮

2：表示quicklist兩端各有兩個(gè)節(jié)點(diǎn)不被壓縮，中間節(jié)點(diǎn)進(jìn)行壓縮

3：表示quicklist兩端各有三個(gè)節(jié)點(diǎn)不被壓縮，中間節(jié)點(diǎn)進(jìn)行壓縮…

以此類(lèi)推

也就是會(huì)出現(xiàn)問(wèn)題所說(shuō)的，兩端節(jié)點(diǎn)為ziplist，中間節(jié)點(diǎn)為quicklistZF

我們看看上面的redis配置文件的默認(rèn)配置。

簡(jiǎn)單了解源碼結(jié)構(gòu)

我通過(guò)上面這個(gè)圖來(lái)簡(jiǎn)單說(shuō)一下quicklist的存儲(chǔ)方式，它底層有兩個(gè)結(jié)構(gòu)，一個(gè)quicklist，一個(gè)就是quicklistNode。下面是我找的源碼，可以簡(jiǎn)單看下。

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;

quicklist的主要作用就是來(lái)指向節(jié)點(diǎn)的頭和尾

總結(jié)

總的來(lái)說(shuō)quicklist就是對(duì)ziplist和linkedlist兩者優(yōu)點(diǎn)的結(jié)合，來(lái)進(jìn)一步優(yōu)化redis的列表鍵底層存儲(chǔ)。

到此這篇關(guān)于Redis快速表、壓縮表和雙向鏈表(重點(diǎn)介紹quicklist)的文章就介紹到這了,更多相關(guān)Redis快速表、壓縮表和雙向鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論