緩存中間件-再談redis的基礎數據類型SDS

世界上並沒有完美的程序，但是我們並不因此而沮喪，因爲寫程序就是一個不斷追求完美的過程。

redis是C語言編寫的，但是爲了更好的實用性，在其基礎上又進行了封裝。其中SDS簡單動態字符串就是一個典型的實現。與C語言字符串結構的對比如下：

圖1 C語言的字符串的結構

圖2 Redis自定義的字符串的結構

由上圖可知，與C語言原生的字符串結構相比，Redis自定義的簡單動態字符串增加了預分配空間free與字符串長度len的記錄，並且通過buf[]存儲字符串的值。

這樣做有三個好處，第一，獲取字符串長度的時間複雜度縮短爲O(1)；第二，可以通過預分配空間與空間的惰性釋放減少空間重分配的次數；第三，二進制安全。

首先對於SDS縮短字符串長度獲取的時間複雜度。當我們要將一個字符串比如「redis」存儲到redis中時，redis首先會判斷這個字符串的長度，然後根據字符串長度分配對應大小的內存空間，即字符串長度加1，其中多出的1是空字符’\0’，在C語言中用空字符’\0’來代表一個字符串的結尾，但是在redis中卻並不是如此，redis中以’\0’結尾是爲了複用C語言的一些函數功能，這一點需要注意。同時將字符串的長度5存儲到len字段中，並且由於還沒有預分配的空間所以free的值爲0。這樣第一個字符串就存儲到redis中了。以上過程除了要記錄字符串長度以外與C語言字符串的存儲過程是一致的。但就是因爲存儲了len的值，所以在我們要獲取字符串長度時，就可以直接取len的值而無需遍歷整個字符串，使得獲取字符串長度這個函數的時間複雜度從O(n)縮短爲了O(1)，並且還有一個好處，就是當我們要對當前字符串執行拼接等操作時，可以預先根據記錄的len值判斷內存空間是否足夠，從而避免內存溢出。

然後對於預分配空間與空間的惰性釋放。接下來，如果我們想要對這個字符串執行拼接操作，將"good"拼接到"redis"字符串後面，在拼接之前首先判斷一下free預分配空間是否足夠，即free的值的大小是否大於等於要存儲的字符串"good"的長度，如果預分配空間不足則需要分配內存空間，內存空間分配好以後，將字符串"good"拼接到字符串"redis"後面，並且更新拼接後字符串的長度len爲9，同時預分配9字節長度的空閒內存空間，並將free的值更新爲9，這樣不僅將"good"拼接到了"redis"後面，將字符串更新爲"redisgood"，而且還預分配9字節長度的空閒空間。如果下次要拼接一個字符串"hello"，會首先判斷預分配空間是否足夠，因爲"hello"的長度爲5，而預分配空間的大小爲9，所以可以直接將"hello"拼接到"redisgood"字符串後面而無需調用底層去分配新的空間了，這樣就減少了底層分配空間的次數，而底層分配內存空間時必然會花費一定的時間，通過這種方式減少底層分配空間的次數，也節省了字符串寫入的時間。空間惰性釋放也是同樣的道理，當我們要縮短字符串的長度時，空出來的空閒空間並不會立即被回收，而是加入到free預分配空間中，這樣後續字符串長度如果變長時如果預分配空間足夠就無需底層再次重新分配內存空間了，節省了內存回收和分配兩次空間重分配的次數的時間，可以大大提高寫操作的效率。當然，redis也提供了api供我們手動釋放預分配空間。最後，對於free預分配空間大小的規則進行介紹：當擴容操作後len的值小於1M時，預分配空間的大小與len相等；當len的值大於1M時，預分配空間的大小爲1M。

最後對於二進制安全。由於在SDS中記錄了字符串的長度，所以我們在判斷一個字符串的範圍時，並不需要以空字符’\0’作爲結尾的標誌，完全可以通過len判斷一個完整字符串的開頭和結尾，所以，當我們存入二進制的數據時，有時一些特殊的字符如空字符’\0’只是作爲數據的一部分存在並不標誌字符串的結尾，如果使用原生的C語言字符串存儲，將’\0’當作結尾標誌，那麼取出的值，可能就是不完整的，但是如果用redis的SDS結構就不會受到特殊字符’\0’的干擾，只根據len判斷存儲數據的範圍，能夠準確的獲取到存儲的完整數據，所以說SDS結構是二進制安全的。

本節通過對redis SDS結構的介紹以及對字符串的操作實例，形象的描述了SDS結構在操作字符串時的優勢，通過free、len、buf[]這種三屬性的記錄方式，奠定了redis安全高效處理字符串的基礎。

更多信息，請關注公衆號：