跟着大彬讀源碼 – Redis 9 – 對象編碼之 三種list

• 2019 年 10 月 3 日
• 筆記

Redis 底層使用了 ziplist、skiplist 和 quicklist 三種 list 結構來實現相關對象。顧名思義，ziplist 更節省空間、skiplist 則注重查找效率，quicklist 則對空間和時間進行折中。

在典型的雙向鏈表中，我們有稱為節點的結構，它表示列表中的每個值。每個節點都有三個屬性：指向列表中的前一個和下一個節點的指針，以及指向節點中字符串的指針。而每個值字符串值實際上存儲為三個部分：一個表示長度的整數、一個表示剩餘空閑位元組數的整數以及字符串本身後跟一個空字符。

可以看到，鏈表中的每一項都佔用獨立的一塊內存，各項之間用地址指針（或引用）連接起來。這種方式會帶來大量的內存碎片，而且地址指針也會佔用額外的內存。這就是普通鏈表的內存浪費問題。

此外，在普通鏈表中執行隨機查找操作時，它的時間複雜度為 O(n)，這對於注重效率的 Redis 而言也是不可接受的。這是普通鏈表的查找效率太低問題。

針對上述兩個問題，Redis 設計了ziplist（壓縮列表）、skiplist（跳躍表）和快速鏈表進行相關優化。

1 ziplist

對於 ziplist，它要解決的就是內存浪費的問題。也就是說，它的設計目標就是是為了節省空間，提高存儲效率。

基於此，Redis 對其進行了特殊設計，使其成為一個經過特殊編碼的雙向鏈表。將表中每一項存放在前後連續的地址空間內，一個 ziplist 整體佔用一大塊內存。它是一個表（list），但其實不是一個鏈表（linked list）。

除此之前，ziplist 為了在細節上節省內存，對於值的存儲採用了變長的編碼方式，大概意思是說，對於大的整數，就多用一些位元組來存儲，而對於小的整數，就少用一些位元組來存儲。

也正是為了這種高效率的存儲，ziplist 有很多 bit 級別的操作，使得代碼變得較為晦澀難懂。不過不要緊，我們本節的目標之一是為了了解 ziplist 對比普通鏈表，做了哪些優化，可以更好的節省空間。

接下來我們來正式認識下壓縮列表的結構。

1.1 壓縮列表的結構

一個壓縮列表可以包含任意多個節點（entry），每個節點可以保存一個位元組數組或者一個整數值。

圖 1-1 展示了壓縮列表的各個組成部分：

相關字段說明如下：

• zlbytes：4 位元組，表示 ziplist 佔用的位元組總數（包括 zlbytes 本身佔用的 4 個位元組）。
• zltail：4 位元組，表示 ziplist 表中最後一項距離列表的起始地址有多少位元組，也就是表尾節點的偏移量。通過此字段，程序可以快速確定表尾節點的地址。
• zllen：2 位元組：表示 ziplist 的節點個數。要注意的是，由於此字段只有 16bit，所以可表達的最大值為 2^16-1。一旦列表節點個數超過這個值，就要遍歷整個壓縮列表才能獲取真實的節點數量。
• entry：表示 ziplist 的節點。長度不定，由保存的內容決定。要注意的是，列表的節點（entry）也有自己的數據結構，後續會詳細說明。
• zlend：ziplist 的結束標記，值固定為 255，用於標記壓縮列表的末端。

圖 1-2 展示了一個包含五個節點的壓縮列表：

• 列表 zlbytes 屬性的值為 0xd2（十進制 210），表示壓縮列表的總長為 210 位元組。
• 列表 zltail 屬性的值為 0xb3,（十進制 179），表示尾結點相比列表的起始地址有 179 位元組的距離。假如列表的起始地址為 p，那麼指針 p + 179 = entry5 的地址。
• 列表 zllen 屬性的值為 0x5（十進制 5），表示壓縮列表包含 5 個節點。

1.2 列表節點的結構

節點的結構源碼如下（ziplist.c）：

typedef struct zlentry {      unsigned int prevrawlensize, prevrawlen;      unsigned int lensize, len;      unsigned int headersize;      unsigned char encoding;      unsigned char *p;  } zlentry;

如圖 1-3，展示了壓縮列表節點的結構。

• prevrawlen：表示前一個節點佔用的總位元組數。此字段是為了讓 ziplist 能夠從後向前遍歷。
• encoding：此字段記錄了節點的 content 屬性中所保存的數據類型。
• lensize：此字段記錄了節點所保存的數據長度。
• headersize：此字段記錄了節點 header 的大小。
• *p：此字段記錄了指向節點保存內容的指針。

1.3 壓縮列表如何節省了內存

回到我們最開始對普通鏈表的認識，普通鏈表中，每個節點包：

• 一個表示長度的整數
• 一個表示剩餘空閑位元組數的整數
• 字符串本身
• 結尾空字符。

以圖 1-4 為例：

圖 1-4 展示了一個普通鏈表的三個節點，這三個節點中，每個節點實際存儲內容只有 1 位元組，但是它們除了實際存儲內容外，還都要有：

• 3 個指針 – 佔用 3 byte
• 2 個整數 – 佔用 2 byte
• 內容字符串 – 佔用 1 byte
• 結尾空字符的空間 – 佔用 1 byte

這樣來看，存儲 3 個位元組的數據，至少需要 21 位元組的開銷。可以看到，這樣的存儲效率是很低的。

另一方面，普通鏈表通過前後指針來關聯節點，地址不連續，多節點時容易產生內存碎片，降低了內存的使用率。

最後，普通鏈表對存儲單位的操作粒度是 byte，這種方式在存儲較小整數或字符串時，每個位元組實際上會有很大的空間是浪費的。就像上面三個節點中，用來存儲剩餘空閑位元組數的整數，實際存儲空間只需要 1 bit，但是有了 1 byte 來表示剩餘空間大小，這一個 byte 中，剩餘 7 個 bit 就被浪費了。

那麼，Redis 是如何使用 ziplist 來改造普通鏈表的呢？通過以下兩方面：

一方面，ziplist 使用一整塊連續內存，避免產生內存碎片，提高了內存的使用率。

另一方面，ziplist 將存儲單位的操作粒度從 byte 降低到 bit，有效的解決了存儲較小數據時，單個位元組中浪費 bit 的問題。

2 skiplist

skiplist 是一種有序數據結構，它通過在每個節點中維持多個指向其他節點的指針，來達到快速訪問節點的目的。

skiplist 本質上是一種查找結構，用於解決算法中的查找問題。即根據指定的值，快速找到其所在的位置。

此外，我們知道，"查找" 問題的解決方法一般分為兩大類：平衡樹和哈希表。有趣的是，skiplist 這種查找結構，因為其特殊性，並不在上述兩大類中。但在大部分情況下，它的效率可以喝平衡樹想媲美，而且跳躍表的實現要更為簡單，所以有不少程序都使用跳躍表來代替平衡樹。

本節沒有介紹跳躍表的定義及其原理，有興趣的童鞋可以參考這裡。

認識了跳躍表是什麼，以及做什麼的，接下來，我們再來看下在 redis 中，是怎麼實現跳躍表的。

在 server.h 中可以找到跳躍表的源碼，如下：

typedef struct zskiplist {      struct zskiplistNode *header, *tail;      unsigned long length;      int level;  } zskiplist;    typedef struct zskiplistNode {      robj *obj;      double score;      struct zskiplistNode *backward;      struct zskiplistLevel {          struct zskiplistNode *forward;          unsigned int span;      } level[];  } zskiplistNode;

Redis 中的 skiplist 和普通的 skiplist 相比，在結構上並沒有太大不同，只是在一些細節上有以下差異：

• 分數（score）可以重複。就是說 Redis 中的 skiplist 在分值字段上是允許重複的，而普通的 skiplist 則不允許重複。
• 第一層鏈表不是單向鏈表，而是雙向鏈表。這種方式可以用倒序方式獲取一個範圍內的元素。
• 比較時，除了比較 score 之外，還比較數據本身。在 Redis 的 skiplist 中，數據本身的內容是這份數據的唯一標識，而不是由 score 字段做唯一標識。此外，當多個元素分數相同時，還需要根據數據內容進行字典排序。

3 quicklist

對於 quicklist，在 quicklist.c 中有以下說明：

A doubly linked list of ziplists

它是一個雙向鏈表，並且是一個由 ziplist 組成的雙向鏈表。

相關源碼結構可在 quicklist.h 中查找，如下：

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.   * We use bit fields keep the quicklistNode at 32 bytes.   * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).   * encoding: 2 bits, RAW=1, LZF=2.   * container: 2 bits, NONE=1, ZIPLIST=2.   * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.   * attempted_compress: 1 bit, boolean, used for verifying during testing.   * extra: 12 bits, free for future use; pads out the remainder of 32 bits */  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;    /* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.   * 'sz' is byte length of 'compressed' field.   * 'compressed' is LZF data with total (compressed) length 'sz'   * NOTE: uncompressed length is stored in quicklistNode->sz.   * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */  typedef struct quicklistLZF {      unsigned int sz; /* LZF size in bytes*/      char compressed[];  } quicklistLZF;    /* quicklist is a 32 byte struct (on 64-bit systems) describing a quicklist.   * 'count' is the number of total entries.   * 'len' is the number of quicklist nodes.   * 'compress' is: -1 if compression disabled, otherwise it's the number   *                of quicklistNodes to leave uncompressed at ends of quicklist.   * 'fill' is the user-requested (or default) fill factor. */  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 而言，它的每一個節點都是一個 ziplist。quicklist 這樣設計，其實就是我們篇頭所說的，是一個空間和時間的折中。

ziplist 相比普通鏈表，主要優化了兩個點：降低內存開銷和減少內存碎片。正所謂，事物總是有兩面性。ziplist 通過連續內存解決了普通鏈表的內存碎片問題，但與此同時，也帶來了新的問題：不利於修改操作。

由於 ziplist 是一整塊連續內存，所以每次數據變動都會引發一次內存的重分配。當在 ziplist 很大的時候，每次重分配都會出現大批量的數據拷貝操作，降低性能。

於是，結合了雙向鏈表和 ziplist 的優點，就有了 quicklist。

quicklist 的基本思想就是，給每一個節點的 ziplist 分配合適的大小，避免出現因數據拷貝，降低性能的問題。這又是一個需要找平衡點的難題。我們先從存儲效率上分析：

• 每個 quicklist 節點上的 ziplist 越短，則內存碎片越多。而內存碎片多了，就很有可能產生很多無法被利用的內存小碎片，降低存儲效率。
• 每個 quicklist 節點上的 ziplist 越長，則為 ziplist 分配大塊連續內存的難度就越大。有可能出現，內存里有很多較小塊的內存，卻找不到一塊足夠大的空閑空間分配給 ziplist 的情況。這同樣會降低存儲效率。

可見，一個 quicklist 節點上的 ziplist 需要保持一個合理的長度。這裡的合理取決於實際應用場景。基於此，Redis 提供了一個配置參數，讓使用者可以根據情況，自己調整：

list-max-ziplist-size -2

這個參數可以取正值，也可以取負值。

當取正值的時候，表示按照數據項個數來限定每個 quicklist 節點上 ziplist 的長度。比如配置為 2 時，就表示 quicklist 的每個節點上的 ziplist 最多包含 2 個數據項。

當取負值的時候，表示按照佔用位元組數來限定每個 quicklist 節點上 ziplist 的長度。此時，它的取值範圍是 [-1, -5]，每個值對應不同含義：

• -1：每個 quicklist 節點上的 ziplist 大小不能超過 4Kb；
• -2：每個 quicklist 節點上的 ziplist 大小不能超過 8Kb（默認值）；
• -3：每個 quicklist 節點上的 ziplist 大小不能超過 16Kb；
• -4：每個 quicklist 節點上的 ziplist 大小不能超過 32Kb；
• -5：每個 quicklist 節點上的 ziplist 大小不能超過 64Kb；

總結

1. 普通鏈表存在兩個問題：內存利用率低和容易產生內存碎片。
2. ziplist 使用連續內存，減少內存碎片，提供內存利用率。
3. skiplist 可以用相對簡單的實現，達到和平衡樹相同的查找效率。
4. quicklist 汲取了普通鏈表和壓縮鏈表的優點，保證性能的前提下，儘可能的提高內存利用率。