Redis - 數據結構詳解（下）

上期，我們詳細介紹了 Redis 的 3 種底層數據結構。下面我們介紹其餘的數據結構，來看看它們是如何實現的。

壓縮列表

壓縮列表是 Redis 爲了節約內存而開發的，是由一系列特殊編碼的連續內存塊組成的順序性數據結構，我們可以從源碼的註釋中看到官方對它的定義。

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.

也就是說，ziplist 是一種特殊編碼的雙向鏈表，目標是爲了提高內存的存儲效率。它的每個節點可用於存儲字符串或整數值，其中整數是按真正的整數進行編碼，而不是一系列字符。它允許在列表的任意一端以 O(1) 的時間複雜度提供 push 和 pop 操作。但是，它的每個操作都需要進行內存重分配，實際的複雜性與 ziplist 使用的內存大小有關，也就是和它的存儲的節點個數有關。   

實際上，ziplist 充分體現了 Redis 對於存儲效率的追求。一個普通的雙向鏈表，鏈表中每一項都佔用獨立的一塊內存，各項之間用指針連接起來，這種方式會帶來大量的內存碎片，而且地址指針也會佔用額外的內存。而 ziplist 卻是將表中每一項存放在前後連續的地址空間內，一個 ziplist 整體佔用一大塊內存。從這種方式理解，其實它是一個表（list），並不是一個鏈表（linked list）。   

另外，ziplist 爲了在細節上節省內存，對於值的存儲採用了變長的編碼方式，也就是說，對於大的整數，就多用一些字節來存儲，而對於小的整數，就少用一些字節來存儲。我們接下來就會討論到這些實現細節。

實現

從源碼註釋中可以看到 ziplist 的組成結構：

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

它並沒有像其他數據結構一樣，用自定義的 struct 之類的來表達，而就是簡單的 unsigned char *，可以從它的創建 API 中就可以看出。

// 創建一個新的壓縮列表
unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;
    zl[bytes-1] = ZIP_END;
    return zl;
}

其中，各個部分的含義如下：

mOwS6X

ziplist 中的每個節點都包含兩個片段的元數據作爲前綴。第一個元數據記錄了前一個節點的長度，方便從後到前遍歷列表。第二個元數據記錄了節點存儲數據的類型和長度。所以一個完整的節點是這樣存儲的:

<prevlen> <encoding> <entry-data>

有時， 屬性本身即存儲了節點自身的類型，也記錄了節點的值，比如一些小整數。在這種情況下，可以表示爲：

<prevlen> <encoding>

cFKDG7

KHiHTS

連鎖更新

上面介紹中，entry 屬性中保存的 prevlen 有 1 字節和 5 字節，所以就會出現一種情況：當壓縮列表存儲的節點 e1 到 eN 的長度都介於 250 字節到 253 字節之間，如果在 e1 之前插入了一個長度大於等於 254 字節的新節點，由於 prevlen 的改變，會導致連鎖更新，時間複雜度爲 O(n^2)。雖然連鎖更新的複雜度較高，但它真正造成性能問題的概率是很低的，原因如下：

使用場景

ziplist 是 哈希對象的底層實現之一，當一個哈希對象包含少量鍵值對，並且每個鍵值對要麼就是小整數值，要麼就是長度比較短的字符串時，Redis 就會使用 ziplist 來作爲哈希對象的底層實現。在 Redis 3.2 版本之前，ziplist 也是列表對象的底層實現之一，但 3.2 版本之後被 quicklist 取代。

跳躍表

跳躍表是一種有序數據結構，通過在每個節點中維持多個指向其他節點的指針，來達到快速訪問節點的目的。相比平衡樹，其實現簡單，而且在大部分情況下的效率能和平衡樹相媲美。

實現

// 跳躍表節點實現
typedef struct zskiplistNode {
    // 成員對象（不可與其他節點重複）
    sds ele;
    // 節點分值（可重複，所有節點按此屬性從小到大排序）
    double score;
    // 後退指針
    struct zskiplistNode *backward;
    // 層
    struct zskiplistLevel {
        // 前進指針
        struct zskiplistNode *forward;
        // 跨度
        unsigned long span;
    } level[];
} zskiplistNode;
// 跳躍表實現
typedef struct zskiplist {
    // 表頭指針，表尾指針
    struct zskiplistNode *header, *tail;
    // 跳躍表中節點的數量（不含表頭節點）
    unsigned long length;
    // 跳躍表中層數最大的節點（不含表頭節點）
    int level;
} zskiplist;

多個跳躍表節點組成了跳躍表，程序可以以 O(1) 的時間複雜度獲取表頭、表尾指針以及節點的數量；跳躍表中以 score 屬性的大小進行排序，score 相同，則以成員 ele 屬性的字典序排列；新增節點的層數根據冪次定律取得一個介於 1 和 32 之間的值。

圖片

跳躍表的實現中，存在着一個不填充數據，但滿層的頭結點，頭結點存在的原因如下：

使用場景

Redis 使用跳躍表作爲有序集合鍵的底層實現之一，如果一個有序集合包含的元素數量比較多，又或者有序集合中元素的成員是比較長的字符串時，Redis 就會使用跳躍表來作爲有序集合鍵的底層實現。這裏就有個問題，爲什麼 Redis 不使用平衡樹呢？原因有以下幾點：

整數集合

整數集合是 Redis 用來保存整數值的集合抽象數據結構，集合中不會出現重複的元素，並且是按值的大小從小到大有序地排列。

實現

// 整數集合實現
typedef struct intset {
    // 編碼方式
    uint32_t encoding;
    // 集合包含的元素數量
    uint32_t length;
    // 保存元素的數組
    int8_t contents[];
} intset;

其中，

  1. encoding 屬性的值有 3 個
  1. contents 屬性的類型聲明爲 int8_t，但它不保存任何 int8_t 類型的值，而是取決於 encoding 屬性。

圖片

升級

當整數集合中元素的類型都是 int16_t 類型的值時，如果你需要添加一個 int32_t 類型的整數，會發生什麼呢？這時就會執行升級操作，來保證大類型可以被放入數組。升級可表述爲以下幾步：

升級的好處，就是可以儘可能的節約內存，提升靈活性。

那麼，提到升級，大家肯定會想到是不是有降級，但整數集合不支持降級，原因就是，既然已經有大的元素插入，那麼以後大概率也會有，降級後，再插入大類型的整數，還會進行升級操作，所以降級操作價值不大，而且降級涉及內存重分配，也不是一種廉價的操作。

使用場景

整數集合是集合對象的底層實現之一，當一個集合只包含整數值元素，並且元素數量不多時，Redis 就會使用整數集合作爲集合對象的底層實現。

快表

快表是 Redis 在 3.2 版本中提供的一種數據結構，是一個基於 ziplist 的雙向鏈表，從源碼註釋中對快表的定義就可以看出這一點。

A doubly linked list of ziplists

quicklist 是 ziplist 和 linkedlist 的混合體，它將 linkedList 按段切分，每一段使用 ziplist 來緊湊存儲，多個 ziplist 之間使用雙向指針鏈接起來。quicklist 爲什麼要這樣設計呢，其實就是在空間和時間上進行的平衡：

因此 Redis 從 3.2 版本開始對列表數據結構進行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。但這也帶來了一個新問題：quicklist 的一個節點中的 ziplist 包換多少數據項合適呢？這又是一個需要找到平衡點的難題。我們從存儲效率上分析一下：

所以，Redis 提供了一個配置參數 list-max-ziplist-size ，讓使用者可以根據自己的應用場景進行調整。這個配置可以取正值，也可以取負值。下面我們來解釋下不同值代表的含義：

ngC150

另外，當列表很長的時候，最容易被訪問的很可能是兩端的數據，中間的數據被訪問的頻率比較低（訪問起來性能也很低）。如果應用場景符合這個特點，那麼 quicklist 還提供了一個選項，能夠把中間的數據節點進行壓縮，從而進一步節省內存空間。Redis 的配置參數 list-compress-depth 就是用來完成這個設置的。這個參數表示一個 quicklist 兩端不被壓縮的節點個數。注：這裏的節點個數是指 quicklist 雙向鏈表的節點個數，而不是指 ziplist 裏面的數據項個數。實際上，一個 quicklist 節點上的 ziplist，如果被壓縮，就是整體被壓縮的。參數 list-compress-depth 的取值含義如下：

由於 0 是個特殊值，很容易看出 quicklist 的頭節點和尾節點總是不被壓縮的，以便於在表的兩端進行快速存取。Redis 對於 quicklist 內部節點的壓縮算法，採用的 LZF （一種無損壓縮算法）。

實現

// 快表節點
typedef struct quicklistNode {
    // 上一個節點
    struct quicklistNode *prev;
    // 下一個節點
    struct quicklistNode *next;
    // 數據指針，如果未壓縮，指向一個ziplist，壓縮後指向quicklistLZF
    unsigned char *zl;
    // 指向的壓縮列表的大小，如果被壓縮，仍是未壓縮前的大小
    unsigned int sz;             /* ziplist size in bytes */
    // ziplist中包含的數據項的個數
    unsigned int count : 16;     /* count of items in ziplist */
    // 是否被壓縮，1：未壓縮 2：壓縮（LZF）
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    // 數據容器，表示底層用什麼數據結構存儲數據，目前只有ziplist一個容器
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    // 如果是一個被壓縮的數據，因使用類似lindex這樣的命令要暫時解壓，需要標記一下，等後面重新壓縮
    unsigned int recompress : 1; /* was this node previous compressed? */
    // Redis自動化測試中使用的字段
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    // 擴展字段，供未來擴展使用
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
// 被壓縮的ziplist結構
typedef struct quicklistLZF {
    /// 壓縮後的ziplist大小
    unsigned int sz; /* LZF size in bytes*/
    // 是個柔性數組，存放被壓縮後ziplist的字節數組
    char compressed[];
} quicklistLZF;
// 快表結構
typedef struct quicklist {
    // 表頭節點
    quicklistNode *head;
    // 表尾節點
    quicklistNode *tail;
    // 所有ziplist數據項的總和
    unsigned long count;        /* total count of all entries in all ziplists */
    // quicklist節點的數量
    unsigned long len;          /* number of quicklistNodes */
    // 單個節點的填充因子，存放list-max-ziplist-size參數的值
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    // 節點壓縮深度，存放list-compress-depth參數的值
    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;

圖片

上圖中是一個含有 3 個節點的 quicklist，其中每個節點有 4 個數據項，兩邊的節點是未壓縮的，中間的節點是壓縮的。

使用場景

Redis 使用快表作爲列表對象的底層實現，不過在 3.2 版本之前，列表對象的底層實現是鏈表或者壓縮列表，使用快表替換鏈表和壓縮列表的實現原因，上面已經講解，這裏就不再贅述了。

zipmap

zipmap 看名字，感覺和 ziplist 很像，zip 有壓縮的意思，map 說明是一個有關於鍵值對的數據結構，可以猜測是對 map 實現上的一種內存優化，下面我們就來驗證一下。

String -> String Map data structure optimized for size.

從上述源碼註釋中得知，zipmap 其實就是一個 String，是一個壓縮了的 map 結構，分配了一段連續的內存空間，用來保存連續的 key-value 集合。它的特點是維護 map 所需要的額外信息很少，對於一個鍵值對最少只需要額外的三個字節來描述。不過這樣做的後果就是，對 map 操作時需要進行遍歷，時間複雜度爲 O(n)，但由於鍵值對的個數不會很多，所以並不會有性能問題。

實現

zipmap 的數據結構特別簡單，簡單到新創建後的 zipmap 只有兩個字節，其中，首字節保存長度，尾字節保存結尾標誌 ZIPMAP_END，其中 ZIPMAP_END = 255，可以從 zipmap 的創建 API 就可以看出來。

/* Create a new empty zipmap. */
unsigned char *zipmapNew(void) {
    unsigned char *zm = zmalloc(2);
    zm[0] = 0; /* Length */
    zm[1] = ZIPMAP_END;
    return zm;
}

那麼 zipmap 是怎樣保存鍵值對的呢，源碼註釋中有一個例子，如果要保存 "foo" => "bar"，"hello" => "world"，那麼會是這樣：

<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"

其中

uynYLk

使用場景

Redis 中的哈希鍵，當元素個數比較少時，會使用到 zipmap，當達到給定的個數時，會切換到字典。因爲字典保存一個鍵值對需要的額外信息比較大 sizeof(struct dictEntry) = 24，而 zipmap 最少只需要三個字節，最多 11 個字節。在查詢效率上，當數據量特別小的時候，順序查詢花費的時間成本雖然是 O(n)，但是 n 小，所以是可以接受的，這樣做可以節約內存。不過，這是在 Redis 2.6 版本之前纔有，在 2.6 版本及之後的版本中已經被 ziplist 替代，也就是說，當鍵值對比較少時，會採用 ziplist 去實現哈希類型的對象。

流

stream 是 Redis 5.0 版本新增加的數據結構，它底層數據的存儲依賴於 一棵 radix tree，主要用於消息隊列的實現，stream 可以說是 Redis 底層數據結構中最複雜的一個。

實現

typedef struct streamID {
    // unix時間戳
    uint64_t ms;        /* Unix time in milliseconds. */
    // 序號
    uint64_t seq;       /* Sequence number. */
} streamID;
typedef struct stream {
    // 指向radix tree的指針
    rax *rax;               /* The radix tree holding the stream. */
    // stream 中保存的元素的數量，以消息ID爲統計維度
    uint64_t length;        /* Number of elements inside this stream. */
    // stream中最後一個消息ID
    streamID last_id;       /* Zero if there are yet no items. */
    // 保存監聽該stream的消費者信息
    rax *cgroups;           /* Consumer groups dictionary: name -> streamCG */
} stream;

從上述實現中可以看出， streamID，也就是消息 ID，是由時間戳 + 序號兩部分組成，各佔 64 位，一共 128 位，此 ID 可由 Redis 自動生成，或者自定義，爲了保證消息的有序性，Redis 自動生成的 ID 是單調遞增的。由於消息 ID 中包含了時間戳，爲了避免 Redis 服務器時間錯誤，比如發生了時鐘向後跳躍，stream 中都維護了一個 last_id，來記錄最後一個消息 ID，若與 last_id 比較發現時間戳退後，則採用時間戳延用 last_id，遞增序號的方式生成消息 ID（這也是序號使用 64 位表示的原因，保證有足夠多的序號使用），從而保證消息 ID 的單調遞增。   

然後，我們再來看 rax 這個屬性表示什麼，從源碼中的註釋中可以得到答案，即 rax 是一棵 radix tree 的實現。

Rax -- A radix tree implementation.

typedef struct raxNode {
    uint32_t iskey:1;
    uint32_t isnull:1;
    uint32_t iscompr:1;
    uint32_t size:29;
    unsigned char data[];
} raxNode;
typedef struct rax {
    // radix tree頭結點指針
    raxNode *head;
    // radix tree中存儲元素的總數
    uint64_t numele;
    // radix tree中節點總數
    uint64_t numnodes;
} rax;

下面我們來詳細介紹一下 raxNode 的屬性：

RDak52

下面我們來展開介紹一下：

[header iscompr=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)
[header iscompr=1][xyz][z-ptr](value-ptr?)

當我們使用 xadd key id field value [field value ...] 向其中添加消息時，還會涉及另外一個數據結構 listpack，它是什麼，也可以從源碼中得到答案：

Listpack -- A lists of strings serialization format

其實也是一個字符串，和 zipmap 很相似，從創建一個新的 listpack 的 API 就可以看出。

unsigned char *lpNew(void) {
    unsigned char *lp = lp_malloc(LP_HDR_SIZE+1);
    if (lp == NULL) return NULL;
    lpSetTotalBytes(lp,LP_HDR_SIZE+1);
    lpSetNumElements(lp,0);
    lp[LP_HDR_SIZE] = LP_EOF;
    return lp;
}

添加元素時，會先找到 radix tree 中的最後一個節點，校驗這個節點的 data 是否超過配置規定的大小（從佔用空間和元素總數上），沒有超過，則使用這個空間；若超過，則會新創建一個 listpack 結構，一個新創建的 listpack 中 field 的組織方式如下：

+-------+---------+------------+---------+--/--+---------+---------+-+
 | count | deleted | num-fields | field_1 | field_2 | ... | field_N |0|
 +-------+---------+------------+---------+--/--+---------+---------+-+

對於 value 的處理有兩種方式，通常是以第一種方式組織，但當添加的 field 和原有的 field 相同時，就採用第二種方式。

// 方式1
+-----+--------+----------+-------+-------+-/-+-------+-------+--------+
|flags|entry-id|num-fields|field-1|value-1|...|field-N|value-N|lp-count|
+-----+--------+----------+-------+-------+-/-+-------+-------+--------+
// 方式2
+-----+--------+-------+-/-+-------+--------+
|flags|entry-id|value-1|...|value-N|lp-count|
+-----+--------+-------+-/-+-------+--------+

由於 stream 的實現比較複雜，涉及的內容比較多，後面會單獨來講 stream，這裏僅做以上概述。

使用場景

Redis 使用 stream 作爲流對象的底層實現，功能就是我們熟知的消息隊列，雖然 Redis 本身就有一個發佈訂閱（pub/sub）可以實現消息隊列的功能，但消息不支持持久化，很容易造成消息丟失。另外 rax 還被用在了 Redis Cluster 中用於記錄 slot 與 key 的對應關係。

總結

從上述對 Redis 底層數據結構的介紹，我們可以看出，Redis 針對底層數據結構的設計是非常精細的，針對每個字節，甚至每一位都進行了考量，可以表現爲以下幾點：

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/TLuass4H0RIowuij6nU23w

猜你喜歡