Redis 數據結構與對象編碼 (Object Encoding)

2020 年 10 月 31 日
筆記
資料庫

數據結構實現

相信大家對 redis 的數據結構都比較熟悉：

string：字元串（可以表示字元串、整數、點陣圖）
list：列表（可以表示線性表、棧、雙端隊列、阻塞隊列）
hash：哈希表
set：集合
zset：有序集合

為了將性能優化到極致，redis 作者為每種數據結構提供了不同的實現方式，以適應特定應用場景。
以最常用的 string 為例，其底層實現就可以分為 3 種：int, embstr, raw

127.0.0.1:6379> SET counter 1
OK
127.0.0.1:6379> OBJECT ENCODING counter
"int"
127.0.0.1:6379> SET name "Tom"
OK
127.0.0.1:6379> OBJECT ENCODING name
"embstr"
127.0.0.1:6379> SETBIT bits 1 1
(integer) 0
127.0.0.1:6379> OBJECT ENCODING bits
"raw"

這些特定的底層實現在 redis 中被稱為編碼encoding，下面逐一介紹這些編碼實現。

string

redis 中所有的 key 都是字元串，這些字元串是通過一個名為 簡單動態字元串SDS的數據結構實現的。

    typedef char *sds; // SDS 字元串指針，指向 sdshdr.buf

    struct sdshdr? { // SDS header，[?] 可以為 8, 16, 32, 64
        uint?_t len;          // 已用空間，字元串的實際長度
        uint?_t alloc;        // 已分配空間，不包含'\0'
        unsigned char flags;  // 類型標記，指明了 len 與 alloc 的實際類型，可以通過 sds[-1] 獲取
        char buf[];           // 字元數組，保存以'\0'結尾的字元串，與傳統 C 語言中的字元串的表達方式保持一致
    };

記憶體布局如下：

+-------+---------+-----------+-------+
|  len  |  alloc  |   flags   |  buf  |
+-------+---------+-----------+-------+
                   ^--sds[-1]  ^--sds

相較於傳統的 C 字元串，其優點如下：

高效：記錄了已用空間，獲取字元串長度的操作為O(1)
安全：記錄了空閑空間，可以避免寫緩衝區越界的問題
記憶體友好：通過記錄了空間資訊，可以預分配空間，實現惰性刪除，減少記憶體分配的同時不會造成記憶體泄露
二進位安全：字元串內容可以為非 ASCII 編碼，任意數據都能被編碼為二進位字元串
兼容 C 字元串：可以復用部分 C 標準庫程式碼，避免無用重複

list

redis 中 list 的底層實現之一是雙向鏈表，該結構支援順序訪問，並提供了高效的元素增刪功能。

    typedef struct listNode {
        struct listNode *prev; // 前置節點
        struct listNode *next; // 後置節點
        void *value;           // 節點值
    } listNode;

    typedef struct list {
        listNode *head; // 頭節點
        listNode *tail; // 尾節點
        unsigned long len;     // 列表長度
        void *(*dup) (void *ptr); // 節點值複製函數
        void (*free) (void *ptr); // 節點值釋放函數
        int (*match) (void *ptr); // 節點值比較函數
    } list;

這裡使用了函數指針來實現動態綁定，根據 value 類型，指定不同 dup, free, match 的函數，實現多態。

該數據結構有以下特徵：

有長：獲取列表長度的操作為O(1)
雙端：可以同時支援正向和逆向遍歷，獲取前後位置的節點複雜度為O(1)
無環：沒有設置哨兵節點，列表為空時，表頭表尾均為 NULL
多態：通過函數指針實現多態，數據結構可以復用

dict

redis 中使用 dict 來保存鍵值對，其底層實現之一是哈希表。

    typedef struct dictEntry {
        void* key;  // 鍵
        union {     // 值，可以為指針、有符號長整，無符號長整，雙精度浮點
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
        struct dictEntry *next;
    } dictEntry;

    typedef struct dictht {
        dictEntry **table;      // 哈希表數組，數組中的每個元素是一個單向鏈表
        unsigned long size;     // 哈希表數組大小
        unsigned long sizemask; // 哈希掩碼，用於計算索引
        unsigned long used;     // 已有節點數量
    } dictht;

    typedef struct dictType {
        unsigned int (*hashFunction) (const void *key);             // 哈希函數，用於計算哈希值
        int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 鍵比較函數
        void *(*keyDup)(void *privdata, const void *key);           // 鍵複製函數
        void *(*valDup)(void *privdata, const void *obj);           // 值複製函數
        void *(*keyDestructor)(void *privdata, const void *key);    // 鍵銷毀函數
        void *(*valDestructor)(void *privdata, const void *obj);    // 值銷毀函數
    } dictType;

    typedef struct dict {
        dictType *type;     // 類型函數，用於實現多態
        void *privdata;     // 私有數據，用於實現多態
        dictht ht[2];       // 哈希表，字典使用 ht[0] 作為哈希表，ht[1] 用於進行 rehash
        int rehashidx;      // rehash索引，當沒有執行 rehash 時，其值為 -1
    } dict;

該數據結構有以下特徵：

哈希演算法：使用 murmurhash2 作為哈希函數，時間複雜度為O(1)
衝突解決：使用鏈地址法解決衝突，新增元素會被放到表頭，時間複雜度為O(1)
重新散列：每次 rehash 操作都會分成 3 步完成

步驟1：為dict.ht[1]分配空間，其大小為 2 的 n 次方冪
步驟2：將dict.ht[0]中的所有鍵值對 rehash 到dict.ht[1]上
步驟3：釋放dict.ht[0]的空間，用dict.ht[1]替換 dict.ht[0]

rehash 的一些細節

分攤開銷

為了減少停頓，步驟2 會分為多次漸進完成，將 rehash 鍵值對所需的計算工作，平均分攤到每個字典的增加、刪除、查找、更新操作，期間會使用dict.rehashidx記錄dict.ht[0]中已經完成 rehash 操作的dictht.table索引：
- 每執行一次 rehash 操作，dict.rehashidx計數器會加 1
- 當 rehash 完成後，dict.rehashidx會被設置為 -1
觸發條件
計算當前負載因子：loader_factor = ht[0].used / ht[0].size
收縮： 當 loader_factor < 0.1 時，執行 rehash 回收空閑空間
擴展：
1. 沒有執行 BGSAVE 或 BGREWRITEAOF 命令，loader_factor >= 1 執行 rehash
2. 正在執行 BGSAVE 或 BGREWRITEAOF 命令，loader_factor >= 5 執行 rehash
大多作業系統都採用了 寫時複製copy-on-write技術來優化子進程的效率：

父子進程共享同一份數據，直到數據被修改時，才實際拷貝記憶體空間給子進程，保證數據隔離

在執行 BGSAVE 或 BGREWRITEAOF 命令時，redis 會創建子進程，此時伺服器會通過增加 loader_factor 的閾值，避免在子進程存在期間執行不必要的記憶體寫操作，節約記憶體

skiplist

跳錶是一種有序數據結構，並且通過維持多層級指針來達到快速訪問的目的，是典型的空間換時間策略。
其查找效率與平衡樹相近，但是維護成本更低，且實現簡單。

    typedef struct zskiplistNode {
        sds ele;                        // 成員對象
        double score;                   // 分值
        struct zskiplistNode *backward; // 後退指針
        struct zskiplistLevel {
            struct zskiplistNode *forward;  // 前進指針
            unsigned long span;             // 跨度，當前節點和前進節點之間的距離
        } level[];
    } zskiplistNode;

    typedef struct zskiplist {
        struct zskiplistNode *header, *tail;// 頭尾指針
        unsigned long length;               // 長度
        int level;                          // 最大層級
    } zskiplist;

該數據結構有以下特徵：

查找：平均查找時間為O(logN)，最壞查找時間為O(N)，並且支援範圍查找
概率：每次創建節點的時候，程式根據冪次定律隨機生成一個 1 至 32 之間的隨機數，用於決定層高
排位：在查找節點的過程中，沿途訪問過所有的跨度 span 累計起來，得到目標節點在表中的排位

intset

有序整型集合，具有緊湊的存儲空間，添加操作的時間複雜度為O(N)。

    typedef struct intset {
        uint32_t encoding;  // 編碼方式，指示元素的實際類型
        uint32_t length;    // 元素數量
        int8_t contents[];  // 元素數組，元素實際類型可能為 int16_t,int32_t,int64_t,
    } intset;

該數據結構有以下特徵：

有序：元素數組中的元素按照從小到大排列，使用二分查找時間複雜度為O(logN)
升級：當有新元素加入集合，且新元素比所有現有元素類型都長時，集合需要進行升級：

步驟1：根據新元素的類型，擴展元素數組空間
步驟2：將現有元素都轉換為新類型
步驟3：將新元素添加到數組中

ziplist

壓縮列表是為了節約記憶體而開發的，是存儲在連續記憶體塊上的順序數據結構。
一個壓縮列表可以包含任意多的 entry 節點，每個節點包含一個位元組數組或整數。
redis 中並沒有顯式定義 ziplist 的數據結構，僅僅提供了一個描述結構 zlentry 用於操作數據。

    typedef struct zlentry {
        unsigned int prevrawlensize;// 用於記錄前一個 entry 長度的位元組數
        unsigned int prevrawlen;    // 前一個 entry 的長度
        unsigned int lensize        // 用於記錄當前 entry 類型/長度的位元組數
        unsigned int len;           // 實際用於存儲數據的位元組數
        unsigned int headersize;    // prevrawlensize + lensize
        unsigned char encoding;     // 用於指示 entry 數據的實際編碼類型
        unsigned char *p;           // 指向 entry 的開頭
    } zlentry;

其實際的記憶體布局如下：

+----------+---------+---------+--------+-----+--------+--------+
|  zlbytes |  zltail |  zllen  | entry1 | ... | entryN |  zlend |
+----------+---------+---------+--------+-----+--------+--------+
<--------------------------- zlbytes --------------------------->
                                               ^--zltail
                                <------- zllen ------->

zlbytes : 壓縮列表佔用的位元組數 (u_int32)
zltail : 壓縮列表表尾偏移量，無需遍歷即可確定表尾地址，方便反向遍歷 (u_int32)
zllen : 壓縮列表節點數量，當節點數量大於 65535 時，具體數量需要通過遍歷得出 (u_int16)
entryX : 列表節點，具體長度不定
zlend : 列表末端，特殊值 0xFF (u_int8)

entry 的記憶體布局如下：

+-------------------+----------+---------+
| prev_entry_length | encoding | content |
+-------------------+----------+---------+

prev_entry_length : 前一個節點的長度，可以根據當前節點的起始地址，計算前一個節點的起始地址（變長：1位元組/5位元組）
encoding : 節點保存數據的類型和長度（變長：1位元組/2位元組/5位元組）
content : 節點保存的數據，可以保存整數或者位元組數組

該數據結構具有以下特徵：

結構緊湊：一整塊連續記憶體，沒有多餘的記憶體碎片，更新會導致記憶體 realloc 與記憶體複製，平均時間複雜度為 O(N)
逆向遍歷：從表尾開始向表頭進行遍歷
連鎖更新：對前一條數據的更新，可能導致後一條數據的 prev_entry_length 與 encoding 所需長度變化，產生連鎖反應，更新操作最壞時間為 O(N²)

quicklist

在較早版本的 redis 中，list 有兩種底層實現：

當列表對象中元素的長度比較小或者數量比較少的時候，採用壓縮列表 ziplist 來存儲
當列表對象中元素的長度比較大或者數量比較多的時候，則會轉而使用雙向列表 linkedlist 來存儲

兩者各有優缺點：

ziplist 的優點是記憶體緊湊，訪問效率高，缺點是更新效率低，並且數據量較大時，可能導致大量的記憶體複製
linkedlist 的優點是節點修改的效率高，但是需要額外的記憶體開銷，並且節點較多時，會產生大量的記憶體碎片

為了結合兩者的優點，在 redis 3.2 之後，list 的底層實現變為快速列表 quicklist。
快速列表是 linkedlist 與 ziplist 的結合: quicklist 包含多個記憶體不連續的節點，但每個節點本身就是一個 ziplist。

    typedef struct quicklistNode {
        struct quicklistNode *prev;  // 上一個 ziplist 
        struct quicklistNode *next;  // 下一個 ziplist 
        unsigned char *zl;           // 數據指針，指向 ziplist 結構，或者 quicklistLZF 結構
        unsigned int sz;             // ziplist 佔用記憶體長度（未壓縮）
        unsigned int count : 16;     // ziplist 記錄數量
        unsigned int encoding : 2;   // 編碼方式，1 表示 ziplist ，2 表示 quicklistLZF
        unsigned int container : 2;  // 
        unsigned int recompress : 1;         // 臨時解壓，1 表示該節點臨時解壓用於訪問
        unsigned int attempted_compress : 1; // 測試欄位
        unsigned int extra : 10;             // 預留空間
    } quicklistNode;

    typedef struct quicklistLZF {
        unsigned int sz;    // 壓縮數據長度
        char compressed[];  // 壓縮數據
    } quicklistLZF;

    typedef struct quicklist {
        quicklistNode *head;        // 列表頭部
        quicklistNode *tail;        // 列表尾部
        unsigned long count;        // 記錄總數
        unsigned long len;          // ziplist 數量
        int fill : 16;              // ziplist 長度限制，每個 ziplist 節點的長度（記錄數量/記憶體佔用）不能超過這個值
        unsigned int compress : 16; // 壓縮深度，表示 quicklist 兩端不壓縮的 ziplist 節點的個數，為 0 表示所有 ziplist 節點都不壓縮
    } quicklist;

該數據結構有以下特徵：

無縫切換：結合了 linkedlist 與 ziplist 的優點，無需在兩種結構之間進行切換
中間壓縮：作為隊列使用的場景下，list 中間的數據被訪問的頻率比較低，可以選擇進行壓縮以減少記憶體佔用

robj

為了實現動態編碼技術，redis 構建了一個對象系統。
redis 可以在執行命令前，根據對象類型判斷當前命令是否能夠執行。
此外，該系統通過引用計數實現記憶體共享，並記錄來對象訪問時間，為優化記憶體回收策略提供了依據。

    typedef struct redisObject {
        unsigned type:4;        // 類型，當前對象的邏輯類型，例如：set
        unsigned encoding:4;    // 編碼，底層實現的數據結構，例如：intset / ziplist
        unsigned lru:24;        /* LRU 時間 (相對與全局 lru_clock 的時間) 或
                                 * LFU 數據 (8bits 記錄訪問頻率，16 bits 記錄訪問時間). */
        int refcount;           // 引用計數
        void *ptr;              // 數據指針，指向具體的數據結構
    } robj;

該數據結構有以下特徵：

高效：同個類型的 redis 對象可以使用不同的底層實現，可以在不同的應用場景上優化對象的使用效率
節約記憶體：對於整數值的記憶體字元串對象，redis 可以通過記錄引用計數來減少記憶體複製
空轉時長：對象系統會記錄對象的訪問時間，方便 LRU 演算法優先回收較少使用的對象

編碼格式

string 類型

string 的編碼類型可能為：

OBJ_ENCODING_INT int：long 類型整數
OBJ_ENCODING_RAW raw：sds 字元串
OBJ_ENCODING_EMBSTR embstr：嵌入式字元串（編碼後長度小於 44 位元組的字元串）

127.0.0.1:6379> SET str "1234567890 1234567890 1234567890 1234567890"
OK
127.0.0.1:6379> STRLEN str
(integer) 43
127.0.0.1:6379> OBJECT ENCODING str
"embstr"
127.0.0.1:6379> APPEND str _
(integer) 44
127.0.0.1:6379> OBJECT ENCODING str
"raw"

使用 embstr 編碼是為了減少短字元串的記憶體分配次數，參考 redis 作者原話：

REDIS_ENCODING_EMBSTR_SIZE_LIMIT set to 39.
The new value is the limit for the robj + SDS header + string + null-term to stay inside the 64 bytes Jemalloc arena in 64 bits systems.

對比兩者記憶體布局可以發現：

embstr 是一個完整連續的記憶體塊，只需要 1 次記憶體分配
raw 的記憶體是不連續的，需要申請 2 次記憶體


<------------------------------------------ Jemalloc arena (64 bytes)  ---------------------------------------------->
+-------------------------------------------------------------------------------+---------------------+--------------+
|                             redisObject (16 bytes)                            |  sdshdr8 (3 bytes)  |   45 bytes   |
+--------------------+---------------------------------+-------+----------+-----+-----+-------+-------+---------+----+
| type(REDIS_STRING) | encoding(REDIS_ENCODING_EMBSTR) |  lru  | refcount | ptr | len | alloc | flags |   buf   | \0 |
+--------------------+---------------------------------+-------+----------+-----+-----+-------+-------+---------+----+


+--------------------+
|    redisObject     |
+--------------------+
|        type        |
|    REDIS_STRING    |
+--------------------+
|      encoding      |
| REDIS_ENCODING_RAW |
+--------------------+      +---------+
|         ptr        | ---> | sdshdr? |
+--------------------+      +---------+
                            |   len   |
                            +---------+
                            |  alloc  |
                            +---------+
                            |  flags  |
                            +---------++---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                            |   buf   || T | h | e | r | e |   | i | s |   | n | o |   | c | e | r | t | a |...|
                            +---------++---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

list 類型

list 默認的編碼類型為 OBJ_ENCODING_QUICKLIST quicklist

list-max-ziplist-size：每個 quicklist 節點上的 ziplist 長度
list-compress-depth：quicklist 兩端不壓縮的節點數目

hash 類型

hash 的編碼類型有 OBJ_ENCODING_ZIPLIST ziplist 與 OBJ_ENCODING_HT hashtable，具體使用哪種編碼受下面兩個選項控制：

hash-max-ziplist-value：當 key 與 value 的長度都小於該值時使用 ziplist 編碼（默認為 64）
hash-max-ziplist-entries：當 hash 中的元素數量小於該值時使用 ziplist 編碼（默認為 512）

key 長度超過 64 的情況：

127.0.0.1:6379> HSET table x 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'
(integer) 0
127.0.0.1:6379> OBJECT ENCODING table
"ziplist"
127.0.0.1:6379> HSET table x 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'
(integer) 0
127.0.0.1:6379> OBJECT ENCODING table
"hashtable"
127.0.0.1:6379> DEL table
(integer) 1
127.0.0.1:6379> HSET table xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 'x'
(integer) 1
127.0.0.1:6379> OBJECT ENCODING table
"ziplist"
127.0.0.1:6379> HSET table xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 'x'
(integer) 1
127.0.0.1:6379> OBJECT ENCODING table
"hashtable"

value 長度超過 64 的情況：

127.0.0.1:6379> HSET table x 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'
(integer) 0
127.0.0.1:6379> OBJECT ENCODING table
"ziplist"
127.0.0.1:6379> HSET table x 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'
(integer) 0
127.0.0.1:6379> OBJECT ENCODING table
"hashtable"
127.0.0.1:6379> DEL table
(integer) 1
127.0.0.1:6379> HSET table xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 'x'
(integer) 1
127.0.0.1:6379> OBJECT ENCODING table
"ziplist"
127.0.0.1:6379> HSET table xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 'x'
(integer) 1
127.0.0.1:6379> OBJECT ENCODING table
"hashtable"

元素數量度超過 512 的情況：

127.0.0.1:6379> EVAL "for i=1,512 do redis.call('HSET', KEYS[1], i, i) end" 1 numbers
(nil)
127.0.0.1:6379> HLEN numbers
(integer) 512
127.0.0.1:6379> OBJECT ENCODING numbers
"ziplist"
127.0.0.1:6379> DEL numbers
(integer) 1
127.0.0.1:6379> EVAL "for i=1,513 do redis.call('HSET', KEYS[1], i, i) end" 1 numbers
(nil)
127.0.0.1:6379> HLEN numbers
(integer) 513
127.0.0.1:6379> OBJECT ENCODING numbers
"hashtable"

set 類型

set 的編碼類型有 OBJ_ENCODING_INTSET intset 與 OBJ_ENCODING_HT hashtable，具體使用哪種編碼受下面兩個選項控制：

當 set 中的所有元素都是整數時考慮使用 intset 編碼，否則只能使用 hashtable 編碼
set-max-intset-entries：當 set 中的元素數量小於該值時使用 intset 編碼（默認為 512）

包含非整數元素的情況：

127.0.0.1:6379> SADD set 1 2
(integer) 2
127.0.0.1:6379> OBJECT ENCODING set
"intset"
127.0.0.1:6379> SADD set "ABC"
(integer) 1
127.0.0.1:6379> OBJECT ENCODING set
"hashtable"

元素數量度超過 512 的情況：

127.0.0.1:6379> EVAL "for i=1,512 do redis.call('SADD', KEYS[1], i, i) end" 1 numbers
(nil)
127.0.0.1:6379> SCARD numbers
(integer) 512
127.0.0.1:6379> OBJECT ENCODING numbers
"intset"
127.0.0.1:6379> DEL numbers
(integer) 1
127.0.0.1:6379> EVAL "for i=1,513 do redis.call('SADD', KEYS[1], i, i) end" 1 numbers
(nil)
127.0.0.1:6379> SCARD numbers
(integer) 513
127.0.0.1:6379> OBJECT ENCODING numbers
"hashtable"

zset 類型

set 的編碼類型有 OBJ_ENCODING_ZIPLIST ziplist 與 OBJ_ENCODING_SKIPLIST skiplist。

使用 ziplist 編碼時，每個集合元素使用兩個相鄰的 entry 節點保存，第一個節點保存成員值 member，第二節點保存元素的分值 score，並且 entry 按照 score 從小到大進行排序：

+----------------------+
|     redisObject      |
+----------------------+
|         type         |
|      REDIS_ZSET      |
+----------------------+
|       encoding       |
| OBJ_ENCODING_ZIPLIST |
+----------------------+      +----------+----------+---------+--------------------+-------------------+-----+-----------------------+--------------------+-------+
|          ptr         | ---> |  zlbytes |  zltail  |  zllen  | entry 1 (member 1) | entry 2 (score 1) | ... | entry 2N-1 (member N) | entry 2N (score N) | zlend |
+----------------------+      +----------+----------+---------+--------------------+-------------------+-----+-----------------------+--------------------+-------+
                                                               >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> score increase >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

使用 skiplist 實現時，使用會使用一個名為 zset 的數據結構：

    typedef struct zset {
        dict *dict;      // 維護 member -> score 的映射，查找給的成員的分值
        zskiplist *zsl;  // 按 score 大小保存了所有集合元素，支援範圍操作
    } zset; // dict 與 zsl 會共享成員與分值


+----------------------+                                       +--------+     +------------+    +---------+
|     redisObject      |                                   +-->| dictht |     |  StringObj | -> |  long   |
+----------------------+                       +-------+   |   +--------+     +------------+    +---------+
|         type         |                   +-->| dict  |   |   | table  | --> |  StringObj | -> |  long   |
|      REDIS_ZSET      |                   |   +-------+   |   +--------+     +------------+    +---------+
+----------------------+                   |   | ht[0] | --+                  |  StringObj | -> |  long   |
|       encoding       |      +--------+   |   +-------+      +-----+         +------------+    +---------+
| OBJ_ENCODING_ZIPLIST |      |  zset  |   |                  | L32 | -> NULL
+----------------------+      +--------+   |                  +-----+
|          ptr         | ---> |  dict  | --+                  | ... |
+----------------------+      +--------+       +--------+     +-----+    +-----------+                     +-----------+
                              |  zsl   | --->  | header | --> | L4  | -> |     L4    | ------------------> |     L4    | -> NULL
                              +--------+       +--------+     +-----+    +-----------+                     +-----------+
                                               | tail   |     | L3  | -> |     L3    | ------------------> |     L3    | -> NULL
                                               +--------+     +-----+    +-----------+    +-----------+    +-----------+
                                               | level  |     | L2  | -> |     L2    | -> |     L2    | -> |     L2    | -> NULL
                                               +--------+     +-----+    +-----------+    +-----------+    +-----------+
                                               | length |     | L1  | -> |     L1    | -> |     L1    | -> |     L1    | -> NULL
                                               +--------+     +-----+    +-----------+    +-----------+    +-----------+
                                                                 NULL <- |     BW    | <- |     BW    | <- |     BW    |
                                                                         +-----------+    +-----------+    +-----------+
                                                                         | StringObj |    | StringObj |    | StringObj |
                                                                         +-----------+    +-----------+    +-----------+
                                                                         |    long   |    |    long   |    |    long   |
                                                                         +-----------+    +-----------+    +-----------+

zset 具體使用哪種編碼受下面兩個選項控制：

zset-max-ziplist-value：當 member 的長度都小於該值時使用 ziplist 編碼（默認為 64）
zset-max-ziplist-entries：當 zset 中的元素數量小於該值時使用 ziplist 編碼（默認為 128)

Redis 整體結構

每個資料庫都是一個 redisDb 結構體：

    typedef struct redisDb {
        dict *dict;                 /* 據庫的鍵空間 keyspace */
        dict *expires;              /* 設置了過期時間的 key 集合 */
        dict *blocking_keys;        /* 客戶端阻塞等待的 key 集合 (BLPOP)*/
        dict *ready_keys;           /* 已就緒的阻塞 key 集合 (PUSH) */
        dict *watched_keys;         /* 在事務中監控受監控的 key 集合 */
        int id;                     /* 資料庫 ID */
        long long avg_ttl;          /* 平均 TTL, just for stats */
        unsigned long expires_cursor; /* 過期檢測指針 */
        list *defrag_later;         /* 記憶體碎片回收列表 */
    } redisDb;

redis 所有資料庫都保存著 redisServer.db 數組中，redisServer.dbnum 保存了資料庫的數量，簡化後的記憶體布局大致如下：

+-------------+
| redisServer |
+-------------+    +------------+------+-------------+
|     db      | -> | redisDb[0] | .... | redisDb[15] |
+-------------+    +------------+------+-------------+
|    dbnum    |      |
|     16      |      |
+-------------+      |  +---------+                         +------------+
                     +->| redisDb |                     +-> | ListObject |
                        +---------+    +------------+   |   +------------+
                        |  dict   | -> |  StringObj | --+
                        +---------+    +------------+       +------------+
                        | expires |    |  StringObj | ----> | HashObject |
                        +---------+    +------------+       +------------+
                              |        |  StringObj | --+
                              |        +------------+   |   +------------+
                              |                         +-> | StringObj  |
                              |                             +------------+
                              |
                              |       +------------+    +-------------+
                              +---->  |  StringObj | -> |    long     |
                                      +------------+    +-------------+
                                      |  StringObj | -> |    long     |
                                      +------------+    +-------------+

至此，redis 的幾種編碼方式都介紹完畢，後續將對 redis 的一些其他細節進行分享，感謝觀看。

Tags: 資料庫

Redis 數據結構與對象編碼 (Object Encoding)

數據結構實現

string

list

dict

rehash 的一些細節

skiplist

intset

ziplist

quicklist

robj

編碼格式

string 類型

list 類型

hash 類型

set 類型

zset 類型

Redis 整體結構

VirMach 便宜 VPS

QNews

Redis 數據結構與對象編碼 (Object Encoding)

數據結構實現

string

list

dict

rehash 的一些細節

skiplist

intset

ziplist

quicklist

robj

編碼格式

string 類型

list 類型

hash 類型

set 類型

zset 類型

Redis 整體結構

分享此文：

Related Posts

統計輸入的數字為正數和負數的個數

Android 項目程式碼品質保證實踐

drf 路由生成

雙11高鐵來幫忙：日均1000列送件 復興號整列裝運快件

VirMach 便宜 VPS

QNews

熱門搜尋

雙11高鐵來幫忙：日均1000列送件復興號整列裝運快件