數(shù)據(jù)分析！原來 Redis 可以這么快
大家好我是躍哥。我們平時(shí)學(xué)習(xí)數(shù)據(jù)存儲的時(shí)候，基本都會想到 Redis，因?yàn)樗芸?！那今天躍哥就和大家一起來從數(shù)據(jù)分析的角度探究下，為什么 Redis 能這么快。
1.簡介和應(yīng)用
Redis是一個(gè)由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：緩存、限流、計(jì)數(shù)器、分布式鎖、分布式Session
Hash：存儲用戶信息、用戶主頁訪問量、組合查詢
List：微博關(guān)注人時(shí)間軸列表、簡單隊(duì)列
Set：贊、踩、標(biāo)簽、好友關(guān)系
Zset：排行榜
再比如電商在大促銷時(shí)，會用一些特殊的設(shè)計(jì)來保證系統(tǒng)穩(wěn)定，扣減庫存可以考慮如下設(shè)計(jì)：? ? ? ??? ? ? ? ? ? ? ? ? ? ?
上圖中，直接在Redis中扣減庫存，記錄日志后通過Worker同步到數(shù)據(jù)庫，在設(shè)計(jì)同步Worker時(shí)需要考慮并發(fā)處理和重復(fù)處理的問題。
通過上面的應(yīng)用場景可以看出Redis是非常高效和穩(wěn)定的，那Redis底層是如何實(shí)現(xiàn)的呢？
2.Redis的對象redisObject
當(dāng)我們執(zhí)行set hello world命令時(shí)，會有以下數(shù)據(jù)模型：
? ? ? ? ? ? ? ? ? ? ? ? ??
dictEntry：Redis給每個(gè)key-value鍵值對分配一個(gè)dictEntry，里面有著key和val的指針，next指向下一個(gè)dictEntry形成鏈表，這個(gè)指針可以將多個(gè)哈希值相同的鍵值對鏈接在一起，由此來解決哈希沖突問題(鏈地址法)。
sds：鍵key“hello”是以SDS（簡單動態(tài)字符串）存儲，后面詳細(xì)介紹。
redisObject：值val“world”存儲在redisObject中。實(shí)際上，redis常用5中類型都是以redisObject來存儲的；而redisObject中的type字段指明了Value對象的類型，ptr字段則指向?qū)ο笏诘牡刂贰?/p>
redisObject對象非常重要，Redis對象的類型、內(nèi)部編碼、內(nèi)存回收、共享對象等功能，都需要redisObject支持。這樣設(shè)計(jì)的好處是，可以針對不同的使用場景，對5種常用類型設(shè)置多種不同的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，從而優(yōu)化對象在不同場景下的使用效率。
無論是dictEntry對象，還是redisObject、SDS對象，都需要內(nèi)存分配器（如jemalloc）分配內(nèi)存進(jìn)行存儲。jemalloc作為Redis的默認(rèn)內(nèi)存分配器，在減小內(nèi)存碎片方面做的相對比較好。比如jemalloc在64位系統(tǒng)中，將內(nèi)存空間劃分為小、大、巨大三個(gè)范圍；每個(gè)范圍內(nèi)又劃分了許多小的內(nèi)存塊單位；當(dāng)Redis存儲數(shù)據(jù)時(shí)，會選擇大小最合適的內(nèi)存塊進(jìn)行存儲。
前面說過，Redis每個(gè)對象由一個(gè)redisObject結(jié)構(gòu)表示，它的ptr指針指向底層實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，而數(shù)據(jù)結(jié)構(gòu)由encoding屬性決定。比如我們執(zhí)行以下命令得到存儲“hello”對應(yīng)的編碼：
redis所有的數(shù)據(jù)結(jié)構(gòu)類型如下（重要，后面會用到）：
3.String
字符串對象的底層實(shí)現(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個(gè)字節(jié)的長整型。raw：大于39個(gè)字節(jié)的字符串。
簡單動態(tài)字符串（SDS），這種結(jié)構(gòu)更像C++的String或者Java的ArrayList
struct sdshdr {
// buf 中已占用空間的長度
int len;
// buf 中剩余可用空間的長度
int free;
// 數(shù)據(jù)空間
char buf[]; // ’\0’空字符結(jié)尾
};get：sdsrange---O(n)
set：sdscpy—O(n)
create：sdsnew---O(1)
len：sdslen---O(1)
常數(shù)復(fù)雜度獲取字符串長度：因?yàn)镾DS在len屬性中記錄了長度，所以獲取一個(gè)SDS長度時(shí)間復(fù)雜度僅為O(1)。
預(yù)空間分配：如果對一個(gè)SDS進(jìn)行修改，分為一下兩種情況：
SDS長度（len的值）小于1MB，那么程序?qū)⒎峙浜蚻en屬性同樣大小的未使用空間，這時(shí)free和len屬性值相同。舉個(gè)例子，SDS的len將變成15字節(jié)，則程序也會分配15字節(jié)的未使用空間，SDS的buf數(shù)組的實(shí)際長度變成15+15+1=31字節(jié)（額外一個(gè)字節(jié)用戶保存空字符）。
SDS長度（len的值）大于等于1MB，程序會分配1MB的未使用空間。比如進(jìn)行修改之后，SDS的len變成30MB，那么它的實(shí)際長度是30MB+1MB+1byte。
惰性釋放空間：當(dāng)執(zhí)行sdstrim（截取字符串）之后，SDS不會立馬釋放多出來的空間，如果下次再進(jìn)行拼接字符串操作，且拼接的沒有剛才釋放的空間大，則那些未使用的空間就會排上用場。通過惰性釋放空間避免了特定情況下操作字符串的內(nèi)存重新分配操作。
杜絕緩沖區(qū)溢出：使用C字符串的操作時(shí)，如果字符串長度增加（如strcat操作）而忘記重新分配內(nèi)存，很容易造成緩沖區(qū)的溢出；而SDS由于記錄了長度，相應(yīng)的操作在可能造成緩沖區(qū)溢出時(shí)會自動重新分配內(nèi)存，杜絕了緩沖區(qū)溢出。
4.List
List對象的底層實(shí)現(xiàn)是quicklist（快速列表，是ziplist 壓縮列表 和linkedlist 雙端鏈表 的組合）。Redis中的列表支持兩端插入和彈出，并可以獲得指定位置（或范圍）的元素，可以充當(dāng)數(shù)組、隊(duì)列、棧等。
typedef struct listNode {
// 前置節(jié)點(diǎn)
struct listNode *prev;
// 后置節(jié)點(diǎn)
struct listNode *next;
// 節(jié)點(diǎn)的值
void *value;
} listNode;
typedef struct list {
// 表頭節(jié)點(diǎn)
listNode *head;
// 表尾節(jié)點(diǎn)
listNode *tail;
// 節(jié)點(diǎn)值復(fù)制函數(shù)
void *(*dup)(void *ptr);
// 節(jié)點(diǎn)值釋放函數(shù)
void (*free)(void *ptr);
// 節(jié)點(diǎn)值對比函數(shù)
int (*match)(void *ptr, void *key);
// 鏈表所包含的節(jié)點(diǎn)數(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é)點(diǎn)帶有prev、next指針、head指針和tail指針，獲取前置節(jié)點(diǎn)、后置節(jié)點(diǎn)、表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的復(fù)雜度都是O（1）。len屬性獲取節(jié)點(diǎn)數(shù)量也為O（1）。
與雙端鏈表相比，壓縮列表可以節(jié)省內(nèi)存空間，但是進(jìn)行修改或增刪操作時(shí)，復(fù)雜度較高；因此當(dāng)節(jié)點(diǎn)數(shù)量較少時(shí)，可以使用壓縮列表；但是節(jié)點(diǎn)數(shù)量多時(shí)，還是使用雙端鏈表劃算。
4.2? ziplist（壓縮列表）
當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng)，且是小整數(shù)值或長度比較短的字符串時(shí)，那么redis就使用ziplist（壓縮列表）來做列表鍵的底層實(shí)現(xiàn)。
? ? ? ? ? ? ?
ziplist是Redis為了節(jié)約內(nèi)存而開發(fā)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊(而不是像雙端鏈表一樣每個(gè)節(jié)點(diǎn)是指針)組成的順序型數(shù)據(jù)結(jié)構(gòu)；具體結(jié)構(gòu)相對比較復(fù)雜，有興趣讀者可以看 Redis 哈希結(jié)構(gòu)內(nèi)存模型剖析。在新版本中l(wèi)ist鏈表使用 quicklist 代替了 ziplist和 linkedlist：
quickList 是 zipList 和 linkedList 的混合體。它將 linkedList 按段切分，每一段使用 zipList 來緊湊存儲，多個(gè) zipList 之間使用雙向指針串接起來。因?yàn)殒湵淼母郊涌臻g相對太高，prev 和 next 指針就要占去 16 個(gè)字節(jié) (64bit 系統(tǒng)的指針是 8 個(gè)字節(jié))，另外每個(gè)節(jié)點(diǎn)的內(nèi)存都是單獨(dú)分配，會加劇內(nèi)存的碎片化，影響內(nèi)存管理效率。
quicklist 默認(rèn)的壓縮深度是 0，也就是不壓縮。為了支持快速的 push/pop 操作，quicklist 的首尾兩個(gè) ziplist 不壓縮，此時(shí)深度就是 1。為了進(jìn)一步節(jié)約空間，Redis 還會對 ziplist 進(jìn)行壓縮存儲，使用 LZF 算法壓縮。
5.Hash
Hash對象的底層實(shí)現(xiàn)可以是ziplist（壓縮列表）或者h(yuǎn)ashtable（字典或者也叫哈希表）。
Hash對象只有同時(shí)滿足下面兩個(gè)條件時(shí)，才會使用ziplist（壓縮列表）：1.哈希中元素?cái)?shù)量小于512個(gè)；2.哈希中所有鍵值對的鍵和值字符串長度都小于64字節(jié)。
hashtable哈希表可以實(shí)現(xiàn)O(1)復(fù)雜度的讀寫操作，因此效率很高。源碼如下：
typedef struct dict {
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 當(dāng) rehash 不在進(jìn)行時(shí)，值為 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在運(yùn)行的安全迭代器的數(shù)量
int iterators; /* number of iterators currently running */
} dict;
typedef struct dictht {
// 哈希表數(shù)組
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼，用于計(jì)算索引值
// 總是等于 size - 1
unsigned long sizemask;
// 該哈希表已有節(jié)點(diǎn)的數(shù)量
unsigned long used;
} dictht;
typedef struct dictEntry {
void *key;
union {void *val;uint64_t u64;int64_t s64;} v;
// 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表
struct dictEntry *next;
} dictEntry;
typedef struct dictType {
// 計(jì)算哈希值的函數(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)：? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
這個(gè)結(jié)構(gòu)類似于JDK7以前的HashMap
Redis中的字典使用hashtable作為底層實(shí)現(xiàn)的話，每個(gè)字典會帶有兩個(gè)哈希表，一個(gè)平時(shí)使用，另一個(gè)僅在rehash（重新散列）時(shí)使用。隨著對哈希表的操作，鍵會逐漸增多或減少。為了讓哈希表的負(fù)載因子維持在一個(gè)合理范圍內(nèi)，Redis會對哈希表的大小進(jìn)行擴(kuò)展或收縮（rehash），也就是將ht【0】里面所有的鍵值對分多次、漸進(jìn)式的rehash到ht【1】里。
6.Set
Set集合對象的底層實(shí)現(xiàn)可以是intset（整數(shù)集合）或者h(yuǎn)ashtable（字典或者也叫哈希表）。
intset（整數(shù)集合）當(dāng)一個(gè)集合只含有整數(shù)，并且元素不多時(shí)會使用intset（整數(shù)集合）作為Set集合對象的底層實(shí)現(xiàn)。
typedef struct intset {
// 編碼方式
uint32_t encoding;
// 集合包含的元素?cái)?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底層實(shí)現(xiàn)為有序，無重復(fù)數(shù)組保存集合元素。intset這個(gè)結(jié)構(gòu)里的整數(shù)數(shù)組的類型可以是16位的，32位的，64位的。如果數(shù)組里所有的整數(shù)都是16位長度的，如果新加入一個(gè)32位的整數(shù)，那么整個(gè)16的數(shù)組將升級成一個(gè)32位的數(shù)組。升級可以提升intset的靈活性，又可以節(jié)約內(nèi)存，但不可逆。
7.ZSet
ZSet有序集合對象底層實(shí)現(xiàn)可以是ziplist（壓縮列表）或者skiplist（跳躍表）。
當(dāng)一個(gè)有序集合的元素?cái)?shù)量比較多或者成員是比較長的字符串時(shí)，Redis就使用skiplist（跳躍表）作為ZSet對象的底層實(shí)現(xiàn)。
typedef struct zskiplist {
// 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
struct zskiplistNode *header, *tail;
// 表中節(jié)點(diǎn)的數(shù)量
unsigned long length;
// 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
int level;
} zskiplist;
typedef struct zskiplistNode {
// 成員對象
robj *obj;
// 分值
double score;
// 后退指針
struct zskiplistNode *backward;
// 層
struct zskiplistLevel {
// 前進(jìn)指針
struct zskiplistNode *forward;
// 跨度---前進(jìn)指針?biāo)赶蚬?jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的距離
unsigned int span;
} level[];
} zskiplistNode;zadd---zslinsert---平均O(logN), 最壞O(N)
zrem---zsldelete---平均O(logN), 最壞O(N)
zrank--zslGetRank---平均O(logN), 最壞O(N)
? ??
skiplist的查找時(shí)間復(fù)雜度是LogN，可以和平衡二叉樹相當(dāng)，但實(shí)現(xiàn)起來又比它簡單。跳躍表(skiplist)是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在某個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問節(jié)點(diǎn)的目的。
0、重磅！兩萬字長文總結(jié)，梳理 Java 入門進(jìn)階哪些事（推薦收藏）
