點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”

優(yōu)質(zhì)文章，第一時(shí)間送達(dá)

? 作者?|??原野漫步?

來(lái)源 |? urlify.cn/3eyMFv

數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)

相信大家對(duì) redis 的數(shù)據(jù)結(jié)構(gòu)都比較熟悉：

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

為了將性能優(yōu)化到極致，redis 作者為每種數(shù)據(jù)結(jié)構(gòu)提供了不同的實(shí)現(xiàn)方式，以適應(yīng)特定應(yīng)用場(chǎng)景。
以最常用的 string 為例，其底層實(shí)現(xiàn)就可以分為 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"

這些特定的底層實(shí)現(xiàn)在 redis 中被稱為?編碼encoding，下面逐一介紹這些編碼實(shí)現(xiàn)。

string

redis 中所有的 key 都是字符串，這些字符串是通過(guò)一個(gè)名為?簡(jiǎn)單動(dòng)態(tài)字符串SDS的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。

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

????struct?sdshdr??{?//?SDS?header，[?]?可以為?8,?16,?32,?64
????????uint?_t?len;??????????//?已用空間，字符串的實(shí)際長(zhǎng)度
????????uint?_t?alloc;????????//?已分配空間，不包含'\0'
????????unsigned?char?flags;??//?類型標(biāo)記，指明了?len?與?alloc?的實(shí)際類型，可以通過(guò)?sds[-1]?獲取
????????char?buf[];???????????//?字符數(shù)組，保存以'\0'結(jié)尾的字符串，與傳統(tǒng)?C?語(yǔ)言中的字符串的表達(dá)方式保持一致
????};

內(nèi)存布局如下：

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

相較于傳統(tǒng)的 C 字符串，其優(yōu)點(diǎn)如下：

高效：記錄了已用空間，獲取字符串長(zhǎng)度的操作為O(1)
安全：記錄了空閑空間，可以避免寫緩沖區(qū)越界的問(wèn)題
內(nèi)存友好：通過(guò)記錄了空間信息，可以預(yù)分配空間，實(shí)現(xiàn)惰性刪除，減少內(nèi)存分配的同時(shí)不會(huì)造成內(nèi)存泄露
二進(jìn)制安全：字符串內(nèi)容可以為非 ASCII 編碼，任意數(shù)據(jù)都能被編碼為二進(jìn)制字符串
兼容 C 字符串：可以復(fù)用部分 C 標(biāo)準(zhǔn)庫(kù)代碼，避免無(wú)用重復(fù)

list

redis 中 list 的底層實(shí)現(xiàn)之一是雙向鏈表，該結(jié)構(gòu)支持順序訪問(wèn)，并提供了高效的元素增刪功能。

????typedef?struct?listNode?{
????????struct?listNode?*prev;?//?前置節(jié)點(diǎn)
????????struct?listNode?*next;?//?后置節(jié)點(diǎn)
????????void?*value;???????????//?節(jié)點(diǎn)值
????}?listNode;

????typedef?struct?list?{
????????listNode?*head;?//?頭節(jié)點(diǎn)
????????listNode?*tail;?//?尾節(jié)點(diǎn)
????????unsigned?long?len;?????//?列表長(zhǎng)度
????????void?*(*dup)?(void?*ptr);?//?節(jié)點(diǎn)值復(fù)制函數(shù)
????????void?(*free)?(void?*ptr);?//?節(jié)點(diǎn)值釋放函數(shù)
????????int?(*match)?(void?*ptr);?//?節(jié)點(diǎn)值比較函數(shù)
????}?list;

這里使用了函數(shù)指針來(lái)實(shí)現(xiàn)動(dòng)態(tài)綁定，根據(jù) value 類型，指定不同?dup,?free,?match?的函數(shù)，實(shí)現(xiàn)多態(tài)。

該數(shù)據(jù)結(jié)構(gòu)有以下特征：

有長(zhǎng)：獲取列表長(zhǎng)度的操作為O(1)
雙端：可以同時(shí)支持正向和逆向遍歷，獲取前后位置的節(jié)點(diǎn)復(fù)雜度為O(1)
無(wú)環(huán)：沒(méi)有設(shè)置哨兵節(jié)點(diǎn)，列表為空時(shí)，表頭表尾均為 NULL
多態(tài)：通過(guò)函數(shù)指針實(shí)現(xiàn)多態(tài)，數(shù)據(jù)結(jié)構(gòu)可以復(fù)用

dict

redis 中使用 dict 來(lái)保存鍵值對(duì)，其底層實(shí)現(xiàn)之一是哈希表。

????typedef?struct?dictEntry?{
????????void*?key;??//?鍵
????????union?{?????//?值，可以為指針、有符號(hào)長(zhǎng)整，無(wú)符號(hào)長(zhǎng)整，雙精度浮點(diǎn)
????????????void?*val;
????????????uint64_t?u64;
????????????int64_t?s64;
????????????double?d;
????????}?v;
????????struct?dictEntry?*next;
????}?dictEntry;

????typedef?struct?dictht?{
????????dictEntry?**table;??????//?哈希表數(shù)組，數(shù)組中的每個(gè)元素是一個(gè)單向鏈表
????????unsigned?long?size;?????//?哈希表數(shù)組大小
????????unsigned?long?sizemask;?//?哈希掩碼，用于計(jì)算索引
????????unsigned?long?used;?????//?已有節(jié)點(diǎn)數(shù)量
????}?dictht;

????typedef?struct?dictType?{
????????unsigned?int?(*hashFunction)?(const?void?*key);?????????????//?哈希函數(shù)，用于計(jì)算哈希值
????????int?(*keyCompare)(void?*privdata,?const?void?*key1,?const?void?*key2);?//?鍵比較函數(shù)
????????void?*(*keyDup)(void?*privdata,?const?void?*key);???????????//?鍵復(fù)制函數(shù)
????????void?*(*valDup)(void?*privdata,?const?void?*obj);???????????//?值復(fù)制函數(shù)
????????void?*(*keyDestructor)(void?*privdata,?const?void?*key);????//?鍵銷毀函數(shù)
????????void?*(*valDestructor)(void?*privdata,?const?void?*obj);????//?值銷毀函數(shù)
????}?dictType;

????typedef?struct?dict?{
????????dictType?*type;?????//?類型函數(shù)，用于實(shí)現(xiàn)多態(tài)
????????void?*privdata;?????//?私有數(shù)據(jù)，用于實(shí)現(xiàn)多態(tài)
????????dictht?ht[2];???????//?哈希表，字典使用?ht[0]?作為哈希表，ht[1]?用于進(jìn)行?rehash
????????int?rehashidx;??????//?rehash索引，當(dāng)沒(méi)有執(zhí)行?rehash?時(shí)，其值為?-1
????}?dict;

該數(shù)據(jù)結(jié)構(gòu)有以下特征：

哈希算法：使用 murmurhash2 作為哈希函數(shù)，時(shí)間復(fù)雜度為O(1)
沖突解決：使用鏈地址法解決沖突，新增元素會(huì)被放到表頭，時(shí)間復(fù)雜度為O(1)
重新散列：每次 rehash 操作都會(huì)分成 3 步完成
步驟1：為dict.ht[1]分配空間，其大小為 2 的 n 次方冪
步驟2：將dict.ht[0]中的所有鍵值對(duì) rehash 到dict.ht[1]上
步驟3：釋放dict.ht[0]的空間，用dict.ht[1]替換?dict.ht[0]

rehash 的一些細(xì)節(jié)

分?jǐn)傞_銷
為了減少停頓，步驟2?會(huì)分為多次漸進(jìn)完成，將 rehash 鍵值對(duì)所需的計(jì)算工作，平均分?jǐn)偟矫總€(gè)字典的增加、刪除、查找、更新操作，期間會(huì)使用dict.rehashidx記錄dict.ht[0]中已經(jīng)完成 rehash 操作的dictht.table索引：

每執(zhí)行一次 rehash 操作，dict.rehashidx計(jì)數(shù)器會(huì)加 1
當(dāng) rehash 完成后，dict.rehashidx會(huì)被設(shè)置為 -1

觸發(fā)條件
計(jì)算當(dāng)前負(fù)載因子：loader_factor = ht[0].used / ht[0].size
收縮：?當(dāng) loader_factor < 0.1 時(shí)，執(zhí)行 rehash 回收空閑空間
擴(kuò)展：
大多操作系統(tǒng)都采用了?寫時(shí)復(fù)制copy-on-write技術(shù)來(lái)優(yōu)化子進(jìn)程的效率：
父子進(jìn)程共享同一份數(shù)據(jù)，直到數(shù)據(jù)被修改時(shí)，才實(shí)際拷貝內(nèi)存空間給子進(jìn)程，保證數(shù)據(jù)隔離
在執(zhí)行?BGSAVE?或?BGREWRITEAOF?命令時(shí)，redis 會(huì)創(chuàng)建子進(jìn)程，此時(shí)服務(wù)器會(huì)通過(guò)增加 loader_factor 的閾值，避免在子進(jìn)程存在期間執(zhí)行不必要的內(nèi)存寫操作，節(jié)約內(nèi)存

沒(méi)有執(zhí)行?BGSAVE?或?BGREWRITEAOF?命令，loader_factor >= 1 執(zhí)行 rehash
正在執(zhí)行?BGSAVE?或?BGREWRITEAOF?命令，loader_factor >= 5 執(zhí)行 rehash

skiplist

跳表是一種有序數(shù)據(jù)結(jié)構(gòu)，并且通過(guò)維持多層級(jí)指針來(lái)達(dá)到快速訪問(wèn)的目的，是典型的空間換時(shí)間策略。
其查找效率與平衡樹相近，但是維護(hù)成本更低，且實(shí)現(xiàn)簡(jiǎn)單。

????typedef?struct?zskiplistNode?{
????????sds?ele;????????????????????????//?成員對(duì)象
????????double?score;???????????????????//?分值
????????struct?zskiplistNode?*backward;?//?后退指針
????????struct?zskiplistLevel?{
????????????struct?zskiplistNode?*forward;??//?前進(jìn)指針
????????????unsigned?long?span;?????????????//?跨度，當(dāng)前節(jié)點(diǎn)和前進(jìn)節(jié)點(diǎn)之間的距離
????????}?level[];
????}?zskiplistNode;

????typedef?struct?zskiplist?{
????????struct?zskiplistNode?*header,?*tail;//?頭尾指針
????????unsigned?long?length;???????????????//?長(zhǎng)度
????????int?level;??????????????????????????//?最大層級(jí)
????}?zskiplist;

該數(shù)據(jù)結(jié)構(gòu)有以下特征：

查找：平均查找時(shí)間為O(logN)，最壞查找時(shí)間為O(N)，并且支持范圍查找
概率：每次創(chuàng)建節(jié)點(diǎn)的時(shí)候，程序根據(jù)冪次定律隨機(jī)生成一個(gè) 1 至 32 之間的隨機(jī)數(shù)，用于決定層高
排位：在查找節(jié)點(diǎn)的過(guò)程中，沿途訪問(wèn)過(guò)所有的跨度 span 累計(jì)起來(lái)，得到目標(biāo)節(jié)點(diǎn)在表中的排位

intset

有序整型集合，具有緊湊的存儲(chǔ)空間，添加操作的時(shí)間復(fù)雜度為O(N)。

????typedef?struct?intset?{
????????uint32_t?encoding;??//?編碼方式，指示元素的實(shí)際類型
????????uint32_t?length;????//?元素?cái)?shù)量
????????int8_t?contents[];??//?元素?cái)?shù)組，元素實(shí)際類型可能為?int16_t,int32_t,int64_t,
????}?intset;

該數(shù)據(jù)結(jié)構(gòu)有以下特征：

有序：元素?cái)?shù)組中的元素按照從小到大排列，使用二分查找時(shí)間復(fù)雜度為O(logN)
升級(jí)：當(dāng)有新元素加入集合，且新元素比所有現(xiàn)有元素類型都長(zhǎng)時(shí)，集合需要進(jìn)行升級(jí)：
步驟1：根據(jù)新元素的類型，擴(kuò)展元素?cái)?shù)組空間
步驟2：將現(xiàn)有元素都轉(zhuǎn)換為新類型
步驟3：將新元素添加到數(shù)組中

ziplist

壓縮列表是為了節(jié)約內(nèi)存而開發(fā)的，是存儲(chǔ)在連續(xù)內(nèi)存塊上的順序數(shù)據(jù)結(jié)構(gòu)。
一個(gè)壓縮列表可以包含任意多的 entry 節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含一個(gè)字節(jié)數(shù)組或整數(shù)。
redis 中并沒(méi)有顯式定義 ziplist 的數(shù)據(jù)結(jié)構(gòu)，僅僅提供了一個(gè)描述結(jié)構(gòu) zlentry 用于操作數(shù)據(jù)。

????typedef?struct?zlentry?{
????????unsigned?int?prevrawlensize;//?用于記錄前一個(gè)?entry?長(zhǎng)度的字節(jié)數(shù)
????????unsigned?int?prevrawlen;????//?前一個(gè)?entry?的長(zhǎng)度
????????unsigned?int?lensize????????//?用于記錄當(dāng)前?entry?類型/長(zhǎng)度的字節(jié)數(shù)
????????unsigned?int?len;???????????//?實(shí)際用于存儲(chǔ)數(shù)據(jù)的字節(jié)數(shù)
????????unsigned?int?headersize;????//?prevrawlensize?+?lensize
????????unsigned?char?encoding;?????//?用于指示?entry?數(shù)據(jù)的實(shí)際編碼類型
????????unsigned?char?*p;???????????//?指向?entry?的開頭
????}?zlentry;

其實(shí)際的內(nèi)存布局如下：

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

zlbytes?: 壓縮列表占用的字節(jié)數(shù) (u_int32)
zltail?: 壓縮列表表尾偏移量，無(wú)需遍歷即可確定表尾地址，方便反向遍歷 (u_int32)
zllen?: 壓縮列表節(jié)點(diǎn)數(shù)量，當(dāng)節(jié)點(diǎn)數(shù)量大于 65535 時(shí)，具體數(shù)量需要通過(guò)遍歷得出 (u_int16)
entryX?: 列表節(jié)點(diǎn)，具體長(zhǎng)度不定
zlend?: 列表末端，特殊值 0xFF (u_int8)

entry 的內(nèi)存布局如下：

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

prev_entry_length?: 前一個(gè)節(jié)點(diǎn)的長(zhǎng)度，可以根據(jù)當(dāng)前節(jié)點(diǎn)的起始地址，計(jì)算前一個(gè)節(jié)點(diǎn)的起始地址（變長(zhǎng)：1字節(jié)/5字節(jié)）
encoding?: 節(jié)點(diǎn)保存數(shù)據(jù)的類型和長(zhǎng)度（變長(zhǎng)：1字節(jié)/2字節(jié)/5字節(jié)）
content?: 節(jié)點(diǎn)保存的數(shù)據(jù)，可以保存整數(shù)或者字節(jié)數(shù)組

該數(shù)據(jù)結(jié)構(gòu)具有以下特征：

結(jié)構(gòu)緊湊：一整塊連續(xù)內(nèi)存，沒(méi)有多余的內(nèi)存碎片，更新會(huì)導(dǎo)致內(nèi)存 realloc 與內(nèi)存復(fù)制，平均時(shí)間復(fù)雜度為?O(N)
逆向遍歷：從表尾開始向表頭進(jìn)行遍歷
連鎖更新：對(duì)前一條數(shù)據(jù)的更新，可能導(dǎo)致后一條數(shù)據(jù)的 prev_entry_length 與 encoding 所需長(zhǎng)度變化，產(chǎn)生連鎖反應(yīng)，更新操作最壞時(shí)間為?O(N²)

quicklist

在較早版本的 redis 中，list 有兩種底層實(shí)現(xiàn)：

當(dāng)列表對(duì)象中元素的長(zhǎng)度比較小或者數(shù)量比較少的時(shí)候，采用壓縮列表 ziplist 來(lái)存儲(chǔ)
當(dāng)列表對(duì)象中元素的長(zhǎng)度比較大或者數(shù)量比較多的時(shí)候，則會(huì)轉(zhuǎn)而使用雙向列表 linkedlist 來(lái)存儲(chǔ)

兩者各有優(yōu)缺點(diǎn)：

ziplist 的優(yōu)點(diǎn)是內(nèi)存緊湊，訪問(wèn)效率高，缺點(diǎn)是更新效率低，并且數(shù)據(jù)量較大時(shí)，可能導(dǎo)致大量的內(nèi)存復(fù)制
linkedlist 的優(yōu)點(diǎn)是節(jié)點(diǎn)修改的效率高，但是需要額外的內(nèi)存開銷，并且節(jié)點(diǎn)較多時(shí)，會(huì)產(chǎn)生大量的內(nèi)存碎片

為了結(jié)合兩者的優(yōu)點(diǎn)，在 redis 3.2 之后，list 的底層實(shí)現(xiàn)變?yōu)榭焖倭斜?quicklist。
快速列表是 linkedlist 與 ziplist 的結(jié)合: quicklist 包含多個(gè)內(nèi)存不連續(xù)的節(jié)點(diǎn)，但每個(gè)節(jié)點(diǎn)本身就是一個(gè) ziplist。

????typedef?struct?quicklistNode?{
????????struct?quicklistNode?*prev;??//?上一個(gè)?ziplist?
????????struct?quicklistNode?*next;??//?下一個(gè)?ziplist?
????????unsigned?char?*zl;???????????//?數(shù)據(jù)指針，指向?ziplist?結(jié)構(gòu)，或者?quicklistLZF?結(jié)構(gòu)
????????unsigned?int?sz;?????????????//?ziplist?占用內(nèi)存長(zhǎng)度（未壓縮）
????????unsigned?int?count?:?16;?????//?ziplist?記錄數(shù)量
????????unsigned?int?encoding?:?2;???//?編碼方式，1?表示?ziplist?，2?表示?quicklistLZF
????????unsigned?int?container?:?2;??//?
????????unsigned?int?recompress?:?1;?????????//?臨時(shí)解壓，1?表示該節(jié)點(diǎn)臨時(shí)解壓用于訪問(wèn)
????????unsigned?int?attempted_compress?:?1;?//?測(cè)試字段
????????unsigned?int?extra?:?10;?????????????//?預(yù)留空間
????}?quicklistNode;

????typedef?struct?quicklistLZF?{
????????unsigned?int?sz;????//?壓縮數(shù)據(jù)長(zhǎng)度
????????char?compressed[];??//?壓縮數(shù)據(jù)
????}?quicklistLZF;

????typedef?struct?quicklist?{
????????quicklistNode?*head;????????//?列表頭部
????????quicklistNode?*tail;????????//?列表尾部
????????unsigned?long?count;????????//?記錄總數(shù)
????????unsigned?long?len;??????????//?ziplist?數(shù)量
????????int?fill?:?16;??????????????//?ziplist?長(zhǎng)度限制，每個(gè)?ziplist?節(jié)點(diǎn)的長(zhǎng)度（記錄數(shù)量/內(nèi)存占用）不能超過(guò)這個(gè)值
????????unsigned?int?compress?:?16;?//?壓縮深度，表示?quicklist?兩端不壓縮的?ziplist?節(jié)點(diǎn)的個(gè)數(shù)，為?0?表示所有?ziplist?節(jié)點(diǎn)都不壓縮
????}?quicklist;

該數(shù)據(jù)結(jié)構(gòu)有以下特征：

無(wú)縫切換：結(jié)合了 linkedlist 與 ziplist 的優(yōu)點(diǎn)，無(wú)需在兩種結(jié)構(gòu)之間進(jìn)行切換
中間壓縮：作為隊(duì)列使用的場(chǎng)景下，list 中間的數(shù)據(jù)被訪問(wèn)的頻率比較低，可以選擇進(jìn)行壓縮以減少內(nèi)存占用

robj

為了實(shí)現(xiàn)動(dòng)態(tài)編碼技術(shù)，redis 構(gòu)建了一個(gè)對(duì)象系統(tǒng)。
redis 可以在執(zhí)行命令前，根據(jù)對(duì)象類型判斷當(dāng)前命令是否能夠執(zhí)行。
此外，該系統(tǒng)通過(guò)引用計(jì)數(shù)實(shí)現(xiàn)內(nèi)存共享，并記錄來(lái)對(duì)象訪問(wèn)時(shí)間，為優(yōu)化內(nèi)存回收策略提供了依據(jù)。

????typedef?struct?redisObject?{
????????unsigned?type:4;????????//?類型，當(dāng)前對(duì)象的邏輯類型，例如：set
??????? unsigned encoding:4;????//?編碼，底層實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，例如：intset / ziplist
????????unsigned?lru:24;????????/*?LRU?時(shí)間?(相對(duì)與全局?lru_clock?的時(shí)間)?或
?????????????????????????????????*?LFU?數(shù)據(jù)?(8bits?記錄訪問(wèn)頻率，16?bits?記錄訪問(wèn)時(shí)間).?*/
????????int?refcount;???????????//?引用計(jì)數(shù)
????????void?*ptr;??????????????//?數(shù)據(jù)指針，指向具體的數(shù)據(jù)結(jié)構(gòu)
????}?robj;

該數(shù)據(jù)結(jié)構(gòu)有以下特征：

高效：同個(gè)類型的 redis 對(duì)象可以使用不同的底層實(shí)現(xiàn)，可以在不同的應(yīng)用場(chǎng)景上優(yōu)化對(duì)象的使用效率
節(jié)約內(nèi)存：對(duì)于整數(shù)值的內(nèi)存字符串對(duì)象，redis 可以通過(guò)記錄引用計(jì)數(shù)來(lái)減少內(nèi)存復(fù)制
空轉(zhuǎn)時(shí)長(zhǎng)：對(duì)象系統(tǒng)會(huì)記錄對(duì)象的訪問(wèn)時(shí)間，方便 LRU 算法優(yōu)先回收較少使用的對(duì)象

編碼格式

string 類型

string 的編碼類型可能為：

OBJ_ENCODING_INT?int：long 類型整數(shù)
OBJ_ENCODING_RAW?raw：sds 字符串
OBJ_ENCODING_EMBSTR?embstr：嵌入式字符串（編碼后長(zhǎng)度小于 44 字節(jié)的字符串）

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?編碼是為了減少短字符串的內(nèi)存分配次數(shù)，參考 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.

對(duì)比兩者內(nèi)存布局可以發(fā)現(xiàn)：

embstr?是一個(gè)完整連續(xù)的內(nèi)存塊，只需要 1 次內(nèi)存分配
raw?的內(nèi)存是不連續(xù)的，需要申請(qǐng) 2 次內(nèi)存


<------------------------------------------?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 默認(rèn)的編碼類型為?OBJ_ENCODING_QUICKLIST?quicklist

list-max-ziplist-size：每個(gè) quicklist 節(jié)點(diǎn)上的 ziplist 長(zhǎng)度
list-compress-depth：quicklist 兩端不壓縮的節(jié)點(diǎn)數(shù)目

hash 類型

hash 的編碼類型有?OBJ_ENCODING_ZIPLIST?ziplist?與?OBJ_ENCODING_HT?hashtable，具體使用哪種編碼受下面兩個(gè)選項(xiàng)控制：

hash-max-ziplist-value：當(dāng) key 與 value 的長(zhǎng)度都小于該值時(shí)使用 ziplist 編碼（默認(rèn)為 64）
hash-max-ziplist-entries：當(dāng) hash 中的元素?cái)?shù)量小于該值時(shí)使用 ziplist 編碼（默認(rèn)為 512）

key 長(zhǎng)度超過(guò) 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 長(zhǎng)度超過(guò) 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"

元素?cái)?shù)量度超過(guò) 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，具體使用哪種編碼受下面兩個(gè)選項(xiàng)控制：

當(dāng) set 中的所有元素都是整數(shù)時(shí)考慮使用 intset 編碼，否則只能使用 hashtable 編碼
set-max-intset-entries：當(dāng) set 中的元素?cái)?shù)量小于該值時(shí)使用 intset 編碼（默認(rèn)為 512）

包含非整數(shù)元素的情況：

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"

元素?cái)?shù)量度超過(guò) 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 編碼時(shí)，每個(gè)集合元素使用兩個(gè)相鄰的 entry 節(jié)點(diǎn)保存，第一個(gè)節(jié)點(diǎn)保存成員值 member，第二節(jié)點(diǎn)保存元素的分值 score，并且 entry 按照 score 從小到大進(jìn)行排序：

+----------------------+
|?????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 實(shí)現(xiàn)時(shí)，使用會(huì)使用一個(gè)名為 zset 的數(shù)據(jù)結(jié)構(gòu)：

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


+----------------------+???????????????????????????????????????+--------+?????+------------+????+---------+
|?????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 具體使用哪種編碼受下面兩個(gè)選項(xiàng)控制：

zset-max-ziplist-value：當(dāng) member 的長(zhǎng)度都小于該值時(shí)使用 ziplist 編碼（默認(rèn)為 64）
zset-max-ziplist-entries：當(dāng) zset 中的元素?cái)?shù)量小于該值時(shí)使用 ziplist 編碼（默認(rèn)為 128)

Redis 整體結(jié)構(gòu)

每個(gè)數(shù)據(jù)庫(kù)都是一個(gè) redisDb 結(jié)構(gòu)體：

????typedef?struct?redisDb?{
????????dict?*dict;?????????????????/*?據(jù)庫(kù)的鍵空間?keyspace?*/
????????dict?*expires;??????????????/*?設(shè)置了過(guò)期時(shí)間的?key?集合?*/
????????dict?*blocking_keys;????????/*?客戶端阻塞等待的?key?集合?(BLPOP)*/
????????dict?*ready_keys;???????????/*?已就緒的阻塞?key?集合?(PUSH)?*/
????????dict?*watched_keys;?????????/*?在事務(wù)中監(jiān)控受監(jiān)控的?key?集合?*/
????????int?id;?????????????????????/*?數(shù)據(jù)庫(kù)?ID?*/
????????long?long?avg_ttl;??????????/*?平均?TTL,?just?for?stats?*/
????????unsigned?long?expires_cursor;?/*?過(guò)期檢測(cè)指針?*/
????????list?*defrag_later;?????????/*?內(nèi)存碎片回收列表?*/
????}?redisDb;

redis 所有數(shù)據(jù)庫(kù)都保存著 redisServer.db 數(shù)組中，redisServer.dbnum 保存了數(shù)據(jù)庫(kù)的數(shù)量，簡(jiǎn)化后的內(nèi)存布局大致如下：

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

至此，redis 的幾種編碼方式都介紹完畢，后續(xù)將對(duì) redis 的一些其他細(xì)節(jié)進(jìn)行分享，感謝觀看。

粉絲福利：實(shí)戰(zhàn)springboot+CAS單點(diǎn)登錄系統(tǒng)視頻教程免費(fèi)領(lǐng)取

???

?長(zhǎng)按上方微信二維碼?2 秒
即可獲取資料

感謝點(diǎn)贊支持下哈?

Redis 數(shù)據(jù)結(jié)構(gòu)與對(duì)象編碼 (Object Encoding)

數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)

string

list

dict

rehash 的一些細(xì)節(jié)

skiplist

intset

ziplist

quicklist

robj

編碼格式

string 類型

list 類型

hash 類型

set 類型

zset 類型

Redis 整體結(jié)構(gòu)