不要虛度每一天，你的經(jīng)驗(yàn)就是這樣積累出來(lái)，然后用在了你的事情上面。
一：摘要概述
很多 redis 的使用者都可以清晰明白的道出Redis中常用的對(duì)象如string、list、hash、set、zset,一些場(chǎng)景比較豐富的使用者可能會(huì)說(shuō)布隆過(guò)濾器、geo、Hash等。但是對(duì)于這些對(duì)象底層實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)卻是知之甚少,將會(huì)詳細(xì)闡述redis中的底層數(shù)據(jù)結(jié)構(gòu)。為了彌補(bǔ)大家的創(chuàng)傷，今天分享Redis底層數(shù)據(jù)結(jié)構(gòu)內(nèi)容。
二：SDS
string作為redis中常用對(duì)象之一,普遍用于用戶信息緩存等場(chǎng)景。當(dāng)string對(duì)象中encoding編碼為embstr或raw時(shí)都是采用sds作為其底層實(shí)現(xiàn)
2.1 SDS結(jié)構(gòu)
源碼文件位于redis安裝目錄src下的sds.h,sds聲明了五種頭部類型,分別為sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。根據(jù)字符串長(zhǎng)度創(chuàng)建不同頭部的sds實(shí)例
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
};
屬性名稱作用含義
len字符串長(zhǎng)度
alloc預(yù)分配空間大小
flags低三位用于表示sds類型,可以查看sds.h文件76-82行定義
buf[]存儲(chǔ)字符串用數(shù)組
2.2 SDS與C字符串區(qū)別
區(qū)別描述
長(zhǎng)度計(jì)算 c中的字符串長(zhǎng)度計(jì)算需要數(shù)組遍歷,但是redis中的sds自身維護(hù)了len屬性。所以O(shè)(1)時(shí)間復(fù)雜度即可
緩沖區(qū)溢出c中字符串更改如果未提前做好內(nèi)存分配則會(huì)內(nèi)存溢出,但是sds則會(huì)根據(jù)alloc與len計(jì)算預(yù)留內(nèi)存是否足夠分配重新申請(qǐng)內(nèi)存
動(dòng)態(tài)擴(kuò)展 緩沖區(qū)溢出已經(jīng)闡述這個(gè)概念,sds的內(nèi)存空間會(huì)在字符串內(nèi)容變更時(shí)自動(dòng)擴(kuò)展計(jì)算。策略為當(dāng)字符換小于1M時(shí)*2翻倍,大于1M時(shí)每次擴(kuò)容1M
惰性釋放 與空間預(yù)分配相似操作的還有內(nèi)存惰性釋放,即字符串刪除某些內(nèi)容后所占用的內(nèi)存空間并不會(huì)立即釋放,后續(xù)字符串變更擴(kuò)展就無(wú)需再申請(qǐng)內(nèi)存
二：ZipList
ziplist可以說(shuō)把redis對(duì)于內(nèi)存的極致操作體現(xiàn)的淋漓盡致,鏈表除了節(jié)點(diǎn)值之外還需要維護(hù)前后節(jié)點(diǎn)兩個(gè)指針,并且還會(huì)造成內(nèi)存碎片。壓縮列表緊湊的內(nèi)存布局,所有節(jié)點(diǎn)都維護(hù)在整塊內(nèi)存中處理
2.1 ZipList結(jié)構(gòu)
屬性名稱作用含義
zlbytes列表健占用內(nèi)存的總字節(jié)數(shù),在對(duì)列表健內(nèi)存重分配或者是計(jì)算zlend的時(shí)候使用
zltail 指向壓縮列表起始地址的指針
zllen 壓縮列表的節(jié)點(diǎn)數(shù)量
entry壓縮列表保存的節(jié)點(diǎn)數(shù)據(jù)
zlend壓縮列表的尾節(jié)點(diǎn)
2.2 Entry節(jié)點(diǎn)結(jié)構(gòu)
屬性名稱作用含義
previous_entry_length 字節(jié)為單位記錄上一個(gè)節(jié)點(diǎn)的長(zhǎng)度,如果上一個(gè)字節(jié)長(zhǎng)度小于254占用1字節(jié)。大于254占用5字節(jié),第一個(gè)字節(jié)設(shè)置為OxFE(十進(jìn)制254),后面四個(gè)字節(jié)儲(chǔ)存長(zhǎng)度
encoding 記錄content記錄的數(shù)據(jù)類型以及長(zhǎng)度。長(zhǎng)度一、二、五字節(jié),值的最高位為00、01、10表示類型為字節(jié)數(shù)組,長(zhǎng)度使用除去最高位的其它位記錄。11開頭表示儲(chǔ)存整數(shù),除去最高位其他位置表示content數(shù)據(jù)長(zhǎng)度
content 記錄壓縮列表記錄的數(shù)據(jù)
2.3 連鎖更新
一個(gè)壓縮列表節(jié)點(diǎn)在保存上一個(gè)節(jié)點(diǎn)長(zhǎng)度使用previous_entry_length屬性,這個(gè)屬性可以使用1字節(jié)或者是5字節(jié)。假設(shè)現(xiàn)有一個(gè)壓縮列表里面保存的節(jié)點(diǎn)長(zhǎng)度全部都是250-253,這時(shí)候previous_entry_length使用一字節(jié)記錄就行。但是這時(shí)候添加一個(gè)新節(jié)點(diǎn)到頭節(jié)點(diǎn)的位置,恰好這個(gè)節(jié)點(diǎn)的大小大于254字節(jié),這時(shí)候所有后面字節(jié)都需要更新,因?yàn)樗麄兊膒revious_entry_length都會(huì)變成5字節(jié)
三：QuickList
list 鏈表是redis中常用對(duì)象之一,之前一些版本中底層編碼數(shù)據(jù)采用雙向鏈表、壓縮列表的數(shù)據(jù)結(jié)構(gòu)。但是后續(xù)考慮鏈表指針維護(hù)開銷以及內(nèi)存碎片原因,開發(fā)新的數(shù)據(jù)結(jié)構(gòu)quicklist,這是一個(gè)雙向鏈表和壓縮列表的混合體
3.1 quicklist圖示
3.2 結(jié)構(gòu)描述
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count;
unsigned long len;
int fill : 16;
unsigned int compress : 16;
} quicklist;
屬性名稱作用含義
head頭部節(jié)點(diǎn)
tail 尾部節(jié)點(diǎn)
count壓縮列表元素?cái)?shù)量總數(shù)
len ziplist節(jié)點(diǎn)數(shù)量
fill 單個(gè)ziplist節(jié)點(diǎn)的填充因子
compress不壓縮節(jié)點(diǎn)的深度
3.3 ziplist節(jié)點(diǎn)
quicklist 內(nèi)部默認(rèn)單個(gè) ziplist 長(zhǎng)度為 8k字節(jié)，超出了這個(gè)字節(jié)數(shù)就會(huì)新建一個(gè) ziplist。ziplist 的長(zhǎng)度由配置參數(shù) list-max-ziplist-size決定
3.4 LZF壓縮
快速列表ziplist為了push與pop操作的效率默認(rèn)首尾節(jié)點(diǎn)不進(jìn)行LZF壓縮,如果需要設(shè)置更多節(jié)點(diǎn)不進(jìn)行LZF壓縮可以通過(guò)redis.conf配置文件中1099行l(wèi)ist-compress-depth 0參數(shù)定義
四：Dict
redis中的hash、set等對(duì)象都有使用到字典這個(gè)數(shù)據(jù)結(jié)構(gòu),字典底層實(shí)現(xiàn)使用哈希表的結(jié)構(gòu)。字典中主要掌握它的漸進(jìn)式hash,結(jié)構(gòu)源碼位置位于dict.h文件中
4.1 字典結(jié)構(gòu)
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx;
} dict;
屬性名稱作用含義
type 自定義一些操作的方法,拷貝key、拷貝value、銷毀key、銷毀value等
privdate創(chuàng)建dict時(shí)傳入,用于某些特殊操作回傳給調(diào)用函數(shù)
ht [0]用于數(shù)據(jù)存儲(chǔ),[1]用于rehash變更
rehashidx表示rehash進(jìn)度,-1表示未進(jìn)行rehash
4.2 哈希表結(jié)構(gòu)
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
屬性名稱作用含義
tablehash表節(jié)點(diǎn)
size hash表大小
sizemark哈希表大小掩碼,計(jì)算索引值。大小等于size -1
used哈希表已有的節(jié)點(diǎn)數(shù)量
4.3 哈希表節(jié)點(diǎn)結(jié)構(gòu)
typedef struct dictEntry{
void *key;
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
struct dictEntry *next;
}dictEntry
屬性名稱作用含義
key 保存數(shù)據(jù)的key值
union值對(duì)象,可以是一個(gè)對(duì)象,因?yàn)橛袀€(gè)對(duì)象空指針或者是uint64、int64的整數(shù)
next 指向下一個(gè)Entry的指針,形成一個(gè)鏈表
4.4 漸進(jìn)式rehash
字典的rehash操作數(shù)據(jù)量過(guò)大時(shí)并不是一次完成,而是分批次逐漸進(jìn)行
rehash過(guò)程中新插入字典數(shù)據(jù)放在[1]哈希表中,并將原[0]中數(shù)據(jù)重新進(jìn)行hash計(jì)算加入[1]中。讀操作將會(huì)讀取[0]、[1]兩個(gè)哈希表
rehash過(guò)程標(biāo)志使用dict中屬性rehashidx標(biāo)識(shí)
rehash采用cow寫時(shí)復(fù)制技術(shù)
五：Intset
redis中常用對(duì)象set會(huì)用到的底層數(shù)據(jù)結(jié)構(gòu)
5.1 整數(shù)集合特點(diǎn)
1：內(nèi)容全是數(shù)字
2：內(nèi)存連續(xù)
3：元素有序,不可重復(fù)
5.2 Intset結(jié)構(gòu)
typedef struct intset{
uint32_t encoding;
uint32_t length;
int8_t contents[];
}intset;
屬性名稱作用含義
encoding整數(shù)集合可以有三種編碼方式16、32、64
length整數(shù)集合數(shù)組中保存的元素個(gè)數(shù)
contents從小到大保存的整數(shù)集合中的元素
六：ZipList
zset中用到的一個(gè)數(shù)據(jù)結(jié)構(gòu),性能可以和紅黑樹、AVL樹不相上下
6.1 跳躍表結(jié)構(gòu)
typedef struct zskiplist{
//表頭結(jié)點(diǎn)和尾節(jié)點(diǎn)
structz skiplistNode *heade,*tail;
//表中節(jié)點(diǎn)數(shù)量
unsigned long length;
//表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
int level;
}zskiplist;
屬性名稱作用含義
head跳躍表頭結(jié)點(diǎn)
tail 跳躍表尾節(jié)點(diǎn)
length跳躍表節(jié)點(diǎn)數(shù)量,表頭結(jié)點(diǎn)不記錄在里面
level 跳躍表最大層數(shù),不記錄表頭節(jié)點(diǎn)
6.2 跳躍表節(jié)點(diǎn)
typedof struct zskiplistNode{
//層
struct zskiplistNode{
//前進(jìn)指針
struct zskiplistNode *forward;
//跨度
unsihned int span;
}level[];
//后退指針
struct zskiplistNode *backward;
//分值
double score；
//成員對(duì)象
robj *obj;
}zsikplistNode;
屬性名稱作用含義
zskiplistNode集合記錄該節(jié)點(diǎn)位于的每一層
forward 每一層節(jié)點(diǎn)對(duì)應(yīng)的下一個(gè)節(jié)點(diǎn)
span 距離下一個(gè)節(jié)點(diǎn)需要跨越的層數(shù)
backward 后退指針
score 節(jié)點(diǎn)分?jǐn)?shù)值
obj 跳躍表節(jié)點(diǎn)保存的對(duì)象
