引言
從本次開始，對Redis設計與實作進行閱讀及相關讀書筆記的記錄，Redis版本為3.0
資料結構
簡單動態字串SDS
sds資料結構位于sds.h/sdshdr
/*
* 保存字串物件的結構
*/
struct sdshdr {
// buf 中已占用空間的長度
int len;
// buf 中剩余可用空間的長度
int free;
// 資料空間
char buf[];
};
相對于C語言的字串，SDS的優點在于
- 常數復雜度獲取字串長度
- 杜絕緩沖區溢位
- 減少修改字串所帶來的記憶體重新分配（注意，釋放空間時候，不會真的釋放，而是設定free的值）
鏈表
鏈表的相關代碼在adlist.h中
鏈表節點listNode
/*
* 雙端鏈表節點
*/
typedef struct listNode {
// 前置節點
struct listNode *prev;
// 后置節點
struct listNode *next;
// 節點的值
void *value;
} listNode;
由多個listNode組成的雙端鏈表
鏈表結構list
/*
* 雙端鏈表結構
*/
typedef struct list {
// 表頭節點
listNode *head;
// 表尾節點
listNode *tail;
// 節點值復制函式
void *(*dup)(void *ptr);
// 節點值釋放函式
void (*free)(void *ptr);
// 節點值對比函式
int (*match)(void *ptr, void *key);
// 鏈表所包含的節點數量
unsigned long len;
} list;
字典
redis中的字典使用哈希表實作，其代碼在dict.h中
哈希表結構dictht
/*
* 哈希表
*
* 每個字典都使用兩個哈希表，從而實作漸進式 rehash ，
*/
typedef struct dictht {
// 哈希表陣列
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼，用于計算索引值
// 總是等于 size - 1 比如7號，當計算索引時候， 7&sizemask就可以得到
unsigned long sizemask;
// 該哈希表已有節點的數量
unsigned long used;
} dictht;
其中dictEntry為一個鍵值對
/*
* 哈希表節點
*/
typedef struct dictEntry {
// 鍵
void *key
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下個哈希表節點，形成鏈表 表明是一個鏈地址法解決哈希沖突
struct dictEntry *next;
} dictEntry;
下面為了形象表示一個哈希表，給出一個例子
下面給出一個多個dictEntry連接的哈希表
最終Redis中的字典資料結構如下
/*
* 字典
*/
typedef struct dict {
// 型別特定函式
dictType *type;
// 私有資料
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 當 rehash 不在進行時，值為 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在運行的安全迭代器的數量
int iterators; /* number of iterators currently running */
} dict;
/*
* 字典型別特定函式
*/
typedef struct dictType {
// 計算哈希值的函式 redis默認的函式演算法為murmurhash2
unsigned int (*hashFunction)(const void *key);
// 復制鍵的函式
void *(*keyDup)(void *privdata, const void *key);
// 復制值的函式
void *(*valDup)(void *privdata, const void *obj);
// 對比鍵的函式
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 銷毀鍵的函式
void (*keyDestructor)(void *privdata, void *key);
// 銷毀值的函式
void (*valDestructor)(void *privdata, void *obj);
} dictType;
跳躍表
redis中的跳躍表結構代碼為redis.h/zskiplistNode和redis.h/zskiplist
/* ZSETs use a specialized version of Skiplists */
/*
* 跳躍表節點
*/
typedef struct zskiplistNode {
// 成員物件
robj *obj;
// 分值 注意redis跳躍表按照節點從小到大排列
double score;
// 后退指標
struct zskiplistNode *backward;
// 層 陣列大小按照冪次定律（越大的數出現概率越小）1-32亂數字
struct zskiplistLevel {
// 前進指標
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
/*
* 跳躍表
*/
typedef struct zskiplist {
// 表頭節點和表尾節點
struct zskiplistNode *header, *tail;
// 表中節點的數量
unsigned long length;
// 表中層數最大的節點的層數
int level;
} zskiplist;
下面給出一個簡單的跳躍表例子
前進指標用于遍歷跳躍表，下面的虛線為遍歷程序
整數集合 intset
當一個集合里面只有整數值元素時候，且元素數量不超過REDIS_SET_MAX_INTSET_ENTRIES時候，集合底層采用整數集合
#define REDIS_SET_MAX_INTSET_ENTRIES 512 /*集合中元素個數小于該值，set底層使用intset*/
redis中整數集合代碼位于intset.h/intset
typedef struct intset {
// 編碼方式
uint32_t encoding;
// 集合包含的元素數量
uint32_t length;
// 保存元素的陣列 按照從小到大的順序，且不重復
int8_t contents[];
} intset;
contents陣列雖然是int8_t，但是里面存放的資料的真實型別由encoding欄位決定
- 升級操作
假如往下面的整數集合中append型別為int32的65535，則會發生升級，升級的程序主要包括將每個元素所占空間進行擴充，然后設定encoding，升級完后為
- 降級操作
注意整數集合無法進行降級，升級之后，會一直持續該編碼
壓縮串列 ziplist
壓縮串列其實就是一塊連續記憶體，一個壓縮串列包括多個節點（entry），每個entry保存一個位元組陣列或者整數值，在redis原始碼中， 壓縮串列沒有資料結構代碼定義，壓縮串列是一種通過記憶體特殊編碼方式實作的資料結構，他是通過定義一些基地址，然后使用偏移量來定義ziplist，其中大量使用了宏函式定義
/*
* ziplist 屬性宏
*/
// 定位到 ziplist 的 bytes 屬性，該屬性記錄了整個 ziplist 所占用的記憶體位元組數
// 用于取出 bytes 屬性的現有值，或者為 bytes 屬性賦予新值
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
// 定位到 ziplist 的 offset 屬性，該屬性記錄了到達表尾節點的偏移量
// 用于取出 offset 屬性的現有值，或者為 offset 屬性賦予新值
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
// 定位到 ziplist 的 length 屬性，該屬性記錄了 ziplist 包含的節點數量
// 用于取出 length 屬性的現有值，或者為 length 屬性賦予新值
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
// 回傳 ziplist 表頭的大小
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
// 回傳指向 ziplist 第一個節點（的起始位置）的指標
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
// 回傳指向 ziplist 最后一個節點（的起始位置）的指標
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
// 回傳指向 ziplist 末端 ZIP_END （的起始位置）的指標
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
其中，redis對entry使用了資料結構描述，如下代碼ziplist.c/zlentry
/*
* 保存 ziplist 節點資訊的結構
*/
typedef struct zlentry {
// prevrawlen ：前置節點的長度
// prevrawlensize ：編碼 prevrawlen 所需的位元組大小
unsigned int prevrawlensize, prevrawlen;
// len ：當前節點值的長度
// lensize ：編碼 len 所需的位元組大小
unsigned int lensize, len;
// 當前節點 header 的大小
// 等于 prevrawlensize + lensize
unsigned int headersize;
// 當前節點值所使用的編碼型別
unsigned char encoding;
// 指向當前節點的指標
unsigned char *p;
} zlentry;
- ziplist的創建
/* Create a new empty ziplist.
*
* 創建并回傳一個新的 ziplist
*
* T = O(1)
*/
unsigned char *ziplistNew(void) {
// ZIPLIST_HEADER_SIZE 是 ziplist 表頭的大小
// 1 位元組是表末端 ZIP_END 的大小
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
// 為表頭和表末端分配空間
unsigned char *zl = zmalloc(bytes);
// 初始化表屬性
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
ZIPLIST_LENGTH(zl) = 0;
// 設定表末端
zl[bytes-1] = ZIP_END;
return zl;
}
由于壓縮串列主要就是為了節約記憶體，因此對于不同的資料，其編碼方式不一樣，前面我們已經知道，entry中主要放位元組陣列和整數，下表給出兩種資料不同長度時候的編碼
位元組陣列編碼
整數編碼
物件
本次首先對Redis的相關資料結構進行介紹，Redis物件主要分為5種：REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET、REDIS_ZSET，下面首先給出Redis中對物件的代碼表示
// 物件型別
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4
#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {
// 型別 型別說明符 位域名：位域長度 標識type占4個二進制位 因為有可能不需要一個完整的位元組
// 1個位元組8位
unsigned type:4;
// 編碼
unsigned encoding:4;
// 物件最后一次被訪問的時間
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
// 參考計數
int refcount;
// 指向實際值的指標
void *ptr;
} robj;
首先看到有2個欄位，為型別和編碼，型別就是redis的5種型別，編碼就是這個型別底層是用什么編碼方式實作
但實際上，Redis的內部并不只是這5種物件，對于上面5種物件，都有幾種底層實作方式，下面給出各資料結構底層實作的對應方式
REDIS_STRING
? REDIS_STRING表示redis中的字串型別，其底層由以下三種實作方式
REDIS_ENCODING_INT
如果一個字串物件保存的是整數值，且這個整數值可以用long型別表示，則字串物件會獎整數值保存在字串物件的ptr屬性中，此時會將ptr的void*轉換為long
127.0.0.1:6379> set number "1"
OK
127.0.0.1:6379> object encoding number
"int"
REDIS_ENCODING_RAW
? 如果字串保存的是一個字串值，且長度大于32位元組，redis的字串物件就會采用簡單動態字串（SDS）實作
127.0.0.1:6379> set longstr "Hello, my name is Shi Linkun, is a programmer who loves code, I hope that each blog can let myself consolidate their knowledge, but also let everyone get a little knowledge, thank you"
OK
127.0.0.1:6379> object encoding longstr
"raw"
這里先不對SDS進行詳細簡介，后續單獨對其進行描述
REDIS_ENCODING_EMBSTR
如果字串物件保存的是一個字串，且長度小于等于32位元組，則使用embstr編碼實作
127.0.0.1:6379> set story "hello my name is shilinkun"
OK
127.0.0.1:6379> object encoding story
"embstr"
注意redis3.0版本中實際間隔為39位元組
#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39
robj *createStringObject(char *ptr, size_t len) {
if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)
return createEmbeddedStringObject(ptr,len);
else
return createRawStringObject(ptr,len);
}
為什么是39位元組，這里參考這個知乎的解釋
embstr是一塊連續的記憶體區域，由redisObject和sdshdr組成，其中redisObject占16個位元組，當buf內的字串長度是39時，sdshdr的大小為8+39+1=48，那一個位元組是'\0'，加起來剛好64，是不是發現了什么？
typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */ int refcount; void *ptr; } robj; struct sdshdr { unsigned int len; unsigned int free; char buf[]; };從2.4版本開始，redis開始使用jemalloc記憶體分配器，這個比glibc的malloc要好不少，還省記憶體，在這里可以簡單理解，jemalloc會分配8，16，32，64等位元組的記憶體，embstr最小為16+8+8+1=33，所以最小分配64位元組，當字符數小于39時，都會分配64位元組，
三個編碼的轉換
-
int->raw
向一個保存整數數值的字串物件使用APPEND命令，就會使得int轉變為raw
-
embstr->raw
對embstr型別的字串，執行任何的修改命令，都會變為raw
相關命令
字串命令的實作在t_string.c中
REDIS_LIST
串列物件底層主要由2種編碼方式：REDIS_ENCODING_ZIPLIST、REDIS_ENCODING_LINKEDLIST
REDIS_ENCODING_ZIPLIST
ziplist是指使用壓縮串列實作
REDIS_ENCODING_LINKLIST
linklist是使用雙端鏈表實作
編碼轉換
redis.h
#define REDIS_LIST_MAX_ZIPLIST_ENTRIES 512 /*list中元素個數小于該值，list底層使用ziplist*/
#define REDIS_LIST_MAX_ZIPLIST_VALUE 64 /*list中所有的字串長度小于該值，list底層使用ziplist*/
上述兩個宏定義分別與redis的組態檔中list-max-ziplist-entries和list-max-ziplist-value對應
REDIS_HASH
哈希物件主要有2種編碼方式，REDIS_ENCODING_ZIPLIST和REDIS_ENCODING_HT
REDIS_ENCODING_ZIPLIST
ziplist作為底層實作，先放入鍵，后放入值
REDIS_ENCODING_HT
編碼轉換
#define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512 //哈希物件保存的鍵值對數量小于512個，使用ziplist;
#define REDIS_HASH_MAX_ZIPLIST_VALUE 64 //哈希物件保存的所有鍵值對的鍵和值的字串長度都小于64位元組,使用ziplist;
上述兩個宏定義分別與redis的組態檔中hash-max-ziplist-entries和hash-max-ziplist-value對應
REDIS_SET
集合的底層編碼方式也是兩種：REDIS_ENCODING_INTSET和REDIS_ENCODING_HT
REDIS_ENCODING_INTSET
使用該編碼方式作為集合的底層實作時候，一般是整數集合，比如
REDIS_ENCODING_HT
使用哈希表作為集合的底層實作方式時，所有的值作為鍵，但對應的值為null
編碼轉換
#define REDIS_SET_MAX_INTSET_ENTRIES 512 /*集合中元素個數小于該值，且全為整數，set底層使用intset*/
對應的redis組態檔選項為set-max-intset-entries
REDIS_ZSET
有序集合底層實作為：REDIS_ENCODING_ZIPLIST和REDIS_ENCODING_SKIPLIST
REDIS_ENCODING_ZIPLIST
當使用壓縮串列作為有序集合的底層實作時候，壓縮串列的entry有2個值，一個是值，一個是得分，同時按照得分由小到大進行排列
REDIS_ENCODING_SKIPLIST
當使用跳躍表進行底層實作時候，一個有序集合同時包括：
- 一個跳躍表
- 一個字典
為什么有序集合需要同時使用跳躍表和字典來實作?
在理論上，有序集合可以單獨使用字典或者跳躍表的其中一種資料結構來實作，但無論單獨使用字典還是跳躍表，在性能上對比起同時使用字典和跳躍表都會有所降低，舉個例子，如果我們只使用字典來實作有序集合，那么雖然以O(1)復雜度查找成員的分值這一特性會被保留，但是，因為字典以無序的方式來保存集合元素，所以每次在執行范圍型操作——比如ZRANK、ZRANGE等命令時，程式都需要對字典保存的所有元素進行排序，完成這種排序需要至少O(NlogN)時間復雜度，以及額外的O(N)記憶體空間（因為要創建一個陣列來保存排序后的元素)，
另一方面，如果我們只使用跳躍表來實作有序集合，那么跳躍表執行范圍型操作的所有優點都會被保留，但因為沒有了字典，所以根據成員查找分值這一操作的復雜度將從O(1)上升為O(logN)，因為以上原因，為了讓有序集合的查找和范圍型操作都盡可能快地執行，Redis 選擇了同時使用字典和跳躍表兩種資料結構來實作有序集合，
編碼轉換
#define REDIS_ZSET_MAX_ZIPLIST_ENTRIES 128 /*有序集合中元素個數小于該值，zset底層使用ziplist*/
#define REDIS_ZSET_MAX_ZIPLIST_VALUE 64 /*有序集合中元素長度小于該值，zset底層使用ziplist*/
上述兩個宏定義分別與redis的組態檔中zset-max-ziplist-entries和zset-max-ziplist-value對應
總結
這一次把redis的資料結構和對應的物件實作方式大致說了一遍，最重要的還是什么時候使用什么資料結構，并且各種資料結構一些命令的時間復雜度等，這些其實還沒有進行闡述，后面會單獨開一章進行講解，因為在實際專案中，我們要針對不同場景對資料結構進行選取
自己的網址：www.shicoder.top
歡迎加群聊天 452380935
本文由博客一文多發平臺 OpenWrite 發布！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/458662.html
標籤：其他