Redis系列(一)底層數據結構之簡單動態字符串

• 2020 年 1 月 5 日
• 筆記

• 前言
• 定義
• 優劣
  • 高性能獲取字符串長度
  • 杜絕緩衝區溢出
  • 減少修改字符串產生的內存分配次數，提高修改字符串性能
  • 二進制安全
  • 兼容部分 C 語言的庫函數
• 總結
• SDS 限制為512M問題
• 參考文章

前言

Redis 已經是大家耳熟能詳的東西了，日常工作也都在使用，面試中也是高頻的會涉及到，那麼我們對它究竟了解有多深刻呢？

我讀了幾本 Redis 相關的書籍，嘗試去了解它的具體實現，將一些底層的數據結構及實現原理記錄下來。

本文將介紹 Redis 中最基礎的 字符串 的實現方法。

定義

Redis 是使用 C 語言實現的，但是 Redis 中使用的字符串卻不是直接用的 C 語言中字符串的定義，而是自己實現了一個數據結構，叫做 SDS(simple dynamic String), 即簡單動態字符串。

Redis 中 SDS 數據結構的定義為：

struct sdshdr{      int len;      int free;      char buf[];  }

一個保存了字符串Redis的 SDS 示例圖如下：

• len=5, 說明當前存儲的字符串長度為 5.
• free=0, 說明這個結構體實例中，所有分配的空間長度已經被使用完畢。
• buf 屬性是一個 char 類型的數組，保存了實際的字符串信息。

帶有 free 空間的 SDS 示例：

可以看到 len 屬性和 buf 屬性的已使用部分都和第一個示例相同，但是 free 屬性為 5, 同時 buf 屬性的除了保存了真實的字符串內容之外，還有 5 個空的未使用空間 (『』結束字符不在長度中計算）.

優劣

Redis 為什麼要這麼做呢，或者說使用 SDS 來作為字符串的具體實現結構，有什麼好處呢？

那麼就不得不提 C 語言本來的字符串了。

C 語言的字符串定義，是使用和字符串相等長度的字符數組來存儲字符串，並且在後面額外加一個字符來存儲空字符』』. 也就是下圖：

這種實現方式的優點就是，簡單且直觀。但是眾所周知，Redis 是一個性能極強的內存數據庫，這種實現方式並不能滿足 Redis 的性能要求，當然，同時也有一部分的功能性要求無法滿足。

後面講述的每一條優點，都是相對於 C 語言字符串而言的，具體的特性再具體分析。

高性能獲取字符串長度

從 C 語言字符串的結構圖中，我們可以看到，如果我們想獲取一個字符串的長度，那麼唯一的辦法就是遍歷整個字符串。遍歷操作需要 O(N) 的時間複雜度。

而 SDS 記錄了字符串的長度，也就是 len屬性，我們只需要直接訪問該屬性，就可以拿到當前 SDS 的長度。訪問屬性操作的時間複雜度是 O(1).

Redis 字符串數據結構的 求長度的命令 STRLEN. 內部即應用了這一特性。無論你的 string 中存儲了多長的字符串，當你想求出它的長度時，可以隨意的執行 STRLEN, 而不用擔心對 Redis 服務器的性能造成壓力。

杜絕緩衝區溢出

C 語言的的字符串拼接函數，strcat(*desc, const char *src), 會將第二個參數的值直接連接在第一個字符串後面，然而如果第一個字符串的空間本就不足，那麼此時就會產生緩衝區溢出。

SDS 記錄了字符串的長度，同時在 API 實現上杜絕了這一個問題，當需要對 SDS 進行拼接時，SDS 會首先檢查剩餘的未使用空間是否足夠，如果不足，會首先擴展未使用空間，然後進行字符串拼接。

因此，SDS 通過記錄使用長度及未使用空間長度，以及封裝 API, 完美的杜絕了在拼接字符串時容易造成緩衝區溢出的問題。

減少修改字符串產生的內存分配次數，提高修改字符串性能

上面提到，C 語言的字符串實現，是一個長度永遠等於 字符串內容長度+1 的位元組數組。那麼也就意味着，當字符串發生修改，它所佔用的內存空間必須要發生更改。

• 字符串變長。需要首先擴展當前字符串的位元組數組，來容納新的內容。
• 字符串變短。在修改完字符串後，需要釋放掉空餘出來的內存空間。

內存分配是比較底層的實現，其中實現比較複雜，且可能執行系統調用，通常情況下比較耗時，Redis 怎麼進行對應的優化呢？

• 空間預分配

SDS 在進行修改之後，會對接下來可能需要的空間進行預分配。這也就是 free 屬性存在的意義，記錄當前預分配了多少空間。

分配策略：

1. 如果當前 SDS 的長度小於 1M, 那麼分配等於已佔用空間的未使用空間，即讓 free 等於 len.
2. 如果當前 SDS 的長度大於 1M, 那麼分配 1M 的 free 空間。

在 SDS 修改時，會先查看 free屬性的值，來確定是否需要進行空間擴展，如果不需要就直接進行拼接了。

通過預分配策略，SDS 連續增長 N 次，所需要的內存分配次數從絕對 N 次，變成了最多 N 次。

• 惰性釋放內存

當 SDS 進行了縮短操作，那麼多餘的空間不着急進行釋放，暫時留着以備下次進行增長時使用。

聽起來預分配和惰性釋放是不是很簡單的道理？本質上也是使用空間換取時間的操作。而且可能發現了其中的一個問題，那就是在內存緊張的機器上，這樣浪費真的好嗎？

這個問題，Redis 當然考慮到了，SDS 也提供了對應的 API, 在需要的時候，會自己釋放掉多餘的未使用空間。

二進制安全

Redis 的字符串是二進制安全的這個特性，我們應該在很多的文章中都看到了。但是它為什麼可以做到二進制安全呢？

C 語言的字符串不是二進制安全的，因為它使用空間符』』來判斷一個字符串的結尾。也就是說，假如你的字符串是 abcaa 哈哈哈、0, 那麼你就不能使用 C 語言的字符串，因為它識別到第一個空字符』』的時候就結束識別了，它認為這次的字符串值是』abc』.

而二進制中的數據，我們誰也說不好，如果我們存儲一段音頻序列化後的數據，中間肯定會有無數個空字符，這時候怎麼 C 語言的字符串就無能為力了。

而 SDS 可以，雖然 SDS 中也會在字符串的末尾儲存一個空字符，但是它並不以這個空字符為判斷條件，SDS 判斷字符串的長度時使用 len屬性的，截取 位元組數組 buf 中的前 len 個字符即可。

因此，在 SDS 中，可以存儲任意格式的二進制數據，也就是我們常說的，Redis 的字符串是二進制安全的。

兼容部分 C 語言的庫函數

上面提到，SDS 使用 len 屬性的長度來判斷字符串的結尾，但是，卻依然遵循了 C 語言的慣例，在字符串結尾的地方填充了一個空字符』』.

這樣做可以在處理一些純文本的字符串時，可以方便的沿用一些 C 語言的庫函數，而不是自己重新為 SDS 進行開發庫函數。

總結

Redis 中使用字符串的大多數場景（鍵的字符串，字符串數據結構的實際值存儲等等）下，都不使用 C 語言的字符串，而是使用 SDS. 簡單動態字符串。

它的實現方式是：一個位元組數組 buf, 一個當前字符串長度的記錄屬性 len, 一個當前未使用空間長度屬性 free. 位元組數組的長度不要求絕對等於字符串值的真實長度，會有一定的緩衝。

相對於 C 語言的字符串，SDS 的優勢如下：

SDS 限制為512M問題

從官網上我們可以得知, Redis的key以及字符串數據結構的值, 最大的大小為 512M.這是官網信息,基本上毋庸置疑.

讓我們試一下:

    public static void main(String[] args) {          Jedis jedis = new Jedis("localhost");          jedis.set("test", "test");          byte[] bytes = new byte[1024 * 1024];          String str = new String(bytes);          // 每次加1MB          for (int i = 0; i < 512; i++) {              jedis.append("test", str);          }      }

Redis會報錯, 報錯信息為:

Exception in thread "main" redis.clients.jedis.exceptions.JedisDataException: ERR string exceeds maximum allowed size (512MB)  	at redis.clients.jedis.Protocol.processError(Protocol.java:132)  	at redis.clients.jedis.Protocol.process(Protocol.java:166)  	at redis.clients.jedis.Protocol.read(Protocol.java:220)  	at redis.clients.jedis.Connection.readProtocolWithCheckingBroken(Connection.java:309)  	at redis.clients.jedis.Connection.getIntegerReply(Connection.java:260)  	at redis.clients.jedis.Jedis.append(Jedis.java:689)  	at daily.JedisTest.main(JedisTest.java:50)

好的, 坐實了~.

參考文章

《Redis 的設計與實現（第二版）》