文章目錄

• • SDS
  • 鏈表
  • 字典

這篇文章關于 Redis 的基礎數據:

SDS

SDS （Simple Dynamic String）是 Redis 最基礎的數據結構。直譯過來就是”簡單的動態字符串“。Redis 自己實現了一個動態的字符串，而不是直接使用了 C 語言中的字符串。

sds 的數據結構：

struct sdshdr {// buf 中已占用空間的長度int len;// buf 中剩余可用空間的長度int free;// 數據空間char buf[]; };

所以一個 SDS 的就如下圖：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-t2YCOSKC-1573627290412)(media/15663750838907/15663751675407.jpg)]
所以我們看到，sds 包含3個參數。buf 的長度 len，buf 的剩余長度，以及buf。

為什么這么設計呢？

可以直接獲取字符串長度。
C 語言中，獲取字符串的長度需要用指針遍歷字符串，時間復雜度為 O(n)，而 SDS 的長度，直接從len 獲取復雜度為 O(1)。

杜絕緩沖區溢出。
由于C 語言不記錄字符串長度，如果增加一個字符傳的長度，如果沒有注意就可能溢出，覆蓋了緊挨著這個字符的數據。對于SDS 而言增加字符串長度需要驗證 free的長度，如果free 不夠就會擴容整個 buf，防止溢出。

減少修改字符串長度時造成的內存再次分配。
redis 作為高性能的內存數據庫，需要較高的相應速度。字符串也很大概率的頻繁修改。 SDS 通過未使用空間這個參數，將字符串的長度和底層buf的長度之間的額關系解除了。buf的長度也不是字符串的長度?；谶@個分設計 SDS 實現了空間的預分配和惰性釋放。

• 預分配
  如果對 SDS 修改后，如果 len 小于 1MB 那 len = 2 * len + 1byte。 這個 1 是用于保存空字節。
  如果 SDS 修改后 len 大于 1MB 那么 len = 1MB + len + 1byte。
• 惰性釋放
  如果縮短 SDS 的字符串長度，redis并不是馬上減少 SDS 所占內存。只是增加 free 的長度。同時向外提供 API 。真正需要釋放的時候，才去重新縮小 SDS 所占的內存

• 二進制安全。
  C 語言中的字符串是以 ”\0“ 作為字符串的結束標記。而 SDS 是使用 len 的長度來標記字符串的結束。所以SDS 可以存儲字符串之外的任意二進制流。因為有可能有的二進制流在流中就包含了”\0“造成字符串提前結束。也就是說 SDS 不依賴 “\0” 作為結束的依據。

• 兼容C語言
  SDS 按照慣例使用 ”\0“ 作為結尾的管理。部分普通C 語言的字符串 API 也可以使用。

鏈表

C語言中并沒有鏈表這個數據結構所以 Redis 自己實現了一個。Redis 中的鏈表是：

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

非常典型的雙向鏈表的數據結構。

同時為雙向鏈表提供了如下操作的函數：

/** 雙端鏈表迭代器*/ typedef struct listIter {// 當前迭代到的節點listNode *next;// 迭代的方向int direction;} listIter;/** 雙端鏈表結構*/ typedef struct list {// 表頭節點listNode *head;// 表尾節點listNode *tail;// 節點值復制函數void *(*dup)(void *ptr);// 節點值釋放函數void (*free)(void *ptr);// 節點值對比函數int (*match)(void *ptr, void *key);// 鏈表所包含的節點數量unsigned long len;} list;

鏈表的結構比較簡單，數據結構如下：
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-pwkSNd6w-1573627290413)(media/15663750838907/15663752964435.jpg)]

總結一下性質：

• 雙向鏈表，某個節點尋找上一個或者下一個節點時間復雜度 O(1)。
• list 記錄了 head 和 tail，尋找 head 和 tail 的時間復雜度為 O(1)。
• 獲取鏈表的長度 len 時間復雜度 O(1)。

字典

字典數據結構極其類似 java 中的 Hashmap。

Redis的字典由三個基礎的數據結構組成。最底層的單位是哈希表節點。結構如下：

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

實際上哈希表節點就是一個單項列表的節點。保存了一下下一個節點的指針。 key 就是節點的鍵，v是這個節點的值。這個 v 既可以是一個指針，也可以是一個 uint64_t或者 int64_t 整數。*next 指向下一個節點。

通過一個哈希表的數組把各個節點鏈接起來：

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

通過圖示我們觀察：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-FVEBYd5O-1573627290413)(media/15663750838907/15663753610286.jpg)]

實際上，如果對java 的基本數據結構了解的同學就會發現，這個數據結構和 java 中的 HashMap 是很類似的，就是數組加鏈表的結構。

字典的數據結構：

typedef struct dict {// 類型特定函數dictType *type;// 私有數據void *privdata;// 哈希表dictht ht[2];// rehash 索引// 當 rehash 不在進行時，值為 -1int rehashidx; /* rehashing not in progress if rehashidx == -1 */// 目前正在運行的安全迭代器的數量int iterators; /* number of iterators currently running */} dict;

其中的dictType 是一組方法，代碼如下：

/** 字典類型特定函數*/ 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;

字典的數據結構如下圖：
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-PI20viEC-1573627290414)(media/15663750838907/15663754115428.jpg)]

這里我們可以看到一個dict 擁有兩個 dictht。一般來說只使用 ht[0],當擴容的時候發生了rehash的時候，ht[1]才會被使用。

當我們觀察或者研究一個hash結構的時候偶我們首先要考慮的這個 dict 如何插入一個數據？

我們梳理一下插入數據的邏輯。

• 計算Key 的 hash 值。找到 hash 映射到 table 數組的位置。

• 如果數據已經有一個 key 存在了。那就意味著發生了 hash 碰撞。新加入的節點，就會作為鏈表的一個節點接到之前節點的 next 指針上。

• 如果 key 發生了多次碰撞，造成鏈表的長度越來越長。會使得字典的查詢速度下降。為了維持正常的負載。Redis 會對 字典進行 rehash 操作。來增加 table 數組的長度。所以我們要著重了解一下 Redis 的 rehash。步驟如下：

  • 根據ht[0] 的數據和操作的類型（擴大或縮小），分配 ht[1] 的大小。
  • 將 ht[0] 的數據 rehash 到 ht[1] 上。
  • rehash 完成以后，將ht[1] 設置為 ht[0]，生成一個新的ht[1]備用。

• 漸進式的 rehash 。

其實如果字典的 key 數量很大，達到千萬級以上，rehash 就會是一個相對較長的時間。所以為了字典能夠在 rehash 的時候能夠繼續提供服務。Redis 提供了一個漸進式的 rehash 實現
rehash的步驟如下：

分配 ht[1] 的空間，讓字典同時持有 ht[1] 和 ht[0]。

在字典中維護一個 rehashidx，設置為 0 ，表示字典正在 rehash。

在rehash期間，每次對字典的操作除了進行指定的操作以外，都會根據 ht[0] 在 rehashidx 上對應的鍵值對 rehash 到 ht[1]上。

隨著操作進行， ht[0] 的數據就會全部 rehash 到 ht[1] 。設置ht[0] 的 rehashidx 為 -1，漸進的 rehash 結束。
這樣保證數據能夠平滑的進行 rehash。防止 rehash 時間過久阻塞線程。

• 在進行 rehash 的過程中，如果進行了 delete 和 update 等操作，會在兩個哈希表上進行。如果是 find 的話優先在ht[0] 上進行，如果沒有找到，再去 ht[1] 中查找。如果是 insert 的話那就只會在 ht[1]中插入數據。這樣就會保證了 ht[1] 的數據只增不減，ht[0]的數據只減不增。

總結

以上是生活随笔為你收集整理的redis源码剖析（三）——基础数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。