天天看點
傳回

Redis核心原理與實踐--字元串實作原理

本文分析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所示。

Redis核心原理與實踐--字元串實作原理

本書第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所示。

Redis核心原理與實踐--字元串實作原理

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所示。

Redis核心原理與實踐--字元串實作原理

從圖1-2中可以看到，使用len記錄字元串長度後，字元串中可以存放空字元。Redis字元串支援二進制安全，可以将使用者的輸入存儲為沒有任何特定格式意義的原始資料流，是以Redis字元串可以存儲任何資料，比如圖檔資料流或序列化對象。C語言字元串将空字元作為字元串結尾的特定标記字元，它不是二進制安全的。

sds常用函數如表1-2所示。

函數 作用
sdsnew，sdsempty 建立sds
sdsfree，sdsclear，sdsRemoveFreeSpace 釋放sds，清空sds中的字元串内容，移除sds剩餘的可用空間
sdslen 擷取sds字元串長度
sdsdup 将給定字元串複制到sds中，覆寫原字元串
sdscat 将給定字元串拼接到sds字元串内容後
sdscmp 對比兩個sds字元串是否相同
sdsrange 擷取子字元串，不在指定範圍内的字元串将被清除

編碼

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

  • OBJ_ENCODING_EMBSTR：長度小于或等于OBJ_ENCODING_EMBSTR_SIZE_LIMIT（44位元組）的字元串。

    在該編碼中，redisObject、sds結構存放在一塊連續記憶體塊中，如圖1-3所示。

    Redis核心原理與實踐--字元串實作原理

OBJ_ENCODING_EMBSTR編碼是Redis針對短字元串的優化，有如下優點：

(1)記憶體申請和釋放都隻需要調用一次記憶體操作函數。

(2)redisObject、sdshdr結構儲存在一塊連續的記憶體中，減少了記憶體碎片。

  • OBJ_ENCODING_RAW：長度大于OBJ_ENCODING_EMBSTR_SIZE_LIMIT的字元串，在該編碼中，redisObject、sds結構存放在兩個不連續的記憶體塊中。
  • OBJ_ENCODING_INT：将數值型字元串轉換為整型，可以大幅降低資料占用的記憶體空間，如字元串“123456789012”需要占用12位元組，在Redis中，會将它轉化為long long類型，隻占用8位元組。

我們向Redis發送一個請求後，Redis會解析請求封包，并将指令、參數轉化為redisObjec。

object.c/createStringObject函數負責完成該操作：

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

可以看到，這裡根據字元串長度，将encoding轉化為OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR的redisObject。

将參數轉換為redisObject後，Redis再将redisObject存入資料庫，例如：

> 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...”轉換為兩個redisObject，再将redisObject存入資料庫，結果如圖1-4所示。

Redis核心原理與實踐--字元串實作原理

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

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】該資料對象被多處引用，不能再進行編碼操作，否則會影響其他地方的正常運作。

【2】如果字元串長度小于或等于20，則調用string2l函數嘗試将其轉換為long long類型，如果成功則傳回1。

在C語言中，long long占用8位元組，取值範圍是-9223372036854775808～9223372036854775807，是以最多能儲存長度為19的字元串轉換後的數值，加上負數的符号位，一共20位。

下面是字元串可以轉換為OBJ_ENCODING_INT 編碼的處理步驟。

【3】首先嘗試使用shared.integers中的共享資料，避免重複建立相同資料對象而浪費記憶體。shared是Redis啟動時建立的共享資料集，存放了Redis中常用的共享資料。shared.integers是一個整數數組，存放了小數字0～9999，共享于各個使用場景。

注意：如果配置了server.maxmemory，并使用了不支援共享資料的淘汰算法（LRU、LFU），那麼這裡不能使用共享資料，因為這時每個資料中都必須存在一個redisObjec.lru屬性，這些算法才可以正常工作。

【4】如果不能使用共享資料并且原編碼格式為OBJ_ENCODING_RAW，則将redisObject.ptr原來的sds類型替換為字元串轉換後的數值。

【5】如果不能使用共享資料并且原編碼格式為OBJ_ENCODING_EMBSTR，由于redisObject、sds存放在同一個記憶體塊中，無法直接替換redisObject.ptr，是以調用createString- ObjectFromLongLongForValue函數建立一個新的redisObject，編碼為OBJ_ENCODING_INT，redisObject.ptr指向long long類型或long類型。

【6】到這裡，說明字元串不能轉換為OBJ_ENCODING_INT 編碼，嘗試将其轉換為OBJ_ENCODING_EMBSTR編碼。

【7】到這裡，說明字元串隻能使用OBJ_ENCODING_RAW編碼，嘗試釋放sds中剩餘的可用空間。

字元串類型的實作代碼在t_string.c中，讀者可以檢視源碼了解更多實作細節。

提示：server.c/redisCommandTable定義了每個Redis指令與對應的處理函數，讀者可以從這裡查找感興趣的指令的處理函數。 
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指令的處理函數為getCommand，SET指令的處理函數為setCommand，以此類推。

另外，我們可以通過TYPE指令檢視資料對象類型，通過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"

總結：

  • Redis中的所有鍵和值都是redisObject變量。
  • sds是Redis定義的字元串類型，支援二進制安全、擴容。
  • sds可以在常數時間内擷取字元串長度，并使用預配置設定記憶體機制減少記憶體拷貝次數。
  • Redis對資料編碼的主要目的是最大限度地節省記憶體。字元串類型可以使用OBJ_ENCODING_ RAW、OBJ_ENCODING_EMBSTR、OBJ_ENCODING_INT編碼格式。

本文内容摘自作者新書《Redis核心原理與實踐》。本書通過深入分析Redis 6.0源碼，總結了Redis核心功能的設計與實作。通過閱讀本書，讀者可以深入了解Redis内部機制及最新特性，并學習到Redis相關的資料結構與算法、Unix程式設計、存儲系統設計，分布式系統架構等一系列知識。

經過該書編輯同意，我會繼續在個人技術公衆号（binecy）釋出書中部分章節内容，作為書的預覽内容，歡迎大家查閱，謝謝。

語雀平台預覽：《Redis核心原理與實踐》

京東連結

Redis核心原理與實踐
上一篇: 态勢感覺業務安全情報新庫上線
下一篇: 論windows系統的安全性（上篇）

繼續閱讀