Redis 簡介

REmote DIctionary Server(Redis) 是一個(gè)由SalvatoreSanfilippo寫的key-value存儲(chǔ)系統(tǒng)。

Redis是一個(gè)開源的使用ANSI C語言編寫、遵守BSD協(xié)議、支持網(wǎng)絡(luò)、可基于內(nèi)存亦可持久化的日志型、Key-Value數(shù)據(jù)庫，并提供多種語言的API。

它通常被稱為數(shù)據(jù)結(jié)構(gòu)服務(wù)器，因?yàn)橹?value)可以是字符串(String), 哈希(Map), 列表(list), 集合(sets) 和有序集合(sorted sets)等類型。

Redis特點(diǎn)

Redis 是完全開源免費(fèi)的，遵守BSD協(xié)議，是一個(gè)高性能的key-value數(shù)據(jù)庫。

Redis 與其他 key - value 緩存產(chǎn)品有以下三個(gè)特點(diǎn)：

• Redis支持?jǐn)?shù)據(jù)的持久化，可以將內(nèi)存中的數(shù)據(jù)保持在磁盤中，重啟的時(shí)候可以再次加載進(jìn)行使用。
• Redis不僅僅支持簡單的key-value類型的數(shù)據(jù)，同時(shí)還提供list，set，zset，hash等數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)。
• Redis支持?jǐn)?shù)據(jù)的備份，即master-slave模式的數(shù)據(jù)備份。

Redis 優(yōu)勢(shì)

性能極高 – Redis能讀的速度是110000次/s,寫的速度是81000次/s 。

豐富的數(shù)據(jù)類型 – Redis支持 Strings, Lists, Hashes, Sets 及 Ordered Sets 數(shù)據(jù)類型操作。

原子 – Redis的所有操作都是原子性的，同時(shí)Redis還支持對(duì)幾個(gè)操作全并后的原子性執(zhí)行。

豐富的特性 – Redis 還支持 publish/subscribe, 隊(duì)列，key 過期等等特性。

Redis對(duì)象類型簡介

Redis是一種key/value型數(shù)據(jù)庫，其中，每個(gè)key和value都是使用對(duì)象表示的。

比如，我們執(zhí)行以下代碼： 

redis> SET message "hello redis" 

其中的key是message，是一個(gè)包含了字符串"message"的對(duì)象。而value是一個(gè)包含了"hello redis"的對(duì)象。

Redis共有五種對(duì)象的類型，分別是：

Redis中的一個(gè)對(duì)象的結(jié)構(gòu)體表示如下： 

typedef struct redisObject {  
// 類型  
unsigned type:4;  
// 編碼方式  
unsigned encoding: 4;  
// 引用計(jì)數(shù)  
int refcount;  
// 指向?qū)ο蟮闹?nbsp; 
void *ptr;  
} robj;  

type表示了該對(duì)象的對(duì)象類型，即上面五個(gè)中的一個(gè)。但為了提高存儲(chǔ)效率與程序執(zhí)行效率，每種對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)都可能不止一種。encoding就表示了對(duì)象底層所使用的編碼。

• Redis對(duì)象底層數(shù)據(jù)結(jié)構(gòu)

• 字符串對(duì)象

字符串對(duì)象的編碼可以是int、raw或者embstr

如果一個(gè)字符串的內(nèi)容可以轉(zhuǎn)換為long，那么該字符串就會(huì)被轉(zhuǎn)換成為long類型，對(duì)象的ptr就會(huì)指向該long，并且對(duì)象類型也用int類型表示。

普通的字符串有兩種，embstr和raw。embstr應(yīng)該是Redis 3.0新增的數(shù)據(jù)結(jié)構(gòu),在2.8中是沒有的。如果字符串對(duì)象的長度小于39字節(jié)，就用embstr對(duì)象。否則用傳統(tǒng)的raw對(duì)象。 

#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 44  
robj *createStringObject(char *ptr, size_t len) {  
if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)  
return createEmbeddedStringObject(ptr,len);  
else  
return createRawStringObject(ptr,len);  
}  

embstr的好處有如下幾點(diǎn)：

1. embstr的創(chuàng)建只需分配一次內(nèi)存，而raw為兩次(一次為sds分配對(duì)象，另一次為objet分配對(duì)象，embstr省去了***次)。
2. 相對(duì)地，釋放內(nèi)存的次數(shù)也由兩次變?yōu)橐淮巍?/li>
3. embstr的objet和sds放在一起，更好地利用緩存帶來的優(yōu)勢(shì)。

raw和embstr的區(qū)別可以用下面兩幅圖所示：

• 列表對(duì)象

列表對(duì)象的編碼可以是ziplist或者linkedlist

1. ziplist是一種壓縮鏈表，它的好處是更能節(jié)省內(nèi)存空間，因?yàn)樗鎯?chǔ)的內(nèi)容都是在連續(xù)的內(nèi)存區(qū)域當(dāng)中的。當(dāng)列表對(duì)象元素不大，每個(gè)元素也不大的時(shí)候，就采用ziplist存儲(chǔ)但當(dāng)數(shù)據(jù)量過大時(shí)就ziplist就不是那么好用了。因?yàn)闉榱吮ＷC他存儲(chǔ)內(nèi)容在內(nèi)存中的連續(xù)性，插入的復(fù)雜度是O(N)，即每次插入都會(huì)重新進(jìn)行realloc。如下圖所示，對(duì)象結(jié)構(gòu)中ptr所指向的就是一個(gè)ziplist整個(gè)ziplist只需要malloc一次，它們?cè)趦?nèi)存中是一塊連續(xù)的區(qū)域。

linkedlist是一種雙向鏈表。它的結(jié)構(gòu)比較簡單，節(jié)點(diǎn)中存放pre和next兩個(gè)指針，還有節(jié)點(diǎn)相關(guān)的信息。當(dāng)每增加一個(gè)node的時(shí)候，就需要重新malloc一塊內(nèi)存。

• 哈希對(duì)象

哈希對(duì)象的底層實(shí)現(xiàn)可以是ziplist或者h(yuǎn)ashtable。

ziplist中的哈希對(duì)象是按照key1,value1,key2,value2這樣的順序存放來存儲(chǔ)的。當(dāng)對(duì)象數(shù)目不多且內(nèi)容不大時(shí)，這種方式效率是很高的。

hashtable的是由dict這個(gè)結(jié)構(gòu)來實(shí)現(xiàn)的, dict是一個(gè)字典，其中的指針dicht ht[2] 指向了兩個(gè)哈希表 

typedef struct dict {  
dictType *type;  
void *privdata;  
dictht ht[2];  
long rehashidx; /* rehashing not in progress if rehashidx == -1 */  
int iterators; /* number of iterators currently running */  
} dict;  
typedef struct dictht {  
dictEntry **table;  
unsigned long size;  
unsigned long sizemask;  
unsigned long used;  
} dictht;  

dicht[0] 是用于真正存放數(shù)據(jù)，dicht[1]一般在哈希表元素過多進(jìn)行rehash的時(shí)候用于中轉(zhuǎn)數(shù)據(jù)。

dictht中的table用語真正存放元素了，每個(gè)key/value對(duì)用一個(gè)dictEntry表示，放在dictEntry數(shù)組中。

• 集合對(duì)象

集合對(duì)象的編碼可以是intset或者h(yuǎn)ashtable

intset是一個(gè)整數(shù)集合，里面存的為某種同一類型的整數(shù)，支持如下三種長度的整數(shù)： 

#define INTSET_ENC_INT16 (sizeof(int16_t))  
#define INTSET_ENC_INT32 (sizeof(int32_t))  
#define INTSET_ENC_INT64 (sizeof(int64_t))  

intset是一個(gè)有序集合，查找元素的復(fù)雜度為O(logN)，但插入時(shí)不一定為O(logN)，因?yàn)橛锌赡苌婕暗缴?jí)操作。比如當(dāng)集合里全是int16_t型的整數(shù)，這時(shí)要插入一個(gè)int32_t，那么為了維持集合中數(shù)據(jù)類型的一致，那么所有的數(shù)據(jù)都會(huì)被轉(zhuǎn)換成int32_t類型，涉及到內(nèi)存的重新分配，這時(shí)插入的復(fù)雜度就為O(N)了。

intset不支持降級(jí)操作。

• 有序集合對(duì)象

有序集合的編碼可能兩種，一種是ziplist，另一種是skiplist與dict的結(jié)合。

ziplist作為集合和作為哈希對(duì)象是一樣的，member和score順序存放。按照score從小到大順序排列

skiplist是一種跳躍表，它實(shí)現(xiàn)了有序集合中的快速查找，在大多數(shù)情況下它的速度都可以和平衡樹差不多。但它的實(shí)現(xiàn)比較簡單，可以作為平衡樹的替代品。它的結(jié)構(gòu)比較特殊。下面分別是跳躍表skiplist和它內(nèi)部的節(jié)點(diǎn)skiplistNode的結(jié)構(gòu)體： 

/*  
* 跳躍表  
*/  
typedef struct zskiplist {  
// 頭節(jié)點(diǎn)，尾節(jié)點(diǎn)  
struct zskiplistNode *header, *tail;  
// 節(jié)點(diǎn)數(shù)量  
unsigned long length;  
// 目前表內(nèi)節(jié)點(diǎn)的***層數(shù)  
int level;  
} zskiplist;  
/* ZSETs use a specialized version of Skiplists */  
/*  
* 跳躍表節(jié)點(diǎn)  
*/  
typedef struct zskiplistNode {  
// member 對(duì)象  
robj *obj;  
// 分值  
double score;  
// 后退指針  
struct zskiplistNode *backward;  
// 層  
struct zskiplistLevel {  
// 前進(jìn)指針  
struct zskiplistNode *forward;  
// 這個(gè)層跨越的節(jié)點(diǎn)數(shù)量  
unsigned int span;  
} level[];  
} zskiplistNode;  

head和tail分別指向頭節(jié)點(diǎn)和尾節(jié)點(diǎn)，然后每個(gè)skiplistNode里面的結(jié)構(gòu)又是分層的(即level數(shù)組)

用圖表示，大概是下面這個(gè)樣子：

總結(jié)

以上簡單介紹了Redis的簡介，特性以及五種對(duì)象類型和五種對(duì)象類型的底層實(shí)現(xiàn)。事實(shí)上，Redis的高效性和靈活性正是得益于同一個(gè)對(duì)象類型采用不同的底層結(jié)構(gòu)，并且在必要的時(shí)候?qū)Χ哌M(jìn)行轉(zhuǎn)換，還有就是各種底層結(jié)構(gòu)對(duì)內(nèi)存的合理利用。