共計(jì) 6451 個(gè)字符，預(yù)計(jì)需要花費(fèi) 17 分鐘才能閱讀完成。
如何從數(shù)據(jù)存儲(chǔ)角度分析 Redis 為何這么快，很多新手對此不是很清楚，為了幫助大家解決這個(gè)難題，下面丸趣 TV 小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。
一、簡介和應(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：存儲(chǔ)用戶信息、用戶主頁訪問量、組合查詢
List：微博關(guān)注人時(shí)間軸列表、簡單隊(duì)列
Set：贊、踩、標(biāo)簽、好友關(guān)系
Zset：排行榜
再比如電商在大促銷時(shí)，會(huì)用一些特殊的設(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)的呢？
二、Redis 的對象 redisObject
當(dāng)我們執(zhí)行 set hello world 命令時(shí)，會(huì)有以下數(shù)據(jù)模型：
dictEntry：Redis 給每個(gè) key-value 鍵值對分配一個(gè) dictEntry，里面有著 key 和 val 的指針，next 指向下一個(gè) dictEntry 形成鏈表，這個(gè)指針可以將多個(gè)哈希值相同的鍵值對鏈接在一起，由此來解決哈希沖突問題(鏈地址法)。
sds：鍵 key“hello”是以 SDS（簡單動(dòng)態(tài)字符串）存儲(chǔ)，后面詳細(xì)介紹。
redisObject：值 val“world”存儲(chǔ)在 redisObject 中。實(shí)際上，redis 常用 5 中類型都是以 redisObject 來存儲(chǔ)的；而 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)行存儲(chǔ)。jemalloc 作為 Redis 的默認(rèn)內(nèi)存分配器，在減小內(nèi)存碎片方面做的相對比較好。比如 jemalloc 在 64 位系統(tǒng)中，將內(nèi)存空間劃分為小、大、巨大三個(gè)范圍；每個(gè)范圍內(nèi)又劃分了許多小的內(nèi)存塊單位；當(dāng) Redis 存儲(chǔ)數(shù)據(jù)時(shí)，會(huì)選擇大小最合適的內(nèi)存塊進(jìn)行存儲(chǔ)。
前面說過，Redis 每個(gè)對象由一個(gè) redisObject 結(jié)構(gòu)表示，它的 ptr 指針指向底層實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，而數(shù)據(jù)結(jié)構(gòu)由 encoding 屬性決定。比如我們執(zhí)行以下命令得到存儲(chǔ)“hello”對應(yīng)的編碼：
redis 所有的數(shù)據(jù)結(jié)構(gòu)類型如下（重要，后面會(huì)用）：
三、String
字符串對象的底層實(shí)現(xiàn)可以是 int、raw、embstr（上面的表對應(yīng)有名稱介紹）。embstr 編碼是通過調(diào)用一次內(nèi)存分配函數(shù)來分配一塊連續(xù)的空間，而 raw 需要調(diào)用兩次。
int 編碼字符串對象和 embstr 編碼字符串對象在一定條件下會(huì)轉(zhuǎn)化為 raw 編碼字符串對象。embstr：=39 字節(jié)的字符串。int：8 個(gè)字節(jié)的長整型。raw：大于 39 個(gè)字節(jié)的字符串。
簡單動(dòng)態(tài)字符串（SDS），這種結(jié)構(gòu)更像 C ++ 的 String 或者 Java 的 ArrayList Character，長度動(dòng)態(tài)可變：
struct sdshdr { // buf 中已占用空間的長度 int len; // buf 中剩余可用空間的長度 int free; // 數(shù)據(jù)空間 char buf[]; // rsquo; rsquo; 空字符結(jié)尾 };get：sdsrange—O(n)
set：sdscpy mdash;O(n)
create：sdsnew—O(1)
len：sdslen—O(1)
常數(shù)復(fù)雜度獲取字符串長度：因?yàn)?SDS 在 len 屬性中記錄了長度，所以獲取一個(gè) SDS 長度時(shí)間復(fù)雜度僅為 O(1)。
預(yù)空間分配：如果對一個(gè) SDS 進(jìn)行修改，分為一下兩種情況：
SDS 長度（len 的值）小于 1MB，那么程序?qū)⒎峙浜?len 屬性同樣大小的未使用空間，這時(shí) free 和 len 屬性值相同。舉個(gè)例子，SDS 的 len 將變成 15 字節(jié)，則程序也會(huì)分配 15 字節(jié)的未使用空間，SDS 的 buf 數(shù)組的實(shí)際長度變成 15+15+1=31 字節(jié)（額外一個(gè)字節(jié)用戶保存空字符）。
SDS 長度（len 的值）大于等于 1MB，程序會(huì)分配 1MB 的未使用空間。比如進(jìn)行修改之后，SDS 的 len 變成 30MB，那么它的實(shí)際長度是 30MB+1MB+1byte。
惰性釋放空間：當(dāng)執(zhí)行 sdstrim（截取字符串）之后，SDS 不會(huì)立馬釋放多出來的空間，如果下次再進(jìn)行拼接字符串操作，且拼接的沒有剛才釋放的空間大，則那些未使用的空間就會(huì)排上用場。通過惰性釋放空間避免了特定情況下操作字符串的內(nèi)存重新分配操作。
杜絕緩沖區(qū)溢出：使用 C 字符串的操作時(shí)，如果字符串長度增加（如 strcat 操作）而忘記重新分配內(nèi)存，很容易造成緩沖區(qū)的溢出；而 SDS 由于記錄了長度，相應(yīng)的操作在可能造成緩沖區(qū)溢出時(shí)會(huì)自動(dòng)重新分配內(nèi)存，杜絕了緩沖區(qū)溢出。
四、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)存模型剖析。在新版本中 list 鏈表使用 quicklist 代替了 ziplist 和 linkedlist：
quickList 是 zipList 和 linkedList 的混合體。它將 linkedList 按段切分，每一段使用 zipList 來緊湊存儲(chǔ)，多個(gè) zipList 之間使用雙向指針串接起來。因?yàn)殒湵淼母郊涌臻g相對太高，prev 和 next 指針就要占去 16 個(gè)字節(jié) (64bit 系統(tǒng)的指針是 8 個(gè)字節(jié))，另外每個(gè)節(jié)點(diǎn)的內(nèi)存都是單獨(dú)分配，會(huì)加劇內(nèi)存的碎片化，影響內(nèi)存管理效率。
quicklist 默認(rèn)的壓縮深度是 0，也就是不壓縮。為了支持快速的 push/pop 操作，quicklist 的首尾兩個(gè) ziplist 不壓縮，此時(shí)深度就是 1。為了進(jìn)一步節(jié)約空間，Redis 還會(huì)對 ziplist 進(jìn)行壓縮存儲(chǔ)，使用 LZF 算法壓縮。
五、Hash
Hash 對象的底層實(shí)現(xiàn)可以是 ziplist（壓縮列表）或者 hashtable（字典或者也叫哈希表）。
Hash 對象只有同時(shí)滿足下面兩個(gè)條件時(shí)，才會(huì)使用 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 String,Object，當(dāng)有兩個(gè)或以上的鍵被分配到哈希數(shù)組的同一個(gè)索引上時(shí)，會(huì)產(chǎn)生哈希沖突。Redis 也使用鏈地址法來解決鍵沖突。即每個(gè)哈希表節(jié)點(diǎn)都有一個(gè) next 指針，多個(gè)哈希表節(jié)點(diǎn)用 next 指針構(gòu)成一個(gè)單項(xiàng)鏈表，鏈地址法就是將相同 hash 值的對象組織成一個(gè)鏈表放在 hash 值對應(yīng)的槽位。
Redis 中的字典使用 hashtable 作為底層實(shí)現(xiàn)的話，每個(gè)字典會(huì)帶有兩個(gè)哈希表，一個(gè)平時(shí)使用，另一個(gè)僅在 rehash（重新散列）時(shí)使用。隨著對哈希表的操作，鍵會(huì)逐漸增多或減少。為了讓哈希表的負(fù)載因子維持在一個(gè)合理范圍內(nèi)，Redis 會(huì)對哈希表的大小進(jìn)行擴(kuò)展或收縮（rehash），也就是將 ht【0】里面所有的鍵值對分多次、漸進(jìn)式的 rehash 到 ht【1】里。
六、Set
Set 集合對象的底層實(shí)現(xiàn)可以是 intset（整數(shù)集合）或者 hashtable（字典或者也叫哈希表）。
intset（整數(shù)集合）當(dāng)一個(gè)集合只含有整數(shù)，并且元素不多時(shí)會(huì)使用 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ù)組將升級(jí)成一個(gè) 32 位的數(shù)組。升級(jí)可以提升 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)的目的。
看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注丸趣 TV 行業(yè)資訊頻道，感謝您對丸趣 TV 的支持。
