Redis資料結構之簡單動態字串SDS
Redis的底層資料結構非常多,其中包括SDS、ZipList、SkipList、LinkedList、HashTable、Intset等。如果你對Redis的理解還只停留在get、set的水平的話,是遠遠不足以應對面試提問的。本文簡單介紹了Redis底層最重要的資料結構 - 簡單動態字串(SDS)
Redis使用C語言開發,但並沒有使用C語言傳統的字串表示(以空字元結尾的位元組陣列,以下簡稱C字串),而是自己構建了一種名為簡單動態字串的(simple dynamic string,SDS)的抽象型別,並將SDS用作Redis的預設字串表示。
在Redis裡面,C字串只會作為字串字面量(static literal)用在一些無須對字串值進行修改的地方。當Redis需要的不僅僅是一個字串字面量,而是一個可以被修改的字串值時,Redis就會使用SDS來表示字串值,比如在Redis的資料庫裡面,包含字串的鍵值對在底層都是由SDS實現的。
咱們來舉個例子,如果在客戶端執行命令:
redis> SET msg "hello world" ok
那麼Redis將在資料庫中建立一個新的鍵值對,其中:
- 鍵值對的鍵是一個字串物件,物件的底層實現是一個儲存著字串“msg”的SDS。
- 鍵值對的值也是一個字串物件,物件的底層實現是一個儲存著字串“hello world”的SDS。
除了用來儲存資料庫中的字串值之外,SDS還被用作緩衝區:AOF模組中的AOF緩衝區,以及客戶端狀態中的輸入緩衝區,都是由SDS實現的。總之,SDS是Redis的最基礎也是最重要的資料結構。
1.SDS的定義
每個 sds.h/sdshdr 結構表示一個SDS值:
struct sdshdr{ // 記錄buf陣列中已使用位元組的數量 // 等於SDS所儲存字串的長度 int len; // 記錄buf陣列中未使用位元組的數量 int free; //位元組陣列,用於儲存字串 char buf[]; }
用一張圖來表示:
SDS 遵循 C 字串以空字元結尾的慣例, 儲存空字元的 1位元組空間不計算在 SDS 的 len 屬性裡面, 並且為空字元分配額外的 1 位元組空間, 以及新增空字元到字串末尾等操作都是由 SDS 函式自動完成的, 所以這個空字元對於 SDS 的使用者來說是完全透明的。
2.SDS與C字串的區別
現在來說,C語言使用長度為N+1的字元陣列來表示長度為N的字串,並且字元陣列的最後一個元素總是空字元“\0”。
C的這種簡單的字串表達方式,並不能滿足Redis對字串在安全性、效率以及功能方面的要求。具體有以下幾個方面。
2.1 常數複雜度獲取字串長度
因為C字串並不記錄字串的長度資訊,所以為了獲取一個C字串的長度,程式必須遍歷整個字串,對遇到的每個字元進行計數,直到遇到空字元為止,這個操作的複雜度為O(n)。而在Redis的SDS中,這個時間複雜度只有O(1)。
2.2 杜絕緩衝區溢位
除了獲取字串長度的複雜度高之外,C字元不記錄自身長度帶來的另一個問題就是緩衝區溢位。舉個例子,C語言的 strcat 函式可以將字串中的內容拼接到 dest 字串的末尾,但是當字串的容量不夠就會產生快取區溢位,因為字串也是基於陣列實現的,也是有大小限制的。
Redis的SDS已經杜絕了這個問題,那它是如何解決的呢?
當API要對SDS進行修改時,API會先檢查SDS的空間是否滿足修改所需的空間,如果不夠的話,API會自動將SDS的空間進行擴容,然後才執行實際的修改操作。這就避免了緩衝區記憶體溢位。
2.3 減少修改字串時帶來的記憶體重分配次數
上面說到了API會在修改SDS字串時自動擴容,如果每次修改都伴隨著對字串內的陣列的記憶體重分配,那效率可想而知。所以Redis實現了空間預分配和惰性空間釋放兩種優化策略。
空間預分配
空間預分配用於優化SDS的字串增長操作:當SDS的API對一個SDS進行修改,並且需要對SDS進行空間擴充套件的時候,程式不僅會為SDS分配修改所需要的空間,還會為SDS分配額外的未使用空間。
總的來說,額外分配的未使用空間數量大小有兩種可能:
- 如果對SDS修改之後,SDS的長度將小於1MB,那麼程式分配和len 屬性同樣大小的未使用空間,這時候SDS的 free 屬性的值將和 len 屬性的值相同。也就是說,該SDS字串修改完後還有近一半的容量。
- 如果對SDS修改之後,SDS的長度大於等於1MB,那麼程式會分配1MB的未使用空間。這個是固定的。
通過空間預分配,Redis可以減少連續執行字串操作所需的記憶體重分配次數。
惰性空間釋放
惰性空間釋放用於優化SDS的字串縮短操作:當SDS的API需要縮短SDS儲存的字串時,程式並不立即使用記憶體重分配來回收縮短後多出來的位元組,而是使用 free 屬性將這些位元組的數量記錄起來,並等待將來使用。
2.4 二進位制安全
在C語言中,字串的儲存必須符合某種編碼(ASCII),並且字串不能包含空字元,否則會被認為是字串結尾。這些限制使得C字串只能儲存文字資料,而不能儲存像圖片、音訊、視訊、壓縮檔案這樣的二進位制資料。
所以,為了解決C字串的不足,Redis的 buf 陣列儲存的是二進位制資料,這也就是把SDS的 buf 陣列稱為位元組陣列的原因。
2.5 相容部分C字串函式
雖然 Redis 的API都是二進位制安全的,但它們一樣遵循C字串以空字串結尾的慣例,這些API總會將SDS儲存的資料的末尾設定為空字元,並且總會在為 buf 陣列分配空間時多分配一個位元組來容納這個空字元,這是為了讓那些儲存文字資料的SDS可以重用一部分C的函式。
舉個例子, 如果我們有一個 SDS 的指標 s , 那麼我們可以直接使用 stdio.h/printf 函式, 通過執行以下語句:
printf("%s", s->buf);
來打印出 SDS 儲存的字串值 "Redis"
, 而無須為 SDS 編寫專門的列印函式。
最後,臨近春節,祝大家新年快樂!