面試問 Redis 的字串原理是什麽？答不出被 Pass 了！

2024-05-23碼農

引言：在 Redis 中，並沒有使用 C 標準庫提供提供的字串，而是實作了一種動態字串，即 SDS (Simple Dynamic String)，然後透過這種數據結構來表示字串，面試中除了基本數據型別讓你去講解，此外還會講1-2種數據結構的底層原理和優勢。

題目

redis 的字串為什麽要升級 SDS，而不用 C 語言字串？

推薦解析

C 語言字串的缺陷

首先最直接的，為什麽不適用一個東西，其最根本的原因就是他有不好的地方， C 語言的字串其實本質上就是 char* 的字元陣列，其本身是存在一定缺陷的，首先我們來盤點一下其缺陷。

1）C 語言字元陣列的結尾位置就用「\0」表示，意思是指字串的結束

2）C 語言字元陣列獲取長度只能透過遍歷獲得，時間復雜度是 O(n)

3）字串操作函式不高效且不安全，比如緩沖區溢位，其可能導致程式異常終止

針對以上問題，C 語言在其基礎上進行了一定的改進，接下裏我們來註意進行分析。

SDS 結構

如下圖所示，SDS 數據結構分為四個部份的內容,如下圖所示

1）len （長度）:記錄了 SDS 字串陣列的長度，當需要獲取字串長度的時候，只需要返回這個成員變量的值就可以了，時間復雜度是O(1)

2）alloc（分配空間長度）:這個欄位的主要作用是指分配給字元陣列的儲存的空間大小，當需要計算剩余空間大小的時候，只需要 alloc - len 就可以直接進行計算，然後判斷空間大小是否符合修改需求，如果不滿足需求的話，就執行相應的修改操作，這樣的話就可以很好地解決我們上面所說的緩沖區溢位問題。

3）flags（表示 SDS 的型別）:一共設計了五種型別的 SDS，分別是 sdshdr 5、sdshdr 8、sdshdr 16、sdshdr 32、sdshdr 64（這個的記憶頁很簡單，就是 32 開始，128，即 2 的多少次方去記憶就可以了），這個型別的主要作用就是靈活保存不同大小的字串，從而有效節省記憶體空間。

4）buf（儲存數據的字元陣列）：主要起到保存數據的作用，如字串、二進制數據（二進制安全就是一個重要原因）等

然後在分析完 SDS 的結構之後，接下來我們來分析原因，我們可以發現，SDS 相對於 C 語言原生的字串，其多了幾個欄位，即 len、alloc、flags，這幾個欄位幫助 SDS 解決了 C 語言字串的問題：

1） 長度計算

首先是 len，他記錄了 SDS 的字串長度，因此當你需要獲取字串長度的時候，你只需要返回 len 的值就可以了，不需要再去遍歷字串，這樣操作的時間復雜度就降低了許多，直接從 O(n) 變成了 O (1)

2） 二進制安全

第二個點在於儲存的字元陣列，SDS 中進行了改進，SDS 中不在需要 \0 來判斷字串是否結束，這就是我們上面所說的 Redis 字串中的 buf 陣列可以儲存任何的二進制數據，因此儲存二進制數據的時候便不會發生字元截斷的問題，避免了由於特殊字元引發的異常，不過需要註意一個點，Redis 為了相容 C 標準庫的一些操作， Redis 仍然為末尾的 \0 預留了記憶體空間

3） 修改操作高效

其次就是 alloc 欄位了，alloc 欄位用來記錄字串預分配的記憶體大小，當發生字串修改的時候，透過 allloc - len 判斷當前空間是否足夠，如果不足夠的話就進行擴容。

然後這裏放一段 sds 擴容的程式碼，用於幫助理解

hisds hi_sdsMakeRoomFor(hisds s, size_t addlen) { ... ... // avail 值就是 allloc-len 的值 // 如果值的大小即剩余空間大於增加的字串長度，則表示空間足夠，不需要進行擴容，直接返回就可以 if (avail >= addlen) return s; //獲取當前 s 的長度大小 len = hi_sdslen(s); sh = (char *)s - hi_sdsHdrSize(oldtype); //求擴容以後 s 需要的最小長度 newlen = (len + addlen); //根據獲取到的新長度，為 s 分配新空間所需要的記憶體空間大小 if (newlen < HI_SDS_MAX_PREALLOC) //新長度 < HI_SDS_MAX_PREALLOC，這裏 HI_SDS_MAX_PREALLOC 的值為 1 MB //表示分配所需空間 2 倍的空間 newlen *= 2; else //不滿足條件的話，分配長度為目前長度 + 1MB 的空間 newlen += HI_SDS_MAX_PREALLOC; ... }

我們可以發現，當 sds 擴容的時候，其是根據 sds 的長度進行判斷的，其判斷的值就是所需要的 sds 的長度是否超過 1 MB

如果需要的 sds 長度小於 1MB 的話，其擴容規則就是翻倍擴容，即 2 倍的新長度

如果需要的 sds 長度大於等於 1 MB 的話，其擴容規則就是 newlen + 1 MB

在擴容之前，SDS 會有限檢查使用空間夠不夠使用，如果不夠使用的話，則會進行擴容處理，即分配額外的未使用空間，這樣可以有效地減少記憶體分配的次數，並且解決了緩沖區溢位的問題。

4） 按需使用，節省記憶體

最後一個要介紹的點就是 flag 欄位，和那個欄位主要分為 5 種型別，即 sdshdr5、sdshdr8、sdshdr16、sdshdr32 以及 sdshdr64 五種字串，他們分別對應儲存長度小於等於 2 的 5/8/16/32/64 次方字節的字串。

透過使用不同儲存型別的結構題，靈活保存不同大小的字串，從而節省記憶體空間，此外，Redis SDS 底層還使用了消除記憶體對齊的方式進行記憶體的最佳化，從而保證所有的成員盡可能在記憶體中相鄰，從而保證按照實際大小分配記憶體，節約記憶體的使用。

源碼版本叠代

Redis 3.2 版本以前的源碼

struct sdshdr { unsigned int len; unsigned int free; char buf[]; };

Redis 3.2 版本以後的源碼

/* Note: sdshdr5 is never used, we just access the flags byte directly. * However is here to document the layout of type 5 SDS strings. */ struct __attribute__((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ char buf[]; }; struct __attribute__((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__((__packed__)) sdshdr16 { uint16_t len; /* used */ uint16_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__((__packed__)) sdshdr32 { uint32_t len; /* used */ uint32_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__((__packed__)) sdshdr64 { uint64_t len; /* used */ uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; };