Redis作為基于內(nèi)存的非關(guān)系型的K-V數(shù)據(jù)庫(kù)。因讀寫響應(yīng)快速、原子操作、提供了多種數(shù)據(jù)類型String、List、Hash、Set、Sorted Set、在項(xiàng)目中有著廣泛的使用，今天我們來(lái)探討下下Redis的數(shù)據(jù)結(jié)構(gòu)是如何實(shí)現(xiàn)的。

1 引言

Redis作為基于內(nèi)存的非關(guān)系型的K-V數(shù)據(jù)庫(kù)。因讀寫響應(yīng)快速、原子操作、提供了多種數(shù)據(jù)類型String、List、Hash、Set、Sorted Set、在項(xiàng)目中有著廣泛的使用，今天我們來(lái)探討下下Redis的數(shù)據(jù)結(jié)構(gòu)是如何實(shí)現(xiàn)的。

2 數(shù)據(jù)存儲(chǔ)

2.1 RedisDB

Redis將數(shù)據(jù)存儲(chǔ)在redisDb中，默認(rèn)0~15共16個(gè)db。每個(gè)庫(kù)都是獨(dú)立的空間，不必?fù)?dān)心key沖突問(wèn)題，可通過(guò)select命令切換db。集群模式使用db0

typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
dict *expires; /* Timeout of keys with a timeout set */
...
} redisDb;

• dict：數(shù)據(jù)庫(kù)鍵空間，保存著數(shù)據(jù)庫(kù)中的所有鍵值對(duì)
• expires：鍵的過(guò)期時(shí)間，字典的鍵為鍵，字典的值為過(guò)期事件UNIX時(shí)間戳

2.2 Redis哈希表實(shí)現(xiàn)

2.2.1 哈希字典dict

K-V存儲(chǔ)我們最先想到的就是map，在Redis中通過(guò)dict實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)如下：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

• type：類型特定函數(shù)是一個(gè)指向dictType結(jié)構(gòu)的指針，每個(gè)dictType結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對(duì)的函數(shù)，Redis會(huì)為用途不同的字典設(shè)置不同的類型特定函數(shù)。
• privdata：私有數(shù)據(jù)保存了需要傳給那些類型特定函數(shù)的可選參數(shù)
• ht[2]：哈希表一個(gè)包含兩個(gè)項(xiàng)的數(shù)組，數(shù)組中的每個(gè)項(xiàng)都是一個(gè)dictht哈希表，一般情況下，字典只使用ht[0] 哈希表，ht[1]哈希表只會(huì)在對(duì)ht[0]哈希表進(jìn)行rehash時(shí)使用
• rehashidx：rehash 索引，當(dāng)rehash不在進(jìn)行時(shí)，值為 -1

hash數(shù)據(jù)存在兩個(gè)特點(diǎn)：

• 任意相同的輸入一定能得到相同的數(shù)據(jù)
• 不同的輸入，有可能得到相同的輸出

針對(duì)hash數(shù)據(jù)的特點(diǎn)，存在hash碰撞的問(wèn)題，dict通過(guò)dictType中的函數(shù)能夠解決這個(gè)問(wèn)題

typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
...
} dictType;

• hashFunction：用于計(jì)算key的hash值的方法
• keyCompare：key的值比較方法

2.2.2 哈希表 dictht

dict.h/dictht表示一個(gè)哈希表，具體結(jié)構(gòu)如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

• table：數(shù)組指針，數(shù)組中的每個(gè)元素都是一個(gè)指向dict.h/dictEntry結(jié)構(gòu)的指針，每個(gè)dictEntry結(jié)構(gòu)保存著一個(gè)鍵值對(duì)。
• size：記錄了哈希表的大小，也就是table數(shù)組的大小，大小總是2^n
• sizemask：總是等于size - 1，這個(gè)屬性和哈希值一起決定一個(gè)鍵應(yīng)該被放到table數(shù)組的哪個(gè)索引上面。
• used：記錄了哈希表目前已有節(jié)點(diǎn)（鍵值對(duì)）的數(shù)量。

鍵值對(duì)dict.h/dictEntry

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

• key：保存著鍵值對(duì)中的鍵(SDS類型對(duì)象)
• val：保存著鍵值對(duì)中的值，可以是一個(gè)uint64_t整數(shù)，或者是一個(gè)int64_t整數(shù)，又或者是一個(gè)指針指向一個(gè)被redisObject包裝的值
• next：指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表指向另一個(gè)哈希表節(jié)點(diǎn)的指針，這個(gè)指針可以將多個(gè)哈希值相同的鍵值對(duì)連接在一次，以此來(lái)解決鍵沖突（collision）的問(wèn)題

使用hash表就一定會(huì)存在hash碰撞的問(wèn)題，hash碰撞后在當(dāng)前數(shù)組節(jié)點(diǎn)形成一個(gè)鏈表，在數(shù)據(jù)量超過(guò)hash表長(zhǎng)度的情況下，就會(huì)存在大量節(jié)點(diǎn)稱為鏈表，極端情況下時(shí)間復(fù)雜度會(huì)從O(1)變?yōu)镺(n)；如果hash表的數(shù)據(jù)再不斷減少，會(huì)造成空間浪費(fèi)的情況。Redis會(huì)針對(duì)這兩種情況根據(jù)負(fù)載因子做擴(kuò)展與收縮操作：

• 負(fù)載因子：哈希表已保存節(jié)點(diǎn)數(shù)量/哈希表大小，load_factor = ht[0].used/ht[0].size
• 擴(kuò)展操作：
• 服務(wù)器目前沒(méi)有在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于 1；
• 服務(wù)器目前正在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于5；

收縮操作：

• 當(dāng)哈希表的負(fù)載因子小于 0.1 時(shí)， 程序自動(dòng)開始對(duì)哈希表執(zhí)行收縮操作。

Redis在擴(kuò)容時(shí)如果全量擴(kuò)容會(huì)因?yàn)閿?shù)據(jù)量問(wèn)題導(dǎo)致客戶端操作短時(shí)間內(nèi)無(wú)法處理，所以采用漸進(jìn)式 rehash進(jìn)行擴(kuò)容，步驟如下：

• 同時(shí)持有2個(gè)哈希表
• 將rehashidx的值設(shè)置為0,表示rehash工作正式開始
• 在rehash進(jìn)行期間， 每次對(duì)字典執(zhí)行添加、刪除、查找或者更新操作時(shí)，程序除了執(zhí)行指定的操作以外,還會(huì)順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對(duì)rehash到ht[1] ,當(dāng)rehash工作完成之后，程序?qū)ehashidx屬性的值增一
• 某個(gè)時(shí)間點(diǎn)上，ht[0]的所有鍵值對(duì)都會(huì)被rehash至ht[1] ，這時(shí)程序?qū)ehashidx屬性的值設(shè)為-1， 表示rehash操作已完成

在漸進(jìn)式 rehash 進(jìn)行期間，字典的刪除（delete）、查找（find）、更新（update）等操作會(huì)在兩個(gè)哈希表上進(jìn)行；在字典里面查找一個(gè)鍵的話， 程序會(huì)先在 ht[0] 里面進(jìn)行查找，如果沒(méi)找到的話，就會(huì)繼續(xù)到ht[1]里面進(jìn)行查找；新添加到字典的鍵值對(duì)一律會(huì)被保存到 ht[1] 里面，而ht[0]則不再進(jìn)行任何添加操作：這一措施保證了ht[0]包含的鍵值對(duì)數(shù)量會(huì)只減不增(如果長(zhǎng)時(shí)間不進(jìn)行操作時(shí)，事件輪詢進(jìn)行這種操作)，并隨著rehash操作的執(zhí)行而最終變成空表。

dict.h/redisObject

Typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
}

• type:4：約束客戶端操作時(shí)存儲(chǔ)的數(shù)據(jù)類型，已存在的數(shù)據(jù)無(wú)法修改類型，4bit
• encoding:4：值在redis底層的編碼模式，4bit
• lru:LRU_BITS：內(nèi)存淘汰策略
• refcount：通過(guò)引用計(jì)數(shù)法管理內(nèi)存，4byte
• ptr：指向真實(shí)存儲(chǔ)值的地址，8byte

完整結(jié)構(gòu)圖如下：

3 String類型

3.1 String類型使用場(chǎng)景

String 字符串存在有三種類型：字符串，整數(shù)，浮點(diǎn)。主要有以下使用場(chǎng)景

1）頁(yè)面動(dòng)態(tài)緩存
比如生成一個(gè)動(dòng)態(tài)頁(yè)面，首次可以將后臺(tái)數(shù)據(jù)生成頁(yè)面，并且存儲(chǔ)到redis字符串中。再次訪問(wèn)，不再進(jìn)行數(shù)據(jù)庫(kù)請(qǐng)求，直接從redis中讀取該頁(yè)面。特點(diǎn)是：首次訪問(wèn)比較慢，后續(xù)訪問(wèn)快速。

2）數(shù)據(jù)緩存
在前后分離式開發(fā)中，有些數(shù)據(jù)雖然存儲(chǔ)在數(shù)據(jù)庫(kù)，但是更改特別少。比如有個(gè)全國(guó)地區(qū)表。當(dāng)前端發(fā)起請(qǐng)求后，后臺(tái)如果每次都從關(guān)系型數(shù)據(jù)庫(kù)讀取，會(huì)影響網(wǎng)站整體性能。
我們可以在第一次訪問(wèn)的時(shí)候，將所有地區(qū)信息存儲(chǔ)到redis字符串中，再次請(qǐng)求，直接從數(shù)據(jù)庫(kù)中讀取地區(qū)的json字符串，返回給前端。

3）數(shù)據(jù)統(tǒng)計(jì)
redis整型可以用來(lái)記錄網(wǎng)站訪問(wèn)量，某個(gè)文件的下載量。（原子自增自減）

4）時(shí)間內(nèi)限制請(qǐng)求次數(shù)
比如已登錄用戶請(qǐng)求短信驗(yàn)證碼，驗(yàn)證碼在5分鐘內(nèi)有效的場(chǎng)景。當(dāng)用戶首次請(qǐng)求了短信接口，將用戶id存儲(chǔ)到redis 已經(jīng)發(fā)送短信的字符串中，并且設(shè)置過(guò)期時(shí)間為5分鐘。當(dāng)該用戶再次請(qǐng)求短信接口，發(fā)現(xiàn)已經(jīng)存在該用戶發(fā)送短信記錄，則不再發(fā)送短信。

5）分布式session
當(dāng)我們用nginx做負(fù)載均衡的時(shí)候，如果我們每個(gè)從服務(wù)器上都各自存儲(chǔ)自己的session，那么當(dāng)切換了服務(wù)器后，session信息會(huì)由于不共享而會(huì)丟失，我們不得不考慮第三應(yīng)用來(lái)存儲(chǔ)session。通過(guò)我們用關(guān)系型數(shù)據(jù)庫(kù)或者redis等非關(guān)系型數(shù)據(jù)庫(kù)。關(guān)系型數(shù)據(jù)庫(kù)存儲(chǔ)和讀取性能遠(yuǎn)遠(yuǎn)無(wú)法跟redis等非關(guān)系型數(shù)據(jù)庫(kù)。

3.2 String類型的實(shí)現(xiàn)——SDS結(jié)構(gòu)

Redis并沒(méi)有直接使用C字符串實(shí)現(xiàn)String類型，在Redis3.2版本之前通過(guò)SDS實(shí)現(xiàn)

Typedef struct sdshdr {
int len;
int free;
char buf[];
};

• len：分配內(nèi)存空間
• free：剩余可用分配空間
• char[]：value值實(shí)際數(shù)據(jù)

3.3 SDS與C字符串之間的區(qū)別

3.3.1 查詢時(shí)間復(fù)雜度

C獲取字符串長(zhǎng)度的復(fù)雜度為O(N)。而SDS通過(guò)len記錄長(zhǎng)度，從C的O(n)變?yōu)镺(1)。

3.3.2 緩沖區(qū)溢出

C字符串不記錄自身長(zhǎng)度容易造成緩沖區(qū)溢出（buffer overflow）。SDS的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性,當(dāng)需要對(duì)SDS進(jìn)行修改時(shí)，會(huì)先檢查SDS的空間是否滿足修改所需的要求，如果不滿足的話SDS的空間擴(kuò)展至執(zhí)行修改所需的大小，然后才執(zhí)行實(shí)際的修改操作，所以使用SDS既不需要手動(dòng)修改SDS的空間大小，也不會(huì)出現(xiàn)緩沖區(qū)溢出問(wèn)題。

在SDS中，buf數(shù)組的長(zhǎng)度不一定就是字符數(shù)量加一，數(shù)組里面可以包含未使用的字節(jié)，而這些字節(jié)的數(shù)量就由SDS的free屬性記錄。通過(guò)未使用空間，SDS實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略：

• 空間預(yù)分配：當(dāng)對(duì)一個(gè)SDS進(jìn)行修改，并且需要對(duì)SDS進(jìn)行空間擴(kuò)展的時(shí)候，程序不僅會(huì)為SDS分配修改所必須要的空間，還會(huì)為SDS分配額外的未使用空間。擴(kuò)展SDS 空間之前，會(huì)先檢查未使用空間是否足夠， 如果足夠的話，就會(huì)直接使用未使用空間，而無(wú)須執(zhí)行內(nèi)存重分配。如果不夠根據(jù)(len + addlen(新增字節(jié))) * 2的方式進(jìn)行擴(kuò)容，大于1M時(shí)，每次只會(huì)增加1M大小。通過(guò)這種預(yù)分配策略，SDS將連續(xù)增長(zhǎng)N次字符串所需的內(nèi)存重分配次數(shù)從必定N次降低為最多N次。
• 惰性空間釋放：惰性空間釋放用于優(yōu)化SDS的字符串縮短操作：當(dāng)需要縮短SDS保存的字符串時(shí)，程序并不立即使用內(nèi)存重分配來(lái)回收縮短后多出來(lái)的字節(jié)，而是使用free屬性將這些字節(jié)的數(shù)量記錄起來(lái)，并等待將來(lái)使用。

3.3.3 二進(jìn)制安全

C字符串中的字符必須符合某種編碼（比如 ASCII，并且除了字符串的末尾之外，字符串里面不能包含空字符， 否則最先被程序讀入的空字符將被誤認(rèn)為是字符串結(jié)尾。

SDS的API都是二進(jìn)制安全的（binary-safe）：都會(huì)以處理二進(jìn)制的方式來(lái)處理SDS存放在buf數(shù)組里的數(shù)據(jù)，程序不會(huì)對(duì)其中的數(shù)據(jù)做任何限制、過(guò)濾、或者假設(shè) —— 數(shù)據(jù)在寫入時(shí)是什么樣的，它被讀取時(shí)就是什么樣。redis不是用這個(gè)數(shù)組來(lái)保存字符，而是用它來(lái)保存一系列二進(jìn)制數(shù)據(jù)。

3.4 SDS結(jié)構(gòu)優(yōu)化

String類型所存儲(chǔ)的數(shù)據(jù)可能會(huì)幾byte存在大量這種類型數(shù)據(jù)，但len、free屬性的int類型會(huì)占用4byte共8byte存儲(chǔ)，3.2之后會(huì)根據(jù)字符串大小使用sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，具體結(jié)構(gòu)如下：

struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};

• unsign char flags：3bit表示類型，5bit表示未使用長(zhǎng)度
• len：表示已使用長(zhǎng)度
• alloc：表示分配空間大小，剩余空間大小可以使用alloc - len獲得

3.5 字符集編碼

redisObject包裝存儲(chǔ)的value值，通過(guò)字符集編碼對(duì)數(shù)據(jù)存儲(chǔ)進(jìn)行優(yōu)化，string類型的編碼方式有如下三種：

• embstr:

CPU每次按Cache Line 64byte讀取數(shù)據(jù)，一個(gè)redisObject對(duì)象為16byte，為填充64byte大小，會(huì)向后再讀取48 byte數(shù)據(jù)。但獲取實(shí)際數(shù)據(jù)時(shí)還需要再通過(guò)*ptr指針讀取對(duì)應(yīng)內(nèi)存地址的數(shù)據(jù)。而一個(gè)sdshdr8屬性的信息占用4byte，其余44byte可以用來(lái)存儲(chǔ)數(shù)據(jù)。如果value值小于44，byte可以通過(guò)一次讀取緩存行獲取數(shù)據(jù)。

• int:

如果SDS小于20位，并且能夠轉(zhuǎn)換成整型數(shù)字，redisObject的*ptr指針會(huì)直接進(jìn)行存儲(chǔ)。

• raw:

SDS

4 總結(jié)

redis作為k-v數(shù)據(jù)存儲(chǔ)，因查找和操作的時(shí)間復(fù)雜度都是O(1)和豐富的數(shù)據(jù)類型及數(shù)據(jù)結(jié)構(gòu)的優(yōu)化，了解了這些數(shù)據(jù)類型和結(jié)構(gòu)更有利于我們平時(shí)對(duì)于redis的使用。下一期將對(duì)其它常用數(shù)據(jù)類型List、Hash、Set、Sorted Set所使用的ZipList、QuickList、SkipList做進(jìn)一步介紹，對(duì)于文章中不清晰不準(zhǔn)確的地方歡迎大家一起討論交流。

到此這篇關(guān)于Redis的數(shù)據(jù)存儲(chǔ)及String類型的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Redis數(shù)據(jù)存儲(chǔ)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論