Redis 作為一種 KV 緩存服務(wù)器，有著極高的性能，相對于 Memcache，Redis 支持更多種數(shù)據(jù)類型，因此在業(yè)界應(yīng)用廣泛。

記得剛畢業(yè)那會參加面試，面試官會問我 Redis 為什么快，由于當時技術(shù)水平有限，我只能回答出如下兩點：

• 數(shù)據(jù)是存儲在內(nèi)存中的。
• Redis 是單線程的。

當然，將數(shù)據(jù)存儲在內(nèi)存中，讀取的時候不需要進行磁盤的 IO，單線程也保證了系統(tǒng)沒有線程的上下文切換。

但這兩點只是 Redis 高性能原因的很小一部分，下面從數(shù)據(jù)存儲層面上為大家分析 Redis 性能為何如此高。

Redis性能如此高的原因，我總結(jié)了如下幾點：

• 純內(nèi)存操作
• 單線程
• 高效的數(shù)據(jù)結(jié)構(gòu)
• 合理的數(shù)據(jù)編碼
• 其他方面的優(yōu)化

在 Redis 中，常用的 5 種數(shù)據(jù)結(jié)構(gòu)和應(yīng)用場景如下：

• String：緩存、計數(shù)器、分布式鎖等。
• List：鏈表、隊列、微博關(guān)注人時間軸列表等。
• Hash：用戶信息、Hash 表等。
• Set：去重、贊、踩、共同好友等。
• Zset：訪問量排行榜、點擊量排行榜等。

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[]：存儲實際內(nèi)容。

例如：執(zhí)行命令 set key value，key 和 value 都是一個 SDS 類型的結(jié)構(gòu)存儲在內(nèi)存中。

SDS 與 C 字符串的區(qū)別

①常數(shù)時間內(nèi)獲得字符串長度

C 字符串本身不記錄長度信息，每次獲取長度信息都需要遍歷整個字符串，復(fù)雜度為 O(n)；C 字符串遍歷時遇到 '\0' 時結(jié)束。

SDS 中 len 字段保存著字符串的長度，所以總能在常數(shù)時間內(nèi)獲取字符串長度，復(fù)雜度是 O(1)。

②避免緩沖區(qū)溢出

假設(shè)在內(nèi)存中有兩個緊挨著的兩個字符串，s1=“xxxxx”和 s2=“yyyyy”。

由于在內(nèi)存上緊緊相連，當我們對 s1 進行擴充的時候，將 s1=“xxxxxzzzzz”后，由于沒有進行相應(yīng)的內(nèi)存重新分配，導(dǎo)致 s1 把 s2 覆蓋掉，導(dǎo)致 s2 被莫名其妙的修改。

但 SDS 的 API 對 zfc 修改時首先會檢查空間是否足夠，若不充足則會分配新空間，避免了緩沖區(qū)溢出問題。

③減少字符串修改時帶來的內(nèi)存重新分配的次數(shù)

在 C 中，當我們頻繁的對一個字符串進行修改（append 或 trim）操作的時候，需要頻繁的進行內(nèi)存重新分配的操作，十分影響性能。

如果不小心忘記，有可能會導(dǎo)致內(nèi)存溢出或內(nèi)存泄漏，對于 Redis 來說，本身就會很頻繁的修改字符串，所以使用 C 字符串并不合適。而 SDS 實現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略：

空間預(yù)分配：當 SDS 的 API 對一個 SDS 修改后，并且對 SDS 空間擴充時，程序不僅會為 SDS 分配所需要的必須空間，還會分配額外的未使用空間。

分配規(guī)則如下：如果對 SDS 修改后，len 的長度小于 1M，那么程序?qū)⒎峙浜?len 相同長度的未使用空間。

舉個例子，如果 len=10，重新分配后，buf 的實際長度會變?yōu)?10(已使用空間)+10(額外空間)+1(空字符)=21。

如果對 SDS 修改后 len 長度大于 1M，那么程序?qū)⒎峙?1M 的未使用空間。

惰性空間釋放：當對 SDS 進行縮短操作時，程序并不會回收多余的內(nèi)存空間，而是使用 free 字段將這些字節(jié)數(shù)量記錄下來不釋放，后面如果需要 append 操作，則直接使用 free 中未使用的空間，減少了內(nèi)存的分配。

④二進制安全

在 Redis 中不僅可以存儲 String 類型的數(shù)據(jù)，也可能存儲一些二進制數(shù)據(jù)。

二進制數(shù)據(jù)并不是規(guī)則的字符串格式，其中會包含一些特殊的字符如 '\0'，在 C 中遇到 '\0' 則表示字符串的結(jié)束，但在 SDS 中，標志字符串結(jié)束的是 len 屬性。

字典

與 Java 中的 HashMap 類似，Redis 中的 Hash 比 Java 中的更高級一些。

Redis 本身就是 KV 服務(wù)器，除了 Redis 本身數(shù)據(jù)庫之外，字典也是哈希鍵的底層實現(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é)點數(shù)量 
     unsigned long used; 
 }

重要的兩個字段是 dictht 和 trehashidx，這兩個字段與 rehash 有關(guān)，下面重點介紹 rehash。

Rehash

學(xué)過 Java 的朋友都應(yīng)該知道 HashMap 是如何 rehash 的，在此處我就不過多贅述，下面介紹 Redis 中 Rehash 的過程。

由上段代碼，我們可知 dict 中存儲了一個 dictht 的數(shù)組，長度為 2，表明這個數(shù)據(jù)結(jié)構(gòu)中實際存儲著兩個哈希表 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 做準備。

漸進式 Rehash

由于 Redis 的 Rehash 操作是將 ht[0] 中的鍵值全部遷移到 ht[1]，如果數(shù)據(jù)量小，則遷移過程很快。

但如果數(shù)據(jù)量很大，一個 Hash 表中存儲了幾萬甚至幾百萬幾千萬的鍵值時，遷移過程很慢并會影響到其他用戶的使用。

為了避免 Rehash 對服務(wù)器性能造成影響，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 的過程中內(nèi)存會增長。另外，在 Rehash 過程中，字典會同時使用 ht[0] 和 ht[1]。

所以在刪除、查找、更新時會在兩張表中操作，在查詢時會現(xiàn)在***張表中查詢，如果***張表中沒有，則會在第二張表中查詢。但新增時一律會在 ht[1] 中進行，確保 ht[0] 中的數(shù)據(jù)只會減少不會增加。

跳躍表

Zset 是一個有序的鏈表結(jié)構(gòu)，其底層的數(shù)據(jù)結(jié)構(gòu)是跳躍表 skiplist，其結(jié)構(gòu)如下：

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é)約內(nèi)存而開發(fā)的，是列表鍵和字典鍵的底層實現(xiàn)之一。

當元素個數(shù)較少時，Redis 用 ziplist 來存儲數(shù)據(jù)，當元素個數(shù)超過某個值時，鏈表鍵中會把 ziplist 轉(zhuǎn)化為 linkedlist，字典鍵中會把 ziplist 轉(zhuǎn)化為 hashtable。 

ziplist 是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型的數(shù)據(jù)結(jié)構(gòu)，ziplist 中可以包含多個 entry 節(jié)點，每個節(jié)點可以存放整數(shù)或者字符串。

由于內(nèi)存是連續(xù)分配的，所以遍歷速度很快。

編碼轉(zhuǎn)化

Redis 使用對象（redisObject）來表示數(shù)據(jù)庫中的鍵值，當我們在 Redis 中創(chuàng)建一個鍵值對時，至少創(chuàng)建兩個對象，一個對象是用做鍵值對的鍵對象，另一個是鍵值對的值對象。

例如我們執(zhí)行 SET MSG XXX 時，鍵值對的鍵是一個包含了字符串“MSG“的對象，鍵值對的值對象是包含字符串"XXX"的對象。

redisObject 的結(jié)構(gòu)如下：

typedef struct redisObject{ 
     //類型 
    unsigned type:4; 
    //編碼 
    unsigned encoding:4; 
    //指向底層數(shù)據(jù)結(jié)構(gòu)的指針 
    void *ptr; 
     //... 
  }robj;

其中 type 字段記錄了對象的類型，包含字符串對象、列表對象、哈希對象、集合對象、有序集合對象。

當我們執(zhí)行 type key 命令時返回的結(jié)果如下：

ptr 指針字段指向?qū)ο蟮讓訉崿F(xiàn)的數(shù)據(jù)結(jié)構(gòu)，而這些數(shù)據(jù)結(jié)構(gòu)是由 encoding 字段決定的，每種對象至少有兩種數(shù)據(jù)編碼：

可以通過 object encoding key 來查看對象所使用的編碼：

細心的讀者可能注意到，list、hash、zset 三個鍵使用的是 ziplist 壓縮列表編碼，這就涉及到了 Redis 底層的編碼轉(zhuǎn)換。

上面介紹到，ziplist 是一種結(jié)構(gòu)緊湊的數(shù)據(jù)結(jié)構(gòu)，當某一鍵值中所包含的元素較少時，會優(yōu)先存儲在 ziplist 中，當元素個數(shù)超過某一值后，才將 ziplist 轉(zhuǎn)化為標準存儲結(jié)構(gòu)，而這一值是可配置的。

String 對象的編碼轉(zhuǎn)化

String 對象的編碼可以是 int 或 raw，對于 String 類型的鍵值，如果我們存儲的是純數(shù)字，Redis 底層采用的是 int 類型的編碼，如果其中包括非數(shù)字，則會立即轉(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>

List 對象的編碼轉(zhuǎn)化

List 對象的編碼可以是 ziplist 或 linkedlist，對于 List 類型的鍵值，當列表對象同時滿足以下兩個條件時，采用 ziplist 編碼：

• 列表對象保存的所有字符串元素的長度都小于 64 字節(jié)。
• 列表對象保存的元素個數(shù)小于 512 個。

如果不滿足這兩個條件的任意一個，就會轉(zhuǎn)化為 linkedlist 編碼。注意：這兩個條件是可以修改的，在 redis.conf 中：

list-max-ziplist-entries 512 
 list-max-ziplist-value 64

Set 類型的編碼轉(zhuǎn)化

Set 對象的編碼可以是 intset 或 hashtable，intset 編碼的結(jié)婚對象使用整數(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 轉(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>

當 Set 對象同時滿足以下兩個條件時，對象采用 intset 編碼：

• 保存的所有元素都是整數(shù)值（小數(shù)不行）。
• Set 對象保存的所有元素個數(shù)小于 512 個。

不能滿足這兩個條件的任意一個，Set 都會采用 hashtable 存儲。注意：第兩個條件是可以修改的，在 redis.conf 中：

set-max-intset-entries 512

Hash 對象的編碼轉(zhuǎn)化

Hash 對象的編碼可以是 ziplist 或 hashtable，當 Hash 以 ziplist 編碼存儲的時候，保存同一鍵值對的兩個節(jié)點總是緊挨在一起，鍵節(jié)點在前，值節(jié)點在后：

當 Hash 對象同時滿足以下兩個條件時，Hash 對象采用 ziplist 編碼：

• Hash 對象保存的所有鍵值對的鍵和值的字符串長度均小于 64 字節(jié)。
• Hash 對象保存的鍵值對數(shù)量小于 512 個。

如果不滿足以上條件的任意一個，ziplist 就會轉(zhuǎn)化為 hashtable 編碼。注意：這兩個條件是可以修改的，在 redis.conf 中：

hash-max-ziplist-entries 512 
 hash-max-ziplist-value 64

Zset 對象的編碼轉(zhuǎn)化

Zset 對象的編碼可以是 ziplist 或 zkiplist，當采用 ziplist 編碼存儲時，每個集合元素使用兩個緊挨在一起的壓縮列表來存儲。

***個節(jié)點存儲元素的成員，第二個節(jié)點存儲元素的分值，并且按分值大小從小到大有序排列。

當 Zset 對象同時滿足一下兩個條件時，采用 ziplist 編碼：

• Zset 保存的元素個數(shù)小于 128。
• Zset 元素的成員長度都小于 64 字節(jié)。

如果不滿足以上條件的任意一個，ziplist 就會轉(zhuǎn)化為 zkiplist 編碼。注意：這兩個條件是可以修改的，在 redis.conf 中：

zset-max-ziplist-entries 128 
 zset-max-ziplist-value 64

思考：Zset 如何做到 O(1) 復(fù)雜度內(nèi)元素并且快速進行范圍操作？Zset 采用 skiplist 編碼時使用 zset 結(jié)構(gòu)作為底層實現(xiàn)，該數(shù)據(jù)結(jié)構(gòu)同時包含了一個跳躍表和一個字典。

其結(jié)構(gòu)如下：

typedef struct zset{ 
     zskiplist *zsl; 
    dict *dict; 
 }

Zset 中的 dict 字典為集合創(chuàng)建了一個從成員到分值之間的映射，字典中的鍵保存了成員，字典中的值保存了成員的分值，這樣定位元素時時間復(fù)雜度是 O(1)。

Zset 中的 zsl 跳躍表適合范圍操作，比如 ZRANK、ZRANGE 等，程序使用 zkiplist。

另外，雖然 Zset 中使用了 dict 和 skiplist 存儲數(shù)據(jù)，但這兩種數(shù)據(jù)結(jié)構(gòu)都會通過指針來共享相同的內(nèi)存，所以沒有必要擔(dān)心內(nèi)存的浪費。

過期數(shù)據(jù)的刪除對 Redis 性能影響

當我們對某些 key 設(shè)置了 expire 時，數(shù)據(jù)到了時間會自動刪除。如果一個鍵過期了，它會在什么時候刪除呢？

下面介紹三種刪除策略：

• 定時刪除：在這是鍵的過期時間的同時，創(chuàng)建一個定時器 Timer，讓定時器在鍵過期時間來臨時立即執(zhí)行對過期鍵的刪除。
• 惰性刪除：鍵過期后不管，每次讀取該鍵時，判斷該鍵是否過期，如果過期刪除該鍵返回空。
• 定期刪除：每隔一段時間對數(shù)據(jù)庫中的過期鍵進行一次檢查。

定時刪除：對內(nèi)存友好，對 CPU 不友好。如果過期刪除的鍵比較多的時候，刪除鍵這一行為會占用相當一部分 CPU 性能，會對 Redis 的吞吐量造成一定影響。

惰性刪除：對 CPU 友好，內(nèi)存不友好。如果很多鍵過期了，但在將來很長一段時間內(nèi)沒有很多客戶端訪問該鍵導(dǎo)致過期鍵不會被刪除，占用大量內(nèi)存空間。

定期刪除：是定時刪除和惰性刪除的一種折中。每隔一段時間執(zhí)行一次刪除過期鍵的操作，并且限制刪除操作執(zhí)行的時長和頻率。

具體的操作如下：

• Redis 會將每一個設(shè)置了 expire 的鍵存儲在一個獨立的字典中，以后會定時遍歷這個字典來刪除過期的 key。除了定時遍歷外，它還會使用惰性刪除策略來刪除過期的 key。
• Redis 默認每秒進行十次過期掃描，過期掃描不會掃描所有過期字典中的 key，而是采用了一種簡單的貪心策略。

從過期字典中隨機選擇 20 個 key；刪除這 20 個 key 中已過期的 key；如果過期 key 比例超過 1/4，那就重復(fù)步驟 1。

• 同時，為了保證在過期掃描期間不會出現(xiàn)過度循環(huán)，導(dǎo)致線程卡死，算法還增加了掃描時間上限，默認不會超過 25ms。

總結(jié)

總而言之，Redis 為了高性能，從各方各面都進行了優(yōu)化，下次小伙伴們面試的時候，面試官問 Redis 性能為什么如此高，可不能傻傻的只說單線程和內(nèi)存存儲了。