Redis01-Redis的數據結構之簡單動態字符串SDS

前言

Redis用了這么久，一直沒有認真的去了解其內部的數據結構和實現原理。從今天開始正式系統性的學習Redis。首先，還是從工作中經常打交道的數據類型開始說起，然后，在說到其內部使用的數據結構。

Redis的簡介

Redis是一個開源的高性能的key-value數據庫，與其他的key-value緩存產品相比有以下三個特點：

Redis支持數據的持久化，可以將內存中的數據持久化到硬盤中，主要有RDB和AOF兩種方式。

Redis 不僅僅支持簡單的key-value類型的數據，還提供了list、set、zset、hash等數據類型的存儲。

Redis支持數據的備份，即master-slaver模式的數據備份。

數據類型

Redis支持5種數據類型：如下表所示：

數據結構

Redis中有如下幾種數據結構。分別是：

簡單動態字符串（sds）

鏈表

字典

跳躍表

整數集合

壓縮列表

Redis的key是頂層模型，它的value是扁平化的，Redis中，所有的value都被包裝成一個對象object。所以，Redis并不是直接使用這些數據結構來實現鍵值對數據庫。而是基于這些數據結構創建了一個對象系統，這個系統包含字符串對象、列表對象、哈希對象、集合對象和有序集合對象這五種類型的對象，每種對象都用到了至少一種上面提到的數據結構。

這個redisObject的定義是：

typedef struct redisObject { unsigned [type] 4; unsigned [encoding] 4; unsigned [lru] REDIS_LRU_BITS; int refcount; void *ptr; } robj;

1

2

3

4

5

6

7

type: 數據類型，就是我們熟悉的String、hash、list等。

encoding: 內部編碼，其實就是數據結構，指的是當前的這個value底層是用的什么數據結構，因為同一個數據類型底層也有多種數據結構的實現，所以這里需要指定數據結構。

lru: 當前對象可以保留的時長，這個我們在后面的講鍵的過期策略的時候會講。

refcount: 對象引用計數，用于GC。

ptr: 指針，指向以encoding的方式實現的這個對象的實際地址。

下面就是數據類型與數據結構的對應關系：(圖片來源于Redis基本類型及其數據結構)

簡單動態字符串（SDS）

Redis沒有直接使用C語言傳統的字符串（以空字符串結尾的字符數組，在Redis中C字符串只會作為字符串字面量，用在一些無需對字符串進行修改的地方，如打印日志），而是自己構建了一種名為簡單動態字符串（simple dynamic string,SDS）的抽象類型，并將SDS用作Redis的默認字符串表示，在Redis數據庫中，包含字符串值的鍵值對都是由SDS實現的（Redis中所有的值對象中包含的字符串對象底層也是由SDS實現）。

其數據結構的定義如下：

struct sdshdr{ //記錄buf數組中未使用字節的數量，如上圖free為0代表未使用字節的數量為0 int free; //記錄buf數組中已使用字節的數量即SDS的長度，如上圖len為5代表未使用字節數量為5 int len; //字節數組用于保存字符串 sds遵循了c字符串結尾的慣例目的是為了重用c字符串函數庫里的函數 char buf[]; }

1

2

3

4

5

6

7

8

為什么要用SDS

1. 常數復雜度獲取字符串長度

由于C字符串并不記錄自身的長度信息，所以為了獲取一個C字符串的長度，程序必須遍歷整個字符串，對遇到的每個字符串進行計數，直到遇到代表字符串結尾的空字符串為止，時間復雜度是O(N)，而SDS的len屬性中記錄了SDS本身已使用自己的長度。所以獲取一個SDS長度的復雜度是O(1)。

2. 杜絕緩沖區溢出

C字符串并不記錄自身長度帶來的另一個問題是容易造成緩沖區溢出（buffer overflow）。例如：有兩個緊鄰著的C字符串S1和S2,其中S1保存了字符串"REDIS",而S2 則保存了字符串"MYSQL"。如果一個程序員執意要通過strcat(s1,“ORCAL”); 將S1的內容修改為 “REDISORCAL”，但是粗心的他去忘記了在執行stact之前為s1分配足夠的空間，那么在strcat 函數執行之后，s1的數據將溢出到s2所在的空間中，導致s2保存的內容被意外的修改，如下圖所示：

與C字符串不同的是，當SDS API需要對SDS進行修改時，API會先檢查SDS的空間是否滿足修改所需要的要求，如果不滿足的話，API會自動將SDS的空間擴展至執行修改時所需要的大小，然后才執行實際的修改操作，所以使用SDS既不需要手動修改SDS的空間大小，也不會出現前面說的緩沖區溢出的問題。

3. 減少修改字符串是帶來的內存重分配次數

C字符串中，如果對字符串進行修改，那么我們就不得不面臨內存重分配，因為C字符串是由一個N+1長度的數組組成，如果字符串的長度變長，我們就必須對數組進行擴容，否則會產生內存溢出，而如果字符串長度變短，我們就必須釋放掉不再使用的空間，否則會發生內存泄露。所以，每次增長或者縮短一個C字符串，程序都總要對保存這個C字符串的數組進行一次內存重分配操作。

因為內存重分配涉及復雜的算法，并且可能需要執行系統調用，所以它通常是一個比較耗時的操作，由于Redis作為數據庫，經常被用于速度要求嚴苛，數據被頻繁修改的場合，如果每次修改字符串的長度都需要執行一次內存重分配的話，那么光是執行內存重分配的時間就會占去修改字符串所有事件的一大部分。為了避免C字符串的這種缺陷，SDS通過未使用空間解除了字符串長度和底層數組長度之間的關聯：在SDS中，buf數組的長度不一定就是字符串數量加一，數組里面可以包含未使用的字節，而這些字節的數量就是由SDS的free屬性記錄的。

通過未使用空間，SDS實現了空間預分配和惰性空間釋放兩種優化策略。

空間預分配

數組在進行擴容的時候，往往會申請一個更大的數組，然后把數組復制過去。為了提升性能，我們在分配空間的時候并不是分配一個剛噶好的空間，而是分配一個更大的空間，Redis同樣基于這種策略提供了空間預分配，當執行字符串增長操作并且需要擴展內存時，程序不僅僅會給SDS分配必要的空間還會分配額外的未使用空間，其長度存到free屬性中。

如果修改后len的長度小于1M，這時分配給free的大小和len一樣，例如修改后為10字節，那么給free也是10字節，buf的長度變成了10+10+1=21byte。

如果修改后len長度將大于等于1M，這是分配給free的長度為1M，例如修改過后為30M，那么給free是1M，buf的實際長度變成了30M+1M+1byte。

惰性空間釋放

惰性空間釋放用于字符串縮短的操作，當字符串縮短時，程序并不是立即使用內存重分配來收縮短出來的字節，而是使用free屬性記錄起來，并等待將來使用。

4.二進制安全

C字符串中的字符必須符合某種編碼（比如ASCII）,并且除了字符串的末尾之外，字符串里面不能包含空字符串，否則最先被程序讀入的空字符串將被誤認為是字符串的結尾，這些限制使得C字符串只能保存文本數據，而不能保存像圖片、音頻、視頻、壓縮文件這樣的二進制數據。而SDS的buf字節數組不是在保存字符，而是一系列二進制數組，SDS API都會以二進制的方式來處理buf數組里的數據，使用len屬性的值而不是空字符串來判斷字符串是否結束。

總結

本文主要介紹了Redis數據庫用來存儲字符串對象的數據結構—簡單動態字符串SDS，SDS相對于C語言傳統的字符串優勢明顯，主要表現在杜絕緩存區內存溢出，減少字符串操作的內存重分配，二進制安全。

參考

《Redis的設計與實現》

Redis基本類型及其數據結構

簡單動態字符串SDS

Redis 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。