Redis數據結構——quicklist

之前的文章我們曾總結到了Redis數據結構——鏈表和Redis數據結構——壓縮列表這兩種數據結構，他們是Redis List(列表)對象的底層實現方式。但是考慮到鏈表的附加空間相對太高，prev 和 next 指針就要佔去 16 個位元組 (64bit 系統的指針是 8 個位元組)，另外每個節點的記憶體都是單獨分配，會加劇記憶體的碎片化，影響記憶體管理效率。因此Redis3.2版本開始對列表數據結構進行了改造，使用 quicklist 代替了 ziplist 和 linkedlist.

一、基本結構

    quicklist 實際上是 zipList 和 linkedList 的混合體，它將 linkedList 按段切分，每一段使用 zipList 來緊湊存儲，多個 zipList 之間使用雙向指針串接起來。

typedef struct quicklistNode {      struct quicklistNode *prev; //上一個node節點      struct quicklistNode *next; //下一個node      unsigned char *zl;            //保存的數據 壓縮前ziplist 壓縮後壓縮的數據      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;
  • 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的實現里也沒用上。
typedef struct quicklistLZF {      unsigned int sz; /* LZF size in bytes*/      char compressed[];  } quicklistLZF;

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

  • sz: 表示壓縮後的ziplist大小。
  • compressed: 是個柔性數組（flexible array member），存放壓縮後的ziplist位元組數組。
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;
  • head: 指向頭節點（左側第一個節點）的指針。
  • tail: 指向尾節點（右側第一個節點）的指針。
  • count: 所有ziplist數據項的個數總和。
  • len: quicklist節點的個數。
  • fill: 16bit，ziplist大小設置，存放list-max-ziplist-size參數的值。
  • compress: 16bit，節點壓縮深度設置，存放list-compress-depth參數的值。

二、常用操作

2.1 插入

quicklist可以選擇在頭部或者尾部進行插入(quicklistPushHead和quicklistPushTail)，而不管是在頭部還是尾部插入數據，都包含兩種情況：

  • 如果頭節點（或尾節點）上ziplist大小沒有超過限制（即_quicklistNodeAllowInsert返回1），那麼新數據被直接插入到ziplist中（調用ziplistPush）。
  • 如果頭節點（或尾節點）上ziplist太大了，那麼新創建一個quicklistNode節點（對應地也會新創建一個ziplist），然後把這個新創建的節點插入到quicklist雙向鏈表中。

也可以從任意指定的位置插入。quicklistInsertAfter和quicklistInsertBefore就是分別在指定位置後面和前面插入數據項。這種在任意指定位置插入數據的操作，要比在頭部和尾部的進行插入要複雜一些。

  • 當插入位置所在的ziplist大小沒有超過限制時，直接插入到ziplist中就好了；
  • 當插入位置所在的ziplist大小超過了限制，但插入的位置位於ziplist兩端，並且相鄰的quicklist鏈表節點的ziplist大小沒有超過限制，那麼就轉而插入到相鄰的那個quicklist鏈表節點的ziplist中；
  • 當插入位置所在的ziplist大小超過了限制，但插入的位置位於ziplist兩端，並且相鄰的quicklist鏈表節點的ziplist大小也超過限制，這時需要新創建一個quicklist鏈表節點插入。
  • 對於插入位置所在的ziplist大小超過了限制的其它情況（主要對應於在ziplist中間插入數據的情況），則需要把當前ziplist分裂為兩個節點，然後再其中一個節點上插入數據。

2.2 查找

list的查找操作主要是對index的我們的quicklist的節點是由一個一個的ziplist構成的每個ziplist都有大小。所以我們就只需要先根據我們每個node的個數，從而找到對應的ziplist，調用ziplist的index就能成功找到。

2.3 刪除

區間元素刪除的函數是 quicklistDelRange

quicklist 在區間刪除時，會先找到 start 所在的 quicklistNode，計算刪除的元素是否小於要刪除的 count，如果不滿足刪除的個數，則會移動至下一個 quicklistNode 繼續刪除，依次循環直到刪除完成為止。

quicklistDelRange 函數的返回值為 int 類型，當返回 1 時表示成功的刪除了指定區間的元素，返回 0 時表示沒有刪除任何元素。

2.4 其它

除了上面介紹的基本操作之外還有一些其它操作，大家可以嘗試著根據鏈表和壓縮列表的數據結構來分析一些quicklist這些操作的時間複雜度。

操作 時間複雜度
quicklistCreate:創建 quicklist ？
quicklistInsertAfter：在某個元素的後面添加數據 ？
quicklistInsertBefore：在某個元素的前面添加數據 ？
quicklistReplaceAtIndex：替換某個元素 ？
quicklistDelEntry：刪除單個元素 ？
quicklistDelRange：刪除區間元素 ？
quicklistPushHead:頭部插入元素 ？
quicklistPushTail:尾部插入元素 ？

小結

    Redis quicklist是Redis 3.2版本以後針對鏈表和壓縮列表進行改造的一種數據結構，是 zipList 和 linkedList 的混合體，相對於鏈表它壓縮了記憶體。進一步的提高了效率。

如果你有什麼疑問，歡迎在評論區給我留言和分享，我會第一時間回饋！我們一起共同學習與進步！

參考

《Redis設計與實現》

《Redis開發與運維》

《Redis官方文檔》

-----END-----

Tags:

VirMach 便宜 VPS