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

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

• 數據是存儲在內存中的。
• Redis 是單線程的。

當然，將數據存儲在內存中，讀取的時候不需要進行磁盤的 IO，單線程也保證了系統沒有線程的上下文切換。

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

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

• 純內存操作
• 單線程
• 高效的數據結構
• 合理的數據編碼
• 其他方面的優化

在 Redis 中，常用的 5 種數據結構和應用場景如下：

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

SDS

Redis 是用 C 語言開發完成的，但在 Redis 字符串中，并沒有使用  C 語言中的字符串，而是用一種稱為 SDS（Simple Dynamic String）的結構體來保存字符串。

struct sdshdr { 
       int len; 
     int free; 
     char buf[]; 
 }

SDS 的結構如上圖：

• len：用于記錄 buf 中已使用空間的長度。
• free：buf 中空閑空間的長度。
• buf[]：存儲實際內容。

例如：執行命令 set key value，key 和 value 都是一個 SDS 類型的結構存儲在內存中。

SDS 與 C 字符串的區別

①常數時間內獲得字符串長度

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

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

②避免緩沖區溢出

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

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

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

③減少字符串修改時帶來的內存重新分配的次數

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

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

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

分配規則如下：如果對 SDS 修改后，len 的長度小于 1M，那么程序將分配和 len 相同長度的未使用空間。

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

如果對 SDS 修改后 len 長度大于 1M，那么程序將分配 1M 的未使用空間。

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

④二進制安全

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

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

字典

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

Redis 本身就是 KV 服務器，除了 Redis 本身數據庫之外，字典也是哈希鍵的底層實現。

字典的數據結構如下所示：

typedef struct dict{ 
       dictType *type; 
     void *privdata; 
     dictht ht[2]; 
     int trehashidx; 
 }

typedef struct dictht{ 
     //哈希表數組 
     dectEntrt **table; 
     //哈希表大小 
     unsigned long size; 
     // 
     unsigned long sizemask; 
     //哈希表已有節點數量 
     unsigned long used; 
 }

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

Rehash

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

由上段代碼，我們可知 dict 中存儲了一個 dictht 的數組，長度為 2，表明這個數據結構中實際存儲著兩個哈希表 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] 創建一張新表，為下次 Rehash 做準備。

漸進式 Rehash

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

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

為了避免 Rehash 對服務器性能造成影響，Redis 采用了一種漸進式 Rehash 的策略，分多次、漸進的將 ht[0] 中的數據遷移到 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]。

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

跳躍表

Zset 是一個有序的鏈表結構，其底層的數據結構是跳躍表 skiplist，其結構如下：

typedef struct zskiplistNode { 
     //成員對象 
    robj *obj; 
     //分值 
    double score; 
     //后退指針 
    struct zskiplistNode *backward; 
     //層 
    struct zskiplistLevel { 
         struct zskiplistNode *forward;//前進指針 
         unsigned int span;//跨度 
    } level[]; 
  } zskiplistNode;

typedef struct zskiplist { 
     //表頭節點和表尾節點 
    struct zskiplistNode *header, *tail; 
     //表中節點的的數量 
    unsigned long length; 
     //表中層數***的節點層數 
    int level; 
  } zskiplist;

前進指針：用于從表頭向表尾方向遍歷。

后退指針：用于從表尾向表頭方向回退一個節點，和前進指針不同的是，前進指針可以一次性跳躍多個節點，后退指針每次只能后退到上一個節點。

跨度：表示當前節點和下一個節點的距離，跨度越大，兩個節點中間相隔的元素越多。

在查詢過程中跳躍著前進。由于存在后退指針，如果查詢時超出了范圍，通過后退指針回退到上一個節點后仍可以繼續向前遍歷。

壓縮列表

壓縮列表 ziplist 是為 Redis 節約內存而開發的，是列表鍵和字典鍵的底層實現之一。

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

ziplist 是由一系列特殊編碼的連續內存塊組成的順序型的數據結構，ziplist 中可以包含多個 entry 節點，每個節點可以存放整數或者字符串。

由于內存是連續分配的，所以遍歷速度很快。

編碼轉化

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

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

redisObject 的結構如下：

typedef struct redisObject{ 
     //類型 
    unsigned type:4; 
    //編碼 
    unsigned encoding:4; 
    //指向底層數據結構的指針 
    void *ptr; 
     //... 
  }robj;

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

當我們執行 type key 命令時返回的結果如下：

ptr 指針字段指向對象底層實現的數據結構，而這些數據結構是由 encoding 字段決定的，每種對象至少有兩種數據編碼：

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

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

上面介紹到，ziplist 是一種結構緊湊的數據結構，當某一鍵值中所包含的元素較少時，會優先存儲在 ziplist 中，當元素個數超過某一值后，才將 ziplist 轉化為標準存儲結構，而這一值是可配置的。

String 對象的編碼轉化

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

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

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

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

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

Set 類型的編碼轉化

Set 對象的編碼可以是 intset 或 hashtable，intset 編碼的結婚對象使用整數集合作為底層實現，把所有元素都保存在一個整數集合里面。

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 集合中保存了非整數類型的數據時，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 編碼：

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

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

set-max-intset-entries 512

Hash 對象的編碼轉化

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

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

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

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

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

Zset 對象的編碼轉化

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

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

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

• Zset 保存的元素個數小于 128。
• Zset 元素的成員長度都小于 64 字節。

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

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

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

其結構如下：

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

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

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

另外，雖然 Zset 中使用了 dict 和 skiplist 存儲數據，但這兩種數據結構都會通過指針來共享相同的內存，所以沒有必要擔心內存的浪費。

過期數據的刪除對 Redis 性能影響

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

下面介紹三種刪除策略：

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

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

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

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

具體的操作如下：

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

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

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

總結

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