聊一聊 Redis 數(shù)據(jù)內(nèi)部存儲使用到的數(shù)據(jù)結(jié)構(gòu)
Redis 數(shù)據(jù)庫雖然一直都在使用，但是對其內(nèi)部存儲結(jié)構(gòu)之類的，都沒有研究過，哪怕是面試的時候都沒有準(zhǔn)備過這方面的東西。最近在看一門網(wǎng)課，里面有講到過這一塊的內(nèi)容，結(jié)合了《Redis 設(shè)計與實現(xiàn)》這本書，粗略的整理了 Redis 的內(nèi)部存儲結(jié)構(gòu)。就是下面這張圖。
對于 Redis 數(shù)據(jù)庫，絕大多數(shù)人都知道有每個 Redis 實例有 16 個數(shù)據(jù)庫，但是對于內(nèi)部是怎么扭轉(zhuǎn)的大部分人可能不太清楚，反正我是不清楚。整體流程差不多就是上圖表示的那樣吧，知識面有限，難免存在缺漏，湊合著看吧。
其實前面的這些都不是太重要，重要的是后面那四種數(shù)據(jù)結(jié)構(gòu)和 redisObject。不管重不重要了，都來過一遍吧。
redisDb
redisDb 就是數(shù)據(jù)庫實例，存儲了真實的數(shù)據(jù)，每個 Redis 實例都會有 16 個 redisDb。redisDb 的結(jié)構(gòu)定義如下：
- typedef struct redisDb {
- dict *dict; /* The keyspace for this DB */
- dict *expires; /* Timeout of keys with a timeout set */
- dict *blocking_keys; /* Keys with clients waiting for data (BLPOP)*/
- dict *ready_keys; /* Blocked keys that received a PUSH */
- dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
- int id; /* Database ID */
- long long avg_ttl; /* Average TTL, just for stats */
- list *defrag_later; /* List of key names to attempt to defrag one by one, gradually. */
- } redisDb;
redisDb 結(jié)構(gòu)體中有 8 個參數(shù)：
- dict：dict 是用來存儲數(shù)據(jù)的，當(dāng)前 DB 下的所有數(shù)據(jù)都存放在這里。
- expires：存儲 key 與過期時間的映射。
- blocking_keys：存儲處于阻塞狀態(tài)的 key 及 client 列表。比如在執(zhí)行 Redis 中 list 的阻塞命令 blpop、brpop 或者 brpoplpush 時，如果對應(yīng)的 list 列表為空，Redis 就會將對應(yīng)的 client 設(shè)為阻塞狀態(tài)，同時將該 client 添加到 DB 中 blocking_keys 這個阻塞 dict。
- ready_keys：存儲解除阻塞的 Key。當(dāng)有其他調(diào)用方在向某個 key 對應(yīng)的 list 中增加元素時，Redis 會檢測是否有 client 阻塞在這個 key 上，即檢查 blocking_keys 中是否包含這個 key，如果有則會將這個 key 加入 read_keys 這個 dict 中。同時也會將這個 key 保存到 server 中的一個名叫 read_keys 的列表中。
- watched_keys：當(dāng) client 使用 watch 指令來監(jiān)控 key 時，這個 key 和 client 就會被保存到 watched_keys 這個 dict 中。
- id：數(shù)據(jù)庫編號。
Dict
Dict 數(shù)據(jù)結(jié)構(gòu)在 Redis 中非常的重要，你可以看到在 redisDb 中，8 個字段中有 5 個是 dict，并且在其他地方也有大量的應(yīng)用。dict 結(jié)構(gòu)體定義如下：
- typedef struct dict {
- dictType *type;
- void *privdata;
- dictht ht[2];
- long rehashidx; /* rehashing not in progress if rehashidx == -1 */
- unsigned long iterators; /* number of iterators currently running */
- } dict;
dict 本身是比較簡單的，字段也不多，其中有三個字段比較重要，有必要了解一下：
- type：用于保存 hash 函數(shù)及 key/value 賦值、比較函數(shù)。
- ht[2]：用來存儲數(shù)據(jù)的數(shù)組。默認(rèn)使用的是 0 號數(shù)組，如果 0 號哈希表元素過多，則分配一個 2 倍 0 號哈希表大小的空間給 1 號哈希表，然后進行逐步遷移。
- rehashidx：用來做標(biāo)志遷移位置。
Dictht & DictEntry
- typedef struct dictht {
- # 哈希表數(shù)組
- dictEntry **table;
- # 哈希表大小
- unsigned long size;
- #哈希表大小掩碼，用于計算索引值
- unsigned long sizemask;
- # 該哈希表已有節(jié)點的數(shù)量
- unsigned long used;
- } dictht;
- typedef struct dictEntry {
- # 鍵
- void *key;
- union {
- # 值
- void *val;
- uint64_t u64;
- int64_t s64;
- double d;
- } v;
- # 指向下個哈希表節(jié)點，形成鏈表
- struct dictEntry *next;
- } dictEntry;
dictht 數(shù)據(jù)結(jié)構(gòu)沒啥說的，dictEntry 是真正掛載數(shù)據(jù)的節(jié)點，跟 Java 中的 Map 有一點像，采用 key-value 的映射方式。key 采用的是 sds 結(jié)構(gòu)的字符串，value 為存儲各種數(shù)據(jù)類型的 redisObject 結(jié)構(gòu)。
redisObject、sds還有其他幾種數(shù)據(jù)結(jié)構(gòu)才是重點，面試的時候有可能會出現(xiàn)，作為使用者，其實了解這幾個就夠了。
redisObject
redisObject 可以理解成 Redis 數(shù)據(jù)的數(shù)據(jù)頭，里面定義了一些數(shù)據(jù)的信息。redisObject 結(jié)構(gòu)體定義如下：
- typedef struct redisObject {
- unsigned type:4;
- unsigned encoding:4;
- unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
- * LFU data (least significant 8 bits frequency
- * and most significant 16 bits access time). */
- int refcount;
- void *ptr;
- } robj;
redisObject 結(jié)構(gòu)體字段不多，就 5 個字段，但是這幾個字段都挺重要的，過一下這 5 個字段的含義：
type
type 表示的是 Redis 對象的數(shù)據(jù)類型，代表這條數(shù)據(jù)是什么類型，目前 Redis 有 7 種類型。分別為：
- OBJ_STRING：字符串對象。
- OBJ_LIST：列表對象。
- OBJ_SET：集合對象。
- OBJ_ZSET：有序集合對象。
- OBJ_HASH：哈希對象。
- OBJ_MODULE：模塊對象。
- OBJ_STREAM：消息隊列/流對象。
encoding
encoding 是 Redis 對象的內(nèi)部編碼方式，即這條數(shù)據(jù)最終在內(nèi)部是以哪種數(shù)據(jù)結(jié)構(gòu)存放的。這個字段的作用還是相當(dāng)大的，我看了一下源碼，目前 Redis 中有 10 種編碼方式，如下：
- OBJ_ENCODING_RAW
- OBJ_ENCODING_INT
- OBJ_ENCODING_HT
- OBJ_ENCODING_ZIPLIST
- OBJ_ENCODING_ZIPMAP
- OBJ_ENCODING_SKIPLIST
- OBJ_ENCODING_EMBSTR
- OBJ_ENCODING_QUICKLIST
- OBJ_ENCODING_STREAM
- OBJ_ENCODING_INTSET
LRU
LRU 存儲的是淘汰數(shù)據(jù)用的 LRU 時間或 LFU 頻率及時間的數(shù)據(jù)。
refcount
refcount 記錄 Redis 對象的引用計數(shù)，用來表示對象被共享的次數(shù)，共享使用時加 1，不再使用時減 1，當(dāng)計數(shù)為 0 時表明該對象沒有被使用，就會被釋放，回收內(nèi)存。
ptr
ptr 是真實數(shù)據(jù)存儲的引用，它指向?qū)ο蟮膬?nèi)部數(shù)據(jù)結(jié)構(gòu)。比如一個 string 的對象，內(nèi)部可能是 sds 數(shù)據(jù)結(jié)構(gòu)，那么 ptr 指向的就是 sds，除此之外，ptr 還可能指向 ziplist、quicklist、skiplist。
redisObject 大概就這些，下面在聊一聊 Redis 中內(nèi)存常用的四種數(shù)據(jù)結(jié)構(gòu)。
1.sds(簡單動態(tài)字符串)
Redis沒有直接使用C語言傳統(tǒng)的字符串表示(以空字符結(jié)尾的字符數(shù)組，以下簡稱C字符串)，而是自己構(gòu)建了一種名為簡單動態(tài)字符串(simple dynamic string，SDS)的抽象類型，并將 SDS 用作 Redis 的默認(rèn)字符串表示。
實現(xiàn)者為了較少開銷，就 sds 定義了 5 種結(jié)構(gòu)體，分別為：sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。這樣最終存儲的時候 sds 會根據(jù)字符串實際的長度，選擇不同的數(shù)據(jù)結(jié)構(gòu)，以更好的提升內(nèi)存效率。5 種結(jié)構(gòu)體的源代碼如下：
- struct __attribute__ ((__packed__)) sdshdr5 {
- unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr8 {
- uint8_t len; /* used */
- uint8_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr16 {
- uint16_t len; /* used */
- uint16_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr32 {
- uint32_t len; /* used */
- uint32_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr64 {
- uint64_t len; /* used */
- uint64_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
除了 sdshdr5 之外，其他的幾個數(shù)據(jù)結(jié)構(gòu)都包含 4 個字段：
- len：字符串的長度。
- alloc：給字符串分配的內(nèi)存大小。
- flags：當(dāng)前字節(jié)數(shù)組的屬性。
- buf：存儲字符串真正的值和一個結(jié)束符 \0。
在 redisObject 中有一個編碼方式的字段，sds 數(shù)據(jù)結(jié)構(gòu)有三種編碼方式，分別為 INT、RAW 、EMBSTR。INT 就相對比較簡單，ptr 直接指向了具體的數(shù)據(jù)。在這里就簡單的說一說 RAW 和 EMBSTR 的區(qū)別。
在 Redis 源碼中，有這么一段代碼，來判斷采用哪種編碼方式。當(dāng)保存的字符串長度小于等于 44 ，采用的是 embstr 編碼格式，否則采用 RAW 編碼方式。(具體的長度可能每個版本定義不一樣)
- #define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
- robj *createStringObject(const char *ptr, size_t len) {
- if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
- return createEmbeddedStringObject(ptr,len);
- else
- return createRawStringObject(ptr,len);
- }
embstr 和 raw 編碼方式最主要的區(qū)別是在內(nèi)存分配的時候。embstr 編碼是專門用于保存短字符串的一種優(yōu)化編碼方式，raw 編碼會調(diào)用兩次內(nèi)存分配函數(shù)來分別創(chuàng)建 redisObject 結(jié)構(gòu)和 sdshdr 結(jié)構(gòu)，而 embstr 編碼則通過調(diào)用一次內(nèi)存分配函數(shù)來分配一塊連續(xù)的空間，空間中依次包含redisObject和sdshdr兩個結(jié)構(gòu)。
embstr 編碼
raw 編碼
raw 編碼
sds 主要是作為字符串的內(nèi)部數(shù)據(jù)結(jié)構(gòu)，同時 sds 也是 hyperloglog、bitmap 類型的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。
2.ziplist(壓縮列表)
ziplist 是專門為了節(jié)約內(nèi)存，并減少內(nèi)存碎片而設(shè)計的數(shù)據(jù)結(jié)構(gòu)，ziplist是一塊連續(xù)的內(nèi)存空間，可以連續(xù)存儲多個元素，沒有冗余空間，是一種連續(xù)內(nèi)存數(shù)據(jù)塊組成的順序型內(nèi)存結(jié)構(gòu)。
ziplist 主要包含 5 個部分：
- zlbytes：ziplist所占用的總內(nèi)存字節(jié)數(shù)。
- Zltail：尾節(jié)點到起始位置的字節(jié)數(shù)。
- Zllen：總共包含的節(jié)點/內(nèi)存塊數(shù)。
- Entry：ziplist 保存的各個數(shù)據(jù)節(jié)點，這些數(shù)據(jù)點長度隨意。
- Zlend：一個魔數(shù) 255，用來標(biāo)記壓縮列表的結(jié)束。
如圖所示，一個包含 4 個元素的 ziplist，總占用字節(jié)是 100bytes，該 ziplist 的起始元素的指針是 p，zltail 是 80，則第 4 個元素的指針是 P+80。
ziplist 的存儲節(jié)點是 zlentry， zlentry 結(jié)構(gòu)體定義如下：
- typedef struct zlentry {
- unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
- unsigned int prevrawlen; /* Previous entry len. */
- unsigned int lensize; /* Bytes used to encode this entry type/len.
- For example strings have a 1, 2 or 5 bytes
- header. Integers always use a single byte.*/
- unsigned int len; /* Bytes used to represent the actual entry.
- For strings this is just the string length
- while for integers it is 1, 2, 3, 4, 8 or
- 0 (for 4 bit immediate) depending on the
- number range. */
- unsigned int headersize; /* prevrawlensize + lensize. */
- unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on
- the entry encoding. However for 4 bits
- immediate integers this can assume a range
- of values and must be range-checked. */
- unsigned char *p; /* Pointer to the very start of the entry, that
- is, this points to prev-entry-len field. */
- } zlentry;
zlentry 結(jié)構(gòu)體中有 6 個字段：
- prevRawLen：前置節(jié)點的長度;
- preRawLenSize：編碼 preRawLen 需要的字節(jié)數(shù);
- len：當(dāng)前節(jié)點的長度;
- lensize：編碼 len 所需要的字節(jié)數(shù);
- encoding： 當(dāng)前節(jié)點所用的編碼類型;
- entryData：當(dāng)前節(jié)點數(shù)據(jù);
由于 ziplist 是連續(xù)緊湊存儲，沒有冗余空間，所以插入新的元素需要 realloc 擴展內(nèi)存，所以如果 ziplist 占用空間太大，realloc 重新分配內(nèi)存和拷貝的開銷就會很大，所以 ziplist 不適合存儲過多元素，也不適合存儲過大的字符串。
ziplist 是 hash、sorted set 數(shù)據(jù)類型的內(nèi)部存儲結(jié)構(gòu)之一，對于 hash 來說，當(dāng)元素不超過 512 個 并且值不超過 64個字節(jié)，會使用 ziplist 作為內(nèi)存存儲結(jié)構(gòu)，我們可以通過修改 hash-max-ziplist-entries、hash-max-ziplist-value 參數(shù)來控制。對于 sorted set 來說，當(dāng)元素個數(shù)不超過 128個并且值不超過 64 字節(jié)，使用 ziplist 來存儲，可以通過調(diào)整 zset-max-ziplist-entries、zset-max-ziplist-value 來控制。
3.quicklist(快速列表)
quicklist 數(shù)據(jù)結(jié)構(gòu)是 Redis 在 3.2 之后引入的，用來替換 linkedlist。因為 linkedlist 每個節(jié)點有前后指針，要占用 16 字節(jié)，而且每個節(jié)點獨立分配內(nèi)存，很容易加劇內(nèi)存的碎片化。
而 ziplist 由于緊湊型存儲，增加元素需要 realloc，刪除元素需要內(nèi)存拷貝，天然不適合元素太多、value 太大的存儲，quicklist 也就誕生了。
quicklist 相關(guān)結(jié)構(gòu)體定義如下：
- typedef struct quicklist {
- quicklistNode *head;
- quicklistNode *tail;
- unsigned long count; /* total count of all entries in all ziplists */
- unsigned long len; /* number of quicklistNodes */
- int fill : 16; /* fill factor for individual nodes */
- unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
- } quicklist;
- typedef struct quicklistNode {
- struct quicklistNode *prev;
- struct quicklistNode *next;
- unsigned char *zl;
- unsigned int sz; /* ziplist size in bytes */
- unsigned int count : 16; /* count of items in ziplist */
- unsigned int encoding : 2; /* RAW==1 or LZF==2 */
- unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
- unsigned int recompress : 1; /* was this node previous compressed? */
- unsigned int attempted_compress : 1; /* node can't compress; too small */
- unsigned int extra : 10; /* more bits to steal for future usage */
- } quicklistNode;
quicklist 整體結(jié)構(gòu)圖：
quicklist 整體結(jié)構(gòu)還是比較簡單的，它是一個基于 ziplist 的雙向鏈表。將數(shù)據(jù)分段存儲到 ziplist，然后將這些 ziplist 用雙向指針連接。
quicklist 結(jié)構(gòu)體說明：
- head、tail 是兩個指向第一個和最后一個 ziplist 節(jié)點的指針。
- count 是 quicklist 中所有的元素個數(shù)。
- len 是 ziplist 節(jié)點的個數(shù)。
- compress 是 LZF 算法的壓縮深度。
quicklistNode 結(jié)構(gòu)體就更簡單的了，quicklistNode 主要包含一個 prev/next 雙向指針，以及一個 ziplist 節(jié)點。單個 ziplist 節(jié)點可以存放多個元素。
quicklist 是 list 列表的內(nèi)部數(shù)據(jù)結(jié)構(gòu)，quicklist 從頭尾讀寫數(shù)據(jù)很快，時間復(fù)雜度為 O(1)。也支持從中間任意位置插入或讀寫元素，但速度較慢，時間復(fù)雜度為 O(n)。
4.zskiplist(跳躍表)
在 Java 中也有跳躍表，跳躍表 zskiplist 是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點維持多個指向其他節(jié)點的指針，從而可以加速訪問，在大部分場景，跳躍表的效率和平衡樹接近，跳躍表支持平均 O(logN) 和最差 O(n) 復(fù)雜度的節(jié)點查找，并且跳躍表的實現(xiàn)比平衡樹要簡單。
但是在 Redis 中zskiplist 應(yīng)用的并不多，只有在以下兩種情況下會使用到跳躍表：
- 在 sorted set 數(shù)據(jù)類型中，如果元素數(shù)較多或元素長度較大，則使用跳躍表作為內(nèi)部數(shù)據(jù)結(jié)構(gòu)。默認(rèn)元素數(shù)超過 128 或者最大元素的長度超過 64，此時有序集合就采用 zskiplist 進行存儲。
- 在集群結(jié)點中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)。
在 Redis 中，跳躍表主要有 zskiplistNode 和 zskiplist 組合，定義如下：
- 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;
- typedef struct zset {
- dict *dict;
- zskiplist *zsl;
- } zset;
跳躍表 zskiplist 結(jié)構(gòu)比較簡單，有四個字段：
- header 指向跳躍表的表頭節(jié)點。
- tail 指向跳躍表的表尾節(jié)點。
- length 表示跳躍表的長度，它是跳躍表中不包含表頭節(jié)點的節(jié)點數(shù)量。
- level 是目前跳躍表內(nèi)，除表頭節(jié)點外的所有節(jié)點中，層數(shù)最大的那個節(jié)點的層數(shù)。跳躍表的節(jié)點 zskiplistNode 要相對復(fù)雜一些。不過也只有 4 個字段：
- ele 是節(jié)點對應(yīng)的 sds 值，在 zset 有序集合中就是集合中的 field 元素。
- score 是節(jié)點的分?jǐn)?shù)，通過 score，跳躍表中的節(jié)點自小到大依次排列。
- backward 是指向當(dāng)前節(jié)點的前一個節(jié)點的指針。
- level 是節(jié)點中的層，每個節(jié)點一般有多個層。每個 level 層都帶有兩個屬性，一個是 forwad 前進指針，它用于指向表尾方向的節(jié)點;另外一個是 span 跨度，它是指 forward 指向的節(jié)點到當(dāng)前節(jié)點的距離。
跳躍表的思想比較簡單，以空間換時間，可以實現(xiàn)快速查找。比如我們要找 S3 這個節(jié)點，從先從表頭節(jié)點的 L32 層開始查找，一層一層的下沉，最后找到想要的元素。
最后總結(jié)一下 Redis 的 8 大類型使用的內(nèi)部存儲結(jié)構(gòu)。
