點擊上方?好好學java?，選擇?星標?公眾號

重磅資訊、干貨，第一時間送達 今日推薦：2020年7月程序員工資統計，平均14357元，又跌了，扎心個人原創100W+訪問量博客：點擊前往，查看更多

Redis 數據庫雖然一直都在使用，但是對其內部存儲結構之類的，都沒有研究過，哪怕是面試的時候都沒有準備過這方面的東西。最近在看一門網課，里面有講到過這一塊的內容，結合了《Redis 設計與實現》這本書，粗略的整理了 Redis 的內部存儲結構。就是下面這張圖。

對于 Redis 數據庫，絕大多數人都知道有每個 Redis 實例有 16 個數據庫，但是對于內部是怎么扭轉的大部分人可能不太清楚，反正我是不清楚。整體流程差不多就是上圖表示的那樣吧，知識面有限，難免存在缺漏，湊合著看吧。

其實前面的這些都不是太重要，重要的是后面那四種數據結構和 redisObject。不管重不重要了，都來過一遍吧。

redisDb

redisDb 就是數據庫實例，存儲了真實的數據，每個 Redis 實例都會有 16 個 redisDb。redisDb 的結構定義如下：

附上我歷時三個月總結的?Java 面試 + Java 后端技術學習指南，筆者這幾年及春招的總結，github 1.4k star，拿去不謝！

下載方式

1.?首先掃描下方二維碼

2.?后臺回復「Java面試」即可獲取

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 結構體中有 8 個參數：

• dict：dict 是用來存儲數據的，當前 DB 下的所有數據都存放在這里。

• expires：存儲 key 與過期時間的映射。

• blocking_keys：存儲處于阻塞狀態的 key 及 client 列表。比如在執行 Redis 中 list 的阻塞命令 blpop、brpop 或者 brpoplpush 時，如果對應的 list 列表為空，Redis 就會將對應的 client 設為阻塞狀態，同時將該 client 添加到 DB 中 blocking_keys 這個阻塞 dict。

• ready_keys：存儲解除阻塞的 Key。當有其他調用方在向某個 key 對應的 list 中增加元素時，Redis 會檢測是否有 client 阻塞在這個 key 上，即檢查 blocking_keys 中是否包含這個 key，如果有則會將這個 key 加入 read_keys 這個 dict 中。同時也會將這個 key 保存到 server 中的一個名叫 read_keys 的列表中。

• watched_keys：當 client 使用 watch 指令來監控 key 時，這個 key 和 client 就會被保存到 watched_keys 這個 dict 中。

• id：數據庫編號。

Dict

Dict 數據結構在 Redis 中非常的重要，你可以看到在 redisDb 中，8 個字段中有 5 個是 dict，并且在其他地方也有大量的應用。dict 結構體定義如下：

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 函數及 key/value 賦值、比較函數。

• ht[2]：用來存儲數據的數組。默認使用的是 0 號數組，如果 0 號哈希表元素過多，則分配一個 2 倍 0 號哈希表大小的空間給 1 號哈希表，然后進行逐步遷移。

• rehashidx：用來做標志遷移位置。

Dictht & DictEntry

typedef?struct?dictht?{#?哈希表數組dictEntry?**table;#?哈希表大小unsigned?long?size;#哈希表大小掩碼，用于計算索引值unsigned?long?sizemask;#?該哈希表已有節點的數量unsigned?long?used; }?dictht;typedef?struct?dictEntry?{#?鍵void?*key;union?{#?值void?*val;uint64_t?u64;int64_t?s64;double?d;}?v;#?指向下個哈希表節點，形成鏈表struct?dictEntry?*next; }?dictEntry;

dictht 數據結構沒啥說的，dictEntry 是真正掛載數據的節點，跟 Java 中的 Map 有一點像，采用 key-value 的映射方式。key 采用的是 sds 結構的字符串，value 為存儲各種數據類型的 redisObject 結構。

redisObject、sds還有其他幾種數據結構才是重點，面試的時候有可能會出現，作為使用者，其實了解這幾個就夠了。

redisObject

redisObject 可以理解成 Redis 數據的數據頭，里面定義了一些數據的信息。redisObject 結構體定義如下：

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 結構體字段不多，就 5 個字段，但是這幾個字段都挺重要的，過一下這 5 個字段的含義：

type

type 表示的是 Redis 對象的數據類型，代表這條數據是什么類型，目前 Redis 有 7 種類型。分別為：

• OBJ_STRING：字符串對象。

• OBJ_LIST：列表對象。

• OBJ_SET：集合對象。

• OBJ_ZSET：有序集合對象。

• OBJ_HASH：哈希對象。

• OBJ_MODULE：模塊對象。

• OBJ_STREAM：消息隊列/流對象。

encoding

encoding 是 Redis 對象的內部編碼方式，即這條數據最終在內部是以哪種數據結構存放的。這個字段的作用還是相當大的，我看了一下源碼，目前 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 存儲的是淘汰數據用的 LRU 時間或 LFU 頻率及時間的數據。

refcount

refcount 記錄 Redis 對象的引用計數，用來表示對象被共享的次數，共享使用時加 1，不再使用時減 1，當計數為 0 時表明該對象沒有被使用，就會被釋放，回收內存。

ptr

ptr 是真實數據存儲的引用，它指向對象的內部數據結構。比如一個 string 的對象，內部可能是 sds 數據結構，那么 ptr 指向的就是 sds，除此之外，ptr 還可能指向 ziplist、quicklist、skiplist。

redisObject 大概就這些，下面在聊一聊 Redis 中內存常用的四種數據結構。

1.sds（簡單動態字符串）

Redis沒有直接使用C語言傳統的字符串表示（以空字符結尾的字符數組，以下簡稱C字符串），而是自己構建了一種名為簡單動態字符串（simple dynamic string，SDS）的抽象類型，并將 SDS 用作 Redis 的默認字符串表示。

實現者為了較少開銷，就 sds 定義了 5 種結構體，分別為：sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。這樣最終存儲的時候 sds 會根據字符串實際的長度，選擇不同的數據結構，以更好的提升內存效率。5 種結構體的源代碼如下：

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 之外，其他的幾個數據結構都包含 4 個字段：

• len：字符串的長度。

• alloc：給字符串分配的內存大小。

• flags：當前字節數組的屬性。

• buf：存儲字符串真正的值和一個結束符 \0。

在 redisObject 中有一個編碼方式的字段，sds 數據結構有三種編碼方式，分別為 INT、RAW 、EMBSTR。INT 就相對比較簡單，ptr 直接指向了具體的數據。在這里就簡單的說一說 RAW 和 EMBSTR 的區別。

在 Redis 源碼中，有這么一段代碼，來判斷采用哪種編碼方式。當保存的字符串長度小于等于 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);elsereturn?createRawStringObject(ptr,len); }

embstr 和 raw 編碼方式最主要的區別是在內存分配的時候。embstr 編碼是專門用于保存短字符串的一種優化編碼方式，raw 編碼會調用兩次內存分配函數來分別創建 redisObject 結構和 sdshdr 結構，而 embstr 編碼則通過調用一次內存分配函數來分配一塊連續的空間，空間中依次包含redisObject和sdshdr兩個結構。

embstr 編碼

raw 編碼

raw 編碼

sds 主要是作為字符串的內部數據結構，同時 sds 也是 hyperloglog、bitmap 類型的內部數據結構。

2.ziplist（壓縮列表）

ziplist 是專門為了節約內存，并減少內存碎片而設計的數據結構，ziplist是一塊連續的內存空間，可以連續存儲多個元素，沒有冗余空間，是一種連續內存數據塊組成的順序型內存結構。

ziplist 主要包含 5 個部分：

• zlbytes：ziplist所占用的總內存字節數。

• Zltail：尾節點到起始位置的字節數。

• Zllen：總共包含的節點/內存塊數。

• Entry：ziplist 保存的各個數據節點，這些數據點長度隨意。

• Zlend：一個魔數 255，用來標記壓縮列表的結束。

如圖所示，一個包含 4 個元素的 ziplist，總占用字節是 100bytes，該 ziplist 的起始元素的指針是 p，zltail 是 80，則第 4 個元素的指針是 P+80。

ziplist 的存儲節點是 zlentry， zlentry 結構體定義如下：

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?bytesheader.?Integers?always?use?a?single?byte.*/unsigned?int?len;????????????/*?Bytes?used?to?represent?the?actual?entry.For?strings?this?is?just?the?string?lengthwhile?for?integers?it?is?1,?2,?3,?4,?8?or0?(for?4?bit?immediate)?depending?on?thenumber?range.?*/unsigned?int?headersize;?????/*?prevrawlensize?+?lensize.?*/unsigned?char?encoding;??????/*?Set?to?ZIP_STR_*?or?ZIP_INT_*?depending?onthe?entry?encoding.?However?for?4?bitsimmediate?integers?this?can?assume?a?rangeof?values?and?must?be?range-checked.?*/unsigned?char?*p;????????????/*?Pointer?to?the?very?start?of?the?entry,?thatis,?this?points?to?prev-entry-len?field.?*/ }?zlentry;

zlentry 結構體中有 6 個字段：

• prevRawLen：前置節點的長度；

• preRawLenSize：編碼 preRawLen 需要的字節數；

• len：當前節點的長度；

• lensize：編碼 len 所需要的字節數；

• encoding：?當前節點所用的編碼類型；

• entryData：當前節點數據；

由于 ziplist 是連續緊湊存儲，沒有冗余空間，所以插入新的元素需要 realloc 擴展內存，所以如果 ziplist 占用空間太大，realloc 重新分配內存和拷貝的開銷就會很大，所以 ziplist 不適合存儲過多元素，也不適合存儲過大的字符串。

ziplist 是 hash、sorted set 數據類型的內部存儲結構之一，對于 hash 來說，當元素不超過 512 個 并且值不超過 64個字節，會使用 ziplist 作為內存存儲結構，我們可以通過修改 hash-max-ziplist-entries、hash-max-ziplist-value 參數來控制。對于 sorted set 來說，當元素個數不超過 128個并且值不超過 64 字節，使用 ziplist 來存儲，可以通過調整 zset-max-ziplist-entries、zset-max-ziplist-value 來控制。

3.quicklist（快速列表）

quicklist 數據結構是 Redis 在 3.2 之后引入的，用來替換 linkedlist。因為 linkedlist 每個節點有前后指針，要占用 16 字節，而且每個節點獨立分配內存，很容易加劇內存的碎片化。

而 ziplist 由于緊湊型存儲，增加元素需要 realloc，刪除元素需要內存拷貝，天然不適合元素太多、value 太大的存儲，quicklist 也就誕生了。

quicklist 相關結構體定義如下：

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 整體結構圖：

quicklist 整體結構還是比較簡單的，它是一個基于 ziplist 的雙向鏈表。將數據分段存儲到 ziplist，然后將這些 ziplist 用雙向指針連接。

quicklist 結構體說明：

• head、tail 是兩個指向第一個和最后一個 ziplist 節點的指針。

• count 是 quicklist 中所有的元素個數。

• len 是 ziplist 節點的個數。

• compress 是 LZF 算法的壓縮深度。

quicklistNode 結構體就更簡單的了，quicklistNode 主要包含一個 prev/next 雙向指針，以及一個 ziplist 節點。單個 ziplist 節點可以存放多個元素。

quicklist 是 list 列表的內部數據結構，quicklist 從頭尾讀寫數據很快，時間復雜度為 O(1)。也支持從中間任意位置插入或讀寫元素，但速度較慢，時間復雜度為 O(n)。

4.zskiplist（跳躍表）

在 Java 中也有跳躍表，跳躍表 zskiplist 是一種有序數據結構，它通過在每個節點維持多個指向其他節點的指針，從而可以加速訪問，在大部分場景，跳躍表的效率和平衡樹接近，跳躍表支持平均 O(logN) 和最差 O(n) 復雜度的節點查找，并且跳躍表的實現比平衡樹要簡單。

但是在 Redis 中zskiplist 應用的并不多，只有在以下兩種情況下會使用到跳躍表：

• 在 sorted set 數據類型中，如果元素數較多或元素長度較大，則使用跳躍表作為內部數據結構。默認元素數超過 128 或者最大元素的長度超過 64，此時有序集合就采用 zskiplist 進行存儲。

• 在集群結點中用作內部數據結構。

在 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 結構比較簡單，有四個字段：

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

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

• length 表示跳躍表的長度，它是跳躍表中不包含表頭節點的節點數量。

• level 是目前跳躍表內，除表頭節點外的所有節點中，層數最大的那個節點的層數。跳躍表的節點 zskiplistNode 要相對復雜一些。不過也只有 4 個字段：

• ele 是節點對應的 sds 值，在 zset 有序集合中就是集合中的 field 元素。

• score 是節點的分數，通過 score，跳躍表中的節點自小到大依次排列。

• backward 是指向當前節點的前一個節點的指針。

• level 是節點中的層，每個節點一般有多個層。每個 level 層都帶有兩個屬性，一個是 forwad 前進指針，它用于指向表尾方向的節點；另外一個是 span 跨度，它是指 forward 指向的節點到當前節點的距離。

跳躍表的思想比較簡單，以空間換時間，可以實現快速查找。比如我們要找 S3 這個節點，從先從表頭節點的 L32 層開始查找，一層一層的下沉，最后找到想要的元素。

最后總結一下 Redis 的 8 大類型使用的內部存儲結構。

參考：

• 《300分鐘吃透分布式緩存》
  

• 《Redis 設計與實現》

最后，再附上我歷時三個月總結的?Java 面試 + Java 后端技術學習指南，筆者這幾年及春招的總結，github 1.4k star，拿去不謝！

下載方式

1.?首先掃描下方二維碼

2.?后臺回復「Java面試」即可獲取

總結

以上是生活随笔為你收集整理的聊一聊 Redis 数据内部存储使用到的数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。