深挖 Redis 6.0 源碼—— SDS
本文精選自 Doocs 開(kāi)源社區(qū)旗下“源碼獵人”項(xiàng)目，作者楊立濱。
項(xiàng)目將會(huì)持續(xù)更新，歡迎 Star 關(guān)注。
項(xiàng)目地址：https://github.com/doocs/source-code-hunter
SDS（Simple Dynamic Strings, 簡(jiǎn)單動(dòng)態(tài)字符串）是 Redis 的一種基本數(shù)據(jù)結(jié)構(gòu)，主要是用于存儲(chǔ)字符串和整數(shù)。?這篇文章里，我們就來(lái)探討一下 Redis SDS 這種數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)原理。
學(xué)習(xí)之前，首先我們要明確，Redis 是一個(gè)使用 C 語(yǔ)言編寫(xiě)的鍵值對(duì)存儲(chǔ)系統(tǒng)。
前置思考
我們首先考慮一個(gè)問(wèn)題，如何實(shí)現(xiàn)一個(gè)二進(jìn)制安全的字符串？
在 C 語(yǔ)言中，\0?表示字符串結(jié)束，如果字符串中本身就包含?\0?字符，那么字符串就會(huì)在?\0?處被截?cái)?，即非二進(jìn)制安全；若通過(guò)使用一個(gè) len 屬性，來(lái)判斷字符串是否結(jié)束，就可以保證讀寫(xiě)字符串時(shí)不受到?\0?的影響，則是二進(jìn)制安全。同時(shí) len 屬性也能保證在 O(1) 時(shí)間內(nèi)獲取字符串的長(zhǎng)度。
Redis 3.2 以前的 SDS 實(shí)現(xiàn)
在 Redis 3.2 版本以前，SDS 的結(jié)構(gòu)如下：
struct sdshdr {unsigned int len;unsigned int free;char buf[];};
其中，buf 表示數(shù)據(jù)空間，用于存儲(chǔ)字符串；len 表示 buf 中已占用的字節(jié)數(shù)，也即字符串長(zhǎng)度；free 表示 buf 中剩余可用字節(jié)數(shù)。
字段 len 和 free 各占 4 字節(jié)，緊接著存放字符串。
這樣做有以下幾個(gè)好處：
?用單獨(dú)的變量 len 和 free，可以方便地獲取字符串長(zhǎng)度和剩余空間；?內(nèi)容存儲(chǔ)在動(dòng)態(tài)數(shù)組 buf 中，SDS 對(duì)上層暴露的指針指向 buf，而不是指向結(jié)構(gòu)體 SDS。因此，上層可以像讀取 C 字符串一樣讀取 SDS 的內(nèi)容，兼容 C 語(yǔ)言處理字符串的各種函數(shù)，同時(shí)也能通過(guò) buf 地址的偏移，方便地獲取其他變量；?讀寫(xiě)字符串不依賴(lài)于?\0，保證二進(jìn)制安全。
但其實(shí)以上的設(shè)計(jì)是存在一些問(wèn)題的，對(duì)于不同長(zhǎng)度的字符串，是否有必要使用 len 和 free 這 2 個(gè) 4 字節(jié)的變量？4 字節(jié)的 len，可表示的字符串長(zhǎng)度為?2^32，而在實(shí)際應(yīng)用中，存放于 Redis 中的字符串往往沒(méi)有這么長(zhǎng)，因此，空間的使用上能否進(jìn)一步壓縮？
那么接下來(lái)，我們就來(lái)看看最新的 Redis 是如何根據(jù)字符串的長(zhǎng)度，使用不同的數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)的。
Redis SDS 最新實(shí)現(xiàn)
在 Redis 3.2 版本之后（v3.2 - v6.0），Redis 將 SDS 劃分為 5 種類(lèi)型：
?sdshdr5：長(zhǎng)度小于 1 字節(jié)?sdshdr8：長(zhǎng)度 1 字節(jié)?sdshdr16：長(zhǎng)度 2 字節(jié)?sdshdr32：長(zhǎng)度 4 字節(jié)?sdshdr64：長(zhǎng)度 8 字節(jié)
Redis 增加了一個(gè) flags 字段來(lái)標(biāo)識(shí)類(lèi)型，用一個(gè)字節(jié)(8 位)來(lái)存儲(chǔ)。
其中：前 3 位表示字符串的類(lèi)型；剩余 5 位，可以用來(lái)存儲(chǔ)長(zhǎng)度小于 32 的短字符串。
struct __attribute__ ((__packed__)) sdshdr5 {unsigned char flags; /* 前3位存儲(chǔ)類(lèi)型，后5位存儲(chǔ)長(zhǎng)度 */char buf[]; /* 動(dòng)態(tài)數(shù)組，存放字符串 */};
而對(duì)于長(zhǎng)度大于 31 的字符串，僅僅靠 flags 的后 5 位來(lái)存儲(chǔ)長(zhǎng)度明顯是不夠的，需要用另外的變量來(lái)存儲(chǔ)。sdshdr8、sdshdr16、sdshdr32、sdshdr64 的數(shù)據(jù)結(jié)構(gòu)定義如下，其中 len 表示已使用的長(zhǎng)度，alloc 表示總長(zhǎng)度，buf 存儲(chǔ)實(shí)際內(nèi)容，而 flags 的前 3 位依然存儲(chǔ)類(lèi)型，后 5 位則預(yù)留。
struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; /* 已使用長(zhǎng)度，1字節(jié) */uint8_t alloc; /* 總長(zhǎng)度，1字節(jié) */unsigned char flags; /* 前3位存儲(chǔ)類(lèi)型，后5位預(yù)留 */char buf[];};struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len; /* 已使用長(zhǎng)度，2字節(jié) */uint16_t alloc; /* 總長(zhǎng)度，2字節(jié) */unsigned char flags; /* 前3位存儲(chǔ)類(lèi)型，后5位預(yù)留 */char buf[];};struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len; /* 已使用長(zhǎng)度，4字節(jié) */uint32_t alloc; /* 總長(zhǎng)度，4字節(jié) */unsigned char flags; /* 前3位存儲(chǔ)類(lèi)型，后5位預(yù)留 */char buf[];};struct __attribute__ ((__packed__)) sdshdr64 {uint64_t len; /* 已使用長(zhǎng)度，8字節(jié) */uint64_t alloc; /* 總長(zhǎng)度，8字節(jié) */unsigned char flags; /* 前3位存儲(chǔ)類(lèi)型，后5位預(yù)留 */char buf[];};
注意，一般情況下，結(jié)構(gòu)體會(huì)按照所有變量大小的最小公倍數(shù)做字節(jié)對(duì)齊，而用?packed?修飾后，結(jié)構(gòu)體則變?yōu)?1 字節(jié)對(duì)齊。這樣做的好處有二：一是節(jié)省內(nèi)存，比如 sdshdr32 可節(jié)約 3 個(gè)字節(jié)；二是?SDS 返回給上層的是指向 buf 的指針，此時(shí)按 1 字節(jié)對(duì)齊，所以可在創(chuàng)建 SDS 后，通過(guò)?(char*)sh+hdrlen?得到 buf 指針地址，也可以通過(guò)?buf[-1]?找到 flags。
以上，Redis 根據(jù)字符串長(zhǎng)度的不同，選擇對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)。接下來(lái)，我們就來(lái)看看 Redis 字符串的相關(guān) API 實(shí)現(xiàn)。
SDS API 實(shí)現(xiàn)
1. 創(chuàng)建字符串
sds sdsnewlen(const void *init, size_t initlen) {void *sh;sds s;// 根據(jù)字符串長(zhǎng)度計(jì)算相應(yīng)類(lèi)型char type = sdsReqType(initlen);// 如果創(chuàng)建的是""字符串，強(qiáng)轉(zhuǎn)為SDS_TYPE_8if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;// 根據(jù)類(lèi)型計(jì)算頭部所需長(zhǎng)度（頭部包含 len、alloc、flags）int hdrlen = sdsHdrSize(type);// 指向flags的指針unsigned char *fp;// 創(chuàng)建字符串，+1是因?yàn)?`\0` 結(jié)束符sh = s_malloc(hdrlen+initlen+1);if (sh == NULL) return NULL;if (init==SDS_NOINIT)init = NULL;else if (!init)memset(sh, 0, hdrlen+initlen+1);// s指向bufs = (char*)sh+hdrlen;// s減1得到flagsfp = ((unsigned char*)s)-1;...// 在s末尾添加\0結(jié)束符s[initlen] = '\0';// 返回指向buf的指針sreturn s;}
創(chuàng)建 SDS 的大致流程是這樣的：首先根據(jù)字符串長(zhǎng)度計(jì)算得到 type，根據(jù) type 計(jì)算頭部所需長(zhǎng)度，然后動(dòng)態(tài)分配內(nèi)存空間。
注意：
1.創(chuàng)建空字符串時(shí)，SDS_TYPE_5?被強(qiáng)制轉(zhuǎn)換為?SDS_TYPE_8（原因是創(chuàng)建空字符串后，內(nèi)容可能會(huì)頻繁更新而引發(fā)擴(kuò)容操作，故直接創(chuàng)建為 sdshdr8）2.長(zhǎng)度計(jì)算有?+1?操作，因?yàn)榻Y(jié)束符?\0?會(huì)占用一個(gè)長(zhǎng)度的空間。3.返回的是指向 buf 的指針 s。
2. 清空字符串
SDS 提供了兩種清空字符串的方法。
一種是通過(guò) s 偏移得到結(jié)構(gòu)體的地址，然后調(diào)用?s_free?直接釋放內(nèi)存。
void sdsfree(sds s) {if (s == NULL) return;// s減去頭部的大小得到結(jié)構(gòu)體的地址s_free((char*)s-sdsHdrSize(s[-1]));}
另一種是通過(guò)重置 len 屬性值而達(dá)到清空字符串的目的，本質(zhì)上 buf 并沒(méi)有被真正清除，新的數(shù)據(jù)會(huì)直接覆蓋 buf 中原有的數(shù)據(jù)，無(wú)需申請(qǐng)新的內(nèi)存空間。
void sdsclear(sds s) {// 將len屬性置為0sdssetlen(s, 0);s[0] = '\0';}
3. 拼接字符串
SDS 拼接字符串的實(shí)現(xiàn)如下：
sds sdscatsds(sds s, const sds t) {return sdscatlen(s, t, sdslen(t));}
可以看到?sdscatsds?內(nèi)部調(diào)用的是?sdscatlen。
而?sdscatlen?內(nèi)部的實(shí)現(xiàn)相對(duì)復(fù)雜一些，由于拼接字符串可能涉及 SDS 的擴(kuò)容，因此?sdscatlen?內(nèi)部調(diào)用?sdsMakeRoomFor?對(duì)拼接的字符串做檢查：若無(wú)需擴(kuò)容，直接返回 s；若需要擴(kuò)容，則返回?cái)U(kuò)容好的新字符串 s。
sds sdscatlen(sds s, const void *t, size_t len) {// 計(jì)算當(dāng)前字符串長(zhǎng)度size_t curlen = sdslen(s);// 確保s的剩余空間足以拼接上ts = sdsMakeRoomFor(s,len);if (s == NULL) return NULL;// 拼接s、tmemcpy(s+curlen, t, len);// 更新s的len屬性sdssetlen(s, curlen+len);// s末尾添加\0結(jié)束符s[curlen+len] = '\0';return s;}
SDS 的擴(kuò)容策略是這樣的：
1.若 SDS 中剩余空閑長(zhǎng)度 avail 大于或等于新增內(nèi)容的長(zhǎng)度 addlen，無(wú)需擴(kuò)容。2.若 SDS 中剩余空閑長(zhǎng)度 avail 小于或等于 addlen，則分情況討論：新增后總長(zhǎng)度?len+addlen < 1MB?的，按新長(zhǎng)度的 2 倍擴(kuò)容；新增后總長(zhǎng)度?len+addlen >= 1MB?的，按新長(zhǎng)度加上?1MB?擴(kuò)容。
sds sdsMakeRoomFor(sds s, size_t addlen) {void *sh, *newsh;// 當(dāng)前剩余長(zhǎng)度size_t avail = sdsavail(s);size_t len, newlen;char type, oldtype = s[-1] & SDS_TYPE_MASK;int hdrlen;/* 剩余長(zhǎng)度>=新增字符串長(zhǎng)度，直接返回 */if (avail >= addlen) return s;// 計(jì)算當(dāng)前字符串長(zhǎng)度lenlen = sdslen(s);sh = (char*)s-sdsHdrSize(oldtype);// 計(jì)算新長(zhǎng)度newlen = (len+addlen);// 新長(zhǎng)度<1MB，按新長(zhǎng)度的2倍擴(kuò)容if (newlen < SDS_MAX_PREALLOC)newlen *= 2;// 否則按新長(zhǎng)度+1MB擴(kuò)容elsenewlen += SDS_MAX_PREALLOC;// 計(jì)算新長(zhǎng)度所屬類(lèi)型type = sdsReqType(newlen);/* type5不支持?jǐn)U容，強(qiáng)轉(zhuǎn)為type8 */if (type == SDS_TYPE_5) type = SDS_TYPE_8;hdrlen = sdsHdrSize(type);if (oldtype==type) {// 類(lèi)型沒(méi)變，直接通過(guò)realloc擴(kuò)大動(dòng)態(tài)數(shù)組即可。newsh = s_realloc(sh, hdrlen+newlen+1);if (newsh == NULL) return NULL;s = (char*)newsh+hdrlen;} else {// 類(lèi)型改變了，則說(shuō)明頭部長(zhǎng)度也發(fā)生了變化，不進(jìn)行realloc操作，而是直接重新開(kāi)辟內(nèi)存newsh = s_malloc(hdrlen+newlen+1);if (newsh == NULL) return NULL;// 原內(nèi)存拷貝到新的內(nèi)存地址上memcpy((char*)newsh+hdrlen, s, len+1);// 釋放原先空間s_free(sh);s = (char*)newsh+hdrlen;// 為flags賦值s[-1] = type;// 為len屬性賦值sdssetlen(s, len);}// 為alloc屬性賦值sdssetalloc(s, newlen);return s;}
總結(jié)
1.SDS 返回的是指向 buf 的指針，兼容了 C 語(yǔ)言操作字符串的函數(shù)，讀取內(nèi)容時(shí)，通過(guò) len 屬性來(lái)限制讀取的長(zhǎng)度，不受?\0?影響，從而保證二進(jìn)制安全；2.Redis 根據(jù)字符串長(zhǎng)度的不同，定義了多種數(shù)據(jù)結(jié)構(gòu)，包括：sdshdr5/sdshdr8/sdshdr16/sdshdr32/sdshdr64。3.SDS 在設(shè)計(jì)字符串修改出會(huì)調(diào)用?sdsMakeRoomFor?函數(shù)進(jìn)行檢查，根據(jù)不同情況進(jìn)行擴(kuò)容。
全文完！
希望本文對(duì)大家有所幫助。如果感覺(jué)本文有幫助，有勞轉(zhuǎn)發(fā)或點(diǎn)一下“在看”！讓更多人收獲知識(shí)！
長(zhǎng)按識(shí)別下圖二維碼，關(guān)注公眾號(hào)「Doocs 開(kāi)源社區(qū)」，第一時(shí)間跟你們分享好玩、實(shí)用的技術(shù)文章與業(yè)內(nèi)最新資訊。