不要虛度每一天，你的經驗就是這樣積累出來，然後用在了你的事情上面。一：摘要概述
很多 redis 的使用者都可以清晰明白的道出Redis中常用的物件如string、list、hash、set、zset,一些場景比較豐富的使用者可能會說布隆過濾器、geo、Hash等。但是對於這些物件底層實現的資料結構卻是知之甚少,將會詳細闡述redis中的底層資料結構。為了彌補大家的創傷，今天分享Redis底層資料結構內容。
二：SDS
string作為redis中常用物件之一,普遍用於使用者資訊快取等場景。當string物件中encoding編碼為embstr或raw時都是採用sds作為其底層實現
2.1 SDS結構
原始碼檔案位於redis安裝目錄src下的sds.h,sds聲明瞭五種頭部型別,分別為sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。根據字串長度建立不同頭部的sds例項
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
};
屬性名稱作用含義
len字串長度
alloc預分配空間大小
flags低三位用於表示sds型別,可以檢視sds.h檔案76-82行定義
buf[]儲存字串用陣列
2.2 SDS與C字串區別
區別描述
長度計算 c中的字串長度計算需要陣列遍歷,但是redis中的sds自身維護了len屬性。所以O(1)時間複雜度即可
緩衝區溢位c中字串更改如果未提前做好記憶體分配則會記憶體溢位,但是sds則會根據alloc與len計算預留記憶體是否足夠分配重新申請記憶體
動態擴充套件 緩衝區溢位已經闡述這個概念,sds的記憶體空間會在字串內容變更時自動擴充套件計算。策略為當字元換小於1M時*2翻倍,大於1M時每次擴容1M
二：ZipList
ziplist可以說把redis對於記憶體的極致操作體現的淋漓盡致,連結串列除了節點值之外還需要維護前後節點兩個指標,並且還會造成記憶體碎片。壓縮列表緊湊的記憶體佈局,所有節點都維護在整塊記憶體中處理
2.1 ZipList結構
屬性名稱作用含義
zlbytes列表健佔用記憶體的總位元組數,在對列表健記憶體重分配或者是計算zlend的時候使用
zltail 指向壓縮列表起始地址的指標
zllen 壓縮列表的節點數量
entry壓縮列表儲存的節點資料
zlend壓縮列表的尾節點
2.2 Entry節點結構
屬性名稱作用含義
previous_entry_length 位元組為單位記錄上一個節點的長度,如果上一個位元組長度小於254佔用1位元組。大於254佔用5位元組,第一個位元組設定為OxFE(十進位制254),後面四個位元組儲存長度
encoding 記錄content記錄的資料型別以及長度。長度一、二、五位元組,值的最高位為00、01、10表示型別為位元組陣列,長度使用除去最高位的其它位記錄。11開頭表示儲存整數,除去最高位其他位置表示content資料長度
content 記錄壓縮列表記錄的資料
2.3 連鎖更新
一個壓縮列表節點在儲存上一個節點長度使用previous_entry_length屬性,這個屬性可以使用1位元組或者是5位元組。假設現有一個壓縮列表裡面儲存的節點長度全部都是250-253,這時候previous_entry_length使用一位元組記錄就行。但是這時候新增一個新節點到頭節點的位置,恰好這個節點的大小大於254位元組,這時候所有後面位元組都需要更新,因為他們的previous_entry_length都會變成5位元組
三：QuickList
list 連結串列是redis中常用物件之一,之前一些版本中底層編碼資料採用雙向連結串列、壓縮列表的資料結構。但是後續考慮連結串列指標維護開銷以及記憶體碎片原因,開發新的資料結構quicklist,這是一個雙向連結串列和壓縮列表的混合體
3.1 quicklist圖示
3.2 結構描述
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count;
unsigned long len;
int fill : 16;
unsigned int compress : 16;
} quicklist;
屬性名稱作用含義
head頭部節點
tail 尾部節點
count壓縮列表元素數量總數
len ziplist節點數量
fill 單個ziplist節點的填充因子
compress不壓縮節點的深度
3.3 ziplist節點
quicklist 內部預設單個 ziplist 長度為 8k位元組，超出了這個位元組數就會新建一個 ziplist。ziplist 的長度由配置引數 list-max-ziplist-size決定
3.4 LZF壓縮
快速列表ziplist為了push與pop操作的效率預設首尾節點不進行LZF壓縮,如果需要設定更多節點不進行LZF壓縮可以透過redis.conf配置檔案中1099行list-compress-depth 0引數定義
四：Dict
redis中的hash、set等物件都有使用到字典這個資料結構,字典底層實現使用雜湊表的結構。字典中主要掌握它的漸進式hash,結構原始碼位置位於dict.h檔案中
4.1 字典結構
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx;
} dict;
屬性名稱作用含義
type 自定義一些操作的方法,複製key、複製value、銷燬key、銷燬value等
privdate建立dict時傳入,用於某些特殊操作回傳給呼叫函式
ht [0]用於資料儲存,[1]用於rehash變更
rehashidx表示rehash進度,-1表示未進行rehash
4.2 雜湊表結構
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
屬性名稱作用含義
tablehash表節點
size hash表大小
sizemark雜湊表大小掩碼,計算索引值。大小等於size -1
used雜湊表已有的節點數量
4.3 雜湊表節點結構
typedef struct dictEntry{
void *key;
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
struct dictEntry *next;
}dictEntry
屬性名稱作用含義
key 儲存資料的key值
union值物件,可以是一個物件,因為有個物件空指標或者是uint64、int64的整數
next 指向下一個Entry的指標,形成一個連結串列
4.4 漸進式rehash
字典的rehash操作資料量過大時並不是一次完成,而是分批次逐漸進行
rehash過程中新插入字典資料放在[1]雜湊表中,並將原[0]中資料重新進行hash計算加入[1]中。讀操作將會讀取[0]、[1]兩個雜湊表
rehash過程標誌使用dict中屬性rehashidx標識
rehash採用cow寫時複製技術
五：Intset
redis中常用物件set會用到的底層資料結構
5.1 整數集合特點
1：內容全是數字
2：記憶體連續
3：元素有序,不可重複
5.2 Intset結構
typedef struct intset{
uint32_t encoding;
uint32_t length;
int8_t contents[];
}intset;
屬性名稱作用含義
encoding整數集合可以有三種編碼方式16、32、64
length整數集合陣列中儲存的元素個數
contents從小到大儲存的整數集合中的元素
六：ZipList
zset中用到的一個數據結構,效能可以和紅黑樹、AVL樹不相上下
6.1 跳躍表結構
typedef struct zskiplist{
//表頭結點和尾節點
structz skiplistNode *heade,*tail;
//表中節點數量
unsigned long length;
//表中層數最大的節點的層數
int level;
}zskiplist;
屬性名稱作用含義
head跳躍表頭結點
tail 跳躍表尾節點
length跳躍表節點數量,表頭結點不記錄在裡面
level 跳躍表最大層數,不記錄表頭節點
6.2 跳躍表節點
typedof struct zskiplistNode{
//層
struct zskiplistNode{
//前進指標
struct zskiplistNode *forward;
//跨度
unsihned int span;
}level[];
//後退指標
struct zskiplistNode *backward;
//分值
double score；
//成員物件
robj *obj;
}zsikplistNode;
屬性名稱作用含義
zskiplistNode集合記錄該節點位於的每一層
forward 每一層節點對應的下一個節點
span 距離下一個節點需要跨越的層數
backward 後退指標
score 節點分數值
obj 跳躍表節點儲存的物件