Redis為什么不直接使用C字符串，而要自定義簡單動態(tài)字符串？
本文轉(zhuǎn)載自微信公眾號「 編程珠璣」，轉(zhuǎn)載本文請聯(lián)系 編程珠璣公眾號。
作者:守望，linux應(yīng)用開發(fā)者，目前在公眾號【編程珠璣】 分享Linux/C/C++/數(shù)據(jù)結(jié)構(gòu)與算法/工具等原創(chuàng)技術(shù)文章和學(xué)習(xí)資源。
Redis (一個使用ANSI C編寫的開源、支持網(wǎng)絡(luò)、基于內(nèi)存、可選持久性的鍵值對存儲數(shù)據(jù)庫。)沒有直接使用 C 語言傳統(tǒng)的字符串表示redis中的字符串，而是使用了一種名為簡單動態(tài)字符串(simple dynamic string，SDS)的抽象類型， 并將 SDS 用作 Redis 的默認(rèn)字符串。
那么，為什么要用這種數(shù)據(jù)結(jié)構(gòu)替代傳統(tǒng)的字符串呢?我們先回顧一下C字符串。
C語言傳統(tǒng)字符串
C語言傳統(tǒng)字符串是以空字符結(jié)尾的字符數(shù)組。例如：
- char str[] = "hello";
計算字符串的長度：
- strlen(str);
C語言傳統(tǒng)字符串我們應(yīng)該已經(jīng)很熟悉了，這里就不再繼續(xù)介紹了。
更多相關(guān)內(nèi)容參考《sizeof,strlen,數(shù)組,字符串整在一起的那些坑》和《C語言入坑指南-數(shù)組之謎》。
簡單動態(tài)字符串
redis中的簡單動態(tài)字符串定義如下：
- struct __attribute__ ((__packed__)) sdshdr64 {
- uint64_t len; //已使用
- uint64_t alloc; //分配的內(nèi)存，包括結(jié)尾\0
- unsigned char flags; //標(biāo)志位
- char buf[];//真正存儲字符串的地方
- };
它有很多種，這里選擇了長度為8字節(jié)范圍的進行介紹。看起來很簡單對不對?
__attribute__ ((packed)) 取消了默認(rèn)的字節(jié)對齊，使得flags前后不會有潛在的填充字段，也便于網(wǎng)絡(luò)傳輸(擴展內(nèi)容參考《理一理字節(jié)對齊的那些事》)。len表示buf中存儲了的內(nèi)容的長度;alloc表示已經(jīng)分配的空間。
那么，定義成這樣的SDS有什么好處呢?
常數(shù)復(fù)雜度獲取長度
我們都知道，strlen獲取C傳統(tǒng)字符串長度的時間復(fù)雜度為O(N)，而上面的結(jié)構(gòu)中，獲取字符串長度的時間復(fù)雜度為常數(shù)，因為len字段存儲了字符串的長度，這樣的做法雖然多占用了一點空間，換來的卻是效率的提升。
實際上這種做法，在很多地方都很常見，例如C++中的標(biāo)準(zhǔn)容器，如vector獲取其大小，string獲取其長度。
預(yù)分配空間減少內(nèi)存分配次數(shù)
實際上，在創(chuàng)建新的sds的時候，它并不僅僅申請要使用的內(nèi)存，而是額外申請了一些空間，以避免下次修改的時候又需要重新申請內(nèi)存。
什么意思呢?
比如說，你有一個字符數(shù)組：
- char str[] = "hello";
現(xiàn)在你想存儲helloworld，怎么辦?原先的空間已經(jīng)確定了，沒有辦法存儲這么多字符串，你只能重新申請空間，然后還要把原先的hello拷貝到新申請的空間中去。如果有頻繁地修改字符串，就會導(dǎo)致系統(tǒng)中頻繁的內(nèi)存申請，釋放，拷貝，這樣還能有高效的redis嗎?
因此在redis中，如果有這樣的情況，分配新的空間的時候，會預(yù)分配一些空間，以備下次使用。
惰性釋放空間
而正因如此，出現(xiàn)字符串縮短的時候，也沒有必要直接釋放內(nèi)存，只需要更新字符串，記錄當(dāng)前使用的長度即可，你說，下次字符串又增長的時候，不就又用上了嗎?
保存二進制數(shù)據(jù)
看下面的字符串：
- char str[] = "hello\0world";
你說下面的字符串，strle長度是多少?不是10，也不是11，而是5。為啥?遇到\0就計算結(jié)束了唄。所以要想存儲一些特殊的字符串，即中間可能出現(xiàn)\0的字符串，傳統(tǒng)的C字符串還不好辦呢。
sds就不一樣了，管你存什么，反正我長度是記錄在len字段中了，輸入寫入多少，我記錄多少。因此它可以保存二進制數(shù)據(jù)。
擴展可以參考《NULL，0，'\0'，“0”，"\0"你真的分得清嗎?》
兼容傳統(tǒng)字符串的常見用法
雖然redis新定義了sds這樣的結(jié)構(gòu)，但是能應(yīng)用于傳統(tǒng)C字符串的函數(shù)，同樣可以應(yīng)用于sds。這點在《數(shù)組下標(biāo)-1你見過嗎?》中已經(jīng)簡單提到過了。
| ↓ | |||
|---|---|---|---|
| len | alloc | flag | buf |
所以，類似下面這樣的操作，也是安全的：
- strlen(pSds);/pSds為sds類型
- strcasecmp(pSds, "hello world");//pSds為sds類型
所以你現(xiàn)在明白為什么要指向buf了吧?適用于傳統(tǒng)C字符串的函數(shù)，也能用在sds上。
而正因如此，我們看到源碼中，有很多地方sds使用了下標(biāo)-1訪問一些內(nèi)容：
例如sdsIncrLen函數(shù)中
- void sdsIncrLen(sds s, ssize_t incr) {
- unsigned char flags = s[-1];
- size_t len;
s[-1]，等價于 *(s-1)，下面就很容易理解了：
| ↓ | |||
|---|---|---|---|
| len | alloc | flag | buf |
所以下次看到下標(biāo)為負(fù)，可不要覺得奇怪了。
總結(jié)
實際上當(dāng)你了解C++的vector的時候，你會發(fā)現(xiàn)，它們利用的思想是驚人的相似
- 預(yù)分配
- 常數(shù)獲取長度
- 惰性釋放
- ……
本文旨在通過了解redis中sds的實現(xiàn)，學(xué)習(xí)其中的設(shè)計思想和策略。
