萬字長文，38 圖爆肝 Redis 基礎！

Redis 在互聯網技術存儲方面的使用可以說是非常廣泛了，只要是接觸過 Java 開發的朋友就算你沒用過，都會聽過它。在面試也是非常高頻的一個知識點。

最近，我的的小弟小胖和老王就對 Redis 非常感興趣；我推薦它一本書《Redis 設計與實現》。誰知這貨說看不下去，非要我來總結一波。所以本文算是給小胖和老王的學習資料，也是我自己的學習筆記。希望對你有幫助。

還是老規矩，先上張腦圖。全文 13274 字，從下午 2 點爆肝到晚上 9 點，先上張思維導圖鎮樓：

官方是這麼描述的：

Redis （用 C 語言實現的）是一個開源的，基於內存的數據結構存儲，可用作於數據庫、緩存、消息中間件。

信息簡潔明瞭，一下就知道了三個點：基於內存、用作緩存、多種數據結構。

的了，那就從這三個方面開始研究唄。

1.0 爲什麼要用 Redis 做緩存？

上面說了，用作緩存。有些小夥伴可能會問：有 MySQL 數據庫就得了唄？幹嘛還要緩存？而且爲啥要用 Redis 做？Map 不行嘛？

• 第一、二個問題，都知道 MySQL 數據是存在磁盤的，而 CPU 訪問磁盤是非常慢的。如果遇到併發高的時候，所有線程每次都要訪問磁盤，估計得掛。

到底有多慢？請看鏈接：zhuanlan.zhihu.com/p/24726196

Redis 和 Map 做下對比，就知道爲啥不合適了。

• Map 是本地緩存，如果在多臺機器部署，必須每個機器都要複製一份，否則造成緩存不一致；Redis 是分佈式緩存，部署在多臺機器，也是用的同一份緩存，保持了一致性，問題不大。

• Map 做緩存，數據量大的話會導致 JVM 內存飆升，進而拖垮程序，並且 JVM 掛了，還會導致數據丟失；Redis 可以用更大容量的內存（看你的配置，即幾十 G 都沒問題）做緩存，並且還可以持久化到磁盤。

你可能第一反應不就 "String（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Sorted Set（有序集合）麼？"，太簡單了，我都會。

老鐵你錯了，你說的是 Redis 的數據類型只有 5 種，也就是他的表現形式。而我說的數據結構是底層的，有 6 種，分別是簡單動態字符串、雙向鏈表、壓縮列表、哈希表、跳錶和整數數組，它們的對應關係如下：

對應關係

由上圖可知 String 類型的底層實現只有一種數據結構，而 List、Hash、Set 和 Sorted Set 這四種數據類型，都有兩種底層實現結構都是集合。

看到這裏，你可能又有疑問了。這些數據結構都是值的底層實現，鍵和值本身之間用什麼結構組織？

2.0 鍵和值用什麼結構組織？

實際上，Redis 使用了一個哈希表來保存所有鍵值對。它的存儲是以 key-value 的形式的。key 一定是字符串，value 可以是 string、list、hash、set、sortset 中的隨便一種。

一個哈希表，其實就是一個數組，數組的每個元素稱爲一個哈希桶。每個哈希桶中保存了鍵值對數據，哈希桶中的元素保存的並不是值本身，而是指向具體值的指針。這點從下圖可以看出：

哈希表

** 哈希桶中的 entry 元素中保存了 *key 和 value 指針，分別指向了實際的鍵和值，這樣一來，即使值是一個集合，也可以通過 value 指針被查找到。

redis 的鍵值都是 redisObject 對象，即在創建時會生成一個用於鍵名的 redisObject 對象和一個用於鍵值的 redisObject 對象。這點從源碼也可以看出來：

typedef struct redisObject {
    // 類型
    unsigned type:4;

        // 編碼
    unsigned encoding:4;

        // 指向數據的指針
    void *ptr;

    // 記錄對象最後一次被程序訪問時間，用於計算空轉時長(當前時間-lru)
    unsigned lru:22; /* lru time (relative to server.lruclock) */

        // 引用計數，用於內存回收
    int refcount;
} robj;

也就是說上圖 entry 中的健值指針就分別指向這樣一個 redisObject。其中 type、 encoding 和 ptr 是最重要的三個屬性。type 記錄了對象所保存的值的類型，它的值可能是以下常量的其中一個。

/*
 * 對象類型
 */
#define REDIS_STRING 0  // 字符串
#define REDIS_LIST 1    // 列表
#define REDIS_SET 2     // 集合
#define REDIS_ZSET 3    // 有序集
#define REDIS_HASH 4    // 哈希表

encoding 記錄了 對象所保存的值的編碼，它的值可能是以下常量的其中一個.

/*
 * 對象編碼
 */
#define REDIS_ENCODING_RAW 0            // 編碼爲字符串
#define REDIS_ENCODING_INT 1            // 編碼爲整數
#define REDIS_ENCODING_HT 2             // 編碼爲哈希表
#define REDIS_ENCODING_ZIPMAP 3         // 編碼爲 zipmap
#define REDIS_ENCODING_LINKEDLIST 4     // 編碼爲雙端鏈表
#define REDIS_ENCODING_ZIPLIST 5        // 編碼爲壓縮列表
#define REDIS_ENCODING_INTSET 6         // 編碼爲整數集合
#define REDIS_ENCODING_SKIPLIST 7       // 編碼爲跳躍表

比如，我們在 redis 裏面 put ("狗哥",666)，在 redisObject 實際上是這樣存放的：

redisObject

2.1 SDS 簡單動態字符串

簡單動態字符串 (Simple dynamic string,SDS)

跟傳統的 C 語言字符串不一樣，Redis 使用了 SDS 來構建自己的字符串對象，源碼如下：

struct sdshdr{

    // 字節數組，用於保存字符串
    char buf[];

    // 記錄buf數組中已使用的字節數量，也是字符串的長度
    int len;

    // 記錄buf數組未使用的字節數量
    int free;
}

圖示：

SDS 例子

buf 屬性是一個 char 類型的數組，最後一個字節保存了空字符 '\0'，不算入 len 長度。

2.1.0 爲什麼使用 SDS？

SDS 比 C 字符串好在哪？

• 常數複雜度獲取字符串長度：C 字符串不記錄長度，統計長度只能逐個遍歷字符，複雜度是 O (N)；而 SDS 在 len 屬性中記錄了自身長度，複雜度僅爲 O (1)。

• 不會發生緩衝區溢出：SDS 不會發生溢出的問題，如果修改 SDS 時，空間不足。先會擴展空間，再修改！(內部實現了動態擴展機制)。

• SDS 可以減少內存分配的次數 (空間預分配 & 惰性空間釋放)。在擴展空間時，除了分配修改時所必要的空間，還會分配額外的空閒空間 (free 屬性)。

• SDS 是二進制安全的，所有 SDS API 都會以處理二進制的方式來處理 SDS 存放在 buf 數組裏的數據。

2.2 鏈表

鏈表，大家都很熟悉了吧？在 Java 中 LinkedList 的底層數據結構就是鏈表 + 數組實現的。那 Redis 中的鏈表是怎樣的呢？

按照慣例，上源碼。它使用 listNode 結構（源碼位於 adlist.h）表示鏈表的每個節點：

typedef strcut listNode{
    //前置節點
    strcut listNode  *pre;

    //後置節點
    strcut listNode  *pre;

    //節點的值
    void  *value;
}listNode

多個 listNode 可以通過 prev 和 next 指針組成一個雙向鏈表，像這樣：

雙向鏈表

節點表示出來了，整個鏈表又該怎麼表示呢？Redis 使用 list 結構（源碼位於 adlist.h）來構建鏈表，上源碼：

typedef struct list{

    //表頭結點
    listNode  *head;

    //表尾節點
    listNode  *tail;

    //鏈表長度
    unsigned long len;

    //節點值複製函數
    void *(*dup) (viod *ptr);

    //節點值釋放函數
    void  (*free) (viod *ptr);

    //節點值對比函數
    int (*match) (void *ptr,void *key);

}list

鏈表

2.2.0 Redis 鏈表的特性

• 雙端：有 prev 和 next 兩個指針；可以前後移動。

• 無環：鏈表不閉環，prev 和 next 都指向 null，鏈表訪問以 null 爲終點。

• 獲取帶表頭指針、表尾指針、節點數量的時間複雜度均爲 O (1)。

• 鏈表使用 void * 指針來保存節點值，可以保存各種不同類型的值。

2.3 哈希表

哈希表，大家也都不陌生吧？在 Java 中哈希表的底層數據結構就是數組 + 鏈表實現的。那 Redis 中的哈希表是怎樣實現的呢？

按照慣例，上源碼。哈希表使用 dictht 結構（源碼位於 dict.h）表示哈希表，源碼如下：

typedef struct dictht{
 // 哈希表數組
 dictEntry **table;  

 // 哈希表大小，也即 table 大小
 unsigned long size;    

 // 哈希表大小掩碼，用於計算索引值
 // 總是等於size-1
 unsigned long sizemark;     

    // 哈希表已有節點數量
 unsigned long used;
}dictht

sizemark 和哈希值決定一個鍵應該被放到 table 數組的那個索引上。PS：就是 Java 中計算哈希值決定位置的方法。

圖示一個大小爲 4 的空哈希表（不包含任何鍵值）

空的哈希表

哈希表節點使用 dictEntry 結構表示，每個 dictEntry 都保存着一個鍵值對。源碼如下：

 typedef struct dictEntry {
 // 鍵
 void *key;

 // 值
 union {
  void *val;
  uint64_tu64;
  int64_ts64;
 }v; 

 // 指向下個哈希節點，組成鏈表
 struct dictEntry *next;
}dictEntry;

key 解釋得很清楚了；說說 v 屬性，它 保存着鍵值對中的值，可以是一個指針，或者是一個 uint64_t 整數，又或者是一個 int64_t 整數。

**next 則是執行下一個哈希表節點的指針，可以將多個哈希值相同的鍵值對連接在一起作爲一個鏈表，以此來解決鍵衝突（collision）的問題。**PS：參考 Java 中 HashMap 是怎麼解決衝突的。舊文：《HashMap 源碼解讀》有提過。

圖示通過 next 指針把相同索引值的鍵 k1 和 k0 連接在一起。

next 指針串聯鍵

爲了更好實現 rehash（擴容）；Redis 又在哈希表之上封裝了一層，稱之爲字典。由 dict 結構表示，源碼如下：

typedef struct dict {
    // 類型特定函數
    dictType *type;
    // 私有數據
    void * privdata; 
    // 哈希表，代表兩個哈希表
    dictht ht[2];
    // rehash索引
    // 當rehash不在進行時， 值爲 - 1 
    in trehashidx; /*rehashing not in pro gress if rehashidx==-1*/
}dict;

-------------------------------------------------------

typedef struct dictType{
    //計算哈希值的函數
    unsigned int (*hashFunction)(const void * key);

    // 複製鍵的函數
    void *(*keyDup)(void *private, const void *key);

    // 複製值的函數
    void *(*valDup)(void *private, const void *obj);  

    // 對比鍵的函數
    int (*keyCompare)(void *privdata , const void *key1, const void *key2)

    // 銷燬鍵的函數
    void (*keyDestructor)(void *private, void *key);

    // 銷燬值的函數
    void (*valDestructor)(void *private, void *obj);  
}dictType

type 屬性和 privdata 屬性是針對不同類型的鍵值對，爲創建多態字典而設置的。

• type 是一個指向 dictType 的指針，每個 dictType 保存了一簇用於操作特定類型鍵值對的函數，Redis 爲用途不同的字典設置不同的類型特定函數

• 而 privdata 則保存了傳給類型特定函數的可選參數

• ht 是包含了兩個哈希表的數組；ht [0] 存放真實數據，ht [1] 在對 ht [0] 進行 rehash（擴容）時使用。

最終，你會發現其實所謂的字典就是兩個哈希表組成的。圖式結構如下：

哈希表

2.3.0 哈希衝突

當往哈希表寫入大量數據時，不可避免的就出現多個 key 計算出來的哈希值相同。也就是多個不同的 key 需要放到同一個哈希桶，這就是所謂的哈希衝突。

而 Redis 解決哈希衝突的手段很 Java 一樣，都是鏈式哈希：同一個哈希桶中的多個元素用一個鏈表來保存，它們之間依次用指針連接。

解決哈希衝突

如圖，假設 entry1、entry2、entry3 的哈希值都是 3 ；那麼他們將存放在下標爲 3 的哈希桶裏面，並轉換成鏈表。

PS：沒懂哈希衝突的看舊文。舊文：《HashMap 源碼解讀》有詳細例子解析。

當不斷髮生哈希衝突，鏈表越來越長，影響查詢性能時，Redis 就需要 rehash。

2.3.1 rehash（擴容）

Redis 開始執行 rehash，這個過程分爲三步：

• 1、給哈希表 2 分配更大的空間，例如是當前哈希表 1 大小的兩倍；

• 2、把哈希表 1 中的數據重新映射並拷貝到哈希表 2 中；

• 3、釋放哈希表 1 的空間。

如此，就可以從哈希表 1 切換到哈希表 2，用增大的哈希表 2 保存更多數據，而原來的哈希表 1 留作下一次 rehash 擴容備用。

你肯定以爲這樣就完美了？但還有坑，當哈希表 1 數據量很大，如果一次性複製就會造成線程阻塞，無法服務其他請求。Redis 不允許這種事發生，因此使用了漸進式 rehash。

PS：沒懂 rehash 的看舊文。舊文：《HashMap 源碼解讀》有詳細例子解析。

2.3.2 漸進式 rehash

啥是漸進式 rehash ？

在第二步拷貝數據時，Redis 仍然正常處理客戶端請求，** 每處理一個請求，順帶從哈希表 1 中的第一個索引位置開始，把這個位置上所有的 entry 複製到哈希表 2 中，下個請求就複製位置 2 **；直至全部複製完成。

過程如下圖所示：

漸進式 rehash

具體到代碼，它的過程是這樣的：

• 1、在字典中維持一個索引計數器變量 rehashidx，並將設置爲 0，表示 rehash 開始。

• 2、在 rehash 期間，客戶端每次對字典進行 CRUD 操作時，會將 ht [0] 中 rehashidx 索引上的值 rehash 到 ht [1]，操作完成後 rehashidx+1。

• 3、字典操作不斷執行，最終在某個時間點，所有的鍵值對完成 rehash，這時將 rehashidx 設置爲 - 1，表示 rehash 完成

說到這，你可能還有以下幾點疑問？

只有在操作字典的時候才進行復制數據嗎？如果客戶端只操作一次字段是不是就完不成 rehash 了？

漸進式 rehash 執行時，除了根據針對字典的 CRUD 操作來進行數據遷移，Redis 本身還會有一個定時任務在執行 rehash，如果沒有針對字典的請求時，這個定時任務會週期性地（例如每 100ms 一次）搬移一些數據到新的哈希表。

漸進式 rehash，CRUD 究竟在哪個哈希表操作呢？

在漸進式 rehash 過程中，字典會同時使用兩個哈希表 ht [0] 和 ht [1]，所有的 CRUD 操作也會在兩個哈希表進行。

比如要查找一個鍵時，服務器會優先查找 ht [0]，如果不存在，再查找 ht [1]。當執行新增操作時，新的鍵值對一律保存到 ht [1]，不再對 ht [0] 進行任何操作，以保證 ht [0] 的鍵值對數量只減不增，最後變爲空表。

2.4 跳躍表

跳躍表在 Java 中很少接觸到，大家對這個知識點也是挺陌生的。之前在學習數據結構是看到過小灰的一篇文章，寫得通俗易懂，大家可以看下，建議看完再往下看。

https://mp.weixin.qq.com/s/COBdoHWDhlw4rmG_fGFhSA

跳躍表 (shiplist) 是實現 sortset (有序集合) 的底層數據結構之一；除此以外，在集羣節點中也有用到它。

Redis 的跳躍表由 zskiplistNode 和  zskiplist 兩個結構定義，源碼位於 redis.h 文件中。其中前者是跳躍表的結構；後者的作用是保存跳躍表的節點數量與頭、尾節點的指針等信息。

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

如下圖所示，展示了不同層高的跳躍表節點

不同層高的節點

typeof struct zskiplist {
    // 表頭節點，表尾節點
    struct skiplistNode *header,*tail;
    // 表中節點數量
    unsigned long length;
    // 表中最大層數
    int level;
} zskiplist;

下圖展示了一個跳躍表示例：

多個節點組成跳躍表

圖片最左邊的是 zskiplist 結構，包含：

• header：指向跳躍表的表頭節點。

• tail：指向跳躍表的表尾節點。

• level：記錄目前跳躍表內，層數最大的那個節點的層數（表頭節點的層數不計算在內）。

• length：記錄跳躍表的長度，也即是，跳躍表目前包含節點的數量（表頭節點不計算在內）。

zskiplist 結構右方的是四個 zskiplistNode 結構， 包含：

• 層：比如節點中的 L1、L2、L3 等，包括前進指針和跨度

• 前進指針：用於訪問位於表尾方向的其他節點

• 跨度：記錄了前進指針所指向節點和當前節點的距離

• 後退指針：指向當前節點的前一個節點，從表尾向表頭遍歷

• 分值：節點按各自分值從小到大排列

• 成員對象：節點所保存的成員對象

PS：跳躍表這塊的內容比較多，比較難說清楚實現細節。具體的看上面的鏈接，以及《Redis 設計與實現》這本書（說得很好，微信讀書網頁版就有）

2.5 整數集合

整數集合是 Set（集合）的底層數據結構之一。當 Set 只包含整數值元素，並且這個 Set 的元素數量不多時，Redis 就會使用整數集合作爲 Set 的底層實現。

Redis 使用了 intset 用於保存整數值集合，它保證了有序以及不重複。源碼如下：

typeof struct intset {
    // 編碼方式
    unit32_t encoding;
    // 集合包含的元素數量
    unit32_t lenght;
    // 保存元素的數組
    int8_t contents[];
} intset;

一個保存了 5 個整數的集合如下所示：

整數集合

length 就不說了，主要說下 contents 和 encoding 的關係；contents 的真正類型取決於 encoding 的值：

• INTSET_ENC_INT16

• INTSET_ENC_INT32

• INTSET_ENC_INT64

這三個值分別對應 16、32、64 編碼對應能存放的數字範圍是不一樣的。16 最小（-32768~32767），32 在中間（-2147483648~2147483647）64 最大（-9223372036854775808~9223372036854775807）。

如下圖所示爲 INTSET_ENC_INT16 類型集合存放 5 位整數佔用的空間：16 * 5

上圖集合佔用位數

2.5.0 升級操作

如果 contents 本來保存 1、3、5 三個整數值，後面加一個 2147483647456。

那麼只有 2147483647456 是真正需要 int64_t 類型來保存的，而其他的 1、3、5 都可以用 int16_t 類型來保存；這時是整體升級，所有元素都會被升級爲 int64_t 類型。

也就是說本來是 int16_t 類型的集合，要放入大於本身的整數。就需要升級，步驟如下：

• 1、根據新元素類型拓展整數集合底層數組的空間併爲新元素分配空間。

• 2、將底層數組現有的所有元素都轉換成與新元素相同的類型，並將類型轉換後的元素放到正確的位上，需要維持底層數組的有序性質不變。

• 3、將新元素添加到底層數組。

舉個栗子：

1、原來是數組是 INTSET_ENC_INT16 類型 3 位，佔用 48 位空間；

原始數據

2、插入整數 65535，超出 INTSET_ENC_INT16 範圍；升級爲 INTSET_ENC_INT32 。需要的空間也從 48 加到 128 位。如下所示：新分配空間 = 128 - 48 = 80

新分配空間

3、元素 3 排名第三，移動到 contents 索引 2 位置；其他類似，元素 2 移動到索引 1 位置；元素 1 移動到索引 0 位置

移動元素 3

4、最後添加新元素 65535 即可完成升級。

注意點：整數集合只支持升級、不支持降級。

2.6 壓縮列表

壓縮列表是 list 和 hash 的底層實現之一，當 list 只包含少量元素，並且每個元素都是小整數值，或者是比較短的字符串，壓縮列表會作爲 list 的底層實現。

壓縮列表（ziplist）是 Redis 爲節約內存而開發，它的理念是多大元素用多大內存。

如下圖，根據每個節點的實際存儲的內容決定內存的大小，第一個節點佔用 5 字節，第二個節點佔用 5 字節，第三個節點佔用 1 字節，第四個節點佔用 4 字節，第五個節點佔用 3 字節。

多大元素用多大內存

圖示爲 ziplist 的結構：它類似於一個數組，不同的是它在表頭有三個字段 zlbytes、zltail 和 zllen；分別表示列表長度、列表尾的偏移量和元素的個數；表尾有 zlend，列表結束的標識。

壓縮列表

2.6.0 節點構成

圖示一個壓縮列表中一個節點的構成：

節點構成

• previous_entry_length：記錄前一個節點的長度

• encoding：編碼，控制 content 的類型和長度；分爲字節數組編碼和整數編碼

• content：保存節點值，可以是一個字節數組或整數

2.6.1 壓縮列表的查找

壓縮列表

如果查找的是第一個元素或最後一個元素，可通過表頭三個字段的長度直接定位，複雜度是 O (1)。而查找其他元素時，只能逐個查找，複雜度是 O (N) 。

倒序遍歷：首先指針通過 zltail 偏移量指向表尾節點，然後通過指向節點記錄的前一個節點的長度依次向前遍歷訪問整個壓縮列表。

還記得文章開頭那張數據類型與底層數據結構的對應關係圖嗎？長這樣：

對應關係

Redis 這種對應關係實際上是由 redisObject 的 type（類型）和 encoding （編碼）共同決定的，詳細對應關係如下：

不同類型和編碼的對象

下面來具體介紹下，什麼條件下使用那種類型實現對應的對象。比如：String 什麼情況下用 int 編碼實現？什麼情況下用 embstr 編碼實現？什麼情況下用 raw 編碼實現呢？

3.0 字符串（String）對象

從上圖得知，String 有 int、raw、embst 三種編碼格式：

• int：整數值，可以用 long 類型表示，使用整數值保存對象

• raw：字符串值且長度 > 32 字節，使用 SDS 保存對象

• embstr：字符串值且長度 < 32 字節，使用 embstr 編碼的 SDS 保存對象

PS：對於浮點數（long double 類型表示的），Redis 會將浮點數轉換成字符串值；最終視長度決定用那種編碼（embstr 或 raw）保存。取出時，再將其轉成浮點值。

總結

3.0.0 embstr 和 raw 有啥區別？

• raw 分配內存和釋放內存的次數是兩次，embstr 是一次

• embstr 編碼的數據保存在一塊連續的內存裏面

3.0.1 編碼的轉換

• int 類型的字符串，當保存的不再是整數值，將轉換成 raw 類型

• embstr 類型的字符串是只讀的，修改時會轉換成 raw 類型。原因：Redis 沒有爲 embstr 提供修改程序，所以它是隻讀的；要修改只能先轉成 raw。

3.1 列表（list）對象

還是從上圖得知，列表的編碼可以是 ziplist 或 linkedlist：

• ziplist：所有元素長度都小於 64 字節且元素數量少於 512 個

• 以上兩個條件的上限值可以通過配置文件的 list-max-ziplist-value 和 list-max-ziplist-entries 修改

• linkedlist：不滿足上述條件時，將從 ziplist 轉換成 linkedlist

3.1.0 區別

執行 RPUSH 命令將創建一個列表對象，比如：

redis> RPUSH numbers 1 "three" 5
(integer) 3

如果 numbers 使用 ziplist 編碼，對象結構如下：

ziplist

否則使用 linkedlist，就是雙端鏈表作爲底層實現。結構如下：

linkedlist

3.2 哈希（hash）對象

又是從上圖得知，哈希的編碼可以是 ziplist 或 hashtable：

• ziplist：哈希對象保存的所有鍵值對的鍵和值的字符串長度都小於 64 字節且鍵值對數量小於 512

• 以上兩個條件的上限值可以通過配置文件的 hash-max-ziplist-value 和 hash-max-ziplist-entries 修改

• hashtable：不能滿足上述條件，將從 ziplist 轉成 hashtable

3.2.0 區別

執行 HSET 命令，可以創建一個 hash 對象並保存數據：

redis> HSET profile name "Tom"
(integer) 1
redis> HSET profile age 25
(integer) 1
redis> HSET profile career "Programmer"
(integer) 1

ziplist 保存的 hash 對象：

ziplist 編碼的哈希對象

ziplist 底層實現

hashtable 保存的 hash 對象：

• 字典中每個鍵都是一個字符串對像，對象中保存鍵值對的鍵

• 字典中每個值都是一個字符串對像，對象中保存鍵值對的值

架構如下：

hashtable 編碼的哈希對象

3.3 集合（set）對象

又又是從上圖得知，哈希的編碼可以是 intset 或 hashtable：

• intset：集合對象保存的所有元素都是整數值且元素數量小於 512 個

• 以上兩個條件的上限值可以通過配置文件的 set-max-intset-entries 修改

• hashtable：不能滿足上述條件，將從 intset 轉成 hashtable

3.3.0 區別

使用 SADD 命令可構建一個 intset 編碼的 set 對象並保存數據：

redis> SADD numbers 1 3 5
(integer) 3

intset 編碼的集合對象結構如下：

intset 編碼的集合對象

使用 SADD 命令可構建一個 hashtable 編碼的 set 對象並保存數據：

redis> SADD fruits "apple" "banana" "cherry"
(integer) 3

hashtable 編碼的 set 使用字典作爲底層實現，每個鍵都是字符串對象，每個對象包含一個集合元素，字典值全部置爲 null 。

hashtable 編碼的集合對象結構如下：

hashtable 編碼的集合對象

3.4 有序集合（Sorted Set）對象

又又又是從上圖得知，有序集合的編碼可以是 ziplist 或 skiplist：

• ziplist：保存的元素數量小於 128 個且所有元素長度都小於 64 字節

• 以上兩個條件的上限值可以通過配置文件的 zset-max-ziplist-entries 和 zset-max-ziplist-value 修改

• skiplist：不能同時滿足上述條件，將從 ziplist 轉成 skiplist

3.4.0 區別

使用 ZADD 命令可以構建一個 Sorted Set 對象並保存數據：

redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3

ziplist 編碼的 zset 對象

ziplist 編碼實現的 Sorted Set 對象，每個集合元素使用兩個相鄰的節點保存，第一個節點是元素成員，第二個節點是元素分值。按分值從小到大進行排序，結構如下：

壓縮列表的具體實現

skiplist 編碼實現的 Sorted Set 使用 zset 作爲底層實現，它包含 跳躍表和字典，源碼如下：

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

大體結構如下：

skiplist 編碼的有序集合對象

• 跳躍表 zsl 按分值從小到大保存所有集合元素；每個節點保存一個集合元素；object 屬性保存元素成員、score 屬性保存元素分值。目的：實現快速的範圍查詢操作。

• 字典 dict 創建一個從成員到分值的 key-value；字典中每個鍵值對都保存一個集合元素；鍵保存元素成員、值保存元素分值。目的：用 O (1) 複雜度 get 元素分值。

最後，詳細的結構如下所示：

有序集合元素同時被保存在字典和跳躍表中

聽到這裏有人可能有疑問：zset 結構同時使用跳躍表和字典來保存有序集合元素，不會重複嗎？

不會，因爲二者會通過指針來共享同一個元素，並不會產生重複。

爲什麼 skiplist 編碼實現的有序集合要同時用跳躍表和字典實現？隨便用一個行嗎？

答案是：不好。我們來看看兩種情況：

• 只用 dict ，可以保留以 O (1) 複雜度 get 成員分值；但字典是無序的，所以每次進行範圍操作都要對所有元素排序；顯然這是性能更低的。

• 只用跳躍表，快速範圍操作得以保留；但是沒了字典，get 成員分值的複雜度將提高至 O (logN)，這也影響性能。

所以，Redis 爲了把兩者有點結合起來，採用了通過指針共享的方式，使用兩種數據結構實現。

4.0 Redis 如何執行命令

Redis 執行命令前，會先檢查值對象類型，判斷鍵是否能執行該命令；再檢查值對象的編碼方式選擇合適的命令執行。

舉個例子：列表對象有 ziplist 和 linkedlist 兩種編碼格式可用；前者通過 ziplist 的 API 執行命令、後者通過 linkedlist 的 API 執行命令。

如果我們執行 LLEN 命令，Redis 第一步判斷執行的命令是不是針對列表的？是的話，第二步判斷值的編碼格式，如果是 ziplist，使用 ziplistLen 函數操作；如果是 linkedlist 則使用 listLength 函數操作。

4.1 Redis 內存回收機制與共享對象

Redis 爲每個對象構建一個引用計數屬性，通過它可實現內存回收機制（當一個對象的引用計數爲 0 時，將會釋放所佔用內存）。

Redis 會共享值爲 0 到 9999 的字符串對象（這個值可能通過修改 redis.h 文件的 REDIS_SHARDED_INTEGER 常量修改）

Redis 只共享字符串對象本身，爲什麼不共享包含字符串的對象？

能共享的前提是目標對象和共享對象完全相同。要共享就需要驗證兩者是否相同？因爲包含字符串的對象複雜度更高，驗證消耗的 CPU 時間也更多，而性能將會下降。

4.2 lru 屬性的作用

redisObject 的 lru 屬性記錄對象最後一次被訪問的時間，這個時間可以用於計算對象的空轉時間（公式：當前時間 - lru 時間）。

• 《Redis 設計與實現》

• redis 源碼：github.com/antirez/redis

• redis 源碼中文註釋版：github.com/huangz1990/redis-3.0-annotated

• cnblogs.com/Java3y/p/9870829.html

• time.geekbang.org/column/article/268253

• http://www.fidding.me/article/108

• segmentfault.com/a/1190000019980165

• cnblogs.com/chenchen0618/p/13260202.html

本文從常用的緩存技術講起，深入 Redis 的數據類型與底層數據結構。第一小節從 Redis 和緩存聊起；第二節站在源碼角度跟你分析 Redis 的 6 種數據結構：SDS、鏈表、哈希表、跳躍表、整數集合以及壓縮列表的特性；第三節着重和你分享 5 種數據類型和 6 中底層結構的對應關係；第四節則是畫龍點睛地和你分享了 Redis 是怎麼執行命令的？怎麼釋放內存等問題。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/8w9Of_q5IIgzeScAeYcPSQ