面試題解 - Redis 的 String 是如何實現的？

作者丨安琪拉的博客

來源丨安琪拉的博客

第 44 題: Redis 的 String 是怎麼實現的？爲什麼不直接用 c 的字符串？

Redis 沒有直接使用 C 語言的字符串表示，而是自己構建一種簡單動態字符串（SDS: simple dynamic string）。

Redis 中的 String 都是 SDS，例如我們執行這樣一條命令:

redis> SET blog angela

那麼 Redis 在內存中創建了一個鍵值對，

• 鍵：鍵是一個字符串對象，對應底層實現是一個保存字符串 “blog” 的 SDS;

• 值：值也是一個字符串對象，對應底層實現是一個保存字符串是 “angela” 的 SDS。

如果執行

redis> RPUSH blog "angela" "de" "blog"

那麼 Redis 將在內存中創建一個鍵值對，鍵還是一個 SDS，存放 “blog”，值是一個列表，存放三個 SDS，“angela”、“de”、“blog”

SDS 如何實現的呢？

首先 SDS 被定義爲這樣一個結構體:

struct sdshdr {
   char buf[];//字節數組,用於保存字符串
   int len;//記錄buf數組中已使用字節的數量
   int free;//記錄buf數組中未使用字節的數量
}

舉個例子:

現有執行redis> SET blog angela 命令後，value 值在 redis 中存放如下圖所示，buf 存放字節數組 (真實數據)，len 表示存放字符串的長度（不包括結束符號'\0'）,free 表示剩餘空間，可以看到還剩 5 個字節。

SDS 遵循了 C 語言字符串以空字符結尾的慣例，保存空字符的 1 個字節空間不在 SDS 的 len 屬性裏面。這樣做有個好處是我們直接可以複用 C 提供的庫函數，比如打印字符串，直接用 C 提供的printf("%s", s->buf);

那又是爲什麼不直接用 C 語言提供的字符串呢？

在 C 語言中，表示一個 “angela” 的字符串如下圖所示，結束也是通過空字符表示：

C 語言的字符串和 SDS 的區別如下：

• 長度獲取效率：C 語言如果需要獲取字符串長度，需要從頭開始遍歷，時間複雜度 O(n)，SDS 提供 len 屬性，訪問時間複雜度 O(1), Redis 的 strlen 獲取字符串長度函數性能毫無壓力；

• 杜絕溢出：C 字符串不記錄自身長度的另一個問題是容易造成緩衝區溢出，比如要做字符串拼接，char *strcat(char *dest, const char *src), 講 src 字符串拼到 desc 字符串，如果 desc 忘記提前擴容，就會溢出，而恰好 desc 後面正好有數據，則會被覆蓋；

• 減少內存重分配：對於 Redis 這種內存數據庫，很多場景會頻繁更新 value 的值，那如果採用 C 字符串，value 長度有變化，就需要頻繁分配內存，SDS 做了內存的預分配和惰性釋放，能有效減少內存分配次數，內存的重分配代價還是很高昂的，對於 Redis 這種對性能要求非常高的緩存產品，這種性能損耗是不能接受的；

• 二進制安全：C 字符串必須符合某種編碼（比如 ASCII），除了空字符結尾，字符串中間是不能包含空字符的，否則會被誤以爲是字符串結尾。這就限定了 C 字符串不能用來存儲類型圖片、音頻、視頻、壓縮文件這種二進制書數據，但是 SDS 可以，SDS 設計的 API 都是二進制安全的。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/3qEXdoZ8SIujoSff2mwGAw