SDS（Simple Dynamic Strings, 簡單動態字串）是 Redis 的一種基本資料結構，主要是用于存盤字串和整數， 這篇文章里，我們就來探討一下 Redis SDS 這種資料結構的底層實作原理，
學習之前，首先我們要明確，Redis 是一個使用 C 語言撰寫的鍵值對存盤系統，
前置思考
我們首先考慮一個問題，如何實作一個二進制安全的字串？
在 C 語言中，\0 表示字串結束，如果字串中本身就包含 \0 字符，那么字串就會在 \0 處被截斷，即非二進制安全；若通過使用一個 len 屬性，來判斷字串是否結束，就可以保證讀寫字串時不受到 \0 的影響，則是二進制安全，同時 len 屬性也能保證在 O(1) 時間內獲取字串的長度，
Redis 3.2 以前的 SDS 實作
在 Redis 3.2 版本以前，SDS 的結構如下：
struct sdshdr { unsigned int len; unsigned int free; char buf[];};其中，buf 表示資料空間，用于存盤字串；len 表示 buf 中已占用的位元組數，也即字串長度；free 表示 buf 中剩余可用位元組數，
欄位 len 和 free 各占 4 位元組，緊接著存放字串，
這樣做有以下幾個好處：
•用單獨的變數 len 和 free，可以方便地獲取字串長度和剩余空間；•內容存盤在動態陣列 buf 中，SDS 對上層暴露的指標指向 buf，而不是指向結構體 SDS，因此，上層可以像讀取 C 字串一樣讀取 SDS 的內容，兼容 C 語言處理字串的各種函式，同時也能通過 buf 地址的偏移，方便地獲取其他變數；•讀寫字串不依賴于 \0，保證二進制安全，
但其實以上的設計是存在一些問題的，對于不同長度的字串，是否有必要使用 len 和 free 這 2 個 4 位元組的變數？4 位元組的 len，可表示的字串長度為 2^32，而在實際應用中，存放于 Redis 中的字串往往沒有這么長，因此，空間的使用上能否進一步壓縮？
那么接下來，我們就來看看最新的 Redis 是如何根據字串的長度，使用不同的資料結構進行存盤的，
Redis SDS 最新實作
在 Redis 3.2 版本之后（v3.2 - v6.0），Redis 將 SDS 劃分為 5 種型別：
•sdshdr5：長度小于 1 位元組•sdshdr8：長度 1 位元組•sdshdr16：長度 2 位元組•sdshdr32：長度 4 位元組•sdshdr64：長度 8 位元組
Redis 增加了一個 flags 欄位來標識型別，用一個位元組(8 位)來存盤，
其中：前 3 位表示字串的型別；剩余 5 位，可以用來存盤長度小于 32 的短字串，
struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 前3位存盤型別，后5存盤長度 */ char buf[]; /* 動態陣列，存放字串 */};
而對于長度大于 31 的字串，僅僅靠 flags 的后 5 位來存盤長度明顯是不夠的，需要用另外的變數來存盤，sdshdr8、sdshdr16、sdshdr32、sdshdr64 的資料結構定義如下，其中 len 表示已使用的長度，alloc 表示總長度，buf 存盤實際內容，而 flags 的前 3 位依然存盤型別，后 5 位則預留，
注意，一般情況下，結構體會按照所有變數大小的最小公倍數做位元組對齊，而用 packed 修飾后，結構體則變為 1 位元組對齊，這樣做的好處有二：一是節省記憶體，比如 sdshdr32 可節約 3 個位元組；二是 SDS 回傳給上層的是指向 buf 的指標，此時按 1 位元組對齊，所以可在創建 SDS 后，通過 (char*)sh+hdrlen 得到 buf 指標地址，也可以通過 buf[-1] 找到 flags，
以上，Redis 根據字串長度的不同，選擇對應的資料結構進行存盤，接下來，我們就來看看 Redis 字串的相關 API 實作，
SDS API 實作
1. 創建字串
創建 SDS 的大致流程是這樣的：首先根據字串長度計算得到 type，根據 type 計算頭部所需長度，然后動態分配記憶體空間，
注意：
1.創建空字串時，SDS_TYPE_5 被強制轉換為 SDS_TYPE_8（原因是創建空字串后，內容可能會頻繁更新而引發擴容操作，故直接創建為 sdshdr8）2.長度計算有 +1 操作，因為結束符 \0 會占用一個長度的空間，3.回傳的是指向 buf 的指標 s，
2. 清空字串
SDS 提供了兩種清空字串的方法，
一種是通過 s 偏移得到結構體的地址，然后呼叫 s_free 直接釋放記憶體，
另一種是通過重置 len 屬性值而達到清空字串的目的，本質上 buf 并沒有被真正清除，新的資料會直接覆寫 buf 中原有的資料，無需申請新的記憶體空間，
void sdsclear(sds s) { // 將len屬性置為0 sdssetlen(s, 0); s[0] = '\0';}3. 拼接字串
SDS 拼接字串的實作如下：
sds sdscatsds(sds s, const sds t) { return sdscatlen(s, t, sdslen(t));}可以看到 sdscatsds 內部呼叫的是 sdscatlen，
而 sdscatlen 內部的實作相對復雜一些，由于拼接字串可能涉及 SDS 的擴容，因此 sdscatlen 內部呼叫 sdsMakeRoomFor 對拼接的字串做檢查：若無需擴容，直接回傳 s；若需要擴容，則回傳擴容好的新字串 s，
SDS 的擴容策略是這樣的：
1.若 SDS 中剩余空閑長度 avail 大于或等于新增內容的長度 addlen，無需擴容，2.若 SDS 中剩余空閑長度 avail 小于或等于 addlen，則分情況討論：新增后總長度 len+addlen < 1MB 的，按新長度的 2 倍擴容；新增后總長度 len+addlen >= 1MB 的，按新長度加上 1MB 擴容，
總結
1.SDS 回傳的是指向 buf 的指標，兼容了 C 語言操作字串的函式，讀取內容時，通過 len 屬性來限制讀取的長度，不受 \0 影響，從而保證二進制安全；2.Redis 根據字串長度的不同，定義了多種資料結構，包括：sdshdr5/sdshdr8/sdshdr16/sdshdr32/sdshdr64，3.SDS 在設計字串修改出會呼叫 sdsMakeRoomFor 函式進行檢查，根據不同情況進行擴容，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/59815.html
標籤：Java