本文首發於公眾號：Hunter後端 原文鏈接：Redis數據結構二之SDS和雙向鏈表 這一篇筆記介紹一下 SDS（simple dynamic string）和雙向鏈表。 以下是本篇筆記目錄： SDS 常數複雜度獲取字元串長度 杜絕緩衝區溢出 減少修改字元串帶來的記憶體重分配次數 二進位安全 相容C字 ...
本文首發於公眾號：Hunter後端
原文鏈接：Redis數據結構二之SDS和雙向鏈表
這一篇筆記介紹一下 SDS（simple dynamic string）和雙向鏈表。
以下是本篇筆記目錄：
- SDS
- 常數複雜度獲取字元串長度
- 杜絕緩衝區溢出
- 減少修改字元串帶來的記憶體重分配次數
- 二進位安全
- 相容C字元串函數
- 雙向鏈表
1、 SDS
SDS，simple dynamic string，即簡單動態字元串
SDS 在 Redis 2.9 版本中數據結構如下：
struct sdshdr {
int len;
int free;
char buf[];
};
在這個結構中，len 表示 buf 數組中已使用位元組的數量，free 表示 buf 數組中未使用位元組的數量，buf 則表示是一個 char 類型的數組。
Redis 沒有復用 C字元串，有以下幾個方面的考慮和優點。
1. 常數複雜度獲取字元串長度
C字元串並不記錄自身的長度信息，如果要獲取C字元串的長度，必須遍歷整個字元串然後計數。
SDS 結構中有 len 屬性記錄 SDS 本身的長度，可以直接獲取。
2. 杜絕緩衝區溢出
因為 C字元串並不記錄自身的長度信息，在執行某些操作，比如拼接字元串的時候，並不會自動查詢是否擁有足夠記憶體，那麼這個操作可能就會造成緩衝區溢出的問題
而 SDS 執行相應的字元串修改時，其 API 會先檢查 SDS 的空間是否需求，不滿足則會進行擴展，這個空間分配策略也就是下麵要講的
3. 減少修改字元串帶來的記憶體重分配次數
C字元串每次進行字元串修改時，程式都需要手動進行記憶體重分配的操作，而 SDS 通過空間預分配和惰性空間釋放兩種策略對此進行了優化
空間預分配
當 SDS API 對一個 SDS 進行修改並需要對 SDS 進行空間擴展時，程式不僅會為 SDS 分配修改所需要的空間，還會為其分配額外的未使用空間
如果修改之後，SDS 的長度，也就是結構中的 len 屬性小於 1MB，那麼程式會額外分配同樣大小的未使用空間，這個時候，len 屬性和 free 屬性將相同
如果修改之後，SDS 的長度，也就是結構中的 len 屬性大於等於 1MB，那麼程式會額外分配 1MB 的未使用空間
惰性空間釋放
當需要對SDS保存的字元串進行縮短時，程式並不會重新分配記憶體來回收多出來的位元組，而是會使用 free 屬性將這些位元組記錄下來，以備後面使用
4. 二進位安全
C字元串保存的字元結尾都是以空字元結尾，所以字元串中間不能包含空字元，否則程式讀入空字元的時候就會被認為是字元串結尾，因此C字元串只能保存文本數據，不能保存圖片、音頻等這樣的二進位數據
而 SDS 的 API 都是以處理二進位的方式來處理 SDS 中存放在 buf 里的數據，程式不會對數據做任何限制、過濾，所以 SDS 的 API 都是二進位安全的
SDS 使用 len 屬性值而不是空字元串來判斷字元串是否結束
5. 相容C字元串函數
雖然SDS的API都是二進位安全的，但是仍然遵循C字元串以空字元結尾的慣例，而且在為 buf 數組分配空間的時候總是會多分配一個位元組來容納這個空字元，所以保存文本數據的 SDS 可以重用一部分C中的函數
以下是 SDS 與 C字元串區別的總結：
| C字元串 | SDS |
|---|---|
| 獲取字元串長度複雜度為 O(N) | 獲取字元串長度複雜度為O(1) |
| API是不安全的，可能會造成緩衝區溢出 | API是安全的，不會造成緩衝區溢出 |
| 修改字元串長度N次必須執行N次記憶體重分配 | 修改長度N次最多需要執行N次記憶體重分配 |
| 只能保存文本數據 | 可以保存文本或者二進位數據 |
| 可以使用<string.h>庫中函數 | 可以使用部分 |
在之後的的 Redis 版本對 SDS 的結構有過更新，將 free 屬性換成了 alloc，這個屬性表示的意思是分配的空間長度。和之前的 free 屬性比較，其關係是 alloc = free + len
2、 雙向鏈表
C 語言沒有鏈表這個結構，所以 Redis 自己設計了一個鏈表數據結構。
在 Redis 中，鏈表節點的結構擁有指向前置節點和後置節點的屬性。
鏈表結構則包含鏈表表頭節點、表尾節點、節點長度等屬性，便於快速獲取鏈表相關信息。
雙向鏈表是列表對象的底層實現之一，什麼情況下使用雙向鏈表作為列表對象的底層實現我們之後再介紹。
以下是鏈表節點的結構：
typedef struct listNode{
// 前置節點
struct listNode *prev;
// 後置節點
struct listNode *next;
// 節點值
struct *value;
}listNode;
在鏈表節點中，擁有前置節點和後置節點的指針構成雙向的鏈表。
以下是鏈表的結構：
typedef struct list{
// 表頭節點
listNode *head;
// 表尾節點
listNode *tail;
// 鏈表包含的節點數量
unsigned long len;
...
}list;
在鏈表結構中，有表頭節點和表尾節點可快速定位到鏈表的頭部和尾部，以及用有 len 屬性表示鏈表包含的節點數量。
如果想獲取更多後端相關文章，可掃碼關註閱讀：
