Redis極致設計-資料儲存的原理
一、Redis 資料儲存的設計思路
目前能夠儲存海量資料的資料庫,底層資料的儲存結構一般有:
陣列,時間複雜度O(1)
索引,比如有tree(紅黑樹、AVL 樹), 時間複雜度logN
連結串列:時間複雜度O(N)
對比發現,陣列查詢資料的時間複雜度最優,所以 Redis 底層的結構就是採用陣列。
那麼既然採用陣列,則redis的key對應的就是陣列的索引。
我們知道Redis中key的結構很豐富,可以是 string、int、float等,為了讓key存入到陣列中,我們一般對key進行hash,hash函式可以將任意字串轉化為一個非常大的自然數,但是這樣索引也就越大,浪費空間,所以在轉化為自然數後利用
求模以及擷取前面的長度
來保證索引的長度。
所以key的對映過程,通常使用 hash 演算法實現,因此也稱對映過程為雜湊化,存放記錄的陣列叫做散列表、或hash表,Redis中如何做hash的稍候我們詳細介紹
雜湊化之後難免會產生一個問題,那就是對不同的關鍵字,可能得到同一個雜湊地址,即
hash衝突
。解決衝突最常用的方法就是
鏈地址法
,就是在衝突的下標處,維護一個連結串列,所有對映到該下標的記錄,都新增到該連結串列上。
以上就是Redis大致的一個底層資料的設計思路,接下來我們詳細看一下其內部原理。
二、Redis 底層資料儲存原理
1。 資料儲存的核心——redisDb
redis 中以redisDb作為整個快取儲存的核心,儲存著我們客戶端需要的快取資料,以下是資料redisDb的結構:
typedef
struct
redisDb
{
dict
*
dict
;
/* The keyspace for this DB */
//保持資料的dict
dict
*
expires
;
/* Timeout of keys with a timeout set */
//保持key的過期資訊
dict
*
blocking_keys
;
/* Keys with clients waiting for data (BLPOP)*/
//一些同步的keys
dict
*
ready_keys
;
/* Blocked keys that received a PUSH */
dict
*
watched_keys
;
/* WATCHED keys for MULTI/EXEC CAS */
int
id
;
/* Database ID */
Redis預設有16個數據庫
long
long
avg_ttl
;
/* Average TTL, just for stats */
}
redisDb
;
dict和expires是redisDB中最主要的兩個屬性,
分別儲存了物件資料鍵值對和key的過期時間,其底層資料結構都是dict字典
。之所以分開儲存,由於過期時間並不是資料的固有屬性,雖然分開儲存需要兩次查詢,但是卻能節省記憶體開銷。
blocking_keys和ready_keys主要為了
實現BLPOP等阻塞命令
watched_keys用於
實現watch命令
,
記錄正在被watch的一些key
eviction_pool是
記錄可能被lru淘汰的一些備選key
id為
當前資料庫的id
,redis支援單個服務多資料庫,預設有16個
2。 redisDb中儲存資料的結構——dict
可以看到dict儲存著資料庫所有的鍵值對,再詳細看一下dict 的結構
/*
* 字典
*
* 每個字典使用兩個雜湊表,用於實現漸進式 rehash
*/
typedef
struct
dict
{
// 特定於型別的處理函式
dictType
*
type
;
// 型別處理函式的私有資料
void
*
privdata
;
// 雜湊表(2 個)
dictht
ht
[
2
];
// 記錄 rehash 進度的標誌,值為 -1 表示 rehash 未進行
int
rehashidx
;
// 當前正在運作的安全迭代器數量
int
iterators
;
}
dict
;
各屬性含義:
type儲存了hash函式、key和value的複製、比較以及銷燬函式,而privdata則儲存了一些私有資料,其和type共同決定了當前dictType結構中所儲存的函式的指向,從而實現多型的目的,比如redis提供的hash函式就有兩種,一種是Murmurhash函式,另一種是djbhash函式
typedef
struct
dictType
{
// hash函式
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
;
ht[2]是一個長度為2的陣列,
正常情況下回使用ht[0]來儲存資料,當進行rehash操作時,redis會使用ht[1]來配合進行漸進式rehash操作
。而在平常情況下,只有 ht[0]有效,ht[1]裡面沒有任何資料。具體rehash過程後面詳細講解
rehashidx是一個整數值,如果當前沒有進行rehash操作,則其值為-1,如果正在進行rehash操作,那麼其值為當前rehash操作正在執行到的ht[1]中dictEntry陣列的索引
iterators當前正在進行遍歷的 iterator 的個數。如果其值不為0,那麼是不允許對hash表進行rehash操作的。
3。 dict中儲存資料的雜湊表-dictht
上述的dict的dictht 就是我們說的 hashTable (dictht 是字典 dict 雜湊表的縮寫,即 dict hash table)
/*
* 雜湊表
*/
typedef
struct
dictht
{
// 雜湊表節點指標陣列(俗稱桶,bucket)
dictEntry
**
table
;
// 指標陣列的大小
unsigned
long
size
;
// 指標陣列的長度掩碼,用於計算索引值,其實永遠都是size-1
unsigned
long
sizemask
;
// 雜湊表現有的節點數量
unsigned
long
used
;
}
dictht
;
dictht 定義一個雜湊表的結構,包括以下部分:
dictEntry 指標陣列(table)。key 的雜湊值最終對映到這個陣列的某個位置上(對應一個 bucket)。如果多個 key 對映到同一個位置,就發生了衝突,那麼就拉出一個 dictEntry 連結串列。
size:標識 dictEntry 指標陣列的長度。它總是 2 的指數次冪。
之所以設定為2的指數次冪是因為經常要對hash值與size(tables陣列長度)取模運算,因為取模運算為了轉化為 雜湊值 % size = 雜湊值 & sizemask,其中sizemask=size-1,為了可以使用&運算提高計算效能,則要求為2的指數次冪,算是求模的最佳化
sizemask:用於將雜湊值對映到 table 的位置索引。它的值等於(size-1),比如 7, 15, 31, 63,等等,也就是用二進位制表示的各個 bit 全 1 的數字。每個 key 先經過 hashFunction 計算得到一個雜湊值,然後計算(雜湊值 & sizemask)得到在 table 上的位置。相當於計算取餘(雜湊值 % size)。
used:記錄 dict 中現有的資料個數。它與 size 的比值就是裝載因子。這個比值越大,雜湊值衝突機率越高,當比值[預設]超過 5,會強制進行 rehash(擴容),這裡就涉及到負載因子的概念,後面詳細說明一下。
4。 dictht雜湊表中節點——dictEntry
/*
* 雜湊表節點
*/
typedef
struct
dictEntry
{
// 鍵
void
*
key
;
// 值
union
{
void
*
val
;
uint64_t
u64
;
int64_t
s64
;
}
v
;
// 鏈的後繼節點
struct
dictEntry
*
next
;
}
dictEntry
;
key是 void 指標,這意味著它可以指向任何型別。
value 是個 union(聯合體),當它的值是 uint64_t、int64_t 或 double 型別時,就不再需要額外的儲存,這有利於減少記憶體碎片。當然,v 也可以是 void 指標,以便能儲存任何型別的資料。
next 指向另一個 dictEntry 結構, 多個 dictEntry 可以透過 next 指標串連成連結串列, 從這裡可以看出, dictht 使用鏈地址法來處理鍵碰撞: 當多個不同的鍵擁有相同的雜湊值時,雜湊表用一個連結串列將這些鍵連線起來。
下圖展示了一個由 dictht 和數個 dictEntry 組成的雜湊表例子:
如果再加上之前列出的 dict 型別,那麼整個字典結構可以表示如下:
5。 RedisDb的整體儲存結構
下圖就是整個主題的資料結構
6。 dictEntry 中value指向的物件——redisObject
根據上面的主體結構圖中可以看到 dictEntry 中的 value 都是指向一個叫做 redisObject的物件,我們看一下其結構
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
;
type 記錄了物件的型別,string、set 等,根據該型別才可以確定是哪種結構,方便使用什麼樣的 API 操作
encoding 表示 ptr 指向的具體資料結構,即這個物件使用了什麼資料結構作為底層實現。
lru 表示物件最後一次被命令程式訪問的時間,記憶體淘汰的時候使用的
refcount 表示引用計數,由於 C 語言並不具備記憶體回收功能,所以 Redis 在自己的物件系統中添加了這個屬性,當一個物件的引用計數為 0 時,則表示該物件已經不被任何物件引用,則可以進行垃圾回收了。
上面可能會出現迴圈引用的問題,Java有考慮,Redis 有沒有考慮迴圈引用的問題呢?這個問題後續我會詳細說明
ptr 指標:指向物件的底層實現資料結構
接下來我們透過命令看一下資料的儲存是什麼樣的,透過
object encoding key
命令來檢視具體的儲存結構
上圖可以看到不同的字串其內部的結構是不一樣的,一個是embstr、另外一個是raw, 為什麼不同的 key ,ptr指向的結構不一樣呢?
後續我將詳細說明每種資料型別底層的資料結構。
三、總結
Redis從一個redisDb的物件來儲存整個資料,其儲存的原理和jdk中hashMap的儲存原理大同小異,但是在細節中也能看出其對記憶體的極致使用,比如為何設計兩個雜湊表,而雜湊表中的節點值為何會有三種類型:uint64_t、int64_t 、void,以及文章最後看到的string型別的值結構有些是embstr,有些是raw,這些都體現了設計者的思考和值得我們學習的經驗。