Redis 數(shù)據(jù)結(jié)構(gòu)之字符串的那些騷操作
Redis 字符串底層用的是 sds 結(jié)構(gòu)，該結(jié)構(gòu)同 c 語言的字符串相比，其優(yōu)點是可以節(jié)省內(nèi)存分配的次數(shù)，還可以...
這樣寫是不是讀起來很無聊？這些都是別人咀嚼過后，經(jīng)過一輪兩輪三輪的再次咀嚼，吐出來的精華，這就是為什么好多文章你覺得干貨滿滿，但就是記不住說了什么。我希望把這個咀嚼的過程，也講給你，希望以后再提到 Redis 字符串時，它是活的。
前置知識：本篇文章的閱讀需要你了解 Redis 的編碼類型，知道有這么回事就行，如果比較困惑可以先讀一下 《面試官問我 redis 數(shù)據(jù)類型，我回答了 8 種》 這篇文章
源碼選擇：Redis-3.0.0
文末總結(jié)：本文行為邏輯是邊探索邊出結(jié)論，但文末會有很精簡的總結(jié)，所以不用怕看的時候記不住，放心看，像讀小說一樣就行，不用邊讀邊記。
我研究 Redis 源碼時的小插曲
我下載了 Redis-3.0.0 的源碼，找到了 set 命令對應(yīng)的真正執(zhí)行存儲操作的源碼方法 setCommand。其實 Redis 所有的指令，其核心源碼的位置都是叫 xxxCommand，所以還是挺好找的。
t_string.c
/*?SET?key?value?[NX]?[XX]?[EX?]?[PX?]?*/
void?setCommand(redisClient?*c)?{
????int?j;
????robj?*expire?=?NULL;
????int?unit?=?UNIT_SECONDS;
????int?flags?=?REDIS_SET_NO_FLAGS;
????for?(j?=?3;?j?argc;?j++)?{
????????//?這里省略無數(shù)行
????????...
????}
????c->argv[2]?=?tryObjectEncoding(c->argv[2]);
????setGenericCommand(c,flags,c->argv[1],c->argv[2]...);
}
不知道為什么，看到字符串這么長的源碼（主要是下面那兩個方法展開很多），我就想難道這不會嚴重影響性能么？我于是做了如下兩個壓力測試。
未修改源代碼時的壓力測試
[root@VM-0-12-centos?src]#?./redis-benchmark?-n?10000?-q
...
SET:?112359.55?requests?per?second
GET:?105263.16?requests?per?second
INCR:?111111.11?requests?per?second
LPUSH:?109890.11?requests?per?second
...
觀察到 set 指令可以達到 112359 QPS，可以，這個和官方宣傳的 Redis 性能也差不多。
我又將 setCommand 的源碼修改了下，在第一行加入了一句直接返回的代碼，也就是說在執(zhí)行 set 指令時直接就返回，我想看看這個 set 性能會不會提高。
void?setCommand(redisClient?*c)?{
????//?這里我直接返回一個響應(yīng)?ok
????addReply(c,?shared.ok);
????return;
????//?下面是省略的?Redis?自己的代碼
????...
}
將 setCommand 改為立即返回后的壓力測試
[root@VM-0-12-centos?src]#?./redis-benchmark?-n?10000?-q
...
SET:?119047.62?requests?per?second
GET:?105263.16?requests?per?second
INCR:?113636.37?requests?per?second
LPUSH:?90090.09?requests?per?second
...
和我預(yù)期的不太一樣，性能幾乎沒有提高，又連續(xù)測了幾次，有時候還有下降的趨勢。
說明這個 setCommand 里面寫了這么多判斷呀、跳轉(zhuǎn)什么的，對 QPS 幾乎沒有影響。想想也合理，現(xiàn)在 CPU 都太牛逼了，幾乎性能瓶頸都是在 IO 層面，以及內(nèi)存分配與釋放這些地方，這個 setCommand 里面寫了這么多代碼，執(zhí)行速度同直接返回相比，都幾乎沒有什么差別。
跟我在源碼里走一遍 set 的全流程
首先，客戶端執(zhí)行指令
127.0.0.1:6379>?set?name?tom
然后就進入我的 debug 斷點了
別深入，先看骨架
源碼沒那么嚇人，多走幾遍你就會發(fā)現(xiàn)看源碼比看文檔容易了，因為最直接，且閱讀量也最少，沒有那么多腦筋急轉(zhuǎn)彎一樣的比喻。
真的全流程，應(yīng)該把前面的 建立 socket 鏈接 --> 建立 client --> 注冊 socket 讀取事件處理器 --> 從 socket 讀數(shù)據(jù)到緩沖區(qū) --> 獲取命令 也加上，也就是面試中的?？碱} 單線程的 Redis 為啥那么快 這個問題的答案。不過本文專注于 Redis 字符串在數(shù)據(jù)結(jié)構(gòu)層面的處理，請求流程后面會專門去講，這里只把前面步驟的 debug 堆棧信息給大家看下
總之當(dāng)客戶端發(fā)送來一個 set name tom 指令后，Redis 服務(wù)端歷經(jīng)千山萬水，找到了 setCommand 方法進來。
//?注意入?yún)⑹莻€?redisClient?結(jié)構(gòu)
void?setCommand(redisClient?*c)?{
????int?flags?=?REDIS_SET_NO_FLAGS;
????//?前面部分完全不用看
????...
????//?下面兩行是主干，先確定編碼類型，再執(zhí)行通用的?set?操作函數(shù)
????c->argv[2]?=?tryObjectEncoding(c->argv[2]);
????setGenericCommand(c,flags,c->argv[1],c->argv[2]...);
}
好長的代碼被我縮短到只有兩行了，因為前面部分真的不用看，前面是根據(jù) set 的額外參數(shù)來設(shè)置 flags 的值，但是像如 set key value EX seconds 這樣的指令，一般都直接被更常用的 setex key seconds value 代替了，而他們都有專門對應(yīng)的更簡潔的方法。
void?setnxCommand(redisClient?*c)?{
????c->argv[2]?=?tryObjectEncoding(c->argv[2]);
????setGenericCommand(...);
}
void?setexCommand(redisClient?*c)?{
????c->argv[3]?=?tryObjectEncoding(c->argv[3]);
????setGenericCommand(...);
}
void?psetexCommand(redisClient?*c)?{
????c->argv[3]?=?tryObjectEncoding(c->argv[3]);
????setGenericCommand(...);
}
| 屬性 | argv[0] | argv[1] | argv[2] |
|---|---|---|---|
| type | string | string | string |
| encoding | embstr | embstr | embstr |
| ptr | "set" | "name | "tom" |
我們可以斷定，這些 argv 參數(shù)就是 將我們輸入的指令一個個的包裝成了 robj 結(jié)構(gòu)體 傳了進來，后面怎么用的，那就再說咯。
骨架了解的差不多了，總結(jié)起來就是，Redis 來一個 set 指令，千辛萬苦走到 setCommand 方法里，tryObjectEncoding 一下，再 setGenericCommand 一下，就完事了。至于那兩個方法干嘛的，我也不知道，看名字再結(jié)合上一講中的編碼類型的知識，大概猜測先是處理下編碼相關(guān)的問題，然后再執(zhí)行一個 set、setnx、setex 都通用的方法。
那繼續(xù)深入這兩個方法，即可，一步步來
進入 tryObjectEncoding 方法
c->argv[2]?=?tryObjectEncoding(c->argv[2]);
我們可以看到調(diào)用方把 argv[2]，也就是我們指令中 value 字符串 "tom" 包裝成的 robj 結(jié)構(gòu)，傳進了 tryObjectEncoding，之后將返回值又賦回去了。一個合理的猜測就是可能 argv[2] 什么都沒變就返回去了，也可能改了點什么東西返回去更新了自己。那要是什么都不變，就又可以少研究一個方法啦。
抱著這個僥幸心理，進入方法內(nèi)部看看。
/*?Try?to?encode?a?string?object?in?order?to?save?space?*/
robj?*tryObjectEncoding(robj?*o)?{
????long?value;
????sds?s?=?o->ptr;
????size_t?len;
????...
????len?=?sdslen(s);
????//?如果這個值能轉(zhuǎn)換成整型，且長度小于21，就把編碼類型替換為整型
????if?(len?<=?21?&&?string2l(s,len,&value))?{
????????//?這個?if?的優(yōu)化，有點像?Java?的?Integer?常量池，感受下
????????if?(value?>=?0?&&?value?????????????...
????????????return?shared.integers[value];
????????}?else?{
????????????...
????????????o->encoding?=?REDIS_ENCODING_INT;
????????????o->ptr?=?(void*)?value;
????????????return?o;
????????}
????}
????//?到這里說明值肯定不是個整型的數(shù)，那就嘗試字符串的優(yōu)化
????if?(len?<=?REDIS_ENCODING_EMBSTR_SIZE_LIMIT)?{
????????robj?*emb;
????????//?本次的指令，到這一行就返回了
????????if?(o->encoding?==?REDIS_ENCODING_EMBSTR)?return?o;
????????emb?=?createEmbeddedStringObject(s,sdslen(s));
????????...
????????return?emb;
????}
????...
????return?o;
}
別看這么長，這個方法就一個作用，就是選擇一個合適的編碼類型而已。功能不用說，如果你感興趣的話，從中可以提取出一個小的騷操作：
在選擇整型返回的時候，不是直接轉(zhuǎn)換為一個 long 類型，而是先看看這個數(shù)值大不大，如果不大的話，從常量池里面選一個返回這個引用，這和 Java Integer 常量池的思想差不多，由于業(yè)務(wù)上可能大部分用到的整型都沒那么大，這么做至少可以節(jié)省好多空間。
進入 setGenericCommand 方法
看完上個方法很開心，因為就只是做了編碼轉(zhuǎn)換而已，這用 Redis 編碼類型的知識很容易就理解了?？磥碇仡^戲在這個方法里呀。
方法不長，這回我就沒省略全粘過來看看
void?setGenericCommand(redisClient?*c,?int?flags,?robj?*key,?robj?*val,?robj?*expire,?int?unit,?robj?*ok_reply,?robj?*abort_reply)?{
????long?long?milliseconds?=?0;?/*?initialized?to?avoid?any?harmness?warning?*/
????if?(expire)?{
????????if?(getLongLongFromObjectOrReply(c,?expire,?&milliseconds,?NULL)?!=?REDIS_OK)
????????????return;
????????if?(milliseconds?<=?0)?{
????????????addReplyErrorFormat(c,"invalid?expire?time?in?%s",c->cmd->name);
????????????return;
????????}
????????if?(unit?==?UNIT_SECONDS)?milliseconds?*=?1000;
????}
????if?((flags?&?REDIS_SET_NX?&&?lookupKeyWrite(c->db,key)?!=?NULL)?||
????????(flags?&?REDIS_SET_XX?&&?lookupKeyWrite(c->db,key)?==?NULL))
????{
????????addReply(c,?abort_reply???abort_reply?:?shared.nullbulk);
????????return;
????}
????setKey(c->db,key,val);
????server.dirty++;
????if?(expire)?setExpire(c->db,key,mstime()+milliseconds);
????notifyKeyspaceEvent(REDIS_NOTIFY_STRING,"set",key,c->db->id);
????if?(expire)?notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,
????????"expire",key,c->db->id);
????addReply(c,?ok_reply???ok_reply?:?shared.ok);
}
我們只是 set key value， 沒設(shè)置過期時間，也沒有 nx 和 xx 這種額外判斷，也先不管 notify 事件處理，整個代碼就瞬間只剩一點了。
void?setGenericCommand(redisClient?*c,?robj?*key,?robj?*val...)?{
????...
????setKey(c->db,key,val);
????...
????addReply(c,?ok_reply???ok_reply?:?shared.ok);
}
addReply 看起來是響應(yīng)給客戶端的，和字符串本身的內(nèi)存操作關(guān)系應(yīng)該不大，所以看來重頭戲就是這個 setKey 方法啦，我們點進去。由于接下來都是小方法連續(xù)調(diào)用，我直接列出主線。
void?setKey(redisDb?*db,?robj?*key,?robj?*val)?{
????if?(lookupKeyWrite(db,key)?==?NULL)?{
????????dbAdd(db,key,val);
????}?else?{
????????dbOverwrite(db,key,val);
????}
????...
}
void?dbAdd(redisDb?*db,?robj?*key,?robj?*val)?{
????sds?copy?=?sdsdup(key->ptr);
????int?retval?=?dictAdd(db->dict,?copy,?val);
????...
?}
int?dictAdd(dict?*d,?void?*key,?void?*val)?{
????dictEntry?*entry?=?dictAddRaw(d,key);
????if?(!entry)?return?DICT_ERR;
????dictSetVal(d,?entry,?val);
????return?DICT_OK;
}
這一連串方法見名知意，最終我們可以看到，在一個字典結(jié)構(gòu) dictEntry 里，添加了一條記錄。這也說明了 Redis 底層確實是用 字典（hash 表）來存儲 key 和 value 的。
跟了一遍 set 的執(zhí)行流程，我們對 redis 的過程有個大致的概念了，其實和我們預(yù)料的也差不多嘛，那下面我們就重點看一下 Redis 字符串用的數(shù)據(jù)結(jié)構(gòu) sds
字符串的底層數(shù)據(jù)結(jié)構(gòu) sds
關(guān)于字符編碼之前說過了，Redis 中的字符串對應(yīng)了三種編碼類型，如果是數(shù)字，則轉(zhuǎn)換成 INT 編碼，如果是短的字符串，轉(zhuǎn)換為 EMBSTR 編碼，長字符串轉(zhuǎn)換為 RAW 編碼。
不論是 EMBSTR 還是 RAW，他們只是內(nèi)存分配方面的優(yōu)化，具體的數(shù)據(jù)結(jié)構(gòu)都是 sds，即簡單動態(tài)字符串。
sds 結(jié)構(gòu)長什么樣
很多書中說，字符串底層的數(shù)據(jù)結(jié)構(gòu)是 SDS，中文翻譯過來叫 簡單動態(tài)字符串，代碼中也確實有這種賦值的地方證明這一點
sds?s?=?o->ptr;
但下面這段定義讓我曾經(jīng)非常迷惑
sds.h
typedef?char?*sds;
struct?sdshdr?{
????unsigned?int?len;
????unsigned?int?free;
????char?buf[];
};
將一個字符串變量的地址賦給了一個 char* 的 sds 變量，但結(jié)構(gòu) sdshdr 才是表示 sds 結(jié)構(gòu)的結(jié)構(gòu)體，而 sds 只是一個 char* 類型的字符串而已，這兩個東西怎么就對應(yīng)上了呢
其實再往下讀兩行，就豁然開朗了。
static?size_t?sdslen(const?sds?s)?{
????struct?sdshdr?*sh?=?(void*)(s-(sizeof(struct?sdshdr)));
????return?sh->len;
}
原來 sds 確實就是指向了一段字符串地址，就相當(dāng)于 sdshdr 結(jié)構(gòu)里的 buf，而其 len 和 free 變量就在一定的內(nèi)存偏移處。
結(jié)構(gòu)與優(yōu)點
盯著這個結(jié)構(gòu)看 10s，你腦子里想到的是什么？如果你什么都想不到，那建議之后和我的公眾號一起，多多閱讀源碼。如果瞬間明白了這個結(jié)構(gòu)的意義，那請聯(lián)系我，收我為徒吧！
struct?sdshdr?{
????unsigned?int?len;
????unsigned?int?free;
????char?buf[];
};
回過頭來說這個 sds 結(jié)構(gòu)，char buf[] 我們知道是表示具體值的，這個肯定必不可少。那剩下兩個字段 len 和 free 有什么作用呢？
敲重點！敲重點！敲重點??！
len：表示字符串長度。由于 c 語言的字符串無法表示長度，所以變量 len 可以以常數(shù)的時間復(fù)雜度獲取字符串長度，來優(yōu)化 Redis 中需要計算字符串長度的場景。而且，由于是以 len 來表示長度，而不是通過字符串結(jié)尾標(biāo)識來判斷，所以可以用來存儲原封不動的二進制數(shù)據(jù)而不用擔(dān)心被截斷，這個叫二進制安全。
free：表示 buf 數(shù)組中未使用的字節(jié)數(shù)。同樣由于 c 語言的字符串每次變更（變長、變短）都需要重新分配內(nèi)存地址，分配內(nèi)存是個耗時的操作，尤其是 Redis 面對經(jīng)常更新 value 的場景。那有辦法優(yōu)化么？
能想到的一種辦法是：在字符串變長時，每次多分配一些空間，以便下次變長時可能由于 buf 足夠大而不用重新分配，這個叫空間預(yù)分配。在字符串變短時，并不立即重新分配內(nèi)存而回收縮短后多出來的字符串，而是用 free 來記錄這些空閑出來的字節(jié)，這又減少了內(nèi)存分配的次數(shù)，這叫惰性空間釋放。
不知不覺，多出了四個名詞可以和面試官扯啦，哈哈?，F(xiàn)在記不住沒關(guān)系，看文末的總結(jié)筆記就好。
上源碼簡單證明一下
老規(guī)矩，看源代碼證明一下，不能光說結(jié)論，我們拿空間預(yù)分配來舉例。
由于將字符串變長時才能觸發(fā) Redis 的這個技能，所以感覺應(yīng)該看下 append 指令對應(yīng)的方法 appendCommand。
跟著跟著發(fā)現(xiàn)有個這樣的方法
/*?Enlarge?the?free?space?at?the?end?of?the?sds?string?so?that?the?caller
?*?is?sure?that?after?calling?this?function?can?overwrite?up?to?addlen
?*?bytes?after?the?end?of?the?string,?plus?one?more?byte?for?nul?term.
?*?Note:?this?does?not?change?the?*length*?of?the?sds?string?as?returned
?*?by?sdslen(),?but?only?the?free?buffer?space?we?have.?*/
sds?sdsMakeRoomFor(sds?s,?size_t?addlen)?{
????struct?sdshdr?*sh,?*newsh;
????size_t?len,?newlen;
????//?空閑空間夠，就直接返回
????size_t?free?=?sdsavail(s);
????if?(free?>=?addlen)?return?s;
????//?再多分配一倍（+1）的空間作為空閑空間
????len?=?sdslen(s);
????sh?=?(void*)?(s-(sizeof(struct?sdshdr)));
????newlen?=?(len+addlen);
????newlen?*=?2;
????newsh?=?zrealloc(sh,?sizeof(struct?sdshdr)+newlen+1);
????..
????return?newsh->buf;
}
本段代碼就是說，如果增長了字符串，假如增長之后字符串的長度是 15，那么就同樣也分配 15 的空閑空間作為 free，總 buf 的大小為 15+15+1=31（額外 1 字節(jié)用于保存空字符）
最上面的源碼中的英文注釋，就說明了一切，留意哦~
其他幾個特性的源代碼，我希望讀者可以自己下載來跟一下，因為最開頭用了大量的篇幅來跟蹤了 set 指令的整個流程，相信驗證其他幾個特性去找源碼，也相對沒有那么恐怖了。
下載不到源碼，或者編譯源碼有問題，或者不知道從何處入手源碼的童鞋，可以公眾號后臺與我交流哦~
總結(jié)
敲重點敲重點，課代表來啦~
一次 set 的請求流程堆棧
建立 socket 鏈接 --> 建立 client --> 注冊 socket 讀取事件處理器 --> 從 socket 讀數(shù)據(jù)到緩沖區(qū) --> 獲取命令 --> 執(zhí)行命令（字符串編碼、寫入字典）--> 響應(yīng)
數(shù)值型字符串一個小騷操作
在選擇整型返回的時候，不是直接轉(zhuǎn)換為一個 long 類型，而是先看看這個數(shù)值大不大，如果不大的話，從常量池里面選一個返回這個引用，這和 Java Integer 常量池的思想差不多，由于業(yè)務(wù)上可能大部分用到的整型都沒那么大，這么做至少可以節(jié)省好多空間。
字符串底層數(shù)據(jù)結(jié)構(gòu) SDS
字符串底層數(shù)據(jù)結(jié)構(gòu)是 SDS，簡單動態(tài)字符串
struct?sdshdr?{
????unsigned?int?len;
????unsigned?int?free;
????char?buf[];
};
優(yōu)點如下：
常數(shù)時間復(fù)雜度計算長度：可以通過 len 直接獲取到字符串的長度，而不需要遍歷 二進制安全：由于是以 len 來表示長度，而不是通過字符串結(jié)尾標(biāo)識來判斷，所以可以用來存儲原封不動的二進制數(shù)據(jù)而不用擔(dān)心被截斷 空間預(yù)分配：在字符串變長時，每次多分配一些空間，以便下次變長時可能由于 buf 足夠大而不用重新分配 惰性空間釋放：在字符串變短時，并不立即重新分配內(nèi)存而回收縮短后多出來的字符串，而是用 free 來記錄這些空閑出來的字節(jié)，這又減少了內(nèi)存分配的次數(shù)。
字符串操作指令
這個我就直接 copy 網(wǎng)上的了
SET key value：設(shè)置指定 key 的值 GET key：獲取指定 key 的值。 GETRANGE key start end：返回 key 中字符串值的子字符 GETSET key value：將給定 key 的值設(shè)為 value ，并返回 key 的舊值(old value)。 GETBIT key offset：對 key 所儲存的字符串值，獲取指定偏移量上的位(bit)。 MGET key1 [key2..]：獲取所有(一個或多個)給定 key 的值。 SETBIT key offset value：對 key 所儲存的字符串值，設(shè)置或清除指定偏移量上的位(bit)。 SETEX key seconds value：將值 value 關(guān)聯(lián)到 key ，并將 key 的過期時間設(shè)為 seconds (以秒為單位)。 SETNX key value：只有在 key 不存在時設(shè)置 key 的值。 SETRANGE key offset value：用 value 參數(shù)覆寫給定 key 所儲存的字符串值，從偏移量 offset 開始。 STRLEN key：返回 key 所儲存的字符串值的長度。 MSET key value [key value ...]：同時設(shè)置一個或多個 key-value 對。 MSETNX key value [key value ...]：同時設(shè)置一個或多個 key-value 對，當(dāng)且僅當(dāng)所有給定 key 都不存在。 PSETEX key milliseconds value：這個命令和 SETEX 命令相似，但它以毫秒為單位設(shè)置 key 的生存時間，而不是像 SETEX 命令那樣，以秒為單位。 INCR key：將 key 中儲存的數(shù)字值增一。 INCRBY key increment：將 key 所儲存的值加上給定的增量值（increment） 。 INCRBYFLOAT key increment：將 key 所儲存的值加上給定的浮點增量值（increment） 。 DECR key：將 key 中儲存的數(shù)字值減一。 DECRBY key decrement：key 所儲存的值減去給定的減量值（decrement） 。 APPEND key value：如果 key 已經(jīng)存在并且是一個字符串， APPEND 命令將指定的 value 追加到該 key 原來值（value）的末尾。
