Redis面試都卷到C語言去了......
Redis 面試都卷到 C 去了。有個小伙伴在前兩天找松哥模面的時候如是說到。
是啊，沒辦法，自從 Java 八股文這個概念被提出來并且逐步在 Java 程序員中強化之后，現(xiàn)在各種各樣的八股文手冊，有免費的有付費的，琳瑯滿目。
單純的八股文已經(jīng)區(qū)分不出 Java 猿水平的高低了，所以現(xiàn)在面試總會卷出新高度。
這次是小伙伴面試時候被問到一個 SDS 的問題，也就是 Redis 中 String 字符串的底層實現(xiàn)原理。
我來和小伙伴們簡單聊一聊這個話題。
一 String 類型
Redis 中有一個 String 類型，使用頻率還比較高，我們?nèi)粘Ｗ鼍彺?、分布式鎖都會用到。
很多小伙伴也都知道 Redis 是用 C 寫的，那么就有一個問題，Redis 中的 String，底層數(shù)據(jù)結(jié)構(gòu)是什么樣的？
是不是就是 C 中的 String 呢？
二 C 中的 String
玩過 C 的小伙伴應(yīng)該知道，C 語言本身并沒有內(nèi)置的 String 類型，但是 C 語言中可以使用字符數(shù)組（char array[]）或指向字符的指針（char *pointer）來表示字符串。在 C 語言中，字符串是以空字符 '\0' 結(jié)尾的字符序列。例如：
char *str1 = "Hello, World!";在這個例子中，str1 是一個指向字符串字面量 "Hello, World!" 的指針。
當(dāng)我們在 Redis 中使用 String 的時候，很多小伙伴可能會想這個 String 可能就是 C 中的 String 吧？并不是！
為什么不直接使用 C 中的 String 呢？主要有以下幾種考慮：
- char* 這種方式無法直接獲取到字符串的長度，只能逐個字符去遍歷，很明顯效率低。
- C 中的字符串使用 \0 去表示字符串結(jié)束，這就導(dǎo)致我們沒法在字符串中存儲二進(jìn)制數(shù)據(jù)，因為二進(jìn)制中的數(shù)據(jù)可能會和 \0 沖突。
- C 中字符串在創(chuàng)建的時候長度和內(nèi)存大小就都確定下來了，后期如果縮容和擴(kuò)容都是創(chuàng)建新數(shù)組然后拷貝內(nèi)容，操作方式過于麻煩。
有鑒于此，Redis 自己搞了個 SDS，全稱是 Simple Dynamic String。這個 SDS 和 C 中的字符串的關(guān)系，有點像我們 Java 中 List 和數(shù)組的關(guān)系，有點。
三 SDS
為了解決上述問題，小伙伴們可以先想想，我們都需要哪些東西呢？
- 首先得有一個存儲字符的 char 數(shù)組吧。
- 數(shù)組的總長度得有一個變量記錄下來吧。
- 數(shù)組已經(jīng)使用的長度得記錄下來吧。
這是三個最基本的屬性。
3.1 SDS 類型
當(dāng)然在具體實踐中還有一個 flags 屬性，這個屬性用來表示 SDS 的類型，因為 Redis 設(shè)計了幾種不同的 SDS 類型，這樣的設(shè)計主要是為了節(jié)省內(nèi)存。
圖片
從這里可以看到，一共有五種不同的 SDS 類型，分別是：
- sdshdr5
- sdshdr8
- sdshdr16
- sdshdr32
- sdshdr64
從注釋中可以看到，sdshdr5 其實沒有使用，另外四個的區(qū)別主要在于數(shù)組長度和分配空間長度的差異。
以 sdshdr16 為例，uint16_t 表示 16 位無符號 int 值，能表示的最大值是 2^16-1，所以它的 buf 數(shù)組的最大長度就是 2^16。
按照這樣的設(shè)計，其實 Redis 的字符串能夠存儲超大的字符串，例如，sdshdr32 類型意味著能夠存儲的字符長度是 2^32，一個字符占一個字節(jié)，就是 4GB。
可是實際上 Redis 的字符串存不了這么長的，Redis 內(nèi)部會對字符串的長度進(jìn)行限制，最大是 512MB。
當(dāng)然實際生產(chǎn)中我們不建議這么搞，一般字符串最好不要超過 1MB。
3.2 編碼格式
為了提升效率，SDS 中使用的編碼格式也會根據(jù)情況來定。
- 如果是數(shù)字類型，且數(shù)字長度小于 20，就會使用 int 編碼。
圖片
- 長度小于等于 44 字節(jié)的字符串，使用 embstr 編碼。
- 長度大于 44 字節(jié)的字符串使用 raw 編碼。
圖片
3.3 其他特點
不同于 C 中的字符串，SDS 可以存儲二進(jìn)制數(shù)據(jù)，因為 SDS 不再通過 \0 去判斷字符串結(jié)束，因為有一個 len 變量存儲了字符串的長度。
同時，SDS 在字符串?dāng)U容的時候也會進(jìn)行預(yù)分配，這些機(jī)制類似于咱們 Java 中 ArrayList 擴(kuò)容、HashMap 擴(kuò)容，擴(kuò)容時會預(yù)留空間，避免頻繁擴(kuò)容。
同時，縮容的時候并不會立馬釋放多余空間，防止后續(xù)又要擴(kuò)容。
