深入理解Redis之簡單動態字串

• SDS
• SDS與C字串的區別
  • SDS獲取字串長度復雜度為O(1),C字串為O(N)
  • SDS杜絕了快取區溢位
  • 減少修改字串時帶來的記憶體重分配次數
  • 二進制安全

Redis沒有直接使用C語言傳統的字串表示(以空字符結尾的字符陣列，以下簡稱C字串)，而是自己構建了一種名為簡單動態字串(simple dynamic string,SDS)的抽象型別，并將SDS用作Redis的默認字串表示，Reids自己構建的sds要比默認的c字串性能更好，也更安全，

SDS

那么sds的結構是什么樣的呢？與C字串有什么不同？

下面是sds的定義

struct sdshdr {
    //記錄buf陣列中已使用位元組的數量
    //等于sds所保存字串的長度
    int len;
    
    //記錄buf陣列中未使用位元組的數量
    int free;
    
    //位元組陣列，用于保存字串
    char buf[];
}

在64位系統下，屬性len和屬性free各占4個位元組，緊接著存放位元組陣列，

上面的buf[]是一個柔性陣列，柔性陣列成員(flexible array member)，也叫伸縮性陣列成員，只能被放在結構體的末尾，包含柔性陣列成員的結構體，通過malloc函式為柔性陣列動態分配記憶體，

關于柔性陣列，可以看這篇文章：C語言柔性陣列講解

下面展示一個SDS示例：

set name "Redis"

• free屬性的值為0，表示這個SDS沒有分配任何未使用空間，
• len屬性的值為5，表示這個SDS保存了一個物位元組長的字串，
• buf屬性是一個char型別的陣列，陣列的前五個位元組分別保存了'R'、'e'、'd'、'i'、's'五個字符，而最后一個位元組則保存了空字符'\0'，

SDS遵循C字串以空字符結尾的慣例，保存空字符的1位元組空間不計算在SDS的len屬性里面，并且為空字符分配額外的1位元組空間，以及添加空字符到字串末尾等操作，都是由SDS函式自動完成的，所以這個空字符對于SDS的使用者來說是完全透明的，遵循空字串結尾這一慣例的好處是，SDS可以直接重用一部分C字串函式庫里面的函式，

SDS與C字串的區別

C語言使用長度為N+1的字符陣列來表示長度為N的字串，并且字符陣列的最后一個元素總是空字符'\0'，但是C語言使用的這種簡單的字串表示方式，并不能滿足Redis對字串在安全性、效率以及功能方面的要求，下面來聊聊為什么SDS比C字串更適合用于Redis，

SDS獲取字串長度復雜度為O(1),C字串為O(N)

由于C字串并不記錄自身的長度資訊，所以為了獲取一個C字串的長度，程式必須遍歷整個字串，對遇到的每個字符進行計數，直到遇到代表字串結尾的空字符為止，這個操作的復雜度為O(N)，

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

通過使用SDS而不是C字串，Redis將獲取字串長度所需的復雜度從O(N)降低到了O(1)，這確保了獲取字串長度的作業不會成為Redis的性能瓶頸，所以，即使我們對一個非常長的字串反復執行STRLEN命令，也不會對系統性能造成任何影響，因為STRLEN命令的復雜度僅為O(1)，

SDS杜絕了快取區溢位

C字串不記錄自身長度除了會導致獲取字串長度復雜度高之外，還帶來的另一個問題就是容易造成快取區溢位(buffer overflow)，舉個例子，假設程式里有兩個在記憶體中緊鄰著的C字串s1和s2，其中s1保存了字串"Redis"，而s2則保存了字串"MongoDB"，如下圖所示，

如果一個程式員決定通過strcat(s1, " Cluster")將s1的內容修改為"Redis Cluster"，但粗心的他卻忘了在執行strcat之前為s1分配足夠的空間，那么在strcat函式執行之后，s1的資料將溢位到s2所在的空間中，導致s2保存的內容被意外地修改，如下圖所示，

這是使用C字串所會帶來的問題，與C字串不同，SDS的空間分配策略完全杜絕了發生快取區溢位的可能性：當SDS API需要對SDS進行修改時，API會先檢查SDS的空間是否滿足修改所需的要求，如果不滿足的話，API會自動將SDS的空間擴展至修改所需的大小，然后才執行實際的修改操作，所以使用SDS既不需要手動修改SDS的空間大小，也不會出現前面所說的快取區溢位問題，

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

因為C字串并不記錄自身的長度，所以對于一個包含了N個字符的C字串來說，這個C字串的底層實作總是一個N+1個字符長的陣列(額外的一個字符空間用于保存空字符)，因為C字串的長度和底層陣列的長度之間存在著這種關聯性，所以每次增長或者縮短一個C字串，程式都總要對保存這個C字串的陣列進行一次記憶體重分配操作：

• 如果程式執行的是增長字串的操作，比如拼接操作(append)，那么在執行這個操作之前，程式需要先通過記憶體重分配來擴展底層陣列的空間大小--如果忘了這一步就會產生快取區溢位，
• 如果程式執行的是縮短字串的操作，比如截斷操作(trim)，那么在執行這個操作之后，程式需要通過記憶體重分配來釋放字串不再使用的那部分空間--如果忘了這一步就會產生記憶體泄漏，

為了避免C字串的這種缺陷，SDS通過未使用空間解除了字串長度和底層陣列長度之間的關聯：在SDS中，buf陣列的長度就不一定是字符數量加一，陣列里面可以包含未使用的位元組，而這些位元組的數量就由SDS的free屬性記錄，

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

1.空間預分配

空間預分配用于優化SDS字串增長操作：當SDS的API對一個SDS進行修改，并且需要對SDS進行空間擴展的時候，程式不僅會為SDS分配修改所必須要的空間，還會為SDS分配額外的未使用空間，其中額外分配的未使用空間數量由以下公司決定：

• 如果對SDS進行修改之后，SDS的長度(也即len屬性的值)小于1MB，那么程式分配和len屬性同樣大小的未使用空間，這時SDS len屬性的值將和free屬性的值相同，舉個例子，如果進行修改之后，SDS的len將變成13位元組，那么程式也會分配13位元組的未使用空間，SDS的buf陣列的實際長度將變成13+13+1位元組(額外的一位元組用于保存空字符)，
• 如果對SDS進行修改之后，SDS的長度將大于等于1MB，那么程式會分配1MB的未使用空間，舉個例子，如果進行修改之后，SDS的len變成了30MB，那么程式會分配1MB的未使用空間，SDS的buf陣列的實際長度為30MB+1MB+1byte，

通過空間預分配策略，Redis可以減少連續執行字串增長操作所需的記憶體重分配次數，

2.惰性空間釋放

惰性空間釋放用于優化SDS的字串縮短操作：當SDS的API需要縮短SDS保存的字串是，程式并不立即使用記憶體重分配來回收縮短后多出來的位元組，而是使用free屬性來將這些位元組的數量記錄起來，并等待將來使用，

通過惰性空間釋放策略，SDS避免了縮短字串時所需的記憶體重分配操作，并未將來可能有的增長操作提供了優化，與此同時，ADS也提供了相應的API，讓我們可以在有需要時，真正地釋放SDS的未使用空間，所以不用擔心惰性空間釋放策略會造成記憶體浪費，

二進制安全

什么是二進制安全？

通俗地將，C語言中，用'\0'表示字串的結束，如果字串本身就有'\0'字符，字串就會被截斷，既非二進制安全；若通過某種機制，保證讀寫字串時不損害其內容，則是二進制安全，

C字串中的字符必須符合某種編碼(比如ASCII),并且除了字串的末尾之外，字串里面不能包含空字符，否則最先被程式讀入的空字符將被誤認為是字串結尾，這些限制使得C字串只能保存文本資料，而不能保存像圖片、音頻、視頻、壓縮檔案這樣的二進制資料，

為了確保Redis可以適用于各種不同的使用場景(保存文本、影像、音視頻等)，SDS的API都是二進制安全的(binary-safe)，所有SDS API都會以處理二進制的方式來處理SDS存放在buf陣列里的資料，程式不會對其中的資料做任何限制、過濾、或者假設，資料在寫入時是神峨眉樣的，它被讀取時就是什么樣的，

這也是將SDS的buf屬性成為位元組陣列的原因----Redis不是用這個陣列來保存字符，而是用它來保存一系列二進制資料，

整理自：

《redis設計與實作(第二版)》

《redis5設計與原始碼分析》

標籤：NoSQL

上一篇：Redis原始碼系列(一)

下一篇：Redis基礎之事務