一、Redis基本操作——String(原理篇)

小喵的嘮叨話：最近京東圖書大減價，小喵手癢了就買了本《Redis設計與實現》[1]來看看。這裡權當小喵看書的筆記啦。這一系列的模式，主要是先介紹Redis的實現原理（可能很大一部分會直接照搬原作者的描述），加上小喵自己的想法，之後配合Redis官網上的各種相關的操作命令（原書上貌似沒有很多的介紹命令）。

小喵的個人博客地址: http://miaoerduo.com, 隨時歡迎各位的大駕。

本章介紹Redis中最常用到的字元串(String)。

Redis的字元串(String)的實現

小喵之前有看到過《Redis設計與實現》的一部分章節。這是第一章的內容，小喵也是因為看了這一章的內容，才決定要買本仔細研究的。

首先，我們知道Redis是由C語言編寫的，以高效和輕量著稱。而C語言中的字元串是怎麼實現的呢？字元數組。

比如一個簡單的字元串”hello world”，其實是一個如下的字元的數組：

[‘h’, ‘e’, ‘l’, ‘l’, ‘o’, ‘ ‘, ‘w’, ‘o’, ‘r’, ‘l’, ‘d’, ‘\0’]

最後的一個’\0’是空字元，表示字元串的結尾。

Redis由於各種原因，並沒有直接使用了C語言的字元串結構，而是對其做了一些封裝，得到了自己的簡單動態字元串(simple dynamic string, SDS)的抽象類型。Redis中，預設以SDS作為自己的字元串表示。只有在一些字元串不可能出現變化的地方使用C字元串。

SDS的定義如下：

可以看出來，SDS的結構並不複雜。

buf是一塊可用的記憶體空間，通常大小會大於等於需要存儲的字元串的大小（大於？為什麼要大於呢？讀者可以思考一下）。

len表示字元串的長度，也表示buf中已經被使用的空間的大小。

free表示buf中沒有被使用的空間的大小。

要註意的是，buf的大小等於len+free+1，其中多餘的1個位元組是用來存儲’\0’的。

那麼這麼封裝到底有什麼好處呢？我們一點一點剖析。

1，常數複雜度獲取字元串長度

在C語言中的字元串只是簡單的字元的數組，當使用strlen獲取字元串長度的時候，C語言內部其實是直接順序遍曆數組的內容，找到對應的’\0’對應的字元，從而計算出字元串的長度。顯然這個演算法複雜度和字元串的長度成正比，即O(N)。而對於SDS來說，只需要訪問SDS的len屬性就能得到字元串的長度，複雜度為O(1)。這樣，獲取字元串長度的操作就不會成為Redis的瓶頸（當然len的作用不止這麼簡單，後面還會介紹別的）。

2，杜絕緩衝區溢出

我們知道C++裡面的字元串使用了STL的string類型，我們開發者不太需要關註記憶體的分配和釋放的過程。但是Redis是C語言編寫的，並沒有這麼方便的數據類型。對於字元串的拼接、複製等操作，C語言開發者必須確保目標字元串的空間足夠大，不然就會出現溢出的情況。

上面的三句代碼，就是C語言的字元串拼接和複製的使用，但是明顯出現了緩衝區溢出的問題。字元數組a的長度是10，而”hello world”字元串的長度為11，則需要12個位元組的空間來存儲（不要忘記了’\0’）。

然後，我們看看Redis的SDS是怎麼處理字元串修改的這種情況。

當使用SDS的API對字元串進行修改的時候，API內部第一步會檢測字元串的大小是否滿足。如果空間已經滿足要求，那麼就像C語言一樣操作即可。如果不滿足，則拓展buf的空間，使得滿足操作的需求，之後再進行操作。每次操作之後，len和free的值會做相應的修改。

這就是SDS的全部的高明之處了嗎？當然不！

當API發現SDS的buf的容量不夠的時候，並不是簡單申請正好適合的大小，而是額外申請了一倍的空間！我們以sds的API sdscat函數為例，該函數實現了sds的拼接的功能。

下麵的例子是”hello” 和” world”的拼接的過程。

圖1 sdscat執行之前的sds

圖2 sdscat執行之後的sds

這裡的buf的容量是23（free + len + 1）。為什麼要這麼做呢？耐心向下看吧。

3，減少修改字元串時帶來的記憶體重分配次數

我們之前說到，對於一個N長的字元串，C語言中底層是一個N+1長的字元數組（有一個位元組存放空字元）。C字元串的長度和底層數組之間的長度存在著這樣的關係，因此當進行字元串的操作而導致字元串長度發生變化的時候，需要對記憶體進行重新分配。

如果操作會增長字元串，那麼在執行之前，就需要進行記憶體分配擴充底層數組的大小。如果是縮短字元串的操作，則需要釋放額外的記憶體（這是書中的意思，但小喵覺得如果字元串縮小的話，其實並不用立刻釋放記憶體，如果字元串是malloc出來的話，需要釋放的直接free就可以，也不需要給定空間的大小，所以不會出現記憶體泄露。當然，也可能Redis裡面是用別的方式實現，這樣小喵就不懂了）。

對於一般的程式而言，如果修改字元串的操作並不是特別常出現，那麼每次修改都重新分配一下記憶體也是可以接受的。但是Redis作為一個資料庫，其讀寫速度，數據修改頻率都被要求達到很高的效率。因此這種低效的方式並不適合Redis。

為了避免C字元串的這些弊端，SDS通過未使用空間解除了字元串長度和底層數組長度之間的關係。也就是之前說的buf的長度為len和free之和（再加1）。數字裡面可以包含未使用的空間，大小用free表示。

Redis主要通過以下兩種策略來處理記憶體問題。

i) 空間預分配

這種方式用於處理字元串長度增加的問題。如果對字元串的修改使得字元串的長度增加，API首先會判斷buf的空間大小是否滿足，如果滿足則直接操作，如果不滿足，則進行如下操作：

如果對SDS進行修改之後的，SDS的長度（即len的值）小於1MB。程式將額外分配和len一樣大小的未使用空間。以上面的”hello” + ” world”的操作為例。在這個例子中”hello”的len是5（不考慮’\0′)，修改之後的字元串”hello world”長度為11，那麼新的SDS的buf的容量就是11*2+1。其中len和free都是11，多餘的1位元組用來存儲’\0’。

如果對SDS修改之後的長度大於1MB，那麼程式會分配1MB的未使用空間。比如原數據是5MB，修改之後需要6MB的空間，進行修改的操作後，buf的實際空間應該是7MB，其中len為6MB，free為1MB。

那麼這些未使用空間能夠做什麼呢？為什麼根據SDS的修改會的大小會有兩種不同的分配原則呢？

小喵是這麼認為的，如果數據被更改，則說明這個數據很可能會被再次更改，如果能夠提前分配多餘的空間，那麼下一次變化的時候很可能就不需要再次分配空間了。如果數據比較小（<1MB）的時候，可以分配等大的未使用空間。但是如果數據已經很大的時候（>1MB），再分配同等大小的記憶體會顯得十分浪費，畢竟不能確保這個字元串一定會被再次修改，所以只額外分配1MB的空間。

通過這種策略，SDS可以做到N次修改，最多進行N次記憶體分配。而C字元串在N次修改則一定要進行N次記憶體分配。一個是至多N次，一個是一定N次。用小喵的腦袋想，也覺得SDS這個策略簡單、粗暴、高效。

ii) 惰性空間釋放

當執行字元串長度縮短的操作的時候，SDS並不直接重新分配多出來的位元組，而是修改len和free的值（len相應減小，free相應增大，buf的空間大小不變化）。通過惰性空間釋放，可以很好的避免縮短字元串需要的記憶體重分配的情況。而且多餘的空間也可以為將來可能有的字元串增長的操作做優化。

當然，SDS也提供直接釋放未使用空間的API，在需要的時候，也能真正的釋放掉多餘的空間。

4，二進位安全

C字元串中的字元必須符合某種編碼（比如ASCII），並且字元串除了末尾之外不能出現空字元，否則會被程式認為是字元串的結尾。這就使得C字元串只能存儲文本數據，而不能保存圖像，音頻等二進位數據。（這裡，小喵的觀點是不同的，小喵本人是做圖像的，opencv等的庫，都是使用unsigned char*來存儲圖像的數據。我們完全可以把字元數組看成一堆記憶體，存放任何數據都可以）

使用SDS就不需要依賴控制符，而是用len來指定存儲數據的大小。同時所有的SDS操作的API都是二進位安全的（binary-safe），所有的SDS API都會以處理二進位的方式來處理SDS的buf的數據。程式不會對buf的數據做任何限制、過濾或假設，數據寫入的時候是什麼，讀取的時候依然不變。

這也是我們將SDS的buf屬性程式位元組數組的原因，Redis不是使用這個數組來保存字元，而是儲存一系列二進位數據。

5，相容部分C字元串函數

由於SDS的buf的定義和C字元串完全相同，因此很多的C字元串的操作都是適用於SDS->buf的。比如當buf裡面存的是文本字元串的時候，printf函數，也完全可以試用。這樣，Redis就不需要為所有的字元串的處理編寫自己的函數，大多數通過調用C語言的函數就可以。

總結

以上則是Redis的string結構的原理部分。下一章我們會介紹一些string操作的redis命令。

轉載請註明出處。

參考：

[1]http://redisbook.com/