redis 原理系列之–字元串存儲的實現原理（1）

• 2019 年 10 月 3 日
• 筆記

背景

redis功能強大，幾乎已經成了現代大中型服務必備的快取技術了。 除了十分給力的快取功能，redis當做消息隊列，資料庫也有著不錯的表現。

我們都知道，redis 有五種數據類型，string，list， hash， set 和zset。 其中 最基本的，同時也是最常用的 就是string了。 本文就來談談 redis內部，string 的實現原理：SDS（simple dynamic string）。

redis簡單動態字元竄：SDS

• 在redis里，C語言的字元竄只用來放字元串字面量，即只有當無序對字元串修改的時候才用C的字元串，例如列印日誌的時候。
• 除了基本的字元串存儲之外，sds還用做緩衝區。AOF模組的緩衝區，和客戶端狀態的輸入緩衝區，都是sds實現的。

SDS 定義

struct sdshdr {        // buf 中已佔用空間的長度      int len;        // buf 中剩餘可用空間的長度      int free;        // 數據空間      char buf[];  };

圖示如下：

• 簡單解釋一下： buf是一個位元組數組，是用來放具體數據的。其長度是按一定策略伸縮的，具體解釋在下面。 len 表示buf 中已經使用掉的長度，free表示 buf中尚未使用的長度。

• buf內 sds 的字元串，總是以空字元結尾，這一點同c字元串一致。 因此sds 可以直接重用一部分c字元串函數庫的函數。

SDS 與C字元串的對比 和優點

1，O(1) 獲取字元串長度

• 因為sds已經存了數據的長度，所以獲取字元串長度複雜度為O（1），而C字元串獲取長度為O（n）。

2，杜絕緩衝區溢出導致的記憶體問題

• 假設記憶體區域有s1：「hi」，s2： 「redis」 兩個字元串，位置緊鄰，如下圖：

• 此時需要給s1 追加一個「boy」， 如果是C字元串，忘記了在追加之前先給s1 分配空間，此時追加將導致 s2的值被意外的修改。 而使用 sds則不會有這個問題。 因為其封裝好的函數，會在追加數據之前先檢查 空間是否夠用，如果不夠用就擴容。

3，通過空間預分配和空間惰性釋放 減少記憶體分配問題

• 當給sds的值追加一個字元串，而當前的剩餘空間不夠時，就會觸發sds的擴容機制。擴容採用了空間預分配的優化策略，即分配空間的時候：如果sds 值大小< 1M ,則增加一倍； 反之如果>1M , 則當前空間加1M作為新的空間。

• 當sds的字元竄縮短了，sds的buf內會多出來一些空間，這個空間並不會馬上被回收，而是暫時留著以防再用的時候進行多餘的記憶體分配。這個是惰性空間釋放的策略

4， 二進位安全

• c字元串必須符合某種編碼（例如ASCII），且不能包含空字元。 這些限制使得 c字元竄不能保存圖片，音頻等二進位文件。 而sds的api 都是二進位安全的，其所有api 都會以處理二進位的方式來處理buf內的數據，所以不會有任何的限制。

SDS 的API介面列表

總結

sds 其實就是字元串數組的一個封裝，但是由於考慮了多種場景，作者給它適配了多個高效、優雅的介面，使得 sds成為了一個存儲字元串的優秀設計。使得sds成為一個獨立的、可提供高效優質服務的基礎實體。

我們在設計一些偏底層的數據結構、對象、甚至是資料庫表的時候，可以參考sds的設計，從中尋找一些啟發。

參考： 《Redis 設計與實現》 黃健宏

有收穫就點個贊吧~