字符串對(duì)象

字符串?dāng)?shù)據(jù)類型是Redis里最常用的類型了，它的鍵和值都是字符串，使用起來(lái)非常的方便。雖然字符串?dāng)?shù)據(jù)類型的值都統(tǒng)稱為字符串了，但是在實(shí)際存儲(chǔ)時(shí)會(huì)根據(jù)值的不同自動(dòng)選擇合適的編碼。字符串對(duì)象的編碼一共有三種：int、raw、embstr。

Redis對(duì)象

Redis用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)來(lái)表示一個(gè)對(duì)象，具體定義如下：

typedef struct redisObject {
 unsigned type:4;
 unsigned encoding:4;
 // 當(dāng)內(nèi)存超限時(shí)采用LRU算法清除內(nèi)存中的對(duì)象
 unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
       * LFU data (least significant 8 bits frequency
       * and most significant 16 bits access time). */
 // 該對(duì)象被引用數(shù)
 int refcount;
 // 對(duì)象的值指針
 void *ptr;
} robj;

其中type字段代表對(duì)象的類型，取值一共有7種：

/* A redis object, that is a type able to hold a string / list / set */

/* The actual Redis Object */
#define OBJ_STRING 0 /* 字符串對(duì)象. */
#define OBJ_LIST 1  /* 列表對(duì)象. */
#define OBJ_SET 2  /* 集合對(duì)象. */
#define OBJ_ZSET 3  /* 有序集合對(duì)象. */
#define OBJ_HASH 4  /* 哈希對(duì)象. */

/* The "module" object type is a special one that signals that the object
 * is one directly managed by a Redis module. In this case the value points
 * to a moduleValue struct, which contains the object value (which is only
 * handled by the module itself) and the RedisModuleType struct which lists
 * function pointers in order to serialize, deserialize, AOF-rewrite and
 * free the object.
 *
 * Inside the RDB file, module types are encoded as OBJ_MODULE followed
 * by a 64 bit module type ID, which has a 54 bits module-specific signature
 * in order to dispatch the loading to the right module, plus a 10 bits
 * encoding version. */
#define OBJ_MODULE 5 /* 模塊對(duì)象. */
#define OBJ_STREAM 6 /* 流對(duì)象. */

然后是encoding字段，代表著對(duì)象值的實(shí)際編碼類型，取值一共有11種：

/* 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  /* 簡(jiǎn)單動(dòng)態(tài)字符串 */
#define OBJ_ENCODING_INT 1  /* long類型的整數(shù) */
#define OBJ_ENCODING_HT 2  /* 字典 */
#define OBJ_ENCODING_ZIPMAP 3 /* 壓縮字典 */
#define OBJ_ENCODING_LINKEDLIST 4 /* 不再使用的舊列表，使用雙端鏈表. */
#define OBJ_ENCODING_ZIPLIST 5 /* 壓縮列表 */
#define OBJ_ENCODING_INTSET 6 /* 整數(shù)集合 */
#define OBJ_ENCODING_SKIPLIST 7 /* 跳躍表和字典 */
#define OBJ_ENCODING_EMBSTR 8 /* embstr編碼的簡(jiǎn)單動(dòng)態(tài)字符串 */
#define OBJ_ENCODING_QUICKLIST 9 /* 編碼為ziplist的列表 */
#define OBJ_ENCODING_STREAM 10 /* 編碼為listpacks的基數(shù)樹 */

前面已經(jīng)提到字符串對(duì)象只用到了long類型的整數(shù)、簡(jiǎn)單動(dòng)態(tài)字符串、embstr編碼的簡(jiǎn)單動(dòng)態(tài)字符串這三種編碼。

OBJ_ENCODING_INT

當(dāng)字符串對(duì)象的值是一個(gè)整數(shù)且可以用long來(lái)表示時(shí)，字符串對(duì)象的編碼就會(huì)是OBJ_ENCODING_INT編碼。

可以看到，當(dāng)值非常大的時(shí)候還是用OBJ_ENCODING_RAW來(lái)存儲(chǔ)的。

OBJ_ENCODING_RAW

當(dāng)字符串對(duì)象的值是一個(gè)字符串且長(zhǎng)度大于44字節(jié)時(shí)，字符串對(duì)象的編碼就會(huì)是OBJ_ENCODING_RAW編碼。具體結(jié)構(gòu)在下文。

OBJ_ENCODING_EMBSTR

當(dāng)字符串對(duì)象的值是一個(gè)字符串且長(zhǎng)度小于等于44字節(jié)時(shí)，字符串對(duì)象的編碼就會(huì)是OBJ_ENCODING_EMBSTR編碼。OBJ_ENCODING_EMBSTR編碼和OBJ_ENCODING_RAW編碼的區(qū)別主要有以下幾點(diǎn)：

• OBJ_ENCODING_RAW編碼的對(duì)象在分配內(nèi)存時(shí)會(huì)分配兩次，分別創(chuàng)建redisObject對(duì)象和SDS對(duì)象。而OBJ_ENCODING_EMBSTR編碼則是一次就分配好。
• 同樣的，OBJ_ENCODING_RAW編碼的對(duì)象釋放內(nèi)存也需要兩次，OBJ_ENCODING_EMBSTR編碼則是一次。
• OBJ_ENCODING_EMBSTR編碼的數(shù)據(jù)都存儲(chǔ)在連續(xù)的內(nèi)存上，OBJ_ENCODING_RAW編碼則不是。

/* Create a string object with EMBSTR encoding if it is smaller than
 * OBJ_ENCODING_EMBSTR_SIZE_LIMIT, otherwise the RAW encoding is
 * used.
 *
 * The current limit of 44 is chosen so that the biggest string object
 * we allocate as EMBSTR will still fit into the 64 byte arena of jemalloc. */
#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
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

字符串是Redis里非常常見的類型，而用C實(shí)現(xiàn)的Redis和Java不一樣。在C里字符串是用長(zhǎng)度為N+1的字符數(shù)組實(shí)現(xiàn)的，且使用空字符串'\0'作為結(jié)束符號(hào)。獲取字符串的長(zhǎng)度需要遍歷一遍，找到空字符串'\0'才知道字符串的長(zhǎng)度，復(fù)雜度是O(N)。

如果有一個(gè)長(zhǎng)度非常大的字符串，單線程的Redis獲取它的長(zhǎng)度就可能會(huì)阻塞很久，這是不能接受的，所以Redis需要一種更高效的字符串類型。

Redis實(shí)現(xiàn)了一個(gè)叫SDS（simple dynamic string）的字符串類型，其中有兩個(gè)變量來(lái)分別代表字符串的長(zhǎng)度和字符數(shù)組未使用的字符數(shù)量，這樣就可以用O(1)的復(fù)雜度來(lái)獲取字符串的長(zhǎng)度了，而且同樣也是使用空字符串'\0'作為結(jié)束符號(hào)。

struct sdshdr {
 // 字符串長(zhǎng)度
 int len;
 // 字符數(shù)組未使用的字符數(shù)量
 int free;
 // 保存字符串的字符數(shù)組
 char buf[];
}

擴(kuò)容機(jī)制

SDS在字符數(shù)組空間不足于容納新字符串的時(shí)候會(huì)自動(dòng)擴(kuò)容。

如果把一個(gè)C字符串拼接到一個(gè)SDS后面，當(dāng)字符數(shù)組空間不足時(shí)，SDS會(huì)先擴(kuò)容到剛好可以容納新字符串的長(zhǎng)度，然后再擴(kuò)充新字符串的空字符長(zhǎng)度，最終SDS的字符數(shù)組長(zhǎng)度等于 2 * 新字符串 + 1（結(jié)束符號(hào)'\0'）。不過(guò)當(dāng)新字符串的大小超過(guò)1MB后，擴(kuò)充的空字符長(zhǎng)度大小會(huì)固定為1MB。

之所以會(huì)有這個(gè)機(jī)制，是因?yàn)镽edis作為一個(gè)NoSQL數(shù)據(jù)庫(kù)，會(huì)頻繁的修改字符串，擴(kuò)容機(jī)制相當(dāng)于給SDS做了一個(gè)緩沖池。把SDS連續(xù)增長(zhǎng)N次字符串需要內(nèi)存重分配N次優(yōu)化成了SDS連續(xù)增長(zhǎng)N次字符串最多需要內(nèi)存重分配N次，這其實(shí)和Java里的StringBuilder實(shí)現(xiàn)思想是一樣的。

后記

我看過(guò)兩本關(guān)于Redis的書，里面都是講Redis如何實(shí)戰(zhàn)的，并沒有講Redis的設(shè)計(jì)和實(shí)現(xiàn)。這也就導(dǎo)致了面試很尷尬，因?yàn)槊嬖嚬僮钕矚g問(wèn)原理相關(guān)的東西了，所以以后學(xué)習(xí)技術(shù)的時(shí)候不要從實(shí)戰(zhàn)類的書籍開始了，還是先看懂原理比較好。

參考資料

這是《Redis設(shè)計(jì)與實(shí)現(xiàn)》里字符串一節(jié)的總結(jié)。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。