Redis 作為一種 KV 緩存服務器影钉，有著極高的性能，相對于 Memcache缩举，Redis 支持更多種數(shù)據(jù)類型，因此在業(yè)界應用廣泛。
記得有次參加面試蚁孔，面試官會問我 Redis 為什么快奶赔，我只能回答出如下兩點：
數(shù)據(jù)是存儲在內存中的。
Redis 是單線程的杠氢。
當然站刑，將數(shù)據(jù)存儲在內存中，讀取的時候不需要進行磁盤的 IO鼻百，單線程也保證了系統(tǒng)沒有線程的上下文切換绞旅。
但這兩點只是 Redis 高性能原因的很小一部分，下面從數(shù)據(jù)存儲層面上為大家分析 Redis 性能為何如此高温艇。
Redis性能如此高的原因因悲，我總結了如下幾點：
純內存操作
單線程
高效的數(shù)據(jù)結構
合理的數(shù)據(jù)編碼
其他方面的優(yōu)化
在 Redis 中，常用的 5 種數(shù)據(jù)結構和應用場景如下：
String：緩存勺爱、計數(shù)器晃琳、分布式鎖等。
List：鏈表琐鲁、隊列卫旱、微博關注人時間軸列表等棒假。
Hash：用戶信息佩脊、Hash 表等倘感。
Set：去重蚁廓、贊述么、踩击狮、共同好友等戈钢。
Zset：訪問量排行榜察署、點擊量排行榜等涝桅。
一拜姿、SDS
Redis 是用 C 語言開發(fā)完成的，但在 Redis 字符串中苹支，并沒有使用 C 語言中的字符串砾隅，而是用一種稱為 SDS（Simple Dynamic String）的結構體來保存字符串。
struct sdshdr {
int len;
int free;
char buf[];
}
SDS 的結構如上圖：
len：用于記錄 buf 中已使用空間的長度债蜜。
free：buf 中空閑空間的長度晴埂。
buf[]：存儲實際內容。
例如：執(zhí)行命令 set key value寻定，key 和 value 都是一個 SDS 類型的結構存儲在內存中儒洛。
二、SDS與C字符串的區(qū)別
1狼速、常數(shù)時間內獲得字符串長度
C 字符串本身不記錄長度信息琅锻，每次獲取長度信息都需要遍歷整個字符串，復雜度為 O(n)；
C 字符串遍歷時遇到 '\0' 時結束恼蓬。
SDS 中 len 字段保存著字符串的長度惊完，所以總能在常數(shù)時間內獲取字符串長度，復雜度是 O(1)处硬。
2小槐、避免緩沖區(qū)溢出
假設在內存中有兩個緊挨著的兩個字符串，s1=“xxxxx”和 s2=“yyyyy”荷辕。
由于在內存上緊緊相連凿跳，當我們對 s1 進行擴充的時候，將 s1=“xxxxxzzzzz”后疮方，由于沒有進行相應的內存重新分配控嗜，導致 s1 把 s2 覆蓋掉，導致 s2 被莫名其妙的修改骡显。
但 SDS 的 API 對字符串修改時首先會檢查空間是否足夠疆栏，若不充足則會分配新空間，避免了緩沖區(qū)溢出問題惫谤。
3承边、減少字符串修改時帶來的內存重新分配的次數(shù)
在 C 中，當我們頻繁的對一個字符串進行修改（append 或 trim）操作的時候石挂，需要頻繁的進行內存重新分配的操作，十分影響性能险污。
如果不小心忘記痹愚，有可能會導致內存溢出或內存泄漏，對于 Redis 來說蛔糯，本身就會很頻繁的修改字符串拯腮，所以使用 C 字符串并不合適。而 SDS 實現(xiàn)了空間預分配和惰性空間釋放兩種優(yōu)化策略：
1）空間預分配
當 SDS 的 API 對一個 SDS 修改后蚁飒，并且對 SDS 空間擴充時动壤，程序不僅會為 SDS 分配所需要的必須空間，還會分配額外的未使用空間淮逻。
分配規(guī)則如下：如果對 SDS 修改后琼懊，len 的長度小于 1M，那么程序將分配和 len 相同長度的未使用空間爬早。
舉個例子哼丈，如果 len=10，重新分配后筛严，buf 的實際長度會變?yōu)?10(已使用空間)+10(額外空間)+1(空字符)=21醉旦。如果對 SDS 修改后 len 長度大于 1M，那么程序將分配 1M 的未使用空間。
2）惰性空間釋放
當對 SDS 進行縮短操作時车胡，程序并不會回收多余的內存空間檬输，而是使用 free 字段將這些字節(jié)數(shù)量記錄下來不釋放，后面如果需要 append 操作匈棘，則直接使用 free 中未使用的空間丧慈，減少了內存的分配。
4羹饰、二進制安全
在 Redis 中不僅可以存儲 String 類型的數(shù)據(jù)伊滋，也可能存儲一些二進制數(shù)據(jù)。
二進制數(shù)據(jù)并不是規(guī)則的字符串格式队秩，其中會包含一些特殊的字符如 '\0'笑旺，在 C 中遇到 '\0' 則表示字符串的結束，但在 SDS 中馍资，標志字符串結束的是 len 屬性筒主。
三、字典
與 Java 中的 HashMap 類似鸟蟹，Redis 中的 Hash 比 Java 中的更高級一些乌妙。
Redis 本身就是 KV 服務器，除了 Redis 本身數(shù)據(jù)庫之外建钥，字典也是哈希鍵的底層實現(xiàn)藤韵。
字典的數(shù)據(jù)結構如下所示：
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é)點數(shù)量
unsigned long used;
}
重要的兩個字段是 dictht 和 trehashidx，這兩個字段與 rehash 有關熊经，下面重點介紹 rehash泽艘。
四、Rehash
1镐依、Rehash
學過 Java 的朋友都應該知道 HashMap 是如何 rehash 的匹涮，在此處我就不過多贅述，下面介紹 Redis 中 Rehash 的過程槐壳。
由上段代碼然低，我們可知 dict 中存儲了一個 dictht 的數(shù)組，長度為 2务唐，表明這個數(shù)據(jù)結構中實際存儲著兩個哈希表 ht[0] 和 ht[1]雳攘，為什么要存儲兩張 hash 表呢？
當然是為了 Rehash枫笛，Rehash 的過程如下：
為 ht[1] 分配空間来农。如果是擴容操作，ht[1] 的大小為第一個大于等于 ht[0].used*2 的 2^n崇堰；如果是縮容操作沃于，ht[1] 的大小為第一個大于等于 ht[0].used 的 2^n涩咖。
將 ht[0] 中的鍵值 Rehash 到 ht[1] 中。
當 ht[0] 全部遷移到 ht[1] 中后繁莹，釋放 ht[0]檩互，將 ht[1] 置為 ht[0]，并為 ht[1] 創(chuàng)建一張新表咨演，為下次 Rehash 做準備闸昨。
2、漸進式Rehash
由于 Redis 的 Rehash 操作是將 ht[0] 中的鍵值全部遷移到 ht[1]薄风，如果數(shù)據(jù)量小饵较，則遷移過程很快。但如果數(shù)據(jù)量很大遭赂，一個 Hash 表中存儲了幾萬甚至幾百萬幾千萬的鍵值時循诉，遷移過程很慢并會影響到其他用戶的使用。
為了避免 Rehash 對服務器性能造成影響撇他，Redis 采用了一種漸進式 Rehash 的策略茄猫，分多次、漸進的將 ht[0] 中的數(shù)據(jù)遷移到 ht[1] 中困肩。
前一過程如下：
為 ht[1] 分配空間划纽，讓字典同時擁有 ht[0] 和 ht[1] 兩個哈希表。
字典中維護一個 rehashidx锌畸，并將它置為 0勇劣，表示 Rehash 開始。
在 Rehash 期間潭枣，每次對字典操作時芭毙，程序還順便將 ht[0] 在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] 中，當 Rehash 完成后卸耘，將 rehashidx 屬性+1。當全部 rehash 完成后粘咖，將 rehashidx 置為 -1蚣抗，表示 rehash 完成。
注意：由于維護了兩張 Hash 表瓮下，所以在 Rehash 的過程中內存會增長翰铡。
另外，在 Rehash 過程中讽坏，字典會同時使用 ht[0] 和 ht[1]锭魔。所以在刪除、查找路呜、更新時會在兩張表中操作迷捧，在查詢時會現(xiàn)在第一張表中查詢织咧，如果第一張表中沒有，則會在第二張表中查詢漠秋。但新增時一律會在 ht[1] 中進行笙蒙，確保 ht[0] 中的數(shù)據(jù)只會減少不會增加。
五庆锦、跳躍表
Zset 是一個有序的鏈表結構捅位，其底層的數(shù)據(jù)結構是跳躍表 skiplist，其結構如下：
typedef struct zskiplistNode {
//成員對象
robj *obj;
//分值
double score;
//后退指針
struct zskiplistNode *backward;
//層
struct zskiplistLevel {
struct zskiplistNode *forward;//前進指針
unsigned int span;//跨度
} level[];
} zskiplistNode;
typedef struct zskiplist {
//表頭節(jié)點和表尾節(jié)點
struct zskiplistNode *header, *tail;
//表中節(jié)點的的數(shù)量
unsigned long length;
//表中層數(shù)最大的節(jié)點層數(shù)
int level;
} zskiplist;
前進指針：用于從表頭向表尾方向遍歷搂抒。
后退指針：用于從表尾向表頭方向回退一個節(jié)點艇搀，和前進指針不同的是，前進指針可以一次性跳躍多個節(jié)點求晶，后退指針每次只能后退到上一個節(jié)點焰雕。
跨度：表示當前節(jié)點和下一個節(jié)點的距離，跨度越大誉帅，兩個節(jié)點中間相隔的元素越多淀散。
在查詢過程中跳躍著前進。由于存在后退指針蚜锨，如果查詢時超出了范圍档插，通過后退指針回退到上一個節(jié)點后仍可以繼續(xù)向前遍歷。
六亚再、壓縮列表
壓縮列表 ziplist 是為 Redis 節(jié)約內存而開發(fā)的郭膛，是列表鍵和字典鍵的底層實現(xiàn)之一。
當元素個數(shù)較少時氛悬，Redis 用 ziplist 來存儲數(shù)據(jù)则剃，當元素個數(shù)超過某個值時，鏈表鍵中會把 ziplist 轉化為 linkedlist如捅，字典鍵中會把 ziplist 轉化為 hashtable棍现。
ziplist 是由一系列特殊編碼的連續(xù)內存塊組成的順序型的數(shù)據(jù)結構，ziplist 中可以包含多個 entry 節(jié)點镜遣，每個節(jié)點可以存放整數(shù)或者字符串己肮。
由于內存是連續(xù)分配的，所以遍歷速度很快悲关。
七谎僻、編碼轉化
Redis 使用對象（redisObject）來表示數(shù)據(jù)庫中的鍵值，當我們在 Redis 中創(chuàng)建一個鍵值對時寓辱，至少創(chuàng)建兩個對象艘绍，一個對象是用做鍵值對的鍵對象，另一個是鍵值對的值對象秫筏。
例如我們執(zhí)行 SET MSG XXX 時诱鞠，鍵值對的鍵是一個包含了字符串“MSG”的對象挎挖，鍵值對的值對象是包含字符串"XXX"的對象。
redisObject 的結構如下：
typedef struct redisObject{
//類型
unsigned type:4;
//編碼
unsigned encoding:4;
//指向底層數(shù)據(jù)結構的指針
void *ptr;
//...
}robj;
其中 type 字段記錄了對象的類型般甲，包含字符串對象肋乍、列表對象、哈希對象敷存、集合對象墓造、有序集合對象。
當我們執(zhí)行 type key 命令時返回的結果如下：
ptr 指針字段指向對象底層實現(xiàn)的數(shù)據(jù)結構锚烦，而這些數(shù)據(jù)結構是由 encoding 字段決定的觅闽，每種對象至少有兩種數(shù)據(jù)編碼：
可以通過 object encoding key 來查看對象所使用的編碼：
細心的讀者可能注意到，list涮俄、hash蛉拙、zset 三個鍵使用的是 ziplist 壓縮列表編碼，這就涉及到了 Redis 底層的編碼轉換彻亲。
上面介紹到孕锄，ziplist 是一種結構緊湊的數(shù)據(jù)結構，當某一鍵值中所包含的元素較少時苞尝，會優(yōu)先存儲在 ziplist 中畸肆，當元素個數(shù)超過某一值后，才將 ziplist 轉化為標準存儲結構宙址，而這一值是可配置的轴脐。
1、String 對象的編碼轉化
String 對象的編碼可以是 int 或 raw抡砂，對于 String 類型的鍵值大咱，如果我們存儲的是純數(shù)字，Redis 底層采用的是 int 類型的編碼注益，如果其中包括非數(shù)字碴巾，則會立即轉為 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 對象的編碼轉化
List 對象的編碼可以是 ziplist 或 linkedlist丑搔，對于 List 類型的鍵值厦瓢，當列表對象同時滿足以下兩個條件時，采用 ziplist 編碼：
列表對象保存的所有字符串元素的長度都小于 64 字節(jié)低匙。
列表對象保存的元素個數(shù)小于 512 個。
如果不滿足這兩個條件的任意一個碳锈，就會轉化為 linkedlist 編碼顽冶。
注意：這兩個條件是可以修改的。
在 redis.conf 中：
list-max-ziplist-entries 512
list-max-ziplist-value 64
3售碳、Set 類型的編碼轉化
Set 對象的編碼可以是 intset 或 hashtable强重，intset 編碼的結婚對象使用整數(shù)集合作為底層實現(xiàn)绞呈，把所有元素都保存在一個整數(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ù)時间景，Redis 會將 intset 轉化為 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>
當 Set 對象同時滿足以下兩個條件時佃声，對象采用 intset 編碼：
保存的所有元素都是整數(shù)值（小數(shù)不行）。
Set 對象保存的所有元素個數(shù)小于 512 個倘要。
不能滿足這兩個條件的任意一個圾亏，Set 都會采用 hashtable 存儲。
注意：第兩個條件是可以修改的封拧。
在 redis.conf 中：
set-max-intset-entries 512
4志鹃、Hash 對象的編碼轉化
Hash 對象的編碼可以是 ziplist 或 hashtable，當 Hash 以 ziplist 編碼存儲的時候泽西，保存同一鍵值對的兩個節(jié)點總是緊挨在一起曹铃，鍵節(jié)點在前，值節(jié)點在后：
當 Hash 對象同時滿足以下兩個條件時捧杉，Hash 對象采用 ziplist 編碼：
Hash 對象保存的所有鍵值對的鍵和值的字符串長度均小于 64 字節(jié)陕见。
Hash 對象保存的鍵值對數(shù)量小于 512 個。
如果不滿足以上條件的任意一個味抖，ziplist 就會轉化為 hashtable 編碼评甜。
注意：這兩個條件是可以修改的。
在 redis.conf 中：
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
5非竿、Zset 對象的編碼轉化
Zset 對象的編碼可以是 ziplist 或 zkiplist蜕着，當采用 ziplist 編碼存儲時，每個集合元素使用兩個緊挨在一起的壓縮列表來存儲红柱。
第一個節(jié)點存儲元素的成員承匣，第二個節(jié)點存儲元素的分值，并且按分值大小從小到大有序排列锤悄。
當 Zset 對象同時滿足一下兩個條件時韧骗，采用 ziplist 編碼：
Zset 保存的元素個數(shù)小于 128。
Zset 元素的成員長度都小于 64 字節(jié)零聚。
如果不滿足以上條件的任意一個袍暴，ziplist 就會轉化為 zkiplist 編碼。
注意：這兩個條件是可以修改的隶症。
在 redis.conf 中：
zset-max-ziplist-entries 128
zset-max-ziplist-value 64
思考：Zset 如何做到 O(1) 復雜度內元素并且快速進行范圍操作政模？
Zset 采用 skiplist 編碼時使用 zset 結構作為底層實現(xiàn)，該數(shù)據(jù)結構同時包含了一個跳躍表和一個字典蚂会。
其結構如下：
typedef struct zset{
zskiplist *zsl;
dict *dict;
}
Zset 中的 dict 字典為集合創(chuàng)建了一個從成員到分值之間的映射淋样，字典中的鍵保存了成員，字典中的值保存了成員的分值胁住，這樣定位元素時時間復雜度是 O(1)趁猴。
Zset 中的 zsl 跳躍表適合范圍操作刊咳，比如 ZRANK、ZRANGE 等儡司，程序使用 zkiplist娱挨。
另外，雖然 Zset 中使用了 dict 和 skiplist 存儲數(shù)據(jù)捕犬，但這兩種數(shù)據(jù)結構都會通過指針來共享相同的內存跷坝，所以沒有必要擔心內存的浪費。
八或听、過期數(shù)據(jù)的刪除對Redis性能影響
當我們對某些 key 設置了 expire 時探孝，數(shù)據(jù)到了時間會自動刪除。如果一個鍵過期了誉裆，它會在什么時候刪除呢顿颅？
下面介紹三種刪除策略：
定時刪除：在這是鍵的過期時間的同時，創(chuàng)建一個定時器 Timer足丢，讓定時器在鍵過期時間來臨時立即執(zhí)行對過期鍵的刪除粱腻。
惰性刪除：鍵過期后不管，每次讀取該鍵時斩跌，判斷該鍵是否過期绍些，如果過期刪除該鍵返回空。
定期刪除：每隔一段時間對數(shù)據(jù)庫中的過期鍵進行一次檢查耀鸦。
定時刪除對內存友好柬批，對 CPU 不友好。如果過期刪除的鍵比較多的時候袖订，刪除鍵這一行為會占用相當一部分 CPU 性能氮帐，會對 Redis 的吞吐量造成一定影響。
惰性刪除對 CPU 友好洛姑，內存不友好上沐。如果很多鍵過期了，但在將來很長一段時間內沒有很多客戶端訪問該鍵導致過期鍵不會被刪除楞艾，占用大量內存空間参咙。
定期刪除是定時刪除和惰性刪除的一種折中。每隔一段時間執(zhí)行一次刪除過期鍵的操作硫眯，并且限制刪除操作執(zhí)行的時長和頻率蕴侧。具體的操作如下：
Redis 會將每一個設置了 expire 的鍵存儲在一個獨立的字典中，以后會定時遍歷這個字典來刪除過期的 key两入。除了定時遍歷外净宵，它還會使用惰性刪除策略來刪除過期的 key。
-
Redis 默認每秒進行十次過期掃描，過期掃描不會掃描所有過期字典中的 key塘娶，而是采用了一種簡單的貪心策略。
從過期字典中隨機選擇 20 個 key痊夭；刪除這 20 個 key 中已過期的 key刁岸；如果過期 key 比例超過 1/4，那就重復步驟 1她我。
同時虹曙，為了保證在過期掃描期間不會出現(xiàn)過度循環(huán)，導致線程卡死番舆，算法還增加了掃描時間上限酝碳，默認不會超過 25ms。
