Redis使用的是自己構(gòu)建的簡單動態(tài)字符串（simple dynamic string拨脉，SDS）的抽象類型或衡， 并將 SDS 用作 Redis 的默認(rèn)字符串表示焦影。

定義

每個 sds.h/sdshdr 結(jié)構(gòu)表示一個 SDS 值：

struct sdshdr {

    // 記錄 buf 數(shù)組中已使用字節(jié)的數(shù)量
    // 等于 SDS 所保存字符串的長度
    int len;

    // 記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量
    int free;

    // 字節(jié)數(shù)組，用于保存字符串
    char buf[];

};

圖 2-1 展示了一個 SDS 示例：

• free 屬性的值為 0 封断， 表示這個 SDS 沒有分配任何未使用空間斯辰。
• len 屬性的值為 5 ， 表示這個 SDS 保存了一個五字節(jié)長的字符串坡疼。
• buf 屬性是一個 char 類型的數(shù)組彬呻， 數(shù)組的前五個字節(jié)分別保存了 'R' 、 'e' 柄瑰、 'd' 闸氮、 'i' 、 's' 五個字符教沾， 而最后一個字節(jié)則保存了空字符 '\0' 蒲跨。

Paste_Image.png

SDS 遵循 C 字符串以空字符結(jié)尾的慣例， 保存空字符的 1 字節(jié)空間不計算在 SDS 的 len 屬性里面授翻， 并且為空字符分配額外的 1 字節(jié)空間或悲， 以及添加空字符到字符串末尾等操作都是由 SDS 函數(shù)自動完成的， 所以這個空字符對于 SDS 的使用者來說是完全透明的藏姐。

遵循空字符結(jié)尾這一慣例的好處是隆箩， SDS 可以直接重用一部分 C 字符串函數(shù)庫里面的函數(shù)。

舉個例子羔杨， 如果我們有一個指向圖 2-1 所示 SDS 的指針 s ， 那么我們可以直接使用 stdio.h/printf 函數(shù)杨蛋， 通過執(zhí)行以下語句：

printf("%s", s->buf);

來打印出 SDS 保存的字符串值 "Redis" 兜材， 而無須為 SDS 編寫專門的打印函數(shù)。

圖 2-2 展示了另一個 SDS 示例:

• 這個 SDS 和之前展示的 SDS 一樣逞力， 都保存了字符串值 "Redis" 曙寡。
• 這個 SDS 和之前展示的 SDS 的區(qū)別在于， 這個 SDS 為 buf 數(shù)組分配了五字節(jié)未使用空間寇荧， 所以它的 free 屬性的值為 5 （圖中使用五個空格來表示五字節(jié)的未使用空間）举庶。

Paste_Image.png

SDS 與 C 字符串的區(qū)別

根據(jù)傳統(tǒng)， C 語言使用長度為 N+1 的字符數(shù)組來表示長度為 N 的字符串揩抡， 并且字符數(shù)組的最后一個元素總是空字符 '\0' 户侥。

比如說镀琉， 圖 2-3 就展示了一個值為 "Redis" 的 C 字符串：

Paste_Image.png

C 語言使用的這種簡單的字符串表示方式， 并不能滿足 Redis 對字符串在安全性蕊唐、效率屋摔、以及功能方面的要求， 本節(jié)接下來的內(nèi)容將詳細(xì)對比 C 字符串和 SDS 之間的區(qū)別替梨， 并說明 SDS 比 C 字符串更適用于 Redis 的原因钓试。

常數(shù)復(fù)雜度獲取字符串長度

因為 C 字符串并不記錄自身的長度信息， 所以為了獲取一個 C 字符串的長度副瀑， 程序必須遍歷整個字符串弓熏， 對遇到的每個字符進(jìn)行計數(shù)， 直到遇到代表字符串結(jié)尾的空字符為止糠睡， 這個操作的復(fù)雜度為 O(N) 硝烂。

舉個例子， 圖 2-4 展示了程序計算一個 C 字符串長度的過程铜幽。

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

和 C 字符串不同滞谢， 因為 SDS 在 len 屬性中記錄了 SDS 本身的長度， 所以獲取一個 SDS 長度的復(fù)雜度僅為 O(1) 除抛。

舉個例子狮杨， 對于圖 2-5 所示的 SDS 來說， 程序只要訪問 SDS 的 len 屬性到忽， 就可以立即知道 SDS 的長度為 5 字節(jié)：

Paste_Image.png

又比如說橄教， 對于圖 2-6 展示的 SDS 來說， 程序只要訪問 SDS 的 len 屬性喘漏， 就可以立即知道 SDS 的長度為 11 字節(jié)护蝶。

Paste_Image.png

設(shè)置和更新 SDS 長度的工作是由 SDS 的 API 在執(zhí)行時自動完成的， 使用 SDS 無須進(jìn)行任何手動修改長度的工作翩迈。

通過使用 SDS 而不是 C 字符串持灰， Redis 將獲取字符串長度所需的復(fù)雜度從 O(N) 降低到了 O(1) ， 這確保了獲取字符串長度的工作不會成為 Redis 的性能瓶頸负饲。

比如說堤魁， 因為字符串鍵在底層使用 SDS 來實現(xiàn)， 所以即使我們對一個非常長的字符串鍵反復(fù)執(zhí)行 STRLEN 命令返十， 也不會對系統(tǒng)性能造成任何影響妥泉， 因為 STRLEN 命令的復(fù)雜度僅為 O(1) 。

杜絕緩沖區(qū)溢出

除了獲取字符串長度的復(fù)雜度高之外洞坑， C 字符串不記錄自身長度帶來的另一個問題是容易造成緩沖區(qū)溢出（buffer overflow）盲链。

舉個例子， <string.h>/strcat 函數(shù)可以將 src 字符串中的內(nèi)容拼接到 dest 字符串的末尾：

char *strcat(char *dest, const char *src);

因為 C 字符串不記錄自身的長度， 所以 strcat 假定用戶在執(zhí)行這個函數(shù)時刽沾， 已經(jīng)為 dest 分配了足夠多的內(nèi)存本慕， 可以容納 src 字符串中的所有內(nèi)容， 而一旦這個假定不成立時悠轩， 就會產(chǎn)生緩沖區(qū)溢出间狂。

舉個例子， 假設(shè)程序里有兩個在內(nèi)存中緊鄰著的 C 字符串 s1 和 s2 火架， 其中 s1 保存了字符串 "Redis" 鉴象， 而 s2 則保存了字符串 "MongoDB" ， 如圖 2-7 所示何鸡。

Paste_Image.png

如果一個程序員決定通過執(zhí)行：

strcat(s1, " Cluster");

將 s1 的內(nèi)容修改為 "Redis Cluster" 纺弊， 但粗心的他卻忘了在執(zhí)行 strcat 之前為 s1 分配足夠的空間， 那么在 strcat 函數(shù)執(zhí)行之后骡男， s1 的數(shù)據(jù)將溢出到 s2 所在的空間中淆游， 導(dǎo)致 s2 保存的內(nèi)容被意外地修改， 如圖 2-8 所示隔盛。

Paste_Image.png

與 C 字符串不同犹菱， SDS 的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性： 當(dāng) SDS API 需要對 SDS 進(jìn)行修改時， API 會先檢查 SDS 的空間是否滿足修改所需的要求吮炕， 如果不滿足的話腊脱， API 會自動將 SDS 的空間擴(kuò)展至執(zhí)行修改所需的大小， 然后才執(zhí)行實際的修改操作龙亲， 所以使用 SDS 既不需要手動修改 SDS 的空間大小陕凹， 也不會出現(xiàn)前面所說的緩沖區(qū)溢出問題。

舉個例子鳄炉， SDS 的 API 里面也有一個用于執(zhí)行拼接操作的 sdscat 函數(shù)杜耙， 它可以將一個 C 字符串拼接到給定 SDS 所保存的字符串的后面， 但是在執(zhí)行拼接操作之前拂盯， sdscat 會先檢查給定 SDS 的空間是否足夠佑女， 如果不夠的話， sdscat 就會先擴(kuò)展 SDS 的空間磕仅， 然后才執(zhí)行拼接操作珊豹。

比如說， 如果我們執(zhí)行：

sdscat(s, " Cluster");

其中 SDS 值 s 如圖 2-9 所示榕订， 那么 sdscat 將在執(zhí)行拼接操作之前檢查 s 的長度是否足夠， 在發(fā)現(xiàn) s 目前的空間不足以拼接 " Cluster" 之后蜕便， sdscat 就會先擴(kuò)展 s 的空間劫恒， 然后才執(zhí)行拼接 " Cluster" 的操作， 拼接操作完成之后的 SDS 如圖 2-10 所示。

Paste_Image.png

Paste_Image.png

注意圖 2-10 所示的 SDS ： sdscat 不僅對這個 SDS 進(jìn)行了拼接操作两嘴， 它還為 SDS 分配了 13 字節(jié)的未使用空間丛楚， 并且拼接之后的字符串也正好是 13 字節(jié)長， 這種現(xiàn)象既不是 bug 也不是巧合憔辫， 它和 SDS 的空間分配策略有關(guān)趣些， 接下來的小節(jié)將對這一策略進(jìn)行說明。

減少修改字符串時帶來的內(nèi)存重分配次數(shù)

正如前兩個小節(jié)所說贰您， 因為 C 字符串并不記錄自身的長度坏平， 所以對于一個包含了 N 個字符的 C 字符串來說， 這個 C 字符串的底層實現(xiàn)總是一個 N+1 個字符長的數(shù)組（額外的一個字符空間用于保存空字符）锦亦。

因為 C 字符串的長度和底層數(shù)組的長度之間存在著這種關(guān)聯(lián)性舶替， 所以每次增長或者縮短一個 C 字符串， 程序都總要對保存這個 C 字符串的數(shù)組進(jìn)行一次內(nèi)存重分配操作：

• 如果程序執(zhí)行的是增長字符串的操作杠园， 比如拼接操作（append）顾瞪， 那么在執(zhí)行這個操作之前， 程序需要先通過內(nèi)存重分配來擴(kuò)展底層數(shù)組的空間大小 —— 如果忘了這一步就會產(chǎn)生緩沖區(qū)溢出抛蚁。
• 如果程序執(zhí)行的是縮短字符串的操作陈醒， 比如截斷操作（trim）， 那么在執(zhí)行這個操作之后瞧甩， 程序需要通過內(nèi)存重分配來釋放字符串不再使用的那部分空間 —— 如果忘了這一步就會產(chǎn)生內(nèi)存泄漏钉跷。

舉個例子， 如果我們持有一個值為 "Redis" 的 C 字符串 s 亲配， 那么為了將 s 的值改為 "Redis Cluster" 尘应， 在執(zhí)行：

strcat(s, " Cluster");

之前， 我們需要先使用內(nèi)存重分配操作吼虎， 擴(kuò)展 s 的空間犬钢。

之后， 如果我們又打算將 s 的值從 "Redis Cluster" 改為 "Redis Cluster Tutorial" 思灰， 那么在執(zhí)行：

strcat(s, " Tutorial");

之前玷犹， 我們需要再次使用內(nèi)存重分配擴(kuò)展 s 的空間， 諸如此類洒疚。

因為內(nèi)存重分配涉及復(fù)雜的算法歹颓， 并且可能需要執(zhí)行系統(tǒng)調(diào)用， 所以它通常是一個比較耗時的操作：

• 在一般程序中油湖， 如果修改字符串長度的情況不太常出現(xiàn)巍扛， 那么每次修改都執(zhí)行一次內(nèi)存重分配是可以接受的。
• 但是 Redis 作為數(shù)據(jù)庫乏德， 經(jīng)常被用于速度要求嚴(yán)苛撤奸、數(shù)據(jù)被頻繁修改的場合吠昭， 如果每次修改字符串的長度都需要執(zhí)行一次內(nèi)存重分配的話， 那么光是執(zhí)行內(nèi)存重分配的時間就會占去修改字符串所用時間的一大部分胧瓜， 如果這種修改頻繁地發(fā)生的話矢棚， 可能還會對性能造成影響。
  為了避免 C 字符串的這種缺陷府喳， SDS 通過未使用空間解除了字符串長度和底層數(shù)組長度之間的關(guān)聯(lián)： 在 SDS 中蒲肋， buf 數(shù)組的長度不一定就是字符數(shù)量加一， 數(shù)組里面可以包含未使用的字節(jié)钝满， 而這些字節(jié)的數(shù)量就由 SDS 的 free 屬性記錄兜粘。

通過未使用空間， SDS 實現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略舱沧。

空間預(yù)分配

空間預(yù)分配用于優(yōu)化 SDS 的字符串增長操作： 當(dāng) SDS 的 API 對一個 SDS 進(jìn)行修改妹沙， 并且需要對 SDS 進(jìn)行空間擴(kuò)展的時候， 程序不僅會為 SDS 分配修改所必須要的空間熟吏， 還會為 SDS 分配額外的未使用空間距糖。

其中， 額外分配的未使用空間數(shù)量由以下公式?jīng)Q定：

• 如果對 SDS 進(jìn)行修改之后牵寺， SDS 的長度（也即是 len 屬性的值）將小于 1 MB 悍引， 那么程序分配和 len 屬性同樣大小的未使用空間， 這時 SDS len 屬性的值將和 free 屬性的值相同帽氓。 舉個例子趣斤， 如果進(jìn)行修改之后， SDS 的 len 將變成 13 字節(jié)黎休， 那么程序也會分配 13 字節(jié)的未使用空間浓领， SDS 的 buf 數(shù)組的實際長度將變成 13 + 13 + 1 = 27 字節(jié)（額外的一字節(jié)用于保存空字符）。
• 如果對 SDS 進(jìn)行修改之后势腮， SDS 的長度將大于等于 1 MB 联贩， 那么程序會分配 1 MB 的未使用空間。 舉個例子捎拯， 如果進(jìn)行修改之后泪幌， SDS 的 len 將變成 30 MB ， 那么程序會分配 1 MB 的未使用空間署照， SDS 的 buf 數(shù)組的實際長度將為 30 MB + 1 MB + 1 byte 祸泪。

通過空間預(yù)分配策略， Redis 可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)建芙。

舉個例子没隘， 對于圖 2-11 所示的 SDS 值 s 來說， 如果我們執(zhí)行：

sdscat(s, " Cluster");

那么 sdscat 將執(zhí)行一次內(nèi)存重分配操作禁荸， 將 SDS 的長度修改為 13 字節(jié)升略， 并將 SDS 的未使用空間同樣修改為 13 字節(jié)微王， 如圖 2-12 所示屡限。

Paste_Image.png

Paste_Image.png

如果這時品嚣， 我們再次對 s 執(zhí)行：

sdscat(s, " Tutorial");

那么這次 sdscat 將不需要執(zhí)行內(nèi)存重分配： 因為未使用空間里面的 13 字節(jié)足以保存 9 字節(jié)的 " Tutorial" ， 執(zhí)行 sdscat 之后的 SDS 如圖 2-13 所示钧大。

Paste_Image.png

在擴(kuò)展 SDS 空間之前翰撑， SDS API 會先檢查未使用空間是否足夠， 如果足夠的話啊央， API 就會直接使用未使用空間眶诈， 而無須執(zhí)行內(nèi)存重分配。

通過這種預(yù)分配策略瓜饥， SDS 將連續(xù)增長 N 次字符串所需的內(nèi)存重分配次數(shù)從必定 N 次降低為最多 N 次逝撬。

惰性空間釋放

惰性空間釋放用于優(yōu)化 SDS 的字符串縮短操作： 當(dāng) SDS 的 API 需要縮短 SDS 保存的字符串時， 程序并不立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié)蹦渣， 而是使用 free 屬性將這些字節(jié)的數(shù)量記錄起來终抽， 并等待將來使用求厕。

舉個例子， sdstrim 函數(shù)接受一個 SDS 和一個 C 字符串作為參數(shù)狡相， 從 SDS 左右兩端分別移除所有在 C 字符串中出現(xiàn)過的字符。

比如對于圖 2-14 所示的 SDS 值 s 來說食磕， 執(zhí)行：

sdstrim(s, "XY");   // 移除 SDS 字符串中的所有 'X' 和 'Y'

會將 SDS 修改成圖 2-15 所示的樣子尽棕。

Paste_Image.png

Paste_Image.png

注意執(zhí)行 sdstrim 之后的 SDS 并沒有釋放多出來的 8 字節(jié)空間， 而是將這 8 字節(jié)空間作為未使用空間保留在了 SDS 里面彬伦， 如果將來要對 SDS 進(jìn)行增長操作的話滔悉， 這些未使用空間就可能會派上用場。

舉個例子单绑， 如果現(xiàn)在對 s 執(zhí)行：

sdscat(s, " Redis");

那么完成這次 sdscat 操作將不需要執(zhí)行內(nèi)存重分配： 因為 SDS 里面預(yù)留的 8 字節(jié)空間已經(jīng)足以拼接 6 個字節(jié)長的 " Redis" 回官， 如圖 2-16 所示。

Paste_Image.png

通過惰性空間釋放策略询张， SDS 避免了縮短字符串時所需的內(nèi)存重分配操作孙乖， 并為將來可能有的增長操作提供了優(yōu)化。

與此同時份氧， SDS 也提供了相應(yīng)的 API 唯袄， 讓我們可以在有需要時， 真正地釋放 SDS 里面的未使用空間蜗帜， 所以不用擔(dān)心惰性空間釋放策略會造成內(nèi)存浪費恋拷。

二進(jìn)制安全

C 字符串中的字符必須符合某種編碼（比如 ASCII）， 并且除了字符串的末尾之外厅缺， 字符串里面不能包含空字符蔬顾， 否則最先被程序讀入的空字符將被誤認(rèn)為是字符串結(jié)尾 —— 這些限制使得 C 字符串只能保存文本數(shù)據(jù)宴偿， 而不能保存像圖片、音頻诀豁、視頻窄刘、壓縮文件這樣的二進(jìn)制數(shù)據(jù)。

舉個例子舷胜， 如果有一種使用空字符來分割多個單詞的特殊數(shù)據(jù)格式娩践， 如圖 2-17 所示， 那么這種格式就不能使用 C 字符串來保存烹骨， 因為 C 字符串所用的函數(shù)只會識別出其中的 "Redis" 翻伺， 而忽略之后的 "Cluster" 。

Paste_Image.png

雖然數(shù)據(jù)庫一般用于保存文本數(shù)據(jù)沮焕， 但使用數(shù)據(jù)庫來保存二進(jìn)制數(shù)據(jù)的場景也不少見吨岭， 因此， 為了確保 Redis 可以適用于各種不同的使用場景峦树， SDS 的 API 都是二進(jìn)制安全的（binary-safe）： 所有 SDS API 都會以處理二進(jìn)制的方式來處理 SDS 存放在 buf 數(shù)組里的數(shù)據(jù)辣辫， 程序不會對其中的數(shù)據(jù)做任何限制、過濾空入、或者假設(shè) —— 數(shù)據(jù)在寫入時是什么樣的络它， 它被讀取時就是什么樣。

這也是我們將 SDS 的 buf 屬性稱為字節(jié)數(shù)組的原因 —— Redis 不是用這個數(shù)組來保存字符歪赢， 而是用它來保存一系列二進(jìn)制數(shù)據(jù)化戳。

比如說， 使用 SDS 來保存之前提到的特殊數(shù)據(jù)格式就沒有任何問題埋凯， 因為 SDS 使用 len 屬性的值而不是空字符來判斷字符串是否結(jié)束点楼， 如圖 2-18 所示。

Paste_Image.png

通過使用二進(jìn)制安全的 SDS 白对， 而不是 C 字符串掠廓， 使得 Redis 不僅可以保存文本數(shù)據(jù)， 還可以保存任意格式的二進(jìn)制數(shù)據(jù)甩恼。

兼容部分 C 字符串函數(shù)

雖然 SDS 的 API 都是二進(jìn)制安全的蟀瞧， 但它們一樣遵循 C 字符串以空字符結(jié)尾的慣例： 這些 API 總會將 SDS 保存的數(shù)據(jù)的末尾設(shè)置為空字符， 并且總會在為 buf 數(shù)組分配空間時多分配一個字節(jié)來容納這個空字符条摸， 這是為了讓那些保存文本數(shù)據(jù)的 SDS 可以重用一部分 <string.h> 庫定義的函數(shù)悦污。

Paste_Image.png

舉個例子， 如圖 2-19 所示钉蒲， 如果我們有一個保存文本數(shù)據(jù)的 SDS 值 sds 切端， 那么我們就可以重用 <string.h>/strcasecmp 函數(shù)， 使用它來對比 SDS 保存的字符串和另一個 C 字符串：

strcasecmp(sds->buf, "hello world");

這樣 Redis 就不用自己專門去寫一個函數(shù)來對比 SDS 值和 C 字符串值了顷啼。

與此類似踏枣， 我們還可以將一個保存文本數(shù)據(jù)的 SDS 作為 strcat 函數(shù)的第二個參數(shù)昌屉， 將 SDS 保存的字符串追加到一個 C 字符串的后面：

strcat(c_string, sds->buf);

這樣 Redis 就不用專門編寫一個將 SDS 字符串追加到 C 字符串之后的函數(shù)了。

通過遵循 C 字符串以空字符結(jié)尾的慣例茵瀑， SDS 可以在有需要時重用 <string.h> 函數(shù)庫间驮， 從而避免了不必要的代碼重復(fù)。

應(yīng)用

介紹完結(jié)構(gòu)瘾婿，下面介紹我們?nèi)绾问褂胷edis string來為我們服務(wù)蜻牢。

命令簡介

使用 bitmap 實現(xiàn)用戶上線次數(shù)統(tǒng)計

假設(shè)現(xiàn)在我們希望記錄自己網(wǎng)站上的用戶的上線頻率吆倦，比如說听诸，計算用戶 A 上線了多少天，用戶 B 上線了多少天蚕泽，諸如此類晌梨，以此作為數(shù)據(jù)，從而決定讓哪些用戶參加 beta 測試等活動 —— 這個模式可以使用 SETBIT 和 BITCOUNT 來實現(xiàn)赛糟。
比如說派任，每當(dāng)用戶在某一天上線的時候，我們就使用 SETBIT 璧南，以用戶名作為key掌逛，將那天所代表的網(wǎng)站的上線日作為offset參數(shù)，并將這個 offset上的為設(shè)置為1司倚。
舉個例子豆混，如果今天是網(wǎng)站上線的第 100 天，而用戶 peter 在今天閱覽過網(wǎng)站动知，那么執(zhí)行命令 SETBIT peter 1001皿伺；如果明天 peter 也繼續(xù)閱覽網(wǎng)站，那么執(zhí)行命令SETBIT peter 1011盒粮，以此類推鸵鸥。
當(dāng)要計算 peter 總共以來的上線次數(shù)時，就使用BITCOUNT 命令：執(zhí)行 BITCOUNT peter，得出的結(jié)果就是 peter 上線的總天數(shù)妒穴。

重點

• Redis 大多數(shù)情況會使用SDS代替C字符串宋税。
• 比起c字符串，SDS具有數(shù)據(jù)長度復(fù)雜度為0讼油；杜絕緩沖區(qū)益處杰赛，減少修改字符串長度所需的內(nèi)存重新分配次數(shù)；二進(jìn)制安全矮台；兼容部分C字符串函數(shù)乏屯。

參考

Binary safe
Redis 設(shè)計與實現(xiàn)
Redis 命令參考
例子
REDIS BITMAPS – FAST, EASY, REALTIME METRICS