本文內(nèi)容思維導(dǎo)圖如下：

一、簡介和應(yīng)用

Redis是一個由ANSI C語言編寫，性能優(yōu)秀、支持網(wǎng)絡(luò)、可持久化的K-K內(nèi)存數(shù)據(jù)庫，并提供多種語言的API。它常用的類型主要是 String、List、Hash、Set、ZSet 這5種

Redis在互聯(lián)網(wǎng)公司一般有以下應(yīng)用:

•  String：緩存、限流、計數(shù)器、分布式鎖、分布式Session
•  Hash：存儲用戶信息、用戶主頁訪問量、組合查詢
•  List：微博關(guān)注人時間軸列表、簡單隊列
•  Set：贊、踩、標(biāo)簽、好友關(guān)系
•  Zset：排行榜

再比如電商在大促銷時，會用一些特殊的設(shè)計來保證系統(tǒng)穩(wěn)定，扣減庫存可以考慮如下設(shè)計：

上圖中，直接在Redis中扣減庫存，記錄日志后通過Worker同步到數(shù)據(jù)庫，在設(shè)計同步Worker時需要考慮并發(fā)處理和重復(fù)處理的問題。

通過上面的應(yīng)用場景可以看出Redis是非常高效和穩(wěn)定的，那Redis底層是如何實現(xiàn)的呢？

二、Redis的對象redisObject

當(dāng)我們執(zhí)行set hello world命令時，會有以下數(shù)據(jù)模型：

•  dictEntry：Redis給每個key-value鍵值對分配一個dictEntry，里面有著key和val的指針，next指向下一個dictEntry形成鏈表，這個指針可以將多個哈希值相同的鍵值對鏈接在一起，由此來解決哈希沖突問題(鏈地址法)。
•  sds：鍵key“hello”是以SDS（簡單動態(tài)字符串）存儲，后面詳細介紹。
•  redisObject：值val“world”存儲在redisObject中。實際上，redis常用5中類型都是以redisObject來存儲的；而redisObject中的type字段指明了Value對象的類型，ptr字段則指向?qū)ο笏诘牡刂贰?/li>

redisObject對象非常重要，Redis對象的類型、內(nèi)部編碼、內(nèi)存回收、共享對象等功能，都需要redisObject支持。這樣設(shè)計的好處是，可以針對不同的使用場景，對5中常用類型設(shè)置多種不同的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，從而優(yōu)化對象在不同場景下的使用效率。

無論是dictEntry對象，還是redisObject、SDS對象，都需要內(nèi)存分配器（如jemalloc）分配內(nèi)存進行存儲。jemalloc作為Redis的默認內(nèi)存分配器，在減小內(nèi)存碎片方面做的相對比較好。比如jemalloc在64位系統(tǒng)中，將內(nèi)存空間劃分為小、大、巨大三個范圍；每個范圍內(nèi)又劃分了許多小的內(nèi)存塊單位；當(dāng)Redis存儲數(shù)據(jù)時，會選擇大小最合適的內(nèi)存塊進行存儲。

前面說過，Redis每個對象由一個redisObject結(jié)構(gòu)表示，它的ptr指針指向底層實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，而數(shù)據(jù)結(jié)構(gòu)由encoding屬性決定。比如我們執(zhí)行以下命令得到存儲“hello”對應(yīng)的編碼：

redis所有的數(shù)據(jù)結(jié)構(gòu)類型如下（重要，后面會用）：

三、String

字符串對象的底層實現(xiàn)可以是int、raw、embstr（上面的表對應(yīng)有名稱介紹）。embstr編碼是通過調(diào)用一次內(nèi)存分配函數(shù)來分配一塊連續(xù)的空間，而raw需要調(diào)用兩次。

int編碼字符串對象和embstr編碼字符串對象在一定條件下會轉(zhuǎn)化為raw編碼字符串對象。embstr：<=39字節(jié)的字符串。int：8個字節(jié)的長整型。raw：大于39個字節(jié)的字符串。

簡單動態(tài)字符串（SDS），這種結(jié)構(gòu)更像C++的String或者Java的ArrayList<Character>，長度動態(tài)可變： 

struct sdshdr {  
 // buf 中已占用空間的長度  
 int len;  
 // buf 中剩余可用空間的長度  
 int free;  
 // 數(shù)據(jù)空間  
 char buf[]; // ’’空字符結(jié)尾  
}; 

•  get：sdsrange---O(n)
•  set：sdscpy—O(n)
•  create：sdsnew---O(1)
•  len：sdslen---O(1)

常數(shù)復(fù)雜度獲取字符串長度：因為SDS在len屬性中記錄了長度，所以獲取一個SDS長度時間復(fù)雜度僅為O(1)。

預(yù)空間分配：如果對一個SDS進行修改，分為一下兩種情況：

•  SDS長度（len的值）小于1MB，那么程序?qū)⒎峙浜蚻en屬性同樣大小的未使用空間，這時free和len屬性值相同。舉個例子，SDS的len將變成15字節(jié)，則程序也會分配15字節(jié)的未使用空間，SDS的buf數(shù)組的實際長度變成15+15+1=31字節(jié)（額外一個字節(jié)用戶保存空字符）。
•  SDS長度（len的值）大于等于1MB，程序會分配1MB的未使用空間。比如進行修改之后，SDS的len變成30MB，那么它的實際長度是30MB+1MB+1byte。

惰性釋放空間：當(dāng)執(zhí)行sdstrim（截取字符串）之后，SDS不會立馬釋放多出來的空間，如果下次再進行拼接字符串操作，且拼接的沒有剛才釋放的空間大，則那些未使用的空間就會排上用場。通過惰性釋放空間避免了特定情況下操作字符串的內(nèi)存重新分配操作。

杜絕緩沖區(qū)溢出：使用C字符串的操作時，如果字符串長度增加（如strcat操作）而忘記重新分配內(nèi)存，很容易造成緩沖區(qū)的溢出；而SDS由于記錄了長度，相應(yīng)的操作在可能造成緩沖區(qū)溢出時會自動重新分配內(nèi)存，杜絕了緩沖區(qū)溢出。

四、List

List對象的底層實現(xiàn)是quicklist（快速列表，是ziplist 壓縮列表 和linkedlist 雙端鏈表 的組合）。Redis中的列表支持兩端插入和彈出，并可以獲得指定位置（或范圍）的元素，可以充當(dāng)數(shù)組、隊列、棧等。 

typedef struct listNode {  
 // 前置節(jié)點  
 struct listNode *prev;  
 // 后置節(jié)點  
 struct listNode *next;  
 // 節(jié)點的值  
 void *value;  
 } listNode;  
 typedef struct list {  
 // 表頭節(jié)點  
 listNode *head;  
 // 表尾節(jié)點  
 listNode *tail;  
 // 節(jié)點值復(fù)制函數(shù)  
 void *(*dup)(void *ptr);  
 // 節(jié)點值釋放函數(shù)  
 void (*free)(void *ptr);  
 // 節(jié)點值對比函數(shù)  
 int (*match)(void *ptr, void *key);  
 // 鏈表所包含的節(jié)點數(shù)量  
 unsigned long len;  
 } list; 

•  rpush: listAddNodeHead ---O(1)
•  lpush: listAddNodeTail ---O(1)
•  push:listInsertNode ---O(1)
•  index : listIndex ---O(N)
•  pop:ListFirst/listLast ---O(1)
•  llen:listLength ---O(N)

4.1 linkedlist（雙端鏈表）

此結(jié)構(gòu)比較像Java的LinkedList，有興趣可以閱讀一下源碼。

從圖中可以看出Redis的linkedlist雙端鏈表有以下特性：節(jié)點帶有prev、next指針、head指針和tail指針，獲取前置節(jié)點、后置節(jié)點、表頭節(jié)點和表尾節(jié)點的復(fù)雜度都是O（1）。len屬性獲取節(jié)點數(shù)量也為O（1）。

與雙端鏈表相比，壓縮列表可以節(jié)省內(nèi)存空間，但是進行修改或增刪操作時，復(fù)雜度較高；因此當(dāng)節(jié)點數(shù)量較少時，可以使用壓縮列表；但是節(jié)點數(shù)量多時，還是使用雙端鏈表劃算。

4.2 ziplist（壓縮列表）

當(dāng)一個列表鍵只包含少量列表項，且是小整數(shù)值或長度比較短的字符串時，那么redis就使用ziplist（壓縮列表）來做列表鍵的底層實現(xiàn)。

ziplist是Redis為了節(jié)約內(nèi)存而開發(fā)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊(而不是像雙端鏈表一樣每個節(jié)點是指針)組成的順序型數(shù)據(jù)結(jié)構(gòu)；具體結(jié)構(gòu)相對比較復(fù)雜，有興趣讀者可以看 Redis 哈希結(jié)構(gòu)內(nèi)存模型剖析。在新版本中list鏈表使用 quicklist 代替了 ziplist和 linkedlist：

quickList 是 zipList 和 linkedList 的混合體。它將 linkedList 按段切分，每一段使用 zipList 來緊湊存儲，多個 zipList 之間使用雙向指針串接起來。因為鏈表的附加空間相對太高，prev 和 next 指針就要占去 16 個字節(jié) (64bit 系統(tǒng)的指針是 8 個字節(jié))，另外每個節(jié)點的內(nèi)存都是單獨分配，會加劇內(nèi)存的碎片化，影響內(nèi)存管理效率。

quicklist 默認的壓縮深度是 0，也就是不壓縮。為了支持快速的 push/pop 操作，quicklist 的首尾兩個 ziplist 不壓縮，此時深度就是 1。為了進一步節(jié)約空間，Redis 還會對 ziplist 進行壓縮存儲，使用 LZF 算法壓縮。

五、Hash

Hash對象的底層實現(xiàn)可以是ziplist（壓縮列表）或者hashtable（字典或者也叫哈希表）。

Hash對象只有同時滿足下面兩個條件時，才會使用ziplist（壓縮列表）：1.哈希中元素數(shù)量小于512個；2.哈希中所有鍵值對的鍵和值字符串長度都小于64字節(jié)。

hashtable哈希表可以實現(xiàn)O(1)復(fù)雜度的讀寫操作，因此效率很高。源碼如下： 

typedef struct dict {  
 // 類型特定函數(shù)  
 dictType *type;  
 // 私有數(shù)據(jù)  
 void *privdata;  
 // 哈希表  
 dictht ht[2];  
 // rehash 索引  
 // 當(dāng) rehash 不在進行時，值為 -1  
 int rehashidx; /* rehashing not in progress if rehashidx == -1 */  
 // 目前正在運行的安全迭代器的數(shù)量  
 int iterators; /* number of iterators currently running */  
 } dict;  
 typedef struct dictht {  
 // 哈希表數(shù)組  
 dictEntry **table;  
 // 哈希表大小  
 unsigned long size;  
 // 哈希表大小掩碼，用于計算索引值  
 // 總是等于 size - 1  
 unsigned long sizemask;  
 // 該哈希表已有節(jié)點的數(shù)量  
 unsigned long used;  
} dictht;  
typedef struct dictEntry {  
 void *key;  
 union {void *val;uint64_t u64;int64_t s64;} v;  
 // 指向下個哈希表節(jié)點，形成鏈表  
 struct dictEntry *next;  
 } dictEntry;  
 typedef struct dictType {  
 // 計算哈希值的函數(shù)  
 unsigned int (*hashFunction)(const void *key);  
 // 復(fù)制鍵的函數(shù)  
 void *(*keyDup)(void *privdata, const void *key);  
 // 復(fù)制值的函數(shù)  
 void *(*valDup)(void *privdata, const void *obj);  
 // 對比鍵的函數(shù)  
 int (*keyCompare)(void *privdata, const void *key1, const void *key2);  
 // 銷毀鍵的函數(shù)  
 void (*keyDestructor)(void *privdata, void *key);  
 // 銷毀值的函數(shù)  
 void (*valDestructor)(void *privdata, void *obj);  
} dictType; 

上面源碼可以簡化成如下結(jié)構(gòu)：

這個結(jié)構(gòu)類似于JDK7以前的HashMap<String,Object>，當(dāng)有兩個或以上的鍵被分配到哈希數(shù)組的同一個索引上時，會產(chǎn)生哈希沖突。Redis也使用鏈地址法來解決鍵沖突。即每個哈希表節(jié)點都有一個next指針，多個哈希表節(jié)點用next指針構(gòu)成一個單項鏈表，鏈地址法就是將相同hash值的對象組織成一個鏈表放在hash值對應(yīng)的槽位。

Redis中的字典使用hashtable作為底層實現(xiàn)的話，每個字典會帶有兩個哈希表，一個平時使用，另一個僅在rehash（重新散列）時使用。隨著對哈希表的操作，鍵會逐漸增多或減少。為了讓哈希表的負載因子維持在一個合理范圍內(nèi)，Redis會對哈希表的大小進行擴展或收縮（rehash），也就是將ht【0】里面所有的鍵值對分多次、漸進式的rehash到ht【1】里。

六、Set

Set集合對象的底層實現(xiàn)可以是intset（整數(shù)集合）或者hashtable（字典或者也叫哈希表）。

intset（整數(shù)集合）當(dāng)一個集合只含有整數(shù)，并且元素不多時會使用intset（整數(shù)集合）作為Set集合對象的底層實現(xiàn)。 

typedef struct intset {  
 // 編碼方式  
 uint32_t encoding;  
 // 集合包含的元素數(shù)量  
 uint32_t length;  
 // 保存元素的數(shù)組  
 int8_t contents[];  
} intset; 

•  sadd:intsetAdd---O(1)
•  smembers:intsetGetO(1)---O(N)
•  srem:intsetRemove---O(N)
•  slen:intsetlen ---O(1)

intset底層實現(xiàn)為有序，無重復(fù)數(shù)組保存集合元素。 intset這個結(jié)構(gòu)里的整數(shù)數(shù)組的類型可以是16位的，32位的，64位的。如果數(shù)組里所有的整數(shù)都是16位長度的，如果新加入一個32位的整數(shù)，那么整個16的數(shù)組將升級成一個32位的數(shù)組。升級可以提升intset的靈活性，又可以節(jié)約內(nèi)存，但不可逆。

7.ZSet

ZSet有序集合對象底層實現(xiàn)可以是ziplist（壓縮列表）或者skiplist（跳躍表）。

當(dāng)一個有序集合的元素數(shù)量比較多或者成員是比較長的字符串時，Redis就使用skiplist（跳躍表）作為ZSet對象的底層實現(xiàn)。 

typedef struct zskiplist {  
 // 表頭節(jié)點和表尾節(jié)點  
 struct zskiplistNode *header, *tail;  
 // 表中節(jié)點的數(shù)量  
 unsigned long length;  
 // 表中層數(shù)***的節(jié)點的層數(shù)  
 int level;  
 } zskiplist;  
typedef struct zskiplistNode {  
 // 成員對象  
 robj *obj;  
 // 分值  
 double score;  
 // 后退指針  
 struct zskiplistNode *backward;  
 // 層  
 struct zskiplistLevel {  
 // 前進指針  
 struct zskiplistNode *forward;  
 // 跨度---前進指針?biāo)赶蚬?jié)點與當(dāng)前節(jié)點的距離  
 unsigned int span;  
 } level[];  
} zskiplistNode; 

zadd---zslinsert---平均O(logN), 最壞O(N)

zrem---zsldelete---平均O(logN), 最壞O(N)

zrank--zslGetRank---平均O(logN), 最壞O(N)

skiplist的查找時間復(fù)雜度是LogN，可以和平衡二叉樹相當(dāng)，但實現(xiàn)起來又比它簡單。跳躍表(skiplist)是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在某個節(jié)點中維持多個指向其他節(jié)點的指針，從而達到快速訪問節(jié)點的目的。