溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文轉自互聯網
本系列文章將整理到我在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型。
在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個字段：
這里特別需要仔細察看的是encoding字段。對于同一個type，還可能對應不同的encoding，這說明同樣的一個數據類型，可能存在不同的內部表示方式。而不同的內部表示，在內存占用和查找性能上會有所不同。
比如，當type = OBJ_STRING的時候，表示這個robj存儲的是一個string，這時encoding可以是下面3種中的一種：
再舉一個例子：當type = OBJ_HASH的時候，表示這個robj存儲的是一個hash，這時encoding可以是下面2種中的一種：
本文剩余主要部分將針對表示string的robj對象，圍繞它的3種不同的encoding來深入討論。前面代碼段中出現的所有10種encoding，在這里我們先簡單解釋一下，在這個系列后面的文章中，我們應該還有機會碰到它們。
我們來總結一下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;
}
這段代碼執行的操作比較復雜，我們有必要仔細看一下每一步的操作：
#define sdsEncodedObject(objptr) (objptr->encoding == OBJ_ENCODING_RAW || objptr->encoding == OBJ_ENCODING_EMBSTR)
其中調用的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放在一個連續的內存塊中分配，這樣對于短字符串的存儲有利于減少內存碎片。這個連續的內存塊包含如下幾部分：
加起來一共不超過64字節（16+3+44+1），因此這樣的一個短字符串可以完全分配在一個64字節長度的內存塊中。
當我們需要獲取字符串的值，比如執行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");
}
}
這個過程比較簡單，需要我們注意的點有：
編碼為數字的字符串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的關系；在本文介紹了robj的概念之后，我們重新總結一下sds與string的關系。
值得一提的是，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的引用計數加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。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
