當(dāng)前位置：首頁(yè) > 编程资源 > 综合教程 >内容正文

综合教程

让我聊聊sds是什么(sds是什么意思)

發(fā)布時(shí)間：2023/12/24 综合教程 52 生活家

生活随笔收集整理的這篇文章主要介紹了让我聊聊sds是什么(sds是什么意思) 小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

1.前言

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

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

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

SDS 是 Redis 中最簡(jiǎn)單的數(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ò)程中一旦提及相關(guān)數(shù)據(jù)結(jié)構(gòu) SDS 一定是繞不過(guò)去的話題，它很簡(jiǎn)單（或者說(shuō)看完此文后很簡(jiǎn)單），面試官可以不問(wèn)，但我們不能不懂。

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

更多命令查看官網(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 獲取字符串長(zhǎng)度

格式：strlen

> strlen name (integer) 6

2.4 獲取子串

格式：getrange start end。獲取字符串的子串，在Redis2.0之前此命令為substr，現(xiàn)使用getrange。返回位移為start(從0開(kāi)始)和end之間(都包括，而不是像其他語(yǔ)言中的包頭不包尾)的子串?？梢允褂秘?fù)偏移量來(lái)提供從字符串末尾開(kāi)始的偏移量。

因此-1表示最后一個(gè)字符，-2表示倒數(shù)第二個(gè)，依此類(lèi)推。該函數(shù)通過(guò)將結(jié)果范圍限制為字符串的實(shí)際長(zhǎng)度來(lái)處理超出范圍的請(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。 返回值：修改后字符串的長(zhǎng)度。

從value的整個(gè)長(zhǎng)度開(kāi)始，從指定的偏移量覆蓋key處存儲(chǔ)的一部分字符串。如果偏移量大于key處字符串的當(dāng)前長(zhǎ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在這種特殊情況下將類(lèi)似于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ò)誤類(lèi)型的值或包含不能表示為整數(shù)的字符串，則返回錯(cuò)誤。此操作僅限于64位帶符號(hào)整數(shù)。計(jì)數(shù)是由范圍的，它不能超過(guò)Long.Max，不能低于Long.Min。

2.8 過(guò)期和刪除

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

格式：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è)置了過(guò)期的字符串設(shè)置為永久的呢？

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

比如說(shuō)，對(duì)一個(gè) key 執(zhí)行INCR命令，對(duì)一個(gè)列表進(jìn)行LPUSH命令，或者對(duì)一個(gè)哈希表執(zhí)行HSET命令，這類(lèi)操作都不會(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 簡(jiǎn)介與特性[八股]

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

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

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

相信各位看官在聽(tīng)到 Redis 中的字符串不是簡(jiǎn)簡(jiǎn)單單的C語(yǔ)言中的字符串，是 SDS（Simple Dynamic String，簡(jiǎn)單動(dòng)態(tài)字符串）時(shí)以為是造出了啥新類(lèi)型呢，對(duì)此，敖丙想說(shuō)的是不慌，其實(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 相差比較大，但是核心思想不變。先從簡(jiǎn)單版本（Redis3.x）開(kāi)始吧~

struct sdshdr { //記錄buf數(shù)組中已使用字節(jié)的數(shù)量 //等于SDS所保存字符串的長(zhǎng)度 unsigned int len; //記錄buf數(shù)組中未使用字節(jié)的數(shù)量 unsigned int free; //char數(shù)組，用于保存字符串 char buf[]; };

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

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

buf 尾部自動(dòng)追加一個(gè)'\0'字符并不會(huì)計(jì)算在 SDS 的len中，這是為了遵循 C 字符串以空字符串結(jié)尾的慣例，使得 SDS 可以直接使用一部分string.h庫(kù)中的函數(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 版本中不同長(zhǎng)度的字符串占用的頭部是相同的，如果某一字符串很短但是頭部卻占用了更多的空間，這未免太浪費(fèi)了。所以我們將 SDS 分為三種級(jí)別的字符串：

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

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

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

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

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

無(wú)需free字段了，32-len即為free

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

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

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

同時(shí)，Redis 中也聲明了5個(gè)常量分別表示五種類(lèi)型的 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 類(lèi)型也多出了幾種：uint8_t / uint16_t / uint32_t /uint64_t。乍一看以為是新增類(lèi)型呢，畢竟 C語(yǔ)言里面可沒(méi)有這些類(lèi)型呀！

敖丙初見(jiàn)也是滿頭霧水，畢竟C 語(yǔ)言忘得差不多了。不過(guò)我憑借強(qiáng)大的知識(shí)儲(chǔ)備(不要face ^_^)猜測(cè)這可能是一個(gè)別名，C語(yǔ)言中有typedef呀！而_t就是其縮寫(xiě)。查看相關(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é)劃分，理論上可以從任何起始地址訪問(wèn)任意類(lèi)型的變量。但實(shí)際中在訪問(wèn)特定類(lèi)型變量時(shí)經(jīng)常在特定的內(nèi)存地址訪問(wèn)，這就需要各種類(lèi)型數(shù)據(jù)按照一定的規(guī)則在空間上排列，而不是順序一個(gè)接一個(gè)地存放，這就是對(duì)齊。

(3) 對(duì)齊原因

為什么需要對(duì)齊填充是由于各個(gè)硬件平臺(tái)對(duì)存儲(chǔ)空間的處理上有很大的不同。一些平臺(tái)對(duì)某些特定類(lèi)型的數(shù)據(jù)只能從某些特定地址開(kāi)始存取。

最常見(jiàn)的是如果不按照適合其平臺(tái)的要求對(duì)數(shù)據(jù)存放進(jìn)行對(duì)齊，會(huì)在存取效率上帶來(lái)?yè)p失。

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

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

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

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

使用偽指令#pragma pack(n)：C編譯器將按照n個(gè)字節(jié)對(duì)齊；
使用偽指令#pragma pack()：取消自定義字節(jié)對(duì)齊方式。另外，還有如下的一種方式(GCC特有語(yǔ)法)：
__attribute((aligned (n)))：讓所作用的結(jié)構(gòu)成員對(duì)齊在n字節(jié)自然邊界上。如果結(jié)構(gòu)體中有成員的長(zhǎng)度大于n，則按照最大成員的長(zhǎng)度來(lái)對(duì)齊。
__attribute__ ((packed))：取消結(jié)構(gòu)在編譯過(guò)程中的優(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 語(yǔ)言string.h庫(kù)中的某些函數(shù)，做到了兼容，十分nice~。

如果不進(jìn)行對(duì)齊填充，那么在獲取當(dāng)前 SDS 的類(lèi)型時(shí)則只需要后退一步即可flagsPointer = ((unsigned char*)s)-1；

相反，若進(jìn)行對(duì)齊填充，由于 Padding 的存在，我們?cè)诓煌南到y(tǒng)中不知道退多少才能獲得flags，并且我們也不能將 sds 的指針指向flags，這樣就無(wú)法兼容 C 語(yǔ)言的函數(shù)了，也不知道前進(jìn)多少才能得到 buf[]。

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

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

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

4.3.2 二進(jìn)制安全

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

通俗地講，C語(yǔ)言中，用'0'表示字符串的結(jié)束，如果字符串本身就有'0'字符，字符串就會(huì)被截?cái)?，即非二進(jìn)制安全；若通過(guò)某種機(jī)制，保證讀寫(xiě)字符串時(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語(yǔ)言開(kāi)發(fā)中使用char *strcat(char *dest,const char *src)方法將src字符串中的內(nèi)容拼接到dest字符串的末尾。

由于C字符串不記錄自身的長(zhǎng)度，所有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++ ) ; /* 無(wú)腦將 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ū)溢出問(wèn)題。

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: 待拼接字符串長(zhǎng)度 */ sds sdscatlen(sds s, const void *t, size_t len) { // 獲取源字符串長(zhǎng)度 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 長(zhǎng)度 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: 新增長(zhǎng)度 */ sds sdsMakeRoomFor(sds s, size_t addlen) { void *sh, *newsh; // sdsavail: s->alloc - s->len, 獲取 SDS 的剩余長(zhǎng)度 size_t avail = sdsavail(s); size_t len, newlen, reqlen; // 根據(jù) flags 獲取 SDS 的類(lèi)型 oldtype char type, oldtype = s[-1] & SDS_TYPE_MASK; int hdrlen; size_t usable; /* Return ASAP if there is enough space left. */ // 剩余空間大于等于新增空間，無(wú)需擴(kuò)容，直接返回源字符串 if (avail >= addlen) return s; // 獲取當(dāng)前長(zhǎng)度 len = sdslen(s); // sh = (char*)s-sdsHdrSize(oldtype); // 新長(zhǎng)度 reqlen = newlen = (len+addlen); // 斷言新長(zhǎng)度比原長(zhǎng)度長(zhǎng)，否則終止執(zhí)行 assert(newlen > len); /* 防止數(shù)據(jù)溢出 */ // SDS_MAX_PREALLOC = 1024*1024, 即1MB if (newlen < SDS_MAX_PREALLOC) // 新增后長(zhǎng)度小于 1MB ，則按新長(zhǎng)度的兩倍擴(kuò)容 newlen *= 2; else // 新增后長(zhǎng)度大于 1MB ，則按新長(zhǎng)度加上 1MB 擴(kuò)容 newlen += SDS_MAX_PREALLOC; // 重新計(jì)算 SDS 的類(lèi)型 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) { // 類(lèi)型沒(méi)變 // 調(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 { // 類(lèi)型變化導(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 類(lèi)型 s[-1] = type; // 設(shè)置長(zhǎng)度 sdssetlen(s, len); } // 獲取 buf 總長(zhǎng)度(待定) usable = usable-hdrlen-1; if (usable > sdsTypeMaxSize(type)) // 若可用空間大于當(dāng)前類(lèi)型支持的最大長(zhǎng)度則截?cái)?br /> usable = sdsTypeMaxSize(type); // 設(shè)置 buf 總長(zhǎng)度 sdssetalloc(s, usable); return s; }

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

擴(kuò)容階段：

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

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

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

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

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

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

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

因?yàn)?SDS 的空間預(yù)分配策略， SDS 字符串在增長(zhǎng)過(guò)程中不會(huì)頻繁的進(jìn)行空間分配。通過(guò)這種分配策略，SDS 將連續(xù)增長(zhǎng)N次字符串所需的內(nèi)存重分配次數(shù)從必定N次降低為最多N次。

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

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

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

/* sdstrim 方法刪除字符串首尾中在 cset 中出現(xiàn)過(guò)的字符 * 比如: * 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)》一書(shū)中針對(duì) sdstrim方法的講解為：刪除字符串中 cset 出現(xiàn)的所有字符，而不是首尾。

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

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

也許各位看官又會(huì)有疑問(wèn)了，這沒(méi)真正釋放空間，是否會(huì)導(dǎo)致內(nèi)存泄漏呢？放心，SDS為我們提供了真正釋放SDS未使用空間的方法sdsRemoveFreeSpace。

sds sdsRemoveFreeSpace(sds s) { void *sh, *newsh; // 獲取類(lèi)型 char type, oldtype = s[-1] & SDS_TYPE_MASK; // 獲取 header 大小 int hdrlen, oldhdrlen = sdsHdrSize(oldtype); // 獲取原字符串長(zhǎng)度 size_t len = sdslen(s); // 獲取可用長(zhǎng)度 size_t avail = sdsavail(s); // 獲取指向頭部的指針 sh = (char*)s-oldhdrlen; /* Return ASAP if there is no space left. */ if (avail == 0) return s; // 查找適合這個(gè)字符串長(zhǎng)度的最優(yōu) SDS 類(lèi)型 type = sdsReqType(len); hdrlen = sdsHdrSize(type); /* 如果類(lèi)型相同，或者至少仍然需要一個(gè)足夠大的類(lèi)型，我們只需 realloc buf即可； * 否則，說(shuō)明變化很大，則手動(dòng)重新分配字符串以使用不同的頭文件類(lèi)型。 */ 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è)置總長(zhǎng)度為len sdssetalloc(s, len); return s; }

4.4 SDS 最長(zhǎng)多少？

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

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

任何細(xì)節(jié)在源碼中都能發(fā)現(xiàn)，在_sdsnewlen方法創(chuàng)建 SDS 中都會(huì)調(diào)用sdsTypeMaxSize方法獲取每種類(lèi)型所能創(chuàng)建的最大buf長(zhǎng)度，不難發(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 通過(guò)sdsnewlen方法創(chuàng)建 SDS。在方法中會(huì)根據(jù)字符串初始化長(zhǎng)度選擇合適的類(lèi)型。

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) { void *sh; sds s; // 根據(jù)初始化長(zhǎng)度判斷 SDS 的類(lèi)型 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ì)不同類(lèi)型的 SDS 可分配空間進(jìn)行截?cái)?br /> if (usable > sdsTypeMaxSize(type)) usable = sdsTypeMaxSize(type); switch(type) { case SDS_TYPE_5: { *fp = type | (initlen << SDS_TYPE_BITS); 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; }

通過(guò)sdsnewlen方法我們可以獲得以下信息：

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

釋放SDS

為了優(yōu)化性能，SDS 提供了不直接釋放內(nèi)存，而是通過(guò)重置len達(dá)到清空 SDS 目的的方法——sdsclear。改方法僅僅將 SDS 的len歸零，而buf的空間并為真正被清空，新的數(shù)據(jù)可以復(fù)寫(xiě)，而不用重新申請(qǐng)內(nèi)存。

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

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

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

我是敖丙，你知道的越多，你不知道的越多，感謝各位人才的：點(diǎn)贊、收藏和評(píng)論，我們下期見(jiàn)！

文章持續(xù)更新，關(guān)注后回復(fù)【資料】有我準(zhǔn)備的一線大廠面試資料和簡(jiǎn)歷模板，有大廠面試完整考點(diǎn)。

總結(jié)

以上是生活随笔為你收集整理的让我聊聊sds是什么(sds是什么意思)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

让我
sds

上一篇： UClient客户端安装说明
下一篇：如何查看曾经连接过的WiFi密码(以前连