學習分享（第 2 期）：從原始碼層面看 Redis 節省記憶體的設計

語言: CN / TW / HK

時間 2023-02-27 18:04:03 楊同學technotes

主題:

這裡記錄每週的學習分享，週一/週二發表，文章維護在 Github：studeyang/leanrning-share。

回顧

在文章《Redis 的 String 型別，原來這麼佔記憶體》中，我們學習了 SDS 的底層結構，發現 SDS 儲存了很多的元資料，再加上全域性雜湊表的實現，使得 Redis String 型別在記憶體佔用方面並不理想。

然後在文章《學習分享（第1期）之Redis：巧用Hash型別節省記憶體》中，我們學習了另一種節省記憶體的方案，使用 ziplist 結構的 Hash 型別，記憶體佔用減少了一半，效果顯著。

雖然我們在使用 String 型別後，佔用了較多記憶體，但其實 Redis 是對 SDS 做了節省記憶體設計的。除此之外，Redis 在其他方面也都考慮了記憶體開銷，今天我們就從原始碼層面來看看都做了哪些節省記憶體的設計。

文中程式碼版本為 6.2.4。

一、redisObject 的位域定義法

我們知道，redisObject 是底層資料結構如 SDS, ziplist 的封裝，因此，redisObject 如果能做優化，最終也能帶來節省記憶體的使用者體驗。在原始碼 server.h 中定義了 redisObject 的結構體，如下面程式碼所示：

#define LRU_BITS 24

typedef struct redisObject {
    unsigned type:4;//物件型別（4位=0.5位元組）
    unsigned encoding:4;//編碼（4位=0.5位元組）
    unsigned lru:LRU_BITS;//記錄物件最後一次被應用程式訪問的時間（24位=3位元組）
    int refcount;//引用計數。等於0時表示可以被垃圾回收（32位=4位元組）
    void *ptr;//指向底層實際的資料儲存結構，如：sds等(8位元組)
} robj;

type, encoding, lru, refcount 都是 redisObject 的元資料，redisObject 的結構如下圖所示。

從程式碼中我們可以看到，在 type、encoding 和 lru 三個變數後面都有一個冒號，並緊跟著一個數值，表示該元資料佔用的位元數。這種變數後使用冒號和數值的定義方法，實際上是 C 語言中的位域定義方法，可以用來有效地節省記憶體開銷。

這種方法比較適用的場景是，當一個變數佔用不了一個數據型別的所有 bits 時，就可以使用位域定義方法，把一個數據型別中的 bits（32 bits），劃分成多個（3 個）位域，每個位域佔一定的 bit 數。這樣一來，一個數據型別的所有 bits 就可以定義多個變量了，從而也就有效節省了記憶體開銷。

另外，SDS 的設計中，也有記憶體優化的設計，我們具體來看看有哪些。

二、SDS 的設計

在 Redis 3.2 版本之後，SDS 由一種資料結構變成了 5 種資料結構。分別是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，其中 sdshdr5 只被應用在了 Redis 中的 key 中，另外 4 種不同型別的結構頭可以適配不同大小的字串。

以 sdshdr8 為例，它的結構定義如下所示：

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 和 sdshdr8 之間使用了 __attribute__ ((__packed__))。這是 SDS 的一個節省記憶體的設計--緊湊型字串。

2.1 緊湊型字串

什麼是緊湊型字串呢？

它的作用就是告訴編譯器，在編譯 sdshdr8 結構時，不要使用位元組對齊的方式，而是採用緊湊的方式分配記憶體。預設情況下，編譯器會按照 8 位元組對齊的方式，給變數分配記憶體。也就是說，即使一個變數的大小不到 8 個位元組，編譯器也會給它分配 8 個位元組。

舉個例子。假設我定義了一個結構體 st1，它有兩個成員變數，型別分別是 char 和 int，如下所示：

#include <stdio.h>
int main() {
    struct st1 {
        char a;
        int b;
    } ts1;
    printf("%lu\n", sizeof(ts1));
    return 0;
}

我們知道，char 型別佔用 1 個位元組，int 型別佔用 4 個位元組，但是如果你執行這段程式碼，就會發現打印出來的結果是 8。這就是因為在預設情況下，編譯器會按照 8 位元組對齊的方式，給 st1 結構體分配 8 個位元組的空間，但是這樣就有 3 個位元組被浪費掉了。

那我用 __attribute__ ((__packed__)) 屬性重新定義結構體 st2，同樣包含 char 和 int 兩個型別的成員變數，程式碼如下所示：

#include <stdio.h>
int main() {
    struct __attribute__((packed)) st2{
        char a;
        int b;
    } ts2;
    printf("%lu\n", sizeof(ts2));
    return 0;
}

當你執行這段程式碼時，可以看到列印的結果是 5，這就是緊湊型記憶體分配，st2 結構體只佔用 5 個位元組的空間。

除此之外，Redis 還做了這樣的優化：當儲存的字串小於等於 44 位元組時，RedisObject 中的元資料、指標和 SDS 是一塊連續的記憶體區域，這種佈局方式被稱為 embstr 編碼方式；當字串大於 44 位元組時，SDS 和 RedisObject 就分開佈局了，這種佈局方式被稱為 raw 編碼模式。

這部分的程式碼在 object.c 檔案中：

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
    // 當字串長度小於等於44位元組，建立嵌入式字串
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    //字串長度大於44位元組，建立普通字串
    else
        return createRawStringObject(ptr,len);
}

當 len 的長度小於等於 OBJ_ENCODING_EMBSTR_SIZE_LIMIT （預設為 44 位元組）時， createStringObject 函式就會呼叫 createEmbeddedStringObject 函式。這是 SDS 第二個節省記憶體的設計--嵌入式字串。

在講述嵌入式字串之前，我們還是先來看看，當 len 的長度大於 OBJ_ENCODING_EMBSTR_SIZE_LIMIT （預設為 44 位元組）時，這種普通字串的建立過程。

2.2 RawString 普通字串

對於 createRawStringObject 函式來說，它在建立 String 型別的值的時候，會呼叫 createObject 函式。createObject 函式主要是用來建立 Redis 的資料物件的。程式碼如下所示。

robj *createRawStringObject(const char *ptr, size_t len) {
    return createObject(OBJ_STRING, sdsnewlen(ptr,len));
}

createObject 函式有兩個引數，一個是用來表示所要建立的資料物件型別，另一個是指向 SDS 物件的指標，這個指標是通過 sdsnewlen 函式建立的。

robj *createObject(int type, void *ptr) {
    // 【1】給redisObject結構體分配記憶體空間
    robj *o = zmalloc(sizeof(*o));
    //設定redisObject的型別
    o->type = type;
    //設定redisObject的編碼型別
    o->encoding = OBJ_ENCODING_RAW;
    // 【2】將傳入的指標賦值給redisObject中的指標
    o->ptr = ptr;
    …
    return o;
}

呼叫 sdsnewlen 函式建立完 SDS 物件的指標後，也分配了一塊 SDS 的記憶體空間。接著，createObject 函式會給 redisObject 結構體分配記憶體空間，如上示程式碼【1】處。然後再把將傳入的指標賦值給 redisObject 中的指標，如上示程式碼【2】處。

我們接著來看嵌入式字串。

2.3 EmbeddedString 嵌入式字串

通過上文我們知道，當儲存的字串小於等於 44 位元組時，RedisObject 中的元資料、指標和 SDS 是一塊連續的記憶體區域。那麼 createEmbeddedStringObject 函式是如何把 redisObject 和 SDS 的記憶體區域放置在一起的呢？

robj *createEmbeddedStringObject(const char *ptr, size_t len) {
    // 【1】
    robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);
    ...
    if (ptr == SDS_NOINIT)
        sh->buf[len] = '\0';
    else if (ptr) {
        // 【2】
        memcpy(sh->buf,ptr,len);
        sh->buf[len] = '\0';
    } else {
        memset(sh->buf,0,len+1);
    }
    return o;
}

首先，createEmbeddedStringObject 函式會分配一塊連續的記憶體空間，這塊記憶體空間的大小等於 redisObject 結構體的大小 + SDS 結構頭 sdshdr8 的大小 + 字串大小的總和，並且再加上 1 位元組結束字元“\0”。這部分程式碼如上【1】處。

先分配了一塊連續的記憶體空間，從而避免了記憶體碎片。

然後，createEmbeddedStringObject 函式會把引數中傳入的指標 ptr 所指向的字串，拷貝到 SDS 結構體中的字元陣列，並在陣列最後新增結束字元。這部分程式碼如上【2】處。

好了，以上就是 Redis 在設計 SDS 結構上節省記憶體的兩個優化點，不過除了嵌入式字串之外，Redis 還設計了壓縮列表，這也是一種緊湊型的記憶體資料結構，下面我們再來學習下它的設計思路。

三、壓縮列表的設計

為了方便理解壓縮列表的設計與實現，我們先來看看它的建立函式 ziplistNew，這部分程式碼在 ziplist.c 檔案中，如下所示：

unsigned char *ziplistNew(void) {
    // 初始分配的大小
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    …
    // 將列表尾設定為ZIP_END
    zl[bytes-1] = ZIP_END;
    return zl;
}

可以看到，ziplistNew 函式的邏輯很簡單，就是建立一塊連續的記憶體空間，大小為 ZIPLIST_HEADER_SIZE 和 ZIPLIST_END_SIZE 的總和，然後再把該連續空間的最後一個位元組賦值為 ZIP_END，表示列表結束。

另外，在 ziplist.c 檔案中也定義了 ZIPLIST_HEADER_SIZE、 ZIPLIST_END_SIZE 和 ZIP_END 的值，它們分別表示 ziplist 的列表頭大小、列表尾大小和列表尾位元組內容，如下所示。

//ziplist的列表頭大小
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2 + sizeof(uint16_t))
//ziplist的列表尾大小
#define ZIPLIST_END_SIZE (sizeof(uint8_t))
//ziplist的列表尾位元組內容
#define ZIP_END 255

列表頭包括 2 個 32 bits 整數和 1 個 16 bits 整數，分別表示壓縮列表的總位元組數 zlbytes，列表最後一個元素離列表頭的偏移 zltail，以及列表中的元素個數 zllen；列表尾包括 1 個 8 bits 整數，表示列表結束。執行完 ziplistNew 函式建立一個 ziplist 後，記憶體佈局就如下圖所示。

注意，此時 ziplist 中還沒有實際的資料，所以圖中並沒有畫出來。

然後，當我們往 ziplist 中插入資料後，完整的記憶體佈局如下圖所示。

ziplist entry 包括三部分內容，分別是前一項的長度（prevlen）、當前項長度資訊的編碼結果（encoding），以及當前項的實際資料（data）。

當我們往 ziplist 中插入資料時，ziplist 會根據資料是字串還是整數，以及它們的大小進行不同的編碼，這種根據資料大小進行相應編碼的設計思想，正是 Redis 為了節省記憶體而採用的。

unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    ...
    /* Write the entry */
    p += zipStorePrevEntryLength(p,prevlen);
    p += zipStoreEntryEncoding(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) {
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}

此處原始碼在下文中還會提及，為了講述方便，這裡標識為【原始碼A處】。

此外，每個列表項 entry 中都會記錄前一項的長度，因為每個列表項的長度不一樣， Redis 會根據資料長度選擇不同大小的位元組來記錄 prevlen。

3.1 使用不同大小的位元組來記錄 prevlen

舉個例子，假設我們統一使用 4 位元組記錄 prevlen，如果前一個列表項只是一個 5 位元組的字串“redis”，那我們用 1 個位元組（8 bits）就能表示 0~256 位元組長度的字串了。此時，prevlen 用 4 位元組記錄，就有 3 位元組浪費掉了。

下面我們就來看看 Redis 是如何根據資料長度選擇不同大小的位元組來記錄 prevlen 的。

通過上面的 __ziplistInsert 函式即【原始碼A處】可以看到，ziplist 在對 prevlen 編碼時，會先呼叫 zipStorePrevEntryLength 函式，該函式程式碼如下所示：

unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) {
    if (p == NULL) {
        return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(uint32_t) + 1;
    } else {
        //判斷prevlen的長度是否小於ZIP_BIG_PREVLEN
        if (len < ZIP_BIG_PREVLEN) {
            //如果小於254位元組，那麼返回prevlen為1位元組
            p[0] = len;
            return 1;
        } else {
            //否則，呼叫zipStorePrevEntryLengthLarge進行編碼
            return zipStorePrevEntryLengthLarge(p,len);
        }
    }
}

可以看到，zipStorePrevEntryLength 函式會判斷前一個列表項是否小於 ZIP_BIG_PREVLEN（ZIP_BIG_PREVLEN 的值是 254）。如果是的話，那麼 prevlen 就使用 1 位元組表示；否則，zipStorePrevEntryLength 函式就呼叫 zipStorePrevEntryLengthLarge 函式進一步編碼。

zipStorePrevEntryLengthLarge 函式會先將 prevlen 的第 1 位元組設定為 254，然後使用記憶體拷貝函式 memcpy，將前一個列表項的長度值拷貝至 prevlen 的第 2 至第 5 位元組。最後，zipStorePrevEntryLengthLarge 函式返回 prevlen 的大小，為 5 位元組。

int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) {
    uint32_t u32;
    if (p != NULL) {
        //將prevlen的第1位元組設定為ZIP_BIG_PREVLEN，即254
        p[0] = ZIP_BIG_PREVLEN;
        u32 = len;
        //將前一個列表項的長度值拷貝至prevlen的第2至第5位元組，其中sizeof(u32)的值為4
        memcpy(p+1,&u32,sizeof(u32));
        ...
    }
    //返回prevlen的大小，為5位元組
    return 1 + sizeof(uint32_t);
}

好了，在瞭解了 prevlen 使用 1 位元組和 5 位元組兩種編碼方式後，我們再來學習下 encoding 的編碼方法。

3.2 使用不同大小的位元組來記錄 encoding 編碼

我們回到上面的 __ziplistInsert 函式即【原始碼A處】，可以看到執行完 zipStorePrevEntryLength 函式邏輯後，緊接著會呼叫 zipStoreEntryEncoding 函式。

ziplist 在 zipStoreEntryEncoding 函式中，針對整數和字串，就分別使用了不同位元組長度的編碼結果。

unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
    //預設編碼結果是1位元組
    unsigned char len = 1;
    //如果是字串資料
    if (ZIP_IS_STR(encoding)) {
        //如果字串長度小於等於63位元組（16進製為0x3f）
        if (rawlen <= 0x3f) {
            //預設編碼結果是1位元組
            if (!p) return len;
            ...
        }
        //字串長度小於等於16383位元組（16進製為0x3fff）
        else if (rawlen <= 0x3fff) {
            //編碼結果是2位元組
            len += 1;
            if (!p) return len;
            ...
        }
        //字串長度大於16383位元組
        else {
            //編碼結果是5位元組
            len += 4;
            if (!p) return len;
            ...
        }
    } else {
        /* 如果資料是整數，編碼結果是1位元組 */
        if (!p) return len;
        ...
    }
}

可以看到當資料是不同長度字串或是整數時，編碼結果的長度 len 大小不同。

總之，針對不同長度的資料，使用不同位元組大小的元資料資訊 prevlen 和 encoding 來記錄，這種方法可以有效地節省記憶體開銷。

封面

參考資料

極客時間《Redis原始碼剖析與實戰》
redis 原始碼 v6.2.4：http://github.com/redis/redis/tree/6.2.4

也許你對下面文章也感興趣。

「其他文章」