redis 系列3 資料結構之簡單動态字元串 SDS

原文: 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之間的差別總結

C字元串	SDS
擷取字元串長度的複雜度為0(N)	擷取字元串長度的複雜度為0(1)
API是不安全的，可能會造成緩沖區溢出	API是安全的，不會造成緩沖區溢出
修改字元串長度N次必然需要執行N次記憶體重配置設定	修改字元串長度N次最多需要執行N次記憶體重配置設定
隻能儲存文本資料	可以儲存文本或者二進制資料
可以使用所有<string.h>庫中函數	可以使用一部分<string.h>庫中函數

　　4.2  SDS API(主要的一些API)      

函數	作用
sdsnew	建立一個SDS字元串
sdsempty	建立一個不包含内容的空SDS 字元串
sdsfree	釋放給定的SDS字元串未使用空間
sdslen	傳回SDS字元串已使用空間位元組數
sdsavail	傳回SDS字元串未使用空間位元組數
sdsdup	建立一個給定SDS的副本
sdsclear	清空SDS字元串内容
sdscat	将給定c字元拼接到SDS字元串的末尾
sdscatsds	将給定的SDS字元串拼接到另一個SDS字元串的末尾
sdscpy	将給定的c字元拼複制到SDS裡機，覆寫SDS原有字元串
sdsgrowzero	用空字元将SDS擴充至指定長度
sdsrange	保留SDS指定區間内的資料，不在區間内的資料會被覆寫或清除
sdstrim	接受一個SDS和一個C字元串作為參數，從SDS中移除所有在C字元串中出現過的字元
sdscmp	對比兩個SDS字元串是否相同