Redis SDS 是以時間換空間，還是空間換時間？
在 Redis中，String稱得上一個萬精油數據結構， 它即可以存放普通的字符串，也可以存放對象，同樣可以存圖片，視頻等二進制數據，使用頻次特別高，真可謂是一個萬精油。
為什么 Redis 的 String 可以存放這么多類型的數據？Redis 底層到底是如何實現 String 的呢？今天我們就來聊一聊。
一、String的特性
String 的特性主要包含下面4點：
- String 是Redis中最基本的數據類型；
- String 是二進制安全，存入和獲取的數據相同；
- Redis 字符串存儲字節序列，包括文本、序列化對象和二進制數組；
- String 存儲的 value值最大為 512MB；
二、String常用指令
String 高頻指令如下表：
指令 | 舉例 | 說明 |
set | set key value | 設置值 |
get | get key | 獲取值 |
getset | getset key | 先獲取之前的值，然后設置一個新的值 |
del | del key | 刪除key |
incr | incr key | 從0開始自增1 |
incrby | incrby key n | 自增指定的步長 |
decr | decr key | 自減1 |
decrby | decrby key n | 自減指定的步長 |
append | append key | 追加內容 |
如下圖，展示了 String常用指令：
三、實現原理
上文介紹了 String數據對象的一些基礎知識，接下來進入核心內容：String 的 Redis 底層實現。
1. SDS 結構
Redis 底層是 C語言實現的，但是 Redis 的 String數據對象并沒有直接使用 C語言傳統的字符串，而是自創了一套 SDS，用于 Redis 默認字符串表示。SDS（simple dynamic string），簡單動態字符串。
SDS 的結構定義在 sds.h 文件中，每個 sds.h/sdshdr 結構表示一個 SDS 值，在 Redis 3.2 版本之后，SDS 由一種數據結構變成了 5 種數據結構，如下源碼截圖：
- sdshdr5：存儲大小為 32 byte = 2^ 5 ，被棄用;
- sdshdr8：存儲大小為 256 byte = 2^ 8;
- sdshdr16：存儲大小為 64KB = 2 ^16
- sdshdr32：存儲大小為 4GB = 2^ 32;
- sdshdr64：存儲大小為 2^ 64;
5 種數據結構存儲不同長度的內容，Redis 會根據 SDS 存儲的內容長度來選擇不同的結構，源碼實現對應 sds.c/sdsReqType，截圖如下：
為了對 SDS 有一個更好的體感，這里以 sdshdr8 為例，執行指令：SET name Redis
執行上述 set 指令后，值對象對應的 SDS 結構如下圖：
SDS 各個屬性說明：
- len：表示 buf 已用空間的長度，占 4 個字節，不包括 \0；
- alloc：表示 buf 的實際分配長度，占 4 個字節，不包括 \0；
- flags：標記當前字節數組是 sdshdr8/16/32/64 中的哪一種，占 1 個字節；
- buf：表示字節數組，保存實際數據。為了表示字節數組的結束，Redis 會自動在數組最后加一個\0，需要額外占用 1 個字節的開銷；
從上面 SDS 的結構可以看出，SDS 依然遵循了 C語言中字符串以 \0 結尾的規則， 但是，\0占用的1 個字節空間并沒有計算在 SDS 的 len 屬性里面。
分析完 SDS 的結構，我們會問，SDS 在 Redis 中是如何存放的呢？
因為 Redis 的數據類型有很多（String、List、Set、Hash等等），不同數據類型會包含相同的元數據，所以值對象并不是直接存儲，而是被包裝成 redisObject 對象（源碼位于 server.h中），其定義如下圖：
所以，SDS 在 Redis Server 端的存儲如下圖：
另外，為了節省內存空間，Redis 還做了如下優化：
- 當保存 Long 類型整數，RedisObject 中的指針直接賦值為整數數據，這樣就不用額外的指針指向整數。這種方式稱為 int 編碼方式。
- 當保存字符串數據，且字符串小于等于 44 字節時，RedisObject 中的元數據、指針和 SDS 是一塊連續的內存區域，這樣可以避免內存碎片。這種方式稱為 embstr 編碼方式。
- 當保存字符串數據，且字符串大于 44 字節時，Redis 不再把 SDS 和 RedisObject 放在一起，而是給 SDS 分配獨立的空間，并用指針指向 SDS 結構。這種方式稱為 raw 編碼模式。
下圖為 int、embstr 和 raw 這三種編碼模式的對比：
如果想查看一個值對象是采用哪種編碼模式，可以使用 OBJECT ENCODING(（大小寫不敏感）命令，下面給了幾個示例截圖：
到此，SDS 的實現原理分析完成，需要補充的是：Redis 官方為了保證 String 的性能，在 SDS 設計上采用了兩個非常優秀的設計：空間預分配 和 惰性空間釋放。
2. 空間預分配
在對 SDS 進行修改操作時（追加字符串，拷貝字符串等），通常會調用 sds.c/sdsMakeRoomFor 方法對 SDS 的剩余容量進行檢查，如有必要會對 SDS 進行擴容，當計算修改之后字符串(用target_string表示)的目標長度之后分以下幾種情況:
(1) 剩余的 freespace 足夠容納 target_string 和末尾\0字符，則不作任何操作
(2) 剩余的 freespace 不夠容納 target_string 和末尾的\0字符
- 當target_string_size < 1MB，則會直接分配2 * target_string_size 的空間用于存儲字符串
- 當target_string_size >= 1MB，則會再額外多分配1MB的空間用于存儲字符串(target_string_size + 1024*1024)
3. 惰性空間釋放
當 SDS 字符串縮短時， 空余出來的空間并不會直接釋放，而是會被保留，等待下次再次使用，字符串縮短操作需要更新 sdshdr 頭中的 Len 字段以及alloced buffer中的\0字符的位置，如下源碼截圖，在更新字符串長度的過程中并沒有涉及到內存的重分配策略，只是簡單的修改sdshdr 頭中的 Len 字段。
四、SDS 的缺點
從上面 SDS 的結構可以看出，SDS 除了存儲 String 的內容外，還需要額外的內存空間記錄數據長度、空間使用等信息，這個就導致了 SDS 的一個比較大的缺點：占內存。那么有什么更好的數據結構呢？我們下篇文章會進行分析。
不過，計算機領域很多時候都在空間和時間上的一種權衡。而Redis String 這種浪費內存換取讀寫速度就是一個很好的體現。
五、SDS 與 C字符串比較
1. 獲取字符串長度復雜度
C字符串不記錄長度，獲取長度必須遍歷整個字符串，復雜度為O(N)，SDS 在 len 屬性中記錄了 SDS 本身的長度， 獲取 SDS 長度的復雜度為 O(1) ；
2. 緩沖區溢出
C字符串不記錄自身的長度，每次增長或縮短一個字符串，都要對底層的字符數組進行一次內存重分配操作。如果在 append 操作之前沒有通過內存重分配來擴展底層數據的空間大小，就會產生緩存區溢出；如果進行 trim 操作之后沒有通過內存重分配來釋放不再使用的空間，就會產生內存泄漏；
SDS 通過未使用空間解除了字符串長度和底層數據長度的關聯，3.0版本用 free屬性記錄未使用空間，3.2版本用 alloc屬性記錄總的分配字節數量。通過未使用空間，SDS實現了空間預分配和惰性空間釋放兩種優化的空間分配策略，解決了字符串拼接和截取的空間問題；
3. 二進制安全
C 字符串以 \0結尾（即 以 \0判斷字符串結束），所以在 C字符串的內容里面不能包含 \0，否則會被認為是字符串結尾，因此，C字符串只能保存文本數據，不能保存像圖片這樣的二進制數據；
而 SDS 的 API 會以處理二進制的方式來處理存放在 bu f數組里的數據，不會對里面的數據做任何的限制。SDS 使用 len 屬性來判斷字符串是否結束，而不是空字符。
兩者比較歸納如下表：
C字符串 | SDS |
獲取字符串長度復雜度為O(N) | 獲取字符串長度復雜度為O(1) |
API是不安全的，可能會造成緩沖區溢出 | API是安全的，不會造成緩沖區溢出 |
修改字符串長度必然需要內存重分配 | 修改字符串長度 N次最多需要執行 N次內存重分配 |
只能保存文本數據 | 可以保存文本或二進制數據 |
可以使用所有<string.h>庫中的函數 | 可以使用一部分<string.h>庫中的函數 |
六、總結
本文從 Redis的底層 SDS 實現分析了 String 的實現原理，可以說 SDS 是一種很優秀的設計，它即遵循了 C語言的部分功能，又規避了 C語言字符串常見的一些問題，這或許就是 Redis 優秀的一個原因。
另外，SDS 為了保證讀寫速度，盡管做了很多節省內存的操作（比如：sdshdr8/16/32/64，int/embstr/raw），但是，還在是一定程度上采用空間換時間。
通過 SDS 的設計，我們可以看出：在程序的世界里沒有“銀彈”，每種數據結構似乎總有其擅長的場景以及不足之處，這也正是各種數據結構百花齊放的原因。
