本文分析Redis字符串的實現原理，內容摘自新書《Redis核心原理與實踐》。這本書深入地分析了Redis常用特性的內部機制與實現方式，內容源自對Redis源碼的分析，并從中總結出設計思路、實現原理。通過閱讀本書，讀者可以快速、輕松地了解Redis的內部運行機制。

Redis是一個鍵值對數據庫（key-value DB），下面是一個簡單的Redis的命令：

> SET msg "hello wolrd"

該命令將鍵“msg”、值“hello wolrd”這兩個字符串保存到Redis數據庫中。
本章分析Redis如何在內存中保存這些字符串。

redisObject

Redis中的數據對象server.h/redisObject是Redis對內部存儲的數據定義的抽象類型，在深入分析Redis數據類型前，我們先了解redisObject，它的定義如下：

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

• type：數據類型。
• encoding：編碼格式，即存儲數據使用的數據結構。同一個類型的數據，Redis會根據數據量、占用內存等情況使用不同的編碼，最大限度地節省內存。
• refcount，引用計數，為了節省內存，Redis會在多處引用同一個redisObject。
• ptr：指向實際的數據結構，如sds，真正的數據存儲在該數據結構中。
• lru：24位，LRU時間戳或LFU計數。

redisObject負責裝載Redis中的所有鍵和值。redisObject.ptr指向真正存儲數據的數據結構，redisObject .refcount、redisObject.lru等屬性則用于管理數據（數據共享、數據過期等）。

提示：type、encoding、lru使用了C語言中的位段定義，這3個屬性使用同一個unsigned int的不同bit位。這樣可以最大限度地節省內存。

Redis定義了以下數據類型和編碼，如表1-1所示。

本書第1部分會對表1-1中前五種數據類型進行分析，最后兩種數據類型會在第5部分進行分析。如果讀者現在對表1-1中內容感到疑惑，則可以先帶著疑問繼續閱讀本書。

sds

我們知道，C語言中將空字符結尾的字符數組作為字符串，而Redis對此做了擴展，定義了字符串類型sds（Simple Dynamic String）。
Redis鍵都是字符串類型，Redis中最簡單的值類型也是字符串類型，
字符串類型的Redis值可用于很多場景，如緩存HTML片段、記錄用戶登錄信息等。

定義

提示：本節代碼如無特殊說明，均在sds.h/sds.c中。
對于不同長度的字符串，Redis定義了不同的sds結構體：

typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 
    uint8_t alloc;
    unsigned char flags;
    char buf[];
};
...

Redis還定義了sdshdr16、sdshdr32、sdshdr64結構體。為了版面整潔，這里不展示sdshdr16、sdshdr32、sdshdr64 結構體的代碼，它們與sdshdr8結構體基本相同，只是len、alloc屬性使用了 uint16_t、uint32、uint64_t類型。Redis定義不同sdshdr結構體是為了針對不同長度的字符串，使用合適的len、alloc屬性類型，最大限度地節省內存。

• len：已使用字節長度，即字符串長度。sdshdr5可存放的字符串長度小于32（25），sdshdr8可存放的字符串長度小于256（28），以此類推。由于該屬性記錄了字符串長度，所以sds可以在常數時間內獲取字符串長度。Redis限制了字符串的最大長度不能超過512MB。
• alloc：已申請字節長度，即sds總長度。alloc-len為sds中的可用（空閑）空間。
• flag：低3位代表sdshdr的類型，高5位只在sdshdr5中使用，表示字符串的長度，所以sdshdr5中沒有len屬性。另外，由于Redis對sdshdr5的定義是常量字符串，不支持擴容，所以不存在alloc屬性。
• buf：字符串內容，sds遵循C語言字符串的規范，保存一個空字符作為buf的結尾，并且不計入len、alloc屬性。這樣可以直接使用C語言strcmp、strcpy等函數直接操作sds。

提示：sdshdr結構體中的buf數組并沒有指定數組長度，它是C99規范定義的柔性數組—結構體中最后一個屬性可以被定義為一個大小可變的數組（該屬性前必須有其他屬性）。使用sizeof函數計算包含柔性數組的結構體大小，返回結果不包括柔性數組占用的內存。
另外，attribute((packed))關鍵字可以取消結構體內的字節對齊以節省內存。

操作分析

接下來看一下sds構建函數：

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    // [1]
    char type = sdsReqType(initlen);
    // [2]
    if (type == SDS_TYPE_5  initlen == 0) type = SDS_TYPE_8;
    // [3]
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1);
    ...
    // [4]
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen  SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        ...
    }
    if (initlen  init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    // [5]
    return s;
}

參數說明：

• init、initlen：字符串內容、長度。

【1】根據字符串長度，判斷對應的sdshdr類型。
【2】長度為0的字符串后續通常需要擴容，不應該使用sdshdr5，所以這里轉換為sdshdr8。
【3】sdsHdrSize函數負責查詢sdshdr結構體的長度，s_malloc函數負責申請內存空間，申請的內存空間長度為hdrlen+initlen+1，其中hdrlen為sdshdr結構體長度（不包含buf屬性），initlen為字符串內容長度，最后一個字節用于存放空字符“\0”。s_malloc與C語言的malloc函數的作用相同，負責分配指定大小的內存空間。
【4】給sdshdr屬性賦值。
SDS_HDR_VAR是一個宏，負責將sh指針轉化為對應的sdshdr結構體指針。
【5】注意，sds實際上就是char*的別名，這里返回的s指針指向sdshdr.buf屬性，即字符串內容。Redis通過該指針可以直接讀/寫字符串數據。

構建一個內容為“hello wolrd”的sds，其結構如圖1-1所示。

sds的擴容機制是一個很重要的功能。

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    // [1]
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1]  SDS_TYPE_MASK;
    int hdrlen;

    if (avail >= addlen) return s;
    // [2]
    len = sdslen(s);
    
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // [3]
    if (newlen  SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    // [4]    
    type = sdsReqType(newlen);
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    // [5]
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    // [6]
    sdssetalloc(s, newlen);
    return s;
}

參數說明：
addlen：要求擴容后可用長度（alloc-len）大于該參數。
【1】獲取當前可用空間長度。如果當前可用空間長度滿足要求，則直接返回。
【2】sdslen負責獲取字符串長度，由于sds.len中記錄了字符串長度，該操作復雜度為O(1)。這里len變量為原sds字符串長度，newlen變量為新sds長度。sh指向原sds的sdshdr結構體。
【3】預分配比參數要求多的內存空間，避免每次擴容都要進行內存拷貝操作。新sds長度如果小于SDS_MAX_PREALLOC（默認為1024×1024，單位為字節），則新sds長度自動擴容為2倍。否則，新sds長度自動增加SDS_MAX_PREALLOC。
【4】sdsReqType(newlen)負責計算新的sdshdr類型。注意，擴容后的類型不使用sdshdr5，該類型不支持擴容操作。
【5】如果擴容后sds還是同一類型，則使用s_realloc函數申請內存。否則，由于sds結構已經變動，必須移動整個sds，直接分配新的內存空間，并將原來的字符串內容復制到新的內存空間。s_realloc與C語言realloc函數的作用相同，負責為給定指針重新分配給定大小的內存空間。它會嘗試在給定指針原地址空間上重新分配，如原地址空間無法滿足要求，則分配新內存空間并復制內容。
【6】更新sdshdr.alloc屬性。

對上面“hello wolrd”的sds調用sdsMakeRoomFor(sds,64)，則生成的sds如圖1-2所示。

從圖1-2中可以看到，使用len記錄字符串長度后，字符串中可以存放空字符。Redis字符串支持二進制安全，可以將用戶的輸入存儲為沒有任何特定格式意義的原始數據流，因此Redis字符串可以存儲任何數據，比如圖片數據流或序列化對象。C語言字符串將空字符作為字符串結尾的特定標記字符，它不是二進制安全的。
sds常用函數如表1-2所示。