­

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

前言

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 的優勢如下：

C 字元串

SDS

獲取字元串長度需要 O(N)

獲取字元串長度需要 O(1)

容易造成緩衝區溢出

通過封裝 API, 自動變化長度，避免緩衝區溢出

每次修改字元串長度，都需要記憶體重新分配

最壞情況下，同 C 語言字元串，其他很多情況不需要記憶體重分配，直接使用預留緩衝即可。

只能保存純文本

二進位安全，可以保存任意格式的二進位數據

無縫使用所有 C 庫函數

可以兼容一部分的 C 庫函數

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 的設計與實現（第二版）》

VirMach 便宜 VPS

QNews

QNews