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

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

struct sdshdr {
  len int; // 所保存的字符串長度
  free int; // 未使用的字節(jié)長度
  char buf[]; // 字節(jié)數(shù)組，用于保存字符串
}

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

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

獲取字符串長度

• c 字符串獲取長度是逐個讀取字符計算長度，時間復雜度為: O(N)
• SDS 是通過 len 來獲取字符串長度，時間復雜度為: O(1)

API 安全

• c 字符串不會檢查內(nèi)存空間是否足夠，當拼接字符串時，有可能會出現(xiàn)緩沖區(qū)溢出問題
• SDS 則會根據(jù) free 來判斷空間是否足夠，如果內(nèi)存空間不足，則會申請內(nèi)存空間，因此不會有緩沖區(qū)溢出問題

二進制安全

• c 字符串是根據(jù)空字符 \0 來判斷字符串是否結束，因此字符串中間不能有空字符， 只能用來保存文本內(nèi)容，無法保存二進制數(shù)據(jù)
• SDS 是通過 len 來判斷字符串是否結束，因此既可以保存文本內(nèi)容，又可以保存二進制數(shù)據(jù)

內(nèi)存分配

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

字典

內(nèi)部實現(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;

結構示意圖：

redis-dict

原理講解

字段

ht 字段

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

rehashidx 字段

當 rehashidx == -1 時，表示當前不是在 rehash, 用于表示在進行 rehash 操作時，進行到了哪一步。

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

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

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

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

 index = hash & dict->ht[x]->sizemask;   
 // x 表示實際存放哈希表的索引， 一般為 0 ，當在進行 rehash 時為 1

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

rehash 過程

當哈希表保存的數(shù)據(jù)太多或太少時，需要對哈希表進行相應的擴容或者收縮。
如果進行擴容操作，那么 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] 中， 當 ht[0] 中的數(shù)據(jù)全部哈希到 ht[1] 后， 釋放 ht[0], 將 ht[1] 變 ht[0]

擴展的觸發(fā)條件

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

負載因子的計算：

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

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

收縮的觸發(fā)條件

負載因子 < 0.1

漸進式哈希

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

1. 為 ht[1] 分配空間
2. 設置 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], 這是可以 設置 rehashidx = 1， 表明 rehash 結束，釋放 ht[0], ht[1] 設置為 ht[0]

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