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，這些都體現了設計者的思考和值得我們學習的經驗。