字符串是redis中最為常見(jiàn)的存儲(chǔ)數(shù)據(jù)存儲(chǔ)類(lèi)型，其底層實(shí)現(xiàn)是簡(jiǎn)單的動(dòng)態(tài)字符串sds(simple dynamic string)，可以修改的字符串。
sds 介紹
sds本質(zhì)上是 char *，因?yàn)橛辛吮眍^sdshdr結(jié)構(gòu)的存在，所以sds比傳統(tǒng)c字符串在某些方面更加優(yōu)秀，并且能夠兼容傳統(tǒng)C字符串。
sds采用預(yù)分配存儲(chǔ)空間的方式來(lái)減少內(nèi)存的頻繁分配，惰性空間釋放的策略來(lái)優(yōu)化sds的縮短操作，降低內(nèi)存重新分配的概率。
redis 的字符串實(shí)現(xiàn)在sds.h sds.c 中。
typedef char *sds;/* 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[];};
上述代碼來(lái)自sds.h
- __attribute__ ((__packed__))redis3.2 之后，針對(duì)不同長(zhǎng)度的字符串引入了不同的sds數(shù)據(jù)結(jié)構(gòu)，并且強(qiáng)制內(nèi)存對(duì)齊1，將內(nèi)存對(duì)齊的交給統(tǒng)一的內(nèi)存分配函數(shù)，從而達(dá)到節(jié)省內(nèi)存的目的稍微了解c/c++的人都會(huì)了解在結(jié)構(gòu)體建立的是時(shí)候，會(huì)進(jìn)行字節(jié)對(duì)齊操作，所以往往比實(shí)際變量占用的字節(jié)要多一些，如果我們不想要字節(jié)對(duì)齊怎么辦？在結(jié)構(gòu)體聲明當(dāng)中__attribute__ ((__packed__))關(guān)鍵字可以讓我們的結(jié)構(gòu)體按照緊湊排列的方式，占用內(nèi)存。如下2種數(shù)據(jù)結(jié)構(gòu)分別sizeof 將得到不同的結(jié)果struct test{ unsigned char flags; int value; }; struct __attribute__ ((__packed__)) test_{ unsigned char flags; int value; }; sizeof(struct test) //size is 8sizeof(struct test_) //size is 5
- char buf[]char buf[] 等價(jià)與 char buf[0] 在標(biāo)準(zhǔn)C和C++中0長(zhǎng)數(shù)組如char buf[0]是不允許使用的，因?yàn)檫@從語(yǔ)義邏輯上看，是完全沒(méi)有意義的。但是，GUN中卻允許使用，而且，很多時(shí)候，應(yīng)用在了變長(zhǎng)結(jié)構(gòu)體中。對(duì)編譯器來(lái)說(shuō)，此時(shí)長(zhǎng)度為0的數(shù)組并不占用空間，因?yàn)閿?shù)組名本身不占空間，它只是一個(gè)偏移量， 數(shù)組名這個(gè)符號(hào)本身代表了一個(gè)不可修改的地址常量。我們可以優(yōu)雅的將buf稱(chēng)之為柔性數(shù)組。在結(jié)構(gòu)中，buf是一個(gè)數(shù)組名；但該數(shù)組沒(méi)有元素；該數(shù)組的真實(shí)地址緊隨結(jié)構(gòu)體sdshdr5之后，而這個(gè)地址就是結(jié)構(gòu)體后面數(shù)據(jù)的地址（如果給這個(gè)結(jié)構(gòu)體分配的內(nèi)容大于這個(gè)結(jié)構(gòu)體實(shí)際大小，后面多余的部分就是這個(gè)buf的內(nèi)容）；這種聲明方法可以巧妙的實(shí)現(xiàn)C語(yǔ)言里的數(shù)組擴(kuò)展。對(duì)于0長(zhǎng)數(shù)組的這個(gè)特點(diǎn)，很容易構(gòu)造出變長(zhǎng)結(jié)構(gòu)體，如緩沖區(qū)，數(shù)據(jù)包等等struct Buffer { int len; char cData[0]; }; 假如我們要發(fā)送1024個(gè)字節(jié)，我們?nèi)绾螛?gòu)造這個(gè)數(shù)據(jù)包呢?char *buffer = (char*)malloc(sizeof(Buffer)+1024)我們首先申請(qǐng)1024字節(jié)的空間，其次做一個(gè)類(lèi)型轉(zhuǎn)換如下代碼Buffer *p = (Buffer*)buffer p->len = 1024 memcpy(p.cData,"1024 data............",1024) send(socket,p,sizeof(Buffer)+1024);//發(fā)送數(shù)據(jù)
sds 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)
我們摘取其中一個(gè)sdshdr32的數(shù)據(jù)結(jié)構(gòu)來(lái)分析redis中sdsh的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)
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[];};
sdsnew(const char *init) 會(huì)根據(jù)init數(shù)據(jù)的長(zhǎng)度去分配內(nèi)存，分配內(nèi)存的大小為s_malloc(hdrlen+initlen+1) 其中 hdrlen 為sdshdr* 的結(jié)構(gòu)體的大小，initlen為傳入的init 變量的數(shù)據(jù)大小或者為sdsnewlen(const void *init, size_t initlen) 傳入的initlen 的大小。
sdsnewlen 方法會(huì)根據(jù)initlen 的數(shù)值去通過(guò)sdsReqType去確定type的類(lèi)型，然后根據(jù)返回的type數(shù)值再通過(guò)sdsHdrSize(type)獲得hdrlen。 具體代碼實(shí)現(xiàn)可參見(jiàn)sds.c文件。
當(dāng)sds s = sdsnew()之后，其中s的位置并不是內(nèi)存的起始位置, sh = s_malloc(hdrlen+initlen+1), 而是偏移了sh + hdrlen 后的位置 s = (char*)sh+hdrlen。
sds 有一個(gè)關(guān)鍵的宏SDS_HDR 定義如下
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
其中SDS_HDR 能夠?qū) 的指針位置減去 sdshdr##T的大小，從而將指針位置指向sdsnew內(nèi)存分配的起始位置dh,進(jìn)而去通過(guò)sh去操作sdshdr##T的成員變量。其中T取值為（5，8，16，32，64）
- 一個(gè) sds 的內(nèi)部數(shù)據(jù)結(jié)構(gòu)
----------------------------- | len | alloc | flags | buf | -----------------------------
如上，其中buf位置真正存儲(chǔ)了字符數(shù)據(jù)， 前面十三個(gè)位置分別存儲(chǔ)了buf相關(guān)的sds信息。
- len記錄當(dāng)前字節(jié)數(shù)組的長(zhǎng)度（不包括），使得獲取字符串長(zhǎng)度的時(shí)間復(fù)雜度由O(N)變?yōu)榱薕(1)
- alloc記錄了當(dāng)前字節(jié)數(shù)組總共分配的內(nèi)存大小（不包括）
- flags記錄了當(dāng)前字節(jié)數(shù)組的屬性、用來(lái)標(biāo)識(shí)到底是sdshdr8還是sdshdr16等
- buf保存了字符串真正的值以及末尾的一個(gè)
整個(gè)sds的內(nèi)存是連續(xù)的，統(tǒng)一開(kāi)辟的。在大多數(shù)操作中，buf內(nèi)的字符串實(shí)體才是操作對(duì)象。統(tǒng)一開(kāi)辟內(nèi)存能通過(guò)buf頭指針進(jìn)行尋址，拿到整個(gè)struct的指針，而且通過(guò)buf的頭指針減1直接就能獲取flags的值, flags = s[-1]。
更詳細(xì)的sds的分配可參見(jiàn)sds.c中sdsnewlen的實(shí)現(xiàn)部分。
