Redis簡單動(dòng)態(tài)字符串

簡單動(dòng)態(tài)字符串

Sds （Simple Dynamic String，簡單動(dòng)態(tài)字符串）是 Redis 底層所使用的字符串表示，幾乎所有的 Redis 模塊中都用了 sds。

本章將對 sds 的實(shí)現(xiàn)、性能和功能等方面進(jìn)行介紹，并說明 Redis 使用 sds 而不是傳統(tǒng) C 字符串的原因。

sds 的用途

Sds 在 Redis 中的主要作用有以下兩個(gè)：

1. 實(shí)現(xiàn)字符串對象（StringObject）；
2. 在 Redis 程序內(nèi)部用作 char* 類型的替代品；

以下兩個(gè)小節(jié)分別對這兩種用途進(jìn)行介紹。

實(shí)現(xiàn)字符串對象

Redis 是一個(gè)鍵值對數(shù)據(jù)庫（key-value DB），數(shù)據(jù)庫的值可以是字符串、集合、列表等多種類型的對象，而數(shù)據(jù)庫的鍵則總是字符串對象。

對于那些包含字符串值的字符串對象來說，每個(gè)字符串對象都包含一個(gè) sds 值。

Note

“包含字符串值的字符串對象”，這種說法初聽上去可能會(huì)有點(diǎn)奇怪，但是在 Redis 中，一個(gè)字符串對象除了可以保存字符串值之外，還可以保存 long 類型的值，所以為了嚴(yán)謹(jǐn)起見，這里需要強(qiáng)調(diào)一下：當(dāng)字符串對象保存的是字符串時(shí)，它包含的才是 sds 值，否則的話，它就是一個(gè) long 類型的值。

舉個(gè)例子，以下命令創(chuàng)建了一個(gè)新的數(shù)據(jù)庫鍵值對，這個(gè)鍵值對的鍵和值都是字符串對象，它們都包含一個(gè) sds 值：

redis> SET book "Mastering C++ in 21 days"
OK

redis> GET book
"Mastering C++ in 21 days"

以下命令創(chuàng)建了另一個(gè)鍵值對，它的鍵是字符串對象，而值則是一個(gè)集合對象：

redis> SADD nosql "Redis" "MongoDB" "Neo4j"
(integer) 3

redis> SMEMBERS nosql
1) "Neo4j"
2) "Redis"
3) "MongoDB"

用 sds 取代 C 默認(rèn)的 char* 類型

因?yàn)?char* 類型的功能單一，抽象層次低，并且不能高效地支持一些 Redis 常用的操作（比如追加操作和長度計(jì)算操作），所以在 Redis 程序內(nèi)部，絕大部分情況下都會(huì)使用 sds 而不是 char* 來表示字符串。

性能問題在稍后介紹 sds 定義的時(shí)候就會(huì)說到，因?yàn)槲覀冞€沒有了解過 Redis 的其他功能模塊，所以也沒辦法詳細(xì)地舉例說那里用到了 sds ，不過在后面的章節(jié)中，我們會(huì)經(jīng)?？吹狡渌K（幾乎每一個(gè)）都用到了 sds 類型值。

目前來說，只要記住這個(gè)事實(shí)即可：在 Redis 中，客戶端傳入服務(wù)器的協(xié)議內(nèi)容、aof 緩存、返回給客戶端的回復(fù)，等等，這些重要的內(nèi)容都是由 sds 類型來保存的。

Redis 中的字符串

在 C 語言中，字符串可以用一個(gè) \0 結(jié)尾的 char 數(shù)組來表示。

比如說， hello world 在 C 語言中就可以表示為 "hello world\0" 。

這種簡單的字符串表示，在大多數(shù)情況下都能滿足要求，但是，它并不能高效地支持長度計(jì)算和追加（append）這兩種操作：

• 每次計(jì)算字符串長度（strlen(s)）的復(fù)雜度為 (\theta(N)) 。
• 對字符串進(jìn)行 N 次追加，必定需要對字符串進(jìn)行 N 次內(nèi)存重分配（realloc）。

在 Redis 內(nèi)部，字符串的追加和長度計(jì)算很常見，而 APPEND [http://redis.readthedocs.org/en/latest/string/append.html#append] 和 STRLEN [http://redis.readthedocs.org/en/latest/string/strlen.html#strlen] 更是這兩種操作，在 Redis 命令中的直接映射，這兩個(gè)簡單的操作不應(yīng)該成為性能的瓶頸。

另外，Redis 除了處理 C 字符串之外，還需要處理單純的字節(jié)數(shù)組，以及服務(wù)器協(xié)議等內(nèi)容，所以為了方便起見，Redis 的字符串表示還應(yīng)該是二進(jìn)制安全的 [http://en.wikipedia.org/wiki/Binary-safe]：程序不應(yīng)對字符串里面保存的數(shù)據(jù)做任何假設(shè)，數(shù)據(jù)可以是以 \0 結(jié)尾的 C 字符串，也可以是單純的字節(jié)數(shù)組，或者其他格式的數(shù)據(jù)。

考慮到這兩個(gè)原因，Redis 使用 sds 類型替換了 C 語言的默認(rèn)字符串表示：sds 既可高效地實(shí)現(xiàn)追加和長度計(jì)算，同時(shí)是二進(jìn)制安全的。

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

在前面的內(nèi)容中，我們一直將 sds 作為一種抽象數(shù)據(jù)結(jié)構(gòu)來說明，實(shí)際上，它的實(shí)現(xiàn)由以下兩部分組成：

typedef char *sds;

struct sdshdr {

    // buf 已占用長度
    int len;

    // buf 剩余可用長度
    int free;

    // 實(shí)際保存字符串?dāng)?shù)據(jù)的地方
    char buf[];
};

其中，類型 sds 是 char * 的別名（alias），而結(jié)構(gòu) sdshdr 則保存了 len 、 free 和 buf 三個(gè)屬性。

作為例子，以下是新創(chuàng)建的，同樣保存 hello world 字符串的 sdshdr 結(jié)構(gòu)：

struct sdshdr {
    len = 11;
    free = 0;
    buf = "hello world\0";  // buf 的實(shí)際長度為 len + 1
};

通過 len 屬性， sdshdr 可以實(shí)現(xiàn)復(fù)雜度為 (\theta(1)) 的長度計(jì)算操作。

另一方面，通過對 buf 分配一些額外的空間，并使用 free 記錄未使用空間的大小，sdshdr 可以讓執(zhí)行追加操作所需的內(nèi)存重分配次數(shù)大大減少，下一節(jié)我們就會(huì)來詳細(xì)討論這一點(diǎn)。

當(dāng)然，sds 也對操作的正確實(shí)現(xiàn)提出了要求 —— 所有處理 sdshdr 的函數(shù)，都必須正確地更新 len 和 free 屬性，否則就會(huì)造成 bug 。

優(yōu)化追加操作

在前面說到過，利用 sdshdr 結(jié)構(gòu)，除了可以用 (\theta(1)) 復(fù)雜度獲取字符串的長度之外，還可以減少追加（append）操作所需的內(nèi)存重分配次數(shù)，以下就來詳細(xì)解釋這個(gè)優(yōu)化的原理。

為了易于理解，我們用一個(gè) Redis 執(zhí)行實(shí)例作為例子，解釋一下，當(dāng)執(zhí)行以下代碼時(shí)， Redis 內(nèi)部發(fā)生了什么：

redis> SET msg "hello world"
OK

redis> APPEND msg " again!"
(integer) 18

redis> 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 [http://redis.readthedocs.org/en/latest/string/append.html#append] 命令時(shí)，相應(yīng)的 sdshdr 被更新，字符串 " again!" 會(huì)被追加到原來的 "hello world" 之后：

struct sdshdr {
    len = 18;
    free = 18;
    buf = "hello world again!\0                  ";     // 空白的地方為預(yù)分配空間，共 18 + 18 + 1 個(gè)字節(jié)
}

注意，當(dāng)調(diào)用 SET 命令創(chuàng)建 sdshdr 時(shí)，sdshdr 的 free 屬性為 0 ，Redis 也沒有為 buf 創(chuàng)建額外的空間 ——而在執(zhí)行 APPEND [http://redis.readthedocs.org/en/latest/string/append.html#append] 之后，Redis 為 buf 創(chuàng)建了多于所需空間一倍的大小。

在這個(gè)例子中，保存 "hello world again!" 共需要 18 + 1 個(gè)字節(jié)，但程序卻為我們分配了 18 + 18 + 1 = 37 個(gè)字節(jié) ——這樣一來，如果將來再次對同一個(gè) sdshdr 進(jìn)行追加操作，只要追加內(nèi)容的長度不超過 free 屬性的值，那么就不需要對 buf 進(jìn)行內(nèi)存重分配。

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

redis> APPEND msg " again!"
(integer) 25

再次執(zhí)行 APPEND [http://redis.readthedocs.org/en/latest/string/append.html#append] 命令之后，msg 的值所對應(yīng)的 sdshdr 結(jié)構(gòu)可以表示如下：

struct sdshdr {
    len = 25;
    free = 11;
    buf = "hello world again! again!\0           ";     // 空白的地方為預(yù)分配空間，共 18 + 18 + 1 個(gè)字節(jié)
}

sds.c/sdsMakeRoomFor 函數(shù)描述了 sdshdr 的這種內(nèi)存預(yù)分配優(yōu)化策略，以下是這個(gè)函數(shù)的偽代碼版本：

def sdsMakeRoomFor(sdshdr, required_len):

    # 預(yù)分配空間足夠，無須再進(jìn)行空間分配
    if (sdshdr.free >= required_len):
        return sdshdr

    # 計(jì)算新字符串的總長度
    newlen = sdshdr.len + required_len

    # 如果新字符串的總長度小于 SDS_MAX_PREALLOC
    # 那么為字符串分配 2 倍于所需長度的空間
    # 否則就分配所需長度加上 SDS_MAX_PREALLOC 數(shù)量的空間
    if newlen < SDS_MAX_PREALLOC:
        newlen *= 2
    else:
        newlen += SDS_MAX_PREALLOC

    # 分配內(nèi)存
    newsh = zrelloc(sdshdr, sizeof(struct sdshdr)+newlen+1)

    # 更新 free 屬性
    newsh.free = newlen - sdshdr.len

    # 返回
    return newsh

在目前版本的 Redis 中，SDS_MAX_PREALLOC 的值為 1024 * 1024 ，也就是說，當(dāng)大小小于 1MB 的字符串執(zhí)行追加操作時(shí)，sdsMakeRoomFor 就為它們分配多于所需大小一倍的空間；當(dāng)字符串的大小大于 1MB ，那么 sdsMakeRoomFor 就為它們額外多分配 1MB 的空間。

Note

這種分配策略會(huì)浪費(fèi)內(nèi)存嗎？

執(zhí)行過 APPEND [http://redis.readthedocs.org/en/latest/string/append.html#append] 命令的字符串會(huì)帶有額外的預(yù)分配空間，這些預(yù)分配空間不會(huì)被釋放，除非該字符串所對應(yīng)的鍵被刪除，或者等到關(guān)閉 Redis 之后，再次啟動(dòng)時(shí)重新載入的字符串對象將不會(huì)有預(yù)分配空間。

因?yàn)閳?zhí)行 APPEND [http://redis.readthedocs.org/en/latest/string/append.html#append] 命令的字符串鍵數(shù)量通常并不多，占用內(nèi)存的體積通常也不大，所以這一般并不算什么問題。

另一方面，如果執(zhí)行 APPEND [http://redis.readthedocs.org/en/latest/string/append.html#append] 操作的鍵很多，而字符串的體積又很大的話，那可能就需要修改 Redis 服務(wù)器，讓它定時(shí)釋放一些字符串鍵的預(yù)分配空間，從而更有效地使用內(nèi)存。

sds 模塊的 API

sds 模塊基于 sds 類型和 sdshdr 結(jié)構(gòu)提供了以下 API ：

sds 還有另一部分功能性函數(shù)，比如 sdstolower 、 sdstrim 、 sdscmp ，等等，基本都是標(biāo)準(zhǔn) C 字符串庫函數(shù)的 sds 版本，這里不一一列舉了。

小結(jié)

• Redis 的字符串表示為 sds ，而不是 C 字符串（以 \0 結(jié)尾的 char*）。

• 對比 C 字符串， sds 有以下特性：

• 可以高效地執(zhí)行長度計(jì)算（strlen）；
• 可以高效地執(zhí)行追加操作（append）；

• 二進(jìn)制安全；

• sds 會(huì)為追加操作進(jìn)行優(yōu)化：加快追加操作的速度，并降低內(nèi)存分配的次數(shù)，代價(jià)是多占用了一些內(nèi)存，而且這些內(nèi)存不會(huì)被主動(dòng)釋放。