Redis簡單動態(tài)字符串SDS的實現(xiàn)示例

更新時間：2023年08月17日 10:40:41 作者：秋天code

Redis沒有直接復用C語言的字符串,而是新建了SDS,本文主要介紹了Redis簡單動態(tài)字符串SDS的實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解一下

定義

眾所周知，Redis是由C語言寫的。對于字符串類型的數(shù)據(jù)存儲，Redis并沒有直接使用C語言中的字符串。而是自己構(gòu)建了一個結(jié)構(gòu)體，叫做“簡單動態(tài)字符串”，簡稱SDS，比C語言中的字符串更加靈活。

SDS的結(jié)構(gòu)體是這樣的：

struct{
	int len; // 數(shù)組中已使用的字節(jié)的數(shù)量，即真實的內(nèi)容長度 
	int free; // 數(shù)組中未使用的字節(jié)的數(shù)量，即還可以繼續(xù)存儲的內(nèi)容的長度 
	char buff[]; // 字節(jié)數(shù)組，用來保存字符串 
};

在C語言中，總是使用長度是N+1的字符數(shù)組來保存長度為N的字符串，并且字符數(shù)組的最后一個是’\0’結(jié)束符，在SDS中，一次申請的字符串的長度比真實的長，所以才會有free這個屬性

SDS與C語言字符串相比，優(yōu)點是：

O(1)復雜度獲取字符串長度
防止了內(nèi)存溢出
減少內(nèi)存分配的次數(shù)
二進制安全

獲取字符串長度

對于C字符串來說，獲取一個字符串的真實長度，需要遍歷字符串，這就是O(N)的時間復雜度。而在SDS中，用一個len屬性保存字符串的真實長度，每次對字符串的修改，都會維護這個len屬性因此對于SDS來說，獲取字符串的真實長度的時間復雜度是O(1)，這確保了獲取字符串長度的操作不會成為Redis字符串的性能瓶頸

內(nèi)存溢出問題

在C字符串中，如果要對字符串進行修改操作，如果忘記了給字符串重新分配足夠的空間，就會導致內(nèi)存溢出問題。在C語言中，并沒有內(nèi)存溢出相關(guān)的檢查機制，因此可能會導致不可預測的問題產(chǎn)生。

通過SDS的API來操作字符串時，會先檢查SDS的空間是否滿足修改的要求，如果不滿足的話，會自動將SDS的空間擴展至要求的大小，然后執(zhí)行字符串操作，所以使用SDS來操作字符串，不用擔心內(nèi)存溢出問題。

減少內(nèi)存分配的次數(shù)

對于C語言字符串，因為總是有一個長度為N+1的字符數(shù)組來保存一個長度為N的字符串。所以，如果對C字符串進行操作：

如果進行字符串的長度增長的操作，比如追加字符append，那么在執(zhí)行這個操作前，需要先為字符串分配新的內(nèi)存空間，然后才能執(zhí)行操作。
如果忘記了重新分配內(nèi)存，會導致內(nèi)存溢出問題。如果進行字符串長度的減少操作，比如刪除某個字符，那么在執(zhí)行這個操作之后，需要釋放掉不再使用的內(nèi)存空間。如果忘記了釋放內(nèi)存，會導致內(nèi)存泄漏問題。

而對于SDS來說，不存在這些問題，通過兩個機制來解決以上問題：

空間預分配
惰性空間釋放

1. 空間預分配

空間預分配機制，用來優(yōu)化SDS字符串的增長操作。我們認為初始化賦值和拼接操作都是對于SDS的擴容操作。當SDS來擴容一個字符串時，系統(tǒng)不僅會為SDS分配所需的內(nèi)存空間大小，還會分配額外的未使用空間，即系統(tǒng)分配給SDS的空間大小比真實的字符串長度要大。至于，額外的空間有多大，有以下規(guī)則：

當擴容后的SDS的長度小于1MB，那么程序分配的額外空間就是len的大小，即與真實的字符串的空間大小相同。例如，擴容后，SDS的len的長度是20，那么額外的空間也是20，總共的SDS的空間是40字節(jié)。
如果擴容后的SDS的長度大于等于1MB，那么程序會分配1MB的額外空間。

通過空間預分配策略，可以減少字符串增長操作的內(nèi)存分配次數(shù)。當進行字符串增長操作時，會先檢查free的空間大小是否夠增加的長度，如果夠，那么直接在真實的數(shù)組上操作，無需再進行內(nèi)存分配操作，并維護free和len的值。如果不夠，那么就會進行擴容操作，擴容機制上面說過了。

2. 惰性空間釋放

惰性空間釋放用來優(yōu)化字符串的縮短操作。當SDS縮短一個字符串時，還是直接在原始的數(shù)組上操作，并維護len和free的值?？s短完成后，程序并不會立即回收釋放后的內(nèi)存，而是使用free屬性記錄下來，方便下次的字符串長度增加時使用。

二進制安全

C字符串中的字符必須符號某種編碼，例如，當編碼格式是ASCII時，除了末尾的空字符’\0’外，字符串內(nèi)容中不可以出現(xiàn)空字符，否則程序在讀取字符串時，會誤以為這是字符串的結(jié)尾。這樣的限制使得，C字符串只能保存文本數(shù)據(jù)，而不能保存圖片、音頻等二進制數(shù)據(jù)。而SDS會以二進制的方式來處理存放到buff數(shù)組中的數(shù)據(jù)，程序不會對其中的數(shù)據(jù)進行限制、過濾等額外操作這就是我們稱SDS是字節(jié)數(shù)組的原因——Redis不是用buff數(shù)組來保存字符，而是保存一系列的二進制數(shù)據(jù)

SDS不是使用空字符’\0’來判斷字符串的結(jié)尾，而是使用len屬性來判斷字符串是否結(jié)尾如"Redis\0String"，C字符串的函數(shù)會把’\0’當做結(jié)束符來處理，而忽略到后面的"String"。而SDS的buf字節(jié)數(shù)組不是在保存字符，而是一系列二進制數(shù)組，SDS API都會以二進制的方式來處理buf數(shù)組里的數(shù)據(jù)，使用len屬性的值而不是空字符來判斷字符串是否結(jié)束。