Redis快速表、壓縮表和雙向鏈表(重點介紹quicklist)

前言

最近在看《Redis的設計與實現》這本書,寫的真的是太好瞭,一下子就看入迷瞭,謝謝作者。不過在學習的時候發現一個問題,我服務器上安裝的是Redis5.0.9版本的,而作者介紹的是Redis3.0版本的,在第一部分將數據結構與對象章節的時候,出現瞭一些差別,就是在redis對外暴露的list結構底層使用的數據結構問題。由於書上沒有記錄,所以就在網上查閱瞭些資料學習瞭一下, 自己再做個總結,當做自己的筆記。

差別

出現的差別就是,在redis3.2版本之前,它使用的是ziplist和linkedlist編碼作為列表鍵的底層實現,在它之後,就采用瞭一個叫做quicklist的數據結構來作其底層實現。
先來介紹下redis3.2之前的版本的知識點:
在使用ziplist和linkedlist作為列表鍵底層實現的時候,他們之間會有一個選擇標準:
選擇ziplist的時候:

  • 列表對象保存的所有字符串元素的長度都小於64字節;
  • 列表對象保存的元素量小於512個

上面的是選擇ziplist作為底層實現所必須滿足的條件,如果沒滿足的話就選用linkedlist作為其底層實現。

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

再來介紹下redis3.2之後的版本:

這個涉及到quicklist這個數據結構瞭,書上沒有記錄,所以我查瞭下資料,也總結到自己的博客當中。

我安裝的時候redis5.0.9版本的,所以上面的幾個指令執行的結果會有所不同

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數據結構的介紹

ziplist和linkedlist就不介紹瞭,書本上有,我們來看看quicklist。
quicklist其實現也是依賴於ziplist和linkedlist來實現的,它是兩個結構的結合。它將ziplist來進行分段存儲,也就是分成一個個的quicklistNode節點來進行存儲。每個quicklistNode指向一個ziplist,然後quicklistNode之間是通過雙向指針來進行連接的。我們來看下大致的結構:

看到這個結構可能會有些疑問:

  • 這個結構啥意思啊,為什麼有的節點是ziplist,有的是quicklistZF?
  • 為什麼quicklist頭部和尾部各有兩個節點是ziplist,剩下中間的是quicklistZF?
  • 為什麼每個quicklistNode節點的ziplist內部的數據個數不一致呢?

為什麼要把底層數據結構優化成quicklist?

在解決上面的問題之前我們先來解決一個首要的問題,也就是redis為什麼要把列表鍵的底層數據結構優化成quicklist?
其實可以從兩個方面來考慮這個原因:

  • ziplist這個結構,它內部的數據存儲是一段連續的空間,這樣的話,就要求很大一塊內存空間。就比如說,我們想存儲很多的數據,但是內存中並沒有符合要求的連續的存儲空間,而是存在很多不連續的小空間(加起來可以符合要求)。
  • 再來說說linkedlist這個結構,它數據存儲不要求連續,就可以避免上面的弊端,不過這樣以來,每個節點都分配一個一塊內存,那就有可能造成大量的內存碎片。

綜上兩個考慮,redis在3.2版本以後就對此情況進行瞭優化,就出來瞭quicklist這個數據結構,quicklist其實就是一個分段的ziplist,為什麼這麼說呢?其實quicklist存儲數據基本單位是quicklistNode,每個quicklistNode的內容區就是以ziplist數據結構存儲的。也就是上面圖示展示的。

為什麼每個quicklistNode節點的ziplist內部的數據個數不一致呢?

現在轉化到quicklist瞭,但是還需要考慮,quicklistNode裡的ziplist裡的內容處理呢?一個ziplist我需要存儲多少個數據呀?也跟上面兩個點考慮的一樣

  • 如果ziplist裡的內容分配的越少的話,也就是往linkedlist方向發展瞭,就可能會產生很多的內存碎片
  • 但要如果ziplist裡的內容分配的越多的話,也會出現問題,就是需要很大一塊連續的內存空間。

redis設計者已經給我們想好瞭,它的配置文件裡有這樣一個參數:list-max-ziplist-size

看到這個配置,我們來解釋下這個參數,它既可以設置正數,也可以設置負數

當它取正數的時候,表示按照數據項個數來限定quicklist節點上的ziplist長度,比如我們設置為4,就說明每個ziplist的數據項最多不能超過5個

當它取負數的時候,表示按照占用字節來限定quicklsit節點上的ziplist長度,這時,它隻能取-1到-5這五個值,每個值的含義如下:
1)、-5:每個quicklist節點上的ziplist大小不能超過64kb。(1kb == 1024 byte)
2)、-4:每個quicklsit節點上的ziplist大小不能超過32kb。
3)、-3:每個quicklsit節點上的ziplist大小不能超過16kb。
4)、-2:每個quicklsit節點上的ziplist大小不能超過8kb。
5)、-1:每個quicklsit節點上的ziplist大小不能超過4kb。

所以就會出現問題所說的,ziplist內存存儲數據個數不一致的問題,我們也可以自己手動設置參數值。

這個結構啥意思啊,為什麼有的節點是ziplist,有的是quicklistZF?

這裡又出現瞭一個配置參數:list-compress-depth
其實,當鏈表很長的時候,最頻繁訪問的就是兩端的數據,中間被訪問的頻率比較低,所以我們可以將中間部分節點進行壓縮,從而能夠進一步節省空間。上面說的list-compress-depth就是來設置這個的。
這個參數的取值含義如下:

0:是個特殊值,表示都不壓縮。這是redis的默認值

1:表示quicklist兩端各有一個節點不被壓縮,中間節點進行壓縮

2:表示quicklist兩端各有兩個節點不被壓縮,中間節點進行壓縮

3:表示quicklist兩端各有三個節點不被壓縮,中間節點進行壓縮…

以此類推

也就是會出現問題所說的,兩端節點為ziplist,中間節點為quicklistZF

我們看看上面的redis配置文件的默認配置。

簡單瞭解源碼結構

我通過上面這個圖來簡單說一下quicklist的存儲方式,它底層有兩個結構,一個quicklist,一個就是quicklistNode。下面是我找的源碼,可以簡單看下。

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的主要作用就是來指向節點的頭和尾

總結

總的來說quicklist就是對ziplist和linkedlist兩者優點的結合,來進一步優化redis的列表鍵底層存儲。

到此這篇關於Redis快速表、壓縮表和雙向鏈表(重點介紹quicklist)的文章就介紹到這瞭,更多相關Redis快速表、壓縮表和雙向鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!