【Redis 源碼】字符串詳解

前言:

學過 C 的人應該都知道 C 的字符串是以字節數組存在,然後以 \ 0 結尾。計算字符串的長度使用 strlen 函數,這個標準庫函數的複雜程度是 O(n)。它需要對字節數組進行掃描遍歷計算長度。作爲 redis 單線程的應用是這種形式是比較消耗性能的。
Redis 實現了字節的字符串叫 sds(Simple Dynamic String),它是一個帶着長度的信息的結構體,屬於柔性字符串。

Redis 的字符串形式如下:

一. Redis 字符串內部編碼介紹:

redis 字符串的內部編碼分爲三種:int、embstr、raw。

| 內部編碼 | 條件 | 備註 | | --- | --- | --- | | int | 滿足 long 取值範圍,也就是 - 9223372036854775808 ~ 9223372036854775807 之間 | 如果設置字符串爲數組類型操作 long 的範圍,小於 44 字節。比如值爲 9223372036854775808 則類型會變爲 embstr | | embstr | 非數組類型,若爲數字。則不在 long 取值範圍。且小於 44 字節。redis 3.2 之前則小於 39 | 如果大於 44 字節,則會變爲 raw 類型,連續內存。注:redis3.2 版本後 | | raw | 大於 44 字節。redis3.2 之後 | 滿足等於或大於 45 字節,非連續內存。 |

注意事項:
(1) embstr 的 44 個字節是 redis3.2 版本之後,之前爲 39;
(2)說 raw 大於 44 個字節這個不能說完全對,利用 APPEND 命令追加後的字符串爲 raw 類型。

1.1 內部編碼 int


debug object 參數解釋:

| 名稱 | 備註 | | --- | --- | | Value at | 位於地址 | | refcount | 引用數量 | | encoding | 編碼 | | serializedlength | 序列化長度(字符串長度) | | lru | LRU 時間 | | lru_seconds_idle | LRU 閒置時間 |

當設置鍵值 test1 爲 9223372036854775807 時,因爲 long 的曲直範圍是 -9223372036854775808 ~ 9223372036854775807 之間。
所以通過 debug object 第一次打印 test1 類型爲 int,當前的長度爲 20。由於第二次打印是,設置 test1 爲 9223372036854775808,超過了 long 的最大值。並且長度爲 20,則現打印類型爲 embstr。

1.2 內部編碼 embstr 和 raw



當設置鍵值 test1 爲 0123456789abcdefghijklmnopqrstuvwxyz12345678 時,因爲 <=44 個字節。所以編碼類型爲 embstr。
當設置鍵值 test1 爲 0123456789abcdefghijklmnopqrstuvwxyz123456789 時,test1 此時爲 45 個字節,則編碼類型爲 raw。

1.3 源碼解析

setCommand 命令源碼

void setCommand(client *c) {
    省略...
    c->argv[2] = tryObjectEncoding(c->argv[2]);  //嘗試對字符串對象進行編碼以節省空間
    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

object.c 中 tryObjectEncoding 函數

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44  //embstr長度限制

robj *tryObjectEncoding(robj *o) {
    long value;
    sds s = o->ptr;
    size_t len;
    
    /* 確保這是一個字符串對象 */
    serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);

    /*我們只對RAW或EMBSTR編碼的,換句話說,仍然是由實際的字符數組表示。*/
    if (!sdsEncodedObject(o)) return o;

    /*對共享對象進行編碼是不安全的:共享對象可以共享
     *在Redis的“對象空間”中的任何地方,並且可能在
     *他們沒有被處理。我們只將它們作爲鍵空間中的值來處理。*/
     if (o->refcount > 1) return o;

    /* 檢查字符串是否爲long類型整數,如果len <=20且在LONG_MIN和LONG_MAX範圍內,則是int編碼 */
    len = sdslen(s);
    if (len <= 20 && string2l(s,len,&value)) {
       /*此對象可編碼爲long。嘗試使用共享對象。
        *注意,當使用maxmemory時,我們避免使用共享整數
        *因爲每個對象都需要有一個用於LRU的私有LRU字段
        *算法運行良好。*/
        if ((server.maxmemory == 0 ||
            !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) &&
            value >= 0 &&
            value < OBJ_SHARED_INTEGERS)
        {
            decrRefCount(o);
            incrRefCount(shared.integers[value]);
            return shared.integers[value];
        } else {
            if (o->encoding == OBJ_ENCODING_RAW) sdsfree(o->ptr);
            o->encoding = OBJ_ENCODING_INT;  //設置爲int編碼
            o->ptr = (void*) value;
            return o;
        }
    }

    //判斷長度小於或等於44,返回一個OBJ_ENCODING_EMBSTR編碼
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
        robj *emb;

        if (o->encoding == OBJ_ENCODING_EMBSTR) return o;
        emb = createEmbeddedStringObject(s,sdslen(s));
        decrRefCount(o);
        return emb;
    }

    /**我們無法對對象進行編碼。。。
     *做最後一次嘗試,至少優化SDS字符串。
     *字符串對象需要很少的空間,以防大於SDS字符串末尾可用空間的10%。
     *我們這樣做只是爲了相對較大的字符串僅當字符串長度大於44。
     */
    if (o->encoding == OBJ_ENCODING_RAW &&
        sdsavail(s) > len/10)
    {
        o->ptr = sdsRemoveFreeSpace(o->ptr);
    }
    
    return o;  //返回原始對象
}

1.4 爲什麼 OBJ_ENCODING_EMBSTR_SIZE_LIMIT 是 44 個字節

redisObject 結構體:

 typedef struct redisObject {
    unsigned type:4;       //4bit
    unsigned encoding:4;   //4bit
    unsigned lru:LRU_BITS; //24bit
    int refcount;          //4byte
    void *ptr;             //8byte
} robj

redisObject 的總大小應該是 16 字節 = (4bit + 4bit + 24bit) + 4byte + 8byte。32bit = 4byte
sds 結構體的最小單位應該是 sdshdr8(sdshdr5 默認會轉化爲 sdshdr8),接下來會說到。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;          //1byte
    uint8_t alloc;        //1byte
    unsigned char flags;  //1byte
    char buf[];
};

內存分配器 jemalloc/tcmalloc 分配內存大小單位爲:2、4、8、16、32、64。爲了能完整容納一個 embstr 對象,最小分配 32 個字節空間。如果稍微長一點就是 64 個字節空間。如果超出 64 個字節,Redis 認爲它是一個大字符串。形式就變爲 RAW,不在是一個連續內存。

64 - 16 - 3 - 1 = 44,64 減去 redisObject 結構體的 16 個字節再減去 sds 結構體的 3 個字節和一個 \ 0 字符的 1 個字節。

二. SDS 介紹:

2.1 SDS 數據結構

sds 的 5 種數據結構,sds.h 中

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

看到以上宏可能不是特別容易理解,接下來我們看一段源碼, sds.c 中:

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)  //2的5次方
        return SDS_TYPE_5; 
    if (string_size < 1<<8)  //2的8次方
        return SDS_TYPE_8;
    if (string_size < 1<<16) //2的16次方
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32) //2的32次方
        return SDS_TYPE_32;
#endif
    return SDS_TYPE_64;       
}

/*
 根據長度創建一個sds字符串
*/
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen); //獲取字符串類型
    //空字符串默認type爲SDS_TYPE_8
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1);
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    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;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';  //字符串結尾添加一個\0
    return s;
}

sds 的數據結構取值範圍:

2.2 SDS 字符串擴容

可以先看一下追加字符串函數,在 sds.c 中:

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s); //獲取當前字符串長度

    s = sdsMakeRoomFor(s,len); //按照需要空間調整字符串空間
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);  //追加到目標字符串數組中
    sdssetlen(s, curlen+len);  //設置追加後長度
    s[curlen+len] = '\0';      //追加後
    return s;
}

sds 字符串調整空間函數,在 sds.c 中

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);  //獲取當前剩下空間
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* 如果空間足夠時返回原來的 */
    if (avail >= addlen) return s;

    len = sdslen(s);                   //獲取長度
    sh = (char*)s-sdsHdrSize(oldtype); //獲取數據
        newlen = (len+addlen);         //計算新的長度
    if (newlen < SDS_MAX_PREALLOC)      // < 1M 2倍擴容,1M = 1024 * 1024
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;    // > 1M 擴容1M

    type = sdsReqType(newlen);  //獲得新長度的sds類型

    if (type == SDS_TYPE_5) type = SDS_TYPE_8;  //type5 默認轉成 type8

    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);
    }
    sdssetalloc(s, newlen);
    return s;
}

擴容時,字符串長度小於 1M 之前,擴容空間都是成倍增加。當長度大於 1M 之後,爲了避免空間過大浪費。
每次擴容只會多分配 1M。

三. 總結:

(1) redis 的字符串爲了節省開銷採用 sds 結構作爲字符串結構,sds 結構分爲:sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64 五種,字符串會根據不同的大小通過 sdsReqType 函數獲取對應的類型。
(2) redis 字符串的編碼分爲三種,int,embstr,raw。int 的範圍爲 min long 到 max long 的整數之間,embstr 爲非整數 44 字節內,raw 爲大於 44 字節字符串。通過 append 命令追加字符串不夠字節影響,編碼類型直接時 raw。
(3)redis 字符串擴容,小於 1M 成倍增加,大於或等於 1M 每次只增加 1M。這種做法是避免資源浪費。
(4)OBJ_ENCODING_EMBSTR_SIZE_LIMIT 等於 44 字節,是因爲 64 字節減去 redisObject 結構體的 16 個字節再減去 sds 結構體的 3 個字節和一個 \ 0 字符的 1 個字節。
(5)sdshdr5 默認爲變爲 sdshdr8。

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/mGvynXnErM8qlCRT7TMgVg