定義

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

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

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

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

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

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

獲取字符串長(zhǎng)度

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

內(nèi)存溢出問題

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

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

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

對(duì)于C語言字符串，因?yàn)榭偸怯幸粋€(gè)長(zhǎng)度為N+1的字符數(shù)組來保存一個(gè)長(zhǎng)度為N的字符串。所以，如果對(duì)C字符串進(jìn)行操作：

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

而對(duì)于SDS來說，不存在這些問題，通過兩個(gè)機(jī)制來解決以上問題：

• 空間預(yù)分配
• 惰性空間釋放

1. 空間預(yù)分配

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

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

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

2. 惰性空間釋放

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

二進(jìn)制安全

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

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

參考文章

Redis數(shù)據(jù)結(jié)構(gòu)——簡(jiǎn)單動(dòng)態(tài)字符串SDS - 隨心所于 - 博客園

《Redis設(shè)計(jì)與實(shí)現(xiàn)》

到此這篇關(guān)于Redis簡(jiǎn)單動(dòng)態(tài)字符串SDS的實(shí)現(xiàn)示例的文章就介紹到這了,更多相關(guān)Redis 動(dòng)態(tài)字符串SDS內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論