Redis設計與實作——簡單動态字元串（SDS）

Redis字元串簡介

在Redis中，字元串的存儲不是使用C語言傳統的字元串表示，而是使用一種名為簡單動态字元串（simple dynamic string）的資料結構表示。

例如: 這一條指令

redis>SET msg "hello"
OK
           

鍵值對的鍵是一個字元串對象，底層實作是一個儲存着“msg”的SDS

鍵值對的值是一個字元串對象，底層實作是一個儲存着“hello”的SDS

SDS的資料結構

SDS與C字元串差別

• 字元串的結尾依然以空字元結尾，遵循了C字元串定義的慣例，為的是可以複用一部分C中函數庫的函數，即相容部分C字元串函數，而不需要重新寫一套。
• len的定義可以以O(1)的時間複雜度擷取字元串的長度,在傳統C的字元串中，需要進行全部周遊才能擷取長度。在大量使用STRLEN時SDS将大大提升效率。
• free的定義可以杜絕緩沖區溢出，例如：

  

  原來記憶體中緊貼的兩個字元串，使用了這個指令。

這樣就會導緻s1的内容溢出到了s2中。而在SDS中則不會發生，因為每次進行類似這種增加字元的操作，首先會判斷free的長度是否大于增加的字元，如果小于，則會重新開辟新的空間再進行增加。

那開辟新的空間的長度與增加後的字元串長度相等的嗎？

不是！為了減少修改字元串時帶來的記憶體重配置設定，在SDS修改之後的長度（len長度）小于1MB時，程式會多配置設定與len長度相同的空間，即free的值與len值相等。反之，則多配置設定1MB的長度。例如修改之後len的值為13位元組，那麼程式會再配置設定13位元組的未使用空間，總長度buf數組則為13+13+1=27位元組（額外的一位元組用來儲存空字元）。若修改之後len的值為30MB，則buf數組為30MB+1MB+1Byte

• 為了減少記憶體重配置設定的次數，SDS采用的是惰性空間釋放，當字元串縮短時，程式不是立即回收縮短後多出來的位元組，而是使用free變量來記錄多出來的位元組。如果擔心記憶體浪費，SDS也提供了API可以在真正有需要時釋放SDS的未使用空間。

二進制安全

Redis作為資料庫存儲，需要滿足各種各樣的存儲形式，若使用傳統C字元串，遇到空字元便會結束，而SDS使用len的值來判斷字元串是否結束，是以程式在寫入資料時怎麼樣，取出也是怎麼樣。

舉個例子：

假如這種存儲形式以空字元來劃分字元，如用C字元串，讀了Redis後面的字元就讀不到了。

總結