Redis 基礎數據類型重溫

有一天你突然收到一條線上告警：Redis 記憶體使用率 85%。你嚇壞了趕緊先進行擴容然後再去分析 big key。等你進行完這一系列操作之後老闆叫你去復盤，期間你們聊到了業務的數據存儲在 Redis 中佔用多大記憶體的問題。老闆按照序列化為 String 的方式來評估每個 key 對應的 value 大概多少位元組來計算總 key 數佔用多大空間。你努力的回想了一下當年你面試的時候背誦的 」真理「，總感覺哪裡不太對。於是你在夜深人靜的時候又打開了 」Redis 面試寶典「。

Redis 核心對象：redisObject

為什麼 Redis 不直接存儲一個字元串進去非要自己封裝一個對象呢？

Redis 為用戶提供了多種類型的數據結構，對於用戶而言你無需關心數據結構內部是如何存儲，只需要一條命令行即可。在 Redis 內部要實現這些不同命令行對應的功能遠遠不止這麼簡單，用戶越簡單，底層越複雜。需要根據不同的命令去處理不同的類型的操作，那麼這些類型資訊就是在 redisObject 對象中封裝。基於 redisObject 對象，底層可以進行類型檢查，對象分配、銷毀等操作。

redisObject 定義如下：

/*
 * Redis 對象
 */
typedef struct redisObject {

    // 類型
    unsigned type:4;

    // 編碼方式
    unsigned encoding:4;

    // LRU - 24位, 記錄最末一次訪問時間（相對於lru_clock）; 或者 LFU（最少使用的數據：8位頻率，16位訪問時間）
    unsigned lru:LRU_BITS; // LRU_BITS: 24

    // 引用計數
    int refcount;

    // 指向底層數據結構實例
    void *ptr;

} robj;

lru屬性: 記錄了對象最後一次被命令程式訪問的時間

空轉時長：當前時間減去鍵的值對象的 lru 時間，就是該鍵的空轉時長。Object idle time 命令可以列印出給定鍵的空轉時長。如果伺服器打開了 maxmemory 選項，並且伺服器用於回收記憶體的演算法為 volatile-lru 或者 allkeys-lru，那麼當伺服器佔用的記憶體數超過了maxmemory 選項所設置的上限值時，空轉時長較高的那部分鍵會優先被伺服器釋放，從而回收記憶體。

type、encoding、ptr 是最重要的三個屬性。

type 記錄了對象所保存的值的類型，它的值可能是以下常量中的一個：

/*
* 對象類型
*/
#define OBJ_STRING 0 // 字元串
#define OBJ_LIST 1 // 列表
#define OBJ_SET 2 // 集合
#define OBJ_ZSET 3 // 有序集
#define OBJ_HASH 4 // 哈希表

encoding 記錄了對象所保存的值的編碼，它的值可能是以下常量中的一個：

/*
* 對象編碼
*/
#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* 注意：版本2.6後不再使用. */
#define OBJ_ENCODING_LINKEDLIST 4 /* 注意：不再使用了，舊版本2.x中String的底層之一. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */

ptr 是一個指針，指向實際保存值的數據結構，這個數據結構由 type 和 encoding 屬性決定。舉個例子， 如果一個 redisObject 的 type 屬性為OBJ_LIST ， encoding 屬性為OBJ_ENCODING_QUICKLIST ，那麼這個對象就是一個Redis 列表（List)，它的值保存在一個 QuickList 的數據結構內，而 ptr 指針就指向 quicklist 的對象。

下圖展示了 redisObject 、Redis 所有數據類型、Redis 所有編碼方式以及底層數據結構之間的關係：

可能這樣說你看起來還是懵逼，那我們就把每一種數據類型都拿出來分析一下。

string 類型

string 是 Redis 中最基本的數據類型，Redis 是用 C 開發的，但是 Redis 中的 string 和 C 中的 string 有很大的區別。

string 類型在 Redis 中有三種存儲方式：int、raw、embstr。即 這種 string 並不是字面意義上的 string。

int 格式存儲

當一個 key 的 value 是整型並且 value 長度不超過 20 個字元，Redis 就將其編碼為 int 類型。很顯然這樣做是為了節約記憶體。

Redis 默認會快取 10000 個整型值（#define OBJSHAREDINTEGERS 10000），這就意味著，如果有 10 個不同的 key，value 都是 10000 以內的值，事實上全部都是共享同一個對象。

SDS （simple dynamic string）

在 Redis 3.2 版本之前如果存儲的是一個字元串且長度大於 39 個位元組，就會使用 SDS 的格式來存儲，並且將 encoding 設置為 raw。如果存儲的是一個字元串但是長度小於等於 39 個位元組，則將 encoding 設置為 embstr 來存儲。

在 3.2 版本之後 39 被改為 44。

sds 的定義如下：

struct sdshdr {  
      
    // buf 中已佔用空間的長度  
    int len;  
  
    // buf 中剩餘可用空間的長度  
    int free;  
  
    // 數據空間  
    char buf[];  
};

欄位含義：

  • len 用於記錄 buf 中已經使用的空間長度；
  • free 用於記錄 buf 中還空餘的空間（初次分配空間一般沒有空餘，在對字元串修改的時候，會有剩餘空間出現）；
  • buf 字元數組，用於記錄我們的字元串。

當你在 Redis 存儲一個 hello 時，它在 sds 中存儲的結構大概如下：

raw 格式和 embstr 格式的區別在於：

raw 編碼會調用兩次記憶體分配來分別創建 redisObject 結構和 sdshdr 結構，而 embstr 編碼則通過一次記憶體分配函數來獲得一塊連續的空間，空間中依次包含 redisObject 和 sdshdr 結構。

同樣對於記憶體釋放來說，embstr 只需要一次，而 sdshdr 需要兩次。

另外，因為 embstr 編碼格式的字元串對象所有數據都是保存在一塊連續的記憶體塊中，那麼對於查找操作來說可以將整塊數據放入快取中，更有利於讀取。

SDS 和 C 字元串的區別

字元串長度計算

C 語言中的字元串使用長度為 n+1 的字元串數組來表達長度為 n 的字元串，獲取字元串長度需要遍歷整個數組。而 SDS 使用獨立的 len 欄位來記錄長度。

C 緩衝區溢出

有兩個在記憶體中緊鄰的字元串」hello「 和 」world「，現在要把 」hello「 改為 」helloo「，但是忘記重新為 」helloo「 分配新的記憶體空間，那麼在 C 中會把 」helloo「 的位置往後溢出到後面的記憶體空間，即 」world「 的位置會被擠占。這兩個單詞就變為：”hellooorld”。

使用 SDS 則不用擔心這種問題。Redis 會在執行修改操作之前先檢查分配給 SDS 的空間是否夠用，如果不夠會先拓展空間再執行修改操作。

另外 SDS 還提供兩個實用功能：空間預分配 和 惰性釋放空間。

預分配策略：

  • 如果修改後的 SDS 長度 < 1MB，預分配同樣 len 大小的空間；

  • 如果修改後的 SDS 長度 > 1MB，預分配1MB 大小的空間。

惰性空間釋放

縮短 SDS 空間時並不立即進行記憶體空間釋放，而是記錄 free 位元組數。下次修改數據如果需要重新分配空間時優先取這一部分位元組而不是重新分配。

Hash 類型

hash 類型的底層存儲分別有兩種方式：ziplist 和 hashtable。

hashtable 存儲

hashtable 實現方式我們就不細說大家都懂，基於 hash 值來實現，Redis 解決 hash 衝突使用鏈地址法。與 Java 中的 HashMap 不同的是，在鏈地址法解決衝突的過程中，對於一個衝突的 key 總是會添加到當前鏈表的表頭而不是表尾，這樣添加節點的時間複雜度就為 o(1)。

hash 的存儲邏輯我們就不說，詳細說一下 rehash 的過程，這個實現比較有意思。

Redis 的 字典結構體 dict 中存放了兩張 hash 表：

typedef struct dict{
    dictType *type; //dictType結構，dictType結構中包含自定義的函數，這些函數使得key和value能夠存儲任何類型的數據
    void *privdata; //私有數據，保存著dictType結構中函數的 參數
    dictht ht[2]; //兩張哈希表
    long rehashidx; //rehash的標記，rehashidx=-1表示沒有進行rehash，rehash時每遷移一個桶就對rehashidx加一
    int itreators;  //正在迭代的迭代器數量
}

正常使用的就是 ht[0]，ht[1] 是只有在擴容/縮容 的時候才會用到。hash 都是有負載因子的，這裡也不例外：

​ load factor = ht[0].used / ht[0].size

觸發 rehash 有兩種情況，一種是觸發擴容，一種是觸發縮容。

觸發擴容的條件包括：

  • 伺服器當前沒有在執行 BGSAVE 命令或者 BGREWRITEAOF 命令，並且 load factor >= 1；
  • 伺服器當前正在執行 BGSAVE 命令或者 BGREWRITEAOF 命令，並且 load factor >= 5；

觸發縮容的條件：

負載因子 < 0.1 時（(ht[0].used / ht[0].siz) < 0.1）。

再說很好玩的一點：漸進式 rehash。這個在 Java 的 HashMap 中是沒有的。

所謂漸進式 rehash 即 rehash 不是一次性、集中式的完成，而是分多次、漸進式的進行。

這樣做的原因在於如果 hash 表裡的 KV 對很大時，比如上百萬的情況如果一次性將這些數據全部從 ht[0] 移到 ht[1] 所需的龐大計算量可能會導致 Redis 在一段時間內停止服務。為了避免這種情況所以 Redis 採取了漸進式 rehash。

漸進式 rehash 期間，Redis 會逐漸的將 ht[0] 的數據轉移到 ht[1] ，查找/刪除/更新 操作會先查 ht[0]， 查不到會再查 ht[1]，新增操作只會在 ht[1] 上執行。

zipList 存儲

說完 hashtable 存儲我們再來說另一種存儲方式：zipList。翻譯過來是壓縮列表，但是並不是我們理解表意上面的那種壓縮。

zipList 是 list 鍵、 hash 鍵以及 zset 鍵的底層實現之一（3.0 之後 list 鍵已經不直接使用 zipList 和 linkedList 作為底層實現，取而代之的是 quickList）。

Redis 官方文檔表示： zipList 是一個經過特殊編碼的雙向鏈表，這種雙向鏈表與普通的雙向鏈表的區別在於：它不存儲上個節點和下個節點的指針，而是上個節點的長度和當前節點的長度。它的設計目標就是為了提高存儲效率，zipList 適用於欄位少和欄位值少的場景。可用於存儲字元串或整數，整數是按照二進位表示進行編碼，而不是編碼成字元串。

另外普通的鏈表中的每一項可能都不在一塊連續的記憶體空間中，通過指針來表示數據引用。而 zipList 為了減少記憶體碎片率和提高查詢效率，一個 zipList 對象將獨自佔用一塊完整的獨立記憶體空間。

下圖展示了 zipList 的構成：

  • zlbytes：32 bit，表示 zipList 佔用的位元組總數（也包括 zlbytes 本身佔用的 4 個位元組）。
  • zltail： 32 bit，表示 zipList 表中最後一項（entry）在 zipList 中的偏移位元組數。zltail 的存在使得我們可以很方便地找到最後一項（不用遍歷整個zipList ），從而可以在 zipList 尾端快速地執行 push 或 pop 操作。
  • zllen： 16 bit， 表示 zipList 中數據項（entry）的個數。zllen 欄位因為只有 16 bit，所以可以表達的最大值為 2^16-1。這裡需要特別注意的是，如果 zipList 中數據項個數超過了 16bit 能表達的最大值，zipList 仍然可以來表示。那怎麼表示呢？這裡做了這樣的規定：如果 zllen 小於等於 216-2（也就是不等於216-1），那麼 zllen 就表示 zipList 中數據項的個數；否則，也就是 zllen 等於 16bit 全為 1 的情況，那麼 zllen 就不表示數據項個數了，這時候要想知道 zipList 中數據項總數，那麼必須對 zipList 從頭到尾遍歷各個數據項才能計數出來。
  • entry：表示真正存放數據的數據項，長度不定。一個數據項（entry）也有它自己的內部結構。具體結構我們下面畫圖解釋。
  • zlend：zipList 最後 1 個位元組，是一個結束標記，值固定等於 255。

再說 zipList entry 的結構：

pre_entry_length：根據編碼方式的不同， pre_entry_length 可能佔用 1 位元組或者 5 位元組：

  • 1 位元組：如果前一節點的長度小於 254 位元組，便使用一個位元組保存它的值。
  • 5 位元組：如果前一節點的長度大於等於 254 位元組，那麼將第 1 個位元組的值設為 254 ，然後用接下來的 4 個位元組保存實際長度。

encoding 和 length

encoding 和 length 兩部分一起決定了 content 部分所保存的數據的類型（以及長度）。其中， encoding 的長度為 2 bit ， 它的值可以是 00 、 01 、 10 和 11 ：

  • 00 、 01 和 10 表示 content 部分保存著字元數組。
  • 11 表示 content 部分保存著整數。

content 部分保存著節點的內容，類型和長度由 encoding 和 length 決定。

壓縮列表的本質還是一個位元組數組，操作時按照既定規則將字元寫入 entry 中。既然底層是一塊連續的記憶體塊那麼大小肯定是有限制的， hash 結構何時使用 hashtable ，何時使用 zipList 來進行存儲呢？

當我們為某個 key 第一次執行 hset key field value 的時候，Redis 會創建一個 hash 結構，這個新創建的 hash 結構的底層就是 zipList 結構來存儲的。

隨著數據插入的越多，達到 Redis 配置的默認值：

hash-max-ziplist-entries 512
hash-max-ziplist-value 64
  • 當 hash 中的數據項（即field-value對）的數目超過 512 的時候，也就是 zipList 數據項超過 1024 的時候（請參考 t_hash.c 中的 hashTypeSet 函數）。
  • 當 hash 中插入的任意一個 value 的長度超過了 64 的時候（請參考 t_hash.c 中的 hashTypeTryConversion函數）。

之所以有這兩個條件限制，是因為 zipList 變大後會有幾個缺點：

  • 每次插入或修改引發的 realloc 操作會有更大的概率造成記憶體拷貝，從而降低性能。
  • 一旦發生記憶體拷貝，記憶體拷貝的成本也相應增加，因為要拷貝更大的一塊數據，類似 COW 的複製機制。
  • 當 zipList 數據項過多的時候，在它上面查找指定的數據項就會性能變得很低，需要遍歷整個鏈表。

List 類型

List 結構在 3.2 版本之前是使用 zipList 和 linkedList 來實現的， 之後引入的新的數據結構 quickList。這裡我們來看一下 linkedList 和 quickList 的結構是什麼樣的。

linkedList 是一個雙向鏈表，他和普通的鏈表一樣都是由指向前後節點的指針。插入、修改、更新的時間複雜度尾 O(1)，但是查詢的時間複雜度確實 O(n)。

linkedList 和 quickList 的底層實現是採用鏈表進行實現，在 C 語言中並沒有內置的鏈表這種數據結構，Redis 實現了自己的鏈表結構。linkList 維護了一個 length 欄位來保存鏈表長度，所以查詢長度時間複雜度為o(1)。

之所以 zipList 和 linkedList 會被取代，是因為這兩種數據結構都有各自的缺點：

  • zipList 因為使用的是一塊連續的記憶體塊，存儲和讀取效率高，但是不利於修改刪除這種需要頻繁的申請和釋放記憶體的操作，並且當 zipList 長度很長的時候， 一次 realloc 可能會耗費很長時間。
  • linkedList 勝在插入數據時間複雜度低，但是每個節點需要維護兩個指針增加了開銷，各個節點又是單獨的記憶體塊，地址不一定連續，這就會導致回收的時候記憶體碎片率增高。

為了解決這兩個數據結構天然帶來的影響，開發者研究出 quickList 結構，quickList 也不是什麼銀彈神奇，概略來說它就是 zipList 和 linkedList 兩者的結合體。quickList 的定義如下：

typedef struct quicklistNode {
    struct quicklistNode *prev; // 前一個節點
    struct quicklistNode *next; // 後一個節點
    unsigned char *zl; // ziplist結構，壓縮的ziplist會指向一個quicklistLZF結構
    unsigned int sz;             /* ziplist的大小 */
    unsigned int count : 16;     /* ziplist的item個數*/
    unsigned int encoding : 2;   /* ziplist是否壓縮，1沒有壓縮，2壓縮*/
    unsigned int container : 2;  /* 目前固定為2，表示使用ziplist作為數據容器 */
    unsigned int recompress : 1; /* 是否壓縮，1表示壓縮。有些命令需要做解壓，因此用該標記以便後續壓縮*/
    unsigned int attempted_compress : 1; /* 暫時不用管，自動測試用的 */
    unsigned int extra : 10; /* 擴展欄位，目前還沒被使用，剛好湊成32bit */
} quicklistNode;

從結構體不難看出，quickList 的外層就是一個 linkedList ，只不過 linkedList 裡面放的不是 source data，而是 zipList。所以 quickList 不能算作是偉大的發明，稱為在偉大發明肩上做了一點微小的工作比較合適（事實上也不算微小）。

了解了 quickList 是什麼之後我們應該會有一些問題：既然底層還是 zipList，那怎麼解決 zipList 過長的問題呢？

如果每個 zipList 上的數據越少，那麼整個 quickList 上的節點就越多，記憶體碎片率就越高；反之如果只有一個 zipList 那跟直接使用 zipList 也沒什麼區別。所以 quickList 還是做了一些細節處理的。

Redis 提供了一個配置參數 list-max-ziplist-size，使用者可以來根據自己的情況進行調整。

這個參數可以取正值，也可以取負值。當取正數時，表示按照你配置的個數來限制每個 zipList 的長度。比如配置了 list-max-ziplist-size=5 即表示 zipList 最多包含 5 個元素。

當取負數時，表示按照佔用位元組數來限制每個 zipList 的長度。Redis 配置只能從 -1 – -5 這幾個數中選擇：

  • -5: 每個 quickList 節點上的 zipList 大小不能超過 64 Kb。
  • -4: 每個 quickList 節點上的 zipList 大小不能超過 32 Kb。
  • -3: 每個 quickList 節點上的 zipList 大小不能超過 16 Kb。
  • -2: 每個 quickList 節點上的 zipList 大小不能超過 8 Kb。（-2是Redis給出的默認值）
  • -1: 每個 quickList 節點上的 zipList 大小不能超過 4 Kb。

使用 List 結構來存儲數據大概率也是兩邊的數據被先訪問的概率大一些 ，中間的數據被訪問的頻率很低。如果你的應用場景符合這個特點，List 還提供一個選項：即把中間的數據進行壓縮以節省空間。Redis 的配置參數 list-compress-depth 就是用來完成這個設置。

這個參數表示一個 quickList 兩端不被壓縮的節點個數。註：這裡的節點個數是指 quickList 雙向鏈表的節點個數，而不是指 zipList 裡面的數據項個數。實際上一個 quickList 節點上的 zipList 如果被壓縮就是整體被壓縮。

參數 list-compress-depth 的取值含義如下：

  • 0: 是個特殊值，表示都不壓縮。這是 Redis 的默認值。
  • 1: 表示 quickList 兩端各有 1 個節點不壓縮，中間的節點壓縮。
  • 2: 表示 quickList 兩端各有 2 個節點不壓縮，中間的節點壓縮。
  • 3: 表示 quickList 兩端各有 3 個節點不壓縮，中間的節點壓縮。
  • 依此類推…

由於 0 是個特殊值，很容易看出 quickList 的頭節點和尾節點總是不被壓縮的，以便於在表的兩端進行快速存取。

Set 集合

List 列表不會管你存入的數據是否是重複的，來了即入隊。Set 是不可重複的集合，底層使用兩種存儲結構來支援：一種是 hashtable，一種是 inset。

hashtable 我們上面已經說過，key 為 set 元素的值， value 為 null。inset 是一種新的數據結構，可以理解為數組。使用 inset 數據結構需要滿足兩個條件：

  • 元素個數不少於默認值 512；
  • 元素可以用整型來表示。

簡單說：Set 集合如果存儲的是非整型數據或者是整型數據且元素個數少於 512 個時底層會用 hashtable 結構來存儲；否則就用 inset 結構來存儲。

inset 結構是由整數組成的集合，實際上是有序集合，從而便於使用二分查找法更快的搜索。它在記憶體分配上同 zipList 一樣，也是使用一塊連續的記憶體空間，但是它做的更好的是：對於大整數和小整數（按照絕對值）採取了不同的編碼以節省空間。

inset 的定義如下：

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

encoding 表示數據編碼方式。它有三種可取的值：

  • INTSET_ENC_INT16 表示每個元素用 2 個位元組存儲;

  • INTSET_ENC_INT32 表示每個元素用 4 個位元組存儲

  • INTSET_ENC_INT64 表示每個元素用 8 個位元組存儲。

因此，intset 中存儲的整數最多只能佔用 64 bit。

length 表示 inset 中元素的個數。它和encoding 一起構成了 inset 的頭部。contents 數組是實際存儲數據的地方，

​ contents 總長度（byte） = （ encoding * length）/ 8

contents 裡面的元素有兩個特性：

  • 元素不重複；
  • 元素在數組中由小到大排列。

正因為此特性，所以在查找元素的時候可以採用二分查找法，查詢的時間複雜度為 o(lgN)。

需要注意的是： encoding 是對整個 inset 結構體生效，所以意味著 contents 裡面所有的數據都採用同一種編碼。如果一開始你存儲的數據比較小使用的是 int16 類型的編碼方式，後面存儲了一個大數據之後需要升級為 int64 類型，contents 裡面所有的數據都將使用這一類型編碼。是否升級使用新的編碼格式取決於數組中最長的元素。

ZSet 集合

ZSet 是有序集合，底層是基於 zipList 和 SkipList 來實現的。zipList 我們已經說過，這裡來說一下 SkipList。

SkipList 我們在準備面試的時候多多少少都會去準備一下，所以大家應該也不陌生。以下是個典型的跳躍表例子（圖片來自維基百科）：

從圖中可以看到， 跳躍表主要由以下部分構成：

  • 表頭（head）：負責維護跳躍表的節點指針。
  • 跳躍表節點：保存著元素值，以及多個層。
  • 層：保存著指向其他元素的指針。高層的指針越過的元素數量大於等於低層的指針，為了提高查找的效率，程式總是從高層先開始訪問，然後隨著元素值範圍的縮小，慢慢降低層次。
  • 表尾：全部由 NULL 組成，表示跳躍表的末尾。

SkipList 設計之初是作為替換平衡樹的一種選擇。AVL樹有著嚴格的 o(lgN)的查詢效率，但是對於插入操作可能需要多次旋轉導致效率變低所以又研發了紅黑樹結構。但是紅黑樹有個問題就是在並發更新環境下效率變低，左右旋自平衡的過程中需要鎖住較多節點。

跳錶的實現也比較簡單，就是在普通的單向鏈表基礎上增加了一些分層的索引。演算法大家可以自行搜索，這裡就不詳細介紹。Redis 的跳錶與普通跳錶有一些區別，除了有 value 之外，還有一個 score 的屬性。score 對 value 做排序輔助用。我們主要關注 Redis 對跳錶做的更改：

  1. 允許重複的 score 值：多個不同的 member 的 score 值可以相同。
  2. 進行對比操作時，不僅要檢查 score 值，還要檢查 member ：當 score 值可以重複時，單靠 score 值無法判斷一個元素的身份，所以需要連 member 域都一併檢查才行。
  3. 每個節點都帶有一個高度為 1 層的後退指針，用於從表尾方向向表頭方向迭代：當執行 ZREVRANGE 或 ZREVRANGEBYSCORE 這類以逆序處理有序集的命令時，就會用到這個屬性。

ZSet 底層使用 zipList 和 SkipList 分別在不同的情況下：

[value，score] 鍵值對數少於 128 個且每個元素長度小於 64 位元組的時候使用 zipList 存儲。當不滿足前面的條件時則使用 SkipList 來存儲 value，key 和 score 則使用 hashtable 來存儲。

目前常用的 key-value 數據結構有三種：Hash 表、紅黑樹、SkipList，它們各自有著不同的優缺點：

  • Hash 表：插入、查找最快，為 O(1)；如使用鏈表實現則可實現無鎖；數據有序化需要顯式的排序操作
  • 紅黑樹：插入、查找為 O(logn)，但常數項較小；無鎖實現的複雜性很高，一般需要加鎖；數據天然有序。
  • SkipList：插入、查找為 O(logn)，但常數項比紅黑樹要大；底層結構為鏈表，可無鎖實現；數據天然有序。

ZSet 之所以選用 SkipList 而不是紅黑樹，是因為對於 ZRANGE 或者 ZREVRANGE 這樣的範圍查找操作，跳錶底層的雙向鏈表十分便捷，如果使用紅黑樹結構在找到指定範圍的小值之後，還需要中序遍歷查找其他不超過大值得節點。並且對於插入刪除來說，跳錶只用更改底層鏈表的指針即可，而紅黑樹可能需要調整子樹層高。

我們看一下 SkipList 的結構：

// 單個節點
typedef struct zskiplistNode {
    robj *obj;                      // member，實為 sds
    double score;                   // 排序權重
    struct zskiplistNode *backward; // 單個後繼節點，用作倒序取範圍
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 層級鏈表指針
        unsigned int span;
    } level[]; // 描述層級關係的多個前驅節點
} zskiplistNode;

// 跳躍表
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 頭尾節點
    unsigned long length;                // 表長度
    int level;                           // 截止目前隨機到的最高層數，無需每次都從最高層下沉
} zskiplist;

如果一個鏈表有 n 個結點，如果每兩個結點抽取出一個結點建立索引的話，那麼第一級索引的結點數大約就是 n/2，第二級索引的結點數大約為 n/4，以此類推第 m 級索引的節點數大約為 n/(2^m)。

假如一共有 m 級索引，第 m 級的結點數為兩個，通過上邊我們找到的規律，那麼求得 n / ( 2^m ) = 2，從而求出 m=log(n) – 1。如果加上原始鏈表，那麼整個跳錶的高度就是 log(n) 。

我們在查詢跳錶的時候，如果每一層都需要遍歷 k 個結點，那麼最終的時間複雜度就為 O(k * log(n))。那這個 k 值為多少呢，按照我們每兩個結點提取一個基點建立索引的情況，我們每一級最多需要遍歷兩個節點，所以 k=2。那跳錶查詢數據的時間複雜度就是 o(2 * log(n))，常數 2 忽略不計，就是 o(log(n))了。

如果嚴格按照這種兩下兩層鏈表上節點個數 2：1 的對應關係進行維護索引，對於插入或者刪除數據的時候很有可能會將索引調整的複雜度升到o(n)，Redis 為了避免這一問題，它不要求上下兩層索引之間節點個數有嚴格的對應關係，而是為每層節點隨機出一個層數，這個隨機過程並不是一個服從均勻分布的隨機數，計算過程如下：

  1. 每個節點都有一個指向第一層的指針（所有數據都在第一層）；
  2. 如果一個節點有第 i 層(i >=1)指針，即節點已經在第一層到第i層鏈表中，那麼它有第i+1層指針的概率為P；
  3. 節點最大層數不允許超過一個最大值，記為 MaxLevel。

以上過程的偽碼如下：

int randomLevel(){
    int level = 1;
    while (Math.random()<p && level<MaxLevel){
        level ++ ;
    }
    return level;
}

在 Redis 中上面兩個參數 p 和 MaxLevel 的取值是固定的：

p = 1/4
MaxLevel = 32 (5.0版本以後是64)

根據這個演算法，一個新增的節點有 50% 的概率在level[1]，25%的概率在level[2]，12.5%的概率在level[3],以此類推，有 2^63 個元素的情況下會有 31 層，且每一層向上晉陞的概率都是50%。

總結

以上介紹了 Redis 的 5 種基本類型數據結構：string、list、hash、set、zset，詳細討論了這些數據結構底層的實現邏輯，可以看到 Redis 在節約記憶體方面做了很多的努力，不僅僅是新存儲結構的開發還包括多少數據量用什麼數據結構的探討。

除了 5 種基本類型數據結構外，還有 3 種高級數據結構：HyperLogLog、Geo、BloomFilter。限於篇幅，我們下一篇接著探討。

Tags:

VirMach 便宜 VPS

QNews

QNews