redis 系列3 簡單動態字元串 SDS

一.  SDS概述

　　Redis 沒有直接使用C語言傳統的字元串表示，而是自己構建了一種名為簡單動態字元串(simple dynamic string, SDS)的抽象類型，並將SDS用作Redis的預設字元串表示。Redis只會使用C字元串作為字面量。在Redis里，使用SDS來表示字元串值，是一個可以被修改的字元串，字元串“鍵值對”底層都是由SDS實現的。

-- 例1：客戶端執行如下命令：
127.0.0.1:6379> set msg "hello world"
OK
127.0.0.1:6379> get msg
"hello world"

　　上面例1中就在資料庫里創建一個新的鍵值對。 其中“鍵”是一個字元串對象，對象的底層實現是一個保存著字元串"msg" 的SDS。 "鍵值" 也是一個字元串對象，對象的底層實現是一個保存著字元串" hello world " 的SDS。

-- 例2: 客戶端執行如下命令：
127.0.0.1:6379> rpush  fruits "apple" "banana" "cherry"
(integer) 3
127.0.0.1:6379> lrange fruits 0 -1
1) "apple"
2) "banana"
3) "cherry"

　　上面例2中也在資料庫里創建一個新的鍵值對。其中“鍵”是一個字元串對象，對象的底層實現是一個保存著字元串" fruits " 的SDS。"鍵值"是一個列表對象，列表包含了三個字元串對象，分別由三個SDS實現。

　　SDS除了用來保存資料庫中的字元串值之外，還用作緩衝區(buffer): AOF模塊中的AOF緩衝區，以及客戶端狀態中的輸入緩衝區。

二. SDS 定義

　　每個SDS.h文件下的sdshdr結構表示一個SDS值, 下麵是Redis源碼，在github的地址是https://github.com/antirez/sds

struct  sdshdr{
    //記錄buf數組中已使用位元組的數量，也就是字元串的長度
     int len ;
    // 記錄buf數組中未使用位元組的數量
     int free;
    //位元組數組，用於保存字元串
     char buf[];
}

　　在C語言中使用長度為N+1的字元數組來表示長度為N的字元串，並且字元數組最後一個元素總是空字元'\0'。 假設SDS的值為 "Redis"，那麼free屬性值為0, len 屬性值為5, buf數組為R,e,d,i,s五個字元，最後一個位元組則保存空字元'\0' 。

三. SDS與C字元串的區別

　　C語言使用簡單的字元串表示方式，並不能滿足Redis對字元串在安全性，效率以及功能方面的要求，從幾個方面說明：

　　1. 常數複雜度獲取字元串長度

　　　　因為c字元串並不記錄自身的長度信息，所以為了獲取一個c字元串的長度，程式必須遍歷整個字元串。與C 字元串不同，因為SDS在len屬性中記錄了SDS本身的長度，對於SDS的值為"Redis"的位元組長度就是5。

　　2. 杜絕緩衝區溢出

　　　　在c中, 假設緊鄰的字元串s1 和 s2， s1保存為"redis", s2保存為"mongodb",  如果修改s1的值為 redis cluster, 但修改之前沒了空間，那麼s1的數據將溢出到s2所在空間中。

　　　　在SDS中，會先檢查給定的SDS空間是否足夠，會自動擴展修改所需的大小空間。然後在執行實際的修改操作。

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

　　　　 在c 中，字元串的底層實現總是一個N+1個字元長的數組，因為字元串的長度和底層數組的長度之間存在著這種關聯，所以每次增長或者縮短一個c字元串，程式都要對保存這個C字元串的數組進行一次記憶體重分配操作。

　　　　在SDS中通過未使用空間解除了字元串長度和底層數組長度之間的關聯，buf數組的長度不一定就是字元數量加1， 數組裡機可以包含未使用的位元組，這些由free屬性記錄。

　　　　3.1 空間預分配

　　　　　　當SDS的API對一個SDS進行操作，並且需要對SDS進行空間擴展的時候，程式不僅會為SDS 分配修改所必須要的空間，還會為SDS分配額外的未使用空間。額外分配的未使用空間數量由以下公式決定：

　　　　　　如果對SDS進行修改之後，SDS的長度(也即是len屬性的值) 將小於1MB，那麼程式分配和len屬性同樣大小的未使用空間。這時SDS len屬性的值將和fee屬性的值相同，例如：修改之後,SDS的len將變成13位元組， 那麼程式也會分配13位元組的未使用空間，SDS的buf數組的實際長度將變成13+13+1=27位元組。

　　　　　　如果對SDS進行修改之後，SDS的len大於等於1MB, 那麼程式會分配1MB的未使用空間，如果對SDS進行修改之後, SDS的len變成30MB,那麼程式會分配1MB的未使用空間，SDS的buf數組的實際長度為30MB + 1MB +1byte。

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

　　　　3.2 惰性空間釋放

　　　　　　惰性空間釋放用於優化SDS的字元串縮短操作。當SDS的API需要縮短SDS保存的字元串時，程式並不立即使用記憶體重分配來回收縮短多出來的位元組，而是使用free屬性將這些位元組的數據記錄起來，並等待將來使用(縮短後未使用的空間不會釋放，而是將來增長操作時，再使用這些未使用空間)。

　　4. 二進位安全

　　　　在c字元串的字元必須符合某種編碼(如ASCII), 並且除了字元串的末尾之處，字元串裡面不能包含空字元，否則最先被程式讀入的空字元將被誤以為是字元串的結尾，這使得c字元串只能保存文本數據，不能保存圖片，音頻，視頻，壓縮文件之類的二進位數據。

　　　　為了保證Redis 可以適用各種不同的使用場景，SDS的API 都是二進位安全的，程式不會對其中的數據做任何限制，過濾，數據寫入是什麼，讀取時就是什麼。

　　5. 相容部分C字元串函數

　　　　在SDS中會遵循C字元串以空字元結尾的慣例，總會為buf數組分配空間時多分配一個位元組來容納這個空字元，這是為了讓SDS的字元串可以重用一部分(string.h>庫定入的函數。

四 總結

　　4.1  C字元串與SDS之間的區別總結

　　4.2  SDS API(主要的一些API)