Redis中字符串與字典如何實(shí)現(xiàn)？

本文和大家分享的主要是redis中字符串與字典相關(guān)內(nèi)容，一起來看看吧，希望對大家學(xué)習(xí)redis有所幫助。

　　簡單動態(tài)字符串 （SDS）

　　內(nèi)部實(shí)現(xiàn)

　　struct sdshdr {

　　len int; // 所保存的字符串長度

　　free int; // 未使用的字節(jié)長度

　　char buf[]; // 字節(jié)數(shù)組，用于保存字符串

　　}

　　c 字符串通常是以空字符 '\\0' 結(jié)尾，所以一個 SDS 的長度為： len + free + 1

　　與 c 字符串的區(qū)別

獲取字符串長度

　?。?c 字符串獲取長度是逐個讀取字符計(jì)算長度，時間復(fù)雜度為: O(N)

　?。?SDS 是通過 len 來獲取字符串長度，時間復(fù)雜度為: O(1)

　　API 安全

　?。?c 字符串不會檢查內(nèi)存空間是否足夠，當(dāng)拼接字符串時，有可能會出現(xiàn)緩沖區(qū)溢出問題

　　． SDS 則會根據(jù) free 來判斷空間是否足夠，如果內(nèi)存空間不足，則會申請內(nèi)存空間，因此不會有緩沖區(qū)溢出問題

　　二進(jìn)制安全

　　． c 字符串是根據(jù)空字符 \\0 來判斷字符串是否結(jié)束，因此字符串中間不能有空字符， 只能用來保存文本內(nèi)容，無法保存二進(jìn)制數(shù)據(jù)

　?。?SDS 是通過 len 來判斷字符串是否結(jié)束，因此既可以保存文本內(nèi)容，又可以保存二進(jìn)制數(shù)據(jù)

　　內(nèi)存分配

　　． c 字符串每次修改內(nèi)容時都需要進(jìn)行重新的內(nèi)存分配

　?。?SDS 則是根據(jù) free 判斷空間是否足夠，如果不足，重新內(nèi)配， 并且當(dāng)修改后的 len < 1M 時， 額外多分配 len 的長度， 此時 free = len ； 當(dāng)縮短 SDS 字符串內(nèi)容時， 并不會立即釋放空間, 而是通過將 free 變大，記錄剩余空間，以減少之后的再分配。（通過惰性釋放避免內(nèi)存浪費(fèi)問題）

　　字典

　　內(nèi)部實(shí)現(xiàn)

　　typedef struct dictEntry {

　　void *key;

　　union {

　　void *val;

　　uint64_t u64;

　　int64_t s64;

　　double d;

　　} v;

　　struct dictEntry *next;

　　} dictEntry;

　　typedef struct dictType {

　　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;

　　/* This is our hash table structure. Every dictionary has two of this as we

　　* implement incremental rehashing, for the old to the new table. */typedef struct dictht {

　　dictEntry **table;

　　unsigned long size;

　　unsigned long sizemask;

　　unsigned long used;

　　} dictht;

　　typedef struct dict {

　　dictType *type;

　　void *privdata;

　　dictht ht[2];

　　long rehashidx; /* rehashing not in progress if rehashidx == -1 */

　　int iterators; /* number of iterators currently running */

　　} dict;

　　結(jié)構(gòu)示意圖：

redis-dict

　　原理講解

　　字段

　　ht 字段

　　ht 是一個兩個項(xiàng)的數(shù)組，其中 ht[0] 用于存放哈希表， ht[1] 在哈希重排時使用

　　rehashidx 字段

　　當(dāng) rehashidx == -1 時，表示當(dāng)前不是在 rehash , 用于表示在進(jìn)行 rehash 操作時，進(jìn)行到了哪一步。

　　如何操作數(shù)據(jù)

　　假設(shè)現(xiàn)在需要添加一個數(shù)據(jù) <K, v="">, 先需要計(jì)算哈希值:

　　hash = dict->type->hashFunction(k);

　　然后根據(jù) sizemask 求出索引值:

　　index = hash & dict->ht[x]->sizemask;

　　// x 表示實(shí)際存放哈希表的索引， 一般為 0 ，當(dāng)在進(jìn)行 rehash 時為 1

　　這樣就可以將 <K, v="">存儲在 dict->ht[x]->table[index] 中， 如果 table[index] 中已經(jīng)有數(shù)據(jù)， 則新添加的數(shù)據(jù)放在鏈表表頭. (這是因?yàn)?nbsp;table[index] 中的鏈表時一個單鏈表，沒有指向鏈表尾部的指針，添加到表頭更快)

　　rehash 過程

　　當(dāng)哈希表保存的數(shù)據(jù)太多或太少時，需要對哈希表進(jìn)行相應(yīng)的擴(kuò)容或者收縮。

　　如果進(jìn)行擴(kuò)容操作，那么 ht[1] 的大小為第一個不小于 ht[0].used * 2 的 2^n (n 為正整數(shù))， 如: used = 5 , ht[0].used * 2 = 10 < 2^4 = 16 , 所以 ht[1] 的大小為：16 ．

　　然后就可以將 ht[0] 的數(shù)據(jù)哈希到 ht[1] 中， 當(dāng) ht[0] 中的數(shù)據(jù)全部哈希到 ht[1] 后， 釋放 ht[0] , 將 ht[1] 變 ht[0]

　　擴(kuò)展的觸發(fā)條件

　　1. 在沒有執(zhí)行 BGSAVE 或 BGREWRITEAOF 時，哈希表的負(fù)載因子 >= 1

　　2. 在執(zhí)行 BGSAVE 或 BGREWRITEAOF 時，哈希表的負(fù)載因子 >= 5

　　負(fù)載因子的計(jì)算：

　　load_factor = ht[0].used / ht[0].size

　　在進(jìn)行 BGSAVE 或 BGREWRITEAOF 時，提高負(fù)載因子是為了避免擴(kuò)容，避免不必要的內(nèi)存寫入

　　收縮的觸發(fā)條件

　　負(fù)載因子 < 0.1

　　漸進(jìn)式哈希

　　在擴(kuò)容或者收縮時，需要將 ht[0] 全部哈希到 ht[1] , 如果一次性哈希， 當(dāng)數(shù)據(jù)足夠多時，會存在效率問題。因此 redis 通過逐步哈希的方式，其具體過程如下：

　　1. 為 ht[1] 分配空間

　　2. 設(shè)置 rehashidx = 0

　　3. 新添加的數(shù)據(jù)不再加入到 ht[0] , 而是加入到 ht[1] 中，保證 ht[0] 不會增加數(shù)據(jù)

　　4. 將 ht[0]->table[rehashidx] 的數(shù)據(jù)全部哈希到 ht[1] 中

　　5. rehashidx++

　　6. 隨著不斷的執(zhí)行， ht[0] 的數(shù)據(jù)哈希到了 ht[1] , 這是可以 設(shè)置 rehashidx = 1 ， 表明 rehash 結(jié)束，釋放 ht[0] , ht[1] 設(shè)置為 ht[0]

　　在 rehash 的過程中， 刪除，查找，更新會同時在 ht[0] , ht[1] 中進(jìn)行， 但是添加只會在 ht[1] 中。

 

來源：簡書