本文轉(zhuǎn)自互聯(lián)網(wǎng)
創(chuàng)新互聯(lián)是一家專業(yè)提供錦州企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計、網(wǎng)站制作、成都h5網(wǎng)站建設(shè)、小程序制作等業(yè)務(wù)。10年已為錦州眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計公司優(yōu)惠進行中。
本系列文章將整理到我在GitHub上的《Java面試指南》倉庫，更多精彩內(nèi)容請到我的倉庫里查看
https://github.com/h3pl/Java-Tutorial
喜歡的話麻煩點下Star哈
文章首發(fā)于我的個人博客：
www.how2playlife.com
本文是微信公眾號【Java技術(shù)江湖】的《探索redis設(shè)計與實現(xiàn)》其中一篇，本文部分內(nèi)容來源于網(wǎng)絡(luò)，為了把本文主題講得清晰透徹，也整合了很多我認為不錯的技術(shù)博客內(nèi)容，引用其中了一些比較好的博客文章，如有侵權(quán)，請聯(lián)系作者。
該系列博文會告訴你如何從入門到進階，Redis基本的使用方法，Redis的基本數(shù)據(jù)結(jié)構(gòu)，以及一些進階的使用方法，同時也需要進一步了解Redis的底層數(shù)據(jù)結(jié)構(gòu)，再接著，還會帶來Redis主從復(fù)制、集群、分布式鎖等方面的相關(guān)內(nèi)容，以及作為緩存的一些使用方法和注意事項，以便讓你更完整地了解整個Redis相關(guān)的技術(shù)體系，形成自己的知識框架。
如果對本系列文章有什么建議，或者是有什么疑問的話，也可以關(guān)注公眾號【Java技術(shù)江湖】聯(lián)系作者，歡迎你參與本系列博文的創(chuàng)作和修訂。
本文是《 Redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)詳解》系列的第三篇，講述在Redis實現(xiàn)中的一個基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：robj。
那到底什么是robj呢？它有什么用呢？
從Redis的使用者的角度來看，一個Redis節(jié)點包含多個database（非cluster模式下默認是16個，cluster模式下只能是1個），而一個database維護了從key space到object space的映射關(guān)系。這個映射關(guān)系的key是string類型，而value可以是多種數(shù)據(jù)類型，比如：string, list, hash等。我們可以看到，key的類型固定是string，而value可能的類型是多個。
而從Redis內(nèi)部實現(xiàn)的角度來看，在前面第一篇文章中，我們已經(jīng)提到過，一個database內(nèi)的這個映射關(guān)系是用一個dict來維護的。dict的key固定用一種數(shù)據(jù)結(jié)構(gòu)來表達就夠了，這就是動態(tài)字符串sds。而value則比較復(fù)雜，為了在同一個dict內(nèi)能夠存儲不同類型的value，這就需要一個通用的數(shù)據(jù)結(jié)構(gòu)，這個通用的數(shù)據(jù)結(jié)構(gòu)就是robj（全名是redisObject）。舉個例子：如果value是一個list，那么它的內(nèi)部存儲結(jié)構(gòu)是一個quicklist（quicklist的具體實現(xiàn)我們放在后面的文章討論）；如果value是一個string，那么它的內(nèi)部存儲結(jié)構(gòu)一般情況下是一個sds。當(dāng)然實際情況更復(fù)雜一點，比如一個string類型的value，如果它的值是一個數(shù)字，那么Redis內(nèi)部還會把它轉(zhuǎn)成long型來存儲，從而減小內(nèi)存使用。而一個robj既能表示一個sds，也能表示一個quicklist，甚至還能表示一個long型。
在server.h中我們找到跟robj定義相關(guān)的代碼，如下（注意，本系列文章中的代碼片段全部來源于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個字段：
這里特別需要仔細察看的是encoding字段。對于同一個type，還可能對應(yīng)不同的encoding，這說明同樣的一個數(shù)據(jù)類型，可能存在不同的內(nèi)部表示方式。而不同的內(nèi)部表示，在內(nèi)存占用和查找性能上會有所不同。
比如，當(dāng)type = OBJ_STRING的時候，表示這個robj存儲的是一個string，這時encoding可以是下面3種中的一種：
再舉一個例子：當(dāng)type = OBJ_HASH的時候，表示這個robj存儲的是一個hash，這時encoding可以是下面2種中的一種：
本文剩余主要部分將針對表示string的robj對象，圍繞它的3種不同的encoding來深入討論。前面代碼段中出現(xiàn)的所有10種encoding，在這里我們先簡單解釋一下，在這個系列后面的文章中，我們應(yīng)該還有機會碰到它們。
我們來總結(jié)一下robj的作用：
當(dāng)我們執(zhí)行Redis的set命令的時候，Redis首先將接收到的value值（string類型）表示成一個type = OBJ_STRING并且encoding = OBJ_ENCODING_RAW的robj對象，然后在存入內(nèi)部存儲之前先執(zhí)行一個編碼過程，試圖將它表示成另一種更節(jié)省內(nèi)存的encoding方式。這一過程的核心代碼，是object.c中的tryObjectEncoding函數(shù)。
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;
}
這段代碼執(zhí)行的操作比較復(fù)雜，我們有必要仔細看一下每一步的操作：
#define sdsEncodedObject(objptr) (objptr->encoding == OBJ_ENCODING_RAW || objptr->encoding == OBJ_ENCODING_EMBSTR)
其中調(diào)用的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重新分配內(nèi)存，將robj和sds放在一個連續(xù)的內(nèi)存塊中分配，這樣對于短字符串的存儲有利于減少內(nèi)存碎片。這個連續(xù)的內(nèi)存塊包含如下幾部分：
加起來一共不超過64字節(jié)（16+3+44+1），因此這樣的一個短字符串可以完全分配在一個64字節(jié)長度的內(nèi)存塊中。
當(dāng)我們需要獲取字符串的值，比如執(zhí)行g(shù)et命令的時候，我們需要執(zhí)行與前面講的編碼過程相反的操作——解碼。
這一解碼過程的核心代碼，是object.c中的getDecodedObject函數(shù)。
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");
}
}
這個過程比較簡單，需要我們注意的點有：
編碼為數(shù)字的字符串robj對象，將long重新轉(zhuǎn)為十進制字符串的形式，然后調(diào)用createStringObject轉(zhuǎn)為sds的表示。注意：這里由long轉(zhuǎn)成的sds字符串長度肯定不超過20，而根據(jù)createStringObject的實現(xiàn)，它們肯定會被編碼成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的關(guān)系；在本文介紹了robj的概念之后，我們重新總結(jié)一下sds與string的關(guān)系。
值得一提的是，append和setbit命令的實現(xiàn)中，都會最終調(diào)用到db.c中的dbUnshareStringValue函數(shù)，將string對象的內(nèi)部編碼轉(zhuǎn)成OBJ_ENCODING_RAW的（只有這種編碼的robj對象，其內(nèi)部的sds 才能在后面自由追加新的內(nèi)容），并解除可能存在的對象共享狀態(tài)。這里面調(diào)用了前面提到的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的引用計數(shù)加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--;
}
}
我們特別關(guān)注一下將引用計數(shù)減1的操作decrRefCount。如果只剩下最后一個引用了（refcount已經(jīng)是1了），那么在decrRefCount被調(diào)用后，整個robj將被釋放。
注意：Redis的del命令就依賴decrRefCount操作將value釋放掉。
經(jīng)過了本文的討論，我們很容易看出，robj所表示的就是Redis對外暴露的第一層面的數(shù)據(jù)結(jié)構(gòu)：string, list, hash, set, sorted set，而每一種數(shù)據(jù)結(jié)構(gòu)的底層實現(xiàn)所對應(yīng)的是哪個（或哪些）第二層面的數(shù)據(jù)結(jié)構(gòu)（dict, sds, ziplist, quicklist, skiplist, 等），則通過不同的encoding來區(qū)分?？梢哉f，robj是聯(lián)結(jié)兩個層面的數(shù)據(jù)結(jié)構(gòu)的橋梁。
本文詳細介紹了OBJ_STRING類型的字符串對象的底層實現(xiàn)，其編碼和解碼過程在Redis里非常重要，應(yīng)用廣泛，我們在后面的討論中可能還會遇到。現(xiàn)在有了robj的概念基礎(chǔ)，我們下一篇會討論ziplist，以及它與hash的關(guān)系。
后記(追加于2016-07-09): 本文在解析“將string編碼成long型”的代碼時提到的判斷21字節(jié)的問題，后來已經(jīng)提交給 @antirez并合并進了unstable分支，詳見 commit f648c5a。
