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