不要虛度每一天，你的經驗就是這樣積累出來，然后用在了你的事情上面。
一：摘要概述
很多 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 跳躍表節點保存的對象
