Redis的簡(jiǎn)單動(dòng)態(tài)字符串

序

Redis沒有直接使用C語言傳統(tǒng)的字符串表示(以空字符結(jié)尾的字符數(shù)組，以下簡(jiǎn)稱C字符串)，而是自己構(gòu)建了一種名為簡(jiǎn)單動(dòng)態(tài)字符串(simple dynamic string,SDS)的抽象類型，并將SDS用作Redis的默認(rèn)字符串表示。Reids自己構(gòu)建的sds要比默認(rèn)的c字符串性能更好，也更安全。

SDS

那么sds的結(jié)構(gòu)是什么樣的呢？與C字符串有什么不同？

下面是sds的定義:

struct?sdshdr?{
//記錄buf數(shù)組中已使用字節(jié)的數(shù)量
//等于sds所保存字符串的長度
int?len;

//記錄buf數(shù)組中未使用字節(jié)的數(shù)量
int?free;

//字節(jié)數(shù)組，用于保存字符串
char?buf[];
}

在64位系統(tǒng)下，屬性len和屬性free各占4個(gè)字節(jié)，緊接著存放字節(jié)數(shù)組。

?

上面的buf[]是一個(gè)柔性數(shù)組。柔性數(shù)組成員(flexible array member)，也叫伸縮性數(shù)組成員，只能被放在結(jié)構(gòu)體的末尾。包含柔性數(shù)組成員的結(jié)構(gòu)體，通過malloc函數(shù)為柔性數(shù)組動(dòng)態(tài)分配內(nèi)存。

?

下面展示一個(gè)SDS示例：

set name "Redis"

]

• free屬性的值為0，表示這個(gè)SDS沒有分配任何未使用空間。
• len屬性的值為5，表示這個(gè)SDS保存了一個(gè)物字節(jié)長的字符串。
• buf屬性是一個(gè)char類型的數(shù)組，數(shù)組的前五個(gè)字節(jié)分別保存了'R'、'e'、'd'、'i'、's'五個(gè)字符，而最后一個(gè)字節(jié)則保存了空字符'\0'。

SDS遵循C字符串以空字符結(jié)尾的慣例，保存空字符的1字節(jié)空間不計(jì)算在SDS的len屬性里面，并且為空字符分配額外的1字節(jié)空間，以及添加空字符到字符串末尾等操作，都是由SDS函數(shù)自動(dòng)完成的，所以這個(gè)空字符對(duì)于SDS的使用者來說是完全透明的。遵循空字符串結(jié)尾這一慣例的好處是，SDS可以直接重用一部分C字符串函數(shù)庫里面的函數(shù)。

2.0SDS與C字符串的區(qū)別

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

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

由于C字符串并不記錄自身的長度信息，所以為了獲取一個(gè)C字符串的長度，程序必須遍歷整個(gè)字符串，對(duì)遇到的每個(gè)字符進(jìn)行計(jì)數(shù)，直到遇到代表字符串結(jié)尾的空字符為止，這個(gè)操作的復(fù)雜度為O(N)。

和C字符串不，因?yàn)镾DS在len屬性中記錄了SDS本身的長度，所以獲取一個(gè)SDS長度的復(fù)雜度為O(1)。公眾號(hào)搜索,[Java學(xué)習(xí)之道],回復(fù)'福利',3T資料等你來拿。

通過使用SDS而不是C字符串，Redis將獲取字符串長度所需的復(fù)雜度從O(N)降低到了O(1)，這確保了獲取字符串長度的工作不會(huì)成為Redis的性能瓶頸。所以，即使我們對(duì)一個(gè)非常長的字符串反復(fù)執(zhí)行STRLEN命令，也不會(huì)對(duì)系統(tǒng)性能造成任何影響，因?yàn)镾TRLEN命令的復(fù)雜度僅為O(1)。

2.2SDS杜絕了緩存區(qū)溢出

C字符串不記錄自身長度除了會(huì)導(dǎo)致獲取字符串長度復(fù)雜度高之外，還帶來的另一個(gè)問題就是容易造成緩存區(qū)溢出(buffer overflow)。舉個(gè)例子，假設(shè)程序里有兩個(gè)在內(nèi)存中緊鄰著的C字符串s1和s2，其中s1保存了字符串"Redis"，而s2則保存了字符串"MongoDB"，如下圖所示。

在內(nèi)存中緊鄰的兩個(gè)C字符串如果一個(gè)程序員決定通過strcat(s1, " Cluster")將s1的內(nèi)容修改為"Redis Cluster"，但粗心的他卻忘了在執(zhí)行strcat之前為s1分配足夠的空間，那么在strcat函數(shù)執(zhí)行之后，s1的數(shù)據(jù)將溢出到s2所在的空間中，導(dǎo)致s2保存的內(nèi)容被意外地修改，如下圖所示。

s1的內(nèi)容溢出到了s2所在的位置這是使用C字符串所會(huì)帶來的問題。與C字符串不同，SDS的空間分配策略完全杜絕了發(fā)生緩存區(qū)溢出的可能性：當(dāng)SDS API需要對(duì)SDS進(jìn)行修改時(shí)，API會(huì)先檢查SDS的空間是否滿足修改所需的要求，如果不滿足的話，API會(huì)自動(dòng)將SDS的空間擴(kuò)展至修改所需的大小，然后才執(zhí)行實(shí)際的修改操作，所以使用SDS既不需要手動(dòng)修改SDS的空間大小，也不會(huì)出現(xiàn)前面所說的緩存區(qū)溢出問題。

2.3減少修改字符串時(shí)帶來的內(nèi)存重分配次數(shù)

因?yàn)镃字符串并不記錄自身的長度，所以對(duì)于一個(gè)包含了N個(gè)字符的C字符串來說，這個(gè)C字符串的底層實(shí)現(xiàn)總是一個(gè)N+1個(gè)字符長的數(shù)組(額外的一個(gè)字符空間用于保存空字符)。因?yàn)镃字符串的長度和底層數(shù)組的長度之間存在著這種關(guān)聯(lián)性，所以每次增長或者縮短一個(gè)C字符串，程序都總要對(duì)保存這個(gè)C字符串的數(shù)組進(jìn)行一次內(nèi)存重分配操作：

• 如果程序執(zhí)行的是增長字符串的操作，比如拼接操作(append)，那么在執(zhí)行這個(gè)操作之前，程序需要先通過內(nèi)存重分配來擴(kuò)展底層數(shù)組的空間大小--如果忘了這一步就會(huì)產(chǎn)生緩存區(qū)溢出。
• 如果程序執(zhí)行的是縮短字符串的操作，比如截?cái)嗖僮?trim)，那么在執(zhí)行這個(gè)操作之后，程序需要通過內(nèi)存重分配來釋放字符串不再使用的那部分空間--如果忘了這一步就會(huì)產(chǎn)生內(nèi)存泄漏。

為了避免C字符串的這種缺陷，SDS通過未使用空間解除了字符串長度和底層數(shù)組長度之間的關(guān)聯(lián)：在SDS中，buf數(shù)組的長度就不一定是字符數(shù)量加一，數(shù)組里面可以包含未使用的字節(jié)，而這些字節(jié)的數(shù)量就由SDS的free屬性記錄。

通過未使用空間，SDS實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略。

1.空間預(yù)分配

空間預(yù)分配用于優(yōu)化SDS字符串增長操作：當(dāng)SDS的API對(duì)一個(gè)SDS進(jìn)行修改，并且需要對(duì)SDS進(jìn)行空間擴(kuò)展的時(shí)候，程序不僅會(huì)為SDS分配修改所必須要的空間，還會(huì)為SDS分配額外的未使用空間。其中額外分配的未使用空間數(shù)量由以下公司決定：

• 如果對(duì)SDS進(jìn)行修改之后，SDS的長度(也即len屬性的值)小于1MB，那么程序分配和len屬性同樣大小的未使用空間，這時(shí)SDS len屬性的值將和free屬性的值相同。舉個(gè)例子，如果進(jìn)行修改之后，SDS的len將變成13字節(jié)，那么程序也會(huì)分配13字節(jié)的未使用空間，SDS的buf數(shù)組的實(shí)際長度將變成13+13+1字節(jié)(額外的一字節(jié)用于保存空字符)。
• 如果對(duì)SDS進(jìn)行修改之后，SDS的長度將大于等于1MB，那么程序會(huì)分配1MB的未使用空間。舉個(gè)例子，如果進(jìn)行修改之后，SDS的len變成了30MB，那么程序會(huì)分配1MB的未使用空間，SDS的buf數(shù)組的實(shí)際長度為30MB+1MB+1byte。

通過空間預(yù)分配策略，Redis可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)。

2.惰性空間釋放

惰性空間釋放用于優(yōu)化SDS的字符串縮短操作：當(dāng)SDS的API需要縮短SDS保存的字符串是，程序并不立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié)，而是使用free屬性來將這些字節(jié)的數(shù)量記錄起來，并等待將來使用。

通過惰性空間釋放策略，SDS避免了縮短字符串時(shí)所需的內(nèi)存重分配操作，并未將來可能有的增長操作提供了優(yōu)化。與此同時(shí)，ADS也提供了相應(yīng)的API，讓我們可以在有需要時(shí)，真正地釋放SDS的未使用空間，所以不用擔(dān)心惰性空間釋放策略會(huì)造成內(nèi)存浪費(fèi)。

2.4二進(jìn)制安全

?

什么是二進(jìn)制安全？

通俗地將，C語言中，用'\0'表示字符串的結(jié)束，如果字符串本身就有'\0'字符，字符串就會(huì)被截?cái)啵确嵌M(jìn)制安全；若通過某種機(jī)制，保證讀寫字符串時(shí)不損害其內(nèi)容，則是二進(jìn)制安全。

?

C字符串中的字符必須符合某種編碼(比如ASCII),并且除了字符串的末尾之外，字符串里面不能包含空字符，否則最先被程序讀入的空字符將被誤認(rèn)為是字符串結(jié)尾，這些限制使得C字符串只能保存文本數(shù)據(jù)，而不能保存像圖片、音頻、視頻、壓縮文件這樣的二進(jìn)制數(shù)據(jù)。

為了確保Redis可以適用于各種不同的使用場(chǎng)景(保存文本、圖像、音視頻等)，SDS的API都是二進(jìn)制安全的(binary-safe)，所有SDS API都會(huì)以處理二進(jìn)制的方式來處理SDS存放在buf數(shù)組里的數(shù)據(jù)，程序不會(huì)對(duì)其中的數(shù)據(jù)做任何限制、過濾、或者假設(shè)，數(shù)據(jù)在寫入時(shí)是神峨眉樣的，它被讀取時(shí)就是什么樣的。

這也是將SDS的buf屬性成為字節(jié)數(shù)組的原因----Redis不是用這個(gè)數(shù)組來保存字符，而是用它來保存一系列二進(jìn)制數(shù)據(jù)。

公眾號(hào)后臺(tái)回復(fù)「手冊(cè)」獲取資料