Redis數據結構與對象編碼 |ObjectEncoding

2020-11-06 Java成長催化師

數據結構實現

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

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

為了將性能優化到極致，redis 作者為每種數據結構提供了不同的實現方式，以適應特定應用場景。

以最常用的 string 為例，其底層實現就可以分為 3 種： int , embstr , raw

127.0.0.1:6379> SET counter 1OK127.0.0.1:6379> OBJECT ENCODING counter"int"127.0.0.1:6379> SET name "Tom"OK127.0.0.1:6379> OBJECT ENCODING name"embstr"127.0.0.1:6379> SETBIT bits 1 1(integer) 0127.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)

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)

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 索引：dict.rehashidx dict.rehashidx
  • 觸發條件計算當前負載因子： loader_factor = ht[0].used / ht[0].size
    收縮：當 loader_factor < 0.1 時，執行 rehash 回收空閒空間擴展：沒有執行 BGSAVE 或 BGREWRITEAOF 命令，loader_factor >= 1 執行 rehash正在執行 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(N2)

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"OK127.0.0.1:6379> STRLEN str(integer) 43127.0.0.1:6379> OBJECT ENCODING str"embstr"127.0.0.1:6379> APPEND str _(integer) 44127.0.0.1:6379> OBJECT ENCODING str"raw"

使用 embstr 編碼是為了減少短字符串的內存分配次數，參考 redis 作者原話：

REDIS_ENCODING_EMBSTR_SIZE_LIMIT set to 39.

對比兩者內存布局可以發現：

embstrraw

<------------------------------------------ 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) 0127.0.0.1:6379> OBJECT ENCODING table"ziplist"127.0.0.1:6379> HSET table x 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'(integer) 0127.0.0.1:6379> OBJECT ENCODING table"hashtable"127.0.0.1:6379> DEL table(integer) 1127.0.0.1:6379> HSET table xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 'x'(integer) 1127.0.0.1:6379> OBJECT ENCODING table"ziplist"127.0.0.1:6379> HSET table xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 'x'(integer) 1127.0.0.1:6379> OBJECT ENCODING table"hashtable"

value 長度超過 64 的情況：

127.0.0.1:6379> HSET table x 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'(integer) 0127.0.0.1:6379> OBJECT ENCODING table"ziplist"127.0.0.1:6379> HSET table x 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'(integer) 0127.0.0.1:6379> OBJECT ENCODING table"hashtable"127.0.0.1:6379> DEL table(integer) 1127.0.0.1:6379> HSET table xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 'x'(integer) 1127.0.0.1:6379> OBJECT ENCODING table"ziplist"127.0.0.1:6379> HSET table xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 'x'(integer) 1127.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) 512127.0.0.1:6379> OBJECT ENCODING numbers"ziplist"127.0.0.1:6379> DEL numbers(integer) 1127.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) 513127.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) 2127.0.0.1:6379> OBJECT ENCODING set"intset"127.0.0.1:6379> SADD set "ABC"(integer) 1127.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) 512127.0.0.1:6379> OBJECT ENCODING numbers"intset"127.0.0.1:6379> DEL numbers(integer) 1127.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) 513127.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 的一些其他細節進行分享，感謝觀看。

來源：https://www.tuicool.com/articles/A3aU3mj

相關焦點

  • Redis數據結構與對象編碼解析
    數據結構實現相信大家對 redis 的數據結構都比較熟悉：string：字符串（可以表示字符串、整數、位圖）list：列表（可以表示線性表、棧、雙端隊列、阻塞隊列）的數據結構實現的。redis 中並沒有顯式定義 ziplist 的數據結構，僅僅提供了一個描述結構 zlentry 用於操作數據。
  • redis的5種對象與8種數據結構之字符串對象（下）
    embstr編碼與raw編碼對應的字符串對象，都是由對象結構(redisObject)和數據結構(sdshdr)組成的。，而釋放raw編碼的字符串對象需要調用兩次內存釋放函數；3、embstr編碼的字符串對象的所有數據都保存在一塊連續的內存裡，結構更加緊湊，而raw編碼是分散開的，redisObject對象結構和sdshdr數據結構彼此間是用指針相關聯的，embstr編碼的對象比raw編碼的對象能夠更好的利用緩存帶來的優勢。
  • redis的5種對象與8種數據結構之字符串對象（上）
    redis的每種對象都由對象結構(redisObject)與對應編碼的數據結構組合而成，redis支持5種對象類型，分別是字符串(string)、列表(list)、哈希(hash)、集合(set)、有序集合(zset)，而每種對象類型至少對應兩種編碼方式，不同的編碼方式所對應的底層數據結構是不同的。
  • Redis底層數據結構詳解
    對象的ptr指針指向對象的底層實現數據結構，而數據結構是由encoding屬性決定的。Encoding屬性記錄了對象所使用的編碼，也即是說使用了何種數據結構 。encoding key可以查看資料庫的鍵的值對象所使用的編碼。
  • 你不知道的Redis：入門？數據結構？常用指令？
    ，官方給出的讀寫性能10 萬/S，與機器性能也有關鍵值對的數據結構伺服器豐富的功能：見上功能簡單穩定：單線程持久化：發生斷電或機器故障，數據可能會丟失，持久化到硬碟主從複製：實現多個相同數據的redis 副本高可用和分布式：哨兵機制實現高可用，保證redis 節點故障發現和自動轉移
  • redis—底層數據結構詳解
    一、redisObject在redis中基本的結構對象我們稱之為RedisObject，其源碼如下：typedefstructredisObject {unsigned type:4;unsigned encoding:4;unsigned lru:LRU_BITS;int refcount;void *ptr;} robj;其中：
  • Redis的String類型的數據結構
    很多用過redis的同事都知道redis的5種基本數據結構。String、List、Hash、Set、zset。少部分同事會知道Redis中的Bitmap、Geo、HyperLogLog以及布隆過濾器。Redis這些數據類型的數據結構是怎麼設計的呢？人人都說redis對內存優化到了極致，具體是怎麼優化的呢？
  • 十二張圖帶你了解 Redis 的數據結構和對象系統
    Redis是一個開源的 key-value 存儲系統，它使用六種底層數據結構構建了包含字符串對象、列表對象、哈希對象、集合對象和有序集合對象的對象系統。今天我們就通過12張圖來全面了解一下它的數據結構和對象系統的實現原理。本文的內容如下：首先介紹六種基礎數據結構：動態字符串，鍊表，字典，跳躍表，整數集合和壓縮列表。
  • 整理了一篇文章讓你快速了解Redis底層數據結構
    redis中使用多種整數編碼並支持升級操作是為了降低內存消耗和增加靈活性。注意：redis並不支持編碼降級的操作。 壓縮表壓縮表（ziplist）是列表鍵和哈希鍵的底層實之一（元素數量比較少或者元素長度短時）。壓縮表，顧名思義是為節約內存而開發的，是一系列特殊編碼的連續內存地址快組成的順序型數據結構。
  • 小白也能看懂的Redis基礎：Redis基礎數據結構
    接下來就由小編我帶大家來揭秘Redis的五種基本數據結構。Redis是C語音編寫的基於內存的數據結構存儲系統。它可以當作資料庫、緩存和消息中間件。它支持多種類型的數據結構，如 字符串（strings），列表（lists）， 字典（dictht），集合（sets）， 有序集合（sorted sets）。通常我們在項目中可以用它來做緩存、記錄籤到數據、分布式鎖等等。要使用Redis首先我們來了解一下它的五種基礎數據結構。
  • 最詳細的Redis五種數據結構詳解（理論+實戰），建議收藏
    這是關於Redis的第三篇文章，主要講解Redis的五種數據結構詳解，包括這五種的數據結構的底層原理實現。理論肯定是要用於實踐的，因此最重要的還是實戰部分，也就是這裡還會講解五種數據結構的應用場景。工作，還是的深入了解這五種數據結構的底層原理。
  • 學習筆記:Redis的對象類型與內存編碼
    Redis持5種對象類型，每種結構都有少兩種編碼；這樣做的好處在於：接與實現分離，當需要增加或改變內部編碼時，戶使不受影響;另可以根據不同的應場景切換內部編碼，提效率。embstr與raw都使redisObject和sds保存數據，區別在於， embstr的使只分配次內存空間（因此redisObject和sds是連續的），raw需要分配兩次內存 空間（分別為redisObject和sds分配空間）。因此與raw相，embstr的好處在於創建時少分配 次空間，刪除時少釋放次空間，以及對象的所有數據連在起，尋找便。
  • 分析Redis key,value的size
    為了便於快速高效的對RDB文件進行讀寫,Redis採用LZF壓縮算法來減少文件的大小,在Redis底層數據結構中,每個對象都會有一個相應大小的前綴用來描述該對象佔用的字節數長度等,因此Redis在加載該RDB文件時,讀取的每個對象Redis都會知道應該為它分配多大的內存空間.
  • Redis基本數據結構之集合
    集合，也是用來保存多個元素的一種數據結構，和之前介紹的列表有所區別：typedef struct intset{ uint32_t encoding; uint32_t length; int8_t content[];} intset;從intset的結構可以看出，底層使用的是一個整數數組實現的。並且有一個length記錄長度，所以當獲取intset編碼的集合的長度時，時間複雜度為O(1)。
  • 深入剖析Redis系列:Redis數據結構之集合 - 程序猿的內心獨白
    內部編碼為整數集合當元素個數 較少且都為 整數 時，內部編碼 為 intset。127.0.0.1:6379> sadd setkey 1 2 3 4(integer) 4127.0.0.1:6379> object encoding setkey"intset"2.3.2.
  • 3天時間，我是如何解決redis bigkey 刪除問題的？
    如果按照數據結構來細分的話，一般分為字符串類型bigkey和非字符串類型bigkey。有一定輔助作用，因為不是每種數據結構都有類似strlen這樣的方法。如何刪除因為 redis 是單線程的，刪除比較大的 keys 就會阻塞其他的請求。當發現Redis中有bigkey並且確認要刪除時，如何優雅地刪除bigkey？無論是什麼數據結構，del命令都將其刪除。
  • Redis存JSON數據時選擇string還是hash
    1、佔用空間根據數據結構的共識我們知道hashtable類型是要比string類型更佔用空間， 而ziplist類型與string類型佔用的空間基本相差不大。如下圖就是ziplist的存儲的格式那我們接下來分別分析redis的string和hash類型佔用空間方面的知識string類型： string類型當然如其名，如果json數據以string類型去存儲，那麼它的空間佔用方面肯定是相當的。hash類型： redis對hash類型是有兩種編碼方式，分別是ziplist和hashtable。
  • 一不小心肝了5W字的Redis入門到代碼實操
    這是關於Redis五種數據結構詳解，包括這五種的數據結構的底層原理實現。理論肯定是要用於實踐的，因此最重要的還是實戰部分，也就是這裡還會講解五種數據結構的應用場景。工作，還是得深入了解這五種數據結構的底層原理。
  • scrapy中scrapy_redis分布式內置pipeline源碼及其工作原理
    scrapy_redis分布式實現了一套自己的組件，其中也提供了Redis數據存儲的數據管道，位於scrapy_redis.pipelines,這篇文章主要分析器源碼及其工作流程，源碼如下：from scrapy.utils.misc import load_objectfrom scrapy.utils.serialize import ScrapyJSONEncoderfrom
  • 徹底教你解決python中編碼問題
    只有 unicode object 和非unicode object其實應該叫 str object）的區別：unicode string（unicode類型）：以Unicode code points形式存儲，人類認識的形式byte string（str 類型）：以byte形式存儲，機器認識的形式當我們直接使用雙引號或單引號包含字符的方式來定義字符串時