Redis - 數據結構詳解（上）

提到 Redis，我想大家並不陌生，基本上每個項目中都會有它的身影出現。作爲一款性能卓越的中間件，其功能強大，在系統中經常扮演着十分重要的角色，像緩存、分佈式鎖和消息隊列等，都是我們所熟知的功能。Redis 在我們的項目中頻繁出現的原因，主要是它可以提升系統的性能，支撐起系統的高併發。那麼 Redis 這麼優秀的原因是什麼呢？這時我們可能會想到它基於內存的存儲介質，多路複用的 IO 方式，以及主模塊的單線程模型等等，但往往忽視了一點，就是 Redis 在底層數據結構上的實現。

當提及 Redis 的數據結構，我們一般會想到 STRING、LIST、SET、ZSET、HASH 等，沒錯，這些在我們平時使用 Redis 的過程中，是直接能夠感知到的數據結構。不過，這僅僅是從使用者的角度去看，如果從內部實現角度，這些高層的數據結構還依賴於更底層的實現，在 Redis 對象系統的實現源碼中，就可以找到底層數據結構的編碼，如下所示。 

注：若沒作說明，本文源碼參考 Redis 6.0.0 版本。

5rEbth

下面，我們依次介紹下 Redis 的底層數據結構，來看看它們是如何實現的。

簡單動態字符串

Redis 是採用 C 語言實現的，但 Redis 並沒有直接使用 C 語言中傳統的字符串表示，而是自己構建了一個名爲簡單動態字符串（simple dynamic string，SDS）的抽象類型，在 Redis 的不同版本中，其實現也是不同的，我們先來看一下 2.8 版本的實現。

struct sdshdr {
    int len;
    int free;
    char buf[];
};

其中：

Mpklwf

與 C 字符串的比較

那就有一個問題，Redis 爲什麼構建了自己的字符串類型，它與 C 字符串的區別在哪，有着什麼樣的優勢呢，下面我們就來看一下。

1. 降低獲取字符串長度的複雜度

2. 拼接操作安全性

3. 減少內存重分配的次數

對於字符串，我們經常會進行修改操作，變長或者變短，這會涉及到內存重分配，可能需要執行系統調用，如果修改操作執行得比較頻繁，過多的內存重分配操作就會影響到系統的性能。

  1. 空間預分配：當要對字符串的長度進行擴展時，如果空間不夠，SDS 是會通過一定的策略分配更多的空間，將未使用的空間記錄到 free 屬性中，這樣就避免下次擴展時再進行申請空間的操作。

  2. 惰性空間釋放：當要縮短字符串時，SDS 並不會釋放掉其對應的空間，而是記錄到 free 屬性中，以便於下次擴展空間時使用。

4. 二進制安全

5. 兼容性

版本優化

上面我們分析了 Redis 爲何設計了自己的字符串類型，但你以爲這樣就可以了嗎，在 3.2 及之後的版本中，Redis 又對 SDS 進行了升級，下面我們來看一下。

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

其中：

6BzB1w

圖片

所做優化

使用場景

Redis 中字符串對象的底層實現之一就使用了 SDS，像 AOF 模塊中的 AOF 緩衝區，以及客戶端狀態中的輸入緩衝區，也是由 SDS 實現的。前言中列舉的 OBJ_ENCODING_EMBSTR、OBJ_ENCODING_INT 也是字符串對象的底層實現，這兩種底層結構會在講解 Redis 的對象系統中講解。

鏈表

鏈表提供了高效的節點重排能力，以及順序性的節點訪問方式，而且增刪節點只需要修改前後節點的指針，非常方便，可以靈活地調整鏈表的長度。鏈表是一種非常常見的數據結構，像高級編程語言中都有它的身影，比如 Java 中的 LinkedList，但 C 語言中卻沒有內置自己的鏈表實現，所以 Redis 自己實現了一個鏈表結構。

實現

typedef struct list {
    listNode *head; // 表頭節點
    listNode *tail; // 表尾節點
    void *(*dup)(void *ptr); // 節點值複製函數
    void (*free)(void *ptr); // 節點值釋放函數
    int (*match)(void *ptr, void *key); // 節點值對比函數
    unsigned long len; // 鏈表包含的節點數量
} list;
typedef struct listNode {
    struct listNode *prev; // 前置節點
    struct listNode *next; // 後置節點
    void *value; // 節點值
} listNode;

圖片

Redis 實現的鏈表可以總結如下：

使用場景

Redis 中列表對象的底層實現之一就使用了鏈表，但在 Redis 3.2 之後，被快表取代，除了這個，像 Redis 中的發佈與訂閱、慢查詢、監視器等功能也使用到了鏈表，以及 Redis 服務器本身的客戶端狀態信息，以及客戶端的輸出緩衝區，也都使用到了鏈表。

字典

同鏈表一樣，C 語言沒有像 Java 等高級編程語言一樣內置自己的字典實現，所以 Redis 構建了自己的字典實現。Redis 的字典是一個用於維護 key 和 value 映射關係的數據結構，底層使用哈希表實現，一個哈希表裏可以有多個哈希節點，每個哈希節點保存了一個鍵值對。

實現

// 字典結構定義
typedef struct dict {
    // 類型特定函數
    dictType *type;
    // 私有數據，保存了需要傳給類型特定函數的可選參數
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash索引 當沒有進行rehash是，值爲 -1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;
// 類型特定函數結構定義
typedef struct dictType {
    // 計算哈希值的函數
    uint64_t (*hashFunction)(const void *key);
    // 複製鍵的函數
    void *(*keyDup)(void *privdata, const void *key);
    // 複製值的函數
    void *(*valDup)(void *privdata, const void *obj);
    // 對比鍵的函數
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 銷燬鍵的函數
    void (*keyDestructor)(void *privdata, void *key);
    // 銷燬值的函數
    void (*valDestructor)(void *privdata, void *obj);
} dictType;
// 哈希表結構定義
typedef struct dictht {
    // 哈希表數組
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩碼，用於計算索引值，總是等於 size - 1
    unsigned long sizemask;
    // 哈希表已有節點的數量
    unsigned long used;
} dictht;
// 哈希表節點結構定義
typedef struct dictEntry {
    // 鍵
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下個哈希表節點，形成鏈表
    struct dictEntry *next;
} dictEntry;

圖片

從上面字典的結構定義，可以看出，它類似 Java 中的 HashMap。談到哈希，總會伴隨一些問題的出現，比如，採用的哈希算法，哈希衝突的解決，重哈希等問題，下面我們來看下 Redis 設計的字典是如何解決這些問題的。

哈希算法

Redis 使用的哈希算法爲 MurmurHash 算法；其索引值的計算，依賴於哈希值和 sizemask 屬性。當給定一個 KV 值時，其索引值的計算過程如下：

哈希衝突

從哈希表節點結構定義中，可以看出，Redis 字典解決哈希衝突的方法爲鏈地址法，因爲哈希表節點中沒有指向鏈表表尾的指針，所以採用的是頭插法，也就是後插入的節點在前面。

rehash

隨着操作的不斷執行，哈希表保存的鍵值對會逐漸地增多或者減少，這時其負載因子可能會在一個不合理的範圍內，太多就會造成哈希衝突的增加，影響查詢的效率，太低就會造成空間存儲效率的下降，因此當負載因子超過設定的閾值，哈希表就會進行相應的擴展或者收縮。其中，哈希表的負載因子計算方式爲：load_factor = ht[0].used / ht[0].size。

rehash 的條件

可以看出，當 BGSAVE 或者 BGREWRITEAOF 命令執行時，負載因子的閾值會變大，這是因爲這兩個命令需要創建當前服務器進程的子進程，而大多數操作都採用寫時複製來優化子進程的使用效率，所以這裏調整閾值上限，可以避免不必要的內存寫入操作，最大限度地節約內存，這一點可以從源碼中得知。

/* This function is called once a background process of some kind terminates,
 * as we want to avoid resizing the hash tables when there is a child in order
 * to play well with copy-on-write (otherwise when a resize happens lots of
 * memory pages are copied). The goal of this function is to update the ability
 * for dict.c to resize the hash tables accordingly to the fact we have o not
 * running childs. */
void updateDictResizePolicy(void) {
    if (!hasActiveChildProcess())
        dictEnableResize();
    else
        dictDisableResize();
}
/* Return true if there are no active children processes doing RDB saving,
 * AOF rewriting, or some side process spawned by a loaded module. */
int hasActiveChildProcess() {
    return server.rdb_child_pid != -1 ||
           server.aof_child_pid != -1 ||
           server.module_child_pid != -1;
}

那 rehash 的擴展和收縮操作的空間是怎麼來決定的呢？

Redis 在執行 rehash 時，也是比較特別的，它並不是一次性、集中式的完成的，而是分多次、漸進式地完成。這樣做的原因在於，如果哈希表中只有很少的鍵值對，那麼可以瞬間將 ht[0] 中的所有數據轉移到 h[1] 中，但如果數據的量級達到了百萬千萬或者億呢，那麼一次性的轉移對於 Redis 將是個災難。這時，rehashidx 這個屬性就有了用武之地，當執行 rehash 時，它會記錄 rehash 的進度，每次對字典執行添加、刪除、查找或者更新時，程序除了會執行指定的操作外，還會將 rehashidx 索引上的鍵值對重新哈希到 ht[1] 中。特別的，在執行 rehash 期間，添加操作會把新的鍵值對直接放到 h[1] 中。

使用場景

Redis 中的哈希對象的底層實現之一就是字典，當包含的鍵值對比較多，或者鍵值對中的元素都是比較長的字符串時，Redis 就會使用字典作爲哈希對象的底層實現。還有一個重要的用途就是，我們通過 Redis 提供的 API 操作數據時，數據存放的數據結構也是字典。

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

猜你喜歡