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