摘要：本文主要介紹的數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單動(dòng)態(tài)字符串簡(jiǎn)稱。遵守字符串以空字符串結(jié)尾的慣例，保存的空字符串一個(gè)字節(jié)空間不計(jì)算在的屬性里面。添加空字符串到字符串末尾等操作，都是由函數(shù)自動(dòng)完成的，所以這個(gè)空字符對(duì)于使用者來說完全是透明的。

Redis是用ANSI C語言編寫的，它是一個(gè)高性能的key-value數(shù)據(jù)庫，它可以作用在數(shù)據(jù)庫、緩存和消息中間件。其中 Redis 鍵值對(duì)中的鍵都是 string 類型，而鍵值對(duì)中的值也是有 string 類型，在 Redis 中 string 類型運(yùn)用還是很廣泛的。本文主要介紹 string 的數(shù)據(jù)結(jié)構(gòu)—— 簡(jiǎn)單動(dòng)態(tài)字符串（Simple Dynamic String） 簡(jiǎn)稱sds。

sds 實(shí)現(xiàn)

sds 的數(shù)據(jù)結(jié)構(gòu):

struct sdshdr {     //buf 已占用的長(zhǎng)度     int len;     // buf 剩余的可用的長(zhǎng)度     int free;        // 保存字符串?dāng)?shù)據(jù)的地方     char buf[]; }

結(jié)構(gòu) sdshdr 保存了 len、free 和 buf 三個(gè)屬性，分別記錄字符的已使用的長(zhǎng)度，未使用的長(zhǎng)度，以及實(shí)際保存字符串的數(shù)組。
以下是一個(gè)新建的，保存 hello world 字符串的 sdshdr 結(jié)構(gòu)：

struct sdshdr {    len = 5;    free = 0;    buf = "hello/0"; }

• free 屬性值為0，表示這個(gè)sds沒有分配未使用的空間。
• len 屬性值為5，表示這個(gè)sds保存了一個(gè)五字節(jié)長(zhǎng)的字符串。
• buf 屬性是一個(gè) char 類型的數(shù)組，數(shù)組的前五個(gè)字節(jié)分別保存了 h、e、l、l、o 五個(gè)字符，而最后一個(gè)字節(jié)保存了空字符/0。

sds 遵守 C 字符串以空字符串結(jié)尾的慣例，保存的空字符串一個(gè)字節(jié)空間不計(jì)算在 sds 的 len 屬性里面。添加空字符串到字符串末尾等操作，都是由 sds 函數(shù)自動(dòng)完成的，所以這個(gè)空字符對(duì)于使用者來說完全是透明的。

通過 len 屬性，可以實(shí)現(xiàn)時(shí)間復(fù)雜度 O(1) 的長(zhǎng)度計(jì)算。另外通過對(duì) buf 分配一些額外的空間，并使用 free 記錄未使用空間的長(zhǎng)度，sdshdr 可以減少內(nèi)存的重新分配。這是 sds 相對(duì) c 字符串的一個(gè)優(yōu)勢(shì)。

為何 Redis 不用 C 語言表示字符串

Redis 是使用 C 語言開發(fā)的，而在使用最多的字符串上，Redis 沒有使用 C 語言傳統(tǒng)的字符串表示，而且使用自己構(gòu)建的簡(jiǎn)單動(dòng)態(tài)字符串（sds）。
在 C 語言中，字符串可以用一個(gè) /0 結(jié)尾的 char 數(shù)組表示。比如 hello world 在 C 語言中就可以表示為"hello world/0"。數(shù)組一般初始化以后長(zhǎng)度就已經(jīng)固定了，不能支持字符串追加append和長(zhǎng)度計(jì)算操作：

• 每次計(jì)算字符串長(zhǎng)度都要遍歷一遍數(shù)組，所以時(shí)間復(fù)雜度是O(N)
• 對(duì)字符串每次進(jìn)行追加操作，需要對(duì)字符串進(jìn)行一次內(nèi)存分配

sds 優(yōu)化追加字符操作

Redis 作為數(shù)據(jù)庫，對(duì)于查詢速度要求嚴(yán)格，數(shù)據(jù)修改也比較頻繁，如果每次修改字符串都需要執(zhí)行一次內(nèi)存分配的話，都會(huì)占用大量的時(shí)間。所以 Redis 選擇了 sds 而不是 C 字符串，sds 可以減少追加字符的內(nèi)存分配。通過舉例來說明，執(zhí)行以下操作時(shí)，sds 內(nèi)部的變化：

redis> set msg "hello world"OKredis> append msg " again"(integer)18redis> get msg"hello world again"

首先 set 命令創(chuàng)建并保存hello world 到一個(gè) sdshdr 中，這個(gè) sdshdr 的值如下：

struct sdshdr {     len = 11;     free = 0;     buf = "hello world/0";}

當(dāng)執(zhí)行 append 命令時(shí)，相對(duì)應(yīng)的 sdshdr 被更新，字符串 " again" 會(huì)被追加到原來的 "hello world" 之后：

struct sdshdr {     len = 17;     free = 17;     buf = "hello world again/0                ";}

當(dāng)調(diào)用 set 命令創(chuàng)建 sdshdr 時(shí)，Redis 沒有給 sdshdr 分配多余的空間，free 屬性為0。而在執(zhí)行 append 操作之后，Redis 為 buf 分配了多于所需空間一倍的大小。

在執(zhí)行 append 命令之后，保存 "hello world again" 共需要17 + 1 個(gè)字節(jié)，但是程序?yàn)?sdshdr 分配了 17 + 17 + 1 = 35 個(gè)字節(jié)，而后續(xù)如果在對(duì) sdshdr 進(jìn)行追加操作，只要追加的長(zhǎng)度不超過 free 屬性值，那么就不需要對(duì) buf 進(jìn)行內(nèi)存重分配。

比如執(zhí)行以后命令并不會(huì)引起 buf 的內(nèi)存重分配，因?yàn)樾伦芳拥淖址L(zhǎng)度小于17：

redis> append msg  " again"(integer) 23

對(duì)應(yīng)的 sdshdr 結(jié)構(gòu)如下：

struct sdshdr {     len = 23;     free = 11;     buf = "hello world again again/0               ";}

redis 內(nèi)存分配可以查看源碼 sds.s/sdsMakeRoomFor，sdsMakeRoomFor 函數(shù)描述了內(nèi)存分配的策略，下面的該函數(shù)的偽代碼：

// sdshdr:追加前的字符// addlen：追加字符串sds sdsMakeRoomFor(sdshdr, addlen) {       // 多余空間大于追加空間，無序再分配內(nèi)存，直接返回    if (free >= addlen) return s;    // 計(jì)算新字符的長(zhǎng)度    newlen = (len+addlen);    // 如果新字符的長(zhǎng)度小于 SDS_MAX_PREALLOC，就分配兩倍新字符空間  //  如果新字符的長(zhǎng)度大于 SDS_MAX_PREALLOC，就分配新字符空間 + SDS_MAX_PREALLOC 空間    if (newlen < SDS_MAX_PREALLOC)        newlen *= 2;    else        newlen += SDS_MAX_PREALLOC;    // 分配內(nèi)存    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);    // 更新 free 屬性    newsh.free = newlen - len;    return newsh;}

而對(duì)于字符的縮短操作，Redis 保存縮短后的字符串，此時(shí)并不會(huì)進(jìn)行內(nèi)存重分配，而是使用 free 屬性記錄縮短的字符長(zhǎng)度。

總結(jié)

Redis 的 string 類型為何使用sds而不是 C 字符串，因?yàn)閟ds有兩點(diǎn)優(yōu)勢(shì)：

• 計(jì)算字符長(zhǎng)度，C 字符串復(fù)雜度O（n），而 sds 復(fù)雜度為 O（1）
• 字符追加操作，C 字符串每次都需要對(duì)內(nèi)存進(jìn)行重分配，而 sds 每次會(huì)進(jìn)行動(dòng)態(tài)擴(kuò)容，當(dāng)添加字符小于空閑字符時(shí)，不會(huì)對(duì)內(nèi)容進(jìn)行分配，減少系統(tǒng)等待時(shí)間

參考

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

如果覺得文章對(duì)你有幫助的話，請(qǐng)點(diǎn)個(gè)推薦吧!