redis的5種物件與8種數據結構之字串物件（下）
簡介： 引言 本文是對《redis設計與實現(第二版)》中數據結構與物件相關內容的整理與說明。本篇文章只對物件結構，1種物件——字串物件。以及字串物件所對應的兩種編碼——raw和embstr，進行了詳細介紹。
引言
本文是對《redis設計與實現(第二版)》中數據結構與物件相關內容的整理與說明。本篇文章只對物件結構，1種物件——字串物件。以及字串物件所對應的兩種編碼——raw和embstr，進行了詳細介紹。表達一些本人的想法與看法，也希望更多朋友一起來討論，分享交流。
作者：太陽
雲掣科技-數據庫團隊
數據庫工程師
字串物件
字串物件可以儲存整數、浮點數、字串，具體策略是：
當儲存整數時，用到的編碼是int，底層的數據結構可以用來儲存long型別的整數；
當儲存字串時，如果字串的長度小於等於32位元組，那麼將用編碼爲embstr的格式來儲存；如果字串的長度大於32位元組，將用編碼爲raw的SDS格式來儲存；
當儲存浮點數時會先將浮點數轉換爲字串，如果轉換後的字串長度小於32位元組就用編碼爲embstr的格式來儲存，否則用編碼爲raw的SDS格式來儲存。
下圖是一個字串物件的結構圖，最左側是物件結構，中間跟右側合起來是raw編碼的SDS數據結構(sdshdr)，範例圖：
raw編碼，簡單動態字串(simple dynamic string-SDS)
redis用的並不是C語言傳統的字串，而是自己構建了簡單動態字串(simpledynamic string,SDS)。
當redis列印日誌資訊或輸出報錯資訊，這些輸出的字串是不會被修改的字串字面量(sting literal)，此時用的是C語言傳統的字串來儲存這些資訊的。當redis需要儲存的是可以被修改的字串時，就會使用SDS結構。
除了用來儲存數據庫中的字串值之外，SDS還被用作緩衝區(buffer)：AOF模組中的AOF緩衝區，以及用戶端狀態中的輸入緩衝區，都是由SDS實現的。
SDS的結構
SDS結構示意圖如下所示：
sdshdr是該數據結構的名稱即SDS，其中：
buf屬性，是一個位元組陣列，用來儲存字串，後面箭頭對應的就是實際儲存的字串內容，最後以’0’空字串結尾；
len屬性，記錄的是buf陣列中實際已使用的位元組數量，等於SDS所儲存字串的長度；
free屬性，記錄的是buf陣列中未使用位元組的數量。
SDS優點
一、可以用O(1)的複雜度獲取到字串長度
SDS的len屬性記錄了字串的長度，而傳統C字串要想知道長度需要遍歷整個字串。相比於傳統C字串，redis獲取字串長度所需的複雜度從O(N)降低到了O(1)。
即使對非常長的字串反覆 反復執行STRLEN命令(獲取字串長度)，也不會造成過多的效能消耗。
二、杜絕緩衝區溢位
在傳統的C字串中，如果要修改字串的內容，但修改後字串的長度超過原先的長度就會發生溢位現象。詳見下圖：
在SDS中，當需要對buf位元組陣列中儲存的內容進行修改(增添或刪除)時，API會先通過free和len屬性檢查SDS的空間是否足夠，如果不夠的話，SDS會自動擴充套件空間再對內容進行修改。關於自動擴充套件空間的策略見下方「空間預分配」的內容。
三、減少修改字串長度時所需的記憶體重分配次數
對於傳統C字串：
如果執行的是增長字串的操作，如拼接操作(append)，那麼在執行命令之前，程式需要先通過記憶體重分配來擴充套件底層數據的空間大小——否則會產生緩衝區溢位。
如果執行的是縮短字串的操作，如截斷操作(trim)，那麼在執行這個操作之後，程式需要通過記憶體重分配來釋放字串不再使用的空間——否則會產生記憶體漏失。
對於redis中的SDS結構：
記憶體重分配設計複雜的演算法，是一個比較耗時的操作，redis作爲速度要求嚴苛、數據會被頻繁執行的數據庫，如果每次修改字串都需要進行一次記憶體重分配，會嚴重影響效能。
使用SDS，buf數組裏可以包含未使用的位元組，這些位元組的數量由free屬性記錄，可以減少修改字串長度時所需的記憶體重分配次數。
空間預分配和惰性空間釋放
通過SDS中free屬性定義的未使用空間，SDS可以實現空間預分配和惰性空間釋放兩種優化策略：
1、空間預分配策略——可以降低字串增長操作引起的記憶體重分配
當需要修改SDS的內容，且需要進行空間擴充套件的時候，程式不僅會爲SDS分配修改所需的必須空間，還會爲SDS分配額外的未使用空間。
其中，額外分配的未使用空間數量由以下公式決定：
如果對SDS進行修改之後，SDS的長度(即len屬性的值)將小於1MB，那麼程式將分配和len屬性同樣大小的未使用空間，這時SDS len屬性的值將和free屬性的值相同。
如果對SDS進行修改後，SDS的長度將大於等於1MB，那麼程式會分配1MB的未使用空間。
說明
如果對一個字串的末尾持續追加內容，當字串整體大小大於1MB時，即使只追加一位元組的字元，程式也會額外分配1MB的空間，當再次追加一位元組的字元時，程式不會再額外分配1MB的空間，而是使用已有的空閒空間。
即在擴充套件空間之前，會先檢查未使用的空間是否足夠，如果足夠，是不會額外再擴充套件的。
通過空間預分配策略，SDS將連續增長N次字串所需的記憶體重分配次數從必定N次降低爲最多N次。
2、惰性空間釋放策略——可以降低字串縮短操作引起的記憶體重分配
當SDS中的字串長度被縮短時，程式並不會立即使用記憶體重分配來回收縮短後多出來的位元組空間，而是使用free屬性將這些位元組的數量記錄起來，以備將來使用。
當然，redis提供了相應的命令來真正釋放這些未使用空間，避免不必要的記憶體浪費。
四、二進制安全
C字串中的字元必須符合某種編碼(比如ASCII)，並且除了字串的末尾之外，字串裏面不能包含空字元，如果字串除末尾外還有其它空字元，那麼最先被程式讀入的空字元將被誤認爲是字串結尾，這些限制使得C字串只能儲存文字數據，而不能儲存圖片、音訊、視訊、壓縮檔案這樣的二進制數據。
爲了確保redis可以適用於各種不同的使用場景，SDS的API都是二進制安全的(binary-safe)，所有SDS API都會以處理二進制的方式來處理SDS存放buf數組裏的數據，程式不會對其中的數據做任何限制、過濾或者假設，數據在寫入時是什麼樣的，它被讀取時就是什麼樣。
這也是RDS的buf屬性被稱爲位元組陣列的原因——redis不是用這個陣列來儲存字元，而是用它來儲存一系列二進制數據。
五、相容部分C字串函數
SDS遵循空字串結尾這一慣例，好處是可以直接重用C字串函數庫裡的函數，從而避免了不必要的程式碼重複。
embstr編碼
如果字串物件儲存的是長度小於等於32位元組的字串，那麼將會使用embstr編碼，embstr編碼是專門用來儲存短字串的一種優化編碼方式。embstr編碼與raw編碼對應的字串物件，都是由物件結構(redisObject)和數據結構(sdshdr)組成的。
區別在於用raw編碼的字串物件會呼叫兩次記憶體分配函數來分別建立redisObject結構和sdshdr結構，而embstr編碼則通過呼叫一次記憶體分配函數來分配一塊連續的空間，空間中一次包含redisObject和sdshr兩個結構，embstr編碼的字串物件結構圖如下所示：
兩者的區別
embstr編碼的字串物件在執行命令時，產生的效果和raw編碼的字串物件執行命令時產生的效果是相同的的，但使用embstr編碼的字串物件來儲存短字串值有以下好處：
1、embstr編碼將建立字串物件所需的記憶體分配次數從raw編碼的兩次降低爲一次；
2、釋放embstr編碼的字串物件只需要呼叫一次記憶體釋放函數，而釋放raw編碼的字串物件需要呼叫兩次記憶體釋放函數；
3、embstr編碼的字串物件的所有數據都儲存在一塊連續的記憶體裡，結構更加緊湊，而raw編碼是分散開的，redisObject物件結構和sdshdr數據結構彼此間是用指針相關聯的，embstr編碼的物件比raw編碼的物件能夠更好的利用快取帶來的優勢。
編碼的轉換
int編碼的字串物件和embstr編碼的字串物件在條件滿足的情況下，會被轉換成raw編碼的字串物件。encoding命令可以檢視鍵對應的值，底層用的是什麼編碼。
int轉換爲raw
對於int編碼的字串物件來說，如果我們向物件執行了一些命令，使得這個物件儲存的不再是整數值，而是一個字串值，那麼字串物件的編碼將從int變爲raw。
27.0.0.1:6379> set a 100 //設定a=100
OK
127.0.0.1:6379> object encoding a //檢視鍵a儲存的值用的是什麼編碼
"int"
127.0.0.1:6379> append a 'a' //向鍵a的值中追加內容’a’，此時鍵a儲存的值將變爲字串型別
(integer) 4
127.0.0.1:6379> get a //查詢鍵a的值
"100a"
127.0.0.1:6379> object encoding a //檢視鍵a儲存的值現在對應的編碼，發現已經變爲raw格式的編碼，表示裏面現在儲存的是字串
"raw"
int編碼的字串，儲存的是long型別的整數，範圍是2^63-1(2的63次方減一) ~ -2^63(2的63次方)，當儲存的整數在該範圍內時，編碼爲int，當值超過該範圍，編碼將轉換爲embstr。
27.0.0.1:6379> set number1 9223372036854775807
OK
127.0.0.1:6379> object encoding number1
"int"
127.0.0.1:6379> set number2 9223372036854775808
OK
127.0.0.1:6379> object encoding number2
"embstr"
127.0.0.1:6379> set number3 -9223372036854775808
OK
127.0.0.1:6379> object encoding number3
"int"
127.0.0.1:6379> set number4 -9223372036854775809
OK
127.0.0.1:6379> object encoding number4
"embstr"
embstr轉換爲raw
embstr編碼的字串物件無法被修改(redis沒有爲embstr編碼的字串物件編寫任何響應的修改程式)，只有int、raw編碼的字串物件可以被修改，所以embstr編碼的字串實際上是隻讀的。
當對embstr編碼的字串物件執行任何修改命令時，程式都會先將物件的編碼從embstr轉換爲raw，然後再執行修改命令。所以一旦embstr編碼的字串被修改，它的數據結構就會變成raw編碼的格式。
127.0.0.1:6379> set a 'ab'
OK
127.0.0.1:6379> object encoding a
"embstr"
127.0.0.1:6379> append a 'c'
(integer)
3127.0.0.1:6379> get a
"abc"
127.0.0.1:6379> object encoding a
"raw"
以上就是根據《redis設計與實現(第二版)》中數據結構與物件相關內容進行的部分整理與分享，歡迎各位共同參與討論一起交流溝通。
