redis存儲類型

主要提供了5種數(shù)據(jù)結(jié)構(gòu)：字符串（String）、哈希(hash)、列表(list)、集合(set)、有序集合(short set)；

redis底層實(shí)現(xiàn)的8種數(shù)據(jù)結(jié)構(gòu)

SDS simple synamic string：支持自動動態(tài)擴(kuò)容的字節(jié)數(shù)組
list ：鏈表
dict ：使用雙哈希表實(shí)現(xiàn)的, 支持平滑擴(kuò)容的字典
zskiplist ：附加了后向指針的跳躍表
intset ： 用于存儲整數(shù)數(shù)值集合的自有結(jié)構(gòu)
ziplist ：一種實(shí)現(xiàn)上類似于TLV, 但比TLV復(fù)雜的, 用于存儲任意數(shù)據(jù)的有序序列的數(shù)據(jù)結(jié)構(gòu)
quicklist：一種以ziplist作為結(jié)點(diǎn)的雙鏈表結(jié)構(gòu), 實(shí)現(xiàn)的非常不錯
zipmap ： 一種用于在小規(guī)模場合使用的輕量級字典結(jié)構(gòu)

其中5種存儲類型與8種數(shù)據(jù)結(jié)構(gòu)的橋梁, 是redisObject；

Redis中的Key與Value在表層都是一個redisObject實(shí)例, 所以該結(jié)構(gòu)有所謂的"類型", 即是ValueType. 對于每一種Value Type類型的redisObject；

其底層至少支持兩種不同的底層數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn). 以應(yīng)對在不同的應(yīng)用場景中, Redis的運(yùn)行效率, 或內(nèi)存占用等

底層數(shù)據(jù)結(jié)構(gòu)分析

1、SDS - simple dynamic string

可以在安裝目錄的src文件夾下看到sds.c和sds.h的源碼文件

typedef char *sds;
 
/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
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[];
};s

sdshdr的存儲結(jié)構(gòu)

sdshdr是頭部, buf是真實(shí)存儲用戶數(shù)據(jù)的地方.（buf="數(shù)據(jù)" + "" ）；sds有四種不同的頭部. sdshdr5未 使用，未顯示

en分別以uint8, uint16, uint32, uint64表示用戶數(shù)據(jù)的長度(不包括末尾的)

alloc分別以uint8, uint16, uint32, uint64表示整個SDS, 除過頭部與末尾的, 剩余的字節(jié)數(shù).

flag始終為一字節(jié), 以低三位標(biāo)示著頭部的類型, 高5位未使用.

創(chuàng)建一個SDS實(shí)例的三個接口

2、list

鏈表實(shí)現(xiàn), 鏈表結(jié)點(diǎn)不直接持有數(shù)據(jù), 而是通過void *指針來間接的指向數(shù)據(jù). 其實(shí)現(xiàn)位于 src/adlist.h與src/adlist.c中,

內(nèi)存布局

list在Redis除了作為一些Value Type的底層實(shí)現(xiàn)外, 還廣泛用于Redis的其它功能實(shí)現(xiàn)中, 作為一種數(shù)據(jù)結(jié)構(gòu)工具使用.

在list的實(shí)現(xiàn)中, 除了基本的鏈表定義外, 還額外增加了:迭代器listIter的定義, 與相關(guān)接口的實(shí)現(xiàn).

由于list中的鏈表結(jié)點(diǎn)本身并不直接持有數(shù)據(jù), 而是通過value字段, 以void *指針的形式間接持有, 所以數(shù)據(jù)的生命周期并不完全與鏈表及其結(jié)點(diǎn)一致. 這給了list的使用者相當(dāng)大的靈活性. 比如可以多個結(jié)點(diǎn)持有同一份數(shù)據(jù)的地址. 但與此同時, 在對鏈表進(jìn)行銷毀, 結(jié)點(diǎn)復(fù)制以及查找匹配時, 就需要list的使用者將相關(guān)的函數(shù)指針賦值于list.dup, list.free, list.match字段.

3、dict

dict類似于C++標(biāo)準(zhǔn)庫中的std::unordered_map, 其實(shí)現(xiàn)位于 src/dict.h 與 src/dict.c中

dict中存儲的鍵值對, 是通過dictEntry這個結(jié)構(gòu)間接持有的, k通過指針間接持有鍵, v通過指針間接持有值. 注意, 若值是整數(shù)值的話, 是直接存儲在v字段中的, 而不是間接持有. 同時next指針用于指向, 在bucket索引值沖突時, 以鏈?zhǔn)椒绞浇鉀Q沖突, 指向同索引的下一個dictEntry結(jié)構(gòu).

dict即為字典. 其中type字段中存儲的是本字典使用到的各種函數(shù)指針, 包括散列函數(shù), 鍵與值的復(fù)制函數(shù), 釋放函數(shù), 以及鍵的比較函數(shù). privdata是用于存儲用戶自定義數(shù)據(jù). 這樣, 字典的使用者可以最大化的自定義字典的實(shí)現(xiàn), 通過自定義各種函數(shù)實(shí)現(xiàn), 以及可以附帶私有數(shù)據(jù), 保證了字典有很大的調(diào)優(yōu)空間.

字典為了支持平滑擴(kuò)容, 定義了ht[2]這個數(shù)組字段. 其用意是這樣的:

一般情況下, 字典dict僅持有一個哈希表dictht的實(shí)例, 即整個字典由一個bucket實(shí)現(xiàn).

隨著插入操作, bucket中出現(xiàn)沖突的概率會越來越大, 當(dāng)字典中存儲的結(jié)點(diǎn)數(shù)目, 與bucket數(shù)組長度的比值達(dá)到一個閾值(1:1)時, 字典為了緩解性能下降, 就需要擴(kuò)容

擴(kuò)容的操作是平滑的, 即在擴(kuò)容時, 字典會持有兩個dictht的實(shí)例, ht[0]指向舊哈希表, ht[1]指向擴(kuò)容后的新哈希表.

內(nèi)存布局

4、zskiplist

zskiplist是Redis實(shí)現(xiàn)的一種特殊的跳躍表. 跳躍表是一種基于線性表實(shí)現(xiàn)簡單的搜索結(jié)構(gòu), 其最大的特點(diǎn)就是: 實(shí)現(xiàn)簡單, 性能能逼近各種搜索樹結(jié)構(gòu).

zskiplist的核心設(shè)計要點(diǎn):

頭結(jié)點(diǎn)不持有任何數(shù)據(jù), 且其level[]的長度為32

每個結(jié)點(diǎn), 除了持有數(shù)據(jù)的ele字段, 還有一個字段score, 其標(biāo)示著結(jié)點(diǎn)的得分, 結(jié)點(diǎn)之間憑借得分來判斷先后順序, 跳躍表中的結(jié)點(diǎn)按結(jié)點(diǎn)的得分升序排列.

每個結(jié)點(diǎn)持有一個backward指針, 這是原版跳躍表中所沒有的. 該指針指向結(jié)點(diǎn)的前一個緊鄰結(jié)點(diǎn).

每個結(jié)點(diǎn)中最多持有32個zskiplistLevel結(jié)構(gòu). 實(shí)際數(shù)量在結(jié)點(diǎn)創(chuàng)建時, 按冪次定律隨機(jī)生成(不超過32). 每個zskiplistLevel中有兩個字段.

內(nèi)存布局

5、intset

用于存儲在序的整數(shù)的數(shù)據(jù)結(jié)構(gòu), 也底層數(shù)據(jù)結(jié)構(gòu)中最簡單的一個, 其定義與實(shí)現(xiàn)在src/intest.h與src/intset.c中

inset結(jié)構(gòu)中的encoding的取值有三個, 分別是宏INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64. length代表其中存儲的整數(shù)的個數(shù), contents指向?qū)嶋H存儲數(shù)值的連續(xù)內(nèi)存區(qū)域

內(nèi)存布局

intset中各字段, 包括contents中存儲的數(shù)值, 都是以主機(jī)序(小端字節(jié)序)存儲的. 這意味著Redis若運(yùn)行在PPC這樣的大端字節(jié)序的機(jī)器上時, 存取數(shù)據(jù)都會有額外的字節(jié)序轉(zhuǎn)換開銷

當(dāng)encoding == INTSET_ENC_INT16時, contents中以int16_t的形式存儲著數(shù)值. 類似的, 當(dāng)encoding == INTSET_ENC_INT32時, contents中以int32_t的形式存儲著數(shù)值.

但凡有一個數(shù)值元素的值超過了int32_t的取值范圍, 整個intset都要進(jìn)行升級, 即所有的數(shù)值都需要以int64_t的形式存儲. 顯然升級的開銷是很大的.

intset中的數(shù)值是以升序排列存儲的, 插入與刪除的復(fù)雜度均為O(n). 查找使用二分法, 復(fù)雜度為O(log_2(n))

intset的代碼實(shí)現(xiàn)中, 不預(yù)留空間, 即每一次插入操作都會調(diào)用zrealloc接口重新分配內(nèi)存. 每一次刪除也會調(diào)用zrealloc接口縮減占用的內(nèi)存. 省是省了, 但內(nèi)存操作的時間開銷上升了.

intset的編碼方式一經(jīng)升級, 不會再降級.

總之, intset適合于如下數(shù)據(jù)的存儲:

所有數(shù)據(jù)都位于一個穩(wěn)定的取值范圍中. 比如均位于int16_t或int32_t的取值范圍中

數(shù)據(jù)穩(wěn)定, 插入刪除操作不頻繁. 能接受O(lgn)級別的查找開銷

6、ziplist

ziplist是Redis底層數(shù)據(jù)結(jié)構(gòu)中, 最茍的一個結(jié)構(gòu). 它的設(shè)計宗旨就是: 省內(nèi)存, 從牙縫里省內(nèi)存. 設(shè)計思路和TLV一致, 但為了從牙縫里節(jié)省內(nèi)存, 做了很多額外工作.

ziplist的內(nèi)存布局與intset一樣: 就是一塊連續(xù)的內(nèi)存空間. 但區(qū)域劃分比較復(fù)雜

和intset一樣, ziplist中的所有值都是以小端序存儲的

zlbytes字段的類型是uint32_t, 這個字段中存儲的是整個ziplist所占用的內(nèi)存的字節(jié)數(shù)

zltail字段的類型是uint32_t, 它指的是ziplist中最后一個entry的偏移量. 用于快速定位最后一個entry, 以快速完成pop等操作

zllen字段的類型是uint16_t, 它指的是整個ziplit中entry的數(shù)量. 這個值只占16位, 所以蛋疼的地方就來了: 如果ziplist中entry的數(shù)目小于65535, 那么該字段中存儲的就是實(shí)際entry的值. 若等于或超過65535, 那么該字段的值固定為65535, 但實(shí)際數(shù)量需要一個個entry的去遍歷所有entry才能得到.

zlend是一個終止字節(jié), 其值為全F, 即0xff. ziplist保證任何情況下, 一個entry的首字節(jié)都不會是255

在畫圖展示entry的內(nèi)存布局之前, 先講一下entry中都存儲了哪些信息:

每個entry中存儲了它前一個entry所占用的字節(jié)數(shù). 這樣支持ziplist反向遍歷.

每個entry用單獨(dú)的一塊區(qū)域, 存儲著當(dāng)前結(jié)點(diǎn)的類型: 所謂的類型, 包括當(dāng)前結(jié)點(diǎn)存儲的數(shù)據(jù)是什么(二進(jìn)制, 還是數(shù)值), 如何編碼(如果是數(shù)值, 數(shù)值如何存儲, 如果是二進(jìn)制數(shù)據(jù), 二進(jìn)制數(shù)據(jù)的長度)最后就是真實(shí)的數(shù)據(jù)了

7、quicklist

如果說ziplist是整個Redis中為了節(jié)省內(nèi)存, 而寫的最茍的數(shù)據(jù)結(jié)構(gòu), 那么稱quicklist就是在最茍的基礎(chǔ)上, 再茍了一層. 這個結(jié)構(gòu)是Redis在3.2版本后新加的, 在3.2版本之前, 我們可以講, dict是最復(fù)雜的底層數(shù)據(jù)結(jié)構(gòu), ziplist是最茍的底層數(shù)據(jù)結(jié)構(gòu). 在3.2版本之后, 這兩個記錄被雙雙刷新了.

這是一種, 以ziplist為結(jié)點(diǎn)的, 雙端鏈表結(jié)構(gòu). 宏觀上, quicklist是一個鏈表, 微觀上, 鏈表中的每個結(jié)點(diǎn)都是一個ziplist.

它的定義與實(shí)現(xiàn)分別在src/quicklist.h與src/quicklist.c中

這里定義了五個結(jié)構(gòu)體:

quicklistNode, 宏觀上, quicklist是一個鏈表, 這個結(jié)構(gòu)描述的就是鏈表中的結(jié)點(diǎn). 它通過zl字段持有底層的ziplist. 簡單來講, 它描述了一個ziplist實(shí)例

quicklistLZF, ziplist是一段連續(xù)的內(nèi)存, 用LZ4算法壓縮后, 就可以包裝成一個quicklistLZF結(jié)構(gòu). 是否壓縮quicklist中的每個ziplist實(shí)例是一個可配置項(xiàng). 若這個配置項(xiàng)是開啟的, 那么quicklistNode.zl字段指向的就不是一個ziplist實(shí)例, 而是一個壓縮后的quicklistLZF實(shí)例

quicklist. 這就是一個雙鏈表的定義. head, tail分別指向頭尾指針. len代表鏈表中的結(jié)點(diǎn). count指的是整個quicklist中的所有ziplist中的entry的數(shù)目. fill字段影響著每個鏈表結(jié)點(diǎn)中ziplist的最大占用空間, compress影響著是否要對每個ziplist以LZ4算法進(jìn)行進(jìn)一步壓縮以更節(jié)省內(nèi)存空間.

quicklistIter是一個迭代器

quicklistEntry是對ziplist中的entry概念的封裝. quicklist作為一個封裝良好的數(shù)據(jù)結(jié)構(gòu), 不希望使用者感知到其內(nèi)部的實(shí)現(xiàn), 所以需要把ziplist.entry的概念重新包裝一下.

quicklist的內(nèi)存布局圖如下所示:

下面是有關(guān)quicklist的更多額外信息:

quicklist.fill的值影響著每個鏈表結(jié)點(diǎn)中, ziplist的長度.

當(dāng)數(shù)值為負(fù)數(shù)時, 代表以字節(jié)數(shù)限制單個ziplist的最大長度. 具體為:

-1 不超過4kb

-2 不超過 8kb

-3 不超過 16kb

-4 不超過 32kb

-5 不超過 64kb

當(dāng)數(shù)值為正數(shù)時, 代表以entry數(shù)目限制單個ziplist的長度. 值即為數(shù)目. 由于該字段僅占16位, 所以以entry數(shù)目限制ziplist的容量時, 最大值為2^15個

quicklist.compress的值影響著quicklistNode.zl字段指向的是原生的ziplist, 還是經(jīng)過壓縮包裝后的quicklistLZF

0 表示不壓縮, zl字段直接指向ziplist

1 表示quicklist的鏈表頭尾結(jié)點(diǎn)不壓縮, 其余結(jié)點(diǎn)的zl字段指向的是經(jīng)過壓縮后的quicklistLZF

2 表示quicklist的鏈表頭兩個, 與末兩個結(jié)點(diǎn)不壓縮, 其余結(jié)點(diǎn)的zl字段指向的是經(jīng)過壓縮后的quicklistLZF

以此類推, 最大值為2^16

quicklistNode.encoding字段, 以指示本鏈表結(jié)點(diǎn)所持有的ziplist是否經(jīng)過了壓縮. 1代表未壓縮, 持有的是原生的ziplist, 2代表壓縮過

quicklistNode.container字段指示的是每個鏈表結(jié)點(diǎn)所持有的數(shù)據(jù)類型是什么. 默認(rèn)的實(shí)現(xiàn)是ziplist, 對應(yīng)的該字段的值是2, 目前Redis沒有提供其它實(shí)現(xiàn). 所以實(shí)際上, 該字段的值恒為2

quicklistNode.recompress字段指示的是當(dāng)前結(jié)點(diǎn)所持有的ziplist是否經(jīng)過了解壓. 如果該字段為1即代表之前被解壓過, 且需要在下一次操作時重新壓縮.

quicklist的具體實(shí)現(xiàn)代碼篇幅很長, 這里就不貼代碼片斷了, 從內(nèi)存布局上也能看出來, 由于每個結(jié)點(diǎn)持有的ziplist是有上限長度的, 所以在與操作時要考慮的分支情況比較多. 想想都蛋疼.

quicklist有自己的優(yōu)點(diǎn), 也有缺點(diǎn), 對于使用者來說, 其使用體驗(yàn)類似于線性數(shù)據(jù)結(jié)構(gòu), list作為最傳統(tǒng)的雙鏈表, 結(jié)點(diǎn)通過指針持有數(shù)據(jù), 指針字段會耗費(fèi)大量內(nèi)存. ziplist解決了耗費(fèi)內(nèi)存這個問題. 但引入了新的問題: 每次寫操作整個ziplist的內(nèi)存都需要重分配. quicklist在兩者之間做了一個平衡. 并且使用者可以通過自定義quicklist.fill, 根據(jù)實(shí)際業(yè)務(wù)情況, 經(jīng)驗(yàn)主義調(diào)參.

8、zipmap

dict作為字典結(jié)構(gòu), 優(yōu)點(diǎn)很多, 擴(kuò)展性強(qiáng)悍, 支持平滑擴(kuò)容等等, 但對于字典中的鍵值均為二進(jìn)制數(shù)據(jù), 且長度都很小時, dict的中的一坨指針會浪費(fèi)不少內(nèi)存, 因此Redis又實(shí)現(xiàn)了一個輕量級的字典, 即為zipmap.

zipmap適合使用的場合是:

鍵值對量不大, 單個鍵, 單個值長度小

鍵值均是二進(jìn)制數(shù)據(jù), 而不是復(fù)合結(jié)構(gòu)或復(fù)雜結(jié)構(gòu). dict支持各種嵌套, 字典本身并不持有數(shù)據(jù), 而僅持有數(shù)據(jù)的指針. 但zipmap是直接持有數(shù)據(jù)的.

zipmap的定義與實(shí)現(xiàn)在src/zipmap.h與src/zipmap.c兩個文件中, 其定義與實(shí)現(xiàn)均未定義任何struct結(jié)構(gòu)體, 因?yàn)閦ipmap的內(nèi)存布局就是一塊連續(xù)的內(nèi)存空間. 其內(nèi)存布局如下所示:

zipmap起始的第一個字節(jié)存儲的是zipmap中鍵值對的個數(shù). 如果鍵值對的個數(shù)大于254的話, 那么這個字節(jié)的值就是固定值254, 真實(shí)的鍵值對個數(shù)需要遍歷才能獲得.

zipmap的最后一個字節(jié)是固定值0xFF

zipmap中的每一個鍵值對, 稱為一個entry, 其內(nèi)存占用如上圖, 分別六部分:

len_of_key, 一字節(jié)或五字節(jié). 存儲的是鍵的二進(jìn)制長度. 如果長度小于254, 則用1字節(jié)存儲, 否則用五個字節(jié)存儲, 第一個字節(jié)的值固定為0xFE, 后四個字節(jié)以小端序uint32_t類型存儲著鍵的二進(jìn)制長度.

key_data為鍵的數(shù)據(jù)

len_of_val, 一字節(jié)或五字節(jié), 存儲的是值的二進(jìn)制長度. 編碼方式同len_of_key

len_of_free, 固定值1字節(jié), 存儲的是entry中未使用的空間的字節(jié)數(shù). 未使用的空間即為圖中的free, 它一般是由于鍵值對中的值被替換發(fā)生的. 比如, 鍵值對hello <-> word被修改為hello <-> w后, 就空了四個字節(jié)的閑置空間

val_data, 為值的數(shù)據(jù)

free, 為閑置空間. 由于len_of_free的值最大只能是254, 所以如果值的變更導(dǎo)致閑置空間大于254的話, zipmap就會回收內(nèi)存空間.