本文轉自互聯網

本系列文章將整理到我在GitHub上的《Java面試指南》倉庫，更多精彩內容請到我的倉庫里查看

https://github.com/h3pl/Java-Tutorial

喜歡的話麻煩點下Star哈

文章首發于我的個人博客：

www.how2playlife.com

本文是微信公眾號【Java技術江湖】的《探索Redis設計與實現》其中一篇，本文部分內容來源于網絡，為了把本文主題講得清晰透徹，也整合了很多我認為不錯的技術博客內容，引用其中了一些比較好的博客文章，如有侵權，請聯系作者。

該系列博文會告訴你如何從入門到進階，Redis基本的使用方法，Redis的基本數據結構，以及一些進階的使用方法，同時也需要進一步了解Redis的底層數據結構，再接著，還會帶來Redis主從復制、集群、分布式鎖等方面的相關內容，以及作為緩存的一些使用方法和注意事項，以便讓你更完整地了解整個Redis相關的技術體系，形成自己的知識框架。

如果對本系列文章有什么建議，或者是有什么疑問的話，也可以關注公眾號【Java技術江湖】聯系作者，歡迎你參與本系列博文的創作和修訂。

本文是《 Redis內部數據結構詳解》系列的第三篇，講述在Redis實現中的一個基礎數據結構：robj。

那到底什么是robj呢？它有什么用呢？

從Redis的使用者的角度來看，一個Redis節點包含多個database（非cluster模式下默認是16個，cluster模式下只能是1個），而一個database維護了從key space到object space的映射關系。這個映射關系的key是string類型，而value可以是多種數據類型，比如：string, list, hash等。我們可以看到，key的類型固定是string，而value可能的類型是多個。

而從Redis內部實現的角度來看，在前面第一篇文章中，我們已經提到過，一個database內的這個映射關系是用一個dict來維護的。dict的key固定用一種數據結構來表達就夠了，這就是動態字符串sds。而value則比較復雜，為了在同一個dict內能夠存儲不同類型的value，這就需要一個通用的數據結構，這個通用的數據結構就是robj（全名是redisObject）。舉個例子：如果value是一個list，那么它的內部存儲結構是一個quicklist（quicklist的具體實現我們放在后面的文章討論）；如果value是一個string，那么它的內部存儲結構一般情況下是一個sds。當然實際情況更復雜一點，比如一個string類型的value，如果它的值是一個數字，那么Redis內部還會把它轉成long型來存儲，從而減小內存使用。而一個robj既能表示一個sds，也能表示一個quicklist，甚至還能表示一個long型。

robj的數據結構定義

在server.h中我們找到跟robj定義相關的代碼，如下（注意，本系列文章中的代碼片段全部來源于Redis源碼的3.2分支）：

/* Object types */
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4
/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
#define LRU_BITS 24
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

一個robj包含如下5個字段：

• type: 對象的數據類型。占4個bit。可能的取值有5種：OBJ_STRING, OBJ_LIST, OBJ_SET, OBJ_ZSET, OBJ_HASH，分別對應Redis對外暴露的5種數據結構（即我們在第一篇文章中提到的第一個層面的5種數據結構）。
• encoding: 對象的內部表示方式（也可以稱為編碼）。占4個bit。可能的取值有10種，即前面代碼中的10個OBJ_ENCODING_XXX常量。
• lru: 做LRU替換算法用，占24個bit。這個不是我們這里討論的重點，暫時忽略。
• refcount: 引用計數。它允許robj對象在某些情況下被共享。
• ptr: 數據指針。指向真正的數據。比如，一個代表string的robj，它的ptr可能指向一個sds結構；一個代表list的robj，它的ptr可能指向一個quicklist。

這里特別需要仔細察看的是encoding字段。對于同一個type，還可能對應不同的encoding，這說明同樣的一個數據類型，可能存在不同的內部表示方式。而不同的內部表示，在內存占用和查找性能上會有所不同。

比如，當type = OBJ_STRING的時候，表示這個robj存儲的是一個string，這時encoding可以是下面3種中的一種：

• OBJ_ENCODING_RAW: string采用原生的表示方式，即用sds來表示。
• OBJ_ENCODING_INT: string采用數字的表示方式，實際上是一個long型。
• OBJ_ENCODING_EMBSTR: string采用一種特殊的嵌入式的sds來表示。接下來我們會討論到這個細節。

再舉一個例子：當type = OBJ_HASH的時候，表示這個robj存儲的是一個hash，這時encoding可以是下面2種中的一種：

• OBJ_ENCODING_HT: hash采用一個dict來表示。
• OBJ_ENCODING_ZIPLIST: hash采用一個ziplist來表示（ziplist的具體實現我們放在后面的文章討論）。

本文剩余主要部分將針對表示string的robj對象，圍繞它的3種不同的encoding來深入討論。前面代碼段中出現的所有10種encoding，在這里我們先簡單解釋一下，在這個系列后面的文章中，我們應該還有機會碰到它們。

• OBJ_ENCODING_RAW: 最原生的表示方式。其實只有string類型才會用這個encoding值（表示成sds）。
• OBJ_ENCODING_INT: 表示成數字。實際用long表示。
• OBJ_ENCODING_HT: 表示成dict。
• OBJ_ENCODING_ZIPMAP: 是個舊的表示方式，已不再用。在小于Redis 2.6的版本中才有。
• OBJ_ENCODING_LINKEDLIST: 也是個舊的表示方式，已不再用。
• OBJ_ENCODING_ZIPLIST: 表示成ziplist。
• OBJ_ENCODING_INTSET: 表示成intset。用于set數據結構。
• OBJ_ENCODING_SKIPLIST: 表示成skiplist。用于sorted set數據結構。
• OBJ_ENCODING_EMBSTR: 表示成一種特殊的嵌入式的sds。
• OBJ_ENCODING_QUICKLIST: 表示成quicklist。用于list數據結構。

我們來總結一下robj的作用：

• 為多種數據類型提供一種統一的表示方式。
• 允許同一類型的數據采用不同的內部表示，從而在某些情況下盡量節省內存。
• 支持對象共享和引用計數。當對象被共享的時候，只占用一份內存拷貝，進一步節省內存。

string robj的編碼過程

當我們執行Redis的set命令的時候，Redis首先將接收到的value值（string類型）表示成一個type = OBJ_STRING并且encoding = OBJ_ENCODING_RAW的robj對象，然后在存入內部存儲之前先執行一個編碼過程，試圖將它表示成另一種更節省內存的encoding方式。這一過程的核心代碼，是object.c中的tryObjectEncoding函數。

robj *tryObjectEncoding(robj *o) {
    long value;
    sds s = o->ptr;
    size_t len;
    /* Make sure this is a string object, the only type we encode
     * in this function. Other types use encoded memory efficient
     * representations but are handled by the commands implementing
     * the type. */
    serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);
    /* We try some specialized encoding only for objects that are
     * RAW or EMBSTR encoded, in other words objects that are still
     * in represented by an actually array of chars. */
    if (!sdsEncodedObject(o)) return o;
    /* It's not safe to encode shared objects: shared objects can be shared
     * everywhere in the "object space" of Redis and may end in places where
     * they are not handled. We handle them only as values in the keyspace. */
     if (o->refcount > 1) return o;
    /* Check if we can represent this string as a long integer.
     * Note that we are sure that a string larger than 21 chars is not
     * representable as a 32 nor 64 bit integer. */
    len = sdslen(s);
    if (len <= 21 && string2l(s,len,&value)) {
        /* This object is encodable as a long. Try to use a shared object.
         * Note that we avoid using shared integers when maxmemory is used
         * because every object needs to have a private LRU field for the LRU
         * algorithm to work well. */
        if ((server.maxmemory == 0 ||
             (server.maxmemory_policy != MAXMEMORY_VOLATILE_LRU &&
              server.maxmemory_policy != MAXMEMORY_ALLKEYS_LRU)) &&
            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;
            o->ptr = (void*) value;
            return o;
        }
    }
    /* If the string is small and is still RAW encoded,
     * try the EMBSTR encoding which is more efficient.
     * In this representation the object and the SDS string are allocated
     * in the same chunk of memory to save space and cache misses. */
    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;
    }
    /* We can't encode the object...
     *
     * Do the last try, and at least optimize the SDS string inside
     * the string object to require little space, in case there
     * is more than 10% of free space at the end of the SDS string.
     *
     * We do that only for relatively large strings as this branch
     * is only entered if the length of the string is greater than
     * OBJ_ENCODING_EMBSTR_SIZE_LIMIT. */
    if (o->encoding == OBJ_ENCODING_RAW &&
        sdsavail(s) > len/10)
    {
        o->ptr = sdsRemoveFreeSpace(o->ptr);
    }
    /* Return the original object. */
    return o;
}

這段代碼執行的操作比較復雜，我們有必要仔細看一下每一步的操作：

• 第1步檢查，檢查type。確保只對string類型的對象進行操作。
• 第2步檢查，檢查encoding。sdsEncodedObject是定義在server.h中的一個宏，確保只對OBJ_ENCODING_RAW和OBJ_ENCODING_EMBSTR編碼的string對象進行操作。這兩種編碼的string都采用sds來存儲，可以嘗試進一步編碼處理。

#define sdsEncodedObject(objptr) (objptr->encoding == OBJ_ENCODING_RAW || objptr->encoding == OBJ_ENCODING_EMBSTR)

• 第3步檢查，檢查refcount。引用計數大于1的共享對象，在多處被引用。由于編碼過程結束后robj的對象指針可能會變化（我們在前一篇介紹sdscatlen函數的時候提到過類似這種接口使用模式），這樣對于引用計數大于1的對象，就需要更新所有地方的引用，這不容易做到。因此，對于計數大于1的對象不做編碼處理。
• 試圖將字符串轉成64位的long。64位的long所能表達的數據范圍是-2^63到2^63-1，用十進制表達出來最長是20位數（包括負號）。這里判斷小于等于21，似乎是寫多了，實際判斷小于等于20就夠了（如果我算錯了請一定告訴我哦）。string2l如果將字符串轉成long轉成功了，那么會返回1并且將轉好的long存到value變量里。
• 在轉成long成功時，又分為兩種情況。
  • 第一種情況：如果Redis的配置不要求運行LRU替換算法，且轉成的long型數字的值又比較小（小于OBJ_SHARED_INTEGERS，在目前的實現中這個值是10000），那么會使用共享數字對象來表示。之所以這里的判斷跟LRU有關，是因為LRU算法要求每個robj有不同的lru字段值，所以用了LRU就不能共享robj。shared.integers是一個長度為10000的數組，里面預存了10000個小的數字對象。這些小數字對象都是encoding = OBJ_ENCODING_INT的string robj對象。
  • 第二種情況：如果前一步不能使用共享小對象來表示，那么將原來的robj編碼成encoding = OBJ_ENCODING_INT，這時ptr字段直接存成這個long型的值。注意ptr字段本來是一個void *指針（即存儲的是內存地址），因此在64位機器上有64位寬度，正好能存儲一個64位的long型值。這樣，除了robj本身之外，它就不再需要額外的內存空間來存儲字符串值。
• 接下來是對于那些不能轉成64位long的字符串進行處理。最后再做兩步處理：
  • 如果字符串長度足夠小（小于等于OBJ_ENCODING_EMBSTR_SIZE_LIMIT，定義為44），那么調用createEmbeddedStringObject編碼成encoding = OBJ_ENCODING_EMBSTR；
  • 如果前面所有的編碼嘗試都沒有成功（仍然是OBJ_ENCODING_RAW），且sds里空余字節過多，那么做最后一次努力，調用sds的sdsRemoveFreeSpace接口來釋放空余字節。

其中調用的createEmbeddedStringObject，我們有必要看一下它的代碼：

robj *createEmbeddedStringObject(const char *ptr, size_t len) {
    robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);
    struct sdshdr8 *sh = (void*)(o+1);
    o->type = OBJ_STRING;
    o->encoding = OBJ_ENCODING_EMBSTR;
    o->ptr = sh+1;
    o->refcount = 1;
    o->lru = LRU_CLOCK();
    sh->len = len;
    sh->alloc = len;
    sh->flags = SDS_TYPE_8;
    if (ptr) {
        memcpy(sh->buf,ptr,len);
        sh->buf[len] = '\0';
    } else {
        memset(sh->buf,0,len+1);
    }
    return o;
}

createEmbeddedStringObject對sds重新分配內存，將robj和sds放在一個連續的內存塊中分配，這樣對于短字符串的存儲有利于減少內存碎片。這個連續的內存塊包含如下幾部分：

• 16個字節的robj結構。
• 3個字節的sdshdr8頭。
• 最多44個字節的sds字符數組。
• 1個NULL結束符。

加起來一共不超過64字節（16+3+44+1），因此這樣的一個短字符串可以完全分配在一個64字節長度的內存塊中。

string robj的解碼過程

當我們需要獲取字符串的值，比如執行get命令的時候，我們需要執行與前面講的編碼過程相反的操作——解碼。

這一解碼過程的核心代碼，是object.c中的getDecodedObject函數。

robj *getDecodedObject(robj *o) {
    robj *dec;
    if (sdsEncodedObject(o)) {
        incrRefCount(o);
        return o;
    }
    if (o->type == OBJ_STRING && o->encoding == OBJ_ENCODING_INT) {
        char buf[32];
        ll2string(buf,32,(long)o->ptr);
        dec = createStringObject(buf,strlen(buf));
        return dec;
    } else {
        serverPanic("Unknown encoding type");
    }
}

這個過程比較簡單，需要我們注意的點有：

• 編碼為OBJ_ENCODING_RAW和OBJ_ENCODING_EMBSTR的字符串robj對象，不做變化，原封不動返回。站在使用者的角度，這兩種編碼沒有什么區別，內部都是封裝的sds。

• 編碼為數字的字符串robj對象，將long重新轉為十進制字符串的形式，然后調用createStringObject轉為sds的表示。注意：這里由long轉成的sds字符串長度肯定不超過20，而根據createStringObject的實現，它們肯定會被編碼成OBJ_ENCODING_EMBSTR的對象。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);
  

  }

再談sds與string的關系

在上一篇文章中，我們簡單地提到了sds與string的關系；在本文介紹了robj的概念之后，我們重新總結一下sds與string的關系。

• 確切地說，string在Redis中是用一個robj來表示的。
• 用來表示string的robj可能編碼成3種內部表示：OBJ_ENCODING_RAW, OBJ_ENCODING_EMBSTR, OBJ_ENCODING_INT。其中前兩種編碼使用的是sds來存儲，最后一種OBJ_ENCODING_INT編碼直接把string存成了long型。
• 在對string進行incr, decr等操作的時候，如果它內部是OBJ_ENCODING_INT編碼，那么可以直接進行加減操作；如果它內部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR編碼，那么Redis會先試圖把sds存儲的字符串轉成long型，如果能轉成功，再進行加減操作。
• 對一個內部表示成long型的string執行append, setbit, getrange這些命令，針對的仍然是string的值（即十進制表示的字符串），而不是針對內部表示的long型進行操作。比如字符串”32”，如果按照字符數組來解釋，它包含兩個字符，它們的ASCII碼分別是0x33和0x32。當我們執行命令setbit key 7 0的時候，相當于把字符0x33變成了0x32，這樣字符串的值就變成了”22”。而如果將字符串”32”按照內部的64位long型來解釋，那么它是0x0000000000000020，在這個基礎上執行setbit位操作，結果就完全不對了。因此，在這些命令的實現中，會把long型先轉成字符串再進行相應的操作。由于篇幅原因，這三個命令的實現代碼這里就不詳細介紹了，有興趣的讀者可以參考Redis源碼：
  • t_string.c中的appendCommand函數；
  • biops.c中的setbitCommand函數；
  • t_string.c中的getrangeCommand函數。

值得一提的是，append和setbit命令的實現中，都會最終調用到db.c中的dbUnshareStringValue函數，將string對象的內部編碼轉成OBJ_ENCODING_RAW的（只有這種編碼的robj對象，其內部的sds 才能在后面自由追加新的內容），并解除可能存在的對象共享狀態。這里面調用了前面提到的getDecodedObject。

robj *dbUnshareStringValue(redisDb *db, robj *key, robj *o) {
    serverAssert(o->type == OBJ_STRING);
    if (o->refcount != 1 || o->encoding != OBJ_ENCODING_RAW) {
        robj *decoded = getDecodedObject(o);
        o = createRawStringObject(decoded->ptr, sdslen(decoded->ptr));
        decrRefCount(decoded);
        dbOverwrite(db,key,o);
    }
    return o;
}

robj的引用計數操作

將robj的引用計數加1和減1的操作，定義在object.c中：

void incrRefCount(robj *o) {
    o->refcount++;
}
void decrRefCount(robj *o) {
    if (o->refcount <= 0) serverPanic("decrRefCount against refcount <= 0");
    if (o->refcount == 1) {
        switch(o->type) {
        case OBJ_STRING: freeStringObject(o); break;
        case OBJ_LIST: freeListObject(o); break;
        case OBJ_SET: freeSetObject(o); break;
        case OBJ_ZSET: freeZsetObject(o); break;
        case OBJ_HASH: freeHashObject(o); break;
        default: serverPanic("Unknown object type"); break;
        }
        zfree(o);
    } else {
        o->refcount--;
    }
}

我們特別關注一下將引用計數減1的操作decrRefCount。如果只剩下最后一個引用了（refcount已經是1了），那么在decrRefCount被調用后，整個robj將被釋放。

注意：Redis的del命令就依賴decrRefCount操作將value釋放掉。

經過了本文的討論，我們很容易看出，robj所表示的就是Redis對外暴露的第一層面的數據結構：string, list, hash, set, sorted set，而每一種數據結構的底層實現所對應的是哪個（或哪些）第二層面的數據結構（dict, sds, ziplist, quicklist, skiplist, 等），則通過不同的encoding來區分。可以說，robj是聯結兩個層面的數據結構的橋梁。

本文詳細介紹了OBJ_STRING類型的字符串對象的底層實現，其編碼和解碼過程在Redis里非常重要，應用廣泛，我們在后面的討論中可能還會遇到。現在有了robj的概念基礎，我們下一篇會討論ziplist，以及它與hash的關系。

后記(追加于2016-07-09): 本文在解析“將string編碼成long型”的代碼時提到的判斷21字節的問題，后來已經提交給 @antirez并合并進了unstable分支，詳見 commit f648c5a。