開場(chǎng)白
作為redis的使用者渐裸，我們最常用的操作可能就是set了摊腋，而最常用的數(shù)據(jù)結(jié)構(gòu)則是string了昙沦，我們常常會(huì)使用命令:
127.0.0.1:6379> set key value
這個(gè)命令中，key和value都被保存到一個(gè)字符串中舍杜。需要注意的是新娜，這個(gè)字符串并非C語(yǔ)言的字符串結(jié)構(gòu)，而是redis自己實(shí)現(xiàn)的一個(gè)名為sds的數(shù)據(jù)結(jié)構(gòu)
SDS的定義
我們翻到redis3.0的源碼既绩，找到src/sds.h,先看看這個(gè)sds的結(jié)構(gòu)體定義：
/*
* 保存字符串對(duì)象的結(jié)構(gòu)
*/
struct sdshdr {
// buf 中已占用空間的長(zhǎng)度
int len;
// buf 中剩余可用空間的長(zhǎng)度
int free;
// 數(shù)據(jù)空間
char buf[];
};
- 字段
free：表示可分配的空間的字節(jié)長(zhǎng)度 - 字段
len：表示已占用空間的字節(jié)長(zhǎng)度 - 字段
buf：表示裝載實(shí)際字符串的字符數(shù)組
舉一個(gè)最簡(jiǎn)單的例子，比如Redis這個(gè)字符串还惠，在sds的保存則是這樣的：
為什么要在后面加上這個(gè)\0呢饲握？這么設(shè)計(jì)的目標(biāo)是為了遵循C語(yǔ)言字符結(jié)尾的慣例，同時(shí)能夠兼容一部分C語(yǔ)言字符串操作庫(kù)函數(shù)蚕键，比如strlen救欧。同時(shí)這個(gè)\0是不會(huì)記錄進(jìn)去len字段的。
使用SDS的好處
1.有效提升處理長(zhǎng)字符串的性能
C語(yǔ)言的字符串類型锣光，計(jì)算長(zhǎng)度是必須要遍歷字符的笆怠，也就是如果長(zhǎng)度為5的字符串，那么計(jì)算長(zhǎng)度必須要遍歷五次才能得出結(jié)果誊爹，計(jì)算復(fù)雜度是O(N)蹬刷。如果使用了sds的話，可以在分配字符串的時(shí)候就直接把長(zhǎng)度記錄在len字段频丘，那么這個(gè)計(jì)算復(fù)雜度將會(huì)是O(1)办成，這么做能夠解決redis處理大型字符串長(zhǎng)度的性能瓶頸問(wèn)題。
2.防止緩沖區(qū)溢出搂漠，優(yōu)化內(nèi)存分配
普通的C語(yǔ)言字符串會(huì)存在緩沖區(qū)溢出的問(wèn)題迂卢，舉個(gè)最簡(jiǎn)單的例子，如字符串s1是redis，字符串s2是mongodb而克，并假設(shè)他們?cè)趦?nèi)存中是緊緊相鄰的靶壮。假如一個(gè)粗心的程序員沒(méi)有為s1去分配更多空間的前提下就調(diào)用了strcat進(jìn)行了字符串拼接，如strcat(s1, "cluster")员萍，那么這個(gè)s1就會(huì)溢出并且可能擦寫s2的內(nèi)存亮钦，就會(huì)出現(xiàn)一些很坑爹但又難以發(fā)現(xiàn)的bug了。但是使用sds就能規(guī)避這個(gè)問(wèn)題充活，比如src/sds.c文件中有一個(gè)函數(shù)叫sdscat,我們看一下代碼
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
sds sdscatlen(sds s, const void *t, size_t len) {
struct sdshdr *sh;
// 原有字符串長(zhǎng)度
size_t curlen = sdslen(s);
// 擴(kuò)展 sds 空間
// T = O(N)
s = sdsMakeRoomFor(s,len);
// 內(nèi)存不足蜂莉？直接返回
if (s == NULL) return NULL;
// 復(fù)制 t 中的內(nèi)容到字符串后部
// T = O(N)
sh = (void*) (s-(sizeof(struct sdshdr)));
memcpy(s+curlen, t, len);
// 更新屬性
sh->len = curlen+len;
sh->free = sh->free-len;
// 添加新結(jié)尾符號(hào)
s[curlen+len] = '\0';
// 返回新 sds
return s;
}
// 著重看這個(gè)函數(shù)
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
// 獲取 s 目前的空余空間長(zhǎng)度
size_t free = sdsavail(s);
size_t len, newlen;
// s 目前的空余空間已經(jīng)足夠，無(wú)須再進(jìn)行擴(kuò)展混卵，直接返回
if (free >= addlen) return s;
// 獲取 s 目前已占用空間的長(zhǎng)度
len = sdslen(s);
sh = (void*) (s-(sizeof(struct sdshdr)));
// s 最少需要的長(zhǎng)度
newlen = (len+addlen);
// 根據(jù)新長(zhǎng)度映穗，為 s 分配新空間所需的大小
if (newlen < SDS_MAX_PREALLOC)
// 如果新長(zhǎng)度小于 SDS_MAX_PREALLOC
// 那么為它分配兩倍于所需長(zhǎng)度的空間
newlen *= 2;
else
// 否則，分配長(zhǎng)度為目前長(zhǎng)度加上 SDS_MAX_PREALLOC
newlen += SDS_MAX_PREALLOC;
// T = O(N)
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
// 內(nèi)存不足幕随，分配失敗蚁滋，返回
if (newsh == NULL) return NULL;
// 更新 sds 的空余長(zhǎng)度
newsh->free = newlen - len;
// 返回 sds
return newsh->buf;
}
我們著重看看sdsMakeRoomFor函數(shù)，它展示了redis的sds是如何分配內(nèi)存的赘淮，還是舉個(gè)栗子：我們有字符串s1="redis"辕录，我們調(diào)用sdscat(s1, "cluster")，那么s1會(huì)變?yōu)?code>redis cluster梢卸，因?yàn)樵瓉?lái)的s1的len字段只有5字節(jié)走诞，因此連接cluster需要進(jìn)行內(nèi)存擴(kuò)展操作，可以從代碼看到蛤高，如果s1的free的長(zhǎng)度大于等于cluster的長(zhǎng)度蚣旱，那么會(huì)把free這部分讓出來(lái)進(jìn)行分配給cluster字符串，但如果不夠長(zhǎng)又會(huì)產(chǎn)生兩種分配策略：
- 如果連接后新的字符串的長(zhǎng)度尚未超過(guò)宏定義
SDS_MAX_PREALLOC(默認(rèn)是1MB)戴陡，那么會(huì)分配兩倍于新字符串的長(zhǎng)度塞绿。比如連接后的字符串s1是redis cluster，長(zhǎng)度即是13恤批，那么會(huì)多分配出13個(gè)字節(jié)异吻，并把長(zhǎng)度保存在free字段，那么最終擴(kuò)容后buf的空間就是13 + 13 + 1 = 27個(gè)字節(jié)喜庞。 - 如果連接后的字符串長(zhǎng)度超過(guò)宏定義
SDS_MAX_PREALLOC（默認(rèn)是1MB）诀浪，那么會(huì)比新字符串長(zhǎng)度分配多SDS_MAX_PREALLOC（默認(rèn)是1MB）的內(nèi)存。比如連接后的字符串s1長(zhǎng)度是10MB赋荆，那么buf擴(kuò)容分配后的空間就是30MB + 1MB + 1Byte笋妥。
除此之外，redis的sds api也有惰性釋放的機(jī)制窄潭。假如一個(gè)字符串需要被裁減春宣，比如redis cluster變?yōu)?code>redis酵颁，sds的api不會(huì)馬上把cluster這7個(gè)字節(jié)空間馬上釋放掉，而是會(huì)繼續(xù)保留月帝，并記錄在free字段中躏惋，也就是free=7，這么做是為了日后如果redis這個(gè)字符串要增長(zhǎng)的時(shí)候就不用去重新分配內(nèi)存了嚷辅。當(dāng)然簿姨，如果你真的覺(jué)得這部分空間用不著了，也可以通過(guò)sdsRemoveFreeSpace這個(gè)函數(shù)去釋放掉這部分free的空間簸搞。
3.保證二進(jìn)制安全
C語(yǔ)言字符串必須符合某種編碼扁位，并且除了字符串末尾之外，字符串里面不能包含空字符串趁俊，否則會(huì)認(rèn)為是結(jié)尾了域仇，因此也導(dǎo)致C語(yǔ)言字符串沒(méi)辦法保存、圖片寺擂、視頻暇务、壓縮文件等二進(jìn)制數(shù)據(jù)。
redis的sds使用了字符數(shù)組作為字符串的保存結(jié)構(gòu)的好處就顯現(xiàn)出來(lái)了怔软，正因?yàn)槭亲址麛?shù)組垦细，那么可以用來(lái)保存任何的二進(jìn)制數(shù)據(jù)，并且保證讀入數(shù)據(jù)是什么挡逼，讀出的數(shù)據(jù)就是什么括改。
以上就是redis簡(jiǎn)單動(dòng)態(tài)字符串的特點(diǎn)和優(yōu)勢(shì)的總結(jié)，后面會(huì)繼續(xù)redis的其他數(shù)據(jù)結(jié)構(gòu)挚瘟，敬請(qǐng)期待叹谁！
文章參考自：<<Redis設(shè)計(jì)與實(shí)現(xiàn)>> 第二版
