搞定 Redis 數據存儲原理，別只會Set、Get 了

作者：就是碼哥呀 2022-12-22 08:57:29

數據庫 Redis

一開始的時候，我只使用Ht_table[0] 這個散列表讀寫數據，Ht_table[1] 指向 NULL，當這個散列表容量不足，觸發擴容操作，這時候就會創建一個更大的散列表 Ht_table[1]。

在上一篇通過源碼編譯構建出可調式環境之后，想必你想更深入了解我的整體架構。當你熟悉我的整體架構和每個模塊，遇到問題才能直擊本源，直搗黃龍，一笑破蒼穹。

我的核心模塊如圖 1-10。

Client 客戶端，官方提供了 C 語言開發的客戶端，可以發送命令，性能分析和測試等。
網絡層事件驅動模型，基于 I/O 多路復用，封裝了一個短小精悍的高性能 ae 庫，全稱是a simple event-driven programming library。

在 ae 這個庫里面，我通過aeApiState 結構體對 epoll、select、kqueue、evport四種 I/O 多路復用的實現進行適配，讓上層調用方感知不到在不同操作系統實現 I/O 多路復用的差異。
Redis 中的事件可以分兩大類：一類是網絡連接、讀、寫事件；另一類是時間事件，也就是特定時間觸發的事件，比如定時執行 rehash 操作。

命令解析和執行層，負責執行客戶端的各種命令，比如SET、DEL、GET等。
內存分配和回收，為數據分配內存，提供不同的數據結構保存數據。
持久化層，提供了 RDB 內存快照文件和 AOF 兩種持久化策略，實現數據可靠性。
高可用模塊，提供了副本、哨兵、集群實現高可用。
監控與統計，提供了一些監控工具和性能分析工具，比如監控內存使用、基準測試、內存碎片、bigkey 統計、慢指令查詢等。

掌握了整體架構和模塊后，接下來進入 src 源碼目錄，使用如下指令執行 redis-server可執行程序啟動 Redis。

./redis-server ../redis.conf

每個被啟動的服務我都會抽象成一個 redisServer，源碼定在server.h 的redisServer 結構體。

這個結構體包含了存儲鍵值對的數據庫實例、redis.conf 文件路徑、命令列表、加載的 Modules、網絡監聽、客戶端列表、RDB AOF 加載信息、配置信息、RDB 持久化、主從復制、客戶端緩存、數據結構壓縮、pub/sub、Cluster、哨兵等一些列 Redis 實例運行的必要信息。

結構體字段很多，不再一一列舉，部分核心字段如下。

truct redisServer {
    pid_t pid;  /* 主進程 pid. */
    pthread_t main_thread_id; /* 主線程 id */
    char *configfile;  /*redis.conf 文件絕對路徑*/
    redisDb *db; /* 存儲鍵值對數據的 redisDb 實例 */
   int dbnum;  /* DB 個數 */
    dict *commands; /* 當前實例能處理的命令表，key 是命令名，value 是執行命令的入口 */
    aeEventLoop *el;/* 事件循環處理 */
    int sentinel_mode;  /* true 則表示作為哨兵實例啟動 */

   /* 網絡相關 */
    int port;/* TCP 監聽端口 */
    list *clients; /* 連接當前實例的客戶端列表 */
    list *clients_to_close; /* 待關閉的客戶端列表 */

    client *current_client; /* 當前執行命令的客戶端*/
};

數據存儲原理

其中redisDb *db指針非常重要，它指向了一個長度為 dbnum（默認 16）的 redisDb 數組，它是整個存儲的核心，我就是用這玩意來存儲鍵值對。

redisDb

redisDb 結構體定義如下。

typedef struct redisDb {
    dict *dict; 
    dict *expires; 
    dict *blocking_keys;
    dict *ready_keys;
    dict *watched_keys; 
    int id;          
    long long avg_ttl; 
    unsigned long expires_cursor;
    list *defrag_later; 
    clusterSlotToKeyMapping *slots_to_keys;
} redisDb;

dict 和 expires

dict 和 expires 是最重要的兩個屬性，底層數據結構是字典，分別用于存儲鍵值對數據和 key 的過期時間。
expires，底層數據結構是 dict 字典，存儲每個 key 的過期時間。

?
MySQL：“為什么分開存儲？”

好問題，之所以分開存儲，是因為過期時間并不是每個 key 都會設置，它不是鍵值對的固有屬性，分開后雖然需要兩次查找，但是能節省內存開銷。

blocking_keys 和 ready_keys

底層數據結構是 dict 字典，主要是用于實現 BLPOP 等阻塞命令。

當客戶端使用 BLPOP 命令阻塞等待取出列表元素的時候，我會把 key 寫到 blocking_keys 中，value 是被阻塞的客戶端。

當下一次收到 PUSH 命令執時，我會先檢查 blocking_keys 中是否存在阻塞等待的 key，如果存在就把 key 放到 ready_keys 中，在下一次 Redis 事件處理過程中，會遍歷 ready_keys 數據，并從 blocking_keys 中取出阻塞的客戶端響應。

watched_keys

用于實現 watch 命令，存儲 watch 命令的 key。

id

Redis 數據庫的唯一 ID，一個 Redis 服務支持多個數據庫，默認 16 個。

avg_ttl

用于統計平均過期時間。

expires_cursor

統計過期事件循環執行的次數。

defrag_later

保存逐一進行碎片整理的 key 列表。

slots_to_keys

僅用于 Cluster 模式，當使用 Cluster 模式的時候，只能有一個數據庫 db 0。slots_to_keys 用于記錄 cluster 模式下，存儲 key 與哈希槽映射關系的數組。

dict

Redis 使用 dict 結構來保存所有的鍵值對（key-value）數據，這是一個散列表，所以 key 查詢時間復雜度是 O(1) 。

所謂散列表，我們可以類比 Java 中的 HashMap，其實就是一個數組，數組的每個元素叫做哈希桶。

dict 結構體源碼在 dict.h 中定義。

struct dict {
    dictType *type;

    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx;

    int16_t pauserehash;
    signed char ht_size_exp[2];
};

dict 的結構體里，有 dictType *type，**ht_table[2]，long rehashidx 三個很重要的結構。

type 存儲了 hash 函數，key 和 value 的復制等函數；
ht_table[2]，長度為 2 的數組，默認使用 ht_table[0] 存儲鍵值對數據。我會使用 ht_table[1] 來配合實現漸進式 reahsh 操作。
rehashidx 是一個整數值，用于標記是否正在執行 rehash 操作，-1 表示沒有進行 rehash。如果正在執行 rehash，那么其值表示當前 rehash 操作執行的 ht_table[1] 中的 dictEntry 數組的索引。
pauserehash 表示 rehash 的狀態，大于 0 時表示 rehash 暫停了，小于 0 表示出錯了。
ht_used[2]，長度為 2 的數組，表示每個哈希桶存儲了多少個鍵值對實體（dictEntry），值越大，哈希沖突的概率越高。
ht_size_exp[2]，每個散列表的大小，也就是哈希桶個數。

重點關注 ht_table 數組，數組每個位置叫做哈希桶，就是這玩意保存了所有鍵值對，每個哈希桶的類型是 dictEntry。

?
MySQL：“Redis 支持那么多的數據類型，哈希桶咋保存？”

他的玄機就在 dictEntry 中，每個 dict 有兩個 ht_table，用于存儲鍵值對數據和實現漸進式 rehash。

dictEntry 結構如下。

typedef struct dictEntry {
    void *key;
    union {
       // 指向實際 value 的指針
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 散列表沖突生成的鏈表
    struct dictEntry *next;
    void *metadata[];
} dictEntry;

*key 指向鍵值對的鍵的指針，指向一個 sds 對象，key 都是 string 類型。
v 是鍵值對的 value 值，是個 union（聯合體），當它的值是 uint64_t、int64_t 或 double 數字類型時，就不再需要額外的存儲，這有利于減少內存碎片。（為了節省內存操碎了心）當值為非數字類型，就是用val 指針存儲。
*next指向另一個 dictEntry 結構，多個 dictEntry 可以通過 next 指針串連成鏈表，從這里可以看出， ht_table 使用鏈地址法來處理鍵碰撞：當多個不同的鍵擁有相同的哈希值時，哈希表用一個鏈表將這些鍵連接起來。

哈希桶并沒有保存值本身，而是指向具體值的指針，從而實現了哈希桶能存不同數據類型的需求。

redisObject

dictEntry 的 *val 指針指向的值實際上是一個 redisObject 結構體，這是一個非常重要的結構體。

我的 key 只能是字符串類型，而 value 可以是 String、Lists、Set、Sorted Set、散列表等數據類型。

鍵值對的值都被包裝成 redisObject 對象， redisObject 在 server.h 中定義。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

type：記錄了對象的類型，string、set、hash 、Lis、Sorted Set 等，根據該類型來確定是哪種數據類型，使用什么樣的 API 操作。
encoding：編碼方式，表示 ptr 指向的數據類型具體數據結構，即這個對象使用了什么數據結構作為底層實現保存數據。同一個對象使用不同編碼實現內存占用存在明顯差異，內部編碼對內存優化非常重要。
lru:LRU_BITS：LRU 策略下對象最后一次被訪問的時間，如果是 LFU 策略，那么低 8 位表示訪問頻率，高 16 位表示訪問時間。
refcount：表示引用計數，由于 C 語言并不具備內存回收功能，所以 Redis 在自己的對象系統中添加了這個屬性，當一個對象的引用計數為 0 時，則表示該對象已經不被任何對象引用，則可以進行垃圾回收了。
ptr 指針：指向對象的底層實現數據結構，指向值的指針。

如圖 1-11 是由 redisDb、dict、dictEntry、redisObejct 關系圖：

注意，一開始的時候，我只使用 ht_table[0] 這個散列表讀寫數據，ht_table[1] 指向 NULL，當這個散列表容量不足，觸發擴容操作，這時候就會創建一個更大的散列表 ht_table[1]。

接著我會使用漸進式 rehash 的方式將 ht_table[0] 的數據遷移到 ht_table[1] 上，全部遷移完成后，再修改下指針，讓 ht_table[0] 指向擴容后的散列表，回收掉原來的散列表，ht_table[1] 再次指向 NULL。

責任編輯：姜華來源：碼哥字節

Redis 數據存儲