面試殺手锏：Redis源碼之SDS

1.前言

Hello，歡迎大家來到《 Redis 數(shù)據(jù)結(jié)構(gòu)源碼解析系列》，在《Redis為什么這么快？》一文中我說過 Redis 速度快的一個(gè)原因就是其簡單且高效的數(shù)據(jù)結(jié)構(gòu)。

本系列文章面向各個(gè)階段的 Coder 們，新手也不用怕。每一篇文章敖丙都將從命令實(shí)戰(zhàn)入門入手，隨后深入源碼解析，最后面試題回顧這三個(gè)方向上給各位卷王一一介紹。

2.SDS命令實(shí)戰(zhàn)[初來乍到]

SDS 是 Redis 中最簡單的數(shù)據(jù)結(jié)構(gòu)。Redis 中所有的數(shù)據(jù)結(jié)構(gòu)都是以唯一的 key 字符串作為名稱，根據(jù) key 獲取value，差異僅在于 value 的數(shù)據(jù)結(jié)構(gòu)不同。

SDS 在生產(chǎn)環(huán)境中使用非常廣泛，比如，我們使用 SDS 做分布式鎖；將對(duì)象轉(zhuǎn)成 JSON 串作為緩存等。

在 Redis 面試過程中一旦提及相關(guān)數(shù)據(jù)結(jié)構(gòu) SDS 一定是繞不過去的話題，它很簡單（或者說看完此文后很簡單??），面試官可以不問，但我們不能不懂??。

首先我們從命令實(shí)戰(zhàn)開始切入吧~（老司機(jī)直接跳過）

更多命令查看官網(wǎng)：https://redis.io/commands#string

2. 1設(shè)置字符串

格式：set 。其中value的值可以為字節(jié)串(byte string)、整型和浮點(diǎn)數(shù)。

>?set?name?aobing
OK

2.2 獲取字符串

格式：get 。

>?get?name
"aobing"

2.3 獲取字符串長度

格式：strlen

>?strlen?name
(integer)?6

2.4 獲取子串

格式：getrange start end。獲取字符串的子串，在Redis2.0之前此命令為substr，現(xiàn)使用getrange。返回位移為start(從0開始)和end之間(都包括，而不是像其他語言中的包頭不包尾)的子串。

可以使用負(fù)偏移量來提供從字符串末尾開始的偏移量。因此-1表示最后一個(gè)字符，-2表示倒數(shù)第二個(gè)，依此類推。

該函數(shù)通過將結(jié)果范圍限制為字符串的實(shí)際長度來處理超出范圍的請(qǐng)求(end設(shè)置非常大也是到字符串末尾就截止了)。

127.0.0.1:6379>?set?mykey?"This?is?a?string"
OK
127.0.0.1:6379>?getrange?mykey?0?3
"This"
127.0.0.1:6379>?getrange?mykey?-3?-1
"ing"
127.0.0.1:6379>?getrange?mykey?0?-1
"This?is?a?string"
127.0.0.1:6379>?getrange?mykey?10?10000
"string"

2.5 設(shè)置子串

格式：setrange offset substr。返回值：修改后字符串的長度。

從value的整個(gè)長度開始，從指定的偏移量覆蓋key處存儲(chǔ)的一部分字符串。如果偏移量大于key處字符串的當(dāng)前長度，則該字符串將填充零字節(jié)以使偏移量適合。

不存在的鍵被視為空字符串，因此此命令將確保它包含足夠大的字符串以能夠?qū)⒅翟O(shè)置為offset。

注意：您可以設(shè)置的最大偏移為2^29 - 1（536870911），因?yàn)镽edis字符串限制為512 MB。如果您需要超出此大小，可以使用多個(gè)鍵。

127.0.0.1:6379>?set?key1?"hello?world"
OK
127.0.0.1:6379>?setrange?key1?6?redis
(integer)?11
127.0.0.1:6379>?get?key1
"hello?redis"
127.0.0.1:6379>?setrange?key2?6?redis
(integer)?11
127.0.0.1:6379>?get?key2
"\x00\x00\x00\x00\x00\x00redis"

2.6 追加子串

格式：append substr如果key已經(jīng)存在并且是字符串，則此命令將value在字符串末尾附加。如果key不存在，則會(huì)創(chuàng)建它并將其設(shè)置為空字符串，因此APPEND在這種特殊情況下 將類似于SET。

127.0.0.1:6379>?exists?key4
(integer)?0
127.0.0.1:6379>?append?key4?hello
(integer)?5
127.0.0.1:6379>?append?key4?world
(integer)?10
127.0.0.1:6379>?get?key4
"helloworld"

2.7 計(jì)數(shù)

在使用Redis中我們經(jīng)常將字符串做為計(jì)數(shù)器，使用incr命令進(jìn)行加一。格式：incr 。返回值：key遞增后的值。將存儲(chǔ)的數(shù)字key加1。如果key不存在，則在執(zhí)行操作之前將其設(shè)置為0。如果key包含錯(cuò)誤類型的值或包含不能表示為整數(shù)的字符串，則返回錯(cuò)誤。此操作僅限于64位帶符號(hào)整數(shù)。計(jì)數(shù)是由范圍的，它不能超過Long.Max，不能低于Long.Min。

2.8 過期和刪除

字符串可以使用del命令進(jìn)行刪除，也可以使用expire命令設(shè)置過期時(shí)間，到期自動(dòng)刪除。我們可以使用ttl命令獲取字符串的壽命（還有多少時(shí)間過期）。

格式：del ...返回值：刪除key的個(gè)數(shù)

127.0.0.1:6379>?SET?key1?"Hello"
"OK"
127.0.0.1:6379>?SET?key2?"World"
"OK"
127.0.0.1:6379>?DEL?key1?key2?key3
(integer)?2?

格式：expire time返回值：如果設(shè)置了超時(shí)返回1。如果key不存在返回0。

如何將設(shè)置了過期的字符串設(shè)置為永久的呢？

生存時(shí)間可以通過使用DEL命令來刪除整個(gè) key 來移除，或者被SET和GETSET命令覆寫(overwrite)，這意味著，如果一個(gè)命令只是修改一個(gè)帶生存時(shí)間的 key 的值而不是用一個(gè)新的 key 值來代替(replace)它的話，那么生存時(shí)間不會(huì)被改變。

比如說，對(duì)一個(gè) key 執(zhí)行INCR命令，對(duì)一個(gè)列表進(jìn)行LPUSH命令，或者對(duì)一個(gè)哈希表執(zhí)行HSET命令，這類操作都不會(huì)修改 key 本身的生存時(shí)間。

如果使用RENAME對(duì)一個(gè) key 進(jìn)行改名，那么改名后的 key 的生存時(shí)間和改名前一樣。

RENAME 命令的另一種可能是，嘗試將一個(gè)帶生存時(shí)間的 key 改名成另一個(gè)帶生存時(shí)間的 another_key ，這時(shí)舊的 another_key (以及它的生存時(shí)間)會(huì)被刪除，然后舊的 key 會(huì)改名為 another_key ，因此，新的 another_key 的生存時(shí)間也和原本的 key 一樣。

使用PERSIST命令可以在不刪除 key 的情況下，移除 key 的生存時(shí)間，讓 key 重新成為一個(gè)『持久的』(persistent) key 。

127.0.0.1:6379>?expire?age?100
(integer)?1
127.0.0.1:6379>?ttl?age
(integer)?97
127.0.0.1:6379>?set?age?20
OK
127.0.0.1:6379>?ttl?age
(integer)?-1
127.0.0.1:6379>?expire?age?100
(integer)?1
127.0.0.1:6379>?ttl?age
(integer)?98
127.0.0.1:6379>?rename?age?age2
OK
127.0.0.1:6379>?ttl?age2
(integer)?87
127.0.0.1:6379>?expire?age?100
(integer)?1
127.0.0.1:6379>?ttl?age
(integer)?96
127.0.0.1:6379>?persist?age
(integer)?1
127.0.0.1:6379>?ttl?age
(integer)?-1

3.SDS 簡介與特性[八股]

Redis 面試中大概率會(huì)提及相關(guān)的數(shù)據(jù)結(jié)構(gòu)，SDS 的八股文大部分人倒背如流，可是沒有讀過源碼，知其然不知其所以然，這可萬萬使不得呀?。?/p>

4.SDS 結(jié)構(gòu)模型[老司機(jī)]

本次敖丙閱讀的Redis源碼為最新的 Redis6.2.6 和 Redis3.0.0 版本

相信各位看官在聽到 Redis 中的字符串不是簡簡單單的C語言中的字符串，是 SDS（Simple Dynamic String，簡單動(dòng)態(tài)字符串）時(shí)以為是造出了啥新類型呢，對(duì)此，敖丙想說的是不慌，其實(shí) SDS 內(nèi)容的源碼底層就是typedef char *sds;。

4.1 數(shù)據(jù)結(jié)構(gòu)

Redis6.x 的 SDS 的數(shù)據(jù)結(jié)構(gòu)定義與 Redis3.0.0 相差比較大，但是核心思想不變。先從簡單版本（Redis3.x）開始吧~

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

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

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

如下圖所示為字符串"Aobing"在Redis中的存儲(chǔ)形式：

• len 為6，表示這個(gè) SDS 保存了一個(gè)長度為5的字符串；
• free 為0，表示這個(gè) SDS 沒有剩余空間；
• buf 是個(gè)char類型的數(shù)組，注意末尾保存了一個(gè)空字符'\0'。

buf 尾部自動(dòng)追加一個(gè)'\0'字符并不會(huì)計(jì)算在 SDS 的len中，這是為了遵循 C 字符串以空字符串結(jié)尾的慣例，使得 SDS 可以直接使用一部分string.h庫中的函數(shù)，如strlen

#include?
#include?

int?main()
{
????char?buf[]?=?{'A','o','b','i','n','g','\0'};
????printf("%s\n",buf);?????????????//?Aobing
????printf("%lu\n",strlen(buf));????//?6
????return?0;
}

4.2 苛刻的數(shù)據(jù)優(yōu)化

4.2.1 數(shù)據(jù)結(jié)構(gòu)優(yōu)化

目前我們似乎得到了一個(gè)結(jié)構(gòu)不錯(cuò)的 SDS ，但是我們能否繼續(xù)進(jìn)行優(yōu)化呢？

在 Redis3.x 版本中不同長度的字符串占用的頭部是相同的，如果某一字符串很短但是頭部卻占用了更多的空間，這未免太浪費(fèi)了。所以我們將 SDS 分為三種級(jí)別的字符串：

• 短字符串(長度小于32)，len和free的長度用1字節(jié)即可；
• 長字符串，用2字節(jié)或者4字節(jié)；
• 超長字符串，用8字節(jié)。

共有五種類型的SDS（長度小于1字節(jié)、1字節(jié)、2字節(jié)、4字節(jié)、8字節(jié)）

我們可以在 SDS 中新增一個(gè) type 字段來標(biāo)識(shí)類型，但是沒必要使用一個(gè) 4 字節(jié)的int類型去做！可以使用 1 字節(jié)的char類型，通過位運(yùn)算（3位即可標(biāo)識(shí)2^3種類型）來獲取類型。

如下所示為短字符串(長度小于32)的優(yōu)化形式：

低三位存儲(chǔ)類型，高5位存儲(chǔ)長度，最多能標(biāo)識(shí)的長度為32，所以短字符串的長度必定小于32。

無需free字段了，32-len即為free

敖丙帶大家分析了一波，接下來看看Redis6.x中是怎么做的吧！

//?注意：sdshdr5從未被使用，Redis中只是訪問flags。
struct?__attribute__?((__packed__))?sdshdr5?{
????unsigned?char?flags;?/*?低3位存儲(chǔ)類型,?高5位存儲(chǔ)長度?*/
????char?buf[];
};
struct?__attribute__?((__packed__))?sdshdr8?{
????uint8_t?len;?/*?已使用?*/
????uint8_t?alloc;?/*?總長度，用1字節(jié)存儲(chǔ)?*/
????unsigned?char?flags;?/*?低3位存儲(chǔ)類型,?高5位預(yù)留?*/
????char?buf[];
};
struct?__attribute__?((__packed__))?sdshdr16?{
????uint16_t?len;?/*?已使用?*/
????uint16_t?alloc;?/*?總長度，用2字節(jié)存儲(chǔ)?*/
????unsigned?char?flags;?/*?低3位存儲(chǔ)類型,?高5位預(yù)留?*/
????char?buf[];
};
struct?__attribute__?((__packed__))?sdshdr32?{
????uint32_t?len;?/*?已使用?*/
????uint32_t?alloc;?/*?總長度，用4字節(jié)存儲(chǔ)?*/
????unsigned?char?flags;?/*?低3位存儲(chǔ)類型,?高5位預(yù)留?*/
????char?buf[];
};
struct?__attribute__?((__packed__))?sdshdr64?{
????uint64_t?len;?/*?已使用?*/
????uint64_t?alloc;?/*?總長度，用8字節(jié)存儲(chǔ)?*/
????unsigned?char?flags;?/*?低3位存儲(chǔ)類型,?高5位預(yù)留?*/
????char?buf[];
};

數(shù)據(jù)結(jié)構(gòu)和我們分析的差不多嘛！也是加一個(gè)標(biāo)識(shí)字段而已，并且不是int類型，而是1字節(jié)的char類型，使用其中的3位表示具體的類型。

同時(shí)，Redis 中也聲明了5個(gè)常量分別表示五種類型的 SDS ，與我們分析的也不謀而合。

#define?SDS_TYPE_5??0
#define?SDS_TYPE_8??1
#define?SDS_TYPE_16?2
#define?SDS_TYPE_32?3
#define?SDS_TYPE_64?4

4.2.2 uintX_t

對(duì)比前后兩版代碼，不難發(fā)現(xiàn)在 Redis6.x 中 int 類型也多出了幾種：uint8_t / uint16_t / uint32_t /uint64_t。乍一看以為是新增類型呢，畢竟 C語言里面可沒有這些類型呀！

敖丙初見也是滿頭霧水，畢竟C 語言忘得差不多了。不過我憑借強(qiáng)大的知識(shí)儲(chǔ)備(不要face ^_^)猜測(cè)這可能是一個(gè)別名，C語言中有typedef呀！而_t就是其縮寫。查看相關(guān)源碼，果然~~

typedef?unsigned?char?uint8_t;
typedef?unsigned?short?uint16_t;
typedef?unsigned?int?uint32_t;
typedef?unsigned?long?long?uint64_t;

4.2.3 對(duì)齊填充

在 Redis6.x 的源碼中 SDS 的結(jié)構(gòu)體為struct __attribute__ ((__packed__))與struct有較大的差別，這其實(shí)和我們熟知的對(duì)齊填充有關(guān)。

(1) 舉個(gè)栗子??

考慮如下結(jié)構(gòu)體：

typedef?struct{
?????char??c1;
?????short?s;?
?????char??c2;?
?????int???i;
}?s;

若此結(jié)構(gòu)體中的成員都是緊湊排列的，假設(shè)c1的起始地址為0，則s的地址為1，c2的地址為3，i的地址為4。下面用代碼論證一下我們的假設(shè)。

#include?

typedef?struct
{
????char?c1;
????short?s;
????char?c2;
????int?i;
}?s;

int?main()
{
????s?a;
????printf("c1?->?%d,?s?->?%d,?c2?->?%d,?i?->?%d\n",
???????????(unsigned?int)(void?*)&a.c1?-?(unsigned?int)(void?*)&a,
???????????(unsigned?int)(void?*)&a.s?-?(unsigned?int)(void?*)&a,
???????????(unsigned?int)(void?*)&a.c2?-?(unsigned?int)(void?*)&a,
???????????(unsigned?int)(void?*)&a.i?-?(unsigned?int)(void?*)&a);
????return?0;
}
//?結(jié)果為：c1 ->?0, s -> 2, c2 -> 4, i -> 8

尷尬??了，和假設(shè)差的不是一星半點(diǎn)呀！這就是對(duì)齊填充搞的鬼，這啥啥啥呀~

(2) 什么是字節(jié)對(duì)齊

現(xiàn)代計(jì)算機(jī)中，內(nèi)存空間按照字節(jié)劃分，理論上可以從任何起始地址訪問任意類型的變量。

但實(shí)際中在訪問特定類型變量時(shí)經(jīng)常在特定的內(nèi)存地址訪問，這就需要各種類型數(shù)據(jù)按照一定的規(guī)則在空間上排列，而不是順序一個(gè)接一個(gè)地存放，這就是對(duì)齊。

(3) 對(duì)齊原因

為什么需要對(duì)齊填充是由于各個(gè)硬件平臺(tái)對(duì)存儲(chǔ)空間的處理上有很大的不同。

一些平臺(tái)對(duì)某些特定類型的數(shù)據(jù)只能從某些特定地址開始存取。最常見的是如果不按照適合其平臺(tái)的要求對(duì)數(shù)據(jù)存放進(jìn)行對(duì)齊，會(huì)在存取效率上帶來損失。

比如有些平臺(tái)每次讀都是從偶地址開始，如果一個(gè)int型（假設(shè)為 32位）存放在偶地址開始的地方，那么一個(gè)讀周期就可以讀出，而如果存放在奇地址開始的地方，就可能會(huì)需要2個(gè)讀周期，并對(duì)兩次讀出的結(jié)果的高低字節(jié)進(jìn)行拼湊才能得到該int數(shù)據(jù)，導(dǎo)致在讀取效率上下降很多。

(4) 更改對(duì)齊方式

注意：我們寫程序的時(shí)候，不需要考慮對(duì)齊問題。編譯器會(huì)替我們選擇適合目標(biāo)平臺(tái)的對(duì)齊策略。

如果我們一定要手動(dòng)更改對(duì)齊方式，一般可以通過下面的方法來改變?nèi)笔〉膶?duì)界條件：

• 使用偽指令#pragma pack(n)：C編譯器將按照n個(gè)字節(jié)對(duì)齊；

• 使用偽指令#pragma pack()：取消自定義字節(jié)對(duì)齊方式。

  另外，還有如下的一種方式(GCC特有語法)：

• __attribute((aligned (n)))：讓所作用的結(jié)構(gòu)成員對(duì)齊在n字節(jié)自然邊界上。如果結(jié)構(gòu)體中有成員的長度大于n，則按照最大成員的長度來對(duì)齊。

• __attribute__ ((packed))：取消結(jié)構(gòu)在編譯過程中的優(yōu)化對(duì)齊，按照實(shí)際占用字節(jié)數(shù)進(jìn)行對(duì)齊。

將上述示例代碼的結(jié)構(gòu)體更改如下(取消對(duì)齊)，再次執(zhí)行，可以發(fā)現(xiàn)取消對(duì)齊后和我們的假設(shè)就一致了。

typedef?struct?__attribute__?((__packed__))
{
????char?c1;
????short?s;
????char?c2;
????int?i;
}?s;
//?再次執(zhí)行：c1 ->?0, s -> 1, c2 -> 3, i -> 4

(5) Redis為什么不對(duì)齊呢？

綜上所述我們知道了對(duì)齊填充可以提高 CPU 的數(shù)據(jù)讀取效率，作為 IO 頻繁的 Redis 為什么選擇不對(duì)齊呢？

我們?cè)俅位仡?Redis6.x 中的 SDS 結(jié)構(gòu)：

有個(gè)細(xì)節(jié)各位需要知道，即 SDS 的指針并不是指向 SDS 的起始位置（len位置），而是直接指向buf[]，使得 SDS 可以直接使用 C 語言string.h庫中的某些函數(shù)，做到了兼容，十分nice~。

如果不進(jìn)行對(duì)齊填充，那么在獲取當(dāng)前 SDS 的類型時(shí)則只需要后退一步即可flagsPointer = ((unsigned char*)s)-1；相反，若進(jìn)行對(duì)齊填充，由于 Padding 的存在，我們?cè)诓煌南到y(tǒng)中不知道退多少才能獲得flags，并且我們也不能將 sds 的指針指向flags，這樣就無法兼容 C 語言的函數(shù)了，也不知道前進(jìn)多少才能得到 buf[]。

4.3 SDS 優(yōu)勢(shì)

4.3.1 O(1)時(shí)間復(fù)雜度獲取字符串長度

由于C字符串不記錄自身的長度，所以為了獲取一個(gè)字符串的長度程序必須遍歷這個(gè)字符串，直至遇到'0'為止，整個(gè)操作的時(shí)間復(fù)雜度為O(N)。而我們使用SDS封裝字符串則直接獲取len屬性值即可，時(shí)間復(fù)雜度為O(1)。

4.3.2 二進(jìn)制安全

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

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

C字符串中的字符除了末尾字符為'\0'外其他字符不能為空字符，否則會(huì)被認(rèn)為是字符串結(jié)尾(即使實(shí)際上不是)。

這限制了C字符串只能保存文本數(shù)據(jù)，而不能保存二進(jìn)制數(shù)據(jù)。而SDS使用len屬性的值判斷字符串是否結(jié)束，所以不會(huì)受'\0'的影響。

4.3.3 杜絕緩沖區(qū)溢出

字符串的拼接操作是使用十分頻繁的，在C語言開發(fā)中使用char *strcat(char *dest,const char *src)方法將src字符串中的內(nèi)容拼接到dest字符串的末尾。由于C字符串不記錄自身的長度，所有strcat方法已經(jīng)認(rèn)為用戶在執(zhí)行此函數(shù)時(shí)已經(jīng)為dest分配了足夠多的內(nèi)存，足以容納src字符串中的所有內(nèi)容，而一旦這個(gè)條件不成立就會(huì)產(chǎn)生緩沖區(qū)溢出，會(huì)把其他數(shù)據(jù)覆蓋掉，Dangerous~。

//?strcat?源碼
char?*?__cdecl?strcat?(char?*?dst,?const?char?*?src)
{
????char?*?cp?=?dst;
?
????while(?*cp?)
????????cp++;?/*?找到?dst?的結(jié)尾?*/
?
????while(?*cp++?=?*src++?)?;?/*?無腦將?src?復(fù)制到?dst?中?*/
?
????return(?dst?);?/*?返回?dst?*/
}????

如下圖所示為一次緩沖區(qū)溢出：

與C字符串不同，SDS 的自動(dòng)擴(kuò)容機(jī)制完全杜絕了發(fā)生緩沖區(qū)溢出的可能性：

當(dāng)SDS API需要對(duì)SDS進(jìn)行修改時(shí)，API會(huì)先檢查 SDS 的空間是否滿足修改所需的要求，如果不滿足，API會(huì)自動(dòng)將SDS的空間擴(kuò)展至執(zhí)行修改所需的大小，然后才執(zhí)行實(shí)際的修改操作，所以使用 SDS 既不需要手動(dòng)修改SDS的空間大小，也不會(huì)出現(xiàn)緩沖區(qū)溢出問題。?

SDS 的sds sdscat(sds s, const char *t)方法在字符串拼接時(shí)會(huì)進(jìn)行擴(kuò)容相關(guān)操作。

sds?sdscatsds(sds?s,?const?sds?t)?{
????return?sdscatlen(s,?t,?sdslen(t));
}

/*?s:?源字符串
?*?t:?待拼接字符串
?*?len:?待拼接字符串長度
?*/
sds?sdscatlen(sds?s,?const?void?*t,?size_t?len)?{
????//?獲取源字符串長度
????size_t?curlen?=?sdslen(s);
??//?SDS?分配空間（自動(dòng)擴(kuò)容機(jī)制）
????s?=?sdsMakeRoomFor(s,len);
????if?(s?==?NULL)?return?NULL;
????//?將目標(biāo)字符串拷貝至源字符串末尾
????memcpy(s+curlen,?t,?len);
????//?更新?SDS?長度
????sdssetlen(s,?curlen+len);
????//?追加結(jié)束符
????s[curlen+len]?=?'\0';
????return?s;
}

自動(dòng)擴(kuò)容機(jī)制——sdsMakeRoomFor方法

strcatlen中調(diào)用sdsMakeRoomFor完成字符串的容量檢查及擴(kuò)容操作，重點(diǎn)分析此方法：

/*?s:?源字符串
?*?addlen:?新增長度
?*/
sds?sdsMakeRoomFor(sds?s,?size_t?addlen)?{
????void?*sh,?*newsh;
????//?sdsavail:?s->alloc?-?s->len,?獲取?SDS?的剩余長度
????size_t?avail?=?sdsavail(s);
????size_t?len,?newlen,?reqlen;
????//?根據(jù)?flags?獲取?SDS?的類型?oldtype
????char?type,?oldtype?=?s[-1]?&?SDS_TYPE_MASK;
????int?hdrlen;
????size_t?usable;

????/*?Return?ASAP?if?there?is?enough?space?left.?*/
????//?剩余空間大于等于新增空間，無需擴(kuò)容，直接返回源字符串
????if?(avail?>=?addlen)?return?s;
????//?獲取當(dāng)前長度
????len?=?sdslen(s);
????//?
????sh?=?(char*)s-sdsHdrSize(oldtype);
????//?新長度
????reqlen?=?newlen?=?(len+addlen);
????//?斷言新長度比原長度長，否則終止執(zhí)行
????assert(newlen?>?len);???/*?防止數(shù)據(jù)溢出?*/
????//?SDS_MAX_PREALLOC?=?1024*1024,?即1MB
????if?(newlen?????????//?新增后長度小于?1MB?，則按新長度的兩倍擴(kuò)容
????????newlen?*=?2;
????else
????????//?新增后長度大于?1MB?，則按新長度加上?1MB?擴(kuò)容
????????newlen?+=?SDS_MAX_PREALLOC;
????//?重新計(jì)算?SDS?的類型
????type?=?sdsReqType(newlen);

????/*?Don't?use?type?5:?the?user?is?appending?to?the?string?and?type?5?is
?????*?not?able?to?remember?empty?space,?so?sdsMakeRoomFor()?must?be?called
?????*?at?every?appending?operation.?*/
????//?不使用?sdshdr5?
????if?(type?==?SDS_TYPE_5)?type?=?SDS_TYPE_8;
????//?獲取新的?header?大小
????hdrlen?=?sdsHdrSize(type);
????assert(hdrlen?+?newlen?+?1?>?reqlen);??/*?Catch?size_t?overflow?*/
????if?(oldtype==type)?{
????????//?類型沒變
????????//?調(diào)用?s_realloc_usable?重新分配可用內(nèi)存，返回新?SDS?的頭部指針
????????//?usable?會(huì)被設(shè)置為當(dāng)前分配的大小
????????newsh?=?s_realloc_usable(sh,?hdrlen+newlen+1,?&usable);
????????if?(newsh?==?NULL)?return?NULL;?//?分配失敗直接返回NULL
????????//?獲取指向?buf?的指針
????????s?=?(char*)newsh+hdrlen;
????}?else?{
????????//?類型變化導(dǎo)致?header?的大小也變化，需要向前移動(dòng)字符串，不能使用?realloc
????????newsh?=?s_malloc_usable(hdrlen+newlen+1,?&usable);
????????if?(newsh?==?NULL)?return?NULL;
????????//?將原字符串copy至新空間中
????????memcpy((char*)newsh+hdrlen,?s,?len+1);
????????//?釋放原字符串內(nèi)存
????????s_free(sh);
????????s?=?(char*)newsh+hdrlen;
????????//?更新?SDS?類型
????????s[-1]?=?type;
????????//?設(shè)置長度
????????sdssetlen(s,?len);
????}
????//?獲取?buf?總長度(待定)
????usable?=?usable-hdrlen-1;
????if?(usable?>?sdsTypeMaxSize(type))
????????//?若可用空間大于當(dāng)前類型支持的最大長度則截?cái)?/span>
????????usable?=?sdsTypeMaxSize(type);
????//?設(shè)置?buf?總長度
????sdssetalloc(s,?usable);
????return?s;
}

自動(dòng)擴(kuò)容機(jī)制總結(jié)：

擴(kuò)容階段：

• 若 SDS 中剩余空閑空間 avail 大于新增內(nèi)容的長度 addlen，則無需擴(kuò)容；
• 若 SDS 中剩余空閑空間 avail 小于或等于新增內(nèi)容的長度 addlen：
• 若新增后總長度 len+addlen < 1MB，則按新長度的兩倍擴(kuò)容；
• 若新增后總長度 len+addlen > 1MB，則按新長度加上 1MB 擴(kuò)容。

內(nèi)存分配階段：

• 根據(jù)擴(kuò)容后的長度選擇對(duì)應(yīng)的 SDS 類型：
• 若類型不變，則只需通過 s_realloc_usable擴(kuò)大 buf 數(shù)組即可；
• 若類型變化，則需要為整個(gè) SDS 重新分配內(nèi)存，并將原來的 SDS 內(nèi)容拷貝至新位置。

自動(dòng)擴(kuò)容流程圖如下所示：

擴(kuò)容后的 SDS 不會(huì)恰好容納下新增的字符，而是多分配了一些空間(預(yù)分配策略)，這減少了修改字符串時(shí)帶來的內(nèi)存重分配次數(shù)

4.3.4 內(nèi)存重分配次數(shù)優(yōu)化

(1) 空間預(yù)分配策略

因?yàn)?SDS 的空間預(yù)分配策略， SDS 字符串在增長過程中不會(huì)頻繁的進(jìn)行空間分配。

通過這種分配策略，SDS 將連續(xù)增長N次字符串所需的內(nèi)存重分配次數(shù)從必定N次降低為最多N次。

(2) 惰性空間釋放機(jī)制

空間預(yù)分配策略用于優(yōu)化 SDS 增長時(shí)頻繁進(jìn)行空間分配，而惰性空間釋放機(jī)制則用于優(yōu)化 SDS 字符串縮短時(shí)并不立即使用內(nèi)存重分配來回收縮短后多出來的空間，而僅僅更新 SDS 的len屬性，多出來的空間供將來使用。

SDS 中調(diào)用sdstrim方法來縮短字符串：

/*?sdstrim?方法刪除字符串首尾中在?cset?中出現(xiàn)過的字符
?*?比如:
?*?s?=?sdsnew("AA...AA.a.aa.aHelloWorld?????:::");
?*?s?=?sdstrim(s,"Aa.?:");
?*?printf("%s\n",?s);
?*
?*?SDS?變成了?"HelloWorld"
?*/
sds?sdstrim(sds?s,?const?char?*cset)?{
????char?*start,?*end,?*sp,?*ep;
????size_t?len;

????sp?=?start?=?s;
????ep?=?end?=?s+sdslen(s)-1;
????//?strchr()函數(shù)用于查找給定字符串中某一個(gè)特定字符
????while(sp?<=?end?&&?strchr(cset,?*sp))?sp++;
????while(ep?>?sp?&&?strchr(cset,?*ep))?ep--;
????len?=?(sp?>?ep)???0?:?((ep-sp)+1);
????if?(s?!=?sp)?memmove(s,?sp,?len);
????s[len]?=?'\0';
????//?僅僅更新了len
????sdssetlen(s,len);
????return?s;
}

勘誤

在《Redis的設(shè)計(jì)與實(shí)現(xiàn)》一書中針對(duì) sdstrim方法的講解為：刪除字符串中 cset 出現(xiàn)的所有字符，而不是首尾。

比如：調(diào)用sdstrim("XYXaYYbcXyY","XY")，后移除了所有的'X'和'Y'。這是錯(cuò)誤?的~

SDS 并沒有釋放多出來的5字節(jié)空間，僅僅將 len 設(shè)置成了7，剩余空間為5。如果后續(xù)字符串增長時(shí)則可以派上用場(chǎng)（可能不需要再分配內(nèi)存）。

也許各位又會(huì)有疑問了，這沒真正釋放空間，是否會(huì)導(dǎo)致內(nèi)存泄漏呢？

放心，SDS為我們提供了真正釋放SDS未使用空間的方法sdsRemoveFreeSpace。

sds?sdsRemoveFreeSpace(sds?s)?{
????void?*sh,?*newsh;
????//?獲取類型
????char?type,?oldtype?=?s[-1]?&?SDS_TYPE_MASK;
????//?獲取?header?大小
????int?hdrlen,?oldhdrlen?=?sdsHdrSize(oldtype);
????//?獲取原字符串長度
????size_t?len?=?sdslen(s);
????//?獲取可用長度
????size_t?avail?=?sdsavail(s);
????//?獲取指向頭部的指針
????sh?=?(char*)s-oldhdrlen;

????/*?Return?ASAP?if?there?is?no?space?left.?*/
????if?(avail?==?0)?return?s;

????//?查找適合這個(gè)字符串長度的最優(yōu)?SDS?類型
????type?=?sdsReqType(len);
????hdrlen?=?sdsHdrSize(type);

????/*?如果類型相同，或者至少仍然需要一個(gè)足夠大的類型，我們只需 realloc buf即可；
?????*?否則，說明變化很大，則手動(dòng)重新分配字符串以使用不同的頭文件類型。
?????*/
????if?(oldtype==type?||?type?>?SDS_TYPE_8)?{
????????newsh?=?s_realloc(sh,?oldhdrlen+len+1);
????????if?(newsh?==?NULL)?return?NULL;
????????s?=?(char*)newsh+oldhdrlen;
????}?else?{
????????newsh?=?s_malloc(hdrlen+len+1);
????????if?(newsh?==?NULL)?return?NULL;
????????memcpy((char*)newsh+hdrlen,?s,?len+1);
????????//?釋放內(nèi)存
????????s_free(sh);
????????s?=?(char*)newsh+hdrlen;
????????s[-1]?=?type;
????????sdssetlen(s,?len);
????}
????//?重新設(shè)置總長度為len
????sdssetalloc(s,?len);
????return?s;
}

4.4 SDS 最長多少？

Redis 官方給出了最大的字符串容量為 512MB。這是為什么呢？

在 Reids3.x 版本中len是使用int修飾的，這就會(huì)導(dǎo)致 buf 最長就是2147483647，無形中限制了字符串的最大長度。

任何細(xì)節(jié)在源碼中都能發(fā)現(xiàn)，在_sdsnewlen方法創(chuàng)建 SDS 中都會(huì)調(diào)用sdsTypeMaxSize方法獲取每種類型所能創(chuàng)建的最大buf長度，不難發(fā)現(xiàn)此方法最大的返回值為2147483647，即512MB。

static?inline?size_t?sdsTypeMaxSize(char?type)?{
????if?(type?==?SDS_TYPE_5)
????????return?(1<<5)?-?1;
????if?(type?==?SDS_TYPE_8)
????????return?(1<<8)?-?1;
????if?(type?==?SDS_TYPE_16)
????????return?(1<<16)?-?1;
#if?(LONG_MAX?==?LLONG_MAX)
????if?(type?==?SDS_TYPE_32)
????????return?(1ll<<32)?-?1;?//?不管方法啥意思，最大返回2147483647。OVER~
#endif
????return?-1;?/*?this?is?equivalent?to?the?max?SDS_TYPE_64?or?SDS_TYPE_32?*/
}

此方法在 Redis3.0.0中是不存在的

4.5 部分 API 源碼解讀

創(chuàng)建SDS

Redis 通過sdsnewlen方法創(chuàng)建 SDS。在方法中會(huì)根據(jù)字符串初始化長度選擇合適的類型。

sds?_sdsnewlen(const?void?*init,?size_t?initlen,?int?trymalloc)?{
????void?*sh;
????sds?s;
????//?根據(jù)初始化長度判斷?SDS?的類型
????char?type?=?sdsReqType(initlen);
????//?SDS_TYPE_5?強(qiáng)制轉(zhuǎn)換為?SDS_TYPE_8
????//?這樣側(cè)面驗(yàn)證了?sdshdr5?從未被使用，創(chuàng)建這一步就GG了???????u\
????if?(type?==?SDS_TYPE_5?&&?initlen?==?0)?type?=?SDS_TYPE_8;
????//?獲取頭部大學(xué)
????int?hdrlen?=?sdsHdrSize(type);
????//?指向?flags?的指針
????unsigned?char?*fp;?/*?flags?pointer.?*/
????//?分配的空間
????size_t?usable;
????//?防止溢出
????assert(initlen?+?hdrlen?+?1?>?initlen);?/*?Catch?size_t?overflow?*/
????//?分配空間
????//?s_trymalloc_usable:?嘗試分配內(nèi)存，失敗則返回NULL
????//?s_malloc_usable:?分配內(nèi)存或者拋異常[不友好]
????sh?=?trymalloc?
????????s_trymalloc_usable(hdrlen+initlen+1,?&usable)?:
????????s_malloc_usable(hdrlen+initlen+1,?&usable);
????if?(sh?==?NULL)?return?NULL;
????if?(init==SDS_NOINIT)
????????init?=?NULL;
????else?if?(!init)
????????memset(sh,?0,?hdrlen+initlen+1);
????//?s?此時(shí)指向buf
????s?=?(char*)sh+hdrlen;
????//?指向flags
????fp?=?((unsigned?char*)s)-1;
????usable?=?usable-hdrlen-1;
????//?對(duì)不同類型的?SDS?可分配空間進(jìn)行截?cái)?/span>
????if?(usable?>?sdsTypeMaxSize(type))
????????usable?=?sdsTypeMaxSize(type);
????switch(type)?{
????????case?SDS_TYPE_5:?{
????????????*fp?=?type?|?(initlen?<????????????break;
????????}
????????case?SDS_TYPE_8:?{
????????????SDS_HDR_VAR(8,s);
????????????sh->len?=?initlen;
????????????sh->alloc?=?usable;
????????????*fp?=?type;
????????????break;
????????}
????????//?...?省略
????}
????if?(initlen?&&?init)
????????memcpy(s,?init,?initlen);
????//?末尾添加\0
????s[initlen]?=?'\0';
????return?s;
}

通過sdsnewlen方法我們可以獲得以下信息：

• SDS_TYPE_5 會(huì)被強(qiáng)制轉(zhuǎn)換為 SDS_TYPE_8 類型；
• 創(chuàng)建時(shí)默認(rèn)會(huì)在末尾加'\0'；
• 返回值是指向 SDS 結(jié)構(gòu)中 buf 的指針；
• 返回值是char *sds類型，可以兼容部分C函數(shù)。

釋放SDS

為了優(yōu)化性能，SDS 提供了不直接釋放內(nèi)存，而是通過重置len達(dá)到清空 SDS 目的的方法——sdsclear。

改方法僅僅將 SDS 的len歸零，而buf的空間并為真正被清空，新的數(shù)據(jù)可以復(fù)寫，而不用重新申請(qǐng)內(nèi)存。

void?sdsclear(sds?s)?{
????sdssetlen(s,?0);//?設(shè)置len為0
????s[0]?=?'\0';//“清空”buf
}

若真正想清空 SDS 則可以調(diào)用sdsfree方法，底層通過調(diào)用s_free釋放內(nèi)存。

void?sdsfree(sds?s)?{
????if?(s?==?NULL)?return;
????s_free((char*)s-sdsHdrSize(s[-1]));
}