天天看點

淺析 Redis 資料結構 List 及其底層編碼方式

作者:馬士兵老師
淺析 Redis 資料結構 List 及其底層編碼方式

list 基本指令和介紹

Redis中的 List 類型與 Java中的 LinkedList類似,可以看做是一個雙向連結清單結構。既可以支援正向檢索也可以支援反向檢索。特征也與LinkedList類似:

  • 有序
  • 元素可以重複
  • 插入和删除快
  • 查詢速度一般

我們可以用 List 存儲一個有序資料,例如:朋友圈點贊清單,評論清單等。

List的常見指令有:

  • LPUSH key element ... :向清單左側插入一個或多個元素
  • LPOP key:移除并傳回清單左側的第一個元素,沒有則傳回nil
  • RPUSH key element ... :向清單右側插入一個或多個元素
  • RPOP key:移除并傳回清單右側的第一個元素
  • LRANGE key star end:傳回一段角标範圍内的所有元素
  • BLPOP和BRPOP:與LPOP和RPOP類似,隻不過在沒有元素時等待指定時間,而不是直接傳回nil

List 的底層編碼方式

為了實作可以從首、尾操作清單中的元素,并且保證查詢效率和降低記憶體占用,在 3.2 版本之前,Redis 采用 ZipList 和 LinkedList 來實作 List,當元素數量小于 512 并且元素大小小于 64 位元組時采用 ZipList 編碼,超過則采用 LinkedList 編碼。在 3.2 版本之後,Redis統一采用 QuickList 來實作 List。

下面我們來看看 ZipList 和 QuickList 的結構分别是怎樣的。

ZipList

ZipList 的結構

ZipList 是一種特殊的“雙端連結清單” ,由一系列特殊編碼的連續記憶體塊組成(類似于連結清單) 。可以在任意一端進行壓入/彈出操作, 并且該操作的時間複雜度為 O(1)。其結構如下圖所示,

淺析 Redis 資料結構 List 及其底層編碼方式

各個成員變量如下:

  • zlbytes,記錄整個壓縮清單占用記憶體位元組數;
  • zltail,記錄壓縮清單「尾部」節點距離起始位址有多少位元組,也就是清單尾的偏移量;
  • zllen,記錄壓縮清單包含的節點數量;
  • entry , 壓縮清單包含的各個節點,節點的長度由節點儲存的内容決定。
  • zlend,标記壓縮清單的結束點,固定值 0xFF(十進制255)。

在壓縮清單中,如果我們要查找定位第一個元素和最後一個元素,可以通過 zltail 直接定位,複雜度是 O(1)。而查找其他元素時,就沒有這麼高效了,隻能逐個查找,此時的複雜度就是 O(N) 了,是以壓縮清單不适合儲存過多的元素。

ZipListEntry

  • ZipList 中的 Entry 并不像普通連結清單那樣記錄前後節點的指針,因為記錄兩個指針要占用16個位元組,浪費記憶體。而是采用下面的結構
淺析 Redis 資料結構 List 及其底層編碼方式
  • previous_entry_length:前一節點的長度,占1個或5個位元組。
    • 如果前一節點的長度小于 254 位元組,則采用1個位元組來儲存這個長度值
    • 如果前一節點的長度大于 254 位元組,則采用5個位元組來儲存這個長度值,第一個位元組為 0xf,後四個位元組才是真實長度資料
  • encoding:編碼屬性,記錄 content 的資料類型(字元串還是整數)以及長度,占用1個、2個或5個位元組,詳見下一個 part -- Encoding 編碼
  • contents:負責儲存節點的資料,可以是字元串或整數

Encoding 編碼

  • ZipListEntry 中的 encoding 編碼分為字元串和整數兩種

字元串

  • 如果encoding:是以“00”、“"01”或者“10”開頭,則證明 content 是字元串,根據字元串的長度大小,encoding 會使用 1 位元組/2位元組/5位元組的空間進行編碼,encoding 編碼的前兩個 bit 表示資料的類型,後續的其他 bit 辨別字元串資料的實際長度,即 data 的長度。
編碼 編碼長度 字元串大小
00pppppp
01pppppp qqqqqqqq
10000000 qqqqqqqq

例如,我們要儲存字元串:“ab”和 “bc”

淺析 Redis 資料結構 List 及其底層編碼方式

整數

  • 如果 encoding 是以“11”開始,則證明 content 是整數,且 encoding 固定隻占用1個位元組。通過 encoding 确認了整數類型,就可以确認整數資料的實際大小了,比如如果 encoding 編碼确認了資料是 int16 整數,那麼 data 的長度就是 int16 的大小。
編碼 編碼長度 整數類型
11000000 1 int16_t(2 bytes)
11010000 1 int32_t(4 bytes)
11100000 1 int64_t(8 bytes)
11110000 1 24位有符整數(3 bytes)
11111110 1 8位有符整數(1 bytes)
1111xxxx 1 直接在xxxx位置儲存數值,範圍從0001~1101,減1後結果為實際值

例如,一個ZipList中包含兩個整數值:“2”和“5”

淺析 Redis 資料結構 List 及其底層編碼方式
可以看到,ZipList 使用 previous_entry_length 來進行向前周遊的操作,而向後周遊使用 encoding的長度 + contents 的長度就可以實作,這導緻 ZipList 對非首尾節點的查詢操作時間複雜度達到 O(n)

ZipList 的連鎖更新問題

連鎖更新

壓縮清單除了查找複雜度高的問題,還有一個問題。

壓縮清單新增某個元素或修改某個元素時,如果空間不不夠,壓縮清單占用的記憶體空間就需要重新配置設定。而當新插入的元素較大時,可能會導緻後續元素的 prevlen 占用空間都發生變化,進而引起「連鎖更新」問題,導緻每個元素的空間都要重新配置設定,造成通路壓縮清單性能的下降。

前面提到,壓縮清單節點的 prevlen 屬性會根據前一個節點的長度進行不同的空間大小配置設定:

  • 如果前一個節點的長度小于 254 位元組,那麼 prevlen 屬性需要用 1 位元組的空間來儲存這個長度值;
  • 如果前一個節點的長度大于等于 254 位元組,那麼 prevlen 屬性需要用 5 位元組的空間來儲存這個長度值;

現在假設一個壓縮清單中有多個連續的、長度在 250~253 之間的節點,如下圖:

淺析 Redis 資料結構 List 及其底層編碼方式

因為這些節點長度值小于 254 位元組,是以 prevlen 屬性需要用 1 位元組的空間來儲存這個長度值。

這時,如果将一個長度大于等于 254 位元組的新節點加入到壓縮清單的表頭節點,即新節點将成為 e1 的前置節點,如下圖:

淺析 Redis 資料結構 List 及其底層編碼方式

因為 e1 節點的 prevlen 屬性隻有 1 個位元組大小,無法儲存新節點的長度,此時就需要對壓縮清單的空間重配置設定操作,并将 e1 節點的 prevlen 屬性從原來的 1 位元組大小擴充為 5 位元組大小。

多米諾牌的效應就此開始。

淺析 Redis 資料結構 List 及其底層編碼方式

e1 原本的長度在 250~253 之間,因為剛才的擴充空間,此時 e1 的長度就大于等于 254 了,是以原本 e2 儲存 e1 的 prevlen 屬性也必須從 1 位元組擴充至 5 位元組大小。

正如擴充 e1 引發了對 e2 擴充一樣,擴充 e2 也會引發對 e3 的擴充,而擴充 e3 又會引發對 e4 的擴充.... 一直持續到結尾。

這種在特殊情況下産生的連續多次空間擴充操作就叫做「連鎖更新」,就像多米諾牌的效應一樣,第一張牌倒下了,推動了第二張牌倒下;第二張牌倒下,又推動了第三張牌倒下....,

壓縮清單的缺陷

空間擴充操作也就是重新配置設定記憶體,是以連鎖更新一旦發生,就會導緻壓縮清單占用的記憶體空間要多次重新配置設定,這就會直接影響到壓縮清單的通路性能。

是以說,雖然壓縮清單緊湊型的記憶體布局能節省記憶體開銷,但是如果儲存的元素數量增加了,或是元素變大了,會導緻記憶體重新配置設定,最糟糕的是會有「連鎖更新」的問題。

是以,壓縮清單隻會用于儲存的節點數量不多的場景,隻要節點數量足夠小,即使發生連鎖更新,也是能接受的。

雖說如此,Redis 針對壓縮清單在設計上的不足,在後來的版本中,新增設計了兩種資料結構:quicklist 和 listpack(這個資料結構會單獨開一篇文章)。這兩種資料結構的設計目标,就是盡可能地保持壓縮清單節省記憶體的優勢,同時解決壓縮清單的「連鎖更新」的問題。

QuickList

為什麼需要 QuickList

在 Redis 3.0 之前,List 對象的底層資料結構是雙向連結清單或者壓縮清單。然後在 Redis 3.2 的時候,List 對象的底層改由 quicklist 資料結構實作。

其實 Quicklist 就是「雙向連結清單 + 壓縮清單」組合,因為一個 quicklist 就是一個連結清單,而連結清單中的每個元素又是一個 ZipList。

在上文中中,我們提到壓縮清單存在一些不足之處,雖然壓縮清單是通過緊湊型的記憶體布局節省了記憶體開銷,但是因為它的結構設計,如果儲存的元素數量增加,或者元素變大了,壓縮清單會有「連鎖更新」的風險,一旦發生,會造成性能下降。而且, ZipList 對非首尾節點的查詢操作時間複雜度是 O(n) ,這在元素數量過多的情況下,同樣不可接受。

Quicklist 解決辦法,通過控制每個連結清單節點中的壓縮清單的大小或者元素個數,來規避連鎖更新的問題。因為壓縮清單元素越少或越小,連鎖更新帶來的影響就越小,對其進行周遊操作所需要的時間代價也變得可以接受,進而提供了更好的通路性能。

是以,QuickList 要做的事情就是

  • 限制 ZipList 的長度和 entry 大小
  • 通過連結清單的結構來管理每一個 ZipList 節點

QuickList 的結構是什麼樣的

從本質上來說,QuickList 是一個雙端清單,特殊之處在于,它的每一個節點是一個 ZipList。

在向 quicklist 添加一個元素的時候,不會像普通的連結清單那樣,直接建立一個連結清單節點。而是會檢查插入位置的壓縮清單是否能容納該元素,如果能容納就直接儲存到 quicklistNode 結構裡的壓縮清單,如果不能容納,才會建立一個新的 quicklistNode 結構。

QuickList

QuickList 的結構源碼如下:

c複制代碼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 head :頭結點指針
  • *quicklistNode tail :尾節點指針
  • unsigned long count :節點中所有 entry 的數量之和
  • unsigned long len :節點數量
  • int fill : QL_FILL_BITS :ZipList 中的 entry 數量上限
    • 為了避免 QuickList 中的每個 ZipList 中 entry 過多,Redis提供了一個配置項:list-max-ziplist-size 來限制,也即 QL_FILL_BITS 的值。
    • 如果值為正,則代表 ZipList 的允許的 entry 個數的最大值
    • 如果值為負,則代表ZipList的最大記憶體大小,分5種情況:(其預設值為 -2)
    • -1:每個ZipList的記憶體占用不能超過4kb
    • -2:每個ZipList的記憶體占用不能超過8kb
    • -3:每個ZipList的記憶體占用不能超過16kb
    • -4:每個ZipList的記憶體占用不能超過32kb
    • -5:每個ZipList的記憶體占用不能超過64kb
  • unsigned int compress : QL_COMP_BITS:首尾不壓縮的節點數量

QuickListNode

c複制代碼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;
           
  • *struct quicklistNode prev :前一個節點指針
  • *struct quicklistNode next :後一個節點指針
  • *unsigned char zl :目前節點的 ZipList 指針
  • unsigned int sz :目前節點的 ZipList 大小
  • unsigned int count : 16 :目前節點的 ZipList entry 個數
  • unsigned int encoding : 2 :編碼方式 1:ZipList ;2:lzf 壓縮模式
  • unsigned int container : 2 :資料類型容器(預留)
  • unsigned int recompress : 1 :是否被解壓縮 1:被解壓了,需要重新壓縮

整體結構圖

淺析 Redis 資料結構 List 及其底層編碼方式
原文連結:https://juejin.cn/post/7239923199609094202

繼續閱讀