【Redis】關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)“簡單動態(tài)字符串(SDS)”的一些雜記

推薦幾篇關(guān)于SDS數(shù)據(jù)結(jié)構(gòu)講解較為詳細的文章：

一、簡單動態(tài)字符串 — Redis 設(shè)計與實現(xiàn) (redisbook.readthedocs.io)

二、深入理解Redis之簡單動態(tài)字符串 - itbsl - 博客園 (cnblogs.com)

三、Redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)詳解(2)——sds - 鐵蕾的個人博客 (zhangtielei.com)

四、簡單動態(tài)字符串 — Redis 設(shè)計與實現(xiàn) (redisbook.readthedocs.io)

一、SDS的結(jié)構(gòu)與實現(xiàn)

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

typedef char *sds;

struct sdshdr {

    // buf 已占用長度
    int len;

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

    // 實際保存字符串數(shù)據(jù)的地方
    char buf[];
};

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

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

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

通過 len 屬性， sdshdr 可以實現(xiàn)復雜度為 θ(1)的長度計算操作。

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

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

二、字符串對象

Redis 是一個鍵值對數(shù)據(jù)庫（key-value DB）， 數(shù)據(jù)庫的值可以是字符串、集合、列表等多種類型的對象， 而數(shù)據(jù)庫的鍵則總是字符串對象。對于那些包含字符串值的字符串對象來說， 每個字符串對象都包含一個 sds 值。

注意：

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

例如，以下命令創(chuàng)建了一個新的鍵值對，該鍵值對的鍵和值都是字符串對象，他們都包含一個sds值：

127.0.0.1:6379> set school "HeFeiUniversity"
OK
127.0.0.1:6379> get school
"HeFeiUniversity"
127.0.0.1:6379>

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

127.0.0.1:6379> sadd nosql "MongoDB" "Redis" "Neo4j"
(integer) 3
127.0.0.1:6379> smembers nosql
1) "Neo4j"
2) "Redis"
3) "MongoDB"
127.0.0.1:6379>

三、Redis字符串與C字符串的區(qū)別

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

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

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

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

在 Redis 內(nèi)部， 字符串的追加和長度計算很常見， 而 APPEND 和 STRLEN 更是這兩種操作，在 Redis 命令中的直接映射， 這兩個簡單的操作不應該成為性能的瓶頸。

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

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

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

通過使用SDS而不是C字符串，Redis將獲取字符串長度所需的復雜度從O(N)降低到了O(1)，這確保了獲取字符串長度的工作不會成為Redis的性能瓶頸。所以，即使我們對一個非常長的字符串反復執(zhí)行STRLEN命令，也不會對系統(tǒng)性能造成任何影響，因為STRLEN命令的復雜度僅為O(1)。

SDS相對于傳統(tǒng)C字符串的優(yōu)點☆☆☆：

四、SDS對內(nèi)存的優(yōu)化策略

SDS采用了空間預分配策略與惰性空間釋放策略來避免內(nèi)存分配問題。

空間預分配策略是指，每次 SDS 進行空間擴展時，程序不但為其分配所需的空間，還會為其分配額外的未使用空間，以減少內(nèi)存再分配次數(shù)。而額外分配的未使用空間大小取決于空間擴展后SDS 的 len 屬性值。

• 如果 len 屬性值小于 1M，那么分配的未使用空間 free 的大小與 len 屬性值相同。
• 如果 len 屬性值大于等于 1M ，那么分配的未使用空間 free 的大小固定是 1M。

SDS 對于空間釋放采用的是惰性空間釋放策略。該策略是指，SDS 字符串長度如果縮短，那么多出的未使用空間將暫時不釋放，而是增加到 free 中。以使后期擴展 SDS 時減少內(nèi)存 再分配次數(shù)。如果要釋放 SDS 的未使用空間，則可通過 sdsRemoveFreeSpace()函數(shù)來釋放。

五、SDS模塊的API

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

本文僅供學習參考！文章來源地址http://www.zghlxwxcb.cn/news/detail-412846.html

到了這里，關(guān)于【Redis】關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)簡單動態(tài)字符串(SDS)的一些雜記的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！