《Redis設計與實現》讀書筆記

簡單動態字元串

SDS的定義

結構：

buf數組：用於保存字元串

len屬性：記錄SDS中保存字元串的長度

free屬性：記錄buf中未使用位元組數量

遵循C字元串以空字元串結尾的慣例，保存空字元串的位元組不計入長度

SDS與C字元串的區別

常數複雜度獲取字元串長度

因為SDS中的len屬性已經記錄了字元串長度，所以不需要像C字元串一樣獲取長度時需要遍歷一遍字元串。確保獲取字元串長度的工作不會限制Redis的性能瓶頸

杜絕緩衝區溢出

當SDS API需要對SDS進行修改時，API會先檢查SDS的空間是否滿足修改所需要的要求，如果不滿足的話，API會自動將SDS的空間擴展至執行修改所需要的大小

減少修改字元串時帶來的記憶體重分配次數

C字元串修改時，需要程式重新分配記憶體，防止記憶體溢出或泄露。對於一個資料庫來說嗎，對於速度的要求時苛刻的，且數據會被頻繁的修改。而重分配會占用大量時間，修改頻繁的話，可能會對性能照成影響

而SDS通過free屬性，實現了空間預分配與惰性空間釋放兩種優化策略

1.空間預分配

SDS進行修改後len小於1MB時：程式會分配和len相同大小的未使用空間

SDS進行修改後len大於1MB時：程式會分配1MB的未使用空間

2.惰性空間釋放

當需要縮短SDS的字元串時，程式不會立刻重分配來回收多餘位元組，而是先使用free將這些位元組記錄起來，等待將來再使用

二進位安全

SDS API會以二進位的方式來處理SDS存放在數組裡面的數據

相容部分C字元串函數

因為SDS遵循了C字元串以空字元串結尾的慣例

SDS API

鏈表

鏈表與鏈表節點的實現

每個鏈表節點使用一個 adlist.h/listNode 結構來表示：

 typedef struct listNode {
 ​
     // 前置節點
     struct listNode *prev;
 ​
     // 後置節點
     struct listNode *next;
 ​
     // 節點的值
     void *value;
 ​
 } listNode;

多個 listNode 可以通過 prev 和 next 指針組成雙端鏈表

雖然僅僅使用多個 listNode 結構就可以組成鏈表， 但使用 adlist.h/list 來持有鏈表的話， 操作起來會更方便：

 typedef struct list {
 ​
     // 表頭節點
     listNode *head;
 ​
     // 表尾節點
     listNode *tail;
 ​
     // 鏈表所包含的節點數量
     unsigned long len;
 ​
     // 節點值複製函數
     void *(*dup)(void *ptr);
 ​
     // 節點值釋放函數
     void (*free)(void *ptr);
 ​
     // 節點值對比函數
     int (*match)(void *ptr, void *key);
 ​
 } list;

list 結構為鏈表提供了表頭指針 head 、表尾指針 tail ， 以及鏈表長度計數器 len ， 而 dup 、 free 和 match 成員則是用於實現多態鏈表所需的類型特定函數：

• dup 函數用於複製鏈表節點所保存的值；

• free 函數用於釋放鏈表節點所保存的值；

• match 函數則用於對比鏈表節點所保存的值和另一個輸入值是否相等。

Redis 的鏈表實現的特性可以總結如下：

• 雙端： 鏈表節點帶有 prev 和 next 指針， 獲取某個節點的前置節點和後置節點的複雜度都是 。

• 無環： 表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL ， 對鏈表的訪問以 NULL 為終點。

• 帶表頭指針和表尾指針： 通過 list 結構的 head 指針和 tail 指針， 程式獲取鏈表的表頭節點和表尾節點的複雜度為 。

• 帶鏈表長度計數器： 程式使用 list 結構的 len 屬性來對 list 持有的鏈表節點進行計數， 程式獲取鏈表中節點數量的複雜度為 。

• 多態： 鏈表節點使用 void* 指針來保存節點值， 並且可以通過 list 結構的 dup 、 free 、 match 三個屬性為節點值設置類型特定函數， 所以鏈表可以用於保存各種不同類型的值。

鏈表和鏈表節點的API

字典

字典的實現

哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 結構定義：

 typedef struct dictht {
 ​
     // 哈希表數組
     dictEntry **table;
 ​
     // 哈希表大小
     unsigned long size;
 ​
     // 哈希表大小掩碼，用於計算索引值
     // 總是等於 size - 1
     unsigned long sizemask;
 ​
     // 該哈希表已有節點的數量
     unsigned long used;
 ​
 } dictht;

table 屬性是一個數組， 數組中的每個元素都是一個指向 dict.h/dictEntry 結構的指針， 每個 dictEntry 結構保存著一個鍵值對。

size 屬性記錄了哈希表的大小， 也即是 table 數組的大小， 而 used 屬性則記錄了哈希表目前已有節點（鍵值對）的數量。

sizemask 屬性的值總是等於 size - 1 ， 這個屬性和哈希值一起決定一個鍵應該被放到 table 數組的哪個索引上面。

哈希表節點

哈希表節點使用 dictEntry 結構表示， 每個 dictEntry 結構都保存著一個鍵值對：

 typedef struct dictEntry {
 ​
     // 鍵
     void *key;
 ​
     // 值
     union {
         void *val;
         uint64_t u64;
         int64_t s64;
     } v;
 ​
     // 指向下個哈希表節點，形成鏈表
     struct dictEntry *next;
 ​
 } dictEntry;

key 屬性保存著鍵值對中的鍵， 而 v 屬性則保存著鍵值對中的值， 其中鍵值對的值可以是一個指針， 或者是一個 uint64_t 整數， 又或者是一個 int64_t 整數。

next 屬性是指向另一個哈希表節點的指針， 這個指針可以將多個哈希值相同的鍵值對連接在一次， 以此來解決鍵衝突（collision）的問題。

舉個例子， 圖 4-2 就展示瞭如何通過 next 指針， 將兩個索引值相同的鍵 k1 和 k0 連接在一起。

字典

Redis 中的字典由 dict.h/dict 結構表示：

 typedef struct dict {
 ​
     // 類型特定函數
     dictType *type;
 ​
     // 私有數據
     void *privdata;
 ​
     // 哈希表
     dictht ht[2];
 ​
     // rehash 索引
     // 當 rehash 不在進行時，值為 -1
     int rehashidx; /* rehashing not in progress if rehashidx == -1 */
 ​
 } dict;

type 屬性和 privdata 屬性是針對不同類型的鍵值對， 為創建多態字典而設置的：

• type 屬性是一個指向 dictType 結構的指針， 每個 dictType 結構保存了一簇用於操作特定類型鍵值對的函數， Redis 會為用途不同的字典設置不同的類型特定函數。

• 而 privdata 屬性則保存了需要傳給那些類型特定函數的可選參數。

 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;

ht 屬性是一個包含兩個項的數組， 數組中的每個項都是一個 dictht 哈希表， 一般情況下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只會在對 ht[0] 哈希表進行 rehash 時使用。

除了 ht[1] 之外， 另一個和 rehash 有關的屬性就是 rehashidx ： 它記錄了 rehash 目前的進度， 如果目前沒有在進行 rehash ， 那麼它的值為 -1 。

哈希演算法

將新的鍵值插入字典時，程式需要先根據鍵值對的鍵計算出哈希值和索引值，然後根據索引值將新鍵值對所在的哈希表節點放到哈希表數組對應的索引上面

Redis 計算哈希值和索引值的方法如下：

 # 使用字典設置的哈希函數，計算鍵 key 的哈希值
 hash = dict->type->hashFunction(key);
 ​
 # 使用哈希表的 sizemask 屬性和哈希值，計算出索引值
 # 根據情況不同， ht[x] 可以是 ht[0] 或者 ht[1]
 index = hash & dict->ht[x].sizemask;

解決鍵衝突

當兩個或兩個以上的鍵分配到哈希數組的同一個索引上時，Redis使用鏈地址法解決鏈衝突

鏈地址法

哈希表節點都有一個next指針，可以使用next指針構成單向鏈表。

且dictEntry節點構成的鏈表沒有指向鏈表末尾的指針，為了節省時間，新的節點一般直接添加到表頭位置

rehash（重新散列）

目的

隨著哈希表鍵值對的逐漸增加或減少，為了讓哈希表的負載因數維持在一定範圍內

步驟

1. 為字典的 ht[1] 哈希表分配空間，這個哈希表的空間大小取決於要執行的操作， 以及 ht[0] 當前包含的鍵值對數量 （也即是ht[0].used屬性的值）：

   • 如果執行的是擴展操作， 那麼 ht[1] 的大小為第一個大於等於 ht[0].used * 2 的 （2 的 n 次方冪）；

   • 如果執行的是收縮操作， 那麼 ht[1] 的大小為第一個大於等於 ht[0].used 的 。

2. 將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上面： rehash 指的是重新計算鍵的哈希值和索引值， 然後將鍵值對放置到 ht[1] 哈希表的指定位置上。

3. 當 ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之後 （ht[0] 變為空表）， 釋放 ht[0] ， 將 ht[1] 設置為 ht[0] ， 併在 ht[1] 新創建一個空白哈希表， 為下一次 rehash 做準備。

哈希表的收縮與擴展

以下條件滿足任意一個時，程式會自動開始對哈希表執行擴展操作：

1. 伺服器目前沒有在執行 BGSAVE 命令或者 BGREWRITEAOF 命令， 並且哈希表的負載因數大於等於 1

2. 伺服器目前正在執行 BGSAVE 命令或者 BGREWRITEAOF 命令， 並且哈希表的負載因數大於等於 5

負載因數計算公式：

 # 負載因數 = 哈希表已保存節點數量 / 哈希表大小
 load_factor = ht[0].used / ht[0].size

當哈希表的負載因數小於 0.1 時， 程式自動開始對哈希表執行收縮操作

漸進式rehash

目的：

假如哈希表中保存了大量的數據，一次性將這些數據進行rehash時會產生龐大的計算量，為了防止rehash對redis的性能產生影響

漸進式rehash實現的詳細步驟：

1. 為 ht[1] 分配空間， 讓字典同時持有 ht[0] 和 ht[1] 兩個哈希表。

2. 在字典中維持一個索引計數器變數 rehashidx ， 並將它的值設置為 0 ， 表示 rehash 工作正式開始。

3. 在 rehash 進行期間， 每次對字典執行添加、刪除、查找或者更新操作時， 程式除了執行指定的操作以外， 還會順帶將 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] ， 當 rehash 工作完成之後， 程式將 rehashidx 屬性的值增一。

4. 隨著字典操作的不斷執行， 最終在某個時間點上， ht[0] 的所有鍵值對都會被 rehash 至 ht[1] ， 這時程式將 rehashidx 屬性的值設為 -1 ， 表示 rehash 操作已完成。

漸進式rehash執行期間的哈希表操作

• 字典的刪改查等操作都會在兩個哈希表之間共同進行

• 新增加的鍵只添加ht[1]上

字典API

跳躍表