學習分享(第 2 期):從源碼層面看 Redis 節省內存的設計

語言: CN / TW / HK

這裏記錄每週的學習分享,週一/週二發表,文章維護在 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 來記錄, 這種方法可以有效地節省內存開銷。

封面

參考資料

相關文章

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