Redis設計與實現之簡單動態字串

語言: CN / TW / HK

簡單動態字串

什麼是 SDS

SDS ,即 Simple Dynamic String,簡單動態字串。

Redis 沒有直接使用 C 語言傳統的字串表示(以空字元結尾的字元陣列),而是自己構建了一種名為簡單動態字串(simple dynamic string,SDS)的抽象型別,並將 SDS 用作 Redis 的預設字串表示。

在 Redis 裡面,C 字串只會作為字串字面量(string literal)用在一些 無須對字串值進行修改的地方 ,比如列印日誌。

當 Redis 需要的不僅僅是一個字串字面量,而是一個可以被修改的字串值時,Redis 就會使用 SDS 來表示字串值,比如在 Redis 的資料庫裡面,包含字串值的 鍵值 對在底層都是由 SDS 實現的。

SDS 的定義

在 SDS 結構中包含:

buf
len
free

舉例:

  • len 屬性的值等於 5,表示在 SDS 中儲存了一個五位元組長度的字串
  • free 屬性的值等於 0,表示在 SDS 中沒有分配任何未使用的空間
  • buf 屬性是一個 char 陣列,前五位儲存了五個字元,在最後一個位元組儲存了一個空字元'\0'

需要注意的是:SDS 遵循 C 字串以空字元結尾的慣例,儲存空字元的 1 位元組空間並不計算在 SDS 的 len 屬性中,並且分配這額外的 1 位元組空間,以及新增空字元到字串末尾等操作,都是由 SDS 函式自動完成的。

剛才展示了 free 為 0 的情況,而存在未使用空間的時候則如下圖,我們還是使用“Redis”字串。

SDS 與 C 字串的區別

剛才我們說過 C 語言使用長度為 N+1 的字元陣列來表示長度為 N 的字串,並且字元陣列的最後一個元素總是空字元'\0'。

這種簡單的字串表示方式,並不能滿足 Redis 對字串的安全性、效率以及功能上的要求。我們接下來對比一下 SDS 和 C 字串之間的區別。

常數複雜度獲取字串長度

首先 C 字串並不記錄自身的長度資訊,要是想獲取 C 字串長度,則必須遍歷整個字串,對遇到的每個字元進行計數,直到遇到結尾識別符號'\0'為止。複雜度為 O(N)。

而 SDS 不同,SDS 中的 len 屬性記錄了 SDS 本身的長度,所以獲取 SDS 字串長度的複雜度僅僅為 O(1)。

需要注意的是,設定和更新 SDS 長度的工作是由 SDS 的 API 在執行的時候自動完成的。

使用 SDS 將獲取字串長度從複雜度 O(N)降低到了 O(1),確保了在 Redis 中獲取字串長度不會成為效能瓶頸。

杜絕緩衝區溢位

除了獲取字串長度的複雜度高之外,C 字串不記錄自身長度帶來的另一個問題就是容易造成緩衝區溢位。

舉個例子,在 string.h 中 strcat 函式可以將 src 字串中的內容拼接到 dest 字串的末尾。

char *strcat(char *dest, const char *src);

由於 C 字串不記錄自身長度,如果沒有為 dest 分配足夠多的記憶體來容下 src 字串的所有內容的話,則會發生緩衝區溢位。

:loudspeaker: 需要注意,如果記憶體中相鄰 s1,s2 兩個字串,如果在修改 s1 字串的時候沒有分配足夠的空間,可能會導致溢位到 s2 字串所在的記憶體空間,導致 s2 字串被篡改。

而 SDS 不同,SDS 的 空間分配策略 完全杜絕了發生緩衝區溢位的可能。在對 SDS 進行修改的時候,API 首先會檢查是否滿足所需的要求,如果不滿足則會自動進行擴容,然後再進行修改。

舉例:

如上圖,這時候我們執行

sdscat(s," Cluster");

首先在拼接之前會進行檢測當前 s 的長度是否足夠,發現不足以拼接" Cluster"後,進行擴容,隨後進行拼接,如下圖所示。

:loudspeaker: 需要注意:SDS 不僅僅進行了拼接操作,還另外分配了 13 位元組的未使用空間,下面我們會了解 SDS 的空間分配策略。

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

我們剛才說過,C 字串是不記錄字串長度的,所以在增加或縮短一個字串時,都要進行記憶體重分配操作。

  • 如果執行的是增長字串操作,比如 append,那麼在操作前需要通過記憶體重分配策略來擴充套件底層陣列的大小,如果忘記這一步,則會發生緩衝區溢位
  • 如果執行的是縮短字串操作,比如 trim,那麼在執行這個操作後需要進行記憶體重分配來釋放不再使用的空間,如果忘記這一步,則會發生記憶體洩漏

為了避免 C 字串的這種缺陷,SDS 通過未使用空間 free 解除了字串長度與底層陣列長度之間的關聯,在 SDS 中,buf 陣列的長度並不一定是字元數量加一,還可能包含未使用位元組。

通過未使用空間 free,SDS 實現了空間預分配和惰性空間釋放兩種優化策略。

1.空間預分配

顧名思義,SDS 在進行擴充套件的時候,不僅僅會為 SDS 分配修改所必要的空間,還會為 SDS 分配額外的未使用空間。

空閒空間分配策略:

len = free

通過這種預分配策略,SDS 將連續增長 N 次的字串所需記憶體操作次數從必定 N 次減少到了最多 N 次。

2.惰性空間釋放

在進行縮短字串操作時,SDS 並不會立即使用記憶體重分配來進行回收多餘的空間,而是使用 free 進行記錄,在後續如果進行增長操作的時候,就可能不需要再進行擴容。SDS 也提供了 API,來進行釋放 SDS 未使用的空間。

二進位制安全

我們知道 C 字串末尾是空字元表示,在中間是不能包含空字元,否則會被認為是字元結尾。並且需要符合某種編碼(比如 ASCII),導致 C 字串只能儲存文字資料,無法儲存圖片、影片等二進位制資料。

SDS 的 API 都是二進位制安全的,程式並不會對資料進行任何處理,寫入時是什麼樣子,讀取時候就是什麼樣子,而且在 SDS 中是可以包含空字元,因為 SDS 中是使用 len 來判斷字串是否結束。

但是為什麼 SDS 末尾還是會有一個空字元?這是為了可以重用 <string.h> 中的部分函式,避免不必要的程式碼重複。

總結

C 字串 SDS
獲取字串長度為 O(N) 獲取字串長度為 O(1)
API 不是安全的,可能造成緩衝區溢位 API 是安全的,不會造成緩衝區溢位
修改字串 N 次則必須要 N 次記憶體重分配 修改字串 N 次則最多進行 N 次記憶體重分配
只能儲存文字資料 不僅可以儲存文字資料也可以儲存二進位制資料
可以使用所有<string.h>庫中的函式 可以使用部分<string.h>庫中的函式