杭州網(wǎng)站定制開(kāi)發(fā)自助建站申請(qǐng)
Redis系列之底層數(shù)據(jù)結(jié)構(gòu)SDS
實(shí)驗(yàn)的環(huán)境
- Redis 6.0
- VSCode 1.88.1
什么是SDS?
SDS:Simple Dynamic String,翻譯為簡(jiǎn)單動(dòng)態(tài)字符串。SDS是一種用于存儲(chǔ)二進(jìn)制數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),具有動(dòng)態(tài)擴(kuò)容的特點(diǎn),代碼位于src/sds.h
和src/sds.c
SDS的總體數(shù)據(jù)結(jié)構(gòu)大致如圖:在源碼里sds包括幾個(gè)部分,len
、alloc
、flags
、buf
,其中 sdshdr
是頭部,buf
是真實(shí)存儲(chǔ)數(shù)據(jù)的地方,在存儲(chǔ)的數(shù)據(jù)后面會(huì)跟一個(gè)\0
,所以數(shù)據(jù)加上\0
就是所謂的buf
- len:保存了SDS字符串的長(zhǎng)度
- buf[]:保存數(shù)據(jù)的地方
- alloc:分別以u(píng)int8, uint16, uint32, uint64表示整個(gè)SDS
- flags:始終為一字節(jié), 以低三位標(biāo)示著頭部的類型, 高5位未使用
查看源碼sds.h,可以看到SDS里面有幾種不同的頭部,其中sdshdr5
實(shí)際并未使用到,所以實(shí)際上有四種不同的頭部
/* Note: sdshdr5 is never used, we just access the flags byte directly.* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {unsigned char flags; /* 3 lsb of type, and 5 msb of string length */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; /* used */uint8_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len; /* used */uint16_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len; /* used */uint32_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {uint64_t len; /* used */uint64_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
為什么要使用SDS?
Redis是用C語(yǔ)言寫(xiě)的,為什么不直接就用C語(yǔ)言里的char
來(lái)定義字符串?
- 獲取字符串長(zhǎng)度
由于有len
屬性,所以獲取SDS
字符串的長(zhǎng)度只需要讀取len
屬性,所以時(shí)間復(fù)雜度為O(1)
。如果直接使用C
語(yǔ)言中的字符串來(lái)實(shí)現(xiàn),獲取字符串的長(zhǎng)度需要遍歷計(jì)數(shù),時(shí)間復(fù)雜度為O(n)
。
- 避免緩存區(qū)溢出
在C
語(yǔ)言中,如果使用strcat
函數(shù)來(lái)進(jìn)行兩個(gè)字符串的拼接,如果沒(méi)有分配足夠長(zhǎng)度的內(nèi)存空間,就會(huì)造成緩存區(qū)溢出。而對(duì)于SDS
數(shù)據(jù)類型,在進(jìn)行字符串修改的時(shí)候,會(huì)根據(jù)記錄的len屬性檢查內(nèi)存空間是否滿足需求,如果不滿足,會(huì)進(jìn)行相應(yīng)空間的擴(kuò)展,所以不會(huì)出現(xiàn)緩存區(qū)溢出
- 減少字符串內(nèi)存重新分配次數(shù)
在C
語(yǔ)言中字符串,是不會(huì)記錄字符串的長(zhǎng)度的,所以一旦修改了字符串,就需要重新分配內(nèi)存,因?yàn)槿绻麤](méi)有重新分配,字符串長(zhǎng)度增大時(shí)會(huì)造成內(nèi)存溢出區(qū)溢出,長(zhǎng)度減小時(shí)會(huì)造成內(nèi)存泄漏。而對(duì)于SDS來(lái)說(shuō),因?yàn)橛虚L(zhǎng)度熟悉len
和alloc
屬性的存在,SDS
實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種策略來(lái)減少重新分配內(nèi)存
- 空間預(yù)分配:SDS對(duì)空間進(jìn)行擴(kuò)展的時(shí)候,擴(kuò)展的內(nèi)存比實(shí)際需要的多,這樣可以減少字符串增長(zhǎng)操作所需的內(nèi)存重新分配次數(shù)
- 惰性空間釋放:SDS對(duì)字符串進(jìn)行縮短操作時(shí),不會(huì)立即進(jìn)行內(nèi)存重新分配,來(lái)回收縮短后多余的內(nèi)存空間,而是使用
alloc
將這些字節(jié)數(shù)量記錄下來(lái),等待后續(xù)使用
- 二進(jìn)制安全
在C
語(yǔ)言中,是以空字符串作為字符串結(jié)束的標(biāo)識(shí),但是一些特殊的字符串,可能就包括空字符串的,所以容易丟失數(shù)據(jù),不能正確存取。而SDS是根據(jù)len
屬性,以處理二進(jìn)制的方式來(lái)處理buf
里的數(shù)據(jù),所以保存數(shù)據(jù)更加安全
- 兼容部分C字符串函數(shù)
SDS可以重用C語(yǔ)言庫(kù)<string.h>
中的一部分函數(shù)
C字符串和SDS對(duì)比
C字符串 | SDS |
---|---|
獲取字符串長(zhǎng)度時(shí)間復(fù)雜度為O(n) | 獲取字符串的長(zhǎng)度時(shí)間復(fù)雜度為O(1) |
不安全,可能會(huì)造成緩沖區(qū)溢出 | 安全,不會(huì)造成緩沖區(qū)溢出 |
修改字符串n次就需要進(jìn)行n次內(nèi)存分配 | 修改字符串長(zhǎng)度n次,最多需要n次內(nèi)存分配 |
只能保存文本數(shù)據(jù) | 可以保存文本數(shù)據(jù)或者二進(jìn)制數(shù)據(jù) |
可以使用所有<string.h>庫(kù)中的函數(shù) | 可以使用一部分<string.h>庫(kù)中的函數(shù) |