Redis數(shù)據(jù)庫里面的每個鍵值對（key-value pair）都是由對象（object）組成的：

• 其中，數(shù)據(jù)庫鍵總是一個字符串對象（string object）;
• 而數(shù)據(jù)庫鍵的值可以是字符串對象、 列表對象（list object）、 哈希對象（hash object）、 集合對象（set object）、 有序集合對象（sorted set object）這五種對象中的其中一種。

Redis沒有使用C語言傳統(tǒng)的字符串表示

（在 C 語言中，字符串實際上是使用 null 字符 '\0' 終止的一維字符數(shù)組。因此，一個以 null 結尾的字符串，包含了組成字符串的字符。

下面的聲明和初始化創(chuàng)建了一個 "Hello" 字符串。由于在數(shù)組的末尾存儲了空字符，所以字符數(shù)組的大小比單詞 "Hello" 的字符數(shù)多一個。
char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};）

而是自己構建了一種名為簡單動態(tài)字符串（simple dynamic string,SDS）的抽象類型，并將SDS用作Redis的默認字符串表示。

1. SDS的定義

struct sdshdr {
      // 記錄 buf 數(shù)組中已使用字節(jié)的數(shù)量
      // 等于 SDS 所保存字符串的長度
      int len;
      // 記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量
      int free;
      // 字節(jié)數(shù)組，用于保存字符串
      char buf[];
};

圖 2-1 展示了一個 SDS 示例：

free 屬性的值為 0 ， 表示這個 SDS 沒有分配任何未使用空間。
len 屬性的值為 5 ， 表示這個 SDS 保存了一個五字節(jié)長的字符串。
buf 屬性是一個 char 類型的數(shù)組， 數(shù)組的前五個字節(jié)分別保存了 'R' 、 'e' 、 'd' 、 'i' 、 's' 五個字符， 而最后一個字節(jié)則保存了空字符 '\0' 。

2-1.png

SDS 遵循 C 字符串以空字符結尾的慣例， 保存空字符的 1 字節(jié)空間不計算在 SDS 的 len 屬性里面， 并且為空字符分配額外的 1 字節(jié)空間， 以及添加空字符到字符串末尾等操作都是由 SDS 函數(shù)自動完成的， 所以這個空字符對于 SDS 的使用者來說是完全透明的。

遵循空字符結尾這一慣例的好處是， SDS 可以直接重用一部分 C 字符串函數(shù)庫里面的函數(shù)。

2. Demo

redis> SET msg "hello world"
OK

那么Redis將在數(shù)據(jù)庫中創(chuàng)建一個新的鍵值對，其中：

• 鍵值對的K是一個字符串對象，對象的底層實現(xiàn)是一個保存著字符串“msg”的SDS。
• 鍵值對的V也是一個字符串對象， 對象的底層實現(xiàn)是一個保存著字符串 "hello world" 的 SDS。

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

(TODO)
除了用來保存數(shù)據(jù)庫中的字符串值之外， SDS 還被用作緩沖區(qū)（buffer）： AOF 模塊中的 AOF 緩沖區(qū)， 以及客戶端狀態(tài)中的輸入緩沖區(qū)， 都是由 SDS 實現(xiàn)的， 在之后介紹 AOF 持久化和客戶端狀態(tài)的時候， 我們會看到 SDS 在這兩個模塊中的應用。

3. SDS的優(yōu)點

• 常數(shù)復雜度獲取字符串長度

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

舉個例子， 對于圖 2-5 所示的 SDS 來說， 程序只要訪問 SDS 的 len 屬性， 就可以立即知道 SDS 的長度為 5 字節(jié)：

2-5.png

設置和更新 SDS 長度的工作是由 SDS 的 API 在執(zhí)行時自動完成的， 使用 SDS 無須進行任何手動修改長度的工作。

通過使用 SDS 而不是 C 字符串， Redis 將獲取字符串長度所需的復雜度從 O(N) 降低到了 O(1) ， 這確保了獲取字符串長度的工作不會成為 Redis 的性能瓶頸。

比如說， 因為字符串鍵在底層使用 SDS 來實現(xiàn)， 所以即使我們對一個非常長的字符串鍵反復執(zhí)行 STRLEN 命令， 也不會對系統(tǒng)性能造成任何影響， 因為 STRLEN 命令的復雜度僅為 O(1) 。

• 杜絕緩沖區(qū)溢出

與 C 字符串不同， SDS 的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性： 當 SDS API 需要對 SDS 進行修改時， API 會先檢查 SDS 的空間是否滿足修改所需的要求， 如果不滿足的話， API 會自動將 SDS 的空間擴展至執(zhí)行修改所需的大小， 然后才執(zhí)行實際的修改操作， 所以使用 SDS 既不需要手動修改 SDS 的空間大小， 也不會出現(xiàn)前面所說的緩沖區(qū)溢出問題。

舉個例子， SDS 的 API 里面也有一個用于執(zhí)行拼接操作的 sdscat 函數(shù)， 它可以將一個 C 字符串拼接到給定 SDS 所保存的字符串的后面， 但是在執(zhí)行拼接操作之前， sdscat 會先檢查給定 SDS 的空間是否足夠， 如果不夠的話， sdscat 就會先擴展 SDS 的空間， 然后才執(zhí)行拼接操作。

比如說， 如果我們執(zhí)行：

sdscat(s, " Cluster");

其中 SDS 值 s 如圖 2-9 所示， 那么 sdscat 將在執(zhí)行拼接操作之前檢查 s 的長度是否足夠， 在發(fā)現(xiàn) s 目前的空間不足以拼接 " Cluster" 之后， sdscat 就會先擴展 s 的空間， 然后才執(zhí)行拼接 " Cluster" 的操作， 拼接操作完成之后的 SDS 如圖 2-10 所示。

2-9.png

2-10.png

注意圖 2-10 所示的 SDS ： sdscat 不僅對這個 SDS 進行了拼接操作， 它還為 SDS 分配了 13 字節(jié)的未使用空間， 并且拼接之后的字符串也正好是 13 字節(jié)長， 這種現(xiàn)象既不是 bug 也不是巧合， 它和 SDS 的空間分配策略有關， 接下來的小節(jié)將對這一策略進行說明。

• 減少修改字符串時帶來的內存重分配次數(shù)

正如前兩個小節(jié)所說， 因為 C 字符串并不記錄自身的長度， 所以對于一個包含了 N 個字符的 C 字符串來說， 這個 C 字符串的底層實現(xiàn)總是一個 N+1 個字符長的數(shù)組（額外的一個字符空間用于保存空字符）。

因為 C 字符串的長度和底層數(shù)組的長度之間存在著這種關聯(lián)性， 所以每次增長或者縮短一個 C 字符串， 程序都總要對保存這個 C 字符串的數(shù)組進行一次內存重分配操作：

如果程序執(zhí)行的是增長字符串的操作， 比如拼接操作（append）， 那么在執(zhí)行這個操作之前， 程序需要先通過內存重分配來擴展底層數(shù)組的空間大小 —— 如果忘了這一步就會產生緩沖區(qū)溢出。
如果程序執(zhí)行的是縮短字符串的操作， 比如截斷操作（trim）， 那么在執(zhí)行這個操作之后， 程序需要通過內存重分配來釋放字符串不再使用的那部分空間 —— 如果忘了這一步就會產生內存泄漏。
舉個例子， 如果我們持有一個值為 "Redis" 的 C 字符串 s ， 那么為了將 s 的值改為 "Redis Cluster" ， 在執(zhí)行：

strcat(s, " Cluster");

之前， 我們需要先使用內存重分配操作， 擴展 s 的空間。

之后， 如果我們又打算將 s 的值從 "Redis Cluster" 改為 "Redis Cluster Tutorial" ， 那么在執(zhí)行：

strcat(s, " Tutorial");

之前， 我們需要再次使用內存重分配擴展 s 的空間， 諸如此類。

因為內存重分配涉及復雜的算法， 并且可能需要執(zhí)行系統(tǒng)調用， 所以它通常是一個比較耗時的操作：

• 在一般程序中， 如果修改字符串長度的情況不太常出現(xiàn)， 那么每次修改都執(zhí)行一次內存重分配是可以接受的。
• 但是 Redis 作為數(shù)據(jù)庫， 經常被用于速度要求嚴苛、數(shù)據(jù)被頻繁修改的場合， 如果每次修改字符串的長度都需要執(zhí)行一次內存重分配的話， 那么光是執(zhí)行內存重分配的時間就會占去修改字符串所用時間的一大部分， 如果這種修改頻繁地發(fā)生的話， 可能還會對性能造成影響。

為了避免 C 字符串的這種缺陷， SDS 通過未使用空間解除了字符串長度和底層數(shù)組長度之間的關聯(lián)： 在 SDS 中， buf 數(shù)組的長度不一定就是字符數(shù)量加一， 數(shù)組里面可以包含未使用的字節(jié)， 而這些字節(jié)的數(shù)量就由 SDS 的 free 屬性記錄。

通過未使用空間， SDS 實現(xiàn)了空間預分配和惰性空間釋放兩種優(yōu)化策略。

空間預分配

空間預分配用于優(yōu)化 SDS 的字符串增長操作： 當 SDS 的 API 對一個 SDS 進行修改， 并且需要對 SDS 進行空間擴展的時候， 程序不僅會為 SDS 分配修改所必須要的空間， 還會為 SDS 分配額外的未使用空間。

其中， 額外分配的未使用空間數(shù)量由以下公式決定：

• 如果對 SDS 進行修改之后， SDS 的長度（也即是 len 屬性的值）將小于 1 MB ， 那么程序分配和 len 屬性同樣大小的未使用空間， 這時 SDS len 屬性的值將和 free 屬性的值相同。 舉個例子， 如果進行修改之后， SDS 的 len 將變成 13 字節(jié)， 那么程序也會分配 13 字節(jié)的未使用空間， SDS 的 buf 數(shù)組的實際長度將變成 13 + 13 + 1 = 27 字節(jié)（額外的一字節(jié)用于保存空字符）。
• 如果對 SDS 進行修改之后， SDS 的長度將大于等于 1 MB ， 那么程序會分配 1 MB 的未使用空間。 舉個例子， 如果進行修改之后， SDS 的 len 將變成 30 MB ， 那么程序會分配 1 MB 的未使用空間， SDS 的 buf 數(shù)組的實際長度將為 30 MB + 1 MB + 1 byte 。

通過空間預分配策略， Redis 可以減少連續(xù)執(zhí)行字符串增長操作所需的內存重分配次數(shù)。

• 二進制安全
  C 字符串中的字符必須符合某種編碼（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否則最先被程序讀入的空字符將被誤認為是字符串結尾 —— 這些限制使得 C 字符串只能保存文本數(shù)據(jù)， 而不能保存像圖片、音頻、視頻、壓縮文件這樣的二進制數(shù)據(jù)。

舉個例子， 如果有一種使用空字符來分割多個單詞的特殊數(shù)據(jù)格式， 如圖 2-17 所示， 那么這種格式就不能使用 C 字符串來保存， 因為 C 字符串所用的函數(shù)只會識別出其中的 "Redis" ， 而忽略之后的 "Cluster" 。

2-17.png

雖然數(shù)據(jù)庫一般用于保存文本數(shù)據(jù)， 但使用數(shù)據(jù)庫來保存二進制數(shù)據(jù)的場景也不少見， 因此， 為了確保 Redis 可以適用于各種不同的使用場景， SDS 的 API 都是二進制安全的（binary-safe）： 所有 SDS API 都會以處理二進制的方式來處理 SDS 存放在 buf 數(shù)組里的數(shù)據(jù)， 程序不會對其中的數(shù)據(jù)做任何限制、過濾、或者假設 —— 數(shù)據(jù)在寫入時是什么樣的， 它被讀取時就是什么樣。

這也是我們將 SDS 的 buf 屬性稱為字節(jié)數(shù)組的原因 —— Redis 不是用這個數(shù)組來保存字符， 而是用它來保存一系列二進制數(shù)據(jù)。

比如說， 使用 SDS 來保存之前提到的特殊數(shù)據(jù)格式就沒有任何問題， 因為 SDS 使用 len 屬性的值而不是空字符來判斷字符串是否結束， 如圖 2-18 所示。

2-18.png

通過使用二進制安全的 SDS ， 而不是 C 字符串， 使得 Redis 不僅可以保存文本數(shù)據(jù)， 還可以保存任意格式的二進制數(shù)據(jù)。

• 兼容部分 C 字符串函數(shù)

字符串對象的編碼可以是 int 、 raw 或者 embstr 。
如果一個字符串對象保存的是整數(shù)值， 并且這個整數(shù)值可以用 long 類型來表示， 那么字符串對象會將整數(shù)值保存在字符串對象結構的 ptr 屬性里面（將 void* 轉換成 long ）， 并將字符串對象的編碼設置為 int 。

如果字符串對象保存的是一個字符串值， 并且這個字符串值的長度大于 39 字節(jié)， 那么字符串對象將使用一個簡單動態(tài)字符串（SDS）來保存這個字符串值， 并將對象的編碼設置為 raw 。

如果字符串對象保存的是一個字符串值， 并且這個字符串值的長度小于等于 39 字節(jié)， 那么字符串對象將使用 embstr 編碼的方式來保存這個字符串值。

embstr 編碼是專門用于保存短字符串的一種優(yōu)化編碼方式， 這種編碼和 raw 編碼一樣， 都使用 redisObject 結構和 sdshdr 結構來表示字符串對象， 但 raw 編碼會調用兩次內存分配函數(shù)來分別創(chuàng)建 redisObject 結構和 sdshdr 結構， 而 embstr 編碼則通過調用一次內存分配函數(shù)來分配一塊連續(xù)的空間， 空間中依次包含 redisObject 和 sdshdr 兩個結構， 如圖 8-3 所示。

8-3.png

embstr 編碼的字符串對象在執(zhí)行命令時， 產生的效果和 raw 編碼的字符串對象執(zhí)行命令時產生的效果是相同的， 但使用 embstr 編碼的字符串對象來保存短字符串值有以下好處：

• embstr 編碼將創(chuàng)建字符串對象所需的內存分配次數(shù)從 raw 編碼的兩次降低為一次。
• 釋放 embstr 編碼的字符串對象只需要調用一次內存釋放函數(shù)， 而釋放 raw 編碼的字符串對象需要調用兩次內存釋放函數(shù)。
• 因為 embstr 編碼的字符串對象的所有數(shù)據(jù)都保存在一塊連續(xù)的內存里面， 所以這種編碼的字符串對象比起 raw 編碼的字符串對象能夠更好地利用緩存帶來的優(yōu)勢。

表 8-6 總結并列出了字符串對象保存各種不同類型的值所使用的編碼方式。

表 8-6 字符串對象保存各類型值的編碼方式

編碼的轉換

int 編碼的字符串對象和 embstr 編碼的字符串對象在條件滿足的情況下， 會被轉換為 raw 編碼的字符串對象。

對于 int 編碼的字符串對象來說， 如果我們向對象執(zhí)行了一些命令， 使得這個對象保存的不再是整數(shù)值， 而是一個字符串值， 那么字符串對象的編碼將從 int 變?yōu)?raw 。

在下面的示例中， 我們通過 APPEND 命令， 向一個保存整數(shù)值的字符串對象追加了一個字符串值， 因為追加操作只能對字符串值執(zhí)行， 所以程序會先將之前保存的整數(shù)值 10086 轉換為字符串值 "10086" ， 然后再執(zhí)行追加操作， 操作的執(zhí)行結果就是一個 raw 編碼的、保存了字符串值的字符串對象：

redis> SET number 10086
OK

redis> OBJECT ENCODING number
"int"

redis> APPEND number " is a good number!"
(integer) 23

redis> GET number
"10086 is a good number!"

redis> OBJECT ENCODING number
"raw"

另外， 因為 Redis 沒有為 embstr 編碼的字符串對象編寫任何相應的修改程序 （只有 int 編碼的字符串對象和 raw 編碼的字符串對象有這些程序）， 所以 embstr 編碼的字符串對象實際上是只讀的： 當我們對 embstr 編碼的字符串對象執(zhí)行任何修改命令時， 程序會先將對象的編碼從 embstr 轉換成 raw ， 然后再執(zhí)行修改命令； 因為這個原因， embstr 編碼的字符串對象在執(zhí)行修改命令之后， 總會變成一個 raw 編碼的字符串對象。

以下代碼展示了一個 embstr 編碼的字符串對象在執(zhí)行 APPEND 命令之后， 對象的編碼從 embstr 變?yōu)?raw 的例子：

redis> SET msg "hello world"
OK

redis> OBJECT ENCODING msg
"embstr"

redis> APPEND msg " again!"
(integer) 18

redis> OBJECT ENCODING msg
"raw"