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

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

> SET msg "hello wolrd"

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

redisObject

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

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

• type：數(shù)據(jù)類型。
• encoding：編碼格式，即存儲數(shù)據(jù)使用的數(shù)據(jù)結(jié)構(gòu)。同一個類型的數(shù)據(jù)，Redis會根據(jù)數(shù)據(jù)量、占用內(nèi)存等情況使用不同的編碼，最大限度地節(jié)省內(nèi)存。
• refcount，引用計數(shù)，為了節(jié)省內(nèi)存，Redis會在多處引用同一個redisObject。
• ptr：指向?qū)嶋H的數(shù)據(jù)結(jié)構(gòu)，如sds，真正的數(shù)據(jù)存儲在該數(shù)據(jù)結(jié)構(gòu)中。
• lru：24位，LRU時間戳或LFU計數(shù)。

redisObject負(fù)責(zé)裝載Redis中的所有鍵和值。redisObject.ptr指向真正存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，redisObject .refcount、redisObject.lru等屬性則用于管理數(shù)據(jù)（數(shù)據(jù)共享、數(shù)據(jù)過期等）。

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

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

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

sds

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

定義

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

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結(jié)構(gòu)體。為了版面整潔，這里不展示sdshdr16、sdshdr32、sdshdr64 結(jié)構(gòu)體的代碼，它們與sdshdr8結(jié)構(gòu)體基本相同，只是len、alloc屬性使用了 uint16_t、uint32、uint64_t類型。Redis定義不同sdshdr結(jié)構(gòu)體是為了針對不同長度的字符串，使用合適的len、alloc屬性類型，最大限度地節(jié)省內(nèi)存。

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

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

操作分析

接下來看一下sds構(gòu)建函數(shù)：

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;
}

參數(shù)說明：

• init、initlen：字符串內(nèi)容、長度。

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

構(gòu)建一個內(nèi)容為“hello wolrd”的sds，其結(jié)構(gòu)如圖1-1所示。

sds的擴(kuò)容機(jī)制是一個很重要的功能。

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;
}

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

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

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

編碼

字符串類型一共有3種編碼：

• OBJ_ENCODING_EMBSTR：長度小于或等于OBJ_ENCODING_EMBSTR_SIZE_LIMIT（44字節(jié)）的字符串。

在該編碼中，redisObject、sds結(jié)構(gòu)存放在一塊連續(xù)內(nèi)存塊中，如圖1-3所示。

OBJ_ENCODING_EMBSTR編碼是Redis針對短字符串的優(yōu)化，有如下優(yōu)點：
(1)內(nèi)存申請和釋放都只需要調(diào)用一次內(nèi)存操作函數(shù)。
(2)redisObject、sdshdr結(jié)構(gòu)保存在一塊連續(xù)的內(nèi)存中，減少了內(nèi)存碎片。

• OBJ_ENCODING_RAW：長度大于OBJ_ENCODING_EMBSTR_SIZE_LIMIT的字符串，在該編碼中，redisObject、sds結(jié)構(gòu)存放在兩個不連續(xù)的內(nèi)存塊中。
• OBJ_ENCODING_INT：將數(shù)值型字符串轉(zhuǎn)換為整型，可以大幅降低數(shù)據(jù)占用的內(nèi)存空間，如字符串“123456789012”需要占用12字節(jié)，在Redis中，會將它轉(zhuǎn)化為long long類型，只占用8字節(jié)。

我們向Redis發(fā)送一個請求后，Redis會解析請求報文，并將命令、參數(shù)轉(zhuǎn)化為redisObjec。
object.c/createStringObject函數(shù)負(fù)責(zé)完成該操作：

robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

可以看到，這里根據(jù)字符串長度，將encoding轉(zhuǎn)化為OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR的redisObject。

將參數(shù)轉(zhuǎn)換為redisObject后，Redis再將redisObject存入數(shù)據(jù)庫，例如：

> SET Introduction "Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker. "

Redis會將鍵“Introduction”、值“Redis...”轉(zhuǎn)換為兩個redisObject，再將redisObject存入數(shù)據(jù)庫，結(jié)果如圖1-4所示。

Redis中的鍵都是字符串類型，并使用OBJ_ENCODING_RAW、OBJ_ENCODING_ EMBSTR編碼，而Redis還會嘗試將字符串類型的值轉(zhuǎn)換為OBJ_ENCODING_INT 編碼。object.c/tryObjectEncoding函數(shù)完成該操作：

robj *tryObjectEncoding(robj *o) {
    long value;
    sds s = o->ptr;
    size_t len;
    ...
    // [1]
     if (o->refcount > 1) return o;

    len = sdslen(s);
    // [2]
    if (len <= 20 && string2l(s,len,&value)) {
        // [3]
        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 {
            // [4]
            if (o->encoding == OBJ_ENCODING_RAW) {
                sdsfree(o->ptr);
                o->encoding = OBJ_ENCODING_INT;
                o->ptr = (void*) value;
                return o;
            } else if (o->encoding == OBJ_ENCODING_EMBSTR) {
                // [5]
                decrRefCount(o);
                return createStringObjectFromLongLongForValue(value);
            }
        }
    }

    // [6]
    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;
    }

    // [7]
    trimStringObjectIfNeeded(o);

    return o;
}

【1】該數(shù)據(jù)對象被多處引用，不能再進(jìn)行編碼操作，否則會影響其他地方的正常運行。
【2】如果字符串長度小于或等于20，則調(diào)用string2l函數(shù)嘗試將其轉(zhuǎn)換為long long類型，如果成功則返回1。
在C語言中，long long占用8字節(jié)，取值范圍是-9223372036854775808～9223372036854775807，因此最多能保存長度為19的字符串轉(zhuǎn)換后的數(shù)值，加上負(fù)數(shù)的符號位，一共20位。
下面是字符串可以轉(zhuǎn)換為OBJ_ENCODING_INT 編碼的處理步驟。
【3】首先嘗試使用shared.integers中的共享數(shù)據(jù)，避免重復(fù)創(chuàng)建相同數(shù)據(jù)對象而浪費內(nèi)存。shared是Redis啟動時創(chuàng)建的共享數(shù)據(jù)集，存放了Redis中常用的共享數(shù)據(jù)。shared.integers是一個整數(shù)數(shù)組，存放了小數(shù)字0～9999，共享于各個使用場景。
注意：如果配置了server.maxmemory，并使用了不支持共享數(shù)據(jù)的淘汰算法（LRU、LFU），那么這里不能使用共享數(shù)據(jù)，因為這時每個數(shù)據(jù)中都必須存在一個redisObjec.lru屬性，這些算法才可以正常工作。
【4】如果不能使用共享數(shù)據(jù)并且原編碼格式為OBJ_ENCODING_RAW，則將redisObject.ptr原來的sds類型替換為字符串轉(zhuǎn)換后的數(shù)值。
【5】如果不能使用共享數(shù)據(jù)并且原編碼格式為OBJ_ENCODING_EMBSTR，由于redisObject、sds存放在同一個內(nèi)存塊中，無法直接替換redisObject.ptr，所以調(diào)用createString- ObjectFromLongLongForValue函數(shù)創(chuàng)建一個新的redisObject，編碼為OBJ_ENCODING_INT，redisObject.ptr指向long long類型或long類型。
【6】到這里，說明字符串不能轉(zhuǎn)換為OBJ_ENCODING_INT 編碼，嘗試將其轉(zhuǎn)換為OBJ_ENCODING_EMBSTR編碼。
【7】到這里，說明字符串只能使用OBJ_ENCODING_RAW編碼，嘗試釋放sds中剩余的可用空間。
字符串類型的實現(xiàn)代碼在t_string.c中，讀者可以查看源碼了解更多實現(xiàn)細(xì)節(jié)。

提示：server.c/redisCommandTable定義了每個Redis命令與對應(yīng)的處理函數(shù)，讀者可以從這里查找感興趣的命令的處理函數(shù)。

struct redisCommand redisCommandTable[] = {
    ...
    {"get",getCommand,2,
     "read-only fast @string",
     0,NULL,1,1,1,0,0,0},

    {"set",setCommand,-3,
     "write use-memory @string",
     0,NULL,1,1,1,0,0,0},
     ...
}

GET命令的處理函數(shù)為getCommand，SET命令的處理函數(shù)為setCommand，以此類推。

另外，我們可以通過TYPE命令查看數(shù)據(jù)對象類型，通過OBJECT ENCODING命令查看編碼：

> SET msg "hello world"
OK
> TYPE msg
string
> OBJECT ENCODING  msg
"embstr"
> SET Introduction "Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker. "
OK
> TYPE Introduction
string
> OBJECT ENCODING  info
"raw"
> SET page 1
OK
> TYPE page
string
> OBJECT ENCODING  page
"int"

總結(jié)：

Redis中的所有鍵和值都是redisObject變量。

• sds是Redis定義的字符串類型，支持二進(jìn)制安全、擴(kuò)容。
• sds可以在常數(shù)時間內(nèi)獲取字符串長度，并使用預(yù)分配內(nèi)存機(jī)制減少內(nèi)存拷貝次數(shù)。
• Redis對數(shù)據(jù)編碼的主要目的是最大限度地節(jié)省內(nèi)存。字符串類型可以使用OBJ_ENCODING_ RAW、OBJ_ENCODING_EMBSTR、OBJ_ENCODING_INT編碼格式。

本文內(nèi)容摘自作者新書《Redis核心原理與實踐》，這本書深入地分析了Redis常用特性的內(nèi)部機(jī)制與實現(xiàn)方式，大部分內(nèi)容源自對Redis源碼的分析，并從中總結(jié)出設(shè)計思路、實現(xiàn)原理。通過閱讀本書，讀者可以快速、輕松地了解Redis的內(nèi)部運行機(jī)制。

京東鏈接
豆瓣鏈接

到此這篇關(guān)于Redis核心原理與實踐之字符串實現(xiàn)原理的文章就介紹到這了,更多相關(guān)Redis字符串實現(xiàn)原理內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論