幾分鐘教你掌握Redis簡單動態字串SDS

2023-01-28 18:01:53

正文

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

在 Redis 裡面，C 字串只會作為字串字面量（string literal），用在一些無須對字串值進行修改的地方，比如列印紀錄檔：

redisLog(REDIS_WARNING,"Redis is now ready to exit, bye bye...");

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

舉個例子，如果使用者端執行命令：

redis> SET msg "hello world"
OK

那麼 Redis 將在資料庫中建立了一個新的鍵值對，其中：

鍵值對的鍵是一個字串物件，物件的底層實現是一個儲存著字串 "msg" 的 SDS 。
鍵值對的值也是一個字串物件，物件的底層實現是一個儲存著字串 "hello world" 的SDS。

又比如說，如果使用者端執行命令：

redis> RPUSH fruits "apple" "banana" "cherry"
(integer) 3

那麼 Redis 將在資料庫中建立一個新的鍵值對，其中：

鍵值對的鍵是一個字串物件，物件的底層實現是一個儲存了字串 "fruits" 的 SDS 。
鍵值對的值是一個列表物件，列表物件包含了三個字串物件，這三個字串物件分別由三個 SDS 實現：第一個 SDS 儲存著字串 "apple" ，第二個 SDS 儲存著字串 "banana" ，第三個 SDS 儲存著字串 "cherry" 。

除了用來儲存資料庫中的字串值之外，SDS 還被用作緩衝區（buffer）：AOF 模組中的 AOF 緩衝區，以及使用者端狀態中的輸入緩衝區，都是由 SDS 實現的，在之後介紹 AOF 持久化和使用者端狀態的時候，我們會看到 SDS 在這兩個模組中的應用。

AOF中記錄的是每一個命令的詳細資訊，包括完整的命令型別、引數等。只要產生寫命令，就會實時寫入到AOF檔案中

SDS的定義

struct sdshdr {
    // 記錄 buf 陣列中已使用位元組的數量
    int len;
    // 記錄 buf 陣列中未使用位元組的數量
    int free;
    // 位元組陣列，用於儲存字串
    char buf[];
};

與C字串的區別

C語言使用長度為 N+1 的字元陣列來表示長度為 N 的字串，並且字元陣列的最後一個元素總是空字元 ''。

獲取字串長度

因為 C 字串並不記錄自身的長度資訊，所以為了獲取一個 C 字串的長度，程式必須遍歷整個字串O(N)O(N)O(N) 。

和 C 字串不同，因為 SDS 在 len 屬性中記錄了 SDS 本身的長度，所以獲取一個 SDS 長度的複雜度僅為 O(1)O(1)O(1) 。

杜絕緩衝區溢位

C 字串不記錄自身長度帶來的另一個問題是容易造成緩衝區溢位（buffer overflow）。

假設程式裡有兩個在記憶體中緊鄰著的 C 字串 s1 和 s2 ，其中 s1 儲存了字串 "Redis" ，而 s2 則儲存了字串 "MongoDB" .

如果一個程式設計師決定通過執行：strcat(s1, "Cluster")將 s1 的內容修改為 "Redis Cluster" ，但粗心的他卻忘了在執行 strcat 之前為 s1 分配足夠的空間，那麼在 strcat 函數執行之後，s1 的資料將溢位到 s2 所在的空間中，導致 s2 儲存的內容被意外地修改。

SDS 的空間分配策略完全杜絕了發生緩衝區溢位的可能性：當 SDS API 需要對 SDS 進行修改時，API 會先檢查 SDS 的空間是否滿足修改所需的要求，如果不滿足的話，API 會自動將 SDS 的空間擴充套件至執行修改所需的大小，然後才執行實際的修改操作，所以使用 SDS 既不需要手動修改 SDS 的空間大小，也不會出現前面所說的緩衝區溢位問題。