Redis 作為一種 KV 緩存服務(wù)器，有著極高的性能，相對(duì)于 Memcache，Redis 支持更多種數(shù)據(jù)類型，因此在業(yè)界應(yīng)用廣泛。
記得有次參加面試，面試官會(huì)問我 Redis 為什么快，我只能回答出如下兩點(diǎn)：
數(shù)據(jù)是存儲(chǔ)在內(nèi)存中的。
Redis 是單線程的。
當(dāng)然，將數(shù)據(jù)存儲(chǔ)在內(nèi)存中，讀取的時(shí)候不需要進(jìn)行磁盤的 IO，單線程也保證了系統(tǒng)沒有線程的上下文切換。
但這兩點(diǎn)只是 Redis 高性能原因的很小一部分，下面從數(shù)據(jù)存儲(chǔ)層面上為大家分析 Redis 性能為何如此高。
Redis性能如此高的原因，我總結(jié)了如下幾點(diǎn)：
純內(nèi)存操作
單線程
高效的數(shù)據(jù)結(jié)構(gòu)
合理的數(shù)據(jù)編碼
其他方面的優(yōu)化
在 Redis 中，常用的 5 種數(shù)據(jù)結(jié)構(gòu)和應(yīng)用場(chǎng)景如下：
String：緩存、計(jì)數(shù)器、分布式鎖等。
List：鏈表、隊(duì)列、微博關(guān)注人時(shí)間軸列表等。
Hash：用戶信息、Hash 表等。
Set：去重、贊、踩、共同好友等。
Zset：訪問量排行榜、點(diǎn)擊量排行榜等。
一、SDS
Redis 是用 C 語言開發(fā)完成的，但在 Redis 字符串中，并沒有使用 C 語言中的字符串，而是用一種稱為 SDS（Simple Dynamic String）的結(jié)構(gòu)體來保存字符串。
struct sdshdr {
int len;
int free;
char buf[];
}
SDS 的結(jié)構(gòu)如上圖：
len：用于記錄 buf 中已使用空間的長度。
free：buf 中空閑空間的長度。
buf[]：存儲(chǔ)實(shí)際內(nèi)容。
例如：執(zhí)行命令 set key value，key 和 value 都是一個(gè) SDS 類型的結(jié)構(gòu)存儲(chǔ)在內(nèi)存中。
二、SDS與C字符串的區(qū)別
1、常數(shù)時(shí)間內(nèi)獲得字符串長度
C 字符串本身不記錄長度信息，每次獲取長度信息都需要遍歷整個(gè)字符串，復(fù)雜度為 O(n)；
C 字符串遍歷時(shí)遇到 '\0' 時(shí)結(jié)束。
SDS 中 len 字段保存著字符串的長度，所以總能在常數(shù)時(shí)間內(nèi)獲取字符串長度，復(fù)雜度是 O(1)。
2、避免緩沖區(qū)溢出
假設(shè)在內(nèi)存中有兩個(gè)緊挨著的兩個(gè)字符串，s1=“xxxxx”和 s2=“yyyyy”。
由于在內(nèi)存上緊緊相連，當(dāng)我們對(duì) s1 進(jìn)行擴(kuò)充的時(shí)候，將 s1=“xxxxxzzzzz”后，由于沒有進(jìn)行相應(yīng)的內(nèi)存重新分配，導(dǎo)致 s1 把 s2 覆蓋掉，導(dǎo)致 s2 被莫名其妙的修改。
但 SDS 的 API 對(duì)字符串修改時(shí)首先會(huì)檢查空間是否足夠，若不充足則會(huì)分配新空間，避免了緩沖區(qū)溢出問題。
3、減少字符串修改時(shí)帶來的內(nèi)存重新分配的次數(shù)
在 C 中，當(dāng)我們頻繁的對(duì)一個(gè)字符串進(jìn)行修改（append 或 trim）操作的時(shí)候，需要頻繁的進(jìn)行內(nèi)存重新分配的操作，十分影響性能。
如果不小心忘記，有可能會(huì)導(dǎo)致內(nèi)存溢出或內(nèi)存泄漏，對(duì)于 Redis 來說，本身就會(huì)很頻繁的修改字符串，所以使用 C 字符串并不合適。而 SDS 實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略：
1）空間預(yù)分配
當(dāng) SDS 的 API 對(duì)一個(gè) SDS 修改后，并且對(duì) SDS 空間擴(kuò)充時(shí)，程序不僅會(huì)為 SDS 分配所需要的必須空間，還會(huì)分配額外的未使用空間。
分配規(guī)則如下：如果對(duì) SDS 修改后，len 的長度小于 1M，那么程序?qū)⒎峙浜?len 相同長度的未使用空間。
舉個(gè)例子，如果 len=10，重新分配后，buf 的實(shí)際長度會(huì)變?yōu)?10(已使用空間)+10(額外空間)+1(空字符)=21。如果對(duì) SDS 修改后 len 長度大于 1M，那么程序?qū)⒎峙?1M 的未使用空間。
2）惰性空間釋放
當(dāng)對(duì) SDS 進(jìn)行縮短操作時(shí)，程序并不會(huì)回收多余的內(nèi)存空間，而是使用 free 字段將這些字節(jié)數(shù)量記錄下來不釋放，后面如果需要 append 操作，則直接使用 free 中未使用的空間，減少了內(nèi)存的分配。
4、二進(jìn)制安全
在 Redis 中不僅可以存儲(chǔ) String 類型的數(shù)據(jù)，也可能存儲(chǔ)一些二進(jìn)制數(shù)據(jù)。
二進(jìn)制數(shù)據(jù)并不是規(guī)則的字符串格式，其中會(huì)包含一些特殊的字符如 '\0'，在 C 中遇到 '\0' 則表示字符串的結(jié)束，但在 SDS 中，標(biāo)志字符串結(jié)束的是 len 屬性。
三、字典
與 Java 中的 HashMap 類似，Redis 中的 Hash 比 Java 中的更高級(jí)一些。
Redis 本身就是 KV 服務(wù)器，除了 Redis 本身數(shù)據(jù)庫之外，字典也是哈希鍵的底層實(shí)現(xiàn)。
字典的數(shù)據(jù)結(jié)構(gòu)如下所示：
typedef struct dict{
dictType *type;
void *privdata;
dictht ht[2];
int trehashidx;
}
typedef struct dictht{
//哈希表數(shù)組
dectEntrt **table;
//哈希表大小
unsigned long size;
//
unsigned long sizemask;
//哈希表已有節(jié)點(diǎn)數(shù)量
unsigned long used;
}
重要的兩個(gè)字段是 dictht 和 trehashidx，這兩個(gè)字段與 rehash 有關(guān)，下面重點(diǎn)介紹 rehash。
四、Rehash
1、Rehash
學(xué)過 Java 的朋友都應(yīng)該知道 HashMap 是如何 rehash 的，在此處我就不過多贅述，下面介紹 Redis 中 Rehash 的過程。
由上段代碼，我們可知 dict 中存儲(chǔ)了一個(gè) dictht 的數(shù)組，長度為 2，表明這個(gè)數(shù)據(jù)結(jié)構(gòu)中實(shí)際存儲(chǔ)著兩個(gè)哈希表 ht[0] 和 ht[1]，為什么要存儲(chǔ)兩張 hash 表呢？
當(dāng)然是為了 Rehash，Rehash 的過程如下：
為 ht[1] 分配空間。如果是擴(kuò)容操作，ht[1] 的大小為第一個(gè)大于等于 ht[0].used*2 的 2^n；如果是縮容操作，ht[1] 的大小為第一個(gè)大于等于 ht[0].used 的 2^n。
將 ht[0] 中的鍵值 Rehash 到 ht[1] 中。
當(dāng) ht[0] 全部遷移到 ht[1] 中后，釋放 ht[0]，將 ht[1] 置為 ht[0]，并為 ht[1] 創(chuàng)建一張新表，為下次 Rehash 做準(zhǔn)備。
2、漸進(jìn)式Rehash
由于 Redis 的 Rehash 操作是將 ht[0] 中的鍵值全部遷移到 ht[1]，如果數(shù)據(jù)量小，則遷移過程很快。但如果數(shù)據(jù)量很大，一個(gè) Hash 表中存儲(chǔ)了幾萬甚至幾百萬幾千萬的鍵值時(shí)，遷移過程很慢并會(huì)影響到其他用戶的使用。
為了避免 Rehash 對(duì)服務(wù)器性能造成影響，Redis 采用了一種漸進(jìn)式 Rehash 的策略，分多次、漸進(jìn)的將 ht[0] 中的數(shù)據(jù)遷移到 ht[1] 中。
前一過程如下：
為 ht[1] 分配空間，讓字典同時(shí)擁有 ht[0] 和 ht[1] 兩個(gè)哈希表。
字典中維護(hù)一個(gè) rehashidx，并將它置為 0，表示 Rehash 開始。
在 Rehash 期間，每次對(duì)字典操作時(shí)，程序還順便將 ht[0] 在 rehashidx 索引上的所有鍵值對(duì) rehash 到 ht[1] 中，當(dāng) Rehash 完成后，將 rehashidx 屬性+1。當(dāng)全部 rehash 完成后，將 rehashidx 置為 -1，表示 rehash 完成。
注意：由于維護(hù)了兩張 Hash 表，所以在 Rehash 的過程中內(nèi)存會(huì)增長。
另外，在 Rehash 過程中，字典會(huì)同時(shí)使用 ht[0] 和 ht[1]。所以在刪除、查找、更新時(shí)會(huì)在兩張表中操作，在查詢時(shí)會(huì)現(xiàn)在第一張表中查詢，如果第一張表中沒有，則會(huì)在第二張表中查詢。但新增時(shí)一律會(huì)在 ht[1] 中進(jìn)行，確保 ht[0] 中的數(shù)據(jù)只會(huì)減少不會(huì)增加。
五、跳躍表
Zset 是一個(gè)有序的鏈表結(jié)構(gòu)，其底層的數(shù)據(jù)結(jié)構(gòu)是跳躍表 skiplist，其結(jié)構(gòu)如下：
typedef struct zskiplistNode {
//成員對(duì)象
robj *obj;
//分值
double score;
//后退指針
struct zskiplistNode *backward;
//層
struct zskiplistLevel {
struct zskiplistNode *forward;//前進(jìn)指針
unsigned int span;//跨度
} level[];
} zskiplistNode;
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;
前進(jìn)指針：用于從表頭向表尾方向遍歷。
后退指針：用于從表尾向表頭方向回退一個(gè)節(jié)點(diǎn)，和前進(jìn)指針不同的是，前進(jìn)指針可以一次性跳躍多個(gè)節(jié)點(diǎn)，后退指針每次只能后退到上一個(gè)節(jié)點(diǎn)。
跨度：表示當(dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的距離，跨度越大，兩個(gè)節(jié)點(diǎn)中間相隔的元素越多。
在查詢過程中跳躍著前進(jìn)。由于存在后退指針，如果查詢時(shí)超出了范圍，通過后退指針回退到上一個(gè)節(jié)點(diǎn)后仍可以繼續(xù)向前遍歷。
六、壓縮列表
壓縮列表 ziplist 是為 Redis 節(jié)約內(nèi)存而開發(fā)的，是列表鍵和字典鍵的底層實(shí)現(xiàn)之一。
當(dāng)元素個(gè)數(shù)較少時(shí)，Redis 用 ziplist 來存儲(chǔ)數(shù)據(jù)，當(dāng)元素個(gè)數(shù)超過某個(gè)值時(shí)，鏈表鍵中會(huì)把 ziplist 轉(zhuǎn)化為 linkedlist，字典鍵中會(huì)把 ziplist 轉(zhuǎn)化為 hashtable。
ziplist 是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型的數(shù)據(jù)結(jié)構(gòu)，ziplist 中可以包含多個(gè) entry 節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以存放整數(shù)或者字符串。
由于內(nèi)存是連續(xù)分配的，所以遍歷速度很快。
七、編碼轉(zhuǎn)化
Redis 使用對(duì)象（redisObject）來表示數(shù)據(jù)庫中的鍵值，當(dāng)我們?cè)?Redis 中創(chuàng)建一個(gè)鍵值對(duì)時(shí)，至少創(chuàng)建兩個(gè)對(duì)象，一個(gè)對(duì)象是用做鍵值對(duì)的鍵對(duì)象，另一個(gè)是鍵值對(duì)的值對(duì)象。
例如我們執(zhí)行 SET MSG XXX 時(shí)，鍵值對(duì)的鍵是一個(gè)包含了字符串“MSG”的對(duì)象，鍵值對(duì)的值對(duì)象是包含字符串"XXX"的對(duì)象。
redisObject 的結(jié)構(gòu)如下：
typedef struct redisObject{
//類型
unsigned type:4;
//編碼
unsigned encoding:4;
//指向底層數(shù)據(jù)結(jié)構(gòu)的指針
void *ptr;
//...
}robj;
其中 type 字段記錄了對(duì)象的類型，包含字符串對(duì)象、列表對(duì)象、哈希對(duì)象、集合對(duì)象、有序集合對(duì)象。
當(dāng)我們執(zhí)行 type key 命令時(shí)返回的結(jié)果如下：
ptr 指針字段指向?qū)ο蟮讓訉?shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，而這些數(shù)據(jù)結(jié)構(gòu)是由 encoding 字段決定的，每種對(duì)象至少有兩種數(shù)據(jù)編碼：
可以通過 object encoding key 來查看對(duì)象所使用的編碼：
細(xì)心的讀者可能注意到，list、hash、zset 三個(gè)鍵使用的是 ziplist 壓縮列表編碼，這就涉及到了 Redis 底層的編碼轉(zhuǎn)換。
上面介紹到，ziplist 是一種結(jié)構(gòu)緊湊的數(shù)據(jù)結(jié)構(gòu)，當(dāng)某一鍵值中所包含的元素較少時(shí)，會(huì)優(yōu)先存儲(chǔ)在 ziplist 中，當(dāng)元素個(gè)數(shù)超過某一值后，才將 ziplist 轉(zhuǎn)化為標(biāo)準(zhǔn)存儲(chǔ)結(jié)構(gòu)，而這一值是可配置的。
1、String 對(duì)象的編碼轉(zhuǎn)化
String 對(duì)象的編碼可以是 int 或 raw，對(duì)于 String 類型的鍵值，如果我們存儲(chǔ)的是純數(shù)字，Redis 底層采用的是 int 類型的編碼，如果其中包括非數(shù)字，則會(huì)立即轉(zhuǎn)為 raw 編碼：
127.0.0.1:6379> set str 1
OK
127.0.0.1:6379> object encoding str
"int"
127.0.0.1:6379> set str 1a
OK
127.0.0.1:6379> object encoding str
"raw"
127.0.0.1:6379>
2、List 對(duì)象的編碼轉(zhuǎn)化
List 對(duì)象的編碼可以是 ziplist 或 linkedlist，對(duì)于 List 類型的鍵值，當(dāng)列表對(duì)象同時(shí)滿足以下兩個(gè)條件時(shí)，采用 ziplist 編碼：
列表對(duì)象保存的所有字符串元素的長度都小于 64 字節(jié)。
列表對(duì)象保存的元素個(gè)數(shù)小于 512 個(gè)。
如果不滿足這兩個(gè)條件的任意一個(gè)，就會(huì)轉(zhuǎn)化為 linkedlist 編碼。
注意：這兩個(gè)條件是可以修改的。
在 redis.conf 中：
list-max-ziplist-entries 512
list-max-ziplist-value 64
3、Set 類型的編碼轉(zhuǎn)化
Set 對(duì)象的編碼可以是 intset 或 hashtable，intset 編碼的結(jié)婚對(duì)象使用整數(shù)集合作為底層實(shí)現(xiàn)，把所有元素都保存在一個(gè)整數(shù)集合里面。
127.0.0.1:6379> sadd set 1 2 3
(integer) 3
127.0.0.1:6379> object encoding set
"intset"
127.0.0.1:6379>
如果 set 集合中保存了非整數(shù)類型的數(shù)據(jù)時(shí)，Redis 會(huì)將 intset 轉(zhuǎn)化為 hashtable：
127.0.0.1:6379> sadd set 1 2 3
(integer) 3
127.0.0.1:6379> object encoding set
"intset"
127.0.0.1:6379> sadd set a
(integer) 1
127.0.0.1:6379> object encoding set
"hashtable"
127.0.0.1:6379>
當(dāng) Set 對(duì)象同時(shí)滿足以下兩個(gè)條件時(shí)，對(duì)象采用 intset 編碼：
保存的所有元素都是整數(shù)值（小數(shù)不行）。
Set 對(duì)象保存的所有元素個(gè)數(shù)小于 512 個(gè)。
不能滿足這兩個(gè)條件的任意一個(gè)，Set 都會(huì)采用 hashtable 存儲(chǔ)。
注意：第兩個(gè)條件是可以修改的。
在 redis.conf 中：
set-max-intset-entries 512
4、Hash 對(duì)象的編碼轉(zhuǎn)化
Hash 對(duì)象的編碼可以是 ziplist 或 hashtable，當(dāng) Hash 以 ziplist 編碼存儲(chǔ)的時(shí)候，保存同一鍵值對(duì)的兩個(gè)節(jié)點(diǎn)總是緊挨在一起，鍵節(jié)點(diǎn)在前，值節(jié)點(diǎn)在后：
當(dāng) Hash 對(duì)象同時(shí)滿足以下兩個(gè)條件時(shí)，Hash 對(duì)象采用 ziplist 編碼：
Hash 對(duì)象保存的所有鍵值對(duì)的鍵和值的字符串長度均小于 64 字節(jié)。
Hash 對(duì)象保存的鍵值對(duì)數(shù)量小于 512 個(gè)。
如果不滿足以上條件的任意一個(gè)，ziplist 就會(huì)轉(zhuǎn)化為 hashtable 編碼。
注意：這兩個(gè)條件是可以修改的。
在 redis.conf 中：
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
5、Zset 對(duì)象的編碼轉(zhuǎn)化
Zset 對(duì)象的編碼可以是 ziplist 或 zkiplist，當(dāng)采用 ziplist 編碼存儲(chǔ)時(shí)，每個(gè)集合元素使用兩個(gè)緊挨在一起的壓縮列表來存儲(chǔ)。
第一個(gè)節(jié)點(diǎn)存儲(chǔ)元素的成員，第二個(gè)節(jié)點(diǎn)存儲(chǔ)元素的分值，并且按分值大小從小到大有序排列。
當(dāng) Zset 對(duì)象同時(shí)滿足一下兩個(gè)條件時(shí)，采用 ziplist 編碼：
Zset 保存的元素個(gè)數(shù)小于 128。
Zset 元素的成員長度都小于 64 字節(jié)。
如果不滿足以上條件的任意一個(gè)，ziplist 就會(huì)轉(zhuǎn)化為 zkiplist 編碼。
注意：這兩個(gè)條件是可以修改的。
在 redis.conf 中：
zset-max-ziplist-entries 128
zset-max-ziplist-value 64
思考：Zset 如何做到 O(1) 復(fù)雜度內(nèi)元素并且快速進(jìn)行范圍操作？
Zset 采用 skiplist 編碼時(shí)使用 zset 結(jié)構(gòu)作為底層實(shí)現(xiàn)，該數(shù)據(jù)結(jié)構(gòu)同時(shí)包含了一個(gè)跳躍表和一個(gè)字典。
其結(jié)構(gòu)如下：
typedef struct zset{
zskiplist *zsl;
dict *dict;
}
Zset 中的 dict 字典為集合創(chuàng)建了一個(gè)從成員到分值之間的映射，字典中的鍵保存了成員，字典中的值保存了成員的分值，這樣定位元素時(shí)時(shí)間復(fù)雜度是 O(1)。
Zset 中的 zsl 跳躍表適合范圍操作，比如 ZRANK、ZRANGE 等，程序使用 zkiplist。
另外，雖然 Zset 中使用了 dict 和 skiplist 存儲(chǔ)數(shù)據(jù)，但這兩種數(shù)據(jù)結(jié)構(gòu)都會(huì)通過指針來共享相同的內(nèi)存，所以沒有必要擔(dān)心內(nèi)存的浪費(fèi)。
八、過期數(shù)據(jù)的刪除對(duì)Redis性能影響
當(dāng)我們對(duì)某些 key 設(shè)置了 expire 時(shí)，數(shù)據(jù)到了時(shí)間會(huì)自動(dòng)刪除。如果一個(gè)鍵過期了，它會(huì)在什么時(shí)候刪除呢？
下面介紹三種刪除策略：
定時(shí)刪除：在這是鍵的過期時(shí)間的同時(shí)，創(chuàng)建一個(gè)定時(shí)器 Timer，讓定時(shí)器在鍵過期時(shí)間來臨時(shí)立即執(zhí)行對(duì)過期鍵的刪除。
惰性刪除：鍵過期后不管，每次讀取該鍵時(shí)，判斷該鍵是否過期，如果過期刪除該鍵返回空。
定期刪除：每隔一段時(shí)間對(duì)數(shù)據(jù)庫中的過期鍵進(jìn)行一次檢查。
定時(shí)刪除對(duì)內(nèi)存友好，對(duì) CPU 不友好。如果過期刪除的鍵比較多的時(shí)候，刪除鍵這一行為會(huì)占用相當(dāng)一部分 CPU 性能，會(huì)對(duì) Redis 的吞吐量造成一定影響。
惰性刪除對(duì) CPU 友好，內(nèi)存不友好。如果很多鍵過期了，但在將來很長一段時(shí)間內(nèi)沒有很多客戶端訪問該鍵導(dǎo)致過期鍵不會(huì)被刪除，占用大量內(nèi)存空間。
定期刪除是定時(shí)刪除和惰性刪除的一種折中。每隔一段時(shí)間執(zhí)行一次刪除過期鍵的操作，并且限制刪除操作執(zhí)行的時(shí)長和頻率。具體的操作如下：
Redis 會(huì)將每一個(gè)設(shè)置了 expire 的鍵存儲(chǔ)在一個(gè)獨(dú)立的字典中，以后會(huì)定時(shí)遍歷這個(gè)字典來刪除過期的 key。除了定時(shí)遍歷外，它還會(huì)使用惰性刪除策略來刪除過期的 key。
-
Redis 默認(rèn)每秒進(jìn)行十次過期掃描，過期掃描不會(huì)掃描所有過期字典中的 key，而是采用了一種簡單的貪心策略。
從過期字典中隨機(jī)選擇 20 個(gè) key；刪除這 20 個(gè) key 中已過期的 key；如果過期 key 比例超過 1/4，那就重復(fù)步驟 1。
同時(shí)，為了保證在過期掃描期間不會(huì)出現(xiàn)過度循環(huán)，導(dǎo)致線程卡死，算法還增加了掃描時(shí)間上限，默認(rèn)不會(huì)超過 25ms。
