一,何謂 SDS
SDS(Simple Dynamic String)在 Redis 中被定義為一個結構
structsdshdr{intlen;// 記錄 buf 數組中已使用字節的數量,等于 SDS 所保存字符串的長度intfree;// 記錄 buf 數組中未使用字節的數量charbuf[];// 字節數組,用于保存字符串}SDS 示例
c語言識別字符串?
free 屬性值為0,表示這個 SDS 沒有分配任何未使用的空間;
len 屬性值為5,表示這個 SDS 保存了一個五字節長的字符串;
buf 數值是一個 char 類型的數組,數組前五個字節分別保存了 'R','e','d','i','s' 五個字符,而最后一個字節則保存了一個空字符;
c語言輸出字符串。二,SDS 與 C 字符串的區別
根據傳統,C 語言使用長度為 N +1 的字符數組來表示長度為 N 的字符串,并且字符數組的最后一個元素總是空字符 '\0';2.1 獲取字符串的長度
C 語言中獲取字符串的長度,需要程序遍歷整個字符串,直到遇到代表字符串結尾的空字符為止,這個操作的復雜度為O(N);比如,如果想獲取字符串 "Redis" 的長度,在 C 中是按照如下過程操作的。與 C 語言不同的是,SDS 中有一個屬性 len,專門用于記錄字符串的屬性,并且該屬性值是由 SDS API 自動計算完成的,我們在使用時只需去讀取該值即可。這樣復雜度就變為 O(1);比如獲取字符串 "hello,world" 的長度只需讀取 len 屬性即可。小結:就獲取字符串的長度而言, SDS 顯然比 C 更具優勢。c++讀取字符串中的某個字符。2.2 杜絕緩沖區溢出
舉例,char *strcat(char *dest, const char *src) 是 C 語言中的函數,用于將 src 字符串拼接到 dest 字符串的末尾,因為 C 字符串不記錄自身的 長度,所以 strcat 假定用戶在執行這個函數時,已經為 dest 分配了足夠多的內存,可以容納 src 字符串中的所有內容,而一旦這個假設不成立時就會產生緩存溢出。假設有兩個在內存中緊鄰的C字符串 s1 和 s2,其中 s1 保存了字符串 "Redis",而 s2 保存了字符串 "MongoDB",如圖所示:如果用戶在未提前分配內存的情況下執行 strcat(s1, " Cluster") ,那么將會導致 s1 的數據溢出到 s2 所在的內存空間中,導致 s2 的數據被修改;針對上面可能造成的問題,SDS 做了如下修改:當 SDS API 需要對 SDS 進行修改時,API 會先檢查 SDS 的空間會否滿足所需,不滿足情況下 API 會自動將 SDS 的空間擴展至執行修改所需的大小,然后才執行實際的修改操作。這樣在不需要用戶自己操作的情況下避免了內存溢出的發生。2.3 操作字符串時的內存分配策略
C 語言中對字符串的增減都需要對這個字符串數組進行內存重新分配。如果是增長字符串的操作,那么在操作之前,需要先通過內存重分配來擴展底層數組的大小,否則就會產生緩沖區溢出。如果是縮短字符串的操作,那么在操作之前,需要先通過內存重新分配來釋放不再使用的那部分空間,否則就會產生內存泄漏。因為內存的重新分配涉及復雜的算法,并且可能需要執行系統調用,所以它通常是一個比較耗時的操作。在一般程序中,如果修改字符串的長度的情況不太常見,那么每次修改就執行一次內存重分配是可以接受的。但是 Redis 作為數據庫,數據被頻繁修改是很常見的,此時如果每次都執行內存重新分配的話,將會對性能造成不小的影響。為了避免 C 中的上述缺陷,SDS 定義了未使用空間屬性。在 SDS 中,buf 數組的長度不一定就是字符數量 + 1,數組里面可以包含未使用的字節,而這些未使用的字節數量就由 SDS 的 free 屬性記錄。基于該屬性 SDS 實現了空間預分配和惰性分配空間釋放兩種優化策略。2.3.1. 空間預分配
當 SDS 字符串增長時,SDS 的 API 不僅會為 SDS 分配修改所必須要的空間,還會為 SDS 分配額外的未使用空間。如果對 SDS 進行修改后,SDS 的 len 小于 1MB,那么程序將會分配和 len 屬性同樣大小的未使用空間即 free = len,buf 的實際長度將是 len + free + 1;如果對 SDS 修改之后的長度大于等于 1MB,那么程序將會分配 1MB 的未使用空間。此時 buf 的實際長度是 len + 1MB + 1byte。通過這種分配策略,SDS 將連續增長 N 次字符串所需要的內存重分配次數從必定 N 次降為 最多 N 次。2.3.2 惰性空間釋放
當 SDS 字符串縮短時,SDS 的 API 不會立即使用內存重分配來回收縮短后多出來的字節,而是使用 free 屬性將這些字節的數量記錄下來,并等待將來使用。舉例,將長度為 11 個字符的字符串 "XYXaYYbcXYY" 中的 "X" 和 "Y" 字符全部去掉;執行完縮短操作之后的結果如圖所示:可知,SDS 并沒有釋放因為去掉 "X" 和 "Y" 所多出來的 8 字節空間,而是將這 8 字節空間作為未使用空間保留在了 SDS 里面,如果將來對 SDS 進行增長操作的話,可以直接使用這些未使用空間。為了避免惰性空間釋放策略造成的內存浪費,SDS 提供了相應的 API,讓我們在需要時通過這些 API 釋放未使用的空間。2.4 二進制安全
C 中字符編碼必須符合某種編碼(比如ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符,因為 C 語言中默認以 \0 作為字符串的結尾。這使得 C 字符串只能用來保存文本數據,而像圖片,音頻,視頻,壓縮文件等這樣的二進制數據則不能被保存。而 SDS 中判斷字符串是否結束的標志是 len 屬性而不是 \0,這使得 Redis 可以存儲任何二進制數據。2.5 總結
C 字符串 | SDS |
獲取字符串長度的復雜度為 O(N) | 獲取字符串長度的復雜度為 O(1) |
API 不安全,可能造成緩存區溢出 | API 是安全的,不會造成緩存區溢出 |
修改 N 次字符串必然需要 N 次內存重新分配 | 修改 N 次字符串最對需要 N 次內存重新分配 |
只能保存文本數據 | 可以保存文本數據或二進制數據 |
可以使用中的所有函數 | 可以使用中的部分函數? |
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态