Redis 中的 “SOS”，不對，是SDS
大家好，我是鴨血粉絲(大家會親切的喊我 「阿粉」)，是一位喜歡吃鴨血粉絲的程序員，之前給大家總結了線上 OOM 的情況，相信大家也能從中學到一些東西，身為一名有追求的程序員，阿粉我的理解是光會吃老本是不行的，所以我一直也在學習，今天大家就跟我一起來了解一下 Redis 的 SDS 吧(不是 SOS 哦~)。
01、SDS 數據結構
Redis 底層是基于 C 語言來開發的，但是它沒有采用 C 語言傳統的字符串表示方式，而是自定義了一種叫做 SDS(Sample Dynamic String，簡單動態字符串)的數據結構來表示字符串。傳統的 C 語言的字符串是采用空字符(\0)作為結尾的字符數組，SDS 的數據結構稍微復雜一點，整個結構包含三個部分，是 Redis 的基礎。(阿粉猜測這里就是傳說中的青出于藍而勝于藍)。
1.1、數據結構
在源碼 sds.h/sdshdr 結構體中定義了 SDS 的數據結構，包括三個部分，free，len，buf[]，依次含義如下
- buf[]：字節數組，用于存放實際的字符串;
- len：記錄 buf 數組中已經使用的字節數量，等同于 SDS 所保存的字符串的長度;
- free：記錄 buf 數組中未使用的字節的數量。
說明
上圖中的 SDS 表示一個存放了 'RED' 字符串，已經使用的長度為 3，未使用的長度為 2(這里用空白格表示未使用)，其中的 '\0' 表示的是字符串的結束，不計算在 SDS 的 len 中，并且由 SDS 底層函數自動添加，對使用者來說是透明。這里統一采用空字符(\0)結尾是為了復用 C 語言的相關函數。這個相信大家也很能理解，畢竟有祖宗可以靠，沒必要全靠自己那么辛苦~。
02、為什么采用 SDS
2.1、SDS 與 C語言字符串的區別
在說明 Redis 為什么要自定義 SDS 之前，阿粉覺得我們應該先看一下 SDS 與傳統的 C 語言的字符串有什么區別，知道了具體的區別我們才能知道這樣實現的原因是什么。
2.1.1、O(1) 獲取字符串的長度
傳統的 C 語言字符串如果要獲取字符串的長度，則需要遍歷整個字符串，直到遇到 '\0' 字符，才知道整個字符串的長度是多少，操作復雜度是 O(n) 的。但是在 SDS 中，由于我們記錄了字符串的長度，所以在獲取字符串長度的時候是可以直接獲取的，整個操作為 O(1)。
如上面的示例，我們可以直接獲取字符串的長度是 3，而不需要遍歷，另外字符串 Key 在 Redis 的底層實現就是采用 SDS 的，所以這個特性就保證了我們在計算 Key 的長度的時候不會出現任何瓶頸，對系統的性能不會有任何影響。
2.1.2、動態擴容
由于 SDS 中記錄了未使用的空間大小，所以如果出現對已有字符串進行修改或者賦值時，SDS 底層函數會自動檢測剩余空間是否能滿足此次修改，如果 free 空間足夠則直接修改;如果 free 空間不夠則會先進行動態擴容達到能滿足的空間大小，然后再執行修改動作。整個擴容的動作是 SDS 底層函數自動完成，對使用者無感。
而對于傳統的 C 語言字符串，如果在修改前忘記手動擴容則會導致字符串后面的數據被覆蓋。這里阿粉就不得不說一句了，為了方便大眾程序員，另一些骨灰級程序員(嗯，仿佛看到了未來的阿粉)也是操碎了心啊~
2.1.3、減少內存分配次數
在傳統的 C 語言的字符串，我們每次對字符串的修改都會涉及到字符串內存的重新分配，不管是增加還是減少字符串的長度。這種情況下，如果我們多次對字符串的長度進行調整的時候就會導致多次的內存重新分配。
而在 SDS 中我們在對一個 SDS 初始化的時候會根據實際 buf[] 字符串的長度進行預先空間分配，并且標記為 free。這種方式叫做空間預分配，在很大程度上可以減少增加字符串長度導致內存重新分配的情況。free 的空間分配的策略是根據 buf[] 大小來決定的，如果 buf[] 大小小于 1MB，則 len 多大 free 就多大;如果 buf[] 大小大于 1MB，則 free 固定設置為 1MB。
上面說的是SDS 字符串的長度增加，另外如果 SDS 的字符串長度減少，那么 SDS 會將減少的長度存放到 free 中，而不是直接回收，這樣可以方便下次如果再次使用，減少內存重新分配。這種策略叫做惰性空間釋放。
同樣的上面兩種操作對使用者是完全無感的，阿粉覺得這種方案還是很合理的，不知道“元芳”你怎么看?
2.1.4、二進制安全
我們都知道 Redis 是可以存儲各種類型數據的，不僅是字符串也可以存儲圖片，視頻等二進制數據流。這是由于 Redis 不依賴一 '\0' 空字符作為結束字符。C 語言之所以不支持就是因為二進制流中會攜帶 '\0' 字符，導致無法知道字符串真實的結束位置。這就帶來了另一個 Redis 特性，就是二進制的安全性。
2.2 為什么使用 SDS
通過上面阿粉提到的內容我們知道了 SDS 比傳統的 C 語言的字符串有很多優勢，也正是這些必不可少的優勢才促成了 SDS的存在。Redis 是一個高性能的內存數據庫，所以在性能方面要求特別高，這種設計方式雖然浪費了一定的空間，但是為了達到性能的要求也是值得的。有空間換時間的這種方式，在軟件設計的領域還是很多的。
2.3 SDS 常用 API
上面阿粉說的都是一些原理，下面從源碼上給大家展示一下。在 2.1 中提到有獲取長度 len 和釋放空間 free 的動作，那么對應在 SDS 底層必定會有提供支持的 API，下面我們通過源碼來看幾個常用的 API。
1.源碼 sds.c 文件中 sdsfree 函數定義如下：
- /* Free an sds string. No operation is performed if 's' is NULL. */
- void sdsfree(sds s) {
- if (s == NULL) return;
- s_free((char*)s-sdsHdrSize(s[-1]));
- }
2.在源碼 sds.h 文件中 sdslen 函數定義如下：
- static inline size_t sdslen(const sds s) {
- unsigned char flags = s[-1];
- switch(flags&SDS_TYPE_MASK) {
- case SDS_TYPE_5:
- return SDS_TYPE_5_LEN(flags);
- case SDS_TYPE_8:
- return SDS_HDR(8,s)->len;
- case SDS_TYPE_16:
- return SDS_HDR(16,s)->len;
- case SDS_TYPE_32:
- return SDS_HDR(32,s)->len;
- case SDS_TYPE_64:
- return SDS_HDR(64,s)->len;
- }
- return 0;
- }
上面兩個是 SDS 底層對應的 sdsfree 和 sdslen 函數，用于釋放 SDS 空間和獲取 SDS 的長度。
3.在源碼 sds.c 文件中創建 sds 的函數定義如下：
- /* Create an empty (zero length) sds string. Even in this case the string
- * always has an implicit null term. */
- sds sdsempty(void) {
- return sdsnewlen("",0);
- }
- /* Create a new sds string starting from a null terminated C string. */
- sds sdsnew(const char *init) {
- size_t initlen = (init == NULL) ? 0 : strlen(init);
- return sdsnewlen(init, initlen);
- }
上面兩個是 SDS 底層對應的 sdsempty 和 sdsnew 函數，顧名思義就是創建空的 SDS 和創建一個新的 SDS 字符串。
03、總結
這篇文章阿粉跟大家介紹了一下 Redis 的 SDS 和 SDS 底層的組成結構，并且與 C 語言傳統字符串進行的詳細的對比，闡述了 SDS 出現解決了哪些問題，最后帶大家從源碼中簡單的看了幾個底層的函數實現。
在走向骨灰級程序員的道路上，阿粉我從不懈怠，充滿斗志，那么你呢?是否跟阿粉一樣，對未來充滿期待!
今天是 2020 年的第一個周末，所以你想怎么過能?歡迎加入到我們 Java 極客技術的知識星球中進行留言，我們共同進步成長。
04、參考文檔
https://github.com/antirez/redis
https://redis.io/
《Redis 設計與實現(第二版)》——黃建宏
